# 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](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/) 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$\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 \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](https://blog.icme.io/can-we-avoid-cycles-of-curves/)

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](https://docs.rs/ark-mnt4-753/latest/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](https://github.com/arkworks-rs/r1cs-tutorial/tree/main/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](https://github.com/arkworks-rs/crypto-primitives/blob/main/src/crh/poseidon/constraints.rs#L28-L54), 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.