ZK Hack 4 Puzzle 1: Gamma Ray

gamma-ray.md

Bob was deeply inspired by the Zcash design [1] for private transactions and had some pretty cool ideas on how to adapt it for his requirements. He was also inspired by the Mina design for the lightest blockchain and wanted to combine the two. In order to achieve that, Bob used the MNT6-753 cycle of curves to enable efficient infinite recursion, and used elliptic curve public keys to authorize spends. He released a first version of the system to the world and Alice soon announced she was able to double spend by creating two different nullifiers for the same key...

[1] https://zips.z.cash/protocol/protocol.pdf

Overview

This challenge makes use of Arkworks crates ark_mnt4_753 and ark_mnt6_753, respective implementations of the MNT4-753 (Miyaji–Nakabayashi–Takano, embedding degree 4, over a 753-bit field) and MNT6-753 (similar but embedding degree 6) elliptic curves. We will use $$\mathbb{F}_q^{(4)}:=\mathbb{F}_{q^{(4)}},\;\;\;\;\mathbb{F}_r^{(4)}:=\mathbb{F}_{r^{(4)}}$$ to (respectively) denote the base and scalar fields of the former curve, where one should consult e.g. the module documentation for details of the field sizes $q^{(4)}$ and $r^{(4)}$. Similarly, $\mathbb{F}_q^{(6)}$ and $\mathbb{F}_r^{(6)}$ denote the base and scalar fields of the latter curve. In fact, the pair of curves form a (pairing-friendly) cycle with $$\mathbb{F}_q^{(4)}=\mathbb{F}_r^{(6)}$$ $$\mathbb{F}_q^{(6)}=\mathbb{F}_r^{(4)}$$ hence for notation we will tend to just use $\mathbb{F}_r^{(4)}$ and $\mathbb{F}_r^{(6)}$ here.

We'll use $\mathbb{G}_1^{(6)}$ to denote the group of points $(x,y)$ satisfying the MNT6-753 curve equation, that is the Weierstrass equation $$y^2=x^3+ax+b$$ with $a=11$ and $b = \mathsf{0x7DA28\cdots C8468A}$ (see module doc for details!). We use $G$ to denote a fixed generator of $\mathbb{G}_1^{(6)}$, and for any $P\in \mathbb{G}_1^{(6)}$, scalar multiplication is denoted $[k]P$ for a scalar $k\in \mathbb{F}_r^{(6)}$.

Spend Circuit Constraints

main.rs contains various type aliases and definitions, the most important of which is the following

struct SpendCircuit {
    pub leaf_params: <LeafH as CRHScheme>::Parameters,
    pub two_to_one_params: <LeafH as CRHScheme>::Parameters,
    pub root: <CompressH as TwoToOneCRHScheme>::Output,
    pub proof: Path<MntMerkleTreeParams>,
    pub secret: ConstraintF,
    pub nullifier: ConstraintF,
}

Assume there is a list of "leaves", and hashing successive pairs of leaves (via parameters specified by leaf_params and two_to_one_params) yields a Merkle tree with root root. The idea of a SpendCircuit is that it captures the statement that secret is among the leaves of the given Merkle tree as established by a Merkle authentication path proof, and the hash of secret is nullifier. Intuitively, the leaf secret is nullified or "spent". One can imagine some separate collection of such nullifiers, recording (but without revealing) those leaves that have been spent. There is a somewhat similar notion of spend transaction in Zcash.

The precise statement captured by a SpendCircuit is specified in detail in its implementation of the ConstraintSynthesizer trait, which is used to build a R1CS (rank-1 constraint system). For example, the following allocates root as a public input of the R1CS:

let root = <LeafHG as CRHSchemeGadget<LeafH, _>>::OutputVar::new_input(
    ark_relations::ns!(cs, "new_digest"),
    || Ok(self.root),
)?;

