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

1 Giriş

STARKs, hash tabanlı bir kanıtlama sistemidir ve eliptik eğri tabanlı SNARKs'tan farklıdır. STARKs'ın şu anda düşük verimliliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayısal değerin küçük olmasıdır; örneğin, döngülerdeki indeksler, doğru/yanlış değerler, sayaçlar vb. Ancak, Merkle ağaçları tabanlı kanıtların güvenliğini sağlamak için, verileri Reed-Solomon kodlaması ile genişletirken, birçok ek fazlalık değeri tüm alanı kaplar; bu, orijinal değer kendisi çok küçük olsa bile geçerlidir. 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 hâlâ 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ı ve verimli olup herhangi bir israf alanı yoktur, yani 4. nesil STARKs.

Tablo 1: STARKs Türev Yolu

| Nesil | Genişlik | Özellikler | |------|------|------| | 1. Nesil | 252bit | Büyük alan, büyük alan israfı | | 2. Nesil | 64bit | Orta alan, geniş alan israfı | | 3. nesil | 32bit | Küçük alan, hala israf alanı var | | 4. Nesil | 1bit | İkili alan, boş alan yok |

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 1980'lerin başlarına 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 protokolü ile SHA-3 finaline katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve yinelemeli hash algoritmaları için oldukça uygundur.

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 gerçek kullanılabilirliğini sağlamak için tamamen genişletmeye dayanı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 elde edilir. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletme alanına inmek zorundadır.

İkili alanlara dayalı bir kanıt sistemi inşa ederken, 2 gerçek sorun vardır: STARKs'ta izin temsilini hesaplamak için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacı taahhüt edilirken, Reed-Solomon kodlaması yapılması gerekir, kullanılan alan boyutu kodlama genişletildikten sonra 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 ederek bunu gerçekleştirdi: İlk olarak, çok değişkenli (, özellikle çok lineer ) polinomları kullanarak, tek değişkenli polinomların yerini aldı ve "hiperküp" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etti; İkincisi, hiperküpün her boyutunun uzunluğunun 2 olması nedeniyle, STARK'lar gibi standart Reed-Solomon genişlemesi yapılamaz; ancak hiperküp kare ) olarak düşünülebilir ve bu kareye dayalı olarak Reed-Solomon genişlemesi gerçekleştirilebilir. Bu yöntem, güvenliği sağlarken aynı zamanda kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.

2 Prensip Analizi

Günümüzde çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki kısmı içerir:

• 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ı kademeli olarak göndermesine olanak tanır; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak 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 şekillerine göre farklılık gösterir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Şeması (Polinomial 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, 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(Hızlı Reed-Solomon IOPP) ve Brakedown gibi şemalar 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 ile Pasta eğrisi üzerine kurulmuştur. Halo2, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun ortadan kaldırılmasına odaklanarak tasarlanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanmaktadır. Plonky2, verimli bir rekürsiyon 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 uyumlu olmalıdır, 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 kurulum gerektirmeden şeffaflık sağlama yeteneğini, rekürsif kanıtlar veya toplu kanıtlar gibi genişletme işlevlerini destekleyip desteklemediğini de belirler.

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

( 2.1 Sınırlı Alan: binary alanların kuleleri temelinde aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaları gerçekleştirmenin anahtarıdır ve bu iki temel nedene dayanmaktadır: verimli hesaplama ve verimli cebirsel yapı. İkili alan, özünde yüksek verimli cebirsel 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ı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilmesi için basitleştirilmiş bir cebirsel süreç destekler. Bu özellikler, kule yapısını kullanarak 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 bir elemanın eşsiz 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 asal alan 32-bit içinde yer alabilirken, her 32-bit dizesinin eşsiz bir alan elemanıyla karşılık gelmesi mümkün değildir; oysa ikili alan bu tür bir birebir eşleme kolaylığına sahiptir. Asal alan Fp'de, yaygın 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 bulunmaktadır. İkili alan F2k'de, yaygın olarak kullanılan azaltma yöntemleri arasında AES'de kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower( gibi özyinelemeli azaltma ) bulunmaktadır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" başlıklı çalışma, 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 biçimindeki sadeleştirilmiş kuralı izlemektedir.

Şekil 1'de gösterildiği gibi, 128 bitlik bir dizi: Bu dizi ikili alan bağlamında çeşitli şekillerde yorumlanabilir. 128 bitlik ikili alandaki benzersiz bir unsur olarak değerlendirilebilir veya iki 64 bitlik kule alan unsuru, dört 32 bitlik kule alan unsuru, 16 adet 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, sadece bit dizisinin tür dönüşümüdür (typecast), oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama maliyeti olmadan daha büyük alan unsurlarına paketlenebilir. Binius protokolü, bu özelliği kullanarak hesaplama verimliliğini artırır. Ayrıca, "On Efficient Inversion in Tower Fields of Characteristic Two" başlıklı makale, n bitlik kule yapısındaki ikili alanda (, m bitlik alt alan )'ya ayrılarak ç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ıklı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ığını sağlamak.

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

3. LookupCheck: Verilen bir arama tablosunda polinom 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ş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: Mantıksal hiper kümede, bir polinomun belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s 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übündeki herhangi bir noktada sıfır olup olmadığını doğrulama ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, polinomun sıfır noktasının dağılımını sağlamak için.

7. SumCheck: Çok değişkenli polinomların toplamının belirtilen değer olup olmadığını kontrol etme ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinom değerlendirme sorununa dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck toplu işlem yapmaya da izin verir; rastgele sayılar getirerek, birden fazla toplam doğrulama örneği için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayalı olarak, birden fazla çok değişkenli çok terimli 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 hiperküp üzerinde her yerde sıfır olmaması ve çarpımın belirli bir değere eşit olması gerekir; 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ıra bölme problemi ile ilgili işleme: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını belirleyememeyi sağladı; Binius bu sorunu doğru bir şekilde ele aldı, sıfır olan bir paydada 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 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 çok terimli doğrulama işlemlerinde daha güçlü fonksiyon desteği sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda...