3 数据结构

hash printers （hash指针）

hash指针既可以找到块的位置，也可以验证hash的正确性

Block chain is a linked list using hash pointers

每一个区块都包含前一个区块的hash指针

• 后面一个区块的hash指针是通过前一个区块的值算出来的。
• 通过上面的数据结构可以实现：tamper-evident-log

只要记住最后一个块的hash值，就可以保证整个链的值无法篡改。

• 我们也可以只保存其中的部分区块，区块的前面的部分我们不必保存，如果需要的时候找别人要；然后验证要的区块的hash值是否是当前区块的hash值即可

Merkle tree

上图：

• 最下面的一层是数据块，data blocks；每个数据块都是交易（tx）
• 上面的那些都是hash pointers
• 最上面的节点是根hash值（root hash）

Merkle tree数据结构的好处：

只要记住root hash就可以检测出节点的修改

每个区块分成块头（block header）和块身（block body）

默克尔证明（Merkle proof）：指一笔交易到跟节点的路径

这种证明也叫做：proof of membership或proof of inclusion（证明节点存在于Merkle tree之中）

proof of non-membership（证明节点存不在于Merkle tree之中）

排序所有交易节点的hash值（Sorted Merkle tree），然后计算需要证明的交易的hash值，找到此hash值应该出现的位置，如果应该出现的位置的两边的节点的hash满足Merkle proof，则说明需要证明的节点不在此Merkle tree之中。

只要不是有环的数据结构，都可以使用hash指针

4 BTC 协议

如何发行数字货币

央行发行数字货币，如果只使用私钥签名，可以吗？

无法防止double spending attack：花两次攻击

中心化方案：

如果央行给发行的货币打上编号并且记录货币当前属于谁，那么可以解决double spending attack；

但是每次花钱都要去央行验证货币是否是真的，并且属于当前花钱的人，花钱之后再变更钱的归属。

去中心化方案

每个交易（如A给B转账）中都包含输入和输出两个部分

• 输入部分需要说明币的来源
• 输入部分需要包含付款人的公钥（因为付款时有付款人的签名，带上公钥为了供别人校验）
• 输出部分要给出收款人公钥的hash

铸币交易（coinbase tx）里面有A的公钥的hash，这样就知道铸币交易的钱是给谁的。

上图中的数据结构有两种hash指针

• 第一种是链接块的hash指针（即前一个区块的hash指针）
• 第二种hash指针是说明币的来源

问题：是否可以检测dobule spending？

如果币的来源是不合法的（验证不合法的方式是币的来源是否存在与UTXO），是不会添加到区块链中，可以检测dobule spending

问题：在A给B转账时，所有人都需要知道A的公钥，为了验证A的签名；那么怎么才能知道A的公钥呢？

在交易的输入部分，付款人需要给出自己的公钥

在比特币的系统里，地址是通过公钥推算出来的，地址相当于银行账号，A需要给B转钱需要B的地址；比特币系统里面是没有功能查询某个人的地址

BitCoin Script：交易脚本，把A的输入部分和上一步的输出脚本拼在一起执行，如果不报错说明交易是合法的。

每一个块包含不止一个交易，每个块包含Block header和Block body

哈希指针包含的hash，是通过Block header做hash的值

Block header包含：

• version：用的哪个比特币协议的版本
• hash of previous block header：上一个区块头的hash
• Merkle root hash：整个Tree的root hash值
• target：挖矿的目标target（满足H(block header + nonce) <= target）
• 随机数nonce

Block body包含：

• transaction list

系统中的节点分为全节点和轻节点

full node

全节点是保存区块链的所有信息的，验证每一个交易，所以全节点也叫做fully validating node

light node

轻节点无法独立验证交易的合法性

问题：每个账户都可以发布交易，谁来决定哪个交易写到区块中？顺序是什么样的？

挖矿决定谁有记账权，有记账权的节点可以申请写入区块，顺序由拥有记账权的节点定

账本的内容要取得分布式的共识

distributed consensus（分布式共识）

distributed hash table

需要取得共识的内容是什么？

FLP impossibility result：

在一个异步的系统里，即使只有一个成员是有问题的，也不可能取得共识

CAP Theorem（定理）

CAP：

• 一致性 （Consistency）
• 可用性 （Availability）
• 分区容错性 （Partition tolerance）

这三个特性分布式系统中最多同时满足两个

分布式的一个协议：Paxos，能够保证Consistency

比特币中的共识协议Consensus in BitCoin

假设系统中大部分的节点是好的，小部分有恶意。

直接投票选择哪些交易是合法的，如果超过半数就接受可以吗？

membership，谁有投票权

hyperledger fabric（联盟链）：可以投票决定

sybil attack（女巫攻击）：超级计算机一直制造账户，参与投票，直到制造的恶意账户超过半数。

比特币的投票，按照算力值

谁先获得下面公式中的nonce，谁就能获得记账权，并且给予初块奖励

Puzzle friendly: H(block header) <= target

longest valid chain 最长合法链

如果不在最长合法链上，新的区块也不会被接受；

上面的图片是分叉攻击（forking attack）

block reward 初块奖励

一次性能造多少币？

刚发布的时候50 BTC，21万个区块之后可以铸造25个比特币

50 BTC -> 25 BTC -> 12.5 BTC

coinbase transaction

mining（挖矿）：争夺记账权

digital gold：数字黄金

miner：矿工

BTC 实现

transaction-based ledger：基于交易的账本模式

每个区块记录的是交易信息，包括转账交易和铸币交易

UTXO：Unspent Transaction Output（还没有被花出去的输出）

UTXO数据结构，以便快速检测double spending；如果想花掉的币不存在UTXO中，说明不存在或已经花出

total inputs = total outputs

比特币的第二个激励机制：transaction fee

其他的模式：account-based ledger，在这种模式中，系统要显示的记录账户的余额，以太坊是基于此种模式记账。

每次尝试nonce可以看作是Bernoulli trial：a random experiment with binary outcome

所有的尝试的集合构成了Bernoulli Process：a sequence of independent Bernoulli trials

尝试计算nonce是memoryless的：即无论以前尝试过多少次下一次的概率还是一样

可以使用Poisson Process近似

出块时间服从指数分布：exponential distribution

BitCoin is secured by mining

比特币的安全性

问题：能不能把别人的钱转给自己？

不可以，因为你没有别人的私钥，无法签名。（比特币在花每一笔钱的时候都要制定币的来源，即某次交易的output，这个output中有币的所有人的公钥，在花钱的时候币的所有人需要用自己的私钥做签名，然后别人通过当前交易的input和币来源的output来验证这个交易的合法性）

问题：能不能double spending？

不可以，因为第二次花的时候在UTXO里面不存在，会验证不通过。

6-BTC-网络

application layer：BitCoin Block chain

network layer：P2P Overlay Network

设计原则：simple, robust, but not efficient

7-BTC-挖矿难度

如何调整挖矿难度：调整挖矿难度就是调整目标空间在整个输出空间中所占的比例。

挖矿即是算出满足：H(block header) <= target的nonce值

sha-256: 可能的值是2的256次方

difficulty = difficulty_1_target/target

问题：为什么要调整挖矿难度？

为了保证出块时间平均10分钟

问题：出块时间太短会有什么问题？

两个节点同时发布区块，可能会出现分叉

平均出块时间过短可能导致上图的很多分叉，这会分散诚实节点的算力

平均出块时间不论设置的多长，都不可以无限的减小下去

如果分叉过多就无法防止51% attack

以太坊的共识协议：ghost

什么时候调整难度？

每2016个区块之后调整一次

如何调整挖矿难度：

调整的target值

公式：target = target_current * (actual time)/(expected time)

当actual time大于expected time，说明难度太大， (actual time)/(expected time)得出的值就大于1，最终算出来的target会比当前的target大，也就是变得容易

调整难度

next_difficulty = previous_diffculty * (2 weeks)/ (time to mine last 2016 blocks)

调整难度与目标域值（target）成反比

expected time = 2016 * 10min

actual time = time spent mining the last 2016 blocks

目标域值调整最大不会超过4倍，最小不会小于1/4

怎么让所有的矿工都调整域值呢？

代码里自动调，如果恶意节点修改了源码不调整，他发布的区块的检查区块合法性就通不过。

8-BTC-挖矿

全节点

• 一直在线
• 在本地硬盘上维护完整的区块链信息
• 在内存里维护UTXO，以便快速验证交易的正确性
• 监听比特币网络上的交易信息，验证每个交易的合法性
• 决定哪些交易会被打包到区块里
• 监听别的矿工挖出来的区块，验证其合法性
• 挖矿
• 决定沿着哪条链挖下去？
• 当出现等长的分叉的时候，选择哪个分叉？
• 缺省情况下是沿着最先听到的区块

轻节点

• 不是一直在线
• 不用保存整个区块链，只要保存每个区块的块头
• 不用保存全部交易，只保存与自己相关的交易
• 无法检验大多数交易的合法性，只能检测与自己相关的那些交易的合法性
• 无法检测网上发布的区块的正确性
• 可以验证挖矿的难度
• 只能检测哪个是最长链，不知道哪个是最长合法链

挖矿具有特性：

memoryless或叫做progress free

挖矿的设备

• 第一代，CPU
• 闲置的cpu、内存、硬盘
• 第二代，GPU
• 为了通用并行计算而设计的
• 也存在浪费
• 第三代，ASIC：Application Specific Integrated Circuit

挖矿的设备的趋势是从通用到专业

puzzle

mining puzzle:挖矿时求解的puzzle

merge mining：使用别的币的mining puzzle

Alternative mining puzzle: 抗ASIC芯片

矿池

（share almost valid block）

假如一个矿池占了51%的比例，他能发动哪些攻击呢？

• forking attack
• Boycott（封锁）

9-BTC-比特币脚本

比特币脚本是stack-based的脚本，包括下面三种类型

• P2PK（Pay to Public Key）
• P2PH（Pay to Public Key Hash）
• P2SH（Pay to Script Hash）对多重签名的支持

redeemScript：

当一个需要联合签名的账号B（如需要5个中的三个签名）需要支付时，需要至少有三个签名才可以，那么在B支付给C时需要验证B的币来来源的output和当前的交易的input做验证。如果需要验证成功则需要在上一步交易的output中包含这些公钥信息。

当一个账号A支付给另一个需要联合签名的账号B时，如果需要A支付时提供B的所有的账户的公钥信息，会导致A支付时特别麻烦。

redeemScript就是解决上面的问题而存在的，详情参考深入理解比特币脚本

Proof of Burn

燃烧证明，在输出脚本中添加return，使这个output在验证时永远报错，也就是这个输出的币永远也花不出去。

自问：如果A在给B付款时，output中面包含return语句，那么B虽然真实收到了款，但是永远花不出去。B能够在接收时验证吗？还是只能等到花钱时才能发现这个问题呢？

自答：因为B需要验证这比交易有没有写入区块链中，所以A会把交易发给B，此时B需要检查output是否包含return，如果包含则认为这比交易无效；假如B是商家并在交易刚发生时不验证，把货发送给A，那么B就收到一笔花不出去的钱。

digital commitment

发布交易不需要记账权，发布区块才需要记账权

10-BTC-分叉

fork

• state fork
• forking attack（deliberate fork）
• protocol fork（协议分叉）
• hard fork
• soft fork

hard fork

系统中只有有一部分节点不更新软件，就会出现永久性的分叉

eg：block size limit

block size不超过1M，计算出7tx/sec（每秒7笔交易）；如果new nodes把软件升级为区块大小最多可以4M，那么旧的节点如果不一起升级继续沿着旧链挖就会导致硬分叉；旧节点认为超过1M大小的区块为非法的。

只要old nodes不更新软件，分叉就不会变更

soft fork

只要系统中有半数中的节点更新软件，就不会出现永久性的分叉；只会出现临时性的分叉

接着使用调整区块大小的例子，如果调整为限制不超过0.5M，那么新节点产生的区块旧节点也认可；但是旧节点产生的区块新节点不认可，如果新节点占多数时就会迫使旧节点升级。

软分叉的例子（P2SH：Pay to Script Hash）

11-BTC-问答

如果转账的时候地址写错了怎么办？

答：没有办法取消一经发布的交易

Proof of Burn，如果OP_RETURN无条件的返回错误，这笔交易是如何写入到区块链里的呢？

答：因为OP_RETURN是写在当前交易的输出脚本里，所以当前交易的验证不会验证这个脚本

你怎么知道哪个矿工最先找到的同一个nonce？

答：不可以偷答案，因为区块里面的coinbase tx指向的收款账户是真正计算出nonce的账户，这个信息如果被修改了，交易就不会验证通过。

transaction fee，如何确定交易费给哪个矿工，给多少？

只要total inputs > total outputs，之间的差额就是交易费

12-BTC-比特币中的匿名性

BitCoin and anonymity

pseudonymity

什么情况下会破坏匿名性？

在多个inputs的时候，多个输入可能是同一个人

什么情况下别人能直到比特币账户对应现实中的某个人呢？

资金的转入转出，购买比特币或者比特币套现；比特币支付的时候也可以

silk road：eBay for illegal drugs

采取什么方法提高匿名性？

零知识证明

零知识证明是指一方（证明者）向另一方（验证着）证明一个陈述是正确的，而无需透露除该陈述是正确的外的任何信息。

我的理解：如比特币的转账（A转给B）签名就是零知识证明，因为这个签名证明了这个交易是A转出去的，却不需要让A提供其他信息。

13-BTC-思考

为什么比特币系统能够绕过被证明的分布式系统的不可能的结论？

比特币并没有绕过

14-ETH-以太坊概述

• memory hard mining puzzle
• ASIC resistance：挖矿时需要访问内存
• proof of work -> proof of stake：目标是从工作量证明过度到权益证明
• smart contract: 智能合约
• BitCoin: decentralized currency（去中心化的货币）
• Ethereum: decentralized contract（去中心化的合同）

15-ETH-账户

• 以太坊是一个accounting-based ledger（基于账户的去中心化的账本）
• 天然防御double spending attack
• 记录交易次数（nonce），以防御replay attack（重放攻击）

账户类型

externally owned account（外部账户）

记录：

• balance
• nonce

Smart contract account（智能合约账户）

记录：

• balance
• nonce
• code
• storage

智能合约账户有以下几个特点：

• 合约账户无法主动发起一个交易
• 创建合约账户的时候会返回一个地址，可以调用这个地址

16-ETH-以太坊中的状态树

维护的功能是账户地址到账户状态的映射：addr -> state

问题：如果把所有账户直接组成一个merkle tree 可以吗？

不可以，因为修改账户时成了串行

问题：为什么比特币可以把所有交易组成一个merkle tree呢？

因为比特币只有一个人拥有记账权，所以这个有记账权的人随意记录即可

即使以太坊使用sorted merkle tree，在有新的账户出现时也会大量的更新merkle tree中的hash值。

数据结构：trie（retrieval-检索）

数据结构：Patricia tree（trie）

• 树的高度变短
• 如果插入新的单词，原来压缩的节点可能需要扩展开

数据结构：MPT（Merkle Patricia tree）

把Patricia tree的指针改为Hash Pointer就成了MPT

数据结构：Modified MPT

下面状态树的例子中的节点有三种：

• Extention Node：如果路径出现压缩，就会出现此节点
• Branch Node：分支节点
• Leaf Node：最终的节点

16-ETH-交易树和收据树

用处：

• 提供Merkle proof

数据结构：bloom filter

用途：支持查找某个元素是否在一个比较大的集合中

实现：把集合中的所有的hash值映射到一个小的数组中，然后把数组中的对应位置的值由0改为1。

• 有可能出现误报（一个值的hash映射的数组中的位置，如果是1只能说明可能存在，因为存在hash碰撞）
• 不会出现漏报（因为只要某个值的hash映射的数组的位置的值是0，说明此值不存在）

以太坊中如何使用bloom filter

包含在块头里面，可以快速过滤某些节点不包含指定交易；然后再在可能包含的节点中检索。

transaction-driven state machine（交易驱动的状态机）

18-ETH-GHOST协议

如果只有和父节点平级的才是uncle block

存在问题：

1、uncle block的个数只能是两个，如果分叉超过3个就无法全部包含进来。
2、故意不包含某个叔父区块

只要与当前节点有共同的主链就认为是uncle block

存在问题：

某个矿工在挖矿难度低的时候产生多个分叉（即以后节点的叔父）区块，期待以后被包含进去以获取初块奖励

GHOST协议：与当前区块在7代以内，才被认为是uncle block

距离当前区块越远的uncle block，得到的奖励越少；为了防止分叉过多，有利于鼓励出现分叉尽快合并。叔父区块得不到gas fee（汽油费）

19-ETH-挖矿算法（ethash）

Block chain is secured by mining。

bug bounty：bug赏金

one cpu， one vote（一个cpu，一张投票）

设计puzzle的原则：difficult to solve， but easy to verify

以太坊的挖矿算法的目标是做到：AISC resistance

memory hard mining puzzle

20-ETH-难度调整

自适应难度调整

子公式解释

难度炸弹（difficulty bomb）

以太坊发展的四个阶段

21-权益证明（Proof of stake）

TWH：Terawatt hours

问题：为什么需要权益证明？

工作量证明太费电了

初块奖励是为了激励矿工参与比特币系统的维护。

virtual mining

权益证明：

• 每个人按照持有币的数量来投票，省去了挖矿的过程；持有的币越多，权益越大。
• 持有的币只能从加密货币的系统中获取，如果有人大量购买这个币以获取权益然后搞垮他，会导致币价大涨；涨价会让搞垮这个币所付出的代价很大。

AltCoin Infanticide：把新币扼杀在摇篮里

Proof of Deposit

如果出现分叉的时候，一个人两边都挖，并不会影响他的币的数量。

Casper the Friendly Finality Gadget（FFG）

验证者有任期，验证者在任期外有等待期，如果没有人检举则给验证者保证金和奖励。

EOS币的权益证明：

DPOS：Delegated Proof of Stake

22-ETH-智能合约

外部账户如何调用智能合约？

• SENDER ADDRESS：调用者的地址
• TO CONTRACT ADDRESS：智能合约的地址
• VALUE：调用时转多少ETH
• GAS USED：汽油费
• GAS PRICE：汽油费的价格
• CAS LIMIT：此调用愿意支付的汽油费上限
• TX DATA：调用的函数及其参数的编码值

一个合约如何调用另一个合约中的函数

1、直接调用

2、使用adress类型的call()函数

3、代理调用delegatecall()

错误处理

• assert：一般用来判断内部条件
• required：一般用于判断外部条件
• revert：无条件的抛出异常

嵌套调用

先执行交易再挖矿,因为挖矿之后发布的账户状态需要先执行交易。

就算账户的代码执行错误，也会被发布；然后收取汽油费，为了防止有恶意节点发送大量的不能验证通过的交易。

问题：智能合约的代码支持多线程执行吗？

不支持多线程,多线程可能造成执行结果的不一致。

智能合约可以获得的区块信息

智能合约可以获得的调用信息

地址类型

地址类型中的不同方法转账时的特点：

• transfer：会导致连锁性回滚
• send：不会导致连锁性回滚
• call：不会导致连锁式回滚，call的方式转账会把剩余的汽油全部发送过去

一个例子：简单拍卖

构造方法

出价和结束拍卖的方法

如果黑客的智能合约中没有callback方法怎么办？

没有办法。。。

Code is low：

优点：没有人能够修改规则

缺点：如果规则有问题，也无法修正，导致上面的问题成为所有人的钱都取不出来

优化后的拍卖代码

无法防止重入攻击（Re-entrancy Attack）

解决的方法是，先把金额修改为0，再发起转账。

转账交易时需要使用这个步骤：先判断条件，再改变条件，再发生交互

better safe by sorry

不要使用call方法转账，因为call支付的汽油费太多

23-ETH-TheDAO

DAO：Decentralized Autonomous Organization（去中心化的自治的组织）

DAC：Decentralized Autonomous Corporation（去中心化的自治的公司）

因为先转账再更改余额导致被发起了重入攻击：

too big to fail

升级后产生两个分叉：通过在链上增加ChainID（为了防止回放），以区分ETC(Ethereum Classic)和ETH

为什么不能只针对黑客的账户？

因为智能合约有bug，所以就算只针对黑客的账户其他人也可以针对这个bug进行攻击。

24-ETH-思考

Is smart contract really smart？（智能合约真的智能吗）

smart contract is anything but smart

Nothing is irrevocable（没有什么是不可篡改的）

如TheDAO的例子；所以不能迷信“不可篡改”

Is solidity the right programming language？

solidity存在一些问题，但是没有什么东西是没有问题的。所以随着时间的检验可能会出现

• 智能合约模板
• 编写智能合约的公司

虽然智能合约的内容是开源的，但是Many eyeball fallacy；在涉及到自己的利益时还是需要自己检查代码。

What does decentralization（权利下放） mean？

分叉是去中心化和民主的体现

decentralized != distributed(去中心化不等于分布式)

state machine的应用场景：

• mission critical application（关键任务应用程序）
• air traffic control（空中交通管制）
• stock exchange（证券交易）
• space shuttle（航天飞机）

智能合约是用来编写控制程序的，只有在互不信任的实体之间建立共识的操作才需要写在智能合约里

25-ETH-Beauty Chain（美链）

IPO：Initial Public Offering

ICO：Initial Coin Offering

美链背景介绍

下图中出现的ERC为Ethereum Request for Comments（以太坊征求意见）

因为下面的代码在计算时出现了溢出，从而导致被攻击，凭空出现了很多的代币BEC

如何预防此类（计算溢出）问题？

26-总结

• 加密货币应该用在法币支持的不太好的地方，而不是用在法币已经支持的很好的地方。
• 下一代的的互联网是价值交换网络
• Democracy is the worst from of Government except for all those other forms that have bean tried from time to time
• Is decentralized aways right thing?