Tác giả của bài viết này, Dongze, là một đối tác nhỏ của Cộng đồng công nghệ Ambi, anh ấy hiện đang học tại Đại học Stanford, và hướng nghiên cứu của anh ấy là mật mã. Loạt bài viết này xuất phát từ ghi chú nghiên cứu của tác giả về khóa học Stanford nổi tiếng "CS 251: Tiền điện tử và công nghệ chuỗi khối". Người hướng dẫn khóa học là Dan Boneh, một bậc thầy về mật mã học.
Sau khi số cuối cùng của bài báo được xuất bản, tôi rất ngạc nhiên khi có rất nhiều bạn thích nó sau khi đọc nó. Vì vậy, hãy tiếp tục với tập phim này! Lần này, hãy tập trung vào SNARK.
Tôi tin rằng những người bạn đã đọc bài viết trước sẽ hơi khó hiểu: tại sao chúng ta có thể tạo ra một bằng chứng ngắn gọn như vậy và chứng minh một thông điệp dài? Trước lớp tôi cũng từng nghi ngờ như vậy, thậm chí còn cho rằng đây là “công nghệ đen”, nhưng tôi tin rằng sau khi đọc xong bài viết này, các bạn sẽ biết cách kiểm soát “công nghệ đen” này.
tiêu đề cấp đầu tiên
Bốn bước xây dựng SNARK
tiêu đề phụ
Bước đầu tiên: xác định trường hữu hạn
Trước khi xây dựng, đầu tiên chúng ta cần xác định một trường hữu hạn (Finite Field) có thể chứa tất cả các số mà chúng ta muốn tính toán. Theo thuật ngữ phổ thông, chúng ta cần chọn một số p rất, rất lớn, đảm bảo rằng số này lớn hơn tất cả các số trong bài toán mà chúng ta muốn giải.
Những người bạn đã tìm hiểu về mật mã RSA trước đây có thể quen thuộc với khái niệm này. Trường hữu hạn là thêm trần cho tất cả các con số của chúng ta và xác định không gian tính toán của toàn bộ hệ thống toán học, nó tương tự như trong máy tính, muốn tạo một biến lưu trữ các con số, chúng ta cần suy nghĩ xem mình có cần uint32_t (32 bit) hoặc Tương tự như uint64_t (64 bit). Tất cả các giá trị vượt quá trường hữu hạn sẽ tràn trực tiếp và sau đó quay trở lại và bắt đầu từ 0.
Trong thế giới toán học, thực tế có rất nhiều loại không gian tính toán đáp ứng đặc điểm này, phổ biến nhất là không gian số nguyên dương modulo một số nguyên tố lớn (số nguyên mod p) được sử dụng trong thuật toán RSA. Tìm một số p nói trên thực sự là một số nguyên tố lớn, và sau đó chúng ta có thể sử dụng nó để tạo ra một không gian tính toán.
tiêu đề phụ
Bước 2: Xây dựng mạch số học
Khi tìm được không gian số, việc tiếp theo chúng ta cần làm là diễn đạt bài toán muốn chứng minh để giải bằng các mạch phép toán.
Mạch hoạt động toán học là gì? Trước tiên chúng ta hãy xem xét các mạch logic truyền thống.
Hình trên mô tả một mạch cổng NAND (NAND). Không cần biết quá nhiều về tính hữu ích của mạch, những gì chúng ta có thể tìm thấy là hai bộ tín hiệu đầu vào lần lượt đi qua hai cổng logic cơ bản là AND và OR. Các cổng logic cơ bản như AND và OR là các khối xây dựng cơ bản của các mạch logic và chúng ta có thể triển khai bất kỳ logic phức tạp nào bằng cách nối và xếp chồng.
Điều này cũng đúng với các mạch hoạt động toán học, ngoại trừ mô-đun cơ bản đã thay đổi từ các cổng logic thành các hoạt động toán học. Bởi vì phép cộng và phép nhân là các phép toán cơ bản nhất, thông qua phép cộng và phép nhân, chúng ta gần như có thể thực hiện được tất cả các phương pháp tính toán khác, vì vậy chúng ta có thể chọn "cổng cộng" và "cổng nhân" làm mô-đun cơ bản trong mạch phép toán của mình. Bằng cách chồng các cổng số học, chúng ta có thể xây dựng một "mạch" các đa thức phức tạp.
Để hiểu rõ hơn về cổng thao tác ta thử chuyển cổng NAND trên từ mạch logic sang mạch thao tác toán học. (Giả sử rằng Inp0 và Inp1 giống như mạch logic ban đầu, chúng vẫn nhập tín hiệu logic 1/0.)
Trước tiên hãy xem xét cổng AND: AND thực ra rất đơn giản, vì kết quả của AND sẽ chỉ là 1 khi cả Inp0 và Inp1 đều là 1. Chúng tôi nhanh chóng phát hiện ra rằng cổng nhân sẽ là sự thay thế hoàn hảo cho cổng AND: kết quả của phép nhân sẽ chỉ là 1 nếu cả hai đầu vào đều là 1.
Sau khi giải quyết AND, hãy chuyển đổi NOT: NOT thực ra rất đơn giản, vì tín hiệu đầu vào chỉ có thể là 0 hoặc 1, miễn là tín hiệu đầu vào được trừ đi 1, kết quả sẽ ngược lại. Lưu ý rằng có một vấn đề là do chúng ta chỉ có phép cộng và phép nhân nên nếu cần thực hiện phép trừ thì chúng ta cần nhân tín hiệu đầu vào với hằng số -1 trước.
Sau khi chuyển đổi như vậy, chúng tôi đã chuyển đổi thành công mạch logic thành mạch logic kỹ thuật số. Đồng thời, vì chúng ta đã biết cách xây dựng AND và NOT, về mặt lý thuyết, chúng ta có thể mô đun hóa hai phần này và ghép bất kỳ logic phức tạp nào.
Nhìn thấy điều này, bạn có thể cảm thấy rằng mạch số học rất đơn giản và việc chuyển đổi sang mạch logic cũng rất đơn giản. Nhưng trên thực tế, điều này là do chúng ta đã giả định rằng đầu vào của mạch số học giống như mạch logic, là 0 hoặc 1. Trong một kịch bản thực tế, giá trị đầu vào của một cổng hoạt động có thể rất lớn (tùy thuộc vào kích thước của sự lựa chọn trường hữu hạn của chúng ta). vì vậy chúng ta phải tìm cáchHạn chế đầu vào cho mạch hoạt động của chúng tôi, do đó nó không chỉ có chức năng giống như mạch logic mà còn chỉ có thể lấy hai số [0,1] trong giá trị đầu vào.
Nhưng làm thế nào để sử dụng các cổng số học để biểu diễn một mối quan hệ như vậy? Vì mạch phép toán thực chất là một đa thức phức tạp (ví dụ mạch NAND ở hình trên trở thành Out = 1 - Inp0 * Inp1), nên chúng ta có thể biến đổi câu hỏi này: có thể tạo đa thức không,Chỉ khi một đầu vào thỏa mãn phạm vi giá trị [0,1], nó sẽ xuất ra 0?Cuối cùng, chúng tôi thấy rằng có một đa thức như vậy có thể đáp ứng yêu cầu này:
Chuỗi biểu thức trên có nghĩa là chỉ khi số n nằm trong khoảng này thì đa thức sau mới cho kết quả là 0. Nói cách khác, chúng ta có thể kết nối Inp0 và Inp1 nói trên với mạch hoạt động được chuyển đổi từ đa thức này,Miễn là kết quả đầu ra của mạch hoạt động này là 0, thì chúng ta có thể chắc chắn rằng đầu ra của mạch hoạt động NAND ở trên cũng đúng.
Có thể một số người hỏi, đa thức giới hạn giá trị trên chỉ có thể giới hạn một đầu vào, nhưng chúng ta có hai đầu vào, làm thế nào để giới hạn phạm vi giá trị của chúng cùng một lúc? Trên thực tế, câu trả lời rất đơn giản, chỉ cần sao chép cùng một đa thức và cộng hai đa thức lại với nhau.
Với 2 mạch này ta chỉ cần đảm bảo đầu ra của mạch ràng buộc bằng 0 thì mạch cổng NAND sẽ hoạt động bình thường.
Lưu ý một điều là do các cổng logic của chúng ta được xây dựng từ các cổng số học nên chúng ta sẽ thấy logic đóhoạt động rất chậmtiêu đề phụ
Bước 3: Chuyển đổi sang Mạch hoạt động toán học có thể chứng minh được
Khi chúng ta có khái niệm về mạch điện toán kỹ thuật số, chúng ta có thể ghép các mô-đun mạch khác nhau lại với nhau để tạo ra một mạch điện toán có thể được sử dụng làm bằng chứng.
Đầu tiên, hãy định nghĩaMột mạch hoạt động kỹ thuật số C(x, w) có thể được sử dụng làm bằng chứng, cấu trúc cụ thể như sau:
Nói một cách đơn giản, mạch C này có hai bộ đầu vào.
Tập hợp đầu vào đầu tiên có nhãn x, chúng tôi gọiđầu vào công khai, có nghĩa là mọi người sẽ biết giá trị của x. x này nói chung thể hiện đặc điểm của vấn đề muốn chứng minh và một số biến môi trường cố định.
Tập đầu vào thứ hai được gắn nhãn w, mà chúng ta gọi làđầu vào bí mật, hay còn gọi là nhân chứng. Bộ dữ liệu này là câu trả lời cho bên thực sự đã gửi bằng chứng và chỉ bên đã gửi bằng chứng mới biết được điều đó và không ai khác có thể lấy được.
Khi chúng tôi có một mạch C, mục tiêu của chúng tôi làChứng minh rằng C(x, w) = 0. Nói cách khác, nếu A và B biết rằng đầu ra của mạch phép toán C là 0 và đầu vào công khai là x, A cần chứng minh rằng cô ấy biết giá trị đầu vào riêng w cấu thành đầu ra này.
Nếu chúng ta thay thế khái niệm C(x, w) này vào ví dụ về cổng NAND được đề cập ở trên, chúng ta sẽ thấy rằng chỉ riêng cổng NAND là không đủ để trở thành một mạch chứng minh. Ta có thể định nghĩa lại bài toán muốn chứng minh:Nếu chúng ta biết rằng đầu ra của cổng NAND là 0 và một trong các đầu vào Inp0 là 1,A muốn chứng minh rằng cô ấy biết giá trị của một đầu vào khác Inp1. Trong quá trình chứng minh này, không chỉ cần đảm bảo rằng đầu ra của cổng NAND là chính xác mà còn phải đảm bảo rằng tất cả các giá trị đầu vào đều nằm trong phạm vi mà chúng tôi đã thống nhất trước.
Chúng tôi kết hợp sơ đồ đã thảo luận ở trên, kết nối đầu ra mạch NAND và mạch ràng buộc giá trị của chúng tôi với nhau để tạo thành mạch hoạt động C, x là Inp0, w là Inp1 và chúng tôi hạn chế đầu ra thành 0, do đó tạo thành một cổng NAND riêng tư hoàn chỉnh Nhập hệ thống chứng nhận.
Khi chúng tôi nhận được mạch chứng minh cuối cùng C, chúng tôi có thể tính toán độ phức tạp của mạch hoạt động này.
Nếu chúng ta muốn biết mức độ phức tạp của mạch thao tác kỹ thuật số C, chúng ta có thể mô tả độ phức tạp của nó bằng cách có bao nhiêu cổng thao tác trong đó. Nói chung, chúng tôi sẽ sử dụng để thể hiện. Giống như mạch chứng minh NAND đã đề cập ở trên, nó có lẽ là khoảng 10.
tiêu đề phụ
Bước 4: Hệ thống bằng chứng ngắn không tương tác (SNARK)
Khi chúng tôi có được mạch chứng minh cuối cùng C và x và w tương ứng qua bước thứ ba, quá trình chuẩn bị của chúng tôi gần như đã hoàn tất. Đối với phần còn lại, chúng tôi có thể chuyển giao cho thuật toán SNARK để tạo và xác minh bằng chứng của chúng tôi.
Đầu tiên, hãy xem định nghĩa chính thức của toàn bộ hệ thống bằng chứng không tương tác.
Một hệ thống SNARK thường bao gồm ba thuật toán cốt lõi: Thiết lập, Chứng minh và Xác minh.
Tạo thuật toán Cài đặt:
Thuật toán Thiết lập sẽ đưa mạch C xác định của chúng ta vào một loạt tiền xử lý (tiền xử lý), sau đó tạo ra hai bộ tham số. Sp là một tham số cho người chứng minh và Sv là người xác minh. Mục đích của các tham số này là để tạo điều kiện thuận lợi cho cả hai bên tạo và xác minh các bằng chứng ngắn. Nói chung, độ phức tạp của thuật toán tạo tỷ lệ thuận với độ phức tạp của mạch C, O(|C|).
Thuật toán chứng minh Chứng minh:
Không cần phải nói về thuật toán chứng minh, người chứng minh sẽ sử dụng thuật toán Chứng minh để tạo ra một bằng chứng, sau đó gửi bằng chứng cho người xác minh. Thuật toán Chứng minh sẽ sử dụng gần như tất cả dữ liệu khi tạo lại bằng chứng: dữ liệu được xử lý trước Sp, đầu vào công khai x và đầu vào riêng tư w. Chứng minh thu được có độ phức tạp không gian rất ngắn: |Π| = O(log|C|).
Thuật toán xác minh Xác minh:
Thuật toán xác minh cũng rất đơn giản. Người xác minh sẽ sử dụng thuật toán Xác minh để xác minh bằng chứng mà chúng tôi nhận được. Thuật toán này sẽ trả về giá trị 1/0, cho biết việc xác minh có được thông qua hay không. Trong quá trình xác minh, ngoài bằng chứng do bên kia cung cấp, chúng tôi cũng cần xử lý trước dữ liệu và thông tin đầu vào công khai x. Độ phức tạp xác minh cũng rất nhỏ, điển hình là O(|x| + log|C|).
Với ba thuật toán này, chúng ta có thể sử dụng một sơ đồ rất đơn giản để mô tả toàn bộ hệ thống chứng minh.
tiêu đề cấp đầu tiên
Ví dụ: Phạm vi đầu vào và đầu ra của các giao dịch riêng tư (Range Proof)
Các bạn đã đọc bài viết trước hẳn vẫn còn nhớ nếu chúng ta muốn thực hiện một giao dịch riêng tư (Giao dịch bí mật), chúng ta cần đính kèm ba bộ chứng từ khi kết thúc giao dịch:
Nhóm đầu tiên làLời hứa cá nhân, chứng minh mối quan hệ toán học giữa đầu vào và đầu ra.
Nhóm thứ hai làbằng chứng khoảng thời gian, cần chứng minh rằng các giá trị của đầu vào và đầu ra đều nằm trong khoảng các số nguyên dương.
Nhóm thứ ba làbằng chứng sở hữu, để chứng minh rằng người khởi xướng giao dịch thực sự có rất nhiều mã thông báo làm đầu vào.
Việc thực hiện lời hứa của Pederson đã được thảo luận trong bài viết trước. Bây giờ chúng ta đã hiểu cấu trúc bốn bước của chứng minh ngắn, chúng ta có thể xem cách thực hiện nó một cách chi tiếtbằng chứng khoảng thời gian。
Đầu tiên, chúng ta cần tìm mộtMạch toán phù hợpđể diễn tả điều muốn chứng minh. (Chúng tôi sử dụng trường hữu hạn của các số nguyên dương theo mặc định và chọn một số nguyên tố p rất lớn cho modulo.)
Nếu ta có số w và muốn chứng minh số w này không phải là số âm thì trước hết ta chứng minh nó phải nằm trong dãy các số nguyên dương. Vì xem xét rằng các số nguyên dương trong hệ thống máy tính thường không vượt quá 256 bit, chúng ta có thể làm yếu vấn đề:Chứng minh rằng một số w có giá trị trong khoảng 0-2^256.(Theo điều kiện này, số nguyên tố p được chọn bởi trường hữu hạn cần phải lớn hơn 2^256.)
Bây giờ chúng ta đã xác định được vấn đề cần giải quyết, chúng ta có thể bắt đầu suy nghĩ về cách biểu thị mối quan hệ giá trị này bằng phép cộng và phép nhân. Hãy nhớ trong chương trước, khi chúng ta nói về giá trị n trong khoảng từ 0 đến 1, chúng ta đã sử dụng n * (n - 1) = 0 để hạn chế phạm vi giá trị này.Theo cách tương tự, nếu chúng ta muốn ràng buộc có giá trị từ 0 đến 5, chúng ta có thể ràng buộc nó bằng một chuỗi phép nhân dài hơn:
Xem đến đây, bạn có thể đã biết cách hạn chế giá trị của w: chúng ta chỉ cần sử dụng cùng một phương pháp để khai triển phương trình này và nhân liên tục từ (w - 1) đến (w - 2^{256}) chứ không chỉ ĐƯỢC RỒI?
Nghe có vẻ đơn giản, nhưng các bạn cẩn thận sẽ thấy rằng trong mạch cuối cùng sẽ cóCó 2^256cổng nhân. Với rất nhiều phép nhân và không có phép cộng, độ phức tạp của mạch này đã là rất lớn. Ngay cả khi bạn chạy Thiết lập, bạn có thể không biết rằng mình sẽ chạy vào Năm Thân, vì vậy chúng tôi nói rằng phương pháp hạn chế này làkhông thực tế.
Sau đó, có cách nào để hạn chế không gian của số này w? chúng ta có thểKhéo léo sử dụng cấu trúc của số nhị phân.Vì chúng ta muốn quy định rằng w là một số nguyên và lớn hơn 0 nhưng nhỏ hơn 2^256, nên chúng ta có thể, ở dạng nhị phân,Chia w thành 256 bit, sau đó ràng buộc từng bit riêng biệt.Trong trường hợp này, kích thước của mạch cuối cùng chúng ta nhận được sẽ chỉ tỷ lệ thuận với số chữ số này có và sẽ không liên quan đến giới hạn trên tối đa của số này. Độ phức tạp đột ngột giảm xuống một mức độ lớn.
Nó đạt được như thế nào? Trước tiên, chúng tôi chia w thành 256 bit:
Bởi vì mỗi bit là nhị phân, chúng ta cần giới hạn không gian giá trị của mỗi bit thành 0 và 1:
Ràng buộc này yêu cầu 256 bản sao, mỗi bản cho một bit. Khi chúng tôi đã sẵn sàng các ràng buộc này, cuối cùng chúng tôi đảm bảo rằng tất cả các bit cùng nhau có thể được khôi phục về w ban đầu:
Chúng tôi kết hợp tất cả các mạch ràng buộc 256+1=257 đã đề cập ở trên và kết hợp chúng thành một đầu ra. Mạch được tạo ra cuối cùng là mạch C mà chúng ta có thể sử dụng để xây dựng hệ thống chứng minh. Nếu đầu ra của C là 0, thì số đại diện cho đầu vào phải thỏa mãn:
Số này là một số nguyên dương có thể được biểu diễn bằng số nhị phân 256 bit.
Số nhị phân 256 bit này thực sự là một số nhị phân. (chỉ có thể nhận giá trị 0 hoặc 1)
Tất cả các số nhị phân 256 bit này có thể được đặt cùng nhau để khôi phục số đã nhập.
Bằng cách khéo léo sử dụng các đặc điểm của nhị phân,tiêu đề cấp đầu tiên
Ví dụ: Quyền sở hữu Đầu vào Giao dịch Cá nhân
Sau khi giải quyết bằng chứng về khoảng thời gian, hãy hoàn thành bộ bằng chứng cuối cùng của giao dịch riêng tư: bằng chứng về quyền sở hữu, chứng minh rằng giá trị đầu vào của giao dịch riêng tư là hợp lý.
Những người bạn đã đọc bài viết trước nên biết rằng chúng tôi đã nói về hai hệ thống chứng minh quyền sở hữu các giao dịch cá nhân:
Giải pháp đầu tiên là một giao dịch có thể tham chiếu trực tiếp đến đầu ra của giao dịch trước đó, nhưng điều này sẽ dẫn đến vấn đề con gà và quả trứng: khó khăn nằm ở cách tạo giao dịch riêng tư đầu tiên. Giải pháp thứ hai là đính kèm một bằng chứng mới khác dưới mỗi giao dịch, chứng minh rằng số dư tài khoản của người dùng thực hiện giao dịch thực sự có số tiền đó.
tôi muốn nhấn mạnhSơ đồ bằng chứng thứ hai là chứng minh số dư tài khoản của người khởi tạo giao dịch ở trạng thái thế giới.
Trong nhiều kịch bản blockchain, trạng thái của toàn thế giới là một cuốn sổ cái khổng lồ. Mỗi dòng của sổ cái ghi lại số dư tài khoản của một người dùng nhất định.
Để thể hiện trạng thái của toàn thế giới một cách thuận tiện hơn, chúng ta thường sử dụng cây Merkle để biến sổ cái thế giới khổng lồ thành một loạt các giá trị băm Merkle ngắn gọn và gọn gàng. Bất cứ khi nào số dư của bất kỳ tài khoản nào thay đổi, hàm băm Merkle này sẽ thay đổi.
Một cây Merkle thực chất là một cây nhị phân, mỗi nút sẽ ghép các giá trị của hai nút con bên dưới lại với nhau và tính giá trị băm tương ứng là giá trị của chính nó. Để thuận tiện cho việc xây dựng cây Merkle, trước tiên chúng tôi sẽ thực hiện phép tính băm trên giá trị số dư gốc nhất, sau đó lưu trữ giá trị băm của chúng ở dưới cùng của cây Merkle.
Khi chúng ta xây dựng cây Merkle theo cách này, chúng ta có thể coi giá trị băm Merkle đầu ra là mộtCam kết: Chừng nào lời hứa không thay đổi, thì tình trạng hiện tại của thế giới không được thay đổi.Trong chuỗi khối, nếu chúng ta muốn ghi lại trạng thái của một danh sách dữ liệu dài, thường để tiết kiệm dung lượng, chúng ta sẽ ghi lại cam kết Merkle của tất cả dữ liệu trên chuỗi thay vì lưu trữ chính dữ liệu đó trên chuỗi.
Sau khi chúng tôi cam kết với tình trạng của thế giới, câu hỏi tiếp theo là:Nếu A là tài khoản 1 trong hình trên, hiện có 5 nhân dân tệ. Làm thế nào để A chứng minh với B rằng trong toàn bộ trạng thái thế giới, số dư của cô ấy thực sự là 5 nhân dân tệ?
Một phương pháp rất đơn giản là: A có thể gửi số dư của tất cả các tài khoản cho B, sau đó B sẽ tự thực hiện phép tính cam kết Merkle. Miễn là cam kết được tính toán của B bằng với cam kết của nhà nước thế giới hiện tại và A trình bày rằng số dư tài khoản của chính cô ấy thực sự là 5 nhân dân tệ, B có thể tin rằng A thực sự có 5 nhân dân tệ.
Nghe có vẻ là một phương pháp rất tốt, nhưng các vấn đề với phương pháp này là hiển nhiên trong nháy mắt. Có hàng trăm triệu người dùng trên thế giới này, nếu A cần gửi số dư tiền gửi hàng trăm triệu dòng cho B, huống chi B có thể tính toán cam kết này một cách hiệu quả, chỉ riêng lưu lượng mạng sẽ cạn kiệt. Và phương pháp chứng minh như vậy sẽ làm lộ thông tin số dư của tất cả người dùng và mọi người chắc chắn không sẵn lòng.
Vậy làm thế nào để chứng minh một cách hiệu quả rằng số dư của tài khoản 1 thuộc về trạng thái thế giới hiện tại? Tại thời điểm này, chúng ta có thể sử dụng các đặc điểm của cây Merkle để xây dựng bằng chứng Merkle.
Nếu chúng ta quan sát kỹ cây Merkle đã được cắt tỉa trong hình trên, chúng ta sẽ thấy rằng miễn là chúng ta chứng minh được rằng số dư của tài khoản 1 có thể hình thành cam kết trạng thái thế giới cuối cùng với các nút liền kề trong cây Merkle, thì chúng ta cũng có thể chứng minh được số dư của tài khoản 1 Nó thuộc về tình trạng hiện tại của thế giới.
Làm thế nào để làm nó? Hãy bắt đầu với số dư của tài khoản 1,Đi hết con đường lên cây Merkle.
Với số dư TK 1 thì ta tính được H1. Sau khi có H1, chúng tôi nhận thấy mình không cần biết số dư tài khoản 0, miễn là một giá trị của H0 có thể kết hợp để tạo ra H4. Theo cách tương tự, cuối cùng chúng ta có thể tạo cam kết Merkle của đỉnh——H6 bằng cách kết hợp với giá trị của H5. Cuối cùng, chúng ta chỉ cần gửi ba thứ để hoàn thành bằng chứng Merkle này: số dư của tài khoản 1, H0 và H5. Tất cả các giá trị băm còn lại có thể được tính toán trong quá trình xác minh. Đây là bằng chứng Merkle.
Chúng tôi có thể giảm đáng kể khối lượng bằng chứng thông qua bằng chứng Merkle và chúng tôi cũng có thể đảm bảo rằng số dư của những người dùng khác ở trạng thái thế giới không bị lộ trong quá trình chứng minh. Bằng chứng Merkle rất hữu ích trong mật mã, chỉ yêu cầu kích thước n để chứng minh rằng thứ gì đó nằm trong danh sách có độ dài N. Chúng tôi thường sử dụng bằng chứng Merkle để chứng minh rằng một tập hợp dữ liệu thuộc về một tệp lớn, người dùng thuộc về một tổ chức lớn, v.v.
Sau khi hiểu nguyên tắc chứng minh Merkle, chúng ta hãy xem cách chứng minh rằng A có thể chứng minh số dư của mình trong một giao dịch riêng tư.
Bản chất của bằng chứng Merkle là chúng ta có thểBắt đầu từ giá trị cần chứng minh, giá trị băm được tính cho đến hết và liên tục được hợp nhất với giá trị băm của các nút lân cận.Nhưng chúng tôi đã phát hiện ra một vấn đề rất nghiêm trọng: mặc dù chúng tôi có thể che giấu sự cân bằng của người khác trong trạng thái thế giới, chúng tôi vẫnBạn phải để lộ số dư của mình(Nếu không thì không có cách nào để tính giá trị băm đầu tiên H1). Điều này trái với bản chất của các giao dịch riêng tư của chúng tôi!
Lúc này, bạn cần sử dụng sức mạnh của SNARK.tiêu đề phụ
Bước 1: Chứng minh số dư Hash
Ở bước đầu tiên, chúng tôi sử dụng SNARK để chứng minh rằng số dư của tài khoản 1 có thể nhận được giá trị băm H1 sau khi chuyển qua hàm băm.
Vì chúng tôi muốn ẩn số dư của tài khoản 1, chúng tôi biểu thị số này bằng w. Trước khi áp dụng SNARK, chúng ta cũng cần thay đổi phương pháp mô tả bài toán để thuận tiện hơn trong việc diễn đạt bằng các mạch phép toán:
Giả sử bản thân A có bí mật w = số dư tài khoản 1. Cả A và B đều biết trước giá trị băm H1 của số dư tài khoản 1 (ta có thể ký hiệu là x). Ta có thể xây dựng mạch phép toán C: Hash(w) - x = 0. Nếu C(x, w) = 0 thì Hash(w) = x.
Để đơn giản hóa việc biểu diễn, chúng tôi sử dụng một mô-đun trừu tượng để biểu diễn hàm băm trên biểu đồ. Trong thực tế, chúng tôi thường sử dụng hàm băm SHA256. Sau khi chúng tôi nhận được mạch C cuối cùng, chúng tôi sử dụng thuật toán Thiết lập để tạo tham số, sau đó sử dụng thuật toán Chứng minh để tạo bằng chứng ngắn.
Qua bước này,Chúng tôi sẽ nhận được một x công khai và một bằng chứng và giá trị của x này là giá trị băm của số dư tài khoản 1.tiêu đề phụ
Bước 2: Hoàn thành bằng chứng Merkle từ H1
Bước trước cho phép chúng tôi có được H1 và cũng cung cấp bằng chứng rằng H1 thực sự được tạo ra từ trạng thái thế giới ban đầu. Những gì chúng ta phải làm bây giờ là bắt đầu từ H1 và kết hợp với H0 và H5 liền kề tương ứng để tạo ra một cam kết trạng thái thế giới mới. Nếu chúng ta so sánh cam kết được tạo với cam kết cũ được lưu trên chuỗi khối, thì chúng ta có thể tin rằng số dư của tài khoản 1 thực sự ở trạng thái thế giới.
Tóm lại, chúng tôi đã chia bằng chứng về quyền sở hữu thành hai bước, bước đầu tiên là chứng minh rằng bí mật w có thể được chuyển đổi thành x bằng hàm băm, sau đó chứng minh rằng công khai x thuộc về cây Merkle của toàn bộ trạng thái thế giới.tiêu đề cấp đầu tiên
Tóm tắt các giao dịch cá nhân
Nhìn thấy điều này, mọi người phải có một sự hiểu biết chung về cách các giao dịch riêng tư được thực hiện. Bây giờ hãy để tôi tóm tắt những gì A phải làm nếu cô ấy muốn thanh toán cho B một giao dịch riêng tư.
Đầu tiên, A cần gửi cho toàn bộ mạnggửi một giao dịch cá nhân, giao dịch này chứa người thực hiện và người nhận thanh toán của giao dịch, nhưng không có số lượng. Số lượng đầu vào và đầu ra ban đầu được thay thế bằng một vài chuỗi ký tự bị cắt xén.
Bên dưới giao dịch này, A cần đính kèm một cam kết Pederson để chứng minh rằng các số đầu vào và đầu ra bằng nhau.
Sau đó, A cần nối thêm một lần nữaBằng chứng khoảng thời gian được tạo bởi SNARK(Range Proof), chứng minh rằng các số đầu vào và đầu ra đều là các số nguyên dương lớn hơn 0.
Cuối cùng, A cần nối thêm mộtbằng chứng sở hữu, điều đó chứng tỏ rằng cô ấy thực sự sở hữu một tài khoản w để gửi tiền vào đó. Bằng chứng về quyền sở hữu này được chia thành hai phần, một phần là bằng chứng giá trị băm do SNARK tạo ra và phần còn lại là bằng chứng Merkle, chứng minh rằng giá trị băm trước đó thực sự thuộc về trạng thái của thế giới.
tiêu đề cấp đầu tiên
còn tiếp
Vì lý do không gian, lần này tôi sẽ dừng ở đây. Có lẽ mọi người đã nhìn thấy điều này và đã hiểu phần "chứng minh" của chứng minh không kiến thức.Bạn có thể biết mạch phép toán là gì, và sau đó làm cách nào để chúng ta chuyển đổi các bài toán thực tế thành mạch.
Tôi tin nhiều người sẽ tò mò, vậy ba thuật toán Setup, Prove và Verify hoạt động như thế nào? Trong số tiếp theo, chúng ta hãy tiếp tục tìm hiểu sâu để hiểu sâu hơn về các nguyên tắc đằng sau hệ thống bằng chứng SNARK.
đọc thêm
Như thường lệ, một phần của danh sách đọc được đưa ra ở cuối bài viết, và các bạn quan tâm có thể tìm hiểu thêm về nó:
IOS
Android