BTC

$96,000

5.73%

ETH

$3,521.91

3.97%

HTX

$0.{5}2273

5.23%

SOL

$198.17

3.05%

BNB

$710

3.05%

简体中文

繁體中文

English

Tiếng Việt

한국어

日本語

ภาษาไทย

Türkçe

Partnered With:

Hiểu biết toàn diện về bằng chứng không có kiến thức

Đọc bài viết này mất 36 phút

Bằng chứng không có kiến thức được sử dụng rộng rãi trong mật mã và đã được chứng minh rõ ràng rằng khái niệm và ứng dụng này có thể giải quyết được nhiều vấn đề.

Tiêu đề gốc: " Phân tích｜Bằng chứng không có kiến thức 》

Tác giả gốc: CryptoYC Tech, CryptoYC Labs

Bằng chứng không có kiến thức được đề xuất bởi S.Goldwasser, S.Micali và C. Rackoff năm 2016 Được đề xuất vào những năm 1980. Ý nghĩa của bằng chứng này là không cần thiết phải cho bên kia xem bằng chứng hay quá trình giải quyết vấn đề để khiến bên kia tin rằng một kết luận nào đó là đúng. Bằng chứng không có kiến thức được sử dụng rộng rãi trong mật mã và đã được chứng minh rõ ràng rằng khái niệm và ứng dụng này có thể giải quyết được nhiều vấn đề.

Định nghĩa bằng chứng không có kiến thức

Bằng chứng không có kiến thức: zkSNARK, viết tắt của không có kiến thức Succint Đối số không tương tác của kiến thức:

Ngắn gọn: Lượng dữ liệu được chứng minh tương đối nhỏ

Không tương tác: Không có hoặc có rất ít tương tác.

Biện luận: Người xác minh chỉ có giá trị đối với người chứng minh có khả năng tính toán hạn chế. Một người chứng minh có đủ khả năng tính toán có thể giả mạo một bằng chứng. Đây còn được gọi là "độ tin cậy tính toán" (nói một cách tương đối là "độ tin cậy hoàn hảo").

của Kiến thức: Đối với người chứng minh, bằng chứng không được biết đến (Nhân chứng , chẳng hạn như đầu vào của hàm băm hoặc đường dẫn để xác định nút cây Merkle), không thể xây dựng một tập hợp các tham số và bằng chứng.

Ví dụ về bằng chứng không có kiến thức - lấy Sudoku làm ví dụ

Bằng chứng

Một ngày nọ, Xiao Ming nghĩ ra một bài Sudoku rất khó và Xiao Hong đã mất rất nhiều thời gian để thử nó. đi giải Sudoku này nhưng không đoán ra được kết quả, Tiểu Hồng cảm thấy Hiểu Minh đang giở trò đồi bại với mình, "Câu hỏi này không có lời giải! Tiểu Minh, cậu đang giở trò với tôi!", Cô bỏ chạy. đến Tiểu Minh để phàn nàn. "Tôi có thể chứng minh cho bạn thấy rằng vấn đề này có giải pháp và tôi biết giải pháp," Xiao Ming bình tĩnh trả lời. "Được rồi," Tiểu Hồng nghĩ thầm, "Hừm, sau khi ngươi chứng minh cho ta thấy, ta sẽ viết ra đáp án rồi đi chơi với Tiểu Cương và làm câu hỏi này cho hắn." Tiểu Minh tiếp tục, "Ta sẽ dùng số 0." -bằng chứng kiến thức để chứng minh cho bạn thấy rằng tôi biết giải pháp cho vấn đề này. Nói cách khác, tôi sẽ không chỉ cho bạn giải pháp, nhưng tôi có thể thuyết phục bạn rằng tôi thực sự có giải pháp cho vấn đề này." Xiao Hong không tin anh ta Có thể làm được điều này, tôi vẫn đang tưởng tượng xem Tiểu Cương bị lừa sẽ như thế nào. Hiểu Minh lấy ra 81 tấm thẻ trắng (9x9) đặt lên bàn, trên mỗi tờ giấy viết số từ 1 đến 9, yêu cầu Tiểu Hồng quay lại, nhắm mắt lại rồi cẩn thận đặt 81 tấm thẻ đó vào. trên bàn, đặt lên bàn theo sự sắp xếp của lời giải, các thẻ đại diện cho đáp án đặt trên bàn với các con số úp xuống, các thẻ đại diện cho câu đố đặt trên bàn với các con số hướng lên trên.

