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

1 Giriş

STARKs'ın verimsizliğinin ana nedenlerinden biri şudur: Gerçek programlardaki çoğu sayısal değer oldukça küçüktür; örneğin döngülerdeki indeksler, doğru-yanlış değerleri, sayaçlar vb. Ancak, Merkle ağacı üzerine kurulu kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması ile verileri genişletirken, birçok ek yedek değer tüm alanı kaplayacaktır, hatta orijinal değer kendisi çok küçük olsa bile. Bu sorunu çözmek için alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARKs kodlama bit genişliği 252bit, 2. nesil STARKs kodlama bit genişliği 64bit, 3. nesil STARKs kodlama bit genişliği 32bit, ancak 32bit kodlama bit genişliği hala büyük ölçüde israf alanı içermektedir. Buna karşılık, ikili alan doğrudan bit işlemleri yapmaya izin verir, bu da kompakt ve verimli kodlama sağlar ve herhangi bir israf alanı barındırmaz, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Şu anda, ikili alanlar kriptografide yaygın olarak kullanılmakta olup, tipik örnekler şunlardır:

• İleri Düzey Ş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 son derece uygundur.

Küçük alanlar kullanıldığında, alan genişletme işlemleri güvenliği sağlamak için giderek daha önemli hale gelmektedir. 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 polinomlar, alan genişletmesine girmeden yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Bununla birlikte, rastgele nokta kontrolü ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir alan genişletmesine derinlemesine girmeyi gerektirir.

İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun ortaya çıkar: STARKs'te izin (trace) gösterimini hesaplarken, kullanılan alanın büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'te Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerektiğinden, kullanılan alanın büyüklüğü, kodlama genişletildikten sonraki boyuttan büyük olmalıdır.

Binius, her iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde temsil ederek bunu başardı: Öncelikle, çok değişkenli (, özellikle çok lineer ) polinomunu tek değişkenli polinomun yerine kullanarak, "hiperküp" ( üzerinde aldığı değerlerle tüm hesaplama izini temsil eder; İkincisi, hiperküpün her boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküpü kare ) olarak düşünerek, bu kareye dayalı olarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliği sağlarken, kodlama verimliliği ve hesaplama performansını büyük ölçüde artırmaktadır.

2 İlkelerin Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki bölümden oluşur:

• Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin çekirdeği olarak, girişteki hesaplama ilişkisini doğrulanabilir polinom denklemlerine 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, böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için az sayıda 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 şekillerine bağlı olarak, tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Protokolü ( Polinom Taahhüt Protokolü, PCS ): Polinom taahhüt protokolü, PIOP tarafından üretilen polinom denklemlerinin doğruluğunu kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı 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 protokolleri arasında KZG, Bulletproofs, FRI ( Hızlı 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'leri seçerek ve uygun bir sonlu alan veya eliptik eğri ile birleştirerek, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile ve Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanmaktadır.

• Plonky2: PLONK PIOP ve FRI PCS kombinasyonunu kullanır ve Goldilocks alanına dayanmaktadır. Plonky2, etkili bir rekursif 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, böylece sistemin doğruluğu, performansı ve güvenliği sağlanır. Bu kombinasyonların seçimi yalnızca SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gerektirmeden şeffaflığı sağlayıp sağlamayacağını, rekursif kanıtlar veya toplu kanıtlar gibi genişletme işlevlerini destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknoloji 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 yapılmasına olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde HyperPlonk çarpım ve permütasyon kontrolünü uyarlayarak, değişkenler ve bunların permütasyonları arasında 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ı sunmaktadır. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmekte ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltmaktadır.

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

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynamaktadır, bu da 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ı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş aritmetik süreçlerini destekler; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel bir biçimde ifade edilebilir. Bu özellikler, kule yapısının katmanlı özelliklerinden tam olarak faydalanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıtlama sistemleri için özellikle uygun hale getirir.

Burada "canonical" terimi, ikili alandaki elemanların tekil 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 eşlenebilir. Bu, asal alanlardan farklıdır; asal alanlar, belirli bir bit sayısı içinde bu tür standart bir temsil sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize tekil bir alan elemanıyla eşleşemezken, ikili alan bu birebir eşleşme kolaylığını sunar. Asal alan Fp'de, yaygın olarak kullanılan azaltma yöntemleri arasında Barrett azaltması, Montgomery azaltması ve belirli sonlu alanlar için Mersenne-31 veya Goldilocks-64 gibi özel azaltma yöntemleri bulunmaktadır. İkili alan F2k'da, yaygın olarak kullanılan azaltma yöntemleri arasında AES'de kullanılan özel azaltma ), POLYVAL'da kullanılan Montgomery azaltması ### ve Tower( gibi tekrarlı azaltma ) yer almaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı çalışmada, ikili alanın toplama ve çarpma işlemlerinde taşma gerektirmediği ve ikili alanın kare alma işleminin oldukça verimli olduğu, çünkü (X + Y )2 = X2 + Y2'nin basitleştirilmiş kuralına uyduğu belirtilmiştir.

Ş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 görülebilir veya iki adet 64 bitlik kule alan unsuru, dört adet 32 bitlik kule alan unsuru, on altı adet 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak analiz edilebilir. Bu temsilin esnekliği herhangi bir hesaplama yükü gerektirmez, yalnızca bit dizisinin tür dönüşümüdür (typecast), oldukça ilginç ve faydalı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek hesaplama yükü olmaksızın daha büyük alan unsurları olarak paketlenebilir. Binius protokolü bu özelliği kullanarak hesaplama verimliliğini artırmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" makalesi, n bitlik kule tipi ikili alanda ( m bitlik alt alan )'da çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

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

Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almış olup, ç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çerir:

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

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin boolean hiperküredeki değer sonuçlarının, polinom değişkenleri arasındaki permütasyon tutarlılığını sağlamak için f)x### = f(π)x() şeklinde bir permütasyon ilişkisi olup olmadığını doğrulama.

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

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: Mantıksal hiperküpte bir rasyonel polinomun değerinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s ile eşit olup olmadığını kontrol etme, polinom çarpımının doğruluğunu sağlamak için.

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 noktalarının dağılımını sağlamak için.

7. SumCheck: Çok değişkenli çok terimli polinomun toplamının, belirtilen değerle eşit olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirme sorununa dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar kullanarak, birden fazla toplam kontrol örneği için toplu işleme olanak tanır ve lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli 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, payda U'nun hiper küp üzerinde her yerde sıfır olmamasını ve çarpımın belirli bir değere eşit olmasını gerektirir; 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 sorunlarının yönetimi: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadığı için U'nun hiper küp üzerindeki sıfır olmayan durumu hakkında kesin bir şey söyleyememektedir; Binius bu sorunu doğru bir şekilde ele alarak, paydanın sıfır olduğu durumlarda bile Binius'un ProductCheck'i devam edebilmekte ve herhangi bir çarpan değerine 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 çok terimli sıralama durumlarını işleyebilmesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasının iyileştirilmesi yoluyla 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ü 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 çok çizgili kaydırma argümanı------boolean hiper küp için uygun

Binius protokolünde, sanal polinomların yapımı ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamağından veya diğer sanal polinomlardan türetilmiş polinomları etkili bir şekilde oluşturup işlemeye olanak tanır. İşte iki anahtar yöntem:

• Paketleme: Bu yöntem, aracılığıyla