4
$\begingroup$

Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 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$
    – Sean
    May 25 '20 at 14:14
  • 1
    $\begingroup$ Start from splitting exponent "y" into bits, then square-and-conditional-multiply loop. @Sean $\endgroup$
    – Vadym Fedyukovych
    May 27 '20 at 14:08
  • $\begingroup$ That's right! Thanks again! $\endgroup$
    – Sean
    May 28 '20 at 0:00
  • $\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$
    – Sean
    May 28 '20 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$
    – Vadym Fedyukovych
    May 29 '20 at 14:38
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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