It really is super simple. There’s a fixed-size bottom buffer, and an uncapped top buffer, both storing Merkle roots. Phase 1 batching Merklelises logs and saves the root to the bottom buffer. When the bottom buffer is full it is Merklelised and the root is saved to the top buffer. Below is incomplete and untested Go code.
package accumulator
type Hash [32]byte
type Log []byte
const bottomBufferSize = 1 << 10
// The bottomBuffer and topBuffer combined make up the accumulator
var bottomBuffer []Hash
var bottomBufferIndex uint
var topBuffer []Hash
func AccumulateLogs(logs []Log) {
// Phase 1 batching: Merklelise logs and save root in bottom buffer
var hashes []Hash
for i := 0; i < len(logs); i += 1 {
hashes = append(hashes, hashLog(logs[i]))
}
bottomBuffer[bottomBufferIndex] = getMerkleRoot(hashes)
// Phase 2 batching: When the bottom buffer is full, Merklelise it and save root in top buffer
bottomBufferIndex += 1
if bottomBufferIndex % bottomBufferSize == 0 {
bottomBufferIndex = 0
topBuffer = append(topBuffer, getMerkleRoot(bottomBuffer))
}
}
func hashLog(log Log) Hash{
var hash Hash
// TODO: Implement a hash function (e.g. SHA256, or Keccak)
return hash
}
func getMerkleRoot(hashes []Hash) Hash{
var root Hash
// TODO: Merklelise hashes and return Merkle root
return root
}