Alex’s notes on ZK-STARKs

It’s time for Alex Pinto’s knowledge to be shared again. This time he has some personal notes on ZK-STARKs.

Since I started looking at the blockchain world, I saw the term ZK-SNARKs pop up here and there, but was not aware of what it meant. When I tried to dig into this concept and find out what it was, I was surprised by yet another term, ZK-STARKs. The term was created in a paper published in EPrint (which is the publication antechamber to the majority of papers in serious cryptographic research) in March this year and refers to Zero-Knowledge Scalable Transparent Arguments of Knowledge, and these constructions seem to be superior to ZK-SNARKs in a number of ways. As far as I know, this is the only paper so far on ZK-STARKs, although there is associated information available publicly in presentation notes (here and here), a posterand a competing construction presented in CCS’17, called Ligero. Both Ligero and ZK-STARKs try to remove the trusted setup of ZK-SNARKs, but ZK-STARKs go farther in terms of also reducing the verifier’s work.

Update: the team behind ZK-STARKs have in the meantime moved to create their own project, Starkware.

The master text to understanding a technology should be the published paper, or if it hasn’t been published yet, its version on EPrint. For full details, the EPrint version is often better, since papers there don’t have a limit on pages and tend to be the full versions. The caveat is that they are also often drafts that have not been under full peer-review and thus can still have mistakes. In this case, EPrint seems to be all there is. But at 83 pages, it’s a hard read, and it is certainly going to take me a long time.

Fortunately, Vitalik Buterin has written a series of posts on his website that, as far as I can tell, give a go at dissecting that paper or at least its contents. So I decided to read Vitalik’s posts and see what I could get out of it.

The current post is more like a sketch of personal notes in my attempt to understand Vitalik’s posts on ZK-STARKs, while leaving Ligero and ZK-SNARKs for another eventual opportunitiy.

Meaning of ZK-STARK

It’s probably a good idea to start by explaining the name ZK-STARK.

ZK: Zero-Knowledge

This is a concept that was developed in the 80s and 90s. It refers to techniques for a Prover to convince a Verifier that s/he knows some piece of information, or a solution to a statement, without revealing anything else. A didactic example is the Ali-Baba cave, proposed by Quisquater and others in a wonderful little paper about teaching Zero-Knowledge to your children. In short, the story is this.

There is a cave whose entrance tunnel forks into two passages, left and right. These eventually turn around, so that they form a loop and touch at a solid wall. Everyone familiar with the cave knows they can either go right or left at the junction, but can only come back the same way. But there is a secret in the cave: a hidden door in the wall between the two passages allows someone who knows the secret to go from the right passage to the left and vice-versa.

This is a valuable secret for some reason, and a Prover who finds the hidden door wants to convince a Verifier that s/he knows it, but without showing the door or how to open it. To do so, the Prover enters the cave and chooses one of the passages. The Verifier then cries at random ‘Left!’ or ‘Right!’, and the Prover must come out the same way. If the Prover can open the hidden door, s/he can always comply with the request. If not, with 50% probability the Prover will fail. Prover and Verifier repeat this a number of times (for example 10), and if the Prover always succeeds, the Verifier is convinced s/he knows the secret.

ARK: Argument of Knowledge

An Argument of Knowledge is a kind of Zero-Knowledge Proof where the statement to be proved is of the kind “Prover knows some private information that satisfies some public function”. In the Ali-Baba example above, the Prover can convince an observer that they can pass through the wall somehow, but does not say anything about the kind of secret door. An Argument of Knowledge would show the Prover knows some secret information, for example, a password, to open the door (instead of, for example, having a physical key for it). The metaphor, in this case, cannot be taken very far, so I’ll be a little more formal instead.

For our purposes, an Argument of Knowledge shows the Prover knows some witness (x) for a given public value y, according to a public function f. That is, f(x) = y. An intuitive example would be:

f(x): “x is the correct password to the system”

and y is either True or False.

There is a further distinction to be made (and glossed over): Argument of Knowledge (ARK) vs Proof of Knowledge (POK). The difference is technical, in the way we specify the soundness of the protocol. An ARK is a weaker construction than a POK, in that it only provides computational soundness, whereas a POK provides statistical soundness. What this means, is that an all-powerful Prover may be able to fool a Verifier with an ARK, but will not be able to do it with a POK.

S: Scalable

ZK-STARKs are doubly scalable. This means they have two good properties referring to the execution time of their parts: the Verifier can check the proof in much less time (exponentially less) than the time needed to execute the public function f (as defined in the section on Arguments of Knowledge); and the Prover needs only moderately more time to construct the proof (quasi-linearly so) than the time needed to execute the public function f.

Notice that if we don’t require Zero-Knowledge, the Verifier could check the veracity of the statement by asking the Prover for f and computing f(x,y). What this property shows is that even with Zero-Knowledge the Verifier can achieve the same result in a significantly smaller time than doing the full work.

T: Transparent

Originally, ZK proofs were interactive systems. The Prover and the Verifier would converse in a protocol: the Verifier would send challenges to the Prover, the Prover would respond and at the end, the Verifier would output whether s/he was convinced by the interaction. ZKP were, in effect, a subset of Interactive-Proofs.

Later on, protocols were developed that made ZK non-interactive, in which the Prover sends a single message to the Verifier and this outputs the final result. This is usually achieved by a Common Reference String, that must be created and shared in a trusted setup phase. ZK-SNARKs fall in this category.

The Trusted Setup is considered a weak point, however, in decentralised environments whose raison d’être is precisely to avoid the need for trust between participants. Therefore, one of the main advantages of ZK-STARKs is that they don’t need this trusted setup phase. Because of this, they are said to be Transparent.

Advantages

There are some important advantages of ZK-STARKs over ZK-SNARKs. One is their transparency, which avoids the need for trust between the participants when the system is set up. This is usually anathema to the cryptocurrency communities. This post briefly addresses this problem with the example of ZCash.

Another important advantage is the assumptions underlying the system. ZK-SNARKs are based on Elliptic-Curve Cryptography, which is susceptible to advances in Quantum-Computers. Zk-STARKs, on the other hand, are Post-Quantum systems, meaning that even if Quantum-Computers become powerful and ubiquitous they will not have an advantage, compared to classical computers, in breaking ZK-STARKs (at least with our current knowledge of Quantum algorithms).

Finally, ZK-STARKs have yet another advantage, which is that the Verification process is simpler and faster than in ZK-SNARKs.

There is a downside to ZK-STARKs, however, in that the proof size is some orders of magnitude larger than for ZK-SNARKs. This means the use of one or the other technique is not immediately a no-brainer. But research will certainly go on, and may yet find ways to reduce the proof size, which will make ZK-STARKs even more appealing than they already are. For me, the maths also seems to be easier, so I’m favouring them instead of ZK-SNARKs.

This is it for tonight. Next time, I’ll dive in the mathematical details of Vitalik’s first post.

Alex is a software engineer at Aventus, working on the blockchain engineering team. He has 20 years of experience working in technology, completing a PhD in Computer Science as well as a post-doctorate in Cryptography. As part of his research, Alex has published papers on Kolmogorov Complexity, Cryptography, Database Anonymization and Code Obfuscation.

Alex also spent seven years lecturing at the University Institute of Maia, including directing the degree programmes for BSc Computer Science and Information Systems and Software.

This article was originally posted on his blog.

Since you are here, we would love if you connected with us on Telegram,Reddit, Twitter, Facebook, Youtube, Instagram and LinkedIn.

Also, we have started a LinkedIn Group for ticketing developers/other developers to engage, join us and start a conversation.