Building a STARK

This post will step through how to build a simple zk-STARK. Whereas I have outlined the ideas already in a couple of posts (STARKS I and II), these took a very general approach and consequently were rather abstract. This post will be more concrete by detailing how one can be built for a specific calculation. For this, I pick a ‘toy’ example for ease of exposition, but which is still very interesting. The calculation will be based on the rule 30 elementary cellular automaton. There are many ways of actually building a STARK, some of which will perform better than others. I make the choices aiming for simplicity and to avoid complex constructions.

First, let’s recap what a zk-STARK is. It is an acronym for zero knowledge Scalable Transparent Argument of Knowledge. While they are often phrased as proofs of existence of some quantity (e.g., existence of 3-colorings of a graph), more properly, they are a proof that the person constructing the STARK has knowledge of this quantity. We can be a bit more precise. The setup must include some algorithm or computable function F and a value b which it may or may not return. This information will be publicly known, so that anyone can verify what F(a) does evaluate to on given input a. Anyone can also make a statement such as:

I know of a value a such that F(a) evaluates to b.

However, such a statement does not itself prove that they do really know of such a value. An argument of knowledge is a method of proving the truth of this statement. As an example, consider digital signatures. In this scenario, the value a is a private key and F is the calculation deriving the associated public key b. A digital signature is an argument of knowledge of a private key. For elliptic curve based schemes as used in ECDSA and Schnorr signatures, it can be shown mathematically that for any public key there does exist an associated private key, although it can be practically impossible to actually find it. Hence, a digital signature is not a proof that a private key exists, which we know already. Instead, it is a proof that it was known to the person constructing the signature.

One method of proving a statement like the one given above is to simply display the value of a, so that anyone can evaluate F(a) and verify that it does indeed equal b. There are two reasons why this may not be a desired or viable approach, corresponding to the other words making up the acronym zk-STARK. Firstly, the value of a may be a secret, such as with the digital signature example. It should be zero knowledge. Ideally, the proof does not reveal any information beyond the fact that the prover knows of a valid value for a. Secondly, it should be scalable.

By scalable, we mean that the size of a zk-STARK should remain small and reasonably quick to validate, even if F is very computationally expensive to compute. For example, we could take the value a and hash it billions of times to get the result b. If we want to convince others of the result, then expecting them to go through the whole tedious calculation might not be realistic. Instead, a STARK can be constructed, which anyone can check proves that the result is b as claimed without having to redo the entire calculation. This is especially useful for blockchains where the use of STARKS can greatly reduce the work required by validators and avoid using up a lot of the limited block space. A long list of transactions with their associated digital signatures could be replaced by a much shorter proof of the combined effect of these transactions.

The scalability property is really the magic part of STARKs and the closely related SNARKs. A very long calculation will take a long time to perform. However, once one person has done this, they are able to prove the result to others without requiring them to also go through the long calculation. We really do not have any right to expect that this is even possible, but luckily it is!

Next, STARKs are transparent, which means that there is no trusted setup. This is in contrast to the closely related SNARKs (scalable non-interactive argument of knowledge), where a procedure is required to initialize the contruction of the SNARKs, and involves data which must be kept secret by those involved. Revealing this data would allow ‘proofs’ to be constructed even though the prover does not have the knowledge being claimed. STARKs do not have this issue.

Finally, I mention that STARKs are non-interactive. Any argument of knowledge involves two parties, the prover and the verifier, with the former trying to convince the latter of the truth of a statement. Interactive proofs involve messages being passed back-and-forth between the two. Essentially, the verifier asks questions of the prover, and checks his responses, until she is convinced of the proof of the original statement. A non-interactive proof just consists of a single message sent from the prover to the verifier. This is what is needed in many blockchain applications, since the proof can simply be constructed and added to the chain. Anyone can be the verifier by reading the data from the blockchain, such as done by validators.

As with any argument of knowledge, STARKs are sound, meaning that it is practically impossible for someone without the claimed knowledge to construct a valid proof. However, I should point out that, in theory, it is always possible to just guess at a valid argument by blind luck. For this reason, any such construction will come with a soundness parameter. This is an upper bound on the probability that, without the claimed knowledge, any parameter choices made in its construction leads to a valid proof by chance. The idea is that this should be tiny to avoid such false positives. It is true that an untrustworthy prover could try over and over, choosing different parameters each time, to try and brute-force a solution. As long as the soundness parameter is small enough — say, about 2-100 or lower — then it becomes practically impossible to even brute-force a solution.

Automaton Rule 30

The toy calculation used in this post is the elementary cellular automaton Rule 30. The idea is that we have a one dimensional array of cells, indexed by the integers. Each cell can be in one of two states, either set or unset, which I will label by the numbers 0 and 1. We then iteratively update this array, one step at a time. At every step of the calculation, each cell is updated according to the value of it and its immediate neighbours.

Using si(t) to represent the state of cell i at time t, I will also denote this by just si, suppressing the time variable for brevity. Its value si(t + 1) at time t + 1, which I denote by si, is some function of si - 1, si, si + 1.

si = S(si - 1, si, si + 1).

The rule is defined by the function S and, given any initial state, this can be applied to compute the state at every future time. There are many different choices for S giving different cellular automata with different properties. I choose rule 30, for which the state si is determined from si - 1sisi + 1 by looking up its value in the following table:

