Chương trình số học bậc hai: Về luận chứng của chứng minh không kiến thức

• tác giả: Vitalik Buterin *

• tiêu đề gốc: 《Quadratic Arithmetic Programs: from Zero to Hero 》

• thời gian xuất bản: ngày 10 tháng 12 năm 2016 *

Gần đây, mọi người rất quan tâm đến công nghệ đứng sau zk-SNARKs (bằng chứng không kiến thức), và ngày càng nhiều người cố gắng vén bức màn bí ẩn của những gì nhiều người gọi là "toán học mặt trăng", vì họ cho rằng độ phức tạp của nó rất khó hiểu. Việc hiểu zk-SNARKs thực sự khá thách thức, đặc biệt là do có quá nhiều bộ phận di động cần được lắp ráp để hệ thống hoạt động, nhưng nếu chúng ta phân tích công nghệ này từng phần một, thì việc hiểu sẽ trở nên dễ dàng hơn.

Mục đích của bài viết này không phải là để giới thiệu đầy đủ về zk-SNARKs, mà giả định rằng bạn có kiến thức nền tảng sau:

1- Bạn biết về zk-SNARKs và nguyên lý tổng quát của nó;

2- Bạn có đủ kiến thức toán học để hiểu một số kiến thức đa thức cơ bản. (Ví dụ: nếu P(x) + Q(x) = (P + Q)(x), P và Q đại diện cho đa thức, nếu bạn đã rất quen thuộc với cách diễn đạt đa thức như vậy, điều đó có nghĩa là bạn đủ điều kiện để tiếp tục đọc).

• Sơ đồ kiến thức zk-SNARK, do Eran Tromer vẽ *

Như trong hình trên, chúng ta có thể chia bằng chứng không kiến thức thành hai giai đoạn từ trên xuống dưới. Đầu tiên, zk-SNARK không thể được áp dụng trực tiếp cho bất kỳ vấn đề tính toán nào; ngược lại, bạn phải chuyển đổi vấn đề thành "hình thức" đúng để hoạt động. Hình thức này được gọi là "chương trình số học bậc hai" (QAP), việc chuyển đổi mã của hàm thành các mã này là rất quan trọng. Cùng với quá trình chuyển đổi mã hàm thành QAP, còn có một quá trình khác diễn ra, để nếu có đầu vào cho mã, có thể tạo ra giải pháp tương ứng (đôi khi được gọi là "chứng cứ" của QAP). Đây là nội dung mà bài viết này cần đề cập.

Sau đó, còn có một quá trình khá phức tạp khác để tạo ra "bằng chứng không kiến thức" thực tế cho QAP này, và một quá trình riêng biệt để xác minh chứng cứ mà người khác gửi cho bạn, nhưng những chi tiết này vượt quá phạm vi của bài viết này.

Trong ví dụ dưới đây, chúng ta sẽ chọn một vấn đề rất đơn giản:

Tìm nghiệm của phương trình bậc ba: x**3 + x + 5 == 35 (gợi ý: câu trả lời là 3).

Vấn đề này rất đơn giản, nhưng quan trọng là bạn có thể thấy tất cả các chức năng hoạt động như thế nào từ trường hợp này.

Mô tả phương trình trên bằng ngôn ngữ lập trình như sau:

def qeval(x):
y = x**3
return x + y + 5
Ngôn ngữ lập trình đơn giản mà chúng tôi sử dụng ở đây hỗ trợ các phép toán số học cơ bản (+, -, *, /), lũy thừa đồng nhất (x7, nhưng không phải x*y) và gán biến, đủ mạnh để lý thuyết có thể thực hiện bất kỳ phép tính nào (miễn là số lượng bước tính toán là hữu hạn; không cho phép vòng lặp). Lưu ý rằng phép toán mô đun (%) và các toán tử so sánh (<, >, ≤, ≥) không được hỗ trợ, vì không có cách hợp lệ nào để thực hiện mô đun hoặc so sánh trực tiếp các thuật toán nhóm vòng hạn chế (cảm ơn; nếu có bất kỳ cách nào để làm điều này, thì tốc độ phá vỡ mã hóa đường cong elip sẽ vượt qua "tìm kiếm nhị phân" và "định lý dư Trung Quốc").

