ศูนย์ความรู้ Canon

หมายเหตุบรรณาธิการ: การเข้ารหัสลับ a16z มีชุดยาวของ “ปืน” จากเรา DAO แคนนอน ปีที่แล้วกับพวกเรา เอ็นเอฟที แคนนอน ก่อนหน้านี้ (และก่อนหน้านั้นต้นฉบับของเรา คริปโตแคนนอน) — อย่าลืมลงทะเบียนเพื่อรับ จดหมายข่าวประจำสัปดาห์ของ web3 สำหรับการอัปเดตเพิ่มเติมรวมถึงทรัพยากรที่ได้รับการดูแลจัดการอื่นๆ

ร้องไห้elow เราได้คัดสรรชุดแหล่งข้อมูลสำหรับผู้ที่แสวงหาความเข้าใจ เจาะลึก และสร้างด้วยทุกสิ่ง ศูนย์ความรู้: เทคโนโลยีพื้นฐานที่ทรงพลังซึ่งถือเป็นกุญแจสำคัญในการปรับขนาดบล็อกเชน และแสดงถึงอนาคตของแอปพลิเคชันที่รักษาความเป็นส่วนตัวและนวัตกรรมอื่นๆ อีกนับไม่ถ้วนที่จะมาถึง หากคุณมีข้อเสนอแนะสำหรับชิ้นส่วนคุณภาพสูงที่จะเพิ่ม แจ้งให้เราทราบ @a16zcrypto.

ระบบการพิสูจน์ความรู้ที่เป็นศูนย์มีมานานหลายทศวรรษแล้ว: การแนะนำโดย Shafi Goldwasser, Silvio Micali และ Charles Rackoff ในปี 1985 มีผลกระทบต่อการเปลี่ยนแปลงในด้านการเข้ารหัส และได้รับรางวัล ACM Turing Award ที่ Goldwasser และ Micali มอบให้ 2012. เนื่องจากงานนี้ รวมถึงการย้ายจากทฤษฎีไปสู่การปฏิบัติและการประยุกต์ใช้ใน crypto/web3 ในปัจจุบัน เป็นเวลาหลายสิบปีในการสร้าง เรายังแบ่งปันเป็นครั้งแรกในชุดศีลของเราในส่วนที่สอง (สำหรับตอนนี้ รวมไว้ที่นี่ด้านล่าง): รายการเรื่องรออ่านที่มีคำอธิบายประกอบโดย จัสติน ทาเลอร์ต่อจากตอนที่หนึ่งด้านล่าง

กิตติกรรมประกาศ: ขอบคุณ Michael Blau, Sam Ragsdale และ Tim Roughgarden ด้วย

รากฐาน ภูมิหลัง วิวัฒนาการ

เอกสารเหล่านี้บางส่วนยังเกี่ยวกับการเข้ารหัสโดยทั่วไป (ไม่ใช่ทั้งหมดที่ไม่มีความรู้ต่อ se) รวมถึงการสรุปปัญหาหรือความก้าวหน้าที่สำคัญที่ได้รับการแก้ไขโดยศูนย์การพิสูจน์ความรู้ในปัจจุบัน: วิธีรับรองความเป็นส่วนตัวและการรับรองความถูกต้องในเครือข่ายแบบเปิด

ทิศทางใหม่ในการเข้ารหัส (1976)
โดย Whitfield Diffie และ Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

วิธีการรับลายเซ็นดิจิทัลและระบบเข้ารหัสคีย์สาธารณะ
โดย Ronald Rivest, Adi Shamir, Leonard Adelman
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

โปรโตคอลสำหรับระบบเข้ารหัสคีย์สาธารณะ (1980)
โดย Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

การสื่อสารที่ปลอดภัยผ่านช่องทางที่ไม่ปลอดภัย (1978)
โดย Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

การใช้เส้นโค้งวงรีในการเข้ารหัส (1988)
โดย Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

ความซับซ้อนของความรู้ของระบบพิสูจน์เชิงโต้ตอบ (1985)
โดย Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

หลักฐานเสียงด้วยคอมพิวเตอร์ (2000)
โดย Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

ตั้งแต่การต้านทานการชนที่แยกออกมาได้ไปจนถึงการโต้แย้งความรู้ที่ไม่โต้ตอบอย่างรวบรัด [SNARK] และกลับมาอีกครั้ง (2011)
โดย Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

อาร์กิวเมนต์ศูนย์ความรู้ที่มีประสิทธิภาพสำหรับความถูกต้องของการสับเปลี่ยน (2012)
โดย Stephanie Bayer และ Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

ความรู้ศูนย์ที่ไม่โต้ตอบแบบรวบรัดสำหรับสถาปัตยกรรม von Neumann (2013)
โดย Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer และ Madars Virza
https://eprint.iacr.org/2013/879.pdf

ความสมบูรณ์ทางคอมพิวเตอร์ที่ปลอดภัยที่ปรับขนาดได้ โปร่งใส และหลังควอนตัม (2018)
โดย Eli Ben-Sasson, Iddo Bentov, Yinon Horesh และ Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

อาร์กิวเมนต์ที่ไม่มีความรู้ด้านเหรียญสาธารณะกับ (เกือบ) เวลาและพื้นที่ที่น้อยที่สุด (2020)
โดย Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum และ Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

ภาพรวมและบทนำ

หลักฐาน ข้อโต้แย้ง และความรู้เป็นศูนย์ — ภาพรวมของการคำนวณที่ตรวจสอบได้และการพิสูจน์และข้อโต้แย้งเชิงโต้ตอบ โปรโตคอลการเข้ารหัสที่ช่วยให้ผู้พิสูจน์สามารถให้การรับประกันแก่ผู้ตรวจสอบได้ว่าผู้พิสูจน์ดำเนินการคำนวณที่ร้องขออย่างถูกต้อง รวมถึงความรู้ที่เป็นศูนย์ (โดยที่หลักฐานไม่เปิดเผยข้อมูลอื่นใดนอกจากความถูกต้องของตนเอง) . ข้อโต้แย้งของ Zk มีแอปพลิเคชั่นมากมายในการเข้ารหัสและได้กระโดดจากทฤษฎีไปสู่การปฏิบัติในช่วงทศวรรษที่ผ่านมา
โดย Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

วิวัฒนาการของแบบจำลองสำหรับการพิสูจน์ความรู้ที่เป็นศูนย์ — การทบทวนการพิสูจน์ที่ไม่มีความรู้ โดยที่ Meiklejohn (University College London, Google) จะพิจารณาแอปพลิเคชันที่ขับเคลื่อนการพัฒนา รูปแบบต่างๆ ที่เกิดขึ้นเพื่อจับภาพการโต้ตอบใหม่เหล่านี้ โครงสร้างที่เราสามารถทำได้ และงาน เหลือให้ทำ
โดย Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

