Sıfır Bilgi İspatlarının tarihine ilişkin son derece öznel görüşümüz

Sıfır-bilgi, Özlü, Etkileşimsiz Bilgi Argümanları (zk-SNARK'lar), bir tarafın, yani kanıtlayıcının, başka bir tarafı, yani doğrulayıcıyı, ifadenin geçerliliğinden başka hiçbir şeyi açığa vurmadan belirli bir ifadenin doğru olduğuna ikna etmesine olanak tanıyan güçlü kriptografik ilkellerdir. Doğrulanabilir özel hesaplamadaki uygulamaları, bilgisayar programlarının yürütülmesinin doğruluğunun kanıtlanmasını sağlamaları ve blok zincirlerinin ölçeklendirilmesine yardımcı olmaları nedeniyle yaygın ilgi gördüler. Yazımızda da belirttiğimiz gibi SNARK'ların dünyamızı şekillendirmede önemli bir etkisi olacağını düşünüyoruz. SNARKs, farklı polinom taahhüt şemaları (PCS), aritmetizasyon şemaları, etkileşimli oracle ispatları (IOP) veya olasılıksal olarak kontrol edilebilir ispatlar (PCP) kullanan farklı ispat sistemleri için bir şemsiye görevi görür. Ancak, temel fikirler ve kavramlar 1980'lerin ortalarına kadar uzanmaktadır. Bitcoin ve Ethereum'un piyasaya sürülmesinden sonra gelişim önemli ölçüde hızlandı ve Sıfır Bilgi kanıtlarını (bu özel kullanım durumu için genellikle Geçerlilik Kanıtları olarak adlandırılır) kullanarak bunları ölçeklendirebildiğiniz için heyecan verici ve güçlü bir kullanım durumu olduğunu kanıtladı. SNARK'lar blok zinciri ölçeklenebilirliği için önemli bir araçtır. Ben-Sasson'un da belirttiği gibi, son yıllarda kriptografik kanıtlarda Kambriyen patlaması yaşandı. Her bir kanıt sistemi avantaj ve dezavantajlar sunar ve belirli ödünleşimler göz önünde bulundurularak tasarlanmıştır. Donanımdaki gelişmeler, daha iyi algoritmalar, yeni argümanlar ve araçlar, performansın artmasına ve yeni sistemlerin doğmasına neden oluyor. Bunların birçoğu üretimde kullanılıyor ve sınırları zorlamaya devam ediyoruz. Tüm uygulamalar için genel bir ispat sistemimiz mi olacak yoksa farklı ihtiyaçlara uygun birkaç sistemimiz mi olacak? Tek bir kanıt sisteminin hepsine hükmetmesinin olası olmadığını düşünüyoruz çünkü:

1. Uygulama çeşitliliği.
2. Sahip olduğumuz kısıtlama türleri (bellek, doğrulama süreleri, kanıtlama süreleri ile ilgili).
3. Sağlamlık ihtiyacı (bir kanıt sistemi bozulursa, hala diğerlerine sahibiz).

İspat sistemleri çok değişse bile, hepsi önemli bir özellik sunar: İspatlar hızlı bir şekilde doğrulanabilir. İspatları doğrulayan ve yeni ispat sistemlerine kolayca uyarlanabilen bir katmana sahip olmak, Ethereum gibi temel katmanın değiştirilmesiyle ilgili zorlukları çözer. SNARK'ların farklı özelliklerine genel bir bakış sağlamak:

• Kriptografik varsayımlar: çarpışmaya dirençli hash fonksiyonları, eliptik eğriler üzerinde ayrık log problemi, üs bilgisi.
• Şeffaf ve güvenilir kurulum.
• Prover zamanı: doğrusal vs süper doğrusal.
• Doğrulayıcı zamanı: sabit zaman, logaritmik, doğrusal altı, doğrusal.
• Prova boyutu.
• Tekrarlama kolaylığı.
• Aritmetikleştirme şeması.
• Tek değişkenli ve çok değişkenli polinomlar.

Bu yazı SNARK'ların kökenlerini, bazı temel yapı taşlarını ve farklı ispat sistemlerinin yükselişini (ve düşüşünü) inceleyecektir. Bu yazı, ispat sistemlerinin kapsamlı bir analizi olma niyetinde değildir. Bunun yerine üzerimizde etkisi olanlara odaklanıyoruz. Elbette bu gelişmeler ancak bu alanın öncülerinin büyük çalışmaları ve fikirleriyle mümkün oldu.

Temel Bilgiler

Bahsettiğimiz gibi, sıfır bilgi kanıtları yeni değildir. Tanımlar, temeller, önemli teoremler ve hatta önemli protokoller 1980'lerin ortalarından itibaren oluşturulmuştur. Modern SNARK'ları inşa etmek için kullandığımız bazı temel fikirler ve protokoller 1990'larda (sumcheck protokolü) veya hatta Bitcoin'in ortaya çıkmasından önce (2007'de GKR) önerilmiştir. Benimsenmesindeki temel sorunlar, güçlü bir kullanım durumunun olmaması (1990'larda internet bu kadar gelişmiş değildi) ve ihtiyaç duyulan hesaplama gücü miktarıyla ilgiliydi.

Sıfır bilgi kanıtları: kökenleri (1985/1989)

Sıfır-bilgi ispatları alanı, Goldwasser, Micali ve Rackoff'un makalesi ile akademik literatüre girmiştir. Kökenleri üzerine bir tartışma için aşağıdaki videoyu izleyebilirsiniz. Bu makale tamlık, sağlamlık ve sıfır-bilgi kavramlarını tanıtmış ve ikinci dereceden kalıntı ve ikinci dereceden kalıntısızlık için yapılar sunmuştur.

Sumcheck protokolü (1992)

Sumcheck protokolü 1992 yılında Lund, Fortnow, Karloff ve Nisan tarafından önerilmiştir. Kısa ve öz interaktif kanıtlar için en önemli yapı taşlarından biridir. Çok değişkenli bir polinomun değerlendirmelerinin toplamı üzerindeki bir iddiayı rastgele seçilen bir noktada tek bir değerlendirmeye indirgememize yardımcı olur.

Goldwasser-Kalai-Rothblum (GKR) (2007)

GKR protokolü, bir devrenin kapı sayısında doğrusal olarak çalışan bir kanıtlayıcıya sahip olan etkileşimli bir protokoldür, doğrulayıcı ise devrenin boyutunda doğrusal olmayan bir şekilde çalışır. Protokolde, kanıtlayıcı ve doğrulayıcı, d katmanı giriş katmanına ve 0 katmanı çıkış katmanına karşılık gelecek şekilde, d derinliğinde sonlu bir alan üzerinde ikiye bölünmüş bir aritmetik devre üzerinde anlaşırlar. Protokol, devrenin çıktısına ilişkin bir iddia ile başlar ve bu iddia bir önceki katmanın değerleri üzerinde bir iddiaya indirgenir. Özyineleme kullanarak, bunu devrenin girişleri üzerinde kolayca kontrol edilebilecek bir iddiaya dönüştürebiliriz. Bu azaltmalar sumcheck protokolü aracılığıyla elde edilir.

KZG polinom taahhüt şeması (2010)

Kate, Zaverucha ve Goldberg 2010 yılında bilineer eşleştirme grubu kullanarak polinomlar için bir taahhüt şeması tanıttı. Taahhüt tek bir grup elemanından oluşur ve taahhüt eden kişi taahhüdü polinomun herhangi bir doğru değerlendirmesine verimli bir şekilde açabilir. Ayrıca, gruplama teknikleri sayesinde, açılış birden fazla değerlendirmeye tabi tutulabilir. KZG taahhütleri Pinocchio, Groth16 ve Plonk gibi birçok verimli SNARK için temel yapı taşlarından birini sağlamıştır. Aynı zamanda EIP-4844'ün de kalbinde yer alır. Yığınlama teknikleri hakkında bir sezgi edinmek için Mina-Ethereum köprüsü hakkındaki yazımıza bakabilirsiniz.

Eliptik eğriler kullanan pratik SNARK'lar

SNARK'lar için ilk pratik yapılar 2013 yılında ortaya çıktı. Bunlar, kanıtlama ve doğrulama anahtarlarını oluşturmak için bir ön işleme adımı gerektiriyordu ve programa/devreye özeldi. Bu anahtarlar oldukça büyük olabilir ve taraflarca bilinmemesi gereken gizli parametrelere bağlı olabilir; aksi takdirde kanıtları taklit edebilirler. Kodu kanıtlanabilecek bir şeye dönüştürmek için kodu bir polinom kısıtlama sistemine derlemek gerekiyordu. Başlangıçta bu işlemin manuel olarak yapılması gerekiyordu ki bu da zaman alıcı ve hataya açık bir işlemdi. Bu alandaki gelişmeler bazı temel sorunları ortadan kaldırmaya çalışmıştır:

1. Daha verimli kanıtlayıcılara sahip olun.
2. Ön işleme miktarını azaltın.
3. Devreye özel kurulumlar yerine evrensel kurulumlara sahip olmak.
4. Güvenilir kurulumlara sahip olmaktan kaçının.
5. Polinom kısıtlamalarını manuel olarak yazmak yerine yüksek seviyeli bir dil kullanarak devreleri tanımlamak için yollar geliştirmek.

Pinokyo (2013)

Pinokyo ilk pratik, kullanılabilir zk-SNARK'tır. SNARK ikinci dereceden aritmetik programlara (QAP) dayanmaktadır. Kanıt boyutu başlangıçta 288 bayttı. Pinocchio'nun araç zinciri, C kodundan aritmetik devrelere bir derleyici sağladı ve bu da bir QAP'ye dönüştürüldü. Protokol, doğrulayıcının devreye özgü anahtarları üretmesini gerektiriyordu. Denklemleri kontrol etmek için eliptik eğri eşleştirmelerini kullanmıştır. Kanıt üretimi ve anahtar kurulumu için asimptotikler hesaplama boyutunda doğrusaldır ve doğrulama süresi genel giriş ve çıkışların boyutunda doğrusaldır.

Groth 16 (2016)

Groth, bir R1CS tarafından tanımlanan problemler için performansı artıran yeni bir bilgi argümanı ortaya koymuştur. En küçük kanıt boyutuna (sadece üç grup elemanı) ve üç eşleştirme içeren hızlı doğrulamaya sahiptir. Ayrıca, yapılandırılmış referans dizesini elde etmek için bir ön işleme adımı da içerir. Ana dezavantajı, kanıtlamak istediğimiz her program için farklı bir güvenilir kurulum gerektirmesidir, bu da elverişsizdir. Groth16 ZCash'te kullanılmıştır.

Bulletproofs & IPA (2016)

KZG PCS'nin zayıf noktalarından biri de güvenilir bir kurulum gerektirmesidir. Bootle ve arkadaşları, bir iç çarpım ilişkisini sağlayan Pedersen taahhütlerinin açılışları için verimli bir sıfır-bilgi argüman sistemi sunmuştur. İç çarpım argümanı, logaritmik iletişim ve etkileşime sahip, ancak doğrusal zamanlı doğrulama ile doğrusal bir kanıtlayıcıya sahiptir. Ayrıca, güvenilir bir kurulum gerektirmeyen bir polinom taahhüt şeması geliştirdiler. Bu fikirleri kullanan PCS, Halo 2 ve Kimchi tarafından kullanılmaktadır.

Sonic, Marlin ve Plonk (2019)

Sonic, Plonk ve Marlin, Groth16'da yaşadığımız program başına güvenilir kurulum sorununu evrensel ve güncellenebilir yapılandırılmış referans dizeleri sunarak çözmektedir. Marlin, R1CS'ye dayalı bir kanıt sistemi sağlar ve Aleo'nun merkezinde yer alır.

Plonk, yeni bir aritmetikleştirme şeması (daha sonra Plonkish olarak adlandırıldı) ve kopya kısıtlamaları için büyük çarpım kontrolünün kullanımını tanıttı. Plonkish ayrıca, özel kapılar olarak adlandırılan belirli işlemler için özel kapıların kullanılmasına da izin verdi. Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 ve Scroll gibi birçok proje Plonk'un özelleştirilmiş sürümlerine sahiptir.

Aramalar (2018/2020)

Gabizon ve Williamson, 2020'de bir değerin önceden hesaplanmış bir değer tablosuna dahil olduğunu kanıtlamak için büyük çarpım kontrolünü kullanarak plookup 'ı tanıttı. Arama argümanları daha önce Arya'da sunulmuş olsa da, yapı, aramalar için çarpımların belirlenmesini gerektiriyordu ve bu da yapıyı daha az verimli hale getiriyordu. PlonkUp makalesi, plookup argümanının Plonk'a nasıl dahil edileceğini göstermiştir. Bu arama argümanlarıyla ilgili sorun, kanıtlayıcıyı arama sayısından bağımsız olarak tüm tablo için bedel ödemeye zorlamasıydı. Bu, büyük tablolar için önemli bir maliyet anlamına gelir ve kanıtlayıcının maliyetini sadece kullandığı arama sayısına düşürmek için çok çaba harcanmıştır.
Haböck, logaritmik türevi kullanarak büyük çarpım kontrolünü karşılıklı toplamlara dönüştüren LogUp'ı tanıttı. LogUp, tüm tabloyu birkaç STARK modülüne bölmeleri gereken Polygon ZKEVM'de performans için çok önemlidir. Bu modüller doğru şekilde bağlanmalıdır ve çapraz tablo aramaları bunu zorunlu kılar. LogUp-GKR 'nin tanıtımı, LogUp'ın performansını artırmak için GKR protokolünü kullanır. Caulk, N'nin tablo boyutu olduğu O(NlogN) ön işleme zamanı ve O(N) depolama alanı kullanarak tablo boyutunda doğrusal olmayan kanıtlayıcı zamanına sahip ilk şemadır. Bunu Baloo, flookup, cq ve caulk+ gibi birkaç başka şema takip etti. Lasso, belirli bir yapıya sahipse tabloya işlemekten kaçınarak çeşitli iyileştirmeler sunar. Ayrıca, Lasso'nun kanıtlayıcısı yalnızca arama işlemleri tarafından erişilen tablo girişleri için ödeme yapar. Jolt, bir sanal makinenin yürütüldüğünü arama yoluyla kanıtlamak için Lasso'dan yararlanır.

Spartan (2019)

Spartan, çok değişkenli polinomların özelliklerinden ve sumcheck protokolünden yararlanarak R1CS kullanılarak tanımlanan devreler için bir IOP sağlar. Uygun bir polinom taahhüt şeması kullanarak, doğrusal zamanlı bir kanıtlayıcı ile şeffaf bir SNARK ile sonuçlanır.

HyperPlonk (2022)

HyperPlonk, çok değişkenli polinomlar kullanarak Plonk'un fikirleri üzerine inşa edilmiştir. Kısıtlamaların uygulanmasını kontrol etmek için bölümler yerine, sumcheck protokolüne dayanır. Ayrıca, kanıtlayıcının çalışma süresine zarar vermeden yüksek dereceli kısıtlamaları da destekler. Çok değişkenli polinomlara dayandığı için FFT yapmaya gerek yoktur ve kanıtlayıcının çalışma süresi devre boyutunda doğrusaldır. HyperPlonk, daha küçük alanlar için uygun yeni bir permütasyon IOP'si ve kanıtlayıcının işini, kanıt boyutunu ve doğrulayıcının zamanını azaltan toplam kontrolü tabanlı bir toplu açma protokolü sunar.

Katlama planları (2008/2021)

Nova, artımlı olarak doğrulanabilir hesaplama (IVC) elde etmek için yeni bir yaklaşım olan katlama şeması fikrini tanıtmaktadır. IVC kavramı, k uzunluğundaki iki kanıtın k uzunluğunda tek bir kanıtta nasıl birleştirileceğini gösteren Valiant 'a dayanır. Buradaki fikir, i adımından I+1+1 adımına kadar olan yürütmenin doğru olduğunu özyinelemeli olarak kanıtlayarak ve i adımından I+1+1 adımına geçişin doğru olduğunu gösteren bir kanıtı doğrulayarak uzun soluklu herhangi bir hesaplamayı kanıtlayabilmemizdir.

-1-1'den 1. adıma kadar haklıydım. Nova, tek tip hesaplamalarla iyi bir şekilde ilgilenir; daha sonra Supernova'nın tanıtılmasıyla farklı devre türlerini ele almak için genişletildi. Nova, R1CS'nin rahatlatılmış bir versiyonunu kullanır ve dostane eliptik eğriler üzerinde çalışır. IVC'ye ulaşmak için dostane eğri döngüleriyle (örneğin, Pasta eğrileri) çalışmak, Mina'nın özlü bir duruma ulaşmak için ana yapı taşı olan Pickles'da da kullanılır. Ancak, katlama fikri özyinelemeli SNARK doğrulamasından farklıdır. Akümülatör fikri, ispatları gruplama kavramıyla daha derinden bağlantılıdır. Halo, özyinelemeli kanıt bileşimine alternatif olarak biriktirme kavramını tanıtmıştır. Protostar, Plonk için yüksek dereceli kapıları ve vektör aramalarını destekleyen tekdüze olmayan bir IVC şeması sağlar.

Çarpışmaya dayanıklı hash fonksiyonları kullanma

Pinokyo'nun geliştirildiği sıralarda, sanal bir makinenin yürütülmesinin doğruluğunu kanıtlayabilecek devreler/aritmetikleştirme şemaları üretmek için bazı fikirler vardı. Bir sanal makinenin aritmetizasyonunu geliştirmek, bazı programlar için özel devreler yazmaktan daha karmaşık veya daha az verimli olsa da, ne kadar karmaşık olursa olsun herhangi bir programın sanal makinede doğru şekilde yürütüldüğünü göstererek kanıtlanabilmesi avantajını sunuyordu. TinyRAM'deki fikirler daha sonra Cairo vm ve sonraki sanal makinelerin (zk-evms veya genel amaçlı zkvms gibi) tasarımıyla geliştirildi. Çarpışmaya dayanıklı hash fonksiyonlarının kullanılması, daha uzun kanıtlar pahasına güvenilir kurulumlara veya eliptik eğri işlemlerinin kullanılmasına olan ihtiyacı ortadan kaldırmıştır.

TinyRAM (2013)

C için SNARK'larda, indirgenmiş bir komut seti bilgisayarı olan TinyRAM'a derlenen bir C programının yürütülmesinin doğruluğunu kanıtlamak için PCP'ye dayalı bir SNARK geliştirdiler. Bilgisayar, bayt düzeyinde adreslenebilir rastgele erişimli belleğe sahip bir Harvard mimarisi kullanıyordu. Nondeterminizmden yararlanarak, devrenin boyutu hesaplamanın boyutunda kuasilineerdir, keyfi ve veriye bağlı döngüleri, kontrol akışını ve bellek erişimlerini verimli bir şekilde ele alır.

STARKs (2018)

STARK 'lar 2018 yılında Ben Sasson ve arkadaşları tarafından tanıtılmıştır. O(log2n)(log2) elde ederler

Hızlı kanıtlayıcı ve doğrulayıcı ile kanıt boyutları, güvenilir bir kurulum gerektirmez ve kuantum sonrası güvenli olduğu varsayılır. İlk olarak Starkware/Starknet tarafından Cairo vm ile birlikte kullanılmışlardır. Cebirsel ara temsil (AIR) ve FRI protokolü (Fast Reed-Solomon Interactive Oracle Proof of Proximity) bu protokolün önemli tanıtımları arasındadır. Diğer projeler (Polygon Miden, Risc0, Winterfell, Neptune) tarafından da kullanılmakta ya da bazı bileşenlerin (zkSync's Boojum, Plonky2, Starky) uyarlamaları görülmektedir.

Ligero (2017)

Ligero, boyutu aşağıdaki gibi olan kanıtlara ulaşan bir kanıt sistemi sunar

O(√n), burada n devrenin boyutudur. Polinom katsayılarını matris biçiminde düzenler ve doğrusal kodlar kullanır.
Brakedown, Ligero'yu temel alır ve alandan bağımsız polinom taahhüt şemaları fikrini ortaya koyar.

Bazı yeni gelişmeler

Üretimde farklı kanıt sistemlerinin kullanılması, yaklaşımların her birinin yararlarını göstermiş ve yeni gelişmelere yol açmıştır. Örneğin, Plonkish aritmetizasyonu özel kapıları ve arama argümanlarını dahil etmek için basit bir yol sunar; FRI, Plonky'ye yol açan PCS olarak büyük performans göstermiştir. Benzer şekilde, AIR'de büyük çarpım kontrolünün kullanılması (ön işleme ile rastgele AIR'e yol açar) performansını artırmış ve bellek erişim argümanlarını basitleştirmiştir. Hash fonksiyonlarına dayalı taahhütler, donanımdaki hash fonksiyonlarının hızına veya yeni SNARK dostu hash fonksiyonlarının piyasaya sürülmesine bağlı olarak popülerlik kazanmıştır.

Yeni polinom taahhüt şemaları (2023)

Spartan veya HyperPlonk gibi çok değişkenli polinomlara dayalı verimli SNARK'ların ortaya çıkmasıyla birlikte, bu tür polinomlara uygun yeni taahhüt şemalarına olan ilgi artmıştır. Binius, Zeromorph ve Basefold çoklu doğrusal polinomları işlemek için yeni formlar önermektedir. Binius, veri türlerini temsil etmek için sıfır ek yüke sahip olma avantajını sunar (oysa birçok kanıt sistemi tek bitleri temsil etmek için en az 32 bitlik alan öğeleri kullanır) ve ikili alanlar üzerinde çalışır. Taahhüt, sahadan bağımsız olacak şekilde tasarlanmış olan frenlemeyi uyarlar. Basefold, FRI'yi Reed-Solomon dışındaki kodlara genelleştirerek alandan bağımsız bir PCS'ye yol açar.

Özelleştirilebilir Kısıt Sistemleri (2023)

CCS, R1CS, Plonkish ve AIR aritmetizasyonunu ek yükler olmadan yakalarken R1CS'yi genelleştirir. CCS'yi Spartan IOP ile kullanmak, kanıtlayıcının kısıtlamanın derecesi ile ölçeklenen kriptografik maliyetlere katlanmasına gerek kalmadan yüksek dereceli kısıtlamaları destekleyen SuperSpartan'ı ortaya çıkarır. Özellikle, SuperSpartan doğrusal zaman kanıtlayıcısıyla AIR için bir SNARK verir.

Sonuç

Bu yazı, 1980'lerin ortalarında piyasaya sürülmelerinden bu yana SNARK'ların kaydettiği gelişmeleri anlatmaktadır. Bilgisayar bilimi, matematik ve donanım alanlarındaki ilerlemeler, blok zincirinin kullanılmaya başlanmasıyla birlikte yeni ve daha verimli SNARK'lara yol açarak toplumumuzu dönüştürebilecek birçok uygulamaya kapı açmıştır. Araştırmacılar ve mühendisler, kanıt boyutu, bellek kullanımı, şeffaf kurulum, kuantum sonrası güvenlik, kanıtlayıcı süresi ve doğrulayıcı süresine odaklanarak ihtiyaçlarına göre SNARK'larda iyileştirmeler ve uyarlamalar önermişlerdir. Başlangıçta iki ana hat varken (SNARK'lar ve STARK'lar), farklı ispat sistemlerinin avantajlarını birleştirmeye çalışarak her ikisi arasındaki sınır kaybolmaya başladı. Örneğin, farklı aritmetikleştirme şemalarını yeni polinom taahhüt şemaları ile birleştirmek. Performansın artmasıyla birlikte yeni kanıt sistemlerinin yükselmeye devam etmesini bekleyebiliriz ve bazı temel altyapıyı değiştirmek zorunda kalmadan bu araçları kolayca kullanamadığımız sürece, uyum sağlamak için biraz zaman gerektiren bazı sistemlerin bu gelişmelere ayak uydurması zor olacaktır.

Sorumluluk Reddi：

1. Bu makale[lambdaclass]'dan yeniden basılmıştır, Tüm telif hakları orijinal yazar[LambdaClass]'a aittir. Bu baskıya itirazınız varsa, lütfen Gate Learn ekibiyle iletişime geçin, onlar bu konuyu derhal ele alacaklardır.
2. Sorumluluk Reddi: Bu makalede ifade edilen görüş ve fikirler yalnızca yazara aittir ve herhangi bir yatırım tavsiyesi teşkil etmez.
3. Makalenin diğer dillere çevirisi Gate Learn ekibi tarafından yapılmaktadır. Belirtilmediği sürece, çevrilen makalelerin kopyalanması, dağıtılması veya intihal edilmesi yasaktır.