Similarly, nullifier is also allocated as a public input. leaf_params and two_to_one_params on the other hand are treated as constants (which don't allocate any variables or constraints). Finally, the following

let secret = FpVar::new_witness(ark_relations::ns!(cs, "secret"), || Ok(self.secret))?;
let cw: PathVar<MntMerkleTreeParams, ConstraintF, MntMerkleTreeParamsVar> =
    PathVar::new_witness(ark_relations::ns!(cs, "new_witness"), || Ok(&self.proof))?;

allocates secret and proof as private witnesses.

Let's look at the constraints on these variables. First, the following

let secret_bits = secret.to_bits_le()?;
Boolean::enforce_smaller_or_equal_than_le(&secret_bits, MNT6BigFr::MODULUS)?;

is a constraint asserting that secret is no larger than $r^{(6)}$ (with both interpreted as little-endian integers). Recall from above that secret's type is the same as that which the R1CS constraints are defined over

type ConstraintF = MNT4BigFr;

that is, it is a field element $s\in\mathbb{F}_r^{(4)}$. So the above constraint essentially enforces that we also have $s\in\mathbb{F}_r^{(6)}$. Next,

let nullifier_in_circuit =
    <LeafHG as CRHSchemeGadget<LeafH, _>>::evaluate(&leaf_crh_params_var, &[secret])?;
nullifier_in_circuit.enforce_equal(&nullifier)?;

computes the hash (according to leaf_params) of secret inside the circuit, and asserts that it matches the public input nullifier. Finally for the following,

let base = G1Var::new_constant(ark_relations::ns!(cs, "base"), G1Affine::generator())?;
let pk = base.scalar_mul_le(secret_bits.iter())?.to_affine()?;
let leaf_g: Vec<_> = vec![pk.x];
cw.verify_membership(
    &leaf_crh_params_var,
    &two_to_one_crh_params_var,
    &root,
    &leaf_g,
)?
.enforce_equal(&Boolean::constant(true))?;

computes the scalar multiplication $[s]G$ inside the circuit, with leaf_g its (affine) $x$-coordinate. The final constraint essentially says that cw proves that leaf_g is indeed a leaf in the Merkle tree. That is, hashing leaf_g successively along the authentication path cw indeed yields root.

Main code

let rng = &mut ark_std::rand::rngs::StdRng::seed_from_u64(0u64);
let leaves: Vec<Vec<MNT4BigFr>> = from_file("./leaves.bin");
let leaked_secret: MNT4BigFr = from_file("./leaked_secret.bin");
let (pk, vk) = from_file("./proof_keys.bin");
let leaf_crh_params = poseidon_parameters::poseidon_parameters();
let two_to_one_crh_params = leaf_crh_params.clone();
let i = 2;

We are given the leaves, which by inspection is a vector containing 4 singleton vectors, each holding a field element in $\mathbb{F}_r^{(4)}$. There is also an additional field element leaked_secret which is used to derive the nullifier

let nullifier = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![leaked_secret]).unwrap();

Now we build a Merkle tree from leaves, and an authentication path tree_proof from the $i$-th leaf to its root:

let tree = MntMerkleTree::new(
    &leaf_crh_params,
    &two_to_one_crh_params,
    leaves.iter().map(|x| x.as_slice()),
)
.unwrap();
let root = tree.root();
let leaf = &leaves[i];
let tree_proof = tree.generate_proof(i).unwrap();

We build our first SpendCircuit with the above data as follows, along with a convincing Groth16 proof of the circuit:

let c = SpendCircuit {
    leaf_params: leaf_crh_params.clone(),
    two_to_one_params: two_to_one_crh_params.clone(),
    root: root.clone(),
    proof: tree_proof.clone(),
    nullifier: nullifier.clone(),
    secret: leaked_secret.clone(),
};
let proof = Groth16::<MNT4_753>::prove(&pk, c.clone(), rng).unwrap();
assert!(Groth16::<MNT4_753>::verify(&vk, &vec![root, nullifier], &proof).unwrap());

Note that by definition of the circuit:

1. nullifier is the hash of leaked_secret (which is no surprise since that is how nullifier was computed above).
2. leaked_secret is an element $s\in\mathbb{F}_r^{(6)}$.
3. Hashing $x$ along the path tree_proof yields root, where $(x,y)=[s]G$.

