区块链总览

在实际运行中，交易网络和记账网络是分离的。

区块链分类

区块链底层基础

哈希指针

传统交易的存储方式，可以简化为两个表——账户表、交易日志表。如果一个攻击者需要修改，其所需的时间复杂度为$O(1)$

Hash指针将指针和Hash函数相结合，哈希指针不仅包括数据存储的指针（即地址），还包括所指数据的哈希值。知道一个数据的指针可以取回该指针所指的数据，知道一个数据的哈希指针不仅可以取回该指针所指的数据，还可以判断该数据是否已经修改。

T1交易数据的哈希指针存在T2交易中，将T2交易数据和携带的T1的哈希指针生成一个新的哈希指针存在T2交易中

区块结构

分布账本

账本的记录是分布式的，其解决了传统的“单点失败”、“中心作恶”问题

但是带来了 “数据一致性”、“代价效率问题”

单独采用链式结构不使用分布账本是否可以取得更好的效果呢？
答案是否定的。采用链式结构的中心账本和单纯的中心账本比，具有更好的数据的完整性和真实性，但是依然不能防止中心作恶，中心是没办法篡改数据了，但是可以有选择性的区分节点，可以威胁节点。

区块链预备知识

结构基础

哈希函数

哈希：任意长度字符串映射到定 定义 长字符串的函数 （例如SHA256）

Hash函数的实现基本上是由若干个压缩函数组成 Hash函数实质上是多次执行特定的压缩函数

• 特性

  • 括免碰撞性
  • 隐匿性：很难逆向计算的函数称为单向函数 。
  • 谜题难解性

• SHA256

  • 输出长度为256比特的消息，通常用一个长度为64的十六进制字 符串来表示
  • 具体参考 密码学基础

梅克尔树

区块链实际系统中为了节省资源，大多数采 用多个交易打包成一个区块，然后将区块作 为一个计算单元来梅克尔。

在单个区块中有成百上千的交 易是非常普遍的，这些交易都 会采用同样的方法归纳起来， 产生一个仅仅32字节的数据作 为梅克尔树根。
为了证明区块中存在某个特定 的交易，一个节点只需要计算 log2(N) 个32字节的哈希值， 形成一条从特定交易到树根的 认证路径或者Merkle路径即可

默克尔证明

在比特币或者以太坊的场景下，一个区块大概有两三千笔交易，一个交易又包含若干字段，如果逐一比较交易不仅速度慢，而且不安全，因为拿单一的区块无法知道拿到的块的真伪。

merkle proof是一种仅需链中全量header就可以证明交易是否存在（proof of membership）某一区块中的方法。

例如 想要验证黄色的tx在不在。需要经过以下步骤

• 请求全结点，返回所有红色的哈希
• 逐层向上计算，比如最底层绿色（即黄色tx的哈希）与红色逐层向上求哈希，即可得到默克尔树。
• 然后对比计算出来的和存入的

区块结构

区块结构：区块大小、区块头、交易计数器、交易

网络基础

运行流程

• 结点发现：新结点需要找到已经存在在区块链的一个结点才能完成加入。有两种方式
  • 第 1 种是域名系统 (domain name system, DNS) 种子节点, 即节点向 DNS 服务器发送请 求获取种子节点的地址, DNS 服务器返回一个可连接的 IP 地址列表.
  • 第 2 种是硬编码种子节点, 即将一部分长期 稳定运行的节点硬编码至代码中
• 邻居选取：邻居选取决定网络拓扑和性能. 当连接成功后, 新节点需要足够数量的邻居确保连接的稳定性, 即新节点将自 身的地址信息发送给邻居, 邻居节点进行转发以保证新节点被更多节点发现
• 结点维护：比特币和以太坊定期发送探活消息维持连接

激励基础

比特币

比特币就是一种数字货币。

比特币地址

申请账户是用户自己来处理的，即自己创建一个公钥-私钥对。一对公私钥就是一个账户。

私钥是随机生成的一个数字。

比特币中私钥使用椭圆曲线乘法这个单向加密的函数可以生成另一个数字，这个数字就是这个私钥所对应的公钥。

比特币的交易过程中，每一笔交易都包含有一个或是 多个的“输入”，同时也包含了一个或是多个的“输 出”。并且输入和输出的总额并不一定持平，一般而 言输出的总额要略小于输入，两者之间的差额代表了 一笔默认的交易费用，交易费用会支付给将该交易计 入账簿的矿工。

比特币钱包

