What are zk-SNARKs?
Trust is a funny thing. Stephen R. Covey once wrote, “Trust is the highest form of human motivation. It brings out the very best in people. But it takes time and patience.”
So, how does perfect strangers trust each other? You could, perhaps, develop a complicated system of codes and verifiers where messages are encoded with a difficult and time-consuming rubric that can only be verified by specially-equipped verifiers. But, what happens if there are more messages to verify than there are verifiers? There could be long waits, high costs for priority treatment, and allegations of unfairness.
Yet, if you have the time to kill, all of this could be fine. What if time was a consideration? What if, for example, you need to prove your worthiness to get into the latest club? How can you prove your trustworthiness quickly without having to resort to picking a fight with the tough-looking biker behind you and dealing with all the horrible, horrible repercussions of this.
Fortunately for you, this is a problem that can be solved with abstract math. Horribly, horribly abstract math.
Spooky Math from the Future
So, what is zk-SNARKs? Zk-SNARK, “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge,” is a mathematical construct that argues that a value is true without showing the value to be true or even admitting that the value exists in the first place. In other words, a zk-SNARK proves something is true while sharing zero knowledge of the thing.
You’re still here? Has your brain exploded yet? I promise that this will make sense if you hang in here.
Zero knowledge proofs came about in the 1980s. Most proof systems assume that it is the job of the prover to verify or prove itself to the verifier. This is known as “soundness” and it assumes that the prover – if there is a malicious party – would be the one to benefit from deceit. A modern-day example would be a computer password system: the user must enter a password to prove his/her authority to use the system. No one questions the system’s motivations in approving or rejecting password attempts.
This follows psychological tenets that argues that in a traditional transaction, the party that wants something is less trustworthy than the party that has what is desired. This may or may not be true, but that is the common perception.
What happens, however, if the verifier is untrustworthy. What if the computer system was compromised, so that once you submit your password, it is automatically shared with hackers? Either the prover would have to accept the verifier’s untrustworthiness or reject the transaction wholesale.
A zero-knowledge proof offers a workaround. A way to think about this is the book “Where’s Waldo?,” where readers must guess where Waldo is in a picture puzzle. Imagine Mary and Beth made a bet about who will find Waldo first. Mary finds Waldo first, but don’t want to show Beth where he is at, as that gives her a certain level of power. But, she still wants to win the bet. In this situation, Beth as the verifier is disadvantaged to accept Mary’s word, as Beth would lose the bet. It is more advantageous for Beth to assume that Mary did not find Waldo and to continue the search on her own. Of course, Mary could just point out Waldo, but that’s sharing information that Mary considers important.
A more classic example is that of Ali Baba’s cave. “In this example, we’ll call the two people Paul (P) and Vick (V), where Paul is the prover and Vick is the verifier,” Investing.com explains. “Paul and Vick both approach a mystic cave that has a magical secret door at the back. The mystic cave is circular, with an entrance at the front and a magical locked door blocking side A from side B. Paul tells Vick that he knows the secret password to open the magical door at the back of the cave, but he doesn’t want to tell Vick or anyone else what the secret word actually is. Vick does not believe Paul and asks him to prove it. The mystic cave has only two paths, A on the left and B on the right. Paul can take either path, A or B, whichever he likes but Vick is not allowed to see which path Paul will take, so Vick waits outside the cave.”
“After a few minutes, Vick enters the cave and shouts to Paul. Vick can ask Paul to come out of the cave from either path A or B, chosen at random, as he doesn’t know which path Paul took in the first place. Paul knows the secret word to the magical door at the back of the cave and can emerge from either side no matter what Vick chooses. In the images below, Paul took path A, and then Victor came to entrance and shouted to Paul to appear from path B. Paul shouts, “No Problem”, and uses the secret word to open the magical door and comes out from path B.”
“So, you may be think there is a 50/50 chance that Vick would just guess correctly and Paul doesn’t know the secret password. By random chance, Vick could choose a path and Paul could appear, making this entire cave story false.”
“That is why, in order test the validity this would be repeated numerous times, until Vick was convinced. Let’s say they did this exercise 15 times and all 15 times Paul came out from the correct path. Paul’s probability of actually entering path A or B, not knowing the secret, and coming out of the same random path that Victor chooses all 15 times, would be very rare or almost impossible.”
A zk-SNARK satisfies three key qualifications: 1) it is complete, or it provides a way to prove that any true statement is indeed true; 2) its sound, or it provides protections to prevent a false statement from ever being found to be true; and 3) it demands zero-knowledge, or the statement itself is enough to prove its truthfulness.
Regarding the Waldo bet, Mary could take a large piece of black cardboard, cut a Waldo-sized hole in it, and with Beth not looking, place the board over the book so only Waldo is visible. This satisfies all the qualifications as Beth can see that the book is still there and the page has not been changed and that Waldo has been found. Once the board is removed, Beth would have a general sense where Waldo is, but no specific data to go on.
A final way to look at this is to imagine that Mary and Beth are doing Sudoku. This time, Beth finished the puzzle first, but smarting from Mary’s lack of faith, she refuses to share the completed answer with Mary. Yet, to satisfy their “double or nothing” bet, not only does Beth has to show that she completed the puzzle, but that she is correct.
One way Beth could prove this is to have Mary use a Sudoku solver to find the solution of the puzzle (ignore for a moment that this would give Mary the information that Beth is trying to hide). The solver would use a cipher that Mary does not have the key to encode the solution. Mary gives the solution to Beth. So, Beth has her answer and the encoded solution, while Mary only has the original Sudoku puzzle at this moment.
With this, Mary could prove Beth’s truthfulness. This works by having Beth ask for one of four choices:
- Reveal a row,
- Reveal a column,
- Reveal a 3×3 box, or
- Reveal the encoded version of the original puzzle.
At the most, this represents 28 choices (although after any 18 choices, the full puzzle will be revealed). So, Mary asks for a choice and it is revealed. As Mary has no clue what these numbers mean, she asks for another choice, and another, and so on. With each successive choice, the likelihood of Beth lying decreases, as it would become progressively harder for Beth to find unique solutions to Mary’s choices. It should be noted, however, that the chance of Beth lying never reaches zero.
What is important here is that zero-knowledge proofs do not seek proofs or the verification of facts, but proof of knowledge. The difference between the two is lie saying “I know it is raining” versus “it’s raining.” As one is an assumption of truth versus a truth (a fact), there will always be a certain level of uncertainty.
The Schnorr Identification Protocol and the Development of the zk-SNARK
The first mathematical exploration of this concept is the Schnorr Identification Protocol.
Let’s assume that Mary and Beth are trying to send a cryptocurrency transaction to each other. At this point, Mary and Beth do not trust each other, so when Mary tells Beth that she has a private key, Beth laughs at her, Mary could show Beth her key, but then Beth would then know what her private key is.
Let’s assume that the variable p is any prime number, that q is any factor of (p-1), and a is a variable such (aq = 1 mod p). Also, let assume that these variables are publicly-known. If Mary’s private key is s and the public key is v, and s is any value that satisfies 0<s<q, then v=a-s mod q.
Mary would not need to share her private key. All she would need to do is to send her transaction with a signature. She would need to pick a random number (r), and use that number to figure out a value so that the value (e) is equal to ar mod p. That signature would be a hash of the concatenation of the value and the content of the transaction.
This signature would be added with one last value y, which is y=(r+s*e) mod q. With e, y, and the original message, Beth can verify the transaction … begrudgedly. Using the public variables, Beth can prove Mary’s work, if:
- V=Mary’s public key,
- P=Mary’s choice of prime number,
- Q=Mary’s choice of factor of “p-1”, and
- A is such that aq=1 mod p, at Mar’s discretion.
Beth would solve for e1=AyVe mod P. Since, through substitution, we can prove that e = e1, Beth can also assume, with some level of confidence, that Mary does have the private key.
This is, however, an interactive proof. To make it non-interactive, Mary must be able to make her assertion in a way that Beth or anyone else can verify it without her help.
Blockgeeks explains how this works with zk-SNARKS: “A Zk-Snark consists of 3 algorithms: G, P and V.”
“G is a key generator takes an input “lambda” (which must be kept confidential and shouldn’t be revealed under any circumstances) and a program C. It then proceeds to generate two publicly available keys, a proving key pk, and a verification key vk. These keys are both public and available to any of the concerned parties.”
“P is the prover who is going to use 3 items as input. The proving key pk, the random input x, which is publicly available, and the private statement that they want to prove the knowledge of without revealing what it actually is. Let’s call that private statement “w”. The P algorithm generates a proof prf such that: prf = P(pk, x,w).”
“The verifier algorithm V has basically returned a boolean variable. A Boolean variable has only two choices, it can be TRUE or it can be FALSE. So, the verifier takes in the verifying key, public input x and proof prf as input such as: V(vk,x,prf), and returns TRUE if the prover is correct and false otherwise. “
“Now, about the parameter lambda. The value of the “Lambda” must be kept confidential because then anyone can use it to generate fake proofs. These fake proofs will return a value of TRUE regardless of whether the prover actually has knowledge of private statement “w” or not.”
Zcash is the only cryptocurrency that uses this methodology, although Ethereum may pick it up as a way to speed up transactions. Of all the anonymity-guaranteeing functions available, zk-SNARKs are the most exciting, and the one most capable of fixing the scaling problem blockchain currently face. However, as zk-SNARKs are not perfect, one must ask if good enough is enough when it comes to blockchain.