哈希指针-抗篡改的数据结构

目录

哈希指针

哈希指针-验证

抗篡改版本的数据结构

抗篡改的链表-基础区块链

如何体现抗篡改特性

抗篡改的二叉树-默克尔树

默克尔树存储数据的例子

使用哈希指针替换指针

哈希指针-抗篡改的数据结构 哈希指针

哈希指针与java中的对象引用或c中的指针具有相同的作用

也有指向存储对象的位置和数据的作用

除此作用之外 哈希指针还存储了一些额外的数据

即它所指向的数据的哈希值 或 该对象或数据的其他表现形式

哈希将数据映射为一个固定大小的哈希值

通过在指针上添加哈希值 我们可以验证数据有没有被修改

哈希指针-验证

哈希指针存储了它所指向的数据的哈希值

如果它所指向的数据发生了修改 它存储的哈希值与所指向数据当前的哈希值不同

则可判断 这个数据发生了修改

H()存储了字符串"THIS CLASS IS GREAT"的地址 以及 此字符串的哈希值"ecfbb…"

当从H()访问字符串时 可以通过 字符串的哈希值 与 哈希值真存储的哈希值 是否相等

判断这个字符串的值是否发生过修改

如果字符串被修改 字符串的哈希值将不再匹配哈希指针存储的哈希值

则可以得知 数据被修改过了

抗篡改版本的数据结构

利用哈希指针可以校验数据是否发生过修改的特性

通过将我们常用的数据结构中使用的指针替换为哈希指针

就可以得到这些数据结构的抗篡改版本

抗篡改的链表-基础区块链

basic blockchain

通过将链表这一数据结构中使用的指针替换为哈希指针

我们就可以得到一个抗篡改的链表数据结构

也就是一个基础的区块链

如何体现抗篡改特性

哈希指针存储的是他所指向的之前的所有数据的哈希值

data1节点的H()存储的是null的哈希值

data2节点的H()存储的是data1节点(包括data1节点的数据 data1 以及 data1节点的哈希指针 H())的哈希值

任何节点的数据发生修改 最终都会将哈希值修改传播到Head:H()

所以我们只需要检查头部的指针哈希值是否等于预期值即可知道数据是否被篡改

抗篡改的二叉树-默克尔树

Merkle tree

将一个二叉树使用的指针替换为哈希指针

且只在叶子节点上存储数据

就可以得到一颗默克尔树

与普通的二叉树相同 每个节点可以有两个子节点

默克尔树存储数据的例子

叶子节点的哈希值为其所存储的数据的哈希值

非叶子节点的有两个哈希指针分别指向其左右子节点

非叶子节点的哈希值为 其左右子节点的哈希值串联后再哈希取得的值

以此步骤组织一颗默克尔树后 创建一个哈希指针指向此默克尔树的头节点

因为默克尔树在结构上与二叉搜索树相同

所以在查找一个元素时时间复杂度为O(log n)

在验证一个数据是否被存储在区块中时 速度相较传统的区块链更快

且与区块链相同的 任何数据的修改都会体现在默克尔树根节点的哈希值上(root hash)

可以快捷的判断是否有数据发生了修改

使用哈希指针替换指针

上面两个例子使用哈希指针替换了传统的指针得到了具有抗篡改特性的数据结构

替换传统链表的指针为哈希指针 得到了区块链

替换传统二叉树的指针为哈希指针 得到了默克尔树

但并不是所有数据结构都可以使用哈希指针:

在没有任何显式指针的数据结构中 不能使用哈希指针

比如 数组数据结构 数组结构没有使用指针 数据为从起始点按偏移量存储 无法使用哈希指针对其提供保护

有循环结构的数据结构

使用哈希指针提供抗篡改保护要求数据结构必须有一个起始点

比如区块链(链表)的头节点 默克尔树(二叉树)的根节点

如果数据结构中存在循环 则没有起点 比如一个环形链表 或者一个无向图

也就没有位置可以存放初始哈希(比如默克尔树的rootHash)

所以哈希指针也就不起作用

---

此文为个人学习笔记

原始内容来自b站转载视频

原视频系列标题:

原视频链接:

https://www.bilibili.com/video/BV1Xa411P7rR?spm_id_from=333.999.0.0&vd_source=e974e5b422b5e93d638b7ac74272a918

感谢原内容作者

转载视频翻译多数为机翻 此文可能某些地方词不达意或翻译错误 若有错误还请指正 感谢