aergo
aergo copied to clipboard
add new function Walk() to trie
Walk allows iteration over all values stored into the SMT.
This is a useful method for exporting the tree (and importing afterwards) and also for search specific values.
Signed-off-by: p4u [email protected]
This is not 100% correct... Sometimes the test will fail and I don't know why (yet).
Maybe someone with more knowledge on this SMT implementation can find the problem.
So with this last implementation, go test -timeout 30s . -run ^TestTrieWalk$ -count=1
works always but -count=10
crashes... I'm not sure if this is something from my changes or just anything wrong with the trie_test.go
Thank you @p4u for your input. Have you checked this repository which does the export of an Aergo state snapshot ? https://github.com/aergoio/state-tools
I did not know about the existence of that repository, I'll take a look.
However, from a SMT API consumer perspective with the experience of using several goLang Merkletree implementations for blockchain development, I think the following methods are missing:
- A
Walk()
as proposed here - A
Snapshot(root)
in order to make an immutable tree (will not change over time) - Get and Walk should allow specifying a
root
, something likesmt.Get(key, root []byte)
- A
Count(root)
method in order to get the number of leafs - A way to export and import the tree in order to generate the same exact Root hash
Does it makes sense to you? To this end, some functions from the state-tools repository might be added to the SMT trie package. I think it would help on the adoption of this trie implementation by other open source blockchain projects.
This is our interface and our current implementations (where I want to add Aergo SMT): https://gitlab.com/vocdoni/go-dvote/-/tree/master/statedb
Definitely makes sense.
I know some projects used the same trie but usually adapt it to their needs. So if there is consensus on an interface/usage that is useful to many, I'm happy to add features. We might have to refactor outside of the Aergo client code.
The interface you linked mentions Iterate
, is that the same as Walk
but for iterating from a subtree?
There is also the new approach https://github.com/ledgerwatch/turbo-geth which stores the leaves directly instead of querying from the root in logN, and re-constructs the root when a leaf is updated. It brings performance benefits but changes how we think about the trie (need to keep track of what is the current version of the trie).
Hey @paouvrard I have been out for some days but now I'm back. Thank you for your review, I am going to incorporate the changes.
I applied your suggestions and now go test -timeout 30s . -run=^TestTrieWalk$ -count=100
works fine, thank you!
I added another function named GetWithRoot
in order to Get a value for a specific Root. And in addition I added the root
as a parameter to Walk()
to the caller can choose on which Root he wants to walk.
I keep everything on the same PR because in my local repository I did not split it, I hope that's not a problem.
Looking forward for your review :)
Damn it, go test -timeout 30s . -count=100
fails... I'll look into it.
Fixed! Now go test -timeout 120s . -count=100
works for me.
The last version solves concurrency problems and it is data race safe. Tested with go test -timeout 120s . -run ^TestTrieWalk$ -count=100 -race
If this PR gets finally merged, next step could be to add a String() function, Export() and Import(), which IMO would make the API more powerful. Something like:
func (t *trie) String() string {
buf := bytes.Buffer{}
t.Walk(nil, func(k, v []byte) int32 {
buf.WriteString(fmt.Sprintf("%x => %x\n", k, v))
return 0
})
return buf.String()
}
So I see there is probably no interest on having this new methods on the SMT. That's fine. I forked the code and applied some changes (including a new abstraction layer). If anyone is interested, the code is here: https://github.com/p4u/asmt