Intro to ZKP and ZK-Snarks:

Zero Knowledge Proofs (ZKPs) are a game-changing cryptographic tool that enables one party to prove to another that they have certain information, all without revealing the information itself. By using a proof where the validator verifies the truthiness of a statement without revealing the underlying data, ZKPs make it possible to create anonymous and private transactions on public blockchain, while maintaining their privacy and keeping their sensitive information secure.

There are many types of zero-knowledge proofs, each designed for specific use cases and applications. Some commonly used types of zero-knowledge proofs include zk-SNARKs and zk-STARKs. ZK-SNARK, an acronym for Zero-Knowledge Succinct Non-interactive Argument of Knowledge, is a type of zero knowledge proof that has gained widespread popularity in the world of blockchain technology. They allow one party to prove to another that they possess a secret without actually revealing the secret itself. Public blockchains use a consensus mechanism to ensure the accuracy of executed transactions, and this often involves requiring other nodes in the network to re-run each transaction to validate it. This process is known as "consensus by replication" and can be slow and resource-intensive, especially as the blockchain grows in size. However, ZK-SNARKs offer an innovative solution to this problem by enabling nodes to check the validity of a computation without the need to replay it. Additionally, they provide a way to offload transactions by allowing for the creation of side chains or second-layer networks that can process transactions faster and at a lower cost. These transactions are offloaded from L1 blockchains by allowing for the creation of L2 (Layer 2) networks, which are secondary networks built on top of L1 blockchains. By doing so, they provide a more efficient and secure way to maintain transaction integrity on public blockchains and allow for the creation of new types of applications that require high throughput and low transaction fees.

ZK-SNARKS is a complex process that allows for the verification of program execution on a blockchain without revealing any secrets. There are many ways to create a zk-snark, including the sonic, halo, and bulletproof constructions. One way to create a zero-knowledge proof is by using polynomial encoding. In this method, the information that the prover wants to prove they know is represented as a polynomial. The prover then generates a "commitment" to this polynomial, which is a cryptographic hash of the polynomial. This commitment can be sent to the verifier, who can then verify that it is a valid hash of a polynomial, without knowing anything about the polynomial itself. Next, the prover uses a homomorphic function to manipulate the polynomial in such a way that it becomes difficult for the verifier to determine the original polynomial. Homomorphic functions are mathematical operations that allow one to perform operations on encrypted data without decrypting it first. In the case of ZK-SNARKs, the prover uses a specific type of homomorphic function called a bilinear pairing, which allows them to perform certain operations on the polynomial without revealing anything about it. Finally, the prover generates a proof that they know the information represented by the polynomial, without revealing the polynomial itself or any other information. This proof is checked by the verifier, who can determine whether the prover knows the information or not, without learning anything about the information itself. This is a general method that can be used to create ZK-SNARKs using various constructions, including the original ZK-SNARK construction as well as more recent constructions such as Plonk, Halo, and Sonic.

EXAMPLE:

For example, let’s say Alice wants to prove to Bob that she knows the solution of a quadratic equation, p(x) = x³ – 3x² + 2x without revealing the solution itself, using a ZK-SNARK proof.

To set up the zk-snark proof:

1. Alice chooses a random degree-2 polynomial f(x) = ax² + bx + c such that p(x) - f(x) has a degree of at most 1 (p(x) - f(x) = dx + e).

2. She also chooses a random value r and computes s = f(r).

   1. To generate the commitment s, Alice chooses a random value r, computes s = f(r), and uses the value of s as the commitment to f(x). This ensures that Alice cannot change the value of f(x) without revealing her choice of r and hence the commitment s.

   2. The value s is then included in the ZK-SNARK proof as part of the statement that f(x) is a valid solution to the equation p(x) = x³ – 3x² + 2x. Bob can verify that f(r) = s by evaluating f(r) and checking that it matches the commitment s.

3. Alice then encrypts the coefficients of f(x) and r using a homomorphic encryption scheme and generates a commitment to them, along with the public parameters required for the ZK-SNARK proof.

Proving:

1. Alice constructs a ZK-SNARK proof that f(x) is a valid solution to the equation p(x) = x³ – 3x² + 2x.

2. The proof includes a statement that f(x) is a degree-2 polynomial, a proof that p(x) - f(x) = dx + e, and a proof that f(r) = s.

3. Alice encrypts the ZK-SNARK proof using the same homomorphic encryption scheme used to encrypt the coefficients of f(x) and r, and generates a commitment to it.

Verification:

1. Bob verifies the commitment to the encrypted coefficients of f(x) and r, and the commitment to the encrypted ZK-SNARK proof.

2. He then uses homomorphic decryption to compute the decrypted values of f(x) and r, and checks that p(x) - f(x) = dx + e.

3. Finally, he checks that f(r) = s.

Recursive zk-SNARKS:

zk-SNARKs can be used to prove that a computation was executed correctly without revealing any information about the computation itself. However, they can have a large proof size and require significant computation and storage resources to verify, which can limit their practical applications. Recursive zk-SNARKs address this issue by allowing multiple proofs to be combined into a single proof, reducing the overall proof size and increasing efficiency. A recursive SNARK system generates proofs in parallel for different transaction blocks and aggregates them into one single block proof that gets submitted to the main blockchain, which means one SNARK can verify other SNARKs. It is helpful to think of this as proving several “state transitions” together. For example, proof 1 can prove block 0 to block 1, proof 2 can prove block 1 to block 2. Then you can combine the proof 1 and proof 2 to prove block 0 -> block 2.

Recursive SNARKs (zk-SNARKs with recursive proof composition) are a type of zero-knowledge proof system that allows for the verification of multiple proofs in a single proof. This makes it possible to build computational integrity proof chains of any length, with each proof being checked in the same amount of time. The key to recursive SNARKs is the use of a "proof composition" function that takes as input a set of SNARK proofs and outputs a single proof that verifies all of them. This function allows the verifier to check the validity of the entire chain of proofs in a single computation, without needing to individually verify each SNARK proof.

The proof composition function is typically based on a recursive construction, in which the input SNARK proofs are grouped into sets, and each set of SNARK proofs is recursively composed into a new SNARK proof. This process continues until a single SNARK proof is obtained that verifies all of the original input SNARK proofs.

EXAMPLE:

For example, let’s say Alice wants to prove to Bob that she knows the solution of a quadratic equation, p(x) = x³ – 3x² + 2x without revealing the solution itself, using a RECURSIVE ZK-SNARK proof.

With the same setup as before,

Setup:

1. Alice chooses a random degree-2 polynomial f(x) = ax² + bx + c such that p(x) - f(x) has a degree of at most 1 (i.e., p(x) - f(x) = dx + e).

2. She also chooses a random value r and computes s = f(r)

3. Alice then encrypts the coefficients of f(x) and r using a homomorphic encryption scheme and generates a commitment to them, along with the public parameters required for the ZK-SNARK proof.

Proving:

1. Alice constructs a ZK-SNARK proof that f(x) is a valid solution to the equation p(x) = x³ – 3x² + 2x.

2. The proof includes a statement that f(x) is a degree-2 polynomial, a proof that p(x) - f(x) = dx + e, and a proof that f(r) = s.

3. Alice encrypts the ZK-SNARK proof using the same homomorphic encryption scheme used to encrypt the coefficients of f(x) and r, and generates a commitment to it.

4. Alice then constructs a new ZK-SNARK proof that she knows the decryption key for the homomorphic encryption scheme used to encrypt the first proof. This second proof is also encrypted and committed.

Verification:

1. Bob verifies the commitment to the encrypted coefficients of f(x) and r, and the commitment to the encrypted ZK-SNARK proof.

2. He then uses homomorphic decryption to compute the decrypted values of f(x) and r, and checks that p(x) - f(x) = dx + e.

3. Finally, he checks that f(r) = s.