Bạn có thể mở rộng ngôn ngữ bằng cách phân tích bit để bao gồm mô đun và so sánh, (ví dụ: 13 = 2**3 + 2**2 + 1 = 8 + 4 + 1) như là đầu vào phụ, chứng minh tính đúng đắn của các phân tích này và thực hiện các phép toán toán học trong mạch nhị phân; trong các thuật toán trên trường hữu hạn, việc thực hiện kiểm tra đẳng thức (==) cũng khả thi, thực tế dễ hơn một chút, nhưng chúng tôi sẽ không thảo luận về hai chi tiết này ngay bây giờ. Chúng tôi có thể mở rộng ngôn ngữ để hỗ trợ các câu điều kiện (ví dụ: chuyển đổi câu lệnh: if x < 5: y = 7; else: y = 9; thành dạng số học: y = 7 * (x < 5) + 9 * (x >= 5);) nhưng hãy lưu ý rằng cả hai "đường đi" của điều kiện đều cần phải thực hiện, nếu bạn có nhiều điều kiện lồng nhau, điều này sẽ dẫn đến chi phí lớn.

Bây giờ, hãy để chúng ta trải qua quá trình này từng bước một. Nếu bạn muốn tự làm bất kỳ mã nào, tôi đã thực hiện một đoạn mã bằng Python ở đây (chỉ dành cho mục đích giáo dục; chưa sẵn sàng để tạo QAP cho zk-SNARK trong thế giới thực!)

Bước 1: Phẳng hóa

Bước đầu tiên là một quá trình "phẳng hóa", chúng ta phân tích mã gốc (có thể chứa các câu lệnh và biểu thức phức tạp tùy ý) thành các biểu thức đơn giản nhất, có hai dạng:

1- x = y (y có thể là biến hoặc số)
2- x = y(op)z (op có thể là +, -, *, /, y và z có thể là biến, số hoặc biểu thức con).

Bạn có thể xem những diễn đạt này như là các cổng logic trong mạch. Kết quả của quá trình phẳng hóa biểu thức x**3 + x + 5 như sau:

sym1 = x * x y = sym1 * x // tương đương với việc thực hiện hàm lũy thừa y = x**3
sym2 = y + x ~out = sym2 + 5

Bạn có thể coi mỗi dòng khai báo ở trên là một cổng logic trong mạch, so với mã gốc, chúng ta đã giới thiệu hai biến trung gian sym1 và sym2, cùng với một biến dư thừa biểu thị đầu ra ~out, không khó để thấy rằng chuỗi khai báo sau khi "phẳng hóa" và mã gốc là tương đương.

Bước 2: Chuyển đổi sang R1CS

Bây giờ, chúng ta sẽ chuyển đổi nó thành một cái gọi là R1CS (Hệ thống ràng buộc Rand-1). R1CS là một chuỗi gồm ba vector (a, b, c), nghiệm của R1CS là một vector s, trong đó s phải thỏa mãn phương trình

s . a * s . b - s . c = 0

trong đó . đại diện cho phép toán tích vô hướng.

Ví dụ, dưới đây là một R1CS thỏa mãn:

a = (5,0,0,0,0,1),
b = (1,0,0,0,0,0),
c = (0,0,1,0,0,0),
s = (1,3,35,9,27,30),

• (Chú thích của người dịch: 35 đầu tiên = 1*5 + 30*1, 35 thứ hai = 35 * 1) *

Ví dụ trên chỉ là một ràng buộc, tiếp theo chúng ta sẽ chuyển đổi mỗi cổng logic (tức là mỗi câu lệnh khai báo sau khi "phẳng hóa") thành một ràng buộc (tức là một bộ ba vector (a, b, c)), phương pháp chuyển đổi phụ thuộc vào phép toán của câu lệnh là gì (+, -, *, /) và tham số của câu lệnh là biến hay số. Trong ví dụ của chúng ta, ngoài năm biến ('x', '~out', 'sym1', 'y', 'sym2') sau khi "phẳng hóa", còn cần giới thiệu một biến dư thừa ~one ở vị trí thành phần đầu tiên để biểu thị số 1, trong hệ thống của chúng ta, một vector tương ứng với 6 thành phần là (có thể là thứ tự khác, miễn là tương ứng):

'~one', 'x', '~out', 'sym1', 'y', 'sym2'

** Cổng đầu tiên **

