Zero Knowledge Proof — 1st place in the zkHack mini challenge

Trapdoor-Tech
6 min readMay 7, 2022

Trapdoor Tech won 1st place in zkHack mini challenge :) https://www.zkhack.dev/mini.html

This challenge consists of two puzzles. A challenge time for a week. Different from the challenges of the first zkHack puzzle challenge, the topics of this challenge are based on the STARK algorithm. STARK algorithm, AIR, FRI low-level testing and other technologies will be introduced in detail in subsequent articles. This article first summarizes the problem-solving ideas of the two puzzles of this challenge.

Puzzle 1 — There’s something in the AIR

Backgound

The puzzle needs you to find the way to cheat the voting system based on ZK-STARK and winterfell.

Analyse

For same topic, if user Alice can vote twice, which means there’s a leak which could be utilized, so that

  • Prover Can generate > 1 nullifiers to build witness
  • Verifier could not detect the fake nullifier according the pulic input and witness

According to the nullifier composition, a nullifier is generated in make_signal and returned as input of verifier

//! - A nullifier is computed by hashing a private key together with a hash of the topic - i.e.:
//! hash(priv_key, hash(topic)) using the same Rp64_256 hash function.

let nullifier = priv_key.get_nullifier(topic);

/// Creates a nullifier for the provided topic against this private key.
///
/// A nullifier is computed simply as hash(key, topic).
pub fn get_nullifier(&self, topic: Digest) -> Digest {
let key: Digest = self.0.into();
Rescue::merge(&[key, topic])
}

But the prover uses 12 columns, State[12..23] of Excution Trace to form a nullifier, not only including Private_key and Topic.

// prover set the initial state 
// -- nullifier section of the trace --
state[12] = Felt::new(8);
state[13] = Felt::ZERO;
state[14] = Felt::ZERO;
state[15] = Felt::ZERO;
state[16] = priv_key[0];
state[17] = priv_key[1];
state[18] = priv_key[2];
state[19] = priv_key[3];
state[20] = topic[0];
state[21] = topic[1];
state[22] = topic[2];
state[23] = topic[3];

A legal nullifier should include 3 parts below,

12     13       14     15]   [ 16     17   18     19 ]   [   20   21 22   23 ]

nullifier = [8 0, 0, 0, — — Private_key — — — — — , — — — -Topic — — — — — ] — For Step 0

Let’s check the verifier part, state[12–15] has no constraints set in function evaluate_transition, which should do as the fuction does for merkle part at step % 8 == 0.

result.agg_constraint(1, hash_init_flag, are_equal(E::from(8u8), next[0]));
result.agg_constraint(2, hash_init_flag, is_zero(next[1]));
result.agg_constraint(3, hash_init_flag, is_zero(next[2]));
result.agg_constraint(4, hash_init_flag, is_zero(next[3]));

Answer

The fake nullifier could be make by setting a different value for state[12–15], e.g. [16, 0, 0, 0].

pub fn get_fake_nullifier(&self, topic: Digest) -> Digest {
let key: Digest = self.0.into();

let mut state = [Felt::ZERO; 12];
state[4..12].copy_from_slice(Digest::digests_as_elements(&[key, topic]));
state[0] = Felt::new(0 as u64);

// apply the Rescue permutation and return the first four elements of the state
Rescue::apply_permutation(&mut state);
Digest::new(state
[4..8].try_into().unwrap())
}

And meanwhile the prover side needs to change its initial state[12–15] according the fake nullifier.

