Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1 Giriş
STARKs'ın verimsizliğinin başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu sayısal değerler küçüktür, örneğin for döngüsündeki indeksler, doğru-yanlış değerleri, sayaçlar vb. Ancak, Merkle ağaçları üzerine kurulu kanıtların güvenliğini sağlamak için, verileri genişletmek amacıyla Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değeri tüm alanı kaplar, hatta orijinal değer kendisi çok küçük olsa bile. 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 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 hala büyük ölçüde israf alanı barındırıyor. Karşılaştırıldığında, ikili alan doğrudan bitlere işlem yapmayı sağlar, kodlama sıkı ve verimlidir ve herhangi bir israf alanı yoktur, yani 4. nesil STARKs.
Tablo 1: STARKs Türev Yolu
| Cebir | Kodlama Genişliği | Temsili Uygulama |
|------|----------|------------|
| 1. Nesil | 252bit | StarkWare |
| 2. Nesil | 64bit | Plonky2 |
| 3. Nesil | 32bit | BabyBear |
| 4. nesil | 1bit | Binius |
Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan sınırlı alan araştırmalarına kıyasla, ikili alan araştırmaları 1980'lere kadar uzanmaktadır. Şu anda, ikili alan 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 finale kalan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve yinelemeli hash algoritması için oldukça uygundur.
Küçük bir alan kullanıldığında, genişletme işlemi güvenliğin sağlanması 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 dayanmak zorundadır. Çoğu Prover hesaplamasında yer alan çok terimli polinomlar genişletme alanına girmeye ihtiyaç duymadan, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hala 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 doğrulama sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin gösterimi için kullanılan alanın büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüdü için Reed-Solomon kodlaması yapılması gerektiğinden, kullanılan alanın büyüklüğü, kodlama genişletmesinden sonra elde edilen boyuttan 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 (, tam olarak çok lineer ) polinomunu tek değişkenli polinom yerine kullanarak, "hiperküpler" ( üzerindeki alımları aracılığıyla tüm hesaplama izini temsil etmek; İkincisi, hiperküpün her 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 kare temel alınarak 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 Prensip Analizi
Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki bölümden oluşur:
Bilgi Teorik Çok Terimli Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin temelini oluşturur ve verilen hesaplama ilişkisini doğrulanabilir çok terimli eşitliklere dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının çok terimleri 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ç çok terimin 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, çok terimli ifadelerin işlenme biçiminde farklılık gösterir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.
Polinom Taahhüt Şeması ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt şeması, PIOP tarafından oluşturulan polinom eşitliğinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır, bununla birlikte, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonucunu doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizli tutar. Yaygın polinom taahhüt şemaları KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown gibi çeşitli şemalardı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ştirildiğinde, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:
Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ve Pasta eğrisi temelinde. Halo2 tasarlanırken, ölçeklenebilirliğe odaklanılmıştır ve ZCash protokolündeki trusted setup'ın kaldırılması amaçlanmıştır.
Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir rekursif 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 olmadan şeffaflık sağlaması, rekursif kanıt veya toplu kanıt gibi genişletilebilir özellikleri destekleyip desteklemeyeceğini de belirler.
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş anahtar teknolojiyi içermektedir. İlk olarak, kule ikili alanlarının (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemleri gerçekleştirme yeteneği sunmaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrolünü adapte ederek, değişkenler ve bunların permütasyonları arasındaki güvenli ve verimli tutarlılık kontrolünü sağlamaktadır. Üçü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ı getirmektedir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü bir güvenlik sunan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi sağlamak ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltmak için küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.
( 2.1 Sonlu Alan: binary alanların kuleleri üzerine kurulu aritmetik
Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik öneme sahiptir, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temelde yüksek verimli aritmetik işlemleri destekler ve 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 hesaplamaların kompakt ve doğrulanması kolay cebirsel biçimde temsil edilebileceği basitleştirilmiş bir aritmetik süreç destekler. Bu özellikler, kule yapısını kullanarak hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile bir araya geldiğinde, ikili alanları Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.
"canonical" terimi, ikili alandaki elemanların eşsiz 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 alanlar belirli bir bit sayısı içinde bu tür bir standart gösterim sağlayamazlar. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize eşsiz 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 olarak kullanılan indirgeme yöntemleri arasında Barrett indirgemesi, Montgomery indirgemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için ö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'da kullanılan Montgomery indirgemesi ### ve Tower( gibi özyinelemeli indirgeme ) bulunmaktadır. "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 işlem (X + Y )2 = X2 + Y 2'nin 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 alandaki benzersiz bir unsur olarak görülebilir veya iki adet 64 bitlik kule alan unsuru, dört adet 32 bitlik kule alan unsuru, on altı adet 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak yorumlanabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, sadece bit dizisinin tür dönüşümü (typecast) ile sağlanır, bu da son derece ilginç ve faydalı bir özellik olarak öne çıkmaktadır. Aynı zamanda, küçük alan unsurları daha büyük alan unsurlarına ek bir hesaplama maliyeti olmadan 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" makalesi, n bitlik kule ikili alanında ('in m bitlik alt alana ) ayrılarak çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.
( 2.2 PIOP: HyperPlonk Ürünü ve Permutasyon Kontrolü için Uygun Olarak Değiştirilmiş Versiyonu------İkili Alan için
Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almış, 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:
GateCheck: Gizli tanıklık ω ve açık giriş x'in C)x, ω(=0 devre işlem ilişkisini karşılayıp karşılamadığını doğrulamak için, devrenin doğru çalıştığını sağlamak.
PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiperkübündeki değerlendirme sonuçlarının permütasyon ilişkisi olup olmadığını doğrulamak için f)x### = f(π)x() denetimi yapılır ve çok terimli değişkenler arasındaki düzenin tutarlılığı sağlanır.
LookupCheck: Verilen arama tablosunda çok terimli değerlendirmenin doğruluğunu doğrulayın, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğunu garanti edin.
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.
ProductCheck: Mantıksal hiper kümede rasyonel çok terimli 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.
ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole hiper kü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.
SumCheck: Çok değişkenli çok terimli polinomun toplam değerinin beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol etme. Çok değişkenli polinomun 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 doğrulama örneği için toplu işleme olanak tanır.
BatchCheck: SumCheck temelinde, birden fazla çok değişkenli polinomun değerlerinin doğruluğunu doğrulamak için, protokol verimliliğini artırmak.
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 böylece hesaplama karmaşıklığını azaltır.
Sıfıra bölme sorunlarının çözümü: HyperPlonk, sıfır durumu ile yeterince başa çıkamamaktadır, bu da U'nun hiper küp üzerindeki sıfırdan farklı olduğu sorununu kesin olarak belirlemeyi 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 edebilmekte ve herhangi bir çarpan değerine genişletmeye izin vermektedir.
Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değil; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli düzenlemeleri işlemesine olanak tanır.
Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasını iyileştirerek protokolün esnekliğini ve verimliliğini artırdı.
Binius: İkili alan üzerindeki optimize edilmiş STARK'lar
Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1 Giriş
STARKs'ın verimsizliğinin başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu sayısal değerler küçüktür, örneğin for döngüsündeki indeksler, doğru-yanlış değerleri, sayaçlar vb. Ancak, Merkle ağaçları üzerine kurulu kanıtların güvenliğini sağlamak için, verileri genişletmek amacıyla Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değeri tüm alanı kaplar, hatta orijinal değer kendisi çok küçük olsa bile. 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 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 hala büyük ölçüde israf alanı barındırıyor. Karşılaştırıldığında, ikili alan doğrudan bitlere işlem yapmayı sağlar, kodlama sıkı ve verimlidir ve herhangi bir israf alanı yoktur, yani 4. nesil STARKs.
Tablo 1: STARKs Türev Yolu
| Cebir | Kodlama Genişliği | Temsili Uygulama | |------|----------|------------| | 1. Nesil | 252bit | StarkWare | | 2. Nesil | 64bit | Plonky2 | | 3. Nesil | 32bit | BabyBear |
| 4. nesil | 1bit | Binius |
Goldilocks, BabyBear, Mersenne31 gibi son yıllarda yapılan sınırlı alan araştırmalarına kıyasla, ikili alan araştırmaları 1980'lere kadar uzanmaktadır. Şu anda, ikili alan kriptografide yaygın olarak kullanılmaktadır, tipik örnekler şunlardır:
Küçük bir alan kullanıldığında, genişletme işlemi güvenliğin sağlanması 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 dayanmak zorundadır. Çoğu Prover hesaplamasında yer alan çok terimli polinomlar genişletme alanına girmeye ihtiyaç duymadan, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları hala 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 doğrulama sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin gösterimi için kullanılan alanın büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüdü için Reed-Solomon kodlaması yapılması gerektiğinden, kullanılan alanın büyüklüğü, kodlama genişletmesinden sonra elde edilen boyuttan 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 (, tam olarak çok lineer ) polinomunu tek değişkenli polinom yerine kullanarak, "hiperküpler" ( üzerindeki alımları aracılığıyla tüm hesaplama izini temsil etmek; İkincisi, hiperküpün her 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 kare temel alınarak 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 Prensip Analizi
Mevcut çoğu SNARKs sisteminin inşası genellikle aşağıdaki iki bölümden oluşur:
Bilgi Teorik Çok Terimli Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, kanıt sisteminin temelini oluşturur ve verilen hesaplama ilişkisini doğrulanabilir çok terimli eşitliklere dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının çok terimleri 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ç çok terimin 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, çok terimli ifadelerin işlenme biçiminde farklılık gösterir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.
Polinom Taahhüt Şeması ( Polynomial Commitment Scheme, PCS ): Polinom taahhüt şeması, PIOP tarafından oluşturulan polinom eşitliğinin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır, bununla birlikte, kanıtlayıcı bir polinomu taahhüt edebilir ve daha sonra bu polinomun değerlendirme sonucunu doğrulayabilir, aynı zamanda polinomun diğer bilgilerini gizli tutar. Yaygın polinom taahhüt şemaları KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) ve Brakedown gibi çeşitli şemalardı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ştirildiğinde, farklı özelliklere sahip kanıt sistemleri oluşturulabilir. Örneğin:
Halo2: PLONK PIOP ve Bulletproofs PCS'nin birleşimi ve Pasta eğrisi temelinde. Halo2 tasarlanırken, ölçeklenebilirliğe odaklanılmıştır ve ZCash protokolündeki trusted setup'ın kaldırılması amaçlanmıştır.
Plonky2: PLONK PIOP ve FRI PCS'nin birleşimini kullanır ve Goldilocks alanına dayanır. Plonky2, verimli bir rekursif 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 olmadan şeffaflık sağlaması, rekursif kanıt veya toplu kanıt gibi genişletilebilir özellikleri destekleyip desteklemeyeceğini de belirler.
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş anahtar teknolojiyi içermektedir. İlk olarak, kule ikili alanlarının (towers of binary fields) aritmetik yapısı, hesaplamalarının temelini oluşturmakta ve ikili alan içinde basitleştirilmiş işlemleri gerçekleştirme yeteneği sunmaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve permütasyon kontrolünü adapte ederek, değişkenler ve bunların permütasyonları arasındaki güvenli ve verimli tutarlılık kontrolünü sağlamaktadır. Üçü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ı getirmektedir. Dördüncüsü, Binius, arama mekanizmasına esneklik ve güçlü bir güvenlik sunan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, ikili alan üzerinde verimli bir kanıt sistemi sağlamak ve genellikle büyük alanlarla ilişkili olan maliyetleri azaltmak için küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.
( 2.1 Sonlu Alan: binary alanların kuleleri üzerine kurulu aritmetik
Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik öneme sahiptir, bu da iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, temelde yüksek verimli aritmetik işlemleri destekler ve 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 hesaplamaların kompakt ve doğrulanması kolay cebirsel biçimde temsil edilebileceği basitleştirilmiş bir aritmetik süreç destekler. Bu özellikler, kule yapısını kullanarak hiyerarşik özelliklerinden tam olarak yararlanma yeteneği ile bir araya geldiğinde, ikili alanları Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirir.
"canonical" terimi, ikili alandaki elemanların eşsiz 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 alanlar belirli bir bit sayısı içinde bu tür bir standart gösterim sağlayamazlar. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dize eşsiz 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 olarak kullanılan indirgeme yöntemleri arasında Barrett indirgemesi, Montgomery indirgemesi ve Mersenne-31 veya Goldilocks-64 gibi belirli sonlu alanlar için ö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'da kullanılan Montgomery indirgemesi ### ve Tower( gibi özyinelemeli indirgeme ) bulunmaktadır. "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 işlem (X + Y )2 = X2 + Y 2'nin 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 alandaki benzersiz bir unsur olarak görülebilir veya iki adet 64 bitlik kule alan unsuru, dört adet 32 bitlik kule alan unsuru, on altı adet 8 bitlik kule alan unsuru veya 128 adet F2 alan unsuru olarak yorumlanabilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, sadece bit dizisinin tür dönüşümü (typecast) ile sağlanır, bu da son derece ilginç ve faydalı bir özellik olarak öne çıkmaktadır. Aynı zamanda, küçük alan unsurları daha büyük alan unsurlarına ek bir hesaplama maliyeti olmadan 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" makalesi, n bitlik kule ikili alanında ('in m bitlik alt alana ) ayrılarak çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.
( 2.2 PIOP: HyperPlonk Ürünü ve Permutasyon Kontrolü için Uygun Olarak Değiştirilmiş Versiyonu------İkili Alan için
Binius protokolündeki PIOP tasarımı HyperPlonk'tan ilham almış, 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:
GateCheck: Gizli tanıklık ω ve açık giriş x'in C)x, ω(=0 devre işlem ilişkisini karşılayıp karşılamadığını doğrulamak için, devrenin doğru çalıştığını sağlamak.
PermutationCheck: İki çok değişkenli çok terimli f ve g'nin Boolean hiperkübündeki değerlendirme sonuçlarının permütasyon ilişkisi olup olmadığını doğrulamak için f)x### = f(π)x() denetimi yapılır ve çok terimli değişkenler arasındaki düzenin tutarlılığı sağlanır.
LookupCheck: Verilen arama tablosunda çok terimli değerlendirmenin doğruluğunu doğrulayın, yani f(Bµ( ⊆ T)Bµ), belirli değerlerin belirtilen aralıkta olduğunu garanti edin.
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.
ProductCheck: Mantıksal hiper kümede rasyonel çok terimli 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.
ZeroCheck: Bir çok değişkenli çok terimli polinomun Boole hiper kü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.
SumCheck: Çok değişkenli çok terimli polinomun toplam değerinin beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol etme. Çok değişkenli polinomun 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 doğrulama örneği için toplu işleme olanak tanır.
BatchCheck: SumCheck temelinde, birden fazla çok değişkenli polinomun değerlerinin doğruluğunu doğrulamak için, protokol verimliliğini artırmak.
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 böylece hesaplama karmaşıklığını azaltır.
Sıfıra bölme sorunlarının çözümü: HyperPlonk, sıfır durumu ile yeterince başa çıkamamaktadır, bu da U'nun hiper küp üzerindeki sıfırdan farklı olduğu sorununu kesin olarak belirlemeyi 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 edebilmekte ve herhangi bir çarpan değerine genişletmeye izin vermektedir.
Sütunlar Arası Permutasyon Kontrolü: HyperPlonk bu özelliğe sahip değil; Binius, birden fazla sütun arasında Permutasyon Kontrolü yapmayı destekler, bu da Binius'un daha karmaşık çok terimli düzenlemeleri işlemesine olanak tanır.
Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasını iyileştirerek protokolün esnekliğini ve verimliliğini artırdı.
![Bitl