merkle: innerHash dominates CPU/RAM consumption by sha256.Sum256(append(bytes...)) but it can be further sped up and allocations reduced as well by using a pool and reusing hashes

[odeke-em]

Summary of Bug

I was auditing the code for both security vulnerabilities and performance improvements and after reading through the literature on HashFromByteSlicesIterative at

go-square/merkle/tree.go

Line 62 in c20eda9

func HashFromByteSlicesIterative(input [][]byte) []byte {

I saw that the prior speed ups had hit their limit; I also profiled the code and indeed confirmed that innerHash consumes lots of CPU and RAM too hence why the use of the recursive vs iterative hashing doesn't show significant differences; the profiles indeed confirmed that Amdahl's law does hold

Analysis

If we examine the code for innerHash

go-square/merkle/hash.go

Lines 23 to 31 in c20eda9

	// returns sha256(0x01 || left || right)
	func innerHash(left []byte, right []byte) []byte {
	return hash(append(innerPrefix, append(left, right...)...))
	}
	func hash(bz []byte) []byte {
	h := sha256.Sum256(bz)
	return h[:]
	}

we can notice these interesting properties

go-square/merkle/hash.go

Line 29 in c20eda9

h := sha256.Sum256(bz)

that code uses a global call sha256.Sum256 whose code creates a new digest everytime and discards it per https://cs.opensource.google/go/go/+/refs/tags/go1.22.0:src/crypto/sha256/sha256.go;l=253

and right there is our opportunity!

Remedy and optimization

We can reuse hashes and reset them each time, but even more, we can avoid the call to append each time but instead invoke h.Write(byteslice)

by this code

var sha256Pool = &sync.Pool{New: func() any { return sha256.New() }}
        
func innerHashPooled(left, right []byte) []byte {
        h := sha256Pool.Get().(hash.Hash)
        defer sha256Pool.Put(h)
                        
        h.Reset()
        h.Write(innerPrefix)
        h.Write(left)
        h.Write(right)  
                        
        return h.Sum(nil)
}          

Results

When we use that new routine, voila the results are remarkable

$ benchstat before.txt after.txt 
name                old time/op    new time/op    delta
HashAlternatives-8    79.9ms ± 3%    73.8ms ± 3%   -7.55%  (p=0.000 n=10+10)

name                old alloc/op   new alloc/op   delta
HashAlternatives-8    28.0MB ± 0%    13.6MB ± 0%  -51.42%  (p=0.000 n=9+10)

name                old allocs/op  new allocs/op  delta
HashAlternatives-8      500k ± 0%      300k ± 0%  -40.00%  (p=0.000 n=10+10)

of which we shaved off 1+ second comparably against leafHash :-)

/cc @elias-orijtech @rootulp @liamsi @musalbas

Version

4135f35

Steps to Reproduce

Please read the above!

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[odeke-em]

I've mailed out a PR #44

[Wondertan]

This merkle tree implementation is forked from Tendermint/Comet and ideally such optimizations should also be submitted there.

Btw, @odeke-em do you know any high quality open source merkle tree implementations as standalone modules? Maintaining yet another merkle tree in go-square doesnt seem like a good idea. Potentially, we could nudge cosmos ecosystem to make one, depend on it and submit all the improvements there.

[odeke-em]

I've gotten jaded from trying to contribute back to tendermint repositories; am not sure I have the time and bandwidth to try to push up that hill, but at least I've highlighted what y'all need to do :-)

As for high quality Merkle tree implementations, I had found some but I am dashing for dinner though I'll look at my list tomorrow.

[cmwaters]

We've reverted back to using the merkle tree in the tendermint/cometbft library. So this issue can be closed.

If there are any other good suitors as a merkle library, I would also be interested to hear of them