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

1 Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri şudur: Gerçek programlardaki çoğu sayı oldukça küçüktür; örneğin, döngülerdeki indeksler, doğru/yanlış değerler, sayaçlar vb. Ancak, Merkle ağacına dayalı kanıtların güvenliğini sağlamak için, Reed-Solomon kodlaması kullanarak verileri genişletirken, birçok ek fazla değer tüm alanı kaplayacaktır; bu durum, orijinal değerler kendileri çok küçük olsa bile geçerlidir. Bu sorunu çözmek için, alanın boyutunu azaltmak ana 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 miktarda israf alanı içermektedir. Buna karşılık, ikili alan doğrudan bitler üzerinde işlem yapmaya olanak tanır, kodlama kompakt ve verimli olup, herhangi bir israf alanı içermez, 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. 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 dayanmaktadır;

• QR kodu, F28 tabanlı Reed-Solomon kodlaması kullanarak;

• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve rekürsif kullanım için son derece uygun bir hash algoritmasıdır.

Küçük bir alan kullanıldığında, alan genişletme işlemi 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 çok terimli ifadeler alan genişletmesine girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gereken güvenliği sağlamak için daha büyük bir alan genişletmesine derinlemesine inmek zorundadır.

İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin temsilini hesaplarken kullanılan alan büyüklüğü, 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 büyüklüğü kodlama genişletildikten sonra büyüklüğünden büyük olmalıdır.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı verileri iki farklı şekilde temsil ederek bunu gerçekleştirdi: İlk olarak, çok değişkenli (, tam olarak çok lineer ) polinomunu tek değişkenli polinom yerine kullanarak, "hiperküplerde" ( alınan değerleri kullanarak tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp bir kare ) olarak düşünülebilir ve bu kare temel alınarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliğin sağlanmasını garanti ederken, kodlama verimliliği ve hesaplama performansını büyük ölçüde artırmaktadır.

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 Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin temelini oluşturur ve giriş hesap ilişkisini doğrulanabilir polinom eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim sağlayarak, kanıtlayıcının polinomları aşamalı olarak göndermesine olanak tanır ve böylece doğrulayıcı, yalnızca birkaç polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır ve bunların her biri polinom ifadelerini işleme biçimi açısından farklılık gösterir, bu da tüm SNARK sisteminin performansı 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; bununla, kanıtlayıcı belirli bir polinom taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını 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 seçenekler bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama senaryolarına sahiptir.

Spesifik 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, tasarlanırken ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanı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ğlanabilir. Bu kombinasyonların seçimi, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum olmadan ş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 içermektedir. İlk olarak, kuleler (towers of binary fields) temelinde bulunan aritmetik, hesaplamalarının temeli olarak işlev görmekte ve ikili alan içerisinde basitleştirilmiş işlemleri gerçekleştirmektedir. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP)'unda, HyperPlonk çarpım ve yer değiştirme kontrollerini uyarlayarak, değişkenler ve bunların yer değiştirmeleri arasındaki güvenli ve verimli tutarlılık kontrolünü 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 alan üzerinde verimli bir kanıt sistemi gerçekleştirmesini sağlayan ve genellikle büyük alanlarla ilişkili olan giderleri azaltan küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alanlar: binary alanların kuleleri üzerine yapılan aritmetik

Kule ikili alanı, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynamaktadır; bunun başlıca iki nedeni vardır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekleyerek performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline gelmektedir. Ayrıca, ikili alan yapısı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebileceği basitleştirilmiş bir aritmetik süreci desteklemektedir. Bu özellikler, kule yapısı aracılığıyla hiyerarşik özelliklerinden tam olarak yararlanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirmektedir.

"canonical" terimi, ikili alan içerisindeki elemanların 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 elemanına 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 elemanına karşılık gelemez; ikili alan ise bu tür bir birebir eşleşmenin kolaylığını sunar. Asal alan Fp'de yaygın olarak kullanılan azaltma yöntemleri Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel azaltma yöntemleridir. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında AES'te kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower( gibi özyinelemeli azaltmalar ) yer alı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 oldukça verimli olduğunu belirtmektedir; çünkü bu, (X + Y )2 = X2 + Y 2 gibi basitleştirilmiş kurallara 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 düşünü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 yorumlanabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümünü (typecast) gerektirir, bu da oldukça ilginç ve kullanışlı bir özelliktir. Aynı zamanda, 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" makalesi, n bitlik kule ikili alanında ( m bitlik alt alan ) için çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

( 2.2 PIOP: Uyarlama 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üme 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 C)x,ω(=0 devre hesaplama ilişkisini karşılayıp karşılamadığını doğrulayarak devrenin doğru çalıştığından emin olun.

2. PermutationCheck: iki çok değişkenli çok terimli f ve g'nin Boolean hiperküpteki değer sonuçlarının bir permütasyon ilişkisi olup olmadığını doğrulamak için f)x### = f(π)x(), çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak amacıyla.

3. LookupCheck: Verilen arama tablosunda çok terimli bir fonksiyonun değerinin doğrulanması yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olmasını sağlamak.

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: Mantıksal hiper küp üzerindeki rasyonel çok terimli polinomun belirli bir beyan edilen değere ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etme, polinomun çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Bool hiper küpündeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏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 etme ∑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ının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar getirerek birden fazla toplam doğrulama örneğini topluca işleme imkan tanır.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinomun 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'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 kontrol sürecini basitleştirmiş ve hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme probleminin yönetimi: HyperPlonk sıfıra bölme durumunu yeterince yönetemedi, bu da U'nun hiperküpte sıfırdan farklı olup olmadığını kesin olarak belirlemeyi engelledi; Binius bu durumu doğru bir şekilde ele aldı, sıfır paydası durumunda bile Binius'un ProductCheck'i işlemeye devam edebiliyor, her türlü çarpan değerine genişletilmesine izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekliyor, bu da Binius'un daha karmaşık çok terimli sıralama durumlarını işleyebilmesini sağlıyor.

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ı işlerken daha güçlü işlevsel destek sağladı. Bu geliştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan temelli 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 çok terimlerin oluşturulması ve işlenmesi temel tekniklerden biridir ve girdi işleyicilerinden veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde üretip işlemeyi sağlar. İşte iki ana yöntem:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu pozisyonlardaki daha küçük öğeleri daha büyük öğeler haline getirerek işlemleri optimize eder. Pack operatörü, boyutu 2κ olan blok işlemleri için geçerlidir ve bunları yüksek boyutlu alanlarda birleştirir.