ZK protocols use special hash functions that are algebraically simple. But if our proof system supported lookup tables, could we do better? Introducing Polocolo: a new ZK-friendly hash function for PlonKup, co-authored by Zellic Cryptographer @baaaaaarkingdog.

In ZK-friendly hash functions, the functions are algebraically simple for efficiency. So an attack against a ZK-friendly hash function focuses on the constrained-input constrained-output (CICO) problem, as solving the system of equations is usually the most effective attack against ZK-friendly hash functions. Although designers carefully choose their structures and parameters with these attack vectors in mind, it’s still common for ZK-friendly hash functions to be attacked.

If the ZK proof system only allows addition and multiplicative gates, operations that cannot be represented algebraically simply require a large number of constraints. But if the ZK proof system supports lookup gates, the required number of gates is dramatically reduced. So the main advantage of using lookup gates in ZK-friendly hash functions is that they are not expressed in a simple algebraic way, which can provide resistance to algebraic attacks.

Reinforced Concrete is the first lookup-based ZK-friendly hash function, which consists of Bricks, Concrete, and Bars layers (this is where lookup tables are used). However, a key drawback is the high cost of evaluating the Bars layer in a ZK setting. Out of the 15 layers in Reinforced Concrete, only one is the Bars layer. It’s desirable and natural to iterate a simple layer over multiple rounds as reducing the cost of the Bars layer and iterating it over multiple rounds may enhance security and allow a trade-off between efficiency and security. This motivates Polocolo’s design.

To address the high cost in the Bars layer, an alternative approach was proposed, dubbed the power residue method. Polocolo is a lookup-based ZK-friendly hash function with a different design rationale. The name Polocolo derives from power residue for lower cost table lookup.

The power residue method efficiently applies lookup tables to Fp elements for a large prime: p(≈2^256). The S-box built using the power residue method is of a high degree that requires only 14 PLONK gates, which is significantly fewer than the 94 gates required for the Bar function from Reinforced Concrete. Using this S-box, we propose Polocolo, a new lookup-based ZK-friendly hash function.

Polocolo was designed by Zellic Cryptographer @baaaaaarkingdog, a member of the KAIST CryptLab, along with fellow researchers from the same lab. In Part 2, we’ll introduce the detailed specifications and cryptanalysis of Polocolo, along with a performance comparison with other ZK-friendly hash functions.