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 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ı üzerinde kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verilerin genişletilmesi sırasında birçok ek fazlalık değeri, orijinal değer oldukça küçük olsa bile tüm alanı kaplayacaktır. Bu sorunu çözmek için alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

1. nesil STARK'ların kodlama bit genişliği 252 bit, 2. nesil STARK'ların kodlama bit genişliği 64 bit ve 3. nesil STARK'ların 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 karşılık, ikili alan doğrudan bitlere işlem yapmaya izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı içermez, yani 4. nesil STARK'lar.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalarla karşılaştırıldığında, ikili alan araştırması 1980'li yıllara kadar uzanmaktadır. Günümüzde ikili alanlar kriptolojide 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 F28 alanına dayanan ve SHA-3 finaline katılan Grøstl hash fonksiyonu, rekürsif kullanıma oldukça uygun bir hash algoritmasıdır.

Küçük bir alan kullanıldığında, genişletme işlemleri güvenliğin sağlanması 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ğımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli polinomların genişletme alanına girmesine gerek yoktur, yalnızca temel alan altında işlem yaparak küçük alanda yüksek verimlilik sağlanı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 alanlara dayalı bir kanıt sistemi oluştururken, iki pratik sorun vardır: STARKs'da iz gösterimi hesaplanırken kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'da Merkle ağacı taahhüt edilirken, Reed-Solomon kodlaması yapılmalı ve kullanılan alan boyutu, kodlama genişletildikten sonra 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 ederek bunu gerçekleştirdi: İlk olarak, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart bir Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare olarak düşünülebilir ve bu kareye dayalı olarak Reed-Solomon genişlemesi yapılabilir. Bu yöntem, güvenliği sağlarken kodlama verimliliği 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 Teorik Polinom Etkileşimli Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin temelini oluşturarak, giriş olarak verilen hesaplama ilişkisini doğrulanabilir polinom denklemlerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşimde bulunarak, kanıtlayıcının aşamalı olarak polinom göndermesine olanak tanır ve böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca 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; 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şitliğinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araçla, kanıtlayıcı bir polinom taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonucunu doğrulayabilirken, polinomun diğer bilgilerini gizler. Yaygın polinom taahhüt şemaları arasında KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) ve Brakedown gibi örnekler 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çerek ve uygun bir sonlu alan veya eliptik eğri ile birleştirerek, farklı özelliklere sahip kanıt sistemleri oluşturabilirsiniz. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi olup, Pasta eğrisi üzerine kurulmuştur. 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'nin birleştirilmesiyle 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 uyumlu olmalıdır, 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 olmaksızın şeffaflık sağlaması, özyinelemeli kanıtları veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknolojiyi kapsamaktadır. İlk olarak, kule şeklindeki ikili alanlar (towers of binary fields) temelinde aritmetik, hesaplamalarının temelini oluşturmakta ve 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, 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ü bir güvenlik sağlayan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesini ve genellikle büyük alanlarla ilişkili olan masrafları azaltmasını sağlayan küçük alan çokpolinom taahhüt sistemi (Small-Field PCS) kullanmaktadır.

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

Kule ikili alanı, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir öneme sahiptir ve bu, iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetikleştirme. İkili alanlar, doğası gereği yüksek verimli aritmetik işlemleri destekler ve bu da onları performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, aritmetik işlemlerin ikili alanda gerçekleştirildiği durumlarda kompakt ve kolayca doğrulanabilir cebirsel biçimlerde ifade edilmesini sağlayan basitleştirilmiş bir aritmetikleştirme sürecini destekler. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alan içindeki 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 eşlenebilir. Bu, asal alanlardan farklıdır; asal alan belirli bir bit sayısı içinde 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 alan öğesi ile eşleşmezken, ikili alan bu birbiriyle 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 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ıldığı gibi), Montgomery azaltması (POLYVAL'de kullanıldığı gibi) ve yinelemeli azaltma (Tower gibi) bulunmaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı 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ü bu (X + Y )2 = X2 + Y 2'nin sadeleştirilmiş kuralına uyar.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: Bu dize, ikili alanın bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir unsur olarak görülebilir veya iki 64 bitlik kule alanı unsuru, dört 32 bitlik kule alanı unsuru, 16 adet 8 bitlik kule alanı unsuru veya 128 adet F2 alanı unsuru olarak yorumlanabilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile sağlanır; bu, çok ilginç ve yararlı bir özelliktir. Ayrıca, küçük alan unsurları daha büyük alan unsurlarına ek bir hesaplama yükü olmaksızın 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" makalesi, n bitlik kule biçimli 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: 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 giriş x'in, devre hesaplama ilişkisi C(x,ω)=0'ı sağlayıp sağlamadığını doğrulamak için, devrenin doğru çalıştığından emin olmak.

2. PermutationCheck: İki çok değişkenli polinom f ve g'nin Bool hiper küpündeki değerlerinin yer değiştirme 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ğerlendirmesinin verilen arama tablosunda olup olmadığını doğrular, 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ş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: Boolean hiperkübünde akıllı çok terimli polinomun, belirli bir beyan edilen değere eşit olup olmadığını kontrol eder ∏x∈Hµ f(x) = s, polinom çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli çok terimli ifadenin Boolean hiperküp üzerindeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, çok terimli ifadenin 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ğerle ∑x∈Hµ f(x) = s olup olmadığını kontrol eder. Ç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 birden fazla toplam doğrulama örneğinin 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 çok terimli polinomun değerlendirilmesinin doğruluğunu doğrulamak için protokol verimliliğini artırır.

Binius ile 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ü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 çözümü: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiper küp üzerindeki sıfır olmayan durumu hakkında kesin bir yargıya varılamamasına neden oldu; Binius bu sorunu 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şletmeye izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu işlevselliğ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şlemesine olanak tanır.

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ğrulama işlemlerinde daha güçlü işlevsellik sağladı. Bu geliş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 çok satırlı kaydırma argümanı------boolean hiper küp için uygundur

Binius protokolünde, sanal çok terimlerin yapılandırılması ve işlenmesi anahtar teknolojilerden biridir ve giriş tutamacı veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturma ve işleme yeteneğine sahiptir. İşte iki anahtar 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ı gruplar.