Zero-Knowledge is a programmable cryptography that is being layered on top of arbitrary computations. 

Computational proof system is a marvelous innovation of the 19th century. It provides computational integrity which means that the output of a certain computation is correct. As described by Eli Ben-sasson in his talk, they have emerged just like the cambrian explosion in the field of cryptography. In my opinion the major dilemma we are facing today is the gap between academia and the implementation industry in the field of cryptography. This series is going to be a comfort catalyst for software engineers who are coming from the background of programming with little to no knowledge about the cryptography realm.

In general a CI proof system can help us solve the two fundamental problems of blockchain technology: Privacy and Scalability. It is the property of a proof system such as SNARK to succinctly verify a system by performing exponential compressing over the amount of computation that is needed to verify the integrity of a large batch of transactions such as zk-rollups. On the other hand, privacy can be achieved by hiding some inputs of computation without compromising the integrity of data(e.g Zcash and Tornado Cash). Without further ado let's dive into some alluring cryptographic techniques that have been getting used in blockchain technology and are salient for zero-knowledge proofs. 

Cryptographic Proofs

What is Zero-Knowledge Proof (ZKP)

A Zero-knowledge proof is a protocol between a Prover and Verifier, which allows a prover to convince a verifier that a certain statement is true without revealing anything more than the integrity of the statement itself. 

The statement could be represented as a NP relation R(x,w): y= F(x,w) where x is a public input by the verifier and w is a witness, acts as a private input by the prover. The relation R defines a computational function F that takes both x and w as inputs and produces an output y. The goal of the prover is to convince the verifier that a valid witness w exists such that F(x,w) equals y, without revealing any information about w apart from its validity.

Its soundness property will make sure that the malicious prover with forged witness will never be able to convince the verifier with high probability. 

Background

In zero-knowledge proofs (ZKPs), the interaction between the prover and verifier follows a specific protocol to achieve the goal of proving a statement without revealing unnecessary information. For example in PCPs:

• The prover commits to some data by applying a commit function and generates a lengthy proof. This proof is divided into multiple instances or elements.

• The verifier randomly selects points or instances from the proof and sends them to the prover.
• The prover performs computations on the selected points using the committed data and provides a proof of evaluation as a response. This proof demonstrates the correctness of the computations.
• The verifier, without conducting redundant computations, checks the proof of evaluation provided by the prover to determine its correctness.

Note: The protocol could be Interactive such as schnorr protocol but in blockchains we mostly use non-interactive zero-knowledge proofs such as SNARKs and STARKs.

Process of Constructing a ZK Proof

In zero-knowledge proofs (ZKPs), the statement we aim to prove is commonly represented over an arithmetic circuit. While the topic can be complex, I will provide a concise summary of the process involved. In subsequent posts, we will explore this in greater detail to ensure a comprehensive understanding.

• For a problem statement we first define the inputs, outputs and properties of the proof. 
• Next we choose a suitable ZKP scheme depending on the requirements such as Bulletproofs, SNARKs, STARKs. Each scheme has different trade-offs in terms of proof size, verification time, and setup complexity.
• We then express the problem as a Boolean circuit or arithmetic circuit, depending on the nature of the computation. The circuit represents the logical or arithmetic relationships between inputs and outputs. Also we break down complex operations into elementary gates or arithmetic operations.
• Next we map our data to constraints, what that means is we assign variables to each input and intermediate value in the circuit. It is to convert the problem's constraints into a set of equations that must hold for a valid computation. These constraints ensure that the circuit is properly constructed and that the desired properties are satisfied.
• Now we transform the circuit's constraints into polynomial form using techniques like the Rank 1 Constraint System (R1CS) or Arithmetic Span Programs (ASPs). Assign polynomials to the variables and encode the constraints as polynomial equations or inequalities.
• For a proof to be constructed, a witness is a must. The witness contains the values of all the variables in the circuit for a specific input. It demonstrates that the input satisfies the constraints and represents a valid computation. The witness is usually generated by the prover and most of the time represented as the coefficients of the polynomial.
• Prover then evaluates the polynomial at specific points (e.g., using the Fast Fourier Transform) to generate evaluations. These evaluations represent the commitments to the polynomials and are used during the proof generation and verification phases.

Also note here that every ZKP scheme uses their own method of generating constraints. Some may use algebraic equations and others may rely on boolean circuits. The degree of the polynomials constructed within a ZKP scheme can also vary based on the complexity of the computation and the desired level of security. 

Now again, I would repeat that if you didn’t understand the process then, there is no need to panic. We will discuss all of these comprehensive topics shortly in this series.