current pattern 111 110 101 100 011 010 001 000
new state for center cell 0 0 0 1 1 1 1 0

Figure 1: Rule 30.

As there are 8 possible values which si - 1sisi + 1 can take, and each of these can lead to two possible states for si, there are 28 = 256 distinct elementary cellular automata. This particular one is called ‘rule 30’ since the second row of figure 1 is the binary expansion of the number 30.

To avoid dealing with infinite arrays, I will use a fixed window width of 200. That is, rather than an infinite array of cells, we just have 200 of them labelled as si for 0 ≤ i < 200. At the edges of the window, we allow the rule to wrap around, so that, on the left, s-1 is defined to equal s199 and, on the right, s200 is defined to be s0.

Then, if we start with the single cell number 50 set, and the others unset, repeated applications of the rule give figure 2 below. Here, the time starts from the top of the figure and increases towards the bottom. Each row of pixels represents the state at the corresponding time, with black pixels representing cells which are set and white those which are unset.

rule 30
Figure 2: Rule 30 with a single initial cell set

Continue reading “Building a STARK”

Non-Interactive Proofs

This post discusses non-interactive zero knowledge proofs, which can also be considered as digital signature algorithms. These can be used in blockchains to verify that the creator of a transaction has access to some secret data satisfying specific defined properties.

I previously discussed zero knowledge proofs, where a party Bob has some secret data satisfying certain properties. For example, this could be the private key associated with a publicly known Bitcoin address, or it could be a file whose SHA256 hash is equal to a given value, or maybe he knows a 3-colouring for a specified graph. In fact, it could be any data satisfying a clearly defined computable property. Bob wants to prove that he has such information to Alice but, as it is secret, he does not want to send her the data itself. Ideally, he wants to prove this without revealing any knowledge besides the simple fact that he knows of something satisfying the claimed properties. As was discussed, this can be achieved by an interactive proof where he exchanges messages with Alice until she is able to conclude with a high degree of confidence that he does indeed have the claimed secret. This as in figure 1 below, where Bob is acting as the prover and Alice is the verifier. As I will build on such zero-knowledge proofs here, if you are not already familiar with them it is suggested to first read the earlier post.

Figure 1: An interactive proof.

Alice verifies that Bob’s messages satisfy some required properties and, if they do, she accepts his proof. Otherwise, she rejects it. Recall the important properties:

  • Completeness: If Bob has the claimed information, he is able to send messages to convince Alice of this fact.
  • Soundness: If Bob does not have the claimed information, he is not able to fool Alice that he does, other than with a very small probability.
  • Zero-knowledge: The verifier learns no information beyond the fact that Bob has the knowledge.

To ensure soundness, Alice should select her messages at random according to a specific procedure. Essentially, she is challenging Bob with unpredictable questions, which he is very unlikely to be able to answer all correctly unless he has the claimed knowledge. If Alice sticks to this method, she is an honest verifier. Similarly, if Bob has the claimed information then, to ensure completeness and zero-information, he should also construct his messages according to a specific procedure which, again, are randomized to ensure that he does not leak any secret information. If he does this, then he is an honest prover.

In many situations, the setup described above is not desirable or is not possible at all. It may be preferable for Bob to send a single proof to Alice for her to verify without having to respond with further questions. Maybe there is no communication channel from Alice to Bob, or maybe she will check the proof at a later date when she no longer has contact with Bob. This is the case, for example, where Bob is submits a transaction containing the proof to be included in a blockchain, and Alice is a network validator who later verifies this transaction. These are non-interactive proofs, so figure 1 should be updated to only include a single message sent from the prover to the verifier.

Figure 2: A non-interactive proof.

Technically, it is not possible for valid non-interactive proofs to be zero-knowledge, at least by the standards described in the previous post. For one thing, Alice could take the message sent from Bob, and pass it off as her own to try and prove that she has access to the secret data, which is incorrect. In fact, Bob may have already done this, and simply passed off a proof originally from someone else as his own. So, the best that we can expect, is for the message to prove that someone had access to the secret and constructed the message. Continue reading “Non-Interactive Proofs”

Zero Knowledge Proofs

Where's Waldo
Where's Waldo?

Alice is busy trying to find Waldo in the picture above (or, Wally, for those outside of North America). After some time without success, she is doubtful that he is even in the image at all. Bob assures her that Waldo is there, since he already found him. However, this is not enough to satisfy Alice. She needs proof before spending any more time on the task. How is it possible for Bob to prove this to her, without giving the game away by pointing out his location?

Assuming that the picture is printed out on a sheet of paper, Bob could take a large piece of cardboard and cut out a small Waldo-shaped hole. Then, while keeping the hole covered, he slides the paper underneath and, after correctly positioning it, he uncovers the hole to reveal Waldo! Alice can look with her own eyes and see his face, which looks like this: Waldo. She agrees that Waldo is in the image but, since all of the rest of the picture is covered by the cardboard, Bob has not revealed the location. So, she continues with her task in the knowledge that, at least, it is possible.

What Bob has done here, is provided a zero-knowledge proof that Waldo is in the picture. That is, he did this while providing no information to Alice other than the fact that he is there. You could argue that he did provide some information. Specifically, he showed Alice the exact size and appearance of Waldo’s face. However, if we assume that this information is no secret and is already publicly known, then it is true that Bob did manage to prove Waldo’s existence in the image without revealing any other previously unknown information. Continue reading “Zero Knowledge Proofs”