Làm cách nào để chuyển đổi bằng chứng tương tác thành bằng chứng không tương tác?

Tiêu đề gốc: " Làm cách nào để chuyển đổi bằng chứng tương tác thành bằng chứng không tương tác? 》

Tác giả gốc: Kang Shuiyue, Giám đốc điều hành của Fox Tech; Mạnh Huyền Cơ, nhà khoa học trưởng của Fox Tech

Lời nói đầu

Công nghệ chứng minh không có kiến thức trong mật mã được sử dụng rộng rãi trong thế giới web3, bao gồm điện toán bảo mật, zkRollup, v.v. Trong số đó, FOAKS được dự án Layer2 FOX sử dụng là thuật toán chứng minh không có kiến thức. Trong số hàng loạt ứng dụng kể trên, có hai thuộc tính cực kỳ quan trọng đối với thuật toán chứng minh không có kiến thức, đó là tính hiệu quả và tính tương tác của thuật toán.

Tầm quan trọng của hiệu quả thuật toán là hiển nhiên. Các thuật toán hiệu quả có thể giảm đáng kể thời gian chạy hệ thống, do đó giảm độ trễ của máy khách, đáng kể Để cải thiện người dùng kinh nghiệm và hiệu quả, đây cũng là lý do quan trọng khiến FOAKS cam kết đạt được thời gian chứng minh tuyến tính.

Mặt khác, từ góc độ mật mã, việc thiết kế các hệ thống chứng minh không có kiến thức thường dựa vào nhiều vòng chứng minh và người xác minh. Sự tương tác. Ví dụ, trong câu chuyện về “hang động không có kiến thức” được sử dụng trong nhiều bài báo khoa học phổ biến giới thiệu bằng chứng không có kiến thức, việc hiện thực hóa bằng chứng phụ thuộc vào nhiều vòng tương tác truyền thông tin giữa Alibaba (người cung cấp) và phóng viên (người xác minh). Nhưng trên thực tế, trong nhiều tình huống ứng dụng, việc dựa vào tương tác sẽ khiến hệ thống không còn khả dụng hoặc độ trễ tăng lên cực độ. Giống như trong hệ thống zkRollup, chúng tôi mong đợi người xác minh (tức là thư mục trong FOX) có thể tính toán giá trị bằng chứng chính xác cục bộ mà không cần dựa vào sự tương tác với người xác minh.

Từ quan điểm này, làm thế nào để chuyển đổi giao thức chứng minh không có kiến thức tương tác thành giao thức không tương tác là một câu hỏi rất có ý nghĩa. Trong bài viết này, chúng tôi sẽ giới thiệu quy trình FOX sử dụng phương pháp phỏng đoán Fiat-Shamir cổ điển để tạo ra các thách thức trong Brakedown nhằm triển khai các giao thức không tương tác.

Thách thức trong bằng chứng không có kiến thức

Thuật toán bằng chứng không có kiến thức sau Nó đã trở nên cực kỳ phổ biến với sự lan rộng của các ứng dụng.Trong những năm gần đây, nhiều thuật toán khác nhau bao gồm FOAKS, Orion, zk-stark, v.v. đã ra đời. Logic chứng minh cốt lõi của các thuật toán này, cũng như giao thức sigma ban đầu trong mật mã, là trước tiên người xác minh (Prover) gửi một giá trị nhất định đến người xác minh (Người xác minh) và người xác minh tạo ra một thử thách (Thử thách) thông qua các số ngẫu nhiên cục bộ và gửi giá trị này Một giá trị thử thách được tạo ngẫu nhiên sẽ được gửi đến người chứng minh và người chứng minh cần phải có kiến thức thực sự để đưa ra phản hồi vượt qua người xác minh với xác suất cao. Ví dụ, trong hang động không kiến thức, phóng viên ném một đồng xu và nói với Alibaba nên đi ra từ bên trái hay bên phải, "trái và phải" ở đây là một thách thức đối với Alibaba. Nếu anh ta thực sự biết câu thần chú, anh ta sẽ nhất định có thể đi ra khỏi cờ vây theo hướng yêu cầu, nếu không có một nửa khả năng thất bại.

