密码学与安全技术

一、Hash 算法

Hash（哈希或散列）算法，又常被称为指纹（fingerprint）或摘要（digest）算法。可以将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash 值）。

可以理解为一种单向有损压缩函数。

# 举例计算一段字符串的 SHA-256 哈希值
echo -n "Hello, world!" | shasum -a 256

# 输出
# a591a6d40bf420404a011733cfb7b190d62c65bf0bcda2f7b097e2b6f3b6a205

哈希函数有很多种，不同的哈希函数有不同的设计目的、应用场景和特性。密码学中，采用的哈希函数名为加密哈希函数，因其有两个重要性质分别为抗哈希碰撞、*隐藏性。

1. 抗哈希碰撞（Collision Resistance）

   给定 x 和 y，且有 x!=y，再给定一个哈希函数 Hash()，可以得到 Hash(x) = Hash(y)，则称为 哈希碰撞。

   之所以会存在哈希碰撞，是因为哈希函数 Hash() 的输出空间是有限的，而输入空间是无限的。 比如 256 位的哈希值，输出空间 2^256，输入空间无限，根据鸽笼原理，终究会有哈希碰撞。

   Collision Resistance 保证，如果有 Hash(x) != Hash(y)，必然可以得到 x != y。（当然，这是理想状态，实际应用中，哈希碰撞基本上难以避免。目前并不存在一个 hash 函数可以从数学上证明具有 Collision Resistance 的性质）

2. 隐藏性（Hiding）
   即无法从散列值逆向推导出原始数据。

谜题友好性（Puzzle Friendly）

事实上，在比特币系统中，还需要第三个性质 Puzzle friendly。该性质要求哈希值计算事先不可预测，仅仅根据输入很难预测出输出。例如：我们需要一个哈希值，存在于某一个范围内，只能通过不停运算查找出来。

• 计算上困难但验证简单：解决某个问题需要大量的计算资源或复杂的推理过程，但一旦解答出来，验证正确性应该是快速且简单的。
• 随机性或不可预测性：谜题的解答无法通过简单的逻辑或预先推测得出，需要参与者进行尝试或使用某种搜索过程。这种不可预测性对防止作弊或预知答案至关重要。
• 逐步逼近的解法：一些谜题友好的系统允许通过不断尝试或逐步逼近的方式最终找到解答。比如在比特币的 PoW 算法中，矿工通过不断变更 nonce 来找到符合要求的哈希值。
• 抗作弊性：谜题友好性还可能包含对抗作弊的设计，确保谜题只能通过正当的计算和逻辑解答，而不是通过捷径或攻击手段快速破解。

扩展：哈希函数类型

二、加解密算法

加解密算法分为对称加密算法和非对称加密算法。

2.1 对称加密算法

对称加密算法，加密和解密使用相同的密钥。

该类算法优点是加解密效率（速度快，空间占用小）和加密强度都很高。

2.2 非对称加密算法

非对称加密算法，加密和解密使用不同的密钥，分别称为公钥（Public Key）和私钥（Private Key）。

公钥和私钥是一对，分别由两个不同的密钥生成算法生成。公钥是公开的，他人可获取的；私钥则是个人持有并且要严密保护，不能被他人获取。

非对称加密算法优点是公私钥分开，无需安全通道来分发密钥。缺点是处理速度（特别是生成密钥和解密过程）往往比较慢，一般比对称加解密算法慢 2~3 个数量级；同时加密强度也往往不如对称加密。

1. 非对称性： 公私钥加密是一种非对称加密方式，意味着加密和解密使用的是不同的密钥。公钥加密的信息只有配对的私钥可以解密，反之，私钥加密的信息可以用公钥解密。
2. 安全性： 私钥是保密的，必须由持有者安全地存储，不能泄露给他人。公钥则可以公开发布，供其他人使用。即使攻击者获得了公钥，也无法解密通过公钥加密的消息，因为解密必须要有私钥。
3. 私钥可推导出公钥，公钥不可推导出私钥。

三、数字签名

在第三方中心化系统中，账户开通依赖于第三方。但去中心化的比特币系统中，申请账户是用户自己来处理的，即自己创建一个公钥-私钥对。

比特币账户创立

• 本地建立公私钥对（asymmetric encryption algorithm 非对称加密）。
• 公钥相当于银行账号；私钥相当于银行卡密码；
• 加密主要用于签名， 比特币交易需要用私钥签名，其他人用公钥验证。
• 在发布交易时，通过自己私钥签名，其他人可以根据公钥进行验证，从而保证该交易由自己发起。也就是说，只有拥有私钥，才能将该账户中的比特币转走。

四、Merkle 树结构

默克尔树（又叫哈希树）是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。

其主要特点为：

• 最下面的叶节点包含存储数据或其哈希值；
• 非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。

进一步地，默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。

默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。

4.1 结构

4.2 作用

• 证明某个集合中存在或不存在某个元素
  通过构建集合的默克尔树，并提供该元素各级兄弟节点中的 Hash 值，可以不暴露集合完整内容而证明某元素存在。
  另外，对于可以进行排序的集合，可以将不存在元素的位置用空值代替，以此构建稀疏默克尔树（Sparse Merkle Tree）。该结构可以证明某个集合中不包括指定元素。

• 快速比较大量数据
  对每组数据排序后构建默克尔树结构，当两个默克尔树根相同时，则意味着所代表的两组数据必然相同。否则，必然不同。
  由于 Hash 计算的过程可以十分快速，预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势。

