Are there any current recommendations for performant hashing in a Merkle tree?
It appears the hash based signatures in Sphincs use Blake2 everywhere (see Table 1 on page 22 of https://sphincs.cr.yp.to/sphincs-20150202.pdf) but I'm unsure how later improvements like Sphincs++ updated this.
A priori, we're hashing together two 16 byte outputs each time, so we've no reason to use blake2's adaptation of chacha, which consumes only 16 bytes per iteration. I'd therefore expect hashing in a Merkle tree to use chacha directly, not a general purpose hash function like blake2.
We'd probably never use heap indexing in practice, meaning node i's two children are 2*i and 2*i+1, but if we did then I'd think a reasonable strategy might be
node[i] := chacha8( key = node[2*i] ++ node[2*i+1], nonce = i )[0..16]
In other words, we run one chacha8 iteration per node, which sounds almost four times faster than blake2, which consumes only 16 bytes per iteration, and uses almost twice as many rounds. I'm currently unsure about how blake2 actually counts rounds though, like maybe it runs 8 quarter-rounds where chacha runs 4 or something.
I'd also think one should use some stronger and more general purpose hashing scheme like a full blake2s at the leaves. Is this initial hashing step somehow be sufficient justification for using only chacha8 at each node?
Edit: The above construction suffers from a birthday bound attack, so one needs 256 bit hash outputs, which makes this optimization not workable for chacha.