But recall tree_proof is a path from the $i$-th leaf to root, so 3. implies that $x$ is that leaf.

The challenge now is to come up with an alternative secret and nullifier - secret_hack and nullifier_hack - such that a second SpendCircuit with these values also induces a convincing proof, thereby implying a double spend!

let c2 = SpendCircuit {
    // other fields same as c
    nullifier: nullifier_hack.clone(),
    secret: secret_hack.clone(),
};
let proof = Groth16::<MNT4_753>::prove(&pk, c2.clone(), rng).unwrap();
assert!(Groth16::<MNT4_753>::verify(&vk, &vec![root, nullifier_hack], &proof).unwrap());

Solution

Note that for a public key $(x,y)$, Bob has chosen to use just the $x$ components as the leaves. This may be due to a (careless!) reading of the Zcash protocol spec. There, $\mathbb{J}^{(r)}$ is a certain subgroup of points in the Jubjub twisted Edwards curve. Then

Lemma 5.4.7. Let $(u,v)\in\mathbb{J}^{(r)}$. Then $(u,-v)\notin\mathbb{J}^{(r)}$.

From this, it is shown (in Theorem 5.4.8) that "taking the $x$-coordinate" is an injective function on $\mathbb{J}^{(r)}$. In other words, $u$ determines $v$, hence it is enough to store $u$ alone. In our settting however, this turns out to not be the case! Indeed, as $\mathbb{G}_1^{(6)}$ consists of the points satisfying a curve equation in Weierstrass form, the inverse of a point $P=(x,y)\in\mathbb{G}_1^{(6)}$ is given by $-P=(x,-y)\in\mathbb{G}_1^{(6)}$. Thus if $x$ is a leaf derived from a public key $P$, it could also just as well be derived from $-P$.

This forms the basis of an attack. First let's do a scalar multiplication on leaked_secret, following roughly what the circuit is doing, to obtain a public key. Recall from the previous section that its $x$-coordinate should be the $i$-th leaf:

let g = G1Affine::generator();
let pk1 = g.mul_bigint(&leaked_secret.into_bigint()).into_affine();
let x1 = pk1.x().unwrap();
let y1 = *pk1.y().unwrap();
assert_eq!(&vec![*x1], leaf);

Inverting the public key $P=(x,y)$ should indeed give us the alternative public key $-P=(x,-y)$

let pk2 = -pk1;
let x2 = pk2.x().unwrap();
let y2 = *pk2.y().unwrap();
assert_eq!(x2, x1);
assert_eq!(y2, -y1);

Now we would like to recover the secret giving rise to $-P$. But since $P=[s]G$, $$-P=-[s]G=[-s]G$$ So we just need $-s$, namely the inverse of leaked_secret. However we need to be careful - the following does not quite work:

let wrong_neg_secret = -leaked_secret;
let wrong_pk = g.mul_bigint(&wrong_neg_secret.into_bigint()).into_affine();
let wrong_x = wrong_pk.x().unwrap();
assert_ne!(wrong_x, x1);

that is, it does not give a valid public key for $x$. The reason is leaked_secret is of type MNT4BigFr, so we are inverting in $\mathbb{F}_r^{(4)}$ which is the wrong scalar field. Instead:

let neg_leaked_secret = -MNT6BigFr::from(leaked_secret.into_bigint());
let other_pk = g.mul_bigint(&neg_leaked_secret.into_bigint())
assert_eq!(other_pk, pk2);

confirms that inverting in the correct field $\mathbb{F}_r^{(6)}$ indeed recovers $-P$. Then it just remains to derive the associated nullifer. More concisely, the solution consists of just the following

/* Enter your solution here */
let neg_leaked_secret = -MNT6BigFr::from(leaked_secret.into_bigint());
let secret_hack = MNT4BigFr::from(neg_leaked_secret.into_bigint());
let nullifier_hack = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![secret_hack]).unwrap();
/* End of solution */