一、事件事件是以太坊提供的一种链内链外沟通的一种机制。通过触发事件，智能合约可以通知链外组件某个交易完成了什么事儿。下面是一个ERC20合约里常见的Transfer事件定义，通过event关键字表明这是一个事件定义声明。event Transfer(address indexed from, address indexed to, uint256 value);在transfer方法的实现中，我们会像下面代码里展示的这样通过emit关键字触发事件的发生。function transfer(address _to, uint256 _value) public returns (bool) { ... emit Transfer(msg.sender, _to, _value); return true; }二、日志在以太坊的语境里，日志代表对事件的存储。在下面的交易回执里，我们可以看到logs数据项，这个就是我们这里所说的日志，合约执行时每触发一次事件，在交易收据里的logs数据项数组里就会多一个日志条目出来。>eth.getTransactionReceipt("0xe03fac05ff4dde83fc9267184fd8c08bd78599f950e817dbf7fa4a4d4d319ce2"); { blockHash: "0x7eaf6abe64592d10828e136635aa6be6f4d09da3bb5b9fddf87773ee152d657c", blockNumber: 4654718, contractAddress: null, cumulativeGasUsed: 52464, from: "0x076979a0b3c87334e5d72e3afcafaa80f7888cac", gasUsed: 52464, logs: [{ address: "0x73c2a5b1a32fa8e33101a6ab119203f4417feae4", blockHash: "0x7eaf6abe64592d10828e136635aa6be6f4d09da3bb5b9fddf87773ee152d657c", blockNumber: 4654718, data: "0x0000000000000000000000000000000000000000000000056bc75e2d63100000", logIndex: 0, removed: false, topics: ["0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef", "0x000000000000000000000000076979a0b3c87334e5d72e3afcafaa80f7888cac", "0x000000000000000000000000cd9f286ba6a3d2df7885f4a2be267fc524d32bd3"], transactionHash: "0xe03fac05ff4dde83fc9267184fd8c08bd78599f950e817dbf7fa4a4d4d319ce2", transactionIndex: 0 }], logsBloom: "0x20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080000008000000000400000000000000000000000000000000000000040000000000000000100000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000000000000200000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000040000000000000000400", status: "0x1", to: "0x73c2a5b1a32fa8e33101a6ab119203f4417feae4", transactionHash: "0xe03fac05ff4dde83fc9267184fd8c08bd78599f950e817dbf7fa4a4d4d319ce2", transactionIndex: 0 }在这个日志里，我们可以看到很多和事件触发上下文相关的信息，比如合约地址（address）、所在区块哈希（blockHash）、所在区块号（blockNumber）、所属交易哈希（transactionHash）等等。这里面最核心的就两个数据：topics和data。我们这里看到topics是个数组，这个数组的第一个元素就代表所触发的事件，是个16进制表示256位的数字。只是看这么个字符串，我们并不能确定这是哪个事件，这时候就需要借助于合约的ABI文件。在ABI文件中找出type为event的那些元素，如下面所示：{ "anonymous": false, "inputs": [ { "indexed": true, "name": "owner", "type": "address" }, { "indexed": true, "name": "spender", "type": "address" }, { "indexed": false, "name": "value", "type": "uint256" } ], "name": "Approval", "type": "event" }, { "anonymous": false, "inputs": [ { "indexed": true, "name": "from", "type": "address" }, { "indexed": true, "name": "to", "type": "address" }, { "indexed": false, "name": "value", "type": "uint256" } ], "name": "Transfer", "type": "event" }为了找出topic所对应的事件，我们需要计算每个事件的签名并找到匹配的签名（事件名和输入参数类型的sha3散列）。对于事件Transfer(address indexed from, address indexed to, uint256 value)，签名就是sha3('Transfer(address,address,uint256)')，这些都是可以从ABI中获得。>web3.sha3("Transfer(address,address,uint256)") "0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef" >web3.sha3("Approval(address,address,uint256)") "0x8c5be1e5ebec7d5bd14f71427d1e84f3dd0314c0f7b2291e5b200ac8c7c3b925"很明显可以看出，"Transfer(address,address,uint256)" 这个事件的签名和上面提到过的topics的第一个数据元素是一致的，说明这个日志就是对应的Transfer事件。["0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef", "0x000000000000000000000000076979a0b3c87334e5d72e3afcafaa80f7888cac", "0x000000000000000000000000cd9f286ba6a3d2df7885f4a2be267fc524d32bd3"],现在我们知道了，日志里面topics数组里的第一个数据元素就是事件的签名。那么topics里其它的元素是什么呢？会看上面截取的 ABI，我们可以看到在事件元素的inputs数据项中，有的indexed的值为true，有的为false，我们在声明一个事件时，也可以指定事件的参数是否indexed，比如下面这个Transfer事件的声明，from就是表明为indexed，表明是被索引收录的。event Transfer(address indexed from, address indexed to, uint256 value);topics里的其它数据元素就是被索引收录的事件参数值，所有在topics里的内容，都是被索引收录，可以通过bloom filter进行过滤的。日志里还有一个关键内容就是data，这个比较容易理解，就是触发事件的时候传给事件的实际参数值，值得注意的是这里面只包含未索引的数据项。日志数据项总结：topics值为事件sha3签名和indexed的参数值，data值为没有indexed的参数值三、作用帮助用户客户端（web3js）读取智能合约的返回值：在真实的环境中我们需要发送交易（Transaction）来调用某个智能合约。这时我们将无法获得智能合约的返回值。因为该交易当前只是被发送、打包、执行还有一段时间（需要矿工的工作量证明来实现），此时调用的返回值只是该交易哈希。智能合约异步通知用户客户端（web3js）:在交易打包到区块当中后，智能合约调用的事件记录到收据Log当中，如果一个web3js客户端正在监听将会收到这个事件。用于智能合约的存储（比Storage便宜得多）：相比智能合约账户的Storage，用日志的方式存储一些信息会便宜很多。Storage中大致的价格是每32字节（256位）存储需要消耗20,000气（Gas），而日志大致是每字节8气（Gas）。但是日志存储的信息智能合约没法读取。四、web3js监听事件以太坊提供了基于http和WebSocket的JSON-RPC事件订阅监听，使用web3js客户端可以订阅指定的合约事件。调用：myContract.events.MyEvent([options][, callback])参数：options - Object: 可选，用于部署的选项，包含以下字段：filter - Object : 可选，按索引参数过滤事件。fromBlock - Number: 可选，仅监听该选项指定编号的块中发生的事件topics - Array : 可选，用来手动为事件过滤器设定主题。callback - Function: 可选，该回调函数触发时，其第二给参数为事件对象，第一个参数为错误对象返回值：EventEmitter: 事件发生器，声明有以下事件:"data" 返回 Object: 接收到新的事件时触发，参数为事件对象"changed" 返回 Object: 当事件从区块链上移除时触发，该事件对象将被添加额外的属性"removed: true""error" 返回 Object: 当发生错误时触发返回的事件对象结构如下：event - String: 事件名称signature - String|Null: 事件签名，如果是匿名事件，则为nulladdress - String: 事件源地址returnValues - Object: 事件返回值，例如 {myVar: 1, myVar2: '0x234...'}.logIndex - Number: 事件在块中的索引位置transactionIndex - Number: 事件在交易中的索引位置transactionHash 32 Bytes - String: 事件所在交易的哈希值blockHash 32 Bytes - String: 事件所在块的哈希值，pending的块该值为 nullblockNumber - Number: 事件所在块的编号，pending的块该值为nullraw.data - String: 该字段包含未索引的日志参数raw.topics - Array: 最多可保存4个32字节长的主题字符串数组。主题1-3 包含事件的索引参数示例代码：myContract.events.MyEvent({ filter: {myIndexedParam: [20,23], myOtherIndexedParam: '0x123456789...'}, // Using an array means OR: e.g. 20 or 23 fromBlock: 0 }, function(error, event){ console.log(event); }) .on('data', function(event){ console.log(event); // same results as the optional callback above }) .on('changed', function(event){ // remove event from local database }) .on('error', console.error); // event output example > { returnValues: { myIndexedParam: 20, myOtherIndexedParam: '0x123456789...', myNonIndexParam: 'My String' }, raw: { data: '0x7f9fade1c0d57a7af66ab4ead79fade1c0d57a7af66ab4ead7c2c2eb7b11a91385', topics: ['0xfd43ade1c09fade1c0d57a7af66ab4ead7c2c2eb7b11a91ffdd57a7af66ab4ead7', '0x7f9fade1c0d57a7af66ab4ead79fade1c0d57a7af66ab4ead7c2c2eb7b11a91385'] }, event: 'MyEvent', signature: '0xfd43ade1c09fade1c0d57a7af66ab4ead7c2c2eb7b11a91ffdd57a7af66ab4ead7', logIndex: 0, transactionIndex: 0, transactionHash: '0x7f9fade1c0d57a7af66ab4ead79fade1c0d57a7af66ab4ead7c2c2eb7b11a91385', blockHash: '0xfd43ade1c09fade1c0d57a7af66ab4ead7c2c2eb7b11a91ffdd57a7af66ab4ead7', blockNumber: 1234, address: '0xde0B295669a9FD93d5F28D9Ec85E40f4cb697BAe' }
虽然区块链技术目前正在快速发展，但是传统区块链技术要落地到商业应用，特别是金融应用，仍然存在很多问题需要解决，如交易性能、隐私保护等。解决这些问题的一种做法是重新开发新的区块链，但是这种做法会造成大量重复性工作，并且需要不断的发行新的数字资产。那么是否存在在不影响原有区块链工作的基础上，依托于原有区块链进行技术升级的解决方案，侧链就是在这种需求背景下被提出的。基础概念侧链协议本质上是一种跨区块链解决方案。通过这种解决方案，可以实现数字资产从第一个区块链到第二个区块链的转移，又可以在稍后的时间点从第二个区块链安全返回到第一个区块链。其中第一个区块链通常被称为主区块链或者主链，每二个区块链则被称为侧链。最初，主链通常指的是比特币区块链，而现在主链可以是任何区块链。侧链协议被设想为一种允许数字资产在主链与侧链之间进行转移的方式，这种技术为开发区块链技术的新型应用和实验打开了一扇大门。产生背景2012年，在比特币聊天室中，首次出现了关于侧链概念的相关讨论。当时比特币的核心开发团队正在考虑如何可以安全的升级比特币协议，以增加新的功能，但是直接在比特币区块链上进行功能添加比较危险，因为如果新功能在实践中发生软件故障，则会对现有的比特币网络造成严重影响。另外，由于比特币的网络结构特性，如果进行较大规模的改动，还需要获得多数比特币矿工的支持。这时，比特币核心开发者便提出了侧链方案。这种技术允许开发人员将新功能附加在其他的区块链，但是这些区块链仍然附着在现有比特币区块链上。这些区块链中新功能可以充分利用现有比特币的网络特性，而不会对现有的比特币网络造成危害。2014年，这时已经出现了许多具有新功能的区块链，并产生了各种竞争币，如莱特币、狗狗币等。这时，比特币的核心开发团队担心这些竞争币的产生会稀释比特币的价值。他们认为，应该把比特币作为一种储备货币，并将新功能添加到侧链上。这样如果用户想使用其他的新的区块链功能，就不需要购买其他代币。为了将侧链由概念转化成现实，Adam Back、Matt Corallo等比特币核心开发者共同发起成立了Blockstream公司，并在同年十月，发布了白皮书《Enabling Blockchain Innovations with Pegged Sidechains》，首次明确提出了侧链的概念及其协议实现方案。通过侧链，可以在主链的基础上，进行交易隐私保护技术、智能合约等新功能的添加，这样可以让用户访问大量的新型服务，并且对现有主链的工作并不造成影响。另外，侧链也提供了一种更安全的协议升级方式，当侧链发生灾难性的问题时，主链依然安然无恙。实现方案侧链实现的技术基础是双向锚定（Two-way Peg），通过双向锚定技术，可以实现暂时的将数字资产在主链中锁定，同时将等价的数字资产在侧链中释放，同样当等价的数字资产在侧链中被锁定的时候，主链的数字资产也可以被释放。双向锚定实现的最大难点是协议改造需兼容现有主链，也就是不能对现有主链的工作造成影响，其具体实现方式可以分为以下几类：（一）单一托管模式最简单的实现主链与侧链双向锚定的方法就是通过将数字资产发送到一个主链单一托管方（类似于交易所），当单一托管方收到相关信息后，就在侧链上激活相应数字资产。这个解决方案的最大问题是过于中心化。比特币为主链的单一托管模式的工作原理示意图：（二）联盟模式联盟模式是使用公证人联盟来取代单一的保管方，利用公证人联盟的多重签名对侧链的数字资产流动进行确认。在这种模式中，如果要想盗窃主链上冻结的数字资产就需要突破更多的机构，但是侧链安全仍然取决于公证人联盟的诚实度。以比特币为主链的联盟模式的工作示意图：单一托管模式与联盟模式的最大优点是它们不需要对现有的比特币协议进行任何的改变。（三）SPV模式SPV（Simplified Payment Verification）模式是最初的侧链白皮书《Enabling Blockchain Innovations with Pegged Sidechains》中的去中心化双向锚定技术最初设想。SPV是一种用于证明交易存在的方法，通过少量数据就可以验证某个特定区块中交易是否存在。在SPV模式中，用户在主链上将数字资产发送到主链的一个特殊的地址，这样做会锁定主链的数字资产，该输出仍然会被锁定在可能的竞争期间内，以确认相应的交易已经完成，随后会创建一个SPV证明并发送到侧链上。此刻，一个对应的带有SPV证明的交易会出现在侧链上，同时验证主链上的数字资产已经被锁住，然后就可以在侧链上打开具有相同价值的另一种数字资产。这种数字资产的使用和改变在稍后会被送回主链。当这种数字资产返回到主链上时，该过程会进行重复。它们被发送到侧链上锁定的输出中，在一定的等待时间后，就可以创建一个SPV证明，来将其发送回主区块链上，以解锁主链上的数字资产。SPV模式存在的问题是需要对主链进行软分叉。以比特币主链的SPV模式的工作流程示意图：（四）驱动链模式驱动链概念是由Bitcoin Hivemind创始人Paul Sztorc提出的。在驱动链中，矿工作为‘算法代理监护人’，对侧链当前的状态进行检测。换句话说，矿工本质上就是资金托管方，驱动链将被锁定数字资产的监管权发放到数字资产矿工手上，并且允许矿工们投票何时解锁数字资产和将解锁的数字资产发送到何处。矿工观察侧链的状态，当他们收到来自侧链的要求时，他们会执行协调协议以确保他们对要求的真实性达成一致。诚实矿工在驱动链中的参与程度越高，整体系统安全性也就越大。如同SPV侧链一样，驱动链也需要对主链进行软分叉。以比特币为主链的驱动链模式的工作流程示意图：（五）混合模式上述所有的模式都是对称的，而混合模式则是将上述获得双向锚定的方法进行有效的结合的模式。由于主链与侧链在实现机制存在本质的不同,所以对称的双向锚定模型可能是不够完善的。混合模式是在主链和侧链使用不同的解锁方法，例如在侧链上使用SPV模式，而在主链网络上则使用驱动链模式。同样，混合模式也需要对主链进行软分叉。典型范例目前，比较著名的侧链包括基于比特币网络的侧链BTC Relay、Rootstock的Liquid，以及非比特币的侧链如Lisk和国内的Asch等。BTC Relay是由ConsenSys的推出的基于以太坊区块链的智能合约的侧链解决方案。BTC Relay把以太坊网络与比特币网络以一种安全去中心化的方式连接起来。BTC Relay通过使用以太坊的智能合约功能允许用户在以太坊区块链上验证比特币交易。以太坊DApp开发者可以从智能合约向BTC Relay进行API调用来验证比特币网络活动。RootStock是一个建立在比特币区块链上的智能合约分布式平台。它的目标是将复杂的智能合约实施为一个侧链，为核心比特币网络增加价值和功能。RootStock实现了以太坊虚拟机的一个改进版本，它将作为比特币的一个侧链，使用了一种可转换为比特币的代币作为智能合约的“燃料”Liquid是Blockstream的开源侧链项目，使用了比特币双向锚定技术，Liquid目的是实现使得比特币可以在主链和侧链中互转，旨在提高隐私性、降低成本、加速交易所和经纪商之间的价值转移及结算流程。Lisk是一个致力于为JavaScript开发者提供创建分布式应用程序的区块链平台，由德国的Max Kordek和Oliver Beddows于2016年初成立。它把每一个分布式应用程序都会在其自己且独一无二的区块链，也就是侧链上运行，这种封装使得主要的Lisk的主网高效，迅速和精简Asch是国内推出的一个基于侧链技术的去中心化应用平台，由单青峰于2016年初成立。Asch平台提供的服务包括一个主链和一套应用软件开发工具包。Asch的主链主要负责构建基础设施、应用间的数据共享以及资产路由，应用软件开发工具包内置了侧链协议，主要负责构建具体的应用，通过侧链协议可以与主链进行资产互通。LISK是新一代的区块链平台，它把每个应用加到LISK的单独侧链上。用过比特币和以太坊的朋友都知道，由于比特币和以太坊只有一条主链，所有功能和数据都加入这条主链导致区块快速膨胀，超大的区块体积，超长的同步时间，这个一个很痛苦的经历。Lisk的侧链模式给在处理高交易量下如何解决网络拥堵的问题提供了一种方法，用户只有用到相关的应用时才需要下载对应的侧链，大大减小了无效的同步数据，保持了整个Lisk网络的高效运行，而且，Lisk网络的速度随着时间的推移会继续加快，越显示他的特别优势总结侧链是以融合的方式实现加密货币金融生态的目标，而不是像其它数字资产一样排斥现有的系统。侧链技术进一步扩展了区块链技术的应用范围和创新空间，使传统区块链可以支持多种资产类型，以及小微支付、智能合约、安全处理机制、财产注册等，并可以增强区块链的隐私保护。利用侧链，我们可以轻松的建立各种智能化的应用如金融合约，股票、期货、衍生品等。
进行区块链扩容的一个答案就是分片技术（Sharding）。分片技术承诺通过改变网络验证的方式来增加吞吐量。分片技术独特于其他解决扩容的链上技术的关键特性，就是它可以进行水平扩容，也就是说，网络的吞吐量随着挖矿网络的扩展而增加。这种特殊的特性可能使它成为推动区块链技术被快速采用的理想技术。简单来说，分片技术就是一个分散式并行系统，在保持主链完整稳定的同时，减少每个节点的数据储存量，从而达到扩容的效果。现有区块链的扩容问题公共区块链平台今天面临的最大问题之一就是可扩展性。所有主流的平台都在努力提高每秒的交易量。事实上，当今的公共以太坊网络和比特币网络平均每秒可以处理7-10笔交易。这一数字远低于像Visa这样的集中支付处理器，后者平均每秒能处理约8000笔交易。缓慢的交易处理造成了一个主要问题，因为大量的未完成交易阻塞了网络，使得那些诸如实时支付这样的应用程序很难在区块链上一展身手。随着确认支付的时间拉长，最终就会给用户带来诸多不便；这也是为什么像PayPal和Visa这样的信用卡支付方式仍然更具吸引力的主要原因之一。随着更多更复杂的DApps开始依赖于相同的一个区块链网络，迟缓的交易速度所导致的问题只会变得更加复杂。从技术角度来看，所有区块链的共识协议都有一个具有挑战性的限制：网络中的每一个完全参与的节点都必须要验证每一笔交易，并且这些节点必须和它的其他节点保持一致，这是区块链技术的组成部分，它通过创建分布式的账本来保证区块链的安全。在大多数像比特币和以太坊这样的区块链上，节点都是由公众进行运行的。虽然去中心化的共识机制提供了一些重要的优势，比如容错性、安全性、政治中立和真实性，但是这种验证链的方法是以降低可扩展性为代价的。当这些公共区块链变得更大时，它将需要越来越多的处理能力来验证这些公共区块链，这可能会在这些区块链的网络中造成瓶颈，从而减慢那些创建新应用程序的速度。分片技术：分而治之分片技术是一种基于数据库分片传统概念的扩容技术，它将数据库分割成多个碎片并将这些碎片放置在不同的服务器上。在公共区块链的情境中，网络上的交易将被分成不同的碎片，其由网络上的不同节点组成。因此，每个节点只需处理一小部分传入的交易，并且通过与网络上的其他节点并行处理就能完成大量的验证工作。将网络分割为碎片会使得更多的交易同时被处理和验证。因此，随着网络的增长，区块链处理越来越多的交易将成为可能。这种属性也称为水平扩容。我们可以想象一下，现有的区块链就像一条繁忙的高速公路，这条高速公路的收费站只有一个收费口。这种布局的结果将是导致交通堵塞，因为人们将排着长队等待通过这唯一的收费站。实现一个基于分片技术的区块链就像在高速公路上增加15或20个收费口。它将极大地提高汽车通过收费站的速度。因此，分片技术将带来巨大的差异，并显著提高区块链的交易速度。基于分片技术的区块链的实现对公共区块链有着不同的好处。首先，区块链上处理交易的速度变成了每秒上千笔甚至更多，这改变了人们对加密货币作为支付方式效率的看法。改善交易吞吐量将会给去中心化的系统带来使越来越多的用户和应用程序，而这将反过来促进区块链的进一步采用，也使挖矿变得更有利可图，同时也能吸引更多加入到公共网络上的节点，从而形成一个良性循环。此外，分片技术可以帮助降低交易费用，因为验证单笔交易的处理量减少了；节点可以在依然盈利运营的同时收取较小的费用。在现实世界中，我们将低费用与高交易处理能力结合起来，会使公共链将变得越来越有吸引力。这些积极的趋势所持续的时间越长，我们就会越能看到更多的主流的加密技术和区块链应用程序的出现。分片技术的策略分片策略有网络分片和交易分片，以及状态分片等。通过网络和交易分片，区块链节点的网络被分割成不同的碎片，每个碎片都能形成独立的处理过程并在不同的交易子集上达成共识。通过这种方式，我们可以并行处理相互之间未建立连接的交易子集，通过提高数量级显著提高交易的吞吐量。另一方面，在当今的主流公共区块链上，所有公共节点都承担着存储交易、智能合约和各种状态的负担，这可能使其在为了获得更大的存储空间而进行巨大的花费，以维持其在区块链上的正常运转。为了解决这一问题，有一种可被称为状态分片的可行方法已被提出。这一技术的关键是将整个存储区分开，让不同的碎片存储不同的部分；因此，每个节点只负责托管自己的分片数据，而不是存储完整的区块链状态。分片技术的复杂性尽管所有不同形式的分片技术都可能非常直观，但通过对技术细节的解读，我们可以看到这一方法的复杂性和潜在的挑战。分片技术的其中一些挑战是很容易克服的，而另一些则不然。一般来说，网络和交易分片更容易实现，而状态分片则要复杂得多。下面，对于不同的分片机制，我们会明确地讨论它们所面临的一些挑战，以及它们的可行性。1、网络分片：如何将全网节点划分到不同分片当中去分片的第一个也是最重要的挑战是创建碎片。开发者需要开发一种机制来确定哪些节点可以按照安全的方式保留在哪些碎片中，这样就能避免那些控制大量特定碎片的人所发起的攻击 。打败攻击者的最佳方法(至少在大多数情况下)就是建立随机性。通过利用随机性，网络可以随机抽取节点形成碎片。这样一种随机抽样的方式可以防止恶意节点过度填充单个碎片。但是，我们如何建立随机性呢？最容易获得公共随机性的来源是区块，例如，交易的Merkle tree root。在区块中所提供的随机性是可被公开验证的，并且可以通过随机提取器中提取统一的随机比特。然而，简单地使用随机机制将节点分配给碎片仍是不够的。我们还必须要确保网络的一个碎片中不同成员意见的一致性。这可以通过像工作量证明这样的共识协议来实现。2、交易分片：如何将全网交易划分到不同分片当中去交易分片可听起来那么简单。考虑到在一个类似于比特币的系统中引入交易分片(没有智能合同)，系统的状态是用UTXOs来进行定义的。我们假设网络已经由碎片所组成，用户发送一笔交易，每一笔交易有两个输入和一个输出。那么，该笔交易将如何分配给一个碎片呢?最直观的方法是根据交易哈希值的最后几位来决定碎片。例如，如果哈希值的最后一个比特是0的话，那么交易将被分配给第一个碎片，否则它被分配给第二个碎片(假设我们只有两个碎片)。这允许我们在单个碎片中验证交易。但是，如果用户是恶意的，他可能会创建另一笔具有两个相同输入但不同输出的交易——是的，就是一个双花交易。第二笔交易将有一个不同的哈希值，因此，这两笔交易就可能形成不同的碎片。然后，每个碎片将分别验证接收到的交易，同时忽略在另一个碎片中验证的双花交易。为了防止双花问题，在验证过程中，碎片将不得不进行相互通信。事实上，由于双花交易可能会在任何碎片中出现，因此特定碎片所接收到的交易将不得不与其它的碎片进行通信。而实际上，这种相互之间的通信可能会破坏交易分片的整个目的。另一方面，当我们有一个基于账户的系统(没有智能合约)时，问题就简单得多了。每一笔交易将会有一个发送者的地址，然后系统可以根据发送者的地址分配一个碎片。这确保了两笔双花交易将在相同的碎片中得到验证，因此系统可以很容易地检测到双花交易，而不需要进行任何跨碎片的通信。3、状态分片：如何让各个节点只维护各自分片内的账本，但又不影响整个系统的安全性。状态分片带来了新的挑战。事实上，状态分片是迄今为止最具挑战性的分片技术提案。继续使用我们的基于账户的模型(我们暂时不在我们的例子中引入智能合约)，在一个状态分片的区块链中，一个特定的碎片只会保留一部分状态。例如，如果我们有两个碎片和两个用户帐户，分别为Alice和Bob，那么每个碎片将保留一个用户的余额。\假设Alice创建了一笔交易，她将支付Bob一笔钱。这笔交易将由第一个碎片进行处理，一旦该笔交易被验证，关于Bob的新余额的信息就必须与他所在的碎片进行共享。如果两个受欢迎的帐户由不同的碎片进行处理，那么这可能需要进行频繁的跨碎片通信和状态交换。确保跨碎片通信不会超过状态分片的性能收益仍然是一个值得公开的研究问题。减少跨碎片通信开销的一种可能方法，是限制用户进行跨碎片交易。以我们上面的例子来说，这就意味着系统不允许Alice直接与Bob进行交易。如果Alice必须与Bob交易的话，她将不得不在那块碎片中占有一个帐户。虽然这确实消除了任何跨碎片通信，但它可能会限制平台的可用性。状态分片的第二个挑战是数据的可用性。我们可以考虑这样一个场景，由于某种原因，一些特定的碎片遭到了攻击而导致其脱机。由于碎片并没有复制系统的全部状态，所以网络不能再验证那些依赖于脱机碎片的交易。因此，在这样的情况下区块链基本上是无法使用的。解决此问题的方法是维护存档或进行节点备份，这样就能帮助系统进行故障修复以及恢复那些不可用的数据。但是，这样就使得节点将不得不存储系统的整个状态，因此这还可能会引发一些中心化的风险。我们在任何分片机制(当然不是特定于状态分片)中需要考虑的另一个要点是，确保碎片在抵御攻击和失败时是具有弹性的； 网络必须接受新的节点并以随机的方式将这些分配给不同的碎片。换句话说，网络必须在一段时间内进行节点的重新分配。然而，在状态分片的情况下，重新分配节点是非常棘手的。由于每个碎片只保留了状态的一部分，所以在一次重新调整网络的过程中，在同步完成前可能会出现导致使整个系统失效的问题。为了防止系统的中断，我们必须对网络进行逐步调整，以确保每个碎片在所有节点被清空前仍有足够多的旧节点。类似地，一旦一个新节点加入了一个碎片中，系统就必须确保该节点有足够的时间与碎片状态进行同步；否则，传入节点将完全拒绝每一笔交易。zilliqa分片开源地址：https://github.com/Zilliqa/ZilliqaC++实现的在亚马逊的EC2上面测试得到用3600节点实现了每秒2488笔交易特点：分片技术、PoW+PBFT混合共识机制测试网络：https://explorer.zilliqa.comZilliqa的设计构思 第1部分：网络分片https://my.oschina.net/zilliqa/blog/2962501Zilliqa 的设计构思 第2部分：共识协议https://my.oschina.net/zilliqa/blog/2962504Zilliqa 的设计构思 第3部分：使共识更有效https://my.oschina.net/zilliqa/blog/2962511Zilliqa官方挖矿指南中文版https://www.huoxing24.com/newsdetail/20181206173835283794.html网络分片假设我们有一个包含1000个节点的网络，将自动地把该网络分成10个、每个包含100个节点的分片，且所有分片可并行地处理交易。由于分片架构能平行地处理交易，因此吞吐量可随着网络规模增加而线性增长。每个分片现在都能独立处理交易并因此产生高吞吐量。需要解决的关键问题对女巫攻击的防御（Sybil Resistance）创建分片、给分片分配节点和任务分片大小跨片交易zilliqa解决方法防控女巫节点使用PoW。每个希望加入Zilliqa网络的新节点都必须先执行PoW，网络中的现有节点验证新节点的PoW并授权其加入网络。POW工作量证明部分跟以太坊基本上是一样的，这要求你将上一个区块的哈希值、节点的IP地址和你的公钥一起进行哈希计算。对应的难度是相匹配的，例如哈希值的前100位都是0，如果你算出来的哈希值满足这个条件，就说明你完成了工作量证明。根据工作量证明节点ID的最后几位，来决定分到哪一个分片上。对于一个新的节点来说，是无法通过自己的意志去加入某一个分片的，只能通过工作量证明，而工作量证明难度较高，因此可以避免出现新节点自己选择分片的情况。因此工作量证明的最后几位，就可以从数学上保证你的随机性是足够的。可以保证一些恶意节点不能直接加入到某一个分片。自动创建分片有一个单独的分片即DS委员会去整合每个分片的结果，收集不同分片里面交易哈希，进行一个共识协议，形成哈希的哈希，然后广播，其他节点验证签名。在每个DS Epoch开始时，所有候选人都将运行工作证明（Ethash算法）过程300秒窗口，以便竞争加入Zilliqa网络。每个DS Epoch（约1.5小时）内总共有100个TX时期（每个~1分钟）。第100个TX时期被称为Vacuous时期。空白时期会处理coinbase交易（奖励机制）、升级机制（因为pBFT中没有分支）和持久状态存储（写入节点的DB而不是仅存储在内存中）。在这个时期，网络不会处理任何常规交易。基于POW选举出DS委员会，使用先进先出策略定期移出一名DS委员会老成员、增加一名新成员，新进入委员会的节点是最快解决PoW的节点，任何时候DS委员会的大小都是固定的。DS委员会一旦当选，便启动分片程序，网络中的所有其他节点立即执行另一个PoW，其PoW由DS委员会验证，每个节点根据提交情况和随机性，被分配到特定的分片。PoW提交的最后几位二进制数字决定了节点将被分配到哪个分片。选择合适的尺寸选择合适的分片大小对系统的安全至关重要。使用PoW创建分片相当于随机无差别地抽样一个节点集。从600个节点开始，其包含三分之一的恶意节点的概率降至百万分之一。出于这个原因，Zilliqa认为最小分片大小为600。避免跨片交易因为跨片交易需要锁协议，因此其开销成本很高，在分片设计之初就尽量避免跨片交易的产生原子提交协议技术方案交易分片每当交易到达网络时，它就被分配到一个特定的分片上。分配是由交易发送地址的前几位二进制数字决定的，这就叫做交易分片。交易首先由分片打包，生成微块，然后上传给DS委员会，如果幸运，能被DS节点确认并签名，生成最终块。每一个节点都可以收到最终的区块，这个区块的内容是很小的。同时，不同区块之间也会进行交换数据，从而分享最终区块内的这些交易。整个系统有三层结构：第一层，是哈希的哈希；第二层，交易的哈希；第三层，真正的交易内容。通过这种三层结构来保证整个系统在每一步进行广播的时候，内容量都是相对比较小的。因此过了一段时间之后，你的不同分片里面，大家都可以获得这一段时间以来交易处理之后的一个共同状态。交易分片按照交易发送者的账号地址来划分，来自同一发送者的所有交易都将在同一个分片中处理，允许每个分片成员检测其是否双花。通过每个交易中存在的随机数nonce，可以轻松检测双重花费（或重放攻击）。计算分片分片还使计算执行和智能合约运行十分高效。例如，一部分分片可以充当映射器（mapper），其他部分分片可以充当归约器（reducer），并非常有效地执行映射-归约任务（map-reduce task），这也被称为计算分片。共识协议计算密集型的PoW需要大量的时间进行计算并且可能减慢共识协议，且它与网络中的节点数量无关，而是取决于网络的集体计算能力。不能很好地利用分片小的优势实用拜占庭容错协议（Practical Byzantine Fault Tolerance, 简称为PBFT）Zilliqa采用PBFT在每个分片中达成共识。该协议是由卡斯特罗和利斯科夫（Castro and Liskov）在1999年提出的。它是在这样的假设下运行的：在执行协议之前，假设每个分片中最多有1/3的节点是恶意的。在PBFT中，一个共识组中（即一个分片中）的所有节点按顺序排列，它有一个主节点（领导者），其他节点被称为备份节点。每轮PBFT都有三个阶段：预备、准备、提交。PBFT与Nakamoto共识协议相比其他优点交易最终性一旦交易被提交到区块链，那么它就是最终的了且不会有临时分叉，因此不需要确认。低能耗Zilliqa只使用PoW来防止女巫节点攻击、确认节点身份并进行分片，而不用于达成共识。现实中，每确认大约100个区块才需要做一次PoW。报酬差异小Zilliqa中参与共识协议的每个矿工都可以获得对应的奖励PBFT的挑战一个主要缺点：只有当分片规模很小时（即小于50）才高效。但是，正如我们前面的文章中所讨论的，出于安全原因，Zilliqa的分片大小必须不少于600个节点。PBFT对于大型网络而言效率低下的主要原因是它有一个潜在的通信成本，即 分片中的每个节点都必须与所有其他节点通信，这就是通信成本二次方的原因。使用数字签名而不是MAC将发送消息的数量从二次方数量级减少到线性，当n很大时这种减少会产生重要影响。以600个节点为例，其中传播的消息数量可以从17.97万减少到599使用多重签名的方法来降低通信成本，减少每个消息的大小目前一种比较流行的多重签名方案是基于Schnorr数字签名技术Zilliqa使用了近期一些学术论文中的技术来提高经典PBFT协议的效率。
分布式系统一致性 一致性即是对于系统中的多个服务节点，在约定的协议下，执行相同的操作并保持状态的一致，简单来说就是多个节点持有相同的数据，如果数据要改变就应该每一个节点都做相同的改变。如果分布式系统能实现“一致”，对外就可以呈现为一个功能正常的，且性能和稳定性都要好很多的“虚处理节点”。 理想的分布式系统一致性应该满足：可终止性（Termination）、共识性（Consensus）、合法性（Validity）。一致性难题但是在实际的计算机集群中，可能会存在以下问题:节点之间的网络通讯是不可靠的，包括数据丢失、延迟、重复、损坏节点处理事务的能力不同，网络节点数据的吞吐量有差异节点可能死记，可能会有作恶节点出现当异步处理能力达到高度一致时，系统的可扩展性就会变差,即容不下新节点的加入弱一致性可想而知，绝对理想的强一致性（Strong Consistency）代价很大。除非不发生任何故障，所有节点之间的通信无需任何时间，这个时候其实就等价于一台机器了。实际上，越强的一致性要求往往意味着越弱的性能 强一致的系统往往比较难实现。很多时候，人们发现实际需求并没有那么强，可以适当放宽一致性要求，降低系统实现的难度。例如在一定约束下实现所谓最终一致性（Eventual Consistency），即总会存在一个时刻（而不是立刻），系统达到一致的状态，这一类弱化的一致性，被笼统称为弱一致性（Weak Consistency）一致性级别强一致性, 这种一致性级别是最符合用户直觉的，它要求系统写入什么，读出来的也会是什么，用户体验好，但实现起来往往对系统的性能影响大 弱一致性, 这种一致性级别约束了系统在写入成功后，不承诺立即可以读到写入的值，也不久承诺多久之后数据能够达到一致，但会尽可能地保证到某个时间级别（比如秒级别）后，数据能够达到一致状态 最终一致性, 最终一致性是弱一致性的一个特例，系统会保证在一定时间内，能够达到一个数据一致的状态。这里之所以将最终一致性单独提出来，是因为它是弱一致性中非常推崇的一种一致性模型，也是业界在大型分布式系统的数据一致性上比较推崇的模型共识算法实际上，要保障系统满足不同程度的一致性，往往需要通过共识算法来达成。共识算法解决的是对某个提案（Proposal），大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等，可以认为任何需要达成一致的信息都是一个提案。 “完美”的系统并不存在，响应请求往往存在时延、网络会发生中断、节点会发生故障、甚至存在恶意节点故意要破坏系统。一般地，把故障（不响应）的情况称为“非拜占庭错误”，恶意响应的情况称为“拜占庭错误”。 针对非拜占庭错误的情况，一般包括Paxos、Raft、zab 及其变种。对于要能容忍拜占庭错误的情况，一般包括 PBFT、PoW、Pos算法等。共识界限一般情况下，分布式系统的共识问题无解。当节点之间的通信网络自身不可靠情况下，很显然，无法确保实现共识。但好在，一个设计得当的网络可以在大概率上实现可靠的通信。然而，即便在网络通信可靠情况下，一个可扩展的分布式系统的共识问题的下限是无解。这个结论，被称为FLP不可能性原理。FLP 不可能原理实际上告诉人们，不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法。FLP不可能性原理：在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。在付出一些代价的情况下，可以设计出一个大致可用的共识算法，这就是CAP理论。CAP理论：分布式计算系统不可能同时确保一致性（Consistency）、可用性（Availablity）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证。一致性（Consistency）：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强性； 可用性（Availablity）：在有限时间内，任何非失败节点都能应求； 分区容忍性（Partition）：网络可能发生分区，即节点之间的通信不可保障。BASE理论BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的缩写。BASE理论是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的总结， 是基于CAP定理逐步演化而来的。BASE理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。基本可用 基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性----注意，这绝不等价于系统不可用。比如： 软状态 软状态指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时最终一致性 最终一致性强调的是所有的数据副本，在经过一段时间的同步之后，最终都能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。去中心化在软件世界里，所谓的“去中心化”，实际上是可以分成三个维度进行讨论的。这三个维度，也是判断一个东西是否是“去中心化”的三把尺子。需要说明的是，这三把尺子，初看起来似乎缺一不可，但总体来说，它们彼此之间相互独立，详解架构层： 在物理世界里，一个系统由多少台计算机组成？在这个系统运行的过程中，可以忍受多少台计算机的崩溃而系统依然不* 受影响？政治层： 有多少个人或者组织，对组成系统的计算机拥有最终的控制权？逻辑层： 从这个系统所设计的接口和数据结构来看，它更像一台完整的单一设备，还是更像一个由无数单位组成的集群？——这个维度可能比较抽象，不太好理解，我们可以用另一种比较简单的方式来做判断： 如果把这个系统分成两半，两部分里同时包含生产者和消费者，那么这两部分能继续作为独立单元完整地运行下去吗？ 这三把尺子，一把用来测量架构层的系统设计、一把用来测量政治层的掌控权力、一把用来测量逻辑层的所属形态。 去中心化优点容错性： 去中心化系统不太可能因为某一个局部的意外故障而停止工作，因为它依赖于许多独立工作的组件，它的容错能力更强。 抗攻击性： 对去中心化系统进行攻击破坏的成本相比中心化系统更高。从经济效益上来说，这是抢劫一个房子和抢劫一片村庄的差别。 抗勾结性： 去中心化系统的参与者们，很难相互勾结。而传统企业和政府的领导层，往往会为了自身的利益，以损害客户、员工和公众利益的方式，相互勾结。 去中心化的缺点则是效率的降低，去中心化程度越高，各个节点间达成共识越难。POW:Proof of Work工作证明POW采用提高提议成本的方式，每一个节点在提出提议时必须解决一个难题（消耗时间），谁先解决谁说了算。比特币所用的POW可简述为：填充区块的随机数字段，使其区块hash满足给定数量前导0的哈希值的过程。要求的前导0的个数越多，代表难度越大；同时为了保证出块的速度，动态调整了全网难度值。POS:Proof of Stake股权证明POW造成了计算机算力浪费，POS在一定程度弥补了这一点，股权证明要求用户证明拥有某些数量的代币和持有时间，币龄（代币数量乘以持有时间）越高提议权越大，一旦达成提议则持有时间清零,币龄清空,没有币就没有话语权。POW+POS 集合POW和POS的优点,使用POW证明方式,利用POS股权降低挖矿难度,即节点提议难度和股权数成反比。POA:Proof-of-Authority权威证明由一些有许可（权威）的节点负责提议，这些节点被称为“验证者”（Validator） 验证者必须满足以下三个条件： 其身份必须得到正式验证，信息可在公有可用域中交叉验证。 其资格必须难以获得，这样所得到的权威才弥足珍贵（例如，潜在的验证者需要获得公证书）。 建立权威的检查和程序必须完全统一。 使用 POA，每个个体都具有变成验证者的权利，因此存在一旦获取就保持验证者位置的动机。通过对身份附加一个声誉，可以鼓励验证者去维护交易的过程。因为验证者并不希望让自己获得负面声誉，这会使其失去来之不易的验证者地位。DPOS:Delegated Proof of Stake委任权益证明POS中可能存在提议权把握在少数拥有大量代币的节点手中,DPOS能够避免"集权"的产生,让每一个节点按一定规则投票选出一定数量的节点来代表整个集群，选出来的节点权利对等，DPoS机制类似于股份制公司，普通股民进不了董事会，要投票选举代表（受托人）代他们做决策。PBFT:Practical Byzantine Fault Tolerance实用拜占庭容错算法pbft算法主要是为了解决拜占庭将军问题，假设网络没有问题但是可能有恶意节点（不能超过1/3），基本流程：客户端发送请求给主节点主节点广播请求给其它节点，节点执行 pbft 算法的三阶段共识流程（预准备阶段，准备阶段，提交阶段）。节点处理完三阶段流程后，返回消息给客户端。客户端收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。PAXOS算法指系统中存在故障，但不存在恶意节点场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。 算法中将节点分为三种类型： proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色； acceptor：负责对提案进行投票。往往是服务端担任该角色； learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。 基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认，learner确认一个提议是否被采纳。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。RAFT算法Raft 算法是Paxos算法的一种简化实现。包括三种角色：leader、candidate和follower，其基本过程为： Leader选举：每个candidate提出选举方案，得票最多者被选为leader； 同步：由leader处理所有提议，并分发给follower，各个节点与leader进行同步。ZAB算法原子消息广播协议，与RAFT算法稍有区别，RAFT主节点提出一个提议，不需要等待follower确认就可以提出下一个，每隔一段时间批量确认，而ZAB是确认一条提议才能处理下一条（原子性）。共识算法总结本质是解决不同节点间的一致性问题； 明确了哪个节点可以提议或者同时提议时选择哪个提议 一般假定信道没有问题，但是可能存在恶意节点，要处理节点作恶对于故障节点处理和如何同步恢复的问题
区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式，它本质上是一个去中心化的分布式数据库，是一串相关联的使用密码学方法产生的的数据区块。比特币白皮书英文原版其实并未出现blockchain一词，而是使用的chain of blocks。最早的比特币白皮书中文翻译版中，将chain of blocks翻译成了区块链。这是“区块链”这一中文词最早的出现时间。狭义来讲，区块链是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构，并以密码学方式保证的不可篡改和不可伪造的分布式账本。广义来讲，区块链技术是利用块链式数据结构来验证与存储数据、利用分布式节点共识算法来生成和更新数据、利用密码学的方式保证数据传输和访问的安全、利用由自动化脚本代码组成的智能合约来编程和操作数据的一种全新的分布式基础架构与计算方式。区块链技术被认为是继蒸汽机、电力、互联网之后，下一代颠覆性的核心技术。 如果说蒸汽机释放了人们的生产力，电力解决了人们基本的生活需求，互联网彻底改变了信息传递的方式，那么区块链作为构造信任的机器，将可能彻底改变整个人类社会价值传递的方式。基本原理区块链包括三个基本概念：交易（transaction）：一次对账本的操作，导致账本状态的一次改变，如添加一条转账记录；区块（block）：记录一段时间内发生的所有交易和状态结果，是对当前账本状态的一次共识；链（chain）：由区块按照发生顺序串联而成，是整个账本状态变化的日志记录。如果把区块链作为一个状态机，则每次交易就是试图改变一次状态，而每次共识生成的区块，就是参与者对于区块中交易导致状态改变的结果进行确认。在实现上，首先假设存在一个分布式的数据记录账本，这个账本只允许添加、不允许删除。账本底层的基本结构是一个线性的链表，这也是其名字“区块链”的来源。链表由一个个“区块”串联组成，后继区块记录前导区块的哈希值。新的数据要加入，必须放到一个新的区块中。而这个块是否合法，可以通过计算哈希值的方式快速检验出来。任意维护节点都可以提议一个新的合法区块，然而必须经过一定的共识机制来对最终选择的区块达成一致。发展历程2008年由中本聪第一次提出了区块链的概念，在随后的几年中，区块链成为了电子货币比特币的核心组成部分：作为所有交易的公共账簿。通过利用点对点网络和分布式时间戳服务器，区块链数据库能够进行自主管理。为比特币而发明的区块链使它成为第一个解决重复消费问题的数字货币。比特币的设计已经成为其他应用程序的灵感来源。2014年，"区块链2.0”成为一个关于去中心化区块链数据库的术语。对这个第二代可编程区块链，经济学家们认为它是一种编程语言，可以允许用户写出更精密和智能的协议。因此，当利润达到一定程度的时候，就能够从完成的货运订单或者共享证书的分红中获得收益。区块链2.0技术跳过了交易和“价值交换中担任金钱和信息仲裁的中介机构”。它们被用来使人们远离全球化经济，使隐私得到保护，使人们“将掌握的信息兑换成货币”，并且有能力保证知识产权的所有者得到收益。第二代区块链技术使存储个人的“永久数字ID和形象”成为可能，并且对“潜在的社会财富分配”不平等提供解决方案。2016年1月20日，中国人民银行数字货币研讨会宣布对数字货币研究取得阶段性成果。会议肯定了数字货币在降低传统货币发行等方面的价值，并表示央行在探索发行数字货币。中国人民银行数字货币研讨会的表达大大增强了数字货币行业信心。这是继2013年12月5日央行五部委发布关于防范比特币风险的通知之后，第一次对数字货币表示明确的态度。2016年12月20日，数字货币联盟——中国FinTech数字货币联盟及FinTech研究院正式筹建。如今，比特币仍是数字货币的绝对主流，数字货币呈现了百花齐放的状态，常见的有bitcoin、litecoin、dogecoin、dashcoin，除了货币的应用之外，还有各种衍生应用，如以太坊Ethereum、Asch等底层应用开发平台以及NXT，SIA，比特股，MaidSafe，Ripple等行业应用。类型公有区块链公有区块链（Public Block Chains)是指：世界上任何个体或者团体都可以发送交易，且交易能够获得该区块链的有效确认，任何人都可以参与其共识过程。公有区块链是最早的区块链，也是应用最广泛的区块链，各大bitcoins系列的虚拟数字货币均基于公有区块链，世界上有且仅有一条该币种对应的区块链。联合（行业）区块链行业区块链（Consortium Block Chains)：由某个群体内部指定多个预选的节点为记账人，每个块的生成由所有的预选节点共同决定（预选节点参与共识过程），其他接入节点可以参与交易，但不过问记账过程(本质上还是托管记账，只是变成分布式记账，预选节点的多少，如何决定每个块的记账者成为该区块链的主要风险点），其他任何人可以通过该区块链开放的API进行限定查询。私有区块链私有区块链（Private Block Chains)：仅仅使用区块链的总账技术进行记账，可以是一个公司，也可以是个人，独享该区块链的写入权限，本链与其他的分布式存储方案没有太大区别。传统金融都是想实验尝试私有区块链，而公链的应用例如bitcoin已经工业化，私链的应用产品还在摸索当中。特征去中心化。区块链技术不依赖额外的第三方管理机构或硬件设施，没有中心管制，除了自成一体的区块链本身，通过分布式核算和存储，各个节点实现了信息自我验证、传递和管理。去中心化是区块链最突出最本质的特征。去信任。由于节点之间的交换遵循固定的算法，其数据交互是无需信任的（区块链中的程序规则会自行判断活动是否有效），因此交易对手无须通过公开身份的方式让对方对自己产生信任，对信用的累积非常有帮助。开放性。区块链技术基础是开源的，除了交易各方的私有信息被加密外，区块链的数据对所有人开放，任何人都可以通过公开的接口查询区块链数据和开发相关应用，因此整个系统信息高度透明。独立性。基于协商一致的规范和协议(类似比特币采用的哈希算法等各种数学算法)，整个区块链系统不依赖其他第三方，所有节点能够在系统内自动安全地验证、交换数据，不需要任何人为的干预。安全性。只要不能掌控全部数据节点的51%，就无法肆意操控修改网络数据，这使区块链本身变得相对安全，避免了主观人为的数据变更。匿名性。除非有法律规范要求，单从技术上来讲，各区块节点的身份信息不需要公开或验证，信息传递可以匿名进行。架构模型一般说来，区块链系统由数据层、网络层、共识层、激励层、合约层和应用层组成。其中，数据层封装了底层数据区块以及相关的数据加密和时间戳等基础数据和基本算法；网络层则包括分布式组网机制、数据传播机制和数据验证机制等；共识层主要封装网络节点的各类共识算法；激励层将经济因素集成到区块链技术体系中来，主要包括经济激励的发行机制和分配机制等；合约层主要封装各类脚本、算法和智能合约，是区块链可编程特性的基础；应用层则封装了区块链的各种应用场景和案例。该模型中，基于时间戳的链式区块结构、分布式节点的共识机制、基于共识算力的经济激励和灵活可编程的智能合约是区块链技术最具代表性的创新点。核心技术分布式账本分布式账本指的是交易记账由分布在不同地方的多个节点共同完成，而且每一个节点记录的是完整的账目，因此它们都可以参与监督交易合法性，同时也可以共同为其作证。需要满足两个特性：一是区块链每个节点都按照块链式结构存储完整的数据。二是区块链每个节点存储都是独立的、地位等同的，依靠共识机制保证存储的一致性。非对称加密存储在区块链上的交易信息是公开的，但是账户身份信息是高度加密的，只有在数据拥有者授权的情况下才能访问到，从而保证了数据的安全和个人的隐私。共识机制共识机制就是所有记账节点之间怎么达成共识，去认定一个记录的有效性，这既是认定的手段，也是防止篡改的手段。区块链的共识机制具备“少数服从多数”以及“人人平等”的特点，其中“少数服从多数”并不完全指节点个数，也可以是计算能力、股权数或者其他的计算机可以比较的特征量。“人人平等”是当节点满足条件时，所有节点都有权优先提出共识结果、直接被其他节点认同后并最后有可能成为最终共识结果。应用金融领域区块链在国际汇兑、信用证、股权登记和证券交易所等金融领域有着潜在的巨大应用价值。将区块链技术应用在金融行业中，能够省去第三方中介环节，实现点对点的直接对接，从而在大大降低成本的同时，快速完成交易支付。比如Visa推出基于区块链技术的Visa B2B Connect，它能为机构提供一种费用更低、更快速和安全的跨境支付方式来处理全球范围的企业对企业的交易。要知道传统的跨境支付需要等3-5天，并为此支付1-3%的交易费用。Visa还联合Coinbase推出了首张比特币借记卡，花旗银行则在区块链上测试运行加密货币“花旗币”。物联网和物流领域区块链在物联网和物流领域也可以天然结合。通过区块链可以降低物流成本，追溯物品的生产和运送过程，并且提高供应链管理的效率。该领域被认为是区块链一个很有前景的应用方向。区块链通过结点连接的散状网络分层结构，能够在整个网络中实现信息的全面传递，并能够检验信息的准确程度。这种特性一 定程度上提高了物联网交易的便利性和智能化。区块链+大数据的解决方案就利用了大数据的自动筛选过滤模式，在区块链中建立信用资源，可双重提高交易的安全性，并提高物联网交易便利程度。为智能物流模式应用节约时间成本。区块链结点具有十分自由的进出能力，可独立的参与或离开区块链体系，不对整个区块链体系有任何干扰。区块链 +大数据解决方案就利用了大数据的整合能力，促使物联网基础用户拓展更具有方向性，便于在智能物流的分散用户之间实现用户拓展。公共服务领域区块链在公共管理、能源、交通等领域都与民众的生产生活息息相关，但是这些领域的中心化特质也带来了一些问题，可以用区块链来改造。区块链提供的去中心化的完全分布式DNS服务通过网络中各个节点之间的点对点数据传输服务就能实现域名的查询和解析，可用于确保某个重要的基础设施的操作系统和固件没有被篡改，可以监控软件的状态和完整性，发现不良的篡改，并确保使用了物联网技术的系统所传输的数据没用经过篡改。数字版权领域通过区块链技术，可以对作品进行鉴权，证明文字、视频、音频等作品的存在，保证权属的真实、唯一性。作品在区块链上被确权后，后续交易都会进行实时记录，实现数字版权全生命周期管理，也可作为司法取证中的技术性保障。例如，美国纽约一家创业公司Mine Labs开发了一个基于区块链的元数据协议，这个名为Mediachain的系统利用IPFS文件系统，实现数字作品版权保护，主要是面向数字图片的版权保护应用。保险领域在保险理赔方面，保险机构负责资金归集、投资、理赔，往往管理和运营成本较高。通过智能合约的应用，既无需投保人申请，也无需保险公司批准，只要触发理赔条件，实现保单自动理赔。一个典型的应用案例就是LenderBot, 是2016年由区块链企业Stratumn、德勤与支付服务商Lemonway合作推出，它允许人们通过Facebook Messenger的聊天功能，注册定制化的微保险产品，为个人之间交换的高价值物品进行投保，而区块链在贷款合同中代替了第三方角色。公益领域区块链上存储的数据，高可靠且不可篡改，天然适合用在社会公益场景。公益流程中的相关信息，如捐赠项目、募集明细、资金流向、受助人反馈等，均可以存放于区块链上，并且有条件地进行透明公开公示，方便社会监督。面临的挑战从实践进展来看，区块链技术在商业银行的应用大部分仍在构想和测试之中，距离在生活、生产中的运用还有很长的路，而要获得监管部门和市场的认可也面临不少困难，主要有:受到现行观念、制度、法律制约。区块链去中心化、自我管理、集体维护的特性颠覆了人们生产生活方式，淡化了国家、监管概念，冲击了现行法律安排。对于这些，整个世界完全缺少理论准备和制度探讨。即使是区块链应用最成熟的比特币，不同国家持有态度也不相同，不可避免阻碍了区块链技术的应用与发展。解决这类问题，显然还有很长的路要走。在技术层面，区块链尚需突破性进展。区块链应用尚在实验室初创开发阶段，没有直观可用的成熟产品。比之于互联网技术，人们可以用浏览器、APP等具体应用程序，实现信息的浏览、传递、交换和应用，但区块链明显缺乏这类突破性的应用程序，面临高技术门槛障碍。再比如，区块容量问题，由于区块链需要承载复制之前产生的全部信息，下一个区块信息量要大于之前区块信息量，这样传递下去，区块写入信息会无限增大，带来的信息存储、验证、容量问题有待解决。竞争性技术挑战。虽然有很多人看好区块链技术，但也要看到推动人类发展的技术有很多种，哪种技术更方便更高效，人们就会应用该技术。比如，如果在通信领域应用区块链技术，通过发信息的方式是每次发给全网的所有人，但是只有那个有私钥的人才能解密打开信件，这样信息传递的安全性会大大增加。同样，量子技术也可以做到，量子通信——利用量子纠缠效应进行信息传递——同样具有高效安全的特点，近年来更是取得了不小的进展，这对于区块链技术来说，就具有很强的竞争优势
一、区块（Block）区块（Block）是以太坊（Ethereum）的核心数据结构之一。所有账户的相关活动，以交易(Transaction)的格式存储，每个区块有一个交易对象的列表；每个交易的执行结果，由一个收据（Receipt）对象与其包含的一组日志（Log）对象记录；所有交易执行完后生成的收据列表，存储在区块中(经过压缩加密)。不同区块之间，通过前向指针父哈希（ParentHash）一个一个串联起来成为一个链表，区块链（BlockChain）结构体管理着这个链表。数据定义：type Block struct { header *Header //区块头 uncles []*Header //叔块头集合 transactions Transactions //交易集合 hash atomic.Value //区块哈希 size atomic.Value //区块大小 td *big.Int //累计的区块难度 ReceivedAt time.Time //区块接收时间 ReceivedFrom interface{} //区块来源 }数据项注解：td（total difficulty）为当前链的总难度，即到当前区块截止，累积的所有区块难度之和核心方法：func (b *Block) Size() common.StorageSize //区块rlp编码后的大小func (b *Block) Hash() common.Hash //区块keccak256哈希，实际是header的哈希1、区块头区块头（Header）是Block的核心，注意到它的成员变量全都是公共的，这使得它可以很方便的向调用者提供关于Block属性的操作。type Header struct { ParentHash common.Hash //父区块哈希。除了创世块外，每个区块有且只有一个父区块 UncleHash common.Hash //所属区块uncles成员的哈希值。uncles是一个Header数组 Coinbase common.Address //打包该区块的矿工的地址，用于接收矿工费 Root common.Hash //状态树的根哈希值 TxHash common.Hash //交易树的根哈希值 ReceiptHash common.Hash //收据树的根哈希值 Bloom Bloom //交易收据日志组成的Bloom过滤器 Difficulty *big.Int //本区块的难度 Number *big.Int //区块的序号。等于其父区块Number+1 GasLimit uint64 //区块内所有Gas消耗的上限，该数值在区块创建时设置，用于限定区块大小。 GasUsed uint64 //区块内所有Transaction执行时所实际消耗的Gas总和 Time uint64 //区块产生的时间戳，一般是打包区块的时间，这个字段不是出块的时间戳 Extra []byte //区块的附加数据 MixDigest common.Hash //哈希值，与Nonce的组合用于工作量计算 Nonce BlockNonce //一个64bit的哈希数，它被应用在区块的"挖掘"阶段，并且在使用中会被修改 }GasLimit是用于限制区块中的交易个数用的。具体由每个矿工自己设置，有些矿工觉得本区块的GasLimit太大，可以在挖下一个区块时间Gas Limit下调1/1024,觉得GasLimit太小的时候，就会上调1/1024。整个区块链中区块的大小，就是所有矿工微调的平均值。以太坊中正是通过GasLimit来限制区块的大小。区块头中比较重要的三个字段是Root、TxHash和ReceiptHash三个哈希值。收据树必须在区块的所有交易执行完成才能生成；交易树理论上只需交易数组即可，不过依然被限制在所有交易执行完后才生成；最有趣的是状态树，由于它存储了所有账户的信息，比如余额，发起交易次数，虚拟机指令数组等等，所以随着每次交易的执行，状态其实一直在变化，这就使得Root值也在变化中。于是StateDB定义了一个函数IntermediateRoot()，用来生成那一时刻的Root值:2、交易区块的成员transactions其实是Transaction数组，交易(Transaction)是指由一个外部账户转移一定资产给某个账户， 或者发出一个消息指令到某个智能合约。在以太坊网络中，交易执行属于一个事务。具有原子性、一致性、隔离性、持久性特点。为了安全性，交易需要发送者签名才有效，别人不能伪造签名发起交易而盗取以太币。需要注意的是，TxByNonceh是按nonce排序的Transaction数组，TxByPrice是按gas价格排序的Transaction数组数据定义：type Transaction struct { data txdata //交易详情 // caches hash atomic.Value //交易哈希 size atomic.Value //交易大小，data成员rlp编码大小 from atomic.Value //交易来源 } type txdata struct { AccountNonce uint64 //账户nonce Price *big.Int //gas价格 GasLimit uint64 //gas上限 Recipient *common.Address //交易接受者 Amount *big.Int //以太币数量 Payload []byte //交易附加数据，智能合约所需 // Signature values V *big.Int //交易签名r、s、v，发送者签名 R *big.Int // S *big.Int // // This is only used when marshaling to JSON. Hash *common.Hash //交易哈希 }注解：账户nonce用于撤销交易、防止双花等交易的哈希、大小、来源等需要经常读写，所以可以把它们缓存起来特别注意的是交易的来源，它是从交易的签名R、S、V中提取出来另外从签名V中可以提取出chainId核心方法：func (tx Transaction) ChainId() big.Intfunc (tx *Transaction) MarshalJSON() ([]byte, error)func (tx *Transaction) UnmarshalJSON(input []byte) errorfunc (tx *Transaction) WithSignature(signer Signer, sig []byte)func (tx *Transaction) AsMessage(s Signer) (Message, error)二、交易池交易池是一个节点存储交易的容器，无论是本节点创建的交易还是其他节点广播过来的交易，都会缓存在交易池中，当需要生成区块时，就从交易池中选择合适的交易打包成块，经由共识最终确认生成新的区块。另外交易池配置限定了交易的gas价格下限、每个账户可保留的交易数、交易最大排队时间等等，一定程度控制了交易池的大小。数据定义：type TxPool struct { config TxPoolConfig //交易池配置 chainconfig *params.ChainConfig //区块链配置 chain blockChain //区块链接口 gasPrice *big.Int //交易池gas价格下限 txFeed event.Feed //交易订阅器 scope event.SubscriptionScope //订阅范围，可以批量关闭订阅 signer types.Signer //交易签名者接口，用于从交易解析发送者 mu sync.RWMutex //读写锁 currentState *state.StateDB //当前区块链的世界状态（包括普通账户和合约账户）， pendingNonces *txNoncer //Pending状态交易的nonce，如果没有就从currentState取 currentMaxGas uint64 //当前最大交易gasLimit locals *accountSet //本地账户集合，可以避免被踢出交易池 journal *txJournal //备份到磁盘的本地交易记录 pending map[common.Address]*txList //所有当前可处理的交易 queue map[common.Address]*txList //所有当前等待处理的交易 beats map[common.Address]time.Time //每个已知帐户的最后一次心跳 all *txLookup //所有交易集合，按哈希索引并加锁 priced *txPricedList //按价格排序的所有交易 chainHeadCh chan ChainHeadEvent //新区块事件通道 chainHeadSub event.Subscription //新区块事件订阅器 reqResetCh chan *txpoolResetRequest //重置交易池请求通道 reqPromoteCh chan *accountSet //账户提升请求通道，升级为本地账户 queueTxEventCh chan *types.Transaction //新交易事件，放入成员queue中，等待处理 reorgDoneCh chan chan struct{} //重新排序完成 reorgShutdownCh chan struct{} //重新排序终止 wg sync.WaitGroup //等待一组操作完成 } type txList struct { strict bool //nonce值是否严格连续 txs *txSortedMap //已排序的交易集合 costcap *big.Int //最高的交易成本价格（gasprice * gaslimit) gascap uint64 //最高的交易GasLimit } type txLookup struct { all map[common.Hash]*types.Transaction lock sync.RWMutex } type txPricedList struct { all *txLookup items *priceHeap //按价格排序的交易堆 stales int //重构堆阀值 }注解：交易池用于缓存交易，过滤无效交易新的交易会尝试放入pending，否则放入queued，如果queued也不行就舍弃低于设定的gasPrice（节点自行设置）交易会被舍弃交易来源有本地的和远程的，本地的有特权,本地交易会缓存到磁盘中交易池存在内存中，不可能无限大，等超过一定阈值就需要对交易池里面的交易进行清理收到新区块会重构交易池核心方法：func (pool TxPool) validateTx(tx types.Transaction, local bool) errorfunc (pool TxPool) journalTx(from common.Address, tx types.Transaction)func (pool TxPool) AddLocal(tx types.Transaction) errorfunc (pool TxPool) AddRemote(tx types.Transaction) errorfunc (pool *TxPool) Status(hashes []common.Hash) []TxStatusfunc (pool TxPool) Get(hash common.Hash) types.Transactionfunc (pool *TxPool) removeTx(hash common.Hash, outofbound bool)三、收据交易通过evm虚拟机执行完成之后会产生一些收据（Receipt)，一个交易一个收据并包括多个日志（Log），收据记载的是交易执行的结果。在以太坊虚拟机里，日志代表对事件的存储，主要记录触发的事件及其数据（比如一个代币转账事件，Topics是转账事件的一些签名，Data记录的是谁给谁转多少代币）。type Receipt struct { // 这些字段由黄皮书定义 PostState []byte //执行交易完成后状态树的根 Status uint64 //交易执行结果，成功为1，失败为0 CumulativeGasUsed uint64 //一个区块里执行到此交易（包括）的gas花费 Bloom Bloom //布隆过滤器 Logs []*Log //虚拟机智能合约执行日志 // 这些字段在处理交易时由geth节点添加。它们存储在区块链数据库中 TxHash common.Hash //交易哈希 ContractAddress common.Address //合约地址 GasUsed uint64 //gas消耗 //这些字段提供与此收据对应的交易记录的信息 BlockHash common.Hash //所属区块的哈希 BlockNumber *big.Int //所属区块的高度 TransactionIndex uint //所在交易列表的序号 } type Log struct { Address common.Address //生成日志的合约地址 Topics []common.Hash //日志提供的主题列表 Data []byte //日志提供的数据，通常为abi编码 BlockNumber uint64 //区块高度 TxHash common.Hash //交易哈希 TxIndex uint //交易在区块里的索引 BlockHash common.Hash //区块哈希 Index uint //在区块中的索引 Removed bool //是否已删除 }注解：收据的日志只有执行智能合约的事件才会产生，实质是由虚拟机log指令（LOG0，LOG1，LOG2，LOG3，LOG4)生成的。如果由于链重组日志不需要了，则Removed字段设为true。日志里面topics数组里的第一个元素就是事件的sha3签名，其余的为indexed的参数签名，参考合约ABI文件核心方法：func NewReceipt(root []byte, failed bool, cumulativeGasUsed uint64) *Receiptfunc (r *Receipt) setStatus(postStateOrStatus []byte) errorfunc (r *Receipt) Size() common.StorageSize
0x00 前言 {#0x00}区块链的火热程度一直以直线上升，其中以区块链 2.0 —— 以太坊为代表，不断的为传统行业带来革新，同时也推动区块链技术发展。区块链是一种分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式，这是一个典型的去中心化应用，建立在 p2p 网络之上；本文以学习和分析以太坊运作原理为目的，将以太坊网络架构作为一个切入点，逐步深入分析，最终对以太坊网络架构有个大致的了解。通过学习以太坊网络架构，可以更容易的对网络部分的源码进行审计，便于后续的协议分析，来发现未知的安全隐患；除此之外，目前基于 p2p 网络的成熟的应用非常少，借助分析以太坊网络架构的机会，可以学习一套成熟的 p2p 网络运行架构。本文侧重于数据链路的建立和交互，不涉及网络模块中的节点发现、区块同步、广播等功能模块。0x01 目录Geth 启动网络架构共享密钥RLPXFrameRW 帧RLP 编码LES 协议总结其中第 3、4、5 三个小节是第 2 节「网络架构」的子内容，作为详细的补充。0x02 Geth 启动在介绍以太坊网络架构之前，首先简单分析下 Geth 的整体启动流程，便于后续的理解和分析。以太坊源码目录tree -d -L 1 . ├── accounts 账号相关 ├── bmt 实现二叉merkle树 ├── build 编译生成的程序 ├── cmd geth程序主体 ├── common 工具函数库 ├── consensus 共识算法 ├── console 交互式命令 ├── containers docker 支持相关 ├── contracts 合约相关 ├── core 以太坊核心部分 ├── crypto 加密函数库 ├── dashboard 统计 ├── eth 以太坊协议 ├── ethclient 以太坊RPC客户端 ├── ethdb 底层存储 ├── ethstats 统计报告 ├── event 事件处理 ├── internal RPC调用 ├── les 轻量级子协议 ├── light 轻客户端部分功能 ├── log 日志模块 ├── metrics 服务监控相关 ├── miner 挖矿相关 ├── mobile geth的移动端API ├── node 接口节点 ├── p2p p2p网络协议 ├── params 一些预设参数值 ├── rlp RLP系列化格式 ├── rpc RPC接口 ├── signer 签名相关 ├── swarm 分布式存储 ├── tests 以太坊JSON测试 ├── trie Merkle Patricia实现 ├── vendor 一些扩展库 └── whisper 分布式消息 35 directories 初始化工作Geth 的 main() 函数非常的简洁，通过 app.Run() 来启动程序：[./cmd/geth/main.go] func main() { if err := app.Run(os.Args); err != nil { fmt.Fprintln(os.Stderr, err) os.Exit(1) } } 其简洁是得力于 Geth 使用了 gopkg.in/urfave/cli.v1 扩展包，该扩展包用于管理程序的启动，以及命令行解析，其中 app 是该扩展包的一个实例。在 Go 语言中，在有 init() 函数的情况下，会默认先调用 init() 函数，然后再调用 main() 函数；Geth 几乎在 ./cmd/geth/main.go#init() 中完成了所有的初始化操作：设置程序的子命令集，设置程序入口函数等，下面看下init() 函数片段：[./cmd/geth/main.go] func init() { // Initialize the CLI app and start Geth app.Action = geth app.HideVersion = true // we have a command to print the version app.Copyright = "Copyright 2013-2018 The go-ethereum Authors" app.Commands = []cli.Command{ // See chaincmd.go: initCommand, importCommand, exportCommand, importPreimagesCommand, ... } ... } 在以上代码中，预设了 app 实例的值，其中 app.Action = geth 作为 app.Run() 调用的默认函数，而 app.Commands 保存了子命令实例，通过匹配命令行参数可以调用不同的函数(而不调用 app.Action)，使用 Geth 不同的功能，如：开启带控制台的 Geth、使用 Geth 创造创世块等。节点启动流程无论是通过 geth() 函数还是其他的命令行参数启动节点，节点的启动流程大致都是相同的，这里以 geth() 为例：[./cmd/geth/main.go] func geth(ctx *cli.Context) error { node := makeFullNode(ctx) startNode(ctx, node) node.Wait() return nil } 其中 makeFullNode() 函数将返回一个节点实例，然后通过 startNode() 启动。在 Geth 中，每一个功能模块都被视为一个服务，每一个服务的正常运行驱动着 Geth 的各项功能；makeFullNode() 通过解析命令行参数，注册指定的服务。以下是 makeFullNode() 代码片段：[./cmd/geth/config.go] func makeFullNode(ctx *cli.Context) *node.Node { stack, cfg := makeConfigNode(ctx) utils.RegisterEthService(stack, &cfg.Eth) if ctx.GlobalBool(utils.DashboardEnabledFlag.Name) { utils.RegisterDashboardService(stack, &cfg.Dashboard, gitCommit) } ... // Add the Ethereum Stats daemon if requested. if cfg.Ethstats.URL != "" { utils.RegisterEthStatsService(stack, cfg.Ethstats.URL) } return stack } 然后通过 startNode() 启动各项服务并运行节点。以下是 Geth 启动流程图：每个服务正常运行，相互协作，构成了 Geth：0x03 网络架构通过 main() 函数的调用，最终启动了 p2p 网络，这一小节对网络架构做详细的分析。三层架构 以太坊是去中心化的数字货币系统，天然适用 p2p 通信架构，并且在其上还支持了多种协议。在以太坊中，p2p 作为通信链路，用于负载上层协议的传输，可以将其分为三层结构：最上层是以太坊中各个协议的具体实现，如 eth 协议、les 协议。第二层是以太坊中的 p2p通信链路层，主要负责启动监听、处理新加入连接或维护连接，为上层协议提供了信道。最下面的一层，是由 Go 语言所提供的网络 IO 层，也就是对 TCP/IP中的网络层及以下的封装。p2p 通信链路层 从最下层开始逐步分析，第三层是由 Go 语言所封装的网络 IO 层，这里就跳过了，直接分析 p2p 通信链路层。p2p 通信链路层主要做了三项工作：由上层协议的数据交付给 p2p 层后，首先通过 RLP 编码。RLP 编码后的数据将由共享密钥进行加密，保证通信过程中数据的安全。最后，将数据流转换为 RLPXFrameRW 帧，便于数据的加密传输和解析。(以上三点由下文做分析)p2p 源码分析 p2p 同样作为 Geth 中的一项服务，通过「0x03 Geth 启动」中 startNode()启动，p2p 通过其 Start() 函数启动。以下是 Start() 函数代码片段：[./p2p/server.go] func (srv *Server) Start() (err error) { ... if !srv.NoDiscovery { ... } if srv.DiscoveryV5 { ... } ... // listen/dial if srv.ListenAddr != "" { if err := srv.startListening(); err != nil { return err } } ... go srv.run(dialer) ... } 上述代码中，设置了 p2p 服务的基础参数，并根据用户参数开启节点发现(节点发现不在本文的讨论范围内)，随后开启 p2p 服务监听，最后开启单独的协程用于处理报文。以下分为服务监听和报文处理两个模块来分析。服务监听通过 startListening() 的调用进入到服务监听的流程中，随后在该函数中调用 listenLoop 用一个无限循环处理接受连接，随后通过 SetupConn() 函数为正常的连接建立 p2p 通信链路。在 SetupConn() 中调用 setupConn() 来做具体工作，以下是 setupConn() 的代码片段：[./p2p/server.go] func (srv *Server) setupConn(c *conn, flags connFlag, dialDest *discover.Node) error { ... if c.id, err = c.doEncHandshake(srv.PrivateKey, dialDest); err != nil { srv.log.Trace("Failed RLPx handshake", "addr", c.fd.RemoteAddr(), "conn", c.flags, "err", err) return err } ... phs, err := c.doProtoHandshake(srv.ourHandshake) ... } setupConn() 函数中主要由 doEncHandshake() 函数与客户端交换密钥，并生成临时共享密钥，用于本次通信加密，并创建一个帧处理器 RLPXFrameRW；再调用 doProtoHandshake() 函数为本次通信协商遵循的规则和事务，包含版本号、名称、容量、端口号等信息。在成功建立通信链路，完成协议握手后，处理流程转移到报文处理模块。下面是服务监听函数调用流程：报文处理p2p.Start() 通过调用 run() 函数处理报文，run() 函数用无限循环等待事务，比如上文中，新连接完成握手包后，将由该函数来负责。run() 函数中支持多个命令的处理，包含的命令有服务退出清理、发送握手包、添加新节点、删除节点等。以下是 run() 函数结构：[./p2p/server.go] func (srv *Server) run(dialstate dialer) { ... for { select { case <-srv.quit: ... case n := <-srv.addstatic: ... case n := <-srv.removestatic: ... case op := <-srv.peerOp: ... case t := <-taskdone: ... case c := <-srv.posthandshake: ... case c := <-srv.addpeer: ... case pd := <-srv.delpeer: ... } } } 为了理清整个网络架构，本文直接讨论 addpeer 分支：当一个新节点添加服务器节点时，将进入到该分支下，根据之前的握手信息，为上层协议生成实例，然后调用 runPeer()，最终通过 p.run() 进入报文的处理流程中。继续分析 p.run() 函数，其开启了读取数据和 ping 两个协程，用于处理接收报文和维持连接，随后通过调用 startProtocols() 函数，调用指定协议的 Run() 函数，进入具体协议的处理流程。下面是报文处理函数调用流程p2p 通信链路交互流程这里整体看下p2p通信链路的处理流程，以及对数据包的封装。0x04 共享密钥在 p2p通信链路的建立过程中，第一步就是协商共享密钥，该小节说明下密钥的生成过程。迪菲-赫尔曼密钥交换 p2p 网络中使用到的是「迪菲-赫尔曼密钥交换」技术[1]。迪菲-赫尔曼密钥交换（英语：Diffie–Hellman key exchange，缩写为D-H）是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。简单来说，链接的两方生成随机的私钥，通过随机的私钥得到公钥。然后双方交换各自的公钥，这样双方都可以通过自己随机的私钥和对方的公钥来生成一个同样的共享密钥(shared-secret)。后续的通讯使用这个共享密钥作为对称加密算法的密钥。其中对于A、B公私钥对满足这样的数学等式：ECDH(A私钥, B公钥) == ECDH(B私钥, A公钥)。共享密钥生成 在 p2p 网络中由 doEncHandshake()方法完成密钥的交换和共享密钥的生成工作。下面是该函数的代码片段：[./p2p/rlpx.go] func (t *rlpx) doEncHandshake(prv *ecdsa.PrivateKey, dial *discover.Node) (discover.NodeID, error) { ... if dial == nil { sec, err = receiverEncHandshake(t.fd, prv, nil) } else { sec, err = initiatorEncHandshake(t.fd, prv, dial.ID, nil) } ... t.rw = newRLPXFrameRW(t.fd, sec) .. } 如果作为服务端监听连接，收到新连接后调用 receiverEncHandshake() 函数，若作为客户端向服务端发起请求，则调用initiatorEncHandshake()函数；两个函数区别不大，都将交换密钥，并生成共享密钥，initiatorEncHandshake() 仅仅是作为发起数据的一端；最终执行完后，调用 newRLPXFrameRW() 创建帧处理器。从服务端的角度来看，将调用 receiverEncHandshake()函数来创建共享密钥，以下是该函数的代码片段：[./p2p/rlpx.go] func receiverEncHandshake(conn io.ReadWriter, prv *ecdsa.PrivateKey, token []byte) (s secrets, err error) { authPacket, err := readHandshakeMsg(authMsg, encAuthMsgLen, prv, conn) ... authRespMsg, err := h.makeAuthResp() ... if _, err = conn.Write(authRespPacket); err != nil { return s, err } return h.secrets(authPacket, authRespPacket) } 共享密钥生成的过程：在完成 TCP 连接后，客户端使用服务端的公钥(node\_id)加密，发送自己的公钥和包含临时公钥的签名，还有一个随机值nonce。服务端收到数据，获得客户端的公钥，使用椭圆曲线算法从签名中获得客户端的临时公钥；服务端将自己的临时公钥和随机值nonce 用客户端的公钥加密发送。通过上述两步的密钥交换后，对于客户端目前有自己的临时公私钥对和服务端的临时公钥，使用椭圆曲线算法从自己的临时私钥和服务端的临时公钥计算得出共享密钥；同理，服务端按照相同的方式也可以计算出共享密钥。以下是共享密钥生成图示：得出共享密钥后，客户端和服务端就可以使用共享密钥做对称加密，完成对通信的加密。0x05 RLPXFrameRW 帧在共享密钥生成完毕后，初始化了 RLPXFrameRW 帧处理器；其 RLPXFrameRW帧的目的是为了在单个连接上支持多路复用协议。其次，由于帧分组的消息为加密数据流产生了天然的分界点，更便于数据的解析，除此之外，还可以对发送的数据进行验证。RLPXFrameRW 帧包含了两个主要函数，WriteMsg()用于发送数据，ReadMsg()用于读取数据；以下是 WriteMsg() 的代码片段：[./p2p/rlpx.go] func (rw *rlpxFrameRW) WriteMsg(msg Msg) error { ... // write header headbuf := make([]byte, 32) ... // write header MAC copy(headbuf[16:], updateMAC(rw.egressMAC, rw.macCipher, headbuf[:16])) if _, err := rw.conn.Write(headbuf); err != nil { return err } // write encrypted frame, updating the egress MAC hash with // the data written to conn. tee := cipher.StreamWriter{S: rw.enc, W: io.MultiWriter(rw.conn, rw.egressMAC)} if _, err := tee.Write(ptype); err != nil { return err } if _, err := io.Copy(tee, msg.Payload); err != nil { return err } if padding := fsize % 16; padding > 0 { if _, err := tee.Write(zero16[:16-padding]); err != nil { return err } } // write frame MAC. egress MAC hash is up to date because // frame content was written to it as well. fmacseed := rw.egressMAC.Sum(nil) mac := updateMAC(rw.egressMAC, rw.macCipher, fmacseed) _, err := rw.conn.Write(mac) return err } 结合以太坊 RLPX 的文档[2]和上述代码，可以分析出 RLPXFrameRW帧的结构。在一般情况下，发送一次数据将产生五个数据包：header // 包含数据包大小和数据包源协议 header_mac // 头部消息认证 frame // 具体传输的内容 padding // 使帧按字节对齐 frame_mac // 用于消息认证 接收方按照同样的格式对数据包进行解析和验证。0x06 RLP 编码RLP编码 (递归长度前缀编码)提供了一种适用于任意二进制数据数组的编码，RLP已经成为以太坊中对对象进行序列化的主要编码方式，便于对数据结构的解析。比起json 数据格式，RLP 编码使用更少的字节。在以太坊的网络模块中，所有的上层协议的数据包要交互给 p2p链路时，都要首先通过 RLP 编码；从 p2p 链路读取数据，也要先进行解码才能操作。以太坊中 RLP 的编码规则[3]。0x07 LES 协议层这里以 LES 协议为上层协议的代表，分析在以太坊网络架构中应用协议的工作原理。LES 服务由 Geth 初始化时启动，调用源码 les 下的 NewLesServer()函数开启一个 LES 服务并初始化，并通过 NewProtocolManager()实现以太坊子协议的接口函数。其中 les/handle.go 包含了 LES 服务交互的大部分逻辑。回顾上文 p2p 网络架构，最终 p2p 底层通过 p.Run() 启动协议，在 LES 协议中，也就是调用 LES 协议的 Run() 函数：[./les/handle.go#NewProtocolManager()] Run: func(p *p2p.Peer, rw p2p.MsgReadWriter) error { ... select { case manager.newPeerCh <- peer: ... err := manager.handle(peer) ... case <-manager.quitSync: ... } } 可以看到重要的处理逻辑都被包含在 handle() 函数中，handle() 函数的主要功能包含 LES 协议握手和消息处理，下面是 handle() 函数片段：[./les/handle.go] func (pm *ProtocolManager) handle(p *peer) error { ... if err := p.Handshake(td, hash, number, genesis.Hash(), pm.server); err != nil { p.Log().Debug("Light Ethereum handshake failed", "err", err) return err } ... for { if err := pm.handleMsg(p); err != nil { p.Log().Debug("Light Ethereum message handling failed", "err", err) return err } } } 在 handle() 函数中首先进行协议握手，其实现函数是 ./les/peer.go#Handshake()，通过服务端和客户端交换握手包，互相获取信息，其中包含有：协议版本、网络号、区块头哈希、创世块哈希等值。随后用无线循环处理通信的数据，以下是报文处理的逻辑：[./les/handle.go] func (pm *ProtocolManager) handleMsg(p *peer) error { msg, err := p.rw.ReadMsg() ... switch msg.Code { case StatusMsg: ... case AnnounceMsg: ... case GetBlockHeadersMsg: ... case BlockHeadersMsg: ... case GetBlockBodiesMsg: ... ... } } 处理一个请求的详细流程是：使用 RLPXFrameRW 帧处理器，获取请求的数据。使用共享密钥解密数据。使用 RLP 编码将二进制数据序列化。通过对 msg.Code 的判断，执行相应的功能。对响应数据进行 RLP 编码，共享密钥加密，转换为 RLPXFrameRW，最后发送给请求方。下面是LES协议处理流程：0x08 总结通过本文的分析，对以太坊网络架构有了大致的了解，便于后续的分析和代码审计；在安全方面来讲，由协议所带的安全问题往往比本地的安全问题更为严重，应该对网络层面的安全问题给予更高的关注。从本文也可以看到，以太坊网络架构非常的完善，具有极高的鲁棒性，这也证明了以太坊是可以被市场所认可的区块链系统。除此之外，由于 p2p 网络方向的资料较少，以太坊的网络架构也可以作为学习 p2p 网络的资料。针对目前主流的以太坊应用，知道创宇提供专业权威的智能合约审计服务，规避因合约安全问题导致的财产损失，为各类以太坊应用安全保驾护航。
accounts 实现了钱包帐户管理build 编译脚本和配置cmd 命令行工具abigen 合约接口生成bootnode 实现网络发现的引导节点clef 钱包账户管理ethkey 私钥管理evm 以太坊虚拟机geth 以太坊命令行客户端p2psim 提供了一个工具来模拟http的APIpuppeth 创建一个新的以太坊网络的向导rlpdump 提供RLP数据的格式化输出util 命令行公共的组件wnode 一个简单的Whisper节点common 提供了一些公共的工具类consensus 共识协议，包括pow和posconsole 交互式命令core 以太坊核心h数据结构和算法（虚拟机、状态、区块链、）crypto 加密和哈希函数库dashboard 统计eth 以太坊协议ethclient 以太坊RPC客户端ethdb eth的数据库，最底层的存储ethstats 统计报告event 事件处理graphql 节点数据的graphql接口internal RPC调用les 轻量级子协议light 轻客户端部分功能log 日志模块metrics 提供磁盘计数器miner 挖矿相关mobile geth的移动端APInode 接口节点p2p p2p网络协议params 一些预设参数值rlp RLP系列化格式rpc RPC接口signer 签名相关swarm 分布式存储tests 以太坊JSON测试trie MPT树实现vendor 引用扩展库打包whisper 分布式消息协议
RLP(Recursive Length Prefix，递归的长度前缀)是一种编码规则，可用于编码任意嵌套的二进制数组数据。RLP编码的结果也是二进制序列。RLP主要用来序列化/反序列化数据。一、RLP数据定义RLP编码的定义只处理以下2类底层数据：字符串（String）是指字节数组列表（List）是指字节数组的数组所有上层类型的数据需要转成以上的2类数据，才能进行RLP编码。转换的规则RLP编码不统一规定，可以自定义转换规则。从上面的数据类型定义中可以看出，RLP编码的数据可看做字节数组和多维变长字节数组。二、编码规则RLP编码的重点是给原始数据前面添加若干字节的前缀，而且这个前缀是和数据的长度相关的，并且是递归的。1.针对单字节b，b ∈ [0,127], Rc(b) = beg:Rc(a) = 97, Rc(w) = 119**2.针对字节数组bytes，length(bytes) <= 55, Rc(bytes) =128+length(bytes) ++ bytes(++符号表示拼接)**eg:Rc(abc) = [131 97 98 99], 其中131 = 128+length(abc), [97 9899]为[abc]本身编码**3.针对字节数组bytes，length(bytes) > 55, Rc(bytes) = 183+sizeof(sizeof(bytes)) ++ Rc(sizeof(bytes)) + bytes**eg: str = "The length of this sentence is more than 55 bytes, I knowit because I pre-designed it" Rc(str) = [184 86 84 104 101 32 108 101 110 103 116 104 32 111102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 3273 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32112 114 101 45 100 101 115 105 103 110 101 100 32 105 116] 经计算该字符串占用字节数为86，显然184 = 183 + sizeof(86)，86 =sizeof(str), 84为“T”的编码，从84开始后面便是str本身的编码。以上是针对字节数组，接下来看以字节数组为元素的数组，这里称之为列表的编码方式：首先要明确几个概念，针对一个列表list，lenL是指list内每个bytes字节数的总和，lenDl是指list每个bytes经过Rc(x)编码后的总长度。**lenL(list) =) lenDl(list) =))****4.针对list[bytes0, bytes1...bytesN]，lenL(list) \<= 55,\ Rc(list) = 192+lenDl(list) ++Rc()**eg: list = ["abc", "def"],\ Rc(list) = [200 131 97 98 99 131 100 101 102]\ 首先，lenL(list) = 3+3 \<= 55,\ 然后，根据规则3可以得出：\ Rc[abc] = [131 97 98 99]，\ Rc[def] = 131 100 101 102\ 现在就知道，lenDl(list) = 4 + 4 =8，所以开始的200就是192+8的结构，后面跟的是list里每个bytes的RLP编码。**5.针对list[bytes0, bytes1...bytesN]，lenL(list) \> 55,\ Rc(list) = 247+sizeof(lenDl(list)) ++ lenDl(list) ++Rc()**eg: list = ["The length of this sentence is more than 55 bytes,",\ " I know it because I pre-designed it"]\ Rc(list) = [248 88 179 84 104 101 32 108 101 110 103 116 104 32 111102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 3273 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116]\ 首先，lenL(list) = 51+35 = 86 \> 55,\ 然后，根据规则2可以得出：\ Rc[The length of this sentence is more than 55 bytes,] = [179 84104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97110 32 53 53 32 98 121 116 101 115 44 32](179 = 128 + 51)，\ Rc[ I know it because I pre-designed it]\ = [163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 10132 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116](163= 128 + 35)\ 现在就知道，lenDl(list) = 52 + 36 =88，88只需占1个字节即可，所以开始的248就是247+1的结构，后面的88是lenDl(list)本身的编码，再后面跟的是list里每个bytes的RLP编码。RLP解码我们知道，有编码就有解码。编码是解码的一个逆过程，我们发现在编码的时候不同的情况都有一个不同的字节前缀，所以解码的时候也是从这个字节前缀入手。设定Dr(x)为解码函数，s为x的第一个字节。\ subX[m,n]表示x的子串，从x的第m个开始取n个字节。\bin2Int(bytes)表示将一个字节数组按BigEndian编码转换为整数，目的在于求出被编码字符串长度。**1. s ∈ [0, 127], 对应编码规则1单字节解码，\ Dr(x) = x****2. s ∈ [128, 184), 对应编码规则2，数组长度不超过55\ Dr(x) = subX[2, s-128]****3. s ∈ [184, 192), 对应编码规则3，数组长度超过55\ bin2Int(subX[1, s-183])为被编码数组的长度\ Dr(x) = subX[bin2Int(subX[1, s-183]+1, bin2Int(subX[1, s-183])]****4. s ∈ [192, 247), 对应编码规则4，总长不超过55的列表 列表总长lenDl =s-192，然后递归调用解码规则1-3即可\ Dr(x) = ![\sum\_{i=0}^NspliceOf(Dr(x\_i))](https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D0%7D%5E%20NspliceOf(Dr(x_i)))****5. s ∈ [247, 256], 对应编码规则5，总长超过55的列表,列表总长lenDl =bin2Int(subX[1, s-247])，然后递归调用解码规则1-3即可\ Dr(x) = ![\sum\_{i=0}^NspliceOf(Dr(x\_i))](https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D0%7D%5E%20NspliceOf(Dr(x_i)))**RLP源码上面大概了解了RLP的编解码方式，下面我们就到eth源代码中去看看有关RLP的代码是怎么写的。上篇文章主要介绍了geth源码结构，RLP源码主要在rlp目录下。RLP源码结构typeCache.go该结构主要实现不同类型和对应编解码器的映射关系，通过它去获取对应的编解码器。核心数据结构// 核心数据结构 var ( typeCacheMutex sync.RWMutex // 读写锁，用于在多线程时保护typeCache typeCache = make(map[typekey]*typeinfo) // 保存类型 -> 编码器函数的数据结构 // Map的key是类型，value是对应的编码和解码器 ) type typeinfo struct { decoder // 解码器函数 writer // 编码器函数 }如何获取编码器和解码器的函数// 获取编码器和解码器的函数 func cachedTypeInfo(typ reflect.Type, tags tags) (*typeinfo, error) { typeCacheMutex.RLock() // 加锁保护 info := typeCache[typekey{typ, tags}] // 将传入的typ和tags封装为typekey类型 typeCacheMutex.RUnlock() // 解锁 if info != nil { // 成功获取到typ对应的编解码函数 return info, nil } // not in the cache, need to generate info for this type. // 编解码不在typeCache中，需要创建该typ对应的编解码函数 typeCacheMutex.Lock() defer typeCacheMutex.Unlock() return cachedTypeInfo1(typ, tags) } // 新建typ对应的编解码函数 func cachedTypeInfo1(typ reflect.Type, tags tags) (*typeinfo, error) { key := typekey{typ, tags} info := typeCache[key] if info != nil { // another goroutine got the write lock first /// 其他线程已经成功创建 return info, nil } // put a dummmy value into the cache before generating. // if the generator tries to lookup itself, it will get // the dummy value and won't call itself recursively. // 这个地方首先创建了一个值来填充这个类型的位置，避免遇到一些递归定义的数据类型形成死循环 typeCache[key] = new(typeinfo) info, err := genTypeInfo(typ, tags) // 生成对应类型的编解码器函数 if err != nil { // remove the dummy value if the generator fails // 创建失败处理 delete(typeCache, key) return nil, err } *typeCache[key] = *info return typeCache[key], err }生成对应编解码器的函数// 生成对应编解码器的函数 func genTypeInfo(typ reflect.Type, tags tags) (info *typeinfo, err error) { info = new(typeinfo) if info.decoder, err = makeDecoder(typ, tags); err != nil { return nil, err } if info.writer, err = makeWriter(typ, tags); err != nil { return nil, err } return info, nil }decode.gotypeCache定义了类型与对应解编码器的映射关系，接下来就看看对应的编码和解码代码。// 定义一些解码错误 var ( // EOL is returned when the end of the current list // has been reached during streaming. EOL = errors.New("rlp: end of list") // Actual Errors ErrExpectedString = errors.New("rlp: expected String or Byte") ErrExpectedList = errors.New("rlp: expected List") ErrCanonInt = errors.New("rlp: non-canonical integer format") ErrCanonSize = errors.New("rlp: non-canonical size information") ErrElemTooLarge = errors.New("rlp: element is larger than containing list") ErrValueTooLarge = errors.New("rlp: value size exceeds available input length") ErrMoreThanOneValue = errors.New("rlp: input contains more than one value") // internal errors errNotInList = errors.New("rlp: call of ListEnd outside of any list") errNotAtEOL = errors.New("rlp: call of ListEnd not positioned at EOL") errUintOverflow = errors.New("rlp: uint overflow") errNoPointer = errors.New("rlp: interface given to Decode must be a pointer") errDecodeIntoNil = errors.New("rlp: pointer given to Decode must not be nil") )// 解码器 根据不同的类型返回对应的解码器函数 func makeDecoder(typ reflect.Type, tags tags) (dec decoder, err error) { kind := typ.Kind() switch { case typ == rawValueType: return decodeRawValue, nil case typ.Implements(decoderInterface): return decodeDecoder, nil case kind != reflect.Ptr && reflect.PtrTo(typ).Implements(decoderInterface): return decodeDecoderNoPtr, nil case typ.AssignableTo(reflect.PtrTo(bigInt)): return decodeBigInt, nil case typ.AssignableTo(bigInt): return decodeBigIntNoPtr, nil case isUint(kind): return decodeUint, nil case kind == reflect.Bool: return decodeBool, nil case kind == reflect.String: return decodeString, nil case kind == reflect.Slice || kind == reflect.Array: return makeListDecoder(typ, tags) case kind == reflect.Struct: return makeStructDecoder(typ) case kind == reflect.Ptr: if tags.nilOK { return makeOptionalPtrDecoder(typ) } return makePtrDecoder(typ) case kind == reflect.Interface: return decodeInterface, nil default: return nil, fmt.Errorf("rlp: type %v is not RLP-serializable", typ) } }根据以上switch方法可以调到各种解码函数。encode.go接下来来看看有关编码的代码解读。首先定义了两种特殊情况下的编码方式。var ( // Common encoded values. // These are useful when implementing EncodeRLP. EmptyString = []byte{0x80} // 针对空字符串的编码 EmptyList = []byte{0xC0} // 针对空列表的编码 )接着定义了一个接口EncodeRLP供调用，但是很多情况下EncodeRLP会调用Encode方法。type Encoder interface { // EncodeRLP should write the RLP encoding of its receiver to w. // If the implementation is a pointer method, it may also be // called for nil pointers. // // Implementations should generate valid RLP. The data written is // not verified at the moment, but a future version might. It is // recommended to write only a single value but writing multiple // values or no value at all is also permitted. EncodeRLP(io.Writer) error }func Encode(w io.Writer, val interface{}) error { if outer, ok := w.(*encbuf); ok { // Encode was called by some type's EncodeRLP. // Avoid copying by writing to the outer encbuf directly. return outer.encode(val) } eb := encbufPool.Get().(*encbuf) // 获取一个编码缓冲区encbuf defer encbufPool.Put(eb) eb.reset() if err := eb.encode(val); err != nil { return err } return eb.toWriter(w) }func (w *encbuf) encode(val interface{}) error { rval := reflect.ValueOf(val) ti, err := cachedTypeInfo(rval.Type(), tags{}) if err != nil { return err } return ti.writer(rval, w) }makeWriter作为一个switch形式的编码函数和上面的makeDecoder类似。
引言MPT树（Merkle Patricia Tree）是以太坊中一种非常重要的数据结构，用来存储用户账户的状态及其变更（状态树）、交易信息（交易树）、交易的收据信息（收据树）。它实际上是Merkle Tree和Patricia Tree组合而成的一种树形结构，并且同时具备这两种树的特性和优点。我们期望从原理和源代码两方面入手，以期对其进行深入的了解。实现原理以Patricia Tree为基础，以太坊主要从以下几个方面对其进行了改进和优化。使用[]byte作为key的类型，而非字符串在以太坊的Trie模块中，key和value都是[]byte类型。如果要使用其它类型，需要将其转换成[]byte类型（比如使用rlp进行转换）。当然这不是什么本质上改变，我个人感觉只是为了编码方便吧。因为rlp模块可以方便的把各种结构序列化成[]byte而不是string。nibble: key类型的最小单位其实在以太坊的Trie模块对外提供的接口中，key类型当然是[]byte。但在内部实现里，将key中的每个字节按高4位和低4位拆分成了两个字节。比如你传入的key是：[0x1a, 0x2b, 0x3c, 0x4d]Trie内部将这个key拆分成：[0x1, 0xa, 0x2, 0xb, 0x3, 0xc, 0x4, 0xd]Trie内部的编码中将拆分后的每一个字节称为nibble如果使用一个完整的byte作为key的最小单位，那么前文提到的索引数组的大小应该是256（byte作为数组的索引，最大值为255，最小值为0）。而索引数组的每个元素都是一个32字节的哈希（这在下一条中进行了说明）,这样每个结点要占用大量的空间。并且索引数组中的元素多数情况下是空的，不指向任何结点。因此这种实现方法占用大量空间而不使用。以太坊的改进方法，可以将索引数组的大小降为16（4个bit的最大值为0xF，最小值为0），因此大大减少空间的浪费。使用hash引用结点而不是内存指针在以太坊的实现中，索引数组的每个元素都是下一个结点的hash，而非指针。也就是说，父结点持有的是子结点的hash。这种实现方式使得以太坊中的Trie带有了默克尔树的功能：如果两个Trie的根结点的hash相同，我们就可以断定，这两棵树的内容完全一样。需要注意的是，这种实现也包括对value的引用。也就是说在以太坊的Trie中，遍历到叶子结点以后得到的是value的hash，而非value本身。使用这个hash从数据库中读取出来的值才是value。当树的某条路径没有分支时，使用一个结点存储路径上的所有key我们回看上面介绍字典树的那张图，其中"medicine"这条路径中，除了前三个字符'med'，其它字符都没有分支，因此为了节省空间，以太坊将这种情况下的结点缩减为一个。如下图所示：这样就可以进一步节省空间的开销。但同时也产生了一个问题：对于某个结点，如何知道它存储的是索引数组，还是key的数组呢？以太坊解决这个问题的方式是通过结点元素个数的不同进行区分。以太坊在Trie内部将结点分成了两类：全节点（fullNode）和快捷节点（shortNode）。全节点有17个元素，而快捷结点有两个元素。它们的示意表达如下：全结点： [i0, i2, ... i15, value]快捷结点：[ [k0, k1, ... kn], value ]可以看到全结点由索引数组（共16个元素）和一个value组成（前面说过value的引用也是通过hash，而不是直接存储value的值）；而快捷结点有2个元素，一个是key数组，另一个就是value。此时虽然可以知道一个结点存储的数据的格式，但对于快捷结点，仍有两个问题没有解决。一个问题是，前面说过key的最小单位是nibble，。那么如果在快捷结点中nibble的个数是奇数，它重新组合成[]byte存储就会有麻烦。比如nibbles: 0x1 0xa 0x2 0xb 0x3\ 组合成[]byte？ 0x1a 0x2b 0x30 还是 0x01 0xa2 0xb3可见无论怎么组合，都会有多写入一个无效的nibble。等再解析的时候，我们怎么知道哪个是无效的呢？另一个问题是，我们该如何解析快捷结点中的value所代表的数据。它是代表真正的value数据，还是另一个结点？这两个问题存在的原因在于，Trie中的结点是需要进行数据库存取的。如果只是在内存中，这两个问题不会存在：只在内存中没有必要把nibble组成的key变成[]byte类型；通过数据的结构体类型也很容易知道value所代表的数据类型。但要将快捷结点存入数据库中，需要将nibble组成的key变成[]byte存储（其实也可以直接存储nibble数组，只是多占了一倍空间）；而从数据库中读取value所代表的数据时，需要知道是将其解析成一个新的结点，还是仅代表value原始值无需解析。有问题就要解决。既然问题产生于数据库的存取，很自然地我们会想到，可以在存的时候加上一些信息，能标识出哪一位是无效的nibble，和value所代表的数据类型。当从数据库中取的时候，就可以根据这些信息将数据恢复啦。是的，解决的思路都是类似的，只是实现方法千千万。以太坊的实现方法是在存入数据库时，将nibble组合成的[]byte值的第0个字节的高4位作为信息存储位而不存储真正的nibble字节。可以说这种方法真是一点内存都不浪费。那么第0个字节的高4位是怎么组织的呢？目前我们有两个信息需要存储：nibble的个数的奇偶信息value代表结点还是真正的value数据可以看到这俩个信息都是二元的（非此即彼），因此有2个bit就可以了。以太坊的做法是第0位存储奇偶信息，第1位存储value代表的类型。具体信息如下：hex charbitsvalue代表类型nibble个数奇偶低4位是否有效00000结点偶数无效10001结点奇数有效，第一个nibble20010数据偶数无效30011数据奇数有效，第一个nibble可以看到当nibble个数为偶数时，第0个字节的低4位总是无效的；但为奇数时，低4位是有效的，其值为第一个nibble。让我们通过例子来确认对这些描述的理解。以下示意的都是快捷结点：[ [0xa, 0xb, 0xc, 0xd, 0xe], value_node ] // 奇数个nibble，value代表node 编码： 0x1a 0xbc 0xde [ [0xa, 0xb, 0xc, 0xd], value_node ] //偶数个nibble，value代表node 编码： 0x00 0xab 0xcd [ [0xa, 0xb, 0xc, 0xd, 0xe], value_data ] //奇数个nibble，value代表数据 编码： 0x3a 0xbc 0xde [ [0xa, 0xb, 0xc, 0xd], value_data ] //偶数个nibble，value代表数据 编码： 0x20 0xab 0xcd需要再强调一下的是，这个编码方法只有在数据库存取的时候才用到。在读到内存中以后，nibble是直接以[]byte类型存储的（虽然每个byte的最大值是15）,且如果value代表的是数据则在nibble数组的最后append值16（注意16是一个无效的nibble值，因此可以和正常的nibble值作区分），代码中根据最后一个值是否是16判断value的类型。另外虽然我们一直没有明确说明，但上面在说value代表的类型的时候，我们其实是在判断当前结点是不是叶子结点：如果是叶子结点，value当然代表数据；如果不是，value也当然代表一个node。至此，所有问题都已解决，终于可以正常的将多个没有分支的结点压缩到一个结点存储了（为了解决一个问题，引入了好几个问题）。我们来总结一下我们当前讨论的改进：以太坊通过以下方式，减少无分支路径上的结点数：将结点类型分成了fullNode和shortNode，shortNode存储多个key的nibble使用第0个字节的高4位编码，标识nibble的奇偶个数（也即第0个字节的低4位是否是有效的nibble）和value类型（也即当前结点是否是叶子结点）内部节点引用计数这一改进其实与trie原理本身没有关系，但我认为也是非常重要的，因此有必要在这里介绍一下。在trie模块中，有一个Database对象，你可以理解为它是底层数据库的一个缓存层。在实际使用过程中，Trie对象就把Database作为数据库使用。但Database的重要功能不在于缓存，而在于缓存时对节点数据进行了引用计数，并提供了Database.Reference和Database.Dereference来引用和解引用某个trie节点。如果某个节点的引用计数变为0，则该节点将被从内存中删除，因而也不会被写入到真正的数据库中。注意Database中只对内存中缓存的节点进行了引用计数，已经写入数据库的节点没有引用计数数据。以太坊的trie模块为什么对trie作了这么一个改进呢？这主要是为了解决以太坊数据存储的问题。随着以太坊的长时间运行，以太坊数据已经非常大且仍在以类似指数的速度增长。增长的主要数据，就是以太坊的账户状态（state）信息，而以太坊trie作为state的底层数据组织方式，它的实现决定了这种增长速度。因为在以太坊中，每生成一个新的区块，不会直接修改上一个区块的state数据，而是类似于“写时复制”的机制，将数据修改后重新存储一份，对于trie来说则是生成新的子节点进行存储，如下图所示：以上图为例，只要修改账户X的信息，就需要新增4个节点而不会修改原来的节点（实际情况可能不止4个），这就是state数据增长如此之快的原因。为了减轻数据存储的压力，以太坊提出了修剪区块（prunedblock）的概念，即利用trie模块中的trie.Database对缓存节点进行引用计数，并在blockchain模块中进行相应的引用和解引用操作。如此释放了大量不需要保存的历史数据的存储空间。（关于区块修剪可以参考这里）特性从上面介绍的所有改进我们可以了解到，以太坊的实现非常节省内存。另一个重要的改进是，它与默克尔树进行了融合，在可以高效存取(key,value)对的同时，还具有默克尔树的特性：通过比较两个Trie对象的根结点的hash，就可以判断这两棵树是否存储了相同的内容。默克尔树的这一特性是非常有用的。在以太坊中，Trie用来存储四种对象：StateStorageTransactionsReceipts现在我们可以不必理会这些对象的意义（其实我现在也不是全部了解），但它们在Trie这一层面都是类似的，我们以State举例。以太坊的State存储了区块上所有账号的信息，包括账户余额等。这些账号信息随着区块的变化而变化。在即将打包一个新的区块时，以太坊会更新代表State的Trie对象，并将更新后的Trie根结点hash写入新的区块头中。当其它运行以太坊节点的机器收到这个区块时，它可以根据上一个区块中的State信息，加上新块区的变动后，将得到的Trie的根结点hash与区块头中的进行比较。如果hash一致，则这个区块的State信息就得到了承认。源码分析以太坊trie模块位于项目目录下的trie目录。下面我们先学习下模块导出的功能和用法，然后结合源代码介绍一下目录的组织结构和框架。trie模块使用方法trie模块提供了四个主要的对象和接口：Trie、SecureTrie、NodeIterator、TrieSync、Database。下面分别介绍。TrieTrie对象实现了Merkle Patricia Tree的全部功能，包括(key,value)对的增删改查、计算默克尔哈希，以及将整个树写入数据库中。你可以使用trie.New或trie.NewTrieWithPrefix来创建或打开一个Trie对象。trie.NewTrieWithPrefix相对于trie.New的不同之处在于，你需要提供一个前缀串，每次查询或写入(key,value)对时，都会自动将这个前缀串加到key的前面，然后再执行相应操作。Trie对象提供的方法名都很简洁易懂，几乎所有方法都可以根据名字知道其功能。这里我们只是简单罗列一下，不一一详细说明。func (t *Trie) NodeIterator(start []byte) NodeIteratorfunc (t *Trie) PrefixIterator(prefix []byte) NodeIteratorfunc (t *Trie) Get(key []byte) []bytefunc (t *Trie) TryGet(key []byte) ([]byte, error)func (t *Trie) Update(key, value []byte)func (t *Trie) TryUpdate(key, value []byte)func (t *Trie) Delete(key []byte)func (t *Trie) TryDelete(key []byte) errorfunc (t *Trie) Root() []bytefunc (t *Trie) Hash() common.Hashfunc (t *Trie) Commit() (root common.Hash, err error)func (t *Trie) CommitTo(db DatabaseWriter) (root common.Hash, err error)func (t *Trie) SetCacheLimit(l uint16)func (t *Trie) Prove(key []byte, fromLevel uint, proofDb DatabaseWriter) errorSecureTrieSecureTrie对象实现了Trie相同的功能，实际上它内部几乎都是调用Trie对象的方法实现的。唯一不同的是，SecureTrie中的所有方法会将传入的key计算一个哈希，然后把这个哈希当作key进行操作。因此你无法通过根结点到叶子结点的路径上的信息拼凑出key的内容，这也是它叫作"Secure"的原因。SecureTrie提供的方法与Trie类似，这里不再细说。唯一需要注意的是，对SecureTrie节点进行枚举时，想要获取原始的key值，需要多调用一步SecureTrie.GetKey。因为NodeIterator.LeafKey和Iterator.Key得到的是加密后的key，需要调用SecureTrie.GetKey得到原始key。NodeIteratorNodeIterator是一个接口，如名字所示，它提供了遍历树内部所有结点的功能。它提供的方法如下：func (it NodeIterator) Next(bool) bool\func (it NodeIterator) Error() error\func (it NodeIterator) Hash() common.Hash\func (it NodeIterator) Parent() common.Hash\func (it NodeIterator) Path() []byte\func (it NodeIterator) Leaf() bool\func (it NodeIterator) LeafBlob() []byte\func (it NodeIterator) LeafKey() []byteNodeIterator的核心是Next方法，每调用一次这个方法，NodeIterator对象当前代表的结点就会更新至下一个结点，此时你可以调用其它方法获取这个结点的信息。当所有结点遍历结束，Next方法返回false。所以使用NodeIterator接口的代码一般形式都像这样：for it.Next(true) { ... // 现在it代表一了一个新的结点，你可以调用其它方法如it.Hash等，获取这个结点的信息 }需要注意的是，NodeIterator接口对结点的遍历是有序的。其实Trie就是一棵有序树，而遍历的内部实现就是按照Key从短到长、从小到大的顺序进行的。（然而貌似并没有文档写明并保证遍历是有序的）生成NodeIterator结口的方法有3种。我们分别说明一下。1.调用和Trie.NodeIterator或Trie.PrefixIterator 如果你想遍历某个Trie对象的所有结点，可以调用Trie对象的方法NodeIterator()或PrefixIterator()，这俩个方法都返回一个NodeIterator接口用来进行遍历。NodeIterator()的start参数可以让你有选择的指定从哪个路径开始遍历，如果为nil则从头到尾按顺序遍历。PrefixIterator()方法能过参数指定前缀后，其返回的NodeIterator接口只会遍历路径中包含了你指定前缀的结点。2.调用NewDifferenceIterator NewDifferenceIterator函数的功能如名字所示，只遍历不同的部分。当你调用NewDifferenceIterator(a,b NodeIterator)后，生成的NodeIterator只遍历存在于b但不存在于a中的结点。3.调用NewUnionIterator NewUnionIterator也如名字所示，会把多个NodeIterator当成一个合集进行遍历。当你调用NewUnionIterator(its[]NodeIterator)后，生成的NodeIterator遍历的结点是所有传入的结点的合集。另外我们不得不强调一下NewIterator函数，因为我觉得这个函数更常用到。这个函数用来枚举树中的所有(key,value)对，而不是每个结点（多数情况下我们并不关心中间结点的数据）。这个函数声明如下：func NewIterator(it NodeIterator) *Iterator它并不返回NodeIterator，而是返回Iterator指针对象。Iterator是一个结构体，只有一个方法。定义如下：type Iterator struct { nodeIt NodeIterator Key []byte // Current data key on which the iterator is positioned on Value []byte // Current data value on which the iterator is positioned on Err error } //Iteartor的Next方法 func (it *Iterator) Next() bool可以看到Iterator结构体导出了Key、Value、Err三个字段。每调用一次Next方法，Key、Value和Err字段就会被更新。以下是一段使用NewIterator的示例：//假设tr是一个Trie变量，并且包含了("hi", "lili"), ("hello", "world"), ("good", "morning")三对数据 it := trie.NewIterator(tr.NodeIterator(nil)) for it.Next { if it.Err != nil { fmt.Println(it.Err) continue } fmt.Println(it.Key, it.Value) } //输出： //good morning //hello world //hi lili注意上面例子的三个输出是按Key从小到大排序的，这并非偶然。刚才已经说过NodeIterator的遍历是有序的，因此这里的输出也肯定是有序的。TrieSyncTrieSync不是trie模块的主要功能，应用得也比较少，只在以太坊的downloader模块中用来辅助同步代表State的trie对象。与TrieSync有关的有以下几个方法：func NewTrieSync(root common.Hash, database DatabaseReader, callback TrieSyncLeafCallback) *TrieSync func (s *TrieSync) AddSubTrie(root common.Hash, depth int, parent common.Hash, callback TrieSyncLeafCallback) func (s *TrieSync) AddRawEntry(hash common.Hash, depth int, parent common.Hash) func (s *TrieSync) Missing(max int) []common.Hash func (s *TrieSync) Process(results []SyncResult) (bool, int, error) func (s *TrieSync) Commit(dbw DatabaseWriter) (int, error) func (s *TrieSync) Pending() int其中NewTrieSync用来生成一个新的TrieSync对象并调用AddSubTrie方法为同步root结点作准备。Peinding用来获取当前的Trie对象有几个结点待同步；而Missing则返回待同步结点的哈希。当调用者通过网络获取到这些结点的数据时，它会调用Process进行处理。在Process内部会解析并记录这些结点，如果解析结果表示它们还有子结点，则加入missing和pending队列里。当调用者再次调用Missing方法时，就会获取到这些缺失的子结点的哈希。这样不断循环，直到Pending队列为空，表示所有结点同步完成。整个过程的示意代码如下：trSync := trie.NewTrieSync(root, db, callback) for trSync.Pending() != 0 { missHashs := trSync.Missing(0) results := downloadTrieNode(missHashs) trSync.Process(results) } trSync.Commit(db)我们可以看到TrieSync并不具备同步的功能，它只是对结点的解析和组装。所以我觉得这个名字起得很有迷惑性，如果是我，我会把它叫做TrieBuilder。DatabaseDatabase是trie模块对真正数据库的缓存层，其目的是对缓存的节点进行引用计数，从而实现区块的修剪功能。Database对外提供的方法有：func NewDatabase(diskdb ethdb.Database) *Database func NewDatabaseWithCache(diskdb ethdb.Database, cache int)*Database func (db *Database) DiskDB() DatabaseReader\ func (db *Database) InsertBlob(hash common.Hash, blob []byte)\ func (db *Database) Node(hash common.Hash) ([]byte, error)\ func (db *Database) Nodes() []common.Hash\ func (db *Database) Reference(child common.Hash, parentcommon.Hash)\ func (db *Database) Dereference(root common.Hash)\ func (db *Database) Cap(limit common.StorageSize) error\ func (db *Database) Commit(node common.Hash, report bool) error\ func (db *Database) Size() (common.StorageSize, common.StorageSize)其中NewDatabase或NewDatabaseWithCache用来创建一个Database对象，其参数diskdb是一个数据库接口。在以太坊早期的trie模块中是没有Database对象的，加上这个就是为了增加节点引用计数功能，实现区块的修剪。详细信息我们后面再进行介绍。目录结构trie模块功能的实现代码全部位于以太坊项目的trie目录中，且没有子目录。下面我们对主要的源代码文件作简单的说明。encoding.go\在上篇文章中我们提到过在Trie内部key的最小单位是nibble而不是byte，以及key在从数据库存取的时候是如何编码的。这个文件里的几个函数实现了这两大块功能。（nibble就是将一个byte的高4位和低4位拆成俩字节得到的值，比如将0xab拆成[0xa0xb]，具体请参看trie上篇）hasher.go\hasher.go中的代码实现了从某个结点开始计算子树的哈希的功能。可以说这个文件里的代码实现了以太坊的Trie的默克尔树特性。node.go\在上篇文章中我们介绍过为了缩短无分支路径上的结点数量，以太坊使用了不同的结点类型和结构。这个文件里的代码就是定义了一个Trie树中所有结点的类型和解析的代码。sync.go\ sync.go中的代码实现了前面说的SyncTrie对象的定义和所有方法。iterator.go\ iterator.go中的代码定义了所有枚举相关接口和实现。secure\_trie.go\ secure\_trie.go中的代码实现了SecureTrie对象。errors.go\errors.go中只定义了一个结构体：MissingNodeError。当找不到相应的结点时，就会返回这个错误。proof.go\proof.go中只包含了Prove和VerifyProof两个函数，它们只在轻量级以太坊子协议（LES）中被使用。这两个函数被用来提供自己拥有某一对(key,value)的证明数据，和对数据进行验证。trie.go\ trie.go实现了Trie对象的主要逻辑功能。database.go\ database.go实现了Database对象的主要逻辑功能。实现框架前面我们说过，以太坊的trie模块提供了4个主要的对象和接口：Trie、SecureTrie、SyncTrie和NodeIterator。然而trie模块的核心功能是Trie对象，所以我们这里仅针对Trie作介绍（SecureTrie与Trie是类似的，实际上SecureTrie基本上是调用了Trie的方法）。Trie对象的功能总得来看可以分成两部分：(key,value)的增删改查和Hash与Commit功能。下面我们分别对其介绍。Trie对象的增删改查Trie对象的Get、Update、Delete等方法实现了其增删改查的功能（当然也包含TryXXX等几个类似的方法）。其实Trie对象本质上是一棵树，对于树的增删改查操作，也就是对树的某一路径上所有结点的访问。所以在Get/Delete等方法的实现代码里，主体结构就是对节点类型的typeswitch，并根据不同的节点类型和目的（新增或删除）对节点进行操作。我对这一过程进行了一下规纳，如下图：\从图中可以看出，在key的驱动下，我们循环获取当前部分key所对应的结点（不断的“查字典”），并根据节点类型的不同使用不同的方式获取下一个结点。具体来说，如果是shortNode，则其value存储的是下一个结点；如果是fullNode，则Children数组中存储的是下一个节点------你需要根据key的值来确定到底是数组中的哪个元素；如果是hashNode，则说明这个结点还没有被从数据库中加载，只是存了一个结点哈希而已，因此要先载入并解析，再进行处理；如果是valueNode，则说明找到了key对应的value值，停止查找。从以上的流程中也可以看出，要理解Trie以太坊中Trie的实现，关键要理解这4个结点类型以及它们是如何被使用的。在上篇中我们已经详细介绍过shortNode和fullNode的设计原理，这里我们再结合代码，详细地介绍一下这四个节点以及它们在代码中的用法。在介绍4个结点类型之前，我们必须先说明一下node类型。这是一个接口类型，是4个结点类型的抽象（上面提到的typeswitch就是针对这个node接口类型进行的）。在shortNode和fullNode中，使用node接口代表其子结点，而不管子结点是什么类型。fullNode我们首先来看fullNode的定义：// code in node.go fullNode struct { Children [17]node flags nodeFlag }结构体中flags字段记录了一些结点的其它信息，可以忽略不看，我们重点关注Children字段。上篇中我们提到过根据数据的元素个数来区分fullNode和shortNode类型，这里可以看到Children字段恰好就是一个17个元素的数据（是的，写入数据库时只写入Children，而不写入flags字段）。相信你现在已经可以很好地理解对fullNode的相关操作了。当遇到一个fullNode时，我们将key[pos]作为索引，从Children数组中取出下一个结点。这里不得不提一下key[pos]的值为16的情况。上篇中我们提到过两个情况：一是[]byte类型的key在Trie内部会被转换成nibble数组，并在nibble数组最后添加一个值16代表key已到达结尾（参考keybytesToHex函数）;二是fullNode的17个元素中最后一个元素代表的是value而不是子结点。因此这里如果key[pos]的值是16，则取到的是Children数组的最后一个元素，也就是value。相信到这里，你可以完全理解为什么要在key尾部加一个值，以及为什么这个值是16而不是17或18等其它值。shortNodeshortNode的定义如下：//code in node.go shortNode struct { Key []byte Val node flags nodeFlag }同样的我们忽略flags字段。可以看到shortNode有两个元素：Key和Val，这与我们之前介绍的一致（17个元素的是fullNode，2个元素的是shortNode）。当遇到一个shortNode时，首先要对比key是否有shortNode.Key保存的前缀，如果是则Val字段代表了下一个结点，如果不是，则代表树中根本存在key这条路径。shortNode稍微特殊一点的处理是新加分支。比如一个shortNode的Key保存的是"hello"，现在要新增一个key为"held"，那么就要把shortNode一分为二，中间插入一个fullNode。这个过程虽然麻烦一些但不难理解，我们这里就不详细展开了。hashNodehashNode的定义如下：type hashNode []bytehashNode就是一个简单的byteslice，它的内容就是某个结点的哈希（所以才叫做hashNode）。为什么会有这个结点类型呢？这个类型的存在是由结点从数据库中延迟加载的机制造成的。之前我们说过，Trie的数据是存储在数据库中的。当我们使用某个root哈希创建一个新的Trie对象时，不会将所有子结点都一下子加载到内存中，而是用到再去加载。例如当我们创建新的Trie对象时，会根据root哈希从数据库中加载根结点。假设根结点是一个fullNode，那我们接下来是否要继续将它的16个子结点加载到内存中呢？答案是不需要的，我们只需要让根结点的Children数组保存子结点的哈希（其类型当然是hashNode），在需要时使用这个哈希从数据库中加载，并替换掉原来的哈希。其它结点的处理方法也是这样。这就是hashNode的意义。valueNodevalueNode的定义如下：type valueNode []byte与hashNode类似，valueNode也是一个byteslice。它的意义是代表value数据，而不再是一个结点了（虽然名字里仍有node这个词）。如果在访问结点时遇到这个类型的结点，说明已经找到了key所对应的value。Trie的Hash与CommitTrie的另一个非常有特色的地方在于，它可以做永久性存储，也可以像默克尔树那样，获取根结点的哈希。这一小节里我们对这两个特性做个简单的介绍。其实的树类数据结构想要做永久性存储，面临的问题都差不多。我觉得一个最主要的问题是，在数据库中没有了内存指针，如何对子结点进行引用。解决这个问题的方法有多种，比如为每个结点编号且存储时将指针改为编号；或者像以太坊这样使用结点哈希引用结点。这些方法的道理都是类似的。之所以将这两个功能放在一起讲，也是因为它们内部的实现实际上用的是同一段代码。Trie.Hash和Trie.Commit方法最终都会调用内部方法Trie.hashRoot（Trie对象中还有两个方法Trie.Root和Trie.CommitTo，但与Trie.Hash、Trie.Commit都是一样的代码）。在hashRoot方法中，会调用内部对象hasher的hash方法。这个方法的就是遍历当前树在内存中每一个结点，将所有shortNode和fullNode结点变成hashNode（代码中叫压缩，collapsed）。直接看代码会更容易理解这个过程（下面的代码都是经过简化的，目的是为了更清晰的描述计算Trie的Hash和写入数据库的方法）Trie.Hashfunc (t *Trie) Hash() common.Hash { //注意hashRoot的参数为nil，即只计算哈希不保存到数据库中 hash, cached, _ := t.hashRoot(nil) t.root = cached return hash }Trie.Commitfunc (t *Trie) Commit() (root common.Hash, err error) { hash, cached, err := t.hashRoot(db) t.root = cached return hash }Trie.hashRootfunc (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) { h := newHasher() return h.hash(t.root, db, true) }hasher.hash及相关代码：//hash返回的第一个node为hashNode，第二个node为传入参数n的缓存（其实也可以理解成拷贝） //collapsed为“压缩的”结点，即把正常的shortNode或fullNode变成一个hashNode。 func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, node, error) { collapsed, cached, err := h.hashChildren(n, db) hashed, err := h.store(collapsed, db, force) return hashed, cached, err } //hashChildren与hash类似，返回的第一个node为hashNode，第二个node为传入参数original的缓存 func (h *hasher) hashChildren(original node, db DatabaseWriter) (node, node, error) { switch n := original.(type) { case *shortNode: collapsed := n.copy() collapsed.Key = hexToCompact(n.Key) cached := n.copy() cached.Key = common.CopyBytes(n.Key) if _, ok := n.Val.(valueNode); !ok { collapsed.Val, cached.Val, err = h.hash(n.Val, db, false) } return collapsed, cached, nil case *fullNode: // Hash the full node's children, caching the newly hashed subtrees collapsed, cached := n.copy(), n.copy() for i := 0; i < 16; i++ { collapsed.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false) } cached.Children[16] = n.Children[16] return collapsed, cached, nil default: // Value and hash nodes don't have children so they're left as were return n, original, nil } } //h.store计算collapsed结点的哈希；如果db不为nil，则将collapsed结点保存到db中。 //Trie.Hash和Trie.Commit的区别也仅仅体现在这里。将普通结点变为hashNode这一操作也是 //发生在这里 func (h *hasher) store(n node, db DatabaseWriter, force bool) (node, error) { h.tmp.Reset() if err := rlp.Encode(h.tmp, n); err != nil { panic("encode error: " + err.Error()) } h.sha.Reset() h.sha.Write(h.tmp.Bytes()) hash = hashNode(h.sha.Sum(nil)) //将普通结点转变成对应的hashNode if db != nil { return hash, db.Put(hash, h.tmp.Bytes()) } return hash, nil }注意上面hasher.hash和hasher.hashChildren的实现。这两个方法通过相互的递归调用，从叶子结点开始逐步地将所有结点变成hashNode。其实hasher.hash和hasher.hashChildren始终维护着两棵树，也就是它们的返回值的前两个node。第一棵树是“压缩的”(collapsed)树，这完全是一棵由hashNode组成的树，因此根结点的值也就是整棵树的哈希；第二棵树是原始的树，这样可以防止每次调用Trie.Hash或Trie.Commit后，所有结点都被变成了hashNode，后续再次调用Trie.Get等方法时又得从数据库中重新加载。Database前面我们说过，在早期的以太坊trie版本中是没有Database对象的，后来加上这个对象就是用来实现区块的修剪功能（关于区块的修剪可以参看这里）。那么Database是怎么实现的呢？那就是对内存中的trie树节点进行引用计数，当引用计数为时，从内存中删除此节点。在Database结构体中，对trie树节点实现引用计数功能的字段是dirties，它的类型是map[common.Hash]*cachedNode。其中cachedNode代表的是一个有引用计数的节点，它的定义如下：type cachedNode struct { node node // node接口 size uint16 parents uint32 // 引用当前节点的节点数量 children map[common.Hash]uint16 // 当前节点的子结点的引用计数 flushPrev common.Hash // flush-list列表的字段 flushNext common.Hash }在这个结构体中，parents和children实现了引用计数功能。而flushPrev和flushNext将当前节点加入到了flush-list链表中。insert我们先看看写入节点时会发生什么。当调用trie的Commit方法时，最终会调用Database.insert方法，且Database.InsertBlob其实也是调用insert方法，因此我们从这个方法看起：func (db *Database) insert(hash common.Hash, blob []byte, node node) { //已存在立即返回 if _, ok := db.dirties[hash]; ok { return } //构造cacheNode entry := &cachedNode{ node: simplifyNode(node), size: uint16(len(blob)), flushPrev: db.newest, } //引用子节点，将所有子节点的parents加1 for _, child := range entry.childs() { if c := db.dirties[child]; c != nil { c.parents++ } } db.dirties[hash] = entry //加入flush-list链表 if db.oldest == (common.Hash{}) { db.oldest, db.newest = hash, hash } else { db.dirties[db.newest].flushNext, db.newest = hash, hash } db.dirtiesSize += common.StorageSize(common.HashLength + entry.size) }Database.insert的主要逻辑非常简单，就是构造一个新加入的cacheNode节点，然后增加所有子节点的引用计数（parents字段）。注意这里并没有增加新节点自身的parents计数，因为这里只是往数据库里加入一个新节点，没有证据显示有人引用了这个节点。reference以太坊在进行区块的修剪时会调用Database.Reference和Database.Dereference两个方法。为了分析的完整一些，我们先来看看修剪时的调用：func (bc *BlockChain) writeBlockWithState(block *types.Block, receipts []*types.Receipt, state *state.StateDB) (status WriteStatus, err error) { ...... if bc.cacheConfig.Disabled { ...... } else { triedb.Reference(root, common.Hash{}) // metadata reference to keep trie alive ...... for !bc.triegc.Empty() { ...... triedb.Dereference(root.(common.Hash)) } } }这里先引用一整棵树，经过一些判断和处理，再找合适机会解引用这棵树（详细分析请参看这里）。对节点进行引用的功能主要在Database.reference中实现，我们来看看这个方法：func (db *Database) reference(child common.Hash, parent common.Hash) { //如果child节点不在缓存中，立即返回 node, ok := db.dirties[child] if !ok { return } //如果children字段不存在则构造并继续后面的执行。 //如果children已存在说明已经引用过子节点了，那么如果child变量代表的不是根节点，就直接返回 if db.dirties[parent].children == nil { db.dirties[parent].children = make(map[common.Hash]uint16) } else if _, ok = db.dirties[parent].children[child]; ok && parent != (common.Hash{}) { return } //增加引用计数 node.parents++ db.dirties[parent].children[child]++ }这个方法就是增加child和parent节点的各自的引用计数。但这里有一个特殊的地方，就是如果child已经被parent引用过了，且child代表的不是一个根节点，那么就不继续增加parent对child的引用了；如果child代表一个根节点，还是要继续增加parent对child的引用。这个处理有些难以理解，我们多解释一下。当父节点已经引用过某个子节点时，不再增加对子节点的引用是合理的，因为一个父节点只能引用某个特定的子节点一次，不存在引用多次的情况。但为什么parent为common.Hash{}时，还要继续引用呢？这是因为在调用Database.Reference时，如果child参数是一个根节点，那么parent的值肯定是common.Hash{}，也即common.Hash{}是任一trie树的根节点的父节点；所以这里判断parent是否是common.Hash{}，也就是在判断child参数是否是一个根节点。对根节点的引用与对普通节点引用的不同之处在于，普通节点的引用发生在trie树的内部，因此刚才说了，一个父节点只能引用某个特定的子节点一次；而根节点是可以被trie树以外的地方引用的，比如在miner模块中引用了某个trie树的根节点，然后blockchain模块又对这个根节点引用了一次。所以这种情况不存在common.Hash{}只能引用某个根节点一次的情况。deference下面我们再来看看解引用的代码。解引用主要在Database.dereference中实现：func (db *Database) dereference(child common.Hash, parent common.Hash) { // Dereference the parent-child node := db.dirties[parent] //首先解除父节点对子节点的引用 if node.children != nil && node.children[child] > 0 { node.children[child]-- if node.children[child] == 0 { delete(node.children, child) } } //如果child不存在，立即返回 node, ok := db.dirties[child] if !ok { return } //减小对child参数代表的节点的引用 if node.parents > 0 { node.parents-- } //如果没人再引用这个节点，则删除它 if node.parents == 0 { //将这个节点从flush-list中删除 switch child { ...... } //解除对所有子节点的引用，然后删除节点 for _, hash := range node.childs() { db.dereference(hash, child) } delete(db.dirties, child) db.dirtiesSize -= common.StorageSize(common.HashLength + int(node.size)) } }这段代码逻辑也比较简单，已经用中文注释进行了说明，这里就不再赘述了。但需要多说一点的时，只有某个节点将要被删除时，才会解引用所有子节点，而不是解引用某个节点的同时也解引用所有子节点。想象一下存在一个引用计数为2的节点A，它有一个引用计数为1的节点B（也即B只被A引用了）。当我们对A进行解引用时，A的计数变成了1，如果我们此时同时解引用A的子节点，那么B的计数将变成0从而被删除，但A仍然需要这么节点。因此只有当A的引用计数变为0将要被删除时，才应该解引用它的所有子节点。flush-list前面我们多次提到"flush-list"这个概念，现在我们就来看看它是什么。要了解flush-list，首先要了解Database.Cap的功能。这个方法将缓存中的数据刷到真实的数据库中，直到缓存占用的内存量达到参数的要求。flush-list就是决定在刷新缓存时，先刷哪个节点、最后刷哪个节点的一个双向链表。Database.oldest和Database.newest定义了这个链表的头和尾，链表的元素是cachedNode，而将cacheNode加入到这个链表中的字段就是cacheNode.flushNext和cacheNode.flushPrev。我们直接看一下Database.Cap是如何使用这个链表的：func (db *Database) Cap(limit common.StorageSize) error { ...... oldest := db.oldest for size > limit && oldest != (common.Hash{}) { // Fetch the oldest referenced node and push into the batch node := db.dirties[oldest] if err := batch.Put(oldest[:], node.rlp()); err != nil { db.lock.RUnlock() return err } ...... size -= common.StorageSize(3*common.HashLength + int(node.size)) oldest = node.flushNext } ...... }可以看到这是一个典型的链表的遍历。至于其它对flush-list插入和删除的代码，相信在了解了它的功能以后，会很容易看懂，因此这里就不再详细说明了。总结在这篇文章中，我们结合源代码，介绍了以太坊中trie模块的功能与实现。trie模块的代码组织还是非常工整的，主要文件有trie.go、node.go、hasher.go、encoding.go和iterator.go。trie模块的主要对象就是Trie。想要理解Trie的实现原理，关键是弄明白代码中的4种node类型，以及key的编码规则（encoding.go）。唯一我觉得不太好的是，在trie.go及其它源文件中，到处都是关于node的typeswitch。我觉得这几乎完全可以放到一个函数中去做，至少可以不像现在这样，在Get/Upate/Delete等方法中都有一套typeswitch。