Introduction
Hash Function
A cryptographic hash function↗ is one of the basic primitives for cryptography. (In this article, the word hash function will mean cryptographic hash function unless otherwise noted.) A cryptographic hash function satisfies the below three secure properties:
- Preimage resistance: Given hash value , it is hard to find any input message that .
- Second-preimage resistance: Given input message , it is hard to find message that .
- Collision resistance: It is hard to find any two different input messages that .
Cryptographic schemes such as digital signatures, message authentication codes, commitment schemes, and authentications are built on top of hash function. For example, the preimage resistance property of a hash function enables the proof-of-work↗ system in cryptocurrency. SHA-2 and SHA-3 are common examples of hash functions, and they are adopted for general purposes.
Usage of Hashes in the ZK protocol
A hash function is also useful in the ZK protocol. One famous example is the membership check in a Merkle tree. For a Merkle root , the prover will claim knowledge of the witness such that
to prove their knowledge of element , which is a member of the Merkle tree. We already discussed this usage in our previous post, “How Does Tornado Cash Work?”.
Traditional uses of hash functions can be utilized in the ZK protocol as well, such as integrity checks using vanilla hash computation, retrieving pseudorandom strings from the fixed length seed, and signing transactions.
Why Are ZK-Friendly Hash Functions Required?
The standardized hash functions such as SHA-2 and SHA-3 are extensively studied, and their security is widely believed. Moreover, traditional software and hardware implementations of them are efficient compared to their competitors.
So when we need to evaluate a hash in ZK protocols, it seems nice to use SHA-2 or SHA-3. However, many ZK protocols are using relatively unfamiliar hash functions such as MiMC↗, Poseidon↗, and Rescue↗ instead of SHA-2 and SHA-3.
The main reason for this is that efficiency in ZK protocols is determined in quite different ways from traditional metrics such as running time, power consumption, and gate count. The efficiency of the circuits in ZK protocols depends on their algebraic structure.
Generally, if the circuit is represented as simple expressions in a large field, it allows efficient proof in terms of prover execution time and proof size. Unfortunately, traditional hash functions are inappropriate for this.
For example, SHA-2 is about 50—100 times more inefficient than ZK-friendly hash functions when the hash is computed in zk-STARK. This huge performance gap demonstrates the need for a ZK-friendly hash function.
In this post, we will introduce several ZK-friendly hash functions that are introduced in famous conferences and journals. It might be fun to focus on the design rationale for each hash function.
ZK Protocols
We first discuss the ZK protocols. Rather than trying to fully understand the protocols, we’ll focus on their high-level characteristics and what the metric is to determine efficiency.
zk-SNARK
zk-SNARK is an acronym that stands for zero-knowledge succinct non-interactive argument of knowledge.
- Zero-knowledge: Verifier learns nothing other than the statement is true.
- Succinct: Proof size and verifier time is sublinear.
- Non-interactive: Needs no interaction between prover and verifier.
- Argument of knowledge: Not only for existence of input but also prover’s knowledge of .
While there are several ways to build a protocol that satisfies the above characteristics, such as linear PCP + pairing-based cryptography↗, constant-round polynomial IOP↗, and polynomial commitment scheme + IOP-based↗, Groth16↗ based on the linear PCP and pairing-based cryptography is the most widely used one.
Groth16 and many other zero-knowledge proof systems such as Aurora↗, Ligero↗, and Bulletproofs↗ are evaluating the circuit in Rank-1 Constraint System (R1CS) form.
R1CS Examples
The R1CS is a system of equations, where each equation is defined by a triplet of vectors such that .
For example, can be interpreted as two equations defined by a triplet of vectors (with intermediate value ):
In the SNARK setting, the cost is determined by the number of constraints in the R1CS. For example, for the constant requires constraints. This implies that and have the same cost in the SNARK setting.
zk-STARK
zk-STARK is an acronym that stands for zero-knowledge scalable transparent argument of knowledge.
- Zero-knowledge: Verifier learns nothing other than that the statement is true.
- Scalable: Prover time is quasilinear; proof size and verifier time is sublinear.
- Transparent: No trusted setup is needed.
- Argument of knowledge: Not only for existence of input but also for prover’s knowledge of .
Any protocol that satisfies the above conditions is called a zk-STARK. However, zk-STARK often refers to the protocol in the paper↗ where the concept was first proposed. We also refer to the protocol in that paper as zk-STARK in this article.
To evaluate the circuits in a STARK setting, the circuit should be transformed into algebraic intermediate representation (AIR).
AIR Examples
We give an example of computing a Fibonacci sequence. The Fibonacci sequence is defined as
The prover wants to prove that . Then an algebraic execution trace (AET), an execution trace of a computation of the Fibonacci sequence, is
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
And the AIR constraints described in the polynomial forms are
Let be a number of rows and be a number of columns in AET. Then the size of the AET is . Moreover, let be the maximal degree of an AIR constraint. In our case, . The efficiency of a zk-STARK is determined by . For each circuit, the efficiency is compared by measuring .
ZK-Friendly Hash Functions
Roughly speaking, the simpler the algebraic representation of a given circuit, the more efficient it is for both R1CS and AIR representations. Therefore, cryptographers began to design structures that were both algebraically simple and still secure. We often called these ciphers as arithmetization-oriented ciphers (AOCs).
For AOCs, most traditional symmetric cryptanalysis such as differential and linear cryptanalysis are generally less relevant. The most powerful attack type for AOCs is algebraic attack, such as Gröbner basis, linearization, GCD, and interpolation attack. Once the designer decides their cipher’s design, the round number is chosen to be safe from those attacks.
On the other hand, this field is relatively new and interesting attacks (see examples one↗, two↗, three↗, and four↗) have been claimed, often resulting in ciphers being broken or parameters being modified, but we’ll talk about those in the next post.
Let’s take a look at the design rationale behind the different AOCs.
MiMC
MiMC↗ is the first ZK-friendly hash function, introduced in ASIACRYPT 2016. Although more efficient ZK-friendly hash functions are suggested after MiMC, MiMC is still widely used in many applications since it is considered mature compared to the other ZK-friendly hash functions.
The design of MiMC is extremely simple: a function is iterated with subkey additions. This concept was already proposed by Nyberg and Knudsen in the 1990s, called KN-Cipher↗.
MiMC-
We first take a look at a block cipher. The block cipher is constructed by iterating rounds, where each round function is described as . In the round function, is a round constant and is a key, and the field is where is a large prime or . The encryption process is defined as
and is fixed to because does not affect security. (If you’re interested, I recommend checking it out for yourself!)
For a field , has an inverse if and only if . Therefore, the author suggested choosing odd for and for prime .
The round constants are not specified in the paper, but is
recommended to be chosen randomly at first and hardcoded into the
implementation. To show nothing up my
sleeve↗ on
the round constants, it is often generated from the SHA-2 (or any other
secure hash functions) digest of certain messages like MiMC0
, MiMC1
,
.
The round number is determined by . For example, the round number for a field . We discuss the reason of this later.
rounds of MiMC-. Images from MiMC paper.
MiMC-
It is also possible to construct a block cipher with the same nonlinear permutation in a Feistel network. The round function of MiMC- is described in the below figure and can be defined as
MiMC- round function. Images from here↗.
For each round, only half of the data is changed; therefore, the number of rounds for the Feistel version is , which is doubled from the number of rounds of MiMC-.
The Hash Function
When the key is fixed at , then the block cipher becomes a permutation. Given a permutation, there is a well-known construction deriving hash functions from a permutation called the sponge framework↗, which is proven secure and used in many other hash functions, including SHA-3↗.
The sponge construction. is input; is hashed output. The unused capacity should be twice the desired collision or preimage attacks. Images from Wikipedia↗.
The sponge construction consists of two phases called absorb and squeeze. In the absorbing phase, the input data is absorbed into the sponge. Afterwards, the result is squeezed out.
The hash function from MiMC is also based on the sponge framework. In the absorbing phase, message blocks are added to a subset of the state, then transformed as a whole using a permutation function (in our case, an MiMC permutation). Note that all the other ZK-friendly hash functions introduced in this post are also based on the sponge framework.
Security Analysis
While interpolation attack, GCD attack, invariant subfields attack, differential cryptanalysis, and linear cryptanalysis are considered in the paper, we will only introduce interpolation attack in here, which provides the lower bound of the round numbers. An interpolation attack constructs a polynomial corresponding to the encryption function without knowledge of the secret key. If an adversary can construct such a polynomial, then for any given plaintext, the corresponding ciphertext can be produced without knowing the secret key.
Let be an encryption function with degree in terms of input . Then with the plaintext-ciphertext pairs, can be constructed using Lagrange’s theorem, and the complexity of constructing a Lagrangian interpolation polynomial is . In our case, degree . By choosing , the degree reaches and the attack becomes infeasible.
SNARK Complexity
Since the single constraint can square the value, there are two R1CS constraints in each round of MiMC permutation:
x2 = xx x3 = x2x
To generate a 256-bits output hash for the 256-bits input , the sponge construction is used. In details, calculate MiMC- of , then left 256-bits are hash value. The round number is chosen as . Then the number of constraints is . Note that field should be chosen as , which means that should not be chosen.
STARK Complexity
In AIR representations, for MiMC-, each row has two variables, and . We denote in -th row as . Then from the round function , the constraint polynomial is defined as
Then the number of rows , the number of columns , and the maximal degree . The efficiency metric is
Implementations
Although the authors suggested as S-box, this S-box is often replaced to other S-boxes such as if . For example, the BN254↗ field is for 254-bits prime , which is . As a result, when using MiMC on the BN254, it is preferred to use or instead of (example 1↗, example 2↗). In this case, the round number is determined as or , which mitigates all the attacks presented so far.
For the round constants, the authors do not specify how to generate them
in the paper. Therefore, each implementation will determine the round
constants by computing the hash value of strings like MiMC0
and
MiMC1
using
SHA-2↗
or SHA-3↗. If
someone creates their own MiMC implementation without disclosing how the
round constants were generated, there might be a potential
vulnerability, such as being susceptible to an invariant subfields
attack.
Poseidon
Poseidon↗ is a yet another ZK-friendly hash function suggested in USENIX 2021. Poseidon is based on the HADES↗ design strategy, which is a generalization of a substitution-permutation network (SPN)↗, suggested in EUROCRYPT 2020.
HADES Design Strategy
SPN is a famous block cipher algorithm. For example, AES↗ uses the SPN structure. By applying enough alternating rounds of substitution boxes and permutation boxes, the attacker is unable to recover a key from plaintext-ciphertext pairs.
HADES is composed of three steps: Add Round Key, SubWords, and MixLayer.
This seems to be the same approach with SPN, but the main difference between the existing SPN and HADES is that some S-box layers in HADES are partial S-box layers, which means that a single S-box is applied for the rightmost element and identity is applied for the others. The author argued that this would reduce the R1CS or AET cost.
Poseidon Hash Function
The Poseidon hash function follows the same construction as HADES, with replacing Add Round Key to Add Round Constants. Poseidon only considers the prime field . Let be the number of words in each layer (to avoid confusion with the number of rows in STARK, we use instead of unlike the notation in the paper). The graphical overview is shown below.
Construction of Poseidon. is the number of the full S-box rounds, and is the number of the partial S-box rounds. Images from Poseidon paper.
The S-box is defined by , where is the smallest positive integer that satisfies .
The purpose of the linear layer is to spread local changes onto the entire state, so usually the linear layer is chosen as an MDS matrix↗, and its effects are negligible on the cost. In Poseidon, the linear layer is a Cauchy matrix↗, which is defined by for the entries of and are pairwise distinct and , where and . This was an original suggestion in Poseidon; however, some Cauchy matrixes are insecure if there is an invariant subspace trail. We omit the details of the attack. The interested reader may refer to the paper↗. Therefore, the linear layer should be carefully chosen to avoid this type of attack.
The structure is highly parameterizable, and the suggested parameters for a 256-bits output hash are for an over with 256-bit . is chosen to prevent statistical attacks, and is chosen to prevent algebraic attacks.
SNARK Complexity
For , S-box is represented by three constraints:
x2 = xx x4 = x2x2 x5 = x4*x
And the total S-box number is . Therefore, the total number of constraints for is . For , it requires R1CS constraints.
STARK Complexity
If we maintain variables for each round, then the number of rows is , the number of columns is , and the maximal degree is . Then the efficency metric is . However, this AET representation does not take advantage of partial S-box rounds. Instead of this, by treating every S-box output as a variable, the number of rows is , the number of columns is , and the maximal degree is still . For , the efficiency metric is .
Vision / Rescue
Vision / Rescue↗ are ZK-friendly hash functions following the Marvellous design strategy. They are suggested in FSE 2020.
Marvellous Design Strategy
Marvellous design is a substitution-permutation network parameterized by the tuple :
- : The field is , with either a power of or a prime number,
- : The state is elements in ,
- : The S-boxes,
- : An MDS matrix↗,
- : The first step constant, and
- : The desired security level.
In each round of a Marvellous design, a pair of S-boxes is used alternately. The difference between and is in their degree. For one, should be chosen with a high degree when evaluated forward and a lower degree when evaluated backward. The other S-box, namely , is chosen with the opposite goal, meaning that it has a low degree in the forward direction and a high degree in the backward direction. This choice has three benefits:
- No matter which direction an adversary is trying to attack, the degree is guaranteed to be high.
- It results in the same cost for the encryption and decryption functions.
- Owing to nonprocedural computation, the low-degree representation of each S-box can be evaluated efficiently.
For Vision / Rescue, is obtained directly from : .
The linear layer is chosen by the Vandermonde matrix↗. As described in Poseidon, there is no security claim related to the Vandermonde matrix, and any other MDS matrix should be fine.
The one interesting thing that differentiates the Marvellous from the others is that it uses a heavy key schedule. In MiMC and HADES, there is no special key schedule and the master key is added for each round. However, in Marvellous, the key schedule reuses the round function. The author claimed that this is a kind of security margin as the domain of AOCs is relatively new. Note that a heavy schedule does not affect the efficiency of hash functions from fixed-key permutations because every subkey is derived in the offline phase.
Vision
Vision is meant to operate on binary fields with its native field . To construct the S-boxes, we select degree , which we denote by . More precisely, there are no terms in : . Then is linearized on and it gives benefits for other computation settings such as MPC↗. However, it is irrelevant with the SNARK/STARK setting, so we don’t discuss it any further.
After is chosen, and is and .
Finally, the number of rounds is doubled for the longest reaching attack, which means a 100% safety margin is added, and the round number varies from 10 to 16.
A single round (two steps) of Vision. Images from Marvellous paper.
Rescue
The second family of algorithms in the Marvellous universe is Rescue. To build the S-box, the smallest prime such that should be found. Then the S-boxes are set to be and . The number of rounds is doubled for the longest reaching attack, as in Vision and the round number it varies from to .
A single round (two steps) of Rescue. Images from Marvellous paper.
SNARK Complexity
For Vision, we should consider both inverse mappings and --- is analogous with . First, for , let . Then if , then , and if , then . Putting this together, we get the necessary and sufficient condition that and . It is represented by three constraints:
z = xy eq1 = x(1+z) eq2 = y*(1+z)
Second, for , it is represented by two constraints because its degree is :
x2 = xx x4 = x2x2
Note that only and are evaluated, and is not yet derived. However, this does not matter because the structure of R1CS allows us to multiply and add variables by a constant later.
A single round consists of two steps, and constraints are added for each step. Therefore, the number of total constraints is for the round number . From the recommended parameters , the number of constraints is .
For Rescue, only and are nonlinear operations, and for , each and requires two constraints, as we saw in MiMC. Therefore, constraints are added for each round, and the total number of constraints is for the round number . From the recommended parameters , the number of the constraints is .
STARK Complexity
For Vision, the author presents an AIR with for each step. The first elements correspond to the original state (say ) and the last elements are stored auxiliary values (say ). For the first cycle, if , and otherwise. We denote the value corresponding to for the next row as . Our goal is to make . Then by setting the below constraints, the values of and are verified to be correct.
For the second cycle, . Then and are verified by the below constraints:
When the round number is , . From the recommended parameters , the efficiency metric is .
For Rescue, no auxiliary values are required. Moreover, it is possible to combine and in one equation. Therefore, for rounds, . From the recommended parameters , the efficiency metric is .
Conclusion
In this article, we’ve discussed the design rationale and performance of various AOCs. There are more AOCs that we haven’t mentioned, such as GMiMC, Jarvis, and Friday, but their design rationale follows similar principles to the ones we’ve covered.
The overall SNARK and STARK performance is shown below.
AOC | R1CS(SNARK) | AET(STARK) |
---|---|---|
MiMC | 628 | 1944 |
Poseidon | 276 | 425 |
Vision | 360 | 576 |
Rescue | 264 | 207 |
As you can see on the table, Rescue has competitive results in both SNARK and STARK. In fact, STARKWARE also recommended Rescue from the STARK-friendly hash in their own survey↗.
In recent years, the hash functions 2-3x more efficient than Rescue in SNARK settings are proposed: Anemoi↗ and Griffin↗. They are not yet fully peer-reviewed and need to be validated by academics and industry, but their overwhelming performance means that they can be considered for use once they are matured.
Meanwhile, the algebraic simplicity of AOCs often allows attackers to attack ciphers. Therefore, it is recommended to use ciphers that have been published and proven to be reliable over time rather than using them based on their efficiency alone. In the next article, we’ll cover algebraic attacks on AOCs.