Sapling audit

QED-it just released its enterprise private asset transfers solution (v1.0.0) incorporating privacy based on Zero-Knowledge Proof technology. Working with the teams in this space, we developed a great appreciation for the Zcash team. We have learned, and still do, a lot from their research work. Moreover, both Zcash and QED-it are pioneers of the ZKProof effort, where we collaborated to write the track proceedings.

We were glad when the Zcash team asked us if we could review the Sapling implementation. We happily agreed to audit the code, as we had already been following the development and found much of the technology interesting.

Given our experience in implementing zkSNARK circuits, we chose to focus on the implementation of the constraint system of the Sapling protocol, as implemented in sapling-crypto. The auditing team included Aurélien Nicolas, Daniel Benarroch and myself, and we spent the majority of two weeks auditing the code and spec. The report on the work and our findings is available here.

Our main contributions in this work have been the review of the circuit implementation at the level of the constraints, both by writing analyses of various sub-circuits and implementing the protocol as described in the specification to produce independent test-vectors. You can find this code in the following repository, as well as various pull requests/issues in the parent repositories.

The Sapling protocol has many improvements over the previous version of Zcash, which was based on the Zerocash paper. Among other things, the transaction validity is now checked by verifying two different kinds of proofs, the spend and output proofs, rather than the single JoinSplit in Sprout. For us, it was important to understand exactly what are the different components of the protocol. In order to visualize how each of these came together, we drew two diagrams, as seen below.

The output circuit description

Another very interesting aspect of Sapling is the introduction of cryptographic primitives which are SNARK-friendly, which, among other things, help reduce considerably the prover’s running time and memory consumption. One of the first things we did was to map out the new construction from the perspective of how the different cryptographic modules interact:

Modules dependencies and usage in Sapling

In conclusion, we mainly have good news — we haven’t found any critical issues in the circuit implementation. We’ve identified a few implementation bugs and specification mismatches that do not affect the current uses of this code.

We were happy to be a part and hope we continue collaborating on making zero-knowledge proofs run in production!

As a side note - another small personal contribution from the audit team was the participation in the two rounds of the Sapling trusted setup MPC, where each of us went through different routes of enhancing their contribution, although Daniel did eventually decide to be dishonest and expose his toxic waste!

Joint post with Daniel Benarroch