Nguồn: Cộng đồng Denglian
Bằng chứng không có kiến thức đã đạt được sự phát triển đáng kể trong 40 năm qua. đạt được độ phức tạp và hiệu quả. Ngày nay, các bài viết và dự án mới xuất hiện mỗi ngày, được xây dựng trên nền tảng ý tưởng và đổi mới phong phú.
Bạn muốn biết mọi chuyện bắt đầu như thế nào? Trong bài viết này, chúng ta sẽ đi sâu vào lịch sử của bằng chứng không có kiến thức, khám phá 10 bài báo mang tính bước ngoặt đã giúp định hình lĩnh vực này.
1 - Gốc
Goldwasser, Micali, 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 (1985) [^1]
We The first cột mốc quan trọng đưa chúng ta trở lại bài báo quan trọng đó vào năm 1985! Công trình này đã giới thiệu nhiều thuật ngữ và khái niệm nền tảng vẫn là cốt lõi của các bằng chứng không có kiến thức ngày nay.
Đầu tiên, bài viết xác định một hệ thống chứng minh, có mô hình là sự thỏa thuận giữa hai bên liên quan đến hai máy Turing xác suất: một máy chứng minh và một máy xác suất. một người xác nhận. Mục tiêu của hệ thống chứng minh là cho phép người chứng minh thuyết phục người xác minh rằng đầu vào x cho trước thuộc về ngôn ngữ hình thức L. Trong hầu hết các công việc ban đầu, bộ chứng minh không bị hạn chế về mặt tính toán, trong khi bộ xác minh bị hạn chế ở các phép tính thời gian đa thức. Khi kết thúc tương tác, người xác minh sẽ đưa ra "Chấp nhận" hoặc "Từ chối".
2 - Đơn đăng ký đầu tiên
Fiat, Shamir - Cách chứng minh bản thân: một giải pháp thiết thực cho vấn đề nhận dạng và chữ ký h2> strong> (1986) [^2]
Bài báo này của Fiat và Shamir, được xuất bản một năm sau công trình cơ bản về bằng chứng không có kiến thức, đã giới thiệu The ứng dụng thực tế đầu tiên của những khái niệm này. Họ đã đề xuất hai giao thức: lược đồnhận dạng có tính tương tác và lược đồ Chữ ký không tương tác. Sự khác biệt chính giữa hai điều này là trong sơ đồ nhận dạng, bên thứ ba có thể tự thuyết phục mình về một tuyên bố sai bằng cách tạo một bản ghi hợp lệ. Trong giao thức chữ ký, ngay cả một người chứng minh không trung thực cũng không thể thuyết phục bản thân về một tuyên bố sai, khiến chữ ký không thể giả mạo được.
Sơ đồ nhận dạng áp dụng hệ thống chứng minh số dư bậc hai như một giao thức tương tác, trong đó người xác minh gửi một thử thách ngẫu nhiên và người chứng minh sẽ phản hồi tương ứng. Lược đồ chữ ký sửa đổi điều này bằng cách thay thế thử thách của người xác minh bằng lệnh gọi hàm băm.
Tên tác giả nghe có quen không? Đây là ví dụ đầu tiên về một kỹ thuật tổng quát mạnh mẽ hiện được biết đến rộng rãi với tên gọiphương pháp phỏng đoán Fiat-Shamir. Nó cho phép chuyển đổi bất kỳ hệ thống bằng chứng tương tác tiền xu công khai nào sang không tương tác bằng cách thay thế thử thách của người xác thực bằng một truy vấn tới một oracle ngẫu nhiên (trong thực tế là hàm băm mật mã).
3 - Chính xác thì chúng ta có thể chứng minh điều gì?
Goldreich, Micali, Wigderson - Cách chứng minh tất cả các câu lệnh NP và phương pháp thiết kế giao thức mật mã bằng không kiến thức (1987) [^ 3
Bài báo năm 1986 này đưa ra một kết quả đáng chú ý:Mọi ngôn ngữ trong NP đều thừa nhận hệ thống chứng minh không có kiến thức . Điều này quan trọng vì nó có nghĩa là chúng ta có thể chứng minh tính đúng đắn của bất kỳ tuyên bố nào có thể được xác minh trong thời gian đa thức mà không tiết lộ thêm thông tin. Các tác giả chứng minh điều này bằng cách cung cấp một hệ thống chứng minh khả năng 3 màu của đồ thị, trong đó vấn đề là xác định xem các nút của đồ thị có thể được tô bằng ba màu sao cho không có hai nút liền kề nào có cùng màu hay không. Hơn nữa, bằng chứng chỉ giả định sự tồn tại của mã hóa xác suất.
Trực quan của chứng minh như sau: trong mỗi vòng,
- < phần style ="text-align: left;">Người chứng minh chọn cách sắp xếp ngẫu nhiên gồm ba màu,
- Người chứng minh hứa hẹn màu sắc sắp xếp của mỗi nút,
- Trình xác minh truy vấn hai nút liền kề và hỏi màu của chúng,
- Người chứng minh mở đầu lời hứa bằng cách tiết lộ màu của nút truy vấn.
- Nếu các màu khớp nhau, trình xác thực sẽ từ chối ngay lập tức .
Bằng cách chạy giao thức này ở mức độ đa thức, người xác minh tự tin với xác suất cao rằng người chứng minh biết một giá trị hợp lệ 3- Tô màu mà không cần tìm hiểu bất kỳ thông tin nào vì các màu mở ra đều được chọn ngẫu nhiên ở mỗi bước!
Có hai bài viết khác trong tác phẩm này cũng đáng chú ý không kém: Mọi thứ có thể chứng minh được đều có thể được chứng minh bằng không kiến thức[^4], điều này cho thấy mọi ngôn ngữ trong IP đều có hệ thống chứng minh không có kiến thức và IP = PSPACE [^5], điều này cho thấy IP cũng mạnh mẽ như PSPACE.
4 - Nguồn gốc của PCP và những bằng chứng ngắn gọn về không tương tác
< p style="text-align: left;">Micali -
Bằng chứng về mặt tính toán (2000) [^6]
Cái này Bài báo năm 2000, do Micali viết, là một đóng góp quan trọng trong lịch sử của chứng minh không có kiến thức. Nó thậm chí có thể được coi là cấu trúc SNARK đầu tiên, mặc dù thuật ngữ SNARK vẫn chưa được đặt ra!
Cấu trúc của Micali biến bất kỳ Bằng chứng có thể kiểm tra xác suất (PCP) nào thành một bằng chứng ngắn gọn và không tương tác. PCP là một bằng chứng có thể được xác minh bằng cách chỉ đọc một vài bit và kết quả chính, Định lý PCP [^7], cho thấy rằng mọi ngôn ngữ trong NP đều có bằng chứng có thể được xác minh chỉ bằng đọc các bit Không đổi để xác minh PCP!
Micali được xây dựng bằng Cây Merkle như sau:
- Người chứng minh xây dựng cây Merkle để chứng minh và gửi gốc cho người xác minh,
- Người xác minh truy vấn các bit cụ thể mà họ muốn kiểm tra, span>
- Trình chứng minh cung cấp đường dẫn xác thực của các bit này, và người xác minh Xác minh các đường dẫn này.
Cấu trúc này có thể được thực hiện ở dạng không tương tác (như một phiên bản tương tác của phép chuyển đổi đã được đề xuất bởi Kilian [ ^8]). Bài viết cũng tập trung vào hiệu quả tính toán: trên thực tế, người xác minh không cần nhận toàn bộ bằng chứng mà chỉ cần một số bit không đổi và đường dẫn chứng nhận, điều này làm cho bằng chứng trở nên nhỏ gọn. Hạn chế chính của hệ thống này là việc xây dựng PCP không thực tế, dẫn đến sự phát triển của các bằng chứng tiên tri tương tác (IOP), một dạng khái quát hóa của PCP có thể tạo ra các lập luận thực tế.
5 - IP hiệu quả kép
Goldwasser, Kalai, Rothblum - Máy tính được ủy quyền: Bằng chứng tương tác cho Muggles (2015) [^9]
Bài viết này tập trung chủ yếu vàohiệu quả và giới thiệugiao thức GKR nổi tiếng, một giao thức tương tác tiền xu công khai cho các mạch số học có sẵn. Đáng chú ý, cả trình xác minh và trình chứng minh đều chạy trong thời gian đa thức, khiến nó trở thành bằng chứng tương táchiệu quả gấp đôi.
Giao thức bắt đầu bằng việc người chứng minh và người xác minh đồng ý về một mạch số học có fan-in đầu vào là 2. Sau đó, bộ chuẩn sẽ gửi đầu ra được yêu cầu của mạch với các giá trị đầu vào. Giao thức tiến hành bằng cách kiểm tra các mạch theo từng lớp, bắt đầu từ lớp đầu ra và di chuyển về phía lớp đầu vào. Mỗi bước sẽ giảm các xác nhận của lớp hiện tại thành các xác nhận của lớp trước đó, cho đến khi người xác minh đến được lớp đầu vào, nơi họ có thể kiểm tra xem nó có khớp với đầu vào ban đầu hay không.
Trong mỗi bước, nguyên hàm chính được sử dụng là giao thức kiểm tra tổng [^10], là một Bằng chứng tương tác cho phép người chứng minh thuyết phục người xác minh về tổng các giá trị của đa thức biến v g với quyền truy cập oracle, được xác định trên siêu khối Boolean:
Do tính hiệu quả và đơn giản của nó, giao thức kiểm tra tổng và giao thức GKR được sử dụng rộng rãi trong thực tế. Để giải thích thêm, bạn có thể tìm thấy một cái nhìn tổng quan khác về các giao thức này trong ghi chú của Thaler [^11].
6 - SNARK thực tế đầu tiên
Gennaro, Gentry, Parno, Raykova - Chương trình khoảng bậc hai và NIZK ngắn gọn không có PCP (2013) [^12]
Bây giờ chúng ta chuyển sang bài viết giới thiệu cấu trúc SNARK thực tế đầu tiên! Công trình này đánh dấu đỉnh cao của nghiên cứu nhằm tạo ra SNARK không dựa vào các định lý PCP kém hiệu quả. Mặc dù định lý PCP cung cấp cấu trúc SNARK về mặt lý thuyết nhưng nó quá chậm để áp dụng vào thực tế, vì vậy các nhà nghiên cứu đã cố gắng tìm các giải pháp thay thế hiệu quả hơn. Ví dụ, Groth vào năm 2010 đã đề xuất một hệ thống lập luận không tương tác dựa trên các nhóm và cặp song tuyến tính [^13], mặc dù nó đòi hỏi thời gian bậc hai về phía người chứng minh. Tuy nhiên, bài viết này đạt được thời gian chứng minh tuyến tính, thể hiện sự cải thiện đáng kể cho các ứng dụng thực tế.
Công trình này đã mở đường cho các giao thức quan trọng khác, chẳng hạn nhưGiao thức Pinocchio[^14] và cuối cùng là giao thức nổi tiếng Groth16[^15] Hệ thống chứng minh. Bài báo cũng giới thiệu các chương trình khoảng bậc hai và các chương trình số học bậc hai, những cấu trúc vẫn còn quan trọng trong các hệ thống này.
Một nhược điểm đáng kể của các cấu trúc này là cần thiết lập đáng tin cậy, nghĩa là thông tin bí mật được tạo ra trong giai đoạn tạo chuỗi tham chiếu công khai (thường được gọi làChất thải độc hại) có thể được sử dụng để tạo ra các chứng nhận giả nếu không được tiêu hủy đúng cách. Ngoài ra, cách thiết lập này không phổ biến, có nghĩa là cần phải thiết lập mới cho mỗi mạch. Bất chấp những hạn chế này, kích thước chứng minh được tạo ra vẫn là nhỏ nhất trong số các cấu trúc khác nhau, khiến nó trở thành lựa chọn phổ biến cho nhiều ứng dụng.
Điều đáng nói là phiên bản đầu tiên của Zerocash [^16] là một ứng dụng Blockchain có ảnh hưởng sớm và có ảnh hưởng lớn, sử dụng zk- SNARK được xây dựng dựa trên các hệ thống này.
7 - PlonK SNARK
Gabizon, Williamson, Ciobotaru - PlonK: Hoán vị trên cơ sở Lagrange cho các lập luận không tương tác đại kết về kiến thức (2019) [^17]
Bài viết có ảnh hưởng lớn năm 2019 này giới thiệu PlonK SNARK, một hệ thống dựa trên bằng chứng oracle tương tác của đa thức (IOP), có nghĩa là người xác minh có thể thực hiện các thao tác trên một số truy cập oracle đa thức và có thể đánh giá nó tại các điểm đã chọn. Hệ thống sử dụng nhiều tiện ích đa thức để chứng minh các phát biểu về đa thức, trong đó đáng chú ý nhất làĐối số tích lớn, cho phép người chứng minh chỉ ra rằng tích của các đánh giá trên một miền là 1. Bằng cách sử dụng điều này, chúng ta có thể xây dựng mộtĐối số hoán vị để chứng minh rằng hai chuỗi là sự thay thế của nhau. Bằng cách sử dụng các tiện ích này, người chứng minh có thể xây dựng bằng chứng cho bất kỳ mạch số học nào và người xác minh có thể xác minh nó theo cách không tương tác.
Trong thực tế, quyền truy cập oracle đạt được thông qua Chương trình cam kết đa thức (PCS), cho phép người chứng minh:
- Cung cấp các giá trị mở để đánh giá đa thức tại một điểm cụ thể.
Điều này cho phép người xác minh truy vấn đa thức tại bất kỳ điểm nào và xác minh mối quan hệ IOP. PCS được đề xuất trong bài viết làChương trình cam kết KZG [^18], vừa hiệu quả vừa thiết thực. KZG cho phép người chứng minh cam kết đa thức dưới dạng một phần tử nhóm duy nhất và người xác minh có thể xác nhận các giá trị mở bằng cách tính toán một số cặp đường cong elip. Mặc dù KZG yêu cầu thiết lập đáng tin cậy nhưng nó có tính phổ quát và có thể được sử dụng trên bất kỳ mạch nào sau khi thiết lập. Tuy nhiên, PlonK có thể được kết hợp với các sơ đồ PCS khác để điều chỉnh nó cho phù hợp với các hệ thống lập luận minh bạch.
Hơn nữa, đối số hoán vị trong PlonK đã truyền cảm hứng cho đối số tìm. Đối số tra cứu cho phép bộ chứng minh chỉ ra rằng tất cả các phần tử của một chuỗi đều được chứa trong một chuỗi khác, điều này rất hữu ích cho kiến trúc zkVM. Đối số tra cứu cho phép phân tách nhân chứng thành các quỹ đạo nhỏ hơn và chứng minh mối quan hệ tra cứu giữa chúng, làm cho các bằng chứng phức tạp trở nên hiệu quả hơn.
8 - STARK
Ben-Sasson, Bentov, Horesh, Riabzev - Tính toàn vẹn tính toán an toàn sau lượng tử, có thể mở rộng, minh bạch và an toàn sau lượng tử (2018) [^19]
Bài viết này giới thiệu hệ thống chứng minh STARK, một hệ thống chứng minh phổ biến khác dựa trênFRI [^20], một bài kiểm tra độ gần cho giao thức IOP mã Reed-Solomon. Trong STARK, người chứng minh cam kết đánh giá đa thức bằng cách xây dựng cây Merkle trên một miền. Vì các giá trị đã cam kết ban đầu không xác định nên trình xác minh sử dụng FRI để xác nhận rằng các đánh giá này tạo thành một đa thức hợp lệ ở mức độ đủ thấp. Giao thức cũng hoạt động như một sơ đồ cam kết đa thức, cho phép người xác minh kiểm tra việc đánh giá đa thức cam kết tại bất kỳ điểm nào.
Một trong những tính năng nổi bật nhất của STARK là chúng chỉ dựa vào hàm băm chống va chạm mật mã và không có mật mã nào khác Các giả định học tập, chẳng hạn như bài toán logarit rời rạc. Điều này mang lại cho STARK một lợi thế về khả năng bảo mật sau lượng tử, vì các hàm băm chống va chạm được coi là an toàn ngay cả trước các cuộc tấn công lượng tử. Hơn nữa, STARKminh bạch, tức là chúng không yêu cầu bất kỳ thiết lập đáng tin cậy nào. Chúng cũngphổ quát, nghĩa là chúng không bị giới hạn ở một mạch cụ thể, mang lại sự linh hoạt trong nhiều ứng dụng.
9 - Đệ quy
Valiant - Tính toán hoặc bằng chứng kiến thức có thể kiểm chứng dần dần hàm ý hiệu quả về thời gian/không gian. (2008) [^21]
Một khái niệm quan trọng đã xuất hiện trong nhiều năm qua là đệ quy, có nghĩa đơn giản là một bằng chứng có thể được sử dụng để chứng minh rằng một bằng chứng khác là đúng. Kịch bản được trình bày trong bài viết này liên quan đến một người chứng minh mong muốn chứng minh tính đúng đắn của kết quả của một phép tính có khả năng kéo dài. Với máy Turing, chúng ta có thể chứng minh tính đúng đắn của một bước duy nhất của hàm chuyển trạng thái, nhưng điều này là chưa đủ; chúng ta muốn chứng minh tính đúng đắn của toàn bộ tính toán, bao gồm một chuỗi các chuyển đổi trạng thái.
Tính toán có thể kiểm chứng tăng dần (IVC) Ý tưởng đằng sau như sau: Giả sử chúng ta có thể chứng minh rằng một trạng thái chuyển đổi từ S1 sang S2 là đúng. Sau đó, chúng ta có thể kết hợp hai bằng chứng thành một: người chứng minh cho thấy rằng họ biết hai bằng chứng hợp lệ:
Bằng chứng được hợp nhất sẽ thuyết phục người xác minh rằng việc chuyển từ S1 sang S3 là chính xác. Quá trình này có thể được lặp lại với số bước bất kỳ, cho phép chúng ta cô đọng các phép tính dài tùy ý thành một bằng chứng duy nhất (cụ thể hơn là các phép tính dài đa thức).
Điều quan trọng cần lưu ý là cách xây dựng này dựa trên hai giả định chính:
- Chứng minh tính đúng đắn về mặt trí tuệ của hệ thống: Người chứng minh không chỉ phải chứng minh rằng một chuyển trạng thái Để có bằng chứng tồn tại, người ta cũng phải chứng tỏ rằng họ biết về chúng. Về mặt trực quan, thông qua khả năng trích xuất kiến thức quy nạp, chúng ta có thể rút ra bằng chứng về tất cả các chuyển đổi trạng thái riêng lẻ.
- Hàm băm trong thực tế là một nhà tiên tri ngẫu nhiên: Đây là một giả định mạnh mẽ hơn nhưng cần thiết để xác minh tính chính xác của bằng chứng neutron chứng minh tập hợp.
Mặc dù cấu trúc này rất hiệu quả về mặt lý thuyết nhưng lại rất tốn kém khi áp dụng trong thực tế. Để giải quyết vấn đề này, các phương pháp mới được đề xuất nhằm nâng cao hiệu quả. Một trong số đó là sử dụng sơ đồ gấp [^22] , giúp giảm bớt các giả định và tránh sự cần thiết phải xác minh SNARK đệ quy. Ý tưởng của phép gấp là cho trước hai bằng chứng π và π′, chúng ta có thể “gấp” chúng thành một bằng chứng duy nhất, π″. Người xác minh tin rằng nếu trường hợp gấp thỏa mãn thì trường hợp ban đầu cũng thỏa mãn <. span style="font-size: 16px;">
10 - Tính toán có thể kiểm chứng qua zkVM
Ben-Sasson, Chiesa, Tromer, Virza - Kiến thức không tương tác ngắn gọn về kiến trúc von Neumann (2014) [^23]
Bài viết cuối cùng này thảo luận về cấu trúc Máy ảo không kiến thức (zkVM) thực tế đầu tiên, là một máy ảo thực thi các chương trình tùy ý và tạo ra các bằng chứng tính toán chính xác này. Máy được mô tả tuân theo kiến trúc von Neumann, có nghĩa là các chương trình và dữ liệu được lưu trữ trong cùng một bộ nhớ, do đó hầu hết các CPU hiện đại đều dựa trên mô hình này, bất kỳ chương trình nào có thể chạy trên máy tính cổ điển cũng có thể chạy trên kiến trúc này. Bài viết giới thiệu một kiến trúc RISC có tên vnTinyRAM và hiển thị trình biên dịch C được chuyển sang tập lệnh này. Hệ thống chứng minh được thiết kế để xác minh tính chính xác của việc thực hiện chương trình theo một số bước cố định. một hàm chuyển đổi trạng thái lặp lại, được mở ra cho đến khi đạt đến giới hạn số lượng lệnh
Một lợi thế chính của zkVM ngày càng trở nên phổ biến là chúng có thể được viết bằng <. mạnh>ngôn ngữ lập trình cấp cao và sử dụng chúng để tạo bản thử nghiệm. Điều này mang lại lợi thế đáng kể so với việc viết mạch theo cách thủ công vì nhiều thuật toán và cấu trúc dữ liệu tiêu chuẩn đã được xác định bằng các ngôn ngữ cấp cao này. Ngoài ra, các nhà phát triển có thể sử dụng lại. các mô hình tính toán quen thuộc, giúp giảm đáng kể chi phí. Đường cong học tập để sử dụng bằng chứng không có kiến thức
Cũng cần lưu ý rằng nhiều zk-rollup dựa trên mô hình này. , ví dụ: hỗ trợ Máy ảo Ethereum (EVM). zk-rollup được thực thi sử dụng zkVM để chứng minh tính đúng đắn của việc thực thi EVM
Cuối cùng, bài báo. giới thiệu kiến trúc của riêng mình, được tối ưu hóa cho các hệ thống chứng minh không có kiến thức. Một ví dụ phổ biến khác về kiến trúc thân thiện với zk là Kiến trúc CPU Cairo [^24] , một CPU hoàn chỉnh của Turing được tối ưu hóa cho các bằng chứng sử dụng STARK.
Tài liệu tham khảo
[^1]: Goldwasser, S., Micali, S., & Rackoff, C. (1985). Sự phức tạp về kiến thức của các hệ thống chứng minh tương tác. (liên kết) ↩︎
[^2]: Fiat, A., & Shamir, A. (1986), Cách chứng minh bản thân: Giải pháp thực tế cho các vấn đề về nhận dạng và chữ ký (liên kết) ↩︎
[^3]: Goldreich, O., Micali, S., & 1987). Cách chứng minh tất cả các tuyên bố NP trong không có kiến thức và phương pháp thiết kế giao thức mật mã. (liên kết) ↩︎
[^4]: Ben-Or, M., Goldreich, O., Goldwasser, S. ., Håstad, J., Kilian, J., Micali, S., & Rogaway, P. (1990). Mọi thứ có thể chứng minh được đều có thể chứng minh được bằng không kiến thức. (liên kết) ↩︎
[^5]: Shamir, A. (1992). IP=PSPACE. (liên kết) ↩︎
[^6]: Micali, S. (2000). Bằng chứng về mặt tính toán ([link](https://people.csail.mit. .edu/silvio/Các bài báo khoa học chọn lọc/Hệ thống chứng minh/Computationally_Sound_Proofs.pdf)) ↩︎
[^7]: Cook, S. A. (1971). Xác minh bằng chứng và độ cứng của các bài toán gần đúng (liên kết) ↩︎
. [^8]: Kilian, J. (1992, tháng 7). Lưu ý về các bằng chứng và lập luận không có kiến thức hiệu quả (liên kết) ↩︎
[^9]: Goldwasser, S., Kalai, Y. T., & ; Rothblum, G. N. (2015). Tính toán ủy quyền: bằng chứng tương tác cho Muggle (liên kết, xem thêm ghi chú này của Justin Thaler) ↩︎
[^10]: Lund, C., Fortnow, L., Karloff, H. , & Nisan, N. (1992). Phương pháp đại số cho các hệ thống chứng minh tương tác. ↩︎
[^11]: Thaler, J. (2015). br>[^12]: Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013). Chương trình nhịp bậc hai và NIZK ngắn gọn không có PCP (liên kết) ↩︎
[^ 13]: Groth, J. (2010). 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. (liên kết) ↩︎
[^14]: Parno, B., Howell, J., Gentry, C ., & Raykova, M. (2016). Pinocchio: Tính toán gần như có thể kiểm chứng thực tế. ↩︎
[^15]: Groth, J. (2016). . (liên kết) ↩︎
[^16]: Sasson, E. B., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & ). Zerocash: Thanh toán ẩn danh phi tập trung từ bitcoin. (liên kết) ↩︎
[^17]: Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). (liên kết) ↩︎
[^18]: Kate, A., Zaverucha, G. M., & Goldberg, I. (2010).
[^19]: Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). link) ↩︎
[^20]: Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). (liên kết) ↩︎
[^21]: Valiant, P. (2008). Tính toán có thể kiểm chứng dần dần hoặc bằng chứng về kiến thức ngụ ý hiệu quả về thời gian/không gian (liên kết) ↩︎
[^22] : Kothapalli, A., Setty, S., & Tzialla, I. (2022, tháng 8). Nova: Lập luận không có kiến thức đệ quy từ các sơ đồ gấp. ., Tromer, E., & Virza, M. (2014). Kiến thức không tương tác ngắn gọn về kiến trúc von neumann (link) ↩︎
[^24]: Goldberg, L ., Papini, S. , &