• 功能
  • 存储公私钥
  • 生成地址
  • 网络广播
• 钱包技术：用于管理公私钥
  • 非确定性钱包：私钥是由没有逻辑关系的随机序列生成， 因此私钥之间没有逻辑关系
  • 确定性钱包：
    • 1、为了避免非确定性钱包备份开销问题， 通过引入钱包种子（助记词）的方式，生 成新的私钥序列。
    • 2、只需要备份种子就可以保证恢复所有密 钥，备份开销更小，恢复也十分便捷。
  • 分层确定钱包：
    • 以树状的方式生成新的私钥。在备份和恢复的时候仍然只需要保存种子
    • 具有主公钥属性，不仅可以用主私钥（种子直接生成）生成之后的所有私钥序列，还可以用对应的主公钥生成之后钱包中所有地址序列，并保证地址和生成的私钥对应。

比特币交易

消息中包发送者的公钥，使用发送者的私钥进行签名，这样就能确认该交易是属于发送者的，并且该消息确实是发送者所发送的

• 比特币交易的主要构成部分：版本信息、交易输入、交易输出和锁定时间
  • 版本号：告知比特币节点和矿工应该使用哪一套规则用来验证这笔交易
  • 每一笔交易中至少包含一个交易输入和一个交易输出，
  • 每个交易输入会花费上一个交易输出产生的比特币，
  • 每个交易输出都作为UTXO直到被作为交易输入花费掉

双花攻击与有效性

【双花攻击】

B已经把全部的比特币转给C和D，B又要转给F 5个比特币，说明的币的来源来自于第二个交易中。别的节点收到这个交易后，从这个新的区块往币的来源回溯一下，到第三个交易时发现这5个比特币已经在这个交易（B将自己的5个比特币转给C 2个和D 3个）中被花出去了，就说明新的这个交易是不合法的，不会把它接受到区块链里

【有效性】

比特币交易中输入部分除了要说明币的来源，还要说明付款人的公钥，而且付款人的公钥需要和币的来源里的公钥的哈希对得上。A给B转账的时候提供的公钥需要和铸币交易中公钥的哈希对的上，这样就防止了恶意节点伪造A的公钥来偷走A的比特币

交易构成-UTXO

⽐特币交易的基本单位是未花费的交易输出，简称UTXO（Unspent TransactionOutput）。比特币币值最小单位是聪，类似于人民币中的分，1聪为0.00000001个比特币，

• 被交易消耗的UTXO称为交易输⼊
• 由交易创建的UTXO称为交易输出

找零的意思：比如A给B五块钱，上一次的交易是10块钱，那么要找零5块钱。

交易过程

• A卖书，B买书
• A老板创 建一个地址（生成公钥和私钥对）用于接收本次交易的比特币，并且把公钥给B同学。
• B同学给自己同学C借了1BTC
• B同学利用 他的私钥 对前一次交易（比特币来源C） 和 下一位所有者A老板的信息 签署一个数字签名【即对她的交易申请进行签名，包含借钱和买书】， 并把这个签名附加在这枚货币的末尾，制作成交易
• B同学将交易广播至全网，每个节点都将受到的交易信息纳入一个区块中
• 每个节点通过解一道数学难题，从而去获得创建新区块权 利，并争取得到比特币的奖励
• 当一个节点找到解时，它就向全网广播该区块记录的所有盖时间戳交易，并由其它节点核对
• 全网其它节点核对该区块记账的正确性，没有错误之后他 们将在该合法区块之后竞争下一个区块，这样就形成了一 个合法记账的区块

交易脚本

类似智能合约。脚本是保障交易完成，检查交易是否合法的核心机制，当所依附的交易发生时被触发。一般每个交易都会包括两个脚本：负责输入的（scriptSight）解锁脚本和负责输出的（scriptPubkey）锁定脚本

比特币网络

• 按照承载功能类型（注：一个结可能均包含下属四个结点的功能）
  • 钱包
  • 矿工
  • 完整区块链
  • 网络路由节点
• 按照功能
  • 核心：包含钱包、矿工、完整区块存储、网络路由四种功能
  • 全结点： 拥有完整的区块链数据，具有网络路由功能
    • 每个节点都有一个完整的账本副本，因此所有交易数据公开透明，系统中的人都可以看到
    • 每个节点的权利是一样的，任意节点被摧毁，都不会影响到整个系统的安全，也不会造成数据丢失
    • 每个节点的账本数据是完全一样的
  • 独立矿工
  • 轻量级钱包：只具有钱包和路由转发
    • SPV节点：轻节点就是只拥有和自己相关的交易数据节点
      • 不能独立地进行区块和交易的验证。无法验证大多数交易合法性，只能检验和自己相关的交易合法性
      • 不一定全程在线
      • 只能检测哪个是最长链，不知道哪个是最长合法链
      • 无法检测网上发布的区块正确性

比特币区块

• 区块链高度与深度

  • 高度：区块链的最新长度
  • 深度：交易确认区块数
    • 如果包含一个交易的区块，已经被6个区块校验过，即可认为不会被篡改和在该块之前产生分叉，从而判断交易是有效的
    • 用以避免链分叉的双花攻击

• 区块一致性

  • 创世区块一致性
  • 新区块一致性

• 区块链分叉

  • Case 1：相近时间同时挖出
    • 存在两个节点 同时或者在相近时间 计算出合法区块。当这 种情况发生时，区块链就会发生分叉。
    • 此时，比特币协议对节点选择某个区块并无要求，仅需要在自己最早听到的区块后计算下一个区块即可。
    • 一旦某个分支率先计算出下一个区块，所有节点应当放弃较短的分支，到较长分支后进行新区块计算。这也就是比特币的“最长链法则”
    • 将在下一节详细说明
  • Case 2：例如共识规则改变
    • 当实施新规则时，未升级的节点将遵循旧规则，而升级后的节点将遵循新规则，这可能会在一段时间内产生分叉，因为节点的更新需要时间，
    • 硬分叉：对区块链协议进行重大改变的分叉方式
      • 升级结点不同意旧规则，未升级节点不同意新规则。
      • 结果——产生了永久的分叉；在硬分叉之后，旧版本的节点将无法与新版本节点相互通信，导致分裂出两个不兼容的区块链网络。
    • 软分叉：对区块链协议进行向后兼容的改变
      • 升级结点同意旧规则，未升级节点不同意新规则。（旧版本的节点仍然可以验证和处理新版本的区块链。只要新区块还遵守旧结点共识规则，即新旧规则有交集）
      • 结果——产生暂时性地分叉

• 区块压缩与区块剪裁
  • 区块压缩：多个区块合并
  • 区块剪裁：中间已经被验证且不适用地直接剪裁。

区块链矿工

• 挖矿过程
  • 挖矿是通过不断修改一个随机数，重复计算区块头的哈希， 直到找到一个与目标值匹配的哈希的过程。

在挖矿过程中，矿工先创建一个填满交易的候选区块。接着，矿工计算区块头的哈希，看其是否小于当前的目标值。 如果哈希不小于目标值，矿工就修改随机数（通常就是对随机数加1）并进行计算。在比特币网络中，矿工需要进 行上亿次计算才有可能找到一个随机数，得到的哈希值足 够小。

• 难度调整
  • 为了维护区块频率的稳定性，需要对挖矿难度进行调节。
  • 每经过2016个区块，所有节点都会调整工作量证明的难度。难度调整算法会计算出最后2016个区块的产生时间，并与预期时间20160分钟进行比较，如果实际产生时间大于20160，那么会降低挖矿难度，否则就会上调挖矿难度。

    最长合法链

    区块链正常运行场景下可能会产生分叉。当两个节点同时获得记账权时，会有两个等长的合法链。

在缺省情况下，节点接收最先收到的区块，该节点会沿着该区块继续延续。但随着时间延续，必然有一个链胜出，由此保证了区块链的一致性（被扔掉的区块称为孤儿区块orphan block）

分叉攻击

M发布一个转账交易给A，已经写到区块链里了。M获得了记账权，把钱再转回给自己，很明显为一个非法区块，不会被其他节点承认。

区块插入到哪一个区块之后是在刚开始挖矿的时候就要决定的（而不是在获得记账权之后）

如果M转账给A的交易不是在最后一个区块，而是后面又跟了几个区块，那么这种攻击的难度就大大增加。M要想回滚交易，要想办法让下面这条链成为最长合法链。诚实的节点不会沿着下面的区块往下扩展，相当于是恶意节点挖下面的链，其他节点挖上面的链的算力比拼。如果大部分算力是掌握在诚实的节点，则最终上面链会胜出，而恶意节点的链会不被认可，从而导致投入成本白费

一种简单防范就是多等几个确认区块（confirmation）。比特币协议中，缺省需要等6个确认区块

如果发现这个交易最后没有写到最长合法链，购物网站可以选择取消发货

以太坊

