Join Log in
Score:0
INDUKURI MANI VARMA 21911012 avatar Crypto

What is the need to convert simple polynomial to QAP in zk-SNARKs?

io flag
INDUKURI MANI VARMA 21911012

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.

97
1 + 0
Score:0
avatar Crypto
et flag
user93353

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.

+ 19
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
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)?
0
Reply
et flag
user93353
@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.
0
Reply
et flag
user93353
@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
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
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.
0
Reply
et flag
user93353
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.
0
Reply
et flag
user93353
@INDUKURIMANIVARMA21911012 `However, the way we create T(x) here we are guaranteed to have those 4 roots in the field itself ` - I mean the 4 roots of $T(x)$ not of the original polynomial
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
Let's assume a scenario. I have 3 devices starting with 3 different/random cubic polynomials(I mean coefficients are different in 3 initial polynomials). After the whole process, we get 3 different QAPs for 3 devices. Now, as per the process, common z= (x-1)*(x-2)*(x-3)*(x-4) is used to get h1, h2, h3 such that t1= h1*z, t2=h2*z, t3=h3*z. Is this analogy correct ?
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
One more question is can I use initial polynomial directly in zk-SNARKs ? Let's say I have simple polynomial p(x) = x^3 - 3x^2 + 2x. It has 3 roots i.e x, (x-1), (x-2). I will assume t(x)= (x-1)(x-2), h(x)=x. Now, if I map this example to be used in proving and verification in zk-SNARK. I will use this polynomial as part of bilinear pairing/homomorphic based zk-SNARKs as in - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf page 24. Can I use this simple polynomial or I have to use QAP form only. What could be security issues in both types of polynomials i.e initial one and QAP form?
0
Reply
et flag
user93353
If you put $ x^3 - 3x^2 + 2x = 0$, then it's roots are $[0, -9, -10]$ - it doesn't have 1 or 2 as roots.
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
Sorry, my mistake. I mean the polynomial can be factorized to x(x-1)(x-2). Now, can I assume t(x)= (x-1)(x-2), h(x)=x and use it as part of zk-snarks or is it mandatory to convert to QAP form only. As you mentioned earlier, original form involves power exponentiation unlike QAP which requires add and multiplication operations which make zk-SNARKs easy and fast to compute ?
0
Reply
et flag
user93353
I think you are going the reverse way, you are trying to find a polynomial to convert to QAP. In reality, you will have a solved polynomial - i.e. you will have an equation like $x^3 + x + 5 = 35$. You as a prover know an $x$ which satisfies this equation & that is $x=3$. Without disclosing the answer, you are trying to create a zkSNARK to convince the verifier that you know some x for which $x^3 + x + 5 = 35$
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
This is what I want to clear up. In zk-snarks, which polynomial to be used ? Can I use simple polynomials also as part of zk-snarks ? I want to know how conversion to QAP form is related to zk-snarks if simple polynomials can be used. If we have a solved polynomial as in above comment, what is the need to convert to QAP form in zk-snarks? I apologize for asking these questions but I am confused a lot. I understand the prover and verification steps in zk-snarks but I am confused with these polynomials.
0
Reply
et flag
user93353
You have to prove to the verifier that you know the solution (i.e. value of x & in many cases multiple variables). You need to prove that the solution is correct. At the same time, you don't want to disclose the what is the value of x & other variables to the verifier. You have to give him a way of verifying the solution without knowing the solution. And the proof has to be Succinct (small)
0
Reply
et flag
user93353
You can look here for a high level example of ZK proofs - https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ - Petkus's document is not a good first document to read - it's good for those who already know what they are trying to achieve & it describes how to achieve it. But before going through petkus, you should understand what you are trying to achieve
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
Thank you very much for taking time to answer my doubts. I understand your comment stating that prover knows root of polynomial and he proves it without revealing to verifier. I assume this process can be done with simple cubic equation also. Is this polynomial should be only in QAP form or it works for any polynomial which can be factorized. I only want to know what we are trying to achieve by converting to QAP form as part of zk-snark protocol. Thank you finally for your help.
0
Reply
et flag
user93353
@INDUKURIMANIVARMA21911012 - could you tell me how exactly you will zero knowledge prove that $x=3$ satisfies $x^3 + x - 30 = 0$ without QAP?
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
Ok, now I understand. We convert the problem into zk-SNARKs and then use it to prove that we know the roots of the original polynomial. Thank you so much.
0
Reply
et flag
user93353
@INDUKURIMANIVARMA21911012 - if my answer answers your question, can you upvote the answer & also accept the answer.
0
Reply
INDUKURI MANI VARMA 21911012 avatar
io flag
INDUKURI MANI VARMA 21911012
Done. Thank you
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.