Let a, b be two statements. Given succinct (fixed size) zero-knowledge proofs z(a), z(b) that a, b are true, how easy is it to build z(a AND b)?

| improve this question | | | | |
  • $\begingroup$ For what succinct ZK schemes? ​ ​ $\endgroup$ – user991 May 28 '17 at 6:06
  • $\begingroup$ I'm interested in ZK schemes similar to the zksnarks used in zcash (z.cash) $\endgroup$ – Randomblue May 28 '17 at 6:52
  • 1
    $\begingroup$ What's the issue with just sending z(a) et z(b) ? $\endgroup$ – Geoffroy Couteau May 29 '17 at 17:00
  • 1
    $\begingroup$ @GeoffroyCouteau I'm looking to agglomerate n zero-knowledge proofs into one for conciseness. Each zk-SNARK proof is 288 bytes and I want to "compress" n*288 bytes into just 288 bytes. $\endgroup$ – Randomblue May 30 '17 at 9:22

One way to do this is to construct two pairing-friendly curves such that the scalar field of the "outer" curve efficiently supports arithmetic for the "inner" curve. Then you can define a circuit for a zk-SNARK over the outer curve, that can verify proofs of a zk-SNARK over the inner curve. This can be done by constructing the outer curve using the Cocks-Pinch method, as in Zexe. In this case you would use an efficient zk-SNARK proving system such as Groth16, to reduce the cost of verifying the inner proofs.

Since I first wrote this answer, another approach has become available using $2$-cycles of non-pairing-friendly curves, as in Halo. (I'm a codesigner of Halo, with Sean Bowe and Jack Grigg.)

The #zcash-wizards channel of the Zcash community chat is a good place to ask about such things.

(This answer previously included a suggestion to use a nested pair of curves with the inner curve as BLS12 and the outer curve as BN. In fact there's no known method of matching up the base field of the BLS12 curve with the scalar field of the BN curve, and there are good reasons to believe that it is not possible to do so.)

Note that any of these approaches will only pay off if the number of proofs being aggregated is large.

| improve this answer | | | | |
  • $\begingroup$ "Cycles of elliptic curves" term was introduced for a pair of curves such that order of the group of points on the first curve is field characteristic the second curve is defined over, and this also holds for curves the other way (switched first-second). youtube.com/watch?v=cLjfufsi2gM starting 41:00 $\endgroup$ – Vadym Fedyukovych Jul 22 '17 at 19:57
  • $\begingroup$ May I suggest that pair of curves is only a part of the answer? It would be nice to have a bird-view of how this particular AND translates into polynomials, "quadratic arithmetic" program, recursion. Yes, I'm aware it is not easy to write that down. It might be reasonable to skip easy known parts like general bilinear pairing and knowledge of exponent assumption. $\endgroup$ – Vadym Fedyukovych Jul 31 '17 at 21:21
  • $\begingroup$ Well, the AND is just a single multiplication constraint. The hard part is optimising the number of R1CS constraints required to implement the pairing operations in the Groth16 proof verification. $\endgroup$ – Daira Hopwood Sep 23 '17 at 13:54

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.