Understanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKs

Very well known in the field of anonymous cryptocurrencies, zero disclosure proofs of knowledge are very powerful cryptographic tools. Simply put, they allow you to prove that you know information, or that information is correct, without having to reveal it.

From confidentiality to scalability, their field of application is vast. The best known types of proofs are zk-SNARKs, used on ZCash, PivX, or Mina Protocol. More recently, ZK-STARKs have appeared on Ethereum, thanks to the company Starkware. To understand how they work, we need to study a few examples and do a little math.

A zero-knowledge disclosure proof is a cryptographic protocol that allows one to prove the truth of a proposition without having knowledge of the proposition itself.

A “proof provider” can mathematically prove to a “verifier” the correctness of a piece of information, without revealing anything other than its truthfulness and integrity.

Mathematically, zero-knowledge disclosure proofs must satisfy three properties:

  • Consistency(completeness): if the evidence provider and the verifier follow the protocol, then the verifier must always accept the evidence;
  • Soundness: if the proposition is false, no malicious proof provider can convince an “honest” verifier that the proposition is true, and this with high probability;
  • Zero knowledge: the verifier learns nothing more from the evidence provider than the truth of the proposition.

There are several methods for constructing zero knowledge proofs. Initially, the protocols required interaction between the prover and the verifier (interactive proofs). Today, they exist in a non-interactive form.

In order to understand the system, Jean-Jacques Quisquater and Louis Guillou proposed an example in their 1989 article entitled “How to explain zero-knowledge protocols to your children”. This is called the Sigma or engagement-challenge-response protocol.

The Guillou-Quisquater example

Let be Alice,

the evidence provider, and Bob the verifier. Consider a cave, with a fork (path A and path B). To get from A to B or from B to A, you have to open a door with a magic word.

Alice wants to prove to Bob that she knows the magic word to open the door, but without Bob knowing it.

This is a proof of knowledge, as Alice proves to Bob that she knows the magic word, but without revealing any information, as Alice does not reveal the secret word.

Commitment, Challenge and Response

Alice and Bob will then repeat the following scenario several times:

  • Commitment: Bob stays outside the cave, and does not see the inside of the tunnel. Alice enters the tunnel and randomly chooses path A or B (e.g. by flipping a coin).

Preuves à divulgation nulle de connaissance - EngagementPreuves à divulgation nulle de connaissance - EngagementCommitment (Wikimedia Commons)

  • Challenge: Bob enters the cave, and stands at the fork in the road. After drawing one of the two paths (A or B), he calls out the result to Alice.

Preuves à divulgation nulle de connaissance - DéfiPreuves à divulgation nulle de connaissance - DéfiChallenge (Wikimedia Commons)

  • Answer: Alice must prove that she has the magic word by going out the way Bob asked.

Preuves à divulgation nulle de connaissance - RéponsePreuves à divulgation nulle de connaissance - RéponseResponse (Wikimedia Commons)

There are several possibilities.

If Alice knows the magic word:

  • Alice is in A, Bob calls out B, and she satisfies his request;
  • She is in B, Bob announces A, and she satisfies his request;
  • She is in A, Bob announces A, and she satisfies his request;
  • Alice is in B, Bob announces B, and she satisfies her request.

If Alice does not know the magic word:

  • Alice is in A, Bob announces B, and she does not satisfy her request;
  • She is in B, Bob announces A, and she does not satisfy her request;
  • She is in A, Bob announces A, and she fulfills her request;
  • Alice is in B, Bob announces B, and she fulfills his request.

An interactive protocol

Assuming

that Alice follows the protocol (consistency), Bob will be certain that Alice does not know the magic word if she makes a mistake. However, Bob can be fooled in the case where Alice does not know the magic word, but Bob’s request matches his current position.

Bob will then repeat the pattern from the first step. With each iteration, he will strengthen the reliability of the proof. If Alice is not in possession of the magic word, there is a 50% chance that she will make a mistake. With N iterations, the probability that Bob claims Alice has the secret when she does not is ( 1 / 2^N ).

As we will see, interactive protocols have a drawback. Let’s look at a classic authentication scheme, Schnorr signatures.

The Schnorr authentication protocol

The Schnorr protocol is one of the first applications of zero-knowledge proofs. In particular, this digital signature scheme could be implemented on Bitcoin to make it more confidential. Let’s do some mathematics to see how it works in an interactive version.

Understanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKsUnderstanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKsClaus-Peter Schnorr – Konrad Jacobs

This protocol is based on the discrete logarithm problem: it consists in proving that we know an element x belonging to a group G, generated by g, given gx .

Let be a prime number q and a group G generated by g, of order q. We say that g is generator of a subgroup, of order q, of G. g and q are public.

Alice wants to prove to Bob that she knows an element x such that y = gx

  • Commitment: Alice randomly draws an integer s from the set Z*q and keeps it secret. She will then calculate v = gs and send it to Bob.
  • Challenge: Bob then randomly draws an integer c from Z*q and sends it to Alice.
  • Answer: Alice computes r = s – cx and sends it to Bob.

By substitution, since r = s – cx and y= gx then: g(s-cx)* gcx = gs = v

Bob verifies that v = gr * yc. If this is the case, then Alice knows x well.

The disadvantages of interactive protocols

These protocols are called interactive, because the proof provider and the verifier must communicate with each other to engage in this challenge-response game. A major drawback is that the evidence provider and verifier must be online at the same time.

As a result, researchers Fiat and Shamir proposed a non-interactive protocol

in 1986. It served as the foundation for the proofs used on Mina, the zk-SNARKs. To achieve their goals, the Israeli researchers used the famous hash functions. Understanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKs<img width=”533″ height=”800″ src=”https://yellowrocketagency.com/wp-content/uploads/2021/08/Adi_Shamir_at_TU_Darmstadt_2013..jpg” alt=” />Adi Shamir at the Technical University of Darmstadt, September 2013 – Erik Tews

The Fiat-Shamir transformation: making proofs non-interactive

The Fiat-Shamir heuristic is a method of simulating the presence of the proof checker: it is thus replaced by a cryptographic hash function. As a reminder, a hash function is one-way.

It is

impossible, from the image of the function (the hash

), to calculate the input data.

  • In the commitment phase, the proof provider will generate an element a.
  • In the challenge phase, it hashes c = H (a, x) and will compute a correct answer r for the challenge c. It then sends π = (a, r) as a proof.
  • In the answer phase, the verifier runs the hash function on (a, x) to compute c and verify that r is a correct answer for the pair (a, c).

Signature scheme

The hash function ensures that the proof provider has not been able to cheat. Using Schnorr’s authentication protocol, here is how the non-interactive signature scheme works:

  • Alice still wants to prove that she knows x such that y = gx in a group G generated by g, of order q. g and q are public.
  • Key generation: She will randomly draw an integer s and compute t = gs . s is secret, it is her private key. On the other hand, Alice publishes t, her public key.
  • Challenge and answer: Alice then computes c = H (g,y,t) where H is a public hash function. Finally, she computes r = v – c*x. The pair (c,r) represents her signature.

Bob, as well as everyone else who has access to the public variables (g, q t, H, c, and r), can verify that t = gr * yc, thus that Alice knows s, and authenticate her signature (c, r).

The Fiat-Shamir transformation allows us to dispense with the interaction between proof provider and verifier. These proofs satisfy well the three fundamental properties sought:

  • Consistency: Bob can be convinced of Alice’s honesty if the relation t = gr * yc is true.
  • Robustness: it is impossible for Alice to generate a correct proof without having her private key.
  • Null disclosure of knowledge: it is impossible for Bob to compute Alice’s private key from the public data.

In the case of zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge

), the proofs are non-interactive and succinct. In the case of

zk-SNARKs

, the

proofs are succinct (the size of the generated proofs is very small – a few kilobytes) and non-interactive (the protocol does not require any interaction between the proof provider and the verifier). Alice and Bob are replaced by algorithms that generate and verify proofs in a short timeframe, to fit the use cases and properties of blockchains (confidentiality, scalability).

A knowledge non-disclosure protocol based on zk-SNARKs relies on three algorithms:

  • The key generator: the algorithm generates two keys, the private key and the public key.and the verification key. These keys are generated by injecting a secret parameter λ within the program. λ must absolutely remain confidential, otherwise it would be possible to fabricate false proofs.
  • The proof provider: the algorithm will generate the proof from 3 inputs. First, the proof key; second, the public x input, and third, the private statement, which it wants to prove knowledge of, without revealing what it actually is.
  • The verifier: the verification algorithm provides as output a boolean variable (“true” or “false”). As input, it must inject the verification key, the proof generated by the provider, and the public input x.

The non-interactive aspect of this scheme allows to generate and broadcast cryptographic proofs on a distributed network, and to allow the nodes of this network to verify these proofs independently and without having to interact with the entity that generated them.

The interest of zk-SNARKs and their applications in the cryptocurrency and blockchain world then starts to jump out.

SNARK proofs applied to cryptos

ZKPs allow one to verify the validity of a sequence of calculations, involving confidential data, without having to reveal the data or redo the calculations.

For example, one can prove the validity of a transaction without having to reveal its amount, the parties involved or other sensitive information.

In cryptocurrencies, it was the ZCash team that first used the amazing properties of zk-SNARKs to create shielded transactions. Thanks to the proofs, the network’s validating nodes can verify that a transaction is valid without knowing the amount or the addresses involved.

Key generation and trusted setup

The secret parameters used for key generation must be unknown to everyone, so that it is not possible to forge false proofs.

The proof provider and the verifier must therefore agree on a common set of knowledge about how proofs are generated. Typically, this information is encoded via a Common Reference String(CRS). This is used to prove that the proof and verification keys are generated by the same algorithm.

In order to keep the proofs “succinct”, i.e., so that their size varies sub-linearly with the amount of computation performed, the relationship must be encoded in a Structured Reference String (SRS) that is part of the CRS. In a way, the proofs undergo a preprocessing.

The different implementations

