Crypto Book (Work in Progress)

Code Analysis

The package directory is organized as follows:

puzzle-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 [Gro16] proof system over the MNT4-753 curve:

    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" of type MNT4BigFr (the scalar field of the MNT4-753 curve) 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 [GKR+21] with parameters specified in the poseidon_parameters.rs file. In particular, the underlying field is also the scalar field MNT4BigFr of the MNT4-753 curve. One can also print the leaves of the Merkle tree:

use ark_ec::AffineRepr;
use ark_ff::PrimeField;
use ark_mnt4_753::{Fr as MNT4BigFr, MNT4_753};
use ark_mnt6_753::G1Affine;
use ark_mnt6_753::{constraints::G1Var, Fr as MNT6BigFr};

use ark_crypto_primitives::merkle_tree::{Config, MerkleTree, Path};
use ark_crypto_primitives::{crh::TwoToOneCRHScheme, snark::SNARK};
use ark_groth16::Groth16;
use ark_r1cs_std::fields::fp::FpVar;
use ark_r1cs_std::prelude::*;
use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, SynthesisError};
use ark_serialize::{CanonicalDeserialize, Read};

use prompt::{puzzle, welcome};

use std::fs::File;
use std::io::Cursor;

pub mod poseidon_parameters;

type ConstraintF = MNT4BigFr;

use ark_crypto_primitives::{
    crh::{poseidon, *},
    merkle_tree::constraints::*,
    merkle_tree::*,
};
use ark_std::rand::SeedableRng;

type LeafH = poseidon::CRH<ConstraintF>;
type LeafHG = poseidon::constraints::CRHGadget<ConstraintF>;

type CompressH = poseidon::TwoToOneCRH<ConstraintF>;
type CompressHG = poseidon::constraints::TwoToOneCRHGadget<ConstraintF>;

type LeafVar = [FpVar<ConstraintF>];
struct MntMerkleTreeParamsVar;
impl ConfigGadget<MntMerkleTreeParams, ConstraintF> for MntMerkleTreeParamsVar {
    type Leaf = LeafVar;
    type LeafDigest = <LeafHG as CRHSchemeGadget<LeafH, ConstraintF>>::OutputVar;
    type LeafInnerConverter = IdentityDigestConverter<FpVar<ConstraintF>>;
    type InnerDigest = <CompressHG as TwoToOneCRHSchemeGadget<CompressH, ConstraintF>>::OutputVar;
    type LeafHash = LeafHG;
    type TwoToOneHash = CompressHG;
}

type MntMerkleTree = MerkleTree<MntMerkleTreeParams>;

struct MntMerkleTreeParams;

impl Config for MntMerkleTreeParams {
    type Leaf = [ConstraintF];

    type LeafDigest = <LeafH as CRHScheme>::Output;
    type LeafInnerDigestConverter = IdentityDigestConverter<ConstraintF>;
    type InnerDigest = <CompressH as TwoToOneCRHScheme>::Output;

    type LeafHash = LeafH;
    type TwoToOneHash = CompressH;
}

#[derive(Clone)]
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,
}

impl ConstraintSynthesizer<ConstraintF> for SpendCircuit {
    fn generate_constraints(
        self,
        cs: ConstraintSystemRef<ConstraintF>,
    ) -> Result<(), SynthesisError> {
        // Allocate Merkle Tree Root
        let root = <LeafHG as CRHSchemeGadget<LeafH, _>>::OutputVar::new_input(
            ark_relations::ns!(cs, "new_digest"),
            || Ok(self.root),
        )?;

        // Allocate Parameters for CRH
        let leaf_crh_params_var =
            <LeafHG as CRHSchemeGadget<LeafH, _>>::ParametersVar::new_constant(
                ark_relations::ns!(cs, "leaf_crh_parameter"),
                &self.leaf_params,
            )?;
        let two_to_one_crh_params_var =
            <CompressHG as TwoToOneCRHSchemeGadget<CompressH, _>>::ParametersVar::new_constant(
                ark_relations::ns!(cs, "two_to_one_crh_parameter"),
                &self.two_to_one_params,
            )?;

        let secret = FpVar::new_witness(ark_relations::ns!(cs, "secret"), || Ok(self.secret))?;
        let secret_bits = secret.to_bits_le()?;
        Boolean::enforce_smaller_or_equal_than_le(&secret_bits, MNT6BigFr::MODULUS)?;

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

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

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

        // Allocate Leaf
        let leaf_g: Vec<_> = vec![pk.x];

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

        cw.verify_membership(
            &leaf_crh_params_var,
            &two_to_one_crh_params_var,
            &root,
            &leaf_g,
        )?
        .enforce_equal(&Boolean::constant(true))?;

        Ok(())
    }
}

fn from_file<T: CanonicalDeserialize>(path: &str) -> T {
    let mut file = File::open(path).unwrap();
    let mut buffer = Vec::new();
    file.read_to_end(&mut buffer).unwrap();
    T::deserialize_uncompressed_unchecked(Cursor::new(&buffer)).unwrap()
}

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

    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): (
        <Groth16<MNT4_753> as SNARK<MNT4BigFr>>::ProvingKey,
        <Groth16<MNT4_753> as SNARK<MNT4BigFr>>::VerifyingKey,
    ) = from_file("./proof_keys.bin");

    let leaf_crh_params = poseidon_parameters::poseidon_parameters();
    let i = 2;
    let two_to_one_crh_params = leaf_crh_params.clone();

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

    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();
    assert!(tree_proof
        .verify(
            &leaf_crh_params,
            &two_to_one_crh_params,
            &root,
            leaf.as_slice()
        )
        .unwrap());

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

    // --snip--

    for (i, leaf) in leaves.iter().enumerate() {
        for (j, p) in leaf.iter().enumerate() {
            println!("leaves[{}][{}]: {}", i, j, p);
        }
    }
    println!("");

    assert!(Groth16::<MNT4_753>::verify(&vk, &vec![root, nullifier], &proof).unwrap());

    // --snip--

    /* 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();
    println!("nullifier_hack: {}", nullifier_hack);
    println!("secret_hack: {}", secret_hack_as_bigint);

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

    println!("Puzzle solved!");
}

const PUZZLE_DESCRIPTION: &str = r"
Bob was deeply inspired by the Zcash design [1] for private transactions [2] 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 MNT7653 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
";

There are four leaves, each consisting of a single MNT4BigFr element. At this point it's not clear what these leaves represent 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 Merkle 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 [BCG+14]) 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).

Next, let us unravel what the spending circuit does.