Detailed write-up for ZK Hack puzzle "Gamma Ray"

gamma_ray_write_up.md

Puzzle 12: Gamma Ray

Note: you can read a slightly edited version at https://yannickseurin.github.io/crypto-book/zk-hack-puzzles/puzzle-12/intro.html

• puzzle page
• GitHub repository
• puzzle description:

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 MNT6753
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...

ZCash, Mina, MNT curves, nullifiers... Let's jump into the code to see what this is about.

Code Analysis

The package directory is organized as follows:

zkhack-gamma-ray
├── Cargo.toml
├── leaked_secret.bin
├── leaves.bin
├── proof_keys.bin
└── src
    ├── main.rs
    └── poseidon_parameters.rs

Files leaked_secret.bin, leaves.bin, and proof_keys.bin contain raw data that will be used to initialize variables, as we will see.

The main.rs file brings a lot of items from various arkworks crates into scope, notably for MNT4-753 and MNT6-753 curves, Groth16 proofs, R1CS arithmetization, etc. We will come back to this shortly.

The first thing the main function does is to define a number of variables for the puzzle, in particular:

• a proving key and a verification key for the Groth16 proof system:

    let (pk, vk): (
        <Groth16<MNT4_753> as SNARK<MNT4BigFr>>::ProvingKey,
        <Groth16<MNT4_753> as SNARK<MNT4BigFr>>::VerifyingKey,
    ) = from_file("./proof_keys.bin");

• a "leaked secret" used by Alice to spend one of her coins:

    let leaked_secret: MNT4BigFr = from_file("./leaked_secret.bin");

• a Merkle tree, with leaf leaf at index i = 2 playing a special role:

    let leaves: Vec<Vec<MNT4BigFr>> = from_file("./leaves.bin");
    // ...
    let leaf_crh_params = poseidon_parameters::poseidon_parameters();
    let i = 2;
    let two_to_one_crh_params = leaf_crh_params.clone();
    // ...
    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];

The hash function used to build the Merkle tree is the SNARK-friendly Poseidon hash function with parameters specified in the poseidon_parameters.rs file. In particular, the underlying field is the scalar field MNT4BigFr of the MNT4-753 curve. One can also check that the tree has four leaves. At this point it's not clear what is the data contained in each leaf but we will clarify this in a moment.

Then, a Merkle proof (a proof that a specific leaf contains a specific element) is computed for the leaf at index i = 2:

    let tree_proof = tree.generate_proof(i).unwrap();

If you're unfamiliar with how ZCash works, the state of the chain is encoded in a Merkel tree where each leaf represents a coin. Attached to this leaf is a public key and a nullifier (originally called coin serial number in the ZeroCash paper) whose role is to prevent double spends: when a coin is spent, the corresponding nullifier is revealed and recorded and the protocol later ensures that any transaction using the same nullifier (and hence trying to spend the same coin) is invalid. Note in particular that leaves of the Merkle tree do not represent UTXOs but rather all coins that ever existed, spent or unspent. For more details about how nullifiers work, this blog post by Ariel Gabizon explains it very well.

Here, we can see that the nullifier is computed as the hash of the secret allowing to spend a coin:

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

In order to spend the coin represented by leaf at index i = 2, Alice needs to provide a Groth16 proof that her transaction is valid:

    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());

We will get into what SpendCircuit is shortly, but before that, let's take a look at the part where we need to work to solve the puzzle:

    /* Enter your solution here */

    let nullifier_hack = MNT4BigFr::from(0);
    let secret_hack = MNT4BigFr::from(0);

    /* End of solution */

    assert_ne!(nullifier, nullifier_hack);

    let c2 = 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_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());

As we can see, we must find another nullifier nullifier_hack (different from nullifier) and another secret secret_hack allowing to spend the same coin again (this is the same coin because the second Groth16 proof uses the same Merkle root root and the same Merkle proof tree_proof as the first Groth16 proof).

The Spending Circuit

At this point, we're ready to dive into the heart of the puzzle.

Let's try to understand what the circuit for which Groth16 proofs are generated does. It is specified by the generate_constraints method from the ConstraintSynthesizer trait implemented on the SpendCircuit struct:

impl ConstraintSynthesizer<ConstraintF> for SpendCircuit {
    fn generate_constraints(
        self,
        cs: ConstraintSystemRef<ConstraintF>,
    ) -> Result<(), SynthesisError> {

    // ...

    }
}

This method generates R1CS constraints (over the field ConstraintF = MNT4BigFr, the scalar field of the MNT4-753 curve) to which the Groth16 proof system is then applied. There is no need to understand precisely how R1CS arithmetization works exactly, just getting what the circuit does will be enough to solve the puzzle. For this, having a quick look at the arkworks R1CS tutorial can help. Let's go step by step into the definition of the circuit. A circuit can have public inputs (the "instance", declared with the new_input method of the AllocVar trait) and private inputs (the "witness", declared with the new_witness method of the AllocVar trait): the proof generation function takes public and private inputs and generates a proof that together they "satisfy" the circuit; the verification function takes only the public inputs and the proof and returns 0 or 1 (valid/invalid). It can also have constants declared with the new_constant of the same AllocVar trait.

Here, the public inputs consist of the Merkle root and the nullifier:

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

        // ...

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

