R1CSQAP/

[utterances-bot]

R1CS and QAP (zkSNARKs) : From Zero to Hero with Finite Fields & sagemath – Risen Crypto – Mathematical Cryptography

https://risencrypto.github.io/R1CSQAP/

[ddbit]

Hi, how can the interpolation of [1 2 3 4] for [0 0 0 5] be [36 16 36 35]? It should be [-5 5/6 -5 5/6] or am I missing something?

[ddbit]

Sorry, I mean [-5 55/6 -5 5/6]

[upavloff]

It is due to the fact that were in a field of order 41.
In this case you have -5 = 36 mod 41 , 6^(-1) = 7 mod 41, 7*55 = 16 mod 41

[RisenCrypto]

Hi, how can the interpolation of [1 2 3 4] for [0 0 0 5] be [36 16 36 35]? It should be [-5 5/6 -5 5/6] or am I missing something?

We are operating in GF(41) & not in Q.

If you see the sagemath program in the writeup

F41 = GF(41)
R41.<x> = PolynomialRing(F41) # Polynomial Ring in GF(41)
points = [(1,0), (2,0), (3,0), (4,5)]
R41.lagrange_polynomial(points)

35*x^3 + 36*x^2 + 16*x + 36

[abbypan]

If T is divided by Z, then it will be perfectly divisible & will leave no remainder i.e. there must exist a Polynomial H such that Z(x)=H(x)⋅T(x)

It should be T(x)=H(x)⋅Z(x) ?

[RisenCrypto]

It should be T(x)=H(x)⋅Z(x) ?

Fixed. Thank you very much.

[xushijie]

How can we get this result:

sage: # We define the solution vector also in the field
....: S = vector(F41,[1, 3, 35, 9, 27, 30])
....: # Create the L, Rx & Ox polynomial
....: Lx = R41(list(S*PolyM[0]))
....: Rx = R41(list(S*PolyM[1]))
....: Ox = R41(list(S*PolyM[2]))
....: print("Lx = " + str(Lx))
....: print("Rx = " + str(Rx))
....: print("Ox = " + str(Ox))
Lx = 29*x^3 + 18*x^2 + 36*x + 2
Rx = 28*x^3 + 36*x^2 + 24*x + 38
Ox = 37*x^3 + 37*x^2 + 17*x

The first coeff is something like:
[136+ 38 + 35* 0 + 935 + 274 + 30* 40, ...]

[xushijie]

[136+ 38 + 35* 0 + 935 + 274 + 30* 40, ...]

[RisenCrypto]

How can we get this result:
The first coeff is something like: [1_36+ 3_8 + 35* 0 + 9_35 + 27_4 + 30* 40, ...]

I am not sure I understand your question. What is this 1_36 + 3_8 ...?

[xushijie]

I think I have already got the answer. My original result is [1683, 2332, 2232, 1013], and I forgot to mod 41. After mod 41, I got the same result. Thanks

[PatoSF]

How can we calculate this ? I mean for T(1) it would equal 1923. I didnt understand this step and the one under it. How did you get 0 ?!
In the R1CS, we had checked if (l⋅S)∗(r⋅S)=(o⋅S) for each of the Gates. After conversion to QAP, we can do the same by checking the value of T at x at 1,2,3,4- if all 4 are zero, then we have checked all the constraints together - thereby proving that the solution vector known to the Provers satisfies the equation.

[RisenCrypto]

How can we calculate this ? I mean for T(1) it would equal 1923.

How did you compute it?
Here I have redone the computation in sagemath

sage: p = 641
sage: F = GF(p)
sage: R. = PolynomialRing(F)
sage: T = 139x^6 + 372x^5 + 275x^4 + 58x^3 + 147x^2 + 379x + 553
sage: T(1)
0

T(1) is 0 - likewise T(2), T(3), T(4)

Which field are you operating in?

I think you are probably not doing computations in the field or doing it in a really big field.

That's why you get 139 + 372 + 275 + 58 + 147 + 379 + 553 = 1923

If you operate in the field GF(641), then 1923%641 = 0