ZK-Hack Puzzle #4 Writeup

Intro

This week the 4th puzzle of the ZK-Hack event was released.
The event includes really cool workshops and puzzles with the goal of teaching more people about the world of Zero-Knowledge.
I (@shalev0s) solved the challenges together with Matan and Elichai.
We also write writeups for every challenge available here: puzzle 1, puzzle 2, puzzle 3.

Hidden in Plain Sight

Sometimes you can say too much

We are also told to read about KZG polynomial commitments.

Then we get to the challenge itself.

One-thousand accounts participate in a shielded pool which hides the
recipients and other data in each transaction between parties in the pool. The
*recipient* is a 256-bit account address which is hidden by blinding a KZG-like
polynomial commitment to the address. The sender of the transaction chooses two
secret *blinding factors* known only to them by which the polynomial commitment
is blinded. Included with the commitment are two openings used to verify the
commitment. You intercept a transaction by observing the shielded pool. 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) can you deanonymize the
recipient address?

Blinding Scheme
---------------
The 256-bit recipient address is split into a vector of 32
bytes, and each byte (as a BLS12-381 scalar) becomes a coefficient of a
degree-31 polynomial P. There is an evaluation domain H = {1, ω, ω^2, ...,
ω^(n-1)} with $ω^n = 1$ and a vanishing polynomial Z_H(x) = x^n -1 which
evaluates to 0 on each element of the evaluation domain. The sender of the
transaction chooses two secret blinding factors b_0 and b_1 and computes the
blinded polynomial Q(x) = P(x) + (b_0 + b_1x) • Z_H(x).

Polynomial Commitment
---------------------

The KZG-like polynomial commitment scheme uses a public
trusted setup S={g, g•s, ..., g•s^(n+1)}$ where g is the generator point of the
BLS12-381 elliptic curve and s is a secret scalar. For the polynomial Q(x) = c_0
+ c_1x+c_2x^2 + ... + c_(n+1)x^(n+1) the commitment com(Q) = c_0•g + c_1•g•s +
c_2•g•s^2 + ... + c_(n+1)•g•s^(n+1).

Openings
--------
Openings of the polynomial are required in order to verify the
polynomial commitment. These are simple evaluations of the polynomial at random
challenges which are public. For instance, for challenges z_1 and z_2, the
openings are Q(z_1) and Q(z_2).

Setup

Let's take a closer look at our setup.

We are given the 256-bit addresses of a 1000 accounts of some network.
For every transaction in the network, the address of the recipient of the transaction is hidden using a blinded commitment.
We are given the blinded commitment of some transaction.

Our goal is to figure out who the recipient is out of all the possible accounts.
We are given:

• The blinded commitment of the transaction
• Two commitment openings for the blinded commitment
• All 1000 account addresses
• Some public trusted setup
  $S$ needed for the commitment

Now let's dive into the blinded commitment scheme:

Blinding Scheme

(Based on the given code)
First, we set an evaluation domain of size

$n:=1024$ to be:

$H=\{\mathrm{\forall }0\le i<n|{\omega }^i\}$ s.t.

${\omega }^n=1$, (roots of unity)

The account address is split into 32 bytes -

$a_0,\dots ,a_{31}$.
We then look at the tuples:

$({\omega }^0,a_0),\dots ,({\omega }^{31},a_{31}),({\omega }^{32},0),\dots ,({\omega }^{n-1},0)$
As

$n$ evaluations of a polynomial.
Using the Inverse FFT algorithm, we compute a polynomial

$P(x)$ of degree

$<n$ s.t. its evaluations at

${\omega }^i$ are

$a^i$ (or

$0$ for

$i\ge 32$).

We also define a vanishing polynomial

$Z_H(x)=x^n-1$.
Let the transaction creator pick to random values

$b_0,b_1{\in }_R{\mathbb{F}}_r$.
Define the blinded polynomial as:

$Q(x):=P(x)+(b_0+b_{1}x)\cdot Z_H(x)$
Note that since

$Z_H({\omega }^i)=0$ for all

$i$, then

$Q(x)$ evaluates to the same values as

$P(x)$ for all

${\omega }^i$.
Also, note that

$deg(Q(x))=n+1$.

Polynomial Commitment

We assume a trusted public setup

$S=\{\mathrm{\forall }0\le i\le n+1|s^i\cdot G\}$.
Where

$G$ is a generator of the BLS12-381 elliptic curve and

$s$ is a secret scalar not known to anyone.
For

$Q(x)=\sum _{i=0}^{n+1}{q}_i\cdot x^i$, the commitment is:

$$comm(Q(x))=\sum _{i=0}^{n+1}(q_i\cdot s^i)\cdot G=(\sum _{i=0}^{n+1}{q}_i\cdot s^i)\cdot G=Q(s)\cdot G$$
This is the blinded commitment for an account.
It is given with two openings:

$(z_1,Q(z_1)),(z_2,Q(z_2))$.

Solution

Openings

Let's break down our openings:

$$\begin{gathered} Q(z_1)=P(z_1)+(b_0+b_1{z}_1)\cdot Z_H(z_1) \\ Q(z_2)=P(z_2)+(b_0+b_1{z}_2)\cdot Z_H(z_2) \end{gathered}$$

Note, that for every account

$a$ we can compute

$P_a(x)$, the

$P(x)$ polymoial for that account.
For the rest of the solution we will always assume we are running the same computation for all accounts.

Since, we can compute

$P_a(x)$ we can also compute

$P_a(z_1),P_a(z_2)$.
We also know

$Z_H(x)$, so we can compute

$Z_H(z_1),Z_H(z_2)$.
So we have:

$$\begin{gathered} \frac{Q(z_1)-P(z_1)}{Z_H(z_1)}=b_0+b_1{z}_1 \\ \frac{Q(z_2)-P(z_2)}{Z_H(z_2)}=b_0+b_1{z}_2 \end{gathered}$$

Note that we now have two linear equations with two unknowns

$b_0,b_1$.
We can easily compute them.

Reconstructing

$Q(x)$

Looking at the

$Q(x)$ coeffients (for every polynomial denote its coeffients with the corresponding small letter):

$$\begin{gathered} Q(x)=P_a(x)+(b_0+b_{1}x)\cdot Z_H(x) \\ {q}_0+q_{1}x+\dots +q_n{x}^n+q_{n+1}{x}^{n+1}=(p_0+p_1{x}_1+\dots +p_{n-1}{x}^{n-1})+b_0{x}^n+b_1{x}^{n+1}-b_0-b_{1}x \end{gathered}$$
Let's reorganize the coeffients a bit:

$$q_0+q_1{x}_1+\dots +q_n{x}^n+q_{n+1}{x}^{n+1}=(p_0-b_0)+(p_1-b_1)x+\dots +p_{n-1}{x}^{n-1}+b_0{x}^n+b_1{x}^{n+1}$$

If 2 polymoials are equal, then so are their coeffients:

$$\begin{gathered} q_0=p_0-b_0 \\ {q}_1=p_1-b_1 \\ \mathrm{\forall }2\le i\le n-1,q_i=p_i \\ {q}_n=b_0 \\ {q}_{n+1}=b_1 \end{gathered}$$
All

$p_i,b_0,b_1$ are known, therefore we can compute

$Q(x)$.

All that's left to do is to compute

$comm(Q(x))$ and check if what we got is the same commitment as we have in the given transaction.
Since we know one of the accounts were used to create the given commitment, by iterating over all of them we must find one that satisfies the commitment.
The probability of the commitment being equal by chance is extremely low and therefore if the commitment is equal, we assume that the account used is indeed the recipient of the transaction.

Now In Code

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

    let (setup, accts, cha_1, cha_2, commt, opn_1, opn_2) = read_cha_from_file();

    let mut solution_commitment = G1Affine::zero();
    let number_of_accts = 1000usize;
    let domain: GeneralEvaluationDomain<Fr> =
        GeneralEvaluationDomain::new(number_of_accts + 2).unwrap();

    // Solution:
    // To find the right account we iterated over all accts, we then saw that accts[535] solves it!
    for evals_p in accts.to_vec() {
        // We compute P_a(x)
        let p = DensePolynomial::from_coefficients_vec(domain.ifft(&evals_p));
        
        // Evaluate it at z_1,z_2
        let p_cha_1: Fr = p.evaluate(&cha_1);
        let p_cha_2: Fr = p.evaluate(&cha_2);
        
        // Here we just set up the 2 equations with 2 unknowns
        let e_cha_1 = opn_1 - p_cha_1;
        let e_cha_2 = opn_2 - p_cha_2;
        const N: u64 = 1024u64;
        
        // We compute b_0, b_1
        let b_1 = ((e_cha_1 / (cha_1.pow(&[N]) - Fr::from(1)))
            - (e_cha_2 / (cha_2.pow(&[N]) - Fr::from(1))))
            / (cha_1 - cha_2);
        let b_0 = (e_cha_1 / (cha_1.pow(&[N]) - Fr::from(1))) - (b_1 * cha_1);

        // We set Q(x) = P(x) since most of the coeffients are the same
        let mut q = vec![Fr::from(0); 1026];
        p.coeffs
            .iter()
            .enumerate()
            .for_each(|(idx, f)| q[idx] = f.clone());
        
        // We compute q_0,q_1,q_1024,q_1025
        q[0] -= b_0;           // q[0] = p[0] - b_0
        q[1] -= b_1;           // q[1] = p[1] - b_1
        q[1024] = b_0.clone();
        q[1025] = b_1.clone();
        
        // We compute comm(Q(x)) and check if it's equal to the given commitment
        let dp = DensePolynomial::from_coefficients_vec(q);
        solution_commitment = kzg_commit(&dp, &setup);
        if (solution_commitment == commt) {
            break;
        }
    }

    // let solution_commitment = kzg_commit(&solution_blinded_acct, &setup);
    assert_eq!(solution_commitment, commt);
}

We run our code and find that accts[535] passes the assertion!
accts[535] is the recipient of the given transaction.
Success!