区块链merkletree 区块链merkle树生成

本篇文章给大家谈谈区块链merkletree，以及区块链merkle树生成对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

区块链和比特币（一）

区块链（Blockchain）是一种很早就被学界提出但近几年才被比特币带火的一个概念。比特币是基于区块链技术的一种实现，比特币是一种加密货币，或者叫数字货币也可以。我们先以比特币入手谈谈比特币是怎么利用区块链技术的。

假设06年世界杯决赛期间，两个互相不认识的足球迷碰到了，意大利打法国，法国球迷说我们法兰西有齐达内肯定赢你们意大利，意大利球迷不服气说我们意大利是战无不胜的，不信咱俩赌100欧元。现实世界里，怎么办呢？

我之前讲过我们搞计算机的，90%以上的时间都在处理异常情况，如果人类都很讲信用的话，那这个世界可能就不是现在这样了。秦国当年许给楚怀王那600里地就不是6里了，说不定统一中国的就是楚国了呢也说不定。如果把钱交到第三方手里，万一第三方也跑了怎么办？把钱私吞了。所以现实的陌生世界单靠一颗善良的心是靠不住的，必须有手段稳稳地保证这个承诺，法律契约等。如今很通用的做法是第三方要找权威机构，比如政府，银行等，要么找个有头有脸的人或组织，归根结底还是找个有公信力的机构或人。但一般情况下这个第三方肯定会“雁过拔毛”，收取一定比例的手续费。

那么到底还有没有办法来解决这个难题呢？这就是比特币最初设计的一个初衷，解决两个陌生人之间的信任问题。

加密算法 + 多人记账

首先说加密算法，这里又要我之前提过的非对称加密，即公钥私钥。每个人都可以有一对或多对公钥私钥，但一个公钥只能有对应的私钥，反之亦然。其原理就是两个非常大的质数（p和q）相乘得一个数字（n），如果要根据公钥破解私钥的话理论上必须暴力破解，算出这个数字是由哪两个大质数相乘得来的。目前世界上没有公布可以破解1024位以上的私钥，所以采用1024或者2048甚至更长的私钥是非常安全的。

那么有了公钥私钥，我作为个人就可以用私钥加密，然后发布公钥，任何人都可以用我的公钥解密来确定这就是我本人发布的东西。同理别人给我的转账我也可以用他的公钥解密，从而判断这个就是某人的身份，这也叫数字签名。原理都是一样的，都是加密算法，利用数学欧拉公式，质数相乘等原理得到的。这是个非常伟大的算法，叫RSA，由3个数学家提出，我们普通人只要理解到公钥私钥的概念和用处就好了。

之前传统模式里，银行或者政府机构都有自己单独的账本，比如张三转给了李四100块，那账本里怎么记？张三的账户里扣除100， 李四的账户里增加100，对吧？

多人账本也是一样的道理，只不过从之前的中心化机构变成了分布式，去中心化的多个机构甚至个人。好比李白给杜甫转了100两银子，以前是财政部记账，区块链里则是唐太宗，杨玉环，张小静，贺知章等多个人一起记账，记到李太白转给了杜子美100两银子，以此为证，后面附有李白的印章。这样一来，有了多个账本，想要篡改那就难于登天了，李白可以放心的转给杜甫并且不担心他会篡改金额或者抵赖。

这样做就可以解决开始提到的球迷打赌的问题，但还有个问题，别人为什么要帮我们记账？

答案是有报酬，这符合人性，不然谁肯帮忙记一笔跟自己没关系的账呢？

但最终记账的人有且只有一个，不然就要乱套了。

有好处的前提下，如何保证哪一个人来记账呢？这里要涉及到一个数学知识，每个要记账的人，其实也就是所谓的矿工他在记账钱必须要解一个数学问题，这个数学问题没有取巧的办法，只能通过把数字带入公式里硬算，算法就是一个Hash（哈希）算法，类似于算一串数字出来，矿工只可以猜，除此之外别无他法。而且目前比特币里这个猜到的概率是万亿分之一，大概一台普通计算机要持续不断的猜一年才可以猜出来这个数字。

但世界上有成千上万台计算机，它们如果一起算的话速度会快很多，因为从概率上讲肯定会有一个计算机算出来，现实情况也确实如此。看个比特币真实的例子。

除此之外，还可以看到Miner（挖矿人）是谁， 这个块里包含了多少比交易（Number of Transactions）。

如果这个矿工是个别有用心的人，他在算出来后，私自篡改转账记录和金额怎么办？

A. 篡改交易记录 / 金额

前面我们介绍了公私钥加密技术，矿工本身理论上是没有发款人或收款人的私钥的，所以他篡改过的交易记录在用正确的公钥解密的时候会出错，最终被认定为非法（这里作者本人不太确定是在什么时间点做的鉴定，但确定这个记录是可以被证伪的）。

B. 删除交易记录

假设一个场景，张三要在北京4环买一个两室一厅的房子，但张三不想出这钱还想白占房子，想到了一种偷鸡摸狗的办法就是篡改交易记录。理论上，在张三付款后，这个记录产生但并未确认，记录需要等到一个解出谜题的矿工来做，假设这个矿工是他自己人，他让矿工把这条记录抹掉，没有问题。但做法有几种：

