[Chứng minh không có kiến thức] zk-SNARK (1) - Tính chất và chứng minh đa thức

Tiêu đề gốc: "Học zk-SNARK từ đầu (1) - Tính chất và cách chứng minh đa thức"
Nguồn gốc: Phòng thí nghiệm Amby Tác giả: Maksym Petkus

Giới thiệu

17 năm kể từ lần đầu tiên tôi đến tiếp xúc với zk-SNARK, tôi đã học được một số kiến thức về zk-SNARK không liên tục, nhưng luôn có rất nhiều nhầm lẫn về các nguyên tắc của nó và tôi chưa hình thành được sự hiểu biết hoàn chỉnh. Tình cờ tôi đọc được bài viết này của Maksym Petkus. Bài viết bắt đầu từ các thuộc tính đa thức cơ bản nhất, bắt đầu với giao thức chứng minh đơn giản và dễ hiểu, sau đó dần dần cải thiện giao thức trong khi phát hiện và sửa đổi các vấn đề như xếp chồng các khối, cho đến khi xây dựng được giao thức zk-SNARK hoàn chỉnh. Ngoài ra, phương pháp giải thích của tác giả dựa trên vấn đề giúp người đọc biết được chuyện gì đang xảy ra và tại sao. Là một lập trình viên đã trả lại kiến thức toán học cho giáo viên nhiều năm sau khi tốt nghiệp, đọc bài viết này tôi cảm thấy như một báu vật, đọc bài viết này cô có cảm giác như đã tìm được một giàn giáo để dần dần ghép lại những kiến thức rời rạc trong đầu mình. Vì vậy tôi muốn dịch nó (được tác giả ủy quyền), một mặt để đào sâu kiến thức của bản thân, mặt khác để chia sẻ kho tàng này với bạn bè.
Có những thiếu sót trong bản dịch của bài viết. Chúng tôi hoan nghênh việc sửa chữa, bổ sung và hướng dẫn.

Không có kiến thức ngắn gọn, không tương tác đối số về kiến thức (zk-SNARK) thực sự là một phương pháp rất tao nhã nhưng không thể tiết lộ thông tin nào. Chứng minh rằng một khẳng định nào đó là đúng theo tiền đề. Nhưng câu hỏi đầu tiên là tại sao nó lại hoạt động?

Trên thực tế, bằng chứng không có kiến thức có lợi thế trong vô số ứng dụng, bao gồm:

1) Xác nhận tuyên bố liên quan đến dữ liệu riêng tư:
Một người Tài khoản ngân hàng của A có nhiều tiền hơn X
Năm ngoái, một ngân hàng đã không giao dịch với pháp nhân Y
So khớp DNA mà không làm lộ tất cả dữ liệu DNA
Điểm tín dụng của một người cao hơn Z

2) Xác thực ẩn danh:
Trong Không tiết lộ thông tin danh tính (chẳng hạn như mật khẩu đăng nhập), chứng minh rằng người yêu cầu R có quyền truy cập vào các khu vực hạn chế của trang web
Chứng minh rằng một người đến từ một nhóm Một quốc gia/khu vực nằm trong danh sách các quốc gia/khu vực được phép nhưng không tiết lộ quốc gia/khu vực nào
Bằng chứng cho thấy một người có thẻ đi tàu điện ngầm hàng tháng và Không tiết lộ số thẻ

3) Thanh toán ẩn danh:
Việc thanh toán hoàn toàn tách biệt với bất kỳ loại danh tính nào
Nộp thuế mà không tiết lộ thu nhập

4) Thuê ngoài tính toán
Thuê ngoài tính toán tốn kém và Xác minh kết quả đó là chính xác mà không cần thực hiện lại; nó mở ra một danh mục điện toán không tin cậy

Các cải tiến cho Mô hình chuỗi khối, từ tất cả các nút thực hiện cùng một phép tính cho chỉ một bên tính toán và sau đó các nút khác xác minh

và "zero Giống như thuật ngữ tuyệt vời "Bằng chứng kiến thức ", phương pháp đằng sau nó có thể nói là một kỳ tích của toán học và mật mã. Kể từ khi khái niệm về bằng chứng không có kiến thức được giới thiệu vào năm 1985 trong bài viết "Sự phức tạp về kiến thức của các hệ thống bằng chứng tương tác" [GMR85] và các bằng chứng không có kiến thức không tương tác tiếp theo [[BFM88]) (trong môi trường blockchain đặc biệt quan trọng ) và hiện đã bước vào thập kỷ nghiên cứu thứ tư.

Trong bất kỳ hệ thống "bằng chứng không có kiến thức" nào, luôn có người chứng minh mà không làm rò rỉ bất kỳ thông tin bổ sung nào. Tiếp theo, hãy để người xác minh tin rằng một số tuyên bố (Tuyên bố) là chính xác. Ví dụ: người xác minh chỉ có thể biết số tiền tài khoản ngân hàng của người chứng minh vượt quá X (tức là số tiền thực tế không được tiết lộ). Thỏa thuận phải đáp ứng ba đặc tính sau:

Tính toàn vẹn - miễn là "tuyên bố" là chính xác, người chứng minh có thể Hãy để người xác minh bị thuyết phục
Độ tin cậy - nếu "tuyên bố" sai thì người chứng minh gian lận sẽ không có cách nào thuyết phục người xác minh
Không có kiến thức - tương tác giao thức chỉ tiết lộ liệu "tuyên bố" có đúng mà không tiết lộ bất kỳ thông tin nào khác

Bản thân thuật ngữ zk-SNARK đã được giới thiệu trong [Bit+11], dựa trên [Gro10] và tuân theo Giao thức Pinocchio [Gen+12 ; Par+13] phù hợp cho các tính toán tổng quát.

Phương tiện chứng nhận

Ở đây chúng tôi không quan tâm đến các khái niệm về không có kiến thức, không tương tác, hình thức và khả năng ứng dụng của nó mà bắt đầu bằng việc cố gắng chứng minh điều gì đó đơn giản.

Hãy tưởng tượng rằng chúng ta có một mảng bit có độ dài 10 và chúng ta muốn chứng minh cho người xác minh (ví dụ: một chương trình) tuyên bố rằng tất cả các bit đều là Đặt thành 1.

người xác minh chỉ có thể kiểm tra (tức là đọc) từng bit một. Để xác minh tuyên bố này, chúng tôi đọc các phần tử theo thứ tự tùy ý và kiểm tra xem chúng có thực sự bằng 1 hay không. Nếu kết quả của lần kiểm tra lấy mẫu đầu tiên là 1, hãy đặt độ tin cậy của "tuyên bố" thành ⅒ = 10%, nếu không, nếu bằng 0 thì "tuyên bố" sai. Người xác minh tiếp tục với vòng xác minh tiếp theo cho đến khi đạt được đủ độ tin cậy. Nếu việc tin cậy người chứng minh trong một số trường hợp yêu cầu độ tin cậy ít nhất là 50% thì điều đó có nghĩa là phải thực hiện 5 lần xác minh. Nhưng nếu trong một số trường hợp khác cần độ tin cậy 95% thì tất cả các yếu tố cần phải được kiểm tra. Nhược điểm rõ ràng của giao thức chứng minh này là nó phải được kiểm tra theo số lượng phần tử, điều này không thực tế nếu chúng ta đang xử lý các mảng có hàng triệu phần tử.

Bây giờ chúng ta hãy xem đa thức được biểu diễn bằng một phương trình toán học, phương trình này có thể được vẽ dưới dạng đường cong trên hệ tọa độ :

Đường cong trên tương ứng với đa thức: f(x) = x³ – 6x² +11x– 6. Bậc của đa thức phụ thuộc vào số mũ lớn nhất của x, hiện tại bậc của đa thức là 3.

Đa thức có một tính chất rất tốt, đó là nếu chúng ta có hai đa thức không bằng nhau cấp d thì chúng là số các điểm giao nhau sẽ không vượt quá d. Ví dụ: sửa đổi một chút đa thức ban đầu thành x³ – 6x² + 10x– 5 (Lưu ý: Xin lưu ý rằng ở đây chỉ sửa đổi hệ số cuối cùng của đa thức, 6 được đổi thành 5) và được đánh dấu màu xanh lục trên hình:

Sự sửa đổi nhỏ này tạo ra một đường cong có những thay đổi lớn. Trên thực tế, không thể tìm thấy hai đường cong khác nhau sẽ trùng nhau ở một khu vực nhất định (chúng sẽ chỉ giao nhau tại một số điểm).

Đây là một tính chất rút ra từ phương pháp tìm điểm chung của các đa thức. Nếu bạn muốn tìm giao điểm của hai đa thức, trước tiên bạn cần làm cho chúng bằng nhau. Ví dụ: để tìm giao điểm của đa thức với trục x (nghĩa là f(x) = 0), chúng ta sẽ đặt x³ – 6x² + 11x – 6 = 0. Nghiệm của phương trình là các điểm chung: x=3. Những giải pháp này cũng có thể được nhìn thấy rõ ràng trong hình trên, nơi đường cong màu xanh giao với trục x.

Tương tự, chúng ta cũng có thể đánh đồng đa thức ban đầu và đa thức đã sửa đổi ở trên và tìm giao điểm của chúng.
x³ – 6x² + 11x – 6 =x³ – 6x² + 10x – 5
x-1=0
Thứ tự của kết quả sau khi rút gọn đa thức là 1, có nghiệm hiển nhiên x = 1. Do đó hai đa thức này có giao điểm.



Bất kỳ phương trình nào chứa một đa thức bậc d cuối cùng sẽ bị rút gọn thành một đa thức bậc khác nhiều nhất d, vì không có phép nhân nào trong phương trình có thể được sử dụng để xây dựng bậc cao hơn. Ví dụ: 5x³ + 7x² – x + 2 = 3x³ – x² + 2x – 5, đơn giản hóa thành 2x³ + 8x² – 3x + 7 = 0. Ngoài ra, các nguyên lý cơ bản của đại số còn cho chúng ta biết rằng có nhiều nhất d nghiệm của một đa thức cấp d (điều này sẽ được giới thiệu chi tiết ở phần sau), và do đó có nhiều nhất d điểm chung.

