Binius STARKs Prensip Analizi ve Optimizasyon Düşünceleri

1 Giriş

STARKs'ın verimsizliğinin başlıca 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ğaçları üzerine kurulu sağlama güvenliğini sağlamak için, verileri genişletirken Reed-Solomon kodlaması kullanıldığında, birçok ek yedek değer tüm alanı kaplar, orijinal değer çok küçük olsa bile. Bu sorunu çözmek için alanın boyutunu azaltmak temel bir strateji haline geldi.

Tablo 1'de gösterildiği gibi, 1. nesil STARK'ların kodlama bit genişliği 252 bit, 2. nesil STARK'ların kodlama bit genişliği 64 bit, 3. nesil STARK'ların kodlama bit genişliği ise 32 bit'tir; ancak 32 bit kodlama bit genişliği hala büyük miktarda israf alanı barındırmaktadır. Buna karşılık, ikili alan doğrudan bitlere işlem yapmaya izin verir, kodlama sıkışık ve verimlidir ve herhangi bir israf alanı içermez; yani 4. nesil STARK'lardır.

| Zaman | STARKs | Kodlama Bit Genişliği | |------|--------|----------| | 2018 | 1. Nesil | 252bit | | 2021 | 2. nesil | 64bit | | 2022 | 3. nesil | 32bit | | 2023 | 4. Nesil | 1bit |

Tablo 1: STARKs türev yolu

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlarla kıyaslandığında, ikili alanların araştırması 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ı kullanır;

• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanan, rekürsif için oldukça uygun bir hash algoritmasıdır.

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 garanti etmek için tamamen genişletmeye bağımlıdır. Çoğu Prover hesaplamasında yer alan çok terimli, genişletmeye girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlamaktadır. 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 proof sistemi inşa ederken, iki pratik sorun vardır: STARKs'te izin gösterimini hesaplamak için kullanılan alan boyutunun, polinomun derecesinden büyük olması gerekir; STARKs'te Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılmalı ve kullanılan alan boyutunun, kodlama genişletildikten sonraki boyutundan büyük olması gerekir.

Binius, bu iki sorunla başa çıkmak için yenilikçi bir çözüm önerdi ve aynı verileri iki farklı şekilde göstererek bunu gerçekleştirdi: İlk olarak, çok değişkenli (, özellikle çok çizgisel ) çok terimli yerine tek değişkenli çok terimli kullanarak, "hiperküpler" ( üzerindeki alım değerleri aracılığıyla tüm hesaplama izini temsil etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, 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 merkezi 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 polinomları aşamalı olarak göndermesine olanak tanır; böylece doğrulayıcı, 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, bunlar polinom ifadelerinin işlenme şekli bakımından farklılık gösterir ve bu durum 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 denkleminin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografi aracıdır; bununla, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonuçlarını doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizleyebilir. 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 uygulama senaryolarına sahiptir.

Belirli ihtiyaçlara göre, farklı PIOP ve PCS'leri seçebilir ve uygun bir sonlu alan veya eliptik eğri ile birleştirerek farklı özelliklere sahip kanıt sistemleri oluşturabilirsiniz. Örneğin:

• Halo2: PLONK PIOP ile Bulletproofs PCS'nin birleşimi ve Pasta eğrisi temelinde geliştirilmiştir. Halo2 tasarımında, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın ortadan kaldırılmasına odaklanılmıştır.

• Plonky2: PLONK PIOP ve FRI PCS kombinasyonunu kullanarak ve Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir özyineleme sağlamak için tasarlanmıştır. Bu sistemleri tasarlarken, seçilen PIOP ve PCS'nin kullanılan sonlu alan veya eliptik eğri ile eşleşmesi gerekmektedir; bu, sistemin doğruluğunu, performansını ve güvenliğini sağlamak için önemlidir. 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 olmadan şeffaflık sağlama yeteneğini, özyinelemeli kanıtları veya toplu kanıtlar gibi genişletilebilirlik işlevlerini destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + binary fields. Specifically, Binius includes five key technologies to achieve its efficiency and security. First, the arithmetic based on the tower of binary fields (towers of binary fields) forms the foundation of its computations, enabling simplified operations within the binary fields. Secondly, Binius adapts HyperPlonk product and permutation checks in its interactive Oracle proof protocol (PIOP), ensuring secure and efficient consistency checks between variables and their permutations. Third, the protocol introduces a new multilinear shift proof that optimizes the efficiency of verifying multilinear relationships over small fields. Fourth, Binius employs an improved Lasso lookup proof, providing flexibility and robust security for the lookup mechanism. Finally, the protocol utilizes a small-field polynomial commitment scheme (Small-Field PCS), enabling an efficient proof system over binary fields and reducing the overhead typically associated with large fields.

( 2.1 Sonlu Alan: binary fields üzerinde towers of arithmetic

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir öneme sahiptir; bu, esasen iki ana nedene dayanmaktadır: etkili hesaplama ve etkili aritmetik. İkili alan, esasen yüksek verimlilikte aritmetik işlemleri destekler, bu da onu performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, ikili alan üzerinde gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebileceği basitleştirilmiş aritmetik süreçleri destekler. Bu özellikler, kule yapısı aracılığıyla hiyerarşik özelliklerini tam olarak kullanma yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

"canonical" terimi, ikili alandaki elemanların 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 elemanına haritalanabilir. Bu, asal alandan farklıdır; asal alan, belirli bir bit sayısı içinde bu tür bir standart temsil 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 gelmeyebilir, oysa ikili alan bu bir-bir eşleme kolaylığını sunar. Asal alan Fp'de yaygın olan azaltma yöntemleri arasında Barrett azaltması, Montgomery azaltması ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için özel azaltma yöntemleri bulunur. İkili alanda F2k, 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 azaltma ) 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 oldukça verimli olduğunu belirtmektedir, çünkü bu (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ın bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikili alanda benzersiz bir eleman olarak görülebilir veya iki adet 64 bitlik kule alanı elemanı, dört adet 32 bitlik kule alanı elemanı, on altı adet 8 bitlik kule alanı elemanı veya 128 adet F2 alanı elemanı olarak çözülür. Bu temsilin esnekliği herhangi bir hesaplama maliyeti gerektirmez, sadece bit dizesinin tür dönüşümüdür (typecast), oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan elemanları, ek bir hesaplama maliyeti olmadan daha büyük alan elemanlarına 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 ( m bitlik alt alana ) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.

Şekil 1: Sütun Tabanlı İkili Alan

( 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 terim ve çok değişken kümesinin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:

1. GateCheck: Gizli tanıklama ω ve açık girdi x'in devre hesaplama ilişkisi C)x, ω(=0 ile uyumlu olup olmadığını doğrulamak için devrenin doğru çalıştığını sağlamak.

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

3. LookupCheck: Verilen bir arama tablosunda çok terimli bir ifadenin değerinin doğrulanması, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğunu güvence altına alır.

4. MultisetCheck: İki çok değişkenli kümenin eşit olup olmadığını kontrol etme, yani {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, birden fazla küme arasındaki tutarlılığı sağlama.

5. ProductCheck: Boolean hiper küp üzerindeki rasyonel çok terimli polinomun belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s ile eşit olup olmadığını kontrol ederek, polinom çarpımının doğruluğunu sağlamak.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole hiperkü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 polinomların 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 sorununu tek değişkenli polinom değerlendirme sorununa dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayı introduk ederek birden fazla toplam kontrol örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli çok terimli polinomun değerlendirme doğruluğunu doğrulamak için protokol verimliliğini artırır.

Binius ve HyperPlonk'un protokol tasarımında birçok benzerliği olmasına rağmen, Binius aşağıdaki 3 alanda iyileştirmeler yapmıştır:

• ProductCheck optimizasyonu: HyperPlonk'da, ProductCheck'in paydası U'nun hiperkü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ştirmiş ve hesaplama karmaşıklığını azaltmıştır.

• Sıfıra bölme problemi ile başa çıkma: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküpte sıfırdan farklı olup olmadığını kesin olarak belirlemeyi imkansız hale getirdi; Binius bu sorunu doğru bir şekilde ele aldı, sıfır durumunda bile Binius'un ProductCheck'i işlemeye devam edebiliyor, böylece herhangi bir çarpan değerine genişletilmesine 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 dizilim durumlarını işleyebilmesini sağlar.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasının iyileştirilmesiyle protokolün esnekliğini ve verimliliğini artırdı, özellikle daha karmaşık çok değişkenli çok terimli doğrulama işlemlerinde daha güçlü işlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, 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 hiperküp için geçerlidir

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi önemlidir.