poseidon

README

Poseidon Hash

This is the GO implementation of poseidon hash. We refer the paper https://eprint.iacr.org/2019/458.pdf and the rust implementation. Poseidon hash is a kind of hash function used for proof systems, such as ZK-STARKs, Bulletproof, so it is also called " zero-knowledge friendly hash". It has been widely used in blockchain for zero-knowledge proofs. You can find more information in the paper.

Install

install:

go get -u github.com/triplewz/poseidon

test:

go test -v 

benchmark:

go test -v --bench=. 

Example

func main() {
	// poseidon hash with 3 input elements and 1 output element.
    input := []*big.Int{big.NewInt(1), big.NewInt(2), big.NewInt(3)}

	// generate round constants for poseidon hash.
	// width=len(input)+1.
	cons, _ := GenPoseidonConstants(4)

	// use OptimizedStatic hash mode.
	h1, _ := Hash(input, cons, OptimizedStatic)
	// use OptimizedDynamic hash mode.
	h2, _ := Hash(input, cons, OptimizedDynamic)
	// use Correct hash mode.
	h3, _ := Hash(input, cons, Correct)
}

Benchmark

CPU: i5-9400 CPU @ 2.90GHz.
OS: win10
go version: 16.3
input: 10 elements, output: 1 element

BenchmarkOptimizedStaticWith10Inputs-6    	   13419	     89416 ns/op
BenchmarkOptimizedDynamicWith10Inputs-6   	    4693	    251820 ns/op
BenchmarkCorrectWith10Inputs-6            	    5006	    236506 ns/op

Other implementations

• filecoin-project/neptune (rust)
• iden3/go-iden3-crypto (go)
• guipublic/poseidon (c)
• shamatar/poseidon_hash (rust)
• dusk-network/Poseidon252 (rust)
• matter-labs/rescue-poseidon (rust)
• dusk-network/dusk-poseidon-merkle (rust)
• arnaucube/poseidon-rs (rust)
• krypto/hadeshash (sage)

License

BSD license.

Documentation

Index

• Constants
• Variables
• func Hash(input []*big.Int, pdsContants *PoseidonConst, hash HashMode) (*big.Int, error)
• func IsEqual(a, b Matrix) bool
• func IsIdentity(m Matrix) bool
• func IsInvertible(m Matrix) bool
• func IsSquareMatrix(m Matrix) bool
• func IsVecEqual(a, b Vector) bool
• func VecMul(a, b Vector) (*ff.Element, error)
• type HashMode
• type Matrix
  • func Invert(m Matrix) (Matrix, error)
  • func MakeIdentity(t int) Matrix
  • func MatMul(a, b Matrix) (Matrix, error)
  • func ScalarMul(scalar *ff.Element, m Matrix) Matrix
• type PoseidonConst
  • func GenPoseidonConstants(width int) (*PoseidonConst, error)
• type SparseMatrix
• type Vector
  • func LeftMatMul(m Matrix, v Vector) (Vector, error)
  • func RightMatMul(v Vector, m Matrix) (Vector, error)
  • func ScalarVecMul(scalar *ff.Element, v Vector) Vector
  • func VecAdd(a, b Vector) (Vector, error)
  • func VecSub(a, b Vector) (Vector, error)

Constants

const Alpha int = 5

for bls12_381 modular p, since p ≠ 1 mod 5, we set Alpha = 5. see https://eprint.iacr.org/2019/458.pdf page 6.

const SecurityLevel int = 128

security level (in bits)

Variables

var PoseidonExp = new(big.Int).SetUint64(5)

exponent used in the sbox.

Functions

func Hash

func Hash(input []*big.Int, pdsContants *PoseidonConst, hash HashMode) (*big.Int, error)

Hash implements poseidon hash in this paper: https://eprint.iacr.org/2019/458.pdf. we refer the rust implement (OptimizedStatic mode), see https://github.com/filecoin-project/neptune. the input length is a slice of big integers. the output of poseidon hash is a big integer.

func IsEqual

func IsEqual(a, b Matrix) bool

func IsIdentity

func IsIdentity(m Matrix) bool

determine if a matrix is identity.

func IsInvertible

func IsInvertible(m Matrix) bool

if delta(m)≠0, m is invertible. so we can transform m to the upper triangular matrix, and if all upper diagonal elements are not zero, then m is invertible.

func IsSquareMatrix

func IsSquareMatrix(m Matrix) bool

the square matrix is a t*t matrix.

func IsVecEqual

func IsVecEqual(a, b Vector) bool

func VecMul

func VecMul(a, b Vector) (*ff.Element, error)

compute the product between two vectors.

Types

type HashMode

type HashMode int

provide three hash modes.

const (
	// used as the default mode. Consumes statically pre-processed constants for simplest operation.
	OptimizedStatic HashMode = iota
	// the simplified correct hash.
	OptimizedDynamic
	// the initial version of the algorithm in the paper.
	Correct
)

type Matrix

type Matrix [][]*ff.Element

func Invert

func Invert(m Matrix) (Matrix, error)

use Gaussian elimination to invert a matrix. A|I -> I|A^-1.

func MakeIdentity

func MakeIdentity(t int) Matrix

make t*t identity matrix.

func MatMul

func MatMul(a, b Matrix) (Matrix, error)

compute the product between two matrices.

func ScalarMul

func ScalarMul(scalar *ff.Element, m Matrix) Matrix

for 0 <= i < row, 0 <= j < column, compute M_ij*scalar.

type PoseidonConst

type PoseidonConst struct {
	Mds            *mdsMatrices
	RoundConsts    []*ff.Element
	ComRoundConts  []*ff.Element
	PreSparse      Matrix
	Sparse         []*SparseMatrix
	FullRounds     int
	HalfFullRounds int
	PartialRounds  int
}

func GenPoseidonConstants

func GenPoseidonConstants(width int) (*PoseidonConst, error)

generate poseidon constants used in the poseidon hash.

type SparseMatrix

type SparseMatrix struct {
	// contains filtered or unexported fields
}

SparseMatrix is specifically one of the form of m”. This means its first row and column are each dense, and the interior matrix (minor to the element in both the row and column) is the identity. For simplicity, we omit the identity matrix in m”.

type Vector

type Vector []*ff.Element

func LeftMatMul

func LeftMatMul(m Matrix, v Vector) (Vector, error)

left Matrix multiplication, denote by M*V, where M is the matrix, and V is the vector.

func RightMatMul

func RightMatMul(v Vector, m Matrix) (Vector, error)

right Matrix multiplication, denote by V*M, where V is the vector, and M is the matrix.

func ScalarVecMul

func ScalarVecMul(scalar *ff.Element, v Vector) Vector

for 0 <= i < length, compute v_i*scalar.

func VecAdd

func VecAdd(a, b Vector) (Vector, error)

func VecSub

func VecSub(a, b Vector) (Vector, error)