Zero Knowledge Proof — 1st place in the zkHack mini 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
//! - 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])
}
// 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];
12     13       14     15]   [ 16     17   18     19 ]   [   20   21 22   23 ]
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())
}
Prover.build_trace()
|state| {
......
// -- nullifier section of the trace --
state[12] = Felt::new(0);

Puzzle 2 — Can you turn up the heat?

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)
  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}}
  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 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?

  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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Trapdoor-Tech

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 :)