Thử nghiệm ngẫu nhiên

Sau khi Hiểu Minh đặt thẻ xong, anh yêu cầu Tiểu Hồng mở mắt và quay lại. Tiểu Hồng rất hưng phấn, nàng cảm giác được đáp án bí ẩn sắp được bại lộ, trong lòng rất vui mừng. Cô đã mất nhiều ngày không thể giải quyết được vấn đề này. Tiểu Minh nói với Tiểu Hồng: “Tiểu Hồng, ngươi không thể nhìn lén những lá bài úp này.” Rõ ràng là Tiểu Hồng thất vọng, nàng cho rằng mình có thể nhìn ra được giải pháp hoàn chỉnh. "Nhưng tôi có thể để bạn thử nghiệm các giải pháp này: bạn có thể chọn thử nghiệm các giải pháp của tôi theo hàng, cột hoặc hộp 3x3. Bạn chọn một", Xiaohong nói với Xiao Ming và quyết định làm theo phương pháp thực tế để xác minh. Sau đó, Xiao Ming thu thập 9 thẻ ở mỗi hàng và đặt chúng riêng lẻ vào bao tải. Tất cả các thẻ được thu thập và đặt trong 9 túi vải bố. Sau đó Tiểu Minh lắc từng bao để rải các thẻ bên trong. Cuối cùng đưa 9 bao này cho Tiểu Hồng.

Xác minh

"Được rồi, bạn có thể mở những chiếc túi này." Xiao Ming nói với Xiao Hong, "Mỗi chiếc túi phải có chính xác 9 bức tranh. Không có số nào lặp lại. Chúng là những lá bài có số từ 1 đến 9." Tiểu Hồng mở từng chiếc túi ra nhìn, hóa ra là sự thật.

"Nhưng điều này chẳng chứng tỏ được gì cả! Tôi cũng có thể làm điều này để cho bạn xem. Tôi chỉ cần chắc chắn rằng rằng mỗi hàng chứa 9 lá bài từ 1 đến 9, bất kể các số trong cột và lưới chín ô vuông đều không lặp lại." Xiao Hong nói. Xiao Ming giải thích: "Nhưng tôi cũng không biết liệu bạn sẽ chọn thu thập thẻ theo hàng, cột hoặc lưới. Tôi đặt thẻ theo lời giải của bài toán và tôi không sợ bạn chọn gì."

Xác minh nhiều lần

Xiaohong vẫn chưa bị thuyết phục. Cô cảm thấy có thể Tiểu Minh vẫn đang lừa mình nên đã yêu cầu Tiểu Minh khôi phục thẻ và chọn lại theo phương pháp ban đầu. Sau khi thử nhiều lần, mỗi lần Xiaohong lại chọn một phương pháp kiểm tra khác nhau. Đã thử nhiều lần với kết quả tương tự. Bây giờ Tiểu Hồng phải thừa nhận rằng Tiểu Minh hoặc là rất rất may mắn và có thể đặt cược xem Tiểu Hồng sẽ chọn phương pháp kiểm tra nào mỗi lần, hoặc cậu ấy thực sự biết giải pháp cho vấn đề (hoặc Tiểu Minh có thể đọc được suy nghĩ và biết trước điều gì sẽ xảy ra). Tiểu Hồng sẽ chọn) phương pháp kiểm tra). Tiểu Hồng rất thất vọng, trải qua nhiều thí nghiệm như vậy, cô vẫn không biết giải pháp thực sự, cô chỉ biết mỗi lần Tiểu Minh sắp xếp các quân bài, khả năng cao là mỗi hàng, cột, lưới sẽ quả thực là 1-9 không lặp lại, điều này cho thấy khả năng cao là câu hỏi này có đáp án và khả năng cao là Tiểu Minh biết đáp án của câu hỏi này.

