For anyone reading, I’ve gathered much more information about this. Here’s what I’ve learned.
1. Key Derivation
In elliptic curve cryptography, key derivation is pretty much always the same and independent of the signature scheme. It’s based on the discrete logarithm problem, and once the specific curve is defined, deriving the keys is pretty straightforward. The discrete logarithm problem says that given:
- a very large prime p that’s specific to the curve,
- a field F_p with arithmetic operations modulo p,
- an arbitrary value x \in F_p,
- a point P expressed as a pair of affine coordinates (or alternatively as a triple of projective coordinates) on F_p,
- a special sum operation between points that I’m not delving into here but it’s provided in the
pasta_curves crate,
- and Q = x \cdot P (meaning that P is added up x times with the aforementioned sum operation),
it’s infeasible to recover x from Q knowing only P. So key generation in elliptic curve cryptography is pretty straightforward:
- come up with a random x and that’s the private key;
- the public key is P = x \cdot G, with G being a special point of the curve known as the generator;
- convert P to affine coordinates to reduce it to a pair of 256-bit numbers;
- use only the X coordinate to communicate the public key, as the Y coordinate is obtained by simply evaluating the elliptic curve in X; this way the public key is a single 256-bit number.
With all this, the answer to my original question is: yes, the ff and pasta_curves crates are more than enough to derive Pasta keypairs (if one is willing to take the risk of implementing a minor amount of cryptography).
2. Signature Scheme
I’ve learned that EdDSA is not even the best choice for SNARK-friendliness. Schnorr is better! (AIUI Schnorr is more general than EdDSA but don’t quote me on this.)
There are some crates to deal with Schnorr but then again, once you have things like ff the math behind it seems to be so straightforward that it’s actually worth taking the risk of implementing some amount of cryptography first-hand rather than the burden of an extra dependency (that may grow stale, may be no longer maintained, etc.).
I think it’s worth summarizing the Schnorr signature and verification algorithms here for anyone interested. Should anyone notice mistakes please call them out and I’ll edit.
Definitions
- G = the generator point of the curve.
- p = a large prime specific to the curve.
- n = a secret random nonce in F_p.
- m = the message to sign (it should also contain its own nonce / timestamp / whatever to prevent replay attacks).
- x = the private key of the signer.
- P = the public key of the signer.
- H = a suitable hash function (Poseidon is recommended for zk-SNARK friendliness).
Schnorr Signature
- Generate the nonce n (such that n \in F_p) with a cryptographic PRNG.
- Compute the nonce commitment point:
N = n \cdot G
- Compute the challenge hash:
c = H(N || P || m)
- Compute the response scalar:
s = n + c \cdot x \mod{p}
- The signature is the pair
(N, s)
Note: x remains secret and unrecoverable from (N, s) because:
- n is unrecoverable from N due to the discrete logarithmic problem;
- if you don’t know n you can’t solve the s equation for x.
WARNING #1: it’s important that n remains secret, otherwise anyone can get your private key by solving:
\begin{aligned}
s &= n + c \cdot x \mod{p} \\
x &= \frac{s - n}{c} \mod{p}
\end{aligned}
where the division over F_p is performed by multiplying by the inverse modulo-p of c.
WARNING #2: NEVER reuse the same random n to sign two different messages, otherwise full private key recovery becomes possible by solving:
\begin{aligned}
s_1 &= n + c_1 \cdot x \mod{p} \\
s_2 &= n + c_2 \cdot x \mod{p} \\
\end{aligned}
\frac{s_1 - s_2}{c_1 - c_2} = \frac{n + c_1 \cdot x - n - c_2 \cdot x}{c_1 - c_2} = x \cdot \frac{c_1 - c_2}{c_1 - c_2} = x
Note that doesn’t work if c_1 = c_2 because in that case s_1 = s_2 and you end up with
\frac{s_1 - s_2}{c_1 - c_2} = \frac00
which is an indeterminate form. So a single signature for a given c does not allow private key recovery.
So make sure n is fresh (and cryptographically secure) for every new signature.
Signing the same message with two different nonces is okay.
Schnorr Verification
- Compute the challenge hash:
c = H(N || P || m)
- Check the equation:
s \cdot G \stackrel{?}{=} N + c \cdot P
3. Conclusions
With all this we have two fundamental cryptographic primitives (a hash and a signature scheme) that are highly efficient for zk-SNARK circuits, especially Halo2 since we’re using the same field. This probably makes Poseidon and Poseidon-Schnorr the best choices for starting a new blockchain project today since Halo2-friendliness buys us the ability to construct recursive proofs (and therefore zk-rollups). Moreover, Halo2 is significantly easier to use than other schemes because it doesn’t require any trusted setup.