Skip to main content
Table of contents
Malte Leip

Breaking Down the Puzzles in ZK Hack IV

A look into the three puzzles solved by the Zellic cryptography team for ZK Hack IV
Article heading

The Zellic cryptography team (Malte Leip, Mohit Sharma, and Avi Weinstock) and Sampriti Panda participated in the most recent ZK Hack competition, ZK Hack IV, consisting of three puzzles overall, with points determined by how fast one managed to solve it. We were happy to win the first puzzle and place second in the third one, securing a second place overall.

ZK Hack IV Leaderboard

This ZK Hack’s puzzles consisted of small cryptographic applications written in Rust using the arkworks libraries. They combined the kind of cryptographic primitives that are typically used in projects surrounding ZK, but in each puzzle some kind of vulnerability was introduced as well. The task was then to understand the provided code, find the vulnerability theoretically, and then implement a solution leveraging the found vulnerability.

Puzzle 1: Gamma Ray

In the first puzzle, we were presented with parts of a small Zcash clone, the task being to double spend a note. Double spending is prevented in Zcash with the use of nullifiers; to spend a note, you must reveal a nullifier associated with that note, and this nullifier is then marked as used. Already used nullifiers are not allowed to be used anymore, so this prevents double spending as long as there is only one valid nullifier that can be computed for each note.

In the case of this puzzle, however, the relationship was roughly nullifier=hash(secret)nullifier = hash(secret) and note=(secretbasepoint).xnote = (secret\cdot basepoint).x, where basepointbasepoint is a point on an elliptic curve and .x.x refers to the x-coordinate in affine coordinates. But if (x,y)(x,y) is a point in affine coordinates on this elliptic curve, then it holds that (x,y)=(x,y)-(x,y) = (x, -y) and thus has the same x-coordinate. Thus the note does not change if we replace secretsecret by secret-secret (taken modulo the order of basepointbasepoint), but the hash changes, so we obtain a second nullifier associated with the note. A more detailed write-up can be found on the ZK Hack page for this puzzle.

This was our solution code:

let secret_hack = MNT4BigFr::from(MNT6BigFr::MODULUS) - MNT4BigFr::from(leaked_secret);
let nullifier_hack = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![secret_hack]).unwrap();

Puzzle 2: Supervillain

The second puzzle concerned a combination of aggregated BLS signatures with a simple proof-of-knowledge scheme. Both of those used a pairing e:G1×G2G3e: G_1 \times G_2 \to G_3. We recently published an introductory article on pairings, so head over there if you would like an introduction.

In a sequence of signatures for a fixed hashed message mG2m\in G_2, signature number ii is signed with a public key pkipk_i of the form pki=skigpk_i = sk_i \cdot g, with gg a fixed element of G1G_1. The signature is a normal BLS signature, so sigi=skimsig_i = sk_i \cdot m. Those can be aggregated with sig=isigisig = \sum_i sig_i, pk=ipkipk = \sum_i pk_i and then verified by checking e(pk,m)=e(g,sig)e(pk, m) = e(g, sig). That this equality follows from e(pki,m)=e(g,sigi)e(pk_i, m) = e(g, sig_i), and that in turn these equalities hold, is a consequence of the bilinearity of ee.

To prove that the signer actually knew skisk_i, they can provide another elliptic curve element pfipf_i, and verification checks that e(pki,ih)=e(g,pfi)e(pk_i, i \cdot h) = e(g, pf_i), where hG2h\in G_2 is a fixed element.

In the puzzle, we were then given a sequence of public keys and proofs pk1,,pknpk_1,\dots, pk_n and pf1,,pknpf_1,\dots,pk_n for which verification of the proof of knowledge of skisk_i succeeds (we do not get skisk_i though). Our task was to come up with skn+1sk_{n+1} and pfn+1pf_{n+1}, so that the proof-of-knowledge verification succeeds for this pair, and additionally a signature sigsig that would verify as a BLS signature for a specific hashed message mm using the aggregate key i=1n+1pki\sum_{i=1}^{n+1} pk_i. This means our constraints were

e(pkn+1,(n+1)h)=e(g,pfn+1)e(pk_{n+1}, (n+1)\cdot h) = e(g, pf_{n+1})


e(i=1n+1pki,m)=e(g,sig)e\left(\sum_{i=1}^{n+1} pk_i, m\right) = e(g, sig)

and we have available e(pki,ih)=e(g,pfi)e(pk_{i}, i\cdot h) = e(g, pf_{i}) for ini\leq n. The available equalities are usable for the first constraint but not the second, so to make the second one pass, we choose pkn+1=i=1npkipk_{n+1} = - \sum_{i=1}^{n} pk_i and sig=0sig=0, making both sides 0 by bilinearity1. The left hand side of the first constraint can then be rewritten as follows.

