As we all know, the more address there are, the more bytes the MPT tree (Merkle Patricia Tree) saves and there may be 35 million active address in Ethereum.
If we put all 35 million active address into one MPT tree, how many bytes is the MPT?
Recently, I am working on my graduation thesis, can you give me more details, thanks a lot.
If you only need verification and are not restricted to a MPT in your thesis, just use a merkle tree to store the addresses. Depending on how you handle uneven leaf counts, the size will differ. If you duplicate the last entry (like Bitcoin does), the size will at maximum be digest_size * ceil(address_count/2) * 4 - 1. In any case, the estimation of the size will be way easier than in a MTP
I won't give you an exact formula, but some food for thoughts which might help you during your exploration of the solution.
The Modified Merkle Patricia Trie stores key-value mappings. Since values generally can vary in length, no exact analysis of space consumption is possible. In your scenario the values consist of addresses, which luckily have a fixed length of 20 Bytes. Let's assume that the key is the value, in that case key and value both have a fixed size of 20 Bytes.
What has to be taken into consideration is that the implementation has effect on the storage size. For example, how does a branch node handle empty nibbles? Does it set the reference to 32 Bytes (digest size) times 0 Bytes? Does it encode in 16 bit which nibbles reference another node hash? Another technical limitation might be that data is stored as Bytes and therefore 1-2 nibbles encoding are required to determine whether the part of the path specified in a node is even or uneven, such as in the MTP document I referenced. For the sake of simplicity, let's just examine the storage requirements for they keys, the hashes of nodes that are really used within the tree to reference a node and the values.
The key has to be stored at least one time completely in the trie. The MTP offers extension nodes, which store a part of a key where no branches are required. One important aspect of your analysis will be how many paths of the keys can be combined in one extension node and at which point the extensions happen. Example (using the notation from the MTP example):
Example 1
------------------------------
data 1: (10 00, value0)
data 2: (10 11, value1)
data 3: (10 22, value2)
-------------------------------
rootHash: <10, hashA>
hashA: <hashB, hashC, hashD>
hashB: <0, value0>
hashC: <1, value1>
hashD: <2, value2>
As you can see, instead of storing 12 nibbles because all the keys have been stored, only 5 nibbles have been stored, 3 additional implicitly in the branch node referenced by hashA. Generally it can be said that the later the keys begin to branch, the more nibbles you can save. For example, if you have three keys
Example 2
-----------------
01 23 45 67 89 0A
01 23 45 67 89 0B
01 23 45 67 89 0C
the MTP tree will store the first 11 nibbles 01 23 45 67 89 0 in an extension node once and only 3 nibbles A, B and C (implicitly) in a following branch node, ending with additional three leaf nodes containing the values. This leads to 15 nibbles stored in total. But when the keys look like
Example 3
-----------------
A1 23 45 67 89 0F
B1 23 45 67 89 0F
C1 23 45 67 89 0F
The MTP tree will store the first three nibbles A, B and C (implicitly) in a branch node and then redundantly store the remaining 11 nibbles in respectively three extension nodes (including the final values).
If we compare Example 2 and 3 now, we observe the following:
Example 2 stored 20 nibbles in total, 3 implicitly. It requires 1 extension node, 1 branch node and 3 leaf nodes. This is in total about 2 + 6 * digest_size Bytes (6 instead of 5 because we have to create the rootHash). Let's say we use digest_size=6 in this example, that leads to 2 + 6 * 6 = 38 Bytes. We also have to take the values into consideration, too keep it simple I'll leave that out here.
Example 3 stored 36 nibbles in total, 3 implicitly. It requires 1 branch node and 3 extension nodes. This requires 4 + 5 * 6 = 34 Bytes.
Another observation is that since your keys have all the same length, every key will have their value stored in one leaf or extension node. So in total you will have to store number_of_keys * node_hash_size Bytes for the nodes containing the values.
Now I leave you with the most difficult part. Find a way to determine the most expensive situation in a MPT. How do you have to balance branch and extension nodes for a given set of keys such that the maximum storage requirement is achieved? You can create some examples as I did and observe the outcome, hopefully seeing a correlation between key sets, node allocation and final space consumption.
A suggestion, it might simplify the calculation massively if you just omit the space consumption for the keys. You can just assume a number for example at maximum number_of_keys * key_size. This is totally acceptable for an upper bound examination. Another way would be to programmatically generate random sets of keys and get the average key storage requirement (percent). This way you can only focus on the space requirements for the nodes (and of course the addresses, which is given you for free).
One last note, a gut feeling I got after playing around with some arrangements. It seems that the most nodes are required when most branching nodes are required. In the following solution I assume that all 35 million keys branch off in the very beginning. This leads to all branch nodes appearing after the root of the trie followed by many extension nodes (for each key one). I estimate the upper bound to be around:
digest_size
+ (number_of_keys - 1) * digest_size
+ digest_size * number_of_keys
+ ceil(2 * digest_size - log16(number_of_keys)) * number_of_keys / 2
+ number_of_keys * address_size`.
digest_size is the storage requirement for the rootHash(number_of_keys - 1) * digest_size is the maximum storage requirement for branch nodesnumber_of_keys * digest_size is the number of leaf nodes or extension nodes that carry the final valueceil(2 * digest_size - log16(number_of_keys)) * number_of_keys / 2 is the maximum storage requirement for the keys, discarding implicitly stored nibbles in the branch nodesnumber_of_keys * address_size if the storage requirement for the values (addresses)If that gut feeling is true, the maximum storage requirement for the tree (uncompressed, 32 Byte digest size, 20 Byte address size) should be about 3955 MB
