ZKHack IV Puzzles #1 Gamma Ray

Given a Merkle tree and a secret corresponding to a leaf. First it will prove that the leaf is on the Merkle tree, and then ask for a new secret to ensure that its corresponding leaf is also on the Merkle tree.

Origin Problem: https://github.com/ZK-Hack/puzzle-gamma-ray

background

It is assumed that you already know about elliptic curve, such as its point addition, scalar multiplication, ECDLP, Generator, order. See these four articles for detail.
There is a fact that, in affine space the graph of the elliptic curve

$y^2=x^3+ax+b$ is symmetrical about the

$x$-axis. For a certain point

$P_0(x_0,y_0)$ above, there must be a point

$P_1(x_0,-y_0)$ on the curve. After

$\mathrm{mod}q$, the

$y$ value of points below the

$x$-axis will be added to

$q$, and the points of their elliptic curves are symmetrical about

$y=\frac{q}{2}$. In the definition of elliptic curve group, they are inverse elements of each other.

Here we introduce CycleCurve. As an example, this is the parameter of Secp256k1:

$y^2\equiv x^3+7\mathrm{mod}q$, where q=0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F, the generator is point G, the amount of elements is order, and order=0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. The Fields generated by mod q is the base field, related to

$(x,y)$, and by mod order is the scalar field, which is related to the coefficient of the point, such as

$aG$.

$a$ is in the scalar field.

In SNARK, the witness prover input is the element in the scalar field, and the proof after instantiation is the point

$(x,y)$ related. In the recursive snark, we take the point

$(x,y)$ as input and repeat the process, but it can be noted that

$q$ is not equal order. At this time, we need to prepare two curves, and their q and order cross-equality. If you need a more detailed description, you can refer to here

When looking at the source code in main.rs, you can find that two curves are used: ark-mnt4-753 and ark-mnt6-753. According to the description of ark-mnt4-753:

The main feature of this curve is that its scalar field and base field respectively equal the base field and scalar field of MNT6_753.

Then I noticed that this is a MerkleTree, which is widely used in existence proof scenarios, such as Tornado Cash. arkworks provides a merkle-tree-example. If you have seen this example before, it will reduce your unfamiliarity.

In SpendCircuit, the only things we customize are secret and nullifier. So we need to pay attention to how they are handled when they are inside the MerkleTree: We look at the implementation of generate_constraints() in the ConstraintSynthesizer trait.

1. Evaluate the secret with Tree's paramaters. The result need be equal to the input nullifier. We do not need to know what operations are performed in the evaluate. If we can get the correct secret, we can get the correct value by printing nullifier_in_circuit.value(). If you want to figure out what evaluate does, you can check code, It just hashes the secret.

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

2. Get the generator point of G1Affine and multiply the secret to get a new point pk. Note that G1Affine is defined as the mnt6 curve in ark-mnt6-753.

   ​let base = G1Var::new_constant(ark_relations::ns!(cs, "base"), G1Affine::generator())?;
   ​let pk = base.scalar_mul_le(secret_bits.iter())?.to_affine()?;
   
   ​# https://github.com/arkworks-rs/curves/blob/master/mnt6_753/src/curves/g1.rs#L9
   ​pub type G1Affine = mnt6::G1Affine<crate::Config>;
   

3. Check that pk.x is indeed on the leaf of the Tree.

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

4. It is required to use different nullifier, and the hidden condition is to use different secret.

   ​​​    assert_ne!(nullifier, nullifier_hack);
   

Therefore, we can find the inverse element of the point corresponding to secret under mnt6(because the Generator is mnt6), then convert it to MNT4BigFr, and then print out nullifier, then used it as nullifier_hack.

    let zero_mnt6 = MNT6BigFr::from(0);
    let leaked_secret_mnt6 = MNT6BigFr::from(leaked_secret.into_bigint());
    let secret_hack_mnt6 = zero_mnt6 - leaked_secret_mnt6.clone();

    let secret_hack = MNT4BigFr::from(secret_hack_mnt6.into_bigint());
    let nullifier_hack = MNT4BigFr::from(BigInt([
        3973337740569432013,
        13414245347258487558,
        2397428639358863969,
        9003710485710992633,
        7549792233030202438,
        12021247171312009477,
        10014790687727384398,
        10719001394312000749,
        12147986067925283906,
        7048510174634313048,
        13041399962513988848,
        81761383246681,
    ]));

The whole solutions see here: https://github.com/flyq/puzzle-gamma-ray.