Prover.build_trace()
|state| {
......
// -- nullifier section of the trace --
state[12] = Felt::new(0);

Puzzle 2 — Can you turn up the heat?

This week has the most difficult puzzle that we’ve ever solved. One must have a clear understanding of the whole STARK proving system in order to work it out.

So what is the puzzle? Reading from the code, we know that Alice received a incorrect proof that can still be verified. Our mission is to find out how to generate it. A valid proof should be able to prove a Fibonacci computation trace, on the start and end positions constraints are satisfied.

The DEEP-FRI method

We can list the constraints here. Since we are manipulating a set of 2-column state registers, let’s denote the 1st column as polynomial f_0(x) and the 2nd f_1(x). We should have:

  1. f_0(0)= 0
  2. f_1(0) = 1
  3. f_0(15) = 832040
  4. f_0(x) + f_1(x) = f_0(gx)
  5. f_1(x) + f_0(gx) = f_1(gx)

According to STARK proving system, these constraints should be converted to a algebraic representation. They can be constructed by polynomial division. So we have:

  1. C_0(x) = \frac{f_0(x) — f_0(0)}{x-g⁰} = \frac{f_0(x)}{x-1}
  2. C_1(x) = \frac{f_1(x) — f_1(0)}{x-g⁰} = \frac{f_1(x) -1}{x-1}
  3. C_2(x) = \frac{f_0(x) — f_0(15)}{x-g^{15}} = \frac{f_0(x)-832040}{x-g^{15}}
  4. C_3(x) = \frac{f_0(gx) — f_0(x) — f_1(x)}{x^{15}-1 / x-g^{15}}
  5. C_4(x) = \frac{f_1(gx) — f_0(gx) — f_1(x)}{x^{15}-1 / x-g^{15}}

Then we use one composition polynomial to combine all the constraints. We will just paste the formula here:

(from https://medium.com/starkware/starkdex-deep-dive-the-stark-core-engine-497942d0f0ab)

If the degree of the composition polynomial is less or equal than D, then we know all the constraints are satisfied. However in STARK proving system, we are not actually checking this composition polynomial. We construct another DEEP polynomial to ensure:

  1. at an random point z, the composition polynomial and all the trace polynomials f_k(x) are evaluated correctly
  2. the DEEP polynomial is a low-degree polynomial, D_{deep} < D

The DEEP polynomial is also a combination of the above polynomials. Here we paste again from the StarkEx article, note that H_1(x) , H_2(x) are the even/odd parts of the composition polynomial:

The last question is how to do a low-degree test? Here comes the FRI protocol but we will not explain its details. All you need to know is that we let the prover commit to a polynomial evaluation merkle tree. After commitment, we challenge the prover D+1 times to get D+1 polynomial evaluations. Then we interpolate a D-1 degree polynomial f(x) with D evaluations f(x_d), check if the remaining evaluation is equal to f(x_{d+1}). If yes then we are almost sure that the original polynomial is a low-degree (less than D) polynomial. (FRI optimized the challenge process so that we don’t actually need to challenge D+1 times, extremely useful when D is huge)

The Hack

What if we provided an invalid program trace to the verifier? First of all, the constraint polynomial cannot be divided by its divisor, so the quotient polynomial will not be a low-degree polynomial. Therefore, the DEEP polynomial will not be a low-degree polynomial, and it cannot pass the FRI low-degree test, with a high probability, but how high is the high probability?

The number of queries in proof options is set to 1, so we know the verifier only query once for the DEEP polynomial. By once, we mean that verifier only checks at one random point in the LDE domain that the DEEP polynomial is indeed constructed by those trace and constraint polynomials. So if we generate a fake DEEP polynomial DEEP_{fake}, that at some certain points it's evaluation is equal to the DEEP_{real}, we have a chance that it can pass the verifier check. Moreover, this DEEP_{fake} should have low-degree, otherwise we cannot pass the successive FRI low-degree test.

Now the hack is clear, steps are described as below:

  1. we generate a fake trace, use the fake trace to compute all the trace polynomials and constraint polynomials. They are of high-degree, but that doesn’t matter.
  2. we generate the composition polynomial, be aware to make sure that the composition polynomial is a combination of those fake polynomials in step 1
  3. we carefully generate the DEEP_{real} polynomial, it can be evaluated by the above polynomials, but is of high degree. As in step 1, it doesn’t matter because we are not going to send this polynomial to the verifier.
  4. we generate a DEEP_{fake} polynomial, it evaluate to the same result as DEEP_{real} polynomial, but only at some certain points. We can do this by sampling point evaluations from DEEP_{real} polynomial, and use Lagrange Interpolation to construct DEEP_{fake}. The maximum point number sampled is equal to the low-degree that we are aiming for. (If we take more that number of points, we will have a interpolated polynomial whose degree exceeds the low-degree).
  5. we use DEEP_{fake} polynomial to run the FRI protocol. Since the polynomial is of low-degree, the FRI test shall always pass.
  6. The verifier also use queries to check whether the DEEP_{fake} is the DEEP polynomial that he expects. Since he only query once, we have a non-negligible succeed chance.

References

StarkDEX Deep Dive: the STARK Core Engine

ethStark documentation

--

--

Trapdoor-Tech

Trapdoor-Tech tries to connect the world with zero-knowledge proof technologies. zk-SNARK/STARK solution and proving acceleration are our first small steps :)