ZK-SNARKs have enabled ideation for new identity applications based on anonymous proof-of-ownership. One of the primary technologies that would enable the jump from existing apps to systems that require anonymous uniqueness is the development of verifiably deterministic signatures. Because Ethereum is based on ECDSA, there is no way right now for someone to verify that a signature is generated deterministically, even with ‘deterministic’ ECDSA signatures: a ZK-SNARK proof would need someone’s private key to do so, and some hardware wallets do not even allow viewing of a private key. Broadly, we don’t want to export/copy-paste the private key into a SNARK to be an intended user behavior, and most hardware wallets will not be able to run SNARK arithmetization inside a secure enclave for existing schemes (and nor do we want to standardize an entire proof system inside a wallet right now when they emerge and evolve almost every year). Thus we are left to select a new algorithm that offers us verifiable, deterministic nullifiers that can be SNARKed outside the enclave.
One specific example of how such a signature can lead to unique pseudonymity is that we prove it was generated correctly in a ZK-SNARK that only reveals publicly the hash(signature), and the SNARK additionally proves some property the public key has (i.e. is in some anonymity set, has executed some set of actions on chain, etc). This proof is the only thing that is ever seen by other people, and so the hash(signature) can be used as a “nullifier”: a public commitment to a specific anonymous account, to forbid actions like double spending, or allow a consistent identity between anonymous actions. We aim to standardize a new verifiably deterministic signature algorithm that both uniquely identifies the keypair, and keeps the account identity secret, where verification does not require a secret key. The specific signature function we found (and will discuss for the rest of the post) is $hash(message, public\ key) ^ {secret\ key}$.
As such, a deterministic value based on the Ethereum account’s ECDSA keypair is a necessary component of ensuring one action per user and enables all these applications on Ethereum.
We propose a new signature standard that offers the following properties, to be implemented for standard ECDSA keys within wallets:
This scheme uses the secp256k1 curve, defined in Standards for Efficient Cryptography 2 (SEC 2) v2, page 9.
We use the following notation to refer to the parameters of this curve:
Note we use exponential notation to denote elliptic curve scalar multiplications.
This scheme uses the SEC1 elliptic curve point encoding scheme defined in Standards for Efficient Cryptography 1 (SEC 1) v2. Point compression is used. We use the notation $\mathsf{sec1}(pk)$ to denote the compressed encoding of secp256k1 curve point $pk$ as a bytestring of length 33.
SHA256
This scheme uses the SHA256 hash function defined in IETF RFC 4634.
In this document, we use the notation $\mathsf{sha256}(a_1,.. a_n)$ to denote the sha256 digest of the concatenation of $n$ values $a_1, ..., a_n$. The digest should then be interpreted as a big-endian value in the secp256k1 scalar field.
We use the notation $\mathsf{htc}([a_1, ..., a_n])$ to denote the elliptic curve point which is the result of the IETF RFC 9380 secp256k1_XMD:SHA-256_SSWU_RO_ in Appendix J.8.1. This hash-to-curve algorithm operates over the concatenation of $n$ values $a_1, ..., a_n$.
A keypair comprises of $(sk, pk)$, defined as such:
This scheme builds upon the Chaum-Pedersen signature scheme 1. Given a 32-byte message $m$ and a keypair $(sk, pk)$, a user may generate a signature as such:
The signature is $(z, s, g^r, c, \mathsf{nul})$.
The length of the input to $\mathsf{htc}$ is always 65 bytes.
Note that in this scheme, we compute $h$ as the hash of the message and $pk$, not the message and $r$. This is to make our scheme deterministic.
📝 Note: This section is non-normative.
Non-ZK signature verification is not part of this proposal but relevant for an intuitive understanding of the ZK signature verification.
In a situation where the verifier knows $g$, $m$, the signer's public key $pk$, and the signature $(z, s, g^r, c, \mathsf{nul})$, they may perform the following checks to determine if the signature is valid:
Now we move onto the ZK signature verification specs.
In a situation where there is a verifier who must not know the signer's $pk$, but the signer must nevertheless prove that they know $sk$ corresponding to the signature given $m$, a zero-knowledge proof is required.
The following verification function may be described via a circuit as part of a non-interactive zero-knowledge proving system, such as Groth16. To create a proof, the prover supplies the following inputs:
Public: $\mathsf{nul}$, $c$ Private: $pk$, $r$, $s$, $z$, $g^r$, $hash[m, g^sk]$ (included to save constraints)
The circuit performs the following computations:
It also establishes the following constraints:
Currently, SHA-256 hashing operations are particularly expensive with zk proofs in the browser. In the context of PLUME, the computation of $c$ is a bottleneck for efficient proof times, so one modification suggested by the Poseidon team was to move this hash computation outside the circuit, into the verifier.
To do this, we make $z$ and $g^r$ public signals in the circuit and update the definition of $c$ to $c = \text{sha256}([\text{nul}, g^r, z])$. The updated protocol is as follows.
Public: $\mathsf{nul}$, $c$, $g^r$, $z$ Private: $pk$, $r$, $s$, $hash[m, g^sk]$
The circuit performs the following computations:
The circuit establishes the following constraints:
In addition to verifying the zk-SNARK, the PLUME verifier performs the following check.
$c == \text{hash}(\text{nul}, g^r, h^r)$
Due to SHA-256 being a native precompile on Ethereum, this operation will still be efficient for smart contract verifiers.
There may be a more efficient V3 in the future, perhaps via removing indifferentiability from hash_to_curve.
We will define a few specific properties we are looking for in a candidate algorithm, then define a few other intuitive algorithms and explain why they don’t actually work.
We based the final design to be as simple as possible, and based off of BLS signatures, Chaum-Pederson EQDL, and Goh-Jarecki’s EDL paper, but to work on secp256k1.
There are formal proofs of this specific algorithm’s cryptography in the PLUME paper 2. The theory has been published, and implementations have had one internal round of audit, but they have not end-to-end been formally verified or audited yet, although empirically they correctly conform to the spec laid out.
The Interactivity-Quantum Secrecy Tradeoff
Note that in the far future, once quantum computers can break ECDSA keypair security, most Ethereum keypairs will be broken, but migration to a quantum-resistant keypair in advance will keep active funds safe. Specifically, people can merely sign messages committing to new quantum-resistant keypairs (or just higher-bit keypairs on similar algorithms), and the canonical chain can fork to make such keypairs valid. ZK-SNARKs become forgeable, but there is still forward-secrecy for zk proofs. In the best case, the chain should be able to continue without a hitch.
However, if people rely on any type of deterministic nullifier like our construction, their anonymity is immediately broken: someone can merely derive the secret keys for the whole anonymity set, calculate all the nullifiers, and see which ones match. This problem will exist for any deterministic nullifier algorithm on ECDSA, since revealing the secret key reveals the only source of “randomness” that guarantees anonymity in a deterministic protocol.
If people want to keep post-quantum secrecy of data, they have to give up at least one of our properties: the easiest one is probably non-interactivity. For example, for the zero-knowledge airdrop, each account in the anonymity set publicly signs a commitment to a new semaphore id commitment (effectively address pk publishes $hash[randomness\ |\ external\ nullifier\ |\ pk]$). Then to claim, they reveal their external nullifier and ZK prove it came from one of the semaphore ids in the anonymity set. This considerably shrinks the anonymity set to everyone who has opted in to a semaphore commitment prior to that account claiming. As a result, there probably needs to be a separate signup phase where people commit to nullifiers in order to seed the anonymity set. This interactivity requirement makes applications such as the zk airdrop or nicer tornado cash construction (in the use cases section) much harder. However, since hashes (as far as we currently know) are still hard with quantum computers, it’s unlikely that people will be able to ever de-anonymize you.
A recent approximation of $2n^2$ qubits needed to solve discrete log via quantum annealing that failed to work on larger than $n$ = 6-bit primes shows that we are likely several decades from this becoming a reality, and the $n^2$ qubits needed to solve RSA having predictions 10-40 years out suggest that it will likely take longer than that to solve discrete log.
We hope that people will choose the appropriate algorithm for their chosen point on the interactivity-quantum secrecy tradeoff for their application, and hope that including this information helps folks make the right choice for themselves. Folks prioritizing shorter-term secrecy, like DAO voting or confessions of the young who will likely no longer care when they’re old, might prioritize this document’s nullifier construction, but whistleblowers or journalists might want to consider the semaphore construction instead.
Copyright and related rights waived via CC0.