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

1 Giriş

STARK'ların verimsizliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır; örneğin, for döngüsündeki indeksler, doğru/yanlış değerler, sayaçlar vb. Ancak, Merkle ağaçları üzerine kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanarak verileri genişletirken, birçok ek fazlalık değeri tüm alanı kaplar. Oysa 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 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ği hala büyük ölçüde israf alanı içermektedir. Buna göre, ikili alan doğrudan bitlere işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı içermez, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alanların araştırması 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alanlar kriptografide yaygın olarak kullanılmaktadır, tipik örnekler şunlardır:

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

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

• 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 tekrarlamalara son derece uygun bir hash algoritmasıdır.

Küçük bir alan kullanıldığında, 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 genişletmeye bağlıdır. Çoğu Prover hesaplamasında yer alan çok terimli ifadeler genişletmeye girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hala gerekli güvenliği sağlamak için daha büyük bir genişletmeye derinlemesine inmelidir.

İkili alanlara dayalı bir kanıt sistemi inşa ederken iki pratik sorun vardır: STARKs'ta izlerin temsilini hesaplarken kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüdü yaparken Reed-Solomon kodlaması yapılmalıdır ve kullanılan alanın boyutu, kodlama genişletildikten sonraki boyuttan büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alarak yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde ifade etti: ilk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerleri ile tüm hesaplama izini temsil etti; ikinci olarak, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare (square) olarak değerlendirilebilir ve bu kareye dayanarak 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ırmıştır.

2 İlkelerin Analizi

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

• Bilgi Teorisi Polinomlu Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin merkezi 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 adım adım 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ı sorgulayabilir. Mevcut PIOP protokolleri arasında PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme şekli açısından farklılık gösterir ve 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şitliklerinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografi aracıdır; bu aracılığıyla, kanıtlayıcı bir polinoma taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, polinomun diğer bilgilerini gizli tutar. Yaygın polinom taahhüt şemaları arasında KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) ve Brakedown gibi şemalar bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama senaryolarına sahiptir.

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

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi olup, Pasta eğrisi üzerine kuruludur. Halo2 tasarlanırken, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanılmış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 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 gerektirmeden şeffaflık sağlamasını, yineleme kanıtlarını veya toplama kanıtları gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alanlar. Özellikle, Binius yüksek verimliliği ve güvenliği sağlamak için beş ana teknoloji içermektedir. İlk olarak, kule tipi ikili alanlar (towers of binary fields) temelinde yapılan aritmetik, hesaplamalarının temelini oluşturarak, ikili alan içinde basitleştirilmiş işlemleri gerçekleştirmektedir. İ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 yeni bir çoklu lineer kaydırma kanıtı tanıtarak, küçük alanlarda çoklu lineer ilişkilerin doğrulanma verimliliğini optimize etmektedir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlamak için geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alanda verimli bir kanıt sistemi gerçekleştirmesini sağlayan ve genellikle büyük alanlarla ilişkili maliyetleri azaltan küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

2.1 Sonlu Alanlar: binary alanların kuleleri üzerine kurulu aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bu, iki ana nedene dayanmaktadır: etkili hesaplama ve etkili aritmetizasyon. İkili alan, temel olarak son derece etkili 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 alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilmesini sağlayan basitleştirilmiş bir aritmetizasyon sürecini destekler. Bu özellikler, kule yapısından tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical", ikili alandaki öğelerin 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 öğesine haritalanabilir. Bu, asal alanlardan farklıdır; asal alan, belirli bir bit sayısında bu tür bir standart gösterimi sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize benzersiz bir alan öğesi ile karşılık gelmeyebilir, oysa ikili alan bu bire bir eşleme kolaylığını sunar. Asal alan Fp'de, yaygın olarak kullanılan 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, sık kullanılan azaltma yöntemleri arasında özel azaltma (AES'te kullanılan), Montgomery azaltması (POLYVAL'da kullanılan) ve yinelemeli azaltma (Tower gibi) yer alır. "Prime Field ile Binary Field ECC-Hardware Implementations Tasarım Alanını Keşfetme" başlıklı makalede, 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 belirtilmiştir; çünkü bu işlem (X + Y )2 = X2 + Y 2'nin basitleştirilmiş kuralına uyar.

Ş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 eleman olarak görülebilir veya iki 64 bitlik kule alanı elemanı, dört 32 bitlik kule alanı elemanı, 16 adet 8 bitlik kule alanı elemanı veya 128 adet F2 alanı elemanı olarak ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, sadece bit dizesinin tür dönüşümü (typecast) ile sağlanır ve bu çok ilginç ve yararlı bir özellik olarak öne çıkar. Aynı zamanda, küçük alan elemanları, ek bir hesaplama maliyeti olmadan daha büyük alan elemanları 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" adlı çalışmada, n bitlik kule biçimindeki ikili alanda (m bitlik alt alanlara ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığı incelenmiştir.

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ümenin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması benimsemiştir. Bu temel kontroller şunları içerir:

1. GateCheck: Gizli tanık ω ve açık girdi x'in, devre hesaplama ilişkisi C(x,ω)=0'ı karşılayıp karşılamadığını doğrulamak için, devrenin doğru çalıştığından emin olmak.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiperküpü üzerindeki değerlendirme sonuçlarının bir permütasyon ilişkisi olup olmadığını doğrular f(x) = f(π(x)), çok terimli değişkenler arasındaki dizilim tutarlılığını sağlamak için.

3. LookupCheck: Verilen bir arama tablosunda çok terimli bir polinomun değerlendirilmesinin doğrulanması, 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ş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: Boole hiper küpü üzerinde rasyonel çok terimli polinomun değerlendirilmesinin belirlenen bir değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol eder, böylece polinom çarpımının doğruluğunu sağlar.

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

7. SumCheck: Çok değişkenli çok terimli polinomun toplamının beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol eder. Ç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 kontrol örneği için toplu işleme olanak tanır.

8. BatchCheck: SumCheck'e dayalı olarak, çoklu çok değişkenli polinom değerlendirmelerinin 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 hiperküpte 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 problemi ile ilgili çözüm: HyperPlonk sıfıra bölme durumunu yeterince ele alamadığından, U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığına dair kesin bir şey söylenememektedir; Binius bu durumu doğru bir şekilde ele almış, paydanın sıfır olduğu durumlarda bile Binius'un ProductCheck'i işlemeye devam edebilmekte ve herhangi bir çarpım değerine genişletmeye izin vermektedir.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değil; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimlilik sıralama durumlarını yönetmesini 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 çok terimli doğrulamalarını ele alırken daha güçlü fonksiyonel destek sağladı. Bu geliştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıtlama sistemleri için bir temel oluşturdu.

2.3 PIOP: Yeni çok çizgili kaydırma argümanı------Boolean hiper kümesine uygundur

Binius protokolünde, sanal polinomların inşası ve işlenmesi önemli teknolojilerden biridir ve giriş kollarından veya diğer sanal polinomlardan türetilen polinomları etkili bir şekilde oluşturup işlemeye olanak tanır. İşte iki temel yöntem:

• Paketleme: