4
$\begingroup$

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)?

$\endgroup$
  • $\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
4
$\begingroup$

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.

I believe that the libsnark authors have generated such pairs of curves, so you might want to ask them about it (the #zcash-wizards channel of the Zcash community chat would be a good place to ask).

Edit: The most efficient approach I'm aware of is for the inner curve to be a BLS12 construction and the outer curve to be BN. The argument goes as follows: BLS12 has a significant gap between the sizes of the scalar field and the field over which the curve is defined, whereas BN only has a gap of a few bits. For roughly 128-bit security, the scalar field needs to be >= 254 bits (to resist Pollard-rho), and the field over which the curve is defined needs to be >= 384 bits if the embedding degree is 12 (to resist index calculus attacks on G_T). Therefore, using BLS12 for the inner curve optimises its resistance to both Pollard-rho and index calculus attacks, while minimising the field sizes to speed up arithmetic. For the outer curve, on the other hand, the scalar field size has to be >= 384 bits already in order to match the field over which the inner curve is defined. Therefore the optimal curve type for the outer curve is BN, because then the field over which the outer curve is defined will be no larger than necessary.

Also, use an efficient zk-SNARK proving system such as Groth16 (which Zcash will probably be moving to), to reduce the cost of verifying the inner proofs.

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

$\endgroup$
  • $\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.