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

1 Giriş

STARKs'ın verimsizliğinin ana 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, boolean değerler, sayacılar vb. Ancak, Merkle ağacı tabanlı 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üçüktür. 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ğinde hâlâ büyük bir israf alanı bulunmaktadır. Buna karşılık, ikili alan doğrudan bitlerle işlem yapmaya izin verir, kodlama kompakt ve verimli olup hiçbir israf alanı yoktur, 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'lere kadar uzanmaktadır. Şu anda, ikili alan 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 özyinelemeye son derece uygun bir hash algoritmasıdır.

Küçük alanlar 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 pratik kullanılabilirliğini sağlamak için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan polinomların genişletmeye girmesine gerek yoktur, sadece temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolleri ve FRI hesaplamaları hâlâ gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmelidir.

İkili alanlara dayalı bir kanıt sistemi inşa ederken iki pratik sorun vardır: STARKs'ta izleri temsil etmek için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüt ederken Reed-Solomon kodlaması yapılması gerekir, kullanılan alanın boyutu kodlama genişletildikten sonra boyutundan 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 temsil etti: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerleriyle tüm hesaplama yolunu temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare (square) olarak düşünülebilir ve bu kare temelinde 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 Prensip Analizi

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

• Bilgi Teorik Polinom 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 eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşimde bulunarak, 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ı sorgulayarak doğrulama yapabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerini işleme şekilleri bakımından farklılık gösterdiğinden, tüm SNARK sisteminin performansı ve verimliliği üzerinde etkili olmaktadır.

• Polinom Taahhüt Şeması (Polynomial Commitment Scheme, PCS): Polinom taahhüt şeması, PIOP tarafından üretilen polinom eşitliklerinin geçerliliğini 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ğ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 yöntemler bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygun senaryolar sunar.

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

• Halo2: PLONK PIOP ile Bulletproofs PCS'nin birleşimi olup, Pasta eğrisi üzerine kurulmuştur. 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'yi birleştirir ve Goldilocks alanına dayanmaktadır. Plonky2, verimli bir özyineleme 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, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gerektirmeden şeffaflığı gerçekleştirebilip gerçekleştiremeyeceğini, özyinelemeli kanıtlar veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip destekleyemeyeceğ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 (towers of binary fields) üzerine kurulu aritmetik, hesaplamalarının temelini oluşturarak ikili alan içinde basitleştirilmiş işlemleri gerçekleştirebilmektedir. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve yer değiştirme kontrollerini uyarlayarak değişkenler ve bunların yer değiştirmeleri arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu lineer kaydırma kanıtı getirmektedir. 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 çoklu 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 Sınırlı Alan: binary alanların kuleleri üzerine kurulu aritmetik

Kule biçimindeki ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır ve bu, iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek derecede verimli aritmetik işlemleri destekler ve bu nedenle performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçimdir. Ayrıca, ikili alan yapısı, basitleştirilmiş aritmetik süreçleri destekler; yani, ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde temsil edilebilir. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanları Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical" terimi, ikili alan içindeki bir öğenin benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan olan F2'de, herhangi bir k bitlik dizi doğrudan k bitlik bir ikili alan öğesine eşlenebilir. Bu, asal alanlardan farklıdır; asal alanlar belirli bir bit sayısı içinde bu tür bir standart temsil sağlayamaz. 32 bitlik bir asal alan 32 bit içinde barındırılabilirken, her 32 bitlik dizi benzersiz bir alan öğesine karşılık gelmez; oysa 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 bulunmaktadır. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma (AES'te kullanılan), Montgomery azaltması (POLYVAL'de kullanılan) ve özyinelemeli azaltma (Tower gibi) 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 oldukça verimli olduğu, çünkü (X + Y )2 = X2 + Y 2 biçimindeki sadeleştirilmiş kuralı takip ettiği 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 eleman olarak görülebilir veya iki 64 bitlik kule alanı elemanı, dört 32 bitlik kule alanı elemanı, 16 sekiz bitlik kule alanı elemanı veya 128 F2 alanı elemanı olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile mümkündür ve oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan elemanları, ek 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" başlıklı makale, n bitlik kule yapıdaki ikili alanda (m bitlik alt alana ayrılabilir) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

2.2 PIOP: Yenilikçi 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ı kullanmaktadır. Bu temel kontroller şunları içerir:

1. GateCheck: Gizli tanık ω ve açık girdi x'in devre işlemi ilişkesi C(x, ω)=0'ı sağladığını doğrulamak için devrenin doğru çalışmasını sağlamak.

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

3. LookupCheck: Verilen arama tablosunda çok terimli fonksiyonun değerinin 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 çokterimli polinomun Boolean hiperkübünde değerlendirilmesinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol eder, böylece çokterimli çarpımın doğruluğunu garanti eder.

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

7. SumCheck: Çok değişkenli polinomların toplamının belirtilen değer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerleme sorununu tek değişkenli polinom değerleme sorununa dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek çoklu toplam kontrol örneklerinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturmayı da mümkün kılar.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinomun değerlemesinin 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, paydanın 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 problemi ile ilgili çözüm: HyperPlonk, sıfıra bölme durumlarını yeterince ele alamadı ve bu nedenle U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirlemek mümkün olmadı; Binius bu problemi doğru bir şekilde ele aldı, sıfır olan bir paydada bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genişletilmesine izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değildir; 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şlemesini 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şlevsel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayalı kanıt sistemlerinin temellerini attı.

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

Binius protokolünde, sanal polinomların yapımı ve işlenmesi anahtar 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 anahtar yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki bitişik konumların daha küçük öğelerini daha büyük öğeler halinde paketleyerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan blok işlemleri hedef alır ve bunları gruplar.