Aztec Grant Application - PLUME Library

Project

Noir Library for PLUME

PLUME is an emerging standard for anonymous nullifiers that is compatible with existing Ethereum keys and hardware wallets. This has numerous applications in anonymous voting, airdrops and other applications.

The design of PLUME ensures all operations that require a private key can be performed out-of-circuit in a secure element such as a hardware wallet. The client side operations have been implemented for different wallets^[1].

This application is to implement the PLUME verification circuit in Noir for the secp256k1 curve that maintains compatibility with existing Ethereum keypairs and the existing PLUME client side library.

PLUME is parameterized by the choice of curve and hash function. This will be reflected in the implementation using traits and generics in Noir.

Implementation Details

The primary operation in-circuit to prove/verify a PLUME nullifier is a hash-to-curve operation, with the remainder being relatively simple hashing and equality check. The core of this proposal is an efficient and secure implementation of hash-to-curve in Noir.

Hash-to-curve

The draft IEFT standard^[2] specifies the details of the hash-to-curve ciphersuite. This can be split into two main operations of hashing to a finite field (hash_to_field) and mapping to a curve (map_to_curve).

Hashing to field applies a regular hash function then expands the result into a number of elements in the chosen field (which can be implemented as generic over the Noir Hasher trait).

Mapping to curve implementation differs depending on the type of curve. The specific secp256k1 map_to_curve implementation uses a simplified SWU method ^[2:1] over a different curve that is isogenous to the secp256k1 curve followed by an isogeny map. As shown in the circom implementation the isogeny map can be implemented in terms of simple field arithmatic operations.

The final part of hash_to_curve involves one call to hash_to_field and two calls to map_to_curve followed by an elliptic curve point addition.

In ^[3] it is estimated that the entire hash-to-curve operation requires ~500k constraints when implemented for the groth16 proving system and we can expect comparable complexity for a Noir implementation.

The proposed implementation in Noir will build upon the BigField implementation in the standard library which supports the secp256k1 base field.

PLUME

Given a message

$m$, curve generator

$g$, ECDSA keypair

$(sk,pk\leftarrow g^{sk})$, secure random value

$r$, a hash-to-curve implementation

$\text{hash2c}()$, and cryptographic hash function

$\text{hash}()$, the PLUME circuit can be defined as follows:

Given private inputs:

• $c\leftarrow \text{hash}(g,pk,\text{hash2c}(m,pk),\text{nullifier},g^r,{\text{hash2c(m, pk)}}^r)$
• $pk$
• $x\leftarrow g^r$
• $y\leftarrow {\text{hash2c(m, pk)}}^r$

and public inputs:

• $\text{nullifier}\leftarrow \text{hash2c}(m,pk{)}^{sk}$
• $s\leftarrow r+sk\ast c$

the circuit must check the constraint

$$c=\text{hash}(g,pk,\text{hash2c}(m,pk),\text{nullifier},x,y).$$

The primary operations required in-circuit are a hash-to-curve operation and a regular cryptographic hashing of curve points. No elliptic curve operations are required as part of the PLUME nullifier check outside of hash-to-curve.

Prior Work

There is an existing Circom implementation of PLUME which makes use of the Circom implementation of hash-to-curve for secp256k1 implemented by Geometry Research.

• PLUME implementation
• https://github.com/geometryxyz/secp256k1_hash_to_curve

Additionally the work done by Geometry Research on standardizing hash-to-curve for common curves including secp256k1 and the resulting IETF draft standard.

• https://geometry.xyz/notebook/Hashing-to-the-secp256k1-Elliptic-Curve
• https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html

A prototype Noir implementation of hash-to-curve following the IETF standard exists however this appears unmaintained, uses an older version of Noir, and depends on obsolete libraries for curve and bigint operations.

• https://github.com/skaunov/hash_to_curve/

Regardles this is a useful resources that can serve as a reference.

Testing

Hash-to-curve

The IEFT draft standard provides complete test vectors for common instantiations of hash-to-curve and Noir tests can be programatically generated from these.

• https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#name-suite-test-vectors
• https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve

PLUME

A full test suite will be written in Noir following the examples set out in the PLUME circom implementation tests.

Milestones

1. Implementation of hash-to-curve crate (2 engineers, 1.5 weeks)

• Implement hash_to_field generic over hash algorithm
• Implement map_to_curve variant specific to secp256k1
  • Implement Simplified SWU algorithm for isogenous curve
  • Implement isogeny map to secp256k1
• Autogenerate tests from specification
• map_to_curve implementation

2. Implementation of PLUME (2 engineers, 0.5 weeks)

• Implement PLUME constraint verification generic over curve and hash-algorithm
• Port tests from circom implementation specific to secp256k1 curve.

About the team

ChainSafe R&D

ChainSafe R&D is a consulting team within ChainSafe with specialized skills in cryptography and systems design. Founded in 2020 we have successfully delivered projects for dozens of notable clients including:

• Ethereum Foundation
• Mina
• ZCash
• Protocol Labs
• Gnosis

We have experience developing production ready ZK implementations of cryptographic primitives. Notably a Halo2 implementation of BLS12-381 pairings which has been audited and is used in the Sygma cross-chain protocol.

• Implementation
• Audit repot

Team

Willem Olding

• PhD in Engineering (signal processing)
• Rust developer with 6 years professional experience
• Previously lead developer for Mina-rs

Sebastian Lindner

• PhD in Computer Science (cryptography and number theory)
• Prior researcher in the field of hyper-elliptic curves including low-level optimized implementations

Additional support requests

• A shared chat for any Noir related questions would be appreciated

Additional Details

ChainSafe is happy to accept fully retroactive payment only upon successful delivery of all above milestones.

---

---

1. https://github.com/plume-sig/zk-nullifier-sig ↩︎

2. https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html ↩︎ ↩︎

3. https://blog.aayushg.com/nullifier/ ↩︎