Os protocolos ZK utilizam funções de hash especiais que são algébrica e simplesmente. Mas se o nosso sistema de prova suportasse tabelas de consulta, poderíamos fazer melhor? Apresentando Polocolo: uma nova função de hash amigável para ZK para PlonKup, co-autoria do criptógrafo da Zellic @baaaaaarkingdog.

Em funções de hash amigáveis a ZK, as funções são algebraicamente simples para eficiência. Assim, um ataque contra uma função de hash amigável a ZK foca no problema de entrada e saída restritas (CICO), uma vez que resolver o sistema de equações é geralmente o ataque mais eficaz contra funções de hash amigáveis a ZK. Embora os designers escolham cuidadosamente suas estruturas e parâmetros tendo em mente esses vetores de ataque, ainda é comum que funções de hash amigáveis a ZK sejam atacadas.

Se o sistema de prova ZK apenas permitir portas de adição e multiplicação, operações que não podem ser representadas algebricamente simplesmente requerem um grande número de restrições. Mas se o sistema de prova ZK suportar portas de pesquisa, o número necessário de portas é dramaticamente reduzido. Portanto, a principal vantagem de usar portas de pesquisa em funções hash amigáveis ao ZK é que elas não são expressas de uma maneira algébrica simples, o que pode proporcionar resistência a ataques algébricos.

O Concreto Armado é a primeira função hash amigável a ZK baseada em lookup, que consiste em camadas de Tijolos, Concreto e Barras (é aqui que são usadas tabelas de consulta). No entanto, uma desvantagem chave é o alto custo de avaliar a camada de Barras em um ambiente ZK. Das 15 camadas no Concreto Armado, apenas uma é a camada de Barras. É desejável e natural iterar uma camada simples por várias rodadas, pois reduzir o custo da camada de Barras e iterá-la por várias rodadas pode aumentar a segurança e permitir um equilíbrio entre eficiência e segurança. Isso motiva o design do Polocolo.

Para abordar o alto custo na camada Bars, foi proposta uma abordagem alternativa, chamada método de resíduo de potência. Polocolo é uma função hash amigável ao ZK baseada em lookup, com uma racionalidade de design diferente. O nome Polocolo deriva de resíduo de potência para uma busca em tabela de menor custo.

O método de resíduos de potência aplica eficientemente tabelas de consulta a elementos Fp para um grande primo: p(≈2^256). A S-box construída usando o método de resíduos de potência é de um grau elevado que requer apenas 14 portas PLONK, o que é significativamente menos do que as 94 portas necessárias para a função Bar do Concreto Reforçado. Usando esta S-box, propomos o Polocolo, uma nova função hash amigável a ZK baseada em lookup.

Polocolo foi concebido pelo criptógrafo Zellic @baaaaaarkingdog, um membro do KAIST CryptLab, juntamente com outros pesquisadores do mesmo laboratório. Na Parte 2, iremos apresentar as especificações detalhadas e a criptoanálise do Polocolo, juntamente com uma comparação de desempenho com outras funções de hash amigáveis ao ZK.