Back Solution

by tom marvolo riddle

Sometimes you can say too much.

### Introduction

The winners of the solution write up for the fourth puzzle, Hidden in Plain Sight, created by Anoma, was from the team tom marvolo riddle. The three team members are Matan, Elichai and Shalev.
The background materials for this puzzle are linked below.

## See puzzle details on Github

### 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
- 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))$$

## 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  passes the assertion!  accts is the recipient of the given transaction.
Success!