Sức mạnh của bằng chứng không có kiến thức: Đi sâu vào zk-SNARK

Bài viết này sẽ giải mã công nghệ này bằng toán học, minh họa cách nó có thể chứng minh sự thật của kiến thức mà không tiết lộ bất kỳ thông tin nào.

Biên soạn bởi: DODO Research

Tác giả: Đồng sáng lập 0xAlpha @DeriProtocol

Giới thiệu loại coin

Zk-SNARK, hay lập luận kiến thức ngắn gọn không tương tác không có kiến thức, cho phép người xác minh xác nhận rằng người chứng minh sở hữu một số kiến thức nhất định (được gọi là nhân chứng) đáp ứng các mối quan hệ cụ thể mà không tiết lộ bất kỳ thông tin nào về chính kiến thức đó.

Tạo zk-SNARK cho một vấn đề cụ thể bao gồm bốn giai đoạn sau:

• Chuyển đổi một bài toán (hoặc hàm) thành một mạch số học.
• Mạch này sau đó được dịch thành một phương trình ma trận.
• Phương trình ma trận này tiếp tục được chuyển đổi thành một đa thức có thể chia hết cho một đa thức tối thiểu cụ thể.
• Cuối cùng, khả năng chia hết này được thể hiện bằng các điểm của đường cong elip trên một trường hữu hạn, nơi việc chứng minh diễn ra.

Ba bước đầu tiên chỉ đơn thuần biến đổi cách trình bày của câu lệnh ban đầu. Bước cuối cùng chiếu tuyên bố từ bước thứ ba vào một không gian được mã hóa bằng cách sử dụng mã hóa đồng hình, cho phép người chứng minh xác minh các tuyên bố được phản chiếu trong đó. Vì phép chiếu này sử dụng mã hóa bất đối xứng nên việc quay ngược từ câu lệnh ở bước 3 về câu lệnh ban đầu là không khả thi, đảm bảo không có kiến thức.

Nền tảng toán học cần thiết để đọc bài viết này có thể so sánh với trình độ đại số mong đợi của sinh viên đại học STEM năm thứ nhất. Khái niệm duy nhất có thể gặp thách thức có thể là mật mã đường cong elip. Đối với những người không quen với điều này, bạn có thể coi nó như một hàm số mũ có cơ số đặc biệt, hãy nhớ rằng nghịch đảo của nó vẫn chưa được giải.

Bài viết này sẽ tuân theo các quy tắc ký hiệu sau:

Ma trận: Chữ in hoa đậm, ví dụ MỘT; được viết dưới dạng tường minh \
Vectơ: Chữ thường có mũi tên, được viết ở dạng tường minh [ ]; tất cả các vectơ đều là vectơ cột theo mặc định \
Vô hướng: Được biểu thị bằng các chữ cái thông thường

Hãy lấy câu hỏi sau đây làm ví dụ:

f(x)=x^3+x^2+5 (1)

Giả sử Alice muốn chứng minh rằng cô ấy biết một sự thật. Chúng ta sẽ hướng dẫn toàn bộ quy trình mà Alice cần thực hiện để tạo zk-SNARK cho bằng chứng của mình.
Câu hỏi này có vẻ quá đơn giản vì nó không liên quan đến luồng điều khiển (ví dụ: if-then-else). Tuy nhiên, không khó để chuyển đổi các hàm có luồng điều khiển thành các biểu thức số học. Ví dụ: hãy xem xét vấn đề sau (hoặc “hàm” trong ngôn ngữ lập trình):

f(x, z):
nếu(z==1):
trả về xxx+xx+5
khác:
trả về xx+5

Viết lại bài toán này thành biểu thức số học sau (giả sử z thuộc (0,1)) không phức tạp hơn phương trình (1) .

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

Trong bài viết này, chúng tôi sẽ tiếp tục sử dụng phương trình (1) làm cơ sở cho cuộc thảo luận của chúng tôi.

Bước 1: Mạch số học

Phương trình (1) có thể được chia thành các phép toán số học cơ bản sau:

Điều này tương ứng với mạch số học sau:

Chúng tôi cũng coi phương trình (2) là một tập hợp gồm 4 “ràng buộc chính”, mỗi ràng buộc mô tả mối quan hệ của một cổng số học trong mạch. Nói chung, một tập hợp n ràng buộc chính có thể được tóm tắt dưới dạng chương trình số học bậc hai (QAP), chương trình này sẽ được giải thích tiếp theo.

Bước 2: Ma trận

Đầu tiên, hãy định nghĩa một vectơ “nhân chứng” như sau:

trong đó y, s1, s2 và s3 được xác định như trong phương trình (2).
Thông thường, đối với một bài toán có m đầu vào và n cổng số học (tức là n-1 bước trung gian và đầu ra cuối cùng), vectơ chứng kiến này sẽ có chiều (m+n+1). Trong trường hợp thực tế, số n có thể cực kỳ lớn. Ví dụ, đối với hàm băm, n thường ở mức hàng nghìn.

Tiếp theo, chúng ta dựng ba ma trận n(m+n+1) A,B,C để có thể viết lại phương trình (2) như sau:

Phương trình (3) chỉ là một cách biểu diễn khác của phương trình (2): mỗi bộ (ai, bi, ci) tương ứng với một cổng trong mạch. Chúng ta có thể thấy điều này bằng cách mở rộng rõ ràng phương trình ma trận:

Vì vậy LHS=RHS hoàn toàn giống với phương trình (2) và mỗi hàng của phương trình ma trận tương ứng với một ràng buộc chính (tức là một cổng số học trong mạch).

Chúng tôi đã bỏ qua các bước xây dựng (A, B, C), những bước này thực sự tương đối đơn giản. Chúng ta chỉ cần chuyển chúng thành ma trận theo các ràng buộc sơ cấp tương ứng để xác định nội dung của từng hàng của (A, B, C), tức là (ai, bi, ci). Lấy hàng đầu tiên làm ví dụ: chúng ta có thể dễ dàng thấy rằng để làm ràng buộc chính đầu tiên x nhân với x bằng s1, chúng ta cần nhân [0,1,0,0,0], [0, 1,0, 0,0] và [0,0,0,1,0,0] theo vectơ s.

Như vậy, chúng ta đã chuyển thành công mạch số học thành phương trình ma trận, cụ thể là phương trình (3). Đồng thời, chúng ta cũng thay đổi đối tượng cần chứng minh làm chủ thành vectơ chứng kiến s.

Bước 3: Đa thức

Bây giờ, hãy xây dựng một ma trận PA n(n+m+*1), xác định một tập hợp các đa thức liên quan đến z:

Đảm bảo rằng chức năngnhận các giá trị sau tại {1, 2, 3, 4} thỏa mãn các điều kiện:

Khi đó chúng ta có thể viết lại A thành:

Đây là bốn bộ phương trình tuyến tính bao gồm sáu biến có thể được giải bằng các phương pháp truyền thống. Tuy nhiên, một cách hiệu quả hơn để giải PA trong trường hợp này là nội suy Lagrange, khai thác những đặc thù của bài toán. Ở đây chúng ta bỏ qua quá trình giải PA, việc này hơi tẻ nhạt nhưng đơn giản.

Tương tự, ta xây dựng PB và PC riêng cho B và C. Sau đó ta viết lại phương trình ma trậnnhư sau:

Quan sát từng hàng riêng biệt, rõ ràng bốn hàng này tương ứng với cùng một biểu thức được đánh giá ở bốn điểm khác nhau. Do đó, phương trình ma trận trên tương đương với:

Bước 3: Điểm đường cong Elliptic

Viết lại phương trình (4) dưới dạng:

trong đó i(z)=1 chỉ là một đa thức bậc 0 tầm thường trong z được sử dụng để thống nhất các phương trình - tất cả các số hạng đều là bậc hai. Sự cần thiết của việc này sẽ sớm trở nên rõ ràng. Lưu ý rằng phương trình này chỉ chứa phép cộng và phép nhân các đa thức trong z.

Xin lưu ý rằng các phép toán số học, phép cộng (+) và phép nhân (X), cũng được ánh xạ tới các phép toán tương ứng trong trường hữu hạn của các điểm trên đường cong elip. Các biểu tượng Và được sử dụng để tránh nhầm lẫn và chỉ ra rằng đây là các hoạt động trường được xác định lại.

Tiếp theo, chúng tôi sẽ giải thích các bước thực tế chi tiết hơn.

Mật mã đường cong Elliptic

Lý thuyết chung về đường cong elip vượt xa phạm vi của bài viết này. Với mục đích ở đây, đường cong elip được định nghĩa là ánh xạ từ trường nguyên tố Fp đến hàm E, trong đó E bao gồm các điểm sao cho y^2=x^3+ax+b (gọi là điểm đường cong elip, hay viết tắt là ECP) .

Xin lưu ý rằng trong khi chúng ta đang thảo luận về số học thông thường cho đến nay, khi chuyển sang trường nguyên tố, các phép toán số học trên các số được thực hiện bằng cách sử dụng số học mô-đun. Ví dụ, a+b=a+b(mod p), trong đó p là bậc của Fp.

Mặt khác, phép cộng hai điểm trên đường cong elip được xác định như sau:

Cụ thể việc bổ sung P và Q của hai ECP:

Tìm giao điểm của đường PQ và đường cong R và xác định nó là -(P+Q)
Lật tới điểm “gương” R' của R trên đường cong.
Do đó, chúng tôi xác định phép cộng các điểm trên đường cong elip P+Q=R':

