搜索区块链中的项目

Question

甲blockchain是包括散列以先前块的链.每个块由单个哈希树(或Merkle树)组成.我正在讨论的是区块链的整体结构.

由于区块链的值在哈希树内部,在块链内查找值的最佳方法是什么？我想通过遍历整个区块链来搜索树以寻找您想要找到的值是不可行的.我是否缺少搜索区块链中块内部值的搜索方法？

Answer 1

如果您拥有的是每个块中具有Merkle树的区块链,则根据定义,此数据结构不提供任何有效搜索任何内容的方法:

• Merkle树的叶子中的所有哈希本质上都是伪随机的,并且不包含关于内容的有用信息
• 在merkle树的节点中的所有散列是通过伪随机比特序列的级联的散列形成的伪随机比特序列(加密强伪随机无意义的平方,log N时间)
• 指向前一个块的哈希除了找到前一个块(伪随机 - 无意义的权力M,其中M是块的数量)之外什么也没有用.
• 对于块本身的哈希也是如此

总而言之:不,块和Merkle树的哈希对搜索信息基本上没用.它不仅"效率低下",而且是设计中区块链中包含的数据最无用的"索引"(因为一旦数据中的一个位翻转,哈希就会完全改变).如果你想在这样的数据结构中找到任何东西,除了在线性时间内遍历它之外,你绝对无能为力.所有这些哈希所做的就是确保区块链不被篡改,而不是其他任何东西.

但是,每当您想要在其中查找某些信息时,没有人强迫您遍历整个区块链.相反,你可以

• 遍历整个区块链一次
• 构建您需要的任何其他数据结构,以便在区块链中找到所需内容(索引,搜索树,图形,指纹,以及您可以根据区块链中的数据构建的任何内容)

然后根据你的每一个要求

• 使用预先计算的数据结构来有效地执行查询

每次附加一个新块

• 更新所有预先计算的数据结构.

或者:偶尔重建数据结构,分别处理最后几个块.

它与"互联网"非常相似.它是一个包含内容的节点网络.你如何在这些节点中找到任何东西？每次想要查找任何内容时,您是否遍历所有节点？不,你问一个搜索引擎.因为搜索引擎已经在后台完成了工作,并访问了网络中的某些节点,并对内容编制了索引,因此您可以轻松地在其中查找内容.同样的事情,除了你的图形是线性的(如果你忘记了孤儿分支),以及之前添加到图形中的节点不会经常变化(从来没有,除非有人不成比例地强大攻击你的区块链).当您更新数据结构时,以前添加的节点的不变性当然应该用于提高效率:如果您已经看过这些节点,则无需每次都重新扫描它们(与互联网中的内容不同)索引节点节点可以改变).

另一个(显而易见的)替代方案,如果你可以影响区块链的设计:考虑提前可能有用的东西,从一开始就将所需的数据结构烘焙到区块链中,这样不仅区块链本身,而且无法轻松修改有助于导航区块链的数据结构.