Vì vậy, chúng ta có thể kết luận rằng kết quả tính toán của bất kỳ đa thức nào tại bất kỳ điểm nào (thêm về tham khảo đánh giá đa thức: [Pik13]) có thể được coi là sự thể hiện bản sắc độc đáo của nó. Hãy đánh giá kết quả của đa thức mẫu khi x = 10.

x³ – 6x² +11x - 6 = 504
x³ – 6x² +10x - 5 = 495

Trên thực tế, trong số tất cả các giá trị mà x có thể chọn, nhiều nhất Ba giá trị làm cho các đa thức này bằng nhau, tất cả các giá trị khác đều không bằng nhau.

Đây cũng là lý do tại sao nếu một người chứng minh tuyên bố rằng anh ta biết một đa thức nào đó mà người xác minh cũng biết (dù lớn đến đâu). bậc của đa thức là ), họ có thể làm theo một giao thức đơn giản để xác minh:

người xác minh chọn một giá trị ngẫu nhiên x và tính toán cục bộ các kết quả đa thức
trình xác minh cung cấp giá trị x cho người chứng minh và cho phép anh ta tính toán các kết quả đa thức có liên quan
người kiểm chứng thay thế x vào phép tính đa thức và đưa kết quả cho người kiểm chứng
người kiểm chứng kiểm tra kết quả tính toán cục bộ và của người chứng minh Kết quả tính toán có bằng nhau hay không. Nếu chúng bằng nhau nghĩa là nhận định của người chứng minh có độ tin cậy cao

Dành cho ví dụ ta đặt phạm vi giá trị của x từ 1 đến 10⁷⁷ thì số điểm có kết quả tính toán khác nhau là 10⁷⁷ – d. Do đó, xác suất để x vô tình "đánh trúng" bất kỳ điểm nào trong số d điểm này có cùng kết quả là bằng (có thể coi là gần như không thể): d/10^77

@Maksym (tác giả)

So với giao thức kiểm tra bit kém hiệu quả, giao thức mới chỉ yêu cầu một vòng xác minh để đưa ra các tuyên bố có độ tin cậy rất cao (giả sử rằng d nhỏ hơn nhiều so với x) giới hạn trên của phạm vi giá trị gần như là 100%)

Đây là lý do tại sao ngay cả khi có thể có phương tiện chứng minh khác, đa thức vẫn là zk -SNARK là phần tương đối cốt lõi.

Chú thích

even@ Ambi Lab: Phần này cho chúng ta biết một tính chất quan trọng của đa thức: không thể tìm thấy hai đường cong không bằng nhau có chung các đoạn liên tục. Nghĩa là, kết quả tính toán của bất kỳ đa thức nào tại bất kỳ điểm nào đều có thể được coi là Biểu diễn nhận dạng duy nhất của nó . Điều đó có nghĩa là, chỉ cần chứng minh được một điểm ngẫu nhiên trên đa thức thì đa thức đó có thể được chứng minh (chỉ sau khi biết đa thức mới có thể tính được giá trị của điểm này). Tính chất này là cốt lõi của tất cả các chứng minh dưới đây của chúng tôi.
Đây là định lý Schwatz-Zippel, có thể mở rộng cho các đa thức đa biến, tạo thành một bề mặt trong không gian đa chiều. Định lý này sẽ xuất hiện nhiều lần trong các chứng minh của nhiều sơ đồ chứng minh không có kiến thức.

Chứng minh kiến thức về đa thức

Cuộc thảo luận của chúng ta bắt đầu với kiến thức về chứng minh đa thức, sau đó dần dần chuyển giao thức chứng minh thành một phương pháp tổng quát. Trong quá trình này, chúng ta cũng sẽ khám phá nhiều tính chất khác của đa thức.

Nhưng cho đến nay, giao thức của chúng tôi chỉ là một bằng chứng rất yếu vì không có Biện pháp nào được thực hiện để đảm bảo rằng người tham gia phải tạo ra bằng chứng theo quy định của thỏa thuận nên người tham gia chỉ có thể tin tưởng lẫn nhau. Ví dụ, người chứng minh không cần biết đa thức và có thể nhận được câu trả lời đúng theo những cách khác. Hơn nữa, nếu phạm vi giá trị của nghiệm đa thức được người xác minh xác minh không đủ lớn, chẳng hạn như số 10 mà chúng tôi đã đề cập trước đó, thì bạn có thể đoán một số và xác suất đoán được câu trả lời đúng là không đáng kể. Vì vậy, chúng ta phải giải quyết lỗ hổng này trong giao thức, trước khi giải quyết vấn đề, trước tiên chúng ta hãy suy nghĩ xem việc biết đa thức có ý nghĩa gì?

