Hash function choices for Taiga

[simonmasson]

This issue summarizes the choices of hash functions in Taiga for our first implementation.

Taiga involves hash function circuits in the different validity predicates. For the first version of Taiga, we target Poseidon, Blake2 and maybe the Pedersen hash.

Nullifier computation

The nullifier is defined similarly to Orchard: [prf(spent_note, nk) + psi] * G + note_commitment, where G is a generator of the inner curve. This computation involves arithmetic over the inner curve, and a hash function for the PRF. As in Orchard, all the circuit is written over InnerCurve::BaseField (even the scalar part). We use Poseidon for the PRF. For our first implementation, we target bls12_377 to be the main curve. Thus, we need the circuit implementation of Poseidon over ed_on_bls12_377::BaseField = bls12_377::ScalarField. This hash function is already implemented here by Penumbra and the corresponding circuit is a WIP here in zk-garage. We need to double-check the Penumbra implementation and be able to generate the parameters. In the long term, we could change the curve and generate a new set of parameters (see also below for the bw6_761 parameters). Also, we want to get rid of using Penumbra implementation.

Blinding circuit

In the current implementation, blinding the circuit is designed similarly to the blinding of the witness in PLONK. It uses Fiat-Shamir challenges but these can be secret informations in the blinding of the circuit. Thus, we don't need hash function in the blinding process.

Commitments for addresses

Addresses of token, notes or users are done using commitments. In practice, we use hash commitments in different fields. Some of them need to be open over Curve::BaseField or Curve::ScalarField (or both). For opening over both fields, we plan to use Blake2. This is not implemented yet in zk-garage but will be part of the Zprize challenges (that end in few months). Also, this could be done as it was already implemented in Dusk implementation (but it is not available anymore). For commitment over only one field, we can use Poseidon. Although, it requires generating parameters for Curve::BaseField. We didn't find any implementation of this but it should be possible to generate the parameters because there is a SageMath script for that.

Hashing to the curve

We also need a circuit-friendly hash_to_curve. A natural choice is the Pedersen hash but it is maybe complicated to find circuits for the curves we target. A temporary solution is to hash a scalar and multiply by a generator of the curve subgroup. We could also use the Poseidon hash for that (as in the case of the nullifier). However, this is probably insecure and in the long term, a Pedersen hash would be preferable.

El gamal encryption

Taiga notes are encrypted with El Gamal, and currently, it involves a hash function. In the long term, we may need an ECIES (Elliptic Curve Integrated Encryption Scheme), an hybrid scheme that is based on asymmetric and symmetric cryptography. As it is independent from the rest of the implementation, we can investigate it thoroughly later.

Conclusion

function	design choice
prf for the nullifier	Poseidon over bls12_377::ScalarField
com_r	Poseidon over bls12_377::ScalarField
com_q	Poseidon over bls12_377::BaseField
com over Fr and Fq	Blake2
hash_to_curve	Poseidon over bls12_377::ScalarField for the scalar
el_gamal for note encryption	will be added later

[joebebel]

If we ultimately depend on the assumption "Poseidon is a PRF" anyway, then we might be able to simplify the nullifier computation.

It may be worth evaluating the Reinforced Concrete hash as well. It's also an option to increase the number of rounds of the Poseidon and/or RC hash.

[XuyangSong]

Now the poseidon hash can be used. And there are two tasks left for future work.

[simonmasson]

We also need a circuit-friendly hash_to_curve. A natural choice is the Pedersen hash but it is maybe complicated to find circuits for the curves we target. A temporary solution is to hash a scalar and multiply by a generator of the curve subgroup. We could also use the Poseidon hash for that (as in the case of the nullifier). However, this is probably insecure and in the long term, a Pedersen hash would be preferable.

This temporary fix is not possible with the whole note data because Poseidon inputs is bounded. For now, we use only owner and token address in order to make it work, but we really need to change the hash_to_curve function to a real one like Pedersen.