Sıfır Bilgi Canon

Editörün notu: a16z kripto uzun bir dizi “silahlar”, bizden DAO Kanonu bizim için geçen yıl NFT Canon daha önce (ve ondan önce orijinalimiz Kripto Kanonu) — bizim için kaydolduğunuzdan emin olun web3 haftalık bülten daha fazla güncelleme ve diğer küratörlü kaynaklar için.

Yani below, anlamak, daha derine inmek ve her şeyle inşa etmek isteyenler için bir dizi kaynak topladık sıfır bilgi: blok zinciri ölçeklenebilirliğinin anahtarlarını elinde tutan ve gizliliği koruyan uygulamaların ve gelecek sayısız diğer yeniliğin geleceğini temsil eden güçlü, temel teknolojiler. Eklemek için yüksek kaliteli parçalar için önerileriniz varsa, bize bildirin @a16zkripto.

Sıfır bilgi kanıtlı sistemler on yıllardır var: Shafi Goldwasser, Silvio Micali ve Charles Rackoff tarafından 1985'te tanıtılmaları kriptografi alanında dönüştürücü bir etki yarattı ve Goldwasser ve Micali'ye verilen ACM Turing Ödülü ile tanındı. 2012. Teoriden pratiğe ve bugün kripto/web3'teki uygulamalara geçişi de dahil olmak üzere bu çalışma onlarca yıldır yapım aşamasında olduğundan, canons serimizde ilk kez ikinci bölümü de paylaşıyoruz (şimdilik buraya dahil edilmiştir): tarafından açıklamalı bir okuma listesi Justin Thaler, aşağıdaki birinci bölümü takip edin.

Teşekkür: Michael Blau, Sam Ragsdale ve Tim Roughgarden'a da teşekkürler.

Temeller, arka plan, evrimler

Bu makalelerden bazıları, aynı zamanda, bugün sıfır bilgi kanıtıyla ele alınan sorunların veya önemli ilerlemelerin ana hatlarını da dahil olmak üzere, genel olarak kriptografi hakkındadır (hepsi sıfır bilgi değil): açık ağlarda gizlilik ve kimlik doğrulamanın nasıl sağlanacağı.

Kriptografide yeni yönler (1976)
Whitfield Diffie ve Martin Hellman tarafından
https://ee.stanford.edu/~hellman/publications/24.pdf

Dijital imzalar ve açık anahtarlı şifreleme sistemleri elde etmek için bir yöntem
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

Açık anahtar şifreleme sistemleri için protokoller (1980)
Ralph Merkle tarafından
http://www.merkle.com/papers/Protocols.pdf

Güvenli olmayan kanallar üzerinden güvenli iletişim (1978)
Ralph Merkle tarafından
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Kriptografide eliptik eğrilerin kullanımı (1988)
tarafından Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

Etkileşimli kanıt sistemlerinin bilgi karmaşıklığı (1985)
Shafi Goldwasser, Silvio Micali, Charles Rackof tarafından
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Hesaplamalı sağlam kanıtlar (2000)
Silvio Micali tarafından
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Çıkarılabilir çarpışma direncinden, kısa ve etkileşimli olmayan bilgi argümanlarına [SNARK'lar] ve tekrar geri (2011)
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Karıştırmanın doğruluğu için verimli sıfır bilgi argümanı (2012)
Stephanie Bayer ve Jens Groth tarafından
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Bir von Neumann Architecture (2013) için kısa ve öz etkileşimli olmayan sıfır bilgisi
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer ve Madars Virza tarafından
https://eprint.iacr.org/2013/879.pdf

Ölçeklenebilir, şeffaf ve kuantum sonrası güvenli hesaplama bütünlüğü (2018)
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh ve Michael Riabzev tarafından
https://eprint.iacr.org/2018/046.pdf

(Neredeyse) minimum zaman ve alan yükü (2020) ile kamu jetonlu sıfır bilgi argümanları
Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum ve Pratik Soni tarafından
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Genel bakış ve tanıtımlar

Kanıtlar, argümanlar ve sıfır bilgi - Doğrulanabilir hesaplamaya ve etkileşimli kanıtlara ve argümanlara genel bir bakış, bir kanıtlayıcının doğrulayıcıya sıfır bilgi dahil olmak üzere doğrulayıcının istenen bir hesaplamayı doğru bir şekilde gerçekleştirdiğine dair bir garanti sağlamasına olanak tanıyan kriptografik protokoller (kanıtların kendi geçerliliklerinden başka hiçbir bilgi göstermediği durumlarda) . Zk argümanlarının kriptografide sayısız uygulaması vardır ve son on yılda teoriden uygulamaya geçiş yapmıştır.
Justin Thaler tarafından
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Sıfır bilgi kanıtları için modellerin evrimi — Meiklejohn'un (University College London, Google) gelişmelerini sağlayan uygulamalara, bu yeni etkileşimleri yakalamak için ortaya çıkan farklı modellere, başarabileceğimiz yapılara ve çalışmaya baktığı sıfır bilgi kanıtlarının bir incelemesi yapmak için ayrıldı.
tarafından Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK beyaz tahta oturumları - giriş modülleri
Dan Boneh ve diğerleri ile
https://zkhack.dev/whiteboard/

zkps ile kripto için güvenlik ve gizlilik - pratikte sıfır bilgi kanıtına öncülük etmek; zkps nedir ve nasıl çalışırlar… canlı sahne “demo” dahil
tarafından Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

En iyi teknoloji konuları, açıklandı - genel olarak sıfır bilginin tanımları ve sonuçları dahil
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

Gelecek gizlilik katmanı bozuk bir ağı nasıl düzeltecek?
Howard Wu tarafından
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

zkSNARK'lara giriş
Howard Wu, Anna Rose ile
https://zeroknowledge.fm/38-2/

zk-SNARK Neden ve Nasıl Çalışır: Kesin bir açıklama
Maksym Petkus tarafından
https://arxiv.org/pdf/1906.07221.pdf

Sıfır bilgi ispatlarına giriş
Fredrik Harrysson ve Anna Rose tarafından
https://www.zeroknowledge.fm/21 [+ başka yerde özet yazı okuyun]

Zk-SNARK'lar: kaputun altında
Vitalik Buterin tarafından
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
parçası 1, parçası 2, parçası 3

Merkezi olmayan hız - sıfır bilgi kanıtı, merkezi olmayan donanımdaki ilerlemeler hakkında
Elena Burger tarafından
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Son teknoloji zk araştırması — Ethereum Foundation'da zk araştırmacısı ile
Mary Maller, Anna Rose, Kobi Gürkan ile birlikte
https://zeroknowledge.fm/232-2/

zk araştırmasını keşfetme — DFINITY'de araştırma direktörü ile; Groth16 gibi gelişmelerin de arkasında
Jens Groth, Anna Rose, Kobi Gürkan ile birlikte
https://zeroknowledge.fm/237-2/

SNARK araştırma ve pedagoji — ZCash ve Starkware'in kurucu ortaklarından biri ile
Alessandro Chiesa, Anna Rose ile
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Derin dalışlar, inşaatçı kılavuzları

Olasılıksal kanıtların temelleri — etkileşimli provalardan 5 ünite ve daha fazlasını içeren bir kurs
Alessandro Chiesa tarafından
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARK'lar — bölüm I, II, III
Vitalik Buterin tarafından
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

Bir STARK'ın Anatomisi — STARK geçirmez sistemin mekaniğini açıklayan altı bölümlük bir eğitim
Alan Szepieniec tarafından
https://aszepieniec.github.io/stark-anatomy/

SNARK tasarımı, bölüm 1 - anket, toplamalarda kullanım, daha fazlası
Justin Thaler tarafından
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK tasarımı, bölüm 2 - toplamalar, performans, güvenlik
Justin Thaler tarafından
https://www.youtube.com/watch?v=cMAI7g3UcoI

SNARK performansını ölçme - ön uçlar, arka uçlar, daha fazlası
Justin Thaler tarafından
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

PLONK'u Anlamak
https://vitalik.ca/general/2019/09/22/plonk.html

PLONK sıfır bilgi kanıtlama sistemi — PLONK'un nasıl çalıştığına dair 12 kısa video dizisi
David Wong tarafından
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

AIR'lerden RAP'lere — PLONK tarzı aritmetizasyon nasıl çalışır?
Ariel Gabizon tarafından
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

PLONK ve Plookup'ta çok ayarlı kontroller
Ariel Gabizon tarafından
https://hackmd.io/@arielg/ByFgSDA7D

Halo2 tasarımı - ECC'den
https://zcash.github.io/halo2/design.html

plonky2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Uygulamalar ve öğreticiler: kavramların kanıtı, demolar, araçlar, daha fazlası

Uygulanan zk - öğrenme kaynakları
0xPARC tarafından
https://learn.0xparc.org/materials/intro

zkSNARK'lar için çevrimiçi bir geliştirme ortamı — zkREPL, tarayıcıdaki Circom araç yığını ile etkileşim için yeni bir araç seti
Kevin Kwok tarafından
https://zkrepl.dev (+ açıklayıcı konu okuyun)

Sıfırdan kahramana ikinci dereceden aritmetik programlar
Vitalik Buterin tarafından
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

zkEVM'lerde
Alex Gluchowski ve Anna Rose ile
https://zeroknowledge.fm/175-2/

Farklı zkEVM türleri
Vitalik Buterin tarafından
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK makine öğrenimi — SNARK'a sinir ağı yerleştirmek için öğretici ve demo
Horace Pan, Francis Ho ve Henri Palacci tarafından
https://0xparc.org/blog/zk-mnist

ZK dillerinde
Alex Özdemir ve Anna Rose ile
https://zeroknowledge.fm/172-2/

Dark Forest — oyunlara zk kriptografisi uygulama — tamamen merkezi olmayan ve kalıcı bir RTS (gerçek zamanlı strateji) oyunu
https://blog.zkga.me/announcing-darkforest

Mühendisler için ZKP'ler — Dark Forest ZKP'lerine bir bakış
https://blog.zkga.me/df-init-circuit

Sıfır bilgiye bir dalış
Elena Nadolinkski, Anna Rose, James Prestwich ile birlikte
https://zeroknowledge.fm/182-2/

zkDocs: Sıfır bilgi bilgi paylaşımı
Sam Ragsdale ve Dan Boneh tarafından
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Sıfır bilgi kanıtı ile gizliliği koruyan kripto airdropları
tarafından Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Zincir üzerinde güvenilir kurulum törenleri -
Valeria Nikolaenko ve Sam Ragsdale tarafından
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Kripto düzenlemeleri, yasadışı finans, mahremiyet ve daha fazlası – mevzuat/uyum bağlamlarında sıfır bilgi ile ilgili bölümü içerir; "gizliliği koruyan" ile kafa karıştıran teknolojiler arasındaki fark
Michele Korver, Jai Ramaswamy, Sonal Chokshi ile birlikte
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Diğer kaynaklar

zkMesh bülteni — merkezi olmayan mahremiyeti koruyan teknolojiler, mahremiyet protokolü geliştirme ve sıfır bilgi sistemlerindeki en son gelişmeleri paylaşan aylık bir haber bülteni
https://zkmesh.substack.com/

Sıfır Bilgi podcast'i — en son zk araştırma ve zk uygulamaları ve kriptografi etkin gizlilik teknolojisi oluşturan uzmanlar hakkında
Anna Rose ile
https://zeroknowledge.fm/

… Justin Thaler tarafından konuya ve kronolojiye göre açıklamalı bir okuma listesi:

Doğrusal PCP'lerden SNARK'lar (devreye özel kurulumlu SNARK'lar)

Kısa PCP'ler Olmadan Etkili Argümanlar (2007)
Yuval Ishai, Eyal Kushilevitz ve Rafail Ostrovsky tarafından

Yaklaşık 2007'den önce, SNARK'lar öncelikle Kilian-mikali “Kısa” olasılıksal olarak kontrol edilebilir bir kanıt (PCP) alma ve onu Merkle hashing ve Fiat-Shamir dönüşümü yoluyla özlü bir argümanda “kriptografik olarak derleme” paradigması. Ne yazık ki, kısa PCP'ler bugün bile karmaşık ve pratik değildir. Bu makale (IKO), "uzun ama yapılandırılmış" PCP'lerden kısa ve öz (şeffaf olmayan) etkileşimli argümanlar elde etmek için homomorfik şifrelemenin nasıl kullanılacağını gösterdi. Bunlar kısa PCP'lerden çok daha basit olabilir ve ortaya çıkan SNARK'lar çok daha kısa kanıtlara ve daha hızlı doğrulamaya sahiptir. Bu argümanlar ilk önce pratik verimlilik potansiyeline sahip olarak kabul edildi ve daha sonra rafine edildi ve uygulandı. Biber. Ne yazık ki, IKO'nun argümanlarının ikinci dereceden zaman ispatlayıcısı ve ikinci dereceden boyutlu yapılandırılmış referans dizgisi vardır, bu nedenle büyük hesaplamalara ölçeklenmezler.

İkinci Dereceden Yayılan Programlar ve PCP'leri Olmayan Kısa NIZK'ler (2012)
Rosario Gennaro, Craig Gentry, Bryan Parno ve Mariana Raykova tarafından

Bu çığır açan makale (GGPR), IKO'nun yaklaşımının kanıtlanmış maliyetlerini devre boyutunda ikinci dereceden yarı doğrusala indirdi. Daha önceki çalışmalar üzerine inşa Groth ve lipma, aynı zamanda IKO'da olduğu gibi etkileşimli argümanlar yerine eşleştirme tabanlı şifreleme yoluyla SNARK'lar verdi. SNARK'larını, aritmetik devre-tatmin edilebilirliğinin bir genellemesi olan, şu anda 1. sıra kısıtlama memnuniyeti (R1CS) sorunları olarak adlandırılan bağlamda tanımladı.

Bu makale aynı zamanda ticari dağıtımı (örneğin, ZCash'te) gören ilk SNARK'ların teorik temeli olarak hizmet etti ve doğrudan bugün popülerliğini koruyan SNARK'lara (örneğin, Groth16) yol açtı. GGPR'nin argümanlarının ilk uygulamaları geldi Zaatar ve Pinokyo, ve sonraki varyantlar şunları içerir: C için SNARK'lar ve BCTV. BCİOP bu doğrusal-PCP'lerden SNARK'a dönüşümleri açıklayan genel bir çerçeve verdi (ayrıca bkz. Zaatar) ve bunun çeşitli örneklerini açıklar.

Eşleştirmeye Dayalı Etkileşimli Olmayan Bağımsız Değişkenlerin Boyutu Üzerine (2016)
Jens Groth tarafından

Halk arasında Groth16 olarak anılan bu belge, bugün bile en gelişmiş somut doğrulama maliyetlerine ulaşan GGPR'nin SNARK'larının bir iyileştirmesini sundu (kanıtlar 3 grup öğesidir ve doğrulama, en azından kamunun giriş kısa). Güvenlik, genel grup modelinde kanıtlanmıştır.

Evrensel güvenilir kuruluma sahip SNARK'lar

PlonK: Bilginin Ekümenik Etkileşimsiz Argümanları için Lagrange-tabanları Üzerindeki Permütasyonlar (2019)
Ariel Gabizon, Zachary Williamson ve Oana Ciobotaru tarafından

Marlin: Evrensel ve Güncellenebilir SRS ile zkSNARK'ların ön işlenmesi (2019)
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely ve Nicholas Ward tarafından

Hem PlonK hem de Marlin, Groth16'daki devreye özel güvenilir kurulumu evrensel bir kurulumla değiştirir. Bu, 4x-6x daha büyük kanıtların pahasına gelir. PlonK ve Marlin'in, Groth16 ve öncekilerde güvenilir kurulum sırasında devreye özgü çalışmayı alıp, gerçekleşen bir ön işleme aşamasına taşıdığı düşünülebilir. sonra güvenilir kurulum ve SNARK kanıt oluşturma sırasında.

Rasgele devreleri ve R1CS sistemlerini bu şekilde işleme yeteneği bazen holografi veya hesaplama taahhütleri olarak adlandırılır ve ayrıca Spartalı (bu derlemede daha sonra tartışılacaktır). Prova oluşturma sırasında daha fazla iş gerçekleştiğinden, belirli bir devre veya R16CS örneği için PlonK ve Marlin'in kanıtlayıcıları Groth1'dan daha yavaştır. Ancak, Groth16'dan farklı olarak, PlonK ve Marlin, R1CS'den daha genel ara temsillerle çalıştırılabilir.

Polinom taahhüt şemaları, SNARK'larda önemli bir kriptografik ilkel

Polinomlara Sabit Boyutlu Taahhütler ve Uygulamaları (2010)
Aniket Kate, Gregory Zaverucha ve Ian Goldberg tarafından

Bu makale, polinom taahhüt şemaları kavramını tanıttı. Sabit boyutlu taahhütler ve değerlendirme kanıtları ile tek değişkenli polinomlar (genellikle KZG taahhütleri olarak adlandırılır) için bir şema verdi. Şema, güvenilir bir kurulum (yani yapılandırılmış referans dizisi) ve eşleştirme tabanlı şifreleme kullanır. Bugün pratikte son derece popüler olmaya devam ediyor ve yukarıda tartışılan PlonK ve Marlin dahil olmak üzere SNARK'larda kullanılıyor (ve Groth16 son derece benzer şifreleme teknikleri kullanıyor).

Hızlı Reed-Solomon Etkileşimli Oracle Proximity Kanıtları (2017)
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Reed-Solomon testi için etkileşimli bir oracle kanıtı (IOP) verir - yani, taahhüt edilen bir dizgenin tek değişkenli bir polinomun değerlendirme tablosuna yakın olduğunu kanıtlar. Merkle-hashing ve Fiat-Shamir dönüşümü ile birleştiğinde, bu polilogaritmik boyutlu değerlendirme kanıtları ile şeffaf bir polinom taahhüt şeması verir (bkz. VP19 detaylar için). Bugün, bu, makul bir şekilde kuantum sonrası polinom taahhüt şemaları arasında en kısa olanı olmaya devam ediyor.

Ligero: Güvenilir Bir Kurulum Olmadan Hafif Alt Doğrusal Argümanlar (2017)
Scott Ames, Carmit Hazay, Yuval Ishai ve Muthuramakrishnan Venkitasubramaniam tarafından

FRI'ye benzer şekilde, bu çalışma Reed-Solomon testi için bir GİB verir, ancak polilogaritmik olmaktan ziyade karekök ispat uzunluğuna sahiptir. teorik çalışır Reed-Solomon kodunun daha hızlı kodlamaya sahip farklı bir hata düzeltme koduyla değiştirilmesiyle, herhangi bir alan üzerinde doğal olarak çalışan bir doğrusal zamanlı kanıtlayıcı elde edilebileceğini gösterdi. Bu yaklaşım rafine edilmiş ve uygulanmıştır. frenleme ve Oryon, son teknoloji kanıtlanmış performans sağlar.

Bulletproofs: Gizli İşlemler için Kısa Kanıtlar ve Daha Fazlası (2017)
Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille ve Greg Maxwell tarafından

tarafından önceki çalışmaların rafine edilmesi BCCGP, Bulletproofs, logaritmik kanıt boyutuna ancak doğrusal doğrulama süresine sahip ayrık logaritmaların hesaplanmasının sertliğine dayanan şeffaf bir polinom taahhüt şeması (aslında, bir iç çarpım argümanı olarak adlandırılan bir genelleme) verir. Şema, şeffaflığı ve kısa kanıtları nedeniyle bugün popülerliğini koruyor (örneğin, ZCash Orchard ve Monero'da kullanılıyor).

Dory: Genelleştirilmiş İç Çarpımlar ve Polinom Taahhütleri için Etkin, Şeffaf Argümanlar (2020)
Jonathan Lee tarafından

Dory, Bulletproofs'taki doğrulama süresini lineerden logaritmiye düşürürken, şeffaflığı ve logaritmik boyutlu provaları (somut olarak Bulletproofs'tan daha büyük olsa da) ve şeffaflığı korur. Eşleştirmeleri kullanır ve SXDH varsayımına dayanır.

Etkileşimli Kanıtlar, çoklu kanıtlayıcı etkileşimli Kanıtlar ve ilişkili SNARK'lar

Hesaplama Delegasyonu: Muggle'lar için Etkileşimli Kanıtlar (2008)
Shafi Goldwasser, Yael Tauman Kalai ve Guy Rothblum tarafından

Bu makaleden önce, genel amaçlı etkileşimli ispatlar için bir süperpolinom zamanı kanıtlayıcı. Bu makale, verimli bir paralel algoritmaya sahip herhangi bir problem için, bir polinom zaman doğrulayıcı ve yarı doğrusal zaman doğrulayıcı ile, yaygın olarak GKR protokolü olarak adlandırılan etkileşimli bir ispat protokolü sunmaktadır (eşdeğer olarak, etkileşimli ispat, küçük derinlikli herhangi bir aritmetik devre için geçerlidir).

Akışlı etkileşimli provalarla pratik doğrulanmış hesaplama (2011)
Graham Cormode, Michael Mitzenmacher, Justin Thaler tarafından

Bu makale (bazen CMT olarak da adlandırılır), GKR protokolündeki kanıtlama süresini devre boyutunda quartic'ten quasilinear'e indirdi. Genel amaçlı bir etkileşimli kanıtın ilk uygulamasını üretti. Sonraki çalışmaların bir satırı (Yenibahar, Thaler13, Zürafa, ve Terazi burcu) kanıtlayıcının çalışma süresini devre boyutunda yarı doğrusaldan doğrusala daha da azalttı.

vSQL: Dinamik Dış Kaynaklı Veritabanları Üzerinden Keyfi SQL Sorgularını Doğrulama (2017)
Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos ve Charalampos Papamanthou tarafından

Başlık belirli bir uygulama alanına (veritabanlarına) atıfta bulunsa da, bu makalenin katkıları daha geneldir. Spesifik olarak, etkileşimli kanıtları polinom taahhüt şemaları ile birleştirerek (çok doğrusal polinomlar için) devre-satisfiability için özlü argümanlar elde edilebileceğini gözlemledi.

daha sonra çalışır render sıfır bilgi argümanları ve çok doğrusal polinomlar için farklı taahhüt şemaları getirdi.

Spartan: Güvenilir kurulum olmadan verimli ve genel amaçlı zkSNARK'lar (2019)
tarafından Srinath Setty

Çok doğrulu etkileşimli kanıtları (MIP'ler) polinom taahhüt şemaları ile birleştirerek devre tatmin ediciliği ve R1CS için SNARK'ları elde eder, adı verilen somut olarak verimli MIP'ler üzerinde daha önceki çalışmalara dayanarak Yonca. Etki, yukarıda tartışılan GKR protokolü gibi etkileşimli kanıtlardan türetilenlerden daha kısa kanıtlara sahip SNARK'lar elde etmektir. PlonK ve Marlin'e benzer şekilde Spartan, ön işleme ve SNARK kanıt oluşturma yoluyla isteğe bağlı devrelerin ve R1CS sistemlerinin nasıl işleneceğini de gösterir.

Spartan, aşağıdakilerden bir polinom taahhüt şeması kullandı: Yaban faresi. Adı geçen sonraki çalışmalar frenleme ve Oryon Spartan'ın MIP'sini diğer polinom taahhüt şemaları ile birleştirerek ilk uygulanan SNARK'ları bir lineer-zaman ispatlayıcısı ile elde edin.

Kısa PCP'ler ve GİB'ler

Polylog Sorgu Karmaşıklığına Sahip Kısa PCP'ler (2005)
Eli Ben-Sasson ve Madhu Sudan

 Bu teorik çalışma, doğrulanacak hesaplamanın boyutunda ve polilogaritmik sorgu maliyetinde (doğrusal doğrulama süresine rağmen) kanıt uzunluğu yarı doğrusal olan ilk olasılıksal olarak kontrol edilebilir kanıtı (PCP) verdi. PCP'lerin SNARK'lara Kilian-Micali dönüşümünü takiben, bu, yarı doğrusal zaman doğrulayıcı ve polilogaritmik zaman doğrulayıcı ile SNARK'lara doğru bir adımdı.

Daha sonra teorik çalışma doğrulayıcı süresini polilogaritmik olarak azalttı. Sonraki pratik odaklı çalışma bu yaklaşımı geliştirdi, ancak kısa PCP'ler bugün pratik değil. Pratik SNARK'lar elde etmek için, sonra çalışır dönük için olarak adlandırılan PCP'lerin etkileşimli bir genellemesi Etkileşimli Oracle Provaları (GİB'ler). Bu çabalar, ÜCRETSİZ, bu derlemenin polinom taahhütleri bölümünde tartışılan popüler bir polinom taahhüt şeması.

Bu kategorideki diğer eserler şunlardır: ZKBoo ve onun soyundan gelenler. Bunlar kısa ve öz kanıtlara ulaşmazlar, ancak iyi sabit faktörlere sahiptirler ve bu nedenle küçük ifadeleri kanıtlamak için çekicidirler. gibi kuantum sonrası imzaların ailelerine yol açtılar. Piknik buna sahip olmuştur optimize in birkaç çalışır. ZKBoo olarak adlandırılan farklı bir tasarım paradigmasının ardından sunulur. kafadaki MPC, ancak bir GİB verir.

Özyinelemeli SNARK'lar

Artımlı Doğrulanabilir Hesaplama veya Bilgi Kanıtları, Zaman/Uzay Verimliliği anlamına gelir (2008)
Paul Valiant tarafından

Bu çalışma, temel olarak aşamalı olarak doğrulanabilir hesaplama (IVC) kavramını ortaya koydu; burada, kanıtlayıcılar bir hesaplama çalıştırıyor ve her zaman, şimdiye kadar yapılan hesaplamanın doğru olduğuna dair bir kanıt sağlıyor. SNARK'ların özyinelemeli bileşimi yoluyla IVC'yi oluşturdu. Burada, bilgi-sağlamlık SNARK'ların özelliği, özyinelemeli olarak oluşturulmuş etkileşimli olmayan argümanların sağlamlığını oluşturmak için esastır. Bu makale ayrıca PCP'den türetilen SNARK'lar için (Kilian-Micali paradigmasına göre) son derece verimli bir bilgi çıkarıcı sağladı.

Eliptik Eğrilerin Döngüleri Yoluyla Ölçeklenebilir Sıfır Bilgisi (2014)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer ve Madars Virza tarafından

Takip etme teorik çalışma, bu makale, basit bir sanal makine (TinyRAM, C için SNARK'lar kağıt).

Ayrıca, eliptik eğri kriptografisinden yararlanan SNARK'ları yinelemeli olarak oluşturmak için yararlı olan eliptik eğri döngüleri kavramını tanıttı.

Güvenilir Kurulum Olmadan Özyinelemeli Prova Kompozisyonu (2019)
Sean Bowe, Jack Grigg ve Daira Hopwood tarafından

Bu çalışma (Halo olarak adlandırılır), şeffaf SNARK'ların özyinelemeli olarak nasıl oluşturulacağını inceler. Bu, şeffaf olmayanları oluşturmaktan daha zordur çünkü şeffaf SNARK'lardaki doğrulama prosedürü çok daha pahalı olabilir.

Bu daha sonra bir kıvılcım çıkardı hat of iş gibi sistemlerle sonuçlandı. yeni Groth16 gibi şeffaf olmayan SNARK'ların bileşimiyle elde edilenden bile üstün, son teknoloji IVC performansı elde etmek.

Uygulamalar

Zerocash: Bitcoin'den Merkezi Olmayan Anonim Ödemeler (2014)
Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Dahil olmak üzere önceki çalışmalar üzerine inşa etmek sıfır para (Ve birlikte Pinokyo Sikke eşzamanlı çalışma olarak), bu makale özel bir kripto para birimi tasarlamak için GGPR'den türetilen SNARK'ları kullanır. ZCash'e yönlendirdi.

Gepetto: Çok Yönlü Doğrulanabilir Hesaplama (2014)
Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno ve Samee Zahur tarafından

Geppetto, Ethereum'un yaratılmasından yaklaşık bir yıl sonra yazılmış olan, özel akıllı sözleşme uygulamasına olan ilgi patlamasının tartışmasız öncesine dayanıyor. Bu nedenle, özel akıllı sözleşme yürütme bağlamında sunulmaz. Ancak, güvenilmeyen bir kanıtlayıcının, çalıştırılan program veya üzerinde çalıştırıldığı veriler hakkında bilgi vermeden özel veriler üzerinde herhangi bir özel (taahhütlü/imzalı) bilgisayar programını yürütmesine izin vermek için SNARK'ların sınırlı derinlikli özyinelemesini kullanır. Buna göre, özel akıllı sözleşme platformlarında yapılan çalışmaların öncüsüdür. Zexe [Aşağıda açıklanan].

Doğrulanabilir ASIC'ler (2015)
Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish tarafından

Bu makale, güvenilmeyen bir dökümhanede üretilen bir ASIC'nin nasıl güvenli ve verimli bir şekilde kullanılacağı sorununu ele almaktadır (2015'te, üst düzey dökümhanelere sahip sadece beş ülke vardı). Yaklaşım, hızlı ancak güvenilmeyen ASIC'nin çıktısının doğruluğunu daha yavaş ama güvenilir bir ASIC üzerinde çalışan bir doğrulayıcıya kanıtlamasını sağlamaktır. Sistemin toplam yürütme süresi (yani, doğrulayıcı ve doğrulayıcı çalışma sürelerinin toplamı artı herhangi bir veri iletim maliyeti) saf temel çizgiden daha az olduğu sürece çözüm ilginçtir: hesaplamayı daha yavaşta tam olarak çalıştırmak için gereken süre -ama-güvenilir ASIC. GKR/CMT/Allspice etkileşimli kanıtlarının bir varyantını kullanan makale, sayı-teorik dönüşümler, örüntü eşleştirme ve eliptik eğri işlemleri dahil olmak üzere bir dizi temel problem için gerçekten de saf temel çizgiyi aşıyor. Bu çalışma, bazı kanıtlama sistemlerinin donanım uygulaması için diğerlerinden daha uygun olduğunu göstermektedir. Donanım uygulaması için kanıtlama sistemlerini optimize etme şimdi alıyor önemli Dikkat, ancak keşfedilmeyi bekleyen çok şey var.

Doğrulanabilir Gecikme Fonksiyonları (2018)
Dan Boneh, Joseph Bonneau, Benedikt Bünz ve Ben Fisch tarafından

Blok zinciri uygulamalarında yaygın olarak kullanılan bir kriptografik ilkel olan doğrulanabilir gecikme işlevleri (VDF'ler) gösterimi, örneğin, hisse ispatı konsensüs protokollerinin olası manipülasyonunu azaltmada tanıtıldı. SNARK'lar (özellikle Artımlı Doğrulanabilir Hesaplama için), son teknoloji ürünü VDF'lere giden bir yol sunar.

Zexe: Merkezi Olmayan Özel Hesaplamayı Etkinleştirme (2018)
Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra ve Howard Wu tarafından

Zexe, özel bir akıllı sözleşme platformu için bir tasarımdır. Zexe, Zerocash'in bir uzantısı olarak görülebilir (yukarıda açıklanmıştır). Zerocash, tek bir uygulamanın zincir üzerinde çalıştırılmasını sağlar (kullanıcıların jetonları transfer etmesine olanak tanır) ve kullanıcı verilerinin gizliliğini korurken, örneğin, token'ları kime gönderdikleri, token'ları aldıkları, aktarılan tokenlerin miktarı vb. Zexe birçok izin verir. aynı blok zincirinde çalışmak ve birbirleriyle etkileşim kurmak için farklı uygulamalar (akıllı sözleşmeler). İşlemler zincir dışında yürütülür ve doğru yürütmenin kanıtları zincir üzerinde yayınlanır. Yalnızca veri gizliliği korunmakla kalmaz, aynı zamanda işlev gizliliği de korunur. Bu, her işlemle ilgili kanıtın, işlemin hangi uygulama(lar)a ait olduğunu bile göstermediği anlamına gelir. Zexe'nin daha genel bir mühendislik katkısı, eşleştirme tabanlı SNARK'ların verimli derinlik-12 bileşimi için yararlı olan bir eliptik eğri grubu olan BLS377-1'yi tanıtmasıdır.

Yinelenen yürütme olmadan çoğaltılmış durum makineleri (2020)
Jonathan Lee, Kirill Nikitin ve Srinath Setty tarafından

Bu, blok zinciri ölçeklenebilirliği için toplamalar üzerine birkaç akademik makaleden biridir. Özetleme terimini kullanmaz, çünkü bu kavram akademik literatürün dışında tanıtılan kavramın öncesine aittir veya onunla çağdaştır.

Ön uçlar (bilgisayar programlarından devre tatmini, R1CS ve daha fazlası gibi ara temsillere verimli dönüşümler)

RAM'lerden Devredilebilir Özlü Kısıt Memnuniyet Sorunlarına Hızlı İndirimler (2012)
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin ve Eran Tromer tarafından

Modern bir bakış açısından, bu, bir sanal makine (VM) soyutlaması için pratik bilgisayar programından devreye SAT dönüşümleri üzerine erken bir çalışmadır. 1970'lerin sonundan 1990'lara kadar olan çalışmaların üzerine inşa etmek (örn. Robson) bu makale, T adımları için bir VM yürütmekten O(T*polylog(T)) boyutlu bir devrenin tatmin edilebilirliğine deterministik bir azalmayı açıklamaktadır.

Sonraki makaleler, örn. C için SNARK'lar ve BCTV, bir VM soyutlaması aracılığıyla ön uçlar geliştirmeye devam etti ve modern örnekler arasında şunlar gibi projeler yer alıyor: Kahire, RISC Sıfır, ve Çokgen Miden.

Kanıta dayalı doğrulanmış hesaplamayı pratikliğe birkaç adım daha yaklaştırmak (2012)
Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg ve Michael Walfish tarafından

Ginger olarak adlandırılan bu makale, pratik ön uç tekniklerine bir başka erken katkıdır. Ginger, koşullu ve mantıksal ifadeler, karşılaştırmalar ve bit bölme yoluyla bitsel aritmetik, ilkel kayan nokta aritmetiği vb. gibi genel programlama ilkelleri için gadget'ları tanıttı. Bu gadget'ları, yüksek seviyeli bir dilden düşük dereceye kadar ilk uygulanan ön ucu sağlamak için kullandı. aritmetik kısıtlamalar (şu anda R1CS olarak bilinen şeye benzer), bir SNARK arka ucunun uygulanabileceği bir ara gösterim (IR).

"Hızlı İndirgemeler" belgesi ve onun torunları, IR'lerin üretilmesinde bir "CPU-emülatörü" yaklaşımını kullanırken (yani, IR, kanıtlayıcının belirli bir sayıda adım için CPU'nun geçiş işlevini uygulayarak belirli bir programı doğru bir şekilde çalıştırmasını zorunlu kılar) , Ginger ve onun soyundan gelenler, daha ASIC benzeri bir yaklaşım benimsiyor ve kanıtlayıcının doğru şekilde yürüttüğünü iddia ettiği bilgisayar programına uyarlanmış IR'ler üretiyor.

Örneğin, büfe ASIC modelindeki karmaşık kontrol akışını, bu tür kontrol akışını yürütülmekte olan programa uyarlanmış sonlu durumlu bir makineye dönüştürerek ele almanın mümkün olduğunu ve bu yaklaşımın genel amaçlı bir CPU öykünücüsü oluşturmaktan çok daha verimli olabileceğini gösteriyor. xJsnark çok hassasiyetli aritmetik için verimli bir yapı, RAM'ler ve ROM'lar için optimizasyonlar sağlar ve Java benzeri yüksek seviyeli bir dili bir programcıya sunar ve bugün hala popüler olan bir programcıdır. sirC bilgisayar programlarını R1CS'de derlemenin, program analizinden iyi bilinen tekniklerle yakından ilişkili olduğunu gözlemler ve her iki topluluktan fikirleri içeren bir derleyici oluşturma araç seti oluşturur (“devre benzeri temsiller için LLVM”). ASIC tarzı ön uçlara katkıda bulunan önceki çalışmalar şunları içerir: Pinokyo ve Geppetto.

"Hızlı İndirgemeler" belgesi, "yönlendirme ağları" adı verilen karmaşık ve pahalı bir yapı kullandı. hafıza kontrolü (yani, doğruluğu kanıtlanan VM'nin yürütülmesi boyunca güvenilmeyen kanıtlayıcının VM'nin rastgele erişim belleğini doğru bir şekilde muhafaza etmesinin sağlanması). Bu seçim yapıldı çünkü bunun gibi erken çalışmalar, ön ucun olmasını gerektiren bir PCP elde etmeye çalışıyordu. her ikisi de etkileşimli olmayan ve bilgi teorik olarak güvenli. Daha sonra çalışma denilen Kiler (bir önceki büfe yukarıda bahsedilen çalışma) yönlendirme ağları yerine Merkle ağaçlarını kullandı, bir cebirsel (yani, “SNARK dostu”) karma işlevi derleyerek verimlilik elde etti. ajtay, kısıtlamalar içine. Bu, "hesaplama açısından güvenli" ön uçlarla sonuçlandı. Bugün, SNARK-dostu hash fonksiyonları hakkında geniş bir araştırma literatürü bulunmaktadır. Poseidon, MiMC, Betonarme, KurtarmaVe daha fazlası.

Kanıtlayıcının RAM'i doğru bir şekilde koruduğundan emin olmak için en son teknikler, en azından M.Ö. Lipton (1989) tarafından hafıza kontrolü için kullanılmıştır. Blum ve ark. (1991). Bu teknikler doğası gereği bir doğrulayıcı ve doğrulayıcı arasındaki etkileşimi içerir, ancak Fiat-Shamir dönüşümü ile etkileşimsiz hale getirilebilir. Bildiğimiz kadarıyla, pratik SNARK ön uçlarıyla ilgili literatüre, adı verilen bir sistemle tanıtıldılar. vRAM.

Permütasyonla değişmez parmak izi teknikleri artık birçok ön uçta ve sanal makine soyutlamaları için SNARK'larda kullanılmaktadır. Kahire. Bugün pratikte yaygın olarak kullanılan aşağıdaki iki eserde birbiriyle yakından ilişkili fikirler ilgili bağlamlarda yeniden ortaya çıktı.

Doğru Program Yürütme için Neredeyse Doğrusal Zamanlı Sıfır Bilgi Kanıtları (2018)
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen ve Mary Maller tarafından

Plookup: Arama tabloları için basitleştirilmiş bir polinom protokolü (2020)
Ariel Gabizon ve Zachary Williamson tarafından

Ön uçlar üzerine yapılan ilk çalışmalar, devreler ve ilgili IR'ler içindeki "aritmetik olmayan" işlemleri (aralık kontrolleri, bitsel işlemler ve tamsayı karşılaştırmaları gibi) temsil etmekteydi ve alan elemanlarını bitlere ayırarak, bu bitler üzerinde işlemleri gerçekleştirerek ve ardından "paketleme". sonucu tek bir alan öğesine geri döndürür. Ortaya çıkan devrenin boyutu açısından bu, işlem başına logaritmik bir ek yük ile sonuçlanır.

Yukarıdaki iki çalışma (BCGJM ve Plookup), bu işlemleri amorti edilmiş bir anlamda devreler içinde daha verimli bir şekilde temsil etmek için etkili teknikler ("arama tabloları" olarak adlandırılanlara dayanarak) verir. Kabaca söylemek gerekirse, ön uç tasarımcı tarafından seçilen bazı B parametreleri için bunlar, devredeki her aritmetik olmayan işlemi temsil etmek için gereken kapı sayısını B'de logaritmik bir faktörle azaltır, bu da ispatlayıcının kriptografik olarak fazladan bir işlem yapması pahasınadır. kabaca B uzunluğundaki "tavsiye" vektörü.