ingonyama-zk/poseidon-hash

Reference implementation in Python of Poseidon and optimized Poseidon (Neptune) hash functions

Poseidon

This repository contains a reference implementations for the original version of Poseidon [1] and the instantiation as a hash function tuned for Filecoin [2]. Moreover, scripts to calculate the round numbers, the round constants, and the MDS matrices are also included.

Theoretical introduction

The set of parameters (t, M, p, alpha) fully specify a unique instance of Poseidon All other Poseidon parameters and constants are derived from these parameters.

The optimized Poseidon hash function is instantiated in the same way as the un-optimized algorithm, however the optimized Poseidon algorithm requires the additional pre-computation of round constants, pre-sparse matrix and sparse matrices. We implemented the pre-computation steps according to [2].

The hash function takes as input a list of elements from a certain field F and outputs o single field element. In addition, for this implementation the input_rate (size of input) parameter is required, which can take any value from 1 to t. A longer input size is possible and it is a work in progress.

Usage: generate new instance with pre-generated parameters

To create a new hash instance, you can use ready-made functions in parameters.py that have all the necessary parameters, or you can set your own parameters that have already been generated.

For matrices and round constants, use the hex representation.

import poseidon

def main():
    poseidon_simple, t = poseidon.parameters.case_simple()

    input_vec = [x for x in range(0, t)]
    print("Input: ", input_vec)
    poseidon_digest = poseidon_simple.run_hash(input_vec)
    print("Output: ", hex(int(poseidon_digest)))

    security_level = 128
    input_rate = 3
    t_opt = 4
    full_round = 8
    partial_round = 56
    alpha = 5
    poseidon_pre_generated = poseidon.OptimizedPoseidon(poseidon.HashType.CONSTINPUTLEN, poseidon.parameters.prime_255, 
                                                    security_level, alpha, input_rate, t_opt,
                                                    full_round=full_round, partial_round=partial_round,
                                                    rc_list=poseidon.parameters.round_constants_neptune, 
                                                    mds_matrix=poseidon.parameters.matrix_neptune)

    input_vec_2 = [x for x in range(0, t_opt - 1)]
    print("Input: ", input_vec_2)
    poseidon_output = poseidon_pre_generated.run_hash(input_vec_2)
    print("Output: ", hex(int(poseidon_output)))


if __name__ == "__main__":
    main()

Usage: generate new instance without pre-generated parameters

The number of rounds, roound constants and matrices are optional parameters; if they are not specified, they will be generated automatically. For the same required input parameters the same optional parameters will always be generated.

import poseidon

def main():
    security_level = 128
    input_rate = 3
    t = 4
    alpha = 5
    poseidon_new = poseidon.Poseidon(poseidon.parameters.prime_255, security_level, alpha, input_rate, t)

    input_vec = [x for x in range(0, t)]
    print("Input: ", input_vec)
    poseidon_output = poseidon_new.run_hash(input_vec)
    print("Output: ", hex(int(poseidon_output)))


if __name__ == "__main__":
    main()

Running tests

Test vectors and parameters for non-optimised implementation are taken from [3].

Parameter generation for the optimized Poseidon is checked using test vectors that are taken (in some cases generated) from the implementation of [2].

Running all tests

python3 -m pytest tests/ 

Running tests by file

python3 -m pytest tests/test_hash.py 

Running a specific test. After :: you must enter the name of the specific test in the corresponding file

python3 -m pytest tests/test_hash.py::test_not_optimized_poseidon

License

The code is released under the MIT license. See LICENSE for more information.

Contact

Feel free to reach out!

[1] Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. Cryptology ePrint Archive, Report 2019/458. https://eprint.iacr.org/2019/458. Accepted at USENIX'21.

[2] Neptune specification https://github.com/filecoin-project/neptune/tree/master/spec

[3] Reference Implementations for Various Versions of Starkad and Poseidon https://extgit.iaik.tugraz.at/krypto/hadeshash

poseidon-hash's Issues

PyPI release?

I was looking for Python implementation of Poseidon for the multihash module of https://github.com/hashberg-io/multiformats, and I came upon this project. Do you have any plans to release this on PyPI?

implement Poseidon 2 !

https://eprint.kobi.one/2023/323

:bug: Bug: poseidon.parameters.case_simple()

Hello!

playing with the library, I think I found a bug 🕵️

so I was trying to run this snippet taken from the pypi site:

import poseidon


poseidon_simple, t = poseidon.parameters.case_simple()

input_vec = [x for x in range(0, t)]
print("Input: ", input_vec)
poseidon_digest = poseidon_simple.run_hash(input_vec)
print("Output: ", hex(int(poseidon_digest)))

And I get the following error:

Traceback (most recent call last):
  File "/Users/alv/code/zokrates+/tutorials/hashes/poseidon/witnessx.py", line 4, in <module>
    poseidon_simple, t = poseidon.parameters.case_simple()
  File "/Users/alv/.pyenv/versions/pycrypto/lib/python3.9/site-packages/poseidon/parameters.py", line 12, in case_simple
    poseidon = Poseidon(prime_64, security_level, alpha, input_rate, t, full_round=full_round,
  File "/Users/alv/.pyenv/versions/pycrypto/lib/python3.9/site-packages/poseidon/hash.py", line 45, in __init__
    if np.gcd(alpha, p - 1) == 1:
numpy.core._exceptions.UFuncTypeError: ufunc 'gcd' did not contain a loop with signature matching types (<class 'numpy.dtype[int64]'>, <class 'numpy.dtype[ulonglong]'>) -> None

versions:
Python: 3.9.7
numpy==1.22.4
poseidon-hash==0.1.2

Just FYI :)

cheers

Saving multiplications in the last round of optimized poseidon.

In the Optimised poseidon we can use a small change that reduces unnecessary multiplications. This was noticed by @mickeyasa

Observation: In the last round: notice that after the S box operation, the full MDS matrix is used to generate all the elements in the state of width $t$. After that the round ends and the element with index state[1] is output as the digest.

Observation: There is no need to compute all the state elements in the MDS multiplication, in the last round.

Proposal: after the S box in the last round, only compute the element with index 1 in
state'= state^(transpose).MDS
i.e just compute state'[1]
since only the digest is needed, and other elements do not matter for the digest or another sequential hash.

Support python 3.11

Currently installing the library with python 3.11 leads to the following error from numba:
RuntimeError: Cannot install on Python version 3.11.0; only versions >=3.7,<3.11 are supported.

Also it seems numba now supports python 3.11: numba/numba#8304

add support for any input length

Add a wrapper for hashing data longer than t. Hashing data of a length greater than t is possible using the sponge construction. How this would look like is described in detail in section 2.1 in https://eprint.iacr.org/2019/458.

add support for output >1 field element

Usually, the Poseidon parameter set is such that hashing into a single field element is assumed. But for some features (e.g. high security-level with a large prime number) it may be necessary to hash more than one element.