[Bằng chứng không có kiến thức] zk-SNARK (2) - Bằng chứng không có kiến thức không tương tác đa thức
Tiêu đề gốc: "Học zk-SNARK từ đầu (2) - Chứng minh không có kiến thức không tương tác về đa thức"
Nguồn gốc: Ambi Labs Tác giả: Maksym Petkus
Giới thiệu
Ở bài viết trước (Tính chất và chứng minh của đa thức), tác giả đã giới thiệu cách sử dụng tính chất của đa thức để chứng minh kiến thức về một đa thức nhất định. Tôi tin rằng mọi người đều đã có một số hiểu biết cơ bản về việc xây dựng chứng minh . Giao thức chứng minh hiện tại vẫn còn một số thiếu sót, bài viết này sẽ cải thiện những điểm yếu này và cuối cùng xây dựng một giao thức chứng minh không có kiến thức cho đa thức. Trọng tâm của bài viết này: KEA, bằng chứng không có kiến thức tương tác, bằng chứng không có kiến thức không tương tác và Thiết lập.
Tác giả: Maksym Petkus
Bản dịch và chú thích: Even@ Secbit Lab (even@secbit.io)
Đang hiệu đính: valuka@ 安比Laboratory
Loạt bài này đã được tác giả cho phép dịch sang tiếng Trung.
Đa thức hạn chế
Như đã đề cập ở trên, kiến thức về đa thức thực chất là kiến thức về các hệ số c0, c1, …, ci. Trong giao thức, chúng tôi "gán" hệ số bằng cách lũy thừa giá trị được mã hóa theo lũy thừa của giá trị bí mật s. Chúng tôi đã hạn chế sự lựa chọn của người chứng minh đối với các giá trị được mã hóa là lũy thừa của s, nhưng hạn chế này không bắt buộc, nghĩa là người chứng minh có thể sử dụng bất kỳ phương pháp khả thi nào để tìm các giá trị zp và zh thỏa mãn các phương trình sau
Một cách để giải quyết vấn đề này là thực hiện thao tác tương tự với một giá trị được mã hóa "được chuyển đổi" khác, hoạt động như một " Tổng kiểm tra tương tự để đảm bảo rằng kết quả là lũy thừa của giá trị ban đầu.
Điều này đạt được thông qua phương pháp Giả định kiến thức về số mũ (KEA), được giới thiệu trong [Dam91], thêm chính xác hơn (lưu ý sự khác biệt giữa hai ký tự a và α(alpha)) nói:
a) Alice có giá trị a, Cô ấy muốn Bob lũy thừa nó với số mũ bất kỳ (ở đây a là phần tử sinh của một nhóm trường hữu hạn). Yêu cầu duy nhất là a chỉ có thể lũy thừa. Để đảm bảo điều này, cô ấy muốn:
Chọn một số ngẫu nhiên α
Tính a' = a α( mod n)
Cung cấp một bộ (a, a') cho Bob rồi để anh ấy so sánh hai giá trị Thực hiện bất kỳ phép tính lũy thừa nào và trả về bộ kết quả (b, b'), trong đó "biến đổi α" số mũ không thay đổi, nghĩa là bα = b'(mod n)
b) Bởi vì Bob không thể trích xuất giá trị của α từ bộ dữ liệu (a, a') và rất khó đạt được giá trị đó thông qua việc bẻ khóa bạo lực, nên có thể suy ra rằng Bob đã tạo ra một bộ dữ liệu hợp lệ. Cách duy nhất để thực hiện việc này là làm theo các bước sau:
Chọn một giá trị c
Tính b=(a)c(mod n) và b' = (a')c (mod n)
Trả lời(b,b')
c) Với bộ dữ liệu trả lời và α, Alice có thể xác minh phương trình:
(b)α = b'
(ac)α = (a')c
ac·α = (aα)c
Kết luận là:
Bob đã sử dụng cùng một chỉ mục (tức là c) để tính cả hai giá trị của bộ dữ liệu
Bob chỉ có thể sử dụng Bộ dữ liệu ban đầu của Alice để duy trì mối quan hệ α
Bob biết chỉ mục c vì cách duy nhất để xây dựng giá trị xác minh (b,b′ ) Nó sử dụng cùng một chỉ mục
Alice không biết c, đó cũng là lý do Bob không biết α
Mặc dù c đã được mã hóa nhưng phạm vi giá trị có thể có của nó không đủ lớn để duy trì thuộc tính không có kiến thức. Chúng ta sẽ thảo luận vấn đề này sau. "Kiến thức" phần được giải quyết.
Cuối cùng, giao thức này cung cấp bằng chứng cho Alice rằng Bob thực sự đã sử dụng một giá trị mà anh ấy biết để lũy thừa a. Và anh ấy không thể làm gì khác các phép toán, chẳng hạn như phép nhân và phép cộng, vì điều này sẽ phá hủy mối quan hệ biến đổi α.
Trong mã hóa đồng cấu, lũy thừa là phép nhân của giá trị được mã hóa. Chúng ta có thể áp dụng cấu trúc này cho ví dụ về đa thức hệ số đơn giản f(x) = c⋅ x:
Cấu trúc này "hạn chế" người chứng minh chỉ sử dụng các số được mã hóa do người xác minh cung cấp để thực hiện các phép tính, vì vậy người chứng minh chỉ có thể gán hệ số c cho đa thức do người xác minh cung cấp. Bây giờ chúng ta có thể mở rộng cách tiếp cận đơn thức này cho đa thức, vì phép tính được thực hiện bằng cách chia phân bố của từng số hạng riêng biệt rồi cộng chúng lại với nhau một cách "đồng hình" (cách tiếp cận này được Jens Groth giới thiệu trong [Gro10] ). Vì vậy, nếu người chứng minh được cấp lũy thừa với số mũ s và giá trị được mã hóa của phép biến đổi của chúng, anh ta có thể tính toán các đa thức ban đầu và đa thức được biến đổi, đồng thời phải đáp ứng các kiểm tra tương tự ở đây. Đối với đa thức bậc d:
Bây giờ chúng ta có thể đảm bảo rằng chứng minh được cung cấp bởi người xác minh. Đa thức được sử dụng thay vì các giá trị khác vì các phương pháp khác không thể bảo toàn phép biến đổi α. Tất nhiên, nếu người xác minh muốn đảm bảo rằng một số lũy thừa nhất định của s, chẳng hạn như j, được loại trừ khỏi đa thức của người chứng minh, thì anh ta sẽ không cung cấp bản mã tương ứng và phép biến đổi của nó:
So với giao thức trước đây, giờ đây chúng tôi có giao thức mạnh mẽ hơn. Tuy nhiên, mặc dù đã mã hóa nhưng vẫn có một lỗ hổng rõ ràng trong thuộc tính không có kiến thức: về lý thuyết, tham số đa thức cᵢ là một giá trị nằm trong một phạm vi giá trị rộng. Trên thực tế, phạm vi này có thể rất hạn chế (chẳng hạn như phạm vi trước đó). 6) trong ví dụ, điều này có nghĩa là người kiểm chứng có thể thực hiện bẻ khóa bằng vũ lực trong một phạm vi giới hạn của các kết hợp hệ số và cuối cùng tính toán kết quả bằng với câu trả lời của người kiểm chứng. Ví dụ: nếu chúng ta đặt phạm vi giá trị của mỗi hệ số là 100 và bậc đa thức là 2 thì sẽ có khoảng 1 triệu kết hợp khác nhau, có thể coi việc bẻ khóa brute Force chỉ cần dưới 1 triệu lần lặp. Quan trọng hơn, giao thức bảo mật phải có khả năng đảm bảo tính bảo mật của nó ngay cả trong trường hợp chỉ có một hệ số có giá trị là 1.
Chú thích
even@ Anbi Labs: Với KEA, người chứng minh có thể bị hạn chế xây dựng bằng chứng chỉ bằng cách sử dụng giá trị được mã hóa do người xác minh cung cấp. Nói đúng ra, một phiên bản mở rộng của KEA được sử dụng ở đây, được gọi là Kiến thức về giả định lũy thừa q-power.
Bằng chứng không có kiến thức
Bởi vì người xác minh có thể trích xuất kiến thức về đa thức p(x) chưa biết từ dữ liệu do người xác minh gửi , thì chúng ta chỉ cần xem những dữ liệu được cung cấp này (bằng chứng):
Hãy để ý thấy việc không có kiến thức dễ dàng như thế nào được tích hợp vào cấu trúc này, thường được gọi là kiến thức không "không tốn kém".
Chú thích
even@ Ambi Lab: Với kỹ thuật "không tốn kém" này, bạn có thể dễ dàng đạt được kiến thức bằng không. Tuy nhiên, phương pháp triển khai không có kiến thức ở đây hơi khác so với giao thức Pinocchio thực tế và sơ đồ Groth16. Giải pháp thực tế là nhân với δ^(δ·t(s)).
Không tương tác
Cho đến nay, chúng ta đã bàn xong về giải pháp tương tác không có kiến thức. Nhưng tại sao chúng ta cần không tương tác? Vì bằng chứng tương tác chỉ có giá trị đối với người xác minh ban đầu nên không ai khác (những người xác minh khác) có thể tin cậy bằng chứng này vì:
Người xác minh có thể thông đồng với người hoạt động và cho anh ta biết các tham số mật khẩu s và α. Với những tham số này, người hoạt động có thể giả mạo chứng chỉ, như đã đề cập ở chú ý 3.1 ở trên.
người xác minh cũng có thể sử dụng phương pháp tương tự để giả mạo chứng chỉ.
người xác minh phải lưu α và t(s) cho đến khi tất cả các bằng chứng liên quan đã được xác minh, điều này dẫn đến khả năng xảy ra các tham số bí mật. Tấn công bổ sung bề mặt để rò rỉ.
Do đó, người chứng minh cần tương tác riêng với từng người xác minh để chứng minh một tuyên bố (tức là kiến thức về đa thức trong ví dụ) .
Mặc dù bằng chứng tương tác cũng có công dụng của chúng, chẳng hạn như người chứng minh chỉ muốn một người xác minh cụ thể (được gọi là người xác minh mục tiêu, xem thêm Để biết thông tin, xem [JSI96]). Nếu bạn bị thuyết phục, bạn không còn có thể sử dụng lại cách chứng minh tương tự để chứng minh nhận định này cho người khác, nhưng khi người chứng minh muốn thuyết phục nhiều người tham gia cùng một lúc hoặc vĩnh viễn thì phương pháp này rất kém hiệu quả. Người chứng minh cần trực tuyến và thực hiện các phép tính giống nhau cho mọi người xác minh.
Do đó, chúng ta cần một tham số bí mật có thể được sử dụng lại, công khai, đáng tin cậy và không bị lạm dụng.
Trước tiên chúng ta hãy nghĩ về cách đảm bảo tính bảo mật của giá trị bí mật (t(s),α) sau khi xây dựng nó. Chúng ta có thể mã hóa nó giống như cách mà người xác minh sử dụng lũy thừa của s trước khi gửi giá trị được mã hóa đến người chứng minh. Tuy nhiên, trong nhận xét 3.2 đã đề cập rằng mã hóa đồng cấu mà chúng tôi sử dụng không hỗ trợ phép nhân hai giá trị bí mật. Điều này rất dễ xác minh đối với phép nhân các giá trị được mã hóa của t(s) và h và nhân các giá trị được mã hóa của p và α. Vấn đề này có thể được giải quyết bằng thao tác Ghép nối.
Chú thích
even@ Ambi Labs: Giao thức chứng minh không tương tác ở đây sẽ mã hóa các tham số nhưng gây ra hai vấn đề:
1) Tương tự như Mã hóa trạng thái không thể nhân hai giá trị được mã hóa, vậy làm cách nào để xác minh các tham số được mã hóa?
2) Một khi giá trị mã hóa bị rò rỉ, mối quan hệ tin cậy của giao thức không thể được đảm bảo. Làm thế nào để đảm bảo tính bảo mật của các tham số?
Nhân các giá trị được mã hóa
Thao tác ghép nối (ánh xạ song tuyến tính) là một cấu trúc toán học, được biểu thị dưới dạng hàm e(g,g). Cho hai đầu vào được mã hóa (tức là ga, gb) trong một tập dữ liệu, chúng có thể ánh xạ một cách xác định tới sản phẩm của họ trên một tập hợp dữ liệu đầu ra khác, tức là e(ga, gb) = e(g, g)ab:
Vì tập dữ liệu nguồn và tập dữ liệu đầu ra (thường được gọi là nhóm) khác nhau nên kết quả của một lần ghép nối không thể được sử dụng làm đầu vào cho các phép tính ghép nối khác. Chúng ta có thể coi tập đầu ra (còn được gọi là "bộ mục tiêu") là một "vũ trụ khác". Do đó, chúng tôi không thể nhân kết quả với một giá trị được mã hóa khác và chính việc ghép tên cho biết rằng chúng tôi chỉ có thể nhân hai giá trị được mã hóa cùng một lúc.
Chú thích
even@ Anbi Labs: Nói cách khác, ghép nối chỉ hỗ trợ nhân hai giá trị như x * y, nhưng không hỗ trợ nhân ba giá trị trở lên, chẳng hạn như x . *y*z.
Theo một nghĩa nào đó, điều này tương tự như hàm băm, ánh xạ tất cả các giá trị đầu vào có thể có vào On an phần tử trong tập hợp các giá trị đầu ra có thể, quá trình này thường không thể đảo ngược.
Lưu ý: Thoạt nhìn, hạn chế này có thể cản trở việc triển khai các chức năng liên quan, nhưng trong zk-SNARK Đây là thuộc tính quan trọng nhất để đảm bảo chế độ an toàn, xem nhận xét 3.3.
Hàm ghép nối e(g,g) ban đầu có thể được tương tự hóa (nói đúng ra là không chính xác) thành "trao đổi" hoạt động của từng cơ số đầu ra và số mũ làm cho cơ số g bị sửa đổi thành số mũ trong quá trình trao đổi, tức là ga → ag. Hai đầu vào được "chuyển đổi" được sửa đổi cùng nhau sao cho giá trị ban đầu a và b được nhân với cùng số mũ, đó là: 
Lưu ý: Thao tác ghép nối đạt được các thuộc tính này bằng cách thay đổi đường cong elip. Ký hiệu gⁿ chúng tôi sử dụng hiện đại diện cho một điểm trên đường cong nơi trình tạo đã được thêm vào n lần và Nó không phải là phép nhân trình tạo nhóm mà chúng tôi đã sử dụng trước đó.
[DBS04] Bài đánh giá này cung cấp điểm khởi đầu để tìm hiểu về cách ghép nối.
Thiết lập cho các bên đáng tin cậy
Với việc ghép nối sẵn có, giờ đây chúng tôi đã sẵn sàng thiết lập các thông số được hiển thị một cách an toàn và có thể tái sử dụng. Giả sử chúng ta để một bên trung thực tạo ra các giá trị bí mật s và α. Chỉ α và tất cả các lũy thừa cần thiết của s và các phép biến đổi α tương ứng của chúng được mã hóa, khi đó dữ liệu gốc phải bị xóa (i là 0, 1,…,d):
Tin tưởng bất kỳ người tham gia nào
Mặc dù thiết lập đáng tin cậy là hiệu quả, nhiều người dùng CRS cũng phải tin tưởng rằng trình tạo thực sự đã xóa α và s, điều này không có cách nào để chứng minh (bằng chứng về sự thiếu hiểu biết là một lĩnh vực nghiên cứu tích cực [DK18]), vì vậy phương pháp này vẫn không hợp lệ . Vì vậy cần giảm thiểu hoặc loại bỏ sự tin tưởng này. Nếu không, bên không trung thực có thể tạo ra bằng chứng giả mà không bị phát hiện.
Một giải pháp dành cho nhiều bên sử dụng các công cụ toán học được giới thiệu trong phần trước để tạo CRS kết hợp sao cho các Không một người có liên quan biết "bí mật". Sau đây là kế hoạch thực hiện, giả sử có ba người tham gia là Alice, Bob và Carol, tương ứng với A, B và C, trong đó i là 1, 2, …, d:
Trừ khi thông đồng, những người tham gia không biết thông số bí mật của nhau. Trên thực tế, một người tham gia phải thông đồng với tất cả những người tham gia khác để có được s và α, do đó chỉ cần một trong những người tham gia trung thực thì không có cách nào giả mạo bằng chứng.
Lưu ý: Quá trình này có thể được lặp lại với càng nhiều người tham gia càng tốt.
Một vấn đề là làm thế nào để xác minh rằng các giá trị ngẫu nhiên được người tham gia sử dụng khi tạo CRS là nhất quán, bởi vì kẻ tấn công có thể tạo ra nhiều số ngẫu nhiên khác nhau s₁, s₂, … và α₁, α₂, …, sau đó thay thế các số ngẫu nhiên khác nhau này để thực hiện các phép tính lũy thừa khác nhau của s (hoặc cung cấp các số ngẫu nhiên dưới dạng phần mở rộng của CRS), từ đó làm cho CRS không hợp lệ hoặc không thể sử dụng được .
May mắn thay, vì chúng ta có thể sử dụng tính năng ghép nối để nhân giá trị được mã hóa nên chúng ta có thể thực hiện từng giá trị một bắt đầu từ tham số đầu tiên và đảm bảo rằng mỗi tham số đều được bắt nguồn từ tham số trước đó. 
Khi chúng tôi xác minh tính nhất quán của các tham số bí mật của từng người tham gia, chúng tôi phải chú ý đến việc tạo người tham gia. Quy trình CRS không bắt buộc người tham gia sau (tức là Bob và Carol trong ví dụ của chúng tôi) sử dụng CRS đã được tiết lộ trước đó. Do đó, nếu kẻ tấn công là người tham gia cuối cùng trong chuỗi, anh ta có thể bỏ qua CRS trước đó và xây dựng CRS hợp lệ theo ý muốn giống như người tham gia đầu tiên trong chuỗi, để anh ta trở thành người duy nhất biết bí mật s và α. mọi người.
Để giải quyết vấn đề này, chúng tôi có thể yêu cầu thêm từng người tham gia ngoại trừ người đầu tiên mã hóa và sau đó tiết lộ các thông số của mình. Ví dụ: Bob cũng tiết lộ:
Tương tự, Carol phải chứng minh rằng CRS của cô ấy nhân với Gained bình thường sau khi có được CRS của Alice-Bob.
Đây là mô hình thiết lập CRS mạnh mẽ và không hoàn toàn phụ thuộc vào một tác nhân duy nhất. Trên thực tế, ngay cả khi tất cả những người tham gia khác thông đồng, miễn là một người tham gia trung thực và có thể xóa và không bao giờ chia sẻ các thông số bí mật của mình thì CRS vẫn hợp lệ. Vì vậy, càng có nhiều người tham gia không liên quan tham gia vào việc thiết lập CRS (đôi khi được gọi là buổi lễ [Wil16]), thì khả năng chứng nhận bị làm giả càng ít. Khi có sự tham gia của các bên cạnh tranh, việc giả mạo bằng chứng gần như là không thể. Mẫu này chấp nhận các bên không đáng tin cậy khác nghi ngờ khả năng nhận dạng của thiết lập vì bước xác minh đảm bảo rằng họ sẽ không làm hỏng (ở đây bao gồm cả việc sử dụng rất yếu α và s) CRS cuối cùng.
Chú thích
even@ Anbi Labs: Hiện có một số giải pháp zkSNARK hỗ trợ CRS có thể nâng cấp và bất kỳ người tham gia nào nghi ngờ CRS đều có thể cập nhật CRS. Ngoài ra, còn có một số giải pháp zkSNARK hỗ trợ Universal CRS, thay vì thiết lập độ tin cậy cho từng mạch thì chỉ cần thực hiện một lần trên toàn cầu. Ngoài ra, một số lượng lớn các giải pháp không yêu cầu Trusted Setup đang được nghiên cứu đầy đủ.
SNARK đa thức
Chúng tôi hiện đã sẵn sàng hợp nhất giao thức zk-SNARKOP đang phát triển dần dần này. Để cho ngắn gọn, chúng ta sẽ sử dụng dấu ngoặc nhọn để biểu thị một tập hợp các phần tử chứa các chỉ số con bên cạnh chúng, ví dụ: 
Nhận xét 3.3 Nếu kết quả ghép nối có thể được sử dụng lại trong các giao thức nhân tương tự khác thì không có sự bảo mật nào cả, vì khi đó có thể xây dựng bộ chứng minh
Kết luận
Chúng tôi sử dụng giao thức zk-SNARK để giải kiến thức bài toán đa thức, nhưng đây chỉ là một ví dụ hạn chế. Bởi vì bạn có thể nói rằng người chứng minh có thể dễ dàng xây dựng một đa thức p(x) có thể vượt qua bài kiểm tra bằng cách nhân t(x) với một đa thức bị chặn khác và cấu trúc này cũng hợp lệ.
Người xác minh biết rằng người chứng minh có đa thức hợp lệ nhưng không biết đó là đa thức nào. Chúng ta có thể bổ sung thêm chứng minh bằng cách sử dụng các tính chất khác của đa thức, chẳng hạn như: chia hết cho nhiều đa thức là bình phương của một đa thức nhất định. Mặc dù có thể có một dịch vụ chấp nhận, lưu trữ và khen thưởng tất cả các đa thức đã được chứng minh hoặc có thể có yêu cầu tính toán bằng mật mã một số dạng đa thức chưa biết. Tuy nhiên, nếu có một giải pháp chung, nó có thể hỗ trợ vô số ứng dụng.
Chú thích
even@ Anby Lab: Tóm lại, bài viết này giải quyết từng bước các vấn đề sau:
Bằng chứng đảm bảo rằng người chứng minh được xây dựng chính xác theo các quy tắc——> KEA
Đảm bảo không có kiến thức thông minh——> Chuyển đổi delta "Không tốn kém"
Bằng chứng có thể tái sử dụng——> Không tương tác
Không tương tác Cách đặt bảo mật , các tham số công khai và có thể tái sử dụng——> Mã hóa tham số, trình xác minh sử dụng ghép nối mật khẩu để xác minh
Đảm bảo rằng trình tạo tham số không làm rò rỉ bí mật --> Thiết lập nhiều bên
Tại thời điểm này, giao thức zk-SNARK hoàn chỉnh được sử dụng để chứng minh kiến thức đa thức đã được xây dựng, nhưng bây giờ Giao thức vẫn còn nhiều hạn chế về tính linh hoạt, các bài viết sau sẽ tiếp tục giới thiệu cách xây dựng một zk-SNARK phổ quát.
Liên kết gốc
https://arxiv.org/pdf/1906.07221.pdf
https://medium.com/@imolfar/why-and- How-zk-snark-works-2-proving-know-of-a-polynomial-f817760e2805
https://medium.com/@imolfar/why-and-how-zk-snark-works-3-non -interactivity-distributed-setup-c0310c0e5d1c
Tài liệu tham khảo
[Dam91]—Ivan Damgård. "Hướng tới các hệ thống khóa công khai thực tế an toàn trước các cuộc tấn công bằng văn bản mã hóa đã chọn". Trong: Hội nghị Mật mã Quốc tế Thường niên. Springer. 1991, trang 445–456.
[ Gro10]—Jens Groth. "Các lập luận không có kiến thức không tương tác dựa trên ghép nối ngắn". Trong: Hội thảo quốc tế về lý thuyết và ứng dụng của mật mã và bảo mật thông tin. Springer. 2010, trang 321–340.
[ JSI96 ]—Markus Jakobsson, Kazue Sako, và Russell Impagliazzo. "Các bằng chứng xác minh được chỉ định và ứng dụng của chúng". Trong: Hội thảo quốc tế về lý thuyết và ứng dụng kỹ thuật mật mã. Springer. 1996, trang 143–154.
[DBS04 ] —Ratna Dutta, Rana Barua, và Palash Sarkar. Các giao thức mã hóa dựa trên cặp đôi: Một cuộc khảo sát. Lưu trữ ePrint mật mã, Báo cáo 2004/064. https://eprint.iacr.org/2004/064.2004.
[ DK18 ]—Apoorvaa Deshpande và Yael Kalai. Bằng chứng về sự thiếu hiểu biết và ứng dụng để che giấu nhân chứng trong 2 tin nhắn. Lưu trữ ePrint mật mã, Báo cáo 2018/896. https://eprint.iacr.org/2018/896. 2018.
[ Wil16 ]—Zooko Wilcox. Thiết kế của buổi lễ. 2016. url: https://z.cash/blog/the-design-of-the-ceremony/
Liên kết nguồn: weixin.qq.com
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
Bài viết liên quan
