What about a tree storing values at key=0xab and key=0xabcd? I imagine it having a node at the 0xab prefix with a value attached. It would have a right child (because 0xc is 0b1100, with the first bit being 1), but not a left child. Especially since you mentioned:
Disallowing keys that are prefixes of others
Several of the hashing schemes above seem to assume that no key can be a prefix of another key. That would disallow of some of the most obvious ways to combine the state trie into a single trie.
It would still be possible to combine the trie I expect, but require a little refactoring. Something like:
It is a bit messier to answer the question “does this account exist?”
It would compel trie implementations to implement a “delete range” API in order to erase all of an account at once
Ugly 33 and 65 byte keys
Most of those costs are implicit in combining into a single trie though. Really the only change is adding the 0x00 byte at the end of the account balance and nonce info, so it’s not a prefix of the others.
I don’t have enough background about the mentioned goal of supporting both 20 byte and 32 byte addresses, though, to tell if we can avoid one key ever being a prefix another.
Encoding leaves with null bytes for left & right children
I like simplicity of a predictable element count, but adding two “null” bytes to the final serialized node isn’t a tradeoff I would make for that simplicity. With the state trie in the rough range of 100 Megaleaves to 1 Gigaleaf, that can have a meaningful impact on sync time.
It looks like we could use 2 of those 5 top bits in the bin prefix to flag that the left or right child as null, then just skip it in the node body.
Misc
There appears to be a bit-flip typo in the first f in caff:
You are considering storage trees “hanging” from account nodes (like in @AlexeyAkhunov’s approach). I had a different model in mind. You are right, though, “hanging” storage is the correct model. This proposal still works in that case, as internal nodes also have a value. It’s just that the “either 2 children or none” property doesn’t hold anymore.
Exactly, and a third one to flag the presence of a value as well.
Code Merkelization isn’t an issue in this case: this is for the internal account+storage state, not proof generation.
For clarity, the rule is this: node_hash = hash(prefix_length%8 || prefix_bits || left_child_hash || right_child_hash || value)
I like this because it is pretty much the multiproof approach, and one can use a flat DB model. Then keys can be stored sequentially and the key length eventually doesn’t matter.
Practically, though, things get a bit more complicated: For example, when doing an insert, one needs to “guess” what the neighboring values are because bits aren’t stored along the path to get there.
It can be done, and I can think of a few hacks in the case of geth. I am not yet convinced it can be done by every client, though.
I am currently running tests on the “M2” approach to see how much the performance and size are impacted, so that I can then compare how much of a gain M3 is, I’m curious.
Your current implementation should work for M1, M2, and M3, you just hash differently. For example M3 omits prefix_bits when hashing. You are correct that M3 hashing include leaf_key at each leaf, but witnesses must have access to that anyway.
Is there anything wrong with banning keys from being prefixes of other keys? I don’t think we need that possibility for a tree model; eg. I was thinking:
jinx – I’m still thinking through the storage size implications, but it’s cool that we could get rid of encoding the account with rlp. You can see the ghost of the idea in how I skipped 0x01 here:
Well, I think that you don’t need to hash the storage slot, in this case. Anyway, I discourage the use of a nested storage slot after account key: storage is better to be considered as a separate concern, and this way, even allow to share same keys and values between storages of different accounts. Having the storage slot nested inside the account address key, implies, someway, that updating n storage slots after block execution, implies to create MORE intermediate nodes to update the trie, than in the current implementation, where the storage trie has less number of levels.
BTW I support that keys could be prefixes of other keys. IE in a storage trie, without hashing keys, we could save values under keys 0x01, 0x0101, 0x010101 and so on, removing the initial zeroes in many cases. The only remaining use for hashed keys for storage are the mappings in Solidity
Sorry, I am a bit late to the party, it took me a long time to get some fragments of time to understand what is going on. I find something like M3 variant proposed @poemm close to ideal. I do not really understand the concern with “guessing” what the neighbouring values are. As the implementer, you are free to chose which data structure you need for this. For example, we would be implementing this without needing any trees and inserts (we use approach based on the “prefix groups” and streaming computation of the state root). But if you are using trees, then why can’t this tree give you the information about the neighbouring values if you need it?
During our last conversation, @AlexeyAkhunov pointed out that removing the concept of extension nodes was addressing all the issues that I had with M2/M3. The structure becomes much simpler:
Pointing out of the most radical changes from M2/M3:
There are no extension nodes in the merkelization rule
The key value is encoded through the tree structure
There is no more need for extracting key bits
Clients and witnesses are still welcome to use extension nodes and explicit keys to store their data.
For example, and in order to save space, a client can store the data using extension nodes. Single-child internal nodes are generated on the fly while merkelizing the stored extension node.
Probably this is a dumb question, but since binarification requires all this recalculation, how about considering a switch from keccak256 to sha256 for the state trie?
The reasoning of Eth2 for using sha256 can be read here, including a claim about security.
I can think of two potential, but questionable, benefits:
Apparently one of the main benefits of sha256 is interoperability with other chains – could this potentially enable other chains to more easily verify proofs of Eth1 blocks? I don’t think it should make a huge difference anyhow.
Making Eth1 and Eth2 closer in terms of cryptographic primitives. Again, this is very slim, given there are more substantial differences between the two, starting with bls12-381 vs secp256k1.
Would there be any (other) benefit? Probably no significant ones, but maybe it is worth briefly entertaining the idea and discussing it.
Would there be any (other) benefit? Probably no significant ones, but maybe it is worth briefly entertaining the idea and discussing it.
I can see three other potential benefits:
sha256 is available in many more languages and platforms and a better coverage from security audits
sha256 is faster than Keccak256
keccak256 has a security flaw that sha256 doesn’t
is a given, so I don’t think there is a big consensus risk to switching. Still, unless either 2) or 3) is true I would say that it’s better not to fix something that isn’t broken.
I don’t expect 2) to be obvious, and indeed the performance is exactly the same when I tried to use sha256 in M4.
I was thinking: instead of adding an extra byte in order to access the account’s properties, and thus ending with 33-byte and 65-byte keys, how about dropping the last two bits of the hashed address (as in “secure trie” address) and using them as an item selector?
2 bits are lost here, which doesn’t matter for this use case: hashing is intended to make sure that values are evenly spread out in order to keep the trie balanced. So the right-most the bit is, the least it helps with balancing the trie. Furthermore, all these values will still be stored together in the DB so it won’t have any impact on the balance.
A quick check as of block ~8M doesn’t show any collision if the last 2 bits are chopped off. It is quite unlikely (a one in 2x10²⁸ chance) that there will be a collision.
It’s nice to be able to verify the state trie from within the EVM, which is currently cheaper to do with keccak256. Although maybe a shift to sha256 can come with the appropriate repricing measures to make it feasible to verify state roots on chain.
This key->value mapping has the huge benefit that it stores the key inside the trie, and yet it randomizes the key position.
Also it’s faster, because you can generate 80 bits of Keccack hash digest faster than 256 bits.
Finally it’s requires only 30 bytes for keys, 2 bytes less than the 32 bytes proposed here.
First, two desired properties for the binary tree structure and merkleization rule. Then, claims that neither M1, M2, M3, nor M4 satisfy both of these desired properties.
Property: Access list-witness correspondence. For a given state tree, each access list uniquely determines a minimal witness. In particular, minimal witnesses are independent of block execution.
Property: Efficiently computable. The cost to merkleize a tree is less than 50n hashes in practical (i.e. average tree depth<50) cases, where n is the number of leaves to be merkleized.
Claim. Binary radix trees like M1, M2, and M3 don’t satisfy the access list-witness correspondence property.
Proof sketch: Consider an access list from a binary radix state tree. When a leaf in the access list is deleted from state after block execution, if the deleted leaf’s parent node has an extension (“prefix”, “edge label of length >1”) as its remaining child, then the extension is extended to preserve the radix property. Information about whether this remaining child is an extension is needed in a witness. Any leaves can be removed, and the access list does not specify which leaves are removed, so a witness must include this extra extension info for all hash nodes which may be extensions and may be extended due to leaf deletions. This extra data makes witnesses non-minimal. So M1, M2, and M3 don’t satisfy the access list-witness correspondence property.
Claim. Sparse trees like M4 don’t satisfy the efficiently computable property.
Proof sketch: In a sparse tree, a leaf requires 256 hashes to merkleize. And n leaves require ~256n hashes to merkleize. And ~256n>50n. So sparse trees are not efficiently computable.
Are there any proposals for a tree structure and merkleization rule which satisfy both of these desired properties?
I definitely agree that M4 does not have the efficiency property. In order to be efficient and secure, there will have to be some kind of cryptographic encoding of the tree structure within the tree itself.
I don’t quite understand why you are saying that M3, say, does not have the access list determines minimal witness.
In your definition of M3, you say that prefix_length is usually 0x00. This is a bit confusing to me. Are you defining prefix_length of an internal node A to be
The length of the prefix shared by all descendants of A which is not shared by all descendants of A’s parent, or
The length of the largest sequence of bits which is a prefix of all leaf keys that descend from A?
It seems like your definition of M3 uses the former, but I think the latter definition solves this minimal witness issue.
As a diagram, consider the following
A
/ \
\
\
B
/ \
C D
In both versions, when leaf D is deleted, its parent B is deleted and its grandparent A replaces B with C as its (right side) direct child. But in the former version, C’s prefix_length must be updated to what was previously the sum of A’s prefix_length and C’s prefix_length, which requires not just the hash of C but the data of C itself.
In the second version, C still has the same set of leaf descendants, and A has descendants on the left, and descendants of C on the right, so the “largest prefix of all descendants” is the same. Since C is unaffected, we can simply slot its hash in where the hash of B used to be in A.
The word prefix is an abuse of notation. My use of prefix in M3 is consistent with the posts above it which use prefix to describe an extension – so your first definition, I think.
Your definition of prefix_length gives nicer properties for node deletion. But your M3-like rule is bad for proofs-of-exclusion, where it breaks the access list-witness correspondence property. And your M3-like rule always breaks the “two 32-byte chunks -> one 32-byte chunk” property.