Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1. Giriş
STARK'ların düşük verimliliğ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ğerleri, sayaçlar vb. Ancak, Merkle ağacı kanıtlarının güvenliğini sağlamak için, veriyi Reed-Solomon kodlaması ile genişletirken, birçok ek yedek değer tüm alanı kaplamaktadır; oysa orijinal değerler kendileri oldukça küçüktür. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.
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 miktarda israf alanı içermektedir. Bununla karşılaştırıldığında, ikili alan doğrudan bitlerle işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı yoktur, yani 4. nesil STARKs.
Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alan araştırmaları 1980'lerin başlarına kadar uzanır. Günümüzde, ikili alanlar kriptolojide 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 finaline katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve tekrarlama için çok uygun bir hash algoritmasıdır.
Küçük bir alan kullanıldığında, alan genişletme işlemi güvenliğin sağlanmasında giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliğini ve pratik kullanılabilirliğini sağlamak için tamamen alan genişletmeye dayanır. Çoğu Prover hesaplamasında yer alan çok terimli polinomların, genişletme alanına girmesine gerek yoktur; yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. 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 inmeyi gerektirir.
İkili alanlara dayanan bir kanıt sistemi inşa ederken, iki pratik 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üdü yapılırken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutu, kodlama genişletildikten sonraki 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 ifade ederek bunu başardı: İlk olarak, çok değişkenli (, tam olarak çok lineer ) çok terimli yerine tek değişkenli çok terimi kullanarak, "hiperküp" ('deki değerleri ile tüm hesaplama izini ifade etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart bir Reed-Solomon genişletmesi yapmak mümkün değildir, ancak hiperküpü kare ) olarak görebiliriz ve bu kare üzerinden Reed-Solomon genişletmesi yapabiliriz. Bu yöntem, güvenliği sağlarken, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.
2. İlkelerin Analizi
Mevcut çoğu SNARKs sistemi 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 temelini oluşturur ve 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 izin vererek doğrulayıcının sadece birkaç polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulamasını sağlar. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme şekli bakımından farklılık gösterir ve 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 denklemlerinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli bir polinoma 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 bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygun kullanım senaryolarına sahiptir.
Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler seçerek ve uygun sonlu alan veya eliptik eğri ile birleştirerek, 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 tasarımında, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanılmıştır.
• Plonky2: PLONK PIOP ve FRI PCS kombinasyonu kullanılarak 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'nin kullanılan sonlu alan veya eliptik eğri ile eşleşmesi gerekmektedir, 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ığı gerçekleştirme yeteneğini, rekürsif kanıtlar veya toplu kanıtlar gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknik içermektedir. İlk olarak, kule biçimindeki ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamanın temelini oluşturmakta olup, ikili alan içinde basitleştirilmiş hesaplamalar gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP)'unda, HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlayarak, değişkenler ile yer değiştirmeleri 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ü güvenlik sunan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi sağlamasına ve genellikle büyük alanlarla ilişkili maliyetleri azaltmasına olanak tanımaktadır.
( 2.1 Sonlu Alanlar: binary alanların kuleleri üzerine kurulu aritmetik
Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir rol oynamaktadır; bu, esasen iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alanlar, yüksek verimli aritmetik işlemleri desteklemeleri nedeniyle, performans gereksinimleri açısından hassas olan kriptografik uygulamalar için ideal bir seçimdir. 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 işlemi sürecini desteklemektedir. Bu özellikler ve kule yapısı aracılığıyla hiyerarşik özelliklerini tam olarak kullanma yeteneği, ikili alanları Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirmektedir.
"canonical" terimi, ikili alandaki öğelerin benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k bitlik dizi doğrudan k bitlik bir ikili alan öğesine haritalanabilir. Bu, asal alanlardan farklıdır, çünkü asal alan belirli bir bit sayısı içinde bu tür bir standart temsili sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dizi benzersiz bir alan öğesine karşılık gelmez; oysa ikili alan bu 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 bulunur. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma ), AES'te kullanılan ###, Montgomery azaltması (, POLYVAL'da kullanılan ) ve tekrarlamalı azaltma (, Tower) gibi yöntemler vardır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı makalede, ikili alanın toplama ve çarpma işlemlerinde taşıma eklemek zorunda kalmadığı ve ikili alanın kare alma işleminin oldukça verimli olduğu belirtilmiştir, çünkü bu, (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 alanında 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 çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizisinin tür dönüşümünü (typecast) gerektirir ve bu oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama yükü 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' adlı makale, n bitlik kule benzeri ikili alanında ('in m bitlik alt alanına ) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.
( 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üme doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunlardır:
GateCheck: Gizli tanık ω ve kamu girişi x'in devre hesaplama ilişkesi C)x,ω###=0'ı sağladığını doğrulamak için, devrenin doğru çalıştığından emin olun.
PermutationCheck: İki çok değişkenli çok terim f ve g'nin Bool hiper küpündeki değerleme sonuçlarının bir permütasyon ilişkisi olup olmadığını doğrulayın f(x) = f(π)x((, çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak için.
LookupCheck: Çoklu polinomların değerlendirilmesinin verilen arama tablosunda doğrulanması, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olmak.
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ığı sağlar.
ProductCheck: Mantıksal hiperküp üzerindeki rasyonel çok terimli polinomun bir beyan değerine eşit olup olmadığını kontrol etme ∏x∈Hµ f(x) = s, polinom çarpımının doğruluğunu sağlamak için.
ZeroCheck: Bir çok değişkenli çok terimli bir polinomun Boolean 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 noktalarının dağılımını sağlamak için.
SumCheck: Çok değişkenli çok terimli polinomun toplamının, beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol etme. Çok değişkenli polinomun değerlendirme sorununu, tek değişkenli polinom değerlendirmesine dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar getirerek, birden fazla toplam kontrol örneği için toplu işlemi gerçekleştirmek için lineer kombinasyonlar oluşturulmasına da izin verir.
BatchCheck: SumCheck'e dayanarak, 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, HyperPlonk ile protokol tasarımında birçok benzerliğe sahip olmasına rağmen, aşağıdaki 3 alanda geliştirmeler yapmıştır:
ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in, paydanın U'nun hiperküp üzerinde 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 problemiyle başa çıkma: HyperPlonk sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküpte sıfır olmayan bir değer olduğunu kesin olarak belirlemeyi imkansız hale getirdi; Binius bu durumu doğru bir şekilde ele aldı, sıfır olan bir payda bile olsa, Binius'un ProductCheck'i işlemeye devam edebildi ve herhangi bir çarpım değerine genişletilmesine izin verdi.
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ı ele almasını sağlıyor.
Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasında yaptığı iyileştirmelerle protokolün esnekliğini ve verimliliğini artırdı; özellikle daha karmaşık çok değişkenli polinom doğrulama işlemlerinde daha güçlü işlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayanan kanıt sistemleri için bir temel oluşturdu.
( 2.3 PIOP: yeni çoklu kaydırma argümanı------boolean hiper küp için uygun
Binius protokolünde, sanal çok terimli ifadelerin yapımı ve işlenmesi, giriş kollarından veya diğer sanal çok terimli ifadelerden türetilen çok terimlilerin etkin bir şekilde üretilmesi ve işlenmesi için anahtar teknolojilerden biridir. İşte iki temel yöntem:
Paketleme: Bu yöntem geçerli
View Original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Binius STARKs: İkili alanın yenilikçi uygulamaları ve performans optimizasyonu
Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1. Giriş
STARK'ların düşük verimliliğ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ğerleri, sayaçlar vb. Ancak, Merkle ağacı kanıtlarının güvenliğini sağlamak için, veriyi Reed-Solomon kodlaması ile genişletirken, birçok ek yedek değer tüm alanı kaplamaktadır; oysa orijinal değerler kendileri oldukça küçüktür. Bu sorunu çözmek için, alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.
Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alan araştırmaları 1980'lerin başlarına kadar uzanır. Günümüzde, ikili alanlar kriptolojide 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 finaline katılan Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve tekrarlama için çok uygun bir hash algoritmasıdır.
Küçük bir alan kullanıldığında, alan genişletme işlemi güvenliğin sağlanmasında giderek daha önemli hale gelir. Binius'un kullandığı ikili alan, güvenliğini ve pratik kullanılabilirliğini sağlamak için tamamen alan genişletmeye dayanır. Çoğu Prover hesaplamasında yer alan çok terimli polinomların, genişletme alanına girmesine gerek yoktur; yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlanır. 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 inmeyi gerektirir.
İkili alanlara dayanan bir kanıt sistemi inşa ederken, iki pratik 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üdü yapılırken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan boyutu, kodlama genişletildikten sonraki 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 ifade ederek bunu başardı: İlk olarak, çok değişkenli (, tam olarak çok lineer ) çok terimli yerine tek değişkenli çok terimi kullanarak, "hiperküp" ('deki değerleri ile tüm hesaplama izini ifade etti; İkincisi, hiperküpün her bir boyutunun uzunluğu 2 olduğundan, STARKs gibi standart bir Reed-Solomon genişletmesi yapmak mümkün değildir, ancak hiperküpü kare ) olarak görebiliriz ve bu kare üzerinden Reed-Solomon genişletmesi yapabiliriz. Bu yöntem, güvenliği sağlarken, kodlama verimliliğini ve hesaplama performansını büyük ölçüde artırdı.
2. İlkelerin Analizi
Mevcut çoğu SNARKs sistemi 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 temelini oluşturur ve 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 izin vererek doğrulayıcının sadece birkaç polinomun değerlendirme sonuçlarını sorgulayarak hesaplamanın doğru olup olmadığını doğrulamasını sağlar. Mevcut PIOP protokolleri arasında: PLONK PIOP, Spartan PIOP ve HyperPlonk PIOP gibi protokoller bulunmaktadır; bunlar, polinom ifadelerinin işlenme şekli bakımından farklılık gösterir ve 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 denklemlerinin geçerliliğini kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araç sayesinde, kanıtlayıcı belirli bir polinoma 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 bulunmaktadır. Farklı PCS'ler, farklı performans, güvenlik ve uygun kullanım senaryolarına sahiptir.
Belirli ihtiyaçlara göre farklı PIOP ve PCS'ler seçerek ve uygun sonlu alan veya eliptik eğri ile birleştirerek, 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 tasarımında, ölçeklenebilirliğe ve ZCash protokolündeki güvenilir kurulumun kaldırılmasına odaklanılmıştır.
• Plonky2: PLONK PIOP ve FRI PCS kombinasyonu kullanılarak 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'nin kullanılan sonlu alan veya eliptik eğri ile eşleşmesi gerekmektedir, 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ığı gerçekleştirme yeteneğini, rekürsif kanıtlar veya toplu kanıtlar gibi genişletme işlevlerini destekleyip destekleyemeyeceğini de belirler.
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Özellikle, Binius, verimliliğini ve güvenliğini sağlamak için beş ana teknik içermektedir. İlk olarak, kule biçimindeki ikili alanların (towers of binary fields) aritmetik yapısı, hesaplamanın temelini oluşturmakta olup, ikili alan içinde basitleştirilmiş hesaplamalar gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP)'unda, HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlayarak, değişkenler ile yer değiştirmeleri 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ü güvenlik sunan geliştirilmiş Lasso arama kanıtını kullanmaktadır. Son olarak, protokol, küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanarak, ikili alan üzerinde verimli bir kanıt sistemi sağlamasına ve genellikle büyük alanlarla ilişkili maliyetleri azaltmasına olanak tanımaktadır.
( 2.1 Sonlu Alanlar: binary alanların kuleleri üzerine kurulu aritmetik
Kule tipi ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde kritik bir rol oynamaktadır; bu, esasen iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alanlar, yüksek verimli aritmetik işlemleri desteklemeleri nedeniyle, performans gereksinimleri açısından hassas olan kriptografik uygulamalar için ideal bir seçimdir. 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 işlemi sürecini desteklemektedir. Bu özellikler ve kule yapısı aracılığıyla hiyerarşik özelliklerini tam olarak kullanma yeteneği, ikili alanları Binius gibi ölçeklenebilir kanıt sistemleri için özellikle uygun hale getirmektedir.
"canonical" terimi, ikili alandaki öğelerin benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan F2'de, herhangi bir k bitlik dizi doğrudan k bitlik bir ikili alan öğesine haritalanabilir. Bu, asal alanlardan farklıdır, çünkü asal alan belirli bir bit sayısı içinde bu tür bir standart temsili sağlayamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilir, ancak her 32 bitlik dizi benzersiz bir alan öğesine karşılık gelmez; oysa ikili alan bu 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 bulunur. İkili alan F2k'de yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma ), AES'te kullanılan ###, Montgomery azaltması (, POLYVAL'da kullanılan ) ve tekrarlamalı azaltma (, Tower) gibi yöntemler vardır. "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" adlı makalede, ikili alanın toplama ve çarpma işlemlerinde taşıma eklemek zorunda kalmadığı ve ikili alanın kare alma işleminin oldukça verimli olduğu belirtilmiştir, çünkü bu, (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 alanında 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 çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama yükü gerektirmeden, yalnızca bit dizisinin tür dönüşümünü (typecast) gerektirir ve bu oldukça ilginç ve yararlı bir özelliktir. Aynı zamanda, küçük alan unsurları, ek bir hesaplama yükü 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' adlı makale, n bitlik kule benzeri ikili alanında ('in m bitlik alt alanına ) çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.
( 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üme doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunlardır:
GateCheck: Gizli tanık ω ve kamu girişi x'in devre hesaplama ilişkesi C)x,ω###=0'ı sağladığını doğrulamak için, devrenin doğru çalıştığından emin olun.
PermutationCheck: İki çok değişkenli çok terim f ve g'nin Bool hiper küpündeki değerleme sonuçlarının bir permütasyon ilişkisi olup olmadığını doğrulayın f(x) = f(π)x((, çok terimli değişkenler arasındaki sıralamanın tutarlılığını sağlamak için.
LookupCheck: Çoklu polinomların değerlendirilmesinin verilen arama tablosunda doğrulanması, yani f)Bµ) ⊆ T(Bµ), belirli değerlerin belirtilen aralıkta olduğundan emin olmak.
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ığı sağlar.
ProductCheck: Mantıksal hiperküp üzerindeki rasyonel çok terimli polinomun bir beyan değerine eşit olup olmadığını kontrol etme ∏x∈Hµ f(x) = s, polinom çarpımının doğruluğunu sağlamak için.
ZeroCheck: Bir çok değişkenli çok terimli bir polinomun Boolean 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 noktalarının dağılımını sağlamak için.
SumCheck: Çok değişkenli çok terimli polinomun toplamının, beyan edilen değerle ∑x∈Hµ f(x) = s olup olmadığını kontrol etme. Çok değişkenli polinomun değerlendirme sorununu, tek değişkenli polinom değerlendirmesine dönüştürerek doğrulayıcı tarafın hesaplama karmaşıklığını azaltır. Ayrıca, SumCheck rastgele sayılar getirerek, birden fazla toplam kontrol örneği için toplu işlemi gerçekleştirmek için lineer kombinasyonlar oluşturulmasına da izin verir.
BatchCheck: SumCheck'e dayanarak, 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, HyperPlonk ile protokol tasarımında birçok benzerliğe sahip olmasına rağmen, aşağıdaki 3 alanda geliştirmeler yapmıştır:
ProductCheck optimizasyonu: HyperPlonk'ta, ProductCheck'in, paydanın U'nun hiperküp üzerinde 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 problemiyle başa çıkma: HyperPlonk sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküpte sıfır olmayan bir değer olduğunu kesin olarak belirlemeyi imkansız hale getirdi; Binius bu durumu doğru bir şekilde ele aldı, sıfır olan bir payda bile olsa, Binius'un ProductCheck'i işlemeye devam edebildi ve herhangi bir çarpım değerine genişletilmesine izin verdi.
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ı ele almasını sağlıyor.
Bu nedenle, Binius mevcut PIOPSumCheck mekanizmasında yaptığı iyileştirmelerle protokolün esnekliğini ve verimliliğini artırdı; özellikle daha karmaşık çok değişkenli polinom doğrulama işlemlerinde daha güçlü işlevsellik sağladı. Bu iyileştirmeler yalnızca HyperPlonk'taki sınırlamaları çözmekle kalmadı, aynı zamanda gelecekte ikili alanlara dayanan kanıt sistemleri için bir temel oluşturdu.
( 2.3 PIOP: yeni çoklu kaydırma argümanı------boolean hiper küp için uygun
Binius protokolünde, sanal çok terimli ifadelerin yapımı ve işlenmesi, giriş kollarından veya diğer sanal çok terimli ifadelerden türetilen çok terimlilerin etkin bir şekilde üretilmesi ve işlenmesi için anahtar teknolojilerden biridir. İşte iki temel yöntem: