本文的区块链相关知识，主要基于北京大学肖臻老师的《区块链技术与应用》总结。

区块链基础

目录

比特币部分

• 密码学基础
• 比特币的数据结构
• 共识协议和系统实现
• 挖矿算法及难度调节
• 比特币脚本
• 软分叉和硬分叉
• 匿名与隐私保护

以太坊部分

• 概述：基于账户的分布式账本
• 数据结构（MPT）：状态树、交易树、收据树
• GHOST协议：对非主链区块的补偿
• 挖矿：memory hard mining puzzle
• 权益证明：由POW向POS转变
• 智能合约

总结与展望

比特币部分

1.密码学基础

哈希碰撞： 简述就是给定hash函数 目前不存在一个方法可以找到满足hash(A) == hash(B) 的 A和B ，即我们无法人为制造hash碰撞。该特性叫做 collision resistance

collision resistance用处： 给出A，但是由于本性质的缘故，无法反推出A的具体值。

hiding： 即在给定A和hash函数的条件下，也无法反推出A的取值。

collision resistance和hiding结合实现digital commitment(数据保证) 如：预测结果为A，提前公布hash(A) , 验证时对A取hash与之对比即可保证发布内容为A，且未提前给出A的信息。

Puzzle friendly： 想得到某个哈希值，没有什么捷径，只能遍历⼀个个尝试。

对称加密： 发送前与接收后，使⽤商量好的同⼀个密钥进⾏加密解密。

非对称加密： A对B传输信息。A使⽤B的公钥加密，B收到后使⽤⾃⼰的私钥解密。公钥相当于银⾏账号，私钥相当于密码。

签名： A发出交易时⽤A⾃⼰的私钥对信息进⾏签名，然后⽤B的公钥进⾏加密，B收到后⽤B⾃⼰的
私钥解密看到信息，⼜可以⽤A的公钥验证签名。

2.BTC的数据结构

区块链：

区块链结构本身为一条链表，节点为区块。而传统链表实现，便是通过指针将各个节点串联起来而称为最终的链。如下便是我们最常见的一个链表：

但在区块链系统中，并未采用指针，而是使用了哈希指针

每个区块根据自己的区块内容生成自己的哈希值，此外，每个区块（除创世纪块）都保存有前一个区块的哈希值。需要注意的是，本区块哈希生成依赖于本区块内容，而本区块内容中又包含有前一个区块的哈希值。从而保证了区块内容不被篡改。

merkle tree (默克尔树):

该数据结构的优点在于：只需要记住Root Hash（根哈希值），便可以检测出对树中任何部位的修改。

当需要向轻节点证明某条交易是否被写入区块链，便需要用到Markle proof。我们将交易到根节点这一条路径称为Markle proof，全节点将整个Markle proof发送给轻节点（如下图所示），轻节点即可根据其算出根哈希值，和自己保存的对比，从而验证该交易是否被写入区块链。只要沿着该路径，所有哈希值都正确，说明内容没有被修改过。

3.共识机制

出现的问题：

双花攻击： 数字货币本身为带有签名的数据文件，可以进行复制。即：对用户来说，可以将同一货币花费两次。

中心化解决办法：对货币添加唯一编号（不可篡改），每次支付向货币发行单位查询真伪。

去中心化解决办法：

• 在比特币系统中由挖矿来决定货币发行权和发行量。
• 系统维护的一个数据结构，记录货币的使用情况（是否被花过？被谁花过？），即区块链。

对每一笔交易都可以进行溯源，直到创世纪块的铸币交易。

比特币区块信息

挖矿求解问题：Hash（block header）<= target
Hash of previous block header只计算区块块头部分的哈希（ Merkle root hash保证了block body内容不被篡改，所以只需要计算block header即可保证整个区块内容不会被篡改）
区块链系统中，轻节点（只存储区块block header信息）只利用区块链，但并不参与区块链系统维护和构造。

分布式共识： 由于各节点独立完成区块链构建，所以对于账本需要取得一个共识，谁写的帐才是对的？

比特币共识机制： 谁在组装好区块后对Nonce进行尝试，第一个找到满足Hash(block header) <= target的Nonce的用户便拥有记账权。

为了激励大家参与竞争记账权 避免恶意节点轻易获得记账权，比特币系统设计规定，起初挖掘每个区块可以获得50个比特币，但之后每隔21万个区块，奖励减半。

区块中保存交易记录，那么，会不会存在节点只想发布区块而不想打包交易？中本聪在设计该系统时，引入了交易费。鼓励拥有记账权的区块将交易包含打包发布到区块链中。

4.BTC系统实现

区块链是一个去中心化的账本，比特币采用了 基于交易的账本模式 。

系统中并无显示记录账户包含比特币数，实际上其需要通过交易记录进行推算。在比特币系统中，全节点需要维护一个名为 UTXO(Unspent Transaction Output尚未被花掉的交易输出) 的数据结构。

如图，A转给B五个BTC，转给C3个BTC，B将5个BTC花掉，则该交易记录不保存在UTXO中，C没有花掉，则该交易记录保存在UTXO中

该结构可以预防双花攻击，判断一个交易是否合法，查询所花的BTC是否在该集合中。该结构由全节点在内存中维护。

区块信息：

比特币网络：

⼯作在应⽤层application layer：BitCoin Block chain
底层network layer：P2P Overlay Network，⽆超级节点⽆主节点，所有节点都平等。
设计原则：simple，鲁棒性robust，but not efficient
消息传播：泛洪flooding，且不考虑拓扑结构
区块⼤⼩字节：1M

5.挖矿算法及难度调节

矿工每次组装完一个区块后，尝试Nonce，使Hash(block header) <= target的过程 叫做挖矿。区块链使用挖矿来争夺记账权，获取出块奖励。

出块奖励每21w个区块 (4年) 减半。

为防范恶意节点的最长链攻击，最好使用 N confirmation，即在交易后多等几个区块，再确认交易。

难度调整
挖矿难度和⽬标阈值成反⽐，难度最⼩是1，target很⼤。
为何调整挖矿难度
出块时间太短造成的问题：分叉成为常态，系统安全性⽆法保证。
怎么调整挖矿难度
每隔2016个区块(两周)，要调整挖矿难度(target)。
target = target X (actual time/expect time)
四倍限制(1/4～4)
如果有恶意节点到了规定时间不调整，其他诚实结点验证其nBits域不会通过。
由于现在挖矿难度加⼤，可能光调整nonce是不够的，还需要调整CoinBase域。
挖矿
在本地组装⼀个候选区块，⼀边监听⼀边挖(nonce)。如果监听到已经有新的区块产⽣，验证后，停⽌挖
矿，在本地重新组装候选区块。
memoryless / progress free：由于⽆记忆性，重新挖并不可惜。

⽐特币是如何保证安全性的？
共识机制(⼤多数矿⼯是好的) + 密码学(私钥签名)
挖矿⼯具(通⽤到专⽤)
家⽤电脑cpu：⼤部分内存浪费，cpu⼤部分部件闲置，硬盘闲置
GPU(主要⽤于⼤规模并⾏计算)：某些部件也浪费。其他货币有些还在⽤。
ASIC芯⽚：Application Specific Integrated Ciral，专⻔设计于挖矿计算hash值

6.比特币脚本

比特币系统中使用的脚本语言非常简单，唯一可以访问的内存空间只有栈，所以也被称为“基于栈的语言。

• 交易的宏观信息：
  
• Vin的内容：
  

如果存在 一个交易有多个输入，那么每个输入都要说明币的来源并给出签名（BTC中一个交易可能需要多个签名）

• Vout的内容：
  

• 脚本执行：

在早期，直接将两个脚本按照如图顺序(input script在前，output script在后) 拼接后执行，后来考虑到安全性问题，两个脚本改为分别执行：先执行input script，若无出错，再执行output script。

• 输入输出的几种形式：

  1. P2PK形式(Pay to public key)

  特点：输出脚本直接给出收款人公钥。(CHECKSIG为检查签名操作)

  

  执行过程：

  

1. P2PKH形式(Pay to public key hash)——最常用

   特点：输出脚本不直接给出收款人公钥，而是公钥的哈希。

   

   执行过程：

   

   

1. P2SH形式(Pay to script hash)

特点：输出脚本给出的不是收款人公钥的哈希，而是收款人提供的一个脚本的哈希。该脚本称为redeemScript,即赎回脚本。等未来花钱的时候，输入脚本要给出redeemScript的具体内容以及可以使之正确运行需要的签名。

验证过程：
1.验证序列化的redeemScript是否与output script中哈希值匹配。
2.反序列化并执行redeemScript，验证iutput script中给出签名是否正确。（将赎回脚本内容当作操作指令执行一遍）
redeemScript的形式：
1.P2PK形式
2.P2PKH形式
3.多重签名形式

7.区块链分叉

分叉指的是，原来的系统中为一条链，但分成了两条链。分叉形成的原因可能有多种，例如：挖矿时两个节点差不多同时挖出矿，都会发布区块(对比特币系统当前状态产生分歧导致的分叉——state fork)；分叉攻击，同样也会导致分叉(forking attack，人为故意造成)；比特币协议改变，在分布式系统中不能保证所有节点同时升级软件，假设存在少数节点未升级，导致出现分叉(protocal fork)

根据对比特币协议修改的不同，可以将分叉分为硬分叉和软分叉。

• 硬分叉(hard fork)
  对比特币协议增加新协议，扩展新功能，未升级软件的旧节点会不认可这些修改，会认为这些特性是非法的。这也就是对比特币协议内容产生分歧，从而导致分叉。硬分叉的一个典型例子，就是对比特币区块大小的修改（之前有提到过，BTC区块大小限制1MB，但是否合适存在争议）。

• 软分叉（soft fork）

  对BTC协议添加限制，使得原本合法交易在新交易中不合法，便会形成软分叉。

总结：

• soft fork
  特点：只要系统中拥有半数以上算力节点更新软件，系统就不会产生永久性分叉
• hard fork
  特点：必须系统中所有节点更新软件，系统才不会产生永久性分叉

以太坊部分

1.以太坊概述

以太坊便对BTC进行了改进。例如：出块时间、共识协议、mining puzzle（对内存要求高，反ASIC芯片使用）

未来，以太坊还将会用权益证明(POS)替代工作量证明(POW)
此外，以太坊增加了对智能合约（smart contract）的支持。

BTC系统是基于交易的账本，系统中并未显示记录账户有多少钱，只能通过UTXO进行推算。

以太坊系统则采用了基于账户的模型，与现实中银行账户相似。系统中显示记录每个账户以太币的数量，转账是否合法只需要查看转账者账户中以太币是否足够即可，同时也不需要每次全部转账。同时，这也也天然地防范了双花攻击。但是存在重放攻击的缺陷。

以太坊系统中存在两类账户：外部账户和合约账户。

外部账户：类似于BTC系统中公私钥对。存在账户余额balance和计数器nonce
合约账户：并非通过公私钥对控制。(不能主动发起交易，只能接收到外部账户调用后才能发起交易或调用其他合约账户)其除了balance和nonce之外还有code(代码)、storage(相关状态-存储)
创建合约时候会返回一个地址，就可以对其调用。调用过程中，代码不变但状态会发生改变。

2.以太坊数据结构

在以太坊中，有三棵树的说法，分别是状态树、收据树和交易树。了解了这三棵树，就弄清楚了以太坊的基础数据结构设计。

merkle tree + 字典树 + 路径压缩 = MPT(Modified Patricia tree)

• 状态树

右上角表示四个账户(为直观，显示较少)和其状态(只显示账户余额)。（需要注意这里的指针都是哈希指针）

每次发布新区块，状态树中部分节点状态会改变。但改变并非在原地修改，而是新建一些分支，保留原本状态。如下图中，仅仅有新发生改变的节点才需要修改，其他未修改节点直接指向前一个区块中的对应节点。

所以，系统中全节点并非维护一棵MPT，而是每次发布新区块都要新建MPT。只不过大部分节点共享。

最后说明
状态树中保存Key-value对，key就是地址，而value状态通过RLP(Recursive Length Prefix，一种进行序列化的方法)编码序列号之后再进行存储。

• 交易树和收据树

每次发布一个区块时，区块中的交易会形成一颗Merkle Tree，即交易树。

每个交易执行完之后形成一个收据，记录交易相关信息。也就是说，交易树和收据树上的节点是一一对应的。

交易树和收据树只将当前区块中的交易组织起来，而状态树将所有账户的状态都包含进去，无论这些账户是否与当前区块中交易有关系。
多个区块状态树共享节点，而交易树和收据树依照区块独立。

交易树和收据树的用途：

1. 向轻节点提供Merkle Proof。
2. 更加复杂的查找操作(例如：查找过去十天的交易；过去十天的众筹事件等)

• bloom filter 布隆过滤器

支持较为高效查找某个元素是否在某个集合中
方法：给一个大的集合，计算出一个紧凑的“摘要”，可以迅速过滤区块链中不包含xxx的区块

3.以太坊的GHOST协议

前景提要：BTC系统中出块时间为10min，而以太坊中出块时间被降低到15s左右，虽然有效提高了系统反应时间和吞吐率，却也导致系统临时性分叉变成常态，且分叉数目更多。由于系统中经常性会出现分叉，则矿工挖到矿很大可能会被废弃，这会大大降低矿工挖矿积极性。

所以，以太坊设计了新的公式协议——GHOST协议(该协议并非原创，而是对原本就有的Ghost协议进行了改进)。

对于出块成功，且未成为最长合法链的区块，被后续最长合法链区块称为叔父区块。

规定E区块在发布时可以将A、C、D叔父区块包含进来，A、C、D叔父区块可以得到出块奖励的7/8，而为了激励E包含叔父区块，规定E每包含一个叔父区块可以额外得到1/32的出块奖励。为了防止E大量包含叔父区块，规定一个区块只能最多包含两个叔父区块，因此E在A、C、D中最多只能包含两个区块作为自己的出块奖励

叔父区块的定义是和当前区块在七代之内有共同祖先才可，对于M来说，无论包含哪个辈分的“叔父”，得到的出块奖励都是1/32出块奖励。这样，就方便了全节点进行记录，此外，也从协议上鼓励一旦出现分叉马上进行合并。

需要注意的是，ETH的区块奖励并不会递减，uncle block中的交易也并不会被执行。

4.以太坊的挖矿算法

挖矿这一过程，虽然并没有创造什么实际价值，但挖矿本身维持了比特币系统的稳定。总体来说，比特币系统中的挖矿算法较为成功，并未发现大的漏洞。

前景提要：BTC的挖矿算法导致了挖矿设备的专业化，普通计算机用户难以参与进去，导致了挖矿中心化的局面产生，而这与“去中心化”这一理念相违背。

所以，后续的加密货币希望针对ASIC矿机，推出增加对内存访问的需求的挖矿算法。

• 莱特币挖矿算法概述

  1. 设置一个很大的数组，按照顺序填充伪随机数。Seed为种子节点，通过Seed进行一些运算获得第一个数，之后每个数字都是通过前一个位置的值取哈希得到的。这样的数组中取值存在前后依赖关系。
     

  2. 在需要求解Puzzle的时候，按照伪随机顺序，从数组中读取一些数，每次读取位置与前一个数相关。例如：第一次，从A位置读取其中数据，根据A中数据计算获得下一次读取位置B；第二次,从B位置读取其中数据，根据B中数据计算获得下一次读取位置C；

总结：如果数组足够大，对于挖矿矿工来说，必须保存该数组以便查询，否则每次不仅计算位置，还要根据Seed计算整个数组数据，才能查询到对应位置的数据。这对于矿工来说，计算复杂度大幅度上升。

• 以太坊挖矿算法概述

以太坊中，设计了两个数据集，一大一小。小的为16MB的cache，大的数据集为1G的dataset(DAG)。其关系为，1G的数据集是通过16MB数据集生成而来的。

为了便于进行验证，轻节点保存16MB的Cache进行验证即可。

而矿工为了挖矿更快，减少重复计算则需要存储1GB大小的大数据集。

以太坊挖矿过程：

根据区块block header和其中的Nonce值计算一个初始哈希，根据其映射到某个初始位置A，读取A位置的数及其相邻的后一个位置A’上的数,根据该两个数进行运算，算得下一个位置B，读取B和B’位置上的数，依次类推，迭代读取64次，共读取128个数。

最后，计算出一个哈希值与挖矿难度目标阈值比较，若不符合就重新更换Nonce，重复以上操作直到最终计算哈希值符合难度要求或当前区块已经被挖出。

具体部分有兴趣者，自行了解。

5.权益证明

按照所占权益投票进行共识达成，类似于股份制有限共识按照股份多少投票，权益证明不需要挖矿。

还有吓唬矿机厂商，减少ASIC矿机研发的功能。

在设计之初，以太坊开发者就设想要从POW转向POS，并为了防止有矿工不愿意转埋下了一颗“难度炸弹”。即ETH的挖矿难度在呈指数级增加。

预挖矿(pre mining) ： 开发以太坊时，给开发者预留了一部分货币。

Pre-Sale： 将预留的货币出售掉用于后续开发，类似于拉风投或众筹。

6.智能合约

智能合约：运行在区块链系统上的一段代码，代码逻辑定义了合约内容。
智能合约的账户保存了合约当前的运行状态：

• balance：当前余额
• nonce：交易次数
• code：合约代码
• storage：存储，数据结构为一棵MPT

智能合约编写代码为Solidity，其语法与JavaScript很接近。
下图显示了智能合约的代码结构。

• 外部账户调用合约账户

• 合约账户调用合约账户

  1. 直接调用

  

  错误处理：直接调用的方式，一方产生异常会导致另一方也进行回滚操作。

1. address调用

   
   错误处理：address.call()的方法，如果调用过程中被调用合约产生异常，会导致call()返回false，但发起调用的函数不会抛出异常，而是继续执行。

1. 代理调用

   
   和call()调用基本一致，区别在于其并不会切入被调用合约的上下文中。

• Payable ：如果一个函数可以接收外部转账，则必须标记为payable

• fallback 函数：

​ 该函数主要是防止A向B转账，但没有在data域中说明要调用哪个函数或说明的要调用函数不存在，此时调用fallback()函数。

• 智能合约创建与运行：

  实际上并不是想转账，而是想要创建智能合约。EVM设计思想类似 于JAVA中的JVM，便于跨平台增强可移植性。EVM中寻址空间256位，而目前个人机主流位32位和64位，与之存在较大差距。

  

  以太坊规定，执行合约中指令需要收取汽油费，并且由发起交易的人进行支付。

• 错误处理

  以太坊中交易具有原子性，要么全执行，要么全不执行，不会只执行一部分(包含智能合约)。
  需要注意的是，在执行过程中产生错误导致回滚，已经消耗掉的汽油费是不会退回的。从而有效防止了恶意节点对全节点进行恶意调用。

  

  

  嵌套调用是否发生回滚，取决于调用方式。一个合约向一个合约账户直接转账，因为fallback函数的存在，仍有可能会引发嵌套调用。

后续完整智能合约内容参见Solidity教程。

总结

由中本聪的BTC引发了去中心化的开端，后面应运而生各种为了解决BTC的问题的各种币，但是直到ETH之前都还是未脱俗。ETH的诞生宣告区块链除了虚拟货币外的其他应用场景。抛去去中心化这个帽子，我们要时常与世界所接触，技术不只是浮于名词表面更要实际的与社会实践所接触，发挥他应有的价值。