I'm sorry to ask this question because this question does not involve the correctness of the code, but is purely a question of my own understanding. After inquiring some information, I did not get a suitable answer, so I think I can only ask the question in here it is.
I don't quite understand how the eval_of_tau function in generator works.
So as I understand it, from here on powers_of_tau becomes the coefficients (a0, a1, ..an) of the polynomial f(x) such that
A polynomial of the form f(x) = a0 + a1 x + a2 x^2 .... an * x^n
Satisfy:
f(ω0) = tau^0
f(ω1) = tau^1
....
How can this be the value of a QAP polynomial at tau?
Because powers_of_tau has been ifft transformed before, so
powers_of_tau[index].0 here should be the indexth coefficient of f(x). What is the significance of multiplying this coefficient with coeff?
I guess based on the comments, here is the equivalent to the point value form of QAP by doing Lagrangian interpolation, the formula:
$$ L(x) = \sum _{j=0}^{k} {y}_j * {l}_j(x) $$
Then coeff is equivalent to $$ {y}_j $$
Then the jth item of powers_of_tau is equal to the l_j(x) corresponding to y_j?
Is this guess correct? Is there any formula to prove that they are indeed equal? Thanks!
I'm sorry to ask this question because this question does not involve the correctness of the code, but is purely a question of my own understanding. After inquiring some information, I did not get a suitable answer, so I think I can only ask the question in here it is.
I don't quite understand how the
eval_of_taufunction ingeneratorworks.Here is the
eval_at_taufunction: https://github.com/zkcrypto/bellman/blob/9bb30a7bd261f2aa62840b80ed6750c622bebec3/src/groth16/generator.rs#L371-L384Its second parameter is the QAP polynomial stored in point-valued form: https://github.com/zkcrypto/bellman/blob/9bb30a7bd261f2aa62840b80ed6750c622bebec3/src/groth16/generator.rs#L313-L316
It's first parameter is
powers_of_tau, but thispowers_of_tauconfuses me. In the front, this variable is exactly what it says, it is the powers of tau https://github.com/zkcrypto/bellman/blob/9bb30a7bd261f2aa62840b80ed6750c622bebec3/src/groth16/generator.rs#L244-L259But before actually using it, make the following transformation: https://github.com/zkcrypto/bellman/blob/9bb30a7bd261f2aa62840b80ed6750c622bebec3/src/groth16/generator.rs#L294-L295
So as I understand it, from here on
powers_of_taubecomes the coefficients (a0, a1, ..an) of the polynomial f(x) such that A polynomial of the form f(x) = a0 + a1 x + a2 x^2 .... an * x^n Satisfy: f(ω0) = tau^0 f(ω1) = tau^1 ....In this case, according to the implementation of the
eval_at_taufunction https://github.com/zkcrypto/bellman/blob/9bb30a7bd261f2aa62840b80ed6750c622bebec3/src/groth16/generator.rs#L375-L381How can this be the value of a QAP polynomial at tau?
Because
powers_of_tauhas been ifft transformed before, sopowers_of_tau[index].0here should be theindexth coefficient of f(x). What is the significance of multiplying this coefficient withcoeff?I guess based on the comments, here is the equivalent to the point value form of QAP by doing Lagrangian interpolation, the formula:
$$ L(x) = \sum _{j=0}^{k} {y}_j * {l}_j(x) $$
Then
coeffis equivalent to $$ {y}_j $$Then the
jth item ofpowers_of_tauis equal to the l_j(x) corresponding to y_j?Is this guess correct? Is there any formula to prove that they are indeed equal? Thanks!