Write up of ZK Hack Puzzle 4: Hidden in Plain Sight

gistfile1.txt

https://hackmd.io/@-yB0zvcCSGu5i7kvgWEeRw/ryYkFHKOY

# Write Up of ZK Hack Puzzle 4: Hidden in Plain Sight
by [grjte](https://github.com/grjte/)

Another week, another fun ZK Hack puzzle to solve! This week's puzzle comes from the team at Anoma.

The puzzle repo with the description is [here](https://github.com/kobigurk/zkhack-hidden-in-plain-sight). 

For this puzzle, there were a few resources that I found particularly helpful for learning about the roots of unity (aka the evaluation domain):

* PLONK By Hand [Part 1](https://research.metastate.dev/plonk-by-hand-part-1/) and [Part 2](https://research.metastate.dev/plonk-by-hand-part-2-the-proof/)
* Vitalik's [article](https://vitalik.ca/general/2019/09/22/plonk.html) on PLONK

PLONK By Hand was shared in the ZK Hack discord, so if you're working on these puzzles but not yet in the discord, I recommend joining.

## Step 1: Break down what's happening
The first thing we want to do is understand how everything in the transaction protocol works.

After reviewing the puzzle description and the rust code in the *[generate.rs](https://github.com/kobigurk/zkhack-hidden-in-plain-sight/blob/main/src/generate.rs)* file, we can break down what's going on into a series of high-level steps grouped into three phases. We'll plan to dig deeper into specific steps later on as needed. There might be details we don't need, which will only be distracting ;)

### Phase 1: Sets up the puzzle (lines 54-61)
1. generates 1000 accounts
1. selects a random account to be the target for this puzzle
1. generates the trusted setup used for the puzzle

### Phase 2: Blinds the target account (lines 63-66)
1. creates a polynomial from the target account called *target_acct_poly* using the evaluation domain - this is the degree-31 polynomial $P$ from the puzzle description
1. generates 2 random numbers and create *blinding_poly*, which will be used to hide the target account polynomial - this is $(b0 + b_1x)$ from the puzzle description
1. uses (1) (2) and [Arkworks](https://docs.rs/ark-algebra-intro/0.3.0/ark_algebra_intro/) function *mul_by_vanishing_poly* to create *blinded_acct_poly*, the blinded polynomial of the account - this is $Q$ from the puzzle description, where $Q(x) = P(x) + (b_0 + b_1x) • Z_H(x)$, and $Z_H(x)$ is the *vanishing_poly* from Arkworks

### Phase 3: Creates the proof data (lines 68-74)
1. creates the commitment using a function called *kzg_commit* with the previously generated  *blinded_acct_poly* and trusted setup *setup*
1. generates the 2 random challenges
1. gets the 2 openings by evaluating the blinded polynomial *blinded_acct_poly* at the challenges

## Step 2: assess what we know
Now that we have a clear view of what's going on, let's go through the steps in our breakdown carefully and identify what we know (or can figure out!)

Here's what the puzzle tells us about what we have to work with:

*Armed with the **blinded commitment** and **two openings** from the intercepted transaction as well as the public data (the **trusted setup** for the KZG commitment scheme, a list of **all one-thousand account addresses** participating in the pool, and the **two
random challenges** used to compute the openings)*

Let's match this information to our breakdown from above and see where that leaves us.

The commitment, two random challenges, and two random openings are exactly the information from our Phase #3, so there's nothing more to look for there.

The list of 1000 account addresses and the trusted setup match up respectively with steps 1 and 3 of Phase #1. The only thing remaining in Phase #1 was the selection of the target account. That's what we're looking for, so Phase #1 has nothing more to offer us.

That leaves us with Phase #2, which had 3 steps. Let's analyse each of them more closely.

### Analyse Phase 2: the polynomial blinding process

#### Step 1: creates a polynomial from the target account called *target_acct_poly* - this is the degree-31 polynomial $P$ from the puzzle description
```
let target_acct_poly = DensePolynomial::from_coefficients_vec(domain.ifft(&target_acct));
```

There are neither secrets nor randomness here, so there's nothing going on that we can't replicate, in theory. 

We know all of the addresses, which means we know the target's address, even though we don't know which one it is. The evaluation domain consists of the unique "roots of unity" for the domain size used to generate the puzzle. We can get it using Arkworks.

```
let domain: GeneralEvaluationDomain<Fr> =
    GeneralEvaluationDomain::new(number_of_accts + 2).unwrap();
```

This means we could potentially create a polynomial for each of our addresses.

The main challenges are that it could be hard to compute, and we would still need to figure out which of the polynomials is actually our *target_acct_poly*. However, it seems like we might have some options here.

#### Step 2: generates 2 random numbers and create *blinding_poly*, which will be used to hide the target account polynomial - this is $(b0 + b_1x)$ from the puzzle description
```
let blinding_poly =
    DensePolynomial::from_coefficients_vec(vec![Fr::rand(&mut rng), Fr::rand(&mut rng)]);
```
This step introduces the blinding polynomial, which is created using 2 randomly generated blinding factors.

There's no easy way for us to recreate this, so $b_0$ and $b_1$ are unknowns.


#### Step 3: uses (1) (2) and [Arkworks](https://docs.rs/ark-algebra-intro/0.3.0/ark_algebra_intro/) function *mul_by_vanishing_poly* to create *blinded_acct_poly*, the blinded polynomial of the account - this is $Q$ from the puzzle description, where $Q(x) = P(x) + (b_0 + b_1x) • Z_H(x)$
```
let blinded_acct_poly = target_acct_poly + blinding_poly.mul_by_vanishing_poly(domain);
```
Finally, this step pulls the other two steps together to create the blinded_acct_poly. 

Here's what we know at this point:
* two evaluations of Q at two known values of x (our two openings at our two random challenges)
* $Z_H(x)$ (Arkworks has a number of useful helpers for interacting with the vanishing polynomial)
* how to generate polynomials for each of our 1000 account addresses. One of these is our target polynomial

The only true unknowns are $b_0$ and $b_1$, so let's reorganize the equation to group all the terms we know something about.

$$(Q(x) - P(x)) / Z_H(x) = b_0 + b_1x$$

Now only actually know about Q at the 2 challenge points $cha_1$ and $cha_2$, so let's look at those points and replace $Q(x)$ with its evaluated openings $opn_1$ and $opn_2$.


$$(opn_1 - P(cha_1)) / Z_H(cha_1) = b_0 + b_1*cha_1$$

$$(opn_2 - P(cha_2)) / Z_H(cha_2) = b_0 + b_1 * cha_2$$

Now we've *almost* got 2 equations with 2 unknowns, which would be a wonderful place to be. We just need to figure out what to do about $P$.

## Brute force FTW 💪
Let's try brute force and see what happens. We'll loop through each of our 1000 account addresses and essentially run a modified version of Phase 2 on it

1. create the polynomial for the account
1. use the new polynomial in our 2 equations from above to solve for our 2 unknowns $b_0$ and $b_1$
1. use $b_0$ and $b_1$ to create the blinding polynomial
1. use the account polynomial from (1), the blinding polynomial from (3) and the vanishing polynomial from Arkworks to create the blinded polynomial
1. use the handy *kzg_commit* helper function to commit the blinded polynomial. 
1. Compare this commitment to the intercepted one to see if we have a match. Stop, if so.

### The Code
Here's how the code looks.

#### Setup
First, let's do a bit of setup. We'll use Arkworks to get the evaluation domain, which will be used to generate each of the account polynomials. We'll also get the evaluation of the vanishing polynomial at both challenge points, which will help us calculate $b_0$ and $b_1$ for each polynomial.

```    
// the # of accounts used to generate the puzzle
let number_of_accts = 1000usize;
// get the roots of unity (use the same domain used to generate the puzzle)
let domain: GeneralEvaluationDomain<Fr> =
    GeneralEvaluationDomain::new(number_of_accts + 2).unwrap();

// evaluate the vanishing polynomial at the two challenge points
let van_1_eval = domain.evaluate_vanishing_polynomial(cha_1);
let van_2_eval = domain.evaluate_vanishing_polynomial(cha_2);
```

#### Blinding Factors
Next, we'll need a function that accepts an account polynomial as input (*acct_poly*) and solves for the blinding factors.

```

// use the 2 challenges, 2 openings, and evaluations of the vanishing polynomial at the 2 openings to
// compute the 2 unknown blinding factors for this account polynomial
fn get_blinding_factors(
    cha_1: Fr,
    cha_2: Fr,
    opn_1: Fr,
    opn_2: Fr,
    acct_poly: DensePolynomial<Fr>,
    van_eval_1: Fr,
    van_eval_2: Fr,
) -> Vec<Fr> {
    // get openings for account polynomial
    let acct_eval_1 = acct_poly.evaluate(&cha_1);
    let acct_eval_2 = acct_poly.evaluate(&cha_2);

    // opening of blinding poly @ cha_1 = (opn_1 - acct_eval_1) / van_eval_1
    let num_1 = opn_1.sub(acct_eval_1);
    let opn_blinding_1 = num_1.div(van_eval_1);
    // opening of blinding poly @ cha_2 = (opn_2 - acct_eval_2) / van_eval_2
    let num_2 = opn_2.sub(acct_eval_2);
    let opn_blinding_2 = num_2.div(van_eval_2);

    // b_2 = (opn_blinding_1 - opn_blinding_2) / (cha_1 - cha_2)
    let opn_diff = opn_blinding_1.sub(opn_blinding_2);
    let b_2 = opn_diff.div(cha_1.sub(cha_2));
    // b_1 = opn_blinding_1 - b_2 * cha_1
    let b_1 = opn_blinding_1.sub(b_2.mul(cha_1));

    // return blinding factors
    (vec![b_1, b_2])
}
```

#### Blinded Account Polynomial
Next, we'll write a function that can take an account and give us a blinded polynomial for it. We'll also pass in the setup info we prepared above and the data required by our *get_blinding_factors* function

```
// use the 2 challenges, 2 openings, evaluations of the vanishing polynomial at the 2 openings, and eval domain to
// get the blinded polynomial for the specified account acct
fn get_blinded_acct_poly(
    domain: GeneralEvaluationDomain<Fr>,
    acct: Vec<Fr>,
    cha_1: Fr,
    cha_2: Fr,
    opn_1: Fr,
    opn_2: Fr,
    van_1_eval: Fr,
    van_2_eval: Fr,
) -> DensePolynomial<Fr> {
    let acct_poly = DensePolynomial::from_coefficients_vec(domain.ifft(&acct));

    // use the challenges and openings to get the blinding factors
    let b_factors = get_blinding_factors(
        cha_1,
        cha_2,
        opn_1,
        opn_2,
        acct_poly.clone(),
        van_1_eval,
        van_2_eval,
    );

    // create the blinded account polynomial with the blinding factors
    let blinding_poly = DensePolynomial::from_coefficients_vec(b_factors);
    let blinded_acct_poly = acct_poly + blinding_poly.mul_by_vanishing_poly(domain);

    // return the blinded account poly
    (blinded_acct_poly)
}
```

#### Run it
We're finally ready to run the loop and see if it works. We'll commit each blinded polynomial and compare it to the commitment from the puzzle data, called *commt*.

```
// initialize the solution vector
let mut solution_commitment = G1Affine::zero();

// brute force it: iterate through the accounts
// use the 2 challenges and 2 openings to find the 2 unknown blinding factors for each account
// the create the commitment for that blinded polynomial of each account and see if it matches the proof commitment
// if so, we have found our account
for index in 0..accts.len() {
    println!("checking acct at index {}", index);
    let acct = &accts[index];

    let blinded_acct_poly = get_blinded_acct_poly(
        domain,
        acct.clone(),
        cha_1,
        cha_2,
        opn_1,
        opn_2,
        van_1_eval,
        van_2_eval,
    );
    let commitment: G1Affine = kzg_commit(&blinded_acct_poly, &setup);

    if commt == commitment {
        println!("solution found at index {}", index);
        solution_commitment = commitment;
        break;
    }
}
```

Success!

We are able to iterate through the addresses, compute each polynomial and compare the commitments in just a couple of minutes, revealing the index of the target address at 535.

This protocol was broken because it was too easy for us to quickly brute force a solution.