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

1 Giriş

STARK'ların verimsizliğinin ana nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır; örneğin, for döngüsündeki indeksler, doğru/yanlış değerleri, sayaçlar vb. Ancak, Merkle ağacı kanıtlarının güvenliğini sağlamak için, verileri genişletirken Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değeri tüm alanı kaplar, hatta orijinal değerler çok küçük olsa bile. 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'tir, ancak 32 bit kodlama bit genişliğinde hala büyük miktarda israf alanı vardır. Karşılaştırıldığında, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimlidir ve herhangi bir israf alanı yoktur, yani 4. nesil STARKs.

Tablo 1: STARKs türev yolu

Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan yeni araştırmalara kıyasla, ikili alan araştırmaları 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ı 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.

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ğımlıdır. Çoğu Prover hesaplamasında yer alan çok terimlilikler, genişletmeye girmeden yalnızca temel alanda çalışmakla yeterlidir, böylece küçük alanda yüksek verimlilik sağlanır. Ancak, rastgele nokta kontrolleri ve FRI hesaplamaları, gerekli güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine girmeyi gerektirir.

İkili alanlara dayalı bir kanıtlama sistemi inşa ederken, iki pratik sorun vardır: STARKs'da iz gösterimini hesaplamak için kullanılan alanın, polinomun derecesinden büyük olması gerekir; STARKs'da Merkle ağacı taahhüt ederken, Reed-Solomon kodlaması yapılması gerekir ve 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, çok değişkenli (, tam olarak çok lineer ) çok terimli ile tek değişkenli polinomun yerini alarak, "hiperküplerde" (, ) değerlerini alarak tüm hesaplama izini temsil etmek için kullanıldı; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare ( olarak düşünülebilir ve bu kare üzerinden Reed-Solomon genişlemesi yapılabilir. Bu yöntem, güvenliği sağlarken kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırmıştır.

2 İlkelerin Analizi

Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki kısmı içerir:

• Bilgi Teorisi Çok Terimli Etkileşimli Oracle Kanıtı ) Information-Theoretic Polynomial Interactive Oracle Proof, PIOP (: PIOP, kanıt sisteminin temelini oluşturur ve girilen hesaplama ilişkisini doğrulanabilir çok terimli eşitliklere dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim kurarak, kanıtlayıcının aşamalı olarak çok terim göndermesine izin verir; böylece doğrulayıcı, hesaplamanın doğru olup olmadığını doğrulamak için yalnızca birkaç çok terimli değerlendirme sonucunu sorgulayarak bunu kontrol edebilir. Mevcut PIOP protokolleri arasında PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi farklılık gösteren çok terimli ifadelerin işlenme şekilleri vardır; bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.

• Polinom Taahhüt Şeması ) Polinom Taahhüt Şeması, 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 sayede, kanıtlayıcı belirli 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ı arasında KZG, Bulletproofs, FRI ) Hızlı Reed-Solomon IOPP ( ve Brakedown 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çebilir ve uygun bir sonlu alan veya eliptik eğri ile birleştirerek farklı özelliklere sahip bir kanıt sistemi oluşturabilirsiniz. Örneğin:

• Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimiyle ve Pasta eğrisi temelinde oluşturulmuştur. Halo2, tasarımında ö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ştirerek Goldilocks alanına dayanmaktadır. Plonky2, 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 kurulum gerektirmeden şeffaflık sağlaması, özyinelemeli kanıtları veya toplu kanıtlar gibi genişletilebilir özellikleri 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 based on tower binary fields )towers of binary fields( forms the basis of its computation, enabling simplified operations within the binary field. Second, Binius adapts HyperPlonk product and permutation checks in its interactive Oracle proof protocol )PIOP( to ensure the secure and efficient consistency check between variables and their permutations. Third, the protocol introduces a new multivariate shift proof, optimizing the efficiency of verifying multivariate 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 it to implement an efficient proof system over binary fields while reducing the overhead typically associated with large fields.

![Bitlayer Research: Binius STARKs prensibi analizi ve optimizasyon düşünceleri])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(

) 2.1 Sonlu Alan: binary field kuleleri üzerine kurulu aritmetik

Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar bir rol oynamaktadır, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan esasen yüksek verimli 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ı basitleştirilmiş bir aritmetik süreci destekler; yani ikili alan üzerinde gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir. Bu özellikler, kule yapısının hiyerarşik özelliklerinden tam olarak yararlanma 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 unsurları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 unsuruna eşlenebilir. Bu, asal alandan 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 şekilde bir alan unsuruna 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 azaltma, Montgomery azaltma 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 özel azaltma ###, AES'te kullanılan (, Montgomery azaltma ), POLYVAL'da kullanılan ( ve Tower ) gibi özyinelemeli azaltma yöntemleri bulunur. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı 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 + Y2 kuralını izler.

Ş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 tekil bir unsur olarak değerlendirilebilir 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 çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tip dönüşümü (typecast) ile sağlanır; bu da son derece 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ı çalışma, n bitlik kule ikili alanının ( m bitlik alt alan ) halinde çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını araştırmaktadır.

Şekil 1: Kule Tabanlı İkili Alan

( 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ıklık ω ve kamuya açık girişi 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 polinom f ve g'nin Boolean hiperküpteki değerlendirme sonuçlarının bir permütasyon ilişkisi olup olmadığını doğrulamak için f(x) = f(π)x((, polinom değişkenleri arasındaki sıralamanın tutarlılığını sağlamak amacıyla.

3. LookupCheck: Polinomun değerinin belirli bir arama tablosunda doğrulanması, yani f)Bµ) ⊆ T(Bµ), belirli bazı değerlerin belirtilen aralığın içinde olduğunu güvence altına alı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üp üzerindeki rasyonel çokterimlinin değerlendirilmesinin belirli bir beyan edilen değerle ∏x∈Hµ f(x) = s eşit olup olmadığını kontrol etmek, çokterimlinin çarpımının doğruluğunu sağlamak için.

6. ZeroCheck: Birden fazla değişkenli bir polinomun Boolean hiperküp üzerindeki 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 amacıyla.

7. SumCheck: Çok değişkenli polinomların toplamının belirtilen değer olup olmadığını kontrol eder ∑x∈Hµ f(x) = s. Çok değişkenli polinomun değerlendirme sorununu tek değişkenli polinomun değerlendirme sorununa dönüştürerek doğrulayıcının hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck, rastgele sayıların tanıtılmasıyla birden çok toplam kontrol örneğinin toplu işlenmesini sağlamak için lineer kombinasyonlar oluşturur.

8. BatchCheck: SumCheck'e dayanarak, birden fazla çok değişkenli polinomun değerlerinin 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, paydanın U'nun hiperküp üzerinde her yerde sıfır olmamasını ve çarpımın belirli bir değere eşit olmasını gerektirir; 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 yönetimi: HyperPlonk, sıfıra bölme durumunu yeterince ele alamamıştır, bu da U'nun hiper küp üzerindeki sıfırdan farklı olup olmadığını kesin olarak belirtmeyi imkansız kılmaktadır; Binius bu sorunu doğru bir şekilde ele almıştır, sıfır paydası durumunda bile Binius'un ProductCheck'i işlemeye devam edebilir, herhangi bir çarpan değerine yayılmasına izin verir.

• 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 polinom sıralama durumlarını işleyebilmesini sağlar.

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 çokterim doğrulamalarını işlerken daha güçlü fonksiyonel destek sağladı. Bu iyileştirmeler sadece 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ı------uygulanabilir