Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri

1 Giriş

STARK'ların verimsizliğinin ana sebeplerinden biri şudur: Gerçek programlardaki çoğu sayısal değer oldukça küçüktür, örneğin for döngüsündeki indeksler, doğru-yanlış değerleri, sayaçlar vb. Ancak, Merkle ağaçlarına dayalı kanıtların güvenliğini sağlamak için, verileri genişletmek amacıyla Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değer tüm alanı kaplayacaktır, bu nedenle orijinal değerler kendileri çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARKs kodlama genişliği 252 bit, 2. nesil STARKs kodlama genişliği 64 bit, 3. nesil STARKs kodlama genişliği 32 bit, ancak 32 bit kodlama genişliğinde hala büyük miktarda israf alanı vardır. Buna karşılık, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı olmadan, yani 4. nesil STARKs.

Goldilocks, BabyBear ve Mersenne31 gibi son yıllarda yapılan araştırmalara kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alan kriptografide yaygın olarak kullanılmaktadır, tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standardı (AES), F28 alanına dayanır;

• Galois Mesaj Doğrulama Kodu ( GMAC ), F2128 alanına dayalı;

• QR kodu, F28 tabanlı Reed-Solomon kodlaması kullanır;

• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve tekrar eden yapılar için oldukça uygun bir hash algoritmasıdır.

Küçük alanlar kullanıldığında, alan genişletme işlemi güvenliği sağlamak için giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliğini ve pratik kullanılabilirliğini sağlamak için tamamen alan genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadelerin genişletilmiş alana girmesine gerek yoktur, yalnızca temel alan altında işlem yapmak yeterlidir; bu da küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletilmiş alana derinlemesine inmek zorundadır.

İkili alan üzerine kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'da iz temsilini hesaplamak için kullanılan alanın büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'da Merkle ağacının taahhüdü için Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alanın büyüklüğü, kodlama genişletildikten sonra büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde ifade ederek bunu başardı: İlk olarak, çok değişkenli (, özellikle çok lineer ) çok terimden oluşan polinomlar kullanarak tek değişkenli polinomların yerini alıyor ve "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama yolunu temsil ediyor; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare ) olarak düşünülebilir ve bu kare temel alınarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliği sağlarken kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırıyor.

2 Prensip Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki kısmı içerir:

• Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin temelini oluşturur ve girilen hesaplama ilişkisini doğrulanabilir polinom eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının polinomları adım adım göndermesine izin verir ve böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca birkaç polinomun değerlendirme sonuçlarını sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunlar, polinom ifadelerinin işlenme biçiminde farklılık gösterir, bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Şeması ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denkleminin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bununla, kanıtlayıcı belirli bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizleyebilir. Yaygın polinom taahhüt şemaları arasında KZG, Bulletproofs, FRI ( Hızlı Reed-Solomon IOPP ) ve Brakedown gibi şemalar bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama senaryolarına sahiptir.

Belirli gereksinimlere göre farklı PIOP ve PCS'ler seçerek, uygun bir sonlu alan veya eliptik eğri ile bir araya getirerek, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ve Pasta eğrisi üzerine kuruludur. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS kombinasyonunu kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir yinelemeyi gerçekleştirmek için tasarlanmıştır. Bu sistemleri tasarlarken, seçilen PIOP ve PCS, kullanılan sonlu alan veya eliptik eğri ile eşleşmelidir; bu, sistemin doğruluğunu, performansını ve güvenliğini sağlamak için önemlidir. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemenin yanı sıra, sistemin güvenilir bir kurulum gerektirmeden şeffaflık sağlama yeteneğini ve yinelemeli kanıtlar veya toplu kanıtlar gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + binary field. Özellikle, Binius, verimliliği ve güvenliğini sağlamak için beş anahtar teknolojiyi içermektedir. İlk olarak, kule biçimindeki ikili alanların (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş hesaplamalar gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde HyperPlonk çarpan ve yer değiştirme kontrolünü uyarlayarak, değişkenler ve bunların yer değiştirmeleri arasındaki güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu doğrusal ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrusal kaydırma kanıtı tanıtmaktadır. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını benimsemektedir. Son olarak, protokol, küçük alan çokgen taahhüt şemasını (Small-Field PCS) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesine ve genellikle büyük alanlarla ilişkili olan yükleri azaltmasına olanak tanımaktadır.

( 2.1 Sonlu Alan: binary alanların kulelerine dayalı aritmetik

Kule ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynar ve bu esasen iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetizasyon. İkili alan, doğası gereği son derece verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, ikili alan üzerinde gerçekleştirilen işlemlerin kompakt ve kolayca doğrulanabilir cebirsel biçimlerde ifade edilebileceği basitleştirilmiş bir aritmetizasyon sürecini destekler. Bu özellikler, kule yapısının katmanlı özelliklerinden tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alandaki bir elemanın benzersiz ve doğrudan gösterim biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k bitlik dize doğrudan k bitlik bir ikili alan elemanına haritalanabilir. Bu, asal alanların aksine, belirli bir bit sayısı içinde bu tür standart bir gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilirken, her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmezken, ikili alan bu birine bir eşleme kolaylığını sunar. Asal alan Fp'de, yaygın azaltma yöntemleri arasında Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel azaltma yöntemleri bulunur. İkili alan F2k'de, yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma ) gibi AES'te kullanılan ###, Montgomery azaltması ( gibi POLYVAL'de kullanılan ) ve yinelemeli azaltma ( gibi Tower ) bulunmaktadır. "Prime Field ile Binary Field ECC-Hardware Implementations Tasarım Alanını Keşfetme" başlıklı makale, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediğini ve ikili alanın kare alma işleminin son derece verimli olduğunu belirtir, çünkü (X + Y )2 = X2 + Y 2'nin basitleştirilmiş kuralını takip eder.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: Bu dize, ikili alan bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir unsur olarak düşünülebilir veya iki 64 bitlik kule alan unsuru, dört 32 bitlik kule alan unsuru, 16 adet 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizesinin tür dönüşümü (typecast) ile sağlanır ve bu oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama maliyeti olmaksızın daha büyük alan unsurlarına paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özellikten yararlanmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" adlı makalede, n bitlik kule biçimindeki ikili alanda (, m bitlik alt alana ) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığı incelenmektedir.

( 2.2 PIOP:Uyarlanmış HyperPlonk Ürünü ve Permütasyon Kontrolü------İkili alan için uygundur

Binius protokolündeki PIOP tasarımı HyperPlonk'tan esinlenmiştir ve çok terimli ve çok değişkenli kümenin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:

1. GateCheck: Gizli tanıklama ω ve açık girdi x'in, devre hesaplama ilişkisi C)x, ω###=0 ile uyumlu olup olmadığını doğrulamak için kullanılmaktadır, böylece devre doğru çalıştığından emin olunur.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Boolean hiperküp üzerindeki değerlendirme sonuçlarının değişim ilişkisi olup olmadığını doğrulamak için f(x) = f(π)x((, polinom değişkenleri arasındaki sıralamanın tutarlılığını sağlamak amacıyla.

3. LookupCheck: Verilen arama tablosunda çok terimli değerlendirmenin doğruluğunu kontrol eder, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğunu garanti eder.

4. MultisetCheck: İki çok değişkenli kümenin eşitliğini kontrol eder, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, birden fazla küme arasındaki tutarlılığı garanti eder.

5. ProductCheck: Bir rasyonel çok terimli polinomun Boole hipo-küpünde belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s olup olmadığını kontrol ederek, polinom çarpımının doğruluğunu sağlamak.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean hiperkübündeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, polinomun sıfır noktası dağılımını sağlamak için.

7. SumCheck: Çok değişkenli çok terimli polinomların toplamının beyan edilen değerle olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirmesine dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar getirerek birden fazla toplam doğrulama örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinom değerlendirmenin doğruluğunu doğrulamak için protokol verimliliğini artırır.

Binius ve HyperPlonk'un protokol tasarımında birçok benzerliği olmasına rağmen, Binius aşağıdaki 3 alanda iyileştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in paydası U'nun hiper küp üzerinde her yerde sıfır olmaması ve çarpımın belirli bir değere eşit olması gerekmektedir; Binius, bu değeri 1 olarak özelleştirerek bu kontrol sürecini basitleştirir ve hesaplama karmaşıklığını azaltır.

• Sıfıra bölme problemiyle başa çıkma: HyperPlonk sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküpte sıfırdan farklı olduğu konusunda kesin bir şey söylemeyi imkansız hale getirdi; Binius bu sorunu doğru bir şekilde ele aldı, hatta paydanın sıfır olduğu durumlarda bile, Binius'in ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genişletmeye izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çoklu polinom sıralama durumlarını işlemesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasındaki iyileştirmelerle protokolün esnekliğini ve verimliliğini artırdı; özellikle daha karmaşık çok değişkenli çok terimli doğrulama işlemlerinde daha güçlü fonksiyonel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayanan kanıtlama sistemleri için bir temel oluşturdu.

( 2.3 PIOP: yeni çok çizgili kaydırma argümanı------boolean hiperküp için uygundur

Binius protokolünde, sanal çok terimli yapıların inşası ve işlenmesi, giriş tutamağından veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturabilen ve işleyebilen anahtar teknolojilerden biridir. İşte iki anahtar yöntem:

• Ambalaj: Bu yöntem aracılığıyla