Binius STARK prensibinin analizi ve optimizasyon düşüncesi

1 Giriş

Eliptik eğri tabanlı SNARK'ların aksine, STARK'lar hash tabanlı SNARK'lar olarak düşünülebilir. STARK'ların mevcut verimsizliğinin ana nedenlerinden biri, gerçek programdaki değerlerin çoğunun, for döngülerindeki indeksler, doğru ve yanlış değerler, sayaçlar vb. gibi küçük olmasıdır. Bununla birlikte, Merkle ağacı tabanlı kanıtların güvenliğini sağlamak için, veriler Reed-Solomon kodlaması ile genişletildiğinde, orijinal değerlerin kendileri çok küçük olsa bile, birçok ek gereksiz değer tüm alanı kaplar. Bu sorunu çözmek için, etki alanının boyutunu küçültmek önemli bir strateji haline gelir.

Tablo 1'de gösterildiği gibi, birinci nesil STARK'lar 252 bit, ikinci nesil STARK'lar 64 bit ve üçüncü nesil STARK'lar 32 bittir. Buna karşılık, ikili alan doğrudan bit hizalama işlemlerine izin verir ve alan israfı olmadan kodlamada kompakt ve verimlidir, yani 4. nesil STARK'lar.

Tablo 1: STARK'ların Evrim Yolları

| Özellik | 1. nesil STARK'lar | 2. nesil STARK'lar | 3. nesil STARK'lar | 4. nesil STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Kod bit genişliği | 252bit | 64 bit | 32 bit | 1 bit | | Temsilcilik Sistemi | StarkWare | Plonky2 | Bebek Ayı | Binius |

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 alanlar kriptografide yaygın olarak kullanılmaktadır, tipik örnekler arasında:

• F28 alan adlarına dayalı Gelişmiş Şifreleme Standardı (AES);

• F2128 etki alanına dayalı Galois mesaj kimlik doğrulama kodu (GMAC);

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

• Orijinal FRI ve zk-STARK protokollerinin yanı sıra SHA-3 finalistine ulaşan Grøstl hash fonksiyonu, F28 alanını temel alır ve özyineleme için çok uygun bir hash algoritmasıdır.

Daha küçük etki alanları kullanırken, güvenliği sağlamak için etki alanı işlemlerini genişletmek giderek daha önemli hale gelir. Öte yandan, Binius tarafından kullanılan ikili etki alanının, güvenliğini ve gerçek kullanılabilirliğini sağlamak için tamamen etki alanı genişletmesine dayanması gerekir. Prover hesaplamalarında yer alan polinomların çoğunun genişletilmiş alana girmesi gerekmez, ancak yalnızca temel etki alanı altında çalışması gerekir, böylece küçük alanlarda yüksek verimlilik elde edilir. Bununla birlikte, gerekli güvenliği sağlamak için rastgele nokta kontrolleri ve FRI hesaplamalarının yine de daha büyük bir genişletme alanında delinmesi gerekir.

İkili etki alanlarına dayalı bir kanıt sistemi oluştururken, iki pratik sorun vardır: STARK'larda iz gösterimini hesaplarken, kullanılan etki alanı boyutu polinomun sırasından daha büyük olmalıdır; STARK'larda Merkle ağacı vaat edildiğinde, Reed-Solomon'da kodlanması gerekir ve kullanılan etki alanının boyutu, kodlama uzantısının boyutundan daha büyük olmalıdır.

Binius, bu iki problemi ayrı ayrı ele alan ve bunu aynı verileri iki farklı şekilde temsil ederek yapan yenilikçi bir çözüm önermektedir: birincisi, tek değişkenli polinomlar yerine çok değişkenli (özellikle, çok doğrusal) polinomlar kullanmak ve tüm hesaplama yörüngesini "hiperküpler" üzerindeki değeriyle temsil etmek; İkinci olarak, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARK'lar gibi standart Reed-Solomon uzantısını yapmak mümkün değildir, ancak hiperküp, Reed-Solomon uzantısına dayalı bir kare olarak ele alınabilir. Bu yöntem, güvenliği sağlarken kodlama verimliliğini ve bilgi işlem performansını büyük ölçüde artırır.

2 Prensip Analizi

Mevcut SNARK sistemlerinin çoğunun yapısı genellikle aşağıdaki iki bölümden oluşur:

• Bilgi-Teorik Polinom Etkileşimli Oracle Kanıtı (PIOP), girdilerin hesaplama ilişkilerini doğrulanabilir polinom denklemlerine dönüştürerek kanıt sisteminin çekirdeği olarak IOP'yi :P. Farklı PIOP protokolleri, kanıtlayıcının doğrulayıcı ile etkileşime girerek polinomları adım adım göndermesine izin vererek, doğrulayıcının az sayıda polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olduğunu doğrulamasına olanak tanır. Mevcut PIOP protokolleri, tümü polinom ifadelerini farklı şekilde ele alan ve tüm SNARK sisteminin performansını ve verimliliğini etkileyen PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP'u içerir.

• Polinom Bağlılık Şeması (PCS): Polinom Bağlılık Şeması, PIOP tarafından oluşturulan polinom denkleminin doğru olup olmadığını kanıtlamak için kullanılır. PCS, bir kanıtlayıcının belirli bir polinomu taahhüt edebileceği ve daha sonra polinom hakkındaki diğer bilgileri gizlerken bu polinomun değerlendirme sonuçlarını doğrulayabileceği bir şifreleme aracıdır. Yaygın polinom taahhüt şemaları arasında KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) ve Brakedown bulunur. Farklı bilgisayarların farklı performans, güvenlik ve uygulama senaryoları vardır.

Belirli gereksinimlere 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şturulabilir. Örneğin:

• Halo2: Bulletproofs PCS ile birleştirilmiş PLONK PIOP tarafından desteklenmektedir ve Makarna eğrilerine dayanmaktadır. Halo2, ölçeklenebilirlik göz önünde bulundurularak ve ZCash protokolünden güvenilir kurulumu kaldırarak tasarlanmıştır.

• Plonky2: PLONK PIOP'u FRI PCS ile birleştirir ve Goldilocks etki alanını temel alır. Plonky2 verimli özyineleme içindir. Bu sistemleri tasarlarken, seçilen PIOP ve PCS, sistemin doğruluğunu, performansını ve güvenliğini sağlamak için kullanılan sonlu alan veya eliptik eğri ile eşleşmelidir. Bu kombinasyonların seçimi yalnızca SNARK'ların kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir ayarlara ihtiyaç duymadan şeffaflık sağlayıp sağlayamayacağını ve özyinelemeli kanıtlar veya toplu kanıtlar gibi genişletilmiş işlevleri destekleyip destekleyemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + İkili Etki Alanı. Spesifik olarak Binius, verimliliğini ve güvenliğini sağlamak için beş temel teknoloji içerir. Her şeyden önce, ikili alanların kulelerine dayanan aritmetik, ikili alanlarda basitleştirilmiş işlemleri gerçekleştirebilen hesaplamalarının temelini oluşturur. İkinci olarak, etkileşimli Oracle Proof Protocol'de (PIOP) Binius, değişkenler ve permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlamak için HyperPlonk ürününü ve permütasyon kontrolünü uyarladı. Üçüncü olarak, protokol, küçük bir alanda çok doğrusal ilişkiyi doğrulamanın verimliliğini optimize etmek için yeni bir çok doğrusal kaydırma argümanı sunar. Dördüncüsü, Binius, arama mekanizması için esneklik ve güçlü güvenlik sağlayan Lasso arama argümanının geliştirilmiş bir sürümünü benimser. Son olarak, protokol, ikili etki alanında verimli bir kanıt sistemi uygulamasına ve tipik olarak büyük etki alanlarıyla ilişkili ek yükü azaltmasına olanak tanıyan bir küçük alan polinom taahhüt şeması (Küçük Alan PCS) kullanır.

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

Kule ikili alanı, temel olarak iki yöne atfedilen hızlı doğrulanabilir hesaplamanın anahtarıdır: verimli hesaplama ve verimli aritmetikleştirme. İkili etki alanları, doğası gereği yüksek verimli aritmetik işlemleri destekler ve bu da onları performans gereksinimlerine duyarlı şifreleme uygulamaları için ideal hale getirir. Ek olarak, ikili alan yapısı basitleştirilmiş bir aritmetik işlemi destekler, yani ikili alan üzerinde gerçekleştirilen işlemler kompakt ve kolayca doğrulanabilir bir cebirsel formda temsil edilebilir. Bu özellikler, kule yapıları aracılığıyla hiyerarşik yapısından tam olarak yararlanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir

burada "kanonik", ikili etki alanındaki bir öğenin benzersiz ve doğrudan bir temsilini ifade eder. Örneğin, en temel ikili etki alanı F2'de, herhangi bir k-bit dizesi doğrudan bir k-bit ikili etki alanı öğesine eşlenebilir. Bu, verilen konum içinde böyle bir kanonik temsil sağlayamayan asal sayı alanının tersidir. 32 bitlik bir asal sayı alanı 32 bitlik bir sistemde bulunabilse de, her 32 bitlik dize benzersiz bir şekilde bir etki alanı öğesine karşılık gelmez ve ikili alanlar bu bire bir eşlemenin rahatlığına sahiptir. Asal alan Fp'de, yaygın 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 (örneğin, AES'de kullanılır), Montgomery indirgemesi (örneğin, POLYVAL'de kullanılır) ve özyinelemeli indirgeme (örneğin, Tower) bulunur. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" (Asal Alan ve İkili Alan ECC-Donanım Uygulamalarının Tasarım Uzayını Keşfetmek) başlıklı makale, ikili alanın hem toplama hem de çarpmada taşımayı tanıtmasına gerek olmadığını ve ikili alanın kare işleminin çok verimli olduğunu çünkü (X + Y'yi takip ettiğini belirtiyor )2 = X2 + Y 2 olur.

! Bitlayer Araştırması: Binius STARK'ın Prensip Analizi ve Optimizasyon Düşüncesi

Şekil 1'de gösterildiği gibi, 128 bitlik bir dize: bu dize, ikili etki alanı bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik bir ikili etki alanında benzersiz bir öğe olarak görülebilir veya iki adet 64 bitlik kule öğesi, dört adet 32 bitlik kule öğesi, 16 adet 8 bitlik kule öğesi veya 128 F2 etki alanı öğesi olarak çözümlenebilir. Bu gösterimin esnekliği herhangi bir hesaplama yükü gerektirmez, sadece çok ilginç ve kullanışlı bir özellik olan bitsel dizelerin bir tür dökümü gerektirir. Aynı zamanda, küçük etki alanı öğeleri, ek hesaplama yükü olmadan daha büyük etki alanı öğelerine paketlenebilir. Binius protokolü, hesaplama verimliliğini artırmak için bu özellikten yararlanır. Ek olarak, "On Efficient Inversion in Tower Fields of Characteristic Two" başlıklı makale, m-bit alt alanlara ayrıştırılabilen bir n-bit kule ikili alanında çarpma, kare alma ve ters çevirme işlemlerinin hesaplama karmaşıklığını araştırıyor.

2.2 PIOP: İkili alanlar için uyarlanmış HyperPlonk Çarpımı ve Permütasyon Kontrolü ------

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: Devrenin doğru çalışmasını sağlamak için gizli tanığın ω ve genel giriş x'in devre çalışma ilişkisini C(x ω)=0 karşılayıp karşılamadığını doğrulayın.

2. Permütasyon Kontrolü: Boolean hiperküpü üzerindeki iki çok değişkenli polinom f ve g'nin değerlendirme sonuçlarının permütasyon bağıntıları olduğunu doğrulayın f(x) = f(π(x)) polinom değişkenleri arasındaki düzenlemede tutarlılığı sağlamaktır.

3. Arama Kontrolü: Polinomun belirli bir arama tablosunda, yani f(Bμ) ⊆ T(Bμ) olarak değerlendirildiğini doğrulayın ve belirli değerlerin belirtilen aralıkta olduğundan emin olun.

4. MultisetCheck: İki çok değişkenli kümenin eşit olup olmadığını kontrol edin, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H.

5. ProductCheck: Polinom çarpımının doğruluğunu sağlamak için bir Boolean hiperküpü üzerindeki rasyonel bir polinomun değerlendirmesinin beyan edilen bir değere ∏x∈Hμ f(x) = s eşit olup olmadığını kontrol eder.

6. ZeroCheck: Polinomun sıfır dağılımını sağlamak için Boolean hiperküpü∏x∈Hμ f(x) = 0,∀x ∈ Bμ üzerinde herhangi bir noktada çok değişkenli bir polinomun sıfır olduğunu doğrulayın.

7. SumCheck: Çok değişkenli polinomun toplam değerinin beyan edilen değer olup olmadığını kontrol eder ∑x∈Hμ f(x) = s. Çok değişkenli polinomların değerlendirme problemini tek değişkenli polinom değerlendirmesine dönüştürerek, doğrulayıcının hesaplama karmaşıklığı azaltılır. Buna ek olarak, SumCheck ayrıca rastgele sayılar tanıtarak, birden çok toplam kontrol örneğinin toplu işlenmesini sağlamak için doğrusal kombinasyonlar oluşturarak toplu işlemeye de izin verir.

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

Binius ve HyperPlonk arasında protokol tasarımı açısından birçok benzerlik olmasına rağmen, Binius aşağıdaki üç açıdan iyileştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'ta ProductCheck, hiperküpün her yerinde U paydasının sıfırdan farklı olmasını ve ürünün belirli bir değere eşit olmasını gerektirir; Binius, bu değeri 1'e özelleştirerek bu kontrol sürecini basitleştirir ve böylece hesaplama karmaşıklığını azaltır.

• Sıfırı bölme probleminin ele alınması: HyperPlonk, sıfırı bölme durumunu yeterince ele alamaz, bu da hiperküp üzerinde sıfır olmayan U problemini ileri sürememesine neden olur; Binius bunu doğru bir şekilde ele alır ve Binius'un ProductCheck'i, payda sıfır olduğunda bile işlemeye devam eder ve rastgele ürün değerlerine genellemelere izin verir.

• Permütasyon Kontrolü: Bu özellik HyperPlonk'ta mevcut değildir; Binius, birden çok sütun arasında Permütasyon Kontrolünü destekler, bu da Binius'un daha karmaşık polinom permütasyonlarını işlemesine olanak tanır.

Bu nedenle, mevcut PIOPSumCheck mekanizmasının iyileştirilmesi yoluyla Binius, özellikle daha karmaşık çok değişkenli polinom doğrulaması ile uğraşırken protokolün esnekliğini ve verimliliğini artırır ve daha güçlü işlevsel destek sağlar. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları ele almakla kalmaz, aynı zamanda gelecek için ikili tabanlı bir temel sağlar