Vitalik: Nguyên lý bên trong zk-SNARKs
Tuyển chọn TechFlowTuyển chọn TechFlow
Vitalik: Nguyên lý bên trong zk-SNARKs
Bài viết này sẽ giả sử bạn đã hiểu hai khái niệm này, đồng thời nắm được kiến thức cơ bản về zk-SNARKs và cách chúng hoạt động.
Chuyên sâu báo cáo Web3*Ghi chú: Bài viết được viết vào tháng 2 năm 2017
Bài viết này giải thích cách thức hoạt động của công nghệ đằng sau zk-SNARKs. Các bài viết trước đó về chương trình toán tử bậc hai và ghép đôi đường cong elliptic là những tài liệu bắt buộc cần đọc. Bài viết hiện tại giả định rằng bạn đã hiểu rõ hai khái niệm trên cũng như kiến thức cơ bản về zk-SNARKs và chức năng của chúng. Bạn cũng nên tham khảo thêm phần giới thiệu khác về zk-SNARKs trong bài viết của Christian Reitwiessner có tựa đề "zkSNARKs in a Nutshell".
Trong các bài viết trước, chúng ta đã giới thiệu chương trình toán tử bậc hai — một phương pháp biểu diễn mọi vấn đề tính toán dưới dạng các phương trình đa thức. Chúng ta cũng đã làm quen với khái niệm ghép đôi đường cong elliptic, cho phép thực hiện một hình thức mã hóa đồng cấu một chiều rất hạn chế, từ đó cho phép kiểm tra đẳng thức. Bây giờ, chúng ta sẽ tiếp tục từ điểm dừng trước đó và sử dụng ghép đôi đường cong elliptic cùng với một số thủ thuật toán học khác để cho phép bên chứng minh (prover) chứng minh họ biết lời giải cho một QAP cụ thể mà không tiết lộ bất kỳ thông tin nào về lời giải thực tế.
Bài viết này tập trung vào giao thức Pinocchio do Parno, Gentry, Howell và Raykova công bố năm 2013 (thường gọi tắt là PGHR13); mặc dù cơ chế cốt lõi có một vài thay đổi nhỏ so với các sơ đồ zk-SNARK được triển khai trong thực tế, nhưng các nguyên lý cơ bản vẫn giữ nguyên.
Đầu tiên, hãy đi đến một giả thiết then chốt: Giả thiết Kiến thức Mũ (KEA - Knowledge of Exponent Assumption). Chúng ta sẽ dùng giả thiết này khi mô tả cơ chế bảo mật nền tảng.
KEA1: Với bất kỳ đối thủ A nào nhận đầu vào q, g, g^a rồi trả về cặp (C, Y) sao cho Y = C^a, thì luôn tồn tại một "trích xuất viên" (extractor) A', khi nhận cùng đầu vào như A, có thể trả về c sao cho g^c = C.
Giả thiết này về cơ bản ngụ ý rằng nếu bạn nhận được một cặp điểm P và Q, trong đó P * k = Q, và bạn nhận thêm một điểm C, thì trừ khi C có thể "rút ra" từ P theo một cách nào đó, bạn sẽ không thể tạo ra điểm tương ứng C * k. Điều này có vẻ hiển nhiên, nhưng thực tế giả thiết này không thể suy ra từ bất kỳ giả thiết nào khác thường được dùng để chứng minh độ an toàn của các giao thức đường cong elliptic (ví dụ như bài toán logarit rời rạc), do đó, zk-SNARK thực sự có một nền tảng an toàn yếu hơn một chút so với mật mã đường cong elliptic — tuy nhiên nó vẫn đủ vững chắc để phần lớn các nhà mật mã học chấp nhận sử dụng.
Bây giờ, hãy xem cách áp dụng nó. Giả sử một cặp điểm (P, Q) rơi từ trên trời xuống, trong đó P * k = Q, nhưng không ai biết giá trị k là gì. Bây giờ, nếu tôi tạo ra một cặp điểm (R, S) sao cho R * k = S, thì theo giả thiết KoE, cách duy nhất tôi có thể đạt được cặp điểm này là nhân P và Q với một hệ số r nào đó mà tôi biết. Cần lưu ý thêm rằng, nhờ đặc tính kỳ diệu của ghép đôi đường cong elliptic, việc kiểm tra R * k = S thực tế không yêu cầu phải biết k — mà chỉ cần kiểm tra e(R, Q) = e(P, S).
Hãy làm điều thú vị hơn. Giả sử có mười cặp điểm rơi từ trên trời xuống: (P_1, Q_1), (P_2, Q_2)...(P_10, Q_10). Trong mọi trường hợp đều thỏa mãn P_i * k = Q_i. Giờ tôi đưa cho bạn một cặp điểm (R, S) sao cho R * k = S. Bây giờ bạn biết được điều gì? Bạn biết rằng R là một tổ hợp tuyến tính của các điểm P_1*i_1 + P_2*i_2 + ... + P_10*i_10, trong đó tôi biết các hệ số i_1, i_2...i_10. Nói cách khác, cách duy nhất để đạt được cặp điểm (R, S) như vậy là lấy bội số của các điểm P_1, P_2,...P_10, cộng chúng lại với nhau, và thực hiện cùng phép tính tương tự đối với Q_1, Q_2,...Q_10.
Lưu ý rằng, với bất kỳ bộ điểm P_1...P_10 cụ thể nào mà bạn muốn kiểm tra tổ hợp tuyến tính, bạn thực tế không thể tạo ra các điểm Q_1...Q_10 đi kèm nếu không biết k; và nếu bạn thực sự biết k, bạn có thể tạo ra cặp (R, S) với R * k = S cho bất kỳ R nào mong muốn mà không cần phải tạo tổ hợp tuyến tính. Vì vậy, để đảm bảo điều này, người tạo ra các điểm này phải đáng tin cậy, và một khi 10 điểm đã được tạo, giá trị k phải bị xóa bỏ. Đây chính là nguồn gốc của khái niệm “thiết lập đáng tin cậy” (“trusted setup” — người dịch: Thiết lập đáng tin cậy là quá trình khởi tạo hệ thống zkSNARK, chỉ cần thực hiện một lần).
Nhớ lại rằng lời giải của một QAP là một bộ ba đa thức (A, B, C) sao cho A(x) * B(x) – C(x) = H(x) * Z(x), trong đó:
A là tổ hợp tuyến tính của một tập hợp đa thức {A_1 ... A_m}
B là tổ hợp tuyến tính của {B_1 ... B_m} với cùng hệ số
C là tổ hợp tuyến tính của {C_1 ... C_m} với cùng hệ số
Tập hợp {A_1 ... A_m}, {B_1 ... B_m} và {C_1 ... C_m} cùng với đa thức Z là một phần của phát biểu bài toán.
Tuy nhiên, trong hầu hết các trường hợp thực tế, A, B và C đều rất lớn; với các thứ như hàm băm có hàng ngàn cổng mạch, các đa thức (và các hệ số tổ hợp tuyến tính) có thể có hàng ngàn hạng tử. Do đó, thay vì yêu cầu bên chứng minh cung cấp trực tiếp tổ hợp tuyến tính, chúng ta sử dụng kỹ thuật đã giới thiệu ở trên để chứng minh rằng thứ mà họ cung cấp đúng là một tổ hợp tuyến tính, mà không tiết lộ bất kỳ thông tin nào khác.
Bạn có thể đã nhận thấy kỹ thuật ở trên áp dụng cho các điểm trên đường cong elliptic chứ không phải các đa thức. Do đó, trong thực tế, chúng ta thêm vào thiết lập đáng tin cậy các giá trị sau đây:
G * A_1(t), G * A_1(t) * k_a
G * A_2(t), G * A_2(t) * k_a
...
G * B_1(t), G * B_1(t) * k_b
G * B_2(t), G * B_2(t) * k_b
...
G * C_1(t), G * C_1(t) * k_c
G * C_2(t), G * C_2(t) * k_c
...
Bạn có thể coi t là "điểm bí mật" để tính toán các đa thức. G là một "phần tử sinh" (một điểm ngẫu nhiên cố định trên đường cong elliptic, một khi xác định sẽ trở thành một phần của giao thức), còn t, k_a, k_b và k_c là "chất thải độc hại", những con số này phải bị xóa bỏ bằng mọi giá, bởi bất kỳ ai sở hữu chúng đều có thể tạo ra các bằng chứng giả. Bây giờ, nếu ai đó đưa cho bạn một cặp điểm P, Q sao cho P * k_a = Q (nhắc lại: chúng ta không cần k_a để kiểm tra điều này, vì có thể dùng kiểm tra ghép đôi), thì bạn biết rằng họ đang cung cấp một tổ hợp tuyến tính của các đa thức A_i được tính tại t.
Do đó, đến thời điểm này, bên chứng minh phải cung cấp:
π_a = G * A(t), π'_a = G * A(t) * k_a
π_b = G * B(t), π'_b = G * B(t) * k_b
π_c = G * C(t), π'_c = G * C(t) * k_c
Lưu ý rằng bên chứng minh thực tế không cần biết (và không nên biết!) t, k_a, k_b hay k_c để tính các giá trị này; thay vào đó, họ nên có thể tính các giá trị này từ các điểm mà chúng ta đã thêm vào thiết lập đáng tin cậy.
Bước tiếp theo là đảm bảo cả ba tổ hợp tuyến tính đều có cùng hệ số. Chúng ta có thể đạt được điều này bằng cách thêm một tập hợp giá trị khác vào thiết lập đáng tin cậy: G * (A_i(t) + B_i(t) + C_i(t)) * b, trong đó b là một con số khác cũng cần được coi là "chất thải độc hại" và bị loại bỏ ngay sau khi hoàn tất thiết lập đáng tin cậy. Sau đó, chúng ta yêu cầu bên chứng minh tạo một tổ hợp tuyến tính từ các giá trị này với cùng hệ số, và sử dụng kỹ thuật ghép đôi như trên để kiểm tra xem giá trị này có khớp với A + B + C được cung cấp hay không.
Cuối cùng, chúng ta cần chứng minh A * B – C = H * Z. Một lần nữa, chúng ta dùng kiểm tra ghép đôi:
e(π_a, π_b) / e(π_c, G) ?= e(π_h, G * Z(t))
Trong đó π_h = G * H(t). Nếu bạn chưa thấy mối liên hệ giữa phương trình này và A * B – C = H * Z, hãy quay lại và đọc bài viết về ghép đôi.
Chúng ta đã thấy cách chuyển A, B và C thành các điểm trên đường cong elliptic ở phần trên; G đơn thuần là phần tử sinh (tức là, điểm G trên đường cong elliptic này tương đương với số 1). Chúng ta có thể thêm G * Z(t) vào thiết lập đáng tin cậy. Việc tính H khó hơn; H chỉ là một đa thức, và với mỗi lời giải QAP, chúng ta khó có thể dự đoán trước hệ số của nó. Vì vậy, chúng ta cần thêm nhiều dữ liệu hơn vào thiết lập đáng tin cậy; cụ thể là dãy:
G, G * t, G * t², G * t³, G * t⁴......
Trong thiết lập đáng tin cậy của Zcash, dãy này dài khoảng 2 triệu phần tử; hãy tưởng tượng lượng sức mạnh tính toán cần thiết để đảm bảo bạn có thể tính H(t). Nhờ dãy này, bên chứng minh có thể cung cấp cho bên xác minh mọi thông tin cần thiết để thực hiện kiểm tra cuối cùng.
Còn một chi tiết nữa mà chúng ta cần thảo luận. Hầu hết thời gian, chúng ta không chỉ muốn chứng minh một cách trừu tượng rằng một giải pháp cụ thể nào đó tồn tại cho một vấn đề nhất định; thay vào đó, chúng ta muốn chứng minh tính đúng đắn của một lời giải cụ thể (ví dụ: chứng minh rằng nếu từ "cow" được băm một triệu lần bằng thuật toán SHA3, kết quả cuối cùng bắt đầu bằng 0x73064fe5), hoặc rằng tồn tại một lời giải nếu một số tham số bị giới hạn. Ví dụ, trong việc triển khai tiền mã hóa, số dư giao dịch và tài khoản đã được mã hóa, bạn cần chứng minh rằng bạn biết một khóa giải mã k sao cho:
decrypt(old_balance, k) ≥ decrypt(tx_value, k)
decrypt(old_balance, k) – decrypt(tx_value, k) = decrypt(new_balance, k)
old_balance, tx_value và new_balance đã mã hóa cần được công khai, vì đây là những giá trị cụ thể mà chúng ta cần kiểm tra tại một thời điểm nhất định; chỉ riêng khóa giải mã cần được ẩn. Cần một vài sửa đổi nhỏ đối với giao thức để tạo ra một "khóa xác minh tùy chỉnh" tương ứng với một số ràng buộc cụ thể đối với đầu vào.
Bây giờ, hãy lùi lại một bước. Dưới đây là thuật toán xác minh đầy đủ, do Ben Sasson, Tromer, Virza và Chiesa cung cấp:
Dòng đầu tiên xử lý tham số hóa; về cơ bản, bạn có thể coi chức năng của nó là tạo ra một "khóa xác minh tùy chỉnh" cho một trường hợp bài toán cụ thể với một số tham số nhất định. Dòng thứ hai kiểm tra tổ hợp tuyến tính của A, B và C; dòng thứ ba kiểm tra xem các tổ hợp tuyến tính có cùng hệ số hay không; dòng thứ tư kiểm tra A * B – C = H * Z.
Tóm lại, quá trình xác minh gồm một số phép nhân đường cong elliptic (mỗi biến đầu vào "công khai" một phép) và năm kiểm tra ghép đôi, trong đó một phép bao gồm thêm một phép nhân ghép đôi. Bằng chứng được cung cấp chứa tám điểm trên đường cong elliptic: một điểm cho mỗi A(t), B(t) và C(t), một điểm cho b*(A(t)+B(t)+C(t)) ký hiệu là π_k, và một điểm cho H(t) ký hiệu là π_h. Trong đó 7 điểm nằm trên đường cong F_p (mỗi điểm 32 byte, vì tọa độ y có thể nén thành 1 bit), trong triển khai Zcash, điểm còn lại (π_b) nằm trên đường cong xoắn F_p² (64 byte), do đó tổng kích thước bằng chứng khoảng 288 byte.
Hai phần tính toán khó nhất trong việc tạo bằng chứng là:
- Thực hiện (A * B – C)/Z để tìm H (các thuật toán dựa trên biến đổi Fourier nhanh có thể hoàn thành việc này trong thời gian dưới bậc hai, nhưng vẫn rất tốn kém)
- Thực hiện phép nhân và cộng đường cong elliptic để tạo các giá trị A(t), B(t), C(t), H(t) và các giá trị ghép đôi tương ứng
Việc tạo bằng chứng rất khó khăn, nguyên nhân là vì chúng ta đang thực hiện bằng chứng kiến thức không (zero-knowledge proof), từng cổng logic nhị phân trong tính toán gốc phải được chuyển thành các thao tác mã hóa qua đường cong elliptic. Thực tế này cùng với độ phức tạp siêu tuyến tính của biến đổi Fourier nhanh khiến việc tạo bằng chứng trong giao dịch Zcash mất khoảng 20-40 giây.
Một vấn đề rất quan trọng khác là: Chúng ta có thể cố gắng làm cho thiết lập đáng tin cậy trở nên... ít phụ thuộc vào niềm tin hơn không? Thật không may, chúng ta không thể loại bỏ hoàn toàn sự tin cậy; chính giả thiết KoE đã loại trừ khả năng tạo ra các cặp độc lập (P_i, P_i * k) mà không biết k. Tuy nhiên, chúng ta có thể tăng cường đáng kể độ an toàn bằng cách sử dụng tính toán đa phương N-trên-N — nghĩa là, xây dựng thiết lập đáng tin cậy giữa N bên, chỉ cần ít nhất một bên xóa bỏ "chất thải độc hại" của họ thì bạn đã an toàn.
Để bạn có cảm giác sơ bộ về cách thực hiện, dưới đây là một thuật toán đơn giản để lấy một tập hợp hiện có (G, G * t, G * t², G * t³...), và "thêm" bí mật của riêng bạn vào, do đó bạn cần cả bí mật của mình và bí mật trước đó (hoặc tập hợp các bí mật trước đó) để gian lận.
Tập hợp đầu ra rất đơn giản:
G, (G * t) * s, (G * t²) * s², (G * t³) * s³......
Lưu ý rằng, ngoại trừ việc bây giờ dùng t * s làm "chất thải độc hại" thay vì t, bạn chỉ cần biết tập hợp ban đầu và s để có được một tập hợp mới có chức năng giống hệt tập cũ. Miễn là bạn và người (hay những người) tạo ra tập trước đó không cùng thất bại trong việc xóa chất thải độc hại và sau đó cấu kết với nhau, thì nhóm này được coi là "an toàn".
Việc thực hiện điều này cho toàn bộ thiết lập đáng tin cậy khó hơn nhiều, vì liên quan đến nhiều giá trị và thuật toán phải trải qua nhiều vòng giữa các bên. Đây là một lĩnh vực nghiên cứu đang phát triển mạnh, nhằm xem liệu các thuật toán tính toán đa phương có thể được đơn giản hóa hơn nữa, cần ít vòng hơn hoặc song song hóa tốt hơn, vì nếu làm được như vậy, sẽ cho phép nhiều bên tham gia hơn vào quy trình thiết lập đáng tin cậy. Có lý do để thấy rằng một thiết lập đáng tin cậy giữa sáu người tham gia có thể khiến một số người cảm thấy lo ngại, nhưng một thiết lập đáng tin cậy với hàng ngàn người tham gia gần như tương đương với việc "không cần tin cậy" — nếu bạn thực sự là người đa nghi, bạn có thể tự tham gia và đảm bảo rằng bạn đã xóa bỏ "chất thải độc hại" của riêng mình.
Một lĩnh vực nghiên cứu tích cực khác là tìm kiếm các phương pháp thay thế để đạt được mục tiêu tương tự mà không cần dùng ghép đôi và thiết lập đáng tin cậy như vậy. Hãy tham khảo bài thuyết trình gần đây của Eli ben Sasson tại đây (lưu ý: nó cũng phức tạp về mặt toán học ít nhất ngang bằng với SNARKs!)
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
