Skip to content

Instantly share code, notes, and snippets.

@niooss-ledger
Created November 30, 2024 09:55
Show Gist options
  • Save niooss-ledger/0290f9daa71ac24300cec41ab871f6d1 to your computer and use it in GitHub Desktop.
Save niooss-ledger/0290f9daa71ac24300cec41ab871f6d1 to your computer and use it in GitHub Desktop.
Write-up for ZK Hack V puzzle V1: Zeitgeist

Write-up for ZK Hack V puzzle V1: Zeitgeist

Nicolas IOOSS, 2024-11-26

0. Warm-up

The day before the release of the first puzzle for ZK Hack V, a tweet was published:

Puyjwuyij

A follow-up tweet hinted it was the name of the first puzzle, encrypted. As some letters were repeated, this seemed to be the result of a substitution cipher, where each letter is replaced by another one. What could the word be?

Is this a ZK Hack puzzle?

It was likely to be a 9-letter English word or a name, with the letters matching u, y and j repeated in the given positions. Searching for lists of every 9-letter word led to a files in the GitHub repository antichown/burp-payload. Loading this file in Python and going through the list to find potential candidates resulted in 5 words:

words = [w.strip() for w in open("9 letter words.pay")]
result = [
    w for w in words
    if w[1] == w[5] and w[2] == w[6] and w[3] == w[8] and len(set(w)) == 6
]
print("\n".join(result))
deianeira
forehorse
moratoria
preloreal
zeitgeist

What could the correct solution be? The encryption algorithm might be even simpler than a 1-character substitution cipher. Analyzing the character differences between candidate words and "Puyjwuyij" led to:

print("\n".join(
    w + " : " + ",".join(f"{(ord(y)-ord(x))%26:2d}" for x, y in zip(w, "puyjwuyij"))
    for w in result
))
deianeira : 12,16,16, 9, 9,16,16,17, 9
forehorse : 10, 6, 7, 5,15, 6, 7,16, 5
moratoria :  3, 6, 7, 9, 3, 6, 7, 0, 9
preloreal :  0, 3,20,24, 8, 3,20, 8,24
zeitgeist : 16,16,16,16,16,16,16,16,16

The solution was likely "Zeitgeist", where each letter was shifted by 16 to produce "Puyjwuyij". Later, another tweet hinted it was a Caesar cipher and finally the puzzle was published:

ZK Hack V - Puzzle V-1: Zeitgeist is out!!

https://zkhack.dev/zkhackV/puzzleV1.html

1. Subject

From the puzzle page https://zkhack.dev/zkhackV/puzzleV1.html:

Everybody knows that you don’t really have to use the ZK version of SNARKs, because the proofs are so small anyway and can’t reveal much. Or do you?

From the GitHub repository https://github.com/ZK-Hack/puzzle-zeitgeist:

A few years ago, Bob signed up to SuperCoolAirdrop™. The process was simple: provide a hash of your private key to register and when your airdrop is ready you'll receive a notification. Today, Bob finally received a notification from SuperCoolAirdrop™. It's time to claim his airdrop!

The process is simple, he just needs to give a proof of knowledge that he knows the private key associated with the commitment he made years ago. To prevent replay attacks, SuperCoolAirdrop™ implemented a nullifier system: on top of proving knowledge of the private key, users must create a secret nonce and produce a public nullifier. Once the SuperCoolAirdrop™ server verifies the proof and logs the nullifier, the proof cannot be re-used.

So Bob picks a random nonce, his favorite proof system and sends in a proof. The proof gets rejected... weird. He samples a new nonce and tries again. And again. And again. Still, his proofs get rejected.

Suddenly it dawns on him. Is SuperCoolAirdrop™ legit? Is this an attempt to steal his private key?

From Twitter:

meme about the puzzle subject

2. Discovering the Circuit

The GitHub repository contains some copy of halo2 and poseidon-circuit and a Rust program using them in src/main.rs.

There also are some binary files in directories commitments/, nullifiers/ and proofs/, named commitment_0.bin, commitment_1.bin... and nullifier_0.bin..., proof_0.bin... Each directory contains 64 files and they get loaded by function deserialize. There also is a function named serialize which creates these files from the result of a function shplonk:

pub fn serialize() {
    for i in 0..64 {
        let (proof, nullifier, commitment) = shplonk();

        let filename = format!("./proofs/proof_{}.bin", i);
        let mut file = File::create(&filename).unwrap();
        file.write_all(&proof).unwrap();

        let filename = format!("./nullifiers/nullifier_{}.bin", i);
        let mut file = File::create(&filename).unwrap();
        file.write_all(&nullifier.to_repr()).unwrap();

        let filename = format!("./commitments/commitment_{}.bin", i);
        let mut file = File::create(&filename).unwrap();
        file.write_all(&commitment.to_repr()).unwrap();
    }
}

To better understand how the content of these files get used, let's take a look at function shplonk. It starts by instantiating a KZG Commitment Scheme on an elliptic curve named BN256:

const K: u32 = 6; // Use 2^6 = 64 rows

let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
let params = ParamsKZG::<Bn256>::setup(K, setup_rng);
let pk = keygen::<KZGCommitmentScheme<_>>(&params);

The documentation of ParamsKZG::setup warns this function must not be used in production, because it draws the toxic secret from the given Random Number Generator (RNG). Indeed, doing such a thing means that it is possible to lie about some commitments done with this trusted setup. So a malicious prover can likely forge a proof which gets accepted by the verifier.

However, the subject of the puzzle indicated that the proofs Bob forged were rejected and the objective of the puzzle appears to be to recover Bob's secret key (according to the template code in function main). Being able to forge an invalid proof does not seem to be useful here.

Function keygen computes a Verifying Key (VK) and a Proving Key (PK) from a PLONK circuit named MyCircuit. The circuit is defined in a impl Circuit<Fr> for MyCircuit block. At first glance, this looks quite complex but from a high level perspective, the circuit:

  • uses 3 witnesses called secret, nonce and const ;
  • computes the Poseidon hash of [secret, const] and calls this commitment ;
  • computes the Poseidon hash of [secret, nonce] and calls this nullifier ;
  • exposes commitment and nullifier, so that the verifier can use them as public inputs.

All field elements (the witnesses and public inputs) use type halo2curves::bn256::Fr, representing the scalar field of curve BN256. The modulus, 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001, is 254-bit long, so field elements get serialized as 32-byte binary data. This is actually the length of every file commitments/commitment_....bin and nullifiers/nullifier_....bin.

Reading functions create_proof and verify_proof makes it clear that each file proofs/proof_....bin contains a PLONK transcript and can be used to verify that commitment and nullifier were computed according to the circuit.

Retrieving secret from the public inputs is possible if the hash function is broken. As the Poseidon hash is used here with parameters explicitly written in the source code, let's review them:

const WIDTH: usize = 3;
const RATE: usize = 2;

digest = poseidon_base::primitives::Hash::<
    _,
    P128Pow5T3Compact<Fr>,
    ConstantLength<2>,
    WIDTH,
    RATE,
>::init()
.hash(msg);

The function parameters seem to match the function definition of poseidon_base::primitives::Hash, with 2 inputs, a width (capacity) of 3 field elements and a sponge rate of 2. P128Pow5T3Compact is documented as:

Poseidon-128 using the $x^5$ S-box, with a width of 3 field elements, and the standard number of rounds for 128-bit security "with margin".

Poseidon's paper provides an example for the S-Box Layer:

$α = 3$ if $p \neq 1 \mod 3$ or $α = 5$ if $p = 1 \mod 3$ and $p \neq 1 \mod 5$

For BN256 scalar field, a Python console gives:

>>> p = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
>>> p % 3
1
>>> p % 5
2

So choosing the $x^5$ S-box matches the example from the paper. In the end, the settings chosen to compute Poseidon hashes seem secure and do not allow retrieval of the message from the digest.

Now let's look at the PLONK implementation. The code includes some intriguing comments in the Vanishing prover implementation:

impl<C: CurveAffine> Argument<C> {
    /// This commitment scheme commits to a _zero polynomial_,
    /// that means our commitment scheme is binding but not hidding.
    /// This is fine for schemes that does not require zero-knowledge.
    pub(in crate::plonk) fn commit /* ... */ {
        // Sample a random polynomial of degree n - 1
        let random_poly = domain.constant_lagrange(C::Scalar::ONE);
        let random_poly = domain.lagrange_to_coeff(random_poly);
        // Sample a random blinding factor
        let random_blind = Blind(C::Scalar::ZERO);
        let c = params.commit(&random_poly, random_blind).to_affine();
        // We write the identity point to the transcript which
        // is the commitment of the zero polynomial.
        transcript.write_point(c)?;

        Ok(Committed {
            random_poly,
            random_blind,
        })
    }

The variables random_poly and random_blind do not contain randomly-generated data at all! And even though "This is fine for schemes that do not require zero-knowledge", the circuit used by the puzzle actually attempts to hide the secret.

Nevertheless, this non-random vanishing polynomial (named vanishing in halo2_proofs::plonk::prover::create_proof) is not the only surprise in the prover implementation. Here is an extract of halo2_proofs::plonk::prover::create_proof where some code using random functions was commented out:

// Add blinding factors to advice columns
for advice_values in &mut advice_values {
    //for cell in &mut advice_values[unusable_rows_start..] {
    //*cell = C::Scalar::random(&mut rng);
    //*cell = C::Scalar::one();
    //}
    let idx = advice_values.len() - 1;
    advice_values[idx] = Scheme::Scalar::ONE;
}

This seems interesting. The "advice columns" are not blinded by random field elements but instead by value 1. Could this be exploited to leak the witnesses?

3. Leaking Sensitive Advice Values

Let's see what advice_values contains after the loop which was supposed to add blinding factors in halo2_proofs::plonk::prover::create_proof. To do so, I added to this function:

// Display advice_values
for (col, values) in advice_values.iter().enumerate() {
    println!("advice_values[{col}] = {values:?}");
}

I also defined some functions in src/main.rs generate a proof for the secret 0x5ecc0de and nonce 0xace (using human-readable constants help identifying them in the steps of the proof system):

/// Compute the Poseidon hash of [a, b]
fn poseidon_hash2(a: Fr, b: Fr) -> Fr {
    poseidon_base::primitives::Hash::<
        _,
        P128Pow5T3Compact<Fr>,
        ConstantLength<2>,
        WIDTH,
        RATE,
    >::init()
    .hash([a, b])
}

fn create_test_proof() {
    use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
    use halo2_proofs::poly::kzg::multiopen::ProverSHPLONK;
    use halo2curves::bn256::Bn256;

    let secret = Fr::from(0x5ecc0de_u64);
    let nonce = Fr::from(0xace_u64);
    let nullifier = poseidon_hash2(secret, nonce);
    let commitment = poseidon_hash2(secret, Fr::from(0));

    let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
    let params = ParamsKZG::<Bn256>::setup(K, setup_rng);
    let pk = keygen::<KZGCommitmentScheme<_>>(&params);
    let circuit = MyCircuit {
        witness: Value::known(secret),
        nonce: Value::known(nonce),
    };
    let mut transcript = Blake2bWrite::<_, _, Challenge255<_>>::init(vec![]);
    create_plonk_proof::<KZGCommitmentScheme<Bn256>, ProverSHPLONK<_>, _, _, _, _>(
        &params,
        &pk,
        &[circuit],
        &[&[&[nullifier, commitment]]],
        rand_chacha::ChaCha20Rng::from_seed([42u8; 32]),
        &mut transcript,
    )
    .expect("proof generation should not fail");
}

Calling create_test_proof() from main() displays 8 polynomials:

advice_values[0] = Polynomial { values: [
    0x0000000000000000000000000000000000000000000000000000000005ecc0de,
    0x0000000000000000000000000000000000000000000000000000000000000ace,
    0x0000000000000000000000000000000000000000000000000000000000000000
    ...
advice_values[1] = Polynomial { values: [
    0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000005ecc0de,
    0x0000000000000000000000000000000000000000000000000000000005ecc0de,
    0x0000000000000000000000000000000000000000000000000000000005ecc0de,
    0x2c74fd27ec1969157b09bac1ded6983ce4b4746eff78e2092711af85fd1ba169,
    0x06fb31434b7bfd16e92aabc40ba3596dcc9ed8aa0bc8233609dae3c123223826,
    ...

Each polynomial has 64 coefficients (by the way, this comes from using K = 6 in src/main.rs, as $2^6 = 64$). Some coefficients are 0x5ecc0de and 0xace: the defined secret and nonce! Let's adapt the for loop in halo2_proofs::plonk::prover::create_proof to only display known values:

for (col, values) in advice_values.iter().enumerate() {
    println!("advice_values[{col}] = [");
    for chunk in values.chunks(16) {
        println!(
            "  {}",
            chunk
                .iter()
                .map(|v| {
                    let v_formatted = format!("{v:?}");
                    if &v_formatted ==
"0x0000000000000000000000000000000000000000000000000000000000000000" {
                        "0"
                    } else if &v_formatted ==
"0x0000000000000000000000000000000000000000000000000000000000000001" {
                        "1"
                    } else if &v_formatted ==
"0x0000000000000000000000000000000000000000000000000000000005ecc0de" {
                        "secret"
                    } else if &v_formatted ==
"0x0000000000000000000000000000000000000000000000000000000000000ace" {
                        "nonce"
                    } else {
                        "..."
                    }
                })
                .collect::<Vec<_>>()
                .join(", ")
        );
    }
    println!("]");
}

This now displays:

advice_values[0] = [
  secret, nonce, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
]
advice_values[1] = [
  0, 0, secret, secret, secret, ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ...
  ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ...
  ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., 0, 0, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
]
advice_values[2] = [
  0, 0, 0, 0, 0, ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ...
  ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., ...
  ..., ..., ..., ..., ..., ..., ..., ..., ..., ..., 0, 0, 0, 0, 0, 0
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
]
...

There is some pattern. Actually, digging a bit more led to understanding that coefficients in advice_values[1] only depend on the secret and not the nonce.

But the transcript of the proof does not directly contain advice_values. There are three operations done on these polynomials:

  1. Some commitments are computed for each polynomial (using params.commit_lagrange(poly, *blind) here).
  2. Each polynomial gets replaced with its Lagrange polynomial interpolation over some domain (using domain.lagrange_to_coeff(poly) here).
  3. Some polynomials get evaluated at a field element named x and these evaluations are written to the transcript (here):
// Compute and hash advice evals for each circuit instance
for advice in advice.iter() {
    // Evaluate polynomials at omega^i x
    let advice_evals: Vec<_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            eval_polynomial(
                &advice.advice_polys[column.index()],
                domain.rotate_omega(*x, at),
            )
        })
        .collect();

    // Hash each advice column evaluation
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }
}

Displaying meta.advice_queries gives:

for (i, query) in meta.advice_queries.iter().enumerate() {
    println!("meta.advice_queries[{i}] = {query:?}");
}
meta.advice_queries[0] = (Column { index: 0, column_type: Advice }, Rotation(0))
meta.advice_queries[1] = (Column { index: 1, column_type: Advice }, Rotation(0))
meta.advice_queries[2] = (Column { index: 2, column_type: Advice }, Rotation(0))
meta.advice_queries[3] = (Column { index: 3, column_type: Advice }, Rotation(0))
meta.advice_queries[4] = (Column { index: 1, column_type: Advice }, Rotation(1))
meta.advice_queries[5] = (Column { index: 2, column_type: Advice }, Rotation(1))
meta.advice_queries[6] = (Column { index: 3, column_type: Advice }, Rotation(1))
meta.advice_queries[7] = (Column { index: 4, column_type: Advice }, Rotation(0))
meta.advice_queries[8] = (Column { index: 3, column_type: Advice }, Rotation(-1))
meta.advice_queries[9] = (Column { index: 1, column_type: Advice }, Rotation(-1))
meta.advice_queries[10] = (Column { index: 2, column_type: Advice }, Rotation(-1))
meta.advice_queries[11] = (Column { index: 5, column_type: Advice }, Rotation(0))
meta.advice_queries[12] = (Column { index: 6, column_type: Advice }, Rotation(0))
meta.advice_queries[13] = (Column { index: 7, column_type: Advice }, Rotation(0))
meta.advice_queries[14] = (Column { index: 5, column_type: Advice }, Rotation(1))
meta.advice_queries[15] = (Column { index: 6, column_type: Advice }, Rotation(1))
meta.advice_queries[16] = (Column { index: 7, column_type: Advice }, Rotation(1))
meta.advice_queries[17] = (Column { index: 8, column_type: Advice }, Rotation(0))
meta.advice_queries[18] = (Column { index: 7, column_type: Advice }, Rotation(-1))
meta.advice_queries[19] = (Column { index: 5, column_type: Advice }, Rotation(-1))
meta.advice_queries[20] = (Column { index: 6, column_type: Advice }, Rotation(-1))

index: 1 appears three times. Let's focus on the second line. What this line means is that the polynomial from advice.advice_polys[1] (resulting from an interpolation from advice_values[1]) gets evaluated at a field element x with no "rotation" (at is Rotation(0)). To check this understanding is right, this code can be added before for eval in advice_evals.iter() {:

println!("x = {:?}", *x);
println!("advice_polys[1](x) = {:?}", eval_polynomial(&advice.advice_polys[1], *x));
println!("advice_evals[1]    = {:?}", advice_evals[1]);
x = 0x2fdf871ea0b4b819a68a5c45d77c47374b8458bcc0c3f0577025d346f7bd117e
advice_polys[1](x) = 0x0b9baaa44a05db0dd3d3213e07996b849ceb27e9723de6e0cbae3a6a400db674
advice_evals[1]    = 0x0b9baaa44a05db0dd3d3213e07996b849ceb27e9723de6e0cbae3a6a400db674

By the way, what is this "Lagrange interpolation" done on advice_values[1]? This is a common transformation in the Zero-Knowledge world where a polynomial is crafted from the values it gets at specific points. The idea behind this is that to fully define a polynomial of degree 63 (with 64 coefficients), knowing 64 evaluations are enough.

In the prover, the call to domain.lagrange_to_coeff(poly) uses 64 roots of unity in the used finite field to craft the polynomial. The roots of unity are $1$, $\omega$, $\omega^2$, $\omega^3$..., $\omega^{63}$ where $\omega$ is domain.get_omega() in Rust:

let omega = domain.get_omega();
println!("omega    = {:?}", omega);
println!("omega^64 = {:?}", omega.pow_vartime([64])); // Verify it is a root of unity
println!(
    "advice.advice_polys[1](omega^0) = {:?}",
    eval_polynomial(&advice.advice_polys[1], omega.pow_vartime([0]))
);
println!(
    "advice_polys[1](omega^1) = {:?}",
    eval_polynomial(&advice.advice_polys[1], omega)
);
println!(
    "advice_polys[1](omega^2) = {:?}",
    eval_polynomial(&advice.advice_polys[1], omega.pow_vartime([2]))
);
println!(
    "advice_polys[1](omega^3) = {:?}",
    eval_polynomial(&advice.advice_polys[1], omega.pow_vartime([3]))
);
omega    = 0x1c4c3a258629905ef6036a4037c3aa6ae18d1d2452d64bd2684cfa8ede70fdc7
omega^64 = 0x0000000000000000000000000000000000000000000000000000000000000001
advice_polys[1](omega^0) = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[1](omega^1) = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[1](omega^2) = 0x0000000000000000000000000000000000000000000000000000000005ecc0de
advice_polys[1](omega^3) = 0x0000000000000000000000000000000000000000000000000000000005ecc0de

advice.advice_polys[1] is a polynomial with 64 coefficients which evaluation at $\omega^0$ is advice_values[1][0] = 0, at $\omega^1$ is advice_values[1][1] = 0, at $\omega^2$ is advice_values[1][2] = secret, etc.

Moreover, as the content of advice_values[1] depends on secret but not on nonce, the interpolated polynomial advice.advice_polys[1] also does not depend on nonce.

In short, all Bob's proofs use the same polynomial advice.advice_polys[1], which evaluates at $\omega^2$ to his secret. And the transcripts contain the evaluation of this polynomial at x, which varies between proofs. Let's name the evaluations P(x). If we recover the values of x and P(x) from all 64 transcripts, would it be possible to recover the polynomial advice.advice_polys[1]? Yes, it is, thanks to Langrange interpolation again.

4. Interpolating the Secret

To summarize the attack, each proof transcript contains an interesting evaluation P(x). The evaluation value x comes from a "verifier challenge" which is actually computed from hashing some proof data. To extract them automatically from a proof, a possible way would be to copy function halo2_proofs::plonk::verifier::verify_proof into a new function which returns x and the decoded evaluations of advice polynomials:

pub fn extract_info_from_proof<
    'params,
    Scheme: CommitmentScheme,
    V: Verifier<'params, Scheme>,
    E: EncodedChallenge<Scheme::Curve>,
    T: TranscriptRead<Scheme::Curve, E>,
    Strategy: VerificationStrategy<'params, Scheme, V>,
>(
    params: &'params Scheme::ParamsVerifier,
    vk: &VerifyingKey<Scheme::Curve>,
    strategy: Strategy,
    instances: &[&[&[Scheme::Scalar]]],
    transcript: &mut T,
) -> Result<(Scheme::Scalar, Vec<Scheme::Scalar>), Error>
{
    // Copy from function verify_proof ... until "let advice_evals = "

    // Extract advice_evals for the first proof
    Ok((*x, advice_evals[0].clone()))
}

This function can then be used in main() to extract the evaluations from the transcripts and interpolate the secret:

use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
use halo2_proofs::poly::kzg::multiopen::VerifierSHPLONK;
use halo2_proofs::poly::kzg::strategy::AccumulatorStrategy;
use halo2curves::bn256::Bn256;
use rand_chacha::ChaCha20Rng;
use rand_core::SeedableRng;

let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
let params = ParamsKZG::<Bn256>::setup(K, setup_rng);
let pk = keygen::<KZGCommitmentScheme<_>>(&params);

// Extract the evaluations of advice[0].advice_polys[1]
let mut xs = Vec::new();
let mut evals = Vec::new();
let (proofs, nullifiers, commitments) = deserialize();
for i in 0..64 {
    let (x, evals_at_x) = halo2_proofs::plonk::verifier::extract_info_from_proof::<
        _,
        VerifierSHPLONK<_>,
        _,
        _,
        _,
    >(
        params.verifier_params(),
        pk.get_vk(),
        AccumulatorStrategy::new(params.verifier_params()),
        &[&[&[nullifiers[i], commitments[i]]]],
        &mut Blake2bRead::<_, _, Challenge255<_>>::init(proofs[i].as_slice()),
    )
    .unwrap();
    let px = evals_at_x[1];
    println!("extracted[{i}]: x = {x:?}, P(x) = {px:?}");
    xs.push(x);
    evals.push(px);
}

// Interpolate the polynomial at omega^2
let omega2 = pk.get_vk().get_domain().get_omega().square();
let mut secret = Fr::zero();
for i in 0..64 {
    let mut term = evals[i];
    for j in 0..64 {
        if i != j {
            term *= (omega2 - xs[j]) * (xs[i] - xs[j]).invert().unwrap();
        }
    }
    secret += term;
}
println!("secret = {secret:?}");

// It is also possible to use:
use halo2_proofs::arithmetic::{eval_polynomial, lagrange_interpolate};
let secret2 = eval_polynomial(&lagrange_interpolate(&xs, &evals), omega2);
println!("secret = {secret2:?}");
secret = 0x066ab256379d1a0d7bd1dd54cf3f4171edbf5ca3976e8956fe0ddd10af67418d

The secret was found! 🎉

Was it really the secret committed using Poseidon hash in files commitments/commitment_....bin?

println!("Hash(secret, 0) = {:?}", poseidon_hash2(secret, Fr::zero()));
println!("commitment_0    = {:?}", commitments[0]);
println!("commitment_1    = {:?}", commitments[1]);
Hash(secret, 0) = 0x1f2b5aac96a2527339892fca32dd80b2eb4132b5f90acf27861cba5ddd6ddacf
commitment_0    = 0x1f2b5aac96a2527339892fca32dd80b2eb4132b5f90acf27861cba5ddd6ddacf
commitment_1    = 0x1f2b5aac96a2527339892fca32dd80b2eb4132b5f90acf27861cba5ddd6ddacf

This confirms Bob's secret was actually 0x066ab256379d1a0d7bd1dd54cf3f4171edbf5ca3976e8956fe0ddd10af67418d (or in decimal: 2902393715628053125157988380733315934099850103804946746061390165677120635277).

4. Getting the Nonces

Is it also possible to get the nonce used in each proof? As it is supposed to be different for each, the same strategy of interpolating an advice polynomial from the 64 transcripts cannot be performed. But there is something else interesting.

In the prover, advice_values[0] contained 64 values [secret, nonce, 0..., 0, 1]. This means we know 63 evaluations of the interpolated polynomial advice.advice_polys[0], named $P_0$ afterwards:

  • $P_0(\omega^0) = secret$
  • (unknown) $P_0(\omega^1) = nonce$
  • $P_0(\omega^2) = 0$
  • $P_0(\omega^3) = 0$
  • ...
  • $P_0(\omega^{62}) = 0$
  • $P_0(\omega^{63}) = 1$

Each proof transcript contains $P_0(x)$ too. With 64 known evaluations, it is possible to interpolate the evaluation at $\omega^1$.

let omega = pk.get_vk().get_domain().get_omega();
let mut xs_for_nonce: Vec<Fr> = (0..64).map(|e| omega.pow_vartime([e])).collect();
let mut evals_for_nonce = vec![Fr::zero(); 64];
evals_for_nonce[0] = secret;
evals_for_nonce[63] = Fr::one();
for i in 0..64 {
    let (x, evals_at_x) = halo2_proofs::plonk::verifier::extract_info_from_proof::<
        _,
        VerifierSHPLONK<_>,
        _,
        _,
        _,
    >(
        params.verifier_params(),
        pk.get_vk(),
        AccumulatorStrategy::new(params.verifier_params()),
        &[&[&[nullifiers[i], commitments[i]]]],
        &mut Blake2bRead::<_, _, Challenge255<_>>::init(proofs[i].as_slice()),
    )
    .unwrap();

    // Replace the unknown evaluation at omega with the known one at x
    xs_for_nonce[1] = x;
    evals_for_nonce[1] = evals_at_x[0];
    let nonce = eval_polynomial(
        &lagrange_interpolate(&xs_for_nonce, &evals_for_nonce),
        omega,
    );
    println!("nonce_{i:<2} = {:?}", nonce);
    assert_eq!(poseidon_hash2(secret, nonce), nullifiers[i]);
}
nonce_0  = 0x0789f88cfa2565006c43f604825d1d08a03410763538e9790901c07f52afaee6
nonce_1  = 0x2492645a21839f106c3601638b7f15b77fc683df21e6782b2269116cfebd8a32
nonce_2  = 0x13a85f8402e27520b8dcffeebccb6822b34e412c1bedf7594dda996543afd3ba
nonce_3  = 0x1471f591b8116e68501c7ac4bbb07b1ce6f468de76ad45fd82dcc669ed7325df
nonce_4  = 0x18eb9e392dc764012bfdde9ca8f97a542f26ca8c3868b3062686e173996f7b25
nonce_5  = 0x1d4d8af0ca22d7be68992c7a2daba20af682fdcb0e6e202e884c944085c70306
nonce_6  = 0x0c4b685b5f424437edbf11b751010161e9693403671c348f9b471087f9ed833d
nonce_7  = 0x17f2eac519a2c458f6d7e303cbf8f9aba8e4346e4de3c2443f52666b7abed9e9
nonce_8  = 0x0f82931603fc034a4dd2ebfee0f0559806e9310317236547b76d4de3a256f302
nonce_9  = 0x21a556af745ffa57f11c39710d82bd1db0a44344014a3db3526d0326e9e55dc4
nonce_10 = 0x1fddf6a3dd74a6141294ea75d8b7a3036e654830bcf926ff532d102f522f76a2
nonce_11 = 0x04badaf4dfa198a4e89f87eeaedf3c52bf80e2f5bb8207fa1aa2757cc10a15a6
nonce_12 = 0x286e46c84fe70db0c2c83d0d5c3d508e4163d09ef8d00d23c54a0eb656d28fdf
nonce_13 = 0x2dd826e219737cc4759546be539c3f5fb29de3fe2b5918a5d71984244a51f15e
nonce_14 = 0x0b185ca8bb92ff6e1f33da5a9e03c840cdf4078f092c1b56e94466c0b2135fd7
nonce_15 = 0x07c47d6804ae234fb98f8a80031c0bb0833b126c0af1bd95eeae8a42b4f9976c
nonce_16 = 0x1361491805079afc0cbe0f4f4eb0377537f7e17b23fc222cd17e210768f3a0ef
nonce_17 = 0x07589ec455592f73c986f3e8ccb48cbfee1f320987374585753a098e5f0a0c77
nonce_18 = 0x19fa51bdf7adcf6cd7dca83c8e6e231764c592656ef45e153097ddd4dc12113c
nonce_19 = 0x08932ef340a71963077106cdf2efef7cb2e435b6e8176cf1f1ff19f5962dd830
nonce_20 = 0x21c9a0db74a583ea45c6d37ed76e7dd7c9118ca84710f78e993dd9560640e33b
nonce_21 = 0x01f6936ba22c7a660510895eee2f37778162437b4d48a2359f71cb3e645e24b7
nonce_22 = 0x1d90e15b0104b7c006cdd0574a415f68cc3dd41ff6c019862cad7586851acd7c
nonce_23 = 0x1156695cf3ccdb69a4b6e812c7680768a1016860c395b9dc424399bdf30790a8
nonce_24 = 0x211dabcdfc9ce6bc8894548fbe5e6f98255cbc5e92074b8f0b9b42cd30812662
nonce_25 = 0x281af2a06c356cf2a153b9ca38b1208da1eb386e6db5c1dd11bad98f05c7ae7a
nonce_26 = 0x04afb5bc70b36b032f41a57e08d519450c147bd61808875b0efa4aea1c107a04
nonce_27 = 0x145b4e056564a5e420c000c286ba421b0bf689a28b8f38c1ca91bc7548bb9d4c
nonce_28 = 0x063f2674680721b384334cd38f3bbcca66de4463e12a32578e6143b3a667d6a9
nonce_29 = 0x24b369a002a057dc9adea337663463ea63239c01aebbb6e51fdae25af2b90c63
nonce_30 = 0x03bc824a13ab47e9996c41b1fa54071dd8325a56d05032cc11c471c70a7e8ca1
nonce_31 = 0x1e7b584c6fecab63c6bb8cacb3ac33248c3f3c835162d2c952e6d15d83811b73
nonce_32 = 0x1c9f81c35e4d163c556ce05ff393ed76a7e567d0bcfbdfb512328eebb44c2533
nonce_33 = 0x0ef6a876a1d39fc6cbb272eccb6225a90847376e2e07de57e922c07d6e427cc2
nonce_34 = 0x12355a7384ab45a72d34e05d4a9606b75468e5bfdcd685dd6c8b80eeef4a0169
nonce_35 = 0x17dea6809b76101bd7c05c84b96102224920c6b3759885106e37ec9fe3cf8633
nonce_36 = 0x1e60b3f817af13efdfa2630a4e0330b057c6fb700c97522a3582ff43cd0d716e
nonce_37 = 0x01148b0e668d8cc27bb7110e4541fe485f596591810d968fe0e21ef5989d712e
nonce_38 = 0x2e1919bd691813f70ec16bb3d3412dd0ea2d84a94654d7705ba9c8d8009b2d46
nonce_39 = 0x258397613e9d7fcbdefcd59f3b6349a8f65403dbdc6e479052b8c24b7ffd6f98
nonce_40 = 0x28b5e7b95a8284a48a5d66546bbd59989d65b93dc87417d3bde94accc837e9a8
nonce_41 = 0x28d70b3c06f3422d86a89f33d8b8aed4f14b3a1cda265119c753c7181184a1c4
nonce_42 = 0x03a73c6107f5edeb7281002de550987966f5fac35bfeacc8d19a7dcf68382c73
nonce_43 = 0x2ea489e84a427cd8ab44433024f147267e27baa6b4662997519d7313761b53f3
nonce_44 = 0x26bee67b1ec090035381909417473b77a88802f459a8dfef29362f965d2cb49b
nonce_45 = 0x272d2bbd124e538ce6c9044608ba71b1a1aee911a77b2ee29ef53b4e44a46932
nonce_46 = 0x1c2b359f8822f5904a610241fd9dace2d7c3cd4751a1576f96f5b520e758c1eb
nonce_47 = 0x135e8684f78d66ba4cfe5d330b7cd23750c471328268bff2c0e7e23e4db57739
nonce_48 = 0x231aa17335ed84e225494200e866b7bd66097a90337bcb7b3e2ceb3ea04d0e95
nonce_49 = 0x0eb0fbd4fa60581654267db7f44623d210f62112bc00fe504a334a801a752210
nonce_50 = 0x114d04e96625419b20d4cdf9b61e1b921699e71002d87e69424f6f1ae04d5f45
nonce_51 = 0x2ce4f36bf68d43ccaf5a1811a74f6f523aa8ab0ed3e0985c6f7fc259e5b8afb3
nonce_52 = 0x0cb9d9ea8c55222159492743517392851ea41964c955785c787252a1177f3433
nonce_53 = 0x1a32445a9421d73c2d964cb7e59490ec782d362337b07ae2f00883d8b09c450f
nonce_54 = 0x275bf5b333ad751e8e8129a9af1e0d741e9bc9941a7b05c914240a9d4004967d
nonce_55 = 0x0498653254d4b602fdbe052dfa72698665b722a9bdbd255b0b051d5ad4efc3e8
nonce_56 = 0x263dbbf942938e955ecf4a4a30fa9e1e3df50b3c7908b0012b4d2a7854018afb
nonce_57 = 0x188d7a8b56752303b985af945914c73f2028b321a228fbe8263fa17446de787f
nonce_58 = 0x15c5b3c946fd954a17a668e46ff83b902ce8d38e5a10a90b39bd8bb8b15d6a3f
nonce_59 = 0x19c894c958317269586a946856285bab191cff5b6b18bc07ad3ca5d3c28ea8b9
nonce_60 = 0x12415861117a111fd391801ae9f0b67a433893d4f13a764fcc2989f6841cb189
nonce_61 = 0x0d0628b1a51afb4c9ac9ed9aa648b01b5728453856621d8577dbd2003105926a
nonce_62 = 0x2767e7df0e22f54348dc2cc3b4325cf36146e8d0ba1f9a09aba61d41688b5a16
nonce_63 = 0x06fa66c37037d95a50fa4d03165bf1e7a1a6cbedd6d19aa4f8cd12dd64125ea3

All nonces were successfully recovered :)

Conclusion

The proof system used by SuperCoolAirdrop™ does not hide the witnesses. This broke the zero-knowledge property and enabled recovering the secret from proof transcripts. In the end, sharing 64 proofs is enough to fully retrieve Bob's secret and all nonces he used.

The patched source code of the puzzle is available on https://github.com/niooss-ledger/zkhack5-puzzle-zeitgeist.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment