以太坊ERC20令牌具体操作流程介绍

c

以太坊令牌是于2014年经由一些程序员和一名青年推出,该以太坊令牌旨在让任何人都能编写几乎任何类型的应用,并将其部署在区块链上。这些分散的应用程序(简称“Dapps”),它们可以帮助使用者轻松的实现交易。

为了实现上述功能,他们花费了18个月的时间,ERC20令牌终于问世了。ERC20令牌允许钱包、交换和其他智能合约的开发人员提前知道基于该标准的任何新标记将如何运行。通过这种方式,他们可以设计自己的应用程序来处理这些令牌,而无需等到新的令牌系统更新。

因此,以太坊区块链上几乎所有的主要令牌,包括最近初始硬币(ICOs)的激增,均符合ERC20令牌的规则标准制定的。

令牌101

(以太坊区块链上几乎所有的主要令牌均符合ERC20令牌的标准 来源:金色财经)

(以太坊区块链上几乎所有的主要令牌均符合ERC20令牌的标准 来源:金色财经)

在进行进一步解释令牌之前,首先要了解它与以太坊的不同之处。以太币是推动以太坊区块链的原生币。当它们与以太坊网络相关联时,令牌将转化为数字资产,它可以代表任何东西,通过传输和计算,再折价成现实世界中的实物。此外,令牌也可以是工具,例如游戏中的物品,用来与其他智能合约进行交换。

简单点说,一个令牌只不过是以太坊区块链上运行的智能合约而已。因此,它是一组带有相关数据库的代码,该代码描述了令牌的行为。若把数据库看作一个表,其中行和列跟踪拥有多少个令牌。如果以太坊内的用户或其他智能合约向该令牌发送一条消息,则代码将更新其数据库。

例如,当一个钱包应用发送一条消息给一个令牌合同,将资金从Alice转移到Bob,这时就发生了:

首先,令牌的合同检查消息是由Alice签署的并且Alice有足够的资金来支付这笔款项;

然后,它将资金从Alice的帐户转移到数据库中的Bob帐户;

最后,它发送了一个响应,让钱包知道交易是否成功。

(与令牌不同的是,以太被硬编码到以太坊区块链 来源:金色财经)

(与令牌不同的是,以太被硬编码到以太坊区块链 来源:金色财经)

与令牌不同的是,以太被硬编码到以太坊区块链。它以一种加密货币的方式出售和交易,并且还通过允许用户支付智能合约交易费用,从而为以太坊网络提供了动力。

例如,当您向交换器发送令牌时,您将为该服务付费。

在以太坊历史的早期,标准是创建用户友好和广泛可访问系统的总体计划的一部分。但是和所有的标准一样,ERC20需要时间来进行一系列的长时间讨论。

因此,在2015年第一次大型以太坊会议之前,以太坊的创始人Vitalik Buterin推出了最初的标准令牌。

同年晚些时候,Fabian Vogelstellar,一位在以太坊的烟雾钱包工作的开发人员,采取了这一标准,改变了一些事情,并向社区提出了一项关于如何实施标准的使用规则。

到了今年4月,由于以太坊基金会组织其GitHub的方式发生了变化,ERC20标准被转移到了GitHub的请求中。

ERC20令牌里面有什么?

(ERC20被定义了六种功能 来源:金色财经)

(ERC20被定义了六种功能 来源:金色财经)

ERC20被定义了六种功能,而以太生态系统中的其他智能合约将会根据数据库的更新来识别。

例如,这些包括如何传递一个令牌(由所有者或代表所有者)以及如何访问令牌的数据(名称、符号、供应、平衡)。该标准还描述了两件事:一种智能合同可以触发的信号:其他的智能合同“倾听”。

总之,这些功能和服务使得以太坊标记在以太生态系统中的几乎所有地方都是一样的。因此,几乎所有支持以太的钱包,包括Jaxx、my以太wallet.com和官方以太钱包,现在也支持了erc-20的代币。

(以太坊的象征性标准的重要性为未来的重大变化奠定了基础 来源:金色财经)

(以太坊的象征性标准的重要性为未来的重大变化奠定了基础 来源:金色财经)

根据Vogelstellar的说法,他谈到了以太坊的象征性标准的重要性,这种互操作性为未来的重大变化奠定了基础。他说:

“我相信,我们刚刚开始对所有事情进行标记。也许在未来,你将能够买到你所坐的椅子的一部分,你房子里的油漆,或者在一个巨大的建筑物里的一小部分股权。”

不过,ERC20是正式的草案,这意味着它没有被强制执行,仍然需要得到以太坊社区的肯定。Vogelstellar说,每一个新的标记都可能符合它的规则。

不过,他警告说,标准还有待完善。其中一个障碍是,将令牌直接发送给令牌的智能合同将导致资金损失。这是因为一个令牌的合同只会跟踪和分配资金。例如,当您从钱包中向另一个用户发送令牌时,该钱包将调用令牌的合约来更新数据库。

以太坊的“令牌”非常流行以太坊ERC20令牌具体操作流程介绍

因此,如果您试图将令牌直接传输到令牌的合约中,那么由于该令牌的合约无法响应,所以金钱就“丢失”了。

但解决方案正在发挥作用。作为ERC20的一种扩展,ERC223试图通过建议一个令牌的合约实现一个令牌回退函数来防止该合约不被直接发送给它的令牌,从而解决这个问题。

Vogelstellar认为,这只是发展一个坚实的体系的一部分,但他说:

“使用这些原型机有时可能会很困难,但最终它们提供了学习的机会,让我们了解了区块链和智能合同交互的未来。”

Merkle Tree概念

这里写图片描述
Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1]

1、Hash

