This page has a listing of various projects I’ve worked on and their current status.
The core strength of Zcash is its best-in-class privacy, backed by best-in-class cryptographic design and engineering. But these core strengths were grafted onto legacy Bitcoin code, making it difficult to build tools to work with Zcash and exposing users to implementation risks.
The Zcash Foundation’s Zebra is a set of modern, modular libraries that provide a second, consensus-compatible implementation of a Zcash node or any other software that needs to work with the Zcash network, like a DNS seeder, network monitor, etc. Zebra is written entirely in Rust, uses Tower and Tokio to process events asynchronously with proper backpressure propagation, and has no main thread.
Zebra’s first alpha release occured in 2020Q4, and further development by the Zcash Foundation engineering team is ongoing. The Zcash Foundation blog has posts on its network stack, details of Bitcoin interoperability, and composable verification strategy.
A basic property of a digital signature scheme is that it should specify which signatures are valid and which signatures are invalid, so that all implementations can accept only valid signatures and reject only invalid signatures. Unfortunately, Ed25519 signatures don’t provide this property, making their use in distributed systems fragile and risky.
Although the scheme was standardized in RFC8032, the RFC does not specify validation criteria, and does not require conformant implementations to agree on whether a particular signature is valid. In addition, because the specification changed validation criteria years after deployment, it is incompatible with almost all existing implementations. Worse still, some implementations added extra ad-hoc criteria, making them further incompatible.
A complete explanation of the problem and a survey of implementation behaviors can be found in this blog post. To fix the problem, the ZIP215 rules precisely specify validation criteria for consensus-critical Ed25519 signatures which resolve this problem. These rules are implemented in ed25519-zebra in Rust and and ed25519consensus in Go, are backwards-compatible with existing signatures, and will be deployed in Zcash as part of the Canopy network upgrade.
The TCN coalition is a community of technologists, privacy experts, and epidemiologists working as fast as possible to deploy interoperable digital contact tracing tools to help stop the spread of COVID-19 without building new surveillance infrastructure or exposing users to new risks. The coalition is organized around the TCN protocol, a decentralized, privacy-preserving digital contact tracing protocol that does on-device matching and is compatible with a number of different use-cases, including authenticated reports, self-reports, self-reported symptoms, or secondary contact notifications.
My contributions included helping to write the description of trust models for contact tracing systems, the protocol description, and the reference implementation. The TCN protocol did not see wide adoption, but similar ideas were used in the Apple/Google Exposure Notification API.
Danake is a lightweight micropayment system which allows anonymous services to bill for resource usage without compromising privacy or performance. It is named in reference to the danake, a silver coin of the Persian empire commonly placed in the mouth of the deceased to pay for passage into the underworld.
Using Danake, a service provider can issue credits to users based on some application-dependent policy, and allow those users to anonymously spend those credits to pay for services. The exact policy is considered out-of-scope for Danake itself, but for instance, a service provider could periodically issue credits to each user, or allow users to purchase credits using Zcash, etc.
Danake is built using a modified form of CMZ13 credentials, implemented using my Schnorr ZKP toolkit. This provides a mechanism to create tiny “anonymous state machines” and to prove statements about their state transitions in zero knowledge with very low overhead.
Doppio applies the Decaf construction to a curve defined over the ristretto255 scalar field, providing a prime-order group which can be efficiently embedded into the language of our Bulletproofs implementation (described below). The website’s curve selection page describes the curve selection process for Doppio specifically and Decaf-friendly embedded curves generally.
The zkp crate provides a toolkit for Schnorr proofs of statements about discrete logarithms. It provides both a low-level, programmable API, and a high-level, declarative API.
The low-level API features a Bellman-inspired constraint system for Schnorr proofs, which supports (constant-time) proving, verification, and batch-verification implementations.
The high-level API uses Rust macros to allow a programmer to define proof statements in source code in a variant of Camenisch-Stadler notation. The macro expands into an invocation of the low-level API, as well as memory-safe serialization and deserialization of proof data to any serde-supported format. Unlike other comparable tools, the high-level API is intended to produce production-ready code.
Bulletproofs are a zero-knowledge proof system for range statements, e.g., \(v \in [0, 2^{64})\), as well as for arbitrary statements expressed in the language of rank-1 constraint systems. Bulletproofs are a generalization of an earlier proof system from UCL.
We wrote a memory-safe, pure-Rust implementation of Bulletproofs, using the ristretto255 group and Merlin proof transcripts. Our implementation of the range proof component set new speed records, achieving up to a 3x speedup relative to the paper’s implementation and 7x over the implementation deployed in Monero.
We also implemented multiparty computation for joint proving, using session types to have the Rust compiler check that MPC participants execute the protocol steps correctly, implemented the first programmable constraint system API for using arbitrary statements with Bulletproofs (unstable), and extended the proof system to allow randomized constraints (still in progress). This allows, e.g., asymptotically smaller proofs-of-shuffles than described in the paper.
The range proof component is completed and has a stable 2.x API. The R1CS API is unstable and in development.
Merlin is a STROBE-based transcript construction for zero-knowledge proofs. It automates the Fiat-Shamir transform, so that by using Merlin, non-interactive protocols can be implemented as if they were interactive.
This is significantly easier and less error-prone than performing the transformation by hand, and in addition, it also provides natural support for: multi-round protocols with alternating commit and challenge phases; natural domain separation, ensuring challenges are bound to the statements to be proved; automatic message framing, preventing ambiguous encoding of commitment data; and protocol composition, by using a common transcript for multiple protocols.
Finally, Merlin also provides a transcript-based random number generator as defense-in-depth against bad-entropy attacks (such as nonce reuse, or bias over many proofs). This RNG provides synthetic randomness derived from the entire public transcript, as well as the prover’s witness data, and an auxiliary input from an external RNG.
The fastest formulas for elliptic curve operations were published by Hisil, Wong, Carter, and Dawson in their 2008 paper Twisted Edwards Curves Revisited. Their paper also describes a parallel version of their formulas, designed to execute four streams of field arithmetic instructions on four independent processors. Because the field arithmetic operations to be parallelized are much less expensive than the cost of thread synchronization, these were never implememented in software.
But a closer look reveals that slightly modifying the formulas allows the expensive instructions to be executed uniformly, and that the divergence in the instruction streams are only on the inexpensive operations. This means that it is possible to practically realize the 4-way parallelism using a vectorized SIMD implementation, handling instruction divergence using masking.
I implemented this strategy for Curve25519, using AVX2 and IFMA instructions, and set speed records.
During a 3-month summer internship at Cloudflare in 2017, I designed a quantum-resistant version of TLS 1.3 using a hybrid key agreement mechanism combining X25519 and supersingular isogeny Diffie-Hellman, wrote a implementation of SIDH in Go, and also implemented TLS 1.3 client support for Go (which did not yet exist at the time). A derivative of this work is now available as an internet-draft.
Ristretto is a technique for constructing prime order elliptic curve groups with non-malleable encodings. It extends Mike Hamburg’s Decaf approach to cofactor elimination to support cofactor-\(8\) curves such as Curve25519, and provides a specific instantiation, ristretto255, which can be implemented using Curve25519.
In particular, this allows an existing Curve25519 library to implement a prime-order group with only a thin abstraction layer, and makes it possible for systems using Ed25519 signatures to be safely extended with zero-knowledge protocols, with no additional cryptographic assumptions and minimal code changes. In addition, Ristretto is carefully constructed so that implementations may use a faster elliptic curve internally, and remain wire-compatible in all functionality, including hash-to-group.
A list of implementations and test vectors are available on the Ristretto website.
curve25519-dalek is a pure-Rust library providing group operations on the Edwards and Montgomery forms of Curve25519, and on the prime-order Ristretto group.
Rather than providing an implementation of any particular protocol, curve25519-dalek is intended to provide a clean and safe mid-level API for use implementing a wide range of ECC-based crypto protocols, such as key agreement, signatures, anonymous credentials, rangeproofs, and zero-knowledge proof systems.
The library demonstrates that it is possible to create safe, misuse-resistant mid-level APIs, and to implement them in legible, memory-safe Rust, with no loss of performance compared to other implementations.
Subtle is a pure-Rust library for constant-time cryptographic operations, intended as a low-level building block for cryptographic implementations.
Finding a short element \(g\) of a number field, given the ideal generated by \(g\), is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in some cryptosystems. We constructed a polynomial-time algorithm to solve this problem for the special case of multiquadratic number fields. (Accepted to EUROCRYPT’17)