Presenting zekrom: a library of arithmetization-oriented constructions for zkSNARK circuits. Part 1: arkworks-rs

zekrom is an open-source library of arithmetization-oriented constructions for zkSNARK circuits. It was created as part of the MSc thesis work of Laurent Thoeny on the Kudelski Security Research team. The goal of zekrom is to analyze the performance of novel constructions for circuits using modern libraries such as arkworks-rs and Halo2. In this post we describe zekrom for arkworks-rs, which provides the Griffin, Neptune and Rescue Prime hashing constructions. Further, it includes the authenticated-encryption Ciminion primitive and the respective AE constructions of Neptune and Griffin using the recently proposed SAFE API.

Introduction

zkSNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) allow us to convince someone that a particular statement is true without revealing any information about it. They typically fit in areas where the accountability and compliance of a party, not generally trusted, need to be demonstrated.

There are many areas that can benefit from zkSNARKs. In the field of finance, zkSNARKs have been proposed for reporting portfolio holdings to employers, pooling information from investors in a private manner, for private blind real state auctions, and more generally, for private regulatory solutions. Further, zkSNARKs are popular in digital payments applications, supporting private transactions (for instance in the Zcash network) and for scaling distributed ledgers by compressing their size.

Other areas where zkSNARKs has been proposed are related to e-voting, machine learning, for proving that a certain vulnerability exists, and for detecting disinformation.

This type of solutions are typically implemented using building blocks such as Merkle tree proofs, private set intersection protocols, and hashing, encryption and authenticated-encryption primitives optimized for zkSNARKs circuits.

Why zekrom ?

In the past, we have described how to implement arithmetization-oriented construction in DSLs for circuits such as Circom, Aleo and gnark. This time, we focus on Rust-based modern libraries for designing circuits such as arkworks-rs and Halo2. In so doing, we implement recent proposals for hashing such as Rescue Prime and Neptune and explore the SAFE API to obtain authenticated-encryption using novel permutations and the sponge construction.

There are different proving systems that were proposed in recent years (Groth16, Marlin, PLONK, Halo, Gemini, etc.) with their primary objectives being: reducing the size of the proof, reducing the proving/verifying time and minimizing the need for a trusted setup.

Further, there are different ways to implement zkSNARKs, but the common idea behind all of them is that the construction has to be represented in an arithmetic circuit on top of a finite field. This is possible using the newest domain specific languages such as Circom or Leo, or using a library such as gnark, Halo2 or arkworks-rs.

In the aforementioned applications, sometimes encryption and hashing algorithms are needed. However, the performance of traditional designs such as SHA256 or BLAKE2 is not optimal in circuits (mainly because operating on bits is more costly than operating on field elements). This has led to the appearance of arithmetization-oriented constructions, new designs which have a better performance in both in native architectures and in circuits. Our reasons for creating zekrom are threefold:

In many cases, the performance of arithmetization-oriented schemes is analysed on the basis of a theoretical number of constraints that will be used to represent them in the targeted proof system. This approach doesn’t take into consideration the possible difficulties when implementing the scheme for a specific proving system. They are typically not implemented in either a domain specific language or a state-of-the-art library. Another issue is that, with the existing libraries, the newest schemes are not provided (for example, Poseidon in Halo2 , Poseidon and MIMC in circomlib). Therefore, there is a need to implement them to further study their performance.
This type of constructions typically require generation of parameters for their implementation. In an effort to help practitioners, we provide code that can help to generate those parameters.
By providing a generic implementation of the SAFE API we can support novel permutations designed in the future and compare their performance for hashing and authenticated-encryption with other proposed constructions.

The constructions

We have already described Griffin and Ciminion in the past.

Rescue Prime: It utilizes the Rescue-XLIX permutation in the case where the sponge state has a size of three field elements. The non-linear layer is performed via a power map: this is done once with a small value of $\alpha$ and subsequently with its inverse $\alpha^{-1}$ . Secondly, an MDS matrix is used as the linear layer and finally, in order to differentiate each round, round constants are added to the state.

