Chương trình số học bậc hai: Luận bàn về bằng chứng không kiến thức
Tuyển chọn TechFlowTuyển chọn TechFlow
Chương trình số học bậc hai: Luận bàn về bằng chứng không kiến thức
Hiểu được zk-SNARKs thực sự khá thách thức, đặc biệt là do hệ thống này có quá nhiều thành phần chuyển động cần phải lắp ráp lại với nhau để hoạt động.
Chuyên sâu báo cáo Web3Tác giả: Vitalik Buterin
Ngày đăng: 10 tháng 12 năm 2016
Gần đây, công nghệ đằng sau zk-SNARKs (bằng chứng không kiến thức) đã thu hút rất nhiều sự quan tâm, và ngày càng có nhiều nỗ lực nhằm vén bức màn bí ẩn của một thứ mà nhiều người gọi là “toán học ngoài hành tinh”, bởi vì mức độ phức tạp của nó được cho là quá khó hiểu.
Việc hiểu zk-SNARKs thực sự khá thách thức, đặc biệt là do hệ thống này có quá nhiều thành phần phải phối hợp chính xác mới hoạt động được. Tuy nhiên, nếu ta phân tích từng mảnh nhỏ của công nghệ này, thì việc hiểu chúng sẽ trở nên dễ dàng hơn.
Mục đích bài viết này không phải để giới thiệu đầy đủ về zk-SNARKs; bài viết giả định bạn đã có những 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 chúng;
2- Bạn có đủ kiến thức toán học để hiểu các khái niệm cơ bản về đa thức (ví dụ như P(x) + Q(x) = (P + Q)(x), trong đó P và Q là các đa thức; nếu bạn đã quen thuộc với cách biểu diễn này, thì bạn đủ điều kiện để tiếp tục đọc).
Sơ đồ kiến thức zk-SNARK, do Eran Tromer vẽ
Như hình trên, 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. Trước hết, zk-SNARK không thể áp dụng trực tiếp vào mọi bài toán tính toán; thay vào đó, bạn phải chuyển đổi bài toán sang đúng "dạng" thao tác. Dạng này được gọi là "chương trình số học bậc hai" (QAP - Quadratic Arithmetic Program), và việc chuyển mã hàm thành dạng này là một bước rất quan trọng. Song song với quá trình chuyển đổi mã hàm sang QAP là một quy trình khác, giúp tạo ra lời giải tương ứng (đôi khi gọi là "nhân chứng" của QAP) nếu có đầu vào cho mã đó. Đây chính là nội dung bài viết này muốn trình bày.
Sau đó còn một quy trình khá phức tạp khác để tạo ra "bằng chứng không kiến thức" thực sự cho QAP này, và một quy trình riêng biệt để kiểm tra bằng chứng mà người khác gửi cho bạn, nhưng những chi tiết đó nằm ngoài phạm vi bài viết này.
Trong ví dụ dưới đây, chúng tôi sẽ chọn một bài toá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 ý: đáp án là 3).
Bài toán này đơn giản, nhưng lại rất quan trọng, vì bạn có thể thấy rõ cách tất cả các chức năng vận hành qua trường hợp này.
Dùng ngôn ngữ lập trình mô tả phương trình trên 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 dùng ở đây hỗ trợ các phép tính cơ bản (+, -, *, /), lũy thừa cố định (x^7, nhưng không phải x*y) và gán biến, đủ mạnh để về mặt lý thuyết có thể thực hiện mọi phép tính (miễn là số bước tính hữu hạn; không cho phép vòng lặp). Lưu ý rằng các phép toán modulo (%) và so sánh (<, >, ≤, ≥) không được hỗ trợ, vì không có cách hiệu quả nào để thực hiện modulo hay so sánh trực tiếp trên nhóm vòng hữu hạn (cảm ơn; nếu có bất kỳ cách nào làm được điều này, thì mật mã đường cong elliptic sẽ bị phá vỡ nhanh hơn cả "tìm kiếm nhị phân" và "định lý số dư Trung Hoa").
Bạn có thể mở rộng ngôn ngữ để hỗ trợ modulo và so sánh thông qua phân tích bit (ví dụ: 13 = 2**3 + 2**2 + 1 = 8+4+1) như đầu vào phụ, chứng minh tính đúng đắn của các phân tích này, rồi thực hiện các phép toán trong mạch nhị phân; việc kiểm tra đẳng thức (==) trong thuật toán trường hữu hạn cũng khả thi, thậm chí còn dễ hơn một chút, nhưng hai chi tiết này chúng tôi sẽ không bàn đến lúc này. Chúng ta có thể mở rộng ngôn ngữ để hỗ trợ câu lệnh đ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)); tuy nhiên cần lưu ý rằng cả hai "nhánh" của điều kiện đều phải được thực thi, và nếu có nhiều điều kiện lồng nhau, điều này sẽ gây ra chi phí lớn.
Bây giờ hãy đi từng bước qua quy trình này. Nếu bạn muốn tự thử code, tôi đã triển khai một đoạn mã bằng Python tại đây (chỉ nhằm mục đích giáo dục; chưa sẵn sàng để tạo QAP cho zk-SNARK thực tế!)
Bước 1: Làm phẳng
Bước đầu tiên là quá trình "làm phẳng", trong đó ta phân rã mã gốc (có thể chứa các biểu thức và câu lệnh phức tạp tùy ý) thành các biểu thức đơn giản nhất, chỉ 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ể coi những biểu thức này như các cổng logic trong mạch. Kết quả làm phẳng biểu thức x**3 + x + 5 như sau:
sym_1 = x * x
y = sym_1 * x // thực hiện hàm mũ y = x**3
sym_2 = y + x
~out = sym_2 + 5
Bạn có thể coi mỗi dòng khai báo trên như một cổng logic trong mạch. So với mã gốc, ở đây ta đưa vào hai biến trung gian sym_1 và sym_2, cùng một biến dư thừa ~out biểu thị đầu ra. Rõ ràng dãy khai báo sau khi "làm phẳng" là tương đương với mã gốc.
Bước 2: Chuyển sang R1CS
Bây giờ, ta sẽ chuyển đổi nó sang một thứ gọi là R1CS (Hệ thống Ràng buộc bậc 1 ngẫu nhiên). R1CS là một dãy gồm ba vector (a, b, c), và lời giải của R1CS là một vector s, sao cho s phải thỏa mãn phương trình:
s . a * s . b - s . c = 0
trong đó . ký hiệu phép nhân vô hướng (tích trong).
Ví dụ, dưới đây là một R1CS hợp lệ:
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),
(Lưu ý 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, ta sẽ chuyển đổi mỗi cổng logic (tức là mỗi khai báo sau khi "làm phẳng") 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 (+,-,*,/) và tham số là biến hay số. Trong ví dụ này, ngoài năm biến sau khi "làm phẳng" ('x', '~out', 'sym_1', 'y', 'sym_2'), ta cần thêm một biến dư thừa ~one ở vị trí thành phần đầu tiên để biểu thị số 1. Đối với hệ thống của chúng ta, sáu thành phần tương ứng với một vector là (có thể theo thứ tự khác, miễn là khớp nhau):
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'
Cổng đầu tiên
sym_1 = x * x, tức là x*x - sym_1 = 0
Ta có được bộ vector sau:
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]
Nếu vector lời giải s có giá trị thứ hai là 3 và giá trị thứ tư là 9, thì biểu thức đúng bất kể các giá trị khác là gì, vì: a = 3 * 1, b = 3 * 1, c = 9 * 1, tức là a * b = c. Tương tự, nếu giá trị thứ hai của s là 7 và giá trị thứ tư là 49, thì cũng vượt qua kiểm tra. Kiểm tra lần đầu tiên chỉ nhằm 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 = sym_1 * x, tức là sym_1 * x - y = 0
Ta có được bộ vector 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
sym_2 = y + x, cổng cộng cần chuyển thành: (x + y) * 1 - sym_2 = 0
Ta có được bộ vector sau:
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0] tương ứng hằng số 1, dùng vị trí ~one
c = [0, 0, 0, 0, 0, 1]
Cổng thứ tư
~out = sym_2 + 5, tức là (sym_2 + 5) * 1 - ~out = 0
Ta có được bộ vector 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ờ, giả sử x = 3, theo cổng đầu tiên, ta có sym_1 = 9, theo cổng thứ hai có y = 27, theo cổng thứ ba có sym_2 = 30, theo cổng thứ tư có ~out = 35. Do đó, theo thứ tự: '~one', 'x', '~out', 'sym_1', 'y', 'sym_2', ta có:
s = [1, 3, 35, 9, 27, 30]
Nếu giả sử x khác nhau, ta sẽ nhận được các s khác nhau, nhưng mọi s đều có thể dùng để kiểm tra (a, b, c)
Giờ ta đã có R1CS gồm bốn ràng buộc, 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 sang QAP
Bước tiếp theo là chuyển đổi R1CS này sang dạng QAP, thực hiện logic hoàn toàn giống nhau nhưng dùng đa thức thay vì tích vô hướng. Ta làm như sau: chuyển từ 4 bộ ba vector dài 6 sang 6 bộ ba đa thức bậc 3, đánh giá đa thức tại mỗi điểm x đại diện cho một ràng buộc. Nói cách khác, nếu ta tính đa thức tại x=1, ta nhận được bộ vector đầu tiên; nếu tại x=2, ta nhận được bộ vector thứ hai, v.v.
Chúng ta có thể dùng nội suy Lagrange để thực hiện phép biến đổi này. Nội suy Lagrange giải quyết bài toán: nếu bạn có một tập điểm (cặp tọa độ (x, y)), thì nội suy Lagrange sẽ tạo ra một đa thức đi qua tất cả các điểm đó. Ta thực hiện bằng cách phân tích bài toán: với mỗi tọa độ x, ta tạo một đa thức đi qua giá trị y mong muốn tại x đó và giá trị y=0 tại tất cả các tọa độ x khác mà ta quan tâm, rồi cộng tất cả các đa thức này lại để có kết quả cuối cùng.
Hãy lấy một ví dụ. Giả sử ta muốn một đa thức đi qua (1,3), (2,2) và (3,4). Trước tiên, ta tạo một đa thức đi qua (1,3), (2,0) và (3,0). Hóa ra, một đa thức "vươn ra" tại x=1 và bằng 0 tại các điểm quan tâm khác rất dễ tạo, ta chỉ cần làm đa thức:
y = (x - 2) * (x - 3)
Như hình dưới:
Sau đó, "kéo dài" theo trục y bằng phương trình:
y = (x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))
Rút gọn, ta được:
y = 1.5 * x**2 - 7.5 * x + 9
Thỏa mãn đi qua ba điểm (1,3), (2,0) và (3,0), như hình:
Thay các điểm (2,2) và (3,4) vào biểu thức trên, ta được:
y = 1.5 * x**2 - 5.5 * x + 7
Đây chính là phương trình tọa độ mà ta muốn. Thuật toán trên cần O(n³) thời gian, vì có n điểm, mỗi điểm cần O(n²) thời gian để nhân các đa thức. Chỉ cần suy nghĩ một chút, có thể giảm xuống O(n²); suy nghĩ sâu hơn nữa, dùng thuật toán biến đổi Fourier nhanh, có thể giảm thêm — đây là một tối ưu hóa quan trọng khi hàm dùng trong zk-SNARK thường có hàng ngàn cổng.
Ở đây tôi trực tiếp đưa ra công thức nội suy Lagrange:
Đa thức bậc n-1 đi qua n điểm (x₁,y₁), (x₂,y₂), (x₃,y₃), ..., (xₙ,yₙ) là:
Ví dụ trên, đa thức đi qua các điểm (1,3), (2,2), (3,4) là:
Sau khi học cách dùng công thức này, ta có thể tiếp tục bước tiếp theo. Bây giờ ta sẽ chuyển bốn bộ ba vector dài 6 thành sáu bộ đa thức, mỗi bộ gồm ba đa thức bậc ba, đánh giá các đa thức tại các điểm x khác nhau để đại diện cho các ràng buộc khác nhau. Ở đây ta có bốn ràng buộc, nên dùng đa thức tại x = 1,2,3,4 để đánh giá bốn bộ vector.
Bây giờ ta dùng công thức nội suy Lagrange để chuyển R1CS sang dạng QAP. Trước tiên tìm đa thức cho giá trị đầu tiên của mỗi vector a trong bốn ràng buộc, tức là 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ự, ta có thể tìm đa thức cho giá trị thứ i của mỗi vector trong các ràng buộc còn lại.
Dưới đây là kết quả:
Đ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 là 0.833 * x**3 - 5 * x**2 + 9.166 * x - 5. Nếu thay x=1 vào 18 đa thức trên, ta nhận đượ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ự, thay x = 2, 3, 4 vào các đa thức trên, ta phục hồi được phần còn lại của R1CS.
Bước 4: Kiểm tra QAP
Bằng cách chuyển R1CS sang QAP, ta có thể kiểm tra đồng thời tất cả các ràng buộc thông qua phép nhân vô hướng đa thức, thay vì kiểm tra từng ràng buộc riêng lẻ như trong R1CS. Như hình dưới:
Vì kiểm tra tích vô hướng ở đây là chuỗi cộng và nhân đa thức, kết quả cũng là một đa thức. Nếu đa thức kết quả có giá trị bằng 0 tại mọi tọa độ x tương ứng với mỗi cổng logic như trên, thì có nghĩa là mọi 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 0, thì có nghĩa là giá trị vào/ra cổng logic không nhất quán.
Lưu ý rằng bản thân đa thức kết quả không nhất thiết phải là đa thức 0, và thực tế trong hầu hết các trường hợp thì không phải; nó có thể hành xử tùy ý tại các điểm không tương ứng với bất kỳ cổng nào, miễn là tại mọi điểm tương ứng với một cổng nào đó, giá trị đều bằng 0. Để kiểm tra tính đúng đắn, ta không tính đa thức t = A . s * B . s - C . s tại từng điểm tương ứng với cổng; thay vào đó, ta chia t cho một đa thức khác Z, rồi 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 mọi điểm tương ứng với cổng logic. Đây là một sự thật cơ bản trong đại số: mọi đa thức bằng 0 tại tất cả các điểm này đều phải là bội của đa thức nhỏ nhất này; nếu một đa thức là bội của Z thì giá trị của nó tại mọi điểm này đều bằng 0; sự tương đương này khiến công việc của ta dễ dàng hơn nhiều.
Bây giờ, hãy thực hiện kiểm tra tích vô hướng với các đa thức trên.
Trước tiên, ta 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]
(Lưu ý của người dịch: quá trình tính toá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 sau khi 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]
(Lưu ý 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 * x³ + 38.5 * x² - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x³ - 5 * x² + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x³ - 24.5 * x² + 71.666 * x - 41.0
A . s * B . s - C . s là phép tính các đa thức trên, sau khi tính, sắp xếp hệ số từ thấp đến cao theo bậc, được: [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
Bấm vào đây để xem quá trình tính toán
Đ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 bấm vào đây để xem
Bây giờ tính chia đa thức:
h = t / Z = [-3.666, 17.055, -3.444]
h phải là phép chia hết không dư.
Có thể bấm vào đây để kiểm tra ngược lại.
Chúng ta đã có lời giải QAP. Nếu ta cố tình làm sai một biến trong R1CS, dẫn đến lời giải QAP — ví dụ đặt chữ số cuối cùng của s là 31 thay vì 30 — ta sẽ nhận được một đa thức t thất bại trong kiểm tra (trong trường hợp này tại x=3=1 thay vì 0), và không phải là bội của Z; thay vào đó, phép chia t / Z sẽ cho dư [-5.0, 8.833, -4.5, 0.666].
Lưu ý rằng trên đây chỉ là một ví dụ rất đơn giản; trong thế giới thực, các phép tính cộng trừ nhân chia thường đi kèm các số không thông thường, vì vậy tất cả các định luật đại số mà ta biết và yêu thích vẫn hữu ích, nhưng mọi kết quả đều là phần tử của một kích thước nhất định, thường là các số nguyên trong khoảng từ 0 đến n-1 với n cố định. Ví dụ, nếu n = 13, thì 1 / 2 = 7 (vì 7 * 2 = 14 ≡ 1 mod 13), 3 * 5 = 2, v.v. Việc dùng đại số trường hữu hạn loại bỏ lo ngại về lỗi làm tròn và cho phép hệ thống hoạt động tốt với các đường cong elliptic, điều này cuối cùng giúp giao thức zk-SNARK trở nên thực sự an toàn.
Chào mừng tham gia cộng đồng chính thức TechFlow
Nhóm Telegram:https://t.me/TechFlowDaily
Tài khoản Twitter chính thức:https://x.com/TechFlowPost
Tài khoản Twitter tiếng Anh:https://x.com/BlockFlow_News
@VitalikButerin
