导因

某种机缘巧合，让我对区块链产生强烈的兴趣，在此开篇，后续慢慢更新。

区块链的密码学基础

加密货币(crypto-currency) BTC是迄今为止最为成功的区块链应用场景。技术是基于密码学哈希函数(cryptographic hash function)的实践。其有三个重要性质:collision resistance hiding puzzle friendly 分别对应:哈希碰撞的抵抗性、单向藏匿性、难题友好性

太好了，恰巧我本科学的是信息安全，在这里当是复习一下密码学的知识。

collision resistance

对于 x != y ==> H(x) == H(y) 两个不同的输入，得到相同的输出，则产生了碰撞。或称 collision resistance 为 collision-free 无碰撞

强碰撞：如果随机找两个消息M1、M2，使得用hash函数加密后的值 H(M1)=H(M2) 则说明存在强碰撞，如果这种碰撞不能实现则叫碰撞稳固(抗强碰撞性)。

弱碰撞：如果给定一个消息M1，寻找消息M2，使得用hash函数加密后的值 H(M1)=H(M2) 则说明存在弱碰撞，如果这种碰撞不能实现则叫第二原像稳固(抗弱碰撞性)。

对于一个hash函数而言，如果一个Hash函数是抗强碰撞的，那么同时也是抗弱碰撞的

目前还没有散列函数能够在数学上(理论上)证明其方案是 collision resistance 的，我们所描绘的 CR 性质是从实践经验中得出的，因为目前没有十分高效的方法产生碰撞，即使是被理论破解了的MD5，想要产生碰撞，实验环境依然严苛。

hiding

对于 x --> H(x) !==> H(x) --> x 我们希望如果第三方知道H(x)，也就是x的哈希值，但不能轻易地猜测出x本身是什么字符串。

要让hash函数能够藏匿字符串，则需要该字符串来自一个拥有很高的**最小熵的概率分布(high min-entropy probability distribution)**。可以输入的字符串越多越随机，而且每一个字符串被使用的可能性都要差不多。如果某些字符串作为输入值，比其他字符串更有可能使用的话，那么这些字符串就很容易被发现，比如admin的MD5值总是很容易被优先试出。

藏匿的定义:如果r是从一个拥有很高的最小熵的概率分布中选出来的话，那么即使是得到 H(r||x)，也找不出x是什么。只要把r和x连接在一起当作输入的字符，别人即使是知道其hash值和x的所有可能性也找不出x是什么。就这样，x的信息就被隐藏起来了[1]

利用hiding的特性，可以将其用在 digital commitment 数字承诺或者说 digital equivalent of a sealed envelope 数字等效的密封信件 中。给予承诺是一个复杂的过程，需要保证消息可信，hiding 结合 CR 特性，可以保证信息可信。类比预言术:若直接预言明天股票涨停或者跌停且广而告之，可能触发羊群效应，被玩家做多或者做空。若不将消息透露，则消息不可信，无人见证，触发薛定谔的玄学力量。倘若将预言信息 hash(msg) 传播出去，等到开盘当天，将msg透露，则用户可以轻松鉴定预言是否正确。

puzzle friendly

对于 H(block header) <= target space 其中BTC的 block header == args + nonce 给定target space和 args信息，求nonce

在BTC上的应用就是挖矿，上述求nonce的过程称为挖矿。如果给出一个随机源良好的message和一堆目标值target-space，谜底是找出所有使得 H(message||nonce) 满足target-space要求的nonce。找到nonce的过程称为 Proof of Work 工作量证明(PoW)

hiding和puzzle-friendly的区别

hiding: 已知哈希值 H(r||x) r未知，即使是知道了x所有的可能性，也找不到对应哈希值的x。而且即使是找到哈希值一样的 H(r'||x') 也不知道x’是不是x，因为可能恰好找到了一个冲突。大白话就是知道了输出找不到输入。

puzzle friendly: 已知哈希值 H(r||x) 即使是给出了r，没有办法在短时间内穷尽所有x的可能性找到对应已知哈希值的x。翻译成大白话就是说，知道了输出和一部分的输入，找不到剩下的输入值。[2]

BTC 中的数据结构

区块链是由一个个的区块组成的链表

于普通链表的区别:区块链的指针为 hash pointer 普通链表指针为 address pointer 普通链表节点数据块的修改不会影响其他节点，而区块链的数据被修改，则其后的所有数据都会被影响。

通过上图描述的结构实现 tamper-evident log 防篡改证明记录。解释为:区块的节点会记录previous节点的hash值，若previous节点的数据变化，则对该前节点的哈希 H(previous block) hash将改变，触发多米诺骨牌效应，后续节点信息都将被改变，所以这种篡改操作是不被允许的。

一个完整的节点包含 block header + block body 只有 block header 的节点称为轻节点 light node，包含 block header + block body 的称为全节点 full node。header 中存在主要信息 node root hash 该节点的根hash值，而body中存在主要信息交易记录 交易记录用 merkle tree 默克尔树存储。SPV(简化支付验证，Simplified Payment Verification) 是基于轻节点的钱包设计(称轻钱包)

轻钱包并不保存完整的区块链，而是只保存每一个区块的区块头。区块体保存了完整的交易信息，而交易信息需要的存储量大部分都是交易头的跨数量级倍数以上。所以，如果只保存交易头，就可以极大的减少本地客户端存储的区块链信息。

上图为一颗 merkle tree 其类似于 binary tree 底部叶子节点的 tx 属交易记录的 data blocks，非叶子节点的value是根据它下面所有的叶子节点值Hash而出，属于 hash pointers 需要注意的是顶层的 merkle root 不是该区块链节点的 root hash 而只是该区块头里的一个字段 mrkl_root。
图片自北京大学肖臻老师《区块链技术与应用》公开课 p3视频截取。

使用 merkle tree 作为交易记录的统计结构，其作用在于提供 merkle proof / proof of membership / proof of inclusion 交易记录存在性证明 通过Merkle路径找到跟该交易相关的区块，并验证对应区块中是否存在目标交易。如何通过Merkle找到对应交易的呢？

如上图黄色标记tx为待验证的交易记录，我们的SPV需要验证该交易是否合法，过程为:

• Step1：获取黄色标记tx的哈希值，H(父级绿)=Hash(黄色交易tx)
• Step2：通过H(父级绿)和相邻交易H(父级红)的哈希值，得到祖父节点的哈希值：H(祖父绿)=H(H(父级绿)+H(父级红))
• Step3：同上，通过H(祖父绿)和H(祖父红)的哈希值，得到曾祖父级哈希值：H(曾祖父绿)=H(H(祖父绿)+H(祖父红))
• Step4：根节点的哈希值：Merkle Root=Hash(H(曾祖父绿)+H(曾祖父红))
• Step5：然后将上一步得到的根哈希值对比区块头中MerkleTree的根哈希值，如果相同，则证明该区块中存在黄色交易tx，否则说明不存在。

BTC 协议

BTC需要解决的两大难题是:货币发行量+验证交易有效性或称 防双花攻击 double speding attack

纸币和数字货币的区别：对于一个中心化的系统而言，纸币由央行直接发布(无法相信央行?)，使用时即用即无，若发行一个基于中心化的数字货币，可能会面临巨大的挑战，比如某用户可能复制多分数字货币进行交易，使用前复刻多分，央行若要处理这个问题，只能维护一个中心化的数据库，控制货币的流入和流出。该中心化的解决方案是目前使用的场景。

去中心化的系统面临的挑战可能主要来源于如何防范双花攻击。

防双花攻击

铸币权归矿工持有，通过挖矿产生的交易称为铸币交易。上图链上有两种哈希指针，其中一个用来连接区块组成区块链，一个用来指向每个账户的收入来源。每一笔交易需要发起者签名，表示该交易是被交易发起者同意过的(如图中的 Sign by A)。每一笔交易都会进行一次回溯，来验证收入来源是否正确，若发现交易不合法，区块将拒绝接受(这就是防双花攻击的策略)。

在一次 A => B 的交易过程中，A需要知道B的公钥(公钥的哈希进行某些转换后得到账户地址)才能进行转账。B需要知道A什么信息呢？B也需要知道A的公钥信息，其一是B需要用A的公钥验证A的签名Sign by A，证明交易来源，其二不单B需要知道A的公钥，所有节点也需要知道A的公钥，用来共同记账。

如何才能知道付款人的公钥信息？付款人的公钥信息由自己给出，每次交易包含输入和输出，其中输入包含币的来源和付款人的公钥，输出包含收款人的公钥哈希。

共识

CAP Theorem 是分布式系统的重要定义，他们分别是：Consistency 一致性Availability 可用性 Partition tolerance 分区容错性，这三个指标不可能同时做到。

Partition tolerance(分区容错)：大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。

Consistency(一致性)：写操作之后的读操作，必须返回该值

Availability(可用性)：只要收到用户的请求，服务器就必须给出回应

BTC是一个分布式的应用，要解决共识问题，当某些节点存在恶意(拜占庭将军问题)时，BTC采用何种机制处理。比特币系统中采用投票的方式超过半数的方式达成共识，而拥有投票权资格的，不是普通的账户，而是拥有记账权的用户，普通账户产生的成本低，此方案会存在女巫攻击 Sybil attack ，采用基于记账权(计算力)的投票，且遵循最长有效链 longest valid chain 的原则，缺省默认按照区块接收时间进行合法认证，但在某个过程中，同时产生了两个区块，指向同一个前驱节点，此时按照最长链原则，将短链抛弃。如果出现了竞争分支，长链胜出，6个确认后交易才被承认。

基于这种分叉的攻击叫做 forking attack 叉分攻击，2节点叫做 orphan block 孤儿节点。

货币发行

货币的发行基于争夺记账权产生的铸币交易。找到合法Nonce的节点会获得记账权，同时会获得铸币权的奖励。

实现

比特币系统采用基于交易的账本模式，其全节点会维护一个UTXO(Unspent Transaction Output) UTXO是未花费的交易输出，它是比特币交易生成及验证的一个核心概念。交易构成了一组链式结构，所有合法的比特币交易都可以追溯到前向一个或多个交易的输出，这些链条的源头都是挖矿奖励，末尾则是当前未花费的交易输出。

与此区别的是，以太坊ETH采用基于账户的账本模式(account-based ledger)，核心由关系数据库支撑。

挖矿过程的概率分析

挖矿过程中每次尝试nonce的过程都是一次 Bernoulli trial (a random experiment with binary outcome)，尝试Bernoulli trial的集合构成 Bernoulli Process (a sequence of independent Bernoulli trial) Bernoulli Process 的性质是无记忆性(memoryless) 做大量的试验，前面的实验结果对后面的实验结果没有影响。

实验的次数很多，每次尝试nonce成功的概率很小，其概率可用 Poisson process 近似。我们只关心出块时间，出块时间服从指数分布 (exponential distribution) 整个系统的平均出块时间是10分钟，由于前后试验nonce是无关的，10分钟到达后，依然没有找到nonce，则接下来找到nonce的概率依然是10分钟。这种性质叫progress free 如果不按照这种方式，则算力强的矿工会有不成比例的优势。

网络

比特币的设计原则是简单鲁棒而不是高效(simple，robust，but not efficient)，比特币协议工作在应用层，底层网络层运行P2P Overlay Network，基于此，比特币网络的所有节点都是对等的，无super/master node。若想加入网络，需要在 P2P 节点之间建立随机网络，就是在一个新加入节点和 P2P 网络中的某个节点间随机建立连接通道，从而形成一个随机拓扑结构。新节点与邻居节点建立连接后，还需要进行全网广播，让整个网络知道该节点的存在。全网广播的方式就是，每个节点维护一个邻居节点的集合，该节点首先向邻居节点广播，邻居节点收到广播消息后，再继续向自己的邻居节点广播，以此类推，从而广播到整个网络。这种广播方法也称为泛洪机制flooding

挖矿难度

挖矿过程符合 H(block header) <= target target越大，挖矿越容易。调整挖矿难度实际为调整目标空间在输出空间实际所占的比例。比特币用的哈希算法为SHA-256，故输出空间实际有2^256的取值。挖矿难度与目标阈值成反比：difficulty=difficulty_1_target/target 挖矿难度最小为1，target越大，难度越小。挖矿难度需要不断调整，否则随着算力的增加，出块的速度会一直加快，导致分叉(攻击)的可能性也越大。

调整挖矿难度

BTC系统每产生2016个区块就需要调整一次难度 (2016*10)/(60*24) = 14 Day。难度调整公式符合 target = target * (actual time/expected time) actual time 是挖2016个区块实际用时，expected time 是理想状况下产生2016个区块用时(2016*10)

分叉

由于同时出块，对当前区块链的状态产生分歧，导致的分叉，叫做state fork。由于分叉攻击导致的分叉forking attack也是state fork，这种人为的分叉叫做deliberate fork。由于比特币协议发生变化，而比特币是一个分布式去中心化的系统，不能同时都升级软件而导致的分叉叫做protocol fork。根据协议修改内容的不同，可以分成hard fork和soft fork。

hard fork 由于对比特币协议添加一些新特性，扩展新功能而导致的分叉，就是硬分叉。旧节点不认新节点，新节点认旧节点。

soft fork 对区块链协议进行一些限制，导致原本合法的区块变得不合法。新节点发布，旧节点认，旧节点发布新节点不认，导致旧节点称为孤儿节点。

ETH

以太坊的出现是对比特币系统的改进，比如出块时间从比特币系统的10分钟左右变为十几秒，挖矿用的mining puzzle 由BTC的计算密集型(算力决定)变为由内存决定(memory hard mining puzzle)。在一定程度上限制了专业芯片的使用，将来还可能将 proof of work 工作量证明(挖矿方式)转为 proof of stake 权益证明(股份方式)。以太坊还添加了对智能合约 smart contract 的支持。

账户

BTC采用基于交易的账本，系统只能通过UTXO推算账户余额。以太坊采用基于账户的模型 account base ledger 系统显式记录账户余额，这种方式对于双花攻击有天然的防御作用，每花一次钱，将会在账户上扣除一次。但是容易产生 replay attack 重放攻击。

externally owned account:外部账户，通过公私钥控制的ETH账户。账户结构含有 balance 余额 和 nonce 交易次数

smart contract account:合约账户，包含外部账户的结构还包含 code 代码 和 storage 存储。

状态树

account base ledger 需要完成一个从 addr -> state 的映射。

通过全节点维护一个哈希表的方式，记录账户的状态变化，看似可行，但是交易采用 merkle tree 进行管理，在进行 merkle proof 证明账户余额时，每新添加一个区块，均需要从新构造一个包含所有账户的 merkle tree 这显然是不合理的，实际上账户状态发生变化的只有小部分，这样实现的代价太大。这与BTC系统不同，BTC使用UTXO进行账户管理， merkle tree 维护的区块交易记录是不变的，而ETH的账户模式如采用这种merkle tree进行管理，则存在千万级别的叶子节点。

如果不使用哈希表，直接将所有账户在一颗大的 merkle tree 进行维护，这样 merkle tree 没有一个高效的方法进行账户的查询和更新，且全节点如果不进行排序，构建出来的 merkle tree 将是不唯一的。

trie 字典树

树形结构，哈希树的变种。典型应用是用于统计，排序，所以经常被用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
性质:根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。

Patricia trie 压缩前缀树

将trie树的公共节点进行压缩。键值分布稀疏，路径压缩效率较高。

Merkle Patricia tree

是Ethereum的数据结构，用来存储用户账户的状态及其变更、交易信息、交易的收据信息。每一个以太坊的区块头包含三颗MPT树，分别是：交易树、收据树(交易执行过程中的一些数据)、状态树(账号信息， 合约账户和用户账户)

交易树和收据树

交易树、状态树、收据树均使用MPT，代码同一，便于管理。

交易树和收据树只将当前区块的交易组织起来，状态树则需要将所有账户状态组织到一起，而不管账户与当前区块有何关系。状态树共享节点，而交易树和收据树独立。

交易树：提供 merkle proof 向轻节点证明某个交易是打包在区块中的。

收据树：向轻节点证明某个交易的执行结果

为了提高查询的效率，ETH采用了 bloom filter 布隆过滤器。

ETH的运行过程可以看成是一个 transaction-driven state machine 交易驱动的状态机。状态机的状态就是所有账户的状态。交易是每次发布区块所包含的交易，执行这些交易，会驱动系统从当前状态转移到下一个状态。
类比BTC，其状态就是UTXO，没有被花掉的输出。他们的共同点是：状态转移都是确定的。

GHOST

BTC和ETH都是运行在应用层上的共识协议，底层为工作在网络层的P2P overlay network，由于其拓扑协议做flooding，使得本身传输时间较长，ETH在大幅提高出块速度后，导致区块发布到其他节点可能需要很长时间。这种问题使得链分叉成为常态。

为了解决经常性的临时链分叉，ETH采用GHOST协议(初版本)，给予分叉区块以奖励，ETH规定不在最长合法链上的分叉区块叫做 uncle block 叔父区块，给予挖掘叔父区块的矿工 (7/8) * 出块奖励 个奖励(uncle reward)。对于最长合法链上的最新一个区块，可以包含最多两个叔父区块的哈希值，并给予 uncle block包含数量 * (1/32 * 出块奖励) 额外的奖励。
如此行事，存在问题：

1. 分叉出的叔父区块多于两个，导致其他的叔父区块无法得到额外奖励
2. 最长合法链上的最新区块故意不包含叔父区块，导致叔父区块得不到额外奖励
3. 网络延时较大，导致最长合法链上的最新区块没有检测到处于发布中的叔父区块

协议改进：最长合法链上的最新区块总是检测没有包含的叔父区块，并将最多两个叔父区块的哈希包含到自己的结构体中。同时规定叔父区块只能包含在7代以内，且隔代关系越远，额外奖励越少。

挖矿算法

对于基于工作量证明的区块链系统来说，挖矿是区块链系统安全的重要保障。

比特币的挖矿时，只需进行简单的哈希运算，于是比特币的挖矿过程逐渐成为了计算力的竞争，于是出现了专门为这种运算而生的ASIC矿机，相比于个人计算机，ASIC只能针对BTC的挖矿逻辑进行计算，其效率是普通计算机的几个数量级倍。由于ASIC矿机的出现，也促使矿池矿场的出现，使得挖矿趋于中心化，这与比特币当初设计之初的去中心化理念背道而驰了。
目前区块链系统设计 mining puzzle 时首要考虑目标就是做到对抗ASIC ASIC resistance。设计对 ASIC 不友好的puzzle的常用做法是增加puzzle对内存访问的需求 memory hard mining puzzle。

ASIC只能进行运算，却没有额外内存空间，基于此，以太坊设计了新的memory hard mining puzzle。以太坊目前的共识机制是 PoW(Proof of Work 工作量证明机制)，使用的算法是Ethash,这种算法是对 Dagger-Hashimoto算法的改良版本，流程大概如下：

1. 对于每一个块，首先计算一个种子(seed)，该种子只和当前块的信息有关;然后根据种子生成一个16M的随机数据集(cache)
2. 根据Cache生成一个1GB大小的数据集合DAG(有向非循环图)，它是一个完整的搜索空间，挖矿的过程就是从DAG中随机选择元素(类似于比特币挖矿中查找合适Nonce)再进行哈希运算，可以从Cache快速计算DAG指定位置的元素，进而哈希验证

要求对Cache和DAG进行周期性更新，并且规定DAG的大小随着时间推移线性增长。

以太坊宣传将过渡到POS (proof-of-stake)，代替传统的POW(proof of work) ，挖矿模式将会被淘汰掉，这种口头宣称也是ASIC resistance的表现。

难度调整

以太坊中的区块的难度调整公式

难度调整公式中的 x 和 ϵ2 的计算公式

ϵ2 的公式意义

难度炸弹公式

以上截图来自 北京大学肖臻老师《区块链技术与应用》公开课

权益证明

BTC和ETH均采用基于工作量的证明，POW受到的普遍的批评就是浪费电力资源。矿工挖矿是为了获得出块奖励。而系统给予出块奖励的目的是激励矿工参与区块链系统维护，进行记账，而挖矿本质上是看矿工投入资金来决定的**(投入资金买设备->设备决定算力->算力比例决定收益)**。

既然挖矿本质上是矿工投入资金的比拼，是否可将矿工买矿机的钱投入到区块链系统开发和维护中，而根据投入钱的多少来进行收益分配呢？这就是权益证明的基本思想。

一般来说，采用权益证明的货币，会先预留一些货币给开发者，比如ETH预留了将近1200万ETH在项目团队手中，开发者通过出售这部分预留货币换取开发经费，在系统进入stable状态后，每个人按照持有货币的数量进行投票。

这样处理的好处：

1. 省去了挖矿的过程，避免了因此产生的能耗和对环境影响。
2. POS的闭环特性。区块链安全的资源可以形成闭环，发动攻击的资源只能通过区块链系统内部获得。在POW系统中，区块链系统的维护需要现实世界的矿机设备参与，这导致只要外围聚集大规模的资本，就可以攻击成功。

这样产生了问题，持有的货币越多，挖矿难度越小，产生公平性问题 proof of deposit。权益证明早期共识机制遇到的挑战 双边下注 nothing at stake

区块链系统产生了分叉，存在两个区块A和B竞争主链时，采用权益证明的方法就是所有持币者对这两个区块投入币进行投票，从而决定哪一个区块成为最长合法链上的区块。假如有一个人，在A和B同时进行了下注。最终A区块胜出，那么他能够获得A区块相应收益，而在B区块进行投票放入的“筹码”也会被退还，这也就导致其每次都能获得收益。[3]

以太坊将采用的POS协议是 Casper the Friendly Finality Gadget(FFG) 过渡阶段需要 POS + POW 混合使用。

Casper协议引入一个概念：Validator(验证者)，一个用户想要成为Validator，需要上交一笔“保证金”，这笔保证金会被系统锁定。Validator的职责是推动系统达成共识，投票决定哪一条链成为最长合法链，投票权重取决于保证金数目。[3]

采用两次投票的方式：预投票 Prepare Message 和Commit 投票 Commit Message，规定每次投票结果都要获得2/3以上的验证者同意。在实际中，针对其进行了一些修改，两次投票在实际中只需要一次即可。[3]

矿工挖矿会获得出块奖励，而验证者也会得到相应奖励。当然，为了防止验证者的不良行为，规定其被发现时要受到处罚。例如某个验证者“行政不作为”，不参与投票导致系统迟迟无法达成共识，这时扣掉部门保证金；如果某个验证者“乱作为”，给两边都进行投票，被发现后没收全部保证金。没收的保证金被销毁，从而减少系统中货币总量。验证者存在“任期”，在任期结束后，进入“等待期”，在此期间等待其他节点检举揭发是否存在不良行为，若通过等待期，则可以取回保证金并获得一定投票奖励。[3]

智能合约

看智能合约相关信息，有点头大，后面慢慢来。智能合约

进度

• BTC 密码学基础
• BTC 基础结构
• BTC 协议
• BTC 实现
• BTC 网络
• BTC 挖矿难度
• BTC 分叉
• ETH 账户
• ETH 状态树
• ETH 交易树和收据树
• ETH GHOST
• ETH 挖矿算法
• ETH 难度调整
• ETH 权益证明
• ETH 智能合约

参考

北京大学肖臻老师《区块链技术与应用》公开课
引用1:藏匿的定义
引用2:hiding和puzzle-friendly的区别
引用3:双边下注
以太坊挖矿原理