Binius STARKs İlkeleri Analizi ve İyileştirme 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, gerçeklik değerleri, sayaçlar vb. Ancak, Merkle ağaçlarına dayalı 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 tüm alanı kaplayacaktır, hatta orijinal değerler çok küçük olsa bile. Bu sorunu çözmek için alanın boyutunu küçültmek ana strateji haline gelmiştir.

Tablo 1'de görüldüğü 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 ise 32 bit'tir; ancak 32 bit kodlama bit genişliğinde hala büyük miktarda israf alanı bulunmaktadır. Buna karşılık, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama sıkışık ve verimli olup herhangi bir israf alanı olmadan gerçekleşir, yani 4. nesil STARKs.

Tablo 1: STARKs türev yolu

| Cebir | Kodlama Genişliği | Örnek | |------|----------|------| | 1. nesil | 252bit | Ethereum STARKs | | 2. Nesil | 64bit | Plonky2 | | 3. Nesil | 32bit | BabyBear | | 4. Nesil | 1bit | Binius |

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlarla karşılaştırıldığında, ikili alan araştırmaları 1980'li yıllara kadar uzanmaktadır. Günümüzde, ikili alanlar kriptolojide 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 F28 alanına dayanan, rekürsif bir hash algoritması için son derece uygun olan Grøstl hash fonksiyonu, SHA-3 finaline girdi.

Küçük bir alan 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ğlıdır. Çoğu Prover hesaplamasında yer alan polinomların genişletme alanına girmesine gerek yoktur; yalnızca temel alanda 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 genişletme alanlarına derinlemesine inmelidir.

İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izin temsilini hesaplarken kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüt edilirken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alanın boyutu, kodlamanın genişletilmiş 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: İlk olarak, tek değişkenli polinom yerine çok değişkenli (, özellikle çoklu lineer ) polinom kullanarak, "hiperküpler" ( üzerindeki değerleri ile tüm hesaplama izini temsil etti; İkincisi, hiperküpün her boyutunun uzunluğunun 2 olması nedeniyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp 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 temelinde, girişteki hesaplama ilişkisini doğrulanabilir polinom eşitliklerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcıyla etkileşim yoluyla, kanıtlayıcının aşamalı olarak polinom göndermesine izin verir, böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için az sayıda polinom değerlendirme sonucunu sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP bulunmaktadır ve bunların her biri polinom ifadelerinin işlenme şeklinde farklılık gösterir, 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çerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır, bununla birlikte, kanıtlayıcı bir polinomu 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 kullanım senaryolarına sahiptir.

Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler seçerek uygun sınırlı alan veya eliptik eğri ile birleştirerek farklı özelliklere sahip kanıt sistemleri inşa edilebilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ile Pasta eğrisi üzerine inşa edilmiştir. Halo2 tasarımı, ölçeklenebilirliğe odaklanmış ve ZCash protokolündeki trusted setup'ı kaldırmayı hedeflemiştir.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleştirilmesi ve Goldilocks alanına dayanarak geliştirilmiştir. 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, yalnızca SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar gerektirmeden ş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. Daha spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş temel teknoloji içermektedir. İlk olarak, kule ikili alanların (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturmakta ve ikili alanda basitleştirilmiş işlemler gerçekleştirmektedir. İ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 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 doğrusal ilişkilerin verimliliğini optimize eden yeni bir çoklu doğrusal kaydırma kanıtı tanıtmaktadır. 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, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirmesini sağlamak ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltmak için küçük alan polinom taahhüt planı (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alan: binary alanlarındaki kuleler temelinde aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik öneme sahiptir ve bu iki ana sebepten kaynaklanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekler ve bu, performansa duyarlı kriptografik uygulamalar için ideal bir seçenek haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş bir aritmetik süreç destekler; yani ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel bir biçimde temsil edilebilir. Bu özellikler, kule yapısını tam olarak kullanarak hiyerarşik özelliklerinden yararlanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical", ikili alan içindeki 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 bit sayısı içinde bu tür bir standart gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize benzersiz bir alan elemanına karşılık gelemeyebilir, oysa ikili alan bu bir- bir eşleme kolaylığını sunar. Asal alan Fp'de, yaygın olan 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 indirgeme yöntemleri arasında AES'de kullanılan özel indirgeme ), POLYVAL'de kullanılan Montgomery indirgemesi ### ve Tower( gibi tekrar eden indirgeme ) bulunmaktadır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetme" 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ü bu işlem (X + Y )2 = X2 + Y 2'nin sadeleştirilmiş kuralını 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 alandaki benzersiz bir öğe olarak veya iki 64 bitlik kule alan öğesi, dört 32 bitlik kule alan öğesi, 16 adet 8 bitlik kule alan öğesi veya 128 adet F2 alan öğesi olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümü (typecast) ile gerçekleştirilir; bu, oldukça ilginç ve faydalı bir özelliktir. Ayrıca, küçük alan öğeleri, ek bir hesaplama maliyeti olmadan daha büyük alan öğeleri olarak paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özelliği kullanır. Ayrıca, 'On Efficient Inversion in Tower Fields of Characteristic Two' başlıklı makale, n bitlik kule ikili alanında ('in m bitlik alt alan ) olarak çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

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

Binius protokolündeki PIOP tasarımı HyperPlonk'tan esinlenmiştir ve çok terimlerin 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ık ω ve açık girdi x'in, devre hesaplama ilişkisi C)x,ω(=0'ı karşılayıp karşılamadığını doğrulamak için, devrenin doğru çalıştığından emin olmak.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiperküpteki değerlerinin permütasyon ilişkisi olup olmadığını doğrulama f)x### = f(π)x(), böylece çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak.

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

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: Mantıksal hiperküpteki rasyonel çok terimli polinomun değerinin belirtilen bir değere eşit olup olmadığını kontrol etmek ∏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 polinomun Boolean hiperküpündeki herhangi bir noktada sıfır olup olmadığını doğrulamak için ∏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 polinomların toplam değerinin beyan edilen değerle eşleşip eşleşmediğini kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomların 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 tanıtarak, birden fazla toplam kontrol örneğinin topluca işlenmesini sağlayan lineer kombinasyonlar oluşturma imkanı da sunar.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli çok terimli 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 hiper küp üzerinde her zaman 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 işlenmesi: HyperPlonk, sıfıra bölme durumunu yeterince işleyemedi, bu da U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığına dair kesin bir yargıda bulunulamamasına neden oldu; 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 özelliği sunmamaktadır; Binius birden fazla sütun arasında Permutasyon Kontrolü yapmayı desteklemektedir, bu sayede Binius daha karmaşık çok terimli sıralama durumlarını işleyebilmektedir.

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 çoktaneli doğrulama işlemlerinde daha güçlü işlevsellik sağladı. Bu iyileştirmeler sadece HyperPlonk'taki sınırlamaları çözmekle kalmayıp, aynı zamanda gelecekteki ikili alan tabanlı kanıt sistemleri için bir temel oluşturdu.

( 2.3 PIOP: yeni çoklu kaydırma argümanı------boolean hiper küpe uygundur

Binius protokolünde, sanal çoklu