This document serves to outline an upgrade path for Glyff to the ZCash Sapling protocol. Sapling changes the way private transactions work in ZCash, and brings with it a number of new features, increased speed, and a new set of cryptographic dependencies. In Glyff, we currently have a rough and incomplete implementation of ZCash's Sprout cryptography over Ethereum. Although ZCash has described developing a ledger-agnostic "ZCash Security Layer" (ZSL), there is no formal specification for ZSL, and the only implementation is for Sprout cryptography, and is incomplete in the sense that it suffers from transaction malleability (JPMorgan's Quorum, built on Ethereum).
It is then our goal to work out the specifics of how Sapling, which was written for ZCash, a fork of Bitcoin, can be applied to Glyff, a fork of Ethereum. Differences such as the account model in Bitcoin and Ethereum, will preclude an unmodified application of the ideas in Sapling to Glyff.
Here we describe new cryptographic primitives we'll need to use, where and how they're used in Sapling, and where we can find how quality implementations (or if we should write our own). It goes without saying that we could use the ZCash implementation of any of these primitives via the Golang ffi interface. We should expect their implementations to be fast, high-quality, and heavily reviewed. However, when there are similarly fast and high-quality alternatives, especially when written in safe languages unlike C++, we should consider using them (spoiler: there aren't for a lot of the new primitives because they're so new and ZCash specific). Additionally, ZCash also uses third-party libraries, and it would make more sense to directly hook into those libraries than effectively use them through ZCash.
JubJub is an elliptic curve designed to be efficiently implementable in zk-SNARK circuits.
JubJub is used in the Windowed and Homomorphic Pedersen commitments used in the Sapling note and value commitments, respectively.
Promising implementations include:
- https://github.com/barryWhiteHat/baby_jubjub_ecc is a standalone implementation written in C++. While it is standalone implementation and that's nicer to interface with, we can probably be a little surgical with what we take from ZCash which is a better option if we're going to do C++ ffi anyway.
- https://github.com/zkcrypto/jubjub is a standalone implementation written in Rust by Sean Bowe (@ebfull), a ZCash employee. I believe that ZCash might be interested in implementing more cryptography in Rust (which plays pretty nicely with C++) given the work @ebfull is doing and some comments I've seen Zooko make in the ring Rust cryptography library Github issue tracker. So maybe this is a potential implementation that everyone is going to use? Definitely worth watching its development.
PedersenHash is an algebraic hash function with collision resistance (for fixed input length) derived from the assumed hardness of the DLP on the JubJub curve (note: basing hash functions on intractibility assumptions is fucking cool, why aren't we all using RFSB-509 already?).
PedersenHash is used in the incremental Merkle tree over the note commitments and in Windowed Pedersen commitments.
https://github.com/barryWhiteHat/baby_jubjub_ecc appears to contain a Pedersen commitment. https://github.com/zkcrypto/jubjub does not, but I suspect that's just because it's in an earlier stage. Most of the comments from the JubJub subsection apply here too.
A Mixing Pedersen Hash Function is used to compute
MixingPedersenHash uses the same building blocks as PedersenHash.
RedDSA is a Schnorr-based signature scheme, optionally supporting key re-randomization. It also supports a Secret Key to Public Key Homomorphism. RedJubJub is a specialization of RedDSA to the JubJub curve using the BLAKE2b-512 hash function.
The spend authorization signature scheme is instantiated by RedJubJub. The binding signature scheme is instantiated by RedJubJub without use of key re-randomization.
The only existing implementation seems to be in ZCash itself.
BLS12-381 (doesn't that just roll of the tongue?) is a represented pairing.
BLS12-381 is used to define the represented group of JubJub points and in as the pairing paramaters for Groth16 proofs, which are the basis for the zk-SNARKs in Sapling.
This should be "hardcoded" in the JubJub and Groth16 implementations we use.
Groth16 refers to the use of zk-SNARKs with the proving system Jens Groth introduced in his 2016 paper "On the Size of Pairing-based Non-interactive Arguments." They are generated by https://github.com/zkcrypto/bellman instead of libsnark and use the BLS12-281 pairing parameters.
Groth16 is used to prove statements in Spend and Output descriptions.
I think the bellman library is our only option here if we want to maintain parity with ZCash, but there seem to be no front-ends like snarky that will perform DSL to zk-SNARK program conversion--they all use libsnark as a backend. This might mean we have to break from their cryptography here unless we can rig up a front-end that will turn a DSL into a circuit that is somewhat easy to feed to bellman. See https://github.com/arcalinea/bellman-tutorial for some example circuits and https://twitter.com/ebfull/status/1015352399869820928 for some information that should probably be in the bellman README.
bellman encodes the proving key and verifying key for a zk-SNARK circuit in a single parameters file. The default parameters were generated using a MPC scheme as in the 2017 paper "Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model" by Bowe et al..
These parameters are used when proving and verifying zero-knowledge statements with zk-SNARKs.
We could do our own MPC generation ceremony a-la https://www.wnycstudios.org/story/ceremony, but we could also just use the parameters that ZCash is... if we trust them.
A string derived by 42-times hashing (SHA-256) the hash of the Bitcoin block at height 514200 (presumably chosen at random).
The value is used in the definition of a JubJub related operation and was used in generating the Sapling zk-SNARK Parameters.
Again, we could pick our own URS, but there's really no reason to not trust this one given how hard it seems to pull of any sort of "up my sleeve" tricks here.
BLAKE2s is BLAKE2 flavor optimized for 8- to 32-bit platforms.
BLAKE2s is used to derive the incoming viewing key for a Sapling shielded payment address, to derive the nullifier for a note, and in computing Windowed and Homomorphic Pedersen commitments.
Currently, we are using https://github.com/minio/blake2b-simd, which does not supply BLAKE2s. There seem to be two potentially good implementations out there:
- https://github.com/BLAKE2/BLAKE2 is the Objective-C reference source code including optimized implementations for CPUs supporting SSE2, SSSE3, SSE4.1, AVX, or XOP.
- https://github.com/dchest/blake2s is a simple Go implementation of only 1465 lines that lacks CPU optimizations.
BLAKE2 is a pretty simple construction, so it would be possible to combine the work of https://github.com/minio/blake2b-simd and https://github.com/dchest/blake2s to create an optimized pure Go implementation. OTOH, the simple implementation means the C reference implementation, which certainly has been reviewed more than the the Go implementations have been (and our hypothetical one will be), is more likely to be correct. Additionally, the reference C implementation should be faster than any pure Go implementation.
I believe then that using ffi to hook into the optimized reference implementation will be our best bet here. We still need BLAKE2b in Sapling, but to reduce dependencies it's better to ditch https://github.com/minio/blake2b-simd altogether and just use the reference implementation via ffi for all our BLAKE2 needs.
This section contains notes potentially of interest when implementing changes to the wallet related to Sapling.
In Sapling there is a separate Spend transfer for each shielded input and a separate Output transfer for each shielded output. Each Spend (resp., Output) transfer is associated with an instance of a Spend (resp., Output) statement for which it provides a zk-SNARK proof. This approach allows the zk-SNARK statements to be independent of each other, potentially increasing opportunities for pre-computation. E.g., I believe it would be possible to generate the spending proofs for every note in the wallet upon receipt. Then when any number of notes are actually spent, only the zk-SNARK proofs for the Output transfers need to be computed. Note a zk-SNARK proof over all the inputs and outputs longer is used to prove mass conservation, but instead a homomorphic property of the Pedersen commitments that allows them to be added and subtracted as elliptic curve points.
A privacy concern about zk-SNARK pre-computation of this type.