Hash是一个把任意长度的数据映射成固定长度数据的函数[2]。例如,对于数据完整性校验,最简单的方法是对整个数据做Hash运算得到固定长度的Hash值,然后把得到的Hash值公布在网上,这样用户下载到数据之后,对数据再次进行Hash运算,比较运算结果和网上公布的Hash值进行比较,如果两个Hash值相等,说明下载的数据没有损坏。可以这样做是因为输入数据的稍微改变就会引起Hash运算结果的面目全非,而且根据Hash值反推原始输入数据的特征是困难的。[3]
这里写图片描述
如果从一个稳定的服务器进行下载,采用单一Hash是可取的。但如果数据源不稳定,一旦数据损坏,就需要重新下载,这种下载的效率是很低的。

2、Hash List
在点对点网络中作数据传输的时候,会同时从多个机器上下载数据,而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性,更好的办法是把大的文件分割成小的数据块(例如,把分割成2K为单位的数据块)。这样的好处是,如果小块数据在传输过程中损坏了,那么只要重新下载这一快数据就行了,不用重新下载整个文件。

怎么确定小的数据块没有损坏哪?只需要为每个数据块做Hash。BT下载的时候,在下载到真正数据之前,我们会先下载一个Hash列表。那么问题又来了,怎么确定这个Hash列表本事是正确的哪?答案是把每个小块数据的Hash值拼到一起,然后对这个长字符串在作一次Hash运算,这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候,首先从可信的数据源得到正确的根Hash,就可以用它来校验Hash列表了,然后通过校验后的Hash列表校验数据块。
这里写图片描述

3、 Merkle Tree

Merkle Tree可以看做Hash List的泛化(Hash List可以看作一种特殊的Merkle Tree,即树高为2的多叉Merkle Tree)。

在最底层,和哈希列表一样,我们把数据分成小的数据块,有相应地哈希和它对应。但是往上走,并不是直接去运算根哈希,而是把相邻的两个哈希合并成一个字符串,然后运算这个字符串的哈希,这样每两个哈希就结婚生子,得到了一个”子哈希“。如果最底层的哈希总数是单数,那到最后必然出现一个单身哈希,这种情况就直接对它进行哈希运算,所以也能得到它的子哈希。于是往上推,依然是一样的方式,可以得到数目更少的新一级哈希,最终必然形成一棵倒挂的树,到了树根的这个位置,这一代就剩下一个根哈希了,我们把它叫做 Merkle Root[3]。

在p2p网络下载网络之前,先从可信的源获得文件的Merkle Tree树根。一旦获得了树根,就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的Merkle Tree。如果Merkle Tree是损坏的或者虚假的,就从其他源获得另一个Merkle Tree,直到获得一个与可信树根匹配的Merkle Tree。

Merkle Tree和Hash List的主要区别是,可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块,这样如果有一块数据损坏,仅仅重新下载这个数据块就行了。如果文件非常大,那么Merkle tree和Hash list都很到,但是Merkle tree可以一次下载一个分支,然后立即验证这个分支,如果分支验证通过,就可以下载数据了。而Hash list只有下载整个hash list才能验证。
这里写图片描述

Merkle Tree的特点

  1. MT是一种树,大多数是二叉树,也可以多叉树,无论是几叉树,它都具有树结构的所有特点;
  2. Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。
  3. 非叶子节点的value是根据它下面所有的叶子节点值,然后按照Hash算法计算而得出的。[4][5]

通常,加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改,可以改用一些安全性低但效率高的校验和算法,如CRC。

Second Preimage Attack: Merkle tree的树根并不表示树的深度,这可能会导致second-preimage attack,即攻击者创建一个具有相同Merkle树根的虚假文档。一个简单的解决方法在Certificate Transparency中定义:当计算叶节点的hash时,在hash数据前加0x00。当计算内部节点是,在前面加0x01。另外一些实现限制hash tree的根,通过在hash值前面加深度前缀。因此,前缀每一步会减少,只有当到达叶子时前缀依然为正,提取的hash链才被定义为有效。

Merkle Tree的操作

1、创建Merckle Tree

加入最底层有9个数据块。

step1:(红色线)对数据块做hash运算,Node0i = hash(Data0i), i=1,2,…,9

step2: (橙色线)相邻两个hash块串联,然后做hash运算,Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7;对于i=9, Node1((i+1)/2) = hash(Node0i)

step3: (黄色线)重复step2

step4:(绿色线)重复step2

step5:(蓝色线)重复step2,生成Merkle Tree Root
这里写图片描述
易得,创建Merkle Tree是O(n)复杂度(这里指O(n)次hash运算),n是数据块的大小。得到Merkle Tree的树高是log(n)+1。

2、检索数据块

为了更好理解,我们假设有A和B两台机器,A需要与B相同目录下有8个文件,文件分别是f1 f2 f3 ….f8。这个时候我们就可以通过Merkle Tree来进行快速比较。假设我们在文件创建的时候每个机器都构建了一个Merkle Tree。具体如下图:
这里写图片描述
从上图可得知,叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8),也就是其子节点node7 node8的值得HASH。就是这样表示一个层级运算关系。root节点的value其实是所有叶子节点的value的唯一特征。

假如A上的文件5与B上的不一样。我们怎么通过两个机器的merkle treee信息找到不相同的文件? 这个比较检索过程如下:

Step1. 首先比较v0是否相同,如果不同,检索其孩子node1和node2.

Step2. v1 相同,v2不同。检索node2的孩子node5 node6;

Step3. v5不同,v6相同,检索比较node5的孩子node 11 和node 12

Step4. v11不同,v12相同。node 11为叶子节点,获取其目录信息。

Step5. 检索比较完毕。

以上过程的理论复杂度是Log(N)。过程描述图如下:

这里写图片描述
从上图可以得知真个过程可以很快的找到对应的不相同的文件。

3、更新,插入和删除

虽然网上有很多关于Merkle Tree的资料,但大部分没有涉及Merkle Tree的更新、插入和删除操作,讨论Merkle Tree的检索和遍历的比较多。我也是非常困惑,一种树结构的操作肯定不仅包括查找,也包括更新、插入和删除的啊。后来查到stackexchange上的一个问题,才稍微有点明白,原文见[6]。

对于Merkle Tree数据块的更新操作其实是很简单的,更新完数据块,然后接着更新其到树根路径上的Hash值就可以了,这样不会改变Merkle Tree的结构。但是,插入和删除操作肯定会改变Merkle Tree的结构,如下图,一种插入操作是这样的:
这里写图片描述
插入数据块0后(考虑数据块的位置),Merkle Tree的结构是这样的:
这里写图片描述
而[6]中的同学在考虑一种插入的算法,满足下面条件:
– re-hashing操作的次数控制在log(n)以内
– 数据块的校验在log(n)+1以内
– 除非原始树的n是偶数,插入数据后的树没有孤儿,并且如果有孤儿,那么孤儿是最后一个数据块
– 数据块的顺序保持一致
– 插入后的Merkle Tree保持平衡

然后上面的插入结果就会变成这样:
这里写图片描述
根据[6]中回答者所说,Merkle Tree的插入和删除操作其实是一个工程上的问题,不同问题会有不同的插入方法。如果要确保树是平衡的或者是树高是log(n)的,可以用任何的标准的平衡二叉树的模式,如AVL树,红黑树,伸展树,2-3树等。这些平衡二叉树的更新模式可以在O(lgn)时间内完成插入操作,并且能保证树高是O(lgn)的。那么很容易可以看出更新所有的Merkle Hash可以在O((lgn)2)时间内完成(对于每个节点如要更新从它到树根O(lgn)个节点,而为了满足树高的要求需要更新O(lgn)个节点)。如果仔细分析的话,更新所有的hash实际上可以在O(lgn)时间内完成,因为要改变的所有节点都是相关联的,即他们要不是都在从某个叶节点到树根的一条路径上,或者这种情况相近。

[6]的回答者说实际上Merkle Tree的结构(是否平衡,树高限制多少)在大多数应用中并不重要,而且保持数据块的顺序也在大多数应用中也不需要。因此,可以根据具体应用的情况,设计自己的插入和删除操作。一个通用的Merkle Tree插入删除操作是没有意义的。

Merkle Tree的应用

1、数字签名

最初Merkle Tree目的是高效的处理Lamport one-time signatures。 每一个Lamport key只能被用来签名一个消息,但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架,即Merkle Signature Scheme。

2、P2P网络

在P2P网络中,Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换,甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输,一来可以加快数据下载速度,二来减轻下载服务器的负担。BT即BitTorrent,是一种中心索引式的P2P文件分分析通信协议[7]。

要进下载必须从中心索引服务器获取一个扩展名为torrent的索引文件(即大家所说的种子),torrent文件包含了要共享文件的信息,包括文件名,大小,文件的Hash信息和一个指向Tracker的URL[8]。Torrent文件中的Hash信息是每一块要下载的文件内容的加密摘要,这些摘要也可运行在下载的时候进行验证。大的torrent文件是Web服务器的瓶颈,而且也不能直接被包含在RSS或gossiped around(用流言传播协议进行传播)。一个相关的问题是大数据块的使用,因为为了保持torrent文件的非常小,那么数据块Hash的数量也得很小,这就意味着每个数据块相对较大。大数据块影响节点之间进行交易的效率,因为只有当大数据块全部下载下来并校验通过后,才能与其他节点进行交易。

就解决上面两个问题是用一个简单的Merkle Tree代替Hash List。设计一个层数足够多的满二叉树,叶节点是数据块的Hash,不足的叶节点用0来代替。上层的节点是其对应孩子节点串联的hash。Hash算法和普通torrent一样采用SHA1。其数据传输过程和第一节中描述的类似。
这里写图片描述

3、Trusted Computing

可信计算是可信计算组为分布式计算环境中参与节点的计算平台提供端点可信性而提出的。可信计算技术在计算平台的硬件层引入可信平台模块(Trusted Platform,TPM),实际上为计算平台提供了基于硬件的可信根(Root of trust,RoT)。从可信根出发,使用信任链传递机制,可信计算技术可对本地平台的硬件及软件实施逐层的完整性度量,并将度量结果可靠地保存再TPM的平台配置寄存器(Platform configuration register,PCR)中,此后远程计算平台可通过远程验证机制(Remote Attestation)比对本地PCR中度量结果,从而验证本地计算平台的可信性。可信计算技术让分布式应用的参与节点摆脱了对中心服务器的依赖,而直接通过用户机器上的TPM芯片来建立信任,使得创建扩展性更好、可靠性更高、可用性更强的安全分布式应用成为可能[10]。可信计算技术的核心机制是远程验证(remote attestation),分布式应用的参与结点正是通过远程验证机制来建立互信,从而保障应用的安全。
这里写图片描述

文献[10]提出了一种基于Merkle Tree的远程验证机制,其核心是完整性度量值哈希树。

首先,RAMT 在内核中维护的不再是一张完整性度量值列表(ML),而是一棵完整性度量值哈希树(integrity measurement hash tree,简称IMHT).其中,IMHT的叶子结点存储的数据对象是待验证计算平台上被度量的各种程序的完整性哈希值,而其内部结点则依据Merkle 哈希树的构建规则由子结点的连接的哈希值动态生成。

其次,为了维护IMHT 叶子结点的完整性,RAMT 需要使用TPM 中的一段存储器来保存IMHT 可信根哈希的值。