เซสชั่นไวท์บอร์ด ZK — โมดูลเบื้องต้น
กับ Dan Boneh et al
https://zkhack.dev/whiteboard/

ความปลอดภัยและความเป็นส่วนตัวสำหรับ crypto ด้วย zkps - บุกเบิกการพิสูจน์ความรู้ที่เป็นศูนย์ในทางปฏิบัติ zkps คืออะไรและทำงานอย่างไร ... รวมถึงการแสดงสด "สาธิต"
โดย Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

หัวข้อเทคโนโลยีชั้นนำอธิบาย — รวมถึงคำจำกัดความและความหมายของศูนย์ความรู้โดยทั่วไป
โดย Joe Bonneau, Tim Roughgarden, Scott Kominers, Ali Yahya, Chris Dixon
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

เลเยอร์ความเป็นส่วนตัวที่กำลังจะมาจะแก้ไขเว็บที่เสียหายได้อย่างไร
โดย Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

ข้อมูลเบื้องต้นเกี่ยวกับ zkSNARKs
กับ Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

ทำไมและอย่างไร zk-SNARK ทำงานอย่างไร: คำอธิบายที่ชัดเจน
โดย มักซิม เพชรกุส
https://arxiv.org/pdf/1906.07221.pdf

บทนำสู่การพิสูจน์ความรู้ที่เป็นศูนย์
โดย Fredrik Harrysson และ Anna Rose
https://www.zeroknowledge.fm/21 [+ การเขียนสรุปที่อื่น โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม]

Zk-SNARKs: ภายใต้ประทุน
โดย Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
1 ส่วนหนึ่ง, 2 ส่วนหนึ่ง, 3 ส่วนหนึ่ง

ความเร็วกระจายอำนาจ — เกี่ยวกับความก้าวหน้าในการพิสูจน์ความรู้ที่เป็นศูนย์ ฮาร์ดแวร์ที่กระจายอำนาจ
โดย Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

การวิจัย zk ที่ทันสมัย — กับนักวิจัย zk ที่ Ethereum Foundation
กับ แมรี่ มาลเลอร์, แอนนา โรส, โคบี กูร์กัน
https://zeroknowledge.fm/232-2/

สำรวจการวิจัย zk — กับผู้อำนวยการฝ่ายวิจัยที่ DFINITY; ยังอยู่เบื้องหลังความก้าวหน้าเช่น Groth16
กับ Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

การวิจัยและการสอนของ SNARK — กับหนึ่งในผู้ร่วมก่อตั้ง ZCash และ Starkware
กับ Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

เจาะลึกคู่มือผู้สร้าง

รากฐานของการพิสูจน์ความน่าจะเป็น — หลักสูตรที่มี 5 หน่วยจากการพิสูจน์เชิงโต้ตอบและอื่น ๆ
โดย Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs — ตอนที่ XNUMX, II, III
โดย Vitalik Buterin
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html

กายวิภาคของ STARK — บทช่วยสอนหกส่วนที่อธิบายกลไกของระบบพิสูจน์ STARK
โดย Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

การออกแบบ SNARK ตอนที่ 1 — สำรวจ, ใช้ในโรลอัพ, อื่นๆ
โดย Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

การออกแบบ SNARK ตอนที่ 2 — โรลอัพ ประสิทธิภาพ ความปลอดภัย
โดย Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

การวัดประสิทธิภาพ SNARK — ส่วนหน้า, แบ็กเอนด์, อื่นๆ
โดย Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

ทำความเข้าใจกับ PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

ระบบการพิสูจน์ความรู้เป็นศูนย์ของ PLONK — ชุดวิดีโอสั้น 12 เรื่องเกี่ยวกับวิธีการทำงานของ PLONK
โดย David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

จาก AIR ถึง RAP — วิธีการทำงานของเลขคณิตแบบ PLONK
โดย Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

การตรวจสอบหลายชุดใน PLONK และ Plookup
โดย Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

การออกแบบ Halo2 — จาก ECC
https://zcash.github.io/halo2/design.html

พลอนกี้2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

แอปพลิเคชันและบทช่วยสอน: การพิสูจน์แนวคิด การสาธิต เครื่องมือ และอื่นๆ

ใช้ zk — แหล่งเรียนรู้
โดย 0xPARC
https://learn.0xparc.org/materials/intro

สภาพแวดล้อมการพัฒนาออนไลน์สำหรับ zkSNARKs — zkREPL ชุดเครื่องมือใหม่สำหรับการโต้ตอบกับชุดเครื่องมือ Circom ในเบราว์เซอร์
โดย Kevin Kwok
https://zkrepl.dev (+ กระทู้อธิบาย โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม)

โปรแกรมเลขคณิตกำลังสองจากศูนย์ถึงฮีโร่
โดย Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

บน zkEVMs
กับ Alex Gluchowski และ Anna Rose
https://zeroknowledge.fm/175-2/

zkEVM ประเภทต่างๆ
โดย Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

การเรียนรู้ของเครื่อง ZK — บทช่วยสอน & การสาธิตสำหรับการวางโครงข่ายประสาทใน SNARK
โดย Horace Pan, Francis Ho และ Henri Palacci
https://0xparc.org/blog/zk-mnist

ในภาษา ZK
กับ Alex Ozdemir และ Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest — ใช้การเข้ารหัส zk กับเกม — เกม RTS (กลยุทธ์แบบเรียลไทม์) ที่กระจายอำนาจอย่างเต็มที่และต่อเนื่อง
https://blog.zkga.me/announcing-darkforest

ZKP สำหรับวิศวกร — ดูที่ Dark Forest ZKPs
https://blog.zkga.me/df-init-circuit

ดำดิ่งสู่ความรู้ที่เป็นศูนย์
นำแสดงโดย Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: การแบ่งปันข้อมูลที่ไม่มีความรู้
โดย Sam Ragsdale และ Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

crypto airdrops ที่ปกป้องความเป็นส่วนตัวโดยไม่มีการพิสูจน์ความรู้
โดย Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

พิธีการติดตั้งที่เชื่อถือได้บนเครือข่าย -
โดย Valeria Nikolaenko และ Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

กฎระเบียบของ Crypto, การเงินที่ผิดกฎหมาย, ความเป็นส่วนตัวและอื่น ๆ – รวมถึงส่วนที่เกี่ยวกับความรู้เป็นศูนย์ในบริบทการกำกับดูแล/การปฏิบัติตาม; ความแตกต่างระหว่าง "การรักษาความเป็นส่วนตัว" กับเทคโนโลยีที่ทำให้งงงวย
ร่วมกับ Michele Korver, ใจ รามาศวามี, โซนัล โชคชี
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

แหล่งข้อมูลอื่น ๆ