Bản chất của bằng chứng không có kiến thức là chứng minh nó cho ai đó mà không tiết lộ điều gì đó mà tôi biết hoặc sở hữu. đã chứng minh rằng tôi có khả năng cao (điều này rất quan trọng, bằng chứng không có kiến thức cuối cùng là bằng chứng xác suất) rằng tôi biết hoặc sở hữu thứ này.

Điều cần chứng minh trong truyện là lời giải của một bài toán Sudoku, Hiểu Minh hỏi Xiao Hong to Cards từ các hàng, cột và lưới mỗi lần được chọn ngẫu nhiên, được tập hợp lại với nhau và xáo trộn ngẫu nhiên, Xiao Hong không thể biết cách giải quyết vấn đề bằng cách mở túi, nhưng cô có thể tin rằng Xiao Ming có xác suất cao của việc biết giải pháp.

Zk-SNIPM trong câu chuyện này cũng nửa đùa nửa thật ám chỉ đến tình trạng công nghệ hiện nay trong các bằng chứng không có kiến thức.Thuật toán zk-SNARKs phổ quát (Tranh luận không tương tác không tương tác không có kiến thức). Mặc dù zk-SNIPM trong câu chuyện có những sơ hở nhưng nó vẫn còn chỗ để cải thiện, chẳng hạn như sử dụng máy quét để quét tất cả các tổ hợp thẻ đầu tiên, sau đó xác minh tất cả các chuỗi thử nghiệm cùng một lúc. Điều này gây khó khăn cho việc hack máy thông qua thử và sai.

Phương pháp chứng minh tương tác ban đầu giữa Xiao Ming và Xiao Hong ngụ ý rằng Bằng chứng tương tác không có kiến thức. Bằng chứng tương tác không có kiến thức yêu cầu người xác minh (Xiaohong) liên tục gửi các thử nghiệm ngẫu nhiên sau khi người chứng minh (Xiaoming) đưa ra câu trả lời (cam kết). Nếu bên xác minh và bên chứng minh thông đồng trước thì họ có thể giả mạo/làm giả chứng minh mà không biết câu trả lời đúng.

Các bằng chứng không tương tác không yêu cầu sự tương tác này. Nhưng nó sẽ yêu cầu một số máy móc hoặc chương trình bổ sung và một chuỗi các thử nghiệm mà không ai có thể biết được. Với chương trình và trình tự kiểm tra như vậy, máy chứng minh có thể tự động tính toán bằng chứng và ngăn chặn bất kỳ bên nào làm sai lệch.

Phân tích bằng chứng không có kiến thức — --Phân tích vấn đề

Bằng chứng không có kiến thức thường bao gồm bốn phần:

Chuyển đổi bài toán đa thức - Bài toán cần chứng minh được chuyển thành bài toán đa thức t(x)h(x) = w(x)v(x), và người chứng minh nộp bằng chứng để người xác minh xác nhận rằng đa thức đúng.

Chọn ngẫu nhiên xác minh - Chọn ngẫu nhiên các giá trị s để xác minh, xác minh t(s)h(s) = w(s)v(s). So với việc xác minh đẳng thức đa thức t(x)h(x) = w(x)v(x), xác minh lựa chọn ngẫu nhiên đơn giản và yêu cầu ít dữ liệu xác minh hơn. Xác minh lựa chọn ngẫu nhiên chắc chắn không an toàn bằng xác minh phương trình đa thức, nhưng nếu thực sự đủ ngẫu nhiên thì độ bảo mật vẫn khá cao.

Ẩn đồng hình - Ẩn đồng cấu đề cập đến một đặc điểm của chức năng. Việc tính toán đầu vào và tính toán đầu ra vẫn “đồng cấu”. Lấy phép đồng cấu cộng tính làm ví dụ, hàm E(x) thỏa mãn ba điều kiện sau được gọi là đồng cấu cộng tính:

1. Cho E(x) khó suy ra x.

2. Các đầu vào khác nhau tương ứng với các đầu ra khác nhau 3. E (x+y) có thể được tính từ E(x), E(y). Đồng cấu nhân là tương tự nhau.