再次,RAMT 的完整性验证过程基于认证路径(authentication path)实施.认证路径是指IMHT 上从待验证叶子结点到根哈希的路径。

4、IPFS

IPFS(InterPlanetary File System)是很多NB的互联网技术的综合体,如DHT( Distributed HashTable,分布式哈希表),Git版本控制系统,Bittorrent等。它创建了一个P2P的集群,这个集群允许IPFS对象的交换。全部的IPFS对象形成了一个被称作Merkle DAG的加密认证数据结构

IPFS对象是一个含有两个域的数据结构:

  • Data – 非结构的二进制数据,大小小于256kB
  • Links – 一个Link数据结构的数组。IPFS对象通过他们链接到其他对象

Link数据结构包含三个域:

  • Name – Link的名字
  • Hash – Link链接到对象的Hash
  • Size – Link链接到对象的累积大小,包括它的Links

这里写图片描述
通过Name和Links,IPFS的集合组成了一个Merkle DAG(有向无环图)。

这里写图片描述
对于小文件(<256kB),是一个没有Links的IPFS对象。
这里写图片描述

对于大文件,被表示为一个文件块(<256kB)的集合。只有拥有最小的Data的对象来代表这个大文件。这个对象的Links的名字都为空字符串。
这里写图片描述
这里写图片描述
目录结构:目录是没有数据的IPFS对象,它的链接指向其包含的文件和目录。
这里写图片描述
IPFS可以表示Git使用的数据结构,git commit object。Commit Object主要的特点是他有一个或多个名为’parent0’和‘parent1’等的链接(这些链接指向前一个版本),以及一个名为object的对象(在Git中成为tree)指向引用这个commit的文件系统结构。
这里写图片描述

5、BitCoin和Ethereum[12][13]

Merkle Proof最早的应用是Bitcoin,它是由中本聪在2009年描述并创建的。Bitcoin的Blockchain利用Merkle proofs来存储每个区块的交易。
这里写图片描述

而这样做的好处,也就是中本聪描述到的“简化支付验证”(Simplified Payment Verification,SPV)的概念:一个“轻客户端”(light client)可以仅下载链的区块头即每个区块中的80byte的数据块,仅包含五个元素,而不是下载每一笔交易以及每一个区块:

  • 上一区块头的哈希值
  • 时间戳
  • 挖矿难度值
  • 工作量证明随机数(nonce)
  • 包含该区块交易的Merkle Tree的根哈希
    如果客户端想要确认一个交易的状态,它只需简单的发起一个Merkle proof请求,这个请求显示出这个特定的交易在Merkle trees的一个之中,而且这个Merkle Tree的树根在主链的一个区块头中。

但是Bitcoin的轻客户端有它的局限。一个局限是,尽管它可以证明包含的交易,但是它不能进行涉及当前状态的证明(如数字资产的持有,名称注册,金融合约的状态等)。

Bitcoin如何查询你当前有多少币?一个比特币轻客户端,可以使用一种协议,它涉及查询多个节点,并相信其中至少会有一个节点会通知你,关于你的地址中任何特定的交易支出,而这可以让你实现更多的应用。但对于其他更为复杂的应用而言,这些远远是不够的。一笔交易影响的确切性质(precise nature),可以取决于此前的几笔交易,而这些交易本身则依赖于更为前面的交易,所以最终你可以验证整个链上的每一笔交易。为了解决这个问题,Ethereum的Merkle Tree的概念,会更进一步。

Ethereum的Merkle Proof

每个以太坊区块头不是包括一个Merkle树,而是为三种对象设计的三棵树:

  • 交易Transaction
  • 收据Receipts(本质上是显示每个交易影响的多块数据)
  • 状态State
    这里写图片描述
    这使得一个非常先进的轻客户端协议成为了可能,它允许轻客户端轻松地进行并核实以下类型的查询答案:
  • 这笔交易被包含在特定的区块中了么?
  • 告诉我这个地址在过去30天中,发出X类型事件的所有实例(例如,一个众筹合约完成了它的目标)
  • 目前我的账户余额是多少?
  • 这个账户是否存在?
  • 假如在这个合约中运行这笔交易,它的输出会是什么?
    第一种是由交易树(transaction tree)来处理的;第三和第四种则是由状态树(state tree)负责处理,第二种则由收据树(receipt tree)处理。计算前四个查询任务是相当简单的。服务器简单地找到对象,获取Merkle分支,并通过分支来回复轻客户端。

第五种查询任务同样也是由状态树处理,但它的计算方式会比较复杂。这里,我们需要构建一个Merkle状态转变证明(Merkle state transition proof)。从本质上来讲,这样的证明也就是在说“如果你在根S的状态树上运行交易T,其结果状态树将是根为S’,log为L,输出为O” (“输出”作为存在于以太坊的一种概念,因为每一笔交易都是一个函数调用;它在理论上并不是必要的)。

为了推断这个证明,服务器在本地创建了一个假的区块,将状态设为 S,并在请求这笔交易时假装是一个轻客户端。也就是说,如果请求这笔交易的过程,需要客户端确定一个账户的余额,这个轻客户端(由服务器模拟的)会发出一个余额查询请求。如果需要轻客户端在特点某个合约的存储中查询特定的条目,这个轻客户端就会发出这样的请求。也就是说服务器(通过模拟一个轻客户端)正确回应所有自己的请求,但服务器也会跟踪它所有发回的数据。

然后,服务器从上述的这些请求中把数据合并并把数据以一个证明的方式发送给客户端。

然后,客户端会进行相同的步骤,但会将服务器提供的证明作为一个数据库来使用。如果客户端进行步骤的结果和服务器提供的是一样的话,客户端就接受这个证明。
这里写图片描述

MPT(Merkle Patricia Trees)

