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[*fr.Element](4)

	// use OptimizedStatic hash mode.
	h1, _ := Hash[*fr.Element](input, cons, OptimizedStatic)
	// use OptimizedDynamic hash mode.
	h2, _ := Hash[*fr.Element](input, cons, OptimizedDynamic)
	// use Correct hash mode.
	h3, _ := Hash[*fr.Element](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 Bits[E Element[E]]() int
• func Bytes[E Element[E]]() int
• func Exp[E Element[E]](z, x E, k *big.Int)
• func Hash[E Element[E]](input []*big.Int, pdsContants *PoseidonConst[E], hash HashMode) (*big.Int, error)
• func IsEqual[E Element[E]](a, b Matrix[E]) bool
• func IsIdentity[E Element[E]](m Matrix[E]) bool
• func IsInvertible[E Element[E]](m Matrix[E]) bool
• func IsSquareMatrix[E Element[E]](m Matrix[E]) bool
• func IsValid[E Element[E]](z *big.Int) bool
• func IsVecEqual[E Element[E]](a, b Vector[E]) bool
• func Modulus[E Element[E]]() *big.Int
• func NewElement[E Element[E]]() E
• func VecMul[E Element[E]](a, b Vector[E]) (E, error)
• type Element
• type HashMode
• type Matrix
  • func Invert[E Element[E]](m Matrix[E]) (Matrix[E], error)
  • func MakeIdentity[E Element[E]](t int) Matrix[E]
  • func MatMul[E Element[E]](a, b Matrix[E]) (Matrix[E], error)
  • func ScalarMul[E Element[E]](scalar E, m Matrix[E]) Matrix[E]
• type PoseidonConst
  • func GenCustomPoseidonConstants[E Element[E]](width, field, sbox, rf, rp int, mds Matrix[E]) (*PoseidonConst[E], error)
  • func GenPoseidonConstants[E Element[E]](width int) (*PoseidonConst[E], error)
• type SparseMatrix
• type Vector
  • func LeftMatMul[E Element[E]](m Matrix[E], v Vector[E]) (Vector[E], error)
  • func RightMatMul[E Element[E]](v Vector[E], m Matrix[E]) (Vector[E], error)
  • func ScalarVecMul[E Element[E]](scalar E, v Vector[E]) Vector[E]
  • func VecAdd[E Element[E]](a, b Vector[E]) (Vector[E], error)
  • func VecSub[E Element[E]](a, b Vector[E]) (Vector[E], error)

Constants

const SecurityLevel int = 128

security level (in bits)

Variables

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

exponent used in the sbox.

Functions

func Bits

func Bits[E Element[E]]() int

func Bytes

func Bytes[E Element[E]]() int

func Exp

func Exp[E Element[E]](z, x E, k *big.Int)

Exp is a copy of gnark-crypto's implementation, but takes a pointer argument

func Hash

func Hash[E Element[E]](input []*big.Int, pdsContants *PoseidonConst[E], 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[E Element[E]](a, b Matrix[E]) bool

func IsIdentity

func IsIdentity[E Element[E]](m Matrix[E]) bool

determine if a matrix is identity.

func IsInvertible

func IsInvertible[E Element[E]](m Matrix[E]) 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[E Element[E]](m Matrix[E]) bool

the square matrix is a t*t matrix.

func IsValid

func IsValid[E Element[E]](z *big.Int) bool

func IsVecEqual

func IsVecEqual[E Element[E]](a, b Vector[E]) bool

func Modulus

func Modulus[E Element[E]]() *big.Int

func NewElement

func NewElement[E Element[E]]() E

func VecMul

func VecMul[E Element[E]](a, b Vector[E]) (E, error)

compute the product between two vectors.

Types

type Element

type Element[E any] interface {
	SetUint64(uint64) E
	SetBigInt(*big.Int) E
	SetBytes([]byte) E
	SetString(string) (E, error)
	BigInt(*big.Int) *big.Int
	SetOne() E
	SetZero() E
	Inverse(E) E
	Set(E) E
	Square(E) E
	Mul(E, E) E
	Add(E, E) E
	Sub(E, E) E
	Cmp(x E) int
}

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[E Element[E]] [][]E

func Invert

func Invert[E Element[E]](m Matrix[E]) (Matrix[E], error)

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

func MakeIdentity

func MakeIdentity[E Element[E]](t int) Matrix[E]

make t*t identity matrix.

func MatMul

func MatMul[E Element[E]](a, b Matrix[E]) (Matrix[E], error)

compute the product between two matrices.

func ScalarMul

func ScalarMul[E Element[E]](scalar E, m Matrix[E]) Matrix[E]

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

type PoseidonConst

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

func GenCustomPoseidonConstants

func GenCustomPoseidonConstants[E Element[E]](width, field, sbox, rf, rp int, mds Matrix[E]) (*PoseidonConst[E], error)

func GenPoseidonConstants

func GenPoseidonConstants[E Element[E]](width int) (*PoseidonConst[E], error)

generate poseidon constants used in the poseidon hash.

type SparseMatrix

type SparseMatrix[E Element[E]] struct {
	// WHat is the first column of the M” matrix, this is a little different with the WHat in the paper because
	// we add M_00 to the beginning of the WHat.
	WHat Vector[E]
	// V contains all but the first element, because it is already included in WHat.
	V Vector[E]
}

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[E Element[E]] []E

func LeftMatMul

func LeftMatMul[E Element[E]](m Matrix[E], v Vector[E]) (Vector[E], error)

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

func RightMatMul

func RightMatMul[E Element[E]](v Vector[E], m Matrix[E]) (Vector[E], error)

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

func ScalarVecMul

func ScalarVecMul[E Element[E]](scalar E, v Vector[E]) Vector[E]

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

func VecAdd

func VecAdd[E Element[E]](a, b Vector[E]) (Vector[E], error)

func VecSub

func VecSub[E Element[E]](a, b Vector[E]) (Vector[E], error)