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.

Comments

Post a Comment

Popular posts from this blog

CAP Theorem and blockchain

Image
In theoretical computer science, the CAP theorem states that it is impossible for a distributed data store (such as a blockchain network) to simultaneously provide more than two out of the three guarantees: Consistency, Availability & Partition tolerance. CAP Theorem – the parts C: Consistency – At any given time, all nodes in the network have exactly the same (most recent) value. A: Availability – Every request to the network receives a response, though without any guarantee that returned data is the most recent. P: Partition tolerance – The network continues to operate, even if an arbitrary number of nodes are failing. Due to the nature of distributed data stores (such as blockchain), Partition tolerance is a given fact; there will always be failing/unreachable nodes in the network (not least because of the unstable nature of the internet). CAP Theorem states that one has to choose between C (Consistency) or A (Availability) when in the presence of P (Partition): Av...
Read more

Length extension attack

Image
What is length extension? When a Merkle–Damgård based hash is misused as a message authentication code with construction H(secret ‖ message), and message and the length of secret is known, a length extension attack allows anyone to include extra information at the end of the message and produce a valid hash without knowing the secret. Quick sidebar, before you freak out: Since HMAC does not use this construction, HMAC hashes are not prone to length extension attacks. So, a length extension attack is a type of attack where an attacker can use Hash(message1) and the length of message1 to calculate Hash(message1 ‖ message2) for an attacker-controlled message2, without needing to know the content of message1. Algorithms like MD5, SHA-1 and most of SHA-2 that are based on the Merkle–Damgård construction are susceptible to this kind of attack. Truncated versions of SHA-2, including SHA-384 and SHA-512/256 are not susceptible, nor is the SHA-3 algorithm. A bit more details ...
Read more

Contract upgrade anti-patterns

Image
A popular trend in smart contract design is to promote the development of upgradable contracts . To be fair, existing techniques to upgrade contracts have flaws, increase the complexity of the contract significantly, and ultimately introduce bugs - even in the Zeppelin contract upgrade strategy. In this article, we are going to detail our analysis of existing smart contract upgrade strategies, describe the weaknesses we have observed in practice, and provide recommendations for contracts that require upgrades. In a follow-up blog post, we will detail a method, contract migration, that achieves the same benefits with few of the downsides. An overview of upgradable contracts Two ‘families’ of patterns have emerged for upgradable smart contracts: Data separation, where logic and data are kept in separate contracts. The logic contract owns and calls the data contract. Delegatecall-based proxies, where logic and data are kept in separate contracts, also, but the data contr...
Read more