ZK HACK - Solution 4

Hidden in Plain Sight

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\) of some transaction. 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 = \{\forall 0 \le i \lt n \ |\ \omega^i\}\) s.t. \(\omega^n = 1\) (roots of unity)

The account address is split into 32 bytes - \(a_0, \ldots, a_{31}\). (We then look at the tuples: \((\omega^0, a_0),\ldots,(\omega^{31}, a_{31}),(\omega^{32}, 0),\ldots,(\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\) and \(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_1x)\cdot Z_H(x)\)
Note that since \(Z_H(\omega^i) = 0\) for all \(i\), then \(Q(x)\) evaluates to the same as \(P(x)\) for all \(\omega^i\)
Also note that \(deg(Q(x)) = n + 1\)

Polynomial Commitment

We assume a trusted public setup \(S = \{\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 scalare 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:

\(Q(z_1) = P(z_1) + (b_0 + b_1z_1)\cdot Z_H(z_1)\)
\(Q(z_2) = P(z_2) + (b_0 + b_1z_2)\cdot Z_H(z_2)\)

Note, that for every account \(a\) we can compute \(P_a(x)\), the \(P(x)\) polynomial 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:

\(\frac{Q(z_1) - P(z_1)}{Z_H(z_1)} = b_0 + b_1z_1\)

\(\frac{Q(z_2) - P(z_2)}{Z_H(z_2)} = b_0 + b_1z_2\)

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)\) coefficients (for every polynomial denote its coeffients with the corresponding small letter):

\(Q(x) = P_a(x) + (b_0 + b_1x) \cdot Z_H(x)\)
\(q_0 + q_1x + \ldots + q_{n}x^{n} + q_{n+1}x^{n+1} = (p_0 + p_1x_1+\ldots +p_{n-1}x^{n-1}) + b_0x^n + b_1x^{n+1} - b_0 - b_1x\)

Let's reorganize the coefficients a bit:

\(q_0 + q_1x_1 + \ldots + q_{n}x^{n} + q_{n+1}x^{n+1} = (p_0 - b_0) + (p_1 - b_1)x + \ldots + p_{n-1}x^{n-1} + b_0x^n + b_1x^{n+1}\)

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

\(q_0 = p_0 - b_0\)
\(q_1 = p_1 - b_1\)
\(\forall 2 \le i \le n-1, \ \ q_i = p_i\)
\(q_n = b_0\)
\(q_{n+1} = b_1\)

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

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

Introduction

See puzzle details on Github