Tác giả: 0xAlpha Đồng sáng lập @DeriProtocol; Trình biên dịch: DODO Research
Giới thiệu
zk-SNARKs, hoặc “các lập luận kiến thức không tương tác ngắn gọn 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 có kiến thức cụ thể nhất định, được gọi là nhân chứng, thỏa mãn các mối quan hệ cụ thể mà không tiết lộ bất cứ điều gì về chính nhân chứng.
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 vấn đề (hoặc hàm) thành một mạch cổng số học.
- Mạch này sau đó được dịch thành công thức ma trận.
- Công thức ma trận này được chuyển đổi thành đa thức, phải chia hết cho một đa thức tối thiểu cụ thể.
- Cuối cùng, chia hết này được biểu diễn trong các điểm đường cong elip trong các trường hữu hạn, nơi chứng minh diễn ra.
Ba bước đầu tiên chỉ đơn giản là chuyển đổi biểu diễn của câu lệnh gốc. Bước cuối cùng sử dụng mã hóa đồng cấu để chiếu câu lệnh của bước 3 vào không gian mật mã, cho phép người chứng minh xác minh câu lệnh nhân bản trong đó. Cho rằng phép chiếu này sử dụng mật mã bất đối xứng, không khả thi để theo dõi lại câu lệnh ban đầu từ bước ba, đảm bảo tiếp xúc với kiến thức bằng không.
Nền tảng toán học cần thiết để đọc bài viết này tương đương với trình độ đại số năm nhất cho các chuyên ngành STEM. Khái niệm duy nhất có thể là thách thức có lẽ là mã hóa đường cong elip. Đối với những người không quen thuộc với điều này, nó có thể được coi là một hàm mũ với một hồng y đặc biệt, trong khi hãy nhớ rằng nghịch đảo của nó vẫn chưa được giải quyết.
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ụ: A; Viết rõ ràng dưới dạng
- Vectơ: chữ thường có mũi tên, viết dưới dạng rõ ràng [ ] ; Theo mặc định, tất cả các vectơ là vectơ cột
- Vô hướng: Biểu diễn chữ cái thông thường
Hãy sử dụng câu hỏi nà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. Chúng ta sẽ đi qua toàn bộ quy trình mà Alice cần thực hiện để tạo zk-SNARK cho các bằng chứng của cô ấy.
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ụ: nếu-thì-khác). Tuy nhiên, không khó để chuyển đổi một hàm có luồng điều khiển thành biểu thức số học. Ví dụ: hãy xem xét câu hỏi sau (hoặc “hàm” trong ngôn ngữ lập trình):
f(x, z):
if(z==1):
trả về x*x*x+x*x+5
khác:
trả về x*x+5
Thật dễ dàng để viết lại vấn đề này thành biểu thức số học sau (giả sử z thuộc về (0,1)), không phức tạp hơn nhiều so với 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.
Bước 1: Mạch cổng 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:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-122a4a0e88-dd1a6f-cd5cc0.webp)
Điều này tương ứng với mạch cổng số học sau:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-9001e3d244-dd1a6f-cd5cc0.webp)
Chúng tôi cũng đề cập đến phương trình (2) là một tập hợp 4 “ràng buộc bậc nhất”, mỗi ràng buộc mô tả mối quan hệ của một cổng số học trong một mạch. Nói chung, một tập hợp n ràng buộc bậc nhất có thể được khái quát hóa thành một thủ tục số học bậc hai (QAP), 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:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-1157f4c74a-dd1a6f-cd5cc0.webp)
trong đó y, s1, s2, s3 giống như được định nghĩa trong phương trình (2).
Nói chung, đối với một bài toán với m đầu vào và n cổng số học (tức là các bước trung gian n-1 và đầu ra cuối cùng), vectơ nhân chứng này sẽ là (m + n + 1) chiều. Trong một bài toán thực tế, số n có thể rất lớn. Ví dụ, đối với một hàm băm, n thường là vài nghìn.
Tiếp theo, hãy xây dựng ba ma trận n*(m+n+*1) A,B,C để ta có thể viết lại phương trình (2) như sau:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a9e2164b2f-dd1a6f-cd5cc0.webp)
Phương trình (3) chỉ là một biểu diễn khác của Phương trình (2): mỗi nhóm (ai, bi, ci) tương ứng với một cổng trong mạch. Chúng ta chỉ cần mở rộng rõ ràng công thức ma trận để thấy điều này:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-630e507588-dd1a6f-cd5cc0.webp)
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 bậc nhất (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), tương đối đơn giản. Chúng ta chỉ cần chuyển đổi chúng thành dạng ma trận theo các ràng buộc cấp một tương ứng, để xác định nội dung của mỗi hàng (A, B, C), TỨC LÀ (AI, BI, CI). Lấy dòng đầu tiên làm ví dụ: dễ dàng thấy rằng để ràng buộc bậc nhất x được nhân với x bằng s1 để giữ, chúng ta cần nhân [0,1,0,0,0,0], [0,1,0,0,0] và [0,0,0,1,0,0] với vectơ s.
Do đó, chúng ta đã thành công trong việc chuyển đổi mạch cổng số học thành một công thức ma trận, tức là phương trình (3). Đồng thời, chúng tôi cũng đã thay đổi đối tượng cần được chứng minh là thành thạo từ vectơ nhân chứng.
Bước 3: Đa thức
Bây giờ, hãy xây dựng một ma trận n * (*n + m + * 1) định nghĩa một tập hợp các đa thức về z:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-94169f2b1d-dd1a6f-cd5cc0.webp)
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-2c37ea96a6-dd1a6f-cd5cc0.webp)
Đây là bốn bộ phương trình tuyến tính cho 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 quyết PA trong trường hợp này là nội suy Lagrange, tận dụng tính đặc thù của vấn đề. Ở đây chúng tôi bỏ qua quá trình giải quyết cho PA, hơi tẻ nhạt nhưng đơn giản.
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-fcac15b335-dd1a6f-cd5cc0.webp)
Trong đó:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a7d3309d02-dd1a6f-cd5cc0.webp)
Bước 4: Điểm cong hình elip
Viết lại phương trình (4) thành:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-f974fc7c93-dd1a6f-cd5cc0.webp)
Trong đó i(z)=1 chỉ là một đa thức bậc không tầm thường cho z, được sử dụng để thống nhất phương trình - tất cả các số hạng đều là bậc hai. Sự cần thiết phải làm như vậ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ủa đa thức của z.
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-8fdea08104-dd1a6f-cd5cc0.webp)
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ã hóa đường cong elip
Lý thuyết chung về đường cong elip vượt xa phạm vi của bài viết này. Theo mục đích của bài báo này, các đường cong elip được định nghĩa là ánh xạ từ miền nguyên tố Fp đến hàm E, trong đó E bao gồm các điểm thỏa mãn y ^ 2 = x ^ 3 + ax + b (được gọi là điểm đường cong elip, hoặc viết tắt là ECP).
Lưu ý rằng trong khi chúng ta đã nói về số học chính quy cho đến nay, bây giờ khi chúng ta chuyển đổi sang các trường nguyên tố, các phép toán số học trên các số được thực hiện theo cách mô-đun. Ví dụ: a + b = a + b (mod p), trong đó p là thứ tự của Fp.
Mặt khác, định nghĩa cộng của hai điểm đường cong elip được thể hiện trong hình sau:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-baf3cc3cbe-dd1a6f-cd5cc0.webp)
Cụ thể, việc bổ sung hai ECP, P và Q:
Tìm giao điểm của đường thẳng PQ và đường cong R, được định nghĩa là -(P + Q)
Lật đến điểm ‘gương’ R’ trên đường cong cho R.
Vì vậy, chúng tôi xác định việc thêm các điểm đường cong elip P + Q = R ':
Lưu ý rằng quy tắc này cũng áp dụng cho các trường hợp đặc biệt, tức là khi tự cộng ECP, trong đó tiếp tuyến của điểm sẽ được sử dụng.
Bây giờ giả sử chúng ta chọn một điểm G ngẫu nhiên và ánh xạ số 1 với nó. (Việc “lập bản đồ ban đầu” này nghe có vẻ hơi tùy tiện.) Thêm về điều đó sau). Sau đó, với bất kỳ n nào thuộc về Fp, chúng tôi định nghĩa:
E(N)=G+G+G+…+G=G
Điều này có một biểu hiện hành động. Các hành động xác định +G là “trình tạo” và được ký hiệu là g. Sau đó, định nghĩa trên tương đương với:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-bb825d6ba2-dd1a6f-cd5cc0.webp)
Đối với những người không quen thuộc với đường cong elip, bạn có thể tương tự ánh xạ này với một hàm mũ thông thường trong đó hồng y g thay thế các số thực. Các phép toán số học hoạt động tương tự. Tuy nhiên, một điểm khác biệt chính là hàm nghịch đảo của g^n không khả thi về mặt tính toán. Đó là, không có cách nào để tính phiên bản đường cong elip! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c989bcd81c-dd1a6f-cd5cc0.webp)。 Tất nhiên, đây là cơ sở của mật mã đường cong elip. Ánh xạ như vậy được gọi là mã hóa một chiều.
Lưu ý rằng với một đường cong elip, vì việc chọn G (và do đó Trình tạo g) là tùy ý (ngoại trừ các điểm trên trục x), có vô số cách để ánh xạ nó. Chọn (G hoặc g) có thể tương tự như chọn số chính của hàm mũ (2^x, 10^x, e^x, v.v.) như một phần của lẽ thường.
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-ce9f261ecc-dd1a6f-cd5cc0.webp)
Tuy nhiên, phương trình (5) mà Alice muốn chứng minh là bậc hai và do đó không đủ tuyến tính. Để đối phó với các thuật ngữ bậc hai, chúng ta cần định nghĩa phép nhân trong không gian mật mã. Điều này được gọi là hàm ghép nối, hoặc bản đồ song tuyến, và sẽ được giải thích tiếp theo.
Ánh xạ tuyến tính
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-146a4881e5-dd1a6f-cd5cc0)
Chuỗi tham chiếu chung
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-17e9a49fa0-dd1a6f-cd5cc0.webp)
Toàn bộ quá trình được gọi là “khóa xác minh”, hay viết tắt là VK. Chỉ có 7 điểm đường cong elip (ECP) liên quan ở đây, cần được cung cấp cho người xác minh. Điều quan trọng cần lưu ý là bất kể có bao nhiêu đầu vào và ràng buộc cấp một có liên quan đến vấn đề, VK luôn được tạo thành từ 7 ECP.
Ngoài ra, điều đáng nói là “thiết lập đáng tin cậy” và quá trình tạo PK và VK có thể được thực hiện một lần cho một vấn đề cụ thể.
Bằng chứng &; Xác minh
Bây giờ với khóa công khai (PK), Alice sẽ tính toán các điểm đường cong elip (ECP) sau:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c7eacd57e6-dd1a6f-cd5cc0.webp)
9 điểm đường cong elip này là chìa khóa cho các bằng chứng không tương tác ngắn gọn không có kiến thức (zk-SNARKs)!
Lưu ý rằng Alice thực sự chỉ thực hiện một số phép toán tổ hợp tuyến tính trên các điểm đường cong elip trong khóa công khai. Điều này đặc biệt quan trọng và sẽ được kiểm tra trong quá trình xác nhận.
Bây giờ Alice đã bàn giao bằng chứng zk-SNARK, cuối cùng chúng ta hãy bước vào quy trình xác minh, đây là quy trình gồm ba bước.
Trước hết, điều quan trọng là phải đảm bảo rằng 8 điểm cong elip đầu tiên thực sự là sự kết hợp tuyến tính của các điểm đó trong chuỗi tham chiếu chung.
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-4cf599e8c2-dd1a6f-cd5cc0.webp)
Nếu cả ba kiểm tra đều đúng, thì phương trình (5) được xác minh, vì vậy chúng tôi tin rằng Alice biết nhân chứng.
Hãy giải thích lý do đằng sau phương trình. Lấy phương trình đầu tiên trong phần đầu tiên làm ví dụ, đúng vì bản chất tuyến tính:
! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-0032ace846-dd1a6f-cd5cc0.webp)
Tuy nhiên, vì Alice không biết giá trị của ký hiệu alpha, cô ấy không thể tính toán phép cộng này một cách rõ ràng. Cách duy nhất cô ấy có thể đưa ra một cặp thỏa mãn phương trình (EA, EA ') là sử dụng cùng một tập hợp các vectơ s mỗi, tính toán! [Sức mạnh của bằng chứng không có kiến thức: Giải mã toán học zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-933d054c72-dd1a6f-cd5cc0.webp).
Tham khảo
“Zk-SNARKs: Dưới mui xe” (Vitalik Buterin)
“A Review of Zero Knowledge Proofs” (Thomas Chen, Abby Lu, Jern Kunpittaya, và Alan Luo)
“Tại sao và làm thế nào zk-SNARK hoạt động: Giải thích dứt khoát” (Maksym Petkus)
Trang web: Zero-Knowledge Proofs
Wikipedia:Đường cong elip
Wikipedia:Trường hữu hạn
Wikipedia:Mật mã dựa trên ghép nối
