Bài viết này đến từBài viết này đến từPhòng thí nghiệm Ambi (ID: SECBIT)
, tác giả Guo Yu, được Odaily sao chép với sự ủy quyền.
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md
Bài viết này đã được cập nhật lên Github
“Thử thách đôi khi là dấu hiệu Chúa tin tưởng bạn.” Thử thách đôi khi là dấu hiệu Chúa tin tưởng bạn. - D. Todd Christofferson
Series 1: Làm quen với "Zero Knowledge" và "Proof"
Series 2: Tìm hiểu về "Mô phỏng"
Series Ba: Đi tìm "Kiến thức"
Tương tác và Thử thách
Các hệ thống chứng minh không có kiến thức mà chúng tôi đã giới thiệu trước đây đều là "tương tác", yêu cầu người xác minh Bob cung cấp một hoặc một số "số ngẫu nhiên" để thách thức trong quá trình tương tác, chẳng hạn như "vấn đề ba màu bản đồ" (xem "Chuỗi 2" ) , người xác minh Bob cần "liên tục" chọn ngẫu nhiên một bên để thách thức câu trả lời của Alice cho đến khi Bob hài lòng và xác suất gian lận của Alice sẽ giảm dần "theo cấp số nhân". Và "cơ sở" để Bob tin vào bằng chứng phụ thuộc vào việc con số ngẫu nhiên mà Bob chọn có đủ ngẫu nhiên hay không. Nếu Alice có thể dự đoán trước con số ngẫu nhiên của Bob, thảm họa sẽ xảy ra, thế giới thực sẽ suy thoái thành "thế giới lý tưởng", và Alice có thể ngay lập tức nâng cấp thành "máy giả lập" để đánh lừa Bob bằng siêu năng lực.
Trong "Series 3", chúng tôi đã phân tích giao thức Schnorr. Trong giao thức, mặc dù người xác minh Bob chỉ cần chọn một số ngẫu nhiên c để thách thức Alice và yêu cầu cô ấy tính giá trị z, nhưng Bob không được để Alice có khả năng dự đoán giá trị của c.Bất kỳ kiến thức nào, nếu không, Alice cũng sẽ biến thành một trình giả lập.
Tầm quan trọng của các số ngẫu nhiên là hiển nhiên:
Các thử thách số ngẫu nhiên là "gốc rễ của niềm tin" cho các bằng chứng tương tác không có kiến thức.
Tuy nhiên, "quá trình tương tác" sẽ giới hạn các tình huống ứng dụng. Điều gì sẽ xảy ra nếu các bằng chứng không kiến thức tương tác có thể bị biến thành "không tương tác"? Nó sẽ rất, rất thú vị. Cái gọi là không tương tác có thể được coi là quy trình chứng minh "một vòng", nghĩa là Alice trực tiếp gửi bằng chứng cho Bob để xác minh.
Bằng chứng không kiến thức không tương tác, tiếng Anh là Non-Interactive Zero Knowledge, viết tắt là NIZK. Có nghĩa là toàn bộ bằng chứng được mã hóa thành một "chuỗi", có thể được viết trên một tờ giấy và gửi đến bất kỳ người xác minh nào theo ý muốn thông qua nhiều phương thức như email và công cụ trò chuyện. Chuỗi thậm chí có thể được đặt trên Github cho mọi người để tải xuống bất cứ lúc nào xác minh.
Trong thế giới blockchain, "NIZK" có thể được sử dụng như một phần của giao thức đồng thuận. Bởi vì một giao dịch yêu cầu nhiều thợ mỏ xác minh. Hãy tưởng tượng, nếu người gửi giao dịch và mỗi người khai thác phải tương tác và để những người khai thác thử thách, thì quá trình đồng thuận sẽ cực kỳ chậm. Bằng chứng không kiến thức không tương tác có thể được phát trực tiếp tới tất cả các nút khai thác, cho phép chúng tự xác minh.
Một số bạn có thể hỏi: Chỉ một thợ mỏ thách đấu thôi chưa đủ sao? Mã hóa tập lệnh tương tác giữa người khai thác và người gửi giao dịch thành bằng chứng, sau đó phát nó cho những người khai thác khác, sau đó những người khai thác khác sẽ trực tiếp tin rằng quy trình thử thách là đáng tin cậy, phải không? Tuy nhiên, rõ ràng là công cụ khai thác tương tác đầu tiên cần được tin cậy là bên thứ ba đáng tin cậy, bên thứ ba? Không có vẻ như là một ý tưởng tốt ...
Thay vì bằng chứng tương tác không có kiến thức, chúng tôi sẽ nói trực tiếp "NIZK" bên dưới, điều này có vẻ lý tưởng và không có bên thứ ba nào tạo ra sự khác biệt.
Sự nhầm lẫn gây ra bởi "không tương tác"
Bằng chứng không có kiến thức không tương tác, NIZK, nếu chúng tồn tại, mạnh hơn nhiều so với bằng chứng tương tác.
Bằng chứng tương tác chỉ có thể được tin cậy bởi một người xác minh; trong khi NIZK có thể được tin cậy bởi nhiều người xác minh, thậm chí là tất cả mọi người.
Bằng chứng tương tác chỉ có thể có hiệu lực tại thời điểm tương tác; trong khi NIZK sẽ luôn có hiệu lực.
NIZK không chỉ có thể mở rộng không gian mà còn cả thời gian
Nghe có vẻ đẹp, phải không? Nhưng,……
Lặp lại một kết luận từ phần trước:
Các thử thách số ngẫu nhiên là "gốc rễ của niềm tin" cho các bằng chứng tương tác không có kiến thức.
Nhưng nếu NIZK thua quá trình thử thách, hậu quả là gì?
Chúng tôi đã nhắc lại bằng chứng "không kiến thức" (tham khảo "Dòng 2"). Quá trình chứng minh cần xây dựng một trình giả lập (thuật toán), mô phỏng này cũng tương tác với người xác minh (Bob) trong một thế giới lý tưởng và người xác minh Bob không Có khả năng phân biệt xem bên kia là Alice thật hay giả lập.
Nếu bây giờ bạn xem xét tính không tương tác trong NIZK, nếu "tôi" cho "bạn" xem một mảnh giấy có bằng chứng X "đúng" được viết trên đó và nếu "bạn" thực sự tin tôi sau khi đọc bài báo này; và bởi vì giao thức là "không có kiến thức", thì nếu "tôi" được thay thế bằng một trình giả lập, thì trình giả lập cũng có thể "giả mạo" bằng chứng sai Y, điều này cũng có thể thuyết phục được "bạn".
Ok, đây là vấn đề:
Làm thế nào để bạn phân biệt giữa X và Y, cái nào đúng và cái nào sai? Tất nhiên bạn không thể phân biệt được, vì giao thức là không có kiến thức, bạn không thể phân biệt được
Tôi cũng có thể chỉ cho bạn Y. Điều đó không có nghĩa là "tôi" có thể lừa dối bạn sao?
Nó có mâu thuẫn không? Xin hãy suy nghĩ trong hai phút ở đây.
(hai phút sau...)
Bởi vì NIZK không có tương tác, không có quy trình thử thách. Tất cả các quy trình chứng minh đều có Alice tính toán và viết. Về lý thuyết, Alice có thể viết bất cứ thứ gì cô ấy muốn và không ai có thể ngăn cản cô ấy. Ví dụ: Alice viết "thế giới lý tưởng" là sai bằng chứng của Y
Có lẽ, những người bạn hiểu sâu về trình giả lập sẽ tìm thấy điểm mấu chốt ở đây: trình giả lập chỉ phải xây dựng Y trong "thế giới lý tưởng", nghĩa là, thứ xấu xa như Y chỉ có thể tồn tại trong "thế giới lý tưởng" và không thể đạt được "thế giới thực" là một thảm họa cho thế giới.
tiếp tục suy nghĩ ...
Ngoài ra còn có một vấn đề sâu xa hơn, xin hãy nhớ lại "vấn đề ba màu bản đồ", lý do cốt lõi khiến người giả lập không thể làm điều ác trong "thế giới thực" là anh ta có siêu năng lực "quay ngược thời gian" trong thế giới lý tưởng. Và trong "thế giới thực" không có ma thuật đen như vậy. "Không tồn tại" của thế giới thực là chìa khóa.
Hơn nữa, không có tương tác trong NIZK, dẫn đến hậu quả nghiêm trọng, trình giả lập không có cách nào sử dụng siêu năng lực "tua ngược thời gian", và tất nhiên có vẻ như nó không thể phân biệt được hành vi của người châm ngôn ở hai thế giới.
Nói cách khác, nếu chúng ta đối mặt với bất kỳ hệ thống NIZK nào, có vẻ như "người giả lập" khó có thể đứng vững trên mặt đất, dường như chỉ có thể rơi vào thế giới và trở thành một người phàm bình thường. Nếu, tôi đã nói nếu, theo suy luận này, giả sử rằng người giả lập không còn siêu năng lực, điều đó có nghĩa là Alice và người giả lập không khác nhau, Alice cũng có thể trở thành người giả lập, sau đó tiếp tục suy luận, Alice có thể ở trong " thế giới thực" Nếu Bob bị lừa một cách tùy tiện trong quá trình này, thì hệ thống bằng chứng này không còn giá trị nữa, vì nó mất đi "độ tin cậy" của nó. Kết luận: Bất kỳ NIZK nào cũng không đáng tin cậy.
Chắc có gì đó sai sai ở đây...
Trong quá trình phân tích ở trên, chúng tôi đã đề cập đến việc thiếu các thách thức tương tác. Thật vậy, nếu Bob không tham gia vào quá trình tạo bằng chứng của Alice, thì mọi bit có trong bằng chứng đều do Alice cung cấp và có vẻ như bản thân "bằng chứng" không có bất kỳ "gốc" nào để Bob tin tưởng. Điều này dường như không có ý nghĩa "theo trực giác".
Điều đó có nghĩa là nếu không có sự tham gia của Bob, thì "hoàn toàn" không có cách nào để thiết lập "gốc của niềm tin"? Nền tảng của niềm tin có thể đến từ đâu nữa?
Câu trả lời là "bên thứ ba"!
Đợi đã..., không phải chỉ có hai bên trong giao thức tương tác sao? Alice và Bob, bên thứ ba ở đâu?
Bên thứ ba cần phải được giới thiệu theo một cách đặc biệt, và có nhiều hơn một phương pháp, trước tiên chúng ta hãy nghiên cứu phương pháp thứ nhất.
(Tears: Bạn không nói hay sao, chúng ta không giới thiệu bên thứ ba sao?)
Xem lại giao thức Schnorr
Hãy xem người bạn cũ của chúng ta—giao thức Schnorr, là một giao thức ba bước: ở bước đầu tiên, Alice gửi một lời hứa, sau đó ở bước thứ hai, Bob gửi một thử thách số ngẫu nhiên, và ở bước thứ ba, Alice đáp lại thách thức.
Hãy xem cách biến giao thức Schnorr ba bước thành một bước.
c = Hash(PK, R)
Nhìn vào bước thứ hai của giao thức Schnorr, Bob cần đưa ra một số thử thách ngẫu nhiên c. Ở đây chúng ta có thể để Alice sử dụng công thức sau để tính toán số thử thách, để đạt được mục đích loại bỏ bước thứ hai của giao thức.
Trong đó R là điểm đường cong elip mà Alice đã gửi cho Bob và PK là khóa chung. Bạn có thể xem kỹ công thức này để tính c bằng thuật toán Hash. Công thức này phục vụ hai mục đích:
Trước khi Alice tạo cam kết R, không có cách nào để dự đoán c, ngay cả khi c cuối cùng được chọn bởi Alice trong ngụy trang
c Được tính bằng hàm Hash, nó sẽ được phân bổ đều trong một trường số nguyên và có thể được sử dụng dưới dạng số ngẫu nhiên (Lưu ý: Bây giờ hãy hiểu điều này, chúng ta sẽ thảo luận sâu hơn sau)
Xin lưu ý: Alice không bao giờ có thể dự đoán c trước khi tạo R, nếu không, Alice có siêu năng lực "đảo ngược thời gian" để ngụy trang, để cô ấy có thể tùy ý đánh lừa Bob.
Và hàm Hash được bảo mật bằng mật mã là "một chiều", chẳng hạn như SHA256, SHA3, blake2, v.v. Theo cách này, mặc dù c được tính bởi Alice, Alice không có khả năng gian lận bằng cách chọn c. Bởi vì ngay khi Alice tạo R, c tương đương với việc cố định. Chúng tôi cho rằng Alice, một người phàm, không có khả năng đảo ngược phép tính Hash trong "thế giới thực".
Nhìn vào hình trên, chúng ta sử dụng hàm Hash để kết hợp giao thức Schnorr ba bước thành một bước. Alice có thể gửi trực tiếp: (R, c, z). Và vì Bob có PK nên Bob có thể tự tính toán c, nên Alice chỉ cần gửi (R, z).
Chúng tôi đã làm biến dạng sơ đồ trên một chút và thu được sơ đồ "chữ ký số". Cái gọi là chữ ký điện tử có nghĩa là "tôi" đưa ra một chuỗi cho "bạn", chẳng hạn như "Mặt trời khuất núi, sông Hoàng Hà chảy ra biển", sau đó để chứng minh rằng bài thơ này đã được trình bày bởi tôi, tôi cần phải ký một cái gì đó. Điều này có thể chứng minh rằng danh tính của tôi được kết nối với bài thơ này.
Chữ ký số từ quan điểm của NIZK
Nói một cách dễ hiểu, sơ đồ chữ ký số tương đương với việc chứng minh (1) rằng tôi có khóa riêng và (2) rằng khóa riêng và thông báo đã được liên kết với phép tính.
Trước tiên tôi phải chứng minh danh tính của mình, vì vậy điều này rất đơn giản, đây là chức năng của giao thức Schnorr, có thể chứng minh tuyên bố "Tôi có khóa riêng" cho bên kia. Và quy trình chứng minh này là không có kiến thức: không có kiến thức nào về "khóa riêng tư" được tiết lộ.
m = "Vậy nó có quan hệ như thế nào với bài thơ Đường này? Chúng tôi sửa đổi quá trình tính toán c:"
c = Hash(m, R)
Mặt trời khuất núi Hoàng Hà chảy ra biển
Ở đây, để đảm bảo kẻ tấn công không thể giả mạo chữ ký theo ý muốn, người ta giả định rằng bài toán logarit rời rạc (DLP) và hàm Hash thỏa mãn khả năng chống tiền giả thứ cấp (Secondary Preimage Resistance).
Lưu ý: Nói một cách chính xác, để đảm bảo tính không thể giả mạo của chữ ký số, cần phải chứng minh rằng giao thức Schnorr đáp ứng thuộc tính mạnh hơn của "Simulation Soundness". Đối với điều này, vui lòng tham khảo [2]
Hình trên là sơ đồ chữ ký số nổi tiếng - Schnorr signature scheme [1]. Ở đây có một cách tối ưu khác, cái mà Alice gửi cho Bob không phải là (R,z) mà là (c,z), bởi vì R có thể được tính thông qua c,z.
Lưu ý: Tại sao đây là "tối ưu hóa"? Hiện tại, có thuật toán Shanks, thuật toán Lambda và thuật toán rho của Pollard để tấn công các đường cong elip. Hãy nhớ rằng độ phức tạp của thuật toán của chúng là khoảng [3] và n là số chữ số trong kích thước của trường hữu hạn. Giả sử chúng ta sử dụng một trường hữu hạn rất gần với 2^256, nghĩa là, z là 256 bit, khi đó kích thước của nhóm đường cong elip gần bằng 256 bit, do đó căn bậc hai của 2^256 là 2^ 128, vì vậy Độ bảo mật của nhóm đường cong elip 256 bit chỉ là 128 bit. Sau đó, chỉ 128 bit là đủ cho thử thách số c. Theo cách này, Alice gửi c sẽ tiết kiệm không gian hơn là gửi R, và cái sau yêu cầu ít nhất 256 bit. Hai giá trị của c và z cộng lại có tổng cộng 384 bit. So với sơ đồ chữ ký ECDSA phổ biến, nó có thể tiết kiệm 1/4 không gian quý giá. Giờ đây, nhóm phát triển Bitcoin đã sẵn sàng thay đổi sơ đồ chữ ký ECDSA thành sơ đồ chữ ký giống Schnorr—muSig[4], sơ đồ này có thể hỗ trợ đa chữ ký và tổng hợp linh hoạt hơn.
Phương pháp sử dụng hàm Hash để thay đổi hệ thống bằng chứng tương tác thành phương pháp không tương tác được gọi là phép biến đổi Fiat-Shamir [5], được đề xuất vào năm 1986 bởi Amos Fiat và Adi Shamir, những người kỳ cựu về mật mã.
Xây Dựng Lại Lòng Tin - Random Prophecy Wizard
Như đã đề cập trước đó, nếu không có thách thức, có vẻ như "nền tảng niềm tin" của bằng chứng đã bị mất. Trong lược đồ chữ ký Schnorr, hàm Hash đảm nhận vai trò “người thách thức”, vai trò này có một cái tên rất hàn lâm: “Random Oracle” (Nhà tiên đoán ngẫu nhiên) [6].
Nhưng tại sao lại sử dụng Hash ở đây? Trên thực tế, khi Alice muốn tạo các số ngẫu nhiên công khai, cô ấy cần một thứ gọi là "lời tiên tri ngẫu nhiên". Nó là gì?
Đó là thời gian động não!
Ta tưởng tượng ở “thế giới thực” có một “thần tiên” trên trời đang cầm một biểu mẫu gồm hai cột, cột bên trái là một chuỗi, cột bên phải là một con số. Bất kỳ ai, kể cả bạn và tôi, kể cả Alice và Bob, đều có thể gửi chuỗi cho "yêu tinh".
Sau khi yêu tinh lấy được chuỗi sẽ kiểm tra cột bên trái của bảng xem có chuỗi như vậy trong bảng không, sẽ xảy ra 2 tình huống như sau:
Tình huống 1: Nếu không tìm thấy chuỗi ở cột bên trái, yêu tinh sẽ tạo ra một "số ngẫu nhiên thực sự", sau đó ghi chuỗi và số ngẫu nhiên vào bảng, sau đó trả lại số ngẫu nhiên cho người phàm trên mặt đất.
Trường hợp 2: Nếu cột bên trái có ghi chuỗi này, yêu tinh sẽ trực tiếp trả lại số ở cột bên phải xuống đất.
Bạn sẽ thấy sprite này hoạt động giống như một trình tạo số ngẫu nhiên, nhưng nó rất khác, sự khác biệt là khi chúng ta gửi cùng một chuỗi, nó sẽ trả về cùng một số. Yêu tinh này là "nhà tiên tri ngẫu nhiên" huyền thoại.
Trong quá trình hợp nhất giao thức Schnorr, thứ chúng ta thực sự cần là một thuật sĩ tiên tri ngẫu nhiên như vậy, không phải hàm Hash. Sự khác biệt giữa hai là gì? Sự khác biệt là:
Nhà tiên tri ngẫu nhiên trả về một số ngẫu nhiên "đúng" với phân phối nhất quán mỗi lần cho một chuỗi mới
Kết quả được tính toán bởi hàm Hash không phải là một số thực sự ngẫu nhiên với phân phối nhất quán
Vậy tại sao hàm Hash được sử dụng sớm hơn? Điều này là do trong thế giới thực, các nhà tiên tri ngẫu nhiên thực sự không tồn tại! Tại sao? Trên thực tế, hàm Hash không thể tạo ra các số thực sự ngẫu nhiên, bởi vì hàm Hash là một thuật toán "xác định" và không có đại lượng ngẫu nhiên nào khác được đưa vào ngoại trừ các tham số.
Và một hàm Hash với cường độ bảo mật bằng mật mã "dường như" có thể hoạt động như một lời tiên tri ngẫu nhiên "giả". Sau đó, giao thức bảo mật kết hợp cần thêm một giả định bảo mật mạnh bổ sung, đó là:
Giả thuyết: Hàm Hash được bảo mật bằng mật mã có thể xấp xỉ "tiên tri ngẫu nhiên" huyền thoại
Bởi vì giả định này không thể được chứng minh, chúng ta chỉ có thể tin tưởng vào giả định này hoặc sử dụng nó như một tiên đề. Bên cạnh đó, các thuộc tính chống va chạm tổng quát của hàm Hash xác định rằng đầu ra của nó có thể mô phỏng các số ngẫu nhiên. Đồng thời, trong nhiều trường hợp (không phải tất cả), rất khó để tấn công hàm Hash, vì vậy nhiều nhà mật mã học mạnh dạn sử dụng nó.
Một mô hình bảo mật không sử dụng giả định này được gọi là "mô hình tiêu chuẩn" và một mô hình bảo mật sử dụng giả định này tất nhiên không thể được gọi là "mô hình phi tiêu chuẩn". Nó có một thuật ngữ hay là "mô hình tiên tri ngẫu nhiên".
Có hai loại người khác nhau trên thế giới, những người thích đậu phụ ngọt và những người không thích. Tương tự như vậy, có hai loại người viết mật mã trên thế giới, những người thích mô hình tiên tri ngẫu nhiên và những người không thích mô hình tiên tri ngẫu nhiên [6].
Cơ sở cấu trúc - Yêu tinh bị bắt cóc
Sau khi giao thức Schnorr trải qua quá trình chuyển đổi Fiat-Shamir, nó có thuộc tính NIZK. Điều này khác với SHVZK mà chúng tôi đã chứng minh, SHVZK yêu cầu người xác minh phải trung thực, trong khi NIZK không còn bất kỳ yêu cầu phi thực tế nào đối với người xác minh, bởi vì người xác minh không tham gia vào tương tác và cái gọi là vấn đề yêu cầu người xác minh trung thực. người xác minh không còn tồn tại.
Lưu ý: Điều gì xảy ra nếu người xác minh Bob không trung thực? Sau đó, Bob có thể trích xuất kiến thức của Alice. Nhưng đối với giao thức Schnorr ba bước, liệu nó có đáp ứng được "không kiến thức" hay không vẫn chưa được biết. Chúng tôi chỉ chứng minh rằng nó thỏa mãn một tính chất tương đối yếu trong Chuỗi 3: SHVZK.
Tuy nhiên, khi giao thức Schnorr được chuyển đổi thành một hệ thống bằng chứng không kiến thức không tương tác, nó thực sự trở thành "không kiến thức".
Tuy nhiên, câu hỏi của bạn cũng có thể đến, khẳng định này nghe có vẻ hợp lý, bạn có thể chứng minh được không?
Hết giờ, "Cuihua, bật trình giả lập"
Làm thế nào để sử dụng phương pháp giả lập để xây dựng một "thế giới lý tưởng"? Bạn có thể nghĩ về nó, trước đây chúng tôi đã sử dụng "ngược thời gian" và sửa đổi siêu năng lực của "băng chuyền số ngẫu nhiên" để cho "người giả lập" gian lận. Nhưng không có tương tác, có nghĩa là: không thể sử dụng siêu năng lực "quay ngược thời gian", băng chuyền số ngẫu nhiên của Bob không tồn tại, cũng không thể sử dụng siêu năng lực "xáo trộn băng chuyền"!
Nhưng giả lập luôn phải có một loại “siêu năng lực” nào đó, để nó có thể xây dựng “cái gốc” của niềm tin
(Nếu trình giả lập có khả năng gian lận mà không có siêu năng lực, điều đó tương đương với việc chứng minh tính không đáng tin cậy của giao thức).
Đến đây chắc mọi người cũng đoán ra rồi, giả lập phải làm gì trên "random oracle".Trước tiên, hãy xem xét việc xây dựng một "thế giới lý tưởng" để chứng minh "không có kiến thức". Trong một thế giới lý tưởng, trình giả lập đã "bắt cóc" "yêu tinh" chịu trách nhiệm đưa ra lời tiên tri. Khi Bob hỏi yêu tinh về một số ngẫu nhiên, yêu tinh đã không đưa ra một số ngẫu nhiên thực sự mà đưa nó cho Zlice (trình giả lập giả vờ là Alice) Một con số được chuẩn bị trước (cũng phù hợp với phân phối nhất quán và đảm bảo không thể phân biệt được), "thần đèn" không còn cách nào khác là trả lại cho Bob một con số trông có vẻ ngẫu nhiên nhưng thực chất lại có một cửa hậu.
Cái gọi là cửa sau có nghĩa là con số này do chính Zlice chọn trước.
Bước 1: Zlice chọn ngẫu nhiên z, chọn ngẫu nhiên c và tính R'=z*G - c*PK.
Bước 2: Zlice viết c và (m, R') vào bảng sprite.
Bước 3: Zlice gửi chữ ký (c,z) cho Bob.
Bước 4: Bob tính toán R=z*G - c*PK, và gửi (m, R) cho yêu tinh, và yêu tinh trả về c'. Lưu ý rằng ở đây R' được tính toán của Bob và R' được tính toán của Zlice là bằng nhau.
Bước 5: Bob xác minh rằng c ?= c', để xem liệu số ngẫu nhiên do yêu tinh trả về có bằng với số ngẫu nhiên do bên kia gửi hay không. Nếu chúng bằng nhau, chữ ký xác minh sẽ vượt qua; nếu không, việc xác minh sẽ thất bại.
Bằng cách bắt cóc "yêu tinh", Zlice cũng có thể dự đoán trước con số ngẫu nhiên, điều này có thể đạt được hiệu quả tương tự như quay ngược thời gian.
Chúng tôi đã chứng minh "sự tồn tại" của Zlice giả lập, vì vậy chúng tôi đã chứng minh NIZK ở trên.
sk = (z1 - z2)/(c1 - c2)
Tiếp theo, chúng tôi chứng minh "độ tin cậy" của giao thức này. Hãy tưởng tượng rằng trong một "thế giới lý tưởng" khác, một thứ gọi là "máy trích xuất" cũng đã bắt cóc yêu tinh. Khi Alice ngây thơ hỏi "yêu tinh" về một số ngẫu nhiên, "yêu tinh" đã trả lại c1 và "người trích xuất" nhìn trộm c1 từ bàn của yêu tinh. Sau khi Alice tính được z1, thì "trình trích xuất" vẫn có thể kích hoạt siêu sức mạnh của "thời gian đảo ngược", hãy để Alice quay lại bước thứ hai và hỏi lại "yêu tinh" về một số ngẫu nhiên, chuỗi do Alice gửi rõ ràng giống với chuỗi được gửi lần đầu tiên, (R, m ) . Theo logic, vì (R, m) đã được viết trong "cột bên trái" của trang tính ma, nên một "sprite" trung thực sẽ trả về c1. Tuy nhiên, "người trích xuất" đã bắt cóc sprite và anh ta đã thay đổi "cột bên phải" tương ứng với hàng (R, m) trong bảng thành một số khác c2. Sau khi Alice tính toán một z2 khác, trình trích xuất hoàn thành nhiệm vụ và tính toán sk khóa riêng của Alice thông qua phương trình sau:
Chuyển đổi Fiat-Shamir - từ Public-Coin sang NIZK
Không chỉ đối với giao thức Schnorr, mà đối với bất kỳ "giao thức Public-Coin" nào, phép biến đổi Fiat-Shamir có thể được sử dụng để "nén" toàn bộ giao thức thành một tương tác một bước, tức là một hệ thống bằng chứng không tương tác. kỹ thuật chuyển đổi lần đầu tiên xuất phát từ Bài báo "Làm thế nào để chứng minh bản thân: Giải pháp thực tế cho các vấn đề về nhận dạng và chữ ký." của Amos Fiat và Adi Shamir đã được xuất bản tại Hội nghị tiền điện tử năm 1986 [5]. Người ta cũng nói rằng kỹ thuật này đến từ Manuel Blum[6].
Xin nhắc lại, trong giao thức Public-coin, trình xác thực Bob chỉ thực hiện một loại việc, đó là tạo một số ngẫu nhiên và thách thức Alice. Thông qua phép biến đổi Fiat-Shamir, mỗi "hành vi thách thức" của Bob có thể được thay thế bằng một "lời tiên tri ngẫu nhiên".
Trong triển khai cụ thể, tiên tri ngẫu nhiên cần sử dụng hàm băm có cường độ bảo mật bằng mật mã (bạn không thể chọn ngẫu nhiên, bạn phải sử dụng hàm băm bảo mật bằng mật mã) và các tham số của hàm băm phải là tất cả các đầu vào ngữ cảnh trước đó. Sau đây là một sơ đồ ví dụ, bạn có thể nhanh chóng hiểu được cách thực hành chuyển đổi Fiat-Shamir này.
Như đã đề cập trước đó, trong một hệ thống bằng chứng không tương tác, bên thứ ba cần được giới thiệu để xây dựng "gốc" của sự tin cậy, để Bob có thể hoàn toàn tin tưởng vào bằng chứng do Alice xây dựng. Ở đây, bên thứ ba là "yêu tinh", theo tiếng lóng học thuật là "Nhà tiên tri ngẫu nhiên". Yêu tinh này không phải là bên thứ ba thực sự, mà là bên thứ ba ảo, tồn tại ở cả "thế giới thực" và "thế giới lý tưởng". Trong "thế giới thực", yêu tinh là một người đàn ông đẹp trai có trách nhiệm và ít nói, nhưng trong "thế giới lý tưởng", nó sẽ bị bắt cóc bởi "người giả lập".
Giao thức Public-Coin còn có một cái tên rất hay là "Trò chơi Arthur-Merlin"...
Nhìn vào bức ảnh trên, "áo choàng trắng" bên trái là Merlin (pháp sư Merlin), và anh chàng đẹp trai với thanh kiếm ở giữa là King Arthur (King Arthur), hai nhân vật đến từ truyền thuyết châu Âu thời trung cổ - Hiệp sĩ Bàn tròn của Vua Arthur.
Arthur là một vị vua thiếu kiên nhẫn luôn mang theo một đồng xu, còn Merlin là một pháp sư có phép thuật với sức mạnh tính toán vô hạn, đến phần đối thoại nhưng vì nhà vua lười biếng nên mỗi lần chỉ tung một đồng xu, sau đó "thử thách" ảo thuật gia, và ảo thuật gia cần phản ứng kịp thời, và cần khiến nhà vua tin vào phán đoán của chính mình sau k hiệp đấu. Vì Merlin có phép thuật nên mọi đồng xu do Vua Arthur ném ra đều có thể được nhìn thấy bởi Merlin[7].đây là với chúng tôi trong"Loạt một"
Hệ thống bằng chứng tương tác (viết tắt là IP) được đề cập trong phần này hơi giống, nhưng khác. IP được Goldwasser, Micali và Rackoff (viết tắt là GMR) chính thức đề xuất vào năm 1985 và khả năng chứng minh của nó bao trùm một lớp lớn các vấn đề phức tạp về tính toán. Sự khác biệt là trong định nghĩa về IP, cả Prover và Verifier đều là máy Turing có thể tung đồng xu và Verifier có thể bí mật tung đồng xu và giấu chúng khỏi Prover; trong khi trong trò chơi Arthur-Merlin, nhà vua chỉ có thể tung đồng xu A, không chỉ vậy, mà Merlin sẽ luôn biết kết quả của việc tung đồng xu.
Tuy nhiên, phép biến đổi Fiat-Shamir chỉ có thể chứng minh tính bảo mật theo "mô hình tiên tri ngẫu nhiên" và liệu quá trình sử dụng hàm Hash để nhận ra tiên tri ngẫu nhiên có an toàn hay không là thiếu bằng chứng bảo mật. Không chỉ vậy, giao thức bảo mật theo "mô hình tiên tri ngẫu nhiên" có thể không an toàn và một số ví dụ ngược lại đã được tìm thấy [8]; thật không may, S. Goldwasser và Y. Tauman đã chứng minh vào năm 2003 rằng phép biến đổi Fiat-Shamir có bảo mật phản ví dụ trong chính nó [9]. Nhưng điều này không có nghĩa là không thể sử dụng phép biến đổi Fiat-Shamir mà phải hết sức cẩn thận trong quá trình sử dụng, không thể áp dụng một cách mù quáng.
Tuy nhiên, người ta không thể cưỡng lại sự cám dỗ của phép biến đổi Fiat-Shamir, được sử dụng cực kỳ rộng rãi. Điều đáng nói là các phép biến đổi Fiat-Shamir có rất nhiều trong các sơ đồ khác nhau của zkSNARK bằng chứng không kiến thức không tương tác cho mục đích chung phổ biến nhất. Ví dụ: bạn có thể quen thuộc với Bulletproofs (chống đạn) và có một số chương trình bằng chứng không kiến thức cho mục đích chung hiện không quá nổi tiếng, chẳng hạn như Hyrax, Ligero, Supersonic, Libra, v.v. (chúng tôi sẽ theo dõi và giải thích từng cái một).
Thận trọng: Ý nghĩa bảo mật trong Chuyển đổi Fiat-Shamir
Trong quá trình chuyển đổi Fiat-Shamir, hãy đặc biệt chú ý đến các tham số được cung cấp cho hàm Hash. Trong quá trình triển khai mã thực tế, có những trường hợp một số tham số của hàm Hash bị bỏ qua:
Ví dụ: trong A, Hash(A), B, Hash(B), hàm Hash thứ hai bỏ lỡ tham số A và cách đúng phải là A, Hash(A), B, Hash(A,B). Ví dụ: trong hệ thống bỏ phiếu điện tử SwissPost-Scytl của Thụy Sĩ, mã triển khai của chuyển đổi Fiat-Shamir đã nhiều lần bỏ sót các tham số lẽ ra phải tồn tại, khiến kẻ tấn công không chỉ có thể làm mất hiệu lực các lá phiếu theo ý muốn, và các lá phiếu có thể được làm giả theo ý muốn để đạt được mục đích gian lận [10]. Vì vậy, trong kỹ thuật thực hiện, hãy chú ý.
Những độc giả cẩn thận có thể nhìn lại chữ ký Schnorr và bạn sẽ thấy rằng thuật toán Hash trong chữ ký Schnorr dường như đã bỏ sót một tham số PK, đây không phải là phép biến đổi Fiat-Shamir nghiêm ngặt, được gọi là phép biến đổi Fiat-Shamir yếu [11 ].Tuy nhiên, không có vấn đề bảo mật nào trong trường hợp đặc biệt này [3], vui lòng không bắt chước trẻ vị thành niên tùy ý.
Gần đây, một số học giả đã bắt đầu nghiên cứu cách chứng minh nghiêm ngặt tính bảo mật của chuyển đổi Fiat-Shamir theo mô hình chuẩn, hiện tại họ đưa ra các giả định bảo mật mạnh bổ sung hoặc chứng minh nó cho một giao thức cụ thể, nhưng có vẻ như không có nhiều tiến triển.
Sức mạnh của sự tương tác
Chuyện kể rằng vào năm 1985, khi luận án của bộ ba GMR được STOC'85 chấp nhận sau nhiều lần từ chối, thì một công trình khác tương tự cũng được STOC'85 chấp nhận cùng thời điểm, đó là László Babai từ Đại học Roland, Hungary và Bài báo "Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes" được viết bởi Shlomo Moran từ Viện Công nghệ Israel [7] đã giới thiệu giao thức tương tác Public-coin (như tên cho thấy, chỉ Trình xác minh tung đồng xu công khai).
Phương pháp của Vua Arthur rất đơn giản, khẳng định của Merlin được kiểm tra bằng những thử thách "ngẫu nhiên" lặp đi lặp lại, điều này phù hợp với trực giác mà chúng tôi đã mô tả trước đó: sử dụng những thử thách ngẫu nhiên để xây dựng "gốc rễ" của niềm tin. Babai đã chứng minh một kết luận thú vị trong bài báo: AM[k]=AM[2], trong đó k đại diện cho số lượng tương tác và tác động của nhiều tương tác tương đương với hai tương tác. Cái gọi là hai lần tương tác có nghĩa là: Arthur gửi đi khiêu chiến dãy số, sau đó Merlin hồi đáp.
Chú thích: Còn có một loại vấn đề thuộc về MA, loại vấn đề này trình tự tương tác không giống với AM, ở MA, Merlin trước tiên đưa ra chứng minh, sau đó Arthur tung đồng xu kiểm tra. Người ta đã chứng minh rằng các vấn đề mà MA có thể xử lý là một tập hợp con của AM.
Không chỉ vậy, Babai còn mạnh dạn đoán: AM[poly] tương đương với IP. Đây là một khẳng định kỳ diệu: nhà vua lười biếng, ông ta chỉ cần lật một đồng xu đa thức để thách thức thành công nhà ảo thuật và sức mạnh biểu đạt của phương pháp này hoàn toàn tương đương với hệ thống bằng chứng tương tác IP do GMR mô tả. Chắc chắn rồi, tại hội nghị STOC'86, một bài báo của S. Goldwasser và M. Sipser đã chứng minh điều này, AM[poly] == IP[12].
Điều này có nghĩa là: "thử thách ngẫu nhiên" công khai lặp đi lặp lại có sức mạnh vô hạn và nó tương đương với bất kỳ hệ thống bằng chứng tương tác nào. Tuy nhiên, mối quan hệ giữa AM[poly] và các lớp phức tạp tính toán khác là điểm nóng nghiên cứu tiếp theo.
AM[poly] == IP == PSPACE
Ba năm sau, vào cuối tháng 11 năm 1989, cách đây đúng 30 năm, nhà mật mã học trẻ tuổi Noam Nisan đã gửi một email, gửi những kết luận học thuật tạm thời của mình cho một số nhà mật mã học, rồi anh chạy sang Nam Mỹ trong kỳ nghỉ. Nhưng anh không bao giờ nghĩ rằng email này sẽ kích nổ một cuộc cạnh tranh học thuật khốc liệt trong lịch sử, với một nhóm đông đảo M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund, v.v. . Giới tinh hoa bắt đầu nhập cuộc, họ thảo luận với nhau ngày đêm, thi nhau công bố kết quả nghiên cứu của mình. Cuối cùng, vào ngày 26 tháng 12, đúng một tháng, Adi Shamir đã chứng minh được kết luận sau:
Nó giải thích các đặc điểm lý thuyết tính toán của khái niệm "bằng chứng hiệu quả" và giải thích sức mạnh tính toán được bao phủ bởi khái niệm "hệ thống bằng chứng tương tác".
Lưu ý: Lớp NP là một tập hợp con của lớp PSPACE. Lớp NP quen thuộc hơn với mọi người và lớp sau liên quan đến các chiến lược giành chiến thắng trong trò chơi hoặc cờ vua [13].
Và L. Babai sau đó đã viết một bài báo có tên "Email và sức mạnh bất ngờ của sự tương tác" (Email và sức mạnh bất ngờ của sự tương tác) [14], được trình bày chi tiết trong cả tháng này trong "Tương tác qua email", và thông tin chi tiết về "bằng chứng tương tác".
Chuỗi tham chiếu công khai - một "gốc của niềm tin" khác
Vâng, bạn đã đọc đúng đó, lại có "bên thứ ba" ở đây! Mặc dù bên thứ ba không trực tiếp tham gia chứng minh, nhưng anh ta phải đảm bảo độ tin cậy của quá trình tạo chuỗi ngẫu nhiên. Quá trình tạo CRS còn được gọi là "Thiết lập đáng tin cậy", đây là điều mà mọi người yêu thích và ghét. Rõ ràng, đưa một bên thứ ba vào một kịch bản trong thế giới thực có thể là một vấn đề đau đầu. Chính xác thì CRS được sử dụng để làm gì? Niềm tin của Trusted Setup bắt đầu từ đâu? Phần này sẽ được dành cho bài viết tiếp theo trong loạt bài này.
còn tiếp
còn tiếp
Kiến thức không tương tác không tương tác chứng minh rằng "gốc rễ của niềm tin" của NIZK cũng yêu cầu một số dạng "thử thách" ngẫu nhiên. Một dạng "thử thách" được giao cho "yêu tinh tiên tri ngẫu nhiên"; Chuỗi ngẫu nhiên được chia sẻ để đạt được. Cả hai hình thức thử thách về cơ bản đều giới thiệu bên thứ ba và cả hai đều phải cung cấp một "cửa sau" mà "trình giả lập" có thể khai thác, để trình giả lập có một số "lợi thế" trong "thế giới lý tưởng" và lợi thế này phải thất bại trong "thế giới thực".
NIZK toát ra sức quyến rũ vô hạn, khiến tôi hết lần này đến lần khác kinh ngạc, trong ba mươi năm qua, những người tiên phong đã khám phá ra những kết luận tinh tế, đồng thời còn biết bao góc khuất chờ đợi ánh sáng soi đường.Chuỗi bài viết này trên Githubkho dự án
Nhận được yêu cầu kéo đầu tiên từ Jingyu Hu (colortigerhu), chỉ thay đổi một vài từ, nhưng ngay lúc đó, tôi cảm thấy sức sống. Việc trao đổi kiến thức, va chạm ý tưởng thật hấp dẫn phải không?
"Mọi người mà chúng ta tương tác đều trở thành một phần của chúng ta." Mọi người mà chúng ta tương tác đều trở thành một phần của chúng ta. ―Jodi Aman
chữ
người giới thiệu
[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.
[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.
[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.
[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.
[5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.
[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols." Proc. of the 1st CCS (1995): 62-73.
[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m
[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.
[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.
[10]Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).
[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.
[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.
[13] Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.
[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.
[15] Yi Deng. "người giới thiệu" https://zhuanlan.zhihu.com/p/29491567
IOS
Android