zkMesh จดหมายข่าว — จดหมายข่าวรายเดือนที่แบ่งปันข้อมูลล่าสุดเกี่ยวกับเทคโนโลยีการรักษาความเป็นส่วนตัวแบบกระจายศูนย์ การพัฒนาโปรโตคอลความเป็นส่วนตัว และระบบศูนย์ความรู้
https://zkmesh.substack.com/

ศูนย์ความรู้พอดคาสต์ — เกี่ยวกับการวิจัย zk ล่าสุด & แอปพลิเคชั่น zk และผู้เชี่ยวชาญที่สร้างเทคโนโลยีความเป็นส่วนตัวที่เปิดใช้งานการเข้ารหัส
กับแอนนา โรส
https://zeroknowledge.fm/

…รายการเรื่องรออ่านที่มีคำอธิบายประกอบ ตามหัวข้อและลำดับเหตุการณ์ โดย Justin Thaler:

SNARK จาก Linear PCP (หรือที่เรียกว่า SNARK พร้อมการตั้งค่าเฉพาะวงจร)

อาร์กิวเมนต์ที่มีประสิทธิภาพโดยไม่ต้อง PCP สั้น (2007)
โดย Yuval Ishai, Eyal Kushilevitz และ Rafail Ostrovsky

ก่อนประมาณปี 2007 SNARK ได้รับการออกแบบโดยหลักผ่าน Kilian-มิกาลี กระบวนทัศน์ของการพิสูจน์ "สั้น" ที่น่าจะตรวจสอบได้ (PCP) และ "รวบรวมการเข้ารหัส" เป็นอาร์กิวเมนต์สั้น ๆ ผ่านการแฮชของ Merkle และการแปลง Fiat-Shamir น่าเสียดายที่ PCP แบบสั้นนั้นซับซ้อนและใช้งานไม่ได้แม้กระทั่งในปัจจุบัน เอกสารนี้ (IKO) แสดงให้เห็นวิธีการใช้การเข้ารหัสแบบโฮโมมอร์ฟิคเพื่อให้ได้อาร์กิวเมนต์เชิงโต้ตอบที่กระชับ (ไม่โปร่งใส) จาก PCP ที่ "ยาว แต่มีโครงสร้าง" สิ่งเหล่านี้สามารถทำได้ง่ายกว่า PCP แบบสั้น และ SNARK ที่เป็นผลลัพธ์ก็มีการพิสูจน์ที่สั้นกว่ามากและการตรวจสอบที่รวดเร็วกว่า ข้อโต้แย้งเหล่านี้ได้รับการยอมรับในครั้งแรกว่ามีศักยภาพสำหรับประสิทธิภาพในทางปฏิบัติ และกลั่นกรองและนำไปปฏิบัติใน พริกไทย. น่าเสียดาย อาร์กิวเมนต์ของ IKO มีตัวพิสูจน์เวลากำลังสองและสตริงอ้างอิงที่มีโครงสร้างขนาดกำลังสอง ดังนั้นจึงไม่ได้ปรับขนาดเป็นการคำนวณขนาดใหญ่

โปรแกรม Quadratic Span และ NIZK ที่รัดกุมโดยไม่ต้องใช้ PCP (2012)
โดย Rosario Gennaro, Craig Gentry, Bryan Parno และ Mariana Raykova

เอกสารการพัฒนา (GGPR) นี้ช่วยลดต้นทุนการพิสูจน์ของแนวทางของ IKO จากกำลังสองในขนาดของวงจรเป็นควอซิลิเนียร์ ต่อยอดจากงานก่อนหน้าของ กรอท และ ลิปมามันยังให้ SNARKs ผ่านการเข้ารหัสแบบจับคู่ แทนที่จะเป็นอาร์กิวเมนต์แบบโต้ตอบเหมือนใน IKO มันอธิบาย SNARKs ของมันในบริบทของสิ่งที่เรียกว่าปัญหาความพึงพอใจข้อ จำกัด rank-1 (R1CS) ซึ่งเป็นลักษณะทั่วไปของความพอใจในวงจรเลขคณิต

บทความนี้ยังทำหน้าที่เป็นรากฐานทางทฤษฎีของ SNARK แรกๆ เพื่อดูการใช้งานเชิงพาณิชย์ (เช่น ใน ZCash) และนำไปสู่ ​​SNARKs โดยตรงที่ยังคงเป็นที่นิยมในปัจจุบัน (เช่น Groth16) การดำเนินการเบื้องต้นของข้อโต้แย้งของ GGPR มาถึงแล้ว ซาตาร์ และ Pinocchioและรุ่นหลังๆ ได้แก่ SNARK สำหรับ C และ BCTV. บีซีโอพี ให้กรอบการทำงานทั่วไปที่อธิบายการเปลี่ยนแปลงเชิงเส้น PCPs เป็น SNARK เหล่านี้ (ดูภาคผนวก A ของ ซาตาร์) และอธิบายอินสแตนซ์ต่างๆ ของสิ่งนั้น

เกี่ยวกับขนาดของอาร์กิวเมนต์ที่ไม่โต้ตอบตามการจับคู่ (2016)
โดย Jens Groth

เอกสารนี้ เรียกขานว่า Groth16 นำเสนอการปรับแต่ง SNARK ของ GGPR ที่บรรลุต้นทุนการตรวจสอบที่ล้ำสมัยแม้ในปัจจุบัน (การพิสูจน์เป็นองค์ประกอบ 3 กลุ่ม และการตรวจสอบถูกควบคุมโดยการดำเนินการจับคู่สามรายการ อย่างน้อยก็ให้เผยแพร่ต่อสาธารณะ อินพุตสั้น) ความปลอดภัยได้รับการพิสูจน์แล้วในรูปแบบกลุ่มทั่วไป

SNARKs พร้อมการตั้งค่าที่เชื่อถือได้สากล

PlonK: การเรียงสับเปลี่ยนเหนือฐาน Lagrange สำหรับอาร์กิวเมนต์ Oecumenical Noninteractive ของ Knowledge (2019)
โดย Ariel Gabizon, Zachary Williamson และ Oana Ciobotaru

Marlin: การประมวลผล zkSNARK ล่วงหน้าด้วย SRS . สากลและอัปเดตได้ (2019)
โดย Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely และ Nicholas Ward

ทั้ง PlonK และ Marlin แทนที่การตั้งค่าที่เชื่อถือได้เฉพาะวงจรใน Groth16 ด้วยการตั้งค่าสากล สิ่งนี้มาพร้อมกับการพิสูจน์ที่ใหญ่กว่า 4x-6x หนึ่งสามารถนึกถึง PlonK และ Marlin เป็นการทำงานเฉพาะวงจรระหว่างการตั้งค่าที่เชื่อถือได้ใน Groth16 และรุ่นก่อน และย้ายไปยังขั้นตอนก่อนการประมวลผลที่เกิดขึ้น หลังจาก การตั้งค่าที่เชื่อถือได้ตลอดจนระหว่างการสร้างการพิสูจน์ SNARK

