Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1 Giriş
STARK'ların verimsizliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır; ancak Merkle ağacı kanıtlarının güvenliğini sağlamak için, verileri genişletirken Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değeri tüm alanı kaplar. 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 64 bit, 3. nesil 32 bit, ancak 32 bit kodlama genişliği hala büyük miktarda israf alanı barındırmaktadır. Karşılaştırıldığında, ikili alan doğrudan bitlerin üzerinde işlem yapmaya olanak tanır, kodlama kompakt ve verimlidir ve herhangi bir israf alanı yoktur, yani 4. nesil STARKs.
Küçük bir alan kullanıldığında, 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 genişletmeye dayanır. Çoğu Prover hesaplamasında yer alan çok terimli ifadeler genişletme alanına girmek zorunda kalmadan, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, istenen güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmeyi gerektirir.
İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin temsilini hesaplamak için kullanılan alan büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan büyüklüğü, kodlama genişletildikten sonra elde edilen büyüklüğünden büyük olmalıdır.
Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önermiştir ve aynı veriyi iki farklı şekilde temsil ederek bunu gerçekleştirmiştir: Öncelikle, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerleri ile tüm hesaplama izini temsil etmektedir; ikincisi, hiperküpün her boyutunun uzunluğunun 2 olması nedeniyle STARKs gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare olarak düşünülebilir ve bu kare temel alınarak 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:
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliği ve güvenliğini sağlamak için beş ana teknolojiyi içermektedir:
Kule tipi ikili alanına dayalı aritmetik
Yeniden Düzenlenmiş HyperPlonk Çarpımı ve Permütasyon Kontrolü
Yeni Çoklu Kaydırma Tezi
Geliştirilmiş Lasso bulma kanıtı
Küçük Alan Çoklu Taahhüt Planı
2.1 Sonlu Alanlar: binary alanların kuleleri üzerine kurulu aritmetik
Kuyruklu ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynar, bu da iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, doğası gereği yüksek verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş aritmetik süreci destekler; yani ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde ifade edilebilir.
Fp asal alanında, yaygın olarak kullanılan 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 bulunmaktadır. İkili alanda F2k, yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma (AES'te kullanılan), Montgomery azaltması (POLYVAL'da kullanılan) ve özyinelemeli azaltma (Tower gibi) bulunmaktadır.
İkili alan, toplama ve çarpma işlemlerinde taşma gerektirmeden çalışır ve ikili alanın kare alma işlemi oldukça etkilidir, çünkü (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralını takip eder.
2.2 PIOP: Uyarlama Versiyonu HyperPlonk Ürünü ve Permutasyon Kontrolü
Binius protokolündeki PIOP tasarımı HyperPlonk'tan esinlenmiştir ve çok terimli ve çok değişkenli kümenin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ÜrünKontrol
ZeroCheck
Toplam Kontrol
BatchCheck
Binius, HyperPlonk ile karşılaştırıldığında aşağıdaki geliştirmeleri yapmıştır:
ProductCheck optimizasyonu
Sıfır bölme sorununun çözümü
Sütunlar Arası Permutasyon Kontrolü
2.3 PIOP: yeni çoklu kaydırma argümanı
Binius protokolünde, sanal çok terimli yapıların inşası ve işlenmesi, giriş kollarından veya diğer sanal çok terimlerden türetilen çok terimlerin etkin bir şekilde üretilmesi ve işlenmesini sağlayan anahtar teknolojilerden biridir. İşte iki anahtar yöntem:
Paketleme
Kaydırma Operatörü
2.4 PIOP: Uyarlama Lasso arama argümanı
Lasso protokolu, kanıtlayıcının bir vektör a ∈ Fm taahhüt etmesine ve tüm elemanlarının önceden belirlenmiş bir tablo t ∈ Fn içinde bulunduğunu kanıtlamasına olanak tanır. Lasso protokolü aşağıdaki üç bileşenden oluşur:
Büyük tablonun sanal çoklu polinom soyutlaması
Küçük tablo arama
Çoklu küme kontrolü
Binius protokolü Lasso'yu ikili alan işlemlerine uyarlayarak Lasso protokolünün çarpan versiyonunu tanıttı.
2.5 PCS：uyarlama Brakedown PCS
BiniusPCS'nin temel fikri packing'tir. Binius belgesinde, ikili alana dayalı iki Brakedown çoktam sayısı taahhüt çözümü sunulmuştur:
Concatenated kod kullanarak örnekleme yapın
Block-level encoding teknolojisini kullanarak, Reed-Solomon kodlarını ayrı olarak destekler.
Binius çok terimli taahhüt temel olarak aşağıdaki teknolojileri kullanır:
Küçük alan çoklu taahhütleri ve genişletilmiş alan değerlendirmesi
Küçük alan genel yapısı
Blok kodlama ve Reed-Solomon kodu
3 Optimizasyon Düşüncesi
Binius protokolünün performansını daha da artırmak için bu makalede dört ana optimizasyon noktası önerilmektedir:
GKR tabanlı PIOP: İkili alan çarpım işlemleri için
ZeroCheck PIOP optimizasyonu: Prover ile Verifier arasında hesaplama yükü dengesi sağlamak
Sumcheck PIOP optimizasyonu: Küçük alan Sumcheck için optimizasyon
PCS optimizasyonu: FRI-Binius ile optimizasyon
3.1 GKR tabanlı PIOP: GKR'ye dayalı ikili alan çarpımı
GKR'ye dayalı tam sayı çarpma işlemi algoritması, "iki 32-bit tam sayısı A ve B'nin A·B =? C'yi sağladığını kontrol et" ifadesini, "(gA)B =? gC'nin geçerli olup olmadığını kontrol et" ifadesine dönüştürerek, GKR protokolü sayesinde taahhüt maliyetlerini önemli ölçüde azaltır.
3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi
Makale "ZeroCheck için PIOP'ta Bazı İyileştirmeler", ispatlayıcı (P) ve doğrulayıcı (V) arasında iş yükü dağılımını ayarlayarak, maliyetleri dengelemek için çeşitli optimizasyon önerileri sunmaktadır. Ana optimizasyonlar şunları içerir:
3.3 Sumcheck PIOP optimizasyonu: Küçük alanlara dayalı Sumcheck protokolü
Ingonyama, 2024 yılında küçük alanlara dayalı Sumcheck protokolü için geliştirme önerisinde bulundu ve uygulama kodunu açık kaynak olarak yayınladı. Ana optimizasyonlar şunlardır:
"Binary Towers Üzerinde Çoklu Doğrusalara Yönelik Polilogaritmik Kanıtlar" başlıklı makale, kısaca FRI-Binius, ikili alan FRI katlama mekanizmasını gerçekleştirmiştir ve 4 alanda yenilik sunmaktadır:
Düzleştirilmiş Çokgen
Alt alan kaybolma polinomu
Cebir Temel Paketleme
Çember Değişimi SumCheck
FRI-Binius sayesinde, Binius kanıt boyutunu bir büyüklük derecesi azaltabilirsiniz.
4 Özet
Binius, "donanım, yazılım ve FPGA'da hızlandırılmış Sumcheck protokolü kullanan" bir işbirliği tasarım çözümüdür ve çok düşük bellek kullanımı ile hızlı bir şekilde kanıt sağlamaktadır. Binius'ta Prover'ın commit taahhüt darboğazı temel olarak tamamen ortadan kaldırılmıştır, yeni darboğaz Sumcheck protokolündedir ve Sumcheck protokolündeki çok sayıda polinom değerlendirmesi ve alan çarpımı gibi sorunlar, özel donanım sayesinde verimli bir şekilde çözülmektedir.
FRI-Binius çözümü, FRI varyantı için, alan kanıtı katmanından gömülü maliyetleri ortadan kaldırırken, birleşik kanıt katmanının maliyetlerinin ani bir artışına neden olmayacak son derece çekici bir seçenek sunmaktadır. Şu anda, Irreducible ekibi kendi yinelemeli katmanını geliştirmekte ve Polygon ekibi ile birlikte Binius tabanlı zkVM inşa etmek için işbirliği yaptıklarını duyurmaktadır; JoltzkVM, yineleme performansını artırmak için Lasso'dan Binius'a geçmektedir; Ingonyama ekibi, Binius'un FPGA versiyonunu uygulamaktadır.
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.
26 Likes
Reward
26
8
Repost
Share
Comment
0/400
AirdropF5Bro
· 3h ago
Ohho bu Starknet görünümü!
View OriginalReply0
¯\_(ツ)_/¯
· 19h ago
Bu optimizasyon da ne kadar güçlü, 252'den ikiliye.
View OriginalReply0
SerumSquirter
· 08-10 20:16
Verimlilik giderek artıyor, alan giderek küçülüyor.
View OriginalReply0
GateUser-afe07a92
· 08-10 09:35
Ne kadar sıkıcı, bir sonraki
View OriginalReply0
ForkTongue
· 08-10 09:20
Gerçekten iyi yazılmış ama profesyonel olanı anlamadım...
View OriginalReply0
NullWhisperer
· 08-10 09:16
hmm... ikili alan optimizasyonu teorik olarak şık görünüyor ama uzantı alanı işlemlerindeki o kenar durumlarını konuşalım...
View OriginalReply0
HalfBuddhaMoney
· 08-10 09:15
Ne zamandır sıfır genişlik alanını çevirmedim, bu sefer anlamak için yaptım.
View OriginalReply0
NonFungibleDegen
· 08-10 09:08
ser bu sert şeyler af... ikililer = sayı yukarı, nihayet bazı gerçek alfa bu merkle ağacı cope değil
Binius STARKs prensibi analizi: İkili alan optimizasyonu ve verimli çok terimli taahhüt
Binius STARKs İlkeleri Analizi ve Optimizasyon Düşünceleri
1 Giriş
STARK'ların verimsizliğinin başlıca nedenlerinden biri, gerçek programlardaki çoğu sayının oldukça küçük olmasıdır; ancak Merkle ağacı kanıtlarının güvenliğini sağlamak için, verileri genişletirken Reed-Solomon kodlaması kullanıldığında, birçok ek fazlalık değeri tüm alanı kaplar. Bu sorunu çözmek için alanın boyutunu azaltmak kritik bir strateji haline gelmiştir.
Küçük bir alan kullanıldığında, 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 genişletmeye dayanır. Çoğu Prover hesaplamasında yer alan çok terimli ifadeler genişletme alanına girmek zorunda kalmadan, yalnızca temel alanda işlem yaparak küçük alanda yüksek verimlilik sağlar. Ancak, rastgele nokta kontrolü ve FRI hesaplamaları, istenen güvenliği sağlamak için daha büyük bir genişletme alanına derinlemesine inmeyi gerektirir.
İkili alanlara dayalı bir kanıt sistemi inşa ederken, iki pratik sorun vardır: STARKs'ta izlerin temsilini hesaplamak için kullanılan alan büyüklüğü, polinomun derecesinden büyük olmalıdır; STARKs'ta Merkle ağacının taahhüdü yapılırken, Reed-Solomon kodlaması yapılması gerekir ve kullanılan alan büyüklüğü, kodlama genişletildikten sonra elde edilen büyüklüğünden büyük olmalıdır.
Binius, bu iki sorunu ayrı ayrı ele alan yenilikçi bir çözüm önermiştir ve aynı veriyi iki farklı şekilde temsil ederek bunu gerçekleştirmiştir: Öncelikle, tek değişkenli polinom yerine çok değişkenli (özellikle çok lineer) polinom kullanarak, "hiperküpler" üzerindeki değerleri ile tüm hesaplama izini temsil etmektedir; ikincisi, hiperküpün her boyutunun uzunluğunun 2 olması nedeniyle STARKs gibi standart Reed-Solomon genişlemesi yapılamaz, ancak hiperküp kare olarak düşünülebilir ve bu kare temel alınarak 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:
Binius: HyperPlonk PIOP + Brakedown PCS + ikili alan. Daha spesifik olarak, Binius, verimliliği ve güvenliğini sağlamak için beş ana teknolojiyi içermektedir:
2.1 Sonlu Alanlar: binary alanların kuleleri üzerine kurulu aritmetik
Kuyruklu ikili alan, hızlı doğrulanabilir hesaplamaların gerçekleştirilmesinde anahtar rol oynar, bu da iki nedene dayanmaktadır: verimli hesaplama ve verimli aritmetik. İkili alan, doğası gereği yüksek verimli aritmetik işlemleri destekler, bu da onu performansa duyarlı kriptografik uygulamalar için ideal bir seçim haline getirir. Ayrıca, ikili alan yapısı, basitleştirilmiş aritmetik süreci destekler; yani ikili alanda gerçekleştirilen işlemler, kompakt ve doğrulanması kolay cebirsel biçimde ifade edilebilir.
Fp asal alanında, yaygın olarak kullanılan 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 bulunmaktadır. İkili alanda F2k, yaygın olarak kullanılan azaltma yöntemleri arasında özel azaltma (AES'te kullanılan), Montgomery azaltması (POLYVAL'da kullanılan) ve özyinelemeli azaltma (Tower gibi) bulunmaktadır.
İkili alan, toplama ve çarpma işlemlerinde taşma gerektirmeden çalışır ve ikili alanın kare alma işlemi oldukça etkilidir, çünkü (X + Y )2 = X2 + Y 2 basitleştirilmiş kuralını takip eder.
2.2 PIOP: Uyarlama Versiyonu HyperPlonk Ürünü ve Permutasyon Kontrolü
Binius protokolündeki PIOP tasarımı HyperPlonk'tan esinlenmiştir ve çok terimli ve çok değişkenli kümenin doğruluğunu doğrulamak için bir dizi temel kontrol mekanizması kullanmaktadır. Bu temel kontroller şunları içerir:
Binius, HyperPlonk ile karşılaştırıldığında aşağıdaki geliştirmeleri yapmıştır:
2.3 PIOP: yeni çoklu kaydırma argümanı
Binius protokolünde, sanal çok terimli yapıların inşası ve işlenmesi, giriş kollarından veya diğer sanal çok terimlerden türetilen çok terimlerin etkin bir şekilde üretilmesi ve işlenmesini sağlayan anahtar teknolojilerden biridir. İşte iki anahtar yöntem:
2.4 PIOP: Uyarlama Lasso arama argümanı
Lasso protokolu, kanıtlayıcının bir vektör a ∈ Fm taahhüt etmesine ve tüm elemanlarının önceden belirlenmiş bir tablo t ∈ Fn içinde bulunduğunu kanıtlamasına olanak tanır. Lasso protokolü aşağıdaki üç bileşenden oluşur:
Binius protokolü Lasso'yu ikili alan işlemlerine uyarlayarak Lasso protokolünün çarpan versiyonunu tanıttı.
2.5 PCS：uyarlama Brakedown PCS
BiniusPCS'nin temel fikri packing'tir. Binius belgesinde, ikili alana dayalı iki Brakedown çoktam sayısı taahhüt çözümü sunulmuştur:
Binius çok terimli taahhüt temel olarak aşağıdaki teknolojileri kullanır:
3 Optimizasyon Düşüncesi
Binius protokolünün performansını daha da artırmak için bu makalede dört ana optimizasyon noktası önerilmektedir:
3.1 GKR tabanlı PIOP: GKR'ye dayalı ikili alan çarpımı
GKR'ye dayalı tam sayı çarpma işlemi algoritması, "iki 32-bit tam sayısı A ve B'nin A·B =? C'yi sağladığını kontrol et" ifadesini, "(gA)B =? gC'nin geçerli olup olmadığını kontrol et" ifadesine dönüştürerek, GKR protokolü sayesinde taahhüt maliyetlerini önemli ölçüde azaltır.
3.2 ZeroCheck PIOP optimizasyonu: Prover ve Verifier hesaplama maliyeti dengesi
Makale "ZeroCheck için PIOP'ta Bazı İyileştirmeler", ispatlayıcı (P) ve doğrulayıcı (V) arasında iş yükü dağılımını ayarlayarak, maliyetleri dengelemek için çeşitli optimizasyon önerileri sunmaktadır. Ana optimizasyonlar şunları içerir:
3.3 Sumcheck PIOP optimizasyonu: Küçük alanlara dayalı Sumcheck protokolü
Ingonyama, 2024 yılında küçük alanlara dayalı Sumcheck protokolü için geliştirme önerisinde bulundu ve uygulama kodunu açık kaynak olarak yayınladı. Ana optimizasyonlar şunlardır:
3.4 PCS Optimize: FRI-Binius Binius proof boyutunu azaltır
"Binary Towers Üzerinde Çoklu Doğrusalara Yönelik Polilogaritmik Kanıtlar" başlıklı makale, kısaca FRI-Binius, ikili alan FRI katlama mekanizmasını gerçekleştirmiştir ve 4 alanda yenilik sunmaktadır:
FRI-Binius sayesinde, Binius kanıt boyutunu bir büyüklük derecesi azaltabilirsiniz.
4 Özet
Binius, "donanım, yazılım ve FPGA'da hızlandırılmış Sumcheck protokolü kullanan" bir işbirliği tasarım çözümüdür ve çok düşük bellek kullanımı ile hızlı bir şekilde kanıt sağlamaktadır. Binius'ta Prover'ın commit taahhüt darboğazı temel olarak tamamen ortadan kaldırılmıştır, yeni darboğaz Sumcheck protokolündedir ve Sumcheck protokolündeki çok sayıda polinom değerlendirmesi ve alan çarpımı gibi sorunlar, özel donanım sayesinde verimli bir şekilde çözülmektedir.
FRI-Binius çözümü, FRI varyantı için, alan kanıtı katmanından gömülü maliyetleri ortadan kaldırırken, birleşik kanıt katmanının maliyetlerinin ani bir artışına neden olmayacak son derece çekici bir seçenek sunmaktadır. Şu anda, Irreducible ekibi kendi yinelemeli katmanını geliştirmekte ve Polygon ekibi ile birlikte Binius tabanlı zkVM inşa etmek için işbirliği yaptıklarını duyurmaktadır; JoltzkVM, yineleme performansını artırmak için Lasso'dan Binius'a geçmektedir; Ingonyama ekibi, Binius'un FPGA versiyonunu uygulamaktadır.