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

1 Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri şudur: Gerçek uygulamalardaki çoğu sayısal değer oldukça küçüktür, örneğin for döngüsündeki indeksler, boolean değerler, sayaçlar vb. Ancak, Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında, birçok ek fazlalık değeri tüm alanı kaplar, oysaki orijinal değerler kendileri oldukça 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 genişliği hala büyük ölçüde israf alanı içermektedir. Buna karşılık, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimlidir ve herhangi 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. Günümüzde, ikili alan kriptografi alanında 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 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 çok uygundur.

Küçük alanlar kullanıldığında, genişletme işlemleri güvenliği sağlamak için giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliği ve pratik kullanılabilirliği sağlamak için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan polinomlar genişletmeye girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlamaktadır. 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 temelinde kanıt sistemi oluşturulurken, iki pratik sorun bulunmaktadır: STARKs'ta iz temsilini hesaplamak için kullanılan alan boyutu, birçok terimin derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekmekte ve kullanılan alan boyutu, kodlama genişletme sonrası boyutundan 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 etti: Öncelikle, çok değişkenli (özellikle çok lineer) bir polinom kullanarak tek değişkenli polinomun yerini alarak, "hiperküpler" üzerindeki değerleri ile tüm hesaplama izini temsil etti; İ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üşünülebilir ve bu kareye dayalı 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ırdı.

2 Prensip Analizi

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

• Bilgi Teorisi Polinom Etkileşimli Oracle İspatı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, bir kanıtlama sisteminin çekirdeği olarak, girişteki 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 adım adım polinom göndermesine izin vererek, doğrulayıcının yalnızca az sayıda polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulamasını sağlar. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme biçiminde farklılıklar göstererek, tüm SNARK sisteminin performansını ve verimliliğini etkilemektedir.

• 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; bu araç sayesinde, kanıtlayıcı bir polinomu taahhüt edebilir ve bu polinomun değerlendirme sonuçlarını daha sonra 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 gereksinimlere göre farklı PIOP ve PCS'ler seçilebilir ve uygun bir sonlu alan veya eliptik eğri ile birleştirilerek farklı özelliklere sahip kanıtlama sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi olup Pasta eğrisi üzerine inşa edilmiştir. 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'yi birleştirerek Goldilocks alanına dayanmaktadır. Plonky2, etkili bir yeniden yineleme sağlamak amacıyla tasarlanmıştır. Bu sistemleri tasarlarken, seçilen PIOP ve PCS'nin kullanılan sonlu alan veya eliptik eğri ile eşleşmesi gerekir, 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 yapılandırma olmaksızın şeffaflık sağlayıp sağlayamayacağını, yeniden kanıt veya toplu kanıt gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliği ve güvenliği sağlamak için beş ana teknolojiyi içermektedir. İlk olarak, kule biçimindeki ikili alanlar (towers of binary fields) üzerine kurulu aritmetik, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş işlemleri gerçekleştirebilir. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrolünü adapte ederek, 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ğrulama 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, ikili alanda verimli bir kanıt sistemi sağlamak ve genellikle büyük alanlarla ilişkili olan masrafları azaltmak için küçük alan çoklu polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

2.1 Sonlu Alanlar: binary fields'ün tower'larına dayalı aritmetik

Kule benzeri ikili alan, hızlı doğrulanabilir hesaplamalar gerçekleştirmek için kritik öneme sahiptir ve bu, iki nedene dayanmaktadır: verimli hesaplama ve verimli cebirsel yapı. İkili alan, temel olarak son derece verimli cebirsel işlemleri destekleyerek 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 doğrulanması kolay cebirsel biçimlerde temsil edilebilen basitleştirilmiş bir cebirsel süreç destekler. Bu özellikler, kule yapısını kullanarak hiyerarşik özelliklerinden tam olarak faydalanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alanda bir öğenin 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 alanlar belirli bir bit sayısında bu tür bir standart gösterim sunamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize benzersiz bir şekilde bir alan öğesi ile eşleşemez, oysa ikili alan bu birbiriyle eşleşme kolaylığını sağlar. Asal alan Fp'de yaygın olarak kullanılan indirgeme yöntemleri arasında Barrett indirgemesi, Montgomery indirgemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel indirgeme yöntemleri bulunur. İkili alan F2k'de yaygın olarak kullanılan indirgeme yöntemleri arasında özel indirgeme (AES'te kullanılan), Montgomery indirgemesi (POLYVAL'da kullanılan) ve yinelemeli indirgeme (Tower gibi) yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" 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 belirtmektedir, çünkü (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralına uyar.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dizi: Bu dizi, 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ı, on altı 8 bitlik kule alan elemanı veya 128 adet F2 alan elemanı olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, sadece bit dizisinin tür dönüşümüne (typecast) dayanmaktadır ve oldukça ilginç ve yararlı bir özelliktir. Ayrıca, küçük alan elemanları, ek bir hesaplama maliyeti olmadan daha büyük alan elemanları olarak paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özelliği kullanmaktadır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" adlı makale, n bitlik kule ikili alanında (m bitlik alt alanlara ayrılabilen) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

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

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

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

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

3. LookupCheck: Polinomun değerlendirilmesinin verilen arama tablosunda, yani f(Bµ) ⊆ T(Bµ), bazı değerlerin belirtilen aralıkta olduğunu doğrulayın.

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ığı sağlamak için.

5. ProductCheck: Mantıksal hiperküp üzerindeki bir polinomun, belirli bir beyan edilen 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 amacıyla.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole hiper küpü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, beyan edilen değer 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ı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek, birden fazla toplam doğrulama örneğini işlemek için lineer kombinasyonlar oluşturarak toplu işlem yapılmasına da olanak tanır.

8. BatchCheck: SumCheck'e dayalı olarak, çoklu çok değişkenli çok terimli polinom değerlemelerinin 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 geliştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in paydası U'nun hiperkü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 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 ele alamadı ve bu nedenle U'nun hiper küp üzerindeki sıfırdan farklı olup olmadığı konusunda kesin bir şey söylemek mümkün olmadı; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan bir payda durumunda 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'ta bu özellik yoktur; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli dizilim durumlarını işleyebilmesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasının geliştirilmesiyle 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 gelecekte ikili alanlara dayalı kanıt sistemleri için bir temel oluşturdu.

2.3 PIOP: Yeni çoklu kaydırma argümanı------Boolean hiper küp için uygundur

Binius protokolünde, sanal polinomların yapılandırılması ve işlenmesi temel tekniklerden 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 ana yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlarda bulunan daha küçük elemanları daha büyük elemanlar haline getirerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan blok işlemleri için tasarlanmıştır ve bunları