Reducing Shielded Proving Time in Sapling

Since the successful Sapling network upgrade, we have already seen an increased adoption of shielded addresses in the Zcash ecosystem. Services like mining pools are beginning to offer shielded address payouts to customers. Further, the number of third-party desktop wallets supporting shielded addresses is also rising. Looking ahead, shielded address light client support will promote even wider adoption. This is just the beginning for Zcash’s mission toward a shielded ecosystem.

The increased adoption of shielded addresses is due to the underlying advancements of Zcash cryptographers. They have developed and implemented significant changes to the zero-knowledge proving mechanism in Sapling. Years of research and cryptographic design work have produced these improvements which build upon existing schemes and invent new ones.

Three improvements

Proving time reduction from Sprout's 37 seconds to Sapling's 2.3 seconds

In order to understand the advancements used to reduce proving time and memory costs, we can break down the overall implementation into three components.

Bowe-Hopwood Pedersen Hash

The first of these comes from Zcash cryptographers, Sean Bowe and Daira Hopwood. Their work improved the efficiency of the Pedersen hash function for use in Zcash’s zk-SNARK circuit.

Proving time reduction of 75% in Sapling due to replacing the zk-SNARKs hashing function

The majority of the zero-knowledge proof operation in shielded transactions consists of generating hashes. Therefore, an improvement here has a significant effect on the time requirements. By replacing the pre-existing SHA-256 hash with the new Bowe-Hopwood Pedersen hash, the time for shielded address payments in Sapling is already reduced by 75%. For details on this, refer to the Zcash protocol specification at section 5.4.1.7 “Pedersen Hash Function.”

Bellman

The second component we’ll consider is the zk-SNARK implementation, which involves two subcomponents. First is the elliptic curve construction and second is the proving system. The legacy implementation is a Zcash fork of libsnark which uses elliptic curve bn128 and the proving system described in BCTV2015 (“Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture”).

Proving time reduction of 50% in Sapling due to replacing the zk-SNARKs circuit implementation from libsnark to bellman

The zk-SNARK circuit implemented for Sapling uses a new elliptic curve construction, BLS12-381, which not only offers better performance but more security than the previous curve. This circuit also uses a more recent proving system as described in Groth16 (“On the Size of Pairing-based Non-interactive Arguments”). Jens Groth’s system computes less than half of the number of proof elements compared to the original proving system. The Rust-language library, bellman, applies these improvements which overall, offers another 50% increase in efficiency. Learn more about Zcash’s zk-SNARKs circuit on the technology overview page.

Split Circuit

The final of these is a split circuit design which replaces the use of JoinSplit transfers in legacy shielded addresses.

Proving time reduction of 50% in Sapling due to implementing a split circuit design

Not only does the split circuit design reduce computation time another 50% but it also allows for more granularity in generating a zk-SNARK for shielded address payments. The number of notes spent and created in a transaction determine the variation in proof creation time. This is also the reason that the transaction anatomy is different in Sapling. For more details about the split circuit design, see section 3.6 of the Zcash protocol specification “Spend Transfers, Output Transfers, and their Descriptions.”

Beyond Sapling

Each of these components alone represent a significant achievement, so suffice it to say that together they deliver a substantial victory. The technological achievements produced for Sapling offer more than an upgrade to Zcash as well. Particularly the bellman library discussed above is a widely applicable tool for working with zk-SNARKs and we encourage other projects to explore the potential opportunities for its use. Keep an eye out for more documentation and don’t hesitate to reach out in the online community if you’re interested in digging deeper.