Fundamentally,now to believe that these ZKPs are secure we should try to understand the security behind them which are often termed as “Cryptographic Primitives”. These primitives are based around the computational hardness assumption– which is: how difficult it would be for a malicious party to break these proof systems. For this we need a numerical procedure which is easy for one direction and harder for the other direction, often termed as “one way function”. For example, logarithms are simple to calculate over all integers but can become hard to compute when it can introduce a modular reduction.

Cryptographic Assumptions

“Privacy is important, not just as a matter of ideology, but as a matter of mechanics”

The major theoretical distinguishing factor among ZKP systems is whether their security depends on symmetric or asymmetric primitives such as signature and commitment schemes. Here is the glimpse of the proof system that exists with different cryptographic assumptions. 

Symmetric Primitives

Symmetric assumptions include CRH functions such as BLAKE and SHA2. In symmetric primitives we assume the notion of collision resistant hash functions(CRH) which are pseudorandom and behave like a random oracle. While Asymmetric primitives include things like hardness of solving the discrete logarithm problem modulo a prime number, an RSA modulus, or elliptic curve group are some of the exotic variants of such problems, like the “knowledge of exponent” assumption etc. They all behave like one-way functions which is our desirable property for proof systems in ZK. Cryptographic schemes such as digital signatures, commitment schemes, and authentications are built on top of these one-way functions. Let’s define a notion of hash function.

A hash function should fulfill the following properties.

1. Preimage resistance: Given a value of hash h, it is hard to find the original message of the hash that f(m) = h.
2. Collision Resistance: It is hard to find two different messages such that m₁, m₂ implies to f(m₁) = f(m₂).

Hash Functions in Zero-Knowledge

In zero-knowledge protocols, hash functions play a crucial role in ensuring the security and privacy of the communication between the prover and verifier. For example commitment schemes, where the prover commits to certain values without revealing them immediately. Hash functions help to hide the actual values being committed to while still allowing the verifier to verify the commitment. One famous example is the membership check in a Merkle tree. Where hash functions generate commitments by hashing the values or polynomials and producing fixed-size commitments that can later be verified. 

Supposedly we wanna commit to a transaction hash by performing these steps:

1. Sign transaction h = H(k,m), where k is a secret
2. Add h to Merkle tree T
3. Prove : h ∈ T and h = H(k,m)

We first express our data in the form of a  polynomial P(x) and then we commit to it. This committed data represents each index or leaf of a Merkle tree.

C=\sum _{\, \, \, \, \, \, \, \, \, \, \, \, \,\, \, \, \, \,  \, \, i=0}\, \, \, ^dp(x_{i})

Now to generate the root hash of the committed values we could use zk-friendly hash functions.   

C\, \, _{hashed}=\, hash(C,\, randomness,\, parameters)

Why Do We Need ZK-Friendly Hash Functions?

The obvious question here lies that why can’t we use traditional hash functions in zero-knowledge? Such as SHA256 and BLAKE which are super fast when performing bitwise operations on typical CPUs. There are two obvious reasons for it. 

• The circuit implementation of SHA256 is quite long and the prover has to perform a lot of bitwise operations in a circuit. This is expensive and complicated as well as the verifier has to verify every computed bit. Since the statement will only be true if all the bits are computed correctly.
• The traditional hash functions could be Snark compatible, however, they will not act as ZK-friendly hash functions, such as MIMC and Poseidon because they are designed to minimize the number of intermediate values that need to be computed during the hashing process hence low circuit complexity. 

ZK Based Hash Functions

A hash function that is suitable for ZK based architecture should be able to express itself as a circuit over some field. This is important because we want to perform arithmetic operations on hash functions such as:

H(a)+H(b)=H(c) or H(a)*b)=H(c)

This is not possible with regular hash functions such as SHA3. Also some hash functions, including Poseidon, have useful algebraic properties that can be leveraged in certain cryptographic constructions or protocols. For example, Poseidon's use of a sponge construction makes it adaptable to various input sizes. In ZKp, a hash function typically could be made of a sequence of hashes.

H(. . .H(H(H(w_{0},w_{1}), w_{2})w_{3})
...,w_{r-1})=y

Where wi’s are the private inputs of the prover while H and y are known and agreed upon by the prover and verifier.  So, the properties we are looking for in a hashing algorithm are:  

• The hash function should operate in a big finite field e.g field of 256 bits.
• Equipped with only addition, multiplication operations and potentially look-ups.
• Low arithmetic complexity (constraints, polynomial degrees).
• Cryptographic security.