Không Kiến thức - Người chứng minh và người kiểm chứng không biết bất kỳ kiến thức nào khác ngoại trừ "vấn đề có được chứng minh hay không" (không biết về các giá trị được chọn ngẫu nhiên, không biết về kết quả tính đa thức của các giá trị được chọn, v.v.).

Chuyển đổi bài toán đa thức

Vấn đề NP và giảm

Giải quyết vấn đề cần có thời gian. Một bài toán được cho là có độ phức tạp đa thức nếu mối quan hệ giữa thời gian cần thiết để giải nó và độ lớn của bài toán là đa thức. Các bài toán tổng quát có thể được chia thành hai loại: bài toán P và bài toán NP. Bài toán P là bài toán có thể giải được trong thời gian đa thức. Bài toán NP (Bài toán đa thức không xác định, bài toán đa thức không xác định) đề cập đến một bài toán không thể giải được trong phạm vi đa thức nhưng có thể được xác minh trong thời gian đa thức.

Rõ ràng bài toán P cũng là bài toán NP, nhưng liệu bài toán NP có phải là bài toán P hay không vấn đề, NP = P? , cho đến nay vẫn chưa có ai có thể chứng minh được điều đó. Người ta thường tin rằng bài toán NP không bằng bài toán P, nghĩa là không có nghiệm đa thức cho bài toán NP.

Sự giảm thiểu có thể được hiểu là sự chuyển hóa của một vấn đề. Đầu vào của bất kỳ chương trình A nào cũng có thể được chuyển đổi thành đầu vào của chương trình B theo một quy tắc nhất định, sao cho đầu ra của hai chương trình giống nhau, khi đó có thể nói bài toán A có thể quy gọn thành bài toán B.

Bài toán NPC là một bài toán NP, và tất cả các bài toán NP khác đều có thể được quy giản về nó. Nói một cách đơn giản, các vấn đề NP có thể được quy gọn lại với nhau. Nếu một vấn đề NP được giải quyết thì các vấn đề NP khác cũng có thể được giải quyết.

Cho ví dụ về các bài toán NP và cách rút gọn các bài toán NP.

Bài toán thỏa mãn công thức Boolean (bài toán SAT, thỏa mãn công thức boolean) là một bài toán NP. Công thức Boolean được định nghĩa như sau:

Giả sử các biến x1 , x2 , x3 , ... là một công thức Boolean

Giả sử f là một công thức Boolean, ￢f cũng là một Boolean công thức (đảo ngược)

→Giả sử f và g là các công thức Boolean, f∧g và f∨g cũng là các công thức Boolean (AND và OR )

Có thể thỏa mãn một công thức Boolean, nghĩa là khi đầu vào là 0/1, có một đầu ra là đúng. Bài toán SAT là tìm tất cả các công thức Boolean thỏa mãn nó. Bài toán SAT dường như không có giải pháp nào tốt hơn ngoài việc liệt kê các công thức Boolean có thể, có nghĩa là nó không thể giải được trong thời gian đa thức. Nếu bạn biết một công thức Boolean thỏa mãn nó, việc xác minh sẽ rất thuận tiện (khi đầu vào là 0/1, hãy xem liệu đầu ra có đúng hay không). Bài toán SAT là một bài toán NP.

Hãy xem xét một bài toán NP khác: bài toán PolyZero. Bài toán PolyZero đề cập đến một đa thức thỏa mãn: khi đầu vào đa thức là 0 hoặc 1 thì đầu ra đa thức là 0.

PolyZero(f):=1

f Khi đầu vào là 0/1 thì đầu ra đa thức là 0.

Biểu thức Boolean f có thể được chuyển đổi thành đa thức thông qua hàm rút gọn r sau:

·r(xi ):=(1-xi )

·r(￢f ) :=(1-r(f))

·r(f∧g):=(1-(1-r(f))(1-r(g)))

·r(f∨g):=r(f)r(g)

Nói cách khác, một bài toán SAT có thể được quy gọn thành bài toán PolyZero thông qua hàm rút gọn r: f thỏa mãn khi và chỉ khi đầu ra của r(f) bằng 0.

SAT(f)=PolyZero(r(f))

