iden3 / go-iden3-crypto Goto Github PK

View Code? Open in Web Editor NEW

94.0 6.0 31.0 2.01 MB

Go implementation of some cryptographic primitives (that fit inside the SNARK field) and compatible with circomlib

License: Apache License 2.0

Go 98.74% Assembly 1.26%

go-iden3-crypto's Introduction

go-iden3-crypto

Go implementation of some cryptographic primitives (that fit inside the SNARK field) used in iden3:

BabyJubJub curve arithmetics & EdDSA on it
Goldilocks curve arithmetics
Poseidon hash for BN254
Poseidon hash for Goldilocks
MIMC7

Contributing

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as below, without any additional terms or conditions.

License

This project is licensed under either of

at your option.

go-iden3-crypto's People

Contributors

Stargazers

Watchers

go-iden3-crypto's Issues

Check number of elements for each Poseidon chunk

https://github.com/iden3/go-iden3-crypto/blob/master/poseidon/poseidon.go#L176
check the approach to set the first element to 1, as in MiMC7 we use the key parameter
https://github.com/iden3/go-iden3-crypto/blob/master/poseidon/poseidon.go#L189

Benchmarks MiMC, Poseidon, BabyJubJub

MiMC7
- go go-iden3-crypto/mimc7
- js iden3js/mimc7
- rust mimc-rs
Poseidon
- go go-iden3-crypto/poseidon
- js iden3js/poseidon
- rust poseidon-rs
BabyJubJub EDDSA
- go go-iden3-crypto/babyjub
- js iden3js/babyjub
- rust babyjubjub-rs

Add a function to check if a big int fits in the ZK field

Instead of doing

cryptoUtils.CheckBigIntArrayInField(bigInts, cryptoConstants.Q)

Just use the Q inside a util so that it looks like this:

cryptoUtils.CheckBigIntArrayInFieldFOO(bigInts)

Also, if it's not there, add a function for a single big int

Poseidon `Hash` function is broken!

The Hash function in poseidon for arbitrary length inputs is calculated like this:

r_0 = 0
r_(i+1) = r_i + hash(a_(i_0), ..., a_(i_4))
output = r_(n+1)

This means that creating a collision is trivial, since any group of 5 elements aligned at 5 elements can be swapped by another group of 5 elements aligned at 5 elements leading to the same hash result. This is checked in the TestPoseidonBrokenChunks, which currently doesn't pass.

Let's discuss a solution.

Is it safe to use 7 for S-box exponent in golden poseidon?

Hi, the Poseidon paper only mentions S-box exponents -1, 3, 5
Why does golden poseidon use the exponent 7 ?

go-iden3-crypto/goldenposeidon/poseidon.go

Line 15 in edc36bf

a.Exp(*a, big.NewInt(7)) //nolint:gomnd

// Hash performs the Poseidon hash over a *big.Int array
// in chunks of 5 elements
func Hash(arr []*big.Int) (*big.Int, error) {
	if !utils.CheckBigIntArrayInField(arr, constants.fqR.Q) {
		return nil, errors.New("inputs values not inside Finite Field")
	}

	r := constants.fqR.Zero()
	for i := 0; i < len(arr); i = i + 5 {
		var fiveElems [5]*big.Int
		for j := 0; j < 5; j++ {
			if i+j < len(arr) {
				fiveElems[j] = arr[i+j]
			} else {
				fiveElems[j] = _constants.Zero
			}
		}
		ph, err := PoseidonHash(fiveElems[:])
		if err != nil {
			return nil, err
		}
		r = constants.fqR.Add(
			r,
			ph)
	}

	return r, nil
}

Whereas the basic poseidon hash function uses groups of 6 elements (T = 6):

// PoseidonHash computes the Poseidon hash for the given inputs
func PoseidonHash(inp []*big.Int) (*big.Int, error) {
	if len(inp) == 0 || len(inp) > T {
		return nil, errors.New("wrong inputs length")
	}
	if !utils.CheckBigIntArrayInField(inp, constants.fqR.Q) {
		return nil, errors.New("inputs values not inside Finite Field")
	}
	state := inp
	for i := len(inp); i < T; i++ {
		state = append(state, constants.fqR.Zero())
	}

	// ARK --> SBox --> M, https://eprint.iacr.org/2019/458.pdf pag.5
	for i := 0; i < NROUNDSF+NROUNDSP; i++ {
		state = ark(state, constants.c[i])
		state = sbox(state, i)
		state = mix(state, constants.m)
	}
	return state[0], nil
}

Why Hash designed this way?