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

1 Giriş

STARK'ların düşük verimliliğinin ana 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ğacı kanıtlarının güvenliğini sağlamak için, Reed-Solomon kodlaması kullanılarak verileri genişletirken, birçok ek gereksiz değer tüm alanı kaplayacaktır, bu da orijinal değerin kendisinin çok küçük olmasına rağmen. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.

Tablo 1'de gösterildiği gibi, 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ı bulunmaktadır. Buna karşın, ikili alan doğrudan bitler üzerinde işlem yapılmasına izin verir, kodlama sıkı ve verimli olup rastgele israf alanı içermez, yani 4. nesil STARKs.

Tablo 1: STARKs türev yolları

| Sıra | Genişlik | Açıklama | |------|------|------| | 1. Nesil | 252bit | Büyük asal alanına dayalı | | 2. Nesil | 64bit | Goldilocks Alanı | | 3. Nesil | 32bit | Babybear Alanı | | 4. Nesil | 1bit | İkili Alan |

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan sınırlı alan araştırmalarına kıyasla, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alanlar kriptografide geniş bir şekilde 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 tekrar eden hash algoritmaları için oldukça uygun bir türdü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ğımlıdır. Çoğu Prover hesaplamasında yer alan polinomlar genişletmeye girmek zorunda kalmadan, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. 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 inşa ederken, iki pratik sorun vardır: STARKs'ta izin (trace) temsilini hesaplamak için kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüt edilmesi sırasında, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alanın boyutu, kodlama genişletmesinden sonra 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 ifade ederek bunu gerçekleştirdi: Öncelikle, tek değişkenli polinom yerine çok değişkenli ( çoklu ) polinom kullanarak, "hiperküp" ( üzerindeki değerleri ile tüm hesaplama izini temsil etti; ikincisi, hiperküpün her boyutunun uzunluğunun 2 olması nedeniyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp bir kare ) olarak düşünülebilir 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ı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 Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin çekirdeği olarak, girilen 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 aşamalı olarak polinom göndermesine izin verir ve bu sayede doğrulayıcı, hesaplamanın doğru olup olmadığını kontrol etmek 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 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 denkleminin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizli tutar. 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ç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 ve Pasta eğrisi temel alınarak oluşturulmuştur. Halo2 tasarımında ö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 bir kombinasyonunu kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir özyineleme sağlamak amacıyla 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 etkileyerek, sistemin güvenilir bir kurulum olmadan şeffaflık sağlamasını ve özyinelemeli kanıtlar veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip destekleyemeyeceğini belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Spesifik olarak, Binius'ın verimliliğini ve güvenliğini sağlamak için beş anahtar teknolojiyi içerir. İlk olarak, kule şeklindeki ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturur ve ikili alan içinde basitleştirilmiş hesaplamaları gerçekleştirebilir. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlayarak, değişkenler ile yer değiştirmeleri arasındaki güvenli ve verimli tutarlılık kontrolünü sağlar. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilere doğrulama verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı getirir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını benimsemiştir. 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 maliyetleri azaltan küçük alan çoklu polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alan: binary alanların kulelerine dayalı aritmetik

Kule ikili alanı, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir unsurdur, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekler ve bu da onu performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı basitleştirilmiş aritmetika süreçlerini destekler; yani ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir. 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 alanda bir öğenin benzersiz ve doğrudan temsil 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 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 yer alabilir, ancak her 32 bitlik dize benzersiz bir alan öğesine karşılık gelmeyebilir; oysa ikili alan bu bir-bir eşleme kolaylığına sahiptir. Asal alan Fp'de, yaygın indirgeme yöntemleri arasında Barrett indirgeme, Montgomery indirgeme ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlara yönelik özel indirgeme yöntemleri yer alır. İkili alan F2k'da, yaygın indirgeme yöntemleri arasında AES'de kullanılan özel indirgeme ), POLYVAL'de kullanılan Montgomery indirgeme ### ve Tower ( gibi rekürsif indirgeme ) bulunur. "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 işlem (X + Y )2 = X2 + Y 2 gibi sadeleştirilmiş bir kuralı izler.

Ş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 alanda benzersiz bir eleman olarak görülebilir ya da 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 tip dönüşümünü (typecast) gerektirir, bu da oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan elemanları daha büyük alan elemanlarına ek bir hesaplama maliyeti olmadan 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ı makale, n bitlik kule benzeri ikili alanda ( 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ümelerin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunlardır:

1. GateCheck: Gizli tanı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ığını sağlamaktadır.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boole hiper küpündeki değerlendirme 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 için.

3. LookupCheck: Verilen bir arama tablosunda çok terimli bir polinomun değerlendirmesinin doğrulanması, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olmak.

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

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ğrulama ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, polinomun sıfır noktalarının dağılımını güvence altına almak için.

7. SumCheck: Çok değişkenli bir polinomun toplamının, beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol eder. Çok değişkenli polinomun değerlendirilmesi sorununu, tek değişkenli polinom değerlendirmesi problemine dönüştürerek, doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar kullanarak, birden fazla toplam doğrulama örneğinin topluca işlenmesini sağlamak için lineer kombinasyonlar oluşturma imkanı sunar.

8. BatchCheck: SumCheck'e dayanarak, birden fazla değişkenli çok terimli polinom değerlendirmelerinin doğruluğunu doğrulamak için, protokol verimliliğini artırmak.

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ı gerekir; 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 sorunlarının çözümü: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı ve U'nun hiperküpte sıfırdan farklı olup olmadığını kesin olarak belirleyemedi; 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 yayılmasına izin veriyor.

• Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu işlevi desteklemiyor; 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 polinom doğrulama işlemlerinde daha güçlü bir işlevsellik sağladı. Bu iyileş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