区块链技术与应用(二)

北京大学肖臻老师《区块链技术与应用》笔记 - ETH篇
北大肖臻《区块链技术与应用》公开课学习笔记
区块链知识

ETH 账户

• ETH 维持账户的概念, 这种账户的概念和我们平时使用的账户概念相似, 这个ETH账户概念可以有效抵御双花问题. 但是同时会产生重放攻击的问题.
  • double spending attack(双花攻击, 支付方不诚实, 一笔钱花了两次) : , 比特币中使用UTXO交易模型抵御 double spending attack;
  • replay attack(重放攻击 收款方不诚实, 复制这次交易, 收两次钱) : , ETH中使用计数器(每笔交易中都有一个nonce字段, 用来记录这是第多少比交易), 如果有人重放这次交易的话, 需要修改 nonce 字段, 但是如果修改了 nonce 字段, 那么这次交易的hash就会改变, 由于其他人没有私钥, 无法重新签名, 所以这样可以有效的抵御重放攻击.
• 账户分类
  • 外部账户 (使用公私钥控制的账户.)
    • balance (账户余额)
    • nonce (交易计数)
  • 合约账户(不能主动发起交易, 所有的交易只能由外部账户发起. 合约账户只能调用另一个合约)
  • ETH 添加合约账户, 是因为, ETH 使用了智能合约, 而使用合约需要一个稳定的账户(BTC中没有稳定的账户), 不能使用某个账户签订完合约后, 又使用另一个账户去履行合约), 创建合约时候会返回一个地址, 通过地址可以调用合约, 调用过程代码不变但是状态会发生改变.
    • balance (账户余额)
    • nonce (合约的调用次数)
    • code (代码)
    • storage( 存储, 每个变量的值)

状态树

• 作用

  • 防篡改, 只要 Merkle Patricia Trie root hash 没有改变, 整个树的任何部分都无法篡改.
  • 通过提供自己账户所在的分支作为 merkle proof 提供给轻节点, 轻节点可以验证账户的余额.
  • 可以证明某个收款账户是不存在的.

• ETH中使用MPT(Modified Merkle Patricia Trie)做的状树(address和state的映射关系, key是地址, value是账户状态(将账户状态序列化(RLP编码 : Recursive Length Prefix)存储在树中));

  • 使用字典 : 无法提供 merkle proof, 因为如果提供merkle proof, 需要将字典中的元素组织成 merkle tree, 然后将 merkle root hash 保存, 但是有个问题是每次有新的交易产生, 需要遍历所有的用户, 然后重新组织成merkle tree, 而用户量是巨大的(BTC中的 merkle proof 用在block中, 每个block中大约有4000个交易, 而且组织完之后是不需要改变的, 区块打包后不用改变)

  • 直接使用merkle tree : 没有高效的查找和更新的方法. 而且如果这个merkle tree的叶子结点没有排序, 那么每个人的生成的merkle tree是不唯一的, 算出的merkle root hash也不唯一(BTC中的merkle tree是获得记账权的节点说了算的);

  • 使用排序的 merkle tree : 新增一个账户发生交易的时候, 整个merkle tree 的结构还是要改变的.

  • trie(字典树, 前缀树) :

    • trie中每个节点的分支数目取决于Key值中每个元素的取值范围(图例中最多26个英文字母分叉+一个结束标志位);
    • trie查找效率取决于key的长度。实际应用中（以太坊地址长度为160byte）。;
    • trie中每个节点的分支数目取决于Key值中每个元素的取值范围(图例中最多26个英文字母分叉+一个结束标志位);
    • 给定输入，无论如何顺序插入，构造的trie都是一样的
    • 更新操作局部性较好

    • 树的高度太高, 对内存不友好.

      
      image.png

  • Patricia trie(压缩前缀树) : 压缩树的高度(对于key分布稀疏的情况, 使用压缩前缀树和使用前缀树的差别是很明显的)

    
    image.png

  • Merkle Patricia Trie(MPT) :

  • Modified Merkle Patricia Trie : (ETH中使用 Modified Merkle Patricia Trie)

    
    image.png

• 发布新区块, 状态树中的部分节点状态会改变. 这种改变不是原地修改, 而是保留原本状态并新建分支, 这样方便回滚(分叉节点回滚回上一个状态并拼接到最长链后边).

  
  image.png

• 数据结构

  • header

    
    image.png

  • block

    
    image.png

  • 区块在网络上发布的时候的信息

    
    image.png

交易树

• 只组织当前发布的区块的交易, 状态树需要把系统中所有账户的状态都包含进去,无论账户和当前区块是否有关系.
• 各个节点之间不同享节点
• 向轻节点提供 Merkle proof, 证明某个交易被打包到区块中.

收据树