ZCash is the first cryptocurrency that implemented zk-SNARKs. Based on the confidentiality of transactions, proofs allow so-called “anonymous” transactions. This is because the network’s validating nodes can verify that the transaction signatures are correct without the parties’ addresses being disclosed. ZCash’s SNARKs proof system is called Sapling. It is based on a famous trusted setup within

of the crypto community.

Indeed, if the secret parameters fall into the wrong hands, it is possible to forge false evidence. So the ZCash team generated them collaboratively (multi-party computation) in a famous ceremony

. With this type of protocol, all participants must be compromised or dishonest to change the final parameters to their advantage. The random numbers used to generate the parameters, as well as the computers used, were destroyed. Understanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKsUnderstanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKsZooko Wilcox, the creator of ZCash, destroying one of the computers used in the trusted setup.

More recently created, Mina Protocol uses zk-SNARKs to maintain its blockchain, a “succinct” blockchain, the lightest in existence. Beyond a very small size (22 kb) offering great scalability to the network, Mina innovates by allowing the use of SNARK proofs within its decentralized applications, the Snapps

. This makes it possible to imagine new types of services and applications, preserving the confidentiality of user data. The possibilities in the field of digital authentication are very interesting.

zk-SNARKs are sophisticated. However, they are far from the perfect solution. Any zero-knowledge proof protocol is a compromise between the confidentiality of the proof provider, and the assurance that he cannot cheat, for the verifier. In addition, the trusted setup

phase is not ideal in terms of transparency.

ZK-STARKs: transparent proofs

If the parameters generated during trusted setup

are compromised, the proofs are worthless. ZK-SNARKs therefore require trusting a third party. Cryptographers wanted to find a way to generate ZKPs without going through a trusted intermediary. To that end, a team of Israeli researchers, Eli Ben-Sasson (founder of Starkware), Iddo Bentov, Yinon Horesh, and Michael Riabzev, conceptualized a new type of ZKP. Starkware-FoundersStarkware-FoundersThe founders of Starkware

In their March 6, 2018 paper, the researchers introduce ZK-STARKs. The acronym stands for

Zero-Knowledge Scalable Transparent ARguments of Knowledge

“. They are superior to ZK-SNARKs in several ways:

  • First of all, ZK-STARKs do not require a trusted setup. They rely on hash functions in the random oracle model ;
  • Second, STARKs are much faster to verify, and their size is smaller(scalable);
  • Finally, they arequantum-resistant, unlike SNARKs.

The random oracle model

A random oracle is a theoretical, idealized model that is used in cryptology to prove the security of an algorithm. It can be visualized as an oracle that is queried and always provides a random answer.

This is

the ideal behavior of a hash function:

  • It is deterministic: the same antecedent (input, pre-image) always gives the same hash value (image, output);
  • This hash value can be computed easily;
  • It is impossible, knowing this image, to find the antecedent (resistance to the preimage);
  • For a given input, it is impossible to find another one with the same hash value (second preimage resistance);
  • Two different entries can never give the same hash value (collision resistance);
  • A slight change in the input changes the hash value significantly.

Some hash functions do not follow the random oracle framework. They are therefore not considered safe.

IOPs (Interactive Oracle Proofs)

STARK proofs are interactive, and use a random oracle during their verification phase. This confers a huge advantage: their scalability.

Indeed,

the verification of the proofs is very fast, and the duration of this verification grows linearly sub-linearly according to their size

. Understanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKsUnderstanding zero-knowledge proofs: ZK-SNARKs, ZK-STARKsProof generation time, verification time, proof size versus computation size – Comparison between ZK-STARKs and other types of proofs – Original Whitepaper

Applications of ZK-STARKs in cryptos

Because of their excellent scalability, ZK-STARKs are primarily used to create secondary layer solutions for blockchains. This is notably the case for Starkware where ZK-SNARKs are the basis of its StarkNet and StarkEx products, second layer solutions for Ethereum

.

StarkNet is a p

A secondlayer platform for Ethereum, based on ZK-Rollups

. It supports the same computations and operations as the core network, with the same degree of security, but with much more scalability.

The operations that take place on StarkNet are aggregated. These aggregations are then accompanied by cryptographic proof of their validity. Ethereum nodes can then verify it and then update the state of the blockchain

. Starkware-StarkNet-ArchitectureStarkware-StarkNet-Architecture

As for StarkEx, it is an engine designed to make Ethereum scalable, thanks to STARKs. The nodes of the second layer generate the off-chain proofs, which will then be verified on-chain

. Starkware-StarkEx-ArchitectureStarkware-StarkEx-ArchitectureThe StarkEx architecture – Starkware

In conclusion

Zero disclosure proofs of knowledge are far too complex to be the subject of a simple article, and this one should be considered very superficial. This field of cryptocurrency has been obsessing the brightest researchers on the planet for years. Thanks to cryptocurrencies, the theories developed are put into practice. Indeed, behind ZKPs lies the grail of anonymity and privacy for users of a blockchain network. Similarly, the scalability of these networks will be greatly improved thanks to the secondary layer solutions that use these mathematical tools. Their applications are new continents to explore in the years to come!

Resources