1. Giriş
ZK-SNARK, bir kuruluşun başka bilgileri açıklamadan bir şeyin doğru olduğunu kanıtlamasına olanak tanıyan bir kriptografik kanıt sistemidir.
ZK-SNARK'lar, blockchain ve doğrulanabilir bilgi işlem gibi birçok uygulama ve alanda faydalıdır. ZK-Rollup'larda dikkate değer bir blockchain uygulaması kullanılıyor.
ZK-Rollup'lar, durum geçişlerinin geçerliliğini kanıtlamak için ZK-SNARK'ları (veya diğer kriptografik kanıt sistemlerini) kullanan diğer blok zincirlerin (Ethereum gibi) üzerine inşa edilmiş ikinci katman blok zincirlerdir. Yani, her yeni ağ güncellemesi yapıldığında (yeni bir işlem kümesi eklendiğinde), yeni bir ağ durumu hesaplanır ve bu durumun geçerliliğine dair bir kanıt oluşturulur. Mesele şu ki, bu kanıtı oluşturmak için yalnızca tek bir varlığa ihtiyaç vardır ve o zaman herkes onun geçerliliğine güvenebilir.
ZK-Rollup'lar tarafından sağlanan istenen özellikler genellikle (i) ölçeklenebilirlik ve/veya (ii) gizlilik korumasıdır. Yalnızca ölçeklenebilirlik gerektiğinde ZK-Toplamalarına bazen etkililik Toplamaları adı verilir.
Ethereum'un EVM'sini genişletmek için tasarlanan ZK-Rollup'lardaki kanıtları hesaplamak için ZK-EVM kullanılabilir. Kesin olarak tanımlanan ZK-EVM, sıfır bilgi kanıtları (ZKP) oluşturmaktan sorumlu bir dizi şifreleme programıdır (devreler), ancak bazen halk dilinde bir bütün olarak EVM özellikli evrensel ZK-Rollup'a da atıfta bulunur.
2.ZK-SNARK tanımı
SNARK, belirli bir ifadenin doğru olduğunun kısa bir kanıtıdır. Biçimsel olarak, belirli bir soruna doğru çözüm üreten bir algoritmanın yürütme izine ilişkin bilgiyi gösterir. Daha ziyade, izlemeyi gerçekleştiren halka açık olmayan ve sabit olmayan değerlere ilişkin bilgiyi gösterir. Bu değerlere bir bütün olarak genellikle tanık denir. Tanığın öğeleri, yani algoritmaya girişin parçaları bağımsız tanıklar oluşturur çünkü bunlar algoritmanın yürütülmesinden önce var olurlar ve yürütme izinin diğer öğeleri tarafından belirlenmezler. Algoritmanın çözdüğü sorun örneğini belirten yürütme izinin genel sabit olmayan değerine genel bildirim denir.
ZK-SNARK, Sıfır Bilgili Kısa, Etkileşimli Olmayan Bilgi Argümanı anlamına gelir.
S - Sadelik
Basitlik - kanıt "kısa" ve doğrulama süresi "hızlı":
"Kısa" bir kanıt, kanıtın boyutunun tanığın boyutuna göre alt doğrusal olduğu anlamına gelir.
"Hızlı" doğrulama süresi, doğrulayıcının çalışma süresinin (i) tanığın boyutunda alt doğrusal olması ve (ii) kamu iddiasında doğrusal olması gerektiği anlamına gelir.
Ama aslında sadece "özlü" değil aynı zamanda "log polinom düzeyinde" olmasını da istiyoruz.
Bu, kanıt boyutunun ve doğrulama süresinin neredeyse tanığın boyutundan bağımsız olduğu anlamına gelir.
π boyutunun, tanığın w boyutunun logaritmasının karesinin sabit çarpımından daha hızlı büyümemesi gerektiğini kanıtlayın (yeterince büyük w için):
Kanıtın boyutu spesifik ZK-SNARK protokolüne bağlıdır. Plonky2 için bu O(log^2(|w|)), ancak bu "en kötü" durumdur. Örneğin klasik PLONK ve Groth16 için ispatın boyutu bir sabit olan O(1)'dir.
Doğrulama süresi t_v, w tanığının logaritmasının karesinin sabit bir katından fazla olmamalı ve genel beyan x'in boyutunda doğrusal olmalıdır (x ve w, yalnızca biri boyutunu değiştirdiğinde yeterince büyüktür).
N - Etkileşimli değil - Kanıt oluşturma, doğrulayıcıdan herhangi bir veri alınmadan gerçekleşir.
ARK - Bilgi Kanıtı - Normal ispatlara benzer, ancak ses yalnızca polinomla sınırlı ispatlayıcılar için geçerliyken, ispatlarda ses, hesaplama açısından sınırsız ispatlayıcılar için geçerlidir. Bir sonraki bölümde ses kavramını tartışacağız.
ZK - Sıfır Bilgi - Tanık açıklaması yok.
3. ZK-SNARK'ların Özellikleri
ZK-SNARK'ların aşağıda açıklandığı gibi üç ana özelliği vardır:
Tamlık: Eğer kanıtlayıcı algoritmanın doğru yürütme yolunu biliyorsa, o zaman doğrulayıcının kanıtlayıcının bu bilgiye sahip olduğuna inanması gerekir.
Bilginin sağlamlığı: Kanıtlayıcı doğru uygulama yolunu gerçekten bilmediği sürece, kanıtlayıcı doğrulayıcıyı bunu bildiğine ikna edemez, ancak çok küçük bir olasılık vardır.
Sıfır bilgi: Doğrulayıcı, yürütme yörüngesi hakkında doğru olması dışında hiçbir şey bilmez.
4.PLONKish ZK-SNARK geçirmez sistem
4.1 PLONKish ZK-SNARK'lara ve işlevlerine giriş
Belirli bir algoritmaya uygulanabilmesi için ZK-SNARK kanıt sisteminin sonlu alandaki denklem sistemini bilmesi gerekir. Bu denklemler, algoritmanın yürütme yörünge tablosundaki değerler arasındaki ilişkiyi tanımlar ( hesaplamanın Bütünlük olmasını sağlamak için yürütme yörüngesini saklayan veri yapısı). Bu denklem sistemini (kısıtlama sistemi olarak da bilinir) ifade etmek için kullanılan dile aritmetik denir.
PLONKish ZK-SNARK prova sistemi, eski prova sistemlerine göre daha yüksek ifade gücüne sahip aritmetik kullanır. Birincisi, kısıtlama değişkenleri üzerinde keyfi polinom formundaki kısıtlama sistemi denklemlerini kullanmamıza olanak sağlarken, daha eski ispat sistemleri için (yani R1CS'ye dayalı sistemler) bu denklemler doğrusal ve ikinci dereceden polinomlar biçimindeydi. Bu özellik, PLONKish ZK-SNARK kanıt sisteminin kanıtlayıcının hesaplama verimliliği üzerinde olumlu bir etkiye sahip olmasını sağlar ve çeşitli algoritmalara uygulanmasını kolaylaştırır. Bu nedenle son yıllarda klasik PLONK, Halo2, Kimchi, Plonky2, HyperPlonk vb. gibi birçok PLONKish ZK-SNARK kanıt sistemi ortaya çıktı.
Taiko'da KZG polinom taahhüt şemasını temel alan Halo2 kanıt sisteminin bir çeşidini kullanıyoruz.
PLONKish ZK-SNARK kanıt sistemi üç bileşenden oluşur:
4.2 Taahhüt planı
Söz şeması, taahhüt edenin, mesajın kendisini açığa vurmadan taahhüt edeni bir mesaja bağlayan, söz adı verilen bir değeri yayınlamasına olanak tanır. İşlemci daha sonra taahhüdü açabilir ve taahhüt edilen mesajı veya bunun bir kısmını, ifşa edilen bilgilerin taahhütle tutarlı olup olmadığını kontrol edebilecek doğrulayıcıya ifşa edebilir.
Farklı yazarlar bir taahhüt şemasını oluşturan farklı sayıda algoritmayı tanımlamaktadır. Ancak bu algoritmalardan en az dördünden bahsetmek gerekir:
Kurulum: bazı başlangıç parametrelerini girdi olarak alır ve kurulum parametrelerini oluşturur. Ayarlar, (i) neyi taahhüt ettiğimizi (örneğin, tekli polinom taahhüt şeması için katsayı alanını ve taahhüt ettiğimiz polinomun maksimum derecesini belirtiriz) ve (ii) bit cinsinden güvenlik düzeyini belirtir. Güvenlik seviyesini basitçe şu şekilde tanımlayabiliriz: Bir şifreleme sisteminin kırılması O(2^n) zaman alıyorsa, şifreleme sisteminin güvenlik seviyesi n bittir.
Promise: Ayarlanan parametrelere göre mesajlar üreten bir söz.
Kısmi açılma: Parametrelerin ayarlanmasının yanı sıra, mesajın seçilen bir kısmına (örneğin, bazı parametreler için işlenmiş bir tekli polinomun değeri) özgü bir kısmi açılma kanıtı oluşturur.
Doğrulama: Kısmen açık bir doğrulama kullanın ve kanıtlayıcı tarafından ifşa edilen bilgilerin, belirtilen taahhüde karşılık gelen mesajın belirtilen kısmı olup olmadığını kontrol etmek için parametreleri ayarlayın.
*Bazı taahhüt şemaları için "kurulum" ve "açık" algoritmalar mevcut olmayabilir (örneğin, büyük değerleri taahhüt etmek için karma işlevi kullanıldığında).
Taahhüt planı aşağıdaki özelliklere sahip olmalıdır:
Bağlayıcı: Kanıtlayıcı belirli bir mesajı taahhüt ettiğinde, taahhüt ettiği mesaja bağlı olacaktır;
Saklama: Mesajla ilgili herhangi bir bilgiyi açıklamama sözü. Gizleme mükemmel olabilir, yani kısmen açık bir kanıt, mesajın sorgulanmayan kısmı hakkında herhangi bir bilgiyi ortaya çıkarmaz (örneğin, KZG taahhüdü) veya mükemmel olmayabilir, yani kısmen açık bir kanıt, yukarıda belirtilen bilgilerin bir kısmını ortaya çıkarabilir (örneğin, FRI tabanlı). polinom bağlılığı).
Bağlılık şemaları, hedef nesneye bağlı olarak çeşitli türlere ayrılabilir: tek öğeli bağlılık; küme bağlılığı; polinom bağlılığı;
Polinom taahhüt şemaları, PLONKish ZK-SNARK kanıt sisteminde doğrudan kullanılan tek türdür. Yukarıdaki kanıt sistemleri için (klasik PLONK, Halo2, Kimchi, Plonky2 vb. gibi), tek değişkenli polinom bağlılık şeması çok önemlidir. Ancak artık çok doğrusal polinom taahhüt şemalarına dayanan bazı yeni PLONKish ZK-SNARK yöntemleri var (örn. HyperPlonk).
4.3 Etkileşimli Oracle Kanıtı
Etkileşimli bir kehanet kanıtı, doğrulayıcının, kanıtlayıcının mesajlarını elde etmek için "kahin erişimine" sahip olduğu, bunları olasılıksal bir şekilde sorgulayabildiği ve kanıtlayıcının mesajlarının tamamını okumasına gerek olmadığı etkileşimli bir kanıttır.
4.4 Fiat-Shamir buluşsal yöntemi
Fiat-Shamir buluşsal yöntemi, (halka açık para) etkileşimli argümanları etkileşimli olmayan argümanlara dönüştürmenin bir yolunu sağlar. Sezgisel olarak fikir, doğrulayıcının rastgele meydan okumasını önceki mesajın karma değeriyle değiştirmektir, ancak ayrıntılar genellikle belirtilmez.
*Public Coin Protokolü, doğrulayıcıların yalnızca rastgele öğeler gönderdiği bir protokoldür.
4.5 PLONK tarzı ZK-SNARK geçirmez sistemin çalışma prensibi
ZK-SNARK kanıt sisteminde, tanığın bilgisini kanıtlamak için, Oracle'ın kanıtlayıcının mesajına erişimini sağlamak için polinom taahhütlerini kullanan ve bunu Fiat-Shamir buluşsal yöntemi aracılığıyla etkileşimsiz hale getiren değiştirilmiş bir etkileşimli Oracle kanıt yöntemi kullanılır. Bu bölümde verilen kurucuyu detaylı olarak açıklayacağız.
ZK-SNARK kanıt sistemini bir algoritmaya uygulamanın karşılık gelen bir kısıtlama sistemi oluşturmayı gerektirdiğini hatırlayın. Bunu kurabilmek için algoritmanın yürütme izleme tablosunun yapısını ve içindeki sabit değerleri tanımlıyoruz. "Devre" terimini, yalnızca sabitler ve karşılık gelen kısıtlama sistemiyle doldurulmuş bir yürütme izleme tablosunun karmaşık yapısına atıfta bulunmak için kullanırız. Bir algoritmanın yürütme örneği için bir ZK-SNARK kanıtı oluşturmak amacıyla, algoritmanın devresinin ve yürütme izleme tablosunun (yani sabitleri, tanıkları belirten bir tablo) karşılık gelen bir örneği olan bir devre örneğini sentezlememiz gerekir. ve genel bildirim değerleri) kombinasyonu.
PLONK tarzı ZK-SNARK kanıt sisteminin kullandığı izleme tablosunun yapısını ele alalım. Böyle bir tablodaki tüm sütunlar, Halo2'de kullanılan terminolojiye göre adlandırdığımız ve şu şekilde tanımladığımız üç türden birine aittir:
Sabit sütunlar - hücreleri yürütme izleme tablosundaki sabitleri içerir;
Örnek sütunu - genel bildirim değerlerini depolamak için kullanılır;
Öneri sütunu - tüm tanık verilerinin depolandığı yer (bağımsız tanık değerleri ve hesaplanan gizli sonuçlar dahil).
Özetlemek gerekirse, aşağıdakilere dikkat çekiyoruz:
Yürütme izleme tablosu (PLONKish tipi) = sabit sütunlar + örnek sütunlar + öneri sütunları; devre = yalnızca sabitleri içeren yürütme izleme tablosu + kısıtlama sistemi; devre örneği = devre + tablosundaki tanıklar + tablosundaki genel bildirimler: (Devre, genel açıklama, bağımsız tanık değeri) → Devre örneği; ZK-SNARK kanıt sistemini belirli bir algoritmaya uygulayın = devreyi tanımlayın + sentez sürecini tanımlayın.
Bu bağlamda neden "devre" terimi yaygın olarak kullanılıyor? Başlangıçta, yalnızca R1CS tabanlı ZK-SNARK kanıt sistemleri mevcut olduğunda, kısıtlama sistemini çıkışının sıfır olması gereken bir aritmetik devre biçiminde temsil etmek uygundu. PLONKish SNARK'lar bağlamında "devre" teriminin tarihsel nedenlerden dolayı kullanıldığına inanıyoruz. Her neyse, ZK-SNARK'ın eski versiyonlarında kullanılan aritmetik devreyi kısaca ele alalım.
R1CS tabanlı SNARK'lara yönelik aritmetik devre, sonlu bir alan üzerinde n değişkenli bir polinomu tanımlar ve bir değerlendirme şemasına sahiptir. Başlangıçta, yönlendirilmiş asiklik grafik (DAG) olarak temsil edilir:
o içerir:
Genel bildirim değerini belirtmek için kullanılan genel giriş x;
Bağımsız tanık değerini belirtmek için kullanılan gizli giriş w;
Sonlu alanlar üzerinde toplama ve çarpma işlemlerini belirtmek için kullanılan aritmetik kapılar.
Rasyonel sayılar alanı üzerinde bir aritmetik devre örneğine bakalım.
En alttan başlayıp diyagramdaki en düşük kapılarla yani (2 x 4 = 8) ve (4 + 11 = 15) ile çalışarak bu değerleri ara değerler olarak kaydediyoruz;
Daha sonra bir satır yukarı çıkıp (ikinci sıraya) iki ara değerin (önceki aşamada elde ettiğimiz) toplamını hesaplıyoruz, yani (8 + 15 = 23);
Yalnızca üç kapımız olduğundan ve hepsinden geçtiğimizden, son çıktımız 23 olur.
PLONKish ZK-SNARK kanıt sistemi devre örneğini sentezledikten sonra, her bir örnek yürütme izleme tablosunun sütunları aşağıdaki şekilde sonlu alanlar üzerinde polinomlar olarak kodlanır. C_j(x)'in j sütununu tanımlayan bir polinom olduğunu ve ω'nin 2^k-th temel kökü olduğunu varsayalım; burada k, 2^k tablo örneğinin başlangıç yüksekliğinden biraz daha büyük olacak şekilde seçilir. Tablo örneği, 2^k satır içerecek şekilde rastgele satırlarla (yalnızca önerilen sütunlarda sıfır olmayan hücrelerle) doldurulur ve C_j(ω^i), j'nin i'inci satırının değerine ayarlanır. verilen tablo örneğinin sütunu. Sıfır bilgi nitelikleri için doldurmanın rolü daha sonra açıklanacaktır.
"ω, 2^k-th'lik ilkel bir köktür" ifadesi, ω^(2^k) = 1 anlamına gelir ve 2^k'den küçük herhangi bir pozitif tamsayı için ω^t ≠ 1'e sahibiz.
Kısıtlama sistemi, içindeki değişkenleri sütun polinomlarından elde edilen karşılık gelen polinomlarla değiştirerek, x yerine "x çarpı ω'nin bir kuvvetine yükseltilmiş" şeklinde polinom denklem formuna dönüştürülür.
Örneğin, s(i) * (a(i) * b(i) - c(i+1)) = 0 kısıt sistemi denklemini ele alalım. Bu, eğer s(i) sıfır değilse, o zaman a(i) * b(i)'nin c(i+1)'e eşit olması gerektiği anlamına gelir. Burada a, b ve c önerilen sütunlardır, s sabit sütundur ve i geçerli satır numarasıdır.
Bu kısıtlama aşağıdaki gibi tüm 2^k satırlara uygulanabilir. S(x), A(x), B(x) ve C(x) sırasıyla a, b, c ve s sütunlarındaki polinomlar olsun. Bu nedenle şunu umuyoruz:
Bu, bu kümedeki tüm elemanların S(x) * (A(x) * B(x) - C(x * ω))'nin kökleri olması gerektiği anlamına gelir. Bu nedenle bu polinom şu şekilde bölünebilir olmalıdır:
Çünkü ω 2^k mertebesinden bir ilkel köktür.
Z(x) = x^(2^k) - 1'e "kaybolan polinom" denir çünkü ω tarafından oluşturulan döngüsel çarpımsal grubun elemanları olan tüm x'ler için 0'dır. Bu nedenle, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0, yukarıdaki kısıtlamaların tüm 2^k satırlar için geçerli olduğu anlamına gelir.
P_0(x), P_1(x), ... , P_m(x)'in tüm 2^k satırlara uygulanan kısıtlamalar olduğunu ve dikkate alınan S(x) * (A(x) * B(x) polinomuyla tutarlı olduğunu varsayalım. yukarıda ) - C(x * ω)) benzer bir forma sahiptir. Eğer α sonlu alandan doğrulayıcı tarafından rastgele seçilirse, o zaman
Bu, son derece yüksek olasılıkla tüm bu kısıtlamaların 2^k satırların tamamı için karşılandığı anlamına gelir. Bu denklem şu şekilde bir T(x) bölüm polinomu bulabileceğimiz anlamına gelir:
Bu nedenle, doğrulayıcının, kanıtlayıcının tüm m kısıtlamalarını çok yüksek bir olasılıkla karşılayan yürütme izleme tablosunun içeriğini bildiğine inanması için, yalnızca rastgele seçilen bir α için kanıtlayıcının P_0 oluşumlarına sahip olduğunun kanıtlanması gerekir. (x), P_1(x),..., önerilen sütun polinomları ve P_m(x)'deki bölüm polinomları T(x) bu polinom denklemini karşılar. Doğrulayıcı bunu, kanıtlayıcıdan, Z(x)'in kök olmayan ζ noktaları arasından doğrulayıcı tarafından seçilen rastgele bir noktada belirli bir polinomun değerini bulmasını ve bu noktada denklemin her iki tarafını da değerlendirmesini isteyerek yapabilir. ζ Kanıtlayıcının muhtemelen bu polinomları bildiğine inanıyorum. Bu yöntem Schwartz-Zippel lemması ile kanıtlanabilir.
Kanıt oluşturmayı etkileşimli olmayan hale getirmek için, etkileşimli versiyonda doğrulayıcı tarafından oluşturulan tüm rastgele değerlerin Fiat-Shamir buluşsal yöntemi kullanılarak elde edilmesi gerekir.
Kanıtlayıcıyı kendi öneri polinomuna ve bölüm polinomu T(x)'e bağlamak için bir polinom bağlılık şeması kullanılır. Kanıt, bu polinomlar üzerinde taahhütlerde bulunur, bu taahhütleri ζ'da (veya bazı kısıtlamalar i ve i + q satırlarını etkiliyorsa ζ * ω^q'da) açar ve (I) bu taahhütleri, (II) değeri içeren bir kanıt oluşturur. ζ'daki polinomun (veya gerekirse ζ * ω^q'nin üzerinde) ve (III) karşılık gelen açık ispatın. Aslında ispatı kısaltmak için çoklu açılış kullanın, yani tüm polinom noktalarının değerleri için küçük bir ispat oluşturun. Bu nedenle kanıt kısadır.
Sıfır bilgi özelliğini karşılamak için, kanıtlayıcı tarafından rastgele seçilen satırlar, yürütme izleme tablosunun örneğine eklenir ve yüksekliği 2^k satır olur. Bu satırların öneri sütununda yalnızca sıfır olmayan hücreler bulunur, çünkü yalnızca öneri sütunu gizlemek istediğimiz verileri içerir. Taahhüt açılış döneminde ortaya çıkan "parametre değeri" çiftlerinin sayısının, her polinom için rastgele eklenen çiftlerin sayısından daha küçük olması için teklif sütunu polinomlarını oluşturmadan önce bunu yapın. Dolayısıyla her bir teklif sütunu polinomu için, taahhüt açıldıktan sonra onu kurtarmak için gereken bilgi miktarı, tanık bilgi miktarından daha fazladır. Bu durum sıfır bilgiyle sonuçlanır.
Ön işleme aşaması sırasında, yürütme devresinin tüm örnekleri, sabit sütun polinomlarının kurulması ve hesaplanması ve bunların polinom taahhüt şeması için taahhütleri dahil olmak üzere aynı hesaplamalardan bazılarını gerçekleştirir. Bu hesaplamalar tarafından üretilen verilerin bir kısmı doğrulayıcı tarafından kullanılır ve genellikle doğrulama anahtarı olarak adlandırılır. Benzer şekilde kanıt anahtarı kavramı da tanımlanabilir. Temel polinom taahhüt şeması, güven ayarlarının ön işleme aşamasında yapılıp yapılmayacağını belirler.
