ZKProphet: Fahimtar Ayyukan Hujjojin Sirri-Sifili akan GPUs

Jerin Abubuwan Ciki

1. Gabatarwa

Hujjojin Sirri-Sifili (ZKPs) suna wakiltar wata sabuwar hanya ta sirri wacce ke baiwa ɗaya ɓangare (Mai Shaida) damar nuna ilimin sirrin shigarwa ba tare da bayyana kowane bayani game da sirrin kansa ba. Wannan damar ta ba da damar ayyuka masu canzawa a cikin kudadden kuɗi masu sirri, aikin lissafi da za a iya tantancewa, da kuma magance matsalolin girman blockchain. Babbar ƙalubale a cikin amfani da ZKP ita ce babban aikin lissafi da ake buƙata don samar da hujja, wanda zai iya ɗaukar mintuna da yawa akan CPUs na zamani don rikitattun lissafi.

GPUs sun zama dandalin hanzari na farko don ZKPs saboda yanayin lissafin tsaki na bayanai masu kama da juna. Kamar yadda aka nuna a Hoto na 1, ZKPs masu hanzari na GPU suna nuna haɓakar gudu har zuwa 200x idan aka kwatanta da aiwatar da CPU. Duk da haka, duk da waɗannan nasarori masu ban sha'awa, ƙayyadaddun siffa na matsalolin aiki da iyakokin girma akan tsarin GPU na zamani an ƙi samun su a cikin wallafe-wallafen.

2. Bayanan Baya da Ayyukan Da suka Danganci

2.1 Tushen Hujjojin Sirri-Sifili

Hujjojin Sirri-Sifili suna aiki bisa ka'idar cewa Mai Shaida zai iya gamsar da Mai Tantancewa game da ilimin shaida $w$ don aikin jama'a $f$ da shigarwa $x$ kamar yadda $f(x,w) = y$, ba tare da bayyana kowane bayani game da $w$ ba. Ka'idar Groth16, wacce ta zama tushen wannan binciken, tana ba da hujjoji a taƙaice da lokutan tantancewa na ƙasa da mili ɗaya, wanda ya sa ya dace musamman don ayyukan duniya.

2.2 Hanzari na GPU a cikin Sirri

Ayyukan da suka gabata a cikin hanzari na GPU na mahimman sirri sun nuna gagarumin ci gaba. Bincike kamar [19,30,31,42] sun nuna cewa tsarin GPU mai kama da juna ya dace da ayyukan sirri, musamman waɗanda suka haɗa da manyan lissafin lissafi. Duk da haka, waɗannan ƙoƙarin sun fi mayar da hankali ga tsaki ɗaya maimakon aikin tsarin ƙarshe-zuwa-ƙarshe.

3. Hanyoyin Bincike da Saitunan Gwaji

3.1 Tsarin ZKProphet

ZKProphet yana ba da cikakken tsarin bincike don kimanta aikin ZKP akan GPUs. Tsarin yana tantance tsakiyar lissafin tsaki cikin tsari ciki har da Ninkawa-Ma'auni-Ma'auni (MSM) da Canjin Ka'idar Lamba (NTT), waɗanda suka haɗa sama da kashi 95% na aikin lissafi a cikin samar da ZKP.

3.2 Saitunan Ma'auni

Saitunan gwajin mu suna amfani da tsarin GPU na zamani daga tsarin Ampere da Ada Lovelace na NVIDIA. Muna kimanta aiki a cikin ƙididdiga daban-daban, waɗanda ke wakiltar rikitarwar lissafin da ake shaida. Ma'auni sun haɗa da ayyukan aiki na roba da ainihin ayyukan ZKP daga fannin kuɗin sirri da blockchain.

4. Sakamakon Binciken Aiki

4.1 Rarrabe Ayyukan Tsaki

Bincikenmu ya nuna wani muhimmin canji a cikin matsalolin aiki. Yayin da bincike na baya ya fi mayar da hankali kan inganta ayyukan MSM, mun gano cewa tare da aiwatar da MSM na zamani, ayyukan NTT yanzu suna ɗaukar har zuwa kashi 90% na jinkirin samar da hujja. Wannan yana wakiltar wani muhimmin canjin tsari wanda ke buƙatar sake mayar da hankali kan inganta NTT.

Hoto 1: Hanzari Mai Shaida da Adadin Ƙuntatawa
Sakamakon gwaji ya nuna cewa aiwatar da GPU yana ba da gagarumin haɓakar gudu akan ma'auni na CPU, tare da aikin ma'auni kusan layi daya tare da ƙididdigar ƙuntatawa har zuwa 200x ingantawa don manyan saitin ƙuntatawa.

4.2 Binciken Girma

Mun lura cewa lissafin ZKP suna aiwatarwa kawai akan bututun lamba 32-bit na GPU kuma suna nuna iyakataccen kama da juna na umarni saboda dogaro da bayanai. Wannan a zahira yana iyakance girman aiki bisa ga raka'o'in lissafin lamba da ake samu maimakon iyawar maki masu iyo.

5. Cikakkun Bayanai na Aiwalar Fasaha

5.1 Tushen Lissafi

Babban aikin lissafi a cikin ZKPs ya dogara ne akan lissafin filin iyaka akan manyan filayen firamare. Aikin NTT, wanda wani takamaiman nau'i ne na canjin Fourier a cikin filayen iyaka, ana iya bayyana shi kamar haka:

$$X_k = \sum_{j=0}^{n-1} x_j \cdot \omega^{jk} \mod p$$

inda $\omega$ shine tushen farko na haɗin kai $n$ modulo $p$, kuma $p$ babban firamare ne. Ana kuma bayyana NTT na baya tare da $\omega^{-1}$.

5.2 Aiwalar Lamba

Mai zuwa pseudocode yana nuna ingantaccen aiwatar da NTT don tsarin 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. Ayyuka da Jagororin Gaba

Inganta ZKPs akan GPUs yana buɗe yuwuwar ayyuka da yawa. A fasahar blockchain, ingantattun ZKPs zasu iya ba da damar mafi ingantaccen magance matsaloli da kwangiloi masu hankali masu kiyaye sirri. Don koyon injin da za a iya tantancewa, kamar yadda aka bincika a cikin ayyuka kamar [32], ZKPs masu hanzari na GPU zasu iya ba da damar tantance ainihin abubuwan da aka yi hasashe ba tare da bayyana sigogin ƙirar mallaka ba.

Jagororin bincike na gaba sun haɗa da bincika lissafin ma'auni gauraye don amfani da ingantaccen tsaki na GPU, haɓaka hanyoyin haɗin gwiwar software-kayan aiki na musamman, da ƙirƙirar tsarin ingantawa masu daidaitawa waɗanda zasu iya daidaita sigogin ZKP ta atomatik bisa takamaiman iyawar kayan aiki da buƙatun aikace-aikace.

Bincike na Asali

Binciken ZKProphet yana wakiltar ci gaba mai muhimmanci a fahimtar halayen ayyukan Hujjojin Sirri-Sifili akan tsarin GPU na zamani. Yayin da bincike na baya, kamar aikin tushe akan zk-SNARKs na Ben-Sasson et al. (2014), ya kafa tushen ka'idar, kuma aiwatar da gaba kamar libsnark da bellman sun ba da tsarin aiki, an sami gibi a cikin binciken aiki na tsari a ko'ina cikin bututun lissafi.

