# PLONK

## What's PLONK?

PLONK, viết tắt của "Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge," là một zero-knowledge proof scheme đa dụng do Ariel Gabizon, Zac Williamson và Oana Ciobotaru phát triển.

## From program to polynomials

### Arithmetic circuit

**Arithmetic circuit** là một mô hình biểu diễn chương trình/toán học dưới dạng **cổng cộng (+)** và **nhân (×)** trên một trường số hữu hạn (finite field).

Nó giống như mạch logic (logic circuit) nhưng thay vì **AND/OR/NOT**, ở đây ta chỉ có **add gate** và **mul gate**.

**Ví dụ**:

Ta có: $b = a^2 + 1$

<center>
<img src="https://hackmd.io/_uploads/HyfGe0Loxe.png" width="30%">
</center>

### Constraint systems

Từ **arithmetic circuit**, ta sinh ra **constraint system** – một tập hợp các phương trình phải thoả mãn nếu mạch chạy đúng.

- Gate constraint: ràng buộc trong từng cổng (gate)
- Copy constraint: ràng buộc giữa các dây (wire)

**Ví dụ:**

- Lấy lại biểu thức trên $b = a^2 + 1$

<center>
<img src="https://hackmd.io/_uploads/ByEL-A8ilg.png" width="50%">
</center>

**Gate constrait:** $\begin{cases}
l_1 * r_1 - o_1 = 0 \\
l_2 - 1 - o_2 = 0
\end{cases}$

**Copy constraint:** $\begin{cases}
l_1 = r_1 = a \\
l_2 = o_1 \\
\end{cases}$

Ta có thể viết dưới dạng tổng quát cho **constraint systems**:

$$
Q_L a + Q_R b + Q_O c + Q_M ab + Q_C = 0
$$

Trong đó, $a, b, c$ lần lượt là **left, right, and output wire** của từng **gate**. Tất cả $Q$ đều là hằng số.

Ví dụ như:

<center>
<img src="https://hackmd.io/_uploads/H18flrdoeg.png" width="70%">
</center>

Từ các phương trình trên $Q$ có thể viết lại dưới dạng vector:

$$
\begin{aligned}
Q_L &= (0, 0, 1, 1) \\
Q_R &= (0, 0, 1, 0) \\
Q_O &= (-1, -1, -1, 0) \\
Q_M &= (1, 1, 0, 0) \\
Q_C &= (0, 0, 0, -30)
\end{aligned}
$$

Và những vector $Q$ này được gọi là **selector** và mã hoá **circuit structure**.

Tương tự, ta cũng có thể viết $a, b, c$ dưới dạng vector

$$
\begin{aligned}
a &= (a_0, a_1, a_2, a_3) \\
b &= (b_0, b_1, b_2, b_3) \\
c &= (c_0, c_1, c_2, c_3) \\
\end{aligned}
$$

Các vector này được gọi là **witness assignments** và biểu diễn toàn bộ giá trị của các **dây (wire)** được suy ra từ đầu vào của người dùng, trong đó một số có thể là **private** và chỉ được biết bởi **prover**.

### Polynomials

Chúng ta có thể biến một vector thành một danh sách các điểm bằng cách dùng chỉ số của nó làm tọa độ *x*.

Ví dụ, $Q_L$ có thể được chuyển thành $(0, 0), (1, 0), (2, 1), (3, 1)$.

Sẽ tồn tại một đa thức bậc 3 duy nhất đi qua các điểm này. Tập $\{0, 1, 2, 3\}$ được gọi là **evaluation domain**.

$Q_L$ đang ở dạng **“evaluation form”**, trong khi dạng **“coefficient form”** của nó có thể thu được bằng cách **nội suy (interpolation)**.

$$Q_L(x) = -\frac{1}{3}x^3 + \frac{1}{2}x^2 - \frac{7}{6}x$$

<center>
<img src="https://hackmd.io/_uploads/BJBucHOoeg.png" width="70%">
</center>

