Orodha ya Yaliyomo
200x
Uongezeko wa Kasi wa Juu Zaidi Ukilinganisha na CPU
90%
Mchango wa NTT kwa Udhoofika
32-bit
Matumizi ya Mfereji wa Namba Kamili
1. Utangulizi
Uthibitishaji wa Kutokujua-Kitu (ZKPs) unawakilisha itifaki ya kisimbu fiche ya kimapinduzi ambayo huwezesha mtu mmoja (Mthibitishaji) kuonyesha ujuzi wa ingizo la siri bila kufichua taarifa yoyote kuhusu siri yenyewe. Uwezo huu umewezesha matumizi ya kubadilika katika sarafu za faragha, utoaji wa hesabu zinazoweza kuthibitishwa, na suluhisho za kuongeza uwezo wa mnyororo wa vitalu (blockchain). Changamoto kuu katika kupitishwa kwa ZKP imekuwa mzigo mkubwa wa kihesabu unaohitajika kwa utengenezaji wa uthibitisho, ambao unaweza kuchukua dakika kadhaa kwenye CPU za kisasa kwa hesabu ngumu.
GPU zimeibuka kama jukwaa kuu la kuongeza kasi kwa ZKP kutokana na hali ya sambamba ya data ya viini vya msingi vya kihesabu. Kama inavyoonyeshwa kwenye Mchoro 1, ZKP zilizoongezewa kasi na GPU zinaonyesha uongezeko wa kasi hadi mara 200 ikilinganishwa na utekelezaji wa CPU. Hata hivyo, licha ya mafanikio haya ya kuvutia, uchambuzi wa kimfumo wa vikwazo vya ufanisi na mapungufu ya uwezo wa kukua kwenye miundo ya kisasa ya GPU umekuwa ukikosekana kwa kiasi kikubwa katika vitabu.
2. Msingi na Kazi Inayohusiana
2.1 Misingi ya Uthibitishaji wa Kutokujua-Kitu
Uthibitishaji wa Kutokujua-Kitu hufanya kazi kwa kanuni kwamba Mthibitishaji anaweza kumshawishi Mhakiki kuhusu ujuzi wa shahidi $w$ kwa utendakazi wa umma $f$ na ingizo $x$ kiasi kwamba $f(x,w) = y$, bila kufichua taarifa yoyote kuhusu $w$. Itifaki ya Groth16, ambayo huunda msingi wa utafiti huu, hutoa uthibitisho mfupi na nyakati za uthibitishaji chini ya millisecond, na kufanya iweze kufaa hasa kwa matumizi ya ulimwengu halisi.
2.2 Uongezeaji wa Kasi wa GPU katika Usimbu Fiche
Kazi ya awali katika kuongeza kasi ya GPU ya misingi ya kisimbu fiche imeonyesha maboresho makubwa ya ufanisi. Tafiti kama vile [19,30,31,42] zimeonyesha kuwa muundo sambamba wa GPU unafaa vizuri kwa shughuli za kisimbu fiche, hasa zile zinazohusisha hesabu za kihisabati za kiwango kikubwa. Hata hivyo, juhudi hizi zimezingatia hasa viini vya kibinafsi badala ya ufanisi wa mfumo wa mwisho-hadi-mwisho.
3. Mbinu na Usanidi wa Majaribio
3.1 Mfumo wa ZKProphet
ZKProphet hutoa mfumo wa uchambuzi wa kina wa kutathmini ufanisi wa ZKP kwenye GPU. Mfumo huu hutathmini kwa utaratibu viini vya msingi vya kihesabu ikiwemo Kuzidisha kwa Skala Nyingi (MSM) na Mabadiliko ya Kinadharia-Namba (NTT), ambazo pamoja huchangia zaidi ya 95% ya mzigo wa kihesabu katika utengenezaji wa ZKP.
3.2 Usanidi wa Vipimo
Usanidi wetu wa majaribio hutumia miundo ya kisasa ya GPU kutoka kizazi cha Ampere na Ada Lovelace cha NVIDIA. Tunatathmini ufanisi katika idadi tofauti za vikwazo, ambavyo huwakilisha utata wa hesabu inayothibitishwa. Vipimo hivi vinajumuisha mizigo ya kazi ya sintetiki na matumizi ya ZKP ya ulimwengu halisi kutoka kwenye sarafu za kidijitali na nyanja za mnyororo wa vitalu.
4. Matokeo ya Uchambuzi wa Ufanisi
4.1 Mgawanyiko wa Ufanisi wa Kernel
Uchambuzi wetu unaonyesha mabadiliko muhimu katika vikwazo vya ufanisi. Ingawa utafiti wa awali ulilenga sana kuboresha shughuli za MSM, tunagundua kuwa kwa utekelezaji wa kisasa ulioboreshwa wa MSM, shughuli za NTT sasa huchangia hadi 90% ya udhoofika wa utengenezaji wa uthibitisho. Hii inawakilisha mabadiliko makubwa ya dhana ambayo yanahitaji umakini mpya katika ubora wa NTT.
Mchoro 1: Uongezeko wa Kasi wa Mthibitishaji dhidi ya Idadi ya Vikwazo
Matokeo ya majaribio yanaonyesha kuwa utekelezaji wa GPU hutoa uongezeko mkubwa wa kasi ukilinganisha na misingi ya CPU, na ufanisi unaokua takriban kwa mstari na hesabu ya kikwazo hadi kuboreshwa kwa mara 200 kwa seti kubwa za vikwazo.
4.2 Uchambuzi wa Uwezo wa Kukua
Tunaona kuwa hesabu za ZKP hufanya kazi pekee kwenye mifereji ya namba kamili ya 32-bit ya GPU na huonyesha uwezo mdogo wa usambamba wa kiwango cha maagizo kutokana na utegemezi wa data asilia. Hii kimsingi inazuia uwezo wa kukua wa ufanisi kulingana na vitengo vinavyopatikana vya kihesabu vya namba kamili badala ya uwezo wa namba zenye sehemu za desimali.
5. Maelezo ya Kiufundi ya Utekelezaji
5.1 Misingi ya Kihisabati
Shughuli za msingi za kihisabati katika ZKP zinategemea hesabu za uga wa mwisho juu ya uga wa pekee mkubwa. Shughuli ya NTT, ambayo ni aina maalum ya mabadiliko ya Fourier katika uga wa mwisho, inaweza kuonyeshwa kama:
$$X_k = \sum_{j=0}^{n-1} x_j \cdot \omega^{jk} \mod p$$
ambapo $\omega$ ni kiini cha msingi cha $n$-th cha umoja modulo $p$, na $p$ ni pekee kubwa. NTT ya kinyume inafafanuliwa vivyo hivyo kwa $\omega^{-1}$.
5.2 Utekelezaji wa Msimbo
Msimbo ufuatao wa bandia unaonyesha utekelezaji ulioboreshwa wa NTT kwa miundo ya GPU:
__global__ void ntt_kernel(uint32_t *a, uint32_t *roots, int n) {
int tid = threadIdx.x + blockIdx.x * blockDim.x;
int stride = blockDim.x * gridDim.x;
for (int i = tid; i < n/2; i += stride) {
int j = bit_reverse(i, log2(n));
if (i < j) {
swap(a[i], a[j]);
}
}
__syncthreads();
for (int len = 2; len <= n; len <<= 1) {
int half = len >> 1;
for (int i = tid; i < n; i += stride) {
if ((i & (len - 1)) < half) {
uint32_t u = a[i];
uint32_t v = mul_mod(a[i + half], roots[len + (i & (half - 1))]);
a[i] = add_mod(u, v);
a[i + half] = sub_mod(u, v);
}
}
__syncthreads();
}
}6. Matumizi na Mwelekeo wa Baadaye
Uboreshaji wa ZKP kwenye GPU unafungua uwezekano mwingi wa matumizi. Katika teknolojia ya mnyororo wa vitalu, ZKP zilizoboreshwa zinaweza kuwezesha suluhisho bora zaidi za rollup na kandarasi za akili zinazohifadhi faragha. Kwa masomo ya mashine yanayoweza kuthibitishwa, kama ilivyo chunguzwa katika kazi kama vile [32], ZKP zilizoongezewa kasi na GPU zinaweza kuwezesha uthibitisho wa vitendo wa hitimisho la mfano bila kufichua vigezo vya mfano wa umiliki.
Maelekezo ya utafiti wa baadaye ni pamoja na kuchunguza hesabu za usahihi mchanganyiko ili kutumia vyema viini vya tensor vya GPU, kuunda mbinu maalum za muundo wa pamoja wa vifaa na programu, na kuunda mifumo ya kuboresha inayoweza kubadilika ambayo inaweza kurekebisha kiotomatiki vigezo vya ZKP kulingana na uwezo maalum wa vifaa na mahitaji ya matumizi.
Uchambuzi wa Asili
Utafiti wa ZKProphet unawakilisha maendeleo makubwa katika kuelewa sifa za ufanisi za Uthibitishaji wa Kutokujua-Kitu kwenye miundo ya kisasa ya GPU. Ingawa utafiti wa awali, kama kazi ya msingi kwenye zk-SNARKs na Ben-Sasson et al. (2014), ulianzisha misingi ya kinadharia, na utekelezaji unaofuata kama libsnark na bellman ulitoa mifumo ya vitendo, kumekuwa na pengo kubwa katika uchambuzi wa ufanisi wa kimfumo katika mfereji mzima wa kihesabu.
Kutambuliwa kwa NTT kama kikwazo kipya cha msingi (kuchangia hadi 90% ya udhoofika) huashiria mabadiliko muhimu katika vipaumbele vya ubora. Ugunduzi huu unafanana na uchunguzi katika nyanja zingine zenye mzigo mkubwa wa kihesabu ambapo ubora wa awali unalenga vikwazo vinavyoonekana wazi, na kufichua tu vikwazo vya sekondari ambavyo huwa vikuu baada ya maboresho ya awali. Mifumo kama hii imeonekana katika utekelezaji wa kisimbu fiche kwa mifumo ya mnyororo wa vitalu, ambapo baada ya kuboresha shughuli za curve za duaradufu, mifumo ya upatikanaji wa kumbukumbu ilikuwa kikwazo.
Matumizi ya kipekee ya mifereji ya namba kamili ya 32-bit yanaonyesha changamoto na fursa. Tofauti na mizigo ya kazi ya kujifunza mashine ambayo hutumia kikamilifu viini vya tensor na hesabu za FP32/FP16, ZKP haziwezi kufaidika na vitengo hivi maalum katika miundo ya sasa ya GPU. Hii inapendekeza uwezekano wa muundo wa pamoja wa vifaa na programu, sawa na mbinu iliyochukuliwa katika muundo wa TPU wa Google kwa mitandao ya neva, lakini iliyotengenezwa maalum kwa shughuli za kisimbu fiche. Uwezo mdogo wa usambafa wa kiwango cha maagizo kutokana na utegemezi wa data unaasisitiza zaidi hitaji la uvumbuzi wa ki-algoritimu ambayo inaweza kufichua usambafa zaidi.
Ikilinganishwa na juhudi zingine za kuongeza kasi ya kisimbu fiche, kama vile zile za usimbu fiche wa homomorphic (kama ilivyotajwa katika [9]) au mifumo ya hesabu inayoweza kuthibitishwa, ZKProphet inayolenga ufanisi wa mwisho-hadi-mwisho badala ya ubora wa kiini cha kibinafsi hutoa maarifa zaidi ya vitendo kwa utumizi wa ulimwengu halisi. Rejea kwa matumizi ya kujifunza mashine yanayoweza kuthibitishwa katika [32] inapendekeza matumizi ya nyanja mbalimbali yanayotabiriwa ambapo ZKP zilizoongezewa kasi na GPU zinaweza kuwezesha miundo mipya ya kuaminika katika mifumo ya AI.
Mapungufu ya uwezo wa kukua wa ufanisi yaliyotambuliwa katika kazi hii yana athari kubwa kwa utumizi wa vitendo wa ZKP katika mifumo ya uzalishaji. Kadiri idadi ya vikwazo inavyoongezeka na hesabu ngumu zaidi, uhusiano wa kukua kwa mstari unapendekeza kuwa miundo ya sasa ya GPU inaweza kukabiliana na mipaka ya msingi bila uvumbuzi wa kimuundo unaolenga hasa mizigo ya kazi ya kisimbu fiche.
7. Marejeo
- Groth, J. (2016). "On the Size of Pairing-Based Non-interactive Arguments." EUROCRYPT 2016.
- Ben-Sasson, E., et al. (2014). "Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture." USENIX Security Symposium.
- Parno, B., et al. (2013). "Pinocchio: Nearly Practical Verifiable Computation." IEEE Symposium on Security and Privacy.
- Setty, S., et al. (2013). "Resolving the conflict between generality and plausibility in verified computation." EuroSys.
- Zhang, J., et al. (2020). "vCNN: Verifiable Convolutional Neural Network based on zk-SNARKs." Cryptology ePrint Archive.
- Wahby, R.S., et al. (2018). "Full accounting for verifiable outsourcing." CCS.
- Kosba, A., et al. (2016). "C∅C∅: A Framework for Building Composable Zero-Knowledge Proofs." USENIX Security.
- Xie, T., et al. (2022). "zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy." CCS.