Merkle Tree & Merkle Signature Scheme
概念
Merkle Tree 又称 Hash Tree,实现一般为二叉树,当然也可以用多叉树实现,本质是一样的,WiKi 上也有相关介绍,点击这里传送。
树的叶子节点处存放数据的哈希值,其他的非叶子节点通过子节点进行构造,按照下方公式:
nodei=hash(node2i+1||node2i+2)nodei=hash(node2i+1||node2i+2)
其中,节点 ii 是节点 2i+12i+1 和 2i+22i+2 的父结点,|||| 表示串接,或者简单的说拼接,比如 a=00012,b=11002a=00012,b=11002 则
c=a||b=000111002c=a||b=000111002