Neptune: proposed by Grassi et al. in 2021, Neptune is a new design based on the study of the widely used Poseidon hash function. It slightly modifies the number of rounds while taking the same approach of internal and external rounds in the permutation. However, the design of both rounds is modified in order to improve the multiplicative cost of the permutation. First, the MDS matrix is different in the external rounds Second, the an $S$ layer applies the $S'$ function on two elements of the state, where $S(x_0, x_1, x_2, x_3 ) = S'(x_0, x_1 ) ||S'(x_2 , x_3)$
where $S' (x0 , x1 ) = y_0 || y_1$ such that
$y_0 = 2 \cdot x_0 + x_1 + 3 \cdot (x_0 - x_1 )^2 + (\gamma + x_0 - 2 \cdot x_1 - (x_0 - x_1 )^2 )^2$ and $y_1 = x_0 + 3 \cdot x_1 + 4 \cdot (x_0 - x_1 )^2 + (\gamma + x_0 - 2 \cdot x_1 - (x_0 - x_1 )^2 )^2$ .

This specific design of the external $S$ layer is what allows Neptune to reduce its cost compared to the easy external layer of Poseidon that required $t$ power maps.

The SAFE API

The Sponge API for Field Elements (SAFE) is a universal API proposal by Khovratovich et al. designed to unify the design of cryptographic primitives using permutations. It uses field elements instead of bits, in order to create different cryptographic primitives from a permutation via the regular sponge mode or using a variant of the duplex mode.

Example of sponge, absorbing 4 message elements and squeezing 3 output elements. Source: https://www.iacr.org/authors/tikz/

The SAFE API removes the need for a padding scheme, at the cost of requiring the input to be of known length, by using the IOPattern, a way to declare the calls to the sponge.

SAFE is used via four different calls:

START: Initializes the state of the sponge using a hash of both the IOPattern and
an a domain separator.
FINISH: It is called when the sponge job is finished, it erases the memory an verify that the pattern was properly executed.
and 4: ABSORB(n), SQUEEZE(n) are used to either add elements to the sponge or retrieve information from it.

For instance, in order to hash a message of 4 elements and produce a hash of length 1 field element, we would do: START, ABSORB(4), SQUEEZE(1), FINISH(). Further, we can use the duplex mode of the sponge in order to perform authenticated encryption.

An example circuit using zekrom for arkworks-rs

We can use the Neptune construction provided by zekrom for proving the knowledge of a hash preimage in the following circuit:

use ark_ff::PrimeField;
use ark_r1cs_std::{
    fields::fp::FpVar,
    prelude::{AllocVar, EqGadget},
};
use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, SynthesisError};

use crate::{
    api::{Sponge, SpongeAPI},
    common::pattern::gen_hash_pattern,
};

use super::chip::*;

#[derive(Clone)]
pub struct NeptuneHashCircuit<F: PrimeField> {
    pub sponge: Sponge<NeptuneChip<F>>,
    pub message: Vec<F>,
    pub hash: F,
}

impl<F: PrimeField> NeptuneHashCircuit<F> {
    /// Use the sponge to compute the hash of a message
    ///
    /// It takes a message composed of blocks where a block is a field element in F
    /// It returns a hash composed of one element in F
    /// This prototype could be extended to support larger digest size easily
    /// It follows the [SAFE API specification](https://hackmd.io/bHgsH6mMStCVibM_wYvb2w)
    pub fn hash(self, message: &[FpVar<F>]) -> Result<FpVar<F>, SynthesisError> {
        let pattern = gen_hash_pattern(message.len(), 1);

        let mut sponge = self.sponge;

        sponge.start(pattern, None);
        sponge.absorb(message.len() as u32, message);
        let hash = sponge.squeeze(1)[0].clone();
        let res = sponge.finish();
        assert!(res.is_ok(), "The sponge didn't finish properly!");

        Ok(hash)
    }
}