以太坊（Ethereum）是一个基于区块链的智能合约平台。

以太坊=比特币+智能合约。

以太坊账户

• 账户的地址
  • 密码+关键文件=私钥
  • 私钥 —（椭圆加密曲线）—> 公钥
  • 公钥 — （哈希）—> 压缩公钥
  • 压缩公钥—前20字节—账户地址
• 账户分类
  • 外部账户：由用户创建的账户
  • 合约账户：外部账户创建的庄户。每个合约账户对应唯一的合约代码
• gas
  • 衡量交易耗费的计算资源的一种计量单位（注意：是单位，不是实际数额）
    • 不可交易性：gas只是一种衡量耗费资源的单位，因此它不能在以 太坊中交易，矿工需要将gas转换成以太币作为收益。
    • 价值恒定性：在gas兑换成以太币的过程中，以太坊通过一系列机 制保证gas的价值不会发生太大变化。
  • 相关概念
    • gasPrice
    • gasCost
    • gasLimit
    • gasFee
• 以太坊
  • 
  • 三类树
    • 状态树：状态树是 记录账户状态的树形结构，因此需要将账户地址映射到账户状态
      • 
    • 交易树：交易列表形成交易树，每个区块都有一棵独立的交易树。交易编号映射到交易内容（默克尔树架构）
    • 收据树：每个交易执行完后，会形成一个收据，该收据中包含一个布隆过滤器，它用 来记录交易的相关信息。

以太坊交易

• 三类交易
  • 转账交易
  • 创建合约交易
  • 执行合约交易
• 转账交易过程
  • A发布交易
  • B同步交易，并转发
  • 矿工打包区块链
    • 如果代码还没有执行完毕 而gas已经耗尽，那么所有状态回滚到代码执行之前
    • 已经消耗的gas不可收回，交易费用 由矿工获得。
    • 如果代码执行完毕后gas还有剩余，那么矿工也只会获得消耗的gas。
  • 广播区块
  • 验证并同步

共识算法

POW

工作量证明

• 先计算出来的随机数的，先广播区块，就使用这个矿工来记账
• 缺点：消耗性能、生成需要大量的时间。
• 场景：时间不敏感（如医院的电子病历）

日蚀攻击：如果一个算力较强的恶意节点控制了一个诚实节点 与系统其他部分的通信路 径，那么该诚实节点就不 会为系统做出持续贡献。

PoS

女巫攻击：一个用户使用了多个虚假身份破坏或以其他方式获得对于网络的控制
PoS利用token所有权来缓解女巫攻击

权益证明：指系统中节点具有的币龄或者币天数，即节点对特定数量 货币的所有权。权益 越大，获得记账权的概率越大。

• 过程
  • 选出出块者
  • 提出区块
  • 验证并更新区块
• 缺陷：
  • 分叉——每个区块共识轮次可 以产生多个符合条件的共识节点，导致产生多个区块，增加了分叉的发生，降低了分叉进行双重支付的难度，影响了区 块链状态的一致性。
  • 算力集中化：有大量未使用代币的节点变得更富有并最终达到垄断地位

DPoS

委托权益证明

节点通过选举选出共识委员会，由共识委员会负责系统记账权，该共识设计的主旨是控制共识委员会的大小从而达到将共识开销达 到一个稳定的状态

拜占庭PBFT

网络资料
可在少数节点作恶(如伪造消息)场景中达成共识

1. 客户端发送请求：客户端向所有节点发送请求消息。
2. 预准备（Pre-Prepare）阶段：主节点（Primary）收到客户端请求后，生成一个唯一标识符（序列号），并将该请求封装成预准备消息（Pre-Prepare Message），同时广播给其他节点。预准备消息包含了请求、视图号（View Number）、序列号等信息。
   • 主节点广播收到的区块给其他结点
3. 准备（Prepare）阶段：每个节点在收到预准备消息后，对其进行验证，并生成准备消息（Prepare Message）。准备消息中包含了视图号、序列号等信息，并广播给其他节点。
   • 每个广播收到的区块给其他结点
4. 提交（Commit）阶段：每个节点在收到足够数量的准备消息后，即达到 2/3 的共识，进入提交阶段。节点生成提交消息（Commit Message），包含视图号、序列号等信息，并广播给其他节点。
   • 收到足够数量的准备消息后，即达到 2/3 的共识。
   • 此步完成后就进行相应的处理（如将区块加入账本或者丢弃，不受到后续的影响），因为共识已经达成
