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)?
$\begingroup$
$\endgroup$
4
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\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$ Jul 22, 2017 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$ Jul 31, 2017 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$ Sep 23, 2017 at 13:54
nzero-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$