第2章
设计理念
以太坊被誉为第二代区块链，它是在以比特币为首的第一代区块链技术之上发展起来的， 不可避免地具有很多与比特币相似的特点。比特币，是一位或者一群署名“中本聪”的天才， 在前人研究密码学货币的基础上，于2008年年末提出的非常系统和完备的点对点数字加密货币。比特币的发明有着强烈的时代背景：2007年8月席卷美国，并很快影响到全球，导致全球金融市场剧烈震荡。加密货币的创导者们认为，次贷危机的根源是美国一些贪得无厌的金融寡头们，滥用规则制造的金融悲剧。这些机构和个人被标榜为美国金融界的核心力量，但同时也是一个欺骗监管、引诱大众的中心化集团。“中本聪”们有着一种朴素的英雄主义理想，即通过技术去开发一种不受中心化控制、安全可靠，同时又满足人人参与和共享，平民化、草根性的金融体系，于是基于加密货币的比特币诞生了。
以太坊继承了比特币的衣钵，天生为去中心化的公链而生。以太坊从设计之初就考虑了严格的加密学安全，无须传统式信任背书，具有去中心化的共识和容错，限制交易双花， 以及使用挖矿模型维护网络运行等特点。
除此之外，以太坊又是独特的。以太坊的作者 Vitalik Buterin，发表了多篇关于以太坊设计和介绍的文章，归纳起来，以太坊的独特性考虑体现在以下几点。
□架构、政治和逻辑的去中心化是完美的，以太坊在架构和政治上努力实现了去中心化，但在逻辑上并不完美，它维护了一个中心化的共同认可的状态。
□底层协议简单，接口易于理解，复杂部分放入中间层的三明治模型。
□去中心化 DApp 的智能合约在以太坊上成功应用。
□为了人人能够自由使用以太坊，抵御攻击和滥用的 Gas 机制不可或缺。
□以太坊体现了基本平台的功能，每个功能尽量做得像泛化的粒子，使得底层概念清晰，功能高效。
□账户模型代替 UTXO。
□一系列不同于比特币的加密学、区块和数据结构的运用。
□独立的合约执行环境 EVM。
这里将重点讲述以太坊在区块链技术里的相同性和不同点，同时尽可能揭示其蕴含的设计思想。
2.1 密码学
密码学知识广泛应用于安全的信息通信、数据存储、交易验证等方面，其也是区块链最基础的技术之一。这些知识既包括对信息的转换、加解密，以及校验过程，也包括以太坊地址和交易 Hash，交易信息 RLP 编码、基于椭圆曲线公私钥签名、区块 Merkle 树交易等。
2.1.1 Hash
Hash，在数学上也被称为“散列”，是指将任意长度的二进制值（明文）转换为较短的固定长度的二进制值（Hash值）。Hash算法的特点具体如下。
□输出长度小于输入长度。
□对于任何输入都能进行快速和高效的计算。
□强抗冲突性：任何输入改变都会影响大量的输出位。输入数据只要稍有变化（比如一个1变成了0），就会得到一个千差万别的结果，且结果无法事先预知。
□单向值：输入不由输出来决定。
当然，不同的输入有时候也可能产生相同的输出，出现相同输出值的概率称为Hash的碰撞率。本质上，Hash是一种将不同信息通过一种恰当的方法产生消息摘要，以便于在后续使用时得到较好的识别。Hash数学模型如图2-1所示。
Hash函数的实现，经过多年的发展已经包含了非常多的种类和实现，有的强调实现简单快速，有的注重Hash结果的较小的碰撞率，还有的则关注算法以实现较高的安全性，总之要根据不同的应用场景，选择不同且适当的Hash算法。目前一些知名的Hash函数包括MD5、SHA系列，以及PBKDF2等。
SHA（Secure Hash Algorithm，SHA）家族的系列Hash算法，由美国国家安全局（NSA）设计，并由美国国家标准与技术研究院（NIST）发布，是在全球范围内被广泛使用的安全Hash算法，常常应用在数字签名和校验的场景中，其中SHA-1使用尤其广泛。但是，2005年2月，山东大学王小云等发表了完整版的对SHA-1的攻击，只需少于2的69次方的计算复杂度，就能找到一组碰撞，根据摩尔定律，随着计算机计算能力的提高，SHA-1很快就被认为是一种不安全的Hash算法。这之后，NIST又相继发布了SHA-224、SHA-256、SHA-384和SHA-512，后四者都称为SHA-2；SHA-256和SHA-512是很新的Hash函数，实际上二者的结构是相同的，只在循环执行的次数上有所差异。SHA-224和SHA-384则是前面两种Hash函数的截短版，利用不同的初始值做计算。
随着硬件设备计算算力的不断攀升，研究破解攻击SHA系列算法的方法和可能性也越来越高，于是在2005年和2006年，美国国家标准与技术研究所（NIST）连续举办了两届研讨会，研究讨论下一代密码Hash方案。新的Hash算法命名为SHA-3，作为新的Hash标准，并在2007年宣布在全球范围内征集下一代密码Hash算法。2010年12月9日，NIST通过讨论评选出五个算法（BLAKE、Gr?stl、JH、Keccak、Skein）进入第三轮的最终评选。2012年10月2日SHA-3的Keccak算法最终获胜。Keccak 算法由意法半导体的 Guido Bertoni、Joan Daemen（AES 算法合作者）和 Gilles Van Assche，以及恩智浦半导体的 Micha?l Peeters 联合开发，它在设计上与 SHA-2 存在极大差别，之前针对 SHA-2 的攻击方法无法有效地攻击 Keccak。
Keccak算法采用了一种称为海绵的结构，如图2-2所示。M为任意长度的输入消息，Z为Hash之后的摘要输出，f[b]称为置换函数，其他参数r为比特率，c为容量，且b=r+c，参数c要求是Hash摘要输出长度n的2倍，即c=2n。海绵结构有两个阶段，一个称为吸收阶段（absorbing），另外一个称为压缩阶段（squeezing）。压缩阶段，输入消息M后串联一个数字串10...01，其中0的个数是将消息M填充为长度为r的最小正整数倍；接着将填充后的输入消息分组，每组有r个比特，填充的最小长度为2，最大为r+1。同时b个初始状态全部初始化为0。海绵结构处理完输入的压缩过程之后，转换到挤压状态，挤压后输出的块数可根据用户需要做出选择。
由于 Keccak 采用了不同于之前 SHA1/2 的 MD（Merkel Damgard）结构，所以针对MD 结构的攻击对 Keccak 不再有效。因此，到目前为止，还没有出现能够对实际运用中的Keccak 算法形成威胁的攻击方法。
以太坊沿用了比特币在 Hash 运算上相同的 Keccak 算法来生成 32 个字节 256 位的摘要信息。下面以 Go 客户端代码实现进行分析，使用的是 f [1600] 函数，f [b] 中的每一轮置换都包含 5 个步骤， 总共循环 24 轮。
func keccakF1600(a *[25]uint64) {
// Implementation translated from Keccak-inplace.c
// in the keccak reference code.
var t, bc0, bc1, bc2, bc3, bc4, d0, d1, d2, d3, d4 uint64
for i := 0; i < 24; i += 4 {
// Combines the 5 steps in each round into 2 steps.
// Unrolls 4 rounds per loop and spreads some steps across rounds.
// Round 1
bc0 = a[0] ^ a[5] ^ a[10] ^ a[15] ^ a[20]
bc1 = a[1] ^ a[6] ^ a[11] ^ a[16] ^ a[21]
bc2 = a[2] ^ a[7] ^ a[12] ^ a[17] ^ a[22]
bc3 = a[3] ^ a[8] ^ a[13] ^ a[18] ^ a[23]
bc4 = a[4] ^ a[9] ^ a[14] ^ a[19] ^ a[24]
d0 = bc4 ^ (bc1<<1 | bc1>>63)
d1 = bc0 ^ (bc2<<1 | bc2>>63)
d2 = bc1 ^ (bc3<<1 | bc3>>63)
d3 = bc2 ^ (bc4<<1 | bc4>>63)
d4 = bc3 ^ (bc0<<1 | bc0>>63)
bc0 = a[0] ^ d0
t = a[6] ^ d1
bc1 = t<<44 | t>>(64-44)
t = a[12] ^ d2
bc2 = t<<43 | t>>(64-43)
t = a[18] ^ d3
bc3 = t<<21 | t>>(64-21)
t = a[24] ^ d4
bc4 = t<<14 | t>>(64-14)
a[0] = bc0 ^ (bc2 &^ bc1) ^ rc[i]
a[6] = bc1 ^ (bc3 &^ bc2)
a[12] = bc2 ^ (bc4 &^ bc3)
a[18] = bc3 ^ (bc0 &^ bc4)
a[24] = bc4 ^ (bc1 &^ bc0)
t = a[10] ^ d0
bc2 = t<<3 | t>>(64-3)
t = a[16] ^ d1
bc3 = t<<45 | t>>(64-45)
t = a[22] ^ d2
bc4 = t<<61 | t>>(64-61)
t = a[3] ^ d3
bc0 = t<<28 | t>>(64-28)
t = a[9] ^ d4
bc1 = t<<20 | t>>(64-20)
a[10] = bc0 ^ (bc2 &^ bc1)
a[16] = bc1 ^ (bc3 &^ bc2)
a[22] = bc2 ^ (bc4 &^ bc3)
a[3] = bc3 ^ (bc0 &^ bc4)
a[9] = bc4 ^ (bc1 &^ bc0)
t = a[20] ^ d0
bc4 = t<<18 | t>>(64-18)
t = a[1] ^ d1
bc0 = t<<1 | t>>(64-1)
t = a[7] ^ d2
bc1 = t<<6 | t>>(64-6)
t = a[13] ^ d3
bc2 = t<<25 | t>>(64-25)
t = a[19] ^ d4
bc3 = t<<8 | t>>(64-8)
a[20] = bc0 ^ (bc2 &^ bc1)
a[1] = bc1 ^ (bc3 &^ bc2)
a[7] = bc2 ^ (bc4 &^ bc3)
a[13] = bc3 ^ (bc0 &^ bc4)
a[19] = bc4 ^ (bc1 &^ bc0)
t = a[5] ^ d0
bc1 = t<<36 | t>>(64-36)
t = a[11] ^ d1
bc2 = t<<10 | t>>(64-10)
t = a[17] ^ d2
bc3 = t<<15 | t>>(64-15)
t = a[23] ^ d3
bc4 = t<<56 | t>>(64-56)
t = a[4] ^ d4
bc0 = t<<27 | t>>(64-27)
a[5] = bc0 ^ (bc2 &^ bc1)
a[11] = bc1 ^ (bc3 &^ bc2)
a[17] = bc2 ^ (bc4 &^ bc3)
a[23] = bc3 ^ (bc0 &^ bc4)
a[4] = bc4 ^ (bc1 &^ bc0)
t = a[15] ^ d0
bc3 = t<<41 | t>>(64-41)
t = a[21] ^ d1
bc4 = t<<2 | t>>(64-2)
t = a[2] ^ d2
bc0 = t<<62 | t>>(64-62)
t = a[8] ^ d3
bc1 = t<<55 | t>>(64-55)
t = a[14] ^ d4
bc2 = t<<39 | t>>(64-39)
a[15] = bc0 ^ (bc2 &^ bc1)
a[21] = bc1 ^ (bc3 &^ bc2)
a[2] = bc2 ^ (bc4 &^ bc3)
a[8] = bc3 ^ (bc0 &^ bc4)
a[14] = bc4 ^ (bc1 &^ bc0)
// Round 2…
为了实现高性能，在ARM处理器上，Keccak 完全使用汇编实现，使用 Go 语言进行封装。以太坊 Go 客户端，在 crypto 加密包中，对外封装了使用接口，用来生成 Hash 值。
// Keccak256 calculates and returns the Keccak256 Hash of the input data.
func Keccak256(data ...[]byte) []byte {
d := sha3.NewKeccak256()
for _, b := range data {
d.Write(b)
}
return d.Sum(nil)}
// Keccak256Hash calculates and returns the Keccak256 Hash of the input data,
// converting it to an internal Hash data structure.
func Keccak256Hash(data ...[]byte) (h common.Hash) {
d := sha3.NewKeccak256()
for _, b := range data {
d.Write(b)
}
d.Sum(h[:0])
return h}
在应用中，只需要调用 crypto.Keccak256 或者 crypto.Keccak256Hash，例如 crypto.Keccak256Hash([]byte(“hello world”)) 即可获取指定输入的 Hash 输出。
以太坊中包含了大量的信息，以 Hash 摘要的形式呈现，例如账户和合约地址、交易 Hash、区块 Hash、事件 Hash。下面这段代码就是计算交易数据的 Hash，将交易（transaction）数据进行 RLP 编码后，再做 Keccak256 算法的 Hash 运算，最后得到 32 字节的交易 Hash 值：0x25e18c91465 c6ee0f79e45016c5dd55eb12424c5d91e59eed237039ba4b239be。
// Hash Hashes the RLP encoding of tx.
// It uniquely identifies the transaction.
func (tx *Transaction) Hash() common.Hash {
if Hash := tx.Hash.Load(); Hash != nil {
return Hash.(common.Hash)
}
v := rlpHash(tx)
tx.Hash.Store(v)
return v}
func rlpHash(x interface{}) (h common.Hash) {
hw := sha3.NewKeccak256()
rlp.Encode(hw, x)
hw.Sum(h[:0])
return h}
2.1.2 椭圆曲线的加解密算法
密码学在工程应用中，一般分为两种加解密方式。一种是对称加密，比如 DES、AES， 这种加密算法是加解密相关方共享一份密钥，一方加密，另外一方解密，很多应用的密码或者关键信息都是通过 AES 加密算法运算存储或者传输的，这种加密算法有个比较突出的优点，即运算相对简单、性能损耗小、效率高。另外一种加密方式称为非对称加密，加解密双方共享不同的密钥，当加密方使用接收方的公钥加密时，解密方必须使用自己的私钥解密。在签名应用中，所有者使用自己的私钥签名，验证者使用签名所有者的公钥验证，比较典型的有 RSA 和椭圆曲线（ECC）加解密算法。
RSA（由 Ron Rivest、Adi Shamir、Leonard Adleman 三个发明人姓氏的首字母组成） 算法利用了一个数学上公认的数论特性：将两个大质数相乘很容易，但是想要对其乘积进行因式分解却非常困难，因此可以将乘积公开作为加密密钥，只要密钥长度足够长，那么破解将是非常困难的。RSA 算法，公钥用来公开并加密，私钥用来保留解密，且不可互换，其更多地应用于加密密钥协商、加密证书签名的场景中。我们常见的 https 协议，就是在采用 RSA 作为前期交换对称密钥协商时，进行非对称安全加解密算法。
椭圆曲线（Ellipse Curve Cryptography，ECC）和签名算法（Ellipse Curve Digital Signature Algorithm，ECDSA）在数字货币和区块链的应用中被普遍采用。ECC与基于大质数因子分解困难性的加密方法不同，其依赖的数学原理是求解椭圆曲线上离散对数问题的困难性。
一个通用的椭圆曲线的表达式，可以描述为：
Ax3+Bx2+Cxy2+Dy3+Ex2+Fxy+Gy2+Hx+Iy+J=0
参数不同，描述的椭圆曲线特性不同，差异很大。比特币和以太坊使用的椭圆曲线用二元三阶方程表示为：y2 = x3 + ax + b，其中 a、b 为系数，同时满足 4a3+27b2 ≠ 0。椭圆曲线如图 2-3 所示。
在数学上，一个椭圆曲线群可以看作曲线上的所有点和无穷远点 O 组成的集合。对于椭圆曲线上不同的两点P 和 Q，若有 P+Q=R，则说明 P 和 Q 的直线与椭圆曲线相交于一点（? R），? R 在 X 轴对称的点即为 R，如图2-4所示。
从图2-4可以看出，椭圆曲线上的加法运算，相加所得到的点，依然在椭圆曲线上。在椭圆曲线的两个点 P 和 Q 之间，存在一个等式 kP = P + P + … + P = Q。如果已知 k 和点 P，则求解 Q 点比较简单，但是如果已知 Q 点和 P 点，要求解有多少个 k，使得 kP = Q，就极其不容易。椭圆曲线的密码学，正是利用求解 k 的困难性作为安全性的理论基础。在应用层面，一般是将k 作为私钥，Q 作为公钥。
以太坊上使用的椭圆曲线和比特币一致，都采用了 Certicom 这家密码领域的专业公司推荐的曲线— secp256k1。椭圆曲线 secp256k1 在二维空间表示为 y2 = x3 + ax + b ，满足六元组关系 D=(p, a, b, G, n, h)，其中各个元组之间的关系如下。
secp256k1由于其自身构造的特殊性，经过优化实现，在性能上比其他曲线提高了大概30%，也可以有效抵御破解攻击。
在区块链技术中，普遍使用椭圆曲线，而非RSA，是因为椭圆曲线相对于RSA，具有如下4个显著优点。
□安全性能更高，160位ECC密钥与1024位RSA安全强度相当。
□处理速度更快，在私钥的处理速度上，ECC远比RSA快得多。
□带宽要求更低。
□存储空间更小。
2.1.3 签名
ECDSA 是基于椭圆曲线生成公私钥进行数字签名和验证的算法过程。下面以以太坊上两个账户 Alice 和 Bob 在以太坊网络中进行 ETH 转账交易来说明以太坊的交易 ECDSA进行签名和校验的过程。
交易的签名过程具体如下。
1）Alice的DApp工具生成一个随机数，作为她账户的私钥k。
2）在椭圆曲线secp256k1上生成P点，根据等式Q=kP，该曲线上所得点Q的坐标（x，y）经过数学处理就可以得到Alice的公钥，公钥经过Hash之后再截断便得到了Alice在以太坊网络中唯一的账户地址。这个过程如图2-5所示。
3）当Alice第一次向Bob转账1个ETH时，生成如下交易信息：
rawTx = {
nonce: 0,
gasPrice: 50000000000,
gasLimit: 120000,
to: '0xC82AA3a402a737284070eA482FfC2471102997cb',
value: 1000000000000000000,
data: '0x00ffee'
};
4）Alice 的 DApp 对转账交易 tx 进行 RLP 编码，再进行 SHA-3 的 Hash，最后对 Hash 进行签名，得到签名结果为 65 字节的（r, s, v）。其中 r 和 s 分别为 32 字节，是签名的主体部分；v=27+(r % 2)，可看作签名结果的一种简单校验，在以太坊中作为恢复签名的 recoveryID。以太坊交易签名的生成过程如图 2-6 所示。
签名实质上是使用私钥k对交易摘要进行加密的过程。
交易验证过程具体如下。
1）交易验证节点接收到Alice发起转账原始交易和她的签名。
2）校验Alice签名，包括检查recoveryID，然后结合签名和交易Hash恢复出Alice的公钥Q。
3）对公钥Q进行Hash，截取后20字节，得到Alice的账户地址。
4）对比原始交易中的from地址与演算恢复的Alice地址是否相同，如果相同则证明本次Alice的转账交易是合法的，否则拒绝该交易。
签名验证实质上是使用公钥Q对交易进行解密的过程。
以太坊Go客户端代码，通过cgo实际集成了比特币的secp256k1 库，Go 代码封装了签名并根据签名恢复公钥。以太坊交易签名生成过程如图2-6所示。
以太坊签名和验证回复的代码片段分别如下。
签名：
func Sign(msg []byte, seckey []byte) ([]byte, error) {
if len(msg) != 32 {
return nil, ErrInvalidMsgLen
}
if len(seckey) != 32 {
return nil, ErrInvalidKey
}
seckeydata := (*C.uchar)(unsafe.Pointer(&seckey[0]))
if C.secp256k1_ec_seckey_verify(context, seckeydata) != 1 {
return nil, ErrInvalidKey
}
var (
msgdata = (*C.uchar)(unsafe.Pointer(&msg[0]))
noncefunc = C.secp256k1_nonce_function_rfc6979
sigstruct C.secp256k1_ecdsa_recoverable_signature
)
if C.secp256k1_ecdsa_sign_recoverable(context, &sigstruct, msgdata, seckeydata, noncefunc, nil) == 0 {
return nil, ErrSignFailed
}
var (
sig = make([]byte, 65)
sigdata = (*C.uchar)(unsafe.Pointer(&sig[0]))
recid C.int
)
C.secp256k1_ecdsa_recoverable_signature_serialize_compact(context, sigdata, &recid, &sigstruct)
sig[64] = byte(recid) // add back recid to get 65 bytes sig
return sig, nil}
恢复公钥：
func RecoverPubkey(msg []byte, s ig []byte) ([]byte, error) {
if len(msg) != 32 {
return nil, ErrInvalidMsgLen
}
if err := checkSignature(sig); err != nil {
return nil, err
}
var (
pubkey = make([]byte, 65)
sigdata = (*C.uchar)(unsafe.Pointer(&sig[0]))
msgdata = (*C.uchar)(unsafe.Pointer(&msg[0]))
)
if C.secp256k1_ecdsa_recover_pubkey(context, (*C.uchar)(unsafe.Pointer (&pubkey [0])), sigdata, msgdata) == 0 {
return nil, ErrRecoverFailed
}
return pubkey, nil}
func checkSignature(sig []byte) error {
if len(sig) != 65 {
return ErrInvalidSignatureLen
}
if sig[64] >= 4 {
return ErrInvalidRecoveryID
}
return nil}
公钥到账户地址的转换：
以太坊中的账户地址和比特币不同，转换相对比较简单。具体来说就是 Hash 结果取后 20 字节，这里的 Hash 算法是 SHA3-256，可以用如下代码来表示：
crypto.Keccak256(pubKey)[12:]
func PubkeyToAddress(p ecdsa.PublicKey) common.Address {
pubBytes := FromECDSAPub(&p)
return common.BytesToAddress(Keccak256(pubBytes[1:])[12:])}
2.1.4 Merkle 树和验证
Merkle树又称为哈希树，是一种二叉树，由一个根节点、若干中间节点和一组叶节点组成。最底层的叶节点包含存储数据，在它之上的一层节点为它们对应的Hash值，中间节点是它下面两个子节点内容的Hash值，根节点是最后顶层的Hash值，这个一般称为Merkle根，如图2-7所示。
Merkle树的层层Hash计算，任何底层叶节点或者说某个节点的数据变动都会传递到其父亲节点，并直达树根。当叶子节点发生数据改变时，如果要比较两个集合的数据是否相同，则只需要比较两次数据的树根即可，若底层叶节点数据相同，则树根相同；反之，树根便不相同。因此Merkle树的典型应用场景具体如下。
□快速比较大量数据：当两个Merkle树根相同时，则意味着所代表的数据必然相同。
□快速定位变更：例如图2-7中，如果L1中的数据被修改，则会影响到Hash0-0、Hash0和Root。因此，沿着Root→Hash0→Hash0-0，可以快速定位到发生改变的L1。
2.1.5 MPT 状态树
Trie树是一种有序的树型结构，也被称作前缀树或字典树，一般用于保存关联数组，其中的键通常是字符串，键不保存在节点中，而是由节点在树中的位置决定，根节点对应空字符串，键对应的值标注在节点之下。
Patricia树是一种节省空间的压缩前缀树。相对于Trie树存在的缺点，每个前置节点仅能表示一个字母，不管key和其他key有没有共享内容，key越长，树的深度也越长。如图2-8所示，Patricia树的主要改进在于如果存在一个父节点只有一个子节点，那么这个父节点将与其子节点合并，这样可以减小Trie中树的深度，加快搜索节点速度，同时也减少了空间的消耗。
MPT（Merkle Patricia Trie）显而易见就是Merkle和Patricia结合后的产物，在以太坊中，MPT包含4种不同的节点：空节点、叶子节点、扩展节点和分支节点。
□空节点：无实际内容节点，但占用一个元数据存储。
□叶子节点（leaf）：是一个键值对（key，value），其中key是原始内容的一种特殊十六进制编码，value是内容的RLP编码。
□扩展节点（extension）：也是一个键值对（key，value），但是value是其他节点的Hash值，即指向其他节点的链接。
□分支节点（branch）：由于key被编码成一种特殊的十六进制的表示，还有最后的value，所以分支节点是一个长度为17的列表，前16个元素对应着key中的16个可能的十六进制字符，如果有一个（key,value）键值对在这个分支节点终止，那么最后一个元素代表一个值，即分支节点既可以是搜索路径的终止也可以是搜索路径的中间节点。分支节点的父节点基本上就是扩展节点。
这里再简单介绍一下MPT中用到的十六进制前缀（hex-prefix，HP）key编码。十六进制字母表中有16个字符（0...9, A...F），如果某个节点有16个子节点，那么每个子节点对应一个字符占用4位，半个字节，被称为nibble。一个nibble被加到key之前（如图2-9中的prefix），用来对终止符的状态和奇偶性进行编码。其中，最低位表示奇偶性，0表示偶数，1表示奇数；倒数第二低位表示终止符状态。如果key是偶数位，则需要加上另外一个nibble。下面结合以太坊官方技术文档上介绍的世界观状态树（图2-9）来具体解释一下以太坊的MPT。
图2-9所示的示例总共有2个扩展节点，2个分支节点，4个叶子节点。
首先，根节点ROOT实际上是一个扩展节点，该节点进行SHA-3Hash计算后的值就是所谓的三大Merkle根之一的stateRoot。这个扩展节点的key为其他实际节点的共有前缀（a7，key）两位字符，需要在前面补充前缀半字节nibble；value指向第一个分支节点，这个分支节点key包含（1，7，f）字符。其中1指向叶子节点，这个叶子节点key为1355，偶数位补充前缀，因为是终止节点，nibble是0010=2，value是balance 45.0 ETH。第一个分支节点key中的7指向第二个扩展节点，它的key是后续两个叶子节点的共有前缀d3，偶数位补字符0，value指向第二个分支节点。这个分支节点key包含3和9，其中3指向叶子节点1.00 WEI，9指向0.12ETH的叶子节点，这两个叶子节点key都只有1位，而且是终止节点，所以补充的nibble前缀0011=3。第一个分支节点key还包含f，它指向1.1 ETH的叶子节点，这个叶子节点的key为9365，偶数位而且是终止节点，所以在前面补充前缀nibble0010=2。叶子节点键值对如图2-10所示。
同时，节点的key前面补充的nibble规律如下，如图2-11所示。
综上所述，以太坊MPT树具有如下特点。
□叶子节点和分支节点可以保存value，扩展节点保存key。
□没有公共的key就成为2个叶子节点。
□若有公共的key则应该提取为一个扩展节点。
□如果公共的key也是一个完整的key，那么数据应该保存到下一级的分支节点中。
MPT数据和验证广泛应用于以太坊中。在区块链中，区块block打包了大量的交易、合约及账号的状态，如何保证每个区块的这些交易是可以被验证以及状态是被频繁改变的呢？实际上，在区块结构中包含区块头header，header里面包含3种类型的树根，如图2-12所示。
// Header represents a block header in the Ethereum blockchain.
type Header struct {
ParentHash common.Hash `json:"parentHash" gencodec:"required"`
UncleHash common.Hash `json:"sha3Uncles" gencodec:"required"`
Coinbase common.Address `json:"miner" gencodec:"required"`
Root common.Hash `json:"stateRoot" gencodec:"required"`
TxHash common.Hash `json:"transactionsRoot" gencodec:"required"`
ReceiptHash common.Hash `json:"receiptsRoot" gencodec:"required"`
1.状态树：stateRoot
状态树是全局的树。
□path = sha3（ethereumAddress）：以太坊账户地址。
□value = rlp（[nonce, balance, storageRoot, codeHash]）：交易次数、账户余额、存储树、合约代码 Hash。
其中 storageRoot 是另一个 trie 树，用于存储合约的所有数据，每个账户都有一个独立的storageRoot 树。
2.交易树：transactionsRoot
每个 block 都有一个交易树。
□path = rlp（transactionIndex）：该交易在 block 中的索引，顺序由矿工决定。
□value = 交易记录。
该树生成后永远不会被修改。
3.收据树：receiptsRoot
每个block都有一个收据树。
□path = rlp（receiptIndex）：该交易在 block 中生成 receipt 的索引，顺序由矿工决定。
□value = receipt 记录。
该树生成后永远不会被修改。
2.2 共识问题
共识问题，或者共识机制在区块链领域中常常被提及，它基本上是去中心化系统中自建信任、达成最终一致性的最核心和最基础的技术。区块链公链网络本质上是一个更大型、更不受控的点对点的分布式网络，各个节点因为网络拥塞、性能受限、错误导致异常等原因，带来各自状态的不确定性。要让加入网络的节点在网络王国中达成总体目标，特别是在完全去中心化的环境下，绝非一件容易的事。因此需要有一个定义容错，可验证、防攻击，并且全局认可的机制来保证整个网络世界的状态确定性和一致性。
区块链的共识问题，最终也是一致性的问题，在去中心化和中心化的系统中，这个问题的终极目标是一致的，但是两者面临的问题环境却不尽相同。中心化的系统经过多年理论和实践的发展，已经比较成熟，而区块链的共识机制算法从比特币诞生之日起，就面临挑战，业界也在不断从理论和应用各个层面进行探索和改进。要深入了解和认识区块链特别是以太坊的共识机制，需要从一致性问题探究开始。
回溯历史，20 世纪 80 年代开始出现的分布式系统，促进了分布式一致性问题的研究， 区块链的共识问题和算法也在这个基础上逐渐被人们提出和探讨。
2.2.1 分布式一致性问题
分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。分布式系统具有如下特点。
□分布性：多节点计算机在地理位置上呈物理距离部署。
□对等性：主/从区分被弱化，副本（Replica）是分布式系统最常见的重要概念，其是分布式系统对数据和服务提供的一种冗余方式。
□并发性：不同节点的逻辑可以同时触发并执行，特别是对集群模式的业务，并发性非常明显。
□无严格时序：消息并不是顺序处理的，也很难定义两个事件时间上的先后顺序。
□故障：节点可能因硬件故障而失效，也可能是软件资源的竞争出现异常；总之，故障在分布式系统中是一个必须考虑的因素。
下面详细介绍下分布式环境面临的各种问题。
1.通信异常
分布式系统运行在网络之上，网络依赖的硬件和软件众多，通信的链路跨越众多的路由器和交换机，不可靠和不可达的情况是必然存在的。原本在单机进程或者线程中的 IPC 通信，在分布式节点中演变成 RPC，通信除了时延从纳秒数量级变成了毫秒，甚至秒级别之外，甚至在故障情况下，消息不可达、通信中断也会普遍存在。
2.网络分区：脑裂
在分布式系统中，节点分布在不同的网络区域中，在某些子网内通信可能正常，但是这部分子网的节点和其他子网间却不能通信，处于一种隔离的状态。对整个分布式系统来说网络环境和节点就好像被切分成了若干个孤立的区域，这就好比是一个正常的人体被“脑裂”，无法做出全面和正常的决策和动作。这种情况对分布式系统的最终一致性达成来说是一个非常严峻的挑战，必须要有方法对网络分区的严重状态做出判断和决策。
3.三态
由于网络的复杂性，分布式系统中的每一次请求与响应，都存在“三态”的概念，即：成功、失败、超时。分布式系统中的调用和响应，可以看作单机版的扩展，单机进程的调用结果要么失败，要么成功；跨网络的调用可能会多出一种结果，暂时超时无响应。这种结果状态对调用方来说，需要做出适时的处理。
4.节点故障
节点故障伴随着网络通信异常，会是分布式环境的常态，容忍节点故障是分布式设计中的常见模式。
前面提到分布式系统的对等性，多主机进行分布式部署的方式提供服务，为了维持节点间共享的状态，肯定会存在数据的复制。而引入复制机制后，不同的数据节点之间由于网络延时或者中断等原因很容易产生数据不一致的情况。复制机制的目的是为了保证数据的最终一致性，但是数据复制问题就是如何保证多个副本之间的数据一致性。在数据库领域，一致性经常被归结到数据库的事务ACID问题上，即A（原子性，只有成功和失败状态）、C（一致性）、I（隔离性，各个事物都有自己的数据空间）、D（持久性，提交事务后的状态必须是永久的）。在一个中心化的节点上满足ACID特性可能比较简单，但是将它放到分布式环境里面，要满足每个特性却是要大费周章的。除了数据库，还有分布式业务常常涉及的事务一致性（CAP）问题，CAP是计算机界对分布式特点提出一个基本理论。CAP理论首先对分布式系统中的三个特性进行了如下归纳。
□一致性（C）：分布式系统中所有节点的数据在同一时刻是否相同（这就意味着用户访问任何一个节点时都能够获得最新的相同的数据拷贝）。
□可用性（A）：在分布式系统中，节点中的一部分发生故障后，系统整体是否还能响应客户端的读写请求（这里的响应是指对数据更新是有效的，不会导致不一致的
问题）。
□分区容错性（P）：在分布式系统中，网络通信存在一定的延时，如果系统因为网络问题不能在有效时间内达成数据一致性，那么很可能会导致分布式系统分区，每个区域内数据均一致可用，但是分区之间无法保证一致性，因此产生分区后，当前操作必须在C和A之间做出选择。
CAP理论是指在分布式系统中，最多只能实现上面三个目标中的两点，要完全达到一致性，可用性和容错性是不可能办到的，其关系图如图2-13所示。因此分布式系统的设计往往会根据业务模型的目标需要而选择性地满足其中的条件，要么高可用、强容错，弱一致性或者最终一致性；要么强一致性、低容错性。
2.2.2 Paxos和Raft
针对分布式系统，网络中的节点一般能够很清楚地获取本机业务逻辑的事务处理上的结果状态，要么成功，要么失败了，但是获取其他节点的事务操作结果，却不是那么廉价的。因此，对于跨网络多节点的分布式事务，为了实现ACID特性，就需要引入一个称为“协调者”（Coordinator）的角色来统一调度所有分布式节点的执行逻辑，这些被调度的分布式节点称为“参与者”（Participant）。参与者依据自己的状况，根据协调者的提案做出自己的决定；协调者负责调度参与者的行为，并最终决定这些参与者是否要真正提交事务。基于这个思路，软件界衍生出二阶段提交2PC和改进版本的三阶段提交3PC两种协议。
谷歌的 Leslie Lamport 于 1990 年提出了一种基于消息传递且具有高度容错特性、一致性的算法Paxos。Paxos本质上是二阶段提交的一种算法，发布算法的论文比较复杂且晦涩难懂，为了简单介绍Paxos，下面围绕二阶段提交来分析算法过程。
Paxos算法定义了三种角色，具体如下。
□Proposer：提案的提出者。
□Acceptor：同意并接受提案者。
□Learners：被动接受Acceptor通知提案选定。
Paxos算法大概可分为两个主要阶段，具体如下。
阶段一：
1） 首先Proposer提出一个编号为（W, V）的提案，然后向超过半数的Acceptor发送这个编号为W的Prepare请求。这里的提案编号W实际上是一种事务id或者版本，V为该提案的内容。
2） 接下来，如果一个Acceptor收到一个编号为（W, V）的Prepare请求，而且编号W比Acceptor曾经回应过的所有Prepare请求的编号都要大，那么Acceptor就会将它已经接收过的编号最大提案作为回应反馈给Proposer，另外Acceptor不会再接收任何编号小于W的提案。
阶段一可简单理解为提案发起人先发出提议，初步统计有多少人会对其提议感兴趣。
阶段二：
1） 当Proposer收到超过半数以上Acceptor对其发出的编号为W的Prepare请求的回应，它就会接着发送一个针对提案的Accept（W, V）请求给那些已经对Prepare做出回应的Acceptor。如果Proposer收到所有的响应没有任何内容，Accept请求中V的内容由Proposer设定。
2） 当Acceptor收到一个编号为W的提案的Accept请求时，如果该Acceptor没有回应过编号大于W的Prepare请求，就向Proposer回应Accept结果。
3） 如果Proposer收到超过半数以上Acceptor回应的Accept请求，即可确定与提案W对应的V内容，在Acceptor中得到了确认。
阶段二可以看作Proposer对满足初步意向的人再次发出提案确认，若超过半数支持者就可以认为提案被接受。
Paxos算法的特点是强调CAP三原则中一致性胜过了可用性。由于Paxos难于理解，算法复杂，也不容易实现，因此Stanford 的 Diego Ongaro 和 John Ousterhout 提出了 Raft 算法，Raft 本质上与 Paxos 类似，在 Raft 协议中，一个服务进程可以扮演如下的三个角色之一。
□Leader：主要负责人，负责处理所有来往的交互、跟踪日志并复制存储，在一次 Raft 共识周期中，只能有一个Leader。
□Follower：跟随者，对本节点的状态信息进行变更，并向 Leader 做出回应。
□Candidate：候选人，作为 Leader 的候选对象。
Raft 也是二阶段提交的一致性算法，首先是 Leader 选举过程，其次在选举出来的
Leader 的基础上完成正常操作，例如日志复制和记账等。过程大致如下。
1）首先每个服务器都可以成为一个候选者Candidate，它发出请求，希望其他服务器Follower选举自己为Leader。所以一开始，大家都是Follower，个别服务成为Candidate。
2）其他Follower同意其成为Leader，并给出自己的确认OK。
3）服务器Candidate成为了Leader，这之后，它就可以向选民Follower发出命令，进行日志复制等操作，Raft服务器根据心跳进行日志复制的通知。
4）如果当前Leader发生了异常，剩下的Follower中其中一个可以成为候选者，发出新一轮Leader的选举请求，重复步骤1）。
5）当旧Leader从故障中恢复之后，只能成为Follower。在恢复阶段，它自己做出新的更新，在获取到新的Leader之后，需要进行回滚，日志状态必须与新Leader保持一致。
2.2.3 拜占庭容错及 PBFT
拜占庭容错源于拜占庭将军问题。拜占庭将军问题（Byzantine Generals Problem）是由 Paxos的作者 Leslie Lamport在20世纪80年代提出的旨在描述分布式对等网络通信容错问题的一个虚构模型。东罗马帝国的首都叫拜占庭，该国的将军们带领各自的军队，驻守辽阔疆土，抵御敌人。由于古代驻地相隔遥远，各军队之间只能靠信差传递情报。战争发生的时候，拜占庭军队内所有将军之间必须达成一致的共识，决定有赢的机会才去攻打敌人的阵营。但是，在这些将军之中可能存在叛徒和敌军的间谍，他们左右将军们的决定从而扰乱整体军队的秩序。这时候，在已知有将军谋反的状况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的作战决策变得尤为重要，拜占庭问题由此而来。
Lamport研究证明了在背叛者为m或者更少，将军总数大于3m时，忠诚的将军们可以达成战争决策上的一致。
要使拜占庭将军问题得到共识，必须满足如下两个条件。
1）总存在两个忠诚的将军必须收到相同的来自其他某个忠诚将军的命令，假设这个命令为C(n)。
2）假定第n个将军是忠诚的，那么他发送的命令和其他忠诚将军收到的C(n)一定相同。
换一个表述，这个模型可以简化为如下内容。
□所有忠诚的将军都遵守相同的决策。
□如果发出决策命令的将军是忠诚的，那么其他所有忠诚的将军都将遵从该决策。
在分布式系统中，在理论条件下，网络中的计算机节点遵循某种预置的协议，通过交换信息达成共识，并按照相同的协作策略行动。在这种场景下，系统很容易达成一致，但某些时候，系统中的计算机节点可能会因为硬件故障或者网络原因而出现异常或者错误，甚至是在网络正常时，因某些显式作恶，导致网络中不同的成员会对全体协作的策略做出不同的结论，破坏了系统期望的一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一，解决拜占庭问题就是要从理论和实践上找到一种方法，在某种不可信的环境中达成一致。
拜占庭问题的容错算法，实际要解决的是网络通信可靠，但节点可能发生故障或者异常情况下的一致性共识问题。
最早由Castro和Liskov在1999年提出的PBET（Practical Byzantine Fault Tolerant）是第一个得到广泛应用的 BFT 算法。
PBFT算法包括三个阶段来达成共识：Pre-Prepare、Prepare 和 Commit，流程如图 2-14所示。
图2-14中客户端C为发送请求节点，0到3为其他服务节点，3为故障节点，具体步骤如下。
1）Request：请求端节点C发送请求到其他任意一节点，假定发送到节点0。
2）Pre-Prepare：节点0收到C的请求后进行广播，广播至节点1、2和3。
3）Prepare：节点1、2、3均被要求收到广播处理完后，再次广播。节点1传播至节点0、2、3节点，2传播至节点0、1、3节点，节点3因为故障无法广播。
4）Commit：节点0、1、2、3在Prepare阶段，如果收到2F+1以上数量相同的请求，则进入Commit阶段，开始广播Commit请求。
5）Reply：节点0、1、2、3在Commit阶段，如果收到2F+1以上数量的相同请求，就对C进行反馈。
在PBFT中，如果满足N≥3F + 1，其中N为总节点数，F为有故障的节点总数，那么最终的一致性是可以达成的。
2.2.4 以太坊IBFT共识
2.2.2节描述的 Paxos 和 Raft 一般应用于中心化的分布式系统，或者受限应用的私有区块链，2.2.3节描述的PBFT 实用拜占庭共识可以应用于联盟链。这节将要介绍适用于以太坊私链或者联盟链的共识协议 IBFT。
PBFT 如果要用于区块链，需要做出很多调整才能顺利工作。首先，区块链里面所有验证者都可以被视为客户端，并没有特定的“客户端”发出请求并等待结果。另外，为了保持区块链交易打包持续进行，每轮都会连续选择一个提议者来创建区块提案以达成共识，每次共识的过程最终都将生成一个被大家验证的新区块，而不是操作类似 LSM 的日志记录或者文件。伊斯坦布尔 BFT（Istanbul Byzantine Fault Tolerant，IBFT），参考自 PBFT，作为以太坊 EIP（Ethereum Improvement Proposal）的 issue 650 被提出。
IBFT 定义了如下几个概念。
□Validator：区块验证参与者。
□Proposer：在本轮共识中，被选择作为出块的验证者。
□Round：共识周期。一轮回合以提议者创建区块提案开始，并以区块提交或轮次切换结束。
□Proposal：正在进行共识处理的新块生成提案。
□Sequence ：提案的序列号。序列号应该大于以前的所有序列号。当前每个建议的块高度是其相关的序列号。
□Backlog：存储共识信息日志。
□Round state ：特定序列和轮次的共识消息，包括预先准备消息、准备消息和提交消息，表示本轮共识状态。
□Consensus proof：可证明该区块的区块提交签名已通过共识流程。
□Snapshot：来自上一个时期的验证者投票状态。
IBFT继承了原始PBFT，通过PRE-PREPARE、PREPARE和COMMIT三个阶段达成共识。系统可以容忍N个验证器节点的网络中有F个故障节点，其中N=3F + 1。在每轮共识之前，验证器将默认以循环方式选择其中的一个作为提议者，然后提议者将提出一个新的分组提议并将其与PRE-PREPARE消息一起广播。在收到来自提议者的PRE-PREPARE消息之后，验证者进入PRE-PREPARED状态，然后广播PREPARE消息。这一步是为了确保所有的验证器都在同一个序列和同一轮上工作。在收到PREPARE消息的2F + 1时，验证器进入PREPARED状态，然后广播COMMIT消息。这一步是通知其同行，它接受建议的区块，并将该区块插入链中。最后，验证器等待COMMIT消息的2F + 1进入COMMITTED状态，然后将该块插入链中。
在IBFT协议中的块是最终确定性的，这意味着没有分叉，任何有效的块必须位于主链中的某个地方。为了防止错误节点从主链生成完全不同的链，每个验证器在将头插入链中之前，要将2F + 1接收到的COMMIT签名附加到头中的extraData字段。这样，块就可以进行自我验证，轻客户端也可以支持了。但是，动态extraData会导致块散列计算问题。由于来自不同验证器的相同块可以具有不同的COMMIT签名集合，所以相同的块也可以具有不同的块散列。为了解决这个问题，可以通过排除COMMIT签名部分来计算块散列。因此，我们仍然可以保持块/块散列的一致性，并将共识证明放在块头中。
IBFT是一种状态机复制算法。每个验证器都维护着一个状态机副本以达到块一致。
□NewRound：提案者发送新的区块提案。验证器等待PRE-PREPARE消息。
□PRE-PREPARED：验证器已收到PRE-PREPARE消息并广播PREPARE消息，然后等待PREFARE或COMMIT消息的2F + 1。
□PREPARE：验证器已收到2F + 1的PREPARE消息并广播COMMIT消息，然后等待COMMIT消息的2F + 1。
□COMMITTED：验证程序已收到2F + 1的COMMIT消息，并能够将建议的块插入区块链。
□FINALCOMMITTED：一个新块已成功插入区块链中，验证器已准备好进行下一轮。
□ROUNDCHANGE：验证器正在等待相同建议的圆号码上的ROUNDCHANGE消息的2F + 1。
IBFT共识状态机如图2-15所示。
IBFT共识算法在金融事务共识容错方面具有非常高的效率和性能，因此被作为以太坊企业联盟链quorum的重要共识算法。有人测试在一个区块包含2000个交易的初步测试中，IBFT共识区块链达到了400～1200的TPS。
2.2.5 PoW
PoW（Proof of Work）称为工作量证明，它是比特币和当前以太坊的核心共识算法。Pow可以简化为一个数学和经济模型：所有矿工公平竞争一个区块的挖矿权，每个矿工遵循一个规则，对候选的区块进行Hash运算，当运算Hash值小于当前难度系数时，就认为该矿工提供的候选区块满足条件，可以广播到全网验证并确认。区块链以最长的确认的区块主链作为链的基础，分叉会被抛弃，因此谁最先真实计算出来这个块的Hash，谁就会成为这个块的矿工，矿工享受这个出块周期的收益，获得特定数量的价值奖励。区块中有个参数nonce，矿工每次计算候选区块的Hash值时，并不能获得期望的值，因此要不断调整nonce进行周期性Hash计算，以期获得满足条件的那个Hash值。尝试Hash的计算可以表述为下面的表达式：
f = Hash（nonce+ 区块其他数据）< dif?culty
PoW 实际上是一种计算能力的竞争的公开比赛，强者胜出。其作为比特币和当前以太坊的共识算法，充分体现了节点分布扁平、计算竞争公开、结果验证透明、不可篡改的特点， 奠定了全网完全去中心化技术的基础。
以太坊的 PoW 实现算法称为Ethash，它依赖于大小约 1GB 的数据集的初始时期的生成，称为有向非循环图（DAG）。DAG 使用 Dagger-Hashimoto 算法的一个版本，该算法结合了 Vitalik Buterin 的 Dagger 算法和 Thaddeus Dryja 的 Hashimoto 算法。Dagger-Hashimoto 算法是 Ethereum 1.0 使用的挖掘算法。随着时间的推移，DAG 会线性增长，并在每个时代更新一次（30,000 块，125 小时）。以太坊的 PoW 算法和比特币有点差异，挖矿的效率基本与 CPU 无关，却与内存大小和内存带宽正相关，更能抵御专用 ASIC 的计算垄断。
PoW 算法步骤及说明如下。
1）通过扫描 DAG 的先前块头来为每个块计算种子。
2）缓存是一个 16MB 的伪随机缓存，根据种子计算，用于轻量级客户端的存储。从缓存生成 DAG 的数据，完整客户端和矿工可以存储这些数据。
3）矿工通过对数据集进行随机切片并将它们散列在一起进行挖掘。可以使用存储的高速缓存和低内存来执行验证，以重新生成所需数据集的特定部分。
PoW 显然是一个简单易行的共识算法，但是也面临两个突出的问题：一部分资金通过设计专用硬件（例如，专用 ASIC、GPU、内存）来提高挖矿效率，构建矿池来垄断挖矿权益，偏离了区块链去中心化的本质；另外因为全球矿池节点通过不断 Hash 计算尝试来竞争挖矿权，浪费了大量能源。这些因素阻碍了区块链的发展，对以太坊来说，其也面临相同的问题，因此以太坊提出了基于 PoS 的 Casper 共识算法。
2.2.6 Casper
PoW 共识需要浪费大量的能源，制约了区块链的可持续发展。于是，有人提出了一种称为权益证明的 PoS（Proof of Stake）算法，它将PoW中的计算算力改为系统权益，拥有权益越大则成为成功验证区块的概率越大。
PoS可以避免大量的挖矿能源浪费，但是也有一个天生的不足，即资产权益越多的人，获得验证出块的几率就会越大，作恶产生分叉的可能性也就越大。以太坊需要一种惩罚作恶的经济模型来修正PoS的不足，于是以太坊最终进化到Casper共识协议。
Casper协议工作在PoS之上，重点在于平衡PoS恶意行为代价下的经济模型，确保以太坊共识可持续运转。Capser工作机制的过程主要如下。
1）潜在的矿工需要预先在链上抵押一定比例的权益资产作为保证金。
2）接着这些矿工发现一个可以被加到链上的新区块的时候，下赌注来验证它并打包。
3）当这个区块被加到链上并通过其他人验证时，下注矿工将得到一个与赌注成比例的奖励。
4）如果存在一个打包矿工恶意做假、试图破坏以太坊共识原则，就会立即遭到惩罚，该矿工已经发放的奖励会被没收，并罚没其保证金。
Casper 设计的初衷就是奖励正向贡献，严惩负向作恶。为了达到这个目的，Casper 设计了严格的规则来保证网络的安全，也包括惩罚没有尽责的矿工，使得他们保持“出块”的日常工作节奏，如果放松懈怠就会导致自己的保证金损失。Casper 这种强调惩罚的机制，对那些怀有作恶动机的矿工产生了强烈的风险约束，从而能够保证以太坊的共识达成。
以太坊按照版本循序渐进的过渡思路，提出了两个版本的 Casper，即 Casper FFG 和Casper CBC。
Casper FFG 是由以太坊创始人 Vitalik Buterin 主导的一个混合 PoW/PoS 共识机制。它将是第一个可以被应用的以太坊 Casper 版本，也是为了在新旧两种共识之间建立一个缓冲的转换过程，使得共识算法在改变前后有比较好的过渡。Casper FFG 的设计方式是在 Ethash PoW 工作量证明协议上叠加权益证明，新区块仍然通过工作量证明方式由矿工打包产生，接着每 50 个区块将触发一个权益证明机制检查点来进行验证，通过这个验证过程来验证区块的最终的合法性。简单来说，Casper FFG 更侧重于通过如下几个步骤的组合来将以太坊从 PoW 过渡到 PoS。
Casper CBC 是由共识专家 Vlad Zamfir 主导的另外一种以太坊 Casper 共识协议，其与传统协议的设计方式有点不同，他提出了一种在“构建中修正”的观点，要点具体如下。
□设计一种顶层通用而又灵活的协议框架，通过定义，证明再继承的这种迭代形式完善成为最终的共识系统。
□协议最终工作在纯 PoS 模式下，没有 PoW。
□共识协议由两个关键的因素组成，通信的消息和参与的角色验证人。消息由三元组(数据，验证者，证明)决定，消息的时序性可影响到验证结果的真伪。
□验证者公示的数据必须是在以前已经达成共识的数据或者函数方法中推导得出，验证者提供的数据和证明方式必须一致，不能自相矛盾。
□违背共识原则包括两个主要方面：一个是接收和处理非法消息，导致错误结果；另外一个是出现了模棱两可的错误，无法确定性获取结果的真伪。
Casper CBC 机制其实是一种比较系统和科学的共识方法论，形成共识的方法将不仅仅局限在以太坊，任何遵循和实现了这套理论的共识算法都将有比较好的安全和效率。
这两个版本的 Casper 本身都是作为独立的项目发展，CBC 更多的还是理论阶段，以太坊最终可能会先采用 FFG 作为第一个可以落地的 PoS 版本。
Casper 的设计，总结起来看，参考了如下的指导设计准则。
1）设计行为的经济学。明确的经济机制设计可以实现其他社会契约中隐含的经济激励。
2）最大化攻击成本。攻击者对协议功能进行攻击的损坏程度应受到一些行为因素的约束，损失的代价应该与成本匹配。换句话说，最大限度地减少用于攻击协议的“攻击利益倍数”。
3）公共成本效益，而不仅仅是私人层面。对于公链来说，协议经济学应该考虑社会成本和收益，对于像比特币那样的 PoW 共识机制，就需要看到大量挖矿导致的能源浪费问题。
4）防止规模经济。中心化违背了公共区块链的基本原则，防范规模经济可以防止这些中心化的因素，以便构建更安全的区块链。
5）网络安全要重视惩戒。“经济价值的损失”确保了 PoS 共识机制的安全可靠。
6）寡头垄断。永远有期望获取中心化利益的力量存在，区块链的设计需要考虑这个因素的存在，并考虑最大化抑制它的发展。
7）责任安全。设计应尽可能地将错误归因于某些作恶者。
8）平衡的治理范围。设计不允许作恶者阻止区块链持续提出并对检查点/块进行投票。
9）最小同步性假设。为了保持区块链的增长和用户的活跃度，Casper 具有最小的同步性假设，验证者会定期重新登录在线工作。
10）去中心化东西应该能够再生。只有当共识协议可以实现在永久删除其中一个节点之后，其他的所有节点完全恢复时，这个共识协议才会被认为是去中心化的。
11）禁止审查。主要权衡的是验证者通过故意离线来实现对区块链网络的损害攻击。选择正确的审查与奖励和处罚一定数目的资本将是实现这一目标的关键手段。
2.2.7 以太坊性能
以太坊已经发展成为一个在全球广受欢迎的公链区块链网络，在2017年疯狂的ICO项目众筹的加密猫售卖过程中，广大区块链使用者深受其严重的网络拥塞和交易确认延迟问题的困扰。可见，以太坊的网络性能已经成为一个严重而急需改进的问题。
以太坊当前采用PoW共识，需要将交易区块在全网广播确认，实际测试中最大不会超过20TPS，也即最多1s内只能有20笔交易进行从提交到确认的流程。另外由于以太坊的交易状态都是串行处理，节点对交易的大并发处理能力远远不够，导致很多交易都阻塞在交易池中。图2-16是从Etherscan网站中截取的区块时间统计图，当前平均的区块时间大概在15秒（block/15s）；图2-17是截取的pending交易统计图，每秒pending交易数峰值达到20k之多，网络繁忙的时候甚至可以达到30k。
造成以太坊性能不高的原因主要有如下三个方面。
1）PoW共识算法的低效率。PoW需要不断竞争Hash算力，为了维持区块不过分分叉，必须设置挖矿的困难系数和区块确认时间。困难系数用于调整挖矿难易程度，使整体矿工算力保持均衡；另外由于点对点网络的范围很广，交易和区块广播需要一定时间才能遍及网络，如一个区块确认需要大概15秒，这也限制了性能。
2）Gas 机制限制。为了防止恶意攻击，以太坊对网络交易设计了 Gas 机制，这个机制在业务逻辑和 EVM 合约执行都做了 Gas 消费的检查和计算，其过程也遍布以太坊的几个主要方面，包括矿工的奖励、区块的 Gas、单账户的资产以及合约调用都有 Gas 的运算。区块的 Gas Limit 在约束区块的计算容量的同时，限制提高区块的 Gas 上限，降低区块时间，也会导致高陈腐率（high stale rate），并降低了面对网络攻击的应对风险。
3）以太坊的串行执行。为了防止双花问题的发生，以太坊无论是单节点 ETH 转账和合约执行，还是全网的交易确认，实际上都是串行执行的。虽然节点的客户端可以利用 CPU 多核的能力，但是在全节点上，每个节点都是复制全局的状态树共享，因此无论是在单节点上的 EVM 指令执行，还是在以太坊全局交易上，每个交易都是按顺序执行确认的，无法实现全网络的并行化，这也是导致以太坊性能不高的主要原因。
针对以太坊当前的性能问题，以太坊社区和区块链行业相应提出了不同的扩展性方案。
关于可扩展性方案，下面介绍 sharding 分片、状态通道和 Plasma 三种。
（1）sharding 分片
以太坊团队提出了链自身的共识改进和分片方案。以太坊的 Ethash PoW 共识将根据Casper 的验证进展，过渡到 PoS 类型的共识机制，目前 Capser 开发到了 POC3 阶段，最新模拟测试达到 3秒的出块时间。
此外，以太坊 sharding 分片方案，旨在提供以太坊的并行性，提高交易的灵活性和吞吐量。在主链之外，新以太坊系统会创建很多协作的分片链，每个分片链会构建自己的交易链。在以太坊主链上将部署一个做验证人管理员合约（VMC）的特殊合约、关联分片和分叉。
（2）雷电网络
雷电网络是一种状态通道的以太坊扩展方案。雷电网络是一种类似比特币闪电网络的线下支付网络，用户可以进行点对点交换转账签名消息并验证，而不是所有的交易都放到区块链上处理，它的显著特点是具有很高的交易处理能力，具体如下。
□可扩展：网络节点越多，雷电网络能够处理的转账能力越高。
□更快：通道转账，转账时间极短。
□保护隐私：通道上多次转账的过程不会在主链记录状态。
□互操作性：遵循以太坊 ERC20 标准的代币 API 互操作。
□更低的费用：通道转账不上链，交易成本很低，和以太坊的 Gas 相比几乎可以忽略。
□微支付：通道特性，适合小额多笔大批量交易，面对微支付的场景非常合适。
雷电网络通过以太坊网络中的点对点支付与保证金存款保留了区块链系统所具备的保障机制，同时线下点对点的快速交易保证了很高的交易处理速度。
（3）Plasma
Plasma是另外一种链下多子链的扩展方案。首先在以太坊主区块链上运行一些智能合约来实现主链和Plasma侧链的交互和状态维护，Plasma侧链以内的交易并不需要每笔都发送到合约中来进行处理，只有从主链到Plasma或者相反方向的“加入”和“退出”才会触发。这就意味着大量的交易被分解到Plasma侧链内处理，侧链的安全性由主链以太坊背书。
另外Plasma实际上是一个链簇或者链树，Plasma网络内还可以组成子链，外部的Plasma主链为其他的信任背书，这样，就组成了以以太坊为树根的树形区块链，大量的交易聚集在对应的子网中处理，不需要由以太坊直接干预，而且安全方面也不会有太多的问题。这种扩展方式提供了以太坊协议生态的区块链吞吐量。
2.3 图灵完备
区块链技术的先驱比特币，是一种点对点的去中心化网络虚拟货币，可跟踪并记录虚拟货币资产的状态变化。“状态转换函数”可实现这种状态转换。 比特币开创和发明了一种交易状态描述：未使用的消费输出 UTXO（Unspent Transaction Outputs）。“状态转换函数”就是比特币全网所有节点可以执行和验证的一个逻辑执行过程，这个过程实现了比特币全网 UTXO 的变更并记录。
改变UTXO状态的“状态转换函数”是一种用基于堆栈的编程语言所编写的比较复杂的脚本。比特币的某个时刻的UTXO可以被某个用户触发，并提供相应的被证明参数，例如发起者的公钥和数量，同时这个UTXO也可以被基于堆栈的编程语言所编写的脚本所拥有。当比特币用户请求改变UTXO，这个过程会触发脚本执行，验证交易和拥有这个UTXO的地址，如果验证成功，则返回1，否则返回0。
2.3.1 比特币脚本
比特币在交易中使用脚本来改变UTXO，这种脚本比较简单，基于堆栈数据结构按从左向右处理，并特意设计成不支持循环指令LOOP，是一种非图灵完整性的逻辑执行器。
当比特币网络中发生了一次由用户发起的转账交易时，在交易中会生成若干实现改变UTXO的指令和参数，这个指令就是比特币脚本的基本操作元素。指令组合的描述意思包含了这个交易发起者的UTXO作为输入，产生一个接收者可以消费的UTXO作为输出。这个过程包含两个关键信息，具体如下。
1）公钥，交易相关方的公钥，并由此生成的比特币的Hash地址，地址被包含在脚本之中。
2）签名，接收者签名，证明一笔资金将是他的未消费输出。
整个比特币的交易，实际上包含两个脚本，一个是锁定脚本，另外一个是解锁脚本。锁定脚本包含在本次交易的输入的UTXO之中，包含了这次交易如何验证的指令代码和参数，可以理解为对本次交易输入UTXO被花费的证明条件；关联的解锁脚本，解锁脚本包含了发送者的公钥和签名，并随交易广播到网络之中，网络节点可以运行该解锁脚本，验证和确认这次交易可以消费掉输入的UTXO，并产生一个新的UTXO，老的输入UTXO被比特币账本记录为已消费。下次接收者作为新交易的发起者发起另外一笔交易时，就需要在这个刚输出的UTXO中附上新的锁定脚本，证明接收者可以花费的证明。
锁定脚本：DUP hash160 EQUALVERIFY CHECKSIG
解锁脚本：
比特币这种脚本语言简单高效，但是缺失循环指令 LOOP，无法实现稍微复杂的逻辑。不支持循环语句的目的是避免交易确认时出现无限循环，对于这种多次循环，即使没有 LOOP 也可以通过大量的 if-else 来实现，导致了代码空间的极大浪费和编程工作的低效率。对于使用智能合约来实现复杂的业务逻辑来说，这种多次循环就显得捉襟见肘了。
图2-18展示了一个实际的比特币交易脚本的执行过程。
2.3.2 以太坊虚拟机（EVM）
以太坊最大的价值在于智能合约，以太坊虚拟机（Eetheruem Virtual Machine，EVM）是执行交易或者合约代码的引擎。在虚拟机中，合约像众多的应用程序一样可完成比较复杂的逻辑功能；EVM 支持循环操作指令，任何复杂可以设想的程序都可以得以在其上顺利运行。像其他语言的虚拟机一样，例如支持了Java、Kotlin、Scala等高级语言的JVM，EVM 提供了一个合约可以安全和隔离的运行环境，每个合约都有其独立的运行时堆栈。EVM 栈最大支持 1024 个元素，每个元素 256 比特，这意味着以太坊智能合约处理器的字长是 32字节，堆栈深度达到1 KBytes。
Vitalik Buterin 在其以太坊设计原理论文“Design Rationale”中针对 EVM 进行了几点总结，大概归纳如下。
- EVM设计目标
EVM的设计目标具体如下。
□简单性：虚拟机操作码尽可能的少而且低级；数据类型和结构也尽可能的少。
□总体确定性：VM规范没有任何可能产生二义性的空间，结果是完全确定性的。而且计算步骤非常精确，完全可以为Gas的消耗提供度量。
□节约空间：EVM的汇编应尽可能紧凑。
□满足应用特殊性设计：20字节的账户地址，32字节密码学通用处理，为读取区块和交易数据与状态交互提供便利。
□简单安全：为了让VM不被攻击，建立一套Gas消耗作为运行费用的模型。
□优化友好：虚拟机可以优化，可以采用即时编译（JIT）和其他加速技术来构建虚拟机。
- EVM特殊性
EVM也包括如下特殊设计。
（1）区分临时/永久存储
先来看看什么是临时存储和永久存储。
□临时存储：只在VM的每个合约运行时存在，例如函数中的一些内存，用完即释放。
□永久存储：存在区块链状态树中，并持久化。
（2）栈/内存模式
计算机中的数据存储一般有三种：栈、堆和永久存储。对于临时存储，栈和堆都可以称为内存模式，或者是寄存器和内存的混合体。在这种存储基础上，每个指令都有三个参数，例如，ADDR1R2R3:M[R1]=M[R2]+M[R3]。选择栈范式的原因很明显，它使代码量缩小到原先的四分之一。
（3）32字节长的处理字
在比特币系统中，指令处理的字长大小是4字节或8字节。4字节或8字节对存储寻址或加密计算来说局限性太大，也很难建立相应的安全的 Gas 模型。32 字节是一个理想大小，因为它足够存储众多加密算法的实现以及更大的地址空间，还不会因为太大而导致处理效率低下。
- EVM设计中存在的不足
EVM 在实际以太坊执行交易中的表现并不完美，存在许多需要改进的地方。
（1）256bit 整数
EVM 采用 256 bit 整数，可以兼顾众多加密学的计算，以及以太坊中大数的表示，例如 1 Ether = 10 的 18 次方 Wei。但是这也带来了一个问题，很多计算无法与当前计算机共用 64 位字长兼容，一方面无法充分利用原生计算机系统的性能优势，另外一方面相对于传统程序开发者来说，智能合约的处理不那么兼容，需要适应。
（2）EVM 中的栈
EVM 指令操作都是基于栈，而不是寄存器，这样处理起来比较简单，且易于优化，但是缺点是其并没有寄存器操作来的效率高，而且因为内存空间无法复用中间状态，空间占用会更大。
（3）不支持浮点数
EVM 不支持浮点数运算，与现代的处理器相比较起来还比较原始。在一些涉及科学计算和复杂金融曲线的运算中，不支持浮点数会带来非常大的麻烦，只能通过整形数放大来规避无法表示精度的问题。
2.4 本章小结
本章主要从区块链共性问题、加密学、共识问题、智能合约支撑程度几个大的方面和一些细节详细地分析了以太坊的设计考虑和特点。通过这些内容，我们可以比较清楚地了解到以太坊使用了 SHA-3 作为基础 Hash 算法，椭圆曲线加密算法进行摘要签名，另外以太坊开启了区块链 2.0 时代的智能合约，其中合约执行的虚拟机环境有其通用的设计考虑，同时也有不足之处。最后本章还分析了当前以太坊性能问题的制约因素。
