Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文
梅克尔树(Merkle trees)是区块链的基本组成部分。虽说从理论上来讲,没有梅克尔树的区块链当然也是可能的,你只需创建直接包含每一笔交易的巨大区块头(block header)就可以实现,但这样做无疑会带来可扩展性方面的挑战,从长远发展来看,可能最后将只有那些最强大的计算机,才可以运行这些无需受信的区块链。 正是因为有了梅克尔树,以太坊节点才可以建立运行在所有的计算机、笔记本、智能手机,甚至是那些由Slock.it生产的物联网设备之上。那么,究竟梅克尔树是如何工作的呢,它们又能够提供些什么价值呢,现在以及未来的?
& f/ L6 t6 s1 [* k, Y" M1 n  g, ]7 p4 h9 S, Z) [
首先,咱们先来讲点基础知识。梅克尔树,一般意义上来讲,它是哈希大量聚集数据“块”(chunk)的一种方式,它依赖于将这些数据“块”分裂成较小单位(bucket)的数据块,每一个bucket块仅包含几个数据“块”,然后取每个bucket单位数据块再次进行哈希,重复同样的过程,直至剩余的哈希总数仅变为1:即根哈希(root hash)。+ N. _" q1 l, |1 t6 @
3 i3 K: t7 l/ Q" B; u% j/ ?
梅克尔树最为常见和最简单的形式,是二进制梅克尔树( binary Mekle tree),其中一bucket单位的数据块总是包含了两个相邻的块或哈希,它的描述如下:
, W! j1 P2 u% w* ^: b( _8 \9 H3 o: U/ v
那么,这种奇怪的哈希算法有什么好处么?为什么不直接将这些数据块串接成一个单独的大块,用常规的哈希算法进行呢?答案在于,它允许了一个整齐的机制,我们称之为梅克尔证明(Merkle proofs):$ X1 Q: j& r- d3 R

6 Z, \  @0 Z1 N# |, i% w" d* J一个梅克尔证明包含了一个数据块,这颗梅克尔树的根哈希,以及包含了所有沿数据块到根路径哈希的“分支”。有人认为,这种证明可以验证哈希的过程,至少是对分支而言。应用也很简单:假设有一个大数据库,而该数据库的全部内容都存储在梅克尔树中,并且这颗梅克尔树的根是公开并且可信的(例如,它是由足够多个受信方进行数字签名过的,或者它有很多的工作量证明)。那么,假如一位用户想在数据库中进行一次键值查找(比如:“请告诉我,位置在85273的对象”),那他就可以询问梅克尔证明,并接受到一个正确的验证证明,他收到的值,实际上是数据库在85273位置的特定根。它允许了一种机制,既可以验证少量的数据,例如一个哈希,也可以验证大型的数据库(可能扩至无限)。
! Q0 @$ F; ~- t+ V+ Q$ c, j2 `* n7 u, B) f1 R
比特币系统的梅克尔证明, S7 M3 x% S& J4 N! F

4 v; m. h$ P6 V# \, Q4 t) T/ ?' g; x梅克尔证据的原始应用是比特币系统(Bitcoin),它是由中本聪(Satoshi Nakamoto)在2009年描述并且创造的。比特币区块链使用了梅克尔证明,为的是将交易存储在每一个区块中:" `% s# I2 P, P$ b1 l. l
" `( b" U# p; g9 Q
而这样做的好处,也就是中本聪描述到的“简化支付验证”(SPV)的概念:而不是下载每一笔交易以及每一个区块,一个“轻客户端”(light client)可以仅下载链的区块头,每个区块中仅包含五项内容,数据块大小为80字节:! S- y* w& i6 u# r! K

) D9 o( h; _: T上一区块头的哈希值
$ x) R: m+ V( _! U# p! t
0 h% u6 Y% f7 W) t, I& o时间戳
( y3 N$ W# o; J3 R- D4 i7 G. T; ]
挖矿难度值
) j, r, R9 O$ U) b0 A" _7 O) @0 ?, n+ R6 j3 ^* B4 F
工作量证明随机数(nonce)" o! S5 l, p) J* c! M% f8 j0 P* M
" H) z% c  K8 Q- \2 X3 D! w# ~
包含该区块交易的梅克尔树的根哈希  A: z) b' j5 N. a. D

! g. h* ~! L' K' B如果一个轻客户端希望确定一笔交易的状态,它可以简单地要求一个梅克尔证明,显示出一个在梅克尔树特定的交易,其根是在主链(main chain,非分叉链)上的区块头。
4 o3 P4 B% q/ R; `
# H- f0 [' {" u8 K: M9 f它会让我们走得很远,但比特币的轻客户确实有其局限性。一个特别的限制是,它们虽然可以证明包含的交易,但无法证明任何当前的状态(例如:数字资产的持有,名称注册,金融合约的状态等)。你现在拥有了多少个比特币?一个比特币轻客户端,可以使用一种协议,它涉及查询多个节点,并相信其中至少会有一个节点会通知你,关于你的地址中任何特定的交易支出,而这可以让你实现更多的应用。但对于其他更为复杂的应用而言,这些远远是不够的。一笔交易影响的确切性质(precise nature),可以取决于此前的几笔交易,而这些交易本身则依赖于更为前面的交易,所以最终你可以验证整个链上的每一笔交易。为了解决这个问题,以太坊的梅克尔树的概念,会更进一步。& Z$ c8 E# ~% O# l2 E- @
7 z4 ?* s8 z1 f% e7 a5 J
以太坊的梅克尔证明
1 Q4 y  V. \1 G! F8 ]( C, M' }+ M3 M; E! k3 [, C# f2 H
以太坊的每一个区块头,并非只包含一颗梅克尔树,而是包含了三颗梅克尔树,分别对应了三种对象:
5 e; E2 J' v9 k+ g% i9 O6 v
5 P1 `# V2 {+ Z# Q0 C) h* z2 I交易(Transactions)
: Q: @3 S! S5 M% u& x% C* A
7 F) o% p& c$ E' ]9 l* V+ I4 c( u收据(Receipts,基本上,它是展示每一笔交易影响的数据条)& B+ n" Z, b/ K