ความสามารถในการประมวลผลวงจรตามอำเภอใจและระบบ R1CS ในลักษณะนี้บางครั้งเรียกว่าโฮโลแกรมหรือภาระผูกพันในการคำนวณ และยังได้อธิบายไว้ใน สปาร์ตัน (จะกล่าวถึงในภายหลังในการรวบรวมนี้) เนื่องจากมีงานเกิดขึ้นมากกว่าระหว่างการสร้างการพิสูจน์ ผู้พิสูจน์ของ PlonK และ Marlin จึงช้ากว่า Groth16 สำหรับวงจรที่กำหนดหรืออินสแตนซ์ R1CS อย่างไรก็ตาม ต่างจาก Groth16 ตรงที่ PlonK และ Marlin สามารถทำงานกับตัวแทนระดับกลางทั่วไปมากกว่า R1CS

แผนการผูกมัดพหุนามซึ่งเป็นรหัสดั้งเดิมในการเข้ารหัสลับที่สำคัญใน SNARK

คำมั่นสัญญาขนาดคงที่ต่อพหุนามและการประยุกต์ของพหุนาม (2010)
โดย Aniket Kate, Gregory Zaverucha และ Ian Goldberg

บทความนี้ได้นำเสนอแนวคิดเกี่ยวกับแผนการผูกมัดพหุนาม มันให้รูปแบบสำหรับพหุนามที่ไม่แปรผัน (โดยทั่วไปเรียกว่าข้อผูกมัด KZG) พร้อมข้อผูกมัดที่มีขนาดคงที่และหลักฐานการประเมิน โครงร่างใช้การตั้งค่าที่เชื่อถือได้ (เช่น สตริงอ้างอิงที่มีโครงสร้าง) และการเข้ารหัสที่ใช้การจับคู่ มันยังคงได้รับความนิยมอย่างมากในทางปฏิบัติในปัจจุบัน และใช้ใน SNARKs รวมถึง PlonK และ Marlin ที่กล่าวถึงข้างต้น (และ Groth16 ใช้เทคนิคการเข้ารหัสที่คล้ายคลึงกันอย่างมาก)

Fast Reed-Solomon Interactive Oracle พิสูจน์ความใกล้เคียง (2017)
โดย Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

ให้การพิสูจน์ oracle แบบโต้ตอบ (IOP) สำหรับการทดสอบ Reed-Solomon นั่นคือการพิสูจน์ว่าสตริงที่คอมมิตอยู่ใกล้กับตารางประเมินของพหุนามที่ไม่มีตัวแปร เมื่อรวมเข้ากับ Merkle-hashing และการแปลง Fiat-Shamir จะทำให้ได้โครงร่างพหุนามที่โปร่งใสพร้อมหลักฐานการประเมินที่มีขนาดพหุลอการิทึม (ดู VP19 เพื่อดูรายละเอียด) ปัจจุบันนี้ยังคงเป็นแผนพันธะพหุนามพหุนามหลังควอนตัมที่สั้นที่สุด

Ligero: อาร์กิวเมนต์ Sublinear น้ำหนักเบาโดยไม่ต้องตั้งค่าที่เชื่อถือได้ (2017)
โดย Scott Ames, Carmit Hazay, Yuval Ishai และ Muthuramakrishnan Venkitasubramaniam

คล้ายกับ FRI งานนี้ให้ IOP สำหรับการทดสอบ Reed-Solomon แต่มีความยาวการพิสูจน์รากที่สองแทนที่จะเป็นพหุลอการิทึม ตามทฤษฎี โรงงาน แสดงให้เห็นว่าโดยการสลับรหัส Reed-Solomon เป็นรหัสแก้ไขข้อผิดพลาดอื่นที่มีการเข้ารหัสที่เร็วขึ้น เราสามารถรับเครื่องพิสูจน์เวลาเชิงเส้นที่ใช้งานได้จริงในทุกสาขา แนวทางนี้ได้รับการขัดเกลาและนำไปปฏิบัติใน เบรกดาวน์ และ กลุ่มดาวนายพรานให้ประสิทธิภาพการพิสูจน์ที่ล้ำสมัย

Bulletproofs: หลักฐานสั้น ๆ สำหรับการทำธุรกรรมที่เป็นความลับและอื่น ๆ (2017)
โดย Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille และ Greg Maxwell

ปรับแต่งงานก่อนหน้าโดย บีซีซีจีพี, Bulletproofs ให้รูปแบบการผูกมัดพหุนามแบบโปร่งใส (อันที่จริง การวางนัยทั่วไปที่เรียกว่าอาร์กิวเมนต์ผลิตภัณฑ์ภายใน) โดยอิงจากความแข็งของการคำนวณลอการิทึมแบบไม่ต่อเนื่องที่มีขนาดการพิสูจน์ลอการิทึมแต่เวลาตัวตรวจสอบเชิงเส้น โครงการนี้ยังคงได้รับความนิยมในปัจจุบัน เนื่องจากมีความโปร่งใสและการพิสูจน์โดยย่อ (เช่น ใช้ใน ZCash Orchard และ Monero)

Dory: ข้อโต้แย้งที่มีประสิทธิภาพและโปร่งใสสำหรับผลิตภัณฑ์ภายในทั่วไปและพันธสัญญาพหุนาม (2020)
โดย Jonathan Lee

Dory ลดเวลาการตรวจสอบใน Bulletproofs จากเชิงเส้นเป็นลอการิทึม ในขณะที่ยังคงความโปร่งใสและการพิสูจน์ขนาดลอการิทึม (แม้ว่าจะมีขนาดใหญ่กว่ากันกระสุน) และความโปร่งใส ใช้การจับคู่และเป็นไปตามสมมติฐานของ SXDH

การพิสูจน์เชิงโต้ตอบ การพิสูจน์เชิงโต้ตอบหลายผู้พิสูจน์ และ SNARKs ที่เกี่ยวข้อง

การมอบหมายงานคอมพิวเตอร์: หลักฐานเชิงโต้ตอบสำหรับมักเกิ้ล (2008)
โดย Shafi Goldwasser, Yael Tauman Kalai และ Guy Rothblum

ก่อนหน้าบทความนี้ หลักฐานเชิงโต้ตอบสำหรับวัตถุประสงค์ทั่วไปจำเป็นต้องมี a superpolynomial-เวลา พิสูจน์ เอกสารนี้ให้โปรโตคอลการพิสูจน์เชิงโต้ตอบ ซึ่งเรียกกันทั่วไปว่าโปรโตคอล GKR พร้อมเครื่องพิสูจน์เวลาพหุนามและตัวตรวจสอบเวลาควอซิลิเนียร์ สำหรับปัญหาใดๆ ที่มีอัลกอริธึมคู่ขนานที่มีประสิทธิภาพ (ในทำนองเดียวกัน การพิสูจน์เชิงโต้ตอบใช้กับวงจรเลขคณิตใดๆ ที่มีความลึกเล็กน้อย)

