HomeEIPs
EIPsEIP-5988
EIP-5988

Add Poseidon hash function precompile

Add a precompiled contract which implements the hash function used in the Poseidon cryptographic hashing algorithm
StagnantStandards Track: Core
Created: 2022-11-15
Abdelhamid Bakhta (@abdelhamidbakhta), Eli Ben Sasson (@Elistark), Avihu Levy (@avihu28), David Levit Gurevich (@DavidLevitGurevich)
DiscussionsOriginal linkEdit
1 min read

The EIP-5988 proposal suggests adding a precompiled contract to Ethereum that implements the hash function used in the Poseidon cryptographic hashing algorithm. This is intended to allow interoperability between the EVM and ZK/Validity rollups, as well as introducing more flexible cryptographic hash primitives to the EVM. The Poseidon hash function is particularly well-suited for building efficient ZK/Validity rollups on Ethereum, and is compatible with all major proof systems. The precompile will support arbitrary parameters, allowing ZK rollups to choose the parameters they want to use. The proposal includes specifications for the precompile, as well as test cases and security considerations.

Video
Anyone may contribute to propose contents.
Go propose
Original

Abstract

This EIP introduces a new precompiled contract which implements the hash function used in the Poseidon cryptographic hashing algorithm, for the purpose of allowing interoperability between the EVM and ZK / Validity rollups, as well as introducing more flexible cryptographic hash primitives to the EVM.

Motivation

Poseidon is an arithmetic hash function that is designed to be efficient for Zero-Knowledge Proof Systems. Ethereum adopts a rollup centric roadmap and hence must adopt facilities for L2s to be able to communicate with the EVM in an optimal manner.

ZK-Rollups have particular needs for cryptographic hash functions that can allow for efficient verification of proofs.

The Poseidon hash function is a set of permutations over a prime field, which makes it particularly well-suited for the purpose of building efficient ZK / Validity rollups on Ethereum.

Poseidon is one of the most efficient hashing algorithms that can be used in this context. Moreover it is compatible with all major proof systems (SNARKs, STARKs, Bulletproofs, etc...). This makes it a good candidate for a precompile that can be used by many different ZK-Rollups.

An important point to note is that ZK rollups using Poseidon have chosen different sets of parameters, which makes it harder to build a single precompile for all of them.

However, we can still build a generic precompile that supports arbitrary parameters, and allow the ZK rollups to choose the parameters they want to use.

This is the approach that we have taken in this EIP.

Specification

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.

Parameters

ConstantValue
FORK_BLKNUMTBD
GAS_COSTTBD
POSEIDON_PRECOMPILE_ADDRESS0xA

Here are the Poseidon parameters that the precompile will support:

Parameter nameDescriptionEncoding size (in bytes)Comments
pPrime field modulus32
security_levelSecurity level measured in bits. Denoted M in the Poseidon paper2
alphaPower of S-box1
input_rateSize of input2
tSize of the state1
full_roundNumber of full rounds. Denoted as R_F in the Poseidon paper.1
partial_roundNumber of partial rounds. Denoted as R_P in the Poseidon paper.1
inputInput to the hash functioninput_rate * 32

The encoding of the precompile input is the following:

[32 bytes for p][2 bytes for security_level][1 byte for alpha][2 bytes for input_rate][1 byte for t][1 byte for full_round][1 byte for partial_round][input_rate * 32 bytes for input]

The precompile should compute the hash function as specified in the Poseidon paper and return hash output.

Rationale

TODO: Add rationale

TODO: Add rationale for gas cost e.g. benchmark and computation cost estimation.

Backwards Compatibility

There is very little risk of breaking backwards-compatibility with this EIP, the sole issue being if someone were to build a contract relying on the address at 0xPOSEIDON_PRECOMPILE_ADDRESS being empty. The likelihood of this is low, and should specific instances arise, the address could be chosen to be any arbitrary value with negligible risk of collision.

Test Cases

The Poseidon reference implementation contains test vectors that can be used to test the precompile. Those tests are available here.

Security Considerations

Quoting Vitalik Buterin from Arithmetic hash based alternatives to KZG for proto-danksharding thread on EthResearch:

The Poseidon hash function was officially introduced in 2019. Since then it has seen considerable attempts at cryptanalysis and optimization. However, it is still very young compared to popular “traditional” hash functions (eg. SHA256 and Keccak), and its general approach of accepting a high level of algebraic structure to minimize constraint count is relatively untested. There are layer-2 systems live on the Ethereum network and other systems that already rely on these hashes for their security, and so far they have seen no bugs for this reason. Use of Poseidon in production is still somewhat “brave” compared to decades-old tried-and-tested hash functions, but this risk should be weighed against the risks of proposed alternatives (eg. pairings with trusted setups) and the risks associated with centralization that might come as a result of dependence on powerful provers that can prove SHA256.

It is true that arithmetic hash functions are relatively untested compared to traditional hash functions. However, Poseidon has been thoroughly tested and is considered secure by multiple independent research groups and layers 2 systems are already using it in production (StarkWare, Polygon, Loopring) and also by other projects (e.g. Filecoin).

Moreover, the impact of a potential vulnerability in the Poseidon hash function would be limited to the rollups that use it.

We can see the same rationale for the KZG ceremony in the EIP-4844, arguing that the risk of a vulnerability in the KZG ceremony is limited to the rollups that use it.

List of projects (non exhaustive) using Poseidon:

  • StarkWare plans to use Poseidon as the main hash function for StarkNet, and to add a Poseidon built-in in Cairo.
  • Filecoin employs POSEIDON for Merkle tree proofs with different arities and for two-value commitments.
  • Dusk Network uses POSEIDON to build a Zcash-like protocol for securities trading.11 It also uses POSEIDON for encryption as described above.
  • Sovrin uses POSEIDON for Merkle-tree based revocation.
  • Loopring uses POSEIDON for private trading on Ethereum.
  • Polygon uses Poseidon for Hermez ZK-EVM.

In terms of security, the choice of parameters is important.

Security of the Poseidon parameters

Choice of the MDS matrix

The MDS matrix is a square matrix of size t * t that is used to mix the state.

This matrix is used during the MixLayer phase of the Poseidon hash function.

The matrix must be chosen s.t. no subspace trail with inactive/active S-boxes can be set up for more than t -1 rounds.

There are some efficient algorithms to detect weak MDS matrices.

Those algorithms are described in the Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer paper.

The process of the generation of the matrix should look like this, as recommended in the Poseidon paper:

  1. Generate a random matrix.
  2. Check if the matrix is secure using Algorithm 1, Algorithm 2, and Algorithm 3 provided Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer paper.
  3. If the matrix is not secure, go back to step 1.

Copyright and related rights waived via CC0.

Further reading
Anyone may contribute to propose contents.
Go propose
Adopted by projects
Anyone may contribute to propose contents.
Go propose

Not miss a beat of EIPs' update?

Subscribe EIPs Fun to receive the latest updates of EIPs Good for Buidlers to follow up.

View all
Serve EIP builders, scale Ethereum.
Resources
GitHub
Supported by