New Crypto Foundations (Zcash) fully hide your identity

Zcash's next major protocol upgrade, codenamed Sapling, will feature a number of improvements to the performance, security and usability of our shielded transactions. This is the first in a series of blog posts that will explore progress made in Sapling's development.

The speedups are especially pronounced in pairing and G2

arithmetic, which increases the performance of zk-SNARK proving and verification.
New multi-exponentiation algorithm

The most expensive part of creating a zk-SNARK proof is the evaluation of large polynomials over the elliptic curve groups G1
and G2. This is done with a so-called "multi-exponentiation" algorithm that computes ∏ni=0bsii for some large number of exponents s⃗ which reside in memory, and a large number of bases b⃗

which reside on disk inside the zk-SNARK proving key.

Currently, we use libsnark's implementation of the Bos-Coster algorithm. In the worst case, this algorithm uses as much memory as the number of bases being operated on, and so the only avenue for decreasing memory usage is working with smaller subsets of the bases at a time. As an example, Ariel Gabizon implemented this kind of an optimization in a change to libsnark.

libsnark has recently implemented a variant of Pippenger's algorithm which splits the multi-exponentiation into bitwise regions of the exponent, accumulating bases into buckets and performing summation by parts. This algorithm is not only more efficient than Bos-Coster, but is very convenient in the context of streamed proving. With this algorithm, we can avoid loading the proving key into memory before constructing a proof, which is a primary source of memory usage in our system.

New proving system

Of course, performing fewer multi-exponentiations would also be a nice way to improve runtime performance. We are strongly considering the use of a new zk-SNARK proving system, discovered by Jens Groth, to replace PGHR (Pinnochio). This proving system makes stronger cryptographic assumptions, but has smaller proofs and faster proving/verification.

What’s more, Groth’s new proving system allows us to design cheaper multi-party computations and other really interesting features that we’ll talk about more in a future blog post.
Next steps

Although the above efforts combined offer substantial improvements to memory usage and proving time, reducing the size of our zk-SNARK circuit will have a much more noticeable effect. We have built a number of new crytographic primitives on top of the BLS12-381 construction which allow us to shrink the size of our arithmetic circuits, reduce the size of Zcash addresses, and simplify the protocol.

In our next blog post, we'll talk more about these primitives and how much all of these improvements will help performance of our zk-SNARKs.