Poseidon Cryptanalysis Initiative 2024-2026
Ethereum Foundation
Scrutinizing Poseidon for Good
Introduction
Poseidon and Poseidon2 are hash functions designed for the use in verifiable computation protocols. They have been optimized for the smallest circuit size over prime fields.
Poseidon hash function has been used in numerous Ethereum applications that deal with verifiable computation. It is among the top performers at recent STARK benchmarks by StarkNet, which makes it a promising candidate for the use at Ethereum L1 for various protocols that employ ZK proofs.
This project aims to boost the security investigation of various Poseidon instances and eventually decide whether there is sufficient evidence that is secure for high-value applications and foundations of Ethereum. Below we present the details of the Phase 1 of this project, which ends in December 2025. Phase 2 will be planned in mid-2025, and shall conclude in December 2026.
Running Team
The project is run by the Ethereum Foundation Poseidon Group (EFPG: poseidon@ethereum.org ):
George Kadianakis
Dmitry Khovratovich
Antonio Sanso
The Advisory Board oversees key decisions and announcements made by EFPG, with members serving in an unpaid capacity:
Jean-Philippe Aumasson (Taurus)
Eli Ben-Sasson (Starknet)
Daira-Emma Hopwood (ZCash)
Daniel Lubarov (PolygonZero)
Ron Rothblum (Succinct)
Documentation on Poseidon
Bounty Program
Bounty program runs till December 1st, 2025. The idea of the bounty program is twofold:
Ensure that the interpolation attack is the fastest preimage attack on Poseidon.
Verify that the complexity of the interpolation attack on the reduced round versions matches the theoretical estimates.
These ideas are implemented as follows: we take original instances of Poseidon and Poseidon2, which claim 128-bit preimage security, and reduce the number of rounds such that the interpolation attack becomes feasible. The expected complexity of the attack 2^T is then used to claim “T-bit estimated security”. If either of our assumptions is violated then a better attack should be found.
Hash function instances in the program:
Poseidon-256 (the original Poseidon paper, the finite field being the scalar field of the BLS12-381 elliptic curve). Degree `d` of power mapping is 5, the state size `t` is 3. The matrix from the reference implementation.
Poseidon-64 (the Poseidon2 paper, the finite field based on a Goldilocks prime 2^{64}-2^{32}+1). Degree `d` of power mapping is 7, the state size `t` is 8.
Poseidon-31 (the Poseidon2 paper, two options:
the finite field being the M31 prime 2^{31}-1 = 2147483647. Degree `d` of power mapping is 5, the state size `t` is 16.
the finite field being the KoalaBear 2^{31}-2^{24}+1 = 2130706433). Degree `d` of power mapping is 3, the state size `t` is 16.
The task is to find a preimage of 0, or, more precisely:
For Poseidon-256 a 256-bit preimage: find X1, X2, Y1, Y2 such that Perm(X1,X2,0)= (Y1,Y2,0)
For Poseidon-64 a 64-bit preimage: find X1,..., X7, Y1,... Y7 such that Perm(X1,...,X7,0)= (Y1,...,Y7,0)
For Poseidon-31 a 62-bit preimage: find X1,..., X14, Y1,... Y14 such that Perm(X1,...,X14,0,0)= (Y1,...,Y14,0,0)
where Perm is the inner sponge permutation (bijective mapping) of the hash function the challenge list.
We encourage cryptanalysts to find an improved attack variant (such as “skipping first rounds” trick) rather than to find a solution with a brute force. New attack ideas might qualify for a bonus.
Common terms:
Solutions should be sent to the Ethereum Foundation Poseidon Group poseidon@ethereum.org .
First come first win. Solutions sent within 1 day period after the first one --- will be considered.
Within 1 month after the submission the authors should provide a technical report with the attack description, which should be released to the public domain at latest December 1st 2025. The code should be also made public before this date.
Total Bounty Budget -- $130 000.
Concrete bounties (details here):
Poseidon-256:
24-bit estimated security: RF=6, RP=8. $4000
28-bit estimated security: RF=6, RP=9. $6000
32-bit estimated security: RF=6, RP=11. $10000
40-bit estimated security: RF=6, RP=16. $15000
Poseidon-64:
24-bit estimated security: RF=6, RP=7 $4000
28-bit estimated security: RF=6, RP=8. $6000
32-bit estimated security: RF=6, RP=10. $10000
40-bit estimated security: RF=6, RP=13. $15000
Poseidon-31:
24-bit estimated security: RF=4, RP=0 (M31) and RP=1 (KoalaBear). $4000 claimed and verified
28-bit estimated security: RF=4, RP=1 (M31) and RP=3 (KoalaBear). $6000 claimed
32-bit estimated security: RF=6, RP=1 (M31) and RP=4 (KoalaBear). $10000
40-bit estimated security: RF=6, RP=4 (M31 only). $15000
We expect that the best attack that solves these bounties is an interpolation attack. A Groebner basis attack that breaks any of these instances may qualify for an additional bonus.
Attack Reward Program
A research paper, which describes an attack on a reduced-round Poseidon, may qualify for a prize. It has to conform to the following rules:
Attack should be on a reduced-round version of one of three instances described above: Poseidon-256, Poseidon-64, or Poseidon-31.
Attack should be an improvement to the attacks presented in the survey
The attack should break one of properties:
collision resistance for 256-bit output
(first or second) preimage resistance for 256-bit or 128-bit output
correlation intractability for relations arising from post-quantum proofs of knowledge (details later)
The paper should be made public (ePrint) by the end of 2025.
The amount of the award is proportional to the paper merit and remains at discretion of Ethereum Foundation. The minimal prize is $5000, the entire award fund is $90000.
Groebner Basis Exploratory
Existing Groebner basis research papers on Poseidon have very imprecise complexity estimates. We would like to launch a more detailed investigation of attack complexity so that the complexity of a full attack can be extrapolated from the ones on small instances.
We provide research grants to derive a formula for Groebner basis preimage attacks arising from round equations. Concretely, we ask the following:
Construct a DRL-order Groebner basis using F4 or F5 GB algorithms for reduced-round versions of Poseidon-256, -64, -31, as specified in the Bounty Program, for all feasible combinations of RF and RP.
Construct, if possible, a Groebner basis manually for other orders but same instances.
Run the basis conversion algorithm in order to get the LEX basis from the bases obtained at previous steps..
Solve the preimage problem by factoring a univariate polynomial from the LEX basis.
The complexity of these steps should be counted separately, both in terms of memory requirements and CPU operations. From the table of practical complexities, a formula for the full instance should be extrapolated.
The investigation is supposed to be done in close collaboration with the EF Poseidon Group. Questions should be sent to poseidon@ethereum.org
Applications should be made at Ethereum Foundation website by January 1st, 2025. They will be processed in the order of receiving.
Workshops and Retreats
We plan to support workshops, retreats, and schools that are devoted to the cryptanalysis of Poseidon and related designs. Among those are
ALPSY workshop in January 2025
FSE-affiliated event in March 2025
Event in May 2025 (in preparation, possibly Eurocrypt-aligned).
Short Term Grants
We have compiled a list of research problems which appear necessary to understand the security of Poseidon instances further. The grant amount ranges from $20000 to $40000, depending on the deliverables that are suggested by the applicants.
Applications should be made at Ethereum Foundation website by January 1st, 2025. They will be processed in the order of receiving.
Constructing an explicit Groebner basis
We invite a research in constructing explicit Groebner basis using some non-common ordering, follow the recent preprint. Such a construction should be accompanied by a trial application of the FGLM or a related algorithm to get a LEX-order basis.
Analysis of small field versions
We invite research on instances of Poseidon that use a very small field size, as long as MDS matrices can be constructed there.
Security over extension fields
Currently Poseidon is defined over prime fields of various size. Parameters for extension fields are unknown as most attacks are not evaluated over such fields. Still some applications are looking for such instances in order to get higher performance or security.
We are looking for the analysis of Poseidon variants where the underlying field is an extension of some prime field, for example M31.
Attack with resultants
With the emergence of AOHs, Gröbner basis attacks have gained significant attention. However, alternative system-solving approaches, such as resultants, have also recently proven useful in the cryptanalysis of primitives like Anemoi, Jarvis, and Rescue-Prime. Expanding the application of resultants could enhance and diversify the quality of security evaluations of Poseidon-like constructions too.
Reducing constants
Currently the round constants for all Poseidon versions are generated in the pseudo-random manner. We are interested in the research whether one can use low-weight constants and use them less frequently.
Security of partial rounds w.r.t. statistical attacks
We invite research on non-algebraic attacks that cover partial rounds. We are particularly interested in attacks that might exploit non-MDS matrices in Poseidon2.
Clustering differential trails
Many algebraic hash functions argue the statistical security from the fact that any differential trail would pass a certain number of nonlinear components and thus has low ``probability''. However, little is known about possible clustering of such differential trails into truncated differentials, or linear relations into linear hulls for such designs.
We are looking for
Research that could prove that truncated differentials also have low probability for certain number of rounds;
Research that could show the clustering into high-probability properties is possible in weak or maliciously crafted instances.
Provable security
While many arithmetic hash functions come with a built-in provable protection against statistical attacks, rather little is known about resistance to algebraic attacks. The arguments supporting the algebraic security are, in the nutshell, the evidence of the high-degree of the transformation and an argument that equations for the Groebner attacks are numerous and have high degree and/or many variables. We would like to see some more universal evidence of such security, for example Security bounds for a transformation modelled as an iteration of random low-degree operations, in the style of Luby-Rackoff proofs.
It would also be interesting to derive provable security for designs which are not necessarily efficient when compared to modern (unproven) approaches. For example, one such idea would be to specifically start with a unique representation of an algebraic structure for which strong arguments about its solving complexity can be made. This structure may then be transformed into a symmetric primitive mimicking the same behavior, but not necessarily being efficient.
Attacks on Fiat-Shamir usage
We are looking into attacks on (reduced-round) instances of Poseidon which would break the security of non-interactive cryptographic protocols obtained via the Fiat-Shamir heuristic, where Poseidon would be used to generate public coins. Applicants are free to choose protocols at their own.
Eligibility
The standard EF rules for small grants apply. Poseidon authors can not be applicants to the grants nor to the award program.
Disclaimer
Ethereum Foundation Poseidon Group includes Dmitry Khovratovich, one of the designers of Poseidon. Dmitry and the Poseidon team contributed to defining the bounty parameters and structuring the research grant program. Decisions on awarding grants and distributing bounties will be made by the members of the Ethereum Foundation Poseidon Group in consultation with the Advisory Board.
ChangeLog
30 Nov 2024 -- 28-bit bounty claimed for Poseidon-31
29 Nov 2024 -- 24-bit bounty claimed for Poseidon-31
29 Nov 2024 -- a typo in the Koala Bear prime definition was fixed (2^32 -> 2^31 )