ZK-protokoller bruker spesielle hash-funksjoner som er algebraisk enkle. Men hvis bevissystemet vårt støttet oppslagstabeller, kunne vi gjøre det bedre? Vi introduserer Polocolo: en ny ZK-vennlig hash-funksjon for PlonKup, medforfatter av Zellic Cryptographer @baaaaaarkingdog.

I ZK-vennlige hash-funksjoner er funksjonene algebraisk enkle for effektivitet. Så et angrep mot en ZK-vennlig hash-funksjon fokuserer på CICO-problemet (constrained-input constrained-output), ettersom det å løse ligningssystemet vanligvis er det mest effektive angrepet mot ZK-vennlige hash-funksjoner. Selv om designere nøye velger sine strukturer og parametere med disse angrepsvektorene i tankene, er det fortsatt vanlig at ZK-vennlige hash-funksjoner blir angrepet.

Hvis ZK-bevissystemet bare tillater addisjon og multiplikative porter, krever operasjoner som ikke kan representeres algebraisk, ganske enkelt et stort antall begrensninger. Men hvis ZK-bevissystemet støtter oppslagsporter, reduseres det nødvendige antallet porter dramatisk. Så den største fordelen med å bruke oppslagsporter i ZK-vennlige hash-funksjoner er at de ikke uttrykkes på en enkel algebraisk måte, noe som kan gi motstand mot algebraiske angrep.

Armert betong er den første oppslagsbaserte ZK-vennlige hash-funksjonen, som består av murstein, betong og stenger (det er her oppslagstabeller brukes). En viktig ulempe er imidlertid de høye kostnadene ved å evaluere Bars-laget i en ZK-innstilling. Av de 15 lagene i armert betong er bare ett Bars-laget. Det er ønskelig og naturlig å iterere et enkelt lag over flere runder, da det å redusere kostnadene for Bars-laget og iterere det over flere runder kan forbedre sikkerheten og tillate en avveining mellom effektivitet og sikkerhet. Dette motiverer Polocolos design.

For å adressere de høye kostnadene i Bars-laget, ble det foreslått en alternativ tilnærming, kalt kraftrestmetoden. Polocolo er en oppslagsbasert ZK-vennlig hash-funksjon med en annen designbegrunnelse. Navnet Polocolo stammer fra strømrester for billigere tabelloppslag.

Potensrestmetoden bruker effektivt oppslagstabeller på Fp-elementer for et stort primtall: p(≈2^256). S-boksen som er bygget med kraftrestmetoden er av høy grad som krever bare 14 PLONK-porter, noe som er betydelig færre enn de 94 portene som kreves for stangfunksjonen fra armert betong. Ved å bruke denne S-boksen foreslår vi Polocolo, en ny oppslagsbasert ZK-vennlig hash-funksjon.

Polocolo ble designet av Zellic Cryptographer @baaaaaarkingdog, et medlem av KAIST CryptLab, sammen med andre forskere fra samme laboratorium. I del 2 introduserer vi de detaljerte spesifikasjonene og kryptoanalysen til Polocolo, sammen med en ytelsessammenligning med andre ZK-vennlige hash-funksjoner.