• 只组织当前发布的区块的交易, 状态树需要把系统中所有账户的状态都包含进去, 无论账户和当前区块是否有关系.
• 各个节点之间不同享节点
• 向轻节点提供 Merkle proof, 证明某个交易的执行结果.

布隆过滤器

• 可以证明某个元素一定不能在集合中/可能(发送hash碰撞, 会误报, 所以是可能)在集合中.
• 每个收据中包含一个布隆过滤器, 几率交易的类型, 地址等其他信息, 发布的区块在header中也有个总的布隆过滤器, 这个总的布隆过滤器是区块中所有交易的所有布隆过滤器的并集.
• 使用布隆过滤器, 查找过去某个时间段内的发生的和某个智能合约相关的所有交易, 先查询哪个header的中总的布隆过滤器中包含要查找的交易类型, 如果块头的总布隆过滤器中不包含这个交易, 则表示一定没有, 如果包含这个交易类型,在去查找区块中所包含的交易所对应的收据树中的布隆过滤器.

GHOST 协议

• 因为ETH中的出块时间大幅度减少(15s), 但是导致频繁的临时分叉, 且分叉多, 这对于共识协议是个挑战, 所以使用了改善的 GHOST协议(对于非决策节点, 也给予挖矿奖励, 否则会大大降低矿工的挖矿积极性, 而矿工相对于大型矿池相比, 有天然的劣势(矿池可能一直沿着自己挖出的区块接着挖), ).
• 方案

  • 第一版

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

      • 矿工自私，故意不包含叔父区块，导致叔父区块7/8出块奖励没了，而自己仅仅损失1/32。如果甲、乙两个大型矿池存在竞争关系，那么他们可以采用故意不包含对方的叔父区块，因为这样对自己损失小而对对方损失大。

        
        image.png

  • 第二版

  • 规则

    • F为E后面一个新的区块。因为规定E最多只能包含两个叔父区块，所以假定E包含了C和D。此时，F也可以将A认为自己的的叔父区块(实际上并非叔父辈的，而是爷爷辈的)。如果继续往下挖，F后的新区块仍然可以包含B同辈的区块(假定E、F未包含完)。这样，就有效地解决了上面提到的最初Ghost协议版本存在的缺陷。

  • 缺点

    • “叔父”这一定义隔多少代才好呢, 如果不限定, 只要一直出挖叔父区块然后坐等收钱就行了, 不合理.

      
      image.png

  • 第三版

    • 规则

      • M为该区块链上一个区块，F为其严格意义上的叔父，E为其严格意义上的“爷爷辈”。以太坊中规定，如果M包含F辈区块，则F获得7/8出块奖励；如果M包含E辈区块，则F获得6/8出块奖励，以此类推向前。直到包含A辈区块，A获得2/8出块奖励，再往前的“叔父区块”，对于M来说就不再认可其为M的"叔父"了。 对于M来说，无论包含哪个辈分的“叔父”，得到的出块奖励都是1/32出块奖励, 也就是说，叔父区块的定义是和当前区块在七代之内有共同祖先才可（合法的叔父只有6辈）。

        
        image.png

  • 如果规定将下面整条链作为一个整体，给予出块奖励，这一定程度上鼓励了分叉攻击(降低了分叉攻击的成本，因为即使攻击失败也有奖励获得)。因此，ETH系统中规定，只认可A区块为叔父区块，给予其补偿，而其后的区块全部作废。

    
    image.png

ETH 挖矿算法

• 比特币的挖矿算法需要专业的矿机进行挖矿, 普通的计算机用户难以参与, 导致挖矿中心化的局面产生, 与设计初衷的"去中心化"违背, 由此就诞生了ETH的ASIC Resistance挖矿算法. 还有人认为使用矿机挖矿比使用通用计算机挖矿更安全, 因为如果有人需要发动攻击的时候, 需要购买大量的矿机后参与挖矿然后才有可能发动攻击, 但是如果使用通用计算机挖矿, 那么很多科技公司可以在发动攻击时候使用自己的服务器去集中攻击, 平时服务器还是正常使用.
• 莱特币挖矿算法思想
  • 流程

    • seed位种子节点, 通过对seed运算出得出数组第一个元素, 之后每个元素都通过前一个位置的元素的hash得到. 这样每个元素和前一个元素都是有依赖关系的.

      
      image.png

    • 求解puzzle的时候, 随机一个索引, 根据索引从数组中取出一个元素, 然后对这个元素进行运算求出下一个索引, 然后重复这个过程.

      
      image.png
  • 分析
    • 如果数组足够大, 矿工必须存储这个数组, 而频繁的访问这个数组就涉及到大量的内存读取.从而实现对ASIC芯片不友好. 但是对于轻节点节点验证来说 一样是不友好的, 验证的时候需要重复这个过程, 所以这个数组无法设置的过大, 只能是128K, 而128K对于矿机来说, 没有起到应有的作用.
• 以太坊挖矿算法思想

  • 流程

    • 以太坊设计了两个数组, 分别是 16M的cache和1G的dataset(两个数组的大小是初始大小, 每隔30000个区块, newSeed = hash(seed), newCache.size = cache.size + cache.size * 1 / 128(增加128K), newDataSet.size = dataset.size + dataset.size * 1 / 128 (增加8M)). 在cache中通过hash(seed)得出数组第一个元素, 之后每个元素都通过前一个位置的元素的hash得到. 这样每个元素和前一个元素都是有依赖关系的.dataset中的每个元素都是随机一个索引, 根据索引从数组中取出一个元素, 然后对这个元素进行运算求出下一个索引, 然后重复256次, 得出的结果放在dataset的数组中.

      
      image.png
    • 求解puzzle的时候根据区块block header 和其中的 nonce值计算一个初始hash, 根据hash值映射到数组中的索引A, 读取A及A(A下一个索引)位置的元素, 然后对两个数组进行运算, 得出下一个索引B和B, 循环执行64次. 将最终得到的hash值与难度目标阈值比较, 如果 result <= target求解puzzle成功, 否则更换nonce然后重复以上过程直到最终result <= target; 轻节点验证的时候, 是临时计算出用到的dataset的元素.
      image.png

  • 伪代码

    
    image.png

  • mkcache

  • 分析

    • 目前以太坊挖矿以GPU为主，可见其设计较为成功，这与以太坊设计的挖矿算法(Ethash)所需要的大内存具有很大关系。

挖矿难度调整

• 难度调整算法

  • 难度最小值是 D0, 第0个区块的难度就是D0;

    
    image.png

  • 自适应难度调整, 基于父区块的时间戳和本区块的时间戳(单位是s).

    
    image.png
    image.png
  • 难度炸弹, 难度炸弹设计的目的是防止从Pow转为Pos时候, 一部分矿工不转换, 使ETH分叉, 使用难度炸弹后, 如果矿工不转换到Pos, 那么难度炸弹的威力指数上升, 矿工挖矿难度大幅度提升.

  • 起初难度炸弹没有减去300W的操作, 但是当难度炸弹的威力体现出来的时候, 发现Pos的一些问题还没有解决掉, 无法切换, 这时候通过减去300W的操作延迟难度炸弹的威力，为POS的实现争取了一定的时间

    
    image.png

• 难度炸弹代码

  
  tz8jrpi6wq.jpg

权益证明 (proof of state)

• 定义
  • 按照所占权益投票进行共识达成，类似于股份制有限共识按照股份多少投票，权益证明不需要挖矿. 这对于矿机厂商来说很不友好, 因为矿机的开发周期长, 成本高, 如果矿机开发成功了, 以太坊改为使用权益证明达成共识, 这对以矿机厂商来说很尴尬, 以太坊目前仍然是POW挖矿共识机制。在设计之初以太坊生成自己下一年就改成POS, 然后第二年说自己下一年就使用POS, 就这么一直骗，以太坊开发者就设想要从POW转向POS，并为了防止有矿工不愿意转埋下了一颗“难度炸弹”。但截至目前，以太坊仍然基于POW共识机制。
• 预挖矿(Pre-Mining) : 开发以太坊时，给开发者预留了一部分货币给开发者
• 预售(Pre-Sale) : 将预留的货币出售掉用于后续开发，类似于拉风投或众筹.
• 分析
  • 使用Pow共识机制, 超级有钱的大户可以购买大量的矿机, 然后集中攻击一些小币种, 使去区块链账本回滚, 从而让用户不在相信这种币, 然后将这种币扼杀.
  • 使用Pos共识机制, 只有拥有大量的币的用户才可以投票, 那么只能购买大量的币, 而购买大量的币会使币的价格上涨.
    • 分析
      • 简单的共识机制, 会导致拥有币越多的人挖矿变得越简单.
      • 简单的共识机制, 会出现有的人两边下注(分叉时候, 两边都投票, 反正哪个下注成功都会有分红)
        • 两边下注解决方案

          • 引入验证者validator，交点保证金。每挖出100个区块作为epoch, 进行两次投票(prepare message 和 commit message), 然后只有每一轮投票都要超过三分之二的验证者通过才能通过。 现在改为每50个区块作为epoch,然后进行一次投票, 这次投票作为上一轮的commit message同时作为下一轮的prepare message; 验证者可以得到奖励, 乱投票/不作为会没收保证金. 验证者的任期满了会换届, 然后保证金会被冷却一段时间, 过一段时间没有问题后保证金才能被取出来用作下一次保证金.