Đa thức có thể được biểu diễn dưới dạng sau (trong đó n là thứ tự của đa thức):
cnxn + … + c1x1 + c0x0
Nếu một người nói rằng họ biết một đa thức bậc nhất (tức là : c1x1 + c0=0), thì điều này có nghĩa là người đó biết giá trị của các hệ số c0, c1. Hệ số này có thể là bất kỳ giá trị nào kể cả 0.
Giả sử người chứng minh tuyên bố biết một đa thức bậc ba có hai nghiệm: x=1 và x=2. Đa thức hợp lệ thỏa mãn điều kiện này là x3 – 3x2+ 2x= 0. Vì x= 1: 1 – 3 + 2 = 0 nên x= 2: 8 – 12 + 4 = 0.
Trước tiên chúng ta hãy nghiên cứu kỹ cấu trúc của câu trả lời này.

Chú thích

even@ Ambi Lab: Phần này cho chúng ta biết bản chất của đa thức - "kiến thức" về đa thức là hệ số của đa thức. Cái gọi là “biết” một đa thức có nghĩa là “biết” các hệ số của đa thức.

Phân tích hệ số

Định lý cơ bản của đại số cho thấy rằng bất kỳ đa thức nào cũng có thể được phân tách thành đa thức tuyến tính miễn là nó có nghiệm (nghĩa là đa thức bậc 1 biểu thị một đường thẳng). Do đó, chúng ta có thể phân tách bất kỳ đa thức hợp lệ nào của có thể coi là tích của các thừa số của nó:
(x-a0)(x-a1)…(x-an) = 0
Nghĩa là, nếu bất kỳ thừa số nào bằng 0 thì toàn bộ phương trình bằng 0, nghĩa là tất cả những gì trong công thức đều là đa thức Tất cả nghiệm.
x3 - 3x2 + 2x =(x-0)(x-1)(x-2)
Vậy nghiệm của đa thức này (giá trị của x) là: 0, 1, 2. Nghiệm của đa thức có thể dễ dàng kiểm chứng dưới mọi dạng, trừ dạng của thừa số Điều này cho phép chúng ta xem nhanh các giải pháp này (còn gọi là gốc).
Hãy quay lại câu hỏi trước. Người chứng minh khẳng định rằng ông biết một đa thức cấp 3 với hai nghiệm lần lượt là 1 và 2. Tức là , dạng của đa thức này là:
(x-1)(x-2) · …
Nói cách khác (x – 1) và (x – 2) là hai thừa số của đa thức trong bài toán. Do đó, nếu người chứng minh muốn chứng minh đa thức của mình có hai nghiệm này mà không làm lộ ra đa thức thì cần chứng minh đa thức p(x) của mình là t(x) = (x- 1)(x- 2) (đồng thời được gọi là đa thức đích) và tích của một số đa thức tùy ý h(x) (nghĩa là x - 0 trong ví dụ của chúng ta), tức là:
p(x) = t(x) · h(x)
Nói cách khác, có một số đa thức h(x) có thể tạo ra t(x) bằng p(x) khi nhân với nó thì p(x) chứa t(x), nên các nghiệm của p(x) cũng chứa tất cả các nghiệm của t(x), đây là điều chúng tôi muốn chứng minh.
Cách tự nhiên để tính h(x) là chia trực tiếp:
Nếu người chứng minh không tìm được h(x) như vậy, nghĩa là p(x) không chứa thừa số t(x), thì phép chia đa thức sẽ có số dư. Ví dụ: chúng ta chia p(x) = x³ – 3x² + 2x cho t(x) = (x – 1)(x – 2) = x² – 3x+ 2
Lưu ý: Công thức bên trái là mẫu số và công thức ở góc trên bên phải là kết quả tính toán. Phần dưới cùng là phần còn lại (có thể tìm thấy giải thích và ví dụ về phép chia đa thức tại đây [Pik14]).
Chúng tôi tính kết quả h(x) = x, không có phần dư.

Lưu ý: Để đơn giản, sau này chúng ta sẽ sử dụng các biến ký tự đa thức để thay thế giá trị kết quả tính toán, ví dụ: p = p(r).

Lưu ýGiải pháp

thậm chí@ Amby Lab: Đa thức có thể được phân tích thành nhân tử Phân tách thành sản phẩm của các yếu tố gốc rễ của nó. Tính chất này có nghĩa là nếu một đa thức có nghiệm nào đó thì công thức phân tích nhân tử của nó phải chứa các thừa số của nghiệm đó.

Với thuộc tính này, chúng ta có thể vui vẻ thực hiện một số bằng chứng.

Sử dụng giao thức kiểm tra tính nhất quán đa thức, chúng ta có thể so sánh các đa thức p(x) và t(x) ⋅ h( x):
trình xác minh chọn một giá trị ngẫu nhiên r, tính toán t = t(r) (tức là đánh giá) rồi gửi r đến Prover .
người chứng minh tính h(x) =p(x) / t(x) và tìm giá trị p(r) và h(r), cung cấp kết quả tính toán p, h cho người kiểm tra.
người xác minh xác minh rằng p= t⋅h. Nếu các đa thức bằng nhau, điều đó có nghĩa là t(x) là một thừa số của p(x) .

Thực hành bằng cách sử dụng ví dụ sau để triển khai giao thức này:
người xác minh chọn số ngẫu nhiên 23, tính t = t(23) = (23 – 1)(23 – 2) = 462, rồi gửi 23 đến người kiểm chứng
người chứng minh tính h(x) =p(x) / t(x) = x và đánh giá p(r) và h(r), p= p(23) = 10626, h= h(23) = 23, cung cấp p và h cho người xác minh
người xác minh sau đó xác minh p= t⋅ h: 10626 = 462 ⋅ 23 đúng nên khẳng định được chứng minh.

Ngược lại, nếu người tục ngữ sử dụng một p′(x) khác thì nó không chứa các thừa số cần thiết, ví dụ p′(x) = 2x³ – 3x² + 2x, sau đó:

@Maksym (tác giả)

Mặc dù một tập hợp các ký hiệu toán học được sử dụng để đơn giản hóa, nhưng sẽ rất bất lợi cho việc hiểu nếu bỏ qua ký hiệu cơ bản phổ biến này: 　 (chữ viết trên). Mục đích cơ bản của ký hiệu này là để nhấn mạnh một biến mới thu được bằng cách biến đổi hoặc dẫn xuất biến ban đầu. Nghĩa là, nếu chúng ta muốn nhân v với 2 và gán nó cho một biến mới, chúng ta có thể sử dụng: v'= 2 ⋅ v.

Ta tính kết quả 2x + 3 và số dư 7x – 6, tức là: p(x) = t(x) × (2x+ 3 ) + 7x – 6. Điều này có nghĩa là người xác minh phải chia t(x) cho số dư để tính kết quả.

Tuy nhiên, vì x được người xác minh chọn ngẫu nhiên nên khả năng phần còn lại là 7x – 6 là rất thấp cuối cùng có thể là t(x) chia hết. Bằng chứng này sẽ chỉ bị từ chối nếu sau đó người xác minh kiểm tra thêm rằng p và h phải là số nguyên. Tuy nhiên, việc xác minh như vậy yêu cầu các hệ số đa thức cũng phải là số nguyên, điều này đặt ra những hạn chế lớn đối với giao thức.

Đây là lý do tại sao tiếp theo chúng tôi sẽ giới thiệu các nguyên tắc mật mã có thể làm cho phần còn lại không chia hết, mặc dù giá trị ban đầu này có thể chia được.

Nhận xét 3.1 Bây giờ chúng ta có thể kiểm tra đa thức dựa trên các tính chất cụ thể mà không cần biết các đa thức. Điều này đã cho chúng ta một số 0 -Tính chất kiến thức và tính đơn giản. Tuy nhiên, cấu trúc này vẫn còn nhiều vấn đề:

người chứng minh có thể không biết p(x) mà anh ta khẳng định, trước tiên anh ta có thể tính t = t(r), sau đó chọn một giá trị ngẫu nhiên h , do đó tính p = t⋅h. Bởi vì phương trình được thiết lập nên nó cũng có thể vượt qua sự xác minh của người xác minh.

Bởi vì người chứng minh biết điểm ngẫu nhiên x = r, nên anh ta có thể xây dựng một đa thức tùy ý phù hợp với t (r ) ⋅ h(r) có điểm chung tại r.

Trong "tuyên bố" trước, người chứng minh đã tuyên bố rằng ông biết một đa thức của một cấp cụ thể, nhưng giao thức hiện tại Không có yêu cầu rõ ràng cho đơn đặt hàng. Do đó, người chứng minh hoàn toàn có thể đánh lừa người kiểm chứng bằng đa thức bậc cao thỏa mãn kiểm tra nhân tố.
Bây giờ chúng ta sẽ giải quyết từng vấn đề một.

Chú thích

even@ Ambi Lab: Một giao thức chứng minh được xây dựng bằng cách sử dụng các thuộc tính của các thừa số, nhưng giao thức này có một số sai sót, chủ yếu là do

Người chứng minh biết t(r), đến lượt anh ta có thể xây dựng một p(r) có thể chia t(r)
prover Biết giá trị của điểm (r,t(r) · h(r)), bạn có thể xây dựng bất kỳ đa thức nào đi qua điểm này, Nó cũng thỏa mãn việc xác minh
Giao thức không hạn chế thứ tự đa thức của câu tục ngữ

Tính toán mờ

Hai vấn đề đầu tiên trong Ghi chú 3.1 là do bị lộ. Nguyên nhân là do thiếu giá trị ban đầu, nghĩa là người chứng minh biết r và t(r). Nhưng sẽ thật hoàn hảo nếu giá trị do người xác minh đưa ra vô hình như được đặt trong hộp đen, tức là người ta vẫn có thể hoàn thành các phép tính trên các giá trị mờ này mà không phá vỡ giao thức. Hơi giống với hàm băm nhưng rất khó để trở về giá trị ban đầu từ kết quả tính toán.

Mã hóa đồng hình

Đây là lý do tại sao mã hóa đồng cấu được thiết kế. Nó cho phép mã hóa một giá trị và thực hiện các phép tính số học trên bản mã. Có nhiều cách để có được các đặc tính đồng cấu của mã hóa, hãy giới thiệu một phương pháp đơn giản.
Ý tưởng chung là chúng ta chọn một số tự nhiên cơ bản (cơ số cần phải có một số thuộc tính cụ thể nhất định) g (chẳng hạn như 5), sau đó chúng tôi sử dụng giá trị mong muốn được mã hóa là số mũ của g. Ví dụ: nếu chúng tôi muốn mã hóa 3:
53=125
Ở đây 125 là bản mã tương ứng với 3. Nếu muốn nhân giá trị được mã hóa với 2, chúng ta có thể nhân văn bản mã hóa với số mũ là 2.
125² = 15625 = (5³)² = 52×3 = 56
Chúng ta không chỉ có thể nhân một giá trị chưa biết với 2 và giữ cho văn bản mã hóa hợp lệ, chúng ta còn có thể cộng hai giá trị bằng cách nhân văn bản mã hóa, chẳng hạn như 3+2:
53 · 52 = 53+2 = 5 5 =3125
Tương tự, chúng tôi cũng có thể trích xuất các số được mã hóa theo phép chia, ví dụ: 5-3
55/53 = 55 ·5-3 =5 5-3 = 52 =25
Tuy nhiên, vì cơ sở 5 là công khai nên rất dễ tìm thấy số được mã hóa. Cứ tiếp tục chia bản mã cho 5 cho đến khi kết quả là 1 thì số lần chia chính là số giá trị được mã hóa.

Số học mô-đun

Đây là lúc số học mô-đun phát huy tác dụng. Ý tưởng của phép toán mô-đun như sau: ngoại trừ n số tự nhiên đầu tiên chúng ta chọn để tạo thành một tập hữu hạn (tức là 0, 1,..., n-1), bất kỳ số nguyên nào đã cho nằm ngoài phạm vi này, chúng ta sẽ “bọc” nó đứng dậy. Ví dụ: chúng tôi chọn sáu số đầu tiên. Để minh họa điều này, hãy coi nó như một vòng tròn có sáu đơn vị có tỷ lệ bằng nhau; đây là cái mà chúng ta gọi là phạm vi (thường đề cập đến một trường hữu hạn).

Bây giờ chúng ta hãy xem số tám nên ở đâu. Ví dụ, chúng ta có thể coi nó như một sợi dây có chiều dài 8.

Nếu chúng ta buộc sợi dây ở đầu vòng tròn

Sau đó quấn sợi dây quanh vòng tròn. Sau khi quấn xong, chúng ta vẫn còn một phần sợi dây.



Sau đó chúng ta tiếp tục quấn và sợi dây sẽ kết thúc ở vạch số 2.

Đây là kết quả của hoạt động mô-đun. Sợi dây dù dài bao nhiêu thì cuối cùng cũng sẽ kết thúc ở một điểm của vòng tròn. Do đó, kết quả của phép toán modulo sẽ vẫn nằm trong một phạm vi nhất định (trong ví dụ từ 0 đến 5). Một sợi dây có chiều dài 15 sẽ kết thúc ở điểm 3 tức là 6 + 6 + 3 (quấn 2 vòng hoàn chỉnh và để lại một đoạn dài 3 đơn vị). Thao tác trên số âm cũng tương tự, điểm khác biệt duy nhất là nó được quấn theo hướng ngược lại, ví dụ, kết quả modulo của -8 là 4.

Khi chúng ta thực hiện các phép tính số học, kết quả sẽ nằm trong phạm vi n này. Từ giờ trở đi chúng ta sẽ sử dụng ký hiệu "mod n" để biểu thị các số trong phạm vi này.

3 × 5 = 3 mod 6
5 + 2 = 1 mod 6

Ngoài ra, tính chất quan trọng nhất của số học mô đun là thứ tự thực hiện không quan trọng. Ví dụ chúng ta có thể hoàn thành mọi thao tác trước rồi mới lấy khuôn, hoặc có thể lấy khuôn sau mỗi bước thao tác. Ví dụ: (2 × 4 – 1) × 3 = 3 (mod 6) tương đương với:

2 × 4 = 1 mod 6
2 - 1 = 1 mod 6
1 × 3 = 3 mod 6

Vậy công dụng của số học mô-đun là gì? Nghĩa là, nếu chúng ta sử dụng số học mô đun thì không dễ để quay về giá trị ban đầu từ kết quả phép toán, bởi vì nhiều cách kết hợp khác nhau sẽ cho ra cùng một kết quả phép tính:

5 × 4 = 2 mod 6
4 × 2 = 2 mod 6
2 × 1 = 1 mod 6
……

Nếu không có số học modulo, kích thước của kết quả sẽ cung cấp một số manh mối về giá trị ban đầu. Trừ khi thông tin có thể được ẩn đi trong khi vẫn giữ được các thuộc tính số học thông thường.

