Rank-1 Constraint System (R1CS) - Interactive Demo

Nếu bạn đang tìm hiểu về cơ chế hoạt động của zk-SNARKs, hẳn là các bạn sẽ bắt gặp một số khái niệm như: Rank-1 Constraint System (R1CS), Quadratic Arithmetic Program (QAP). Bài viết này giúp bạn hình dung chi tiết về cách hoạt động của việc chuyển đổi 1 biểu thức thành dạng R1CS cùng với một demo tương tác. Hy vọng sẽ giúp bạn dễ hình dung vấn đề một cách thấu đáo hơn.

Bài viết này sẽ dựa trên bài viết chính của Vitalik với tựa đề “Quadratic Arithmetic Programs: from Zero to Hero“

Tại sao là R1CS ?

R1CS (Rank-1 Constraint System) là một biểu diễn tiêu chuẩn để mô tả các phép toán đại số phức tạp trong ngữ cảnh của zk-SNARKs. Chúng ta phải chuyển đổi sang dạng R1CS vì một số lý do sau:

• Đầu tiên, zk-SNARKs cần chuyển các phép toán phức tạp thành các ràng buộc toán học dưới dạng $A \times B = C$. R1CS giúp chuyển các tính toán phức tạp thành một hệ thống các ràng buộc tuyến tính mà các thuật toán zk-SNARKs có thể dễ dàng xử lý.

• R1CS là một định dạng tổng quát, có thể biểu diễn bất kỳ phép toán nào (cộng, nhân, lũy thừa, điều kiện, logic). Điều này giúp zk-SNARKs xử lý được nhiều loại vấn đề toán học và chương trình khác nhau. Một chương trình tính toán phức tạp có thể được chuyển thành hàng nghìn ràng buộc R1CS nhưng vẫn giữ được tính chính xác toán học.

• Sau khi có R1CS, hệ thống có thể được chuyển thành một hệ đa thức gọi là Quadratic Arithmetic Program (QAP), đây là bước quan trọng trong zk-SNARKs để tạo và xác minh các chứng minh mật mã.

Ví dụ

Giả sử ta có một function để tính biểu thức , đoạn code tương đương có thể là:

function evaluate(x,y) {
    return x**3 + y + 5;
}

Biểu thức kiểm chứng sẽ có dạng: $z=x^3+y+5$. Biểu thức này sẽ được phân tích thành một hệ các biểu thức ràng buộc đơn giản có dạng tích của 2 thừa số có hạng (rank) không quá 1.

Đó cũng chính là lý do tại sao nó có tên Rank-1 Constraint System. Quay lại với biểu thức trên $z=x^3+x+5$ sẽ được chia nhỏ và biểu diễn thành $m$ các biểu thức ràng buộc:

• Biểu thức ràng buộc (constraint) 1: $z_1 =x \times x$

• Biểu thức ràng buộc 2: $z_2 = z_1 \times x$

• Biểu thức ràng buộc 3: $z_3 =z_2 + y$

• Và ràng buộc cuối cùng: $z = z_3 + 5$

Witness vector

Witness là một bộ giá trị (tuple) có dạng vector $1 \times n$ chứa tất cả các giá trị của biến, hằng số, output, … thỏa mãn tất cả các constraint được sinh ra từ biểu thức ban đầu. Với ví dụ trên, witness vector có dạng là một bộ các giá trị $[\text{constant = 1},x,y,z,z_1,z_2,z_3]$. Ví dụ: $x=2, y=3 \Rightarrow z=16$ có một trong các witness vector như sau:

Nếu thay các giá trị của witness vector trên vào các ràng buộc ta thấy toàn bộ các contraint đều thỏa mãn:

• Constraint 1: $z_1=x \times x \rightarrow 4 = 2 \times 2 \quad \checkmark$

• Constraint 2: $z_2=z_1 \times x \rightarrow 8= 4 \times 2 \quad \checkmark$

• Constraint 3: $z_3=z_2 + y \rightarrow 11 = 8 + 3 \quad \checkmark$

• Constraint 4: $z=z_3 + 5 \rightarrow 16 = 11 + 5 \quad \checkmark$

Chuyển R1CS thành dạng ma trận

Dạng cơ sở của các constraint là $C = A \times B$, và chúng ta có $m$ constraint, cùng với một witness vector $w$ có $n$ thành phần, chúng ta sẽ cố gắng đưa về dạng ma trận như sau:

Với $\mathbf {O,L,R}$ là các ma trận kích thước $m \times n$ (có $m$ dòng, $n$ cột):

