如果我们将3500万活动地址全部放入一个MPT树()，那么MPT是多少字节？

Question

我们都知道，地址越多，MPT树()保存的字节就越多，而Ethereum中可能有3500万个活动地址。

如果我们将3500万个活动地址都放在一个MPT树中，那么MPT是多少字节？

最近，我正在写毕业论文，你能告诉我更多的细节吗，非常感谢。

Answer 1

初始考虑事项

如果您只需要验证，并且不限于您的论文中的MPT，只需使用merkle树来存储地址。根据您如何处理不均匀的叶数，大小将有所不同。如果您复制最后一个条目(就像比特币一样)，大小将最大为digest_size * ceil(address_count/2) * 4 - 1。在任何情况下，估计大小都比在MTP中容易得多。

我不会给你一个确切的公式，但一些食物的想法，可能会帮助你在你的解决方案的探索。

改良Merkle Patricia Trie存储键值映射。由于值的长度通常会有所不同，因此无法对空间消耗进行精确分析。在您的场景中，值由地址组成，幸运的是，地址的固定长度为20 Bytes。让我们假设键是值，在这种情况下，键和值都有一个固定的大小为20字节。

需要考虑的是，实现对存储大小有影响。例如，分支节点如何处理空节点？它是否将引用设置为32 Bytes (摘要大小)乘以0 Bytes？它是否在16位中编码，而该位位是对另一个节点哈希的引用？另一个技术限制可能是数据存储为Bytes，因此需要1-2个比特编码来确定节点中指定的路径的部分是均匀的还是不均匀的，例如在我引用的MTP文档中。为了简单起见，让我们只检查它们的存储需求，键，树中真正用于引用节点和值的节点的散列。

空间消耗分析

密钥必须至少一次完全存储在trie中。MTP提供扩展节点，它存储不需要分支的密钥的一部分。您分析的一个重要方面将是在一个扩展节点中可以组合多少个键路径，以及在什么时候扩展会发生。示例(使用来自MTP实例的符号)：

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>

正如您所看到的，由于所有的密钥都已经存储，所以没有存储12小段，而是只存储了5个小块，而是在hashA引用的分支节点中隐式地存储了3个。通常可以说，键开始分支的时间越晚，您可以保存的越多。例如，如果你有三把钥匙

Example 2
-----------------
01 23 45 67 89 0A
01 23 45 67 89 0B
01 23 45 67 89 0C

MTP树将将前11位01 23 45 67 89 0存储在扩展节点中一次，而只有3位A、B和C (隐式)存储在下面的分支节点中，并以包含这些值的其他三个叶节点结束。这导致总共储存了15口。但当钥匙看起来像

Example 3
-----------------
A1 23 45 67 89 0F
B1 23 45 67 89 0F
C1 23 45 67 89 0F

MTP树将将前三个小块A、B和C (隐式)存储在分支节点中，然后冗余地将剩下的11个比特分别存储在三个扩展节点(包括最终值)中。

如果我们现在比较示例2和3，我们会观察到以下情况：

示例2总共存储了20小段，隐式存储了3个。它需要1个扩展节点、1个分支节点和3个叶节点。这是关于2 + 6 * digest_size字节(6而不是5，因为我们必须创建rootHash)。假设我们在本例中使用digest_size=6，这将导致2 + 6 * 6 = 38 Bytes。我们还必须考虑到这些值，也要保持简单--我把它放在这里。

示例3总共存储了36口，隐式存储了3条。它需要一个分支节点和三个扩展节点。这需要4 + 5 * 6 = 34 Bytes。

另一个观察是，由于您的键具有相同的长度，每个键的值都将存储在一个叶或扩展节点中。因此，总的来说，您必须为包含值的节点存储number_of_keys * node_hash_size字节。

结果

现在我给你留下最困难的部分。找到一种方法来确定MPT中最昂贵的情况。如何平衡给定一组密钥的分支节点和扩展节点，从而达到最大存储需求？您可以像我一样创建一些示例并观察结果，希望看到键集、节点分配和最终空间消耗之间的关联。

一个建议是，如果忽略键的空间消耗，它可能会极大地简化计算。您只需假设一个数字，例如，在最大的number_of_keys * key_size。这是完全可以接受的上限考试。另一种方法是以编程方式生成随机密钥集，并获得平均密钥存储需求(百分比)。通过这种方式，您只能关注节点的空间需求(当然还有地址，这是免费提供的)。

最后一个音符，我在玩了一些安排后的直觉。当需要大多数分支节点时，似乎需要最多的节点。在下面的解决方案中，我假设所有3500万个密钥从一开始就断开。这将导致所有分支节点出现在trie的根之后，然后是多个扩展节点(对于每个关键节点)。我估计上界在附近：

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`.

1. digest_size是rootHash的存储需求。
2. (number_of_keys - 1) * digest_size是分支节点的最大存储需求。
3. number_of_keys * digest_size是带有最终值的叶节点或扩展节点的数目。
4. ceil(2 * digest_size - log16(number_of_keys)) * number_of_keys / 2是密钥的最大存储需求，它丢弃了分支节点中隐式存储的比特。
5. 如果值(地址)的存储要求是number_of_keys * address_size的话

如果这种直觉是正确的，那么树的最大存储需求(未压缩，32字节摘要大小，20字节地址大小)应该大约为3955 MB。