sym1 = x * x, tức là x*x - sym1 = 0

Chúng ta có thể có được bộ vector như sau:

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

Nếu thành phần thứ hai của vector nghiệm s là 3, thành phần thứ tư là 9, bất kể các thành phần khác là bao nhiêu, đều thỏa mãn, vì: a = 3 * 1, b = 3 * 1, c = 9 * 1, tức là a * b = c. Tương tự, nếu thành phần thứ hai của s là 7, thành phần thứ tư là 49, cũng sẽ được kiểm tra, lần kiểm tra đầu tiên chỉ để xác minh tính nhất quán giữa đầu vào và đầu ra của cổng đầu tiên.

** Cổng thứ hai **

y = sym1 * x, tức là sym1 * x - y = 0
Có thể có được bộ vector như sau:

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

** Cổng thứ ba **

sym2 = y + x, cổng cộng cần chuyển đổi thành: (x + y) * 1 - sym2 = 0
Có được bộ vector như sau:

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0] tương ứng với hằng số 1, dùng vị trí ~one
c = [0, 0, 0, 0, 0, 1]

** Cổng thứ tư **

~out = sym2 + 5, tức là (sym2 + 5) * 1 - ~out = 0
Có được bộ vector như sau:

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

Bây giờ, chúng ta giả sử x = 3, theo cổng đầu tiên, có được sym1 = 9, theo cổng thứ hai có được y = 27, theo cổng thứ ba, có được sym2 = 30, theo cổng thứ tư có được ~out = 35, do đó, theo: '~one', 'x', '~out', 'sym1', 'y', 'sym2', có thể có được:

s = [1, 3, 35, 9, 27, 30]

Nếu giả sử x khác, có thể có được s khác nhau, nhưng tất cả s đều có thể được sử dụng để xác minh (a, b, c)

Bây giờ chúng ta đã có bốn ràng buộc R1CS, R1CS hoàn chỉnh như sau:

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]

B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

Bước 3: Từ R1CS đến QAP

Bước tiếp theo là chuyển đổi R1CS này thành dạng QAP, nó thực hiện cùng một logic, chỉ sử dụng đa thức thay vì tích vô hướng. Chúng tôi thực hiện như sau: từ 4 bộ ba vector có độ dài 6 đến 6 bộ đa thức có bậc 3, tại mỗi tọa độ x, đa thức đại diện cho một điều kiện ràng buộc. Nói cách khác, nếu chúng tôi tìm ra đa thức tại x=1, chúng tôi sẽ có được bộ vector đầu tiên, nếu chúng tôi tìm ra đa thức tại x=2, chúng tôi sẽ có được bộ vector thứ hai, và cứ như vậy.

Chúng tôi có thể sử dụng nội suy Lagrange để thực hiện chuyển đổi này. Vấn đề mà phương pháp nội suy Lagrange giải quyết là: nếu bạn có một tập hợp các điểm (tức là các cặp tọa độ (x, y)), sau đó thực hiện nội suy Lagrange trên các điểm này để có được một đa thức đi qua tất cả các điểm đó. Chúng tôi phân tích vấn đề: đối với mỗi tọa độ x, chúng tôi tạo ra một đa thức, tọa độ y cần thiết của tọa độ x và tọa độ y 0 tại tất cả các tọa độ x khác mà chúng tôi quan tâm, sau đó cho phép kết quả cuối cùng chúng tôi cộng tất cả các đa thức lại với nhau.

Hãy làm một ví dụ. Giả sử chúng tôi muốn một đa thức đi qua (1,3), (2,2) và (3,4). Đầu tiên, chúng tôi làm một đa thức đi qua (1,3), (2,0) và (3,0). Thực tế cho thấy, một đa thức, "kéo dài" x = 1 và 0 tại các điểm quan tâm khác là rất dễ dàng, chúng tôi chỉ cần thực hiện đa thức sau:

y = (x - 2) * (x - 3)

Như trong hình dưới đây:

Sau đó, "kéo dài" theo hướng trục y, sử dụng phương trình sau:

y = (x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

Sau khi sắp xếp lại, có được:

y = 1.5 * x**2 - 7.5 * x + 9

Thỏa mãn đồng thời đi qua ba điểm (1,3), (2,0) và (3,0), như trong hình dưới đây:

Thay (2,2) và (3,4) vào phương trình trên, có thể có được:

y = 1.5 * x**2 - 5.5 * x + 7

Đó chính là phương trình tọa độ mà chúng tôi muốn. Thuật toán trên cần O(n3) thời gian, vì có n điểm, mỗi điểm cần O(n2) thời gian để nhân đa thức. Suy nghĩ một chút, điều này có thể giảm xuống O(n**2) thời gian, suy nghĩ thêm một chút, sử dụng thuật toán biến đổi Fourier nhanh, v.v., nó có thể giảm thêm nữa------ đây là một tối ưu hóa quan trọng, khi các hàm thường được sử dụng trong zk-spuks thường có hàng ngàn cổng.

Tại đây, tôi sẽ trực tiếp đưa ra công thức nội suy Lagrange:

Đối với n điểm (x1,y1), (x2,y2), (x3,y3),…,(xn,yn), đa thức bậc n-1 là:

Ví dụ trong trường hợp trên, đa thức đi qua các điểm (1,3), (2,2) và (3,4) là:

Sau khi học cách sử dụng công thức này, chúng ta có thể tiếp tục các bước của mình. Bây giờ chúng ta cần chuyển đổi bốn bộ ba vector có độ dài 6 thành sáu nhóm đa thức, mỗi nhóm đa thức bao gồm ba đa thức bậc ba, chúng tôi sẽ đánh giá các điều kiện khác nhau tại mỗi điểm x, ở đây, chúng tôi có tổng cộng bốn điều kiện, vì vậy chúng tôi sẽ lần lượt đánh giá các vector nhóm tại x = 1, 2, 3, 4.

Bây giờ chúng tôi sử dụng công thức nội suy Lagrange để chuyển đổi R1CS thành dạng QAP. Chúng tôi trước tiên tìm ra đa thức tương ứng với giá trị đầu tiên của mỗi vector a trong bốn điều kiện, tức là sử dụng định lý nội suy Lagrange để tìm đa thức đi qua các điểm (1,0), (2,0), (3,0), (4,0), tương tự, chúng tôi có thể tìm ra đa thức tương ứng với giá trị thứ i của mỗi vector trong bốn điều kiện còn lại.

Tại đây, tôi sẽ đưa ra câu trả lời ngay:

Đa thức A
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

Đa thức B
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

Đa thức C
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

Các hệ số này được sắp xếp theo thứ tự tăng dần, ví dụ, đa thức đầu tiên ở trên là 0.833 * x**3 - 5 * x**2 + 9.166 * x - 5. Nếu chúng tôi thay x=1 vào mười tám đa thức trên, có thể có được ba vector của ràng buộc đầu tiên

(0, 1, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0),
…
Tương tự, chúng tôi sẽ thay x = 2, 3, 4 vào các đa thức trên có thể phục hồi phần còn lại của R1CS.

Bước 4: Kiểm tra QAP

Bằng cách chuyển đổi R1CS thành QAP, chúng tôi có thể kiểm tra tất cả các ràng buộc cùng một lúc thông qua phép toán tích của các đa thức thay vì kiểm tra từng ràng buộc một như R1CS. Như trong hình dưới đây:

Bởi vì trong trường hợp này, kiểm tra tích vô hướng là một chuỗi các phép cộng và nhân của các đa thức, kết quả tự nó là một đa thức. Nếu đa thức nhận được, tại mỗi tọa độ x mà chúng tôi đã sử dụng để biểu thị các cổng logic, có giá trị bằng 0, thì điều đó có nghĩa là tất cả các kiểm tra đều đã vượt qua; nếu đa thức kết quả có ít nhất một giá trị khác không, thì điều đó có nghĩa là giá trị vào ra của cổng logic không nhất quán.

Cần lưu ý rằng, đa thức nhận được không nhất thiết phải bằng 0, thực tế trong hầu hết các trường hợp là không; nó có thể có bất kỳ hành vi nào tại các điểm không thỏa mãn bất kỳ cổng logic nào, miễn là tại tất cả các điểm thỏa mãn một số cổng, kết quả là 0. Để xác minh tính đúng đắn, chúng tôi không tính toán đa thức t = A . s * B . s - C . s tại mỗi điểm tương ứng với một cổng; ngược lại, chúng tôi chia t cho một đa thức khác Z, sau đó kiểm tra xem Z có chia đều t hay không, tức là phép chia t / Z không có dư.

Z được định nghĩa là (x - 1) * (x - 2) * (x - 3)…- đa thức đơn giản nhất, bằng 0 tại tất cả các điểm tương ứng với cổng logic này. Đây là một sự thật cơ bản của đại số, bất kỳ đa thức nào bằng 0 tại tất cả các điểm này đều phải là bội số của đa thức nhỏ nhất này, nếu một đa thức là bội số của Z thì giá trị của nó tại bất kỳ điểm nào trong số này đều bằng 0; sự tương đương này làm cho công việc của chúng tôi dễ dàng hơn nhiều.

Bây giờ, hãy để chúng tôi thực hiện kiểm tra tích vô hướng với các đa thức ở trên.

Đầu tiên, chúng tôi có được các đa thức trung gian:

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]
(Chú thích của người dịch: quá trình tính toán trên:
43.0 = -5 * 1 + 8 * 3 + 0 * 35 - 6 * 9 + 4 * 27 - 1 * 30,
-73.333 = 9.166 * 1 - 11.333 * 3 + 0 * 35 + 9.5 * 9 - 7 * 27 + 1.833 * 30,
…
-3 = 3 * 1 - 2 * 3 + 0 * 35 + 0 * 9 + 0 * 27 + 0 * 30
…)