• 快速定位修改
  以上图为例，基于数据 D0……D3 构造默克尔树，如果 D1 中数据被修改，会影响到 N1，N4 和 Root。

  因此，一旦发现某个节点如 Root 的数值发生变化，沿着 Root --> N4 --> N1，最多通过 O(lgN) 时间即可快速定位到实际发生改变的数据块 D1。

• 零知识证明
  Merkle 树为零知识证明提供了一种 高效的数据组织方式，使得验证者可以在 不知晓数据详情的情况下验证信息的正确性。

零知识证明（Zero-Knowledge Proof）

零知识证明是一种密码学技术，它允许一方（证明者）向另一方（验证者）证明他们知道某个信息，而不需要透露该信息的具体内容。 比如：

1. 证明者（Prover）想要证明 D1 属于该 Merkle 树，但不暴露 D1 本身:

   • 证明者计算 Hash(D1)（即 N1）
   • 证明者提供 Merkle 证明（Merkle Path）:
     • Hash(D0) = N0
     • Hash(N0 + N1) = N4
     • Hash(N2) = N2
     • Hash(N3) = N3
     • Hash(N2 + N3) = N5
     • Hash(N4 + N5) = Root

2. 验证者（Verifier）只需要:

   • 计算 Hash(D1) = N1
   • 结合 N0 计算 Hash(N0 + N1) = N4
   • 结合 N2 + N3 计算 Hash(N4 + N5) = Root
   • 如果计算出的 Root 等于给定的 Merkle Root，则 D1 存在于该 Merkle 树中

五、双花攻击（Double Spending）

双花攻击指的是 同一笔数字货币被用于两次或多次支付，导致交易欺诈或资金凭空增加的问题。
在传统金融系统中，银行或支付系统会防止同一笔资金被重复使用。但在 区块链和加密货币 中，由于数字货币是基于去中心化网络，如何防止双花成为了核心技术挑战之一。

双花问题通常发生在 区块链确认之前，即交易尚未得到全网共识时。主要分为以下几种情况：

5.1 交易替换攻击（Race Attack）

• 攻击方式

  • 攻击者向商家支付一笔比特币（BTC），并在商家确认交易后获得商品或服务
  • 在区块链网络中，攻击者同时发起一笔新的交易，把同样的 BTC 发送到自己的另一个钱包，并提高交易手续费，让矿工更愿意打包新的交易，而不是原先的交易
  • 如果矿工优先打包了攻击者的交易，而不是商家收到的交易，那么商家以为自己收到了 BTC，但实际最终交易被覆盖

• 防御方式

  • 等待多个区块确认（比特币建议 6 个区块确认）
  • 使用 RBF（Replace-By-Fee）检测机制，拒绝未确认交易
  • 使用更快的支付网络（如闪电网络）防止交易替换

5.2 交易回滚攻击（Revert Attack）

5.3 交易吞噬攻击（Transaction Censorship）

5.4 交易分叉攻击（Transaction Forking）

5.5 51% 攻击

• 攻击方式

在 PoW 区块链中，如果一个攻击者掌握了超过 51% 的算力，就可以重组区块链，使得某些交易被回滚。

攻击者可以:

1. 发送一笔交易给商家，获得商品或服务
2. 继续挖矿，但不广播这笔交易，而是创建一条隐藏的分叉链
3. 当自己这条分叉链比主链更长时，广播出来，让整个网络接受这条链，并回滚原来的交易
4. 这样，攻击者可以夺回已支付的币，而商家却无法追回商品或服务

• 防御方式

• 选择安全性更高的区块链（如比特币），因为比特币的总算力巨大，51% 攻击的成本极高

• 等待多个区块确认（比特币通常建议 6 个确认，其他小币种可能需要更多）

• 使用权益证明（PoS）或其他共识机制，降低算力攻击的可能性

Finney Attack（芬尼攻击）

• 攻击方式

  • 由比特币早期开发者 Hal Finney 提出的攻击方式
  • 前提：攻击者自己是矿工，并且成功挖出了一个新区块
  • 攻击过程：
    1. 矿工在新区块中包含了一笔交易（A → 攻击者的钱包），但不广播该区块
    2. 之后，攻击者再发起一笔相同金额的交易（A → 商家钱包）
    3. 商家接受交易并提供商品或服务
    4. 攻击者立即广播之前隐藏的区块，让原交易成为区块链的一部分，而商家那笔交易变成孤立交易（Orphan Transaction），无法被确认

• 防御方式

  • 等待多个区块确认，不要接受 0 确认交易
  • 要求额外的防欺诈机制，如查看交易历史、IP 地址分析等

5.6 自私挖矿（Selfish Mining）

• 攻击方式

  • 类似于 51% 攻击，但算力要求较低
  • 攻击者不广播自己挖出的新区块，而是秘密积累多个区块形成一条隐藏链
  • 当攻击者的隐藏链变得更长时，才公布出来，使得之前的主链区块变成孤块（Orphan Block），并回滚某些交易
  • 这样可以导致一些交易被撤销，从而达到双花的目的

• 防御方式

  • 提高区块链去中心化程度，降低矿工集中度
  • 使用防自私挖矿机制，如 GHOST 协议、Ethereum 的 Uncle Block 奖励机制

参考

• 北京大学肖臻老师《区块链技术与应用》
• 区块链技术指南