Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1. Giriş
Elliptik eğri tabanlı SNARK'lardan farklı olarak, STARK'lar hash tabanlı SNARK'lar olarak düşünülebilir. Mevcut STARK'ların verimsiz olmasının başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu sayı küçüktür, örneğin for döngüsündeki indeksler, boolean değerler, sayaçlar vb. Ancak, Merkle ağaçları tabanlı kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında, birçok ek gereksiz değer tüm alanı kaplar, bu nedenle orijinal değerler çok küçük olsa bile. Bu sorunu çözmek için alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.
nesil STARKs kodlama bit genişliği 252bit, 2. nesil STARKs kodlama bit genişliği 64bit, 3. nesil STARKs kodlama bit genişliği 32bit, ancak 32bit kodlama bit genişliği hala büyük miktarda israf alanı bulunmaktadır. Karşılaştırıldığında, ikili alan doğrudan bitler üzerinde işlem yapmaya izin verir, kodlama sıkı ve verimli olup herhangi bir israf alanı olmadan, yani 4. nesil STARKs.
Goldilocks, BabyBear, Mersenne31 gibi son yıllarda keşfedilen sonlu alanlara kıyasla, ikili alanların araştırması 1980'lere kadar uzanıyor. 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 dayanıyor;
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 giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve yinelemeli hash algoritmaları için oldukça 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 garanti etmek için tamamen genişletmeye bağlıdır. Çoğu Prover hesaplamasında yer alan polinomlar genişletme alanına girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlamaktadır. Ancak, rastgele nokta kontrolleri 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 dayalı bir kanıt sistemi oluştururken, iki pratik sorun vardır: STARKs'ta izlerin temsilinde kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağaçları taahhüt edilirken, Reed-Solomon kodlaması yapılmalıdır ve kullanılan alanın boyutu kodlama genişletildikten 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 (, özellikle çoklu lineer ) polinomları tek değişkenli polinomlar yerine kullanılarak, "hiperküpler" ( üzerindeki değerleri ile tüm hesaplama yolunu 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 dayalı olarak 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 kısmı içerir:
Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin merkezi olarak, girilen hesaplama ilişkisini doğrulanabilir polinom eşitliğine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının polinomları adım adım 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ı sorgulayabilir. 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österir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.
Polinom Taahhüt Şeması (Polinom Commitment Scheme, PCS): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denkleminin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araçla, 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 ihtiyaçlara göre, farklı PIOP ve PCS'ler seçilebilir ve uygun sonlu alan veya eliptik eğri ile birleştirilerek farklı özelliklere sahip bir kanıt sistemi 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ı, ölçeklenebilirlik ve ZCash protokolündeki güvenilir kurulumun ortadan kaldırılmasına odaklanmıştır.
• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimi kullanılarak ve Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir rekürsif 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 sadece SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar gerekmeksizin şeffaflık sağlayıp sağlayamayacağını, rekürsif kanıtlar veya toplama kanıtları gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini de belirler.
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş temel teknoloji içermektedir. Öncelikle, kuleler üzerine inşa edilmiş ikili alan (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturmakta ve ikili alan içinde sadeleştirilmiş hesaplamalar gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlayarak, değişkenler ve bunların yer değiştirmeleri arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı tanıtmaktadır. Dördüncüsü, Binius, arama mekanizmesine 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 sağlamak ve genellikle büyük alanlarla ilişkili yükleri azaltmak için küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.
( 2.1 Sınırlı Alan: binary alanlar üzerindeki kuleler temelinde aritmetik
Kule tipi ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde önemli bir rol oynamaktadır; bu, iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, özünde 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ı, aritmetik süreçleri basitleştirir; yani, ikili alanda gerçekleştirilen işlemler, sıkı ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir. Bu özellikler, kule yapısı aracılığıyla 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.
Burada "canonical", ikili alanlardaki elemanların benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan olan F2'de, herhangi bir k bitlik dize doğrudan k bitlik bir ikili alan elemanına eşlenebilir. Bu, asal alanların aksine, asal alan belirli bit sayısı içinde bu tür standart bir temsil sunamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilirken, her 32 bitlik dize 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 AES'te kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower( gibi rekürsif azaltma ) yer alı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 getirmeden çalıştığını ve ikili alanın kare alma işleminin son derece verimli olduğunu belirtmektedir; çünkü bu, (X + Y )2 = X2 + Y 2 basitleştirilmiş 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 benzersiz bir öğe olarak görü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 çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümünü(typecast) gerçekleştirir; bu da oldukça ilginç ve faydalı bir özelliktir. Ayrıca, küçük alan öğeleri, ek bir hesaplama maliyeti olmaksızın daha büyük alan öğelerine 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ı makale, n bitlik kule benzeri ikili alanda(, m bitlik alt alan) bölünerek çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.
( 2.2 PIOP: uyarlama HyperPlonk Ürünü ve PermutationCheck------ikili alan için uygundur
Binius protokolündeki PIOP tasarımı HyperPlonk'tan yararlanmakta 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 şunları içerir:
GateCheck: Gizli tanık ω ve kamu girişi x'in, devre hesaplama ilişkisi C)x,ω(=0'ı sağlayıp sağlamadığını doğrulamak için devrenin doğru çalıştığından emin olun.
PermutationCheck: İki çok değişkenli polinom f ve g'nin boolean hiperküpteki değerlerinin 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.
LookupCheck: Çoklu polinomun değerlendirmesinin verilen arama tablosunda olup olmadığını doğrulayın, yani f(Bμ( ⊆ T)Bμ), belirli değerlerin belirtilen aralıkta olduğunu güvence altına alın.
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 hiperküp üzerindeki rasyonel çok üyeli bir polinomun değerlendirilmesinin 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 sağlamak içindir.
ZeroCheck: Bir çok değişkenli çok terimli bir polinomun Boole hiper küpündeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏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ğer olup olmadığını kontrol eder ∑x∈Hμ f(x) = s. Çok değişkenli polinomun 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 getirerek, birden fazla toplam kontrol örneğini toplu işleme gerçekleştirmek için lineer kombinasyonlar oluşturmasına da olanak tanır.
BatchCheck: SumCheck'e dayalı olarak, çoklu çok değişkenli polinom 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'in paydası 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 sorununun işlenmesi: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküp üzerindeki sıfır olmayan durumunu kesin olarak belirleyemedi; Binius bu sorunu doğru bir şekilde işledi, sıfır paydası olsa bile, Binius'in ProductCheck'i işlemeye devam edebilir ve herhangi bir çarpan değerine genişletilmesine izin verir.
Sütunlar Arası PermutationCheck: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında PermutationCheck'i destekleyerek daha karmaşık çok terimli sıralama durumlarını işleyebilmesini sağlıyor.
Bu nedenle, Binius aracılığıyla
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 altında verimli zk-SNARKs sistemi
Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1. Giriş
Elliptik eğri tabanlı SNARK'lardan farklı olarak, STARK'lar hash tabanlı SNARK'lar olarak düşünülebilir. Mevcut STARK'ların verimsiz olmasının başlıca nedenlerinden biri şudur: Gerçek programlardaki çoğu sayı küçüktür, örneğin for döngüsündeki indeksler, boolean değerler, sayaçlar vb. Ancak, Merkle ağaçları tabanlı kanıtların güvenliğini sağlamak için Reed-Solomon kodlaması ile verilerin genişletilmesi sırasında, birçok ek gereksiz değer tüm alanı kaplar, bu nedenle orijinal değerler çok küçük olsa bile. 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 alanların araştırması 1980'lere kadar uzanıyor. 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 dayanıyor;
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 giren Grøstl hash fonksiyonu, F28 alanına dayanmaktadır ve yinelemeli hash algoritmaları için oldukça 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 garanti etmek için tamamen genişletmeye bağlıdır. Çoğu Prover hesaplamasında yer alan polinomlar genişletme alanına girmeden, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlamaktadır. Ancak, rastgele nokta kontrolleri 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 dayalı bir kanıt sistemi oluştururken, iki pratik sorun vardır: STARKs'ta izlerin temsilinde kullanılan alanın boyutu, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağaçları taahhüt edilirken, Reed-Solomon kodlaması yapılmalıdır ve kullanılan alanın boyutu kodlama genişletildikten 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 (, özellikle çoklu lineer ) polinomları tek değişkenli polinomlar yerine kullanılarak, "hiperküpler" ( üzerindeki değerleri ile tüm hesaplama yolunu 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 dayalı olarak 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 kısmı içerir:
Bilgi Teorisi Polinom Etkileşimli Oracle Kanıtı ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, kanıt sisteminin merkezi olarak, girilen hesaplama ilişkisini doğrulanabilir polinom eşitliğine dönüştürür. Farklı PIOP protokolleri, doğrulayıcı ile etkileşim yoluyla, kanıtlayıcının polinomları adım adım 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ı sorgulayabilir. 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österir ve bu da tüm SNARK sisteminin performansını ve verimliliğini etkiler.
Polinom Taahhüt Şeması (Polinom Commitment Scheme, PCS): Polinom taahhüt şeması, PIOP tarafından üretilen polinom denkleminin geçerli olup olmadığını kanıtlamak için kullanılır. PCS, bir kriptografik araçtır; bu araçla, 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 ihtiyaçlara göre, farklı PIOP ve PCS'ler seçilebilir ve uygun sonlu alan veya eliptik eğri ile birleştirilerek farklı özelliklere sahip bir kanıt sistemi 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ı, ölçeklenebilirlik ve ZCash protokolündeki güvenilir kurulumun ortadan kaldırılmasına odaklanmıştır.
• Plonky2: PLONK PIOP ve FRI PCS'nin birleşimi kullanılarak ve Goldilocks alanına dayanarak geliştirilmiştir. Plonky2, verimli bir rekürsif 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 sadece SNARK'ın kanıt boyutunu ve doğrulama verimliliğini etkilemekle kalmaz, aynı zamanda sistemin güvenilir bir ayar gerekmeksizin şeffaflık sağlayıp sağlayamayacağını, rekürsif kanıtlar veya toplama kanıtları gibi genişletilebilir özellikleri destekleyip destekleyemeyeceğini de belirler.
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Spesifik olarak, Binius, verimliliğini ve güvenliğini sağlamak için beş temel teknoloji içermektedir. Öncelikle, kuleler üzerine inşa edilmiş ikili alan (towers of binary fields) aritmetiği, hesaplamalarının temelini oluşturmakta ve ikili alan içinde sadeleştirilmiş hesaplamalar gerçekleştirilmesine olanak tanımaktadır. İkincisi, Binius, etkileşimli Oracle kanıt protokolü (PIOP) içinde, HyperPlonk çarpım ve yer değiştirme kontrolünü uyarlayarak, değişkenler ve bunların yer değiştirmeleri arasında güvenli ve verimli bir tutarlılık kontrolü sağlamaktadır. Üçüncüsü, protokol, küçük alanlarda çoklu ilişkilerin doğrulanma verimliliğini optimize eden yeni bir çoklu doğrulama kaydırma kanıtı tanıtmaktadır. Dördüncüsü, Binius, arama mekanizmesine 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 sağlamak ve genellikle büyük alanlarla ilişkili yükleri azaltmak için küçük alan polinom taahhüt şemasını (Small-Field PCS) kullanmaktadır.
( 2.1 Sınırlı Alan: binary alanlar üzerindeki kuleler temelinde aritmetik
Kule tipi ikili alan, hızlı ve doğrulanabilir hesaplamaların gerçekleştirilmesinde önemli bir rol oynamaktadır; bu, iki ana nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, özünde 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ı, aritmetik süreçleri basitleştirir; yani, ikili alanda gerçekleştirilen işlemler, sıkı ve doğrulanması kolay cebirsel biçimlerde temsil edilebilir. Bu özellikler, kule yapısı aracılığıyla 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.
Burada "canonical", ikili alanlardaki elemanların benzersiz ve doğrudan temsil biçimini ifade eder. Örneğin, en temel ikili alan olan F2'de, herhangi bir k bitlik dize doğrudan k bitlik bir ikili alan elemanına eşlenebilir. Bu, asal alanların aksine, asal alan belirli bit sayısı içinde bu tür standart bir temsil sunamaz. 32 bitlik bir asal alan 32 bit içinde yer alabilirken, her 32 bitlik dize 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 AES'te kullanılan özel azaltma ), POLYVAL'de kullanılan Montgomery azaltması ### ve Tower( gibi rekürsif azaltma ) yer alı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 getirmeden çalıştığını ve ikili alanın kare alma işleminin son derece verimli olduğunu belirtmektedir; çünkü bu, (X + Y )2 = X2 + Y 2 basitleştirilmiş 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 benzersiz bir öğe olarak görü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 çözümlenebilir. Bu temsilin esnekliği, herhangi bir hesaplama maliyeti gerektirmeden, yalnızca bit dizisinin tür dönüşümünü(typecast) gerçekleştirir; bu da oldukça ilginç ve faydalı bir özelliktir. Ayrıca, küçük alan öğeleri, ek bir hesaplama maliyeti olmaksızın daha büyük alan öğelerine 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ı makale, n bitlik kule benzeri ikili alanda(, m bitlik alt alan) bölünerek çarpma, kare alma ve ters alma işlemlerinin hesaplama karmaşıklığını incelemektedir.
( 2.2 PIOP: uyarlama HyperPlonk Ürünü ve PermutationCheck------ikili alan için uygundur
Binius protokolündeki PIOP tasarımı HyperPlonk'tan yararlanmakta 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 şunları içerir:
GateCheck: Gizli tanık ω ve kamu girişi x'in, devre hesaplama ilişkisi C)x,ω(=0'ı sağlayıp sağlamadığını doğrulamak için devrenin doğru çalıştığından emin olun.
PermutationCheck: İki çok değişkenli polinom f ve g'nin boolean hiperküpteki değerlerinin 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.
LookupCheck: Çoklu polinomun değerlendirmesinin verilen arama tablosunda olup olmadığını doğrulayın, yani f(Bμ( ⊆ T)Bμ), belirli değerlerin belirtilen aralıkta olduğunu güvence altına alın.
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 hiperküp üzerindeki rasyonel çok üyeli bir polinomun değerlendirilmesinin 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 sağlamak içindir.
ZeroCheck: Bir çok değişkenli çok terimli bir polinomun Boole hiper küpündeki herhangi bir noktada sıfır olup olmadığını doğrulamak ∏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ğer olup olmadığını kontrol eder ∑x∈Hμ f(x) = s. Çok değişkenli polinomun 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 getirerek, birden fazla toplam kontrol örneğini toplu işleme gerçekleştirmek için lineer kombinasyonlar oluşturmasına da olanak tanır.
BatchCheck: SumCheck'e dayalı olarak, çoklu çok değişkenli polinom 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'in paydası 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 sorununun işlenmesi: HyperPlonk, sıfıra bölme durumunu yeterince ele alamadı, bu da U'nun hiperküp üzerindeki sıfır olmayan durumunu kesin olarak belirleyemedi; Binius bu sorunu doğru bir şekilde işledi, sıfır paydası olsa bile, Binius'in ProductCheck'i işlemeye devam edebilir ve herhangi bir çarpan değerine genişletilmesine izin verir.
Sütunlar Arası PermutationCheck: HyperPlonk bu özelliği desteklemiyor; Binius, birden fazla sütun arasında PermutationCheck'i destekleyerek daha karmaşık çok terimli sıralama durumlarını işleyebilmesini sağlıyor.
Bu nedenle, Binius aracılığıyla