Bu makale, MSM algoritmasını, eliptik eğri noktası toplama algoritmasını, Montgomery çarpma algoritmasını vb. ayrıntılı olarak analiz eder ve BLS12_381 eğri noktası toplamada GPU ile FPGA arasındaki performans farkını karşılaştırır.
Yazan: Star Li
Sıfır bilgi kanıtı teknolojisi, gizlilik kanıtı, hesaplama kanıtı, fikir birliği kanıtı vb. gibi giderek daha yaygın bir şekilde kullanılmaktadır. Daha fazla ve daha iyi uygulama senaryoları ararken, birçok kişi yavaş yavaş sıfır bilgi kanıtının performansın bir darboğaz olduğunu kanıtladığını keşfetti. Trapdoor Tech ekibi, 2019'dan beri sıfır bilgi kanıtlı teknolojiyi derinlemesine araştırıyor ve sıfır bilgi kanıtlı verimli hızlandırma çözümlerini araştırıyor. GPU veya FPGA, şu anda piyasada bulunan nispeten yaygın hızlandırma platformlarıdır. Bu makale MSM'nin hesaplanmasıyla başlar ve FPGA ve GPU hızlandırmalı sıfır bilgi kanıtı hesaplamasının avantajlarını ve dezavantajlarını analiz eder.
TL;DR
ZKP, gelecek için geniş umutları olan bir teknolojidir. Giderek daha fazla uygulama, sıfır bilgi kanıtı teknolojisini benimsiyor. Ancak birçok ZKP algoritması vardır ve çeşitli projeler farklı ZKP algoritmaları kullanır. Aynı zamanda, ZKP ispatının hesaplama performansı nispeten zayıftır. Bu makale, MSM algoritmasını, eliptik eğri noktası toplama algoritmasını, Montgomery çarpma algoritmasını vb. ayrıntılı olarak analiz eder ve BLS12_381 eğri noktası toplamada GPU ile FPGA arasındaki performans farkını karşılaştırır. Genel olarak, ZKP kanıtlı bilgi işlem açısından, kısa vadeli GPU'nun belirgin avantajları, yüksek verimi, yüksek maliyet performansı, programlanabilirliği vb. vardır. Nispeten konuşursak, FPGA'nın güç tüketiminde belirli avantajları vardır. Uzun vadede ZKP hesaplamalarına uygun FPGA çipleri veya ZKP'ye özel ASIC çipleri olabilir.
ZKP algoritma kompleksi
ZKP, Sıfır Bilgi Kanıtı teknolojisi (Sıfır Bilgi Kanıtı) için genel bir terimdir. Temel olarak iki sınıflandırma vardır: zk-SNARK ve zk-STARK. zk-SNARK'ın mevcut ortak algoritmaları Groth16, PLONK, PLOOKUP, Marlin ve Halo/Halo2'dir. zk-SNARK algoritmasının yinelemesi esas olarak iki yöndedir: 1/güvenilir bir kurulumun gerekli olup olmadığı 2/devre yapısının performansı. zk-STARK algoritmasının avantajı, güvenilir bir kurulum gerektirmemesi, ancak doğrulama hesaplama miktarının log-lineer olmasıdır.
zk-SNARK/zk-STARK algoritmasının uygulaması söz konusu olduğunda, farklı projeler tarafından kullanılan sıfır bilgi kanıt algoritmaları nispeten dağınıktır. zk-SNARK algoritmasının uygulamasında, PLONK/Halo2 algoritması evrensel olduğundan (güvenilir kuruluma gerek yoktur), giderek daha fazla uygulama olabilir.
PLONK hesaplama miktarını kanıtlıyor
PLONK algoritmasını örnek alarak, PLONK kanıtının hesaplama miktarını analiz edin.
PLONK ispat kısmının hesaplama miktarı dört kısımdan oluşur:
1/ MSM - Çoklu Skaler Çarpma. MSM genellikle polinom taahhütlerini hesaplamak için kullanılır.
2/ NTT Hesaplaması - Nokta değeri ve katsayı gösterimi arasındaki polinom dönüşümü.
3/ Polinom hesaplama - polinom toplama, çıkarma, çarpma ve bölme. Polinom değerlendirmesi (uation) vb.
4/ Devre Sentezleme - devre sentezi. Bu kısmın hesaplanması devrenin ölçeği/karmaşıklığı ile ilgilidir.
Genel olarak, Devre Sentezleme bölümündeki hesaplama miktarı daha fazla muhakeme ve döngü mantığıdır ve paralellik derecesi nispeten düşüktür, bu da CPU hesaplaması için daha uygundur. Genel olarak konuşursak, sıfır bilgi kanıtı ivmesi genellikle ilk üç bölümün hesaplama ivmesini ifade eder. Bunlar arasında, MSM'nin hesaplanan miktarı nispeten en büyüğüdür ve onu NTT takip eder.
MSM nedir
MSM (Multiple Scalar Multiplication), eliptik eğri üzerinde belirli bir dizi nokta ve skaler anlamına gelir ve bu noktaların toplanmasının sonuçlarına karşılık gelen noktaları hesaplar.
Örneğin, eliptik bir eğri üzerinde bir dizi nokta verildiğinde:
Belirli bir eğriden sabit bir dizi Eliptik eğri noktası verildiğinde:
[G_1, G_2, G_3, ..., G_n]
ve rastgele katsayılar:
ve belirtilen skaler alandan rastgele örneklenmiş sonlu alan öğeleri:
[s_1, s_2, s_3, ..., s_n]
MSM, Eliptik eğri noktası Q'yu elde etmek için yapılan hesaplamadır:
Q = \toplam_{i=1}^{n}s_i*G_i
Endüstri, MSM hesaplamasını optimize etmek için genellikle Pippenger algoritmasını kullanır. Pippenger'in algoritma sürecinin şematik diyagramına daha yakından bakın:
Pippenger algoritmasının hesaplama süreci iki adıma ayrılmıştır:
1/ Skaler, Windows'a bölünmüştür. Skaler 256 bit ve bir Pencere 8 bit ise, tüm Skalerler 256/8=32 Windows'a bölünür. Her Pencere katmanı, ara sonuçları geçici olarak depolamak için bir "Paketler" kullanır. GW_x, bir katmandaki birikme noktası sonucudur. GW_x'i hesaplamak da nispeten basittir, sırayla bir katmandaki her Skaler'den geçer ve Skaler katmanın değerini İndeks olarak kullanır ve karşılık gelen G_x'i karşılık gelen Kovalara ekler. Aslında prensip görece basit: İki noktanın toplama katsayıları aynıysa, Skaleri toplamadan önce iki noktayı iki kere toplamak yerine önce iki noktayı topla sonra tekrar Skalayı topla.
2/ Her Pencere tarafından hesaplanan puanlar, nihai sonucu elde etmek için çift eklenerek toplanır.
Pippenger'in algoritması ayrıca birçok deformasyon optimizasyonu algoritmasına sahiptir. Her durumda, MSM algoritmasının altında yatan hesaplama, eliptik eğri üzerindeki noktaların eklenmesidir. Farklı optimizasyon algoritmaları, eklenen farklı sayıda noktaya karşılık gelir.
Eliptik eğri noktası toplama (Ekleme Noktası)
Bu siteden "kısa Weierstrass" formu ile eliptik eğrilerde nokta toplama için çeşitli algoritmalara bakabilirsiniz.
İki noktanın Projektif koordinatlarının sırasıyla (x1, y1, z1) ve (x2, y2, z2) olduğu varsayılarak, nokta toplamanın sonucu (x3, y3, z3) aşağıdaki hesaplama formülü ile hesaplanabilir.
Hesaplama işleminin ayrıntılı olarak verilmesinin nedeni, tüm hesaplama işleminin çoğunlukla tamsayı işlemlerden oluştuğunu göstermektir. Tamsayının bit genişliği, eliptik eğrinin parametrelerine bağlıdır. Bazı yaygın eliptik eğrilerin bit genişliklerini verin:
BN256 - 256 bit
BLS12_381 - 381 bit
BLS12_377 - 377 bit
Bu tamsayı işlemlerinin modulo alanındaki işlemler olmasına özellikle dikkat edilmelidir. Modüler toplama/modül çıkarma nispeten basittir, modüler çarpmanın ilkesine ve uygulamasına odaklanır.
模乘（Modüler Çoğaltma）
Bir modulo alanı üzerinden verilen iki değer: x ve y. Modüler çarpma hesaplaması, x*y mod p'yi ifade eder. Bu tamsayıların bit genişliğinin eliptik eğrinin bit genişliği olduğuna dikkat edin. Modüler çarpmanın klasik algoritması Montgomery çarpmasıdır (MontgomeryMulplication). Montgomery çarpımını gerçekleştirmeden önce, çarpanın Montgomery gösterimine dönüştürülmesi gerekir:
Montgomery çarpımını hesaplama formülü aşağıdaki gibidir:
Pek çok Montgomery çarpma uygulama algoritması vardır: CIOS (Kaba Tümleşik İşlenen Tarama), FIOS (İnce Tümleşik İşlenen Tarama) ve FIPS (İnce Tümleşik Ürün Tarama) vb. Bu makale, çeşitli algoritma uygulamalarının ayrıntılarını derinlemesine tanıtmaz ve ilgilenen okuyucular kendi araştırmalarını yapabilirler.
FPGA ve GPU arasındaki performans farkını karşılaştırmak için en temel algoritma uygulama yöntemini seçin:
Basitçe söylemek gerekirse, modüler çarpma algoritması ayrıca iki hesaplamaya ayrılabilir: büyük sayı çarpma ve büyük sayı toplama. MSM'nin hesaplama mantığını anladıktan sonra, FPGA ve GPU'nun performansını karşılaştırmak için modüler çarpma (Verimlilik) performansını seçebilirsiniz.
Gözlemleyin ve düşünün
Bu tür bir FPGA tasarımı altında, tüm VU9P'nin BLS12_381 eliptik eğri noktalarında verimi sağlayabileceği tahmin edilebilir. Bir nokta toplama (add_mix yolu) yaklaşık 12 modüler çarpma gerektirir. FPGA'nın sistem saati 450M'dir.
Aynı modüler çarpma/modül toplama algoritması altında, aynı nokta toplama algoritması kullanılarak, Nvidia 3090'ın nokta artı Troughput'u (veri aktarım faktörleri dikkate alındığında) 500M/s'yi aşıyor. Tabii ki, tüm hesaplama çeşitli algoritmalar içerir, bazı algoritmalar FPGA için uygun olabilir ve bazı algoritmalar GPU için uygundur. Aynı algoritma karşılaştırmasının kullanılmasının nedeni, FPGA ve GPU'nun temel bilgi işlem yeteneklerini karşılaştırmaktır.
Yukarıdaki sonuçlara dayanarak, ZKP kanıt performansı açısından GPU ve FPGA arasındaki karşılaştırmayı özetleyin:
Özetle
Giderek daha fazla uygulama, sıfır bilgi kanıtı teknolojisini benimsiyor. Ancak birçok ZKP algoritması vardır ve çeşitli projeler farklı ZKP algoritmaları kullanır. Uygulamalı mühendislik deneyimimizden, FPGA bir seçenektir, ancak GPU şu anda uygun maliyetli bir seçenektir. FPGA, gecikme ve güç tüketimi avantajlarına sahip olan deterministik hesaplamayı tercih eder. GPU, yüksek programlanabilirliğe sahiptir, nispeten olgunlaşmış yüksek performanslı bir bilgi işlem çerçevesine sahiptir ve kısa bir geliştirme yineleme döngüsüne sahiptir ve iş hacmi senaryolarını tercih eder.
View Original
The content is for reference only, not a solicitation or offer. No investment, tax, or legal advice provided. See Disclaimer for more risks disclosure.
FPGA ve GPU hızlandırmalı sıfır bilgi kanıtlı hesaplamanın avantajlarını ve dezavantajlarını anlamaya yönelik bir makale
Yazan: Star Li
Sıfır bilgi kanıtı teknolojisi, gizlilik kanıtı, hesaplama kanıtı, fikir birliği kanıtı vb. gibi giderek daha yaygın bir şekilde kullanılmaktadır. Daha fazla ve daha iyi uygulama senaryoları ararken, birçok kişi yavaş yavaş sıfır bilgi kanıtının performansın bir darboğaz olduğunu kanıtladığını keşfetti. Trapdoor Tech ekibi, 2019'dan beri sıfır bilgi kanıtlı teknolojiyi derinlemesine araştırıyor ve sıfır bilgi kanıtlı verimli hızlandırma çözümlerini araştırıyor. GPU veya FPGA, şu anda piyasada bulunan nispeten yaygın hızlandırma platformlarıdır. Bu makale MSM'nin hesaplanmasıyla başlar ve FPGA ve GPU hızlandırmalı sıfır bilgi kanıtı hesaplamasının avantajlarını ve dezavantajlarını analiz eder.
TL;DR
ZKP, gelecek için geniş umutları olan bir teknolojidir. Giderek daha fazla uygulama, sıfır bilgi kanıtı teknolojisini benimsiyor. Ancak birçok ZKP algoritması vardır ve çeşitli projeler farklı ZKP algoritmaları kullanır. Aynı zamanda, ZKP ispatının hesaplama performansı nispeten zayıftır. Bu makale, MSM algoritmasını, eliptik eğri noktası toplama algoritmasını, Montgomery çarpma algoritmasını vb. ayrıntılı olarak analiz eder ve BLS12_381 eğri noktası toplamada GPU ile FPGA arasındaki performans farkını karşılaştırır. Genel olarak, ZKP kanıtlı bilgi işlem açısından, kısa vadeli GPU'nun belirgin avantajları, yüksek verimi, yüksek maliyet performansı, programlanabilirliği vb. vardır. Nispeten konuşursak, FPGA'nın güç tüketiminde belirli avantajları vardır. Uzun vadede ZKP hesaplamalarına uygun FPGA çipleri veya ZKP'ye özel ASIC çipleri olabilir.
ZKP algoritma kompleksi
ZKP, Sıfır Bilgi Kanıtı teknolojisi (Sıfır Bilgi Kanıtı) için genel bir terimdir. Temel olarak iki sınıflandırma vardır: zk-SNARK ve zk-STARK. zk-SNARK'ın mevcut ortak algoritmaları Groth16, PLONK, PLOOKUP, Marlin ve Halo/Halo2'dir. zk-SNARK algoritmasının yinelemesi esas olarak iki yöndedir: 1/güvenilir bir kurulumun gerekli olup olmadığı 2/devre yapısının performansı. zk-STARK algoritmasının avantajı, güvenilir bir kurulum gerektirmemesi, ancak doğrulama hesaplama miktarının log-lineer olmasıdır.
zk-SNARK/zk-STARK algoritmasının uygulaması söz konusu olduğunda, farklı projeler tarafından kullanılan sıfır bilgi kanıt algoritmaları nispeten dağınıktır. zk-SNARK algoritmasının uygulamasında, PLONK/Halo2 algoritması evrensel olduğundan (güvenilir kuruluma gerek yoktur), giderek daha fazla uygulama olabilir.
PLONK hesaplama miktarını kanıtlıyor
PLONK algoritmasını örnek alarak, PLONK kanıtının hesaplama miktarını analiz edin.
PLONK ispat kısmının hesaplama miktarı dört kısımdan oluşur:
1/ MSM - Çoklu Skaler Çarpma. MSM genellikle polinom taahhütlerini hesaplamak için kullanılır.
2/ NTT Hesaplaması - Nokta değeri ve katsayı gösterimi arasındaki polinom dönüşümü.
3/ Polinom hesaplama - polinom toplama, çıkarma, çarpma ve bölme. Polinom değerlendirmesi (uation) vb.
4/ Devre Sentezleme - devre sentezi. Bu kısmın hesaplanması devrenin ölçeği/karmaşıklığı ile ilgilidir.
Genel olarak, Devre Sentezleme bölümündeki hesaplama miktarı daha fazla muhakeme ve döngü mantığıdır ve paralellik derecesi nispeten düşüktür, bu da CPU hesaplaması için daha uygundur. Genel olarak konuşursak, sıfır bilgi kanıtı ivmesi genellikle ilk üç bölümün hesaplama ivmesini ifade eder. Bunlar arasında, MSM'nin hesaplanan miktarı nispeten en büyüğüdür ve onu NTT takip eder.
MSM nedir
MSM (Multiple Scalar Multiplication), eliptik eğri üzerinde belirli bir dizi nokta ve skaler anlamına gelir ve bu noktaların toplanmasının sonuçlarına karşılık gelen noktaları hesaplar.
Örneğin, eliptik bir eğri üzerinde bir dizi nokta verildiğinde:
Belirli bir eğriden sabit bir dizi Eliptik eğri noktası verildiğinde:
[G_1, G_2, G_3, ..., G_n]
ve rastgele katsayılar:
ve belirtilen skaler alandan rastgele örneklenmiş sonlu alan öğeleri:
[s_1, s_2, s_3, ..., s_n]
MSM, Eliptik eğri noktası Q'yu elde etmek için yapılan hesaplamadır:
Q = \toplam_{i=1}^{n}s_i*G_i
Endüstri, MSM hesaplamasını optimize etmek için genellikle Pippenger algoritmasını kullanır. Pippenger'in algoritma sürecinin şematik diyagramına daha yakından bakın:
Pippenger algoritmasının hesaplama süreci iki adıma ayrılmıştır:
1/ Skaler, Windows'a bölünmüştür. Skaler 256 bit ve bir Pencere 8 bit ise, tüm Skalerler 256/8=32 Windows'a bölünür. Her Pencere katmanı, ara sonuçları geçici olarak depolamak için bir "Paketler" kullanır. GW_x, bir katmandaki birikme noktası sonucudur. GW_x'i hesaplamak da nispeten basittir, sırayla bir katmandaki her Skaler'den geçer ve Skaler katmanın değerini İndeks olarak kullanır ve karşılık gelen G_x'i karşılık gelen Kovalara ekler. Aslında prensip görece basit: İki noktanın toplama katsayıları aynıysa, Skaleri toplamadan önce iki noktayı iki kere toplamak yerine önce iki noktayı topla sonra tekrar Skalayı topla.
2/ Her Pencere tarafından hesaplanan puanlar, nihai sonucu elde etmek için çift eklenerek toplanır.
Pippenger'in algoritması ayrıca birçok deformasyon optimizasyonu algoritmasına sahiptir. Her durumda, MSM algoritmasının altında yatan hesaplama, eliptik eğri üzerindeki noktaların eklenmesidir. Farklı optimizasyon algoritmaları, eklenen farklı sayıda noktaya karşılık gelir.
Eliptik eğri noktası toplama (Ekleme Noktası)
Bu siteden "kısa Weierstrass" formu ile eliptik eğrilerde nokta toplama için çeşitli algoritmalara bakabilirsiniz.
İki noktanın Projektif koordinatlarının sırasıyla (x1, y1, z1) ve (x2, y2, z2) olduğu varsayılarak, nokta toplamanın sonucu (x3, y3, z3) aşağıdaki hesaplama formülü ile hesaplanabilir.
Hesaplama işleminin ayrıntılı olarak verilmesinin nedeni, tüm hesaplama işleminin çoğunlukla tamsayı işlemlerden oluştuğunu göstermektir. Tamsayının bit genişliği, eliptik eğrinin parametrelerine bağlıdır. Bazı yaygın eliptik eğrilerin bit genişliklerini verin:
模乘（Modüler Çoğaltma）
Bir modulo alanı üzerinden verilen iki değer: x ve y. Modüler çarpma hesaplaması, x*y mod p'yi ifade eder. Bu tamsayıların bit genişliğinin eliptik eğrinin bit genişliği olduğuna dikkat edin. Modüler çarpmanın klasik algoritması Montgomery çarpmasıdır (MontgomeryMulplication). Montgomery çarpımını gerçekleştirmeden önce, çarpanın Montgomery gösterimine dönüştürülmesi gerekir:
Montgomery çarpımını hesaplama formülü aşağıdaki gibidir:
Pek çok Montgomery çarpma uygulama algoritması vardır: CIOS (Kaba Tümleşik İşlenen Tarama), FIOS (İnce Tümleşik İşlenen Tarama) ve FIPS (İnce Tümleşik Ürün Tarama) vb. Bu makale, çeşitli algoritma uygulamalarının ayrıntılarını derinlemesine tanıtmaz ve ilgilenen okuyucular kendi araştırmalarını yapabilirler.
FPGA ve GPU arasındaki performans farkını karşılaştırmak için en temel algoritma uygulama yöntemini seçin:
Basitçe söylemek gerekirse, modüler çarpma algoritması ayrıca iki hesaplamaya ayrılabilir: büyük sayı çarpma ve büyük sayı toplama. MSM'nin hesaplama mantığını anladıktan sonra, FPGA ve GPU'nun performansını karşılaştırmak için modüler çarpma (Verimlilik) performansını seçebilirsiniz.
Gözlemleyin ve düşünün
Bu tür bir FPGA tasarımı altında, tüm VU9P'nin BLS12_381 eliptik eğri noktalarında verimi sağlayabileceği tahmin edilebilir. Bir nokta toplama (add_mix yolu) yaklaşık 12 modüler çarpma gerektirir. FPGA'nın sistem saati 450M'dir.
Aynı modüler çarpma/modül toplama algoritması altında, aynı nokta toplama algoritması kullanılarak, Nvidia 3090'ın nokta artı Troughput'u (veri aktarım faktörleri dikkate alındığında) 500M/s'yi aşıyor. Tabii ki, tüm hesaplama çeşitli algoritmalar içerir, bazı algoritmalar FPGA için uygun olabilir ve bazı algoritmalar GPU için uygundur. Aynı algoritma karşılaştırmasının kullanılmasının nedeni, FPGA ve GPU'nun temel bilgi işlem yeteneklerini karşılaştırmaktır.
Yukarıdaki sonuçlara dayanarak, ZKP kanıt performansı açısından GPU ve FPGA arasındaki karşılaştırmayı özetleyin:
Özetle
Giderek daha fazla uygulama, sıfır bilgi kanıtı teknolojisini benimsiyor. Ancak birçok ZKP algoritması vardır ve çeşitli projeler farklı ZKP algoritmaları kullanır. Uygulamalı mühendislik deneyimimizden, FPGA bir seçenektir, ancak GPU şu anda uygun maliyetli bir seçenektir. FPGA, gecikme ve güç tüketimi avantajlarına sahip olan deterministik hesaplamayı tercih eder. GPU, yüksek programlanabilirliğe sahiptir, nispeten olgunlaşmış yüksek performanslı bir bilgi işlem çerçevesine sahiptir ve kısa bir geliştirme yineleme döngüsüne sahiptir ve iş hacmi senaryolarını tercih eder.