alexanderbez/mustafa_storage.txt

## mustafa_storage.txt
My current thoughts and conclusions after all this are:
1. I do not think that it's really necessary for Cosmos to replace the IAVL with the SMT, as they're both theoretically provide roughly the same computational complexity for operations. I think SMT is actually less suitable for the Cosmos SDK because it doesn't support efficient range proofs, and the Cosmos SDK modules use a lot of iteration.
2. The fact that Cosmos SDK modules use iteration is a poor design. Iterating over the entire validator set and requiring an O(n) operation to add a validator is not efficient; and IMO modules should be designed without iteration by using things like ordered linked list and binary search.
3. If Cosmos SDK did not require iteration, we could make the store way faster as we would not need to use a b-tree to cache keys.
4. It's possible to implement state storage+state commitment decoupling in IAVL; which is what I believe what https://github.com/cosmos/iavl/pull/468 does with "fast nodes".
5. The current IAVL is a hacky mish-mash of code that has been piled on over the a few years, and does not support pruning
6. It's not straightforward to just add SMT to store v1 because we need to allow for efficient range queries over historical and present state (which is doable using the technique I proposed above, but still extra unnecessary work: https://celestia-team.slack.com/archives/C03511RUB6H/p1663405482049109)
7. Fraud proofs / deep trees with IAVL should be efficient, because rebalancing operations afaik don't require you to access nodes that are not in the path of the merkle proof.

My conclusion is therefore:
1. In the future, someone should implement a modular store (and rewrite the IAVL) that fully decouples state storage and state commitment, so that you can for example swap out the state commitment to anything you like (IAVL, SMT, KZG, whatever) without effecting the state storage. In the future the Cosmos SDK can also do this, while keeping IAVL, thus avoiding the need for hard forks. I started with this here: https://github.com/celestiaorg/goodstore
2. We should try to upgrade Cosmos modules in the future to avoid iteration.
3. We should implement a deep tree for IAVL, I believe that deep proofs will be the same size as the ones for SMT, as rebalancing operations in an IAVL only requires looking at inner node stubs, which we have anyway from the Merkle proofs.
4. Since the IAVL supports efficient range proofs, fraud proofs for transactions that require iteration might actually be reasonably small anyway.

I'm implementing a better store, that decouples ss and sc, and uses a b-tree for ss caching, and a memory map for sc internal node caching

Initial results show that it blows the IAVL state store's cache out of the water for gets. Like 4x faster compared to roysc's store v1 benchmarks
goos: linux
goarch: amd64
pkg: github.com/celestiaorg/goodstore
cpu: 11th Gen Intel(R) Core(TM) i9-11900H @ 2.50GHz
BenchmarkGet-16    	 1969509	       666.6 ns/op	      15 B/op	       1 allocs/op
	My current thoughts and conclusions after all this are:
	1. I do not think that it's really necessary for Cosmos to replace the IAVL with the SMT, as they're both theoretically provide roughly the same computational complexity for operations. I think SMT is actually less suitable for the Cosmos SDK because it doesn't support efficient range proofs, and the Cosmos SDK modules use a lot of iteration.
	2. The fact that Cosmos SDK modules use iteration is a poor design. Iterating over the entire validator set and requiring an O(n) operation to add a validator is not efficient; and IMO modules should be designed without iteration by using things like ordered linked list and binary search.
	3. If Cosmos SDK did not require iteration, we could make the store way faster as we would not need to use a b-tree to cache keys.
	4. It's possible to implement state storage+state commitment decoupling in IAVL; which is what I believe what https://github.com/cosmos/iavl/pull/468 does with "fast nodes".
	5. The current IAVL is a hacky mish-mash of code that has been piled on over the a few years, and does not support pruning
	6. It's not straightforward to just add SMT to store v1 because we need to allow for efficient range queries over historical and present state (which is doable using the technique I proposed above, but still extra unnecessary work: https://celestia-team.slack.com/archives/C03511RUB6H/p1663405482049109)
	7. Fraud proofs / deep trees with IAVL should be efficient, because rebalancing operations afaik don't require you to access nodes that are not in the path of the merkle proof.

	My conclusion is therefore:
	1. In the future, someone should implement a modular store (and rewrite the IAVL) that fully decouples state storage and state commitment, so that you can for example swap out the state commitment to anything you like (IAVL, SMT, KZG, whatever) without effecting the state storage. In the future the Cosmos SDK can also do this, while keeping IAVL, thus avoiding the need for hard forks. I started with this here: https://github.com/celestiaorg/goodstore
	2. We should try to upgrade Cosmos modules in the future to avoid iteration.
	3. We should implement a deep tree for IAVL, I believe that deep proofs will be the same size as the ones for SMT, as rebalancing operations in an IAVL only requires looking at inner node stubs, which we have anyway from the Merkle proofs.
	4. Since the IAVL supports efficient range proofs, fraud proofs for transactions that require iteration might actually be reasonably small anyway.

	I'm implementing a better store, that decouples ss and sc, and uses a b-tree for ss caching, and a memory map for sc internal node caching

	Initial results show that it blows the IAVL state store's cache out of the water for gets. Like 4x faster compared to roysc's store v1 benchmarks
	goos: linux
	goarch: amd64
	pkg: github.com/celestiaorg/goodstore
	cpu: 11th Gen Intel(R) Core(TM) i9-11900H @ 2.50GHz
	BenchmarkGet-16 1969509 666.6 ns/op 15 B/op 1 allocs/op