Giới thiệu về bằng chứng không có kiến thức (1)

Tiêu đề gốc: "Thông tin khô khan | Giới thiệu về bằng chứng không có kiến thức (1)"

Nguồn gốc: Cộng đồng người Trung Quốc Nervos

Tiếp theo lần trước Shor đã đưa ra phản hồi cho Nghiên cứu toàn diện về các vấn đề định tuyến trong mạng thanh toán Sau đó, một số khác lại yêu thích nghiên cứu Cyte, người bạn nhỏ của Nervos, đã thực hiện nghiên cứu chi tiết về bằng chứng không có kiến thức.

Trong bài viết này Cyte sẽ giới thiệu đến các bạn định nghĩa về zero-know proof (ZKP) và so sánh zero-know proof với SNARK và STARK phân biệt hai khái niệm này.

Những khái niệm mật mã như ZKP, SNARK và STARK đã trở nên phổ biến nhờ sự phát triển gần đây của blockchain. Tuy nhiên, chúng thường bị hiểu lầm và sử dụng thay thế cho nhau. Trên thực tế, tất cả các khái niệm này thuộc một phạm trù rộng hơn gọi là Hệ thống chứng minh hoặc Bằng chứng mật mã. Có sự chồng chéo giữa các bằng chứng không có kiến thức, SNARK và STARK, nhưng chúng không bao gồm lẫn nhau. Mối quan hệ giữa chúng có thể được biểu diễn bằng sơ đồ.

Cái này bài viết Đầu tiên chúng tôi sẽ giới thiệu định nghĩa về hệ thống chứng minh và thảo luận về các đặc tính khác nhau của hệ thống chứng minh, tập trung vào "không có kiến thức", "chứng minh kiến thức", "đơn giản" và "không tương tác". Đặc biệt, nếu một hệ thống chứng minh có "không kiến thức" thì nó được gọi là "bằng chứng không có kiến thức". Cuối cùng, bài viết thảo luận và so sánh các định nghĩa về SNARK và STARK.

Hệ thống chứng minh

Hệ thống chứng minh là một giao thức tương tác giữa hai bên Người chứng minh và Người xác minh và Thiết lập thuật toán . Chức năng của hệ thống bằng chứng là cho phép Người chứng minh thuyết phục Người xác minh tin vào điều gì đó mà chúng tôi gọi là một tuyên bố.

Trước khi giao thức bắt đầu, ai đó cần gọi thuật toán Thiết lập. Thuật toán Thiết lập chấp nhận một số tham số công khai làm đầu vào và xuất ra thông tin Thiết lập mà Nhà cung cấp và Người xác minh yêu cầu, trong đó thông tin mà Người xác minh thu được được ký hiệu là , và thông tin mà Người cung cấp thu được được ký hiệu là . Phần chung của và được gọi là Chuỗi tham chiếu chung (CRS). Ai gọi thuật toán Thiết lập và khi nào phụ thuộc vào thiết kế của hệ thống chứng minh.

Khi bắt đầu giao thức, Người chứng minh và Người xác minh nhận được các câu lệnh đầu vào cùng một lúc. Người cung cấp phải có một số lợi thế bổ sung so với Người xác minh, chẳng hạn như sức mạnh tính toán mạnh hơn hoặc nhận được một số đầu vào bổ sung . Ngoài ra, Prover và Verifier cũng lần lượt học được . Thời gian cần thiết để có được thông tin Thiết lập tùy thuộc vào thiết kế của hệ thống chứng nhận. Ví dụ: Nhà cung cấp và Người xác minh có thể đã được tải xuống và lưu trữ trong ổ cứng tương ứng để sử dụng nhiều lần hoặc có thể đã được nhập ngay trước khi giao thức bắt đầu.

Sau đó, Người chứng minh và Người xác minh bắt đầu thực thi giao thức được chỉ định bởi hệ thống chứng minh. Nếu cả Người chứng minh và Người xác minh đều trung thực thì họ sẽ tuân thủ nghiêm ngặt quy trình. Tuy nhiên, cũng có thể một bên có ác ý và không thực hiện theo giao thức, điều gì sẽ xảy ra vào lúc này phụ thuộc vào tính bảo mật của hệ thống chứng minh. Nếu cả hai bên đều có ác ý và không tuân theo thỏa thuận thì điều đó không liên quan gì đến hệ thống bằng chứng này.

