Instantly share code, notes, and snippets.

# negativeknowledge/writeup.md Secret

Created Nov 20, 2021
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.