New host functions and Poseidon hash support

[ymcrcat]

Starting a discussion here about new host functions.
Note that there are other threads that discuss support for specific curves or use-cases (BN254 host functions, cryptographic primitives for proof-verification).

Poseidon is a ZK-friendly hash that works directly on field elements and has some existing Rust implementations as well as implementations for the Circom compiler.
However, Poseidon is actually a hash-family that can result in different concrete instantiations based on parameters (round constants, MDS matrix). Hence it's important to pick the right parameters for host support of Poseidon bearing in mind what we expect it to be compatible with (perhaps the Circom library, poseidon-lite JS implementation, etc?)

[jayz22]

+1. Thanks for initiating the discussion @ymcrcat , we also have a tracking issue here: stellar/rs-soroban-env#1586

[Fantoni0]

I'm just sharing some thoughts: You are right that Poseidon is a family of hashes rather than a specific instantiation. Careful selection of the parameters must be studied to ensure security levels and comparable results with other systems.

For Poseidon parameter selection, I recommend checking Table 2 (page 8) of the original paper and the referenced scripts for round and matrices configurations.

For Poseidon2, there's the official repository with a Sage script to generate the parameters under different fields and configurations.

Regarding the internal configuration, most implementations let you define the input size, then adaptively select the proper state size t, and correct parameters generated using previous scripts. (See, for example, https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom#L76-L79, https://github.com/ax0/noir/blob/master/noir_stdlib/src/hash/poseidon/bn254.nr#L107-L242). This provides a nice balance between flexibility of using different configurations, but prevents the user from instantiating an insecure hash function.

However, I have seen other implementations that only present a more structured and optimized version for a specific configuration: https://github.com/risc0/risc0/blob/main/risc0/zkp/src/core/hash/poseidon2/consts.rs.

Just to let you know, some details might still differ between different implementations (although they can produce the identical hashes), as is the case for the absorption in Noir and Circom (https://research.aragon.org/poseidon-noir.html).

[Fantoni0]

@tomerweller
Not directly, Poseidon2 is not required for the on-chain proof verification as @Oghma points out.
But for applications where you maintain a public state/inputs that need to be updated on-chain (e.g., an incremental Merkle tree for a privacy pool), you'll need to use the same hash function that is being used off-chain for proving (to maintain consistency).
You can use any hash function while in a zkVM guest program, but Poseidon2 will probably be used frequently as it is really efficient for off-chain proving.

[tomerweller]

Got it. Based on the above it sounds like ideally we should have both, with a slight higher priority to the original poseidon hash function given it's prevalence in existing systems like 0xBow.

What should the interfaces look like, given that we need to support both bn254 and bls-12-381 based circuits?

[Fantoni0]

It's tricky, because many of the configuration options should be transparent to the final user. But I think it could look something like this: I think we can have exposed the high-level methods in the crypto library. Something like:

Poseidon2Bls12381(n_inputs) {
	PoseidonInternalBls(n_inputs, 1) // Assuming a single output is desired for now.
}

Poseidon2BN254(n_inputs) {
	PoseidonInternalBN254(n_inputs, 1) // Assuming a single output is desired for now.
}

Then, inside the Hazmat crypto library, we can have the internal configuration.
This should check that the provided input size is supported in the current implementation.

struct Poseidon2InternalConfig {
	n_inputs,
	n_outputs, // Generally 1.
	t = n_inputs + 1 // Generally for bn and bls. But it might be left up to configuration for more advanced users.
	rate,
	capacity
}

For each valid configuration we should store its constants. Obtained from for Poseidon2, and for Poseidon1.

• Initial parameters.
• Linear layer
• Number of full and partial rounds.
• Full matrix
• Partial matrix
• Rounds constants

Internally, we could expose the sponge construction itself and its methods (As arkworks does). So that:

• absorb()
• permute()
• squeeze()

are availabe for the experienced user. Then we can implement the Poseidon2 hash with those methods.

I think this configuration allows Stellar to only expose the most secure API for Poseidon, while it allows the more advanced user to decide if they want to modify the internal configuration. This could also allow users to implement the compression function (not a hash) on top of the Poseidon permutation.

If you want to start smaller, we could always simply expose the hash() function, and not expose absorb, permute and/or aqueeze.

[jayz22]

Thank you @Fantoni0
How important is it to let the user pick their own (assuming securely generated) constants, i.e. MDS matrix and round constants? IIUC in the original paper it describes the guideline for MDS generation, and provided sage script as one such instance. In reality do different chains generate their own constants or use the provided set?
(e.g. it seems like Mina uses their own generated parameters according to this thread)

[Fantoni0]

@jayz22
Most implementations do not let the user pick their own parameters. So, not important, really depends on how you want to design it and how easy/cheap is to generalize, or update later, in Soroban.
Regarding the parameters, most projects employ the provided by the scripts: they are the default ones and ensure better compatibility, and are assumed to be secure (or at least the most researched ones). There might be valid reasons to roll your own ones, but if you seek compatibility I do not recommend it.
The first option you propose in your message below seems to be ok. Just make sure to pick the right input sizes to be compatible with the configurations you want to support.

[ymcrcat]

Regarding Antonion's comment on Poseidon in Circom...
While Circom's standard library (circomlib) provides a poseidon implementation, it is not something that's at the core of the Circom compiler. So as long as someone is willing to provide a tested implementation for Poseidon2 for Circom, that's fine too. That of course might not be compatible with existing Circom circuits relying on the circomlib version, but can be perfectly fine for new circuits.

[jayz22]

Based on inputs above and some of my initial research, here are a few approaches to supporting these as host functions (in decreasing preference)

1. As hash functions.

This will introduce four new host functions poseidon_bn254_hash(arity: u32), poseidon_bls12_hash(arity: u32), poseidon2_bn254_hash(arity: u32), poseidon2_bls12_hash(arity: u32)

As a starting point only support a few fixed arities (e.g. 1, 2, 4 which corresponds to a Merkle tree with arity=4).

The main advantage of this is simplicity, based on a given curve and arity, the internal parameters can be fixed. We will pick the reference parameters but need to ensure its compatibility with major protocols (e.g. circom).

The new metering cost types will likely be permutation of (version, curve, arity), each case being a new const costtype. The arity could be treated as a linear input, so it would just be (version, curve), each case being a linear costtype. We will decide based on calibration.

2. Expose the internal Poseidon building blocks (absorb, permute, squeeze)

The main advantage is generality as @Fantoni0 pointed out above. The user gets to choose their own parameters to ensure compatibility with their proving side crypto.

We will still need two versions, for Poseidon and Poseidon2.

3. No Poseidon host functions. Instead provide optimized Field arithmetic functions.

Such as bn254_fr_dot_product(lhs: Vec<Fr>, rhs: Vec<Fr>) -> Fr, and bn254_fr_matmul(lhs: Vec<Vec<Fr>>, rhs: Vec<Vec<Fr>>) -> Vec<Vec<Fr>>.

This was my initial preference. Because theoretically the most expensive part are the field arithmetics which we already provide for BLS12-381 and BN254 (soon to come). The contract could be able to rollout their own Poseidon implementation.

I took @ymcrcat's prototype and did a few analysis, an optimized hash_2 call still takes 17.6M instructions. Out of which only 2.5M are the crypto arithmetics (Add/Sub, Mul, Pow), rest are mostly overhead (roundtrip conversion between the internal Fr repr and bytes (5.5M), host function dispatching (2M), wasm exec (3.2M)). Providing field arithmetic host functions that batches multiple operations can save these overhead. However, according to @ymcrcat the requirement upper bound is ~20 hash operations per invocation, these savings may not be enough.

Overall my preference is 1 > 2 > 3, given our P24 timeline.

[tomerweller]

Recapping a few of the discussion points in protocol meeting:

• Option 1 seems to assume that all projects using poseidon on Stellar will share a configuration. This does not seem to be an acceptable assumption given the variety of configurations observed in the wild.
• Option 2 will require an initialization step if we accept arbitrary configuration. We need to evaluate it's cost and figure out how to amortize it across repeat calls
• The complexity of Option 2 can be abstracted away in the SDK by providing high level hash functions (similar to option 1)

[dmkozh]

Option 2 will require an initialization step if we accept arbitrary configuration. We need to evaluate it's cost and figure out how to amortize it across repeat calls

If we take a look at the arkworks implementation, we can see that they provide a CryptographicSponge trait that is initialized once and then mutated by some methods. We could use the same approach and perform operations on a new host object type. The downside is that, well, we'd need a new host object type, which takes time to introduce. But I'm not sure if introducing a new object type is avoidable with option 2 anyways.

Also, it seems like option 2 has a design complexity issue that has been overlooked during the protocol meeting. Specifically, all the functions proposed (absorb, permute, squeeze) mutate the sponge inner state. Soroban objects are immutable, so we'll need to copy the current state on every operation. I don't know how expensive that would end up being, and I also don't know if it's even possible to copy it (I'm not sure what the concrete implementation of the sponge interface would look like). We have to figure this issue as well in addition to the one raised here.

[jayz22]

Discussed with @dmkozh offline, the mutable internal state itself shouldn't be an issue, we could follow the prng design, i.e the host contains a mutable sponge and the guest contract frame can call it to mutate its internal state. We just need to figure out the requirements w.r.t multiple contracts sharing the sponge / different contracts want different configuration etc.

Option 2 does add more design complexity I agree. Also to point out, in order to support the generic interface, there likely won't be a single library that provides everything we need (arkworks only provide Poseidon(1) implementation), so we might need to build the abstraction layer in the host ourselves that integrates different libs.

[jayz22]

I went into this a bit further. I think the generic interface arkworks provided: absorb, permute, squeeze is an overkill:
It accounts for arbitrary length of inputs/outputs and capacities, and provides methods for squeezing arbitrary length of bits, as well as non-native field elements. It also has this duplex mode which I'm not sure about its use case, I believe it's a Keccak thing.

For our most common use case the flow should be very straightforward, for instance hashing two inputs into a single output is just:

1. Initialize a state vector of size 3
2. Set 2 elements to the two inputs
3. Perform the permutation on the state vector.
4. Take the 0-th element as output.

The permutation function, i.e. $Poseidon^{\pi}$ and $Poseidon2^{\pi}$, are the main focuses of those two papers (1 and 2), and it is also the cryptographic heavy part. In other words, the core crypto primitive we need to support are these two permutation functions. I will propose this approach below as approach 4.

[jayz22]

4. Provide host functions for $Poseidon^{\pi}$ and $Poseidon2^{\pi}$ permutation

As mentioned above, the actual primitives are these permutation functions, and the hash algorithm (i.e. sponge absorb, squeeze) can be built from just these two.

We provide two host functions of the following rough shape:

• fn poseidon_permutation(state: Vec<U256Val>, field_type, params: ... ) -> Vec<U256Val>
• fn poseidon2_permutation(state: Vec<U256Val>, field_type, params: ... ) -> Vec<U256Val>

where the params are the internal parameters: num_full_rounds, num_partial_rounds, round_constants, mds_matrices. The output Vec will have the same length as the input state.

(Note: U256Val here represents field element, can be either bn254 or bls12_381, specified by field_type)

In the sdk, we can provide the actual hash instances, for example:

// this is pseudo-code in the sdk
pub fn poseidon2_bn254_hash_two(input1: Fr, input2: Fr, params: Opt<Params>) -> Fr {
      state <-- vec[Fr::Zero; 3];
      state[1] <-- input1,  state[2] <-- input2, 
      params <-- "initialized from a preset" or "pass as inputs"
      poseidon2_permutation(state, 'bn254', params)
      return state[0]
}

it is also straightforward to extend this into generic number of inputs/outputs, see Noir's absorb method for instance.

With this approach the host provides the core cryptographic primitives - Poseidon/Poseidon2 permutation, while the sdk provides the sponge implementation and hash instantiations. This reduces the maintenance surface area of the host (and the hash function call is entirely stateless in the host). It also gives the flexibility to build other flavors of Poseidon, for example, the compression function Poseidon2 paper describes.

(edit: corrected the state indices in the pseudo-code thanks to @ymcrcat pointing out)

[jayz22]

@Fantoni0 @ymcrcat would be especially interested to hear your thoughts on this approach.

[Fantoni0]

I would absolutely agree on this simplified approach.
It is sufficient for most applications, but still allows the user to implement the sponge construction if needed. It is also the default approach for most implementations. I recommend signaling in the documentation the difference between sponge and permutation mode so that users are aware of that, since sometimes, we all abuse notation.
Great job @jayz22 🙌

[dmkozh]

This looks really nice and simple. IIUC all the cryptographic logic still happens on the host side, so the remaining costs should be minimal (unless some initialization steps are omitted here).
FWIW we could make Params a contracttype for the sake of simple SDK->host interaction, so we can afford rather complex parameter structure (as long as they are easy enough to support in the host).

[ymcrcat]

@jayz22 The host interface seems good to me. And providing the SDK function you suggested should address the Privacy Pools use-case. I wonder if the initialization in the SDK function pseudocode shouldn't be
state[1] <-- input1, state[2] <-- input2 ? Let's look into that, but that doesn't affect the interface.

[jayz22]

@ymcrcat yes I corrected it above, and made sure it's correct in the CAP-75. Thanks

[anupsdf]

CAP-75 has been created for this.