การคำนวณที่ตรวจสอบแล้วในทางปฏิบัติพร้อมการพิสูจน์เชิงโต้ตอบแบบสตรีมมิ่ง (2011)
โดย Graham Cormode, Michael Mitzenmacher, Justin Thaler

เอกสารนี้ (บางครั้งเรียกว่า CMT) ลดเวลาพิสูจน์ในโปรโตคอล GKR จากควอร์ติกในขนาดของวงจรเป็นควอซิลิเนียร์ ผลิตการใช้งานครั้งแรกของการพิสูจน์เชิงโต้ตอบเอนกประสงค์ ผลงานที่ตามมา (เจรื่องเทศชนิดหนึ่ง, ธาเลอร์13, ยีราฟและ ราศีตุล) ลดเวลารันไทม์ของโพรบลงอีก จากควอซิลิเนียร์เป็นเชิงเส้นในขนาดของวงจร

vSQL: การตรวจสอบการสืบค้นข้อมูล SQL โดยพลการบนฐานข้อมูลไดนามิกเอาต์ซอร์ซ (2017)
โดย Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos และ Charalampos Papamanthou

แม้ว่าชื่อเรื่องจะอ้างอิงถึงพื้นที่การใช้งานเฉพาะ (ฐานข้อมูล) การมีส่วนร่วมของบทความนี้ก็เป็นเรื่องทั่วไป โดยเฉพาะอย่างยิ่ง สังเกตได้ว่าสามารถหาข้อโต้แย้งที่รัดกุมสำหรับความพอใจของวงจรได้โดยการรวมการพิสูจน์เชิงโต้ตอบกับแผนการผูกมัดพหุนาม (สำหรับพหุนามพหุเชิงเส้น)

ต่อมา โรงงาน การแสดงผล อาร์กิวเมนต์ไม่มีความรู้และแนะนำแผนความมุ่งมั่นที่แตกต่างกันสำหรับพหุนามพหุเชิงเส้น

Spartan: zkSNARK ที่มีประสิทธิภาพและใช้งานได้ทั่วไปโดยไม่ต้องตั้งค่าที่เชื่อถือได้ (2019)
โดย ศรีนาถ เศรษฐ์

รับ SNARKs สำหรับความพอใจของวงจรและ R1CS โดยการรวมการพิสูจน์เชิงโต้ตอบหลายผู้พิสูจน์ (MIP) เข้ากับแผนการผูกมัดพหุนาม ต่อยอดจากงานก่อนหน้าใน MIP ที่มีประสิทธิภาพเป็นรูปธรรมซึ่งเรียกว่า ไม้จำพวกถั่ว. ผลที่ได้คือการได้รับ SNARK ที่มีหลักฐานสั้นกว่าที่ได้จากการพิสูจน์เชิงโต้ตอบ เช่น โปรโตคอล GKR ที่กล่าวถึงข้างต้น คล้ายกับ PlonK และ Marlin สปาร์ตันยังแสดงวิธีการประมวลผลวงจรตามอำเภอใจและระบบ R1CS ผ่านการประมวลผลล่วงหน้าและการสร้างการพิสูจน์ SNARK

สปาร์ตันใช้แผนการผูกมัดพหุนามจาก hyrax. ผลงานที่ตามมาเรียกว่า เบรกดาวน์ และ กลุ่มดาวนายพราน รวม MIP ของ Spartan กับแผนการผูกมัดพหุนามอื่น ๆ เพื่อให้ได้ SNARKs ที่นำมาใช้ครั้งแรกด้วยเครื่องพิสูจน์เวลาเชิงเส้น

PCP แบบสั้นและ IOPs

PCP แบบสั้นพร้อม Polylog Query Complexity (2005)
โดย Eli Ben-Sasson และ Madhu Sudan

 งานเชิงทฤษฎีนี้ให้การพิสูจน์ความน่าจะเป็นครั้งแรกที่ตรวจสอบได้ (PCP) ที่มีความยาวของการพิสูจน์เป็นควอซิลิเนียร์ในขนาดของการคำนวณที่จะตรวจสอบและต้นทุนการสืบค้นแบบพหุลอการิทึม (แม้ว่าเวลาตัวตรวจสอบเชิงเส้น) หลังจากการแปลง PCP ของ Kilian-Micali เป็น SNARK นี่เป็นขั้นตอนสู่ SNARK ด้วยเครื่องพิสูจน์เวลากึ่งเชิงเส้นและตัวตรวจสอบเวลาหลายลอการิทึม

ต่อมางานทฤษฎี ลดเวลาของผู้ตรวจสอบเป็นพหุลอการิทึม ภายหลัง งานที่เน้นการปฏิบัติจริงได้ขัดเกลาแนวทางนี้ แต่ PCP สั้น ๆ ยังคงไม่สามารถทำได้ในปัจจุบัน เพื่อให้ได้ SNARK ที่ใช้งานได้จริง ต่อมา โรงงาน หัน ไปยัง ลักษณะทั่วไปเชิงโต้ตอบของ PCP ที่เรียกว่า Oracle Proofs เชิงโต้ตอบ (ไอโอพี) ความพยายามเหล่านี้นำไปสู่และต่อยอด ฟรีซึ่งเป็นโครงการผูกมัดพหุนามยอดนิยมที่กล่าวถึงในส่วนพันธะสัญญาพหุนามของการรวบรวมนี้

ผลงานอื่นๆ ในหมวดนี้ได้แก่ สเคบู และลูกหลานของมัน สิ่งเหล่านี้ไม่ได้พิสูจน์อย่างรัดกุม แต่มีปัจจัยคงที่ที่ดีและด้วยเหตุนี้จึงน่าสนใจสำหรับการพิสูจน์ข้อความเล็ก ๆ พวกเขาได้นำไปสู่ตระกูลของลายเซ็นหลังควอนตัมเช่น ปิกนิก ที่มี รับ การปรับให้เหมาะสม in หลาย โรงงาน. ZKBoo นำเสนอตามกระบวนทัศน์การออกแบบที่แตกต่างกันซึ่งเรียกว่า MPC ในหัวแต่ให้ผล IOP

SNARK แบบเรียกซ้ำ

การคำนวณที่ตรวจสอบได้แบบเพิ่มหน่วยหรือการพิสูจน์ความรู้โดยนัยถึงประสิทธิภาพของเวลา/พื้นที่ (2008)
โดย Paul Valiant

