zkSNARKS (Ongoing)

• zkSNARK is a proof that a program has been executed correctly by a prover and given the elements that the prover has used to generate the proof, anyone verifier can perform checks to see if the program has been executed correctly or not.

• To do so, the program will be transformed into a set of different computations. This is called the Arithmetization Process

• The protocol is then reinforced such that it reveals no information other than if the program has been executed correctly or not.

• zkSNARK - Zero Knowledge Succinct Non-interactive ARgument of Knowledge

• Zero knowledge proofs are cryptographic proofs aiming at proving that a given statement is true without revealing the statement.

• Eg: Alice want’s to prove Bob that she has more than $100. One way to prove this would be to show her account balance to Bob. But this isn’t zero knowledge since she’s revealing the information. In a ZK proof Alice generates a proof saying that she has more than $100 in her account that Bob can verify without revealing her account balance.

• Succinct in zkSNARK means that the proof is small and it can be easily verified by anyone without requiring a lot of compute power.

• A zkSNARK proof is only 288 bytes therefore it can be verified instantaneously with very little compute power.

• Non interactivity means that it is possible to write and store proof that can be publicly verified.

• Example of an interactive proof:Alice aims to convince Bob, who is colorblind, that two balls are of different colors. Bob can swap the positions of the balls while Alice isn't looking, and Alice can determine whether or not he's done so. They need to repeat this process multiple times to increase the likelihood of Alice's claims being accurate. However, Bob remains unaware of the balls' colors, only knowing that they differ. They need to repeat this interaction several times for Bob to gain confidence in Alice's proof.

• Argument of Knowledge is a set of statements that aims to determine the degree of truth of another statement.

• With zkSNARKs arguments are formed with math instead of reasoning.

• As we are dealing with computation in math, it is possible to objectively determine what is true and what is false.

• This means we have to transform our original statement into verifiable computations.

• The arguments used for for generating zkSNARKs are concerning knowledge, namely the fact that the prover knows something.

• That something is called a witness

• A witness in cryptography is a piece of information that allows to verify efficiently that a given statement is true.

• In the witness we do not reveal any information. We only reveal the result of the computation.

• zkSNARKS implies the ability for a prover to produce a short and convincing proof of the knowledge of a witness related to a computation that has been performed without conveying any other information to a verifier.

• Zero Knowledge Proofs have 3 specific properties
  • zero-knowledgeness: proving without revealing the information
  • completeness: if the statement being proven is true, and both the prover and verifier follow the protocol correctly, then the verifier will be convinced of the truth of the statement by the end of the proof process.
  • soundness: A malicious prover cannot produce a valid proof for a false statement

• zkSNARK = function(_privateInput, publicInput) → true or false

Arithmetization

• The first part of zkSNARK consists of turning a computer program into verifiable computation. This is what arithmetic circuits do.

• Example: Imaging you have to prove if a number x is either 10, 15 or 25. You can code it like this.

if(x == 10 || x == 15 || x == 25 ) {
	return 1;
} else {
	return 0;
}

• This same program can be formulated into the following equation.

• (x - 10) * (x - 15) * (x - 25) ?= 0

• We know that if x is either 10, 15 or 25, the equation will return 0

• We can represent the equation as an arithmetic circuit

R1CS - Rank 1 Constraint System

• The goal of R1CS is to flatten the equation that is derived from the program so that it’s easier to handle

• In the above equation (x - 10) * (x - 15) * (x - 25) ?= 0, excluding the constants, each link we have traced can be considered as a wire from the base of the circuit. (ref: image above)

• We get a total of 8 wires.

• The operations - and * are represented as gates.

• The wires can be represented as w0, w1, w3, ..... w7 and the gates can be represented as g0, g1, g2.... g4

• Relationship between wires and gates
  • g0: w1 - 10 = w4 ⇒ g0: w4 = w1 -10
  • g1: w5 = w2 - 15
  • g2: w7 = w3 - 25
  • g3: w6 = w4 * w3
  • g4: w8 = w6 * w7

• Alice knows a value x such that w8 = 0. Let this value be 15.
  • g0: w4 = 5
  • g1: w5 = 0
  • g2: w7 -10
  • g3: w6 = 0
  • g4: w8 = 0

• If Alice proves that all the gate equations are correct then she can prove that her original equation is also correct.

• Now Alice needs to create a vector with all the wires she computed. This vector is the witness.

• We start with w0 = 1 always to compute the witness.

• Each gate has to be represented as a set of constraints (a, b, c) such that there’s a solution s where $a.s * b.s - c.s = 0$.

• Here the s is the witness vector.

R1CS example in detail

• An R1CS is a sequence of groups of three vectors (a, b, c)

• the solution to an R1CS is a vector s, where s must satisfy the equation s . a * s . b - s . c = 0

• We have one such constraint for each logic gate

• eg equation: $x^3 + x + 5$

• Flattening the equation, we get

  sym_1 = x * x
  y = sym_1 * x
  sym_2 = y + x
  ~out = sym_2 + 5

• Solution variable mapping

  '~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

• For this equation the solution vector is s = 1, 3, 35, 9, 27, 30

• Constraints for g0
  • $a = [0, 1, 0, 0, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 1, 0, 0]$
  • For the solution s this equation $a.s * b.s - c.s = 0$ returns 3 * 3 - 9 = 0
  • the purpose of this first check is to verify the consistency of the inputs and outputs of the first gate only.

• Constraints for g1
  • $a = [0, 0, 0, 1, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 0, 1, 0]$

• Constraints for g2
  • $a = [0, 1, 0, 0, 1, 0] b = [1, 0, 0, 0, 0, 0] c = [0, 0, 0, 0, 0, 1]$

  Constraints for g3

  • $a = [5, 0, 0, 0, 0, 1] b = [1, 0, 0, 0, 0, 0] c = [0, 0, 1, 0, 0, 0]$

• Here we have all the constraints for the R1CS for the given equation.

• The witness is just the assignment to all the variables, including input, output and internal variables. The witness here is s = 1, 3, 35, 9, 27, 30

Largarnge Interpolation

• Used to estimate a function that goes through all the given points (x1, y1), (x2, y2),…. (xn, yn)

• Step 1: Find polynomials for each points such that $l_n$ passes through $(x_n, y_n)$ and 0 for all other values for $(x, y)$

• The first polynomial $l_1$ passes $(x_0, y_0)$ and passes through (0, 0) for all other nodes.

Quadratic Arithmetic Program - QAP

• This final step requires turning our (a, b, c) matrices into polynomials using Lagrange Interpolation

Resources

• https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649