• $\mathbf O$ là ma trận biểu diễn các biến output

• $\mathbf L$ là ma trận biểu diễn các biến vế trái

• $\mathbf R$ là ma trận biểu diễn các biến vế phải

Hãy xem một ví dụ: $z = a \times b$, witness vector $w = [\text{constant = }1,a=3,b=11,z=33]$. Với trường hợp này, chỉ có 1 constraint, do đó, các ma trận $\mathbf {O,L,R}$ chỉ có 1 dòng. Các ma trận này sẽ có dạng như sau:

Cách thiết lập các giá trị của $\mathbf {O,L,R}$

1. Trường hợp constraint là phép nhân hai biến $z = a \times b$

Để ý rằng ta có thứ tự cách biến tuần tự là $w = [\text{constant = }1,a,b,z]$. Ở đây, mỗi phần tử của ma trận thể hiện sự hiện diện của một biến ở vị trí tương ứng trong constraint ấy. Đối với constraint $\underbrace{z}_{\mathbf O}=\underbrace{a}_{\mathbf L} \times \underbrace{b}_{\mathbf R}$ thì ta có:

• $\mathbf O = [0,0,0,1]$ đại diện cho sự hiện diện của biến $z$ ở vị trí cột 4

• $\mathbf L = [0,1,0,0]$ đại diện cho sự hiện diện của biến ở $a$ vị trí cột 2

• $\mathbf R = [0,0,1,0]$ đại diện cho sự hiện diện của biến $b$ ở vị trí cột 3

💡 Để ý rằng cột thứ nhất (constant) luôn được set giá trị bằng 1, và sẽ được dùng trong các trường hợp với contraints phức tạp hơn.

2. Trường hợp constraint chứa constant $z = a \times [\text{constant}]$ hoặc $z=[\text{constant}] \times a$

Lúc này, cột thứ nhất sẽ được set bằng giá trị constant.

Ví dụ 1: với $z = x \times3$,$w=[1,a,z]$ thì $\mathbf O = [0, 0, 1], \mathbf L = [0, 1, 0], \mathbf R = [3, 0, 0]$

Ví dụ 2: với $z=3 \times x$, $w=[1,a,z]$ thì $\mathbf O = [0, 0, 1], \mathbf L = [3, 0, 0], \mathbf R = [0, 1, 0]$

3. Trường hợp constraint là phép cộng $z=a+b$

Lúc này, ta sẽ chuyển về dạng $z=a+b \Rightarrow z=(a+b)\times 1$

Lúc đó, với $w = [1,a,b,z]$ thì $\mathbf O = [0, 0, 0, 1], \mathbf L = [0, 1, 1, 0], \mathbf R = [1, 0, 0,0]$

4. Trường hợp rút gọn

Thực ra, các trường hợp đã nếu trên là các trường hợp constraint đơn giản. Trong thực tế, một constraint miễn là thỏa tiêu chí:

• Có dạng $C=A \times B$

• Tất cả các thành phần đều có bậc của biến không quá 1

Ví dụ:

• $z = a+b+c$ hoặc $z+b = a+c+x+y$ đều là các constraint rank 1.

• $z=a\times b + c$ không phải constraint rank 1

Giả sử có biểu thức dạng $z+a+2 = b+x+y$ và witness vector $w=[1,a,b,x,y,z]$ thì ta chuyển đổi thành dạng $z+a+2 = (b+x+y)\times 1$ và áp dụng tương tự phương pháp như trên để có:

• Ma trận $\mathbf O = [2,1,0,0,0,1]$

• Ma trận $\mathbf L = [0,0,1,1,1,0]$

• Ma trận $\mathbf R = [1,0,0,0,0,0]$

Các ma trận $\mathbf {O,L,R}$ cho nhiều constraint

Quay lại ví dụ ban đầu $z=x^3+x+5$ với các constraint

Và với witness vector $w = [1,x,z_1,z_2,z_3, z]$ tương ứng, các ma trận $\mathbf {O,L,R}$ sẽ có nhiều dòng, mỗi dòng biểu diễn cho một constraint tương ứng:

Demo

Đây là một demo đơn giản để mô tả việc chuyển một biểu thức thành dạng R1CS:

• Các constraints sinh ra có thể là chưa tối ưu

• Chỉ cho phép các phép tính: lũy thừa (^), phép nhân (*), phép cộng (+). Các phép tính trừ và chia sẽ được hiểu là phép nhân và phép cộng với nghịch đảo trên trường hữu hạn