งานนี้นำเสนอแนวคิดพื้นฐานของการคำนวณที่ตรวจสอบได้แบบเพิ่มหน่วย (IVC) ซึ่งเป็นเครื่องพิสูจน์ที่ดำเนินการคำนวณและเก็บรักษาหลักฐานว่าการคำนวณนั้นถูกต้องตลอดเวลา มันสร้าง IVC ผ่านองค์ประกอบแบบเรียกซ้ำของ SNARK ที่นี่ ความรู้-ความสมบูรณ์ คุณสมบัติของ SNARKs เป็นสิ่งจำเป็นในการสร้างความสมบูรณ์ของอาร์กิวเมนต์ที่ไม่โต้ตอบที่ประกอบด้วยการเรียกซ้ำ บทความนี้ยังให้ความรู้ที่มีประสิทธิภาพมากสำหรับ SNARK ที่ได้มาจาก PCP (ตามกระบวนทัศน์ Kilian-Micali)

Zero Knowledge ที่ปรับขนาดได้ผ่านวงจรของ Elliptic Curves (2014)
โดย Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer และ Madars Virza

กำลังติดตาม งานเชิงทฤษฎีเอกสารนี้ใช้แอปพลิเคชันแบบเรียกซ้ำของตัวแปร SNARK ของ GGPR เพื่อให้การนำ IVC ไปใช้ครั้งแรกสำหรับเครื่องเสมือนอย่างง่าย (TinyRAM จาก SNARK สำหรับ C กระดาษ).

ยังได้แนะนำแนวคิดเรื่องวงจรของเส้นโค้งวงรี ซึ่งมีประโยชน์สำหรับการเขียน SNARK แบบเรียกซ้ำซึ่งใช้ประโยชน์จากการเข้ารหัสแบบเส้นโค้งวงรี

องค์ประกอบการพิสูจน์แบบเรียกซ้ำโดยไม่มีการตั้งค่าที่เชื่อถือได้ (2019)
โดย Sean Bowe, Jack Grigg และ Daira Hopwood

งานนี้ (เรียกว่า Halo) ศึกษาวิธีการเขียน SNARK ที่โปร่งใสแบบเรียกซ้ำ สิ่งนี้ท้าทายกว่าการเขียนแบบไม่โปร่งใส เนื่องจากขั้นตอนการตรวจสอบใน SNARK แบบโปร่งใสอาจมีราคาแพงกว่ามาก

สิ่งนี้จุดประกายให้ เส้น of งาน ที่มีจุดสุดยอดในระบบต่างๆ เช่น โนวา บรรลุประสิทธิภาพ IVC ที่ล้ำสมัย เหนือกว่าแม้กระทั่งที่ได้จากองค์ประกอบของ SNARK ที่ไม่โปร่งใส เช่น Groth16

การใช้งาน

Zerocash: การกระจายการชำระเงินแบบไม่ระบุชื่อจาก Bitcoin (2014)
โดย Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

ต่อยอดจากงานเดิม ได้แก่ Zerocoin (และด้วย เหรียญพินโนชิโอ เป็นงานพร้อมกัน) บทความนี้ใช้ SNARK ที่ได้มาจาก GGPR เพื่อออกแบบสกุลเงินดิจิทัลส่วนตัว นำไปสู่ ​​ZCash

Geppetto: การคำนวณที่ตรวจสอบได้เอนกประสงค์ (2014)
โดย Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno และ Samee Zahur

Geppetto อาจมีเนื้อหาล่วงหน้าก่อนการระเบิดของความสนใจในการดำเนินการสัญญาอัจฉริยะส่วนตัว โดยเขียนขึ้นประมาณหนึ่งปีหลังจากการสร้าง Ethereum ดังนั้นจึงไม่ได้นำเสนอในบริบทของการดำเนินการตามสัญญาอัจฉริยะส่วนตัว อย่างไรก็ตาม มันใช้การเรียกซ้ำในเชิงลึกของ SNARK เพื่อให้ผู้พิสูจน์ที่ไม่น่าเชื่อถือสามารถรันโปรแกรมคอมพิวเตอร์ส่วนตัว (ที่ตกลง/ลงนาม) ใดๆ บนข้อมูลส่วนตัว โดยไม่เปิดเผยข้อมูลเกี่ยวกับโปรแกรมที่กำลังรันหรือข้อมูลที่รันอยู่ ดังนั้นจึงเป็นบรรพบุรุษของงานบนแพลตฟอร์มสัญญาสมาร์ทส่วนตัวเช่น เซ็กซ์ [อธิบายไว้ด้านล่าง].

ASIC ที่ตรวจสอบได้ (2015)
โดย Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

บทความนี้พิจารณาถึงปัญหาในการใช้ ASIC อย่างปลอดภัยและได้ผลซึ่งผลิตในโรงหล่อที่ไม่น่าเชื่อถือ (ในปี 2015 มีเพียงห้าประเทศที่มีโรงหล่อระดับบนสุด) วิธีการคือการมี ASIC ที่รวดเร็วแต่ไม่น่าเชื่อถือพิสูจน์ความถูกต้องของเอาต์พุตไปยังตัวตรวจสอบที่ทำงานบน ASIC ที่ช้ากว่าแต่เชื่อถือได้ วิธีแก้ปัญหานี้น่าสนใจตราบเท่าที่เวลาดำเนินการทั้งหมดของระบบ (เช่น ผลรวมของรันไทม์ของโพรเวอร์และผู้ตรวจสอบ บวกกับค่าใช้จ่ายในการส่งข้อมูลใดๆ) น้อยกว่าค่าพื้นฐานที่ไร้เดียงสา: เวลาที่ต้องใช้ในการคำนวณแบบเต็มเมื่อทำงานช้าลง -แต่ ASIC ที่เชื่อถือได้ การใช้การพิสูจน์เชิงโต้ตอบ GKR/CMT/Allspice ที่แปรผัน ทำให้กระดาษสามารถเอาชนะพื้นฐานที่ไร้เดียงสาสำหรับปัญหาพื้นฐานหลายประการ รวมถึงการแปลงทฤษฎีจำนวน การจับคู่รูปแบบ และการดำเนินการโค้งวงรี งานนี้ชี้ให้เห็นว่าระบบการพิสูจน์บางระบบมีความเหมาะสมสำหรับการใช้งานฮาร์ดแวร์มากกว่าระบบอื่น ขณะนี้กำลังรับการเพิ่มประสิทธิภาพระบบพิสูจน์สำหรับการใช้งานฮาร์ดแวร์ มาก ความสนใจแต่ยังต้องสำรวจอีกมาก

ตรวจสอบได้ ฟังก์ชั่นการหน่วงเวลา (2018)
โดย Dan Boneh, Joseph Bonneau, Benedikt Bünz และ Ben Fisch

แนะนำสัญกรณ์ของฟังก์ชันการหน่วงเวลาที่ตรวจสอบได้ (VDFs) ซึ่งเป็นพื้นฐานการเข้ารหัสที่มีประโยชน์อย่างกว้างขวางในแอปพลิเคชันบล็อกเชน เช่น ในการบรรเทาการจัดการที่เป็นไปได้ของโปรโตคอลฉันทามติที่พิสูจน์หลักฐานของการมีส่วนได้เสีย SNARK (โดยเฉพาะอย่างยิ่งสำหรับการคำนวณที่ตรวจสอบได้แบบเพิ่มหน่วย) เสนอเส้นทางไปยัง VDF ที่ล้ำสมัย

Zexe: การเปิดใช้งานการคำนวณส่วนตัวแบบกระจายอำนาจ (2018)
โดย Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra และ Howard Wu

Zexe คือการออกแบบสำหรับแพลตฟอร์มสัญญาอัจฉริยะส่วนตัว สามารถดู Zexe เป็นส่วนขยายของ Zerocash (อธิบายไว้ด้านบน) Zerocash ช่วยให้แอปพลิเคชั่นเดียวทำงานบนเครือข่าย (ทำให้ผู้ใช้สามารถโอนโทเค็นได้) ในขณะที่ปกป้องความเป็นส่วนตัวของข้อมูลผู้ใช้ เช่น ใครที่พวกเขากำลังส่งโทเค็นให้ รับโทเค็นจากจำนวนโทเค็นที่โอน ฯลฯ Zexe อนุญาตให้มีมากมาย แอปพลิเคชันต่างๆ (สัญญาอัจฉริยะ) เพื่อทำงานบนบล็อกเชนเดียวกันและโต้ตอบซึ่งกันและกัน ธุรกรรมจะดำเนินการนอกเครือข่าย และมีการโพสต์หลักฐานการดำเนินการที่ถูกต้องในเครือข่าย ความเป็นส่วนตัวของข้อมูลไม่เพียงได้รับการคุ้มครองเท่านั้น ความเป็นส่วนตัวของฟังก์ชันก็เช่นกัน ซึ่งหมายความว่าหลักฐานที่เกี่ยวข้องกับการทำธุรกรรมแต่ละครั้งไม่ได้เปิดเผยว่าแอปพลิเคชันใดที่เกี่ยวข้องกับธุรกรรม ผลงานทางวิศวกรรมทั่วไปของ Zexe คือเปิดตัว BLS12-377 ซึ่งเป็นกลุ่มเส้นโค้งวงรีที่มีประโยชน์สำหรับองค์ประกอบเชิงลึกที่มีประสิทธิภาพ 1 ของ SNARK ที่ใช้การจับคู่

เครื่องจำลองสถานะโดยไม่ต้องดำเนินการจำลอง (2020)
โดย Jonathan Lee, Kirill Nikitin และ Srinath Setty

นี่เป็นหนึ่งในเอกสารทางวิชาการไม่กี่ฉบับเกี่ยวกับการปรับขยายของบล็อคเชน ไม่ได้ใช้คำว่า rollups เพราะมันเกิดขึ้นก่อนหรือเกิดขึ้นพร้อมกับแนวคิดที่นำมาใช้นอกวรรณกรรมทางวิชาการ

Front-end (การแปลงที่มีประสิทธิภาพจากโปรแกรมคอมพิวเตอร์เป็นการแสดงข้อมูลระดับกลาง เช่น ความพอใจของวงจร, R1CS และอื่นๆ)

การลดอย่างรวดเร็วจาก RAMs เป็นปัญหาความพึงพอใจข้อจำกัดที่รัดกุมซึ่งรับมอบสิทธิ์ได้ (2012)
โดย Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin และ Eran Tromer

จากมุมมองที่ทันสมัย ​​นี่เป็นงานแรกๆ เกี่ยวกับการแปลงโปรแกรมคอมพิวเตอร์สู่วงจร SAT ในทางปฏิบัติสำหรับการสร้างเครื่องเสมือน (VM) ที่เป็นนามธรรม ต่อยอดจากงานช่วงปลายทศวรรษ 1970 ถึง 1990 (เช่น งานของ Robson) เอกสารนี้อธิบายการลดแบบกำหนดจากการดำเนินการ VM สำหรับขั้นตอน T ไปจนถึงความพอใจของวงจรขนาด O(T*polylog(T))

เอกสารที่ตามมา เช่น SNARK สำหรับ C และ BCTV, ยังคงพัฒนา front-end ผ่าน VM abstraction และการสร้างอินสแตนซ์ที่ทันสมัยรวมถึงโปรเจ็กต์ต่างๆ เช่น ไคโร, RISC ศูนย์และ รูปหลายเหลี่ยม Miden.

นำการคำนวณที่ผ่านการตรวจสอบโดยพิสูจน์แล้วมาใช้อีกสองสามขั้นตอนใกล้กับการปฏิบัติจริง (2012)
โดย Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg และ Michael Walfish

เอกสารนี้เรียกว่า Ginger เป็นอีกหนึ่งส่วนสนับสนุนเบื้องต้นสำหรับเทคนิค front-end ที่ใช้งานได้จริง Ginger ได้แนะนำโปรแกรมเบ็ดเตล็ดสำหรับโปรแกรมพื้นฐานทั่วไป เช่น เงื่อนไขและนิพจน์เชิงตรรกะ การเปรียบเทียบ และเลขคณิตระดับบิตผ่านการแยกบิต เลขทศนิยมดั้งเดิม ฯลฯ โดยใช้เครื่องมือเหล่านี้เพื่อจัดเตรียมส่วนหน้าที่ใช้งานครั้งแรกจากภาษาระดับสูงถึงระดับต่ำ ข้อจำกัดทางคณิตศาสตร์ (คล้ายกับที่รู้จักกันในชื่อ R1CS) ซึ่งเป็นการแทนค่าระดับกลาง (IR) ที่สามารถใช้แบ็คเอนด์ SNARK ได้

ในขณะที่กระดาษ "การลดอย่างรวดเร็ว" และผู้สืบทอดใช้แนวทาง "CPU-emulator" ในการผลิต IR (เช่น IR บังคับใช้ว่าผู้พิสูจน์รันโปรแกรมเฉพาะอย่างถูกต้องโดยใช้ฟังก์ชันการเปลี่ยนของ CPU สำหรับจำนวนขั้นตอนที่ระบุ) , Ginger และผู้สืบทอดใช้แนวทางที่คล้ายกับ ASIC มากขึ้น โดยผลิต IR ที่ปรับให้เหมาะกับโปรแกรมคอมพิวเตอร์ที่ผู้พิสูจน์อ้างว่าดำเนินการได้อย่างถูกต้อง

ตัวอย่างเช่น บุฟเฟ่ต์ แสดงให้เห็นว่าเป็นไปได้ที่จะจัดการโฟลว์การควบคุมที่ซับซ้อนในแบบจำลอง ASIC โดยการเปลี่ยนโฟลว์การควบคุมดังกล่าวให้เป็นเครื่องที่มีสถานะจำกัดซึ่งปรับให้เหมาะกับโปรแกรมที่กำลังดำเนินการ และวิธีการนี้จะมีประสิทธิภาพมากกว่าการสร้างตัวจำลอง CPU ทั่วไปอย่างมีนัยสำคัญ xJsnark ให้โครงสร้างที่มีประสิทธิภาพสำหรับการคำนวณแบบหลายความแม่นยำ การเพิ่มประสิทธิภาพสำหรับ RAM และ ROM และแสดงภาษาระดับสูงที่เหมือน Java แก่โปรแกรมเมอร์ ซึ่งยังคงเป็นที่นิยมในปัจจุบัน เซอร์ซี สังเกตว่าการรวบรวมโปรแกรมคอมพิวเตอร์ไปยัง R1CS นั้นเกี่ยวข้องอย่างใกล้ชิดกับเทคนิคที่รู้จักกันดีจากการวิเคราะห์โปรแกรมและสร้างชุดเครื่องมือสร้างคอมไพเลอร์ที่รวมแนวคิดจากทั้งสองชุมชน (“LLVM สำหรับการแทนแบบวงจร”) งานก่อนหน้านี้ที่มีส่วนร่วมกับส่วนหน้าแบบ ASIC รวมถึง Pinocchio และ Geppetto.

กระดาษ "ลดอย่างรวดเร็ว" ใช้โครงสร้างที่ซับซ้อนและมีราคาแพงที่เรียกว่า "เครือข่ายการกำหนดเส้นทาง" สำหรับสิ่งที่เรียกว่า ตรวจความจำ (กล่าวคือ ตรวจสอบให้แน่ใจว่าผู้พิสูจน์ที่ไม่น่าเชื่อถือนั้นรักษาหน่วยความจำการเข้าถึงโดยสุ่มของ VM ไว้อย่างถูกต้องตลอดการดำเนินการของ VM ซึ่งกำลังพิสูจน์ความถูกต้องอยู่) ทางเลือกนี้เกิดขึ้นเพราะงานช่วงแรกๆ เช่นนี้กำลังหา PCP ซึ่งต้องการให้ส่วนหน้าเป็น ทั้งสอง ไม่โต้ตอบและความปลอดภัยข้อมูลตามหลักวิชา ต่อมาเรียกว่างาน ตู้กับข้าว (บรรพบุรุษของ บุฟเฟ่ต์ งานที่กล่าวถึงข้างต้น) ใช้ Merkle-trees แทนเครือข่ายเราต์ติ้ง บรรลุประสิทธิภาพโดยการรวบรวมฟังก์ชันแฮชเกี่ยวกับพีชคณิต (เช่น "SNARK-friendly") เนื่องจาก อัจไท, เป็นข้อจำกัด ส่งผลให้ส่วนหน้า "ปลอดภัยในการคำนวณ" วันนี้ มีงานวิจัยขนาดใหญ่เกี่ยวกับฟังก์ชันแฮชที่เป็นมิตรกับ SNARK พร้อมตัวอย่าง เช่น โพไซดอน, มิ.ย, คอนกรีตเสริมเหล็ก, กู้ภัยและอื่น ๆ

เทคนิคที่ล้ำสมัยเพื่อให้แน่ใจว่าผู้พิสูจน์รักษา RAM อย่างถูกต้องนั้นต้องอาศัยวิธีการที่เรียกว่า ลิปตัน (1989) และใช้สำหรับตรวจสอบหน่วยความจำโดย บลูมและคณะ (1991). เทคนิคเหล่านี้เกี่ยวข้องกับการโต้ตอบระหว่างผู้พิสูจน์และผู้ตรวจสอบโดยเนื้อแท้ แต่สามารถแสดงผลแบบไม่โต้ตอบกับการแปลง Fiat-Shamir เท่าที่เราทราบ พวกเขาได้รับการแนะนำให้รู้จักกับวรรณกรรมเกี่ยวกับส่วนหน้าของ SNARK ที่ใช้งานได้จริงโดยระบบที่เรียกว่า VRAM.

ขณะนี้มีการใช้เทคนิคการพิมพ์ลายนิ้วมือแบบไม่แปรเปลี่ยนในหลายส่วนหน้าและ SNARK สำหรับการแยกเครื่องเสมือน รวมถึงตัวอย่าง ไคโร. แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดปรากฏขึ้นอีกครั้งในบริบทที่เกี่ยวข้องในผลงานทั้งสองด้านล่าง ซึ่งใช้กันอย่างแพร่หลายในทางปฏิบัติในปัจจุบัน

หลักฐานความรู้ที่เป็นศูนย์ในระยะเวลาเกือบเป็นเชิงเส้นสำหรับการดำเนินการโปรแกรมที่ถูกต้อง (2018)
โดย Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen และ Mary Maller

Plookup: โปรโตคอลพหุนามแบบง่ายสำหรับตารางค้นหา (2020)
โดย Ariel Gabizon และ Zachary Williamson

งานแรกในส่วนหน้าแสดงการดำเนินการ "ที่ไม่ใช่เลขคณิต" (เช่น การตรวจสอบช่วง การดำเนินการระดับบิต และการเปรียบเทียบจำนวนเต็ม) ภายในวงจรและ IR ที่เกี่ยวข้องโดยแบ่งองค์ประกอบของฟิลด์ออกเป็นบิต ดำเนินการกับบิตเหล่านี้ แล้วจึง "บรรจุ" ผลลัพธ์กลับเป็นองค์ประกอบฟิลด์เดียว ในแง่ของขนาดของวงจรผลลัพธ์ จะส่งผลให้ค่าโสหุ้ยลอการิทึมต่อการทำงาน

ผลงานทั้งสองข้างต้น (BCGJM และ Plookup) ให้เทคนิคที่มีอิทธิพล (ตามที่เรียกว่า "ตารางค้นหา") เพื่อให้แสดงการดำเนินการเหล่านี้ภายในวงจรได้อย่างมีประสิทธิภาพมากขึ้นในแง่ค่าตัดจำหน่าย พูดคร่าวๆ สำหรับพารามิเตอร์ B ที่เลือกโดยนักออกแบบ front-end สิ่งเหล่านี้จะลดจำนวนเกทที่จำเป็นในการแสดงการดำเนินการที่ไม่ใช่เลขคณิตในวงจรด้วยปัจจัยลอการิทึมใน B ที่ต้นทุนของผู้พิสูจน์ที่กระทำการพิเศษด้วยการเข้ารหัสลับ "คำแนะนำ" เวกเตอร์ความยาวประมาณ B