Cuối cùng, Người xác minh đưa ra kết quả chấp nhận hoặc từ chối, cho biết liệu họ có tin vào tuyên bố đó hay không.

Một hệ thống chứng minh cần phải thỏa mãn hai tính chất:

-Tính đầy đủ: Nếu câu là đúng và cả Nhà cung cấp và Người xác minh đều tuân thủ giao thức này thì kết quả đầu ra của Người xác minh chấp nhận với xác suất ít nhất là , trong đó được gọi là lỗi toàn vẹn của hệ thống bằng chứng (Lỗi hoàn chỉnh)

-Độ tin cậy (Tính đúng đắn): Nếu câu không chính xác thì Người chứng minh phải không trung thực và Người xác minh tuân thủ thỏa thuận thì không Nhà chứng minh nào có thể để Người xác minh xuất ra xác suất chấp nhận vượt quá . này được gọi là lỗi hợp lý của hệ thống chứng minh.

Hai yêu cầu này là những yêu cầu tối thiểu để thiết lập một hệ thống chứng minh. Nếu không có bất kỳ yêu cầu nào, chúng ta sẽ có được một hệ thống chứng minh đáp ứng được yêu cầu nhưng hoàn toàn vô dụng. Ví dụ: nếu chúng ta chỉ yêu cầu tính toàn vẹn thì bất kể Prover làm gì, Verifier sẽ luôn chỉ đưa ra chấp nhận; nếu chúng ta chỉ yêu cầu độ tin cậy thì hãy để Verifier luôn chỉ đưa ra từ chối. Ngoài ra, thông thường hy vọng và không vượt quá 1/2, tổng nhỏ hơn 2/3, nếu không điều này chứng tỏ lỗi hệ thống quá lớn và gần như vô dụng.

Nếu người ta chứng minh được độ tin cậy của một hệ thống chỉ đối với bất kỳ tính toán nào Prover với khả năng hạn chế được thiết lập, nghĩa là một đối thủ có sức mạnh tính toán vô hạn có thể đánh lừa Người xác minh, tại thời điểm này, hệ thống chứng minh chỉ có tính đúng đắn về mặt tính toán (Computational Soundness), hệ thống như vậy còn được gọi là Hệ thống luận cứ. Ngược lại, độ tin cậy an toàn đối với bất kỳ Prover nào được gọi là Độ tin cậy thống kê.

Chứng minh các tính chất khác của hệ

Một hệ thống chứng minh cũng có thể đáp ứng một số thuộc tính (không bắt buộc) khác

-Mô hình CRS: Nếu thông tin Thiết lập được mở cho tất cả mọi người Có thể thấy that Setup=Setup p=Setup v, hệ thống chứng minh này được cho là thuộc mô hình CRS

-Interactive (Tương tác) / Non-Interactive (Không tương tác) ): Nếu chỉ Prover gửi một tin nhắn đến Verifier trong toàn bộ quá trình tương tác thì hệ thống được gọi là hệ thống bằng chứng không tương tác, ngược lại hệ thống này là hệ thống bằng chứng tương tác

- Có thể chuyển nhượng/Từ chối: Nếu câu đúng và việc gửi quá trình tương tác đến những Người xác minh khác cũng có thể thuyết phục những Người xác minh khác về tính đúng đắn của câu thì hệ thống bằng chứng này có thể được chuyển nhượng; nếu không thì điều này Chứng minh rằng hệ thống này là không thể chối bỏ

-Người xác minh có thể xác minh công khai/Người xác minh được chỉ định: Nếu Setup v hiển thị công khai với mọi người, tức là bất kỳ ai cũng có thể trở thành Người xác minh, thì hệ thống bằng chứng Zero-knowed này có thể được xác minh công khai. Mặt khác, hệ thống này dành cho một người xác minh cụ thể

-Coin công khai: Nếu việc lựa chọn tất cả các tin nhắn của Người xác minh là ngẫu nhiên thống nhất và độc lập với các tin nhắn của Người chứng minh, thì hệ thống này là được cho là ngẫu nhiên công khai

-Zero-Knowledge: Trong trường hợp câu đúng, nếu tính đúng của bị loại trừ, , Người xác minh không thể thu được bất kỳ "kiến thức" nào khác từ sự tương tác, vì vậy hệ thống được cho là không có kiến thức

-Tính ngắn gọn: Nếu hệ thống chứng minh là Nó được sử dụng để chứng minh NP Ngôn ngữ và khối lượng giao tiếp của hệ thống chứng minh nhỏ hơn bằng chứng , thì hệ thống chứng minh này đơn giản

Ví dụ: Chứng minh hai quả bóng có màu khác nhau

Thông tin thiết lập: Có hai quả bóng

Tuyên bố : Hai quả bóng có màu khác nhau

1. Khả năng tính toán của Người xác minh bị hạn chế bởi (bị bịt mắt), Prover có thị lực bình thường

2. Người xác minh cầm một quả bóng trong mỗi tay và đưa nó cho Prover. Người xác minh đặt hai tay ra sau lưng và sau đó (trong đầu anh ta) tung một đồng xu ngẫu nhiên, nếu nó ngửa thì đổi bóng ở tay trái và tay phải, nếu không anh ta sẽ không đổi.

3. Người xác minh lấy quả bóng ra và đưa cho Người chứng minh.

4. Người kiểm chứng cho Người xác minh biết liệu hai quả bóng đã được trao đổi chưa.

Kết quả: Nếu Người chứng minh đoán đúng thì kết quả đầu ra của Người xác minh sẽ chấp nhận, nếu không thì kết quả đầu ra của Người xác minh sẽ từ chối.

Tầm quan trọng

Ở trên chúng tôi đã đưa ra định nghĩa, ví dụ và tính chất của hệ chứng minh. Tiếp theo chúng ta thảo luận một số tính chất quan trọng của hệ thống chứng minh.

Không có kiến thức

Không có kiến thức được sử dụng để bảo vệ Nhà cung cấp trung thực khỏi bị Người xác minh độc hại lừa dối và làm rò rỉ bằng chứng bí mật cần thiết để làm bằng chứng.

Bản chất không có kiến thức của hệ thống chứng minh đã được đề cập ở trên, được mô tả đơn giản là Người xác minh không thể có được bất kỳ "kiến thức nào". " từ sự tương tác." Mô tả này không chính xác vì nó không đưa ra tiêu chí nghiêm ngặt để đánh giá.

Bản thân định nghĩa về zero-know thức đã phản trực giác: Prover rõ ràng gửi một số bit dữ liệu tới Verifier, tại sao hệ thống này lại như vậy? "không có kiến thức"?

Trên thực tế, “thông tin” không giống như “kiến thức”. Nếu Người xác minh thu được thông tin, nhưng việc thu thập thông tin này không cho phép Người xác minh tính toán thêm kết quả hoặc thông tin đó có thể được chính Người xác minh tính toán thì Người xác minh chưa thu được bất kỳ "kiến thức" nào.

Trong quá trình thực thi hệ thống bằng chứng, tất cả thông tin mà Người xác minh thu được bao gồm: Thiết lập v; Số ngẫu nhiên r của riêng Người xác minh; Tất cả thông tin được Prover gửi tới Người xác minh (ký hiệu là p). Chúng tôi gọi thông tin này là "trường quan sát" của Người xác minh, ký hiệu là . Thông tin này là nguồn gốc của mọi sự không chắc chắn trong tính toán của Người xác minh. Một khi thông tin này được xác định, mọi thứ khác có thể được tính toán một cách xác định.

Chú ý rằng là một biến ngẫu nhiên. Khi Người xác minh và Người chứng minh thực hiện hệ thống chứng minh, Người xác minh sẽ lấy được mẫu của biến ngẫu nhiên này. Nếu Người xác minh có thể tự mình lấy mẫu mà không có sự tham gia của Người chứng minh thì hệ thống này không có kiến thức.

Chúng tôi gọi thuật toán lấy mẫu biến ngẫu nhiên là một trình mô phỏng. Theo các phương pháp làm việc khác nhau của trình mô phỏng, có các định nghĩa khác nhau như sau:

1. Trình mô phỏng không phải hộp đen, không có kiến thức tương ứng được gọi là không -hộp đen Không có kiến thức. Định nghĩa không có kiến thức này cho phép mỗi Người xác minh có một trình mô phỏng "được tùy chỉnh riêng". Định nghĩa này cho phép trình mô phỏng tùy chỉnh các quy trình lấy mẫu khác nhau dựa trên chi tiết triển khai của các Người xác minh khác nhau.

2. Trình mô phỏng hộp đen, tương ứng với kiến thức không về hộp đen. Định nghĩa không có kiến thức này yêu cầu sự tồn tại của một trình mô phỏng duy nhất sao cho nó có thể lấy mẫu cho tất cả Người xác minh. Trình mô phỏng duy nhất này không thể biết tất cả chi tiết triển khai cụ thể của Người xác minh, vì vậy nó chỉ có thể truy cập Người xác minh thông qua các cuộc gọi hộp đen. Tuy nhiên, trình mô phỏng có toàn quyền kiểm soát Người xác minh. Trình mô phỏng có thể xác định số ngẫu nhiên r của Người xác minh và nhập bất kỳ thông báo Người xác minh hoặc Thiết lập v nào vào Người xác minh. Do đó, trong mắt trình mô phỏng, Trình xác minh là một thuật toán xác định hộp đen.

3. Nếu trình mô phỏng chỉ nhắm mục tiêu Người xác minh trung thực thì người tương ứng là Người xác minh trung thực Zero Knowledge (Người xác minh trung thực ZK). Vì hành vi của những người xác minh trung thực hoàn toàn được mong đợi nên trình mô phỏng có thể khai thác thông tin này một cách tự nhiên, do đó quyền truy cập của trình mô phỏng vào trình xác minh không phải là hộp đen.

Trình mô phỏng không phải hộp đen có quyền truy cập vào nhiều thông tin hơn, do đó, không có kiến thức về hộp đen sẽ dễ thiết lập hơn so với không có kiến thức về hộp đen . Và Người xác minh trung thực không có kiến thức là cách dễ thực hiện nhất.

Về Verifier trung thực không có kiến thức, Verifier trung thực ở đây chính xác hơn là Semi-Honest, hay nói cách khác là “Trung thực nhưng tò mò” . Người xác minh như vậy có vẻ sẽ tuân thủ giao thức nhưng có thể bí mật cố gắng trích xuất kiến thức từ tin nhắn.

Ngược lại, hành vi của Người xác minh độc hại là hoàn toàn không bị hạn chế. Trình xác minh có thể gặp sự cố, gửi tin nhắn không phù hợp với định dạng, phân phối mẫu không tuân theo giao thức, v.v. Để chứng minh rằng một hệ thống hoàn toàn không có khả năng chống lại Người xác minh độc hại, tất cả các tình huống này phải được đề cập.

Trình mô phỏng là một thuật toán ngẫu nhiên và giá trị đầu ra của nó cũng là một biến ngẫu nhiên, được ghi là . Không có kiến thức yêu cầu hai biến ngẫu nhiên và không thể phân biệt được. Tuy nhiên, có nhiều phiên bản của từ "không thể phân biệt được", từ đó có thể dẫn ra nhiều định nghĩa khác nhau về bằng chứng không có kiến thức:

-Nếu phân phối hai ngẫu nhiên các biến không thể phân biệt được về mặt thống kê, tức là khoảng cách thống kê (Statistical Distance) của chúng không đáng kể, hệ thống chứng minh gọi là Statistically Zero-Knowledge (Statistically Zero-Knowledge); nếu khoảng cách thống kê bằng 0 thì còn gọi là Perfect Zero-Knowledge ( Không có kiến thức hoàn hảo) -Kiến thức);

-Nếu phân phối của hai biến ngẫu nhiên là Không thể phân biệt được về mặt tính toán, tức là bất kỳ đối thủ ngẫu nhiên theo thời gian đa thức nào cũng không thể phân biệt được giữa hai phân bố, được gọi là hệ thống chứng minh không có kiến thức về mặt tính toán (Computationally Zero-Knowledge).

Lưu ý rằng định nghĩa về không có kiến thức chỉ yêu cầu rằng đối với các phát biểu đúng, phân bố của  và  là không thể phân biệt được. Đối với các tuyên bố sai, chúng tôi không quan tâm Người xác minh có thể thu được kiến thức gì, vì trong trường hợp này Bản thân Người chứng minh là không trung thực và không cần phải bảo vệ điều đó. Nói cách khác, vì Người chứng minh không tuân thủ thỏa thuận, bất kể thỏa thuận của chúng ta được thiết kế tốt đến mức nào thì nó không thể được bảo vệ.

Tuy nhiên, mặc dù  sai, nhưng không có kiến thức không đưa ra bất kỳ giả định nào về việc phân phối . Nhưng nếu có là sự khác biệt đáng kể về xác suất thu được bằng cách nhập mẫu không chính xác và được Người xác minh xác minh và trường hợp đúng, chúng ta có thể sử dụng điều này để đánh giá tính đúng đắn của . Điều này có nghĩa là chỉ có thể đến từ ngôn ngữ NP tầm thường. Do đó, đối với các bài toán NP khó, nếu nhập sai vào trình mô phỏng thì thu được cũng có thể được xác minh với xác suất tương tự.

Trong trường hợp này, chẳng phải kiến thức bằng không và độ tin cậy là mâu thuẫn nhau sao? Nói cách khác, đối với lỗi, tại sao Prover không thể gọi trình giả lập để đánh lừa Verifier? Trên thực tế, Prover không thể kiểm soát Trình xác minh và không thể cung cấp cho trình mô phỏng các tài nguyên cần thiết để lấy mẫu. Thật vậy, một Prover độc hại có thể gọi trình mô phỏng, nhưng điều này là vô ích đối với nó, bởi vì r trong do trình mô phỏng xuất ra không phải là số ngẫu nhiên của Trình xác minh đang tương tác với Prover. Ngoài ra, đầu ra của trình mô phỏng có thể khác với đầu ra mà Người xác minh nhận được, khiến việc xác minh không thành công. Tuy nhiên, trình mô phỏng được Prover gọi lên không thể lấy được số lượng Người xác minh ngẫu nhiên, đủ để đảm bảo an ninh, vì vậy ngay cả khi là hằng số cố định trong bằng chứng tương tác thì cũng không có vấn đề gì.

Bằng chứng kiến thức

Nếu Nhà cung cấp được yêu cầu "biết" một số thông tin để Người xác minh vượt qua quá trình xác minh, hệ thống này được gọi là Bằng chứng về Kiến thức. Bằng chứng về kiến thức có thể được coi là một phiên bản nâng cao của độ tin cậy. Ngoài ra còn có một phiên bản tính toán của bằng chứng kiến thức, được gọi là Luận cứ về Kiến thức.

Hệ thống chứng minh tri thức thường được sử dụng để chứng minh các ngôn ngữ NP. Ngôn ngữ NP đề cập đến tập hợp , sao cho sự tồn tại của phần tử thuộc về   có thể được chứng minh bằng bằng chứng   nghĩa là có một thuật toán thời gian đa thức có thể xác định liệu   có phải là bằng chứng pháp lý cho thấy  ; thuộc về  .

Hệ thống chứng minh thông thường cho phép Người chứng minh chứng minh với Người xác minh. Hệ thống chứng minh kiến thức cho phép Prover chứng minh cho Verifier không chỉ mà còn cả Prover “biết” . Nói cách khác, ngay cả khi , nếu Prover không biết tương ứng thì sẽ khó xác minh được.

Tương tự như không có kiến thức đã thảo luận ở phần trước, “kiến thức” cũng cần một định nghĩa chặt chẽ. Một chương trình P "biết" dữ liệu . Nó nên được xác định như thế nào? Hãy tưởng tượng bạn đang chạy chương trình này trong một máy ảo và số ngẫu nhiên của nó có thể được chúng ta chỉ định theo ý muốn. Trong toàn bộ hoạt động của nó, máy ảo có thể ghi lại toàn bộ lịch sử trạng thái CPU cũng như tất cả các hoạt động đọc và ghi bộ nhớ. Nếu chương trình này "biết" , chúng ta nên trích xuất thông tin về từ các bản ghi này. Trên thực tế, đây là cách hiểu trực quan về Extractor. Trình trích xuất là một thuật toán chạy đồng thời với chương trình được trích xuất và có quyền truy cập vào trạng thái bên trong của chương trình được trích xuất. Cuối cùng, nó có thể xuất ra kết quả được trích xuất.

Trình trích xuất được mô tả ở trên là trình trích xuất không phải hộp đen vì nó có quyền truy cập vào trạng thái bên trong của chương trình được trích xuất. Thuật toán của trình trích xuất không phải hộp đen nhất thiết phải thay đổi tùy thuộc vào chương trình được trích xuất. Do đó, hệ thống chứng minh là một bằng chứng kiến thức, được định nghĩa như sau: "Đối với bất kỳ Prover  nào, đều có một trình trích xuất , thực thi cùng lúc với  và có thể truy cập trạng thái bên trong của . If  Sau khi và  tương tác,  đầu ra chấp nhận, thì  sẽ xuất ra đáp ứng các điều kiện."

Tương tự như trình mô phỏng ở trạng thái không có kiến thức định nghĩa, trình trích xuất cũng có thể được xác định theo cách hộp đen. Trình trích xuất không có quyền truy cập vào trạng thái bên trong của chương trình, nhưng nó có thể gọi chương trình, điều khiển các số ngẫu nhiên của chương trình và đọc đầu ra của chương trình. Chúng tôi giới thiệu ký hiệu như vậy để chỉ ra rằng trình trích xuất truy cập vào quá trình tương tác của một cặp Người chứng minh và Người xác minh theo cách hộp đen. Chỉ cần một trình trích xuất hộp đen cho tất cả Prover, do đó bằng chứng kiến thức có thể được định nghĩa như sau: "Có một trình trích xuất. Đối với bất kỳ trình trích xuất Prover  nào, nếu  tương tác với ,   đầu ra đều chấp nhận, thì  sẽ xuất ra thỏa mãn điều kiện."

Đơn giản

Đơn giản

h4>

Sử dụng  để biểu diễn một thể hiện của một ngôn ngữ NP và để thể hiện bằng chứng  tồn tại trong ngôn ngữ đó. Tính ngắn gọn đề cập đến một hàm tuyến tính chứng minh rằng giao tiếp mà hệ thống yêu cầu nhỏ hơn . Nói cách khác, Prover và Verifier triển khai hệ thống bằng chứng này, giúp tiết kiệm băng thông liên lạc so với việc Prover gửi trực tiếp đến Verifier. Đôi khi, tính đơn giản cũng có thể yêu cầu Người xác minh phải thực hiện ít công việc tính toán phức tạp hơn Người xác minh trong hệ thống chứng minh. Tóm lại, sự đơn giản đòi hỏi phải chứng minh được rằng hệ thống có ưu điểm về mặt hiệu quả.

Chúng ta có thể muốn một hệ thống chứng minh ngắn gọn với mức độ truyền đạt logarit hoặc thấp hơn, tức là . Tuy nhiên, những yêu cầu đơn giản như vậy sẽ mang lại những tổn thất về an ninh. Bởi vì nếu âm lượng liên lạc thấp đến mức logarit, thì toàn bộ không gian nơi đặt tổ hợp tin nhắn p của Prover có thể cạn kiệt trong thời gian . Tuy nhiên, độ tin cậy của hệ thống yêu cầu đối với câu sai , Prover không thể tìm thấy p cho phép Verifier vượt qua quá trình xác minh.

Nếu cái có thể được xác minh hoàn toàn không tồn tại thì điều này thực sự có thể đảm bảo độ tin cậy. Nhưng theo cách này, tính hợp pháp của   có thể được đánh giá bằng cách liệt kê đầy đủ p, khi đó   không phải là một vấn đề khó khăn, ngoại trừ các ngôn ngữ NP chung. Nếu chúng ta muốn có một hệ thống chứng minh tổng quát cho các ngôn ngữ NP, chúng ta phải cho phép rằng có một số lượng nhỏ p có thể được xác minh ngay cả đối với trường hợp sai .

Trong trường hợp này, chúng tôi chỉ có thể giới thiệu tham số bảo mật bổ sung và giảm kích thước của âm lượng liên lạc xuống , làm cho p đầy đủ trở nên phức tạp. mức độ đạt , ít nhất đạt được độ tin cậy theo nghĩa tính toán. Đồng thời, âm lượng liên lạc vẫn là logarit so với nên vẫn đảm bảo tính đơn giản.

Tóm lại, đối với các ngôn ngữ NP tổng quát, hệ thống chứng minh ngắn gọn (mức logarit) chỉ có thể là hệ thống lập luận.

Không tương tác

Không tương tác có nghĩa là toàn bộ tương tác của hệ thống bằng chứng chỉ là một tin nhắn được Nhà cung cấp gửi tới Người xác minh. Tin nhắn này được gọi là bằng chứng và được ghi là . Tính không tương tác có thể mang lại nhiều tiện lợi và mang lại nhiều kịch bản ứng dụng hơn cho hệ thống chứng minh. Ví dụ: trong hệ thống blockchain, bằng chứng không có kiến thức không tương tác có thể được đính kèm vào giao dịch để bất kỳ ai kiểm tra bất kỳ lúc nào mà không yêu cầu tác giả của giao dịch tương tác trực tuyến với người xác minh bất kỳ lúc nào.

Bất kỳ ngôn ngữ NP nào đương nhiên đều có giao thức chứng minh không tương tác, nghĩa là Nhà cung cấp gửi trực tiếp bằng chứng đến Người xác minh và bằng chứng này là bằng chứng kiến thức. Vì vậy, việc xây dựng một hệ thống chứng minh hoàn toàn không có tính tương tác là vô nghĩa. Tính không tương tác chỉ thú vị khi kết hợp với hai thuộc tính đã thảo luận trước đó, không có kiến thức hoặc tính đơn giản.

Không tương tác + không có kiến thức

Kết hợp không có kiến thức và không tương tác , có Kiến thức không tương tác (NIZK).

Chúng tôi đã đề cập trước đây khi thảo luận về kiến thức 0 rằng lý do tại sao kiến thức 0 không mâu thuẫn với độ tin cậy là do trình mô phỏng được lấy mẫu trong   r có khả năng cao là khác với số lượng ngẫu nhiên Người xác minh tương tác với Người chứng minh. Tuy nhiên, đối với kiến thức không có tính tương tác, chúng ta cần xem xét lại quá trình suy luận này.

Trong bằng chứng tương tác, Người xác minh có số ngẫu nhiên r1 rất có thể xác minh một thông báo p của Người xác minh đã được chuyển và trực tiếp chuyển nó đến một Trình xác minh có số ngẫu nhiên r2. Xác minh không thành công. Do đó, trong các bằng chứng tương tác, tính đúng đắn của p không mang tính toàn cục mà phụ thuộc vào r.

Trong bằng chứng không tương tác, Prover không nhận được bất kỳ tin nhắn nào từ Verifier nên quá trình tính toán của Prover không sử dụng số ngẫu nhiên r của Verifier. Do đó, để đạt được tính toàn vẹn của hệ thống bằng chứng, đầu ra p của Người kiểm chứng trung thực có thể được xác minh cho hầu hết các số ngẫu nhiên r của Người xác minh. Do đó, tính đúng đắn của p trong chứng minh không tương tác là toàn cục và không phụ thuộc vào bất kỳ r nào.

Không yêu cầu kiến thức, quan điểm của Người xác minh  và đầu ra của trình mô phỏng  là không thể phân biệt được. Điều này có nghĩa là nếu nhìn riêng lẻ các thành phần này thì không thể phân biệt được. Tức là   trong  và  cũng không thể phân biệt được. Do đó, Prover độc hại có thể gọi trình mô phỏng để xuất ra . Đây không phải là vấn đề trong các bằng chứng tương tác, trong đó Prover độc hại chỉ lấy p đúng cho một số r. Tuy nhiên, trong các chứng minh không tương tác, tính đúng đắn của p không phụ thuộc vào r, điều này sẽ gây ra vấn đề về bảo mật.

Lúc này đến lượt phát huy vai trò của mình. Mặc dù tính đúng đắn của p không còn phụ thuộc vào r nữa nhưng nó vẫn phụ thuộc vào . Vì mục đích đáng tin cậy, chúng tôi hy vọng rằng với   và câu lệnh , thật khó để tính p có thể vượt qua xác minh. Mặc dù trình mô phỏng có thể xuất ra đồng thời một cặp 0 khi được cung cấp , nhưng rất khó để tính toán cái trước và cái sau. Cách thực hiện cụ thể sẽ được giải thích chi tiết khi giới thiệu các giải pháp cụ thể ở các bài viết tiếp theo.