5. 响应（Reply）阶段：每个节点在收到足够数量的提交消息后，即达到 2/3 的共识，将执行请求，并生成响应消息（Reply Message）。节点向客户端发送响应消息，完成请求处理。
6. 客户端确认：客户端在收到足够数量的响应消息后，即达到 2/3 的共识，确认请求已经成功执行。

• 为什么要求达到2/3不是1/2
  • 假设有n个结点（包括f个恶意结点），假设1~f都是恶意结点，那么一共有n-f个正常结点，如果n-f个正常结点即使出现分歧也能最终达成一致，那么有$\frac{n-f}{2}【正常结点投赞成票】>f【恶意结点全投反对票】 \rightarrow f<\frac{n}{3}$
  • 此时系统最多又 $\frac{1}{3}n$个恶意结点，那么就需要正常结点个数为 $\frac{2}{3}n$

为了保证 liveness，当收到 n-f 个节点的消息时，系统需要继续执行下一步（因为可能f个恶意节点故意不发消息，永远也等不到）。
为了保证 safety，任意两个 n-f（这里n-f是来源于上面的liveness） 消息集合的交集必须保证至少有 f+1 个节点（保证前面达成的结果能够传到后面（前后投票或者前后view），前后投票已经各自达成了蓝色是好人的情况（因为大于二分之一了），但是传递消息的时候也需要一个好人），因为这样才能保证至少有一个正常节点。因此 (n-f) + (n-f) – n >= f+1，即n >= 3f+1。

另外一种解释：总的节点个数为N个，拜占庭节点个数为f个，为保证算法活性，每次收集投票只能收集N-f个，但实际收集的投票可能包含f张恶意节点的投票，因此只可以保证收集到N-2f张诚实节点投票。需保证诚实节点投票的个数占诚实节点的大多数，因此N-2f>f，即N>=3f+1。

Hotstuff

网络资料参考
在拜占庭算法中，每个结点需要和其他全部结点互换信息

交互通信成本巨大！

我们不妨从中选择一个leader，我们只需要和leader沟通自己的投票决定即可

三轮投票：

1. 第一轮投票（Round 1）：在第一轮投票中，Leader节点生成提议并将其广播给其他节点。其他节点在收到提议后，会对提议进行投票，表明自己是否接受该提议。此时，节点只能选择投赞同票、反对票或不投票。

2. 第二轮投票（Round 2）：如果提议在第一轮投票中获得足够多的赞同票数，进入第二轮投票。在第二轮投票中，其他节点将发送带有自己签名的投票消息给Leader。Leader在收集到足够多的投票消息后，可以确认该提议为下一个区块。

3. 第三轮投票（Round 3）：第三轮投票主要用于区块的确认和安全性增强。在此轮中，Leader会发送一个确认消息给其他节点，以确保大多数节点已经确认了该提议，并将其添加到本地区块链中。其他节点在收到确认消息后，将验证其有效性，并根据协议规则将区块添加到本地区块链中。

视图变更（View Change）：如果节点在某个轮次内无法收到足够数量的投票消息或确认消息，可能会触发视图变更。在视图变更中，新的节点被选择为新的 Leader，并重新开始新的轮次的共识过程。

leader可以按如下方式担任

• 可信结点
• 轮转算法

为了保证 HotStuff 协议中的 Leader 的有效性，以防止其成为恶意节点，可以采取以下几种措施：

1. 随机选择：HotStuff 中的 Leader 应该通过随机选择而不是固定的方式确定。这样可以防止攻击者预测 Leader 的身份并构造攻击。【不好：因为随机的过于随机了】
2. 轮流成为 Leader：在每个轮次（round）开始之前，可以按照事先约定的顺序轮流选择 Leader，确保每个参与节点都有机会成为 Leader。这样可以实现公平性，减少某个节点长期担任 Leader 的可能性。【不好：因为轮流仍然可以被预测】
3. 多签名验证：Leader 生成的提议需要经过多个节点的验证才能被接受。例如，至少需要其他两个节点对 Leader 提议进行签名验证，以确保 Leader 没有恶意行为。【不好：因为随机的过于随机了】
4. 选举机制：如果发现当前的 Leader 具有恶意行为，可以通过选举机制重新选择 Leader。这可以由其他节点共同参与，基于一定的规则和算法重新选出新的 Leader。

😀优势：将网状共识转为星形共识，减少了网络的通信量

具体参考：Hotstuff相关的改进

chain hotstuff流水线

带流水线的更进一步缩短了时间花销
可以用在时间敏感的区块链上

参考1