Tóm lại, bài toán NP là bài toán không có lời giải trong thời gian đa thức nhưng có thể kiểm chứng được trong thời gian đa thức. Các vấn đề NP có thể rút gọn được với nhau.

Câu hỏi QSP

Bài toán cần chứng minh phải là bài toán NP. Nếu là bài toán P thì không có "việc tìm ra" lời giải của bài toán và không có bằng chứng nào. Nói một cách đơn giản, các bài toán zkSNARK giải quyết các bài toán NP. Vì các bài toán NP có thể quy giản lẫn nhau, trước tiên bạn cần xác định một bài toán NP. Tất cả các bài toán NP khác có thể quy gọn về bài toán NP này, sau đó chứng minh nó. Nghĩa là, nếu bạn chứng minh được một bài toán NP, bạn có thể chứng minh tất cả các bài toán NP. Bài toán QSP là bài toán NP và nó cũng đặc biệt phù hợp với zkSNARK .

Cho một chuỗi đa thức, cho trước một đa thức đích, tìm đa thức Tổ hợp chia đa thức đích.Bài toán QSP với đầu vào n-bit được định nghĩa như sau:

Cho nhiều đa thức: v0,...,vm,w0,...,wm

Đa thức đích: t

Hàm ánh xạ: f:{(i,j)∣1

Cho một nhân chứng (Nhân chứng) u, có thể khẳng định u là lời giải cho bài toán QSP nếu nó thỏa mãn các điều kiện sau:

ak ,bk = 1 Nếu k=f(i,u[i])

ak ,bk =0 Nếu k=f(i,1- u[i])

va wb có thể được chia đều t, trong đó va =v0 +a1 v1 +...+am vm ,wb =w0 +b1 w1 +...+bm wm

Đối với một phần bằng chứng u, hãy thực hiện hai phép tính ánh xạ cho mỗi bit (u[i] ; và 1 -u[i] ), xác định hệ số giữa các đa thức. Vì với mỗi bit chứng cứ u thực hiện hai phép tính để xác định hệ số giữa các đa thức, nếu 2n <m thì vẫn có sự linh hoạt rất lớn trong việc lựa chọn đa thức.

Nếu người chứng minh biết giải pháp cho vấn đề QSP, anh ta cần cung cấp bằng chứng (nghĩa là , bạn). Sau khi biết bằng chứng u, người kiểm chứng khôi phục các hệ số của đa thức theo quy tắc trên và xác minh xem va vb có thể chia t: th=va wb hay không. Để tạo điều kiện thuận lợi cho việc xác minh của người xác minh, người chứng minh có thể cung cấp h cùng lúc. Khi chiều đa thức tương đối lớn thì phép nhân đa thức vẫn tương đối phức tạp.

Một ý tưởng đơn giản là thay vì trình kiểm tra xác minh xem toàn bộ đa thức có bằng nhau hay không, nó có thể chọn ngẫu nhiên các giá trị xác thực. Giả sử người xác minh chọn ngẫu nhiên giá trị xác minh s, người xác minh chỉ cần xác minh t(s)h(s)=va (s)wb (s) .

Ví dụ về bài toán chứng minh đa thức

Quy trình chứng minh bài toán đa thức

Giả sử đa thức

Chứng minh một đa thức, nghĩa là với đầu vào x, hãy chứng minh f(x ) .

3.1 Cơ sở lý thuyết nhóm hữu tuyến (đường cong elip)

Xác định một nhóm hữu hạn với sinh g và cấp n. Khi đó nhóm gồm các phần tử sau: g0, g1, g2,..., gn−1. Mã hóa thông qua các nhóm hữu hạn rất đơn giản: E(x):=gx. Nói cách khác, biết gx, ta không thể suy ra x.

3.2 Chọn số ngẫu nhiên

Người kiểm tra chọn ngẫu nhiên một phần tử trong nhóm hữu hạn, chẳng hạn như s. Cung cấp kết quả tính toán sau (kết quả mã hóa ở các mức s khác nhau):

E(s0),E(s1),...,E(sd)

Sau khi các phép tính này được tạo ra, s không còn cần thiết nữa và có thể bị lãng quên.

3.3E(f(s)) Tính toán

Ví dụ: f(x)=4+2x+4x2, E(f(s))=E(s0)4E(s1)2E(s2)4. Rõ ràng, E(f(s)) có thể được tính toán thông qua dữ liệu do người xác minh cung cấp mà không biết s.

Ví dụ về bài toán chứng minh đa thức

Quy trình chứng minh bài toán đa thức

3.4α Có

Lưu ý rằng người kiểm chứng không biết đa thức cần chứng minh Tham số, ngay cả khi người chứng minh cung cấp E(f(s)) , người xác minh không thể xác minh nó. α Phương pháp phù hợp cho phép người xác minh xác nhận rằng người chứng minh đã tính kết quả thông qua đa thức. Trên cơ sở 3.2, người kiểm chứng còn chọn ngẫu nhiên một phần tử khác α và đưa ra kết quả tính toán bổ sung:

E(αs0),E(αs1),...,E(αsd)

Người chứng minh cần cung cấp E(f(s)) và E(αf(s)) .

E(f(s))=E(s0)4E(s1)2E(s2)4

E(αf(s))=E(αs0)4E(αs1)2E(αs2)4

3.5 Hàm ghép nối

Hàm ghép nối e thỏa mãn định nghĩa sau:

e(gx,gy)=e(g,g)xy

Cách người xác minh xác minh cặp α rất đơn giản. Kiểm tra xem những điều sau đây có đúng không phương trình đúng

e(E(f(s)),gα)=e( E(αf (s)),g)

Giả sử A=e(E(f(s)),B=E(αf(s)). Quá trình phái sinh như sau:

e(A,gα)=e(E(f(s)),gα)=e(gf(s),gα)=e(g,g)αf (s)

e(B,g)=e(E(αf(s)),g)=e(gαf(s),g)= e(g,g)αf(s)

Cho đến nay, người xác minh đã cung cấp cặp α Trong trong trường hợp , người chứng minh có thể chứng minh rằng một kết quả nhất định được tính toán thông qua một đa thức nhất định và người kiểm chứng không biết các tham số cụ thể của đa thức

Ví dụ về bài toán chứng minh đa thức

Quy trình chứng minh bài toán đa thức

3.6 ;δ Offset

Hơn nữa, người chứng minh sử dụng δ offset, hoặc thậm chí Không muốn người xác minh biết E(f(s)). Sử dụng offset delta, bộ chuẩn không còn cung cấp A và B nữa mà cung cấp ngẫu nhiên A′ và B′ một tham số delta.

Rõ ràng người kiểm chứng không thể suy ra E từ A′ (f (s)), nhưng người xác minh cũng có thể xác minh xem chức năng ghép nối của cặp α có giữ được hay không:

Ví dụ về bài toán chứng minh đa thức--quy trình tổng thể

bằng chứng skSNARK về bài toán QSP

skSNARK quy trình chứng minh được chia thành hai phần:

a) giai đoạn thiết lập

b) Giai đoạn chứng minh Bài toán QSP nhằm chứng minh rằng có một chứng cứ u cho dãy đa thức v0,...,vm,w0,...,wm và đa thức đích t. Bậc cao nhất của các đa thức này là d.

Thiết lập 4.1 và CRS

CRS - Common Reference String, là thông tin công khai được thiết lập trước. Với s và α được chọn, công bố thông tin sau:

Kết quả tính toán của s và α

Kết quả tính toán cặp đa thức α

Kết quả tính toán tham số đa thức βv, βw, γ

4.2 Người chứng minh đưa ra bằng chứng

Trong hàm ánh xạ của QSP, nếu 2n < m, 1, ... , tồn tại các số trong m mà không được ánh xạ tới. Những số chưa được ánh xạ này tạo thành Ifree và được xác định (k là số chưa được ánh xạ):

Bằng chứng mà người chứng nhận cần cung cấp như sau

4.3 Xác minh của người xác minh

Trong chức năng ánh xạ của QSP, nếu 2n < m, 1 , .. ., tất cả các số được ánh xạ tới trong m được định nghĩa là nhị thức gồm các hệ số thành phần (bổ sung cho vfree):