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

1 Giriş

STARKs'ın verimsizliğinin başlıca nedenlerinden biri, gerçek programlarda ç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ı tabanlı kanıtların güvenliğini sağlamak için, verileri genişletirken Reed-Solomon kodlaması kullanıldığında, birçok ek gereksiz değer tüm alanı kaplayacaktır, orijinal değer kendisi çok küçük olsa bile. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline geldi.

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 ise 32 bit'tir, ancak 32 bit kodlama bit genişliğinde hala büyük miktarda israf alanı bulunmaktadır. Karşılaştırıldığında, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı yoktur, yani 4. nesil STARKs.

Tablo 1: STARKs Türev Yolu

| Cebir | Kodlama Bit Genişliği | Temsil Sistemi | |------|----------|----------| | 1. nesil | 252bit | StarkWare |
| 2. Nesil | 64bit | Plonky2 | | 3. nesil | 32bit | BabyBear | | 4. Nesil | İkili Alan | 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 alan 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ı kullanır;

• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve tekrarlamalara son derece uygun bir hash algoritmasıdır.

Küçük alanlar kullanıldığında, alan genişletme işlemi güvenliği sağlamak için giderek daha önemli hale gelir. Binius'un kullandığı ikili alan tamamen güvenliği ve pratik kullanılabilirliği sağlamak için alan genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan polinomlar, alan genişletmesine girmek zorunda kalmadan, yalnızca temel alan altında işlem yaparak küçük alanlarda 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 alan genişletmesine derinlemesine inmeyi gerektirir.

İkili alanlara dayalı bir kanıtlama sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta iz gösterimini hesaplamak için kullanılan alanın 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ın büyüklüğü kodlama genişletildikten sonra olan 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ı veriyi iki farklı şekilde temsil ederek bunu gerçekleştirdi: İlk olarak, çok değişkenli (, tek değişkenli polinom yerine çok lineer ) çok terimli kullanarak, "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etmek; İkincisi, hiperküpün her bir boyutunun uzunluğunun 2 olması nedeniyle, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp kare ) olarak değerlendirilebilir 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ırmaktadır.

2 Prensip Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki bölümden oluşur:

• Bilgi Teorik Polinom İnteraktif Oracle Kanıtı (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin çekirdeği olarak, girilen hesaplama ilişkisini doğrulanabilir polinom denklemlerine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının adım adım polinom göndermesine olanak tanır; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için az sayıda polinomun değerlendirme sonuçlarını sorgulayabilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi çeşitli protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme şekli bakımından farklılık gösterir ve bu da tüm SNARK sisteminin performansı ve verimliliği üzerinde etki yaratır.

• Polinom Taahhüt Şeması (Polynomial Commitment Scheme, PCS ): Polinom taahhüt şeması, PIOP tarafından üretilen polinom eşitliğinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araçla, kanıtlayıcı bir polinoma taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilirken, polinomun diğer bilgilerini gizleyebilir. Yaygın polinom taahhüt şemaları KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown gibi şemalardı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 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 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 odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleştirilmesiyle ve Goldilocks alanına dayanmaktadır. Plonky2, verimli bir tekrarın gerçekleştirilmesi 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ğunu, performansını ve güvenliğini sağlanır. Bu kombinasyonların seçimi sadece SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir kurulum gereksinimi olmadan şeffaflık sağlaması, tekrar kanıtları veya toplama kanıtları gibi genişletme özelliklerini 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ş temel teknolojiyi içermektedir. İlk olarak, kule ikili alanların (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturarak ikili alanda basitleştirilmiş işlemlerin gerçekleştirilmesini sağlar. İ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ştirme arasındaki güvenli ve verimli tutarlılık kontrolünü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı sunar. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş bir Lasso arama kanıtı kullanmaktadır. Son olarak, protokol, küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanarak, ikili alanda verimli bir kanıt sistemi gerçekleştirilmesini sağlamış ve genellikle büyük alanlarla ilişkili olan masrafları azaltmıştır.

( 2.1 Sonlu Alan: binary alanlar üzerindeki kuleler temelinde aritmatikleştirme

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır, bu da iki temel nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, esasen yüksek verimli aritmetik işlemleri destekleyerek, performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline gelir. Ayrıca, ikili alan yapısı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulanabilir cebirsel bir biçimde temsil edilebileceği basitleştirilmiş bir aritmetik süreç destekler. Bu özellikler, kule yapısını kullanarak hiyerarşik özelliklerinden tam anlamıyla yararlanabilme 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 elemanların benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k-bit dizesi doğrudan k-bit ikili alan elemanına haritalanabilir. Bu, asal alanlardan farklıdır; asal alan, belirli bir bit sayısı içinde bu tür bir standart temsil sağlayamaz. 32-bit'lik bir asal alan 32 bit içinde bulunabilirken, her 32 bit dizesinin benzersiz bir alan elemanına karşılık gelmesi söz konusu değildir; oysa ikili alan bu birbiriyle eşleşme kolaylığını sağlar. Asal alan Fp'de yaygın olarak kullanılan 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 ), AES'te kullanılan ###, Montgomery indirgemesi (, POLYVAL'de kullanılan ) ve tekrarlamalı indirgeme (, Tower ) gibi yöntemler yer alır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" 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 çünkü (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralını takip ettiğini belirtmektedir.

Ş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 unsur olarak görülebilir veya iki 64 bitlik kule alan unsuru, dört 32 bitlik kule alan unsuru, on altı 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak ayrıştırılabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizesinin tür dönüşümü ( typecast ) olması, oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama maliyeti olmaksızın daha büyük alan unsurlarına 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" başlıklı makale, n bitlik kule biçimindeki ikili alanda ('in m bitlik alt alana ) ayrılmasının çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

( 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 şunları içerir:

1. GateCheck: Gizli tanık ω ve açık girdi x'in, devre hesaplama ilişkisi C)x, ω###=0'ı sağlayıp sağlamadığını doğrulayarak devrenin doğru çalıştığından emin olun.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiper küpü üzerindeki değerlerinin, çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak için bir permütasyon ilişkisi olup olmadığını doğrulamak f(x) = f(π)x((.

3. LookupCheck: Verilen bir lookup tablosunda polinomun değerinin doğrulanması, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olun.

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: Boolean hiperküp üzerindeki rasyonel çok terimli fonksiyonun belirli bir bildirilen değerle eşit olup olmadığını test eder ∏x∈Hµ f(x) = s, çok terimli çarpımın doğruluğunu sağlamak için.

6. ZeroCheck: Birden fazla değişkenli çok terimli bir polinomun Boole hiperkümesindeki 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 ç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 problemini tek değişkenli polinom değerlendirme probleminin haline getirerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek, çoklu toplam kontrol örneklerinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturarak toplu işlemeyi de destekler.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli polinom değerlemesinin 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 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ştirir ve böylece hesaplama karmaşıklığını azaltır.

• Sıfıra bölme sorununun işlenmesi: HyperPlonk sıfıra bölme durumunu yeterince iyi işleyemedi ve bu nedenle U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını belirlemek mümkün olmadı; Binius bu durumu doğru şekilde işledi, sıfır olan bir payda ile bile Binius'un ProductCheck'i işlemeye devam edebiliyor ve herhangi bir çarpan değerine genişletilmesine izin veriyor.

• Kol Geçişi 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şlemesine olanak tanıyor.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasının geliştirilmesiyle protokolün esnekliğini ve verimliliğini artırmış, özellikle daha karmaşık çok değişkenli çok terimli doğrulamaları işlerken daha güçlü işlevsel destek sağlamıştır. 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şturmuştur.

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

Binius protokolünde, sanal