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.

  • 2
    $\begingroup$ Sphincs+ (note the single +) uses SHA-256, SHAKE or Haraka within its Merkle function. Also, the Merkle node logic turns out not to be performance critical; the vast majority of the time is spent computation the WOTS+ and HORST trees... $\endgroup$
    – poncho
    Apr 11, 2019 at 13:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.