Projects

This page has a listing of various projects I’ve worked on and their current status.

Doppio

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.

Status: In Progress

Website

Code

Joint work with Cathie Yun.

Schnorr zkp toolkit

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.

Status: In Progress

Code

Bulletproofs

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 1.x API. The R1CS API is unstable and in development.

Status: In Progress

Website

Code

Joint work with Cathie Yun, Oleg Andreev.

Merlin

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.

Status: Complete

Website

Code

Parallel Edwards Formulas

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.

Status: Complete

Website

Code

Ristretto

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.

Status: Complete

Website

Joint work with Mike Hamburg, Isis Lovecruft, Tony Arcieri.

curve25519-dalek

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.

Status: Complete

Website

Code

Joint work with Isis Lovecruft.

subtle

Subtle is a pure-Rust library for constant-time cryptographic operations, intended as a low-level building block for cryptographic implementations.

Status: Complete

Website

Code

Joint work with Isis Lovecruft.