improve merkle tree's hash logic

[zhenfeizhang]

currently merkle tree hash is implemented as

/// Hash function used to compute an internal node value
/// * `a` - first input value (e.g.: left child value)
/// * `b` - second input value (e.g.: middle child value)
/// * `c` - third input value (e.g.: right child value)
/// * `returns` - rescue_sponge_no_padding(a,b,c)
pub(crate) fn hash<F: RescueParameter>(
    a: &NodeValue<F>,
    b: &NodeValue<F>,
    c: &NodeValue<F>,
) -> NodeValue<F> {
    let perm = Permutation::default();
    let digest = perm.sponge_no_padding(&[a.0, b.0, c.0], 1).unwrap()[0];
    NodeValue(digest)
}

Every time a hash function is called, the same permutation initialization is called. This incurs a non-negligible cost.

hash/ed_on_bn254::init  time:   [28.953 us 28.962 us 28.971 us]
hash/ed_on_bn254::digest                        
                        time:   [346.65 us 346.80 us 346.96 us]

We should separate the initialization and the actual hash function so that it gets initialized for only once. This will save around 29/(29 + 346) = 7.7%.

[alxiong]

So what's the status on this, it seems that we still have this problem even after @mrain's work on #135 ?

RescueCRHF::sponge_no_padding is still internally calling Permutation::default() here, which essentially will incur the initialization cost?

[tessico]

It's still on my radar, once the higher-level refactors are done. This one should hopefully be easy.