Earlier this year we partnered with the Zcash Foundation to bring threshold signatures support to Sapling. In this blog we want to share with the community about our progress and some exciting results we got so far. The highlight is that for the first time we were able to run a Zcash full node, patched to support 2 party Sapling shielded transactions. Proof of Concept is hereby released. The blog is highly technical and structured as a series of challenges we faced.
Motivation and Background
Shielded transactions are opt-in type of transactions in the Zcash blockchain that provide complete privacy: sender, receiver and amount cannot be derived from looking at the public blockchain.
This strong privacy guarantee is cryptographically assured using zero-knowledge technology. Sapling is the latest network update to Zcash. With Sapling, shielded transactions have become efficient to the point of running them in a few seconds on any consumer-grade hardware such as mobile devices.
It is also useful to off-load the heavy computations involved to a third party without compromising on security (see note in Sapling protocol specification, section 4.13).
However, Sapling does not support multi-signature with privacy, which we call here “threshold shielded transactions”. This is a basic feature in most blockchains, allowing for different access structures to sign a transaction and to add secure HW elements to the signing process. In this blog post we show a step by step what it takes to add such support directly into Zcash core.
Challenge #1: protocol design
Sapling signature scheme, called Redjubjub, is a Schnorr-like signature scheme with some additional design choices made by ECC cryptographers, partly inspired by EdDSA signature scheme.
The key tree structure in Sapling is involved as can be seen below. Our challenge was to come up with a scheme that answers the following demands:
- Can work for a general number of actual signers (threshold t) out of the group of potential signers (n)
- Provable secure
- No significant change to the key tree or protocol, i.e. no change to the zk-snark that is used to prove knowledge of some of the keys as part of the statement.
A description of our multiparty RedJubjub can be found on our github.
We ended up changing the lowest level of the key tree: ask is no longer the result of key derivation from sk but computed in distributed manner between untrusted parties. In fact ask is never constructed in a single place. The parties only share the derived ak which is also shared as part of the Sapling protocol with a third party that help with the computation of the zero knowledge proofs. We assumed that this party might as well participate in the multiparty signing (the third party cannot produce a signature by itself and we don’t give it any extra power). This means that the privacy we get in the multiparty computation is against blockchain on-lookers as with the original Zcash protocol, however there is no privacy between the parties running the protocol. We think that it is acceptable as most use cases are of one party that will want to run the computation on multiple self owned devices. We leave for future work to make the scheme private towards some of the signing parties as well.
We use simulation-based security for our scheme and do not use any extra security assumptions over what is already used in Sapling. The protocol is extremely efficient with small overhead in computation. It is highly likely that some parties could be run on hardware devices.
Challenge #2: re-using Zcash cryptography
As common in the blockchain space, everything is built on Elliptic Curve cryptography. Sapling is using a unique elliptic curve called Jubjub: Jubjub is a twisted Edwards curve built over the BLS12-381 scalar field. Since this EC is relatively new and used mainly in Zcash the only implementation of Jubjub arithmetic is the one used in Zcash.
The bad news is that we need for the multiparty computation to run some general purpose computations on Jubjub EC points and BLS12-381 scalar field.
Unfortunately, the library for Jubjub is built to support Zcash Sapling and not so much as API that can be used by other consumers who wants to work with this curve. The good news is that the Zcash implementation, LibRustZcash is solid: it is written in Rust which is also our language of choice, it is being constantly reviewed and audited and a bug there could lead to bug in Zcash.
What we have ended up doing is forking LibRustZcash, stripped it from unnecessary code (for example zero knowledge related) and plugged it as part of our general purpose Elliptic Curve library. The by-product is that now anyone can use Jubjub for any computation in a safe way.
Challenge #3: Integrating multiparty-RedJubjub Into Zcash Full Node
Now that we had the cryptographic building blocks and the updated protocol it was actually straightforward to write “Paradise-city”: a two-party RedJubjub proof of concept library. This worked well in a stand-alone mode but it is not worth much unless we can demonstrate it can work as part of the full node code.
The biggest challenge was not to interfere with the zero-knowledge proof generated as part of the transaction. As can be seen in the Sapling specs of the proof (4.15.2) there are elements from the spending signature protocol that are also used in the zero-knowledge proof. Moreover the Zcash code was never designed to include interactive protocols between signers to derive some of the key matariel. To this end we needed to dive deep into both Zcash code architecture and cryptographic implementation of the zero-knowledge proof.
Few comments are in place on the Zcash full node architecture – It is a C++ code that calls methods from LibRustZcash Rust code for the cryptography in the protocol. The dependencies are “vendored” such that each library that Zcash code uses needs to be added manually and verified against hardcoded checksum.
Since our code is not vendored we rewrote Paradise-city library to minimize its dependency tree by %80, reusing as much as possible Rust libraries that are already part of Zcash codebase. The rest were added manually. We plugged the Paradise-City distributed Key Generation and distributed Signing methods as replacements for some of the original methods in LibRustZcash and used some glue logic to make our types and LibRustZcash types compatible. In addition, we made some minor changes to the C++ code. Here are links to the patched LibRustZcash and the patched zcash full node code. Finally we run a proof of concept on zcash 2.0.5 for testnet and stand alone regtest (should probably work on newer versions).
In this demo we are running a patch zcash node in regtest mode (lower window). In the upper window we are operating a client wallet. At first, the wallet mine some coins into a transparent address it owns. We then invoke a 2 party key generation, simulating both parties locally. As a result we generate a shielded address with a distributed key. We move some funds from the transparent address to the shielded address of the wallet. Finally we generate new shielded address running a 2 party signature protocol to sign a shielded transaction, transferring funds privately from the first shielded address to the second.
The full instructions on how to run this demo and documentation on how to add new libraries can be found here.
Threshold shielded signatures are coming to Zcash probably as part of NU3 activation. It is now in the hands of the ZF engineers as part of the roadmap for 2020. We hope that our proof of concept served as a stepping stone towards building this useful tool in robust manner. Zcash is an important digital asset with unique privacy properties. It would be an excellent candidate to include in ZenGo in the future. Please use our telegram research group for any follow-up question.
Finally we would like to thank Ariel Nof for designing the protocol and prove its security.