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

1 Giriş

STARK'ların verimsizliğinin başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu değer oldukça küçüktür; örneğin döngülerdeki indeksler, mantıksal değerler, sayaçlar vb. Ancak, Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verilerin genişletilmesi sırasında, birçok ek yedek değer tüm alanı kaplar, bu durum orijinal değer kendisi çok küçük olsa bile geçerlidir. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

Tablo 1'de gösterildiği gibi, 1. nesil STARKs kodlama bit genişliği 252 bit, 2. nesil STARKs kodlama bit genişliği 64 bit, 3. nesil STARKs kodlama bit genişliği 32 bit, ancak 32 bit kodlama bit genişliğinde hala büyük ölçüde israf alanı bulunmaktadır. Buna karşılık, ikili alan doğrudan bitlerle işlem yapmaya izin verir, kodlama kompakt ve verimli bir şekilde herhangi bir israf alanı olmaksızın gerçekleştirilir, yani 4. nesil STARKs.

Tablo 1: STARKs türev yolu

| Nesil | Kodlama Bit Genişliği | Temsilci Sistem | |------|----------|----------| | 1. Nesil | 252 bit | StarkWare STARKs | | 2. nesil | 64 bit | Plonky2 | | 3. Nesil | 32 bit | BabyBear | | 4. nesil | 1 bit | Binius |

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara göre, ikili alan üzerindeki çalışmalar 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alan kriptografi alanında yaygın olarak kullanılmaktadır, tipik örnekler arasında şunlar bulunmaktadır:

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

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

• 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 yinelemeli hash algoritması için oldukça uygundur.

Küçük bir alan kullanıldığında, genişletme işlemi güvenliğin sağlanmasında giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliğini ve gerçek kullanılabilirliğini garantilemek için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan polinomlar genişletme alanına girmek zorunda kalmadan, yalnızca temel alanda işlem yaparak 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şletme alanına derinlemesine inmek zorundadır.

İkili alan temelli bir kanıt sistemi kurarken, iki pratik sorun vardır: STARKs'ta izin (trace) temsilini hesaplamak için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüdü (commitment) için Reed-Solomon kodlaması yapılırken, kullanılan alanın boyutu kodlama sonrasında genişletilmiş boyuttan 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 temsil ederek bunu gerçekleştirdi: İlk olarak, çok değişkenli ('leri, tek değişkenli polinomlar yerine kullanarak, "hiperküpler" ) üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etmek için çok değişkenli ( çok terimli polinomları kullanmaktadır; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare ) olarak değerlendirilebilir ve bu kare temel alınarak Reed-Solomon genişlemesi yapılabilir. Bu yöntem, güvenliği sağlarken kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırmıştır.

2 Prensip Analizi

Günümüzde çoğu SNARKs sistemi genellikle aşağıdaki iki bölümden oluşmaktadır:

• Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin merkezi olarak, 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 aşamalı olarak polinom göndermesine izin verir; 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ı sorgulayarak doğrulama yapabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunlar polinom ifadelerinin işlenme şekline göre 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 eşitliğinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır, bununla birlikte, 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(Fast Reed-Solomon IOPP) ve Brakedown bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve kullanım senaryolarına sahiptir.

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

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarlanırken ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir yineleme sağlamak 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 da sistemin doğruluğunu, performansını ve güvenliğini sağlamak için gereklidir. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum olmaksızın şeffaflık sağlama yeteneğini, yinelemeli kanıtları veya toplu kanıtlar gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + binary fields. Özellikle, Binius, verimliliği ve güvenliği sağlamak için beş anahtar teknolojiyi içerir. İlk olarak, kule biçimindeki ikili alanların (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş işlemler gerçekleştirilmesine olanak tanır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrollerini uyarlayarak, değişkenler ile bunların permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlar. Üçü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ı sunar. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını benimser. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesini sağlayan ve genellikle büyük alanlarla ilişkili maliyetleri azaltan küçük alan çoklu polinom taahhüt şemasını (Small-Field PCS) kullanır.

( 2.1 Sonlu Alanlar: binary alanların kulelerine dayanan aritmetik

Kule tipi ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bu durum iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekler ve bu da onu performansa duyarlı kriptografi uygulamaları için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulaması kolay cebirsel biçimde temsil edilebileceği basitleştirilmiş bir aritmetik süreç destekler. Bu özellikler, kule yapısı aracılığıyla katmanlı özelliklerinden tam anlamıyla yararlanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıtlama sistemleri için özellikle uygun hale getirir.

Burada "canonical", ikili alandaki elemanların benzersiz ve doğrudan temsil 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 alanlardan farklıdır, çünkü asal alan belirli bir bit sayısında bu tür standart bir temsili sağlayamaz. 32 bitlik asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmez; oysa ikili alan bu bir-bir eşleştirme kolaylığını sağlar. 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 bulunmaktadır. İkili alan F2k'de, yaygın kullanılan azaltma yöntemleri arasında AES'te kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower ( gibi özyinelemeli azaltma ) bulunmaktadır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetme" adlı çalışmada, ikili alanın toplama ve çarpma işlemlerinde taşıma gerektirmediği ve ikili alanın kare alma işleminin son derece verimli olduğu belirtilmektedir, çünkü bu (X + Y )2 = X2 + Y2'nin basitleştirilmiş kuralını izler.

Ş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 öğe olarak değerlendirilebilir veya iki 64 bitlik kule alan öğesi, dört 32 bitlik kule alan öğesi, 16 adet 8 bitlik kule alan öğesi veya 128 adet F2 alan öğesi olarak ayrıştırılabilir. Bu temsilin esnekliği herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizisinin tür dönüşümüne dayanmaktadır (typecast), oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan öğeleri, ek hesaplama yükü gerektirmeden daha büyük alan öğelerine paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özelliği kullanır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" başlıklı makale, n bitlik kule ikili alanının ( m bitlik alt alanlara ) çarpma, kare alma ve tersini alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

Şekil 1: Kule Tipi İkili Alan

( 2.2 PIOP: Uyarlanmış HyperPlonk Ürünü ve Permutasyon 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ümelerin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içermektedir:

1. GateCheck: Gizli kanıt ω ve açık girdi x'in, devre işlemi ilişkisi C)x,ω(=0'ı karşılayıp karşılamadığını doğrulayarak devrenin doğru çalışmasını sağlamaktadır.

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

3. LookupCheck: Verilen bir arama tablosunda polinomun değerlendirmesinin doğruluğunu kontrol etme, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğunu garanti etme.

4. MultisetCheck: İki çok değişkenli kümenin eşit olup olmadığını 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: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun değerlendirilmesinin belirli bir bildirilmiş değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmek için, polinom çarpımının doğruluğunu sağlamak.

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

7. SumCheck: Çok değişkenli polinomların toplam değerinin beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol eder. Çok değişkenli polinomların değerlendirilmesi 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şturulmasına da olanak tanır.

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

Binius, HyperPlonk ile protokol tasarımında birçok benzerliğe sahip olmasına rağmen, 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ştirmiş ve hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme sorunlarının işlenmesi: HyperPlonk, sıfıra bölme durumlarını yeterince işleyememiştir, bu da U'nun hiper küp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirlemeyi engellemektedir; Binius bu sorunu doğru bir şekilde ele almıştır, hatta paydanın sıfır olduğu durumlarda bile, Binius'un ProductCheck'i işlemeye devam edebilmekte ve herhangi bir çarpan değeri için genişletilmesine izin vermektedir.

• 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 polinom dizilim durumlarını işleyebilmesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasını geliştirerek protokolün esnekliğini ve verimliliğini artırdı; özellikle daha karmaşık çok değişkenli polinom doğrulama işlemlerinde daha güçlü işlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıt sistemleri için bir temel oluşturdu.

( 2.3 PIOP: yeni çoklu kaydırma argümanı------uygun