Lưu ý rằng quy tắc này cũng áp dụng cho trường hợp đặc biệt khi sử dụng phép cộng một ECP, trong trường hợp đó tiếp tuyến với điểm đó sẽ được sử dụng.

Bây giờ giả sử chúng ta chọn ngẫu nhiên một điểm G và ánh xạ số 1 tới đó. (“Bản đồ ban đầu” này nghe có vẻ hơi tùy tiện. Chúng ta sẽ thảo luận về nó sau). Và với mọi n thuộc Fp, ta xác định:

E(N)=G+G+G+…..+G=G nhân với n

Có một biểu thức hoạt động. Xác định phép toán +G là “trình tạo”, ký hiệu là g. Khi đó định nghĩa trên tương đương với:

Sau khi xác định phép cộng, mối quan hệ tuyến tính sau đây trở nên rõ ràng:

Do đó, mọi mối quan hệ tuyến tính (hoặc ràng buộc) trong Fp sẽ được giữ nguyên trong không gian B được mã hóa thông qua ánh xạ này. Ví dụ, phương trình l + m = n trong Fp sẽ dẫn đến

Tuy nhiên, vì phương trình (5) mà Alice muốn chứng minh ở dạng bậc hai nên nó không đủ tuyến tính. Để xử lý các số hạng bậc hai, chúng ta cần định nghĩa phép nhân trong không gian được mã hóa. Đây được gọi là bản đồ ghép nối hoặc bản đồ song tuyến mà tôi sẽ giải thích trong phần sau.

Bản đồ song tuyến

Giả sử G1, G2 và GT là các nhóm cấp nguyên tố g. Hàm ghép nối hoặc bản đồ song tuyến được định nghĩa như sau:

Chuỗi tham chiếu chung

Toàn bộ điều này được gọi là “chìa khóa chứng minh” (PK). Lưu ý rằng việc biểu diễn các vectơ trong E() nên được hiểu là vectơ của các điểm trên đường cong elip, trong đó mỗi điểm được ánh xạ từ phần tử vectơ tương ứng. Do đó, 11 vectơ này thực sự bao gồm 62 (=42+63+63+63) điểm đường cong elip. 62 ECP này sẽ được cung cấp cho Alice, người chứng minh. Trong kịch bản chung, đối với một bài toán có m đầu vào và n ràng buộc chính, PK sẽ chứa 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP.

Đồng thời, các tính toán sau sẽ được thực hiện:

Toàn bộ quá trình này được gọi là “khóa xác minh” (VK). Ở đây chỉ có 7 điểm đường cong elip (ECP) cần được cung cấp cho người xác minh. Cần lưu ý rằng cho dù vấn đề có liên quan đến bao nhiêu đầu vào và ràng buộc chính, VK luôn bao gồm 7 ECP.

Ngoài ra, điều đáng nói là việc “thiết lập tin cậy” và quá trình tạo PK, VK chỉ cần thực hiện một lần cho một vấn đề cụ thể.

Chứng minh và xác minh

Bây giờ sở hữu khóa chung (PK), Alice sẽ tính các điểm trên đường cong elip (ECP) sau:

9 điểm đường cong elip này rất quan trọng đối với một đối số kiến thức không tương tác, ngắn gọn, không có kiến thức (zk-SNARK)!

Lưu ý rằng về cơ bản Alice chỉ đang thực hiện các kết hợp tuyến tính trên các điểm của đường cong elip trong khóa chung. Điều này đặc biệt quan trọng và sẽ được kiểm tra nghiêm ngặt trong quá trình xác minh.

Bây giờ, Alice trình bày bằng chứng zk-SNARK, cuối cùng dẫn chúng ta đến quy trình xác minh, diễn ra theo ba bước.

Đầu tiên, cần phải xác nhận rằng 8 điểm trên đường cong elip đầu tiên thực sự là tổ hợp tuyến tính của các điểm đó trong chuỗi tham chiếu chung.

Tuyên bố từ chối trách nhiệm:

1. Bài viết này được in lại từ [chaincatcher]. Mọi bản quyền đều thuộc về tác giả gốc [Người đồng sáng lập 0xAlpha @ DeriProtocol]. Nếu có ý kiến phản đối việc tái bản này, vui lòng liên hệ với nhóm Gate Learn , họ sẽ xử lý kịp thời.
2. Tuyên bố miễn trừ trách nhiệm pháp lý: Các quan điểm và ý kiến trình bày trong bài viết này chỉ là của tác giả và không cấu thành bất kỳ lời khuyên đầu tư nào.
3. Việc dịch bài viết sang các ngôn ngữ khác được thực hiện bởi nhóm Gate Learn. Trừ khi được đề cập, việc sao chép, phân phối hoặc đạo văn các bài viết đã dịch đều bị cấm.