前面我们提到,最为简单的一种Merkle Tree大多数情况下都是一棵二叉树。然而,Ethereum所使用的Merkle Tree则更为复杂,我们称之为“梅克尔.帕特里夏树”(Merkle Patricia tree)。

对于验证属于list格式(本质上来讲,它就是一系列前后相连的数据块)的信息而言,二叉Merkle Tree是非常好的数据结构。对于交易树来说,它们也同样是不错的,因为一旦树已经建立,花多少时间来编辑这棵树并不重要,树一旦建立了,它就会永远存在并且不会改变。

但是,对于状态树,情况会更复杂些。以太坊中的状态树基本上包含了一个键值映射,其中的键是地址,而值包括账户的声明、余额、随机数nounce、代码以及每一个账户的存储(其中存储本身就是一颗树)。例如,摩登测试网络(the Morden testnet )的创始状态如下所示:
这里写图片描述
然而,不同于交易历史记录,状态树需要经常地进行更新:账户余额和账户的随机数nonce经常会更变,更重要的是,新的账户会频繁地插入,存储的键( key)也会经常被插入以及删除。我们需要这样的数据结构,它能在一次插入、更新、删除操作后快速计算到树根,而不需要重新计算整个树的Hash。这种数据结构同样得包括两个非常好的第二特征:

  • 树的深度是有限制的,即使考虑攻击者会故意地制造一些交易,使得这颗树尽可能地深。不然,攻击者可以通过操纵树的深度,执行拒绝服务攻击(DOS attack),使得更新变得极其缓慢。
  • 树的根只取决于数据,和其中的更新顺序无关。换个顺序进行更新,甚至重新从头计算树,并不会改变根。
    MPT是最接近同时满足上面的性质的的数据结构。MPT的工作原理的最简单的解释是,值通过键来存储,键被编码到搜索树必须要经过的路径中。每个节点有16个孩子,因此路径又16进制的编码决定:例如,键‘dog’的16进制编码是6 4 6 15 6 7,所以从root开始到第六个分支,然后到第四个,再到第六个,再到第十五个,这样依次进行到达树的叶子。

在实践中,当树稀少时也会有一些额外的优化,我们会使过程更为有效,但这是基本的原则。

6、其他应用

用到Merkle Tree的应用还有很多,比如Git,Amazon Dynamo,Apache Wave Protocol,Tahoe-LAFS backup system,Certificate Transparency framework,NoSQL systems like Apache Cassadra and Riak等

区块链解读