We have multiple hash functions available but these are the most prominent ones. For the sake of this post, we will understand the general construction of Poseidon hash functions which is the widely used cryptographic primitive for ZKPs. 

Poseidon Hash Function

The hash function POSEIDON which maps strings of data over F_p(for a prime p ≃ 2³¹) to a fixed length output field F _p^o. Poseidon hash function is made up of a sponge construction with the poseidon permutation. So what is exactly the sponge construction?

The Sponge Construction

All the above listed hash functions are based on sponge construction. It is a method similar to symmetric cipher and can be used to encode arbitrary length messages. However, as per ZKPs, our main concern is not encoding rather the input M and hash instance both must be either part of the arithmetic circuit for a NP statement or a Merkle tree.  

The sponge construction can be efficiently parallelized, meaning that multiple independent computations can be performed simultaneously. In ZKPs, this property can be leveraged to perform many calculations in parallel, leading to faster proof generation and verification times. Also When implemented in hardware or used in certain cryptographic protocols, the sponge construction can have low circuit depth, making it suitable for zk-SNARKs and other ZKP systems that require efficient computation.

To understand how it works consider a tuple t=r+c. The sponge poseidon permutation takes a tuple of size t, applies a series of fixed length t permutations and outputs a digest r elements in a field F^r. The input message M=[m ₁ | m ₂ | m ₃ |. . .|] is padded such that |m _i|=r. After each permutation a part of message | m _i | is absorbed into the permutation function. 

Essentially, a function f  is used repeatedly in two phases, absorbing and squeezing. The message M is divided into multiple M (m ₀, m ₁, m ₂, m ₄) and padding is applied to make it up to the r bits. The c is irrelevant here and is used for the security purpose. 

• In the absorbing phase,  small chunks of the input data are mixed into the beginning of the buffer using XORs. This updated buffer value is then passed through f and the process continues. With each step a small amount of input data (the bit-length of r) is "absorbed" into the buffer and then it uses f to semi-randomize the entire buffer. For example, the f function is applied on the input t=[m _i ⨁ r _i]. The permute block f outputs t elements which undergo further permutation after addition with the next message:t=[m _i+1 ⨁ r _i+1], and so on. Once all m _i are exhausted, the sponge design switches to the squeeze phase.

• In the squeezing phase, the same process is repeated but instead of XOR-ing the first r bits with data, they are extracted as the next r bits of the output. The output at the end of the absorb phase has already reached the uniform distribution. In the squeeze phase, the user can determine the number of output blocks, and for each block the first r elements are outputted as the digest, followed by another permutation f until the number of output blocks is reached.

Moving forward, we now know the working of sponge construction, however we are still unsure about the function f, inside the construction. This is a permutation function inside sponge construction which stores the updated state and gives us this digest r.

Permutation Function Based on Hades Design

Permutation Function

Random permutations and random functions are only theoretical bases upon which cryptographic security is measured. The only difference between pseudo random functions and pseudo random permutations is that PRFs may output any number of bits whereas PRPs give output of the same number of bits as input. 

For a permutation function we instantiate a hash by a parameter triple (t,p,S) which sets the prime field, security level and size of internal state t.

• The prime field modulus p: in bit size n= log ₂ (p)
• Security level S=log ₂ (√p)min(r,c)
• The width t=len(input)+len(output)=len(input)+[2S/log ₂(p)]

We will represent all the intermediate states of hash by the variable: 

state[i], ∀ i=0,1, . . .  ,t-1 

Computations on the other hand consists of sequential operations referred to as the round function. At the end of all the rounds R the hash function outputs the digest element (refer to the sponge construction diagram).

Round Function

Cryptographic permutations usually consist of an efficient round function which is applied sufficiently many times in order to make the permutation behave like a randomly drawn one. From the above diagram we could clearly understand that inside the sponge construction the same permutation function is getting applied in multiple rounds.

In general, the same round function is used throughout the permutation, in order to destroy all of its possible symmetries and structural properties. However, in HADES we consider different round functions within the same construction. 

More precisely, we mix rounds with full S-box layers and rounds with partial S-box layers. The motivation to have different types of rounds is that full S-box layers are expensive in ZK proof systems but are a good protection against statistical attacks, whereas partial layers are relatively cheap but are, in some cases, similarly good as full ones against algebraic attacks.

Construction of HADES-based Poseidon permutation

Now to achieve the ease of performing arithmetic operations in Poseidon we use Hades design, which is constructed to minimize the number of field operations required during hashing. For example “Linear Mixing” and “Sparse S-Box”.

 Each round function of our Poseidon permutation consists of the following three components.