e(pkn+1,(n+1)h)=e(i=1npki,(n+1)h)=i=1ne(pki,(n+1)h)=i=1nn+1ie(pki,ih)=i=1nn+1ie(g,pfi)=e(g,i=1nn+1ipfi)\begin{align*} e(pk_{n+1}, (n+1)\cdot h) &= e\left( - \sum_{i=1}^{n} pk_i, (n+1)\cdot h\right) \\ &= - \sum_{i=1}^{n} e(pk_i, (n+1) \cdot h) \\ &= - \sum_{i=1}^{n} \frac{n+1}{i} e(pk_i, i \cdot h) \\ &= - \sum_{i=1}^{n} \frac{n+1}{i} e(g, pf_i ) \\ &= e\left(g, - \sum_{i=1}^{n} \frac{n+1}{i} pf_i\right) \end{align*}

The first constraint thus means that we must choose pfn+1pf_{n+1} in such a way that the following equality holds.

e(g,i=1nn+1ipfi)=e(g,pfn+1)e\left(g, - \sum_{i=1}^{n} \frac{n+1}{i} pf_i\right) = e(g, pf_{n+1})

The puzzle is thus solved by using pfn+1=i=1nn+1ipfipf_{n+1} = - \sum_{i=1}^{n} \frac{n+1}{i} pf_i.

A more detailed write-up for this puzzle can again be found on its ZK Hack page.

This was our solution code:

let aggregate_rest = public_keys
.fold(G1Projective::zero(), |acc, (pk, _)| acc + pk)
let new_key = aggregate_rest.neg();

let proofs_raw = public_keys
.map(|(i, (_pk, proof))| *proof * Fr::from(i as u64 + 1).inverse().unwrap());
let proofs_add = proofs_raw.fold(G2Projective::zero(), |acc, el| acc + el).neg();
let new_proof = (proofs_add * Fr::from(new_key_index as u64 + 1)).into();

let aggregate_signature = G2Affine::zero();

Puzzle 3: Chaos Theory

In this puzzle, we again encountered BLS signatures, this time combined with ElGamal encryption. We were given an encrypted, authenticated message and had to find out which message it was, out of a small number of possibilities.

As in Puzzle 2, the sender has a secret key sksendsk_{send} with public key pksend=sksendgpk_{send} = sk_{send} \cdot g, and so does the receiver. The ElGamal ciphertext of the message mm is then given by c=(pksend,d)c = (pk_{send}, d) with d=sksendpkrecv+md = sk_{send}\cdot pk_{recv} + m (the receiver can decrypt by subtracting sksendpkrecv=skrecvpksendsk_{send}\cdot pk_{recv} = sk_{recv}\cdot pk_{send} from dd). The signature we are also provided is a BLS signature of a hash of the ElGamal ciphertext — so ss satisfying e(g,s)=e(pksend,hash(c))e(g, s) = e(pk_{send}, hash(c)).

We have a small number of possible messages mm' to check. To eliminate dependence on the message if we guessed correctly, we begin by considering dmd - m', which will be sksendpkrecv=skrecvpksendsk_{send}\cdot pk_{recv} = sk_{recv}\cdot pk_{send} in that case (and something different if mmm' \neq m). Thus, if m=mm' = m, we will have

=e(dm,hash(c))=e(skrecvpksend,hash(c))=skrecve(pksend,hash(c))=skrecve(g,s)=e(skrecvg,s)=e(pkrecv,s).\begin{align*} &\phantom{=} e(d - m', hash(c)) \\ &= e( sk_{recv}\cdot pk_{send}, hash(c)) \\ &= sk_{recv}\cdot e(pk_{send}, hash(c)) \\ &= sk_{recv}\cdot e(g, s) \\ &= e(sk_{recv} \cdot g, s) \\ &= e(pk_{recv}, s). \end{align*}

While the middle steps above involve terms we do not know, we can check whether e(dm,hash(c))=e(pkrecv,s)e(d - m', hash(c)) = e(pk_{recv}, s). If this equality holds, then m=mm'=m.

As with the other puzzles, a more detailed write-up can be found on its ZK Hack page.

This was our solution code:

for (i, msg) in messages.iter().enumerate() {
let shared = blob.c.1 - msg.0;

let lhs = { Bls12_381::pairing(shared, blob.c.hash_to_curve()) };
let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };

if lhs == rhs {
println!("Msg {i} is correct");


We would like to thank ZK Hack for organizing this competition and Geometry Research for creating these three interesting puzzles.

About Us

Zellic’s dedicated zero-knowledge team combines a distinguished skill set in advanced cryptography, vulnerability research, and competitive hacking. We review circuits in Circom, Halo2, and other frameworks for zkEVMs, zkVMs, privacy and identity protocols, and interoperability infrastructure.

Notable clients include rollups (Scroll), coprocessors (Axiom), privacy primitives (Nocturne), and zk-bridges (Polyhedra).

Contact us for a ZK audit.


  1. I am writing G3G_3 additively here to simplify exposition.