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

1 Giriş

STARK'ları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ı üzerindeki kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması kullanıldığında, verileri genişletmek amacıyla birçok ek yedeklilik değeri tüm alanı kaplar, bu da orijinal değerin kendisi çok küçük olsa bile geçerlidir. Bu sorunu çözmek için, alanın boyutunun azaltılması kritik bir strateji haline gelmiştir.

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 32 bit, ancak 32 bit kodlama bit genişliği hala büyük ölçüde israf alanı barındırıyor. Buna göre, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı içermez, yani 4. nesil STARK'lar.

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 | Polygon zkEVM | | 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 uzanıyor. Günümüzde, ikili alanlar kriptolojide yaygın olarak kullanılmaktadır, tipik örnekler şunlardır:

• Gelişmiş Şifreleme Standartı (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 katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve yinelemeli hash algoritmaları için son derece 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 pratik kullanılabilirliğini sağlamak için tamamen genişletmeye bağlıdır. Çoğu Prover hesaplamasında yer alan polinomlar genişletmeye girmek zorunda değildir, yalnızca temel alanda işlem yaparak küçük alanda 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 genişletme alanına derinlemesine inmek zorundadır.

İkili alanlara dayanan bir kanıt sistemi oluştururken, iki pratik sorun vardır: STARKs'ta izin temsilini hesaplamak için kullanılan alan boyutunun, polinomun derecesinden büyük olması gerekir; STARKs'ta Merkle ağacı taahhüdü yaparken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutunun, kodlama genişletildikten sonraki boyuttan büyük olması gerekir.

Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önerdi ve aynı veriyi iki farklı şekilde temsil ederek bunu başardı: İlk olarak, çok değişkenli (, özellikle çok lineer ) polinomunu tek değişkenli polinomun yerini almak için kullandı ve "hiperküpler" ( üzerindeki değerleri aracılığıyla tüm hesaplama izini temsil etti; İkincisi, hiperküpün her boyutunun uzunluğunun 2 olmasından dolayı, STARK'lar gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp bir kare ) olarak düşünülebilir ve bu kareye dayalı olarak Reed-Solomon genişletmesi yapılabilir. Bu yöntem, güvenliğin sağlanmasını garanti ederken, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırmıştır.

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 sistemi olarak, girişteki hesaplama ilişkisini doğrulanabilir polinom eşitliklerine dönüştürmektedir. Farklı PIOP protokolleri, doğrulayıcı ile etkileşimde bulunarak, kanıtlayıcının aşamalı olarak polinom 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 ve bunlar, polinom ifadelerinin işlenme şekli bakımından farklılık göstermektedir, bu da tüm SNARK sisteminin performansını ve verimliliğini etkilemektedir.

• Polinom Taahhüt Şeması ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt şeması, PIOP tarafından üretilen polinom eşitliğinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli 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 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çilerek, 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 inşa edilmiştir. Halo2, ölçeklenebilirliğe ve ZCash protokolündeki güvenilen kurulumun kaldırılmasına odaklanarak tasarlanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'nin bir kombinasyonu kullanarak Goldilocks alanına dayanmaktadır. Plonky2, yüksek 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, SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar olmaksızın şeffaflık sağlaması, özyinelemeli kanıtlar veya toplama kanıtları gibi genişletilebilir özellikleri destekleyip desteklemeyeceğini de belirler.

Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknoloji içermektedir. İlk olarak, (towers of binary fields) temelinde, aritmetik yapısı, ikili alan içinde basitleştirilmiş işlemler gerçekleştirmeye olanak tanıyan hesaplamanın temelini oluşturur. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrolünü uyarlayarak, değişkenler ve bunların permütasyonları arasında güvenli ve verimli bir tutarlılık kontrolü sağlar. Üçüncüsü, protokol, küçük alanlarda çoklu doğrusal ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrusal kaydırma kanıtı getiriyor. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü güvenlik sağlayan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi gerçekleştirebilmesini ve genellikle büyük alanlarla ilişkili maliyetleri azaltabilmesini sağlayan küçük alan çoklu terim taahhüt şemasını (Small-Field PCS) kullanmaktadır.

( 2.1 Sonlu Alanlar: binary fields üzerindeki towers of arithmetic

Kule biçimindeki ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır; bu, iki ana nedene dayanmaktadır: etkili hesaplama ve etkili aritmetik. İkili alan, temelde son derece etkili aritmetik işlemleri destekleyerek, performans gereksinimlerine duyarlı kriptografik uygulamalar için ideal bir seçenek haline gelir. Ayrıca, ikili alan yapısı, ikili alanda gerçekleştirilen işlemlerin kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebileceği basitleştirilmiş bir aritmetik süreçleri destekler. Bu özellikler, kule yapısını kullanarak hiyerarşik özelliklerini tam anlamıyla 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 elemanı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 bir bit sayısı içinde bu tür bir standart gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilse de, her 32 bitlik dize benzersiz bir alan elemanına karşılık gelmezken, ikili alan bu birbiriyle eşleşme kolaylığına sahiptir. 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 alanlara yönelik özel indirgeme yöntemleri bulunmaktadır. İkili alan F2k'de, yaygın olarak kullanılan indirgeme yöntemleri arasında AES'de kullanılan özel indirgeme ), POLYVAL'de kullanılan Montgomery indirgemesi ### ve Tower( gibi özyinelemeli indirgeme ) bulunmaktadı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, çü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 öğe olarak düşünülebilir 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 ayrıştırılabilir. Bu temsilin esnekliği herhangi bir hesaplama masrafı gerektirmeden, sadece bit dizisinin tür dönüşümü (typecast) ile mümkündür ve bu oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan öğeleri daha büyük alan öğeleri olarak paketlenebilir ve ek bir hesaplama masrafı olmadan kullanılabilir. Binius protokolü bu özelliği kullanarak hesaplama verimliliğini artırmaktadı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 alan ) üzerinde çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

( 2.2 PIOP: Uyarlama HyperPlonk Ürünü ve Permütasyon Kontrolü------ İkili alan için uygundur

Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almıştır ve çoklu polinomların 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ıkları ω ve açık girişi x'in devre hesaplama ilişkisi C)x, ω(=0 ile sağlanıp sağlanmadığını doğrulamak, devrenin doğru çalıştığını garanti etmek için.

2. PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiperküpündeki değerlendirme sonuçlarının değişim ilişkisi olup olmadığını doğrulamak için f)x### = f(π)x(), çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak amacıyla.

3. LookupCheck: Polinomun değerlendirmesinin verilen arama tablosunda olup olmadığını doğrulamak, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğunu sağlamaktır.

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 hiperkübün üzerinde rasyonel çok terimli bir polinomun değerlendirmenin belirli bir ifade edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol eder, böylece polinom çarpımının doğruluğunu sağlar.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boolean 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 çok terimli polinomun toplamının belirtilen değer olup olmadığını kontrol etme ∑x∈Hµ f(x) = s. Çok değişkenli polinom değerlendirme problemini tek değişkenli polinom değerlendirmesine dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar tanıtarak çoklu toplam doğrulama örneklerinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli çok terimli polinom değerlendirmenin 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 gelişmeler göstermiştir:

• 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ı gerekir; 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 probleminin çözümü: HyperPlonk sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirleyememeye yol açtı; Binius bu durumu 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 genişletilmesine izin veriyor.

• Sütunlar Arası 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şleyebilmesini sağlıyor.

Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasının geliştirilmesiyle protokolün esnekliğini ve verimliliğini artırdı, özellikle daha karmaşık çok değişkenli polinom doğrulamalarını işlerken daha güçlü işlevsel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekteki ikili alan tabanlı kanıt sistemlerinin temelini attı.

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

Binius protokolünde, sanal