Bằng chứng không có kiến thức: Nó giống như phép thuật, nhưng tôi sẽ giải thích nó

Giả sử Peggy cần chứng minh cho Victor thấy rằng cô ấy đang sở hữu một bí mật mà không tiết lộ bí mật đó. Liệu cô ấy có thể làm như vậy theo cách thuyết phục Victor rằng cô ấy thực sự biết bí mật không? Đây là câu hỏi trọng tâm của một trong những quy trình mã hóa mạnh mẽ nhất mà chúng tôi có thể sử dụng trong các hệ thống nhận dạng: bằng chứng không có kiến thức (ZKP) .

Ví dụ, giả sử rằng Peggy có bằng lái xe kỹ thuật số và muốn chứng minh với Victor, người pha chế rượu, rằng cô ấy trên 21 tuổi mà không cần phải đưa bằng lái xe hoặc thậm chí cho anh ta xem ngày sinh của cô ấy. ZKP cho phép Peggy chứng minh bằng lái xe của cô ấy và nói rằng cô ấy ít nhất 21 tuổi theo cách thuyết phục Victor mà không cần Peggy phải tiết lộ bất cứ điều gì khác (tức là không có kiến thức dư thừa ).

Vấn đề này lần đầu tiên được khám phá bởi các nhà nghiên cứu MIT Shafi Goldwasser, Silvio Micali và Charles Rackoff vào những năm 1980 như một cách chống rò rỉ thông tin. Mục đích là giảm lượng thông tin bổ sung mà người xác minh, Victor, có thể tìm hiểu về người chứng minh, Peggy.

Một cách để hiểu cách thức hoạt động của ZKP là câu chuyện về Hang động Alibaba, được xuất bản lần đầu bởi các nhà mật mã học Quisquater, Guillou và Berson1. Sơ đồ sau đây cung cấp một minh họa.

Hang Alibaba có hai lối đi, được dán nhãn A và B, tách ra một lối đi duy nhất nối với lối vào. Peggy sở hữu một mật mã bí mật cho phép cô mở cánh cửa nối A và B. Victor muốn mua mật mã nhưng sẽ không trả tiền cho đến khi chắc chắn rằng Peggy biết nó. Peggy sẽ không chia sẻ nó với Victor cho đến khi anh ấy trả tiền.

Thuật toán để Peggy chứng minh cô ấy biết mật mã được tiến hành như sau:

• Victor đứng bên ngoài hang động trong khi Peggy bước vào và chọn một trong những lối đi. Victor không được phép xem Peggy đi con đường nào.
• Victor vào hang và gọi ngẫu nhiên "A" hoặc "B".
• Peggy đi ra từ đúng lối đi vì cô ấy có thể dễ dàng mở khóa cửa bất kể lựa chọn nào khi bước vào.
• Tất nhiên, Peggy có thể chỉ gặp may mắn và đoán đúng nên Peggy và Victor lặp lại thí nghiệm nhiều lần.

Nếu Peggy luôn có thể quay lại bằng bất kỳ lối đi nào mà Victor chọn, thì khả năng Peggy thực sự biết mật mã ngày càng tăng. Sau 20 lần thử, có ít hơn một phần triệu cơ hội Peggy chỉ đoán được lá thư nào Victor sẽ gọi. Đây là bằng chứng xác suất cho thấy Peggy biết bí mật.

Thuật toán này không chỉ cho phép Peggy thuyết phục Victor rằng cô ấy biết mật mã mà còn thực hiện theo cách đảm bảo Victor không thể thuyết phục bất kỳ ai khác mà Peggy biết mật mã. Giả sử Victor ghi lại toàn bộ giao dịch. Điều duy nhất mà người quan sát nhìn thấy là Victor đang gọi những lá thư và Peggy xuất hiện từ đường hầm bên phải. Người quan sát không thể chắc chắn rằng Victor và Peggy không thống nhất trước về một chuỗi ký tự để đánh lừa người quan sát.

Vì vậy, trong khi Peggy không thể phủ nhận với Victor rằng cô ấy biết bí mật, cô ấy có thể phủ nhận rằng mình biết bí mật đó với các bên thứ ba khác. Điều này đảm bảo rằng bất cứ điều gì cô chứng minh cho Victor đều nằm giữa họ và Victor không thể tiết lộ nó — ít nhất là theo cách mật mã chứng minh nó đến từ Peggy. Peggy giữ quyền kiểm soát cả bí mật của mình và sự thật là cô ấy biết điều đó.

Khi chúng ta nói "không có kiến thức" và nói về việc Victor không học được gì ngoài mệnh đề được đề cập, điều đó không hoàn toàn đúng. Trong hang động của Alibaba, Peggy chứng minh rằng cô biết bí mật. Nhưng có nhiều điều khác mà Victor biết được về Peggy mà ZKP không thể làm được. Ví dụ, Victor biết rằng Peggy có thể nghe thấy anh ấy, nói ngôn ngữ của anh ấy, bước đi và hợp tác. Anh ta cũng có thể tìm hiểu những điều về hang động, chẳng hạn như mất bao lâu để mở khóa cửa. Peggy biết được những điều tương tự về Victor. Vì vậy, thực tế là bằng chứng là kiến thức xấp xỉ bằng 0 chứ không phải kiến thức bằng 0 hoàn toàn .

Hệ thống ZKP

Ví dụ về Hang động của Alibaba là một cách sử dụng ZKP rất cụ thể, cái được gọi là bằng chứng kiến thức không có kiến thức . Peggy đang chứng minh rằng cô ấy biết (hoặc sở hữu thứ gì đó). Tổng quát hơn, Peggy có thể muốn chứng minh nhiều sự thật cho Victor. Chúng có thể bao gồm các cụm từ mệnh đề hoặc thậm chí các giá trị. ZKP cũng có thể làm điều đó.

Để hiểu cách chúng ta có thể chứng minh các mệnh đề với kiến thức bằng không, hãy xem xét một ví dụ khác, đôi khi được gọi là Bài toán triệu phú xã hội chủ nghĩa . Giả sử Peggy và Victor muốn biết liệu họ có được trả lương công bằng hay không. Cụ thể, họ muốn biết liệu họ có được trả số tiền như nhau hay không nhưng không muốn tiết lộ mức lương cụ thể theo giờ của mình cho nhau hoặc thậm chí cho bên thứ ba đáng tin cậy. Trong trường hợp này, Peggy không chứng minh rằng cô ấy biết một bí mật, thay vào đó, cô ấy đang chứng minh một mệnh đề bình đẳng (hoặc bất bình đẳng).

Để đơn giản, giả sử rằng Peggy và Victor đang được trả mức lương là 10 USD, 20 USD, 30 USD hoặc 40 USD mỗi giờ.

Thuật toán hoạt động như thế này:

• Peggy mua bốn hộp khóa và dán nhãn chúng là 10 đô la, 20 đô la, 30 đô la và 40 đô la.
• Cô ấy vứt chìa khóa của mọi hộp, ngoại trừ chiếc có ghi tiền lương của cô ấy.
• Peggy đưa tất cả những chiếc hộp có khóa cho Victor, người đã đặt riêng một tờ giấy có dấu "+" vào khe trên cùng của chiếc hộp có ghi tiền lương của anh ấy. Anh ta đặt một phiếu có dấu "-" vào tất cả các ô khác.
• Victor trả lại những chiếc hộp cho Peggy, người đã sử dụng chìa khóa riêng của cô ấy để mở chiếc hộp có ghi tiền lương của cô ấy trên đó.
• Nếu cô ấy tìm thấy dấu "+" thì họ sẽ kiếm được số tiền tương tự. Nếu không, họ kiếm được một số tiền khác. Cô ấy có thể sử dụng điều này để chứng minh sự thật cho Victor.

Đây được gọi là một sự chuyển giao không rõ ràng và chứng minh mệnh đề VictorSalary = PeggySalary đúng hay sai khi không có kiến thức (tức là không tiết lộ bất kỳ thông tin nào khác).

Để điều này có hiệu quả, Peggy và Victor phải tin tưởng rằng người kia sẽ đến và nêu rõ mức lương thực sự của họ. Victor cần tin tưởng rằng Peggy sẽ vứt ba chiếc chìa khóa còn lại. Peggy phải tin tưởng rằng Victor sẽ chỉ bỏ một phiếu có dấu "+" vào hộp.

Giống như chứng chỉ kỹ thuật số cần PKI để tạo dựng niềm tin vượt xa những gì có thể chỉ với chứng chỉ tự cấp, ZKP mạnh hơn trong một hệ thống cho phép Peggy và Victor chứng minh sự thật từ những điều người khác nói về họ, không chỉ những gì họ nói về họ. chúng tôi. Ví dụ: thay vì Peggy và Victor tự khẳng định mức lương của mình, giả sử họ có thể dựa vào một tài liệu đã ký từ bộ phận nhân sự để đưa ra khẳng định của mình để cả hai biết rằng người kia đang nêu rõ mức lương thực sự của họ. Thông tin xác thực có thể xác minh cung cấp một hệ thống sử dụng ZKP để chứng minh nhiều sự kiện khác nhau một mình hoặc phối hợp, theo những cách mang lại sự tin cậy vào phương pháp và sự tin cậy vào dữ liệu.

ZKP không tương tác

Trong các ví dụ trước, Peggy đã có thể chứng minh mọi điều với Victor thông qua một loạt tương tác. Để ZKP trở nên thiết thực, sự tương tác giữa người chứng minh và người xác minh phải ở mức tối thiểu. May mắn thay, một kỹ thuật có tên SNARK cho phép chứng minh không có kiến thức không tương tác.

SNARK có các thuộc tính sau (từ đó chúng lấy được tên của chúng):

• Ngắn gọn: kích thước của thông điệp nhỏ so với độ dài của bằng chứng thực tế.
• Không tương tác : ngoài một số thiết lập, người chứng minh chỉ gửi một tin nhắn đến người xác minh.
• Luận cứ: đây thực sự là một lập luận cho thấy điều gì đó là đúng, không phải là một bằng chứng như chúng ta hiểu về mặt toán học. Cụ thể, về mặt lý thuyết, người chứng minh có thể chứng minh những tuyên bố sai khi có đủ sức mạnh tính toán. Vì vậy, SNARK là "âm thanh tính toán" chứ không phải "âm thanh hoàn hảo".
• của Kiến thức: người chứng minh biết sự thật được đề cập.

Thông thường, bạn sẽ thấy "zk" (có nghĩa là không có kiến thức) được đính ở mặt trước để cho biết rằng trong quá trình này, người xác minh không học được gì ngoài những sự thật đã được chứng minh.

Toán học cơ bản của zkSNARK liên quan đến tính toán đồng hình trên các đa thức bậc cao. Nhưng chúng ta có thể hiểu cách zkSNARK hoạt động mà không cần biết cơ sở toán học đảm bảo rằng chúng hoạt động tốt. Nếu bạn muốn biết thêm chi tiết về toán học, tôi khuyên bạn nên giới thiệu "zkSNARKs in a Nutshell" của Christian Reitwiessner .

Một ví dụ đơn giản, giả sử Victor được cấp một hàm băm sha256 , H , có giá trị nào đó. Peggy muốn chứng minh rằng cô ấy biết một giá trị s sao cho sha265(s) == H mà không tiết lộ s cho Victor. Chúng ta có thể định nghĩa hàm C nắm bắt mối quan hệ:

 C(x, w) = ( sha256(w) == x )

Vì vậy, C(H, s) == true , trong khi các giá trị khác của w sẽ trả về false .

Việc tính toán zkSNARK yêu cầu ba hàm G , P và V . G là trình tạo khóa lấy tham số bí mật gọi là lambda và hàm C rồi tạo hai khóa chung, khóa chứng minh pk và khóa xác minh vk . Chúng chỉ cần được tạo một lần cho một hàm nhất định C . Tham số lambda phải bị hủy sau bước này vì nó không cần thiết nữa và bất kỳ ai có nó đều có thể tạo ra bằng chứng giả .

Hàm chứng minh P lấy đầu vào là khóa chứng minh pk , đầu vào công khai x và nhân chứng riêng (bí mật) w . Kết quả của việc thực thi P(pk,x,w) là một bằng chứng, prf , rằng người chứng minh biết một giá trị của w thỏa mãn C .

Hàm xác minh V tính toán V(vk, x, prf) đúng nếu prf chứng minh là đúng và ngược lại là sai.

Quay lại với Peggy và Victor, Victor chọn một hàm C đại diện cho điều anh ấy muốn Peggy chứng minh, tạo một số ngẫu nhiên lambda và chạy G để tạo các khóa chứng minh và xác minh:

 (pk, vk) = G(C, lambda)

Peggy không được học giá trị của lambda . Victor chia sẻ C , pk và vk với Peggy.

Peggy muốn chứng minh rằng cô ấy biết giá trị s thỏa mãn C cho x = H . Cô chạy hàm chứng minh P sử dụng các giá trị này làm đầu vào:

 prf = P(pk, H, s)

Peggy trình bày prf chứng cho Victor, người điều hành chức năng xác minh:

 V(vk, H, prf)

Nếu kết quả là đúng thì Victor có thể yên tâm rằng Peggy biết giá trị s .

Hàm C không cần phải giới hạn ở hàm băm như chúng ta đã làm trong ví dụ này. Trong giới hạn của toán học cơ bản, C có thể khá phức tạp và liên quan đến bất kỳ số lượng giá trị nào mà Victor muốn Peggy chứng minh cùng một lúc.

Bài viết này là một đoạn trích từ cuốn sách Học nhận dạng kỹ thuật số của tôi, được xuất bản bởi O'Reilly Media.

Ghi chú

1. Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). Cách giải thích các giao thức không có kiến thức cho con bạn (PDF). Những tiến bộ trong mật mã học – CRYPTO '89: Kỷ yếu. Ghi chú bài giảng về Khoa học máy tính. 435. trang 628–631. doi:10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.