PKU-区块链技术与应用
北大肖臻 区块链技术与应用
第一节 密码学基础
crypto-currency 加密货币,加密货币实际上不加密
加密货币用到的密码学算法:哈希函数、签名
哈希函数的三个特性:
- collision resistance/free 抗哈希碰撞,碰撞客观存在,但没有高效的方法,能够人为构造哈希碰撞(无法证明,但可以用实践经验)
MD5已经不安全了,可以人为构造哈希碰撞
- hiding,哈希函数是单向函数
两者合作实现digital commitment/equivalent of a sealed envelope(封起来的信封)
预测结果不能提前公开 H(result || nonce)
- puzzle friendly 谜题友好性
找nonce,要求H(block header || nonce) <= target,落在指定的范围之内,挖矿的过程没有捷径,只能一个个去试,工作量证明(Proof of work)
挖矿很难,但验证很容易 difficult to solve but easy to verify
BTC中用到的哈希函数:SHA-256(Secure Hash Algorithm - 256 bit)
比特币中的账户开户:创建一个公私钥对,来自非对称加密体系asymmetric encryption algorithm
非对称加密中:
-
发信息时加密用接受者的公钥,解密用接受者的私钥,加解密都是用同一个人的公钥和私钥,公钥公开,私钥保密。其中,公钥相当于银行账号,私钥相当于密码
-
签名用我的私钥,别人验证签名用的是我的公钥
生成公私钥对的随机源要好a good source of randomness,签名时也要用好的随机源
比特币中一般是先取哈希后签名,此时要签名的对象就变成了256bit的二进制数。
第二节 BTC数据结构
BlockChain 区块链
普通结构体存储的是一个结构体在内存中的(起始)地址,哈希指针还需要保存该结构体的哈希值。
Blockchain is a linked list using hash pointers.
genesis block 创世区块
most recent block 最近的区块
通过这样的数据结构可以实现防篡改记录 tamper-evident log
这个数据结构的好处是只需要保存一个哈希值,就可以确保整个区块链的篡改感知
Merkle tree 默克尔树
binary tree 二叉树
现用哈希指针代替了普通的指针,得到Merkle Tree。
根节点也可以取个哈希,叫作根哈希值root hash,用根哈希值就可以检测出树中任何部位的修改。底下的数据块是一个个的交易tx
每个区块分为block header和block body,block header存放了由所有交易组成的merkle tree的根哈希值,而block body存放若干交易的具体信息,相当于交易的结构体数组
block header能够提供Merkle Proof,全节点提供路径上需要用到的哈希值,即可证明交易是被写入到了区块链中,也叫做Proof of membership或者Proof of inclusion,复杂度为
如果要证明Proof of nonmembership,即证明交易不存在于区块链中,只能对叶节点进行遍历。如果能够能够对交易的哈希值进行排序,那么可以采用二分查找的方式,复杂度为
只要数据结构是无环的,都可以用哈希指针来代替普通指针。
第三节 BTC共识协议
介绍
央行可以发行带有签名的100元货币和50元货币:
然而,这个数字货币本质上是文件,可以无限复制下去。Double Spending Attrack 双花攻击,是指一份钱花两次的攻击。
如果每个数字货币上都有个编号,央行的数据库要记录每个数字货币在谁手里,这个方案理论上可行,但太过于复杂。因此引入比特币,让广大群众共同维护这个账本。
交易包含输入和输出部分,输入要说明币的来源以及A的公钥,输出要说明收款人的公钥的哈希
两种哈希指针,图中弯曲的指针用来验证币的来源。以铸币交易为例,中,输出说明了A的公钥的哈希值,那么在下一笔交易中,就可以通过A的公钥去溯源币的来源。
钱包的地址是通过公钥推算出来的,具体过程如下:
- 公钥 → SHA-256 → RIPEMD-160 → 公钥哈希
- 公钥哈希 + 网络前缀 → 双重SHA-256 → 校验和
- 公钥哈希 + 网络前缀 + 校验和 → Base58Check编码 → 钱包地址
铸币交易中,输出是收款方的公钥的哈希,可以用作币来源的证明,此时如果有B的同伙B’冒名顶替A,发起B’->B(5),那么B’的公钥哈希于A的公钥哈希对不上,验证不会通过,交易不会被写入区块链中,这个过程是通过比特币脚本BTC Script进行
比特币包含了区块头和区块体,包含的内容如下表所示:
Block Header | Block Body |
---|---|
version 比特币协议版本 | transaction list 交易列表 |
hash of previous block header 前一个区块的哈希值(即哈希指针) | - |
Merkle root hash 区块体中所有交易组成的merkle tree的根哈希值 | - |
target 挖矿难度目标阈值 | - |
nonce 随机数 | - |
BTC中要解决的谜题puzzle:
对比比特币中的全节点和轻节点:
full (validating)node 全节点 | light node 轻节点 |
---|---|
保存区块链中的所有信息 | 一般无法独立验证交易的合法性 |
负责区块链的构造和维护 | 只是利用区块链的信息进行一些查询 |
账本的内容要取得分布式的共识 distributed consensus,比如distributed hash table要对key-value对进行共识。
FLP impossibility result:在一个异步系统(网络传输时延没有上限)里,哪怕一个节点是faulty的,也不能达成共识(悲观)
CAP Theorem:
- Consistency 一致性
- Availability 可用性
- Partition Tolerance 分区容错性
三个性质中只能满足两个
比特币中的共识协议 Consensus in BitCoin
假设恶意节点是小部分,大部分都是好的节点,任何基于投票的共识机制,membership,如Hyperledger Fabric都不可行
女巫攻击sybil attrack,一直产生账户,账户量超过50%,就可以掌握投票权
比特币用算力投票,尝试各种nonce值(4 Bytes),如果某个节点找到了这个nonce,那么这个节点就有了记账权
合法的区块:区块中的交易都合法,但该区块仍然可能不被接受:最长合法链原则 longest valid chain
分叉攻击 forking attack,通过在区块链中插入区块导致交易被回滚。假如两个节点同时获得记账权
大家争夺记账权,希望让合法交易都写入区块链中。比特币设计了一个出块奖励block reward。拥有记账权的节点在打包交易时可以包含一个铸币交易coinbase transaction,唯一一个产生新币的途径。如果将区块链插入到链的中间,大部分诚实节点不会接受,因此会做无用功。
比特币中的共识是去中心化账本中的内容,只有获得记账权的节点才能往该账本写入交易,而只有通过计算puzzle才能获得记账权。因此hash rate越高的节点获得记账权的概率越大。
可以防范女巫攻击,因为无限产生账户不会让hash rate增加。比特币叫数字黄金,因此寻找nonce的过程相当于淘金,也就叫挖矿,争夺记账权的节点也叫作矿工miner
第四节 BTC具体实现
比特币是基于交易的账本模式 transaction-based ledger,无法直接知道每个账户上有多少钱,而可以通过交易记录间接推算。
BTC中的全节点需要在内存中维护一个UTXO的数据结构Unspent Transaction Output
UTXO中的每个元素要给出产生这个输出交易的哈希值,以及是第几个输出,为了检测Double Spending,total inputs = total outputs
transaction fee,用来激励矿工打包交易
矿工收入=transaction fee+出块奖励
10分钟出一个区块,21万个区块后,记账奖励减半,故每过4年左右时间交易费减半,交易费会逐渐成为主要收入
ETH用的是account-based ledger,显式记录每个账户上的余额,不需要显示的说明币的来源
BTC中区块的数据结构:
区块头的数据结构:
如今挖矿难度越来越大,遍历nonce实际上已经不满足难度要求,现在可以将merkle root hash和time作为extra nonce来使用,而要改变merkle root hash,可以改变coinbase tx中的coinbase域来实现,里面可以写你的人生感想
交易的验证过程:将该交易的输入脚本和提供该币来源的输出脚本进行配对执行,如果顺利执行则说明交易合法
对挖矿进行概率分析
每次挖矿可以看作是一次伯努利试验 Bernoulli trail: a random experiment with binary outcome,典型抛硬币
多个伯努利试验构成了Bernoulli process: a sequence of independent Bernoulli trails,无记忆性memmoryless,做大量的试验,前面的实验结果对后面的实验没有关系
可以用泊松process来近似,出块时间服从指数分布exponential distribution
概率密度曲线:
progress free,过去做的工作都白做了,很无情,但恰恰是比特币公平性的保证
出快的比特币数量构成了一个几何序列geometric series
21w * 50 + 21w * 25 + 21w * 12.5 + …
= 21w * 50 * (1 + 0.5 + 0.25 + …)
= 21w * 50 * 2 = 2100w
即系统中所有比特币的总量,比特币的稀缺性是人为造成的,但挖矿的过程对比特币的安全性是至关重要的
BitCoin is secured by mining. 挖矿表面上没有实际意义,但对维护系统安全性至关重要。
安全性分析
能不能保证写入区块链的交易都是合法的?不能保证记账权落入诚实节点手里,也就是说恶意节点有可能也可以拿到记账权。
- 能偷币吗?不能,因为不能伪造别人的签名
- 如果硬写交易呢?不能,因为诚实节点是不会接受这个交易的,而且拿到记账权的节点损失很大,既没有攻击成功,也白白损失了这笔出块奖励
- 能double spending吗?不能,可以通过等待N个区块来防范攻击,因为在等待了N个区块后,发生分叉攻击的可能性大大减小。也叫作多等几个确认confirmation,比特币中要求等6个区块才能确认合法,1个小时左右。
区块链是不可篡改的账本irrevocable ledger,但这只是概率上的保证
zero confirmation用的很普遍,因为诚实的节点不会接受双花的交易
-
能否故意不包含某些合法的交易?可以,因为总有诚实节点会打包这些交易,可能是打包下一个区块,一个区块大小为1MB
-
selfish mining,自己挖了很多区块藏着,在后面一下子公布所有区块,将另一条分叉干掉?可能性很小,前提是有恶意的节点算力占据了全系统算力的很大一部分,才会发生这种攻击
selfish mining有没有什么好处?减少了算力竞争,一次性拿N份出块奖励,但是也有很大的风险
第五节 BTC网络
The BitCoin Network 工作原理
工作在应用层 application layer,运行比特币协议BitCoin Blockchain
网络层协议运行P2P Overlay Network,比特币运行的P2P网络与普通的P2P网络不同。普通的P2P网络中会有Super node或者Master node
BTC设计的原则是:简单鲁棒而非高效
simple, robust, but not efficient
flooding,不考虑实际的网络结构
best effort 尽力而为,去中心化网络中会有很多延迟、节点恶意性的问题
第六节 BTC挖矿难度
H(block header) <= target,SHA-256,2^256,要求前面有多少个0,通俗来讲是这样
target越大时,挖矿难度difficulty越小
出块时间太短会有问题,假设出块只需要1s,而传播需要几十s,那么分叉会成为常态,那就会出现二分叉、三分叉,甚至是十分叉,分叉越多,越会危害系统的安全性。
诚实节点的算力被分散,导致女巫攻击变得容易
ETH创建了新的共识协议ghost,将出块时间调整为15s。时间长度都需要稳定,不能无限减少下去。
对orphan block也有一些uncle reward
BTC中,每2016个区块后,约等于2周,就调整一次区块,调整公式:
或者
其中
实际代码中有4倍的限制,后面的比例因素大小在中
如果恶意矿工不调整响应的target,那么它的nbits域不对,诚实节点是不会接受的
比特币的这些参数可能就是自己想出来的,比较保守的采用,make sense罢了,不一定最优
第7节 BTC挖矿
缺省=默认=by default
比特币网络中大部分都是轻节点
全节点如果监听到有别的矿工挖到区块,此时应该停止已有的挖矿,然后在本地重新组装候选区块,重头开始挖。不可惜,因为memoryless和progress free,前后挖矿的概率一样
BTC的安全性由密码学和共识机制保障
BTC中的挖矿设备
用于大规模并行计算,而浮点数运算是闲置的。现在用ASIC(Application Specific Integration Circuit)芯片挖矿
一个ASIC只对应一个mining puzzle,除非新币为了吸引挖矿,就会采用同一个mining puzzle,叫merge mining
有些加密货币:Alternative mining puzzle,能做到ASIC resistance,抗ASIC芯片,让通用计算机也能够挖矿
大型矿池,一个全节点驱动很多矿机
全节点的其他功能由矿主实现,计算哈希值的操作由矿工实现
原来的的挖矿难度很难,但矿主可以通过降低挖矿难度(增大target)给矿工分配任务,也就是一个share,当矿工挖矿得到了一个almost valid block提交给矿主时,矿主将矿工提交的share数目作为其工作量证明,在真正挖到矿时进行分配
假如矿池达到了51%的算力,具体可以发起哪些攻击?
- 分叉攻击,使得大额交易回滚
- Boycott,估计不打包A的交易,只要与A有关的交易都不让上链。与forking attack不同的是,boycott不需要等待6个确认区块
- 不可能盗币
矿池可能带来的潜在危害 on demand computing/mining,需要用到的时候可以随时召唤
第八节 比特币脚本**
locktime:等待多久时间后写入区块链
Alternative Coin
比特币脚本语言,是基于栈的语言
第九节 BTC分叉
- state fork 意见不一致
- forking attack,也称deliberate fork 故意的分叉
- protocol fork 协议不一致
- hard fork 硬分叉
- soft fork 软分叉
hard fork 硬分叉
block size limit区块大小限制:1M->4M
只要旧节点不肯更新软件,那么分叉一直存 在
soft fork 软分叉
block size limit区块大小限制:1M->0.5M
旧节点会生活的比较抑郁,因为挖出来的区块都白挖了。系统不会出现永久性的分叉。
这种特性会促使旧节点赶紧更新,保证自己的收益。
软分叉的例子:
- 给coinbase域赋予一些新的规则。实际上coinbase域前8Byte可以用作extra nonce
- 有人提出可以存放UTXO组织成Merkle Proof的根哈希值,也就是各个全节点记录的账本哈希,来用于轻节点对自己账户上的证明。在这种情况下,旧节点认新节点,但新节点不认旧节点
- BTC中一个著名的软分叉:P2SH (Pay to Script Hash)
总结:
- soft fork:只要系统有半数以上节点,系统不会出现永久性分叉
- hard fork:必须所有节点都更新才不会出现分叉,否则一定出现分叉
第十节 课堂问答
- 转账如果接收者不在线怎么办?
不需要接受者在线,在不在线没有关系
- 假设全节点接受到转账交易,有没有可能这个收款地址是全节点以前都没有听说过的?
有可能,比特币创建时不需要通知其他人
- 如果你账户的私钥丢失了,该怎么办?
凉拌,账户里的钱就永远取不出来了。有些加密货币的交易所,是中心化的交易机构,类似银行开户也需要身份验证,私钥是由交易所来保管的
但是交易所目前缺乏监管,会存在黑客攻击的问题,因此交易所也没那么安全
Mt. Gox,被黑客攻击,破产,也有可能卷款跑路
- 如果账户的私钥泄露了,该怎么办?
赶紧把账户的钱转到另一个新的安全账户上
- 如果转账时写错了地址怎么办
没办法,没有办法取消已经发布的交易
- Proof of Return中RETURN后面的语句根本无法执行,为什么会写在区块链里呢?
验证的过程是将交易的输入和币的来源交易的输出拼在一起执行,如果没有抛出错误则认为交易合法。
OP_RETURN语句是写在当前交易的输出脚本中的,因此在验证交易合法性的时候OP_RETURN是不会被执行的。而如果后面有人想花这笔钱时才会执行到这条语句,这个时候才会抛出错误。
- 矿工能不能偷nonce?
不能。coinbase tx域。如果偷nonce的话,就得修改coinbase tx改成自己,就会改变merkle root hash,最终导致nonce无效
- 事先怎么知道哪个矿工会挖到矿
事先不需要知道哪个旷工会得到这个交易费 total inputs > total outputs,那么差值就可以作为给矿工的交易费
第十一节 BTC匿名性
Bitcoin and anonymity/privacy
psseudonymity
unnamed lake 未名湖
普通银行的匿名性比比特币要好,我要查某个账户上有多少钱,银行的账本是保密的,但比特币的账本是公开的
Inputs: addr1(4), addr2(5)
Outputs: addr3(6), addr4(3)
故找零的地址是addr4
有可能破坏匿名性的方法:
- 一个人生成了很多个账户,但账户很有可能被关联起来
- 与社会真实身份会产生关联
- 实体世界中,用比特币支付时。但这是个bad idea
比特币一做交易就会与实体世界发生联系,直接就会被抓
比特币中的匿名性没有我们想象中的好
hide your identity from whom?
使用比特币如何尽可能的提高匿名性?在网络层在学术界已经有很好的解决方法,洋葱路由TOR,在Application层有很多跳
提高匿名性的做法:coin mixing,让人分不清楚币是从哪来的,然而coin mixing也存在捐款跑路的风险
在线钱包或交易所本身有coin mixing的性质
实际上区块链的不可篡改性对隐私保护并非是好事,因为一旦暴露那么就无力回天
零知识证明
例子:我要证明这个账户是我的,即我有这个账户的私钥,但我又不想把私钥告诉你
- 加密函数不会出现碰撞,说明如果E(x)=E(y),那么x一定等于y
- hiding
- 同态运算
例子
专门为匿名性设计的加密货币,但是在性能上有损失、不能提供百分百的匿名,导致不是很主流
第十二节 BTC思考
- 区块链中的哈希指针,只有哈希没有指针在实际系统当中,区块用<key,value>存储在levelDB中
- 对于多个人的共享账号,不要用截断私钥的方法(区块恋),而是使用多重签名(MULTISIG)
- 为什么比特币系统能够绕过分布式共识中的那些不可能结论?比特币并没有达到真正意义上的共识,同时很多意义下的不可能理论在现实中是有可能的(模型的参数改一改)
第十三节 ETH概述
memory hard mining puzzle, ASIC resistance 抗ASIC芯片
proof of work -> proof of stake 权益证明
smart contract 智能合约
BitCoin: decentralized currency
Ethereum: decentralized contract
Satoshi Wei
现实生活中通过司法手段进行合约,我们希望用以代码形式实现这样的合约
与法币相比,去中心化的货币有什么好处,有什么应用场景?跨过转账
费时费力的事情
技术手段保证合同的参与方一开始就不可能违约,区块链的不可篡改性保证没人能改代码。
第十四节 ETH账户
A->B(10 BTC)
比特币的模式没有显式的维护账本
ETH是account-based ledger,显式地维护了一个账本,与人们平时的使用习惯相符
比特币面临的是double spending attack的威胁,但ETH对dsa有天然的防御作用
replay attack 重放攻击:A->B(10ETH),收钱的人在收到钱后,重新再广播一次
ETH中增加一个nonce域,别人改不了
nonce一开始都是0,全节点都会维护这个账户的nonce,每发生一次都+1。如果有人想重放攻击,那么nonce会对不上
ETH中有两类账户:
external owned acctount 公私钥对控制,balance,nonce(计数器)
smart contract account 不能主动发起一个交易,所有交易只能由外部账户发起 balance nonce code storage
为什么要设计这样新的模型?以太坊要支持的是智能合约,比特币中合同的执行会有一些麻烦
金融衍生品financial derivative
第十五节 ETH状态树
addr -> state 160bits,40位16进制数,这是一个key-value pair
Q:能不能用哈希表来存储这些pair?不考虑哈希碰撞时,查询和更新都是常数级别的复杂度
如果使用哈希表的话,要提供Merkle Proof怎么弄,比如证明账户余额,将所有账户的状态组织成一颗merkle tree?代价太大,因为如果每次发布一个新区块后,哈希表中只有很小一部分的账户会发生变化,大多数账户的状态是不变的,重新组织merkle tree的计算代价很大
比特币中每出一个区块也要构建Merkle tree,但比特币中是将区块中的交易组织成merkle tree,merkle tree root hash只构建一次,构建完是不会再改的。且区块中大概也就4000个交易,如果以太坊将所有的以太坊账户构建成Merkle tree,那么账户的数目比比特币交易数目高出很多个数量级
Merkle tree除了提供Merkle Proof之外,还有一个很重要的功能:维护全节点之间状态的一致性
Q:如果只使用Merkle tree呢,将所有账户组织成一颗merkle tree,要改也直接从merkle tree中改,是否可行?
merkle tree没有提供高效的查找和更新的方法。同时,还有一个问题,merkle tree要不要排序?如果不排序的话(不规定账户出现的顺序),那么每个全节点构建出来的的merkle tree root hash是唯一的。
Q:比特币当中不也不排序吗,为什么比特币中就没有这个问题?
比特币中各个全节点监听到的交易顺序也是不同的,但最终的记账权只掌握在一个矿工的手里,具体的tx list的顺序也是由这个获得记账权的矿工决定的,所以不需要排序。
Q:那为什么ETH中不能这么干?
因为如果要取得共识,那么全节点就必须把所有的账户状态都发布出去,这样是不可行的。
综上,不排序的merkle tree是会有问题的。
Q:那我使用Sorted Merkle Tree可以吗?
也会有问题,如果新增一个账户怎么办,在叶节点的插入位置很可能是插入在中间的,此时插入的复杂度会很高,因为有大半棵树需要重构,此时用哈希表反而更方便。删除代价也大(其实可以不删)。ETH中没有显式删除账户的方法。
ETH中采用的数据结构是Merkle Patricia Tree(MPT),,在此之前,先讲Trie
Trie字典树 retrieval,有几个单词放在一起排成字典树:
这种数据结构有几个很明显的特点:
- 每个节点的分支数目取决于Key的取值范围,此例中,每个节点的分支数目最多是26+1(结束标志位)。ETH中,branching factor 0~f,所以是17
- Trie的查找效率取决于Key的长度。此例中单词的长度一致,但ETH中账户的地址是定长的,都是40位的十六进制数
- Trie中是不会出现碰撞的,只要地址不一样,一定能够映射到两个不同的分支
- Merkle Tree不排序的话,插入元素的顺序不同,得到的树就不同。但Trie中不同的插入顺序能够得到相同的树。
- 更新操作的局部性很重要。Trie中只需要访问一个分支,不需要遍历整棵树。因此Trie中更新操作的局部性很好
然而Trie中也有一些缺点:
- 存储有点浪费,合并节点可以减少存储开销,提升查找效率,因此引出Patricia tree 压缩前缀树
对原树进行路径压缩:
因此树高变小,访问内存的次数变少。但是如果此时新添加一个单词,原来的压缩路径需要重新扩展开来,比如添加geometry
路径压缩在什么情况下比较好:键值分布比较稀疏时,Patricial tree效率高
比如几个长英文单词:
misunderstanding、discentralization、disintermediation(去中介化,区块链的一个应用场景,去掉中间商,没有中间商赚差价)。如果将这三个单词插入trie中:
如果用Patricia Tree,效果较好:
Q:我们这个应用中,键值是否稀疏?非常稀疏,ETH中有的地址空间。为什么搞那么长的账户?让地址足够长,分布足够稀疏,这是一个去中心化系统防止账户冲突的唯一办法。
MPT:Merkle Patricia Tree,MPT与PT的区别是:用哈希指针替代普通指针,因此也可以计算得到根哈希值,写在Block header中。ETH中有三个根哈希值。
作用:
- 不可篡改性;
- Merkle Proof,能证明你的账户上的余额。全节点把账户的路径发给轻节点,轻节点就可以验证账户里有多少钱;
- 能不能证明某个账户是不存在的?直白的说,在这个MPT中能不能证明某个Key-value Pair是不存在的?可以。如果存在就能找到这个路径分支,把这个路径作为Merkle Proof发出去,不存在就找不到这个路径。因此可以证明不存在。
ETH中用的还不是原生的MPT,而是使用修改版的MPT(Modified MPT)
如果出现了路径压缩,就会出现Extension Node,nibble就是十六进制数的意思,如果出现分支,就会出现Branch Node
中间Branch Node中7这个节点的值存的是下面那个Extension Node的哈希值。
在ETH中,新发布的区块状态树中有一些节点的状态要发生改变,但这种状态的更新不是在原地改的,而是新建一些分支,原来的状态是保留下来的
合约账户的Storage也是用状态树的形式存储下来的,维护的是变量到变量取值的一个映射。因此ETH中的这个MPT是一个大的MPT包含了很多小的MPT,每个合约账户的存储都是一颗小的MPT。
所以系统中的每个全节点需要维护的不是一颗MPT,而是每次出现一个区块都要新建一个MPT,大部分节点是共享的,少部分需要新建分支。
Q:为什么要保留历史状态,而不在原地直接改了?
ETH中出现分叉是常态,两个分叉会有一个胜出,那下面那个orphan block只能回滚roll back,退回到上一个区块的状态。即有时候我们需要退回到发生交易的前一个状态。实现回滚只能是保留历史状态,因为这些交易有可能要undo。
比特币中的交易类型比较简单,可以通过简单的推算逆推出要回滚的状态。而ETH中支持了智能合约,Solidity是图灵完备的,理论上说可以实现很复杂的功能。因此智能合约执行完后推算出前面的状态是非常困难的。因此要实现回滚,只能保存历史状态。
图灵完备是指在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)按照一定的顺序,可以计算出结果。
通俗来讲:图灵完备即可以解决所有可计算的问题。
以太坊中的数据结构:
区块块头的哈希值
叔叔区块的哈希值,和父区块不是同一个辈份的
挖出区块的矿工地址
三棵树的根哈希 状态数、交易树和收据树
boolm滤波器:提供高效的符合某种条件的交易的执行结果
挖矿难度
与Gas有关
Time区块大致的产生时间
Nonce和MixDigest与挖矿相关,MixDigest是将Nonce经过一些计算得到的
区块的结构:
- 指向block header的指针
- 指向叔父区块的指针,是个数组
- 交易列表
真正在网上发布的就是这些信息,即前三个属性:
(key, value) Pair中的value是如何存储在状态树中的呢?通过RLP(Recursive Length Prefix)序列化编码,特点是简单
Protocol buffer,简称protobuf,很常用的序列化的库
RLP是极简主义,只支持一种类型:Nested Array of Bytes,字节数组,可以嵌套。ETH中的所有数据类型都归结于NAB,难的都不做,都推给应用层做
序列化是将对象转换为字节序列,便于存储或传输,反序列化则是恢复对象的过程
https://www.jianshu.com/p/cf10c4503110
在以太坊中,采用了一种名为Recursive Length Prefix(RLP)的方法对交易、账号、合约等基础的数据结构进行序列化处理,从而实现对链上数据的网络传输和持久化存储。
和其他的序列化协议不同,RLP只支持两种数据类型:
1)byte数组,可以是二进制数组,当然也可以是字符串;
2)byte数组的数组,也就是列表。并支持列表内的嵌套。
第十六节 ETH交易树和收据树
交易树和比特币类似。
每个交易执行完毕后会形成一个收据,记录这个交易的相关信息。两个树中的节点一一对应。用于快速查询一些执行的结果。
交易树和收据树都是MPT。MPT的一个好处是支持查找操作
交易树和收据树组织交易,而状态树组织系统中的账户状态。相比之下,状态树需要共享节点,而交易树和收据树是独立的,不需要共享节点。
交易树和收据树都可以提供Merkle Proof。ETH支持更加复杂的查询操作。比如想找到过去10天与某个智能合约有关的交易,应该怎么查:
- 把过去10天产生的区块的所有交易列表全都扫描一遍,复杂度很高
- ETH中引入了Bloom Filter布隆过滤器这个数据结构。能够查找某个元素是否在比较大的集合当中。
会出现false positive,可能出现误报,但一定不会漏报
然而Bloom Filter不支持删除操作
直接查Bloom Filter去过滤掉很多不相关的区块
ETH的运行过程可以理解为交易驱动的状态机 transaction-driven state machine
状态1->交易->状态2
而比特币可以理解为额交易驱动的状态机,比特币状态机中的状态是UTXO。对一个给定的状态,一组确定性的交易,要执行确定性的状态转移
Q:有人在ETH中发起一笔交易,这个收款人的地址是否有可能从来没有听说过?
有可能。此时全节点需要在状态树中新插入一个节点
Q:状态树需要包含系统中所有账户的状态,无论账户是否参与了系统中的交易。是否能将状态树改一改,改成和交易树一样,只包含与交易相关的账户的状态?
不能。每个区块没有一个完整的状态树,这样查找某个账户的状态就不方便了,如果实在要查找就必须遍历整个区块链。还有一个更大的问题:
比如A->B(10ETH),全节点必须修改A和B的状态(比如A的余额-10,B的余额+10),**那么就需要在状态树中查找B。**假如B是个刚创建的账户,全节点发现状态树中没有B这个节点,只能从头扫到创世区块,结果发现还没有。这种方法是低效的
& 2047实际上是对2048取余
查询bloomFilter中是否存在我们感兴趣的topic:
第十七节 ETH-GHOST协议
GHOST- Greedy Heaviest Observed Subtree
15s的出块时间,临时性的分叉会变成常态。BTC中的共识协议认为,最长合法链上的区块是有效的,其他链上的区块无效
比特币中出现临时性分叉的情况比较少,但ETH中出现分叉是常态,矿工很大可能白挖,对个体矿工不公平
什么是公平?算力比例和收益比例想等才算公平。如果不匹配,比如收益多了,那就不公平
大型矿池的出现导致mining centralization,centralization bias
ETH采用了基于Ghost协议的共识机制,进行了一些修改,核心思想:对失效的orphan block区块给予一些安慰奖励,ETH给它一个好听的名字:uncle block
一个叔父区块最多包含两个叔父区块。
有利于鼓励系统中出现出现分叉后,及时合并。
Q:这是最初的版本,如果这样设计,有什么缺陷?
- uncle block只能出现两个,出现第三个的叔叔就不乐意了
- 挖出第五个区块的前提是,知道了另外两个叔父区块的存在,此时可以包含进来。如果来不及包含叔父,那叔父就真的没有奖励了。
- 如果矿工比较自私的话,会不包含叔父区块。自身损失比较小,对另一方损失比较大。有的矿池就会故意这么做。
协议改一改:**将叔父的定义进行拓展。**在最长合法链延伸的过程中,orphan block依旧可以作为叔父区块,就算这个区块不包含进去,后面的区块也会包含。
但是不能多少代都是叔父,所以ETH中有个规定,N代以内的叔父可以包含在unclehash中,越遥远的辈份拿到的安慰奖励越少
再往前,不叔父,要求7代以内有共同的祖先。At most seven generation。这么设计的原因:
- 如果不限制叔父辈份,那么实现起来,全节点要维护的状态就太多了
- 出块奖励逐渐递减,有利于鼓励出块时尽早合并区块(挖出叔叔区块的矿工会抓紧时间mining,尽早包含自己的orphan block)
设计这个协议的目的是为了解决系统出现的临时性分叉,属于state fork
BTC中发布一个区块包含两个奖励,block reward(静态奖励)和tx fee(动态奖励)
ETH中也有这个奖励,tx fee称gas fee,执行只能合约可以得到gas fee,叔父区块是得不到gas fee的
和BTC类似,gas fee只占block reward的很小一部分
**ETH中没有要求每隔多少个区块出块奖励减半。**ETH执行智能合约是需要消耗Gas的,发布智能合约要付出Gas fee,负责执行智能合约的那个矿工可以得到Gas fee
因此ETH和BTC的设计理念不同。
Q:把叔父区块包含进来的时候,是否需要执行叔父区块的交易?
不需要执行。最长合法链与叔父块中的交易可能是有冲突的,可能会导致double spending,叔父区块中的交易本身可能不非法,但是如果都执行的话,就可能变得非法。
ETH只在最长合法链上执行。最长合法链需要包含叔父区块时,需要检查叔父区块的合法性(符合挖矿难度要求),至于叔父区块里的交易是否合法,不需要检查。
如果有人发起的交易被包含到叔父区块了,此时叔父区块无效,那么交易也会被包含到后面的区块当中,交易总会被执行的。
如果是这种情况怎么办:
如果这条分叉链上的区块都给奖励,那么forking attack分叉攻击就变得太便宜了,那么人人都会搞分叉攻击,因为两者都能得到收益。
因此ETH规定,只有分叉的第一个区块可以得到uncle reward,后面的区块都不能得到奖励
实际系统中大部分的区块都得到了合并。
第十八节 ETH挖矿算法
Blockchain is secured by mining.
bug bounty
bounty hunter 赏金猎人
one cpu, one vote
ASIC resistance,设计memory hard mining puzzle,设计的puzzle应该是普通计算机能干的事情
早期的例子:LiteCoin,基于Scrypt的puzzle,开设一个很大的数组,有一个seed,依次取哈希
有些矿工可以:数组只保留奇数或偶数位置的元素,需要的内存可以少一半,time-memory trade off 用时间换空间
然而,这样的puzzle不仅对矿工memory hard,也对轻节点memory hard
早期的宣传,对于聚集人气来说是很重要的。
LTC的出块速度是两分半,puzzle不同,除此之外都与BTC一样
16M Cache, 1G dataset DAG
轻节点只需要保存Cache,而全节点需要保存DAG
ETH挖矿主要是以GPU矿机为主,使用的挖矿算法是ethash,挖矿要用1G内存
PoW -> PoS (Proof of Stake),权益证明不挖矿,类似持股投票
预挖矿 pre-mining,留给ETH开发人员一些币
pre-sale类似众筹,将来加密货币成功后,也能拿很大一笔钱
但有人认为通用计算机挖矿是不安全的,因为发动攻击的成本大幅度下降,ASIC矿机一统天下才是最安全的。
第十九节 ETH难度调整算法
以太坊决定回调难度炸弹,为权益证明的开发争取时间
BIP:BitCoin Improvement Proposal
因为挖矿容易了,出块奖励要相应减少一些
以太坊的实际统计情况
出块时间出现大幅度增长
链的总难度,最长合法链在ETH中是最难合法链
第二十节 ETH权益证明
y轴:TWh = Terawatt hours 10^12
一个交易要花一千度电,比特币的Pow机制十分耗电
ETH:
ETH与BTC相比,已经少了很多了。从直觉来讲,ETH包含了对智能合约调用的支持,应该更复杂,耗电更多才对。但是ETH中15s出一个区块, 而BTC要10min,因此ETH挖矿的时间短,耗电少。
但ETH处理一个交易的能耗依旧比信用卡公私高的多,不在一个数量级上
矿工挖矿:为了取得收益
为什么给矿工收益:为了激励矿工参与区块链的维护
矿工挖矿的过程:找一大笔设备,买现成的矿机设备,收益由算力所占的比例决定,而算力由硬件设备的数量决定,设备数量也由投入的资金决定的。也就是拼钱决定的,谁的钱多,收益就高
那不如直接拼钱?这就是pos的基本思想,也叫作virtual mining
优点:
- 省去了挖矿的过程,减少了温室气体的排放
AltCoin Infanticide 将AltCoin扼杀在摇篮里
在POS共识的区块链系统当中,想要发起攻击,只能是花钱大量的购入这个币,权益证明维护安全的过程是一个闭环
pos与pow并非互斥,越有钱那么挖矿的难度越小
Proof of Deposit 通过质押一定的币,减少挖矿难度
早期基于pos共识机制遇到的问题:两头下注的问题
下面那条链也有可能成为最长合法链。如果用pow那么不能两头挖,因为算力会分散;但用pos的话可以两遍都下注,如果上面的链成为最长合法链,那么下面那条链锁定的币是不会受影响的,也称nothing at stake
ETH中采用的权益证明采用Casper the Friendly Finality Gadget(FFG)
ETH中引入了Validator验证者,投入一定数量的ETH作为保证金,指责是推动系统达成共识,决定哪条链是最长合法链,投票的权重取决于保证金的数目大小
每50个区块就是一个epoch
Validator履行指责的话,可以得到相应奖励;若不作为或乱作为,会销毁或扣除相应的保证金
Q:投票达成的Finality会不会被推翻?
如果这个组织仅仅是矿工,而没有Validator作为同伙,那么Finality不可能被推翻。
攻击成功的情况:大量的Validator对两头有冲突的Finality都下注了,那么至少有1/3的验证者两边下注,一旦发现,保证金会全部没收
Q:为什么ETH没有在一开始就使用POS呢?
因为POS还没有那么成熟,而POW已经经过了时间的检验
EOS柚子,利用的是权益证明的思想,用的是DPOS:Delegated Proof of Stake的思想,投票产生21个超级节点,让这21个节点产生区块
有人认为挖矿所占的电源对环境的影响有限,电是很难存储的,很难传输。挖矿能够有效利用过剩产能,带动当地经济发展。
第二十一节 ETH智能合约
网络拍卖的具体例子
payable:ETH中规定,能接收外部转账的函数,都要标注payable,why
下面那个withdraw可以将自己出的以太币在拍卖结束后去回来
调用合约:
emit对程序的运行逻辑没有影响
这个过程实际上也是需要一个外部账户调用B的callFooDirectly,这个函数才能调用A的函数
两种方法在错误处理中不同,使用call函数的话,深层函数出错,外层函数依旧能继续执行
delegatecall不需要切换到被调用合约的环境中去执行,而是在当前合约中执行就可以了
如果Data什么都不写,默认调用的函数。可以不定义fallback,但会抛出异常
转账金额是给收款人的,gas fee是给矿工的。转账金额可以是0,但gas fee不能是0
Java Virtual Machine:增强可移植性
EVM类似,通过加一层虚拟机,为智能合约的执行提供一致性的平台,也成为World Wide Computer,寻址范围很大,256bit,远远大于目前的服务器寻址范围
矿工在打包智能合约的发布交易后,会返回一个合约地址
gas-fee
智能合约 Turing-complete Programming Model
出现死循环:Halting Problem停机问题,不可解,不是NPC的
判断图是否为哈密尔顿回路,可解,但复杂度是指数级别的
一次性先把GasLimit的汽油费扣掉,再根据实际的执行情况多退少补。如果交易发起方的Gas limit不够,那么这个交易会回滚,且已经消耗的gas fee不退。
ETH中的交易具有原子性,出现错误时要么redo要么undo。出现错误:
sendTransfer会导致连锁式回滚,而callvalue不会导致连锁式回滚
GasUsed是指所有交易加起来的GasUsed
GasLimit是这个区块里所有交易能够消耗Gas的上限,而并非将所有交易的GasLimit总和。BTC固定了区块大小的上限1M,而由于ETH中所支持的智能合约交易会比较复杂,比如很少字节的交易可能会带来很大的资源开销,因此ETH不能简单地对区块的大小进行限制。
ETH的矿工可以对这个GasLimit进行微调,可以在上一个区块的基础上上调或下调,而15s就出一个区块,这些区块中的GasLimit都是按照矿工自己的意愿调整的,可以导致最终整个系统的Gas Limit趋于所有矿工的平均意见。
Q:汽油费是怎么扣的?
三棵树都是全节点在本地维护的数据结构,因此扣汽油费的操作是在本地的状态树中进行修改就行了,如果余额不够那么就不执行。智能合约执行过程中任何对状态的修改都是改本地的数据结构,只有当智能合约执行完毕以后,这种本地的修改才会发布到区块链上,成为外部可见的。
矿工在挖矿的过程中,都是先执行相应的交易(修改本地内存的数据结构),如果监听到了别的全节点发布了新的区块,那么就把这个状态回滚到前一个区块,并执行这个发布的新的区块中的所有交易,以此达到共识
Q:交易是先执行再打包到区块,还是先打包到区块再执行?
矿工的挖矿过程是组装候选区块。如上图的数据结构Header所示,矿工需要先执行完交易,再计算三个根hash,才能开始试nonce开始挖矿。因此是先执行后挖矿,没有办法先挖矿。
Q:如果我花费很多的计算资源在交易的执行上,但最后没有成功挖矿,我能得到什么补偿吗?
ETH中没有任何补偿,得不到Gas Fee也得不到任何补偿,同时还得执行新区块中的所有交易。因此,在这种机制下,挖矿慢的矿工会很吃亏。
目前来讲,Gas Fee占比很小,所以并不是一个很大问题。
Q:会不会有这种情况:你不给我Gas Fee,那我就不验证了
如果这么干会危害区块链的安全。如果某个矿工想不通,这种风气蔓延会危害区块链的安全。**如果跳过这个验证,本地的数据结构跟系统就不一致了,以后都没法挖矿了。**因此跳过验证的步骤是不可行的。
Q:发布在区块链上的交易是不是都是成功执行的?
要扣掉Gas Fee,如果不发布到区块链上的话,Gas Fee扣不掉
Q:智能合约是否支持多线程?
Solidity根本不支持多线程,不支持多核并行处理,没有这个语句。
ETH是交易驱动的状态机,要求在给定的起始状态在给定的状态转换函数后,能够到达新的确定的状态。多线程是异步的,结果是不确定的。因此ETH中无法产生真正意义上的随机数
智能合约的确定性导致不能像传统编程语言那样通过system call来获取操作系统的状态信息,因为每个全节点的执行环境并非完全一样(有的是Linux,有的是Windows…)
msg.data写了要调用的函数和参数
msg.sender和tx.origin不一样,如下图:
对于C2中的f2函数来说,msg.sender是C1,而tx.origin是A
以上要理解addr是谁的balance,谁向谁转账
send和transfer的区别在于,transfer会导致连锁式回滚,send不会
call也可以用来转账,不会导致连锁式回滚,但是花的Gas fee会更高,所以一般不会用call去转账
智能合约这么写是有问题的,是没法改BUG的
autionEnd总会需要一个人去调s用的,没有办法自动执行
假如黑客这么干:
通过合约来参与拍卖,退款时会出现问题。钱只能退到黑客写的这个合约当中,而这个合约没有定义fallback函数,导致抛出异常,transfer函数所在的函数会被回滚,那此时所有参与拍卖的钱都会变成死钱。
矿工执行transfer函数本身只是更改本地的数据结构,并非在区块链中发起一笔新的交易。如果这个合约执行完毕,且矿工挖矿成功的话,全部状态才会上传到区块链中完成同步。
如果出现问题了,发布在区块链上的合约是没法改代码的,因此里面的钱也永远取不出来了
Code is law,好处是没有人能篡改规则,坏处是没有人能改BUG
不可撤销的信托irrevocable trust
因此在发布智能合约之前,需要测试,测试再测试。确保没有问题时,再发布。
不需要循环,参与竞标的人主动把钱取回
结果就是黑客把合约中的钱全都转走了,递归结束条件:合约上余额不够、Gas费不够、调用栈溢出
合适的做法是先清0,再转账,防止合约间递归调用的出现。区块链中任何的合约都可能是有恶意的。
转账时用的是send。send和transfer有个共同的特点,就是Gas fee只有2300个单位,不足以让对方合约的fallback函数干别的事情,也因此能够防范重入攻击
第二十二节 ETH-The DAO
DAO:Decentralized Autonomous Organization
致力于众筹投资的DAO:The DAO,本质上是一个ETH上的智能合约。工作方式类似DAC:Decentralizad Autonomous Corporation
DAC是为了盈利赚钱的,而DAO可以是非盈利的
splitDAO,将大DAO进行拆分得到childDAO
黑客在此会进行重入攻击,给ETH社区带来极大恐慌
如果出了问题就回滚,那就真的乱套了
The DAO:too big to fail,因此认为要管
采取补救措施的原则:只影响与黑客攻击相关的交易,而不影响其他的正常交易
升级软件:增加了一条新的判断规则,与The DAO发生交易的账户都不能发生交易。增加规则后新矿工挖的区块旧矿工认,但旧矿工挖的区块新区块可能不认,因此是软分叉。
但是有个bug,判断账户是否与DAO相关的交易要不要收取汽油费,即本来交易是合法的,但加了新的规则后交易非法,汽油费要不要收?
要锁定与DAO相关的账户而不仅仅是锁定黑客的账户,是因为合约有可能会遭遇二次攻击。
汽油费的机制目的在于提高攻击者发起交易的门槛,但以太坊EIP更新以后在此基础上没有收取汽油费,导致全节点收到很多恶意攻击,最终矿工纷纷回滚到之前的版本。
EIP最终采取硬分叉的方式,强行将这个智能合约的钱转到新的智能合约当中。为什么是硬分叉?用软件升级的方式重新指定的规则,旧矿工认为这是非法的交易,因此是硬分叉。大部分人都支持硬分叉。
但是旧链上依旧有人用,叫ETC(Ehereum Classic),经典以太坊,旧链上挖矿难度小。但是两条链并存会带来很多问题,比如重放攻击:
新链的交易在旧链上是合法的,旧链的交易在新链上的算力也是合法的。因此采用ChainID对两者进行区分。
第二十三节 ETH反思
Is smart contract really smart?
ATM可以看作物理世界上的自动合约,按照事先规定的规则执行。
-
Smart contract is anything but smart. 智能合约并非智能
-
Irrevocability is a double edged sword. 不可篡改性实际上是双刃剑
不可篡改性增大的合约的公信力,但也意味着无法更新升级。要升级就必然会导致硬分叉,硬分叉要说明理由,但说明理由后就会有黑客在升级前抢先发起攻击,导致更多的损失。
-
人们发现有非法交易后,无法冻结账户,且无法阻止区块链上对智能合约的调用。
- 只能是自己也发动攻击,利用与黑客同样的手法,赶紧将合约中的钱转走
-
Nothing is irrevocability. 不要迷信区块链的不可篡改性。连宪法都可以改,为什么区块链改不了。
- Prohibition 18,全国范围内禁酒。21修正案,推翻
- open container laws
-
Is solidity the right programming language?
- formal verification 正确性的证明,智能合约的终极目标
- 智能合约会最终走向成熟
-
开源的好处是什么
- 公信力、安全
- Many eyeball fallacy(misbelief),但实际真正有人看代码的人少之又少,不要认为开源的软件就安全,涉及财产安全的,要自己看看合约中写的是否有问题
-
What does decentralization mean?
- 不全是ETH开发团队说了算,硬分叉的成功是多数矿工的支持导致的,ETH没有办法强迫矿工升级
- 去中心化并不是说全自动化,不能有人为的干预
- 也不是说已经指定的规则不能修改,而是说规则的修改要用去中心化的方式来完成
- 分叉恰恰是去中心化的提现,而中心化的系统中没有办法分叉。分叉的出现恰恰是民主的体现。
-
Decentralized ≠ Distrubution
- 在分布式的平台上,可运行分布式应用,也可以运行去中心化的应用
- ETH是一个状态机state machine,状态机的目的不是为了速度,而是为了容错
- mission critical applications: air traffic control, stock exchange, space shutlle
- 不要把EVM平台当做大规模计算和存储服务,不仅速度慢,且贵。智能合约是用来编写控制逻辑的,在互不信任的实体之间建立共识的操作才需要写在智能合约里。
第二十四节 ETH-美链
Beauty Chain
ICO: Initial Coin Offering,依附在基础链上的交易系统
IPO: Initial Public Offering
发行规则:1ETH=100BEC
ERC:Ethereum Request for Comments
batchTransfer的实现:
乘法发生了溢出
在进行数学运算时一定要进行溢出的检测
第二十五节 总结
区块链的一些应用:
- 保险理赔的:理赔速度慢是因为理赔的内容需要人工审核,而区块链本身并没有好的优势
- 溯源:如果农产品被撒了农药,或运输销售过程中被掉包,区块链本身检测不出来。
- 共识机制:在互不信任的实体之间建立共识,但也有人说这是个伪命题,因为你不会去一个没有信用的商家那里买东西。
- 中心化和去中心化的界限并非黑白分明的,并不是说使用了去中心化的支付方式,就意味着商业模式必须是去中心化的
区块链的不可篡改性:一旦发布交易,无法撤销。但共识协议中没有撤销的机制。所谓的退款实在应用层重新发起一次退款,是两笔不同的交易。
法律的监管和保护:有一些支付方式是受到法律的监管和保护的。区块链目前是缺乏监管的。但是监管本身并不是一件坏事,因为出了事之后没有人能保护你。法律上的监管和保护措施和信用卡在技术层面上的设计其实是没有什么必然联系的。
BTC不应该与已有的支付方式去竞争。而是应用于目前已有的支付方式解决的不是很好的领域,比如跨过转账。目前缺乏一种能在全球流通的电子货币
支付方式的效率:每个交易的能耗非常大,浪费电,不能做到绿色环保。
- 不与已有的支付方式竞争,如果觉得比特币不环保就去用信用卡
- 随着区块链技术的发展,一些加密货币在支付效率上已经有了很大的提升
- 评价一个支付方式效率要有唯物史观,要在特定的历史条件下去看,要跟当时存在的支付方式相比较
智能合约相关:编程语言书写的,老百姓看不懂,反而不利于检查安全漏洞
- 程序化是个大趋势 Software is eating the world
物理世界的智能合约:ATM机。ATM机也会出问题,到现在还会发生故障,但不会因为ATM出现故障就不去使用了。
- 将来会出现智能合约的成熟模板
- 智能合约和去中心化不能解决所有的问题
- 民主一定是正确的吗,大的决策就是好的事情吗?
- 不是最好的方法,只是最不坏的方法
不一定。现实生活中所做的决定是很复杂的,并非简单投一个票就可以决定。不要以为去中心化就能解决所有问题,不要以为去中心化的商业模式就一定是好的