Tương tự, chúng ta có thể chuyển đổi các vector khác thành các đa thức, được tính trên cùng một miền. Hãy định nghĩa $f(x)$ như sau:

$$
f(x) = Q_L(x)a(x) + Q_R(x)b(x) + Q_O(x)c(x) + Q_M(x)a(x)b(x) + Q_C(x)
$$

$f(0)$ có giá trị bằng 0, vì:

$$
\begin{aligned}
f(0) &= Q_L(0)a(0) + Q_R(0)b(0) + Q_O(0)c(0) + Q_M(0)a(0)b(0) + Q_C(0) \\
&= (0)a_0 + (0)b_0 + (-1)c_0 + (1)a_0 b_0 + (0) \\
&= 0
\end{aligned}
$$

Tương tự, bạn có thể tính $f$ tại $1, 2, 3$, và tất cả đều cho kết quả bằng 0.

Mọi ràng buộc trong hình:

<center>
<img src="https://hackmd.io/_uploads/H18flrdoeg.png" width="70%">
</center>

sẽ được thỏa mãn khi và chỉ khi điều kiện sau đúng:

$$
f(x) = 0, \quad \forall x \in \{0, 1, 2, 3\}
$$

---

Chúng ta gom tất cả các ràng buộc vào một đa thức duy nhất $f(x)$, có thể biểu diễn như sau:

$$
f(x) = Z(x)H(x)
$$

trong đó

$$
Z(x) = x(x-1)(x-2)(x-3)
$$

---

**Giải thích:**
- Các điểm $0,1,2,3$ đều là nghiệm (roots) của $f(x)$.
- Do đó, tồn tại một đa thức $H(x)$ sao cho $f(x)$ chia hết cho $Z(x)$ mà không dư.
- $Z(x)$ được gọi là *vanishing polynomial* , còn $H(x)$ gọi là *quotient polynomial*.

---

Định nghĩa thêm một đa thức $g(x)$:

$$
g(x) = f(x) - Z(x)H(x)
$$

Nếu $f(x) = Z(x)H(x)$ thực sự đúng, thì ta có:

$$
g(x) = 0
$$

tại mọi điểm, tức là $g(x)$ chính là *zero polynomial*.

### Định lý Schwartz–Zippel

#### Phát biểu
Cho đa thức không đồng không $P(x_1, \ldots, x_n)$ trên trường $\mathbb{F}$, với bậc $\deg(P) = d$.
Xét một tập hữu hạn $S \subseteq \mathbb{F}$. Nếu chọn ngẫu nhiên một điểm $(a_1, \ldots, a_n) \in S^n$, thì ta có:

$$
\Pr[P(a_1, \ldots, a_n) = 0] \leq \frac{d}{|S|}
$$

với điều kiện $P \not\equiv 0$ (không phải đa thức đồng không).

---

#### Giải thích dễ hiểu
- Một đa thức bậc $d$ có nhiều nhất $d$ nghiệm.
- Nếu ta chọn giá trị ngẫu nhiên trong một tập rất lớn (ví dụ $|S| \approx 2^{256})$, thì tỉ lệ $\tfrac{d}{|S|}$ gần như bằng 0.
- Do đó, nếu $P$ cho kết quả bằng 0 tại một điểm ngẫu nhiên, thì gần như chắc chắn rằng $P \equiv 0$.

---

#### Ý nghĩa
- Nếu $P \equiv 0$ thì tất nhiên nó bằng 0 ở mọi điểm.
- Nếu $P \not\equiv 0$, thì xác suất để nó “vô tình” bằng 0 ở một điểm ngẫu nhiên là rất nhỏ $(\le \tfrac{d}{|S|})$.
- Điều này dẫn đến hệ quả quan trọng trong kiểm chứng đa thức:
- Nếu đánh giá hai đa thức tại một điểm ngẫu nhiên và kết quả bằng nhau, thì gần như chắc chắn chúng bằng nhau ở mọi điểm.

## Polynomial commitment scheme