impl<F: PrimeField> ConstraintSynthesizer<F> for NeptuneHashCircuit<F> {
    fn generate_constraints(self, cs: ConstraintSystemRef<F>) -> Result<(), SynthesisError> {
        let mut v = Vec::with_capacity(self.message.len());

        for elem in self.message.iter() {
            v.push(FpVar::new_witness(cs.clone(), || Ok(elem))?);
        }
        let hash = FpVar::new_input(cs, || Ok(self.hash))?;
        let result = self.hash(&v)?;

        result.enforce_equal(&hash)?;

        Ok(())
    }
}

Generating new parameters

Typically, arithmetization-oriented constructions require to generate different parameters prior to the implementation and deployment of the primitive. In order to help practitioners to generate them, we have added different helper functions in parameters.sage.

Griffin

The round constants, $\alpha$ and $\beta$ parameters for a prime $p$ can be obtained via:

def get_params_griffin(p, seed, m, n):
    shake = SHAKE128.new()
    shake.update(bytes("Griffin", "ascii"))
    for v in seed:
        shake.update(bytes(v));
    consts = get_n_random_elements(p, n*m, shake)
    alpha, beta = get_alpha_beta(p, shake)
    return alpha, beta, consts

Neptune

The round constants for Neptune for a prime $p$ , can be obtained via:

def get_round_constants_neptune(p, seed, m, n):
    shake = SHAKE128.new()
    shake.update(bytes("Neptune", "ascii"))
    for v in seed:
        shake.update(bytes(v))
    consts = get_n_random_elements(p, n*m, shake)
    gamma = get_random_element(p, shake)
    int_matrix = get_n_random_elements(p, m, shake)
    return consts, gamma, int_matrix

Further, the number of external and internal rounds for a power map exponent $d$ , a prime $p$ , $t$ field elements and s security level can be obtained via:

def get_nb_rounds_neptune(d, p, t, s):
    re = 6    
    ri_p_1 = ceil((min(s, math.log(p,2)) - 6)/math.log(d, 2) + 3 + t + log(t, d))
    ri_p_2 = ceil((s/2) - 4*t - 2)
    
    return re, ceil(1.125 * max(ri_p_1, ri_p_2))

Ciminion

The round constants for n rounds Ciminion can be obtained via:

def get_round_constants_ciminion(p, n):
    shake = SHAKE256.new()
    shake.update(bytes(f"GF({p})", "ascii"))
    return get_n_random_elements(p, 4*n, shake, True)

Rescue Prime

The round constants can be generated for a prime $p$ , sponge capacity, security level and rounds via:

def get_round_constants_rescue(p, m, capacity, security_level, n):
    shake = SHAKE256.new()
    shake.update(bytes("Rescue-XLIX (%i,%i,%i,%i)" % (p, m, capacity, security_level), "ascii"))
    return get_n_random_elements(p, m*n, shake)

The number of rounds can be estimated via:

def get_number_of_rounds_rescue(p, m, c, s, d):
    r = m - c
    def dcon(N): return floor(0.5 * (d-1) * m * (N-1) + 2)
    def v(N): return m*(N-1)+r
    target = 2 ** s
    for l1 in range(1, 25):
        if binomial(v(l1) + dcon(l1), v(l1)) ** 2 > target:
            break
    return ceil(1.5*max(5, l1))

Performance analysis

In order to obtain a fair comparison on the performance of the hashing and authenticated-encryption primitives, we have obtained the required number of R1CS constraints for every construction.

In arkworks-rs, the field exponentiations by the inverse of $d$ , seem to be responsible of the increasing number of R1CS constraints in Rescue Prime and therefore, we can expect a worst performance in proof generation in proving systems such as Groth16 and in the overall operations in Halo2.

The Neptune improvements over the Poseidon hash provide the best overall performance in arkworks-rs, both for hashing and AE operations using the SAFE API.

Where to find zekrom for arkworks-rs

You can download the implementation for arkworks-rs at https://github.com/kudelskisecurity/zekrom-arkworks.

Stay tuned for the second part of this blog post, comprising Halo2 and the Reinforce Concrete hashing construction.