Ở đây chúng tôi nhận thấy rằng việc tạo Thử thách là một bước rất quan trọng. Nó có hai yêu cầu, ngẫu nhiên và không thể đoán trước được bởi người thực hiện. Đầu tiên, tính ngẫu nhiên đảm bảo tính chất xác suất của nó. Điểm thứ hai, nếu người chứng minh có thể dự đoán giá trị thử thách, điều đó có nghĩa là tính bảo mật của giao thức bị phá hủy. Người chứng minh có thể vượt qua xác minh mà không cần biết. Chúng ta có thể tiếp tục phép loại suy. Nếu Alibaba có thể dự đoán phía nào thì phóng viên yêu cầu anh ta đến ra ngoài, hắn sẽ cho dù không có bùa chú, ngươi có thể trước tiến vào bên đó, kết quả vẫn là thông qua thỏa thuận.

Vì vậy, chúng tôi cần một cách để cho phép người chứng minh tạo ra một số ngẫu nhiên không thể đoán trước như vậy tại địa phương, đồng thời, nó có thể được xác minh bởi Xác thực người xác minh, để có thể triển khai giao thức không tương tác.

Hàm băm

Hàm băm Cái tên này có thể không còn xa lạ với us Cho dù đó là một bài toán để khai thác trong giao thức đồng thuận POW của Bitcoin, nén lượng dữ liệu, xây dựng mã xác minh tin nhắn, v.v., các hàm băm đều có mặt. Trong các giao thức khác nhau được đề cập ở trên, các thuộc tính khác nhau của hàm băm thực sự được sử dụng.

Cụ thể, các thuộc tính của hàm băm an toàn bao gồm các điểm sau:

Khả năng nén: Hàm băm xác định có thể nén thông báo có độ dài bất kỳ thành độ dài cố định.

Tính hợp lệ: Cho một đầu vào x, có thể dễ dàng tính được đầu ra h(x).

Khả năng chống va chạm: Cho đầu vào x1, chúng tôi hy vọng tìm được đầu vào khác x2, x1x2, h (x1) = h(x2), thật khó.

Lưu ý rằng nếu hàm băm thỏa mãn khả năng chống va chạm thì nó phải thỏa mãn tính chất một chiều. Nghĩa là, với đầu ra y, việc tìm x sao cho h(x) = y là điều khó khăn. Trong mật mã học, về mặt lý thuyết không thể xây dựng một hàm thỏa mãn tuyệt đối các tính chất một chiều, nhưng về cơ bản, hàm băm có thể được coi là hàm một chiều trong các ứng dụng thực tế.

Bằng cách này, chúng ta có thể thấy rằng các ứng dụng nêu trên tương ứng với một số thuộc tính khác nhau của hàm băm. Đồng thời, chúng tôi nói, các hàm băm cũng đóng một vai trò rất quan trọng trong việc cung cấp tính ngẫu nhiên. Mặc dù hiện tại chưa thể xây dựng được bộ tạo số ngẫu nhiên hoàn hảo cần có trong lý thuyết mật mã, nhưng các hàm băm cũng có thể đóng vai trò này trong thực tế. Điều này cung cấp cho chúng ta phương pháp phỏng đoán Fiat-Shamir ( Heuristic) kỹ thuật được giới thiệu sau này cung cấp cơ sở.

Phương pháp phỏng đoán Fiat-Shamir (Heuristic)

Trên thực tế, phương pháp phỏng đoán Fiat-Shamir Công thức (Heuristic) sử dụng hàm băm để thực hiện thao tác băm trên tập lệnh được tạo trước đó nhằm thu được một giá trị, giá trị này được sử dụng làm giá trị thử thách.

Vì hàm băm H được coi là hàm ngẫu nhiên nên thử thách phải được chọn thống nhất một cách ngẫu nhiên, độc lập với thông tin công khai của người chứng minh Và cam kết. Phân tích bảo mật tin rằng Alice không thể dự đoán đầu ra của H và chỉ có thể coi nó như một lời tiên tri. Trong trường hợp này, xác suất để Alice phản hồi đúng mà không tuân theo giao thức (đặc biệt khi cô ấy không biết bí mật cần thiết) tỷ lệ nghịch với kích thước của phạm vi H.

Hình 1: Sử dụng Fiat -Shamir Heuristic triển khai FOAKS không tương tác bằng chứng không tương tác

Trong phần này, chúng tôi trình bày cụ thể phương pháp heuristic Fiat-Shamir trong giao thức FOAKS Ứng dụng này chủ yếu được sử dụng để tạo ra phần Brakedown của thử thách nhằm đạt được FOAKS không tương tác.