Here, Alice constructs two ZK-SNARK proofs - one that f(x) is a valid solution to the equation p(x) = x³ – 3x² + 2x, and a second one that she knows the verification key for the homomorphic encryption scheme used to encrypt the first proof. The second proof is encrypted and committed as well, which creates a chain of proofs that can be verified recursively.

This differs from a non-recursive ZK-SNARK proof in that a single proof attests to the validity of a statement, whereas a recursive ZK-SNARK proof creates a chain of proofs, each attesting to the validity of the previous proof.

ADVANTAGES OF RECURSIVE ZK-SNARKS:

There are many advantages of using recursive zk-snarks over regular zk-snarks. One of the main advantages of using a recursive ZK-SNARKs is that it can be used to offload computations from L1 blockchains to L2 networks, improving scalability and reducing transaction costs. This is because L2 networks can process many more transactions per second than L1 networks, and recursive ZK-SNARKs can be used to prove the validity of transactions without executing them on-chain. Additionally, recursive ZK-SNARKs can be verified in a distributed manner, which means that multiple parties can independently verify the proof without revealing the statement or the proof itself. This is achieved by using a recursive proof construction, where each proof attests to the validity of the previous proof, creating a chain of proofs that can be verified recursively.

CURRENT APPLICATIONS OF RECURSIVE ZK-SNARKS:

With ongoing advancements in the field, recursive zk-SNARKs have the potential to transform the landscape of blockchain technology, enabling new use cases that were previously impossible. For example, recursive zk-snarks are used in privacy-preserving cryptocurrencies such as Zcash which use recursive snarks to ensure privacy of transactions. They are also used in supply chain management to ensure the authenticity and provenance of goods. They can be used to prove that the product was produced by a specific manufacturer and that it has not been tampered with during transport. Recursive ZK-SNARKs can be used to ensure the integrity and privacy of voting systems. They can be used to prove that votes are valid and have not been tampered with, without revealing the details of the votes themselves. Lastly, a recent project called “Ethdos Numbers,” by** Adhyyan, Nalin, Sampriti and Vivek,** use zero-knowledge proofs to measure the separation between people. By Adhyyan, Nalin, Sampriti and Vivek, ETHdos uses recursive zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs) to create proofs that demonstrate the degree of separation between people while keeping individual friendships hidden. How does this work?

Users begin by receiving an ETHdos page URL from a friend. They can then use this proof to mint a soul-bound NFT of their degrees of separation or share their ETHdos page URL on social media. To add friends, users sign an authenticating message and share the ETHdos page directly with their friend. To create a proof of degrees of separation, a source node (a mutual friend) initiates computation by signing a message and running proof generation for the ZK circuit. The circuit takes in as input the source node, the sink node (the user who wants to prove their degree of separation), and a path of nodes connecting the two. The path is represented as a series of edge commitments, each of which represents an edge in the graph and consists of two node commitments, one for each endpoint of the edge. The ZK circuit generates a proof based on this path of nodes, demonstrating the degree of separation between the source node and the sink node without revealing any individual friendships along the way.

The design of this looks like:

Overall, recursive ZK-SNARKs have a wide range of current and potential applications in various domains, and they are likely to become increasingly important as more applications move to decentralized, privacy-preserving systems.

CONCLUSION:

In conclusion, zk-SNARKs and recursive zk-SNARKs are powerful tools for ensuring the privacy and security of transactions on blockchain networks that use smart contracts. By representing contracts as sets of polynomial constraints, these techniques allow us to generate proofs of validity without revealing any sensitive information. Recursive zk-SNARKs take this a step further by breaking down complex contracts into smaller pieces that can be verified independently, making it easier to ensure their validity. Overall, the use of zk-SNARKs and recursive zk-SNARKs helps to enhance the trustworthiness, transparency, and scalability of blockchain networks, which is essential for their widespread adoption in various industries.

Author

Riddhi Patel (Blockchain at Berkeley Education Department).