The private inputs consist of the secret secret and the Merkle proof (the field proof of the SpendCircuit struct):

        let secret = FpVar::new_witness(ark_relations::ns!(cs, "secret"), || Ok(self.secret))?;

        // ...

        // Allocate Merkle Tree Path
        let cw: PathVar<MntMerkleTreeParams, ConstraintF, MntMerkleTreeParamsVar> =
            PathVar::new_witness(ark_relations::ns!(cs, "new_witness"), || Ok(&self.proof))?;

Then, the generate_constraints method calls a number of "gadgets" to implement the logic of the circuit. First, it checks that the secret is less than the size of the scalar field of the MNT6-763 curve:

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

It also checks that the hash of the secret is equal to the nullifier passed as input:

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

Then, it computes the public key associated with secret:

        let base = G1Var::new_constant(ark_relations::ns!(cs, "base"), G1Affine::generator())?;
        let pk = base.scalar_mul_le(secret_bits.iter())?.to_affine()?;

Note that the G1Affine type here represents the group of points of the MNT6-753 curve in short Weierstrass affine representation, meaning pk here is a point on this curve, encoded as a pair $(x,y)$ of elements of the base field $\mathbb{F}_{q_6}$ of the MNT6-753 curve, and computed as $P = s G$ where $G$ is the generator of this group corresponding to variable base and $s$ corresponds to secret.

Finally, the circuit verifies that the Merkle proof passed as private input to the circuit is valid for the root passed as public input and the leaf defined as pk.x, the $x$-coordinate of pk.

        // Allocate Leaf
        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))?;

This concludes our inspection of the spending circuit. In short, to spend a coin, Alice must provide the secret corresponding to the ($x$-coordinate of the) public key of the leaf representing the coin, a valid Merkle proof for this public key, and the corresponding nullifier, i.e., the hash of the secret.

Solving the Puzzle

Recall that our task is to find another secret/nullifier pair that will satisfy the spending circuit. We are not allowed to modify the Merkle root nor the Merkle proof, meaning this secret/nullifier pair must correspond to the exact same leaf of the Merkle tree.

But wait, the leaf does not really encode the public key pk, only its $x$-coordinate! This is the key insight to solve the puzzle. Indeed, for any point $P = (x,y)$ on the curve (different from the point at infinity), there is another point on the curve with the same $x$-coordinate, namely $-P = (x,-y)$. This point simply correspond to secret $-s \bmod r_6$ where $r_6$ is the size of the scalar field of the MNT6-753 curve since $(-s \bmod r_6) G = - (sG) = -P$.

Hence, all we have to do to solve the puzzle is to take the opposite of leaked_secret mod $r_6$ and compute the corresponding nullifier! There's a catch though: leaked_secret is defined as an element in the scalar field of MNT4-753, hence simply defining secret_hack = - leaked_secret won't work as this will compute $-s \bmod r_4$ where $r_4$ is the size of the scalar field of MNT4-753.

There are probably several options here, but a simple one is to cast leaked_secret as a big integer first. For this, we need to add the num-bigint crate to the project:

$ cargo add num-bigint

And here is the code allowing to solve the puzzle:

    /* Enter your solution here */

    // cast leaked_secret as big integer...
    let s: num_bigint::BigUint = leaked_secret.into();
    // ... and then as an element of MNT6BigFr
    let s_as_mnt6bigfr = MNT6BigFr::from_le_bytes_mod_order(&s.to_bytes_le());
    // take the opposite and cast it again as a big integer...
    let secret_hack_as_bigint: num_bigint::BigUint = (- s_as_mnt6bigfr).into();
    // and finally cast it back to an element of MNT4BigFr
    let secret_hack = MNT4BigFr::from_le_bytes_mod_order(&secret_hack_as_bigint.to_bytes_le());
    // compute the corresponding nullifier
    let nullifier_hack = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![secret_hack]).unwrap();
    // cast the nullifier as big int to print it
    let nullifier_hack_as_bigint: num_bigint::BigUint = nullifier_hack.into();
    println!("nullifier_hack: {:?}", nullifier_hack_as_bigint);
    println!("secret_hack: {:?}", secret_hack_as_bigint);

    /* End of solution */

Background about MNT Curve Cycles

Although the puzzle uses the MNT4/6-753 cycle, it did not actually use the fact that it forms a cycle. Cycles of curves were proposed in [BCTV14] to solve the "field mismatch" problem when composing SNARKs recursively [BCCT13]. It consists of two elliptic curves such that the base field of one is the scalar field of the other and vice-versa. For more background, see for example [AHG23].

A Note about Hint 1

The first hint revealed to help solve the puzzle points to Lemma 5.4.7 of the ZCash specifications. It reads:

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

Here, $\mathbb{J}^{(r)}$ is (a subgroup of) the Jubjub curve developed by the ZCash team. Its base field is actually the scalar field of BLS12-381, allowing to efficiently prove algebraic statements about this curve using BLS12-381-based SNARKs.

The reason why the "attack" used to solve the puzzle would not apply with this curve is that it is a twisted Edwards curve rather than a curve in short Weierstrass form. In particular, Theorem 5.4.8 states that the function mapping points in $\mathbb{J}^{(r)}$ to their $x$-coordinate is injective, meaning two distinct points have distinct $x$-coordinates. In this case, it is safe to encode a point by recording only its $x$-coordinate in a leaf.