ZK-protokoll använder speciella hashfunktioner som är algebraiskt enkla. Men skulle vi kunna göra det bättre om vårt bevissystem hade stöd för uppslagstabeller? Vi presenterar Polocolo: en ny ZK-vänlig hashfunktion för PlonKup, som Zellic Cryptographer @baaaaaarkingdog har varit medförfattare till.

I ZK-vänliga hashfunktioner är funktionerna algebraiskt enkla för effektivitet. Så en attack mot en ZK-vänlig hash-funktion fokuserar på problemet med constrained-input constrained-output (CICO), eftersom att lösa ekvationssystemet vanligtvis är den mest effektiva attacken mot ZK-vänliga hashfunktioner. Även om konstruktörer noggrant väljer sina strukturer och parametrar med dessa attackvektorer i åtanke, är det fortfarande vanligt att ZK-vänliga hashfunktioner attackeras.

Om ZK-bevissystemet endast tillåter additions- och multiplikativa grindar, kräver operationer som inte kan representeras algebraiskt helt enkelt ett stort antal begränsningar. Men om ZK-proof-systemet stöder uppslagsportar minskar det nödvändiga antalet grindar dramatiskt. Så den största fördelen med att använda uppslagsportar i ZK-vänliga hashfunktioner är att de inte uttrycks på ett enkelt algebraiskt sätt, vilket kan ge motstånd mot algebraiska attacker.

Armerad betong är den första uppslagsbaserade ZK-vänliga hashfunktionen, som består av lager av tegelstenar, betong och barer (det är här uppslagstabeller används). En viktig nackdel är dock den höga kostnaden för att utvärdera Bars-lagret i en ZK-inställning. Av de 15 skikten i armerad betong är det bara ett som är barlagret. Det är önskvärt och naturligt att iterera ett enkelt lager över flera omgångar eftersom att minska kostnaden för Bars-lagret och iterera det över flera omgångar kan förbättra säkerheten och möjliggöra en kompromiss mellan effektivitet och säkerhet. Detta motiverar Polocolos design.

För att ta itu med de höga kostnaderna i Bars-lagret föreslogs ett alternativt tillvägagångssätt, kallat Power residue-metoden. Polocolo är en uppslagsbaserad ZK-vänlig hashfunktion med en annan designlogik. Namnet Polocolo härstammar från strömrester för att slå upp tabeller med lägre kostnad.

Metoden för effektrester tillämpar effektivt uppslagstabeller på Fp-element för ett stort primtal: p(≈2^256). S-boxen som byggs med hjälp av power residue-metoden är av en hög grad som endast kräver 14 PLONK-grindar, vilket är betydligt färre än de 94 grindar som krävs för Bar-funktionen från armerad betong. Med hjälp av denna S-box föreslår vi Polocolo, en ny uppslagsbaserad ZK-vänlig hashfunktion.

Polocolo designades av Zellic Cryptographer @baaaaaarkingdog, en medlem av KAIST CryptLab, tillsammans med andra forskare från samma labb. I del 2 kommer vi att presentera de detaljerade specifikationerna och kryptoanalysen för Polocolo, tillsammans med en prestandajämförelse med andra ZK-vänliga hashfunktioner.