Poseidon SPONGE_RATE constant

[cloud mauve]

hey 👋 I'm working alongside with my team (@jaunty shale and @rocky bear) on some primitives for o1js.

I would love to get some help from someone more knowledgeable regarding Poseidon implementation on o1js. I saw there is a parameter SPONGE_RATE that is a constant with the value of 2.
I would like to get some information behind the chosen value as constant and if there would be some impactful implications on increasing this value. The reasone behind this question is because, if I'm correct, this is the total number of inputs per hash, which limits if we want to build a merkle tree with more than two children per node right? Also feel free to correct me if I'm wrong 🙂

https://github.com/o1-labs/proof-systems/blob/71d6a09be2592014d9c8019aaa2c35ab358dfc61/poseidon/src/poseidon.rs#L81

Thank you 🙏

cc: @lone horizon @coral frigate @twilit lion

[lone horizon]

#development message

if I'm correct, this is the total number of inputs per hash, which limits if we want to build a merkle tree with more than two children per node right?

Why is that? You can just hash arbitrary input data Poseidon.hash([node0, node1, node2]);

Also, changing the Poseidon constants is not possible from within o1js. I would have to look into what exactly it takes to change these, but it's definitely a bit more work than just changing some values in o1js (maybe some work in Kimchi), especially because we are using a custom gate for Poseidon

[coral frigate]

@cloud mauve is it sufficient that the API exposes poseidon hashing of arbitrary-length field arrays? Or do you specifically mean to tune the performance and security characteristics of the hash function?

[cloud mauve]

I can be wrong but from my research seems that the improvements on performance for implementing n-ary merkle trees, like quinary merkle trees come from an implementation of Poseidon that accepts 5 inputs per permutation

General explanation: https://ethresear.ch/t/gas-and-circuit-constraint-benchmarks-of-binary-and-quinary-incremental-merkle-trees-using-the-poseidon-hash-function/7446
"“Tree” refers to the Merkle tree arity and is equal to the rate/capacity ratio." from Poseidon Paper which I still haven't read everything yet but I will do to be more certain about this.

From here and the code I understand that a permutation is done for each two inputs. If this is correct I believe that the true win from implementing n-ary merkle trees come from having a Poseidon implementation with higher SPONGE_RATE and yes I'm aware that this has a bigger impact on the implementation and it is not only changing this value, this is why I also wanted to get more feedback from people that understand the proof system better than me 🙂