ZEXE - Zero-knowledge EXEcution

ZK Study club is a learning group where people from the zero-knowledge/Blockchain community gather to study a specific topic. There have been so far nine sessions that discussed several cryptographic topics. The first four sessions broke down the ZK-STARKs, the fifth session was a deep dive into RSA accumulators, the sixth was about Sigma protocols, the seventh discussed the Fiat-Shamir heuristic and the eighth was about multi-party computations. The sessions are usually recorded and put available online:

• session 1: ZK-STARKs
• seesion 2: ZK-STARKs
• session 3: ZK-STARKs
• session 4: ZK-STARKs
• session 5: RSA accumulators
• session 6: Sigma protocols
• session 7: Fiat-Shamir heuristics
• session 8: Multi-party computations

The ninth session happened last Monday 6th May and was the first of a series about the recent paper called “Zexe: Enabling Decentralized Private Computation” by Sean Bowe from ZCash, Alessandro Chiesa, Pratyush Mishra and Howard Wu from UC Berkeley, Matthew Green from Johns Hopkins University and Ian Miers from Cornell Tech. I had the chance to lead this session and discuss the paper’s ideas with wonderful community enthusiasts. The video can be found here and the session’s notes here.

Basically, the aim behind Zexe is to write private smart contract on a distributed ledger. Such a scheme can be constructed by doing offline computation and uploading a proof of correct execution to the ledger. The proof should be zero-knowledge, succinct and easy to verify. To do this, the paper introduces a new cryptographic primitive called decentralized private computation (DPC) and comes up with some efficient implementation tricks that range from zkSNARK optimization, recursive proof composition and a new set of elliptic curves.

The starting point of Zexe is to extend Zerocash protocol to more general token-based blockchains. This protocol provides a privacy-preserving version of Bitcoin-like blockchains via the use of zero-knowledge proofs (ZKP). To create a coin a user publishes a commitment and to consume it he publishes its unique serial number alongside some ZKP that the serial numbers belong to some old coins and that the commitments preserve the same total value. In Zexe, an integer value coin is a data payload record and the ZKP assures that an arbitrary function was applied to old records to create the new ones. The problem now is, if we want the function to be user-defined, how can we make sure it stays private, and if so, how can we isolate “malicious” functions from “honest” functions? One straightforward solution would be to add a ZKP that proves the same function was used; this basically boils down to using a Zerocash per function (i.e. per token) which results in a functionality limitation as one cannot do private cross-token swaps for instance and moreover the anonymity set would be limited to each each specific token history. Another solution would be to use a universal function on the ledger and embed user-defined functions within the data payload. To do this, we need a minimalist shared execution environment (some sort of an operating system) where different processes can be executed without violating the privacy of each. Zexe calls it records nano-kernel where a record is now: data payload, birth predicate for records creation, death predicate for records consumption, transaction memorandum for public input needed by the predicates and auxiliary input for private input. The problem now is, if the predicates are arbitrary functions, do we need a SNARK per predicate or a universal SNARK? While awesome research is being conducted to propose a universal SNARK like Sonic, efficient implementations are yet to come. A solution to the cost of universality would be to do “a proof of a proof”, that is, generating a proof of the predicate and then generating another proof of the previous proof that will be verified on the ledger. This way, we need a single circuit on the ledger and a circuit per predicate offline.

While empirically proved via cycles of elliptic curves, recursive proofs are not efficient at 128-bit security level. In fact, a SNARK proof (i.e. in Groth16) is a set of points on an elliptic curve that has a subgroup of order $n$ so the generation has arithmetic in $\mathbb{F}_n$ whereas the verification uses p airing computations where most of the computations are on an extension of the field size $p$. This causes an arithmetic mismatch that results in an overhead of $log(p)$ when one wants to implement naïvely a verification circuit. The solution to this is to use a cycle of elliptic curves where the field size of one is equal to the subgroup order of the other and vice-versa. The only pairing-friendly cycle of elliptic curves we know is the set of MNT4 and MNT6 curves that have a low embedding degree and thus are not quite efficient at 128-bit security level. In Zexe scheme, we need merely a proof of a proof so the authors came up with a chain of elliptic curves rather than a cycle, namely a Cocks-pinch curve embedded over a BLS curves that is highly 2-adic with respect to both the field size and the subgroup order.

This is somewhat an overview of Zexe, but the paper includes more contributions such as delegating the generation of a proof to an untrusted worker (delegated DPC), minimizing operations over the (heavy) embedded cocks-pinch curve, optimizing the NP statements à la Zcash and more…