Vitalik Buterin aracılığıyla Vitalik Buterin'in Blogu

Bu, şu adresteki yazının bir aynasıdır: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Son zamanlarda zk-SNARK'ların arkasındaki teknolojiye büyük ilgi var ve insanlar giderek daha fazla gizemi çözmeye çalışıyorum Çözülemez karmaşıklığı nedeniyle çoğu kişinin "ay matematiği" olarak adlandırdığı bir şey. zk-SNARK'ları kavramak gerçekten oldukça zordur, özellikle de her şeyin çalışması için bir araya gelmesi gereken çok sayıda hareketli parça nedeniyle, ancak teknolojiyi parça parça ayırırsak kavramak daha kolay hale gelir.

Bu yazının amacı zk-SNARK'lara tam bir giriş yapmak değil; arka plan bilgisi olarak (i) zk-SNARK'ların ne olduğunu ve ne yaptığını bildiğinizi ve (ii) polinomlar gibi şeyler hakkında mantık yürütmeye yetecek kadar matematik bildiğinizi varsayar (eğer �(�)+�(� ifadesi ise) =(�+�)(�) , burada � ve � polinomlardır, size doğal ve açık görünüyor, o zaman doğru seviyedesiniz). Gönderi bunun yerine teknolojinin arkasındaki mekanizmayı daha derinlemesine inceliyor ve zk-SNARK araştırmacısı Eran Tromer tarafından burada çizildiği şekliyle sürecin ilk yarısını mümkün olduğu kadar açıklamaya çalışıyor:

Buradaki adımlar iki yarıya ayrılabilir. Birincisi, zk-SNARK'lar herhangi bir hesaplama problemine doğrudan uygulanamaz; bunun yerine, sorunun üzerinde çalışılabilmesi için sorunu doğru "forma" dönüştürmeniz gerekir. Bu forma "ikinci dereceden aritmetik program" (QAP) adı verilir ve bir fonksiyonun kodunu bunlardan birine dönüştürmek oldukça basit bir işlemdir. Bir fonksiyonun kodunu bir QAP'ye dönüştürme sürecinin yanı sıra, birlikte yürütülebilecek başka bir süreç daha vardır; böylece koda bir girişiniz varsa karşılık gelen bir çözüm oluşturabilirsiniz (bazen QAP'ye "tanık" olarak da adlandırılır). Bundan sonra, bu tanık için gerçek "sıfır bilgi kanıtını" oluşturmak için oldukça karmaşık bir süreç ve başka birinin size ilettiği kanıtı doğrulamak için ayrı bir süreç var, ancak bunlar bu yazının kapsamı dışında kalan ayrıntılar. .

Seçeceğimiz örnek basit bir örnek: kübik denklemin çözümünü bildiğinizi kanıtlamak: �3+�+5=35 (ipucu: cevap 3). Bu sorun, ortaya çıkan QAP'nin korkutucu olmayacak kadar büyük olmayacağı kadar basittir, ancak tüm mekanizmaların devreye girdiğini görebileceğiniz kadar önemsiz de değildir.

Fonksiyonumuzu şu şekilde yazalım:

def qeval(x):
    y = x**3
    return x + y + 5

Burada kullandığımız basit özel amaçlı programlama dili, teorik olarak yapabileceğiniz kadar güçlü olan temel aritmetiği (+, −, ⋅, /), sabit kuvvet üssünü (�7 ama �� değil) ve değişken atamayı destekler. içindeki herhangi bir hesaplama (hesaplama adımlarının sayısı sınırlı olduğu sürece; döngülere izin verilmez). Modulo (%) ve karşılaştırma işleçlerinin (<, >, ≤, ≥) desteklenmediğini unutmayın; çünkü doğrudan sonlu döngüsel grup aritmetiğinde modulo veya karşılaştırma yapmanın etkili bir yolu yoktur (bunun için minnettar olun; eğer bir yol olsaydı). ikisinden birini yaparsanız, eliptik eğri kriptografisi "ikili arama" ve "Çin kalan teoremi" diyebileceğinizden daha hızlı kırılır.

Yardımcı girişler olarak bit ayrıştırmaları (örn. 13=23+22+1) sağlayarak, bu ayrıştırmaların doğruluğunu kanıtlayarak ve ikili devrelerde matematik yaparak dili modulo ve karşılaştırmalara kadar genişletebilirsiniz; sonlu alan aritmetiğinde eşitlik (==) kontrolleri yapmak da yapılabilir ve aslında biraz daha kolaydır, ancak bunların her ikisi de şu anda girmeyeceğimiz ayrıntılardır. Dili, koşullu ifadeleri destekleyecek şekilde genişletebiliriz (örn. if �<5:�=7; aksi halde: �=9), bunları aritmetik bir forma dönüştürerek: �=7⋅(�<5)+9⋅(�≥5) ) ancak koşulun her iki "yolunun" da yürütülmesi gerekeceğini unutmayın ve eğer çok sayıda iç içe geçmiş koşulunuz varsa, bu durum büyük miktarda ek yüke yol açabilir.

Şimdi bu süreci adım adım inceleyelim. Herhangi bir kod parçası için bunu kendiniz yapmak istiyorsanız, burada bir derleyici uyguladı (yalnızca eğitim amaçlı; gerçek dünyadaki zk-SNARK'lar için QAP'ler oluşturmaya henüz hazır değil!).

düzleşme

İlk adım, keyfi olarak karmaşık ifadeler ve ifadeler içerebilen orijinal kodu, iki biçimde olan bir dizi ifadeye dönüştürdüğümüz bir "düzleştirme" prosedürüdür: �=� (burada � bir değişken veya bir sayı olabilir) ) ve �=� (��) � (burada �� +, −, ⋅, / ve � ve � değişkenler, sayılar veya kendileri alt ifadeler olabilir). Bu ifadelerin her birini bir devredeki mantık kapıları gibi düşünebilirsiniz. Yukarıdaki kod için düzleştirme işleminin sonucu aşağıdaki gibidir:

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

Orijinal kodu ve buradaki kodu okursanız ikisinin eşdeğer olduğunu oldukça kolay görebilirsiniz.

R1CS'ye açılan kapılar

Şimdi bunu derece 1 kısıtlama sistemi (R1CS) adı verilen bir şeye dönüştürüyoruz. Bir R1CS, üç vektörden (�, �, �) oluşan bir grup dizisidir ve bir R1CS'nin çözümü bir � vektörüdür; burada �, �.�⋅�.�−�.�=0 denklemini karşılamalıdır, burada . nokta çarpımı temsil eder – daha basit bir ifadeyle, � ve �'yi "bir araya getirirsek", aynı konumlardaki iki değeri çarparsak ve ardından bu çarpımların toplamını alırsak, sonra aynısını � ve � ve ardından � ve � için yaparsak ise üçüncü sonuç ilk iki sonucun çarpımına eşit olur. Örneğin, bu memnun bir R1CS'dir:

Ancak tek bir kısıtlama yerine birçok kısıtlamamız olacak: her mantık kapısı için bir tane. İşlemin ne olduğuna (+, −, ⋅ veya /) ve argümanların değişken mi yoksa sayı mı olduğuna bağlı olarak bir mantık kapısını (�,�,�) üçlüsüne dönüştürmenin standart bir yolu vardır. Her vektörün uzunluğu, sistemdeki değişkenlerin toplam sayısına eşittir; bunlar arasında ilk indekste 1 sayısını temsil eden bir kukla değişken, giriş değişkenleri, çıktıyı temsil eden bir kukla değişken ~out ve daha sonra tüm değişkenler bulunur. ara değişkenler (���1 ve ����2 yukarıda); vektörler genellikle çok seyrek olacak, yalnızca belirli bir mantık kapısından etkilenen değişkenlere karşılık gelen yuvaları dolduracak.

İlk olarak kullanacağımız değişken eşlemesini sağlayacağız:

'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

Çözüm vektörü bu sırayla tüm bu değişkenlere yönelik atamalardan oluşacaktır.

Şimdi ilk kapı için (�,�,�) üçlüsünü vereceğiz:

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

Çözüm vektörünün ikinci konumda 3 ve dördüncü konumda 9 içermesi durumunda, çözüm vektörünün geri kalan içeriği ne olursa olsun, iç çarpım kontrolünün 3⋅3=9'a indirgeneceğini ve yani geçecek. Çözüm vektörünün ikinci konumunda -3 ve dördüncü konumunda 9 varsa kontrol de başarılı olacaktır; aslında, eğer çözüm vektörünün ikinci konumunda 7 ve dördüncü konumunda 49 varsa o zaman bu kontrol yine de başarılı olacaktır — bu ilk kontrolün amacı yalnızca birinci kapının giriş ve çıkışlarının tutarlılığını doğrulamaktır.

Şimdi ikinci kapıya geçelim:

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

İlk nokta çarpım kontrolüne benzer tarzda burada ���1⋅�=� ifadesini kontrol ediyoruz.

Şimdi üçüncü kapı:

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]

Burada model biraz farklıdır: çözüm vektöründeki ilk öğeyi ikinci öğeyle, ardından beşinci öğeyle çarpıyor, iki sonucu ekliyor ve toplamın altıncı öğeye eşit olup olmadığını kontrol ediyor. Çözüm vektöründeki ilk öğe her zaman bir olduğundan, bu yalnızca çıktının iki girdinin toplamına eşit olup olmadığını kontrol eden bir toplama kontrolüdür.

Son olarak dördüncü kapı:

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

Burada son kontrolü değerlendiriyoruz, ~out =���2+5. Nokta çarpım kontrolü, çözüm vektöründeki altıncı öğeyi alıp ilk öğenin beş katını ekleyerek çalışır (hatırlatma: ilk öğe 1'dir, yani bu aslında 5 eklemek anlamına gelir) ve bunu üçüncü öğeye göre kontrol ederek çalışır; çıkış değişkenini saklayın.

Ve burada dört kısıtlamalı R1CS'miz var. Tanık, girdi, çıktı ve iç değişkenler de dahil olmak üzere tüm değişkenlerin atanmasıdır:

[1, 3, 35, 9, 27, 30]

Bunu, yukarıdaki düzleştirilmiş kodu basitçe "yürüterek", giriş değişkeni ataması �=3 ile başlayarak ve bunları hesaplarken tüm ara değişkenlerin ve çıktının değerlerini girerek kendiniz hesaplayabilirsiniz.

Bir araya getirilen R1CS'nin tamamı şöyledir:

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]

B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

R1CS'den QAP'ye dönüştürücü

Bir sonraki adım, bu R1CS'yi alıp, nokta çarpımları yerine polinomların kullanılması dışında tam olarak aynı mantığı uygulayan QAP formuna dönüştürmektir. Bunu şu şekilde yapıyoruz. 3uzunluğundaki üç vektörden oluşan dört gruptan üç derece-3 polinomdan oluşan altı ila altı gruba gidiyoruz, burada polinomları her birinde değerlendiriyoruz x koordinatı kısıtlamalardan birini temsil eder. Yani, polinomları �=1'de değerlendirirsek ilk vektör kümemizi elde ederiz, polinomları �=2'de değerlendirirsek ikinci vektör kümemizi elde ederiz, vb.

Bu dönüşümü, adı verilen bir şeyi kullanarak yapabiliriz. Lagrange enterpolasyonu. Lagrange enterpolasyonunun çözdüğü sorun şudur: Eğer bir dizi noktanız varsa (yani (�,�) koordinat çiftleri), o zaman bu noktalar üzerinde Lagrange enterpolasyonu yapmak size tüm bu noktalardan geçen bir polinom verir. Bunu problemi ayrıştırarak yaparız: her bir koordinat için, o koordinatta istenen koordinata ve ilgilendiğimiz diğer tüm koordinatlarda 0 koordinatına sahip bir polinom yaratırız ve ardından sonuncuyu elde ederiz. sonuç olarak tüm polinomları bir araya topluyoruz.

Bir örnek yapalım. (1,3),(2,2) ve (3,4)'ten geçen bir polinom istediğimizi varsayalım. (1,3),(2,0) ve (3,0)'dan geçen bir polinom yaparak başlıyoruz. Görünen o ki, �=1'de "dışarı çıkan" ve diğer ilgi çekici noktalarda sıfır olan bir polinom yapmak kolaydır; basitçe şunu yaparız:

(x - 2) * (x - 3)

Hangisi şuna benziyor:

Şimdi, x=1'deki yüksekliğin doğru olması için onu "yeniden ölçeklendirmemiz" gerekiyor:

(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

Bu bize şunları verir:

1.5 * x**2 - 7.5 * x + 9

Daha sonra aynısını diğer iki nokta için de yaparız ve benzer görünümlü iki polinom daha elde ederiz, ancak bunların �=2 yerine �=3 ve �=1 noktasında "çıkıntılı" olması gerekir. Üçünü bir araya getiriyoruz ve şunu elde ediyoruz:

1.5 * x**2 - 5.5 * x + 7

Tam olarak istediğimiz koordinatlarla. Yukarıda açıklanan algoritma �(�3) zaman alır, çünkü � nokta vardır ve her nokta polinomları birlikte çarpmak için �(�2) zaman gerektirir; biraz düşünerek bu süre �(�2) zamana indirilebilir ve çok daha fazla düşünülerek, hızlı Fourier dönüşüm algoritmaları ve benzerleri kullanılarak daha da azaltılabilir - zk'de kullanılan işlevler söz konusu olduğunda çok önemli bir optimizasyon -Uygulamada SNARK'ların genellikle binlerce kapısı vardır.

Şimdi R1CS'mizi dönüştürmek için Lagrange enterpolasyonunu kullanalım. Yapacağımız şey, her π vektöründen ilk değeri çıkarmak, bundan bir polinom oluşturmak için Lagrange enterpolasyonunu kullanmak (burada π'deki polinomun değerlendirilmesi size π'inci vektörün ilk değerini verir), işlemi tekrarlamak her � ve � vektörünün ilk değeri için ve ardından bu işlemi ikinci değerler, üçüncü değerler vb. için tekrarlayın. Kolaylık sağlamak için cevapları hemen vereceğim:

A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

Katsayılar artan sırada olduğundan yukarıdaki ilk polinom aslında 0.833⋅�3—5⋅�2+9.166⋅�−5'tir. Bu polinom seti (artı daha sonra açıklayacağım bir Z polinomu) bu özel QAP örneğinin parametrelerini oluşturur. Doğrulamak için zk-SNARK'ları kullanmaya çalıştığınız her işlev için bu noktaya kadar yapılan tüm çalışmaların yalnızca bir kez yapılması gerektiğini unutmayın; QAP parametreleri oluşturulduktan sonra yeniden kullanılabilirler.

Tüm bu polinomları �=1 noktasında değerlendirmeye çalışalım. Bir polinomu �=1'de değerlendirmek, basitçe tüm katsayıların toplanması anlamına gelir (tüm � için 1�=1 gibi), dolayısıyla zor değildir. Şunu elde ederiz:

A results at x=1
0
1
0
0
0
0

B results at x=1
0
1
0
0
0
0

C results at x=1
0
0
0
1
0
0

Ve işte, burada sahip olduğumuz şey, yukarıda oluşturduğumuz ilk mantık kapısı için üç vektör kümesiyle tamamen aynı.

QAP'yi kontrol etme

Peki bu çılgın dönüşümün amacı ne? Cevap şu: R1CS'deki kısıtlamaları tek tek kontrol etmek yerine artık kontrol edebiliriz tüm kısıtlamalar aynı anda nokta çarpım kontrolünü yaparak polinomlar üzerinde.

Bu durumda nokta çarpım kontrolü polinomların bir dizi toplaması ve çarpması olduğundan, sonuç da bir polinom olacaktır. Yukarıda bir mantık kapısını temsil etmek için kullandığımız her π koordinatında değerlendirilen sonuçtaki polinom sıfıra eşitse bu, tüm kontrollerin başarılı olduğu anlamına gelir; Bir mantık kapısını temsil eden � koordinatlarından en az biri olarak değerlendirilen sonuçtaki polinom sıfırdan farklı bir değer veriyorsa bu, o mantık kapısına giren ve çıkan değerlerin tutarsız olduğu anlamına gelir (örn. kapı �=�⋅�� �1 ancak sağlanan değerler �=2,���1=2 ve �=5 olabilir).

Ortaya çıkan polinomun kendisinin sıfır olması gerekmediğini ve aslında çoğu durumda sıfır olmayacağını unutmayın; sonuç tüm noktalarda sıfır olduğu sürece, herhangi bir mantık kapısına karşılık gelmeyen noktalarda herhangi bir davranışa sahip olabilir. do bazı kapılara karşılık gelir. Doğruluğunu kontrol etmek için aslında �=�.�⋅�.�−�.� polinomunu bir kapıya karşılık gelen her noktada değerlendirmiyoruz; bunun yerine, �'yi başka bir polinomla böleriz ve �'nin eşit olarak bölündüğünü, yani `/' bölümünün kalan bırakmadığını kontrol ederiz.

� (�−1)⋅(�−2)⋅(�−3)… olarak tanımlanır: mantık kapılarına karşılık gelen tüm noktalarda sıfıra eşit olan en basit polinom. Cebirin temel bir gerçeğidir ki herhangi tüm bu noktalarda sıfıra eşit olan polinom, bu minimal polinomun bir katı olmalıdır ve eğer bir polinom, −'nin katı ise, o zaman bu noktalardan herhangi birindeki değerlendirmesi sıfır olacaktır; bu denklik işimizi çok kolaylaştırıyor.

Şimdi yukarıdaki polinomlarla nokta çarpım kontrolünü yapalım. İlk olarak ara polinomlar:

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

Şimdi, �.�⋅�.�—�.�:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

Şimdi, minimum polinom �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4):

Z = [24, -50, 35, -10, 1]

Yukarıdaki sonucu �'ye bölersek şunu elde ederiz:

h = t / Z = [-3.666, 17.055, -3.444]

Geri kalanı olmadan.

Ve böylece QAP için bir çözümümüz var. Bu QAP çözümünü türettiğimiz R1CS çözümündeki değişkenlerden herhangi birini tahrif etmeye çalışırsak - örneğin sonuncuyu 31 yerine 30'e ayarlarsak, o zaman kontrollerden birini geçemeyen bir π polinomu elde ederiz (bu özel durumda) durumda, �=3'teki sonuç 1 yerine −0 olacaktır) ve ayrıca �, �'nin katı olmayacaktır; bunun yerine, �/�'yi bölmek, [−5.0,8.833,−4.5,0.666] kalanını verecektir.

Yukarıdakilerin bir basitleştirme olduğunu unutmayın; "Gerçek dünyada" toplama, çarpma, çıkarma ve bölme normal sayılarla değil, sonlu alan elemanlarıyla gerçekleşecektir; kendi içinde tutarlı olan ürkütücü bir aritmetik türü, dolayısıyla bildiğimiz ve sevdiğimiz tüm cebir yasaları hala doğrudur, ancak tüm yanıtların bazı sonlu boyutlu kümelerin öğeleri olduğu durumlarda, bazı � için genellikle 0 ila −1 aralığında tamsayılar bulunur. Örneğin, �=13 ise 1/2=7 (ve 7⋅2=1),3⋅5=2 vb. Sonlu alan aritmetiğinin kullanılması, yuvarlama hataları konusunda endişelenme ihtiyacını ortadan kaldırır ve sistemin eliptik eğrilerle güzel bir şekilde çalışmasına olanak tanır; bu, zk-SNARK protokolünü gerçekten güvenli kılan zk-SNARK makinesinin geri kalanı için gerekli hale gelir.

zk-SNARK'ların iç işleyişine ilişkin birçok ayrıntıyı bana açıklama konusunda yardımcı olduğu için Eran Tromer'a özellikle teşekkür ederim.

• SEO Destekli İçerik ve Halkla İlişkiler Dağıtımı. Bugün Gücünüzü Artırın.
• PlatoData.Network Dikey Üretken Yapay Zeka. Kendine güç ver. Buradan Erişin.
• PlatoAiStream. Web3 Zekası. Bilgi Genişletildi. Buradan Erişin.
• PlatoESG. karbon, temiz teknoloji, Enerji, Çevre, Güneş, Atık Yönetimi. Buradan Erişin.
• PlatoSağlık. Biyoteknoloji ve Klinik Araştırmalar Zekası. Buradan Erişin.
• Blok Ofsetleri. Çevre Dengeleme Sahipliğini Modernleştirme. Buradan Erişin.
• Kaynak: Plato Veri Zekası.