Mã hóa đồng cấu mạnh

Hãy quay lại mã hóa đồng cấu và sử dụng số học mô-đun, chẳng hạn như modulo 7, chúng ta có thể Nhận:
51 = 5(mod 7)
52 = 4( mod 7)
53 = 6(mod 7)
...
Các phép toán với số mũ khác nhau mang lại kết quả như nhau:
55 = 3(mod 7)
511 = 3(mod 7)
517 = 3(mod 7)
......
Điều này gây khó khăn cho việc biết số mũ là gì. Trên thực tế, nếu mô-đun được làm khá lớn thì việc tính ngược từ kết quả của phép toán hàm mũ là không khả thi; mật mã hiện đại phần lớn dựa vào độ “khó” của bài toán này.

Tất cả các thuộc tính đồng hình trong sơ đồ được giữ lại trong hoạt động mô-đun:

mã hóa: 53 = 6 (mod 7)
phép nhân: 62 = (53)2 = 56 = 1 (mod 7)
cộng: 53 · 52 = 55 = 3(mod 7) khoảng>

Lưu ý: Việc phân chia pha theo mô-đun hơi khó khăn và nằm ngoài phạm vi.
Hãy giải thích rõ ràng chức năng mã hóa:
E (v ) = gv(mod n)
Ở đây v là giá trị chúng ta muốn mã hóa.
Ghi chú 3.2 Chế độ mã hóa đồng cấu này có một hạn chế, chúng ta có thể nhân một giá trị được mã hóa và một giá trị không được mã hóa, nhưng chúng ta không thể Nhân (hoặc chia) hai giá trị được mã hóa, có nghĩa là chúng tôi không thể lũy thừa giá trị được mã hóa. Mặc dù những đặc tính này thoạt nhìn có vẻ không thân thiện nhưng chúng tạo thành nền tảng của zk-SNARK. Hạn chế này sẽ được thảo luận sau trong phần "Nhân giá trị được mã hóa".

Chú thích

even@ Anby Lab: Tập hợp được hình thành bằng phép toán mô-đun được gọi là "trường hữu hạn" và tập hợp được hình thành bằng cách tính số mũ và sau đó thực hiện phép toán mô-đun là bao gồm "Nhóm chu kỳ". Ngoài lũy thừa số nguyên modulo, các phương pháp mã hóa đồng cấu phổ biến còn bao gồm phép nhân trên các đường cong elip.

Đa thức mã hóa

Với những công cụ này, giờ đây chúng tôi có thể thực hiện các thao tác trên các số ngẫu nhiên được mã hóa x và sửa đổi giao thức không có kiến thức cho phù hợp.
Hãy xem cách tính đa thức p(x) = x³ – 3x² + 2x. Chúng ta đã nói rõ trước đó rằng biết một đa thức có nghĩa là biết các hệ số của nó, tức là trong ví dụ này: 1, -3, 2. Vì mã hóa đồng cấu không cho phép lũy thừa giá trị được mã hóa nên chúng ta phải cấp lũy thừa từ 1 đến 3 của x để có được giá trị được mã hóa: E(x), E(x²), E(x³), sau đó chúng ta phải tính toán Mã hóa đa thức là:
E(x3)1 · E(x2)-3 · E(x)2 = (gx³)1 · ( gx²) -3 ·(gx)2 = g1x³ · (g-3x²)·(gx)2 = g x³-3x²+2x
Vậy qua những điều này phép tính, chúng ta thu được kết quả tính toán được mã hóa của đa thức tại một số x chưa biết. Đây quả thực là một cơ chế rất mạnh mẽ, vì do tính chất đồng cấu nên thao tác mã hóa của cùng một đa thức luôn giống nhau trong không gian mã hóa.

Bây giờ chúng ta có thể cập nhật phiên bản trước của giao thức, chẳng hạn như đối với đa thức bậc d:

Người xác minh
Lấy một số ngẫu nhiên s, là giá trị bí mật
Khi số mũ i lấy giá trị 0, 1,...,d thì kết quả mã hóa của s lũy thừa i được tính tương ứng, điều đó là:
Đặt s vào để tính đa thức đích không được mã hóa: t(s)
Sẽ là các giá trị được mã hóa của lũy thừa được cung cấp cho người hoạt ngôn: E(s0), E(s1)
,
,
E(sd)

Prover
Tính đa thức h( x) = p(x)/t(x)
Tính g^p(s) bằng cách sử dụng các giá trị được mã hóa,,..., và hệ số,,...
Rồi tính E(h(s)) =gh(s)
Cung cấp kết quả gp và gh cho người xác minh

Người xác minh
Cuối cùng Bước đầu tiên là xác minh p = t(s) ·h: gp = (gh)t(s) => gp = gt(s )·h
Lưu ý: Vì người chứng minh không biết bất kỳ thông tin nào liên quan đến s nên điều này gây khó khăn cho anh ta trong việc đề xuất các kết quả tính toán trái luật có thể phù hợp với việc xác minh.