Không tương tác + đơn giản

Như đã đề cập ở trên, tính đơn giản của hệ thống chứng minh It phải là một hệ thống lập luận. Kết hợp với tính năng không tương tác, bạn có ARGument không tương tác ngắn gọn (SNARG). Trên thực tế, một hệ thống đáp ứng định nghĩa SNARG đã được Micali xây dựng ngay từ năm 2000 và cái tên này xuất hiện muộn hơn.

Nếu SNARG cũng là một đối số kiến thức, thì nó được gọi là Đối số kiến thức không tương tác ngắn gọn (SNARK). Cái tên SNARK được tiên phong bởi bài báo BCCT12 và hiện đã trở thành một trong những khái niệm nóng nhất trong lĩnh vực chứng minh không có kiến thức. Trên thực tế, SNARK chỉ ngắn gọn và không có tính tương tác và không nhất thiết không có kiến thức. Nếu nó không có kiến thức thì nó phải được gọi là zkSNARK.

Phân tích STARK và SNARK

Một khái niệm khác thường được nhắc đến cùng với SNARK là STARK. Nó chỉ khác SNARK một từ nhưng có rất nhiều điểm khác biệt. Hãy cùng so sánh hai khái niệm này dưới đây.

Điểm chung:

-Chúng đều là những lập luận về tri thức (ARK), tức là chúng chỉ đáng tin cậy về mặt tính toán, còn cách chứng minh mang tính trí tuệ

Sự khác biệt:

-Chữ “S” của SNARK là Sự gọn gàng, còn “S” của STARK là Khả năng mở rộng. đơn giản, nó cũng yêu cầu độ phức tạp của Prover cao nhất là gần tuyến tính, tức là 1, trong khi độ phức tạp tính toán của Setup cao nhất là logarit

- Minh bạch: STARK không yêu cầu Thiết lập đáng tin cậy của bên thứ ba; SNARK không có giới hạn này

-Non-Interactivity ): SNARK phải không tương tác, nhưng STARK không có hạn chế này

Có thể thấy hạn chế duy nhất của SNARK so với STARK là tính không tương tác. Tuy nhiên, thông qua phép chuyển đổi Fiat-Shamir sẽ được giới thiệu trong các bài viết tiếp theo, STARK thường có thể được chuyển đổi thành bằng chứng không tương tác và kết quả của chuyển đổi phải là SNARK. Theo nghĩa này, STARK có thể được coi là tập con của SNARK.

Các định nghĩa trên về SNARK và STARK là kết quả của những hai danh từ Ý nghĩa rộng. Theo nghĩa hẹp, chúng lần lượt đề cập đến hai phương án kết cấu cụ thể. SNARK đề cập đến một loạt các sơ đồ xây dựng zkSNARK dựa trên QAP và các cặp song tuyến được biểu thị bằng sơ đồ Groth16. Theo nghĩa hẹp, STARK đề cập cụ thể đến giải pháp dựa trên AIR và FRI do Ben-Sasson và cộng sự đề xuất vào năm 2018.

Tóm tắt

Bài viết này giới thiệu định nghĩa về hệ thống chứng minh và thảo luận các khía cạnh khác nhau của hệ thống chứng minh . Thuộc tính lớp, tập trung vào "không có kiến thức", "bằng chứng kiến thức", "sự chính xác" và "không tương tác", giải thích cách sử dụng trình mô phỏng để xác định không có kiến thức và trình trích xuất để xác định bằng chứng kiến thức. Cuối cùng bài viết thảo luận và so sánh SNARK và STARK.

Tài liệu tham khảo

Goldreich. Nền tảng của mật mã học, Tập 1. Các công cụ cơ bản. 2001.

Cộng đồng ZKProof. Tài liệu tham khảo của cộng đồng ZKProof. 2019. https://docs.zkproof.org/reference .pdf

Yehuda Lindell. Cách mô phỏng – Hướng dẫn về kỹ thuật chứng minh mô phỏng. 2018.

Eli Ben-Sasson. Sự bùng nổ của các bằng chứng tiền điện tử trong kỷ Cambri. https:/ /nakamoto.com/cambrian-explosion-of-crypto-proofs/

Liên kết gốc

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