Quadratic Arithmetic Program (QAP) - Interactive Demo [VN]

Bài viết này là bài viết tiếp theo của bài viết về các kỹ thuật về zk-SNARKs, bạn có thể xem lại lý thuyết về Rank-1 Constraint System (R1CS), tại đây.

Bài viết dựa trên nội dung từ bài viết của Vitalik Buterin với tựa đề “Quadratic Arithmetic Programs: from Zero to Hero“

Ý tưởng chính

Đối với R1CS, chúng ta muốn kiểm chứng \(\mathbf{O}w \stackrel{?}{=}\mathbf{L}w. \mathbf{R}w\). Vấn đề là nếu có \(m\) contraints, nghĩa là mỗi ma trận có \(m\) dòng thì độ phức tạp sẽ tăng lên \(m\) lần. Để tránh việc này, chúng ta sẽ cố gắng làm giảm độ phức tạp từ \(O(m)\) xuống \(O(1)\) bằng cách thay vì tính toán trên ma trận và vector, ta đưa về dạng đa thức trên trường hữu hạn \((\mod p)\) thông qua đa thức nội suy Lagrange, ta đơn giản hóa thành một phương trình đa thức duy nhất.

Tính đồng cấu (homomorphism) giữa phép cộng vector và phép cộng đa thức

Xét hàm số \(f_1(x) = x+2, f_2(x)=x^3\), nếu tính giá trị hàm số tại các điểm: \(1,2,3,4\) ta có \(f_1(1)=3,f_1(2)=4, f_1(3)=5,f_1(4)=6\) và \(f_2(1)=1,f_2(2)=8,f_2(3)=27, f_2(4)=64\).

Ngược lại, \(f_1(x)\) có thể nội suy Lagrange từ các điểm \((1,3),(2,4),(3,5),(4,6)\) và \(f_2(x)\) có thể nội suy từ \((1,1),(2,8),(3,27),(4,64)\). Một cách rút gọn, \(f_1(x) \) nội suy vector \(v_1=[3,4,5,6]\) và \(f_2(x)\) nội suy vector \(v_2=[1,8,27,64]\). Gọi vector \(v=v_1+v_2=[3,4,5,6]+[1,8,27,64] = [4,12,32,70]\). Nếu nội suy Lagrange các giá trị của vector \(v\): \((1,4),(2,12),(3,32),(4,70)\) ta được đa thức \(f(x)=x^3+x+3 = f_1(x)+f_2(x)\), hiển nhiên:

• \(f(1)=f_1(1)+f_2(1)\)

• \(f(2)=f_1(2)+f_2(2)\)

• \(f(3)=f_1(3)+f_2(3)\)

• …

Tóm lại, nếu gọi ánh xạ \(\mathcal L: v \to f\) là phép nội suy Langrange biến vector thành đa thức, ta có:

$$\mathcal L(v_1+v_2) = \mathcal L(v_1) + \mathcal L(v_2)$$

Kiểm tra \(\mathbf Av_1 \stackrel{?}{=} \mathbf Bv_2\)

Giả sử ta có các ma trận

$$\begin{align*} \mathbf{A} = \begin{bmatrix} 4 & 3\\ 4 & 6\\ \end{bmatrix}\\ \mathbf{B} = \begin{bmatrix} 2 & 4 \\ 5 & 5\\ \end{bmatrix} \end{align*}$$

và các vector \(v_1=[2,2], v_2=[3,2]\) và muốn kiểm tra \(\mathbf Av_1 \stackrel{?}{=} \mathbf Bv_2\), ta có thể biểu diễn ma trận \(\mathbf A \) bằng cách tách thành các vector cột \([4,4],[6,3]\) và ma trận \(\mathbf B\) thành \([2,5],[4,5]\). Lúc đó, \(\mathbf Av_1 \stackrel{?}{=} \mathbf Bv_2\) trở thành:

$$\begin{bmatrix} 4 \\ 4 \\ \end{bmatrix}\cdot 2+ \begin{bmatrix} 3 \\ 6 \\ \end{bmatrix}\cdot 2\stackrel{?}{=} \begin{bmatrix} 2 \\ 5 \\ \end{bmatrix}\cdot 3+ \begin{bmatrix} 4 \\ 5 \\ \end{bmatrix}\cdot 2$$

Để tận dụng tính chất đồng cấu, ta biến mỗi vector cột thành một đa thức riêng:

$$\underbrace{ \begin{bmatrix} 4 \\ 4 \\ \end{bmatrix}}{p_1(x)}\cdot 2+ \underbrace{ \begin{bmatrix} 3 \\ 6 \\ \end{bmatrix}}{p_2(x)}\cdot 2\stackrel{?}{=} \underbrace{ \begin{bmatrix} 2 \\ 5 \\ \end{bmatrix}}{q_1(x)}\cdot 3+ \underbrace{ \begin{bmatrix} 4 \\ 5 \\ \end{bmatrix}}{q_2(x)}\cdot 2$$

Lúc này, ta có thể kiểm tra đa thức tương đương thay vì kiểm tra vector:

$$p_1(x) \cdot 2+ p_2(x) \cdot 2 \stackrel{?}= q_1(x) \cdot 3 + q_2(x) \cdot 2$$

Rõ ràng, nếu kiểm tra trên đa thức, ta có thể rút gọn từ \(O(n) \to O(1)\)

Kiểm tra \(\mathbf Ow \stackrel{?}{=} \mathbf Lw \cdot \mathbf Rw\)

Để kiểm tra \(\mathbf Ow \stackrel{?}{=} \mathbf Lw \cdot \mathbf Rw\), ta áp dụng phương pháp trên.

• Gọi \(l_1(x),l_2(x),\dots,l_n(x)\) là các đa thức nội suy từ các vector cột của \(\mathbf L\)

• Gọi \(r_1(x),r_2(x),\dots,r_n(x)\) là các đa thức nội suy từ các vector cột của \(\mathbf R\)

• Gọi \(o_1(x),o_2(x),\dots,o_n(x)\) là các đa thức nội suy từ các vector cột của \( \mathbf O\)

Với \(w = [w_1, w_2,\dots,w_n]\), ta có:

$$\begin{align*} \mathbf Ow&\to\begin{bmatrix} o_1(x) & o_2(x) & \dots & o_n(x) \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_4 \end{bmatrix}\\ &=w_1o_1(x) + w_2o_2(x) + \dots + w_no_n(x)\\ &=\sum_{i=1}^n w_io_i(x) \end{align*}$$

Tương tự \(\mathbf Rw \to \sum_{i=1}^n w_ir_i(x), \mathbf Lw \to \sum_{i=1}^n w_il_i(x)\).

Như vậy, mỗi thành phần \(\mathbf Ow,\mathbf Lw, \mathbf Rw\) đang được biểu diễn dưới dạng tổng các đa thức nhỏ hơn, cà các tổng này lại biến thành một đa thức mới. Để cho gọn, ta có thể biểu diễn:

• \(\mathbf Ow \to \sum_{i=1}^n w_io_i(x) = o(w)\)

• \(\mathbf Lw \to \sum_{i=1}^n w_il_i(x)= l(x)\)

• \(\mathbf Rw \to \sum_{i=1}^n w_ir_i(x)=r(x)\)

Vì các đa thức cột của các ma trận trên đều là nội suy Lagrange, và áp dụng lại tính chất đồng cấu ở trên \(\mathcal L(v_1+v_2) = \mathcal L(v_1) + \mathcal L(v_2)\) ta có thể viết lại tính toán như sau:

• \(o(w) = \mathcal L(\mathbf Ow)\)

• \(l(w) = \mathcal L(\mathbf Lw)\)

• \(r(w) = \mathcal L(\mathbf Rw)\)

Và cuối cùng, biểu thức cần kiểm tra sẽ như sau:

$$o(x) \stackrel{?}{=} l(x)r(x)$$

Có một vấn đề xảy ra ở đây, đó là đa thức vế trái và vế phải không cùng bậc vì \(o(x)\)có bậc \(n-1\), còn \(l(x)r(x)\) lại có bậc \(2(n-1)\). Tuy nhiên, vì ta đã dùng phương pháp nội suy Lagrange nên đẳng thức trên sẽ thỏa với các giá trị nội suy \(1,2,\dots,n\) hay nói cách khác:

$$((1, o(1)), (2, o(2)), …, (n, o(n))) = ((1, l(1)r(1)), (2, l(2)r(2)), …, (n, l(n)r(n)))$$

Dù cho \(o(x)=l(x)r(x)\) không luôn đúng.

Chúng ta tạm nghỉ chút xíu ở đây đã, sợ rằng nếu đi quá xa các bạn sẽ quên mất những chi tiết ban đầu.

Nội suy các đa thức cột của \(\mathbf{L,R,O}\) cụ thể là gì?

Quay lại vấn đề đầu tiên, mình đã nhắc rất nhiều về nội suy Lagrange cho các đa thức cột. Vậy cụ thể là gì? Để dễ hình dung, mình sẽ lấy ví dụ ngay trong bài viết của Vitalik để các bạn dễ theo dõi.

Theo hình trong bài viết, ma trận \(\mathbf A\) sẽ được tách thành các 6 vector cột theo như phương pháp đã đề cập trên phần trên:

$$\mathbf A \to \begin{bmatrix} 0 \\ 0 \\ 0 \\ 5 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$

Đối với từng vector cột này, ta sẽ thực hiện nội suy Lagrange cho các điểm \(1,2,\dots, n\) với \(n \) là số hàng hay số phần tử của vector. Ví dụ như vector đầu tiên \([0,0,0,5]\), \(n=4\) ta sẽ thực hiện nội suy đa thức bậc \(n-1 = 3\) thông qua các điểm: \((1,0),(2,0),(3,0),(4,5)\)

Và nếu như bạn tính toán đúng, đa thức này trên trường số thực sẽ là: \(p(x) = \displaystyle \frac 5 6 x^3 - 5x^2+\frac {55} 6x - 5 \to [\frac 5 6, -5, \frac {55} 6, -5]\), như trong bài viết của Vitalik, các số bị đảo thứ tự là \([-5,9.166,-5,0.833]\).

Nếu như bạn tính toán trên trường số nguyên tố hữu hạn, các phép trừ và phép chia sẽ được thay thế bởi các phép tính với phần tử nghịch đảo. Mình thử tính với \(\mathbb F_p, p = 47\) và nhận được đa thức tương ứng là \(p(x) = 40x^3 + 42x^2+17x+42\)

Nếu như bạn lần lượt thực hiện nội suy cho tất cả các vector cột, bạn sẽ nhận được một tập hợp \(n\) đa thức ứng với \(n\) vector.

Tiếp tục quay lại với \(\mathbf Ow \stackrel{?}{=} \mathbf Lw \cdot \mathbf Rw\)

Ở trên, ta đã có: \(\mathcal L (\mathbf Ow) = o(x) = \sum_{i=1}^no_i(x)w_i\), với \(w=[w_1,w_2,\dots,w_n]\) là witness vector, và cũng đã biết cách nội suy cho từng vector cột \(o_i(x)\), như vậy để tính \(o(x)\), đơn giản là ta có thể tính theo công thức lấy lần lượt từng đa thức \(o_i(x)\) đem nhân với từng phần từ \(w_i\).

Áp dụng tương tự ta cũng có thể tính được \(l(x),r(x)\). Lúc này, ta tính được mối tương quan của \(o(x)\) và \(l(x).r(x)\) để xem xét \(o(x) \stackrel{?}{=}l(x)r(x)\).

Như đã đề cập \(l(x)r(x)\) có bậc cao hơn bậc của \(o(x)\) nên ta có \(l(x)r(x)=o(x)+b(x) \stackrel{(1)}{}\).

Tiếp theo, như đã giả định, \(l(x)r(x) = o(x)\) tại mọi điểm \(x=1,2,\dots,n\), do đó: \(b(x) = 0, \forall x=\{1,2\dots,n\} \stackrel{(2)}{}\)

Gọi \(t(x)= (x-1)(x-2)\dots(x-n)\), Từ \(\stackrel{(1)}{}\), \(\stackrel{(2)}{}\) ta suy ra \(b(x)\) phải chia hết cho \(t(x)\) hay nói cách khác: \(b(x) = t(x)h(x)\).

Vậy

$$l(x)r(x)=o(x)+h(x)t(x) \implies h(x) = \frac{l(x)r(x)-o(x)}{t(x)}$$

Để ý là \(h(x)\) sẽ chỉ tồn tại nếu như \(w\) hợp lệ, nếu không, phép chia \(\displaystyle h(x) = \frac{l(x)r(x)-o(x)}{t(x)}\) sẽ có dư.

Bằng chứng không để lộ tri thức ngắn gọn (succint zkp) với QAP

Verifier gửi một giá trị challenge ngẫu nhiên \(c\) đến prover để kiểm tra witness \(w\). Prover phải trả về \(\mathbf L=l(c),\mathbf R=r(c), \mathbf O = o(c)+h(c)t(c)\)

Verifier kiểm tra \(\mathbf O=\mathbf L \mathbf R\) để chấp nhận witness \(w\) hợp lệ.

Demo

Lưu ý là demo này tính toán trên trường hữu hạn, các đa thức sẽ được thể hiện như vector cho gọn nha!