Mặc dù người chứng minh có tính linh hoạt hạn chế trong giao thức này, nhưng anh ta vẫn có thể thực hiện các phép tính mà không thực sự sử dụng giá trị được mã hóa do người xác minh cung cấp mà thông qua cách khác để giả mạo bằng chứng. Ví dụ: nếu người chứng minh tuyên bố có đa thức thỏa mãn điều kiện thì nó chỉ sử dụng 2 giá trị lũy thừa s3 và s1, không thể xác minh được trong giao thức hiện tại.

Chú thích

even@ Ambi Labs: Sử dụng công cụ mã hóa đồng cấu mạnh, một giao thức chứng minh không có kiến thức tương đối mạnh đã được xây dựng. Nhưng như đã đề cập ở trên, vẫn còn một số vấn đề ở đây - không thể xác minh liệu người chứng minh có thực sự sử dụng giá trị do người xác minh cung cấp để xây dựng bằng chứng hay không.

Bạn có thể suy nghĩ xem, giải quyết vấn đề này như thế nào? Và những sai sót trong thỏa thuận này là gì?

Trong phần tiếp theo, chúng ta sẽ tiếp tục thảo luận và chỉ ra cách xây dựng một đa thức hoàn chỉnh không có kiến thức. Chứng minh hiệp định.

Liên kết gốc

https://arxiv.org/pdf/1906.07221.pdf
https://medium.com/@ imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160
https://medium.com/@imolfar/why-and-how-zk -snark-works-2-proving-know-of-a-polynomial-f817760e2805

Tài liệu tham khảo

[ Bit +11]—Nir Bitansky, Ran Canetti, Alessandro Chiesa và Eran Tromer. Từ khả năng chống va chạm có thể trích xuất đến các lập luận ngắn gọn về kiến thức không tương tác và quay lại. Lưu trữ ePrint mật mã, Báo cáo 2011/443. https://eprint.iacr .org/2011/443. 2011
[Par+13]—Bryan Parno, Craig Gentry, Jon Howell và Mariana Raykova. Pinocchio: Tính toán gần như có thể kiểm chứng thực tế. Lưu trữ ePrint mật mã, Báo cáo 2013/279. https:// / /eprint.iacr.org/2013/279. 2013
[Rei16]—Christian Reitwiessner.zkSNARKs in a Nutshell. 2016. url: https://blog.ethereum.org/2016/12/05/zksnarks- trong -a-nutshell/
[But16]—Vitalik Buterin. Chương trình số học bậc hai: từ số 0 đến anh hùng. 2016. url: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero- tới -hero-f6d558cea649
[But17]—Vitalik Buterin. zk-SNARKs: Under the Hood. 2017. url: https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
[Gab17]—Ariel Gabizon. Giải thích về SNARK. 2017. url: https://z.cash/blog/snark-explain/
[Ben+14]—Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer và Madars Virza. Zerocash: Thanh toán ẩn danh phi tập trung từ Bitcoin. Lưu trữ ePrint mật mã, Báo cáo 2014/349. https://eprint.iacr.org/2014/349. 2014
[GMR85 ] —S Goldwasser, S Micali, và C Rackoff. "Sự phức tạp về kiến thức của các hệ thống chứng minh tương tác". Trong: Kỷ yếu của Hội nghị chuyên đề ACM thường niên lần thứ 17 về lý thuyết máy tính. STOC 　85. Providence, Rhode Island, Hoa Kỳ: ACM, 1985 , trang 291–304.isbn: 0–89791–151–2. doi: 10.1145/22145.22178. url: http://doi.acm.org/10.1145/22145.22178
[BFM88]—Manuel Blum, Paul Feldman và Silvio Micali. "Kiến thức không tương tác và các ứng dụng của nó". Trong: Kỷ yếu của Hội nghị chuyên đề ACM thường niên lần thứ 20 về lý thuyết máy tính. STOC 　88. Chicago, Illinois, USA: ACM, 1988, trang 103–112 . isbn: 0–89791–264–0. doi: 10.1145/62212.62222. url: http://doi.acm.org/10.1145/62212.62222
[Gro10]—Jens Groth. "Không tương tác dựa trên ghép nối ngắn " lập luận không có kiến thức". Trong: Hội nghị quốc tế về lý thuyết và ứng dụng mật mã và bảo mật thông tin. Springer. 2010, trang 321–340
[Gen+12]—Rosario Gennaro, Craig Gentry, Bryan Parno, và Mariana Raykova. Chương trình khoảng bậc hai và NIZK ngắn gọn không có PCP. Lưu trữ ePrint mật mã, Báo cáo 2012/215. https://eprint.iacr.org/2012/215. 2012
[Pik13]—Scott Pike. Đánh giá các hàm đa thức. 2013 . url: http://www.mesacc.edu/~scotz47781/mat120/notes/polynomials/evaluating/evaluating.html
[Pik14]—Scott Pike. Chia cho một đa thức. 2014. url: http:// www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/long_division/long_division.html

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