7
$\begingroup$

I was reading Vitalik Buterin's post on ZK-snarks and I need some clarification on some points . since there aren't that many posts and articles regarding the subject , I had no choice other than turning to stackexchange . here is the post : https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

first I need to know what does he mean by saying " There is a standard way of converting a logic gate into a (a, b, c) triple depending on what the operation is " ? is he pointing to a specific topic in math ? why triple ? googled R1CS . not that many results came up.

secondly , why use the variable "one" . why assign the variables in a particluar order which is : "one" "x" "out" ... etc . why 3 vectors ? and HOW does that exactly work ? ESPECIALLY assigning the variables at the 3rd gate is a bit not clear .

I know these are too many questions and even though I really appreciate any help that I can get , yet I don't expect you to answer every single question.however , if you could point me to the topics,keywords,etc... which describe the methods used therein ,perhaps I could work my way to the end of this article . i wish someone would have wrote a complementary post on this article instead of repeating the sudoku example over and over again . all you can find is either really heavy math papers or waldo analogy . nothing in between .

p.s : i have read posts on zcash blog. still not clear on R1CS and QAP . and scientific papers are too math heavy ...! thanks in advance

$\endgroup$
11
$\begingroup$

what does he mean by saying " There is a standard way of converting a logic gate into a (a, b, c) triple depending on what the operation is " ?

He means that every "+" operation will follow the same pattern. (As will every "-" operation, "*" operation, and "/" operation)

Example using '+' operation:

Statement:

x + y = z

Witness vector

Let's assume our witness vector corresponds to the following variables:

  • [ ~one, x, y, z (or ~out) ]

The order of these variables is arbitrary, it just has to be kept consistent through out the process

Convert the statement into the A * B - C = 0 format:

(x+y) * 1 - z = 0

This means the following is also true:

A = x + y
B = 1
C = z

Determine the "factors" for each variable in our witness vector

A = (0 * ~one) + (1 * x) + (1 * y) + (0 * z) = x + y
B = (1 * ~one) + (0 * x) + (0 * y) + (0 * z) = ~one
C = (0 * ~one) + (0 * x) + (0 * y) + (1 * z) = z

Our vectors then directly correspond to the factors for each variable in the witness vector

A = [0, 1, 1, 0]
B = [1, 0, 0, 0]
C = [0, 0, 0, 1]

Note that this "pattern" of vector will be used for ANY addition gate where two variables are being added to create a third variable.

  • A:
    • 1 for each value corresponding to the variables being added
    • 0 for everything else
  • B:
    • 1 for the value corresponding to ~one
    • 0 for everything else
  • C:
    • 1 for the value corresponding to the output variable
    • 0 for everything else

I hope this also demonstrates why the ~one variable is necessary.


EDIT:

why 3 vectors ? and HOW does that exactly work ?

The formula A.s * B.s - C.s = 0 allows you to perform any addition/subtraction/multiplication/division operations between values and variables.

The dot product (A.s) allows for scaling and addition of values, and the A*B part allows for multiplication and division of values.

The C vector simply represents the result as a value or variable

$\endgroup$
13
  • $\begingroup$ thank you very much .... does sym1 = 2x * y count as a flattened equation or should we go one more step forward and convert the 2x to x+x = k ? also , in some instances such as y = sym1 * x in vitalik's article , it seems that you could define "A" vector based on sym1 and "B" vector based on x , or vice versa . is that correct ? if that is correct , then the stack of "A" vectors and "B" vectors which are made at the end would look a bit different . I mean there could be variations since in each equation its not decided which should be taken as "A" vector . right ? $\endgroup$ – Hesaam Feb 28 '18 at 12:57
  • $\begingroup$ any other areas that use the techniques used here ? $\endgroup$ – Hesaam Feb 28 '18 at 13:35
  • 1
    $\begingroup$ I should have put a disclaimer that I'm not an expert at this, I am just trying to learn all about it myself (which is how I found your post), but I will try to answer your questions: 1. No need to break it down further when 2x + y = z, you can just replace the '1' in the A vector corresponding to 'x' with a 2. The values in these vectors aren't limited to 1 and 0, they can be any number $\endgroup$ – ninni21 Mar 1 '18 at 16:49
  • 2
    $\begingroup$ 2. ‎Yes, when arranging the formula x+y = z into the A * B - C = 0 format, you can have: A = 1 * z; ‎B = 1 * ~one; ‎C = 1 * x + 1 * y; It can also be the following, swapping A and B like you proposed: A = 1 * ~one; ‎B = 1*x + 1*y; ‎C = 1 * z; Or you could combine them all into A: A = 1*x + 1*y + -1*z; ‎B = 1*~one; ‎C = 0; ‎ These all produce valid solutions, and some may even produce the same 't' vector after a witness is provided. 3. No clue if any other areas use this technique $\endgroup$ – ninni21 Mar 1 '18 at 16:51
  • 1
    $\begingroup$ Ah, I see what you mean. The numbers (1,2,3,4) are not arbitrary, they identify which Gate the coordinates belong to. If you wanted to get the A/B/C vectors for gate 4, you use x=4 for each polynomial to get the corresponding vector value. You are right that swapping A & B and reordering the gates would produce different coordinates and polynomials. However, they are all valid QAPs. I actually had this same question and tested it with the python code that Vitalik provided. I suggest you do the same to see how changing A/B or the Gate order affects each step of the process $\endgroup$ – ninni21 Mar 3 '18 at 14:19
2
$\begingroup$

The accepted answer is good but I'd like to add a few more details. The values in the witness vector (s) can be different from 1, especially when you have a succession of addition gates. In this case, it is not cost effective to use a single constraint for each gate. Instead, they can be clustered together into more complex constraints (that is what JSnark does, for example).

For example, if you have

_x2 = 2 * _x0 + 3 * _x1
_x3 = 3 * _x2 + 7

you'd first create a linear combination for _x2 equal to (considering there are no more variables) [0, 2, 3, 0] Then you'd create a second one [7, 0, 3, 0] since you are never multiplying a variable by another variable.

It is only when you need to do this that you must use the A * B - C = 0 construction. Note that this is equivalent to A * B = C, and naturally checks that the input of a multiplication gate is equal to the product of its two inputs.

For example:

z = y^2 + 2xy

must be decomposed in that way. For the variable vector [1,x,y,z, _w0, _w1, _w2], the result would be

_w0 = y * y
_w1 = x * y
_w2 = _w0 + _w1

Leading to these constraints (each constraint has 3 linear combinations: A, B, C)

_w0: [0, 0, 1, 0, 0, 0, 0] * [0, 0, 1, 0, 0, 0, 0] = [0, 0, 0, 0, 1, 0, 0]
_w1: [0, 2, 0, 0, 0, 0, 0] * [0, 0, 1, 0, 0, 0, 0] = [0, 0, 0, 0, 0, 1, 0]
_w2: [0, 0, 0, 0, 1, 1, 0] * [1, 0, 0, 0, 0, 0, 0] = [0, 0, 0, 0, 0, 0, 1]

Notice the third constraint, which encodes a + gate in a multiplication. If this is the last wire, you may need to do this, as there is no another gate to absorb the addition.


I've also seen in the comments questions about the numbering of the constraints. Yes, these can be arbitrary, and in real world implementations they will not be 1, 2, 3, 4. Instead, they will be equally spaced "roots of unity" in a domain with a certain order. I don't think that is a level of complexity needed in this post.

The rationale is that we are going to create a polynomial to represent all A linear combinations (one per constraint), another polynomial for B and another for C. To define these polynomials we are going to interpolate them, by fixing a given number of points where the polynomial evaluates to the constraints values.

I tried to answer all these questions in some posts in my blog in a more down to earth way than Vitalik and with more detail than I can do here. If you are interested, you can read them here:

QAPs

R1CS

Constraint numbering

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.