Trước hết, chúng ta thấy rằng trong số các bước tạo ra bằng chứng trong Brakedown, các bước cần được thử thách là "kiểm tra gần đúng và phần chứng minh phần Merkle Tree (bạn đọc có thể tham khảo bài viết trước “Tìm hiểu về phanh giao thức cam kết đa thức trong FOAKS”). Đối với điểm đầu tiên, quy trình ban đầu là người chứng minh cần một vectơ ngẫu nhiên do người xác minh tạo ra ở đây. Quá trình tính toán được thể hiện trong hình bên dưới:

Hình 2: Kiểm tra phanh trong FOAKS bằng chứng không tương tác

Bây giờ chúng ta sử dụng hàm băm và để người chứng minh tự tạo ra vectơ ngẫu nhiên này.

Cho 0=H(C1,R, r0,r1), tương ứng, trong tính toán xác minh của người xác minh cũng cần thiết để thêm Bước này tính 0. Theo cấu trúc này, có thể thấy rằng trước khi đưa ra cam kết, người chứng minh không thể dự đoán trước giá trị thử thách nên không thể “gian lận” dựa trên giá trị thử thách trước, tức là tạo ra giá trị cam kết sai tương ứng. Đồng thời, theo hàm băm Tính ngẫu nhiên của hàm đầu ra, giá trị thử thách này cũng thỏa mãn tính ngẫu nhiên.

Đối với điểm thứ hai, đặt I=H(C1,R, r0,r1,c1,y1,c0,y0).

Chúng tôi sử dụng mã giả để cung cấp chức năng chứng minh và xác minh trong cam kết đa thức Brakedown không tương tác đã sửa đổi, cam kết này cũng được sử dụng trong hệ thống FOAKS Chức năng.

chức năng PC. Commit():

Phân tích w dưới dạng ma trận kk. Bộ chứng minh tính toán cục bộ mã tensor mã hóa C1, C2, C1 là ma trận kn, C2 là ma trận nn.

cho tôi [n] làm

Tính toán gốc cây Merkle Roott=Merkle.Commit(C2[:,i])

Tính toán Merkle gốc cây R=Merkle.Commit([Root0,...Rootn-1]) và xuất R dưới dạng cam kết.

hàm PC. Prover(, X, R)

Người chứng minh tạo ra một vectơ ngẫu nhiên 0Fk bằng cách tính toán : 0=H(C1,R, r0,r1)

Sự gần gũi: c0=i=0k -10[ i]C1[:,i],y0=i=0k-10[i]w[i]

Tính nhất quán: c1=i=0k-1r0[i]C1[:,i],y1=i=0k-1r0[i]w[i]

Nhà cung cấp gửi c1,y1,c0,y0 tới người xác minh.

Prover tính vectơ I là thử thách, trong đó I=H(C1,R, r0,r1,c1,y1,c0,y0)

dành cho idxI

Nhà cung cấp gửi C1 [:,idx] và bằng chứng cây Merkle của Rootidx cho C2 [:,idx] trong R tới người xác minh

PC chức năng. VERIFY_EVAL(X,X,y=(X),R)

Gần: idxI ,C0[idx]==<0,C1[:,idx]>và EC(y0)==C0

Tính nhất quán: idxI,C1[idx]==<r0,C1[:,idx]>và EC(y1)==C1

y==<r1, y1>

idxI, EC (C1[:,idx]) nhất quán với ROOTidx và bằng chứng cây Merkle của ROOTidx là hợp lệ.

Chấp nhận đầu ra nếu tất cả các điều kiện trên được giữ nguyên. Nếu không thì đầu ra sẽ từ chối.

Kết luận

Nhiều thuật toán chứng minh không có kiến thức dựa vào sự tương tác giữa người chứng minh và người xác minh khi bắt đầu thiết kế, nhưng điều này Tương tác Giao thức chứng minh chính thức không phù hợp để sử dụng trong các tình huống ứng dụng theo đuổi hiệu quả cao và yêu cầu chi phí truyền thông mạng lớn, chẳng hạn như bảo vệ quyền riêng tư dữ liệu trên chuỗi và zkRollup, v.v. Thông qua phương pháp heuristic Fiat-Shamir (Heuristic), người chứng minh có thể tạo ra một "thử thách" số ngẫu nhiên cục bộ mà không phá hủy tính bảo mật của giao thức và nó có thể được người chứng minh xác minh. Theo phương pháp này, FOAKS cũng triển khai các bằng chứng không tương tác và áp dụng chúng vào hệ thống.

Bài viết này là từ một bài gửi và không thể hiện quan điểm của BlockBeats  

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia