首页
下载应用
提交文章
关于我们
🔥 热搜 🔥
1
百度
2
今日热点
3
微信公众平台
4
贴吧
5
opgg
6
dnf私服
7
百度贴吧
8
知乎
9
dnf公益服
10
百度傻逼
分类
社会
娱乐
国际
人权
科技
经济
其它
首页
下载应用
提交文章
关于我们
🔥
热搜
🔥
1
上海
2
习近平
3
新疆
4
鄂州父女瓜
5
乌鲁木齐
6
疫情
7
H工口小学生赛高
8
习明泽
9
芊川一笑图包
10
印尼排华
分类
社会
娱乐
国际
人权
科技
经济
其它
李尚福、魏凤和双双被拿下,与美国一份报告是否有关?
有的人走了,却永远活着
圈内疯传某谣言
不要放过这些人渣
最大“独立日烟花秀”存恐怖威胁 纽约市警全力部署
生成图片,分享到微信朋友圈
2023年1月30日
2023年2月21日
2023年2月22日
2023年2月22日
2023年2月23日
2023年2月23日
2023年2月24日
2023年2月24日
2023年2月25日
2023年2月25日
2023年2月26日
2023年2月26日
2023年2月27日
2023年2月27日
2023年2月28日
查看原文
其他
比特币史话·83 | 压缩(1): 默克尔树
Original
刘教链
刘教链
2023-01-30
收录于合集 #史话
102个
(拉尔夫·默克尔,默克尔树发明者。图片来源于网络)
前情回顾:
比特币史话·78 | 有容乃大(2): 零食售卖机
比特币史话·79 | 有容乃大(3): 现金而非信贷
比特币史话·80 | 有容乃大(4): SWIFT
比特币史话·81 | 有容乃大(5): 1比特币300万美元?
比特币史话·82 | 有容乃大(6): 二层支付网络
正文:
在1980年4月由IEEE计算机协会举办的安全和隐私研讨会的会议论文集中,收录了SHA-256哈希函数所用的“默克尔-丹加德”构造发明者、美国计算机科学家拉尔夫·默克尔(Ralph Merkle, 1952-)的《公钥密码系统的协议》(Protocols for public key cryptosystems)一文[1]。在该论文中,拉尔夫给出了他发明的、后来以他的名字命名的一种称之为“默克尔树”(Merkle tree)的构造方法和用例。
在2008年比特币白皮书中,中本聪在第7篇参考文献的位置引用了拉尔夫的这篇论文。
默克尔树是一种使用密码学哈希函数构造的二叉树。二叉树是一种计算机中常见的数据结构,望文生义,就是从树根到树叶中间的每一层都是二分叉。1分2,2分4,4分8,如此下去。这颗二叉树还是一颗满二叉树,也就是说所有分支都是从根到叶子的完整路径,没有缺失。默克尔树的根是它直接分叉的两个枝干节点拼接起来之后求哈希值,每个枝干节点又是它直接分叉的两个下一级节点拼接后求哈希值,直到叶子节点。叶子节点是对原始数据求哈希值。
在比特币所用的默克尔树中,以上求哈希值的函数使用的是双哈希SHA-256算法。
默克尔树这种结构有一个特点,就是对原始数据的篡改会改变所在路径的默克尔值。这样,我们就可以做到在不需要原始数据的情况下,仅仅使用一条从根到叶子的、由数个哈希值组成的链条,来证明某笔交易的存在性,这种存在性证明又被称之为“默克尔证明”(Merkle proof)。
默克尔树的引入可以让我们在保持区块链不可篡改的同时,允许删除过时的交易,甚至完全删除原始交易数据,而不改变根节点的哈希值。我们只需要把当前区块打包的一笔笔交易的数据作为叶子节点,层层计算,最终算出根节点的哈希值,称为“根哈希”。把“根哈希”和其他的非交易数据,比如当前区块的工作量证明信息,放在一起,组合成为所谓的“区块头”(block header)。
在比特币白皮书的第7节“回收磁盘空间”一节中,中本聪指出,“一旦一枚硬币中的最新交易被埋在足够多的区块底下,已用完的交易就可以丢弃,以节省磁盘空间。为了在不破坏区块哈希值的情况下实现这一点,在默克尔树中对交易进行哈希处理,仅将根包含在区块哈希中。然后,可以通过砍掉树的分支来压缩旧区块。(被砍)分支内的哈希都不需要存储”[2]。
中本聪进一步仔细计算了一下实际数值。一个区块头的大小大约是80字节。按每10分钟生成一个新区块,则一年会产生80字节乘以6乘以24乘以365等于约4.2兆字节(MB)的区块头数据。“按照2008年销售的典型的计算机系统通常有2GB内存,以及摩尔定律预测当前每年将增长1.2GB,即使必须把区块头保存在内存中,存储也不应该有问题”,中本聪如此写道。
【未完待续】(公众号:刘教链)
您可能也对以下帖子感兴趣
{{{title}}}
文章有问题?点此查看未经处理的缓存