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

1. Giriş

STARKs'ın düşük verimliliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır. Ancak Merkle ağacı kanıtlarının güvenliğini sağlamak için, Reed-Solomon kodlaması kullanarak verileri genişlettiğimizde, birçok ek yedek değer 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.

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ğinde hâlâ büyük ölçüde israf alanı bulunmaktadır. Buna karşılık, ikili alan doğrudan bit üzerinde işlem yapmaya izin verir, kodlama kompakt ve verimli olup herhangi bir israf alanı olmadan, yani 4. nesil STARKs.

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 1980'lere kadar uzanıyor. Şu anda, 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ı kullanarak
• Orijinal FRI ve zk-STARK protokolleri ile SHA-3 finaline giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve tekrarlama için son derece uygun bir hash algoritmasıdır.

Daha küçük bir alan kullanıldığında, alan genişletme işlemi güvenliği sağlamak için giderek daha önemli hale geliyor. Binius'un kullandığı ikili alan, güvenliğini ve pratik kullanılabilirliğini sağlamak için tamamen alan genişletmeye dayanmak zorundadır. Çoğu Prover hesaplamasında yer alan çok terimlilerin alan genişletmesine girmesine gerek yoktur ve yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hala gerekli güvenliği sağlamak için daha büyük bir alan genişletmesine inmek zorundadır.

İkili alanlara dayalı bir kanıtlama sistemi kurarken iki pratik sorun vardır: STARKs'te izlerin temsilini hesaplamak için kullanılan alan boyutu, polinomun derecesinden büyük olmalıdır; STARKs'te Merkle ağacının taahhüdü sırasında Reed-Solomon kodlaması yapılması gerektiğinden, 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 etti: Öncelikle, tek değişkenli polinom yerine çok değişkenli ( çoklu lineer ) polinom kullanarak, "hiperküpler" ( üzerindeki değerlerini alarak tüm hesaplama izini temsil eder; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişletmesi yapılamaz, ancak hiperküp 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ırmaktadır.

2. İlkelerin 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, verilen 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 aşamalı olarak polinom göndermesine olanak tanır; böylece doğrulayıcı, hesaplamanın doğruluğunu doğrulamak için yalnızca az sayıda polinomun değerlendirme sonuçlarını sorgulayarak kontrol edebilir. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar polinom ifadelerinin işlenme biçiminde farklılık göstererek 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 denkleminin doğru olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araçla, 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 yöntemler bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygulama senaryolarına sahiptir.

Belirli gereksinimlere göre, farklı PIOP ve PCS'ler seçilerek ve uygun bir sonlu alan veya elips eğri ile birleştirilerek, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleştirilmesiyle oluşturulmuş olup, Pasta eğrisi temel alınmıştır. Halo2 tasarımı, ölçeklenebilirliğe ve ZCash protokolündeki trusted setup'ın kaldırılmasına odaklanmıştır.

• Plonky2: PLONK PIOP ve FRI PCS'yi birleştirir ve Goldilocks alanına dayanır. Plonky2, verimli bir özyinelemeyi gerçekleştirmek 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 gerekir, 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 olmadan şeffaflık sağlayıp sağlayamayacağını, özyinelemeli kanıtlar veya toplu kanıtlar gibi genişletilebilir işlevleri destekleyip destekleyemeyeceğ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 construction based on tower binary fields (towers of binary fields) forms the basis of its computation, enabling simplified operations within the binary field. Second, Binius adapted 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, optimizing the efficiency of verifying multilinear relations over small fields. Fourth, Binius adopts an improved 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 implement an efficient proof system over binary fields while reducing the overhead typically associated with large fields.

( 2.1 Sonlu Alan: binary alanları kulelerine dayanan aritmetik

Kule ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik öneme sahiptir; bu, iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan esasen son derece verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografi 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 ifade edilebileceği basitleştirilmiş aritmetik süreçleri destekler. Bu özellikler, kule yapısını kullanarak hiyerarşik özelliklerinden tam olarak yararlanabilme yeteneği ile birleştiğinde, ikili alanı Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.

Burada "canonical" terimi, ikili alandaki elemanların benzersiz ve doğrudan gösterim biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k bitlik dizi doğrudan k bitlik bir 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 gösterim sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilirken, her 32 bitlik dizi benzersiz bir alan elemanına karşılık gelmeyebilir; oysa ikili alan bu birbiriyle eşleşme kolaylığını sunar. 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 bulunur. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma ), AES'te kullanılan ###, Montgomery azaltması (, POLYVAL'de kullanılan ) ve yineleme azaltması (, Tower ) vardır. "Asal Alan ile İkili Alan ECC Donanım Uygulamaları Tasarım Alanını Keşfetme" 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 işlem (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralına uyar.

Ş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 alanda 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 temsil esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizesinin tür dönüşümü (typecast) ile sağlanır ve oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan unsurları daha büyük alan unsurlarına ek maliyet olmadan 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" adlı makale, n bitlik kule benzeri ikili alanlarda ('in m bitlik alt alan )'ye çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

( 2.2 PIOP: Uyarlanmış 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 şunlardır:

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

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

3. LookupCheck: Verilen arama tablosunda çok terimli değerlendirmenin doğruluğunu doğrulamak, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olmak.

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: Akıllı çok terimli polinomun Boolean hiper küpü üzerindeki değerlendirmesinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmesi, polinom çarpımının doğruluğunu garanti etmek için.

6. ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole hiperkümesindeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏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, beyan edilen değer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomların değerleme sorununu tek değişkenli polinom değerleme sorununa dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayılar getirerek birden fazla toplam kontrol örneğinin toplu işlenmesini sağlamak için lineer kombinasyon oluşturarak toplu işleme de izin verir.

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

Binius'in HyperPlonk ile 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'ta, ProductCheck'in, paydanın U'nun hiperkübede 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 hesaplama karmaşıklığını azaltır.

• Sıfıra bölme sorunlarının işlenmesi: HyperPlonk sıfıra bölme durumlarını yeterince işleyemediği için U'nun hiperküp üzerindeki sıfır olmayan durumu hakkında kesin bir şey söylenememektedir; Binius bu sorunu doğru bir şekilde ele almıştır, sıfır olan bir payda durumunda bile Binius'un ProductCheck'i işlemeye devam edebilir ve herhangi bir çarpım değerine yayılmasına izin verir.

• 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ı ele almasını 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ğrulamaların işlenmesinde daha güçlü işlevsel destek sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayalı kanıt sistemleri için bir temel oluşturdu.

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

Binius protokolünde, sanal çok terimli yapıların oluşturulması ve işlenmesi anahtardır ve giriş tutamağından veya diğer sanal çok terimlerden türetilen çok terimleri etkili bir şekilde oluşturup işlemeye olanak tanır. Aşağıda iki anahtar yöntem bulunmaktadır:

• Paketleme: Bu yöntem, sözlük sırasındaki komşu konumlardaki daha küçük öğeleri daha büyük birimlere paketleyerek çalışır.