Skip to content

Instantly share code, notes, and snippets.

@negativeknowledge
Created Nov 20, 2021
Embed
What would you like to do?
Puzzle 4 write up

ZK Hack Puzzle 4 Writeup

The setup

The intro describes a 1000 person shielded pool. To summarize, we observe the following information:

  • A kzg setup
  • The 1000 addresses in the pool.
  • One transaction. i.e. a commitment to a polynomial Q(x) = P(x) + (b_0 + b_1x) H_Z(x). Here P(x) is the recipient address in polynomial form, b_0 and b_1 are secret blinding factors and H_Z(x) is the known hiding polynomial.
  • Two challenges cha_1 and cha_2.
  • Two openings opn_1 = Q(cha_1) and opn_2 = Q(cha_2).

Our goal is to recover P(x).

Idea

The hint says the the puzzle is motivated by rounds 1,2 and 4 of Plonk. Round 4 looks similar to the challenge/opening process of our protocol, but in plonk only one opening is given. The two opening give us the following information

b_0 + cha_1 * b_1 = (opn_1 - P(cha_1)) / H_Z(cha_1) b_0 + cha_2 * b_1 = (opn_2 - P(cha_2)) / H_Z(cha_2)

On the right hand side of the two equations, P(cha_1) and P(cha_2) are the only unknowns. In other words, if we knew P then we'd have a system of two equations with two unknowns and could solve for b_0 and b_1. While we don't know P yet, we do know that it's one of the 1000 provided accounts. This means we can attack the problem by brute force: for each candidate P we solve for the corresponding b_0 and b_1 and check if the resulting commitment is equal to commt. If it is then we know we've found the right P.

Details

Solving the above equations gives

b_1 = (tau_1 - tau_2)/(cha_1 - cha_2) where tau_i := (opn_i - p(cha_i))/Z_h(cha_i)

and then b_0 = tau_1 - b_1 * cha_1

Solution

Here is the computation needed to find the recipient:

let number_of_accts = 1000usize;
let domain: GeneralEvaluationDomain<Fr> =
GeneralEvaluationDomain::new(number_of_accts + 2).unwrap();
let vanishing_poly = domain.vanishing_polynomial();
let denom_1: Fr = vanishing_poly.evaluate( &cha_1);
let denom_2: Fr = vanishing_poly.evaluate( &cha_2);

let mut solution_blinded_acct = DensePolynomial::from_coefficients_vec(vec![Fr::from(4), Fr::from(5)]);

for i in 0..number_of_accts{
    

    let mut tmp_acc = &accts[i];
    let mut tmp_poly = DensePolynomial::from_coefficients_vec(domain.ifft( tmp_acc));

    // compute tau_1 := (o_1 - p_1)/Z_h(c_1) and tau_2
    let mut p_1: Fr = tmp_poly.evaluate( &cha_1);
    let mut p_2: Fr = tmp_poly.evaluate( &cha_2);
    let mut num_1: Fr = opn_1 - p_1;
    let mut num_2: Fr = opn_2 - p_2;

    let mut tau_1: Fr = num_1 * denom_1.inverse().unwrap();
    let mut tau_2: Fr = num_2 * denom_2.inverse().unwrap();

    // compute b_1 = ( tau_1 - tau_2)/(c_1 - c_2)
    let mut num: Fr = tau_1 - tau_2;
    let mut denom: Fr = cha_1 - cha_2;
    let mut b_1: Fr = num * denom.inverse().unwrap();

    // compute b_0 = tau_1 - b_1*c_1
    let mut b_0: Fr = tau_1 - b_1 * cha_1;
    // compute alternate b_0 = tau_2 - b_1 * c_2 and make sure they match
    //let mut alt_b_0: Fr = tau_2 - b_1 * cha_2;
    //assert!( b_0 == alt_b_0, "two methods of computing b_0 do not agree");

    // commit to poly and see if it agrees with commt
    let mut blinding_poly =
        DensePolynomial::from_coefficients_vec(vec![b_0, b_1]);
    let mut blinded_acct_poly = tmp_poly + blinding_poly.mul_by_vanishing_poly(domain);
    let mut commitment: G1Affine = kzg_commit(&blinded_acct_poly, &setup); 

    if commt==commitment{
        println!("Found Answer!!! Trail # {:?}", i);
        solution_blinded_acct = blinded_acct_poly.clone();
        break;
    }
}

One tricky point

My original solution failed because of a subtle detail. The accounts are given as length 32 vectors and I assumed each entry in the vector represented a coefficient of the corresponding polynomial. However, digging into generate.rs it seems that the polynomial is actually given in evaluation form. Generate.rs shows how to translate it to coefficient form.

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