Gano NTT a matsayin sabon babban toshewa (wanda ya kai har zuwa kashi 90% na jinkiri) yana nuna wani muhimmin canji a cikin fifikon ingantawa. Wannan binciken ya yi daidai da abin da aka gani a wasu yankuna masu ƙarfin lissafi inda ingantawa na farko ke niyya ga mafi bayyanannun matsaloli, kawai don bayyana ƙuntatawa na biyu waɗanda suka zama masu rinjaye bayan ingantawa na farko. An kuma lura da irin wannan alamu a cikin aiwatar da sirri don tsarin blockchain, inda bayan inganta ayyukan lanƙwasa lankwasa, tsarin samun damar ƙwaƙwalwar ajiya ya zama abin iyakancewa.

Amfani na musamman na bututun lamba 32-bit yana gabatar da ƙalubale da dama. Ba kamar ayyukan koyon injina waɗanda ke amfani da tsaki na tensor da lissafin FP32/FP16 ba, ZKPs ba za su iya amfana da waɗannan raka'o'in na musamman a cikin tsarin GPU na yanzu ba. Wannan yana nuna yuwuwar haɗin gwiwar software-kayan aiki, kama da hanyar da aka ɗauka a cikin tsarin TPU na Google don hanyoyin sadarwa na jijiyoyi, amma an keɓance shi don ayyukan sirri. Iyakataccen kama da juna na umarni saboda dogaro da bayanai ya ƙara jaddada buƙatar ƙirƙira na algorithm wanda zai iya bayyana ƙarin kama da juna.

Idan aka kwatanta da sauran ƙoƙarin hanzari na sirri, irin su waɗanda ke da sirri (kamar yadda aka ambata a cikin [9]) ko tsarin lissafi da za a iya tantancewa, ZKProphet ya fi mayar da hankali kan aikin ƙarshe-zuwa-ƙarshe maimakon inganta tsaki ɗaya yana ba da ƙarin haske mai amfani don turawa a duniyar gaske. Ambaton ayyukan koyon injin da za a iya tantancewa a cikin [32] yana nuna ayyuka masu ban sha'awa na ketare yanki inda ZKPs masu hanzari na GPU zasu iya ba da damar sabbin tsarin amana a cikin tsarin AI.

Iyakataccen girman aikin da aka gano a cikin wannan aikin yana da muhimman tasiri ga aiwatar da ZKPs a cikin tsarin samarwa. Yayin da ƙididdigar ƙuntatawa ke ƙaruwa tare da ƙarin rikitattun lissafi, alaƙar ma'auni na layi yana nuna cewa tsarin GPU na yanzu na iya fuskantar iyakoki na asali ba tare da ƙirƙira na gine-gine da aka keɓance musamman ga ayyukan aikin sirri ba.

7. Bayanan da aka yi Amfani da su

1. Groth, J. (2016). "Akan Girman Muhawarar Rashin Hulɗa na Tushen Haɗin gwiwa." EUROCRYPT 2016.
2. Ben-Sasson, E., et al. (2014). "Hujjar Sirri-Sifili Mai Taƙaitacce don Tsarin von Neumann." Taron Tsaro na USENIX.
3. Parno, B., et al. (2013). "Pinocchio: Kusan Aikin Lissafi da za a iya Tantancewa." Taron Tsaro da Sirri na IEEE.
4. Setty, S., et al. (2013). "Warware rikici tsakanin gabaɗaya da yuwuwar a cikin lissafin da aka tantance." EuroSys.
5. Zhang, J., et al. (2020). "vCNN: Cibiyar Sadarwar Jijiyoyi da za a iya Tantancewa bisa zk-SNARKs." Taskar ePrint na Cryptology.
6. Wahby, R.S., et al. (2018). "Cikakken lissafin kuɗi don fitar da aiki." CCS.
7. Kosba, A., et al. (2016). "C∅C∅: Tsarin Gina Hujjojin Sirri-Sifili Masu Haɗawa." Tsaron USENIX.
8. Xie, T., et al. (2022). "zkCNN: Hujjojin Ilimin Sirri don Hasashen Cibiyar Sadarwar Jijiyoyi da Daidaito." CCS.