Các đa thức trên qua phép tính: A . s * B . s - C . s cho kết quả:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
(Chú thích của người dịch: quá trình tính toán:
A . s = [43.0, -73.333, 38.5, -5.166] = -5.166 * x3 + 38.5 * x2 - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x3 - 5 * x2 + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x3 - 24.5 * x2 + 71.666 * x - 41.0
A . s * B . s - C . s chính là phép tính của các đa thức trên, sau khi tính toán, theo bậc từ thấp đến cao sắp xếp các hệ số, có được: [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

Nhấp vào đây để xem quá trình tính toán-%5Cleft(2.833x%5E%7B3%7D-24.5x%5E%7B2%7D%2B71.666x-41%5Cright))

Đa thức nhỏ nhất là:

Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)

tức là:

Z = [24, -50, 35, -10, 1]

Quá trình tính toán trên nhấp vào đây để xem%20%5Ccdot%20%5Cleft(x%20-%203%5Cright)%20%5Ccdot%20%5Cleft(x%20-%204%5Cright))

Bây giờ tính toán phép chia đa thức:

h = t / Z = [-3.666, 17.055, -3.444]

h phải là một phép chia hoàn toàn không có dư.

Bạn có thể nhấp vào đây để xác minh%20%5Ccdot%5Cleft(x%20-%203%5Cright)%20%5Ccdot%5Cleft(x%20-%204%5Cright)%5Ccdot%5Cleft(-3.444x%5E%7B2%7D%2B17.055x-3.666%5Cright)).

Chúng ta đã có giải pháp cho QAP. Nếu chúng ta cố gắng giả mạo biến trong R1CS, và R1CS này suy diễn ra giải pháp QAP------ chẳng hạn, đặt số cuối cùng của s là 31 thay vì 30, chúng ta sẽ nhận được một đa thức t không vượt qua kiểm tra (trong trường hợp cụ thể, tại x = 3 = 1 thay vì 0), và sẽ không phải là bội số của Z; ngược lại, phép chia t / Z sẽ cho dư là [-5.0, 8.833, -4.5, 0.666].

Lưu ý rằng, trên chỉ là một ví dụ rất đơn giản; trong thế giới thực, các phép toán cộng, trừ, nhân, chia thường đi kèm với các số không chuẩn, vì vậy tất cả những gì chúng ta biết và yêu thích về các định luật đại số vẫn hữu ích, nhưng tất cả các câu trả lời là một số phần tử------ thường là các số nguyên trong khoảng từ 0 đến n - 1. Ví dụ, nếu n = 13, thì 1 / 2 = 7 (7 * 2 = 1), 3 * 5 = 2, v.v. Sử dụng các thuật toán trên trường hữu hạn đã loại bỏ mối lo ngại về sai số làm tròn và cho phép hệ thống hoạt động tốt với các đường cong elip, điều này cuối cùng làm cho giao thức zk-SNARK trở nên thực sự an toàn.