ZK Hack IV - Gamma Ray

This is the solution of the challenge “Gamma Ray” from ZK Hack IV . It was possible to forge a nullifier of a circuit using the negation of a valid nullifier on a Miyaji-Nakabayashi-Takano curve.

Details

Author: Geometry research

Points: 893

Description

Nullify me once, shame on you. Nullify me twice, shame on me.

Puzzle link

Solution

According to the code, the secret $s$ is an element of the prime field MNT4BigFr (753 bits):

1
2
3
4
5
6
7

#[derive(MontConfig)]
#[modulus = "41898490967918953402344214791240637128170709919953949071783502921025352812571106773058893763790338921418070971888458477323173057491593855069696241854796396165721416325350064441470418137846398469611935719059908164220784476160001"]
#[generator = "17"]
#[small_subgroup_base = "5"]
#[small_subgroup_power = "2"]
pub struct FrConfig;
pub type Fr = Fp768<MontBackend<FrConfig, 12>>;

The nullifier $n = H(s)$ is the hash of the secret. The hash function is the poseidon hash instanced over MNT4BigFr. Thus $n$ is also an element of MNT4BigFr. The public key is $Q = s\cdot G$ on the curve MNT6-753. The curve is a Miyaji-Nakabayashi-Takano curve defined over MNT4BigFr. The scalar field of this curve is the field MNT6BigFr:

1
2
3
4
5
6
7

#[derive(MontConfig)]
#[modulus = "41898490967918953402344214791240637128170709919953949071783502921025352812571106773058893763790338921418070971888253786114353726529584385201591605722013126468931404347949840543007986327743462853720628051692141265303114721689601"]
#[generator = "17"]
#[small_subgroup_base = "5"]
#[small_subgroup_power = "2"]
pub struct FqConfig;
pub type Fq = Fp768<MontBackend<FqConfig, 12>>;

To have a proper definition of the public key, the secret is enforced to be less or equal than the MNT6BigFr modulus in the circuit

The SpendCircuit is a Merkle tree with 4 leaves using Poseidon as a hash function. The same hash function is used for leaf and intermediate nodes. The circuit verify the membership of the $x$ coordinate of the public key in this Merkle tree.

The Miyaji-Nakabayashi-Takano curve has a Weistrass form and one notable fact of this kind of curve is that for a point $P = (x,y)$ on the curve we have the point $-P = (x,-y)$ which is also on the curve. This property is the opposite as for twisted Edward curve like Jubjub where $-P = (-x,y)$. Since the curve has a prime order then we are working with the full group of points of the curve. So if we are able to find $\tilde{s} = -s \mod q$ the point $\tilde{Q} = -Q = -s\cdot G$ have the same $x$-coordinate compared to $Q$. The proof of membership would work as well on this point with the nullifier $n = H(-s)$.

We need to be careful in which field we work since the rogue secret $\tilde{s} = -s \mod q = q-s$ should lies in MNT4BigFr to be accepted by the Poseidon hash function. Thus the solution is:

1
2
3
4
5
6

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

Here is my repository solution. you can verify to run properly by running:

1

$ cargo run -r