Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
final_exp_gadget<>() of libsnark could be a practical example to tune for DLP. The idea is, "final exponentiation" is a part of Ate pairing, that is verified as a part of check_e_equals_e_gadget<>(), which stands for Groth16 verification equation.
answered May 24, 2020 at 0:56
-
1$\begingroup$ Just curious, if R1CS is eventually translated into arithmetic gate circuit, how would the expnentiation like x^y is encoded as a circuit? Would we end up with a loop of multiplication gates, since "y" is a variable here. $\endgroup$– SeanMay 25, 2020 at 14:14
-
1$\begingroup$ Start from splitting exponent "y" into bits, then square-and-conditional-multiply loop. @Sean $\endgroup$ May 27, 2020 at 14:08
-
-
$\begingroup$ I'm looking at zokrate (instead of direclty cut into the libsnark as you suggested) - it looks like its language spec does not support power operations also the loop is bounded. Are there any particular reason for this? -- in another word, could this make proof generation too costly in zksnark? (looks like not to me - as square-and-multiply would be linear with the number of bits - the number of gates needed cound't be a very large number) $\endgroup$– SeanMay 28, 2020 at 0:42
-
1$\begingroup$ Zokrates is still in my todo pipline, sorry. Gate cost/complexity should be the same as with libsnark, as you suggested. $\endgroup$ May 29, 2020 at 14:38
$\begingroup$
$\endgroup$
Yes, for sure! R1CS is an NP-complete language. It is basically a characterization of arithmetic circuits, hence every computation can be expressed as a R1CS.
There are compilers that reduce program executions to R1CS. One of my favourite tools is Zokrates.
answered May 23, 2020 at 7:55