0 p  k& J, M) r4 |( J* x状态(State)
5 m7 ^/ c" U; V4 [
* N9 i2 |; v- n0 l! l" Z这使得一个非常先进的轻客户端协议成为了可能,它允许轻客户端轻松地进行并核实以下类型的查询答案:0 `# w* G) Z( k, U6 L; i

0 y0 g/ j0 |' H这笔交易被包含在特定的区块中了么?
, }' U+ ^- J: G1 p1 w* c4 ^, e; ]3 f; Z0 y2 {
告诉我这个地址在过去30天中,发出X类型事件的所有实例(例如,一个众筹合约完成了它的目标)
/ p" d$ R0 f7 Y% e: x( D& `' h. s; g3 k, [+ |1 ]4 v
目前我的账户余额是多少?
! c2 y+ h, {# [/ l
! Q- ^2 O8 O5 J, }4 i这个账户是否存在?
5 ~( H2 t: f( L- _# [" [6 _. [. a. C: _4 [7 i
假装在这个合约中运行这笔交易,它的输出会是什么?, O+ [( v( f- G) i

) f& y, d0 @5 H  u; q; n2 C% t( v第一种是由交易树(transaction tree)来处理的;第三和第四种则是由状态树(state tree)负责处理,第二种则由收据树(receipt tree)处理。计算前四个查询任务是相当简单的。服务器简单地找到对象,获取梅克尔分支,并通过分支来回复轻客户端。
4 u* I6 K8 h$ y  ^2 ?& T3 Q; q! O8 ~
第五种查询任务同样也是由状态树处理,但它的计算方式会比较复杂。这里,我们需要构建下我们称之为梅克尔状态转变的证明(Merkle state transition proof)。从本质上来讲,这样的证明也就是在说“如果你在根S的状态树上运行交易T,其结果状态树将是根为S’,log为L,输出为O” (“输出”作为存在于以太坊的一种概念,因为每一笔交易都是一个函数调用,它在理论上并不是必要的)。/ L+ a* B  }. a1 R, Z
8 ~: c9 U2 v/ O2 V3 y  U; T  X
为了推断这个证明,服务器在本地创建了一个假的区块,将状态设为 S,并假装是一个轻客户端,同时请求这笔交易。也就是说,如果请求这笔交易的过程,需要客户端确定一个账户的余额,这个轻客户端会发出一个余额疑问。如果这个轻客户端需要检查存储在一个特定合约的特定项目,该轻客户端会对此发出针对查询。服务器会正确地“回应”它所有的查询,但服务器也会跟踪它所有发回的数据。然后,服务器会把综合数据发送给客户端。客户端会进行相同的步骤,但会使用它的数据库所提供的证明。如果它的结果和服务器要求的是相同的,那客户端就接受证明。
) J0 e* _' B3 B" A3 j: q$ u3 S$ S9 _' L0 |* z
帕特里夏树(Patricia Trees)
5 W* N3 e+ i8 s
& H( M: l: U( R% f前面我们提到,最为简单的一种梅克尔树是二进制梅克尔树。然而,以太坊所使用的梅克尔树则更为复杂,我们称之为“梅克尔.帕特里夏树”(Merkle Patricia tree),这在我们的文档中有提到过。本文不会详细说明它的概念。如果你想了解的话,可以在这篇和这篇文章中找到答案,本文中,我仅仅会讨论下基本的论证。
* K" ?- X) j0 U% g. I6 [9 ?/ U& g) A$ z1 ]2 }9 W- \
二进制梅克尔树对于验证“清单”格式的信息而言,它是非常好的数据结构,本质上来讲,它就是一系列前后相连的数据块。而对于交易树来说,它们也同样是不错的,因为一旦树已经建立,花多少时间来编辑这颗树并不重要,树一旦建立了,它就会永远存在。
. S; g' p4 T/ D; E* P
- Q; L- d3 m2 e* n而对状态树来说,情况会更复杂些。以太坊中的状态树基本上包含了一个键值映射,其中的键是地址还有各种值,包括账户的声明、余额、随机数、代码以及每一个账户的存储(其中存储本身就是一颗树)。例如,摩登测试网络(the Morden testnet )的创始状态如下所示:/ t2 j3 t2 d) E5 v' I9 y

+ g* N- H2 {  D! y1 N4 M4 S" f{"0000000000000000000000000000000000000001":{"balance":"1"},"0000000000000000000000000000000000000002":{"balance":"1"},"0000000000000000000000000000000000000003":{"balance":"1"},"0000000000000000000000000000000000000004":{"balance":"1"},"102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c":{"balance":"1606938044258990275541962092341162602522202993782792835301376"}}) p- m) k1 g9 v  I3 ?& Y

- U" R) J/ F7 r$ {+ G. u然而,不同于交易历史记录,状态树需要经常地进行更新:账户余额和账户的随机数nonce经常会更变,更重要的是,新的账户会频繁地插入,存储的键( key)也会经常被插入以及删除。而这样的数据结构设计,我们可以在一次插入、更新编辑或者删除操作之后,快速地计算出新的树根(tree root),而无需重新计算整颗树。此外,它还有两个灰常好的次要特性:" M2 v& ]) D6 [- O
0 F1 A2 N8 b. X' ^
树的深度是有限制的,即使考虑攻击者会故意地制造一些交易,使得这颗树尽可能地深。不然,攻击者可以通过操纵树的深度,执行拒绝服务攻击(DOS attack),使得更新变得极其缓慢。
" S5 e7 K1 |  P
  N' C' M9 J- T& r( \: ~* j树的根只取决于数据,和其中的更新顺序无关。换个顺序进行更新,甚至重新从头计算树,并不会改变根。8 C7 h, S- x+ E; H& i& _+ j4 |

% Z, r7 k: W/ ?8 |  ~2 M3 i而帕特里夏树,简单地说,或许最接近的解释是,我们可以同时实现所有的这些特性。其工作原理,最为简单的解释是,一个以编码形式存储到记录树的“路径”的值。每个节点会有16个子(children),所以路径是由十六进制编码来确定的:例如,狗(dog)的键的编码为 6 4 6 15 6 7,所以你会从这个根开始,下降到第六个子,然后到第四个,并依次类推,直到你达到终点。在实践中,当树稀少时也会有一些额外的优化,我们会使过程更为有效,但这是基本的原则。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

万象争辉1 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    27