Exploring Zero-Knowledge Friendly Hash Functions

Hash functions are crucial tools in the world of blockchain and cryptography, helping to keep data secure and intact. Recently, as zero-knowledge proofs have become more popular, there's been a need for hash functions that fit these complex systems better. This article will look at how traditional hash functions work, their role in blockchain technology, and why they're so important for security. We'll also explore why these traditional functions aren't always the best fit for zero-knowledge proofs and introduce some new hash functions—RESCUE, Poseidon, and Poseidon2—that are designed to work well in these scenarios.

What is a Hash Function?

A hash function is a mathematical algorithm that converts input data of any size into a fixed-size string of bytes, typically a hash, which appears random. Hash functions are fundamental in various applications, including data integrity verification, password storage, and digital signatures. They are crucial for ensuring that data has not been altered unknowingly or maliciously. These functions are designed to be fast, deterministic, and collision-resistant, making them effective for a broad range of cryptographic applications.

Hash functions are integral to blockchain technology, serving as the backbone for maintaining the immutable ledger that blockchains are known for. In Bitcoin, SHA-256 is employed not only in transaction processing but also in mining, aiding in the creation of a consistent and secure ledger. Ethereum uses Keccak-256 to ensure the integrity of transactions. Other blockchain systems like Solana and Substrate-based Polkadot use BLAKE3 and xxHash respectively, optimizing for speed and efficiency. Cosmos' Tendermint consensus utilizes SHA-256 and RIPEMD-160 for similar purposes, highlighting the versatility and necessity of hash functions in these environments.

Original Block Details:

• Version: 1
• Previous Block Hash: 00000000000000000008bba8e0a0c675bf8fcf374e8db1c99f6fcbba1ad2ff7a
• Merkle Root: 3a81e543bf23d77e4b12fbcaae638d58c8a8c4932f120de706da0fb7bcdb5f92
• Timestamp: 1631021642
• Bits: 436289524
• Nonce: 1000000000
• Transaction:
  • From: 1A8JiWcwvpY7tAopUkSnGuEYHmzGYfZPiq
  • To: 1JQtt4k6xSMdWzAW4hM4eAA7iMhYYaNCNU
  • Amount: 0.5 BTC
  • Fee: 0.0001 BTC

The Calculated SHA-256 hash is 43ed17cf66496413dfb13974c0e15869dd75589bbd7743901870dd9da9754122

Now, let's consider a variation where the amount in the transaction is changed from 0.5 BTC to 0.6 BTC:

• Amount: 0.6 BTC (changed from 0.5 BTC)

The new calculated SHA-256 hash e529adf4690c2afc14fc14ddf9a698fd2343fd2ef8f4809802f602e273e0ad1e

As you can see, this dramatic change from a minor modification demonstrates the hash function's sensitivity, which is known as the avalanche effect. Such a property is crucial because it ensures that any tampering with transaction data can be easily detected: altering any part of the data results in a completely different hash, signaling that something has been changed. This characteristic is what makes hash functions so valuable for maintaining the integrity and security of blockchain systems like Bitcoin. For a more detailed exploration of hash functions, you can refer to our previous article, which covers the SHA-3 Keccak hashing algorithm in depth.

Hash Functions and L2 Rollups

Layer 2 (L2) rollups, particularly optimistic rollups like those implemented by Optimism, use hash functions to enhance blockchain scalability by handling transactions off the main Ethereum chain. In Optimism's OpStack framework, transactions are executed off-chain, and their results are batched into a cryptographic digest using hash functions, typically Keccak-256, which is also used by Ethereum.

These transaction hashes are then organized into a Merkle tree, where the root of this tree—a single hash summarizing all transactions in the batch—is posted to the main Ethereum chain. This Merkle root is crucial for ensuring the integrity and security of the transaction data recorded on-chain.

If a transaction is challenged, the OpStack framework utilizes fraud proofs, where validators can verify the transaction's validity by recomputing hashes and comparing them with those in the submitted Merkle proof. Discrepancies in these hashes can invalidate the transaction, proving its fraudulence.

In zero-knowledge rollups, transactions are grouped and processed off-chain, where each transaction's results are converted into a cryptographic proof. These proofs, which are succinct and require minimal computation to verify, are then aggregated into a single proof representing the entire batch of transactions.

This aggregated proof, often structured using a Merkle tree, is then posted to the main blockchain. The root of this Merkle tree provides a hash that condenses all transaction proofs into one, ensuring that the entire batch can be verified quickly and efficiently. This process does not require the transaction details to be revealed on the main chain, thus preserving privacy.

Zero-knowledge rollups use these hash functions not just for creating cryptographic proofs but also for ensuring that the proofs are compact and can be verified quickly on the blockchain, significantly reducing the computational burden and enhancing throughput. The choice of hash function in this context is critical, as it needs to balance computational efficiency with cryptographic security to be effective for blockchain applications.

Limitations of Current Hash Functions in Zero-Knowledge Systems

Traditional hash functions like SHA-256 are fundamental in numerous cryptographic applications due to their security and reliability. However, when it comes to zero-knowledge proof systems, particularly those used in blockchain technology, these functions encounter significant limitations due to their complex structure, which is not optimized for zero-knowledge circuits.

Zero-knowledge proof systems require the construction of a computational circuit where every operation translates into a mathematical constraint that the verifier checks. The effectiveness and efficiency of a zero-knowledge proof rely heavily on the complexity and number of these constraints. A hash function that is suitable for zero-knowledge systems needs to minimize the number of constraints to optimize the size and speed of the proof verification process.