1. AddRoundConstants(ARC(.))
2. SubWords(S-box or SB(.))
3. MixLayer(M(.))

While ARC(·) and M(·) are the same in each round, the number of S-boxes is not the same.

The HADES design consist of R _full rounds in the beginning, in which S-boxes are applied to the full state. After these rounds,  R _partial rounds in the middle contain only a single S-box in each round, and the rest of the state goes through the nonlinear layer unchanged. Finally,  R _full rounds at the end are applied by again using S-boxes for the full state.

The number of rounds in Poseidon is carefully chosen to strike a balance between security and efficiency. More rounds generally increase security, but they also increase the degree of the polynomial. Poseidon uses a relatively small number of rounds, which keeps the degree low while still providing a strong level of security.

1- Non-Linear Addition of Round Constants(ARC)

This is simply t field additions of the state with that round’s constant RoundConstants. By adding round constants in each round, Poseidon introduces an additional source of randomness and diffusion. 

state= state ⨁ RoundConstants _j

The round constant is  the actual public key which is usually injected into each round. Given the triplet (t,p,S) keys are generated usually in a deterministic way.

2- Non-Linear Layer (S-box)

Non-linear layers consist of power maps that are specifically designed to increase the degree of elements. Why we need it we will discuss in the further post of this series, but for now you could assume that What it means is to choose a substitution box(S-box) to raise the non-linearity mapping between inputs and outputs, to provide confusion in data. The S-box is chosen as the power map:

π ₀: x →x ^a

Where >3 is usually chosen as the smallest integer that guarantees invertibility and provides non-linearity.  is the smallest possible integer that satisfies: gcd(α, p-1)=1.

3- Linear Layer (Mix Layer)

During the linear mixing step, the sponge state undergoes a matrix multiplication to mix its elements. This linear mixing increases the security of the hash function. 

state= state × M

How is Poseidon ZK-Friendly?

Poseidon is designed based on the sponge construction, which is a versatile cryptographic framework. It allows efficient parallelization of computations for GPU-based computing environments. It is designed to have a low degree of intermediate computations during its hashing process. Low-degree intermediates reduce the complexity of zero-knowledge proofs and contribute to the succinctness of the proofs generated using Poseidon. 

Poseidon Implementation

A circuit is a huge mathematical expression used by the system to calculate the outputs and the proof of computation. There is no doubt that circuits can be complex but thanks to libraries and circuits programming languages that make it easy for us to write our own circuits. For the sake of simplicity we will use a domain specific language called “Circom” to define our circuit.

Circom is written in Rust. To install it, you have to install the Rust environment with the following command:

curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh

After the Rust installation, clone the Circom repo and build the compiler:

git clone https://github.com/iden3/circom.git

cd circom

cargo build --release

cargo install --path circom

Now we need Circomlib which is a programming library with some predefined circuits. 

npm init

npm i circomlib

Now, everything is ready to create our circuit. Here’s what that looks like:

pragma circom 2.0.0;

include "node_modules/circomlib/circuits/poseidon.circom";

template PoseidonHasher() {
signal input in;
signal output out;

component poseidon = Poseidon(1);
poseidon.inputs[0] <== in;
out <== poseidon.out;
}

component main = PoseidonHasher();

I have taken a simplest example where we have a private input and a single output signal. We have used a poseidon hash function for circomlib to generate the input hash. Next we compile the circuit by the circom compiler that will generate a wasm and an r1cs file.

circom poseidon_hasher.circom --wasm --r1cs -o ./build

Now oftentimes to generate proof we need some multiparty computation ceremony which we will discuss later but nevertheless we have our constraints generated from the provided circuit in the build folder.

Applications of Poseidon Hash Function

Poseidon hash function has many applications in zero-knowledge proofs (ZKPs), including:

• Merkle Trees:  Poseidon enables the construction of efficient Merkle trees, for data integrity verification in ZKPs.
• zk-SNARKs and zk-STARKs: Poseidon serves as a foundational component in these ZKP systems, providing cryptographic primitives like hash functions and permutations that are essential for secure and efficient proof generation.
• Commitments and Verifiable Delay Functions: Poseidon serves as a cryptographic commitment scheme and is used in ZKPs for secure value binding and verifiable delay functions.

TL;DR

In this post, we explored the concept of zero-knowledge proofs and their relevance in the blockchain realm. We delved into the basics of ZK cryptography, including its fundamental principles. Additionally, we examined the Poseidon hashing scheme and how it is constructed. In the next post, we will shift our focus to asymmetric cryptography primitives and their construction. Stay tuned for more!