一、区块链
1. 分布式去中心化
比特币设计的初衷就是要避免依赖中心化的机构,没有发行机构,也不可能操纵发行数量。既然没有中心化的信用机构,在电子货币运行的过程中,也势必需要一种机制来认可运行在区块链上的行为(包括比特币的运营,亦或是运行在区块链上的其他业务),这种机制就是共识机制。在完全去中心化的区块链上运行的比特币,采用的是PoW(Proof of Work,工作量证明),该机制完美的解决了拜占庭将军问题(存在异常的情况下仍能达成一致)。因为基础网络架构为分布式,对单独一个节点是无法控制或破坏整个网络,掌握网内51%的运算能力(非节点数)才有可能操作交易,而这个代价大概要超过270亿美元。
2. 无须信任
整个区块链网络中的数据是公开透明的,每个节点(参与者)都可自由加入该网络中,下载到所有的数据。任意两个节点间的数据交换无需互相信任,完全依靠区块链中的交易历史和数据的可追溯,以及共识机制来保证数据交换的正确且不可逆的执行。
3. 不可篡改和加密安全性
跟当前银行网银系统(特别是公司网银系统)的加密机制类似,区块链的数据结构和交易流程中大量的使用了公私钥来加解密,保证数据的安全性。基于该技术基础,甚至可以应用群组签名来保证共有数据的安全性。任何事物既然有优点,也同时会存在不足之处。根源于分布式网络架构和共识机制,在区块链上运行的交易确认时间会比较长(比特币的确认时间大概是15分钟),交易并发数受限(比特币的每秒交易数为7笔,而淘宝的每秒并发数能达到10万左右),区块的容量限制(当前为1M,区块链的扩容一直在讨论中),监管难以介入,基于工作量证明的共识机制存在浪费系统资源和带宽的问题。
4. 区块链技术
a. 区块
区块是一个包含在区块链(公开账簿)里的聚合了交易信息的容器。它由一个包含元数据的区块头和紧跟其后的构成区块主体的一长串交易组成。区块头是80字节,而平均每个交易至少是250字节,而且平均每个区块至少包含超过500个交易。
区块结构如下图
1.jpg
区块结构
交易(Tx)详情中的结构如下图
2.jpg
交易(Tx)详情中的结构
b. 区块链
当一个节点从网络接受到传入的区块时,它会验证这些区块,然后链接到现有的区块链上,链接的形态如下图:
3.jpg
enter description here
由于每个区块包含前一个区块的HASH值,这就使得从创世块到当前块形成了一条块链,每个区块必定按时间顺序跟随在前一个区块之后,因为如果不知道前一块区块的HASH值就没法生成当前区块。要改变一个已经在块链中存在一段时间的区块,从计算上来说是不可行的,因为如果它被改变,它之后的每个区块必须随之改变。这些特性使得双花比特币非常困难,区块链是比特币的最大创新。
5. 比特币钱包
a. 比特币钱包的生成
首先使用随机数发生器生成一个 私钥 。一般来说这是一个256bits的数,拥有了这串数字就可以对相应 钱包地址 中的比特币进行操作,所以必须被安全地保存起来。
私钥经过SECP256K1算法处理生成了公钥。SECP256K1是一种椭圆曲线算法,通过一个已知私钥时可以算得公钥,而公钥已知时却无法反向计算出私钥。这是保障比特币安全的算法基础。
同SHA256一样,RIPEMD160也是一种Hash算法,由公钥可以计算得到公钥哈希,而反过来是行不通的。
将一个字节的地址版本号连接到公钥哈希头部(对于比特币网络的pubkey地址,这一字节为“0”),然后对其进行两次SHA256运算,将结果的前4字节作为公钥哈希的校验值,连接在其尾部。
将上一步结果使用BASE58进行编码(比特币定制版本),就得到了钱包地址。
流程图如下
%u83B7%u53D6%u6BD4%u7279%u5E01%u94B1%u5305%u5730%u5740%u6D41%u7A0B%u56FE
比特币钱包的生成流程图
b .转账
比特币钱包间的转账是通过交易(Transaction)实现的。交易数据是由转出钱包私钥的所有者生成,也就是说有了私钥就可以花费该钱包的比特币余额。生成交易的过程如下:
%u6BD4%u7279%u5E01%u4EA4%u6613%u6D41%u7A0B%u56FE
转账交易流程图
交易的原始数据包括“转账数额”和“转入钱包地址”,但是仅有这些是不够的,因为无法证明交易的生成者对“转出钱包地址”余额有动用的权利。所以需要用私钥对原始数据进行签名。
生成“转出钱包公钥”,这一过程与生成钱包地址的第2步是一样的。
将“转出签名”和“转出公钥”添加到原始交易数据中,生成了正式的交易数据,这样它就可以被广播到比特币网络进行转账了。
二、以太坊Ethereum
1. 概念
a. 什么是以太坊
简单来说,以太坊是一种新的法律形式。现行法律的本质是一种合约。它是由(生活于某一社群的)人和他们的领导者之间所缔结的,一种关于彼此该如何行动的共识。个体之间也存在着一些合约,这些合约可以理解为一种私法,相应的,这种私法仅对合约的参与者生效。
例如,你和一个人订立合约,借给他一笔钱,但他最后毁约了,不打算还这笔钱。此时你多半会将对方告上法庭。在现实生活中,打官司这种事情常常混乱不堪并且充满了不确定性。将对方告上法庭,也通常意味着你需要支付高昂的费用聘请律师,来帮你在法庭上针对法律条文展开辩论,而且这一过程一般都旷日持久。而且,即使你最终赢了官司,你依然可能会遇到问题(比如,对方拒不执行法庭判决)。
令人欣慰的是,当初你和借款人把条款写了下来,订立了合约。但法律的制定者和合约的起草者们都必须面对一个不容忽视的挑战:那就是,理想情况下,法律或者合约的内容应该是明确而没有歧义的,但现行的法律和合约都是由语句构成的,而语句,则是出了名的充满歧义。
因此,一直以来,现行的法律体系都存在着两个巨大的问题:首先,合约或法律是由充满歧义的语句定义的,第二,强制执行合约或法律的代价非常大。
而以太坊,通过数字货币和编程语言的结合,解决了现行法律体系的这两大问题。
以太坊系统自身带有一种叫做以太币(Ether)的数字货币。以太币和著名的数字货币比特币(Bitcoin)有着非常多的相似之处。两者均为数字储值货币,且无法伪造,都以去中心化的方式运行来保证货币供应不被某一方所控制。两者都可以像电子邮件一样,作为货币自由地在全世界流通。而且,由于它们可以做到传统货币做不到的事情,因此用户对它们未来的价值充满期待 ,详情请阅读以太坊白皮书 (中文, 英文)。
b. 基本知识
公钥加密系统。 Alice有一把公钥和一把私钥。她可以用她的私钥创建数字签名,而Bob可以用她的公钥来验证这个签名确实是用Alice的私钥创建的,也就是说,确实是Alice的签名。当你创建一个以太坊或者比特币钱包的时候,那长长的0xdf…5f地址实质上是个公钥,对应的私钥保存某处。类似于Coinbase的在线钱包可以帮你保管私钥,你也可以自己保管。如果你弄丢了存有资金的钱包的私钥,你就等于永远失去了那笔资金,因此你最好对私钥做好备份。
点对点网络。 就像BitTorrent, 以太坊分布式网络中的所有节点都地位平等,没有中心服务器。
区块链。 区块链就像是一个全球唯一的帐簿,或者说是数据库,记录了网络中所有交易历史。
以太坊虚拟机(EVM)。 它让你能在以太坊上写出更强大的程序(比特币上也可以写脚本程序)。它有时也用来指以太坊区块链,负责执行智能合约以及一切。
节点。 你可以运行节点,通过它读写以太坊区块链,也即使用以太坊虚拟机。完全节点需要下载整个区块链。轻节点仍在开发中。
矿工。 挖矿,也就是处理区块链上的区块的节点。这个网页可以看到当前活跃的一部分以太坊矿工:stats.ethdev.com。
工作量证明。 矿工们总是在竞争解决一些数学问题。第一个解出答案的(算出下一个区块)将获得以太币作为奖励。然后所有节点都更新自己的区块链。所有想要算出下一个区块的矿工都有与其他节点保持同步,并且维护同一个区块链的动力,因此整个网络总是能达成共识。(注意:以太坊正计划转向没有矿工的权益证明系统(POS),不过那不在本文讨论范围之内。)
以太币。 缩写ETH。一种你可以购买和使用的真正的数字货币。这里是可以交易以太币的其中一家交易所的走势图。在写这篇文章的时候,1个以太币价值65美分。
Gas. 在以太坊上执行程序以及保存数据都要消耗一定量的以太币,Gas是以太币转换而成。这个机制用来保证效率。
DApp. 以太坊社区把基于智能合约的应用称为去中心化的应用程序(Decentralized App)。DApp的目标是(或者应该是)让你的智能合约有一个友好的界面,外加一些额外的东西,例如IPFS(可以存储和读取数据的去中心化网络,不是出自以太坊团队但有类似的精神)。DApp可以跑在一台能与以太坊节点交互的中心化服务器上,也可以跑在任意一个以太坊平等节点上。
2. 工作流程
a. 环境搭建
建议使用Mac OS环境,不然可能会出现各种坑。
安装NodeJS,安装Python。
安装testrpc(测试环境中使用),安装go-ethereum(真实环境中使用)。
安装solc。
安装truffle。
b. Solidity语言简介
下面是官网上面的一段关于智能投票合约的示例代码
contract Ballot {
//一个选民的构造体
struct Voter {
uint weight; // 权重(即他可以投几票)
bool voted; //是否已经投过票
address delegate; // 代表地址(他可以代表某个人进行投票)
uint vote; // index of the voted proposal
}
// 投票的提案的构造体
struct Proposal
{
bytes32 name; // 提案名称
uint voteCount; //获得的票数
}
address public chairperson;//会议主席
//地址 -选民 的map
mapping(address => Voter) public voters;
// 投票种类的动态数组
Proposal[] public proposals;
///构造函数
function Ballot(bytes32[] proposalNames) {
chairperson = msg.sender;//初始化会议主席
voters[chairperson].weight = 1;
//初始化所有的提案
for (uint i = 0; i < proposalNames.length; i++) {
proposals.push(Proposal({
name: proposalNames[i],
voteCount: 0
}));
}
}
// 给予投票权
function giveRightToVote(address voter) returns (bool b) {
if (msg.sender != chairperson || voters[voter].voted) {
//对于会议主席和已经投过票的选民这里不处理
return false;;
}
voters[voter].weight = 1;
return true;
}
/// 投票权转移函数
function delegate(address to) {
// 投票权转移的发起人
Voter sender = voters[msg.sender];
if (sender.voted)
throw;
//递归找到没有转移投票权的 选民
while (
voters[to].delegate != address(0) &&
voters[to].delegate != msg.sender
) {
to = voters[to].delegate;
}
if (to == msg.sender) {
throw;
}
//将发起人设置为已经投过票的状态
sender.voted = true;
//将代表设置为刚才递归获取的选民
sender.delegate = to;
Voter delegate = voters[to];
if (delegate.voted) {
//如果代表已经投过票就在他投票的提案的票数增加
proposals[delegate.vote].voteCount += sender.weight;
}
else {
//将代表的的票数增加
delegate.weight += sender.weight;
}
}
/// 投票函数
function vote(uint proposal) {
Voter sender = voters[msg.sender];
if (sender.voted)
throw;
sender.voted = true;
sender.vote = proposal;
//将投的提案票数增加
proposals[proposal].voteCount += sender.weight;
}
///获得票数最多的提案
function winningProposal() constant
returns (uint winningProposal)
{
uint winningVoteCount = 0;
for (uint p = 0; p < proposals.length; p++) {
if (proposals[p].voteCount > winningVoteCount) {
winningVoteCount = proposals[p].voteCount;
winningProposal = p;
}
}
}
}
解读
address. 地址类型。chairperson是会议主席的钱包地址。这个地址会在合约的构造函数function Ballot()中被赋值。很多时候也称呼这种地址为’owner’(所有人)。
public. 这个关键字表明变量可以被合约之外的对象使用。private修饰符则表示变量只能被本合约(或者衍生合约)内的对象使用。如果你想要在测试中通过web3.js使用合约中的某个变量,记得把它声明为public。
Mapping或数组。mapping(address => Voter)为选民钱包地址和选民构造体的键值对。Proposal[] public proposals是一个提案构造体的数组。
有特殊的变量和函数总是在全局命名空间存在,主要用于提供有关blockchain信息,例如msg,block,tx,其中msg.sender为发起人的地址。
solidity语言更深入的理解可以阅读官方文档。
c. 使用geth部署合约
启动一个测试节点
geth –testnet –fast –cache=512 –genesis CustomGenesis.json console
这里的CustomGenesis.json是为了给测试的账户分配以太币
{
“coinbase”: “0x0000000000000000000000000000000000000000”,
“difficulty”: “0x20000”,
“extraData”: “”,
“gasLimit”: “0x2fefd8”,
“nonce”: “0x0000000000000042”,
“mixhash”: “0x0000000000000000000000000000000000000000000000000000000000000000”,
“parentHash”: “0x0000000000000000000000000000000000000000000000000000000000000000”,
“timestamp”: “0x00”,
“alloc”: {
“0xe49c283bc6bf92c5833cc981b97679238dd3b5da”: {
“balance”: “111111111000000000000000000000000000”
},
“0xd8927c296b3ebe454a6409770a0c323ec4ed23ba”: {
“balance”: “222222222000000000000000000000000000”
}
}
}
solc下的内容要替换成你的测试账户地址。具体geth的用法请查看官方文档和源码介绍。
使用solc编译智能合约,获得二进制代码
例如以下代码
contract test {
function multiply(uint a) returns(uint d) {
return a * 7;
}
}
在geth中输入
source = “contract test { function multiply(uint a) returns(uint d) { return a * 7; } }”
clientContract = eth.compile.solidity(source).test
编译返回的结果的JSON格式如下
solc%u7F16%u8BD1%u7ED3%u679C%u56FE
enter description here
其中,
code:编译后的EVM字节码
info:编译器返回的metadata
abiDefination:Application Binary Interface定义。具体接口规则参见这里
compilerVersion:编译此代码的solidity编译器版本
developerDoc:针对开发者的Natural Specification Format,类似于Doxygen
language:合约语言
languageVersion:合约语言版本
source:源代码
userDoc:针对用户的Ethereum的Natural Specification Format。
编译器返回的JSON结构反映了合约部署的两种不同的路径。info信息真实的存在于区中心化的云中,作为metadata信息来公开验证Blockchain中合约代码的实现。而code信息通过创建交易的方式部署到区块链中。
使用solc编译智能合约,获得二进制代码
部署合约前,确保你有一个解锁的账户并且账户中有余额,因为部署合约得过程中会消耗以太币。输入web3.fromWei(eth.getBalance(eth.accounts[0]),”ether”)可以查看账户余额。
解锁一个账户
personal.unlockAccount(eth.accounts[0])
获得账户
primaryAddress = eth.accounts[0]
定义一个abi (abi是个js的数组,否则不成功)
abi = [{ constant: false, inputs: [{ name: ‘a’, type: ‘uint256’ } ]}]
创建智能合约
MyContract = eth.contract(abi)
发送交易部署合约
contract = MyContract.new({from: primaryAddress, data:”0x6060604052602a8060106000396000f3606060405260e060020a6000350463c6888fa18114601a575b005b6007600435026060908152602090f3″})
%u6548%u679C%u56FE
结果图
如果交易被pending,如图说明你的miner没有在挖矿
%u6548%u679C%u56FE
enter description here
启动一个矿工
miner.setEtherbase(eth.primaryAddress) //设定开采账户
miner.start(8)
eth.getBlock(“pending”, true).transactions
这时候发现交易已经在区块中
%u6548%u679C%u56FE
enter description here
不过会发现,交易还是pending,这是因为该交易区块没有人协助进行运算验证,这时候只需要再启动一个矿工就行了
miner.start(8)
与合约进行交互
Multiply7 = eth.contract(clientContract.info.abiDefinition);
var myMultiply7 = Multiply7.at(contract.address);
myMultiply7.multiply.call(3)
myMultiply7.multiply.sendTransaction(3, {from: contract.address})
d. 使用truffle框架
使用truffle部署智能合约的步骤:
truffle init (在新目录中) => 创建truffle项目目录结构,
编写合约代码,保存到contracts/YourContractName.sol文件。
例如Ballot .sol,此时要找到migrations文件夹,在deploy_contracts.js文件中添加deployer.deploy(Ballot);
truffile compile 编译合约代码。
启动以太坊节点(例如在另一个终端里面运行testrpc)。
truffle migrate(在truffle项目目录中)。
1. 编写单元测试
在test文件夹中新建ballot.js文件
contract(‘Ballot’,function(accounts)){
//accounts是所以账户得数值
it(“获取投票权”,function(){
var meta = Ballot.deployed();
return meta.giveRightToVote(accounts[1]).then(function(b){
assert.equal(Boolean(b),true,”获取投票权失败”);
});
});
}
在项目根目录下运行truffle test,你应该看到测试通过,如果使用自己构造的ballot对象,可以这样写:
contract(‘Ballot’,function(accounts)){
//accounts是所以账户得数值
it(“获取投票权”,function(){
var proposals = [];
proposals.push(“proposal0”);
Ballot.new(proposals).then(function(meta){
return meta.giveRightToVote(accounts[1]).then(function(b){
assert.equal(Boolean(b),true,”获取投票权失败”);
});
});
});
}
合约中发送以太币。 this是合约实例的地址,以变接下来检查这个地址的余额(或者直接使用this.balance)
当你通过web3.js调用交易函数时(使用web3.eth.sendTransaction),交易并不会立即执行。事实上交易会被提交到矿工网络中,交易代码直到其中一位矿工产生一个新区块把交易记录进区块链之后才执行。因此你必须等交易进入区块链并且同步回本地节点之后才能验证交易执行的结果。用testrpc的时候可能看上去是实时的,因为测试环境很快,但是正式网络会比较慢。
Gas. (译注:以太坊上的燃料,因为代码的执行必须消耗Gas。直译为汽油比较突兀,故保留原文做专有名词。)直到现在我们都没有涉及Gas的概念,因为在使用testrpc时通常不需要显式的设置。当你转向geth和正式网络时会需要。在交易函数调用中可以在{ from: , value: , gas: _ } 对象内设置Gas参数。Web3.js提供了web3.eth.gasPrice调用来获取当前Gas的价格,Solidity编译器也提供了一个参数让你可以从命令行获取合约的Gas开销概要:solc –gas YouContract.sol.
2. 为合约创建一个界面
在app目录中,可以编写自己的html和js文件,js与智能合约的交互与单元测试基本一致,例如一个界面上有一个输入框和一个按钮,获得选民的投票权。
<!DOCTYPE html>
<html>
<head>
<title>Ballot App</title>
<link href=’https://fonts.googleapis.com/css?family=Open+Sans:400,700′ rel=’stylesheet’ type=’text/css’>
<link href=”./app.css” rel=’stylesheet’ type=’text/css’>
<script src=”./app.js”></script>
</head>
<body>
<h1>Ballot</h1>
<h2>Example Truffle Dapp</h2>
<br>
<h1>Send</h1>
<br><label for=”amount”>Account:</label><input type=”text” id=”account” placeholder=”e.g., 0x453468394hdfg84858345348″></input>
<br><br><button id=”getRightVote” onclick=”getRight()”>Get Right Vote</button>
<br><br>
<span id=”status”></span>
</body>
</html>
app.js中的代码为
function getRight() {
var account = document.getElementById(“account”).value;
var meta = Ballot.deployed();
meta.giveRightToVote(account).then(function(b){
if(Boolean(b)){
setStatus(“Get Right Vote Success”);
}else{
setStatus(“Get Right Vote Error”);
}
}).catch(function(e){
setStatus(“Get Right Vote Error”);
console.log(e);
});
};