Traditional hash functions like SHA-256 are designed to be secure and robust against attacks, involving numerous bitwise operations, modular additions, and logical shifts. These operations are specifically chosen because modern CPUs offer native support for them, making these hash functions extremely efficient under normal execution conditions. The design of these functions is optimized for speed and low computational overhead when running on conventional hardware, which can directly execute these bitwise operations.

When these operations are translated into the arithmetic constraints of a zero-knowledge circuit, each computational step must be translated into arithmetic constraints suitable for the cryptographic field operations that underpin zero-knowledge proofs. Specifically, each operation in the zero-knowledge circuit must be represented as an equation, typically with a left-hand side (LHS) and a right-hand side (RHS), involving operations over a finite field - as described in more details in our previous article.

The result is a large and "bloated" circuit. A bloated circuit means more computational overhead and higher costs for generating and verifying proofs. In blockchain contexts, where efficiency and speed are paramount, this can lead to slower transaction verifications and increased costs for users. For example, in SHA-256, each round of the hash function includes a series of complex operations that, when converted into constraints for a zero-knowledge proof, dramatically increase the computational resources required to process and verify proofs.

Specialized Hash Functions

To address these issues, there is a growing demand for specialized hash functions that are tailored to the needs of zero-knowledge proof systems. These functions need to be "symmetric" in terms of their constraint count, ensuring that they do not disproportionately increase the number of constraints with each operation. Ideal zero-knowledge friendly hash functions, such as Poseidon or MiMC, are designed to have a lower arithmetic complexity and fewer multiplicative constraints. These functions reduce the circuit size by using simple algebraic operations that are more naturally compatible with the field arithmetic used in zero-knowledge proofs.

By integrating hash functions with lower constraint complexities, zero-knowledge systems can achieve the dual goals of maintaining robust security while also enhancing proof generation and verification efficiency. This improvement is crucial for scaling blockchain technologies and making advanced cryptographic techniques like zero-knowledge proofs more practical and accessible in real-world applications.

RESCUE, Poseidon, and Poseidon2 represent advancements in the development of hash functions tailored for zero-knowledge applications. RESCUE and Poseidon are designed with a focus on efficiency in field operations, crucial for SNARKs and STARKs. These functions are structured to minimize the number of expensive cryptographic operations, thereby speeding up the proof generation and verification process. Poseidon2, an iteration on Poseidon, introduces optimizations that further reduce computational overhead and improve integration with newer zero-knowledge proof frameworks.

MiMC

Speed: MiMC (MiniMixColumns) is specifically designed to minimize the number of multiplicative constraints in a zero-knowledge circuit. It relies on a single non-linear operation—raising the input to an odd power (typically 3 or 5)—followed by an addition, making it computationally lightweight. Security: MiMC offers security through a simple yet secure round function. However, its security has been scrutinized, particularly regarding potential algebraic attacks, requiring careful analysis and implementation. Usage: MiMC has found application in projects like ZoKrates, a zero-knowledge toolkit for Ethereum, and in various academic studies exploring zero-knowledge proof efficiencies.

RESCUE

Speed: RESCUE is designed to balance both speed and security by minimizing the number of constraints per round. It alternates between two different types of permutations: one based on a power function, and another based on its inverse. This balanced structure reduces the number of necessary multiplicative constraints. Security: RESCUE's design also mitigates certain types of cryptographic attacks, including differential and algebraic attacks, through its well-structured rounds and non-linear operations. Usage: RESCUE is gaining traction in the zero-knowledge ecosystem, with interest from projects focused on scalable and efficient cryptographic solutions, including blockchain protocols and privacy-focused applications.

Poseidon

Speed: Poseidon is highly optimized for zero-knowledge circuits, using a S-box based on raising the input to a specific power (usually 5), combined with an efficient linear layer, minimizing the total number of multiplicative constraints per round. Security: Poseidon provides robust security against differential and linear cryptanalysis through its careful choice of round functions and constant values. Its design has been subject to extensive peer review and cryptographic analysis. Usage: Poseidon is widely adopted across the zero-knowledge ecosystem. It's used in several protocols, including Matter Labs' zkSync, a Layer 2 scaling solution for Ethereum, and is also supported by various zero-knowledge proof libraries, making it a popular choice in blockchain applications.

Poseidon2

Speed: Poseidon2 is an improved version of Poseidon, designed to further reduce circuit complexity and enhance speed. It achieves this by simplifying its round functions and reducing the number of rounds needed, thus lowering the total number of constraints. Security: Poseidon2 maintains the robust security features of its predecessor, including resistance to differential and linear cryptanalysis, and offers even greater security guarantees through more optimized parameter choices. Usage: Poseidon2 is gaining adoption in new zero-knowledge projects, especially those that require efficient proof generation and verification processes, such as Layer 2 rollups and privacy-focused blockchain protocols.

Conclusion

In comparison, MiMC, RESCUE, Poseidon, and Poseidon2 each offer unique advantages for zero-knowledge applications. MiMC's simplicity makes it ideal for lightweight circuits, though its security necessitates scrutiny. RESCUE's balanced design offers both speed and security, making it an increasingly popular choice. Poseidon and its successor Poseidon2 stand out for their comprehensive optimization, making them well-suited for various zero-knowledge proof systems, particularly in the blockchain space. Their adoption by numerous projects underscores the critical role these hash functions play in ensuring secure and efficient cryptographic proofs.