Poseidon Parameter Generation
The problem of Poseidon parameter generation is to pick secure choices for the parameters used in the permutation given the field, desired security level in bits, as well as the width of the hash function one wants to instantiate (i.e. 1:1 hash, 2:1 hash, etc.).
Poseidon parameters consist of:
- Choice of S-box: choosing the exponent for the S-box layer where ,
- Round numbers: the numbers of partial and full rounds,
- Round constants: the constants to be added in the
- MDS Matrix: generating a Maximum Distance Separable (MDS) matrix to use in the linear layer, where we multiply this matrix by the internal state.
Appendix B of the Poseidon paper provides sample implementations of both the Poseidon
permutation as well as parameter generation. There is a Python script called
calc_round_numbers.py which provides the round numbers given the security level
, the width of the hash function , as well as the choice of used
in the S-box step. There is also a Sage script, which generates the round numbers,
constants, and MDS matrix, given the security level , the width of the hash
function , as well as the choice of used in the S-box step.
Since the publication of the Poseidon paper, others have edited these scripts, resulting in a number of implementations being in use derived from these initial scripts. We elected to implement Poseidon parameter generation in Rust from the paper, checking each step, and additionally automating the S-box parameter selection step such that one can provide only the modulus of a prime field and the best will be selected.
Below we describe where we deviate from the parameter selection procedure described in the text of the Poseidon paper.
Choice of S-Box
The Poseidon paper focuses on the cases where , as well as BLS12-381 and BN254. For a choice of positive , it must satisfy , where is the prime modulus.
For our use of Poseidon on BLS12-377, we wanted to generate a procedure for selecting the optimal for a general curve, which we describe below.
We prefer small, positive for software (non-circuit) performance, only using when we are unable to find an appropriate positive . For positive , the number of constraints in an arithmetic circuit per S-Box is equal to its depth in a tree of shortest addition chains. For a given number of constraints (i.e. at a given depth in the tree), we pick the largest at that level that meets the GCD requirement. Since larger provides more security, choosing the largest at a given depth reduces the round requirement.
The procedure in detail:
We proceed down the tree from depth 2 to depth 5 (where depth 0 is the root of 1):
- At a given depth, proceed from largest number to smaller numbers.
- For a given element, check if is satisfied. If yes, we choose it, else continue.
If we get through these checks to depth of 5 without finding a positive exponent for , then we pick , which is well-studied in the original Poseidon paper.
decaf377, following this procedure we end up with .
We implement the round numbers as described in the original paper. These are the number of rounds necessary to resist known attacks in the literature, plus a security margin of +2 full rounds, and +7.5% partial rounds.
We test our round number calculations with tests from Appendices G and H from the paper which contain concrete instantiations of Poseidon for and their round numbers.
We do not use the Grain LFSR for generating pseudorandom numbers as described in Appendix F of the original paper. Instead, we use a Merlin transcript to enable parameter generation to be fully deterministic and easily reproducible.
We first append the message
"poseidon-paramgen" to the transcript
We then bind this transcript to the input parameter choices:
- the width of the hash function using label
- the security level using label
- the modulus of the prime field using label
We then also bind the transcript to the specific instance, as done with the Grain LFSR in Appendix F, so we bind to:
- the number of full rounds using label
- the number of partial rounds using label
- the choice of S-box exponent using label
We generate random field elements from hashes of this complete transcript of all the input parameters and the derived parameters , , and .
Each round constant is generated by obtaining challenge bytes from the Merlin transcript, derived
round-constant. We obtain bytes where is the
field size in bits. These bytes are then interpreted as an unsigned little-endian
integer reduced modulo the field.
We generate MDS matrices using the Cauchy method. However instead of randomly sampling the field as described in the text, we deterministically generate vectors and as:
Each element of the matrix is then constructed as:
This deterministic matrix generation method has been verified to be safe over the
base field of
decaf377, using algorithms 1-3 described in Grassi, Rechberger
and Schofnegger 2020 over the
t range 1-100.
The parameters that are used for
poseidon377 are located in the
module of the source code. The parameters were generated on an Apple M1.