众所周知比特币挖矿需要很长一段时间，因为要做提到很麻烦的数学题，现在这个周期大概是10分钟所有，这是基于全世界几十万矿机同时满负荷工作的前提下。也就是说每十分钟有上万笔交易会被统一确认并放到一个不可改变的区块里，并且这几十万台矿机同时更新自己本地的记录。

2.1 如果这笔交易刚生成，房东看到了，然后下一秒就把产权过户给张三，那么张三如果想篡改这个付款记录他必须满足几个条件：

成功的难度取决于在篡改的记录之后有多少块被确认过的区块。如果只有一个，那么太简单了，因为区块链算法默认矿工在发布新的区块时，采用第一个收到且较长的区块。所以这次修改后就一劳永逸，因为所有的账本都会背同步，但也有一个问题，就是这次同步会被记录，如果房东查不到账，张三最终还是会被抓起来的。如果有很多个，比如张三转账完后，房东在确认转账后1小时才做的产权过户，那么张三就必须篡改之前差不多6块左右的区块信息，这个很麻烦，因为每一个区块都会指向上一个区块，并且每个区块都会有一个摘要（Hash），这是当前区块所有交易记录的汇总。所以如果试图修改一个很久前的区块，那么后面的区块的摘要都会变掉，这就是哈希树（MerkleTree）。其他节点是可以报告区块链被篡改的信息的。这就要涉及到最重要的一点，经常有人提到的51%算力，就是说如果张三拥有了超过50%的账本都承认这次修改，那么其他节点按照算法设计也会承认这次修改。不过，先不谈世界上基本没人可以同时做到以上两点，就算做到了，如果有人对此有疑问，依然可以把系统强制修复，之前以太坊就出过类似的问题，结局是以太坊篡改了整个区块，追回了被盗取的财产。 以太坊分叉事件 。

以上只是粗浅的介绍了应用区块链技术实现的比特币的特征，它可以很好的实现公开，公正，中立和平等。世界上任意两个陌生人可以依赖比特币或者其他区块链技术实现互相信任。

梅克尔树-Merkle Trees

梅克尔树是一种二叉树，能快速检查和归纳大量数据，可用于验证区块中交易记录区块链merkletree的完整性。

梅克尔树是区块链的重要数据结构， 其作用是快速归纳和校验区块数据的存在性和完整性。一般意义上来讲，它是哈希大量聚集数据“块”的一种方式，它依赖于将这些数据“块”分裂成较小单位的数据块，每一个 bucket 块仅包含几个数据“块”，然后取每个 bucket 单位数据块再次进行哈希，重复同样的过程，直至剩余的哈希总数仅变为1。

在这颗数中，每个交易都可以单独删除，只需要保存好这笔交易的哈希值即可。这样一来，就可以极大的减小了每个区块的内存，可以存放更多的最新交易。所以在 UTXO 模型中，使用默克尔树结构，就无需担心数据的增长过大的问题了。

使用场景：

1、区块头维护交易的梅克尔树；

2、SPV 钱包通信的交易验证，存放该树。

欢迎留言讨论，有错误请指出，谢谢区块链merkletree！

【联系我（QQ：3500229193）或者加入社群，请戳这里！】

什么是梅克尔树(Merkle)

首先，它可不是一棵梅花树，虽然名字有点像，但是此树非彼树。梅克尔树是区块头中的三巨头之一，我们要知道，区块是区块链的基本结构单元，是有包含元数据的 区块头 和包含交易数据的 区块主体 构成。而我们这棵梅花树呢，就是区块头中的一大成员。

可能你们会好奇，区块头是什么，莫非是变异的头部吗？其实很简单，顾名思义，区块头就是一个区块的前部分，相当于人类身体的头部，控制人类躯体的关键部位。区块头由三组元数据组成，一是父区哈希值;二是挖矿难度，Nonce，时间戳;三是梅克尔树根，也就是我们今天的主角，别小瞧这棵树，它能快速归纳校验区块中所有的交易数据，是不是超级优秀~

区块链利用梅克尔树的数据结构存放所有叶子节点的值，并以此为基础生成一个统一的哈希值。梅克尔树的叶子节点存储的是数据信息的哈希值，非叶子的节点存储的是对其下面所有叶子节点的组合进行哈希计算后得出的哈希值。

还有一点需要重视，就像重视我们的高考成绩一样，那就是，区块中任意一个数据的变更都会导致梅克尔树结构发生变化，在交易信息验证对比的过程中，梅克尔树结构能够大大减少数据的计算量，毕竟，我们只需验证梅克尔树结构生成的统一哈希值就可以啦。

一粒沙里看出一个世界，一朵野花里一座天堂，把无限放在你的手掌上，永恒在一刹那里收藏。 用布莱克这句话解释梅克尔树再合适不过了。

比特币之为什么使用Merkle Tree（原创）

A用户向商户B 发起了一笔比特币转账，并且告知B ，这笔交易的Txid和SPV上面的Block 信息，于是B根据Txid和Block信息，同时向多个FullPeer去confirm这笔交易是否真的存在。Merkle Tree就是要解决这个问题！

SPV向一个Full Peer发送 Block信息和 TXID，查询这笔Txid是否存在在这个Txid里面（假设是HK交易），FullPeer根据Block.Hash值，先找到这个Block，然后遍历Block的Transactions数组，可以理解为遍历Transaction.Txid是否一样，如果没有，就直接返回SPV交易不存在，如果有的话，那么就要根据下图的信息，传输HL、HIJ、HMNOP 和 HABCDEFGH的值

所以SPV收到Peer的一串值的时候，就可以根据这些值，计算出在这个Block的MerkleRootNode.data了（也叫RootPath），如果和自己的SPV里面的RootPath一样，那么说明这笔交易在区块链中真实存在

Merkle Tree的优势在于：在传输空间和数据不可篡改上都做到很好

区块链-默克尔树

Merkle 树是一种组织和构造大量数据以使其更易于处理的方法。在加密货币和区块链的情况下区块链merkletree，Merkle 树用于以对资源要求较低的方式构建交易数据。

当在 Merkle 树结构中进行加密货币交易时，它会被散列，然后被赋予一个等效的散列值。每笔交易在 Merkle 树中散列后，产生的散列值与另一个散列值配对，然后再次散列。例如，将散列值“AB”和“AC”组合起来创建“ABC”。

重复这个配对散列值的过程，直到产生最终的散列值。最终的哈希值，即默克尔根，提供了它包含的所有交易的摘要。然后将 Merkle 根摘要插入到块头中。

Merkle 树结构提供了一个区块中交易的易于访问的记录。因此，检查块中的数据是否已更改或篡改非常简单。这是真的，因为对 Merkle 树中的交易（或任何其区块链merkletree他相关数据）的任何更改都会导致完全不同的对应 Merkle 根。

如果加密货币不使用 Merkle 树，则每个验证请求都将涉及通过网络发送的大量信息。在 Merkle 树中构建交易数据是一种更有效的资源利用。验证交易不需要账本的完整副本，因为可以在 Merkle 根中验证散列的交易数据，需要在节点间发送的信息少得多，因此分析整体数据完整性的计算能力也更少。

换句话说，Merkle 树结构使用户能够验证单个交易是否已包含在一个区块中，而无需经过下载整个区块链的过程。该技术是加密货币组织交易数据并像它们一样高效运行的重要工具。如果没有默克尔树，对资源的更大需求很可能会导致参与网络的节点更少。

认识MMR(Merkle Mountain Range)

merkle tree一种二叉树也是区块链中一种常见的数据结构，其特性就是树的根及中间节点主要是由其左右子树的Hash构成。Parent = H(0,1)，其以密码学保证其安全性，以相同顺序插入才能计算出最终一致的树根。

而mmr(Merkle Mountain Range)是Peter Todd提出的一种Merkle tree，长相类似一组连续的山峰组成，其被设计为节点插入后就不能被修改，支持动态插入。

对于普通Merkle树对于每个新加入节点都需要重新计算merkle root,如果节点数量很大的话这个计算量会非常巨大，而mmr支持动态加入新节点并计算root。

由上图可以发现，以存储索引位置作为其坐标的二叉树，都有左子树与父节点的距离(offset)为 offset=2^Height ,兄弟节点之间的距离为 offset=2^Height - 1 ,这样就可以计算出任意节点的兄弟节点与父节点的坐标。

另外如果我们能够计算出任意节点的高度，我们就能计算出任意节点的父节点及兄弟节点的坐标了，将节点坐标从 1 开始并以 二进制 来表示。如图：

现在我们可以顺序追加节点了，我们只需要判断下一个节点的高度，如果大于当前高度则需要合并左右子树，方法如下:

由图2可以知道，MMR可能会有多个 山峰 ，而MMR的root是由最右侧的山峰依次向左合并，直到最后形成root,这个操作也被称为山峰的 拱起 操作。图2中的 root=Hash(Hash(18,17),14) 。

MMR的root是由山峰的 拱起 得到,那么最左侧的山峰一定一个完全的二叉树,节点数量为 2^Height - 1 ，由此我们可以在固定节点数量下(Count)不断尝试左侧山峰的高度,找到 2^Height - 1 Count 的最大的树，如下:

在计算出左侧山峰后，可以以此为坐标，依次计算出右侧的所有山峰，如下:

获取到所有山峰后，就可以对所有山峰，由左到右依次 拱起 ，最后得到MMR的root。如下:

构造叶子节点的 merkle proof，分三个步骤：

如下:

proof的验证，以相同的顺序重新计算Merkle Root就可以，如下:

MMR可以极大的减少merkle证明的数据量，可以大幅度的减轻存储和网络的负担，提升验证效率，目前Open timestamp 和 Grin 等项目及Fly client的论文中都使用了MMR的证明。

区块链merkletree的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于区块链merkle树生成、区块链merkletree的信息别忘了在本站进行查找喔。