0
$\begingroup$

From Vitalik Buterin's Blogpost - Quadratic Arithmetic Programs: from Zero to Hero.

In the blog, a cubic equation:x**3 + x + 5 == 35 is chosen. It has been assumed that this equation is some computational problem. Since, zk-SNARKs cannot be applied to any computational problem directly, we convert to algebraic circuit, R1CS, QAP, Linear interactive proof, and zk-snarks finally.

Finally, we get t:A.s * B.s — C.s i.e QAP. It is divided by a minimal polynomial z= (x-1)*(x-2)*(x-3)*(x-4) to get h i.e., t= h*z => h=t/z.

My questions are

  1. Why did the inital cubic polynomial converted to QAP ? Can we not use an equation which have multiple real roots. Ultimately, we got a polynomial of higher degree(QAP) to divide it by z.

  2. After getting QAP, how did it happen to get reminder zero when t/z is computed ? What is the correlation between cubic equation and QAP ?

I am new to understanding this level of math. Though I understand the steps involved, I cannot acquire the logical significance in the steps.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

After getting QAP, how did it happen to get reminder zero when t/z is computed ? What is the corelation between cubic equation and QAP ?

Numbering the gates as 1, 2, 3, 4 etc, you think of this number as the x-coordinate of a point. The first column of the $A$ Matrix is $[0, 0, 0, 5]^T$

Each element corresponds to one of the gates. So if you think of these values as the corresponding y co-ordinates.

So you have 4 points $(1,0), (2,0), (3,0), (4,5)$.

Using Lagrange interpolation, you can get the polynomial passing through these 4 points. Likewise you can find the polynomials for first column of the $B$ & $C$ matrices also.

So you get your $A_1(x), B_1(x)$ & $C_1(x)$ polynomials & all the way upto $A_6(x), B_6(x), C_6(x)$

The witness vector is $S$.

$A(x).S + B(x).S = C(x).S$

This is shown in Buterin's diagram enter image description here

You can create a new polynomial $T(x) = A(x).S + B(x).S - C(x).S$.

$T(x)$ has 4 known roots at $x = [1, 2, 3, 4]$.

Let $Z(x) = (x-1)(x-2)(x-3)(x-4)$

By the Polynomial Reminder Theorem, with constant $a$, the remainder of a polynomial $P(x)$ divided by $x−a$ is equal to $P(a)$. So $P(1), P(2), P(3), P(4)$ are all equal to $0$.

Hence when $T(x)$ is divided by each of the $(x-1), (x-2), (x-3), (x-4)$, the remainder is $0$.

Hence when $T(x)$ is divided by $Z(x)$, the remainder is $0$

i.e. when divided, it's exactly divisible & has no remainder.

Why did the inital cubic polynomial converted to QAP ? Can we not use an equation which have multiple real roots. Ultimately, we got a polynomial of higher degree(QAP) to divide it by z.

In Computer Science, there are 2 models of computation - circuits and Turing Machines. Circuits can express most things through just the 2 operations addition & multiplication & hence reduce the complexity of ZK proofs. If you hadn't flattened the original program & had not used circuits, you would also needed powerof operation & in other computations more operations.

Improve this answer
$\endgroup$
19
  • $\begingroup$ Thank you for the explanation. Does initial computational problem(cubic equation in the example) we choose should have real roots, and only then t/z leaves zero remainder ? In real time application, how does one choose initial polynomial(computational problem)? $\endgroup$
    – INDUKURI MANI VARMA 21911012
    Commented Feb 3, 2023 at 9:18
  • $\begingroup$ @INDUKURIMANIVARMA21911012 - Buterin's says this in the post -` Note that the above is a simplification; “in the real world”, the addition, multiplication, subtraction and division will happen not with regular numbers, but rather with finite field elements`. So you will have roots in the field. $\endgroup$
    – user93353
    Commented Feb 3, 2023 at 9:21
  • $\begingroup$ @INDUKURIMANIVARMA21911012 - in a real application, the problem is the one which you need to verify. For that, you need to go into why these zkSNARKS are used. For e.g. in a regular blockchain, transactions are posted in the chain by one person & everyone else has to verify the transaction. These are zero knowledge verifications - which serve 2 purposes - privacy & also efficiency. For e.g. in a transaction, you need to ensure if the money transferred is less than or equal to what the sender has in his account. This check would be converted into a zkSNARK $\endgroup$
    – user93353
    Commented Feb 3, 2023 at 9:25
  • $\begingroup$ You mean, I can choose any polynomial equation before converting it to QAP. In the blog, x**3 + x + 5 == 35 is the polynomial, it has one real root and 2 imaginary roots. It's not advisable to use this cubic polynomial for ZKP as it is not a circuit. So, when it's converted to QAP form, it can be factorized to two lower-degree polynomials say z,h and used in zk-SNARKs. You meant any polynomial after converted to QAP form will have roots over finite fields ? Am I correct ? I want to clear mathematical doubts in the example. $\endgroup$
    – INDUKURI MANI VARMA 21911012
    Commented Feb 3, 2023 at 9:52
  • $\begingroup$ The polynomial you are working with $T(x)$ is not the same polynomial you started with - it's a different polynomial. The original polynomial also would be defined in a field. A polynomial defined in a field need not have all or any of it's roots in the field - they may be in extension fields also. However, the way we create $T(x)$ here we are guaranteed to have those 4 roots in the field itself - that's because we have created it that way. $\endgroup$
    – user93353
    Commented Feb 3, 2023 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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