cosmos / iavl

Merkleized IAVL+ Tree implementation in Go

IAVL+ Tree

Note: Requires Go 1.18+

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

Benchmarks

The purpose of this data structure is to provide persistent storage for key-value pairs (say to store account balances) such that a deterministic merkle root hash can be computed. The tree is balanced using a variant of the AVL algorithm so all operations are O(log(n)).

Nodes of this tree are immutable and indexed by their hash. Thus any node serves as an immutable snapshot which lets us stage uncommitted transactions from the mempool cheaply, and we can instantly roll back to the last committed state to process transactions of a newly committed block (which may not be the same set of transactions as those from the mempool).

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Whenever this condition is violated upon an update, the tree is rebalanced by creating O(log(n)) new nodes that point to unmodified nodes of the old tree. In the original AVL algorithm, inner nodes can also hold key-value pairs. The AVL+ algorithm (note the plus) modifies the AVL algorithm to keep all values on leaf nodes, while only using branch-nodes to store keys. This simplifies the algorithm while keeping the merkle hash trail short.

In Ethereum, the analog is Patricia tries. There are tradeoffs. Keys do not need to be hashed prior to insertion in IAVL+ trees, so this provides faster iteration in the key space which may benefit some applications. The logic is simpler to implement, requiring only two types of nodes -- inner nodes and leaf nodes. On the other hand, while IAVL+ trees provide a deterministic merkle root hash, it depends on the order of transactions. In practice this shouldn't be a problem, since you can efficiently encode the tree structure when serializing the tree contents.

IAVL x Cosmos SDK

IAVL	DB Interface	Cosmos SDK
v0.19.x	tm-db	v0.45.x, v0.46.x
v0.20.x	cometbft-db	v0.47.x
v1.x.x	cosmos-db	-

NOTE: In the past, a v0.21.x release was published, but never used in production. It was retracted to avoid confusion.

iavl's Issues

Bump Tendermint version to v0.26.0?

I see that the develop branch is already on version = "=v0.26.0-rc0".

As v0.26.0 is quite a large release, and it also moves from 20 bytes to 32 bytes hashes, would you consider bumping the Tendermint version in Gopkg.toml of the master branch to v0.26.0?

Define design Decisions of IAVL

Reference to discussion: #167 (comment)

Reintroduce encoding of proofs, export verification-related types

The proof.Bytes() disappeared with introducing range proofs. We might want to reintroduce this (could basically be an amino encoding of the proof). If we want to write (or others to write) a proof-verifier in other languages we can pass it the encoded bytes, describe how to decode them and how to verify the (range)-proof.

At the same time we should export (and document) every verification-relevant type included in the proof (including proofLeafNode).

Switch the internal hash function to SHA2 from RIPEMD160

I'm expecting that the auditors will eventually make the same recommendation.

But I don't think we should go to 1.0 with RIPEMD160 as our hash function.

RIPEMD160 is a bad choice for a few reasons.

1. The birthday bound on RIPEMD160 is 2^80 for a second preimage. A 2nd preimage would at very least allow for state corruption in our database and possibly allow for forgeries

2. RIPEMD160 is roughly the same speed/throughput as SHA256 on current hardware. Future generations of Intel and ARM server hardware have will have native SHA256 instructions that allow massive speed ups. Here is how fast SHA156 is on Ryzen: https://crypto.stackexchange.com/questions/50618/how-fast-can-a-sha-256-implementation-go/50620

3. RIPEMD160 is 10x more expensive to verify on the EVM than sha256.
   https://github.com/ethereum/go-ethereum/blob/master/params/protocol_params.go#L69-L72

Bikeshed

It's a reasonable choice to ask if we should adopt a modern hash function. The consensus among hash function experts is that SHA2 will never be broken and will likely be the most widely supported hash function for the rest of human existence.

BLAKE2b is almost 5x faster in software than RIPE160MD but doesn't currently have ethereum ecosystem compatibility and is unlikely ever to be implemented in widely available hardware. Tho hardware sha256 is only 2x faster blake2b.

Shake128 is kinda slow. Farfalle is very fast but too new.

Ethereum KECCAK is indefensible.

deleting the previous version causes a panic

Test code to reproduce:

tree := iavl.NewMutableTree(db.NewMemDB(), 1024)

tree.Set([]byte{0x1}, []byte{0x1})

tree.SaveVersion()

tree.Set([]byte{0x1}, []byte{0x2})

tree.SaveVersion()

tree.LoadVersionForOverwriting(1)

tree.Set([]byte{0x2}, []byte{0x3})

tree.SaveVersion()

tree.DeleteVersion(1)

tree.Set([]byte{0x1}, []byte{0x3})

The last line of code panics. Probably deleting the version that was loaded for overwriting causes this panic.

Write Spec

We need a clear specification of how this works, most importantly how data is serialized and hashes are computed.

A secondary concern is how it's cached and persisted on disk.

Idempotent SaveVersion(), need tests

VersionedTree.SaveVersion() should return successfully if the save is idempotent.
We still need tests for this commit: ae2ea4a

Remove dependency on go-wire

iavl uses/vendors go-wire (which depends on ripemd160)
Make it either indpendendent from go-wire / amino, or update to amino.

Remove ripemd dependency from gilde file(s).

Tendermint tmlibs and common dependencies

tmlibs and common are core dependencies of Tendermint containing a lot of somewhat independent code. Aggregating this code does make a lot of sense for versioning Tendermint, but for other projects like this one creates an undesirable level of coupling that could be avoided. I would like to propose that we drop the dependency on both. This would make it possible to upgrade Tendermint and iavl independently without forcing an upgrade of one or the other, which is the issue I am running into. I would argue that the code dependencies that iavl has on tmlibs and common are trivial, and particularly in the latter case is not pulling its weight.

tmlibs is currently imported for a subset of the DB interface and NewMemDB. This is convenient but means we pull in an entire dependency of tmlibs which makes it hard to use independently with Tendermint. Instead we could replicate the portion of the DB interface we need (Get, Set, NewBatch, and Iterator). MemDB is pretty trivial and the implementation against this subset interface would be even easier. This also adds a significant advantage for extensibility and mocking int that NodeDB would only be asking for what it actually needs - which is not the entire DB interface (e.g. https://blog.chewxy.com/2018/03/18/golang-interfaces/). I think this combined with decoupling from Tendermint/tmlibs is probably a good enough reason to accept the small amount of duplication. Admittedly iavl does depend on the semantics of the DB interface, but I think we could make clear that you may want use tmlibs in your iavl-based application - you would also have the flexibility to use a previous version with this subset interface (I think - and if not it would easier to make an adapter).

common is used for HexBytes, RandStr, Fmt, and PanicSanity. I think this is one of those cases where being DRY is the wrong thing to do. These are all relatively low value methods and don't seem to me to justify the dependency. They could either be replicated or removed. I feel like HexBytes is a convention that should belong to parent projects, RandStr introduces non-determinism into the unit tests which is not ideal, and Fmt and PanicSanity add very little.

Write test to test getRangeProof logic

https://github.com/tendermint/iavl/pull/105/files#r215906281

I scanned the history and it looks like pathCount = -1 is correct -- I think the pathCount-- was introduced as a bug; but as Ismael points out, the tests should have caught it but didn't.

We should write tests that fail when pathCount-- but passes with pathCount = -1.

Clarify tree.Hash / Skipped test TestProof

Find out why TestProof fails (tree root never seems to match here).
It's not clear why this is a race-condition. Either 1) fix test, 2) clarify why it is skipped, or 3) remove test (only if the test does not make sense).

https://github.com/tendermint/iavl/blob/35f66e53d9b01e83b30de68b931f54b2477a94c9/basic_test.go#L392-L422

Setup CI for testing

Redesign the IAVL tree with pruning in mind

When we original designed the IAVL tree, the application state did not prune old state and all versions were kept in memory.

The current default behavior is that we prune we keep the last 100 versions and prune the 101st version. If the application has a the behavior of having "hot" keys that updated on every block, this effective doubles the disk i/o.

At the moment, I think the biggest improvement in IAVL i/o performance is that we introduce awareness of the pruning strategy into the IAVL tree so that generally we don't write values to the database except at snapshot heights.

If pruning is disabled, all values are persisted to the database.

When using the deleteVersion method, the disk size increases.

After each commit, call the deleteVersion function to delete the previous version.

The deletion attempted to reduce the size of the data, but the size increased.

Could you explain why this is happening?

Use version - v0.11.0

Compare size
version:10,000, size:3.1 MB (No delete previous version)
version:10,000, size:4.0 MB (Delete previous version)

Is iavl tree multi-routine safe?

in the following code, TestIavlRaceMultAddr( ) has 5 account(= routine ), which tries to get/set its owner transaction ID concurrently, and race occurs?

How can I avoid such race condition except adding mutex in GetNextID()? Any comments are welcome!

you can remove the ".txt" from the race_test.go.txt and run the following test case.

race_test.go.txt
//Source code

---

`package iavl

import (
"fmt"
"github.com/stretchr/testify/assert"
"github.com/tendermint/tm-cmn/db"
"math/big"
"sync"
"testing"
)

func Int64ToBytes(i int64) []byte {
v := big.NewInt(i)
return v.Bytes()
}

func BytesToInt64(buf []byte) int64 {
v:= big.NewInt(0)
v.SetBytes(buf)
return v.Int64()
}

//Self-increasing ID
func GetNextId(tree *MutableTree, key []byte) int64 {
_, bz := tree.Get(key)
value := BytesToInt64(bz)
tree.Set(key, Int64ToBytes(value+1))
return value
}

//MultAddress, race happens
func TestIavlRaceMultAddr(t testing.T) {
db := db.NewMemDB()
tree := NewMutableTree(db, 0)
addrNum, iterNum := 5, 10
seenMap := make(map[string]string, addrNumiterNum)

var mtx sync.Mutex
var wg sync.WaitGroup


for addr := 0; addr <= addrNum; addr++ {
	wg.Add(1)
	key := []byte(fmt.Sprintf("address%v", addr))
	tree.Set(key, Int64ToBytes(0))

	go func(key []byte) {
		for iter := 0; iter < iterNum; iter++ {
			val := GetNextId(tree, key)
			mtx.Lock()
			_, seen := seenMap[fmt.Sprintf("%s-%d", string(key[:]), val)]
			assert.False(t, seen, "duplicate:%s-%d ", string(key[:]), val)
			seenMap[fmt.Sprintf("%s-%d", string(key[:]), val)] = "seen"
			mtx.Unlock()
		}
		defer wg.Done()
	}(key)
}
wg.Wait()

}
//SingleAddr, work as expected
func TestIavlRaceSingleAddr(t *testing.T) {
db := db.NewMemDB()
tree := NewMutableTree(db, 100)
iterNum := 100
seenMap := make(map[int]string, iterNum)

var mtx sync.Mutex

key := []byte("address")
tree.Set(key, Int64ToBytes(0))

for iter := 0; iter < iterNum; iter++ {
	val := GetNextId(tree, key)

	mtx.Lock()
	_, seen := seenMap[int(val)]
	assert.False(t, seen, "duplicate:%d ", val)
	seenMap[int(val)] = "seen"
	mtx.Unlock()
}

}

func TestInt2Byte(t *testing.T){
for i:=0; i<10000;i++{
v:= BytesToInt64(Int64ToBytes(int64(i)))
assert.Equal(t, int64(i), v)
}
}

//testReult

add information about which hashing algorithm is used

@simonvadee commented on Mon Sep 25 2017

I have an ABCI application storing IAVLProofs and one has to be able to validate these proofs outside of the application's context (and independently from the merkleeyes module). The application also store different kinds of merkle trees (using some other hashing algorithm), but all of them implementing the IAVL format to store merkle proofs :

type IAVLProof struct {
	LeafHash   []byte
	InnerNodes []IAVLProofInnerNode
	RootHash   []byte
}

type IAVLProofInnerNode struct {
	Height int8
	Size   int
	Left   []byte
	Right  []byte
}

The only information missing to independently validate a proof is the hsh function used to build the IAVL tree (ripemd160 in tendermint's case). My suggestion is to add a field hashFunction, either in IAVLProofInnerNode or directly in IAVLProof to make it possible for merkle proof validation systems to work with several kinds of merkle trees, including your IAVL+ implementation.

Accessing previous versions of tree leaks memory

When a version is saved SaveBranch is called: https://github.com/tendermint/iavl/blob/master/nodedb.go#L133

SaveBranch both saves the nodes to disk and unloads the nodes from memory. This is nice/necessary because it means all we store in memory as our versioned history grows is a pointer (hash) two the root of each older version.

However if we access values from a previous tree via GetVersioned (btw we could really do with a IterateVersioned or just GetTree(version) because currently hanging on to a previous tree is awkward but possible by calling Tree() the right time) then the necessary nodes to access our value are lazy-loaded. However once loaded they are never unloaded which is a memory leak. We cannot call SaveBranch to unload the tree because the nodeDB is private.

Context: we hang on to the previous tree and use it as a read-only tree that can run long iterations on without interfering with writes. It's possible that we load large portions of the tree of many previous versions. We also currently store unlimited versions, so these things together mean we will leak memory unless we can unload.

Allow SaveBranch would do the job it doesn't seem quite right for this purpose. Can we expose the ability to unload a Tree.

On a more general note, it feels like some useful functionality is hidden by being unexported. For example access to previous trees or operations on the NodeDB. It would be nice to see a slightly more permissive policy to exporting types and functions that would allow IAVL to be used in ways that might not have been anticipated by the user. I realise it is a balance, but currently it feels a little closed off to reasonable extension.

An optimal backend for the IAVL

So I've been thinking a bit about the properties of an optimal backend for the IAVL tree.

We currently use a general purpose backend for the IAVL tree like leveldb.

This isn't optimal because general purpose back end because general purpose backends where not designed to store immutable data structures and locality properties of common data access.

Here are things we observe.

1. Some leaves are mutated frequently. Some subtrees are accessed every block. Others are infrequently red. We want to have a cache oblivious data structure that is optimized for this access pattern. Frequently mutated and red data should be stored together.

2. Ideally we would have copy on write semantics for the immutable data structure and we should be pulling lessons from purely functional data structures. Ideally we should never copy a leaves and nodes from a new version of the merkle tree. Instead we should track references to those nodes in unpruned versions and only delete the value when all the versions which reference a leaf/node have been pruned.

Can I use multi iavl trees with one db?

Like using MPT for ethereum storage tries, can I make multiple iavl trees for each account storages?
Iavl tree looks great to world state,but I am not sure how to make multiple iavl trees with one db.
If nodedb can handle such as like namespace (prefix) per trees, It can work.. IMHO. Is it right?

iavl should only be imported by cosmos-sdk

from discussion with Bucky

Make it possible to obtain the hash of sub-trees, and consider re-exposing the ability to `load` sub-trees from sub-root hashes

In previous incarnations of go-merkle we have used tree.Load(subRootHash) (https://github.com/tendermint/iavl/blob/master/tree.go#L229-L237) to load a sub-root and make use of an addressable sub-tree of our merkle tree as in: https://github.com/hyperledger/burrow/blob/develop/execution/state.go#L406-L412

In the current code base this functionality has been made private: https://github.com/tendermint/iavl/blob/master/tree.go#L229-L237. I can also see that the more limited sharing in this API is important.

In our case we have a global storage prefix tree where all storage for an account lives under a particular prefix. We need to be able to quickly check if a particular account has changed rather than the entire storage tree and so we at least need a mechanism to take the hash of a sub-tree, but in this updated code-base it is only possible to do that for the root of a Tree: https://github.com/tendermint/iavl/blob/master/tree.go#L85

I wonder if there are some safety reasons why the load function has been made private. It would suffice for us if we had:

func (t *Tree) SubHash(prefix []byte) []byte { ... }

and we needed maintain a reference to a sub-tree (that may need to be carefully coordinated in db access to the root).

Happy to do the changes and make a PR if you are happy with a particular direction. More broadly I'd be up for contributing to maintaining this project, which we rely upon and I was once not sure of its status through go-merkle, tmlibs, and merkleeyes. I see the cosmos-sdk uses it now so assume its future is more assured.

Thanks!

DeleteVersion is quite slow

While reworking the tests for #25, I decided to replicate the proper orphan cleanup. That is, after SaveVersion(version+1), I also call DeleteVersion(version-1).

Here are the rough results from local benchmarks, without DeleteVersion (no cleanup):

$ go test -bench=Medium -v
Init Tree took 96.26 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  300000	      5078 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      5900 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   20000	     75020 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	     200	   9160188 ns/op
Init Tree took 57.27 MB

And with DeleteVersion (as we use it min the sdk):

$ go test -bench=Medium -v
Init Tree took 96.25 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  200000	      5149 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      5980 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   10000	    286915 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      50	  29462219 ns/op

context:
times for update is each call to update, committing to "disk"/"memdb" every 100 updates
time for block is the total time to call query/set on 100 different keys.
all of this is done with a db prep-populated with 100k key/value pairs
(the code is <dbtype>-<initial size>-<block size>-<key bytes>-<value bytes>)

We can see that adding the DeleteVersion cleanup triples the time.

I would show numbers for goleveldb, except that it crashes.... #27

Update / improve godoc

As part of the spec writing work, it would be nice to update and improve the golang documentation.

Current state is here: http://localhost:6060/pkg/github.com/tendermint/iavl/

Benchmark scripts out of date

Scripts in benchmarks/setup/ contain references to tendermint/merkleeyes/iavl. Need to be updated to tendermint/iavl. (example)

Allow Index Keys

right now iavl panics if there is a no value provided:
https://github.com/tendermint/iavl/blob/master/tree.go#L90

we do however want to be able to store indexes which should be holding no value, right now we can store a single 0 byte, but I think it would be useful to allow either storing nil, or building in some explicit index function

Use immutable key for nodes to avoid excessive LevelDB reorgs

Follow-up of cosmos/cosmos-sdk#2131.

After discussion on Slack, a suggestion to implement a fix:

1. For each new node in IAVL tree, assign an sequential integer ID. This ID never changes for the node.
2. Use this integer ID as "key" in the <key, value> pair stored in LevelDB.
3. The value part stored in LevelDB contains the node hash (existing LevelDB key).
4. All parent/child references must be through integer IDs.
5. A special "root" key stored in LevelDB has an value that contains the integer ID of the root node.

Why are Iterate/IterateRange and IterateRangeInclusive expecting different callback functions

Iterate/IterateRange expect a function from (key, value) to boolean, while IterateRangeInclusive expects a function from (key, value, version) to boolean.

Some errors are not checked (errcheck linter)

Some errors are not handled. If we expect that no errors can occur at these places, we can panic to clarify that something is seriously wrong (if an error occurs). If not, at least add a comment. Better handle all errors:

node.go:197:14:warning: error return value not checked (hasher.Write(buf.Bytes())) (errcheck)
node.go:216:14:warning: error return value not checked (hasher.Write(buf.Bytes())) (errcheck)
orphaning_tree.go:49:25:warning: error return value not checked (tree.ndb.SaveEmptyRoot(version)) (errcheck)
orphaning_tree.go:55:20:warning: error return value not checked (tree.ndb.SaveRoot(tree.root, version)) (errcheck)
proof.go:70:14:warning: error return value not checked (hasher.Write(buf.Bytes())) (errcheck)
proof.go:101:14:warning: error return value not checked (hasher.Write(buf.Bytes())) (errcheck)

Benchmarks crash on goleveldb

Orphan cleanup issue. I'm not sure if VersionedTree has a problem, or if it is the benchmark....

$ go test -bench=Medium -v
Init Tree took 96.31 MB
goos: linux
goarch: amd64
pkg: github.com/tendermint/iavl/benchmarks
BenchmarkMedium/memdb-100000-100-16-40/query-miss-8         	  300000	      5091 ns/op
BenchmarkMedium/memdb-100000-100-16-40/query-hits-8         	  300000	      5897 ns/op
BenchmarkMedium/memdb-100000-100-16-40/update-8             	   10000	    291086 ns/op
BenchmarkMedium/memdb-100000-100-16-40/block-8              	      50	  29693712 ns/op
Init Tree took 57.69 MB
BenchmarkMedium/goleveldb-100000-100-16-40/query-miss-8     	  100000	     13341 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/query-hits-8     	  100000	     17206 ns/op
BenchmarkMedium/goleveldb-100000-100-16-40/update-8         	panic: Panicked on a Sanity Check: Orphan expires before it comes alive

goroutine 89 [running]:
github.com/tendermint/iavl/vendor/github.com/tendermint/tmlibs/common.PanicSanity(0x7c22c0, 0x8a2180)
	/home/ethan/go/src/github.com/tendermint/iavl/vendor/github.com/tendermint/tmlibs/common/errors.go:26 +0xf3
github.com/tendermint/iavl.(*nodeDB).saveOrphan(0xc4201c00a0, 0xc42c2c4e40, 0x14, 0x20, 0x1, 0x0)
	/home/ethan/go/src/github.com/tendermint/iavl/nodedb.go:200 +0x189
github.com/tendermint/iavl.(*nodeDB).SaveOrphans(0xc4201c00a0, 0x2, 0xc42c43d050)
	/home/ethan/go/src/github.com/tendermint/iavl/nodedb.go:193 +0x14d
github.com/tendermint/iavl.(*orphaningTree).SaveVersion(0xc42c8ee560, 0x2)
	/home/ethan/go/src/github.com/tendermint/iavl/orphaning_tree.go:63 +0x8b
github.com/tendermint/iavl.(*VersionedTree).SaveVersion(0xc4201ce000, 0x2, 0x14, 0x20, 0xc42c8ee560, 0xc423c32b00, 0x10)
	/home/ethan/go/src/github.com/tendermint/iavl/versioned_tree.go:138 +0x107
github.com/tendermint/iavl/benchmarks.commitTree(0xc42019ca80, 0xc4201ce000)
	/home/ethan/go/src/github.com/tendermint/iavl/benchmarks/bench_test.go:39 +0x4f
github.com/tendermint/iavl/benchmarks.runUpdate(0xc42019ca80, 0xc4201ce000, 0x28, 0x64, 0xc42b386000, 0x186a0, 0x186a0, 0x4a1c54c2d)
	/home/ethan/go/src/github.com/tendermint/iavl/benchmarks/bench_test.go:83 +0x13e
github.com/tendermint/iavl/benchmarks.runSuite.func3(0xc42019ca80)
	/home/ethan/go/src/github.com/tendermint/iavl/benchmarks/bench_test.go:272 +0x6d
testing.(*B).runN(0xc42019ca80, 0x64)
	/usr/lib/go-1.9/src/testing/benchmark.go:141 +0xb2
testing.(*B).launch(0xc42019ca80)
	/usr/lib/go-1.9/src/testing/benchmark.go:291 +0x84
created by testing.(*B).doBench
	/usr/lib/go-1.9/src/testing/benchmark.go:260 +0x70
exit status 2
FAIL	github.com/tendermint/iavl/benchmarks	19.918s

Restructure repository / packages

Currently, every file lives in the root directory. We need to refactor the code such that different logical parts live in different packages. This will also help clarifying the exposed API.

Proof should return index

https://github.com/tendermint/abci/pull/116/files#diff-2a85f77f2fae17da0ba77e56b78f3234R68

SaveVersion won't save an empty tree

This is admittedly an edge case, but SaveVersion returns error on attempting to save an empty tree.

The following code panics:

package main

import (
	"github.com/tendermint/iavl"
	"github.com/tendermint/tmlibs/db"
)

func main() {
	// create a new database
	db := db.NewDB("bug", db.GoLevelDBBackendStr, "")
	state := iavl.NewVersionedTree(500, db)
	height := state.LatestVersion() + 1

	_, err := state.SaveVersion(height)
	if err != nil {
		panic(err)
	}
}

This also happens if you remove the last key and attempt to save (which is how we detected it).

There's not a good workaround. Testing the returned error for equality to iavl.ErrNilRoot doesn't help, because if you are attempting to preserve history but remove all keys, that last key removal was not saved.

A workaround I don't particularly like is to store a single "impossible" key in the tree at creation so that it's basically impossible to remove the last key.

If you would please give some guidance on how you think this should be handled, I will try to create a PR that fixes it.

Inspect cosmos-sdk db?

I have a basic question. Im building a cosmos-sdk app and running into a problem joining two nodes. I get an error that looks like the following despite both nodes using the same genesis file.

E[2019-10-31|06:04:59.442] enterPrevote: ProposalBlock is invalid       module=consensus height=2 round=0 err="Wrong Block.Header.AppHash.  Expected 0800C9102DB9D3D0E288E8D4FA08DF74399498A855D25CF1EAFE2E8F5C630FF3, got 137CB732C9449914B4F97126309AAFCB2B3A2DD231CED3D48460F13C2DCE7D7B"

I'd like to inspect the database of cosmos and I thought this was the tool for that, but I can't seem to figure out how to use it properly and I can't find any example or docs on how to use it with cosmos. Maybe im barking up the wrong tree.

I start my chain, add a few records into the kvstore, and my db is empty somehow.

iaviewer data ~/.ssd/data/application.db                                                                                             ✓  08:03:53
Got version: 0
Printing all keys with hashed values (to detect diff)
Hash:
Size: 0

Any insights? thanks in advance.

Refactor API for clean separation of Mutable vs Immutable access to tree

Refactor API to split functionality into mutable and immutable interfaces. This will enable read only snapshots to previously stored versions, (fixing #68, see also #87). With these changes, it will be possible to load read-only snapshots at previous versions on demand, and only load mutable trees at the most recently saved tree. This should speed up load times for trees with many versions, as we are currently loading each root into memory, which takes a linear number of database calls.

Steps:

• Replace Tree with ImmutableTree
• Merge VersionedTree and orphaningTree into MutableTree
• Move mutable methods on Tree into MutableTree
• Move recursive mutation methods on Node into MutableTree
• Move recursive lookup methods on Node into ImmutableTree

High level overview of resulting interfaces:

MutableTree

• tree *ImmutableTree
• Load()
• Set(key, value)
• Remove(key)
• Commit()
• Rollback()
• GetImmutable(version)
• DeleteImmutable(version)

ImmutableTree

• root *Node
• Has(key)
• Get(key)
• GetWithProof(key)
• GetByIndex(index)
• IterateRange(start, end)
• GetRangeWithProof(start, end)
• Hash()
• Size()
• Version()

Node

• isLeaf()
• hash()
• getLeftNode()
• getRightNode()

Do we need separate getters for cast return types?

We currently have multiple similar getter methods, such as Get64, Has64, Version64, etc. with corresponding methods Get, Has, Version, etc. which return regular ints.

Are these needed for some specific reason? or is it just to avoid user side casting to int?

cc @liamsi

Generic Merkle Operators

The Merkle proof operator is a generic proof format that can be implemented on any platform easily, without depending on specific libraries or language features. When a Merkle proof is needed to be wire encoded and verified on another machine, platform dependant parts can be converted into the generic merkle format.

We are now using IAVLValueOp, IAVLAbsentOp which are wrappers on golang struct RangeProof, which cannot be easily decoded and verified on other machines(e.g. solidity).

Turns out IAVLValueOp can be decomposed into few primitive operators, and I think the other proof types(absent and range) can be too.

// For a single input, prepends lengthprefixed Key, prepends Prefix, appends Suffix. 
type HashConcatOp struct {
  Key []byte
  Prefix []byte
  Suffix []byte
}

// Apply SHA256 hash on the inputs
type HashValueOp struct{}

// Prepend their length on the inputs
type PrependLengthOp struct {}

With them, we can define IAVL existence proof as the following:

[]merkle.ProofOperator{
  // LEAFNODE
  HashValueOp{},
  PrependLengthOp{},
  HashConcatOp{Key: key, Prefix: 0 + 1 + Version, Suffix: nil},
  // INNERNODES(repeat)
  for node := range nodes {
    PrependLengthOp{},
    if len(Left) == 0
      HashConcatOp{Key: nil, Prefix: Height + Size + Version, Suffix: Right},  
    } else {
      HashConcatOp{Key: nil, Prefix: Height + Size + Version + Left, Suffix: nil}
    },
  }
}

Local test passing: mossid#1

VersionedTree.LatestVersion() no longer exists in v0.6.1

How do we get the latest version now? The docs still use that function as an example, but the example is the only place in that file where the string LatestVersion exists.

Not increasing the version when the tree is untouched

SaveVersion methods always increase the version of the tree.
I suggest to check the hash before increasing the version, if the hash has not changed, it can simply return the current hash. Something like:

if bytes.Compare(tree.LastHash, tree.WorkingHash()) == 0) // Not Hash()
  return tree.LastHash, tree.version, nil

Changing version will cause changing hash and it can cause application thinks that tree has changed which is not true.

UPDATE:
WorkingHash() (not Hash()) return current Hash.

drop `iavl_` prefix from file names

dep: Change the tendermint import

Currently we're using an old tendermint version, and we use an equal sign. Because of this, we have to use an override for tendermint in the sdk's gopkg.toml. This makes it hard to import the sdk, and use any type from tendermint. This is because overrides do not apply transitively with dep. Only overrides in the top directory you're calling dep ensure from get applied. Therefore in your downstream application you have to add an override import yourself, which is confusing,

We should change the tendermint import to be ^v0.22.0, or ^v0.22.4. (In the SDK its just getting replaced with v0.22.4 anyway) This would alleviate issues in the future as well.

Make iavl.Tree unexported

The VersionedTree should be sufficient for people to work with. We currently use the Tree only in the cosmos-sdk iavlstore. It would be nice if we could change this there. It would further simplify the exposed API.

There are some test-cases showing even our devs are confused by how to use the tree vs. the versioned tree: #50

cc @jlandrews

also related #62

Use 64-bit wide prefix rather than 10 decimal digits

It would take a few hundred years to cause my use case (one version per Tendermint block) any problems, but it currently we overflow various of our nodedb prefixes well before we overflow the underyling int64 type used for versions:

https://github.com/tendermint/iavl/blob/master/nodedb.go#L24-L30

IAVL used to load every node from previous versions:

v0.9.2...v0.10.0#diff-6d87913bee304887177dad726b816faeR256

Once we get past version 9999999999 then we will not be able to load newer versions because of the behaviour of Sscanf: https://github.com/tendermint/iavl/blob/master/nodedb.go#L344.

We'll actually still save them because the corresponding Sprintf will include digits outside the padding. But we'll hit this error when loading a large version: https://github.com/tendermint/iavl/blob/master/mutable_tree.go#L248

It would make sense to use a prefix that is 8 bytes - we could use raw big-endian padded bytes or we could use 16 chars of hex so that we maintain the lexicographical sorting we need for iteration. At least things blow up at the same time (and a significantly larger number) as well as it being neater to concede the same version bound.

Note the lazy-loading added by 0.10.0 makes it cheap to store a large number of versions, which is nice.

Range proofs are missing version numbers

Alexis Sellier [17:20] 
basically, at the moment we verify the proof by creating a `proofLeafNode` for every key

[17:20] 
but the issue is we don't have the versions for each key (they aren't returned or passed into the verification function)

[17:20] 
so there's no way for it to hash the keys properly for the proof to verify

[17:21] 
the obvious thing to do is return versions too with the abci query

Would like an IterateRange where start is inclusive and end is non-inclusive

This is a pretty common practice and I feel the expected behavior. Would make getting subspaces much much easier.

EDIT: Oops I misread the comment of IterateRangeInclusive.

Evaluate feasibility of deterministic indexical chunk mapping for state sync

Is there an efficient way we can map from integer indices to sub-key-spaces of a particular tree version, such that chunks would be approximately the same size or at least size-bounded, and individually provable (some metadata about top-level tree-structure can be transmitted up front)?

ref tendermint/tendermint#828

cc @liamsi @ebuchman

switch from glide to dep

most of the stack has made this switch

Consider content-addressing values in the nodeDB

It would be a nice feature for the application layer not to have to worry about normalising data that may get stored twice. For example in the case of Burrow things like deployed bytecode or serialised transactions stored multiple times in events could be normalised in the application layer but it is more general if we can lean on the storage layer for this.

The way this would work is value []byte in Node would become valueAddress []byte where valueAddress is the hash of the value. When writing a value we would first try and read the value from the db by its hash, if the key is found then no write is performed. We could also add a cache similar to nodeCache for values that could catch reads (at least for nodes in the nodeCache).

In this way we would deduplicate storage across the lifetime of the chain - depending on the level of duplication this could be significant. Also, knowing this, applications can try to avoid mixing noise with values that might otherwise be dedupable when storing in the tree. It would cost almost nothing computationally given that we are already hashing Node each time we save - this would just make that a two step process where we first hash the value and then only have that hash to hash for the node.

I wanted to get some feedback on this, but if I actually get some time to spend on the state subsystem of Burrow this is something I'd be interested in taking on. Though I realise I have been threatening to do something useful round here for a while ... :o

enhance dotgraph functionality

for our usage and on my way implement tendermint state sync (tendermint/tendermint#828), I found dotgraph is helpful while it somehow broken now:

1. node key and values are encoded []byte array, the encoding logic is depends on application, so sometimes they cannot be represented as string, we need show their hex representation on graph.
2. edges cannot be established because the lazy loading of children nodes, we need a set of traversal methods set child along the way we traverse. Currently I just do below on my way of debugging:

func (node *Node) getLeftNode(t *ImmutableTree) *Node {
	if node.leftNode != nil {
		return node.leftNode
	}
	node.leftNode = t.ndb.GetNode(node.leftHash)
	return node.leftNode
}

func (node *Node) getRightNode(t *ImmutableTree) *Node {
	if node.rightNode != nil {
		return node.rightNode
	}
	node.rightNode = t.ndb.GetNode(node.rightHash)
	return node.rightNode
}

I have already made these changes 80% done on my local machine, will push them soon.

Proposal: export `proofLeafNode`

Currently, proofLeafNode is not exported. While it is good practice to export only what is really neccessary (and hide fields and functionality that are not essential for the API), I think this type should be public/exported: If someone is about to write a verifier in another language, he needs to know enough details what a RangeProof consists of (and proofLeafNode is part of that):
https://github.com/tendermint/iavl/blob/f2c70966873724a199ea37d0cbfc8b50baa0f7bf/proof_range.go#L12-L21

Exporting the type would also create a proper godoc item. Similarly, proofInnerNode (as PathToLeaf is just a type alias to []proofInnerNode).

cc @jlandrews @jaekwon

Update to circleci 2.0, use dep only

CircleCI 1.0 will no longer be supported after August 31, 2018.

Also, there are still relicts of glide in the make file and a glide.yml file. Migrate completely to dep.