练习 01：Hash 函数直觉训练

目标

完成本练习后，你应该能回答：

1. 改一个字符，hash 变化多大？（雪崩效应）
2. 能不能找到两个不同输入产生相同 hash？（抗碰撞性）
3. 知道 hash 值，能不能反推原文？（单向性）

环境

Python 3.8+，无需额外安装。

代码

将以下代码保存为 01_hash_playground.py 并运行：

"""
Exercise 01: Hash 函数直觉训练
================================
目标：亲手验证 SHA-256 的三个核心性质
运行：python 01_hash_playground.py

完成所有 TODO 后，你应该能回答：
1. 改一个字符，hash 变化多大？（雪崩效应）
2. 能不能找到两个不同输入产生相同 hash？（抗碰撞性）
3. 知道 hash 值，能不能反推原文？（单向性）
"""

import hashlib
import time


def sha256(text: str) -> str:
    """计算 SHA-256 哈希"""
    return hashlib.sha256(text.encode()).hexdigest()


# ============================================================
# Part 1: 雪崩效应
# ============================================================
print("=" * 60)
print("Part 1: 雪崩效应 — 微小输入变化 → 巨大输出变化")
print("=" * 60)

msg_a = "Hello, Blockchain!"
msg_b = "Hello, blockchain!"  # 只改了一个大写字母

hash_a = sha256(msg_a)
hash_b = sha256(msg_b)

print(f"\n输入 A: {msg_a}")
print(f"Hash A: {hash_a}")
print(f"\n输入 B: {msg_b}")
print(f"Hash B: {hash_b}")

# TODO 1: 计算两个 hash 有多少位(bit)不同
# 提示：先把 hex 转成二进制，逐位比较
# 256 位中大约应该有 ~128 位不同（50%）
#
# 你的代码写在这里：
# diff_bits = ???
# print(f"\n256 位中有 {diff_bits} 位不同 ({diff_bits/256*100:.1f}%)")


# ============================================================
# Part 2: 抗碰撞性（简化版）
# ============================================================
print("\n" + "=" * 60)
print("Part 2: 碰撞难度 — 缩短到前 4 字符，暴力碰撞需要多少次？")
print("=" * 60)

target_prefix = sha256("secret message")[:4]  # 只取前 4 个 hex 字符 (16 bit)
print(f"目标前缀: {target_prefix}")

# TODO 2: 暴力搜索——找一个不同的输入，使其 hash 前 4 位和 target_prefix 相同
# 提示：从 0 开始递增数字，计算 sha256(str(i))，检查前缀
# 16 bit 空间，平均约 65536 次能找到
#
# start = time.time()
# for i in range(10_000_000):
#     if sha256(str(i))[:4] == target_prefix:
#         elapsed = time.time() - start
#         print(f"找到碰撞！输入 = {i}, 尝试次数 = {i+1}, 耗时 = {elapsed:.3f}s")
#         print(f"Hash: {sha256(str(i))}")
#         break

# 思考：如果是完整的 256 bit (64 个 hex 字符)，需要多少次？


# ============================================================
# Part 3: Merkle Tree 简易实现
# ============================================================
print("\n" + "=" * 60)
print("Part 3: Merkle Tree — 区块链轻节点验证的数据结构")
print("=" * 60)

transactions = [
    "Alice -> Bob: 1 BTC",
    "Bob -> Charlie: 0.5 BTC",
    "Charlie -> Dave: 0.3 BTC",
    "Dave -> Eve: 0.1 BTC",
]

# TODO 3: 实现一个函数，输入交易列表，返回 Merkle Root
# 步骤：
#   1. 对每笔交易算 hash，得到叶子节点
#   2. 两两配对，将 hash_a + hash_b 拼接后再算 hash，得到父节点
#   3. 如果某层节点数为奇数，最后一个节点复制自己配对
#   4. 重复直到只剩一个节点（Merkle Root）
#
# def merkle_root(txs: list[str]) -> str:
#     ...
#
# root = merkle_root(transactions)
# print(f"Merkle Root: {root}")
#
# 验证：改动任意一笔交易，Merkle Root 应该完全不同
# transactions_tampered = transactions.copy()
# transactions_tampered[2] = "Charlie -> Dave: 999 BTC"
# root_tampered = merkle_root(transactions_tampered)
# print(f"篡改后的 Root: {root_tampered}")
# print(f"Root 相同? {root == root_tampered}")


print("\n" + "=" * 60)
print("完成所有 TODO 后，运行看结果。")
print("然后想一想：为什么 Merkle Tree 能让轻节点只下载")
print("一小部分数据就验证某笔交易是否在区块中？")
print("=" * 60)

运行方式

python 01_hash_playground.py

思考问题

完成所有 TODO 后，用自己的话回答：

1. 为什么 SHA-256 不能用来”加密”密码？密码存储的正确做法是什么？（提示：bcrypt、Argon2）
2. Merkle Tree 怎么让比特币轻节点只下载区块头（80 字节）而不是整个区块（~1MB）就能验证交易？

参考答案

Q1: SHA-256 为什么不适合存密码？ SHA-256 速度太快——现代 GPU 每秒可以算数十亿次，暴力破解短密码只需几秒。密码存储需要故意慢的算法：bcrypt 有内置 cost factor 控制迭代次数，Argon2 还额外消耗内存，两者都能把单次哈希时间拉到几百毫秒，让暴力破解变得不可行。

Q2: Merkle Tree 如何实现轻节点验证？ 轻节点只需下载区块头（包含 Merkle Root）。验证某笔交易时，全节点提供一条从该交易到 Root 的「Merkle Proof」——只需 log₂(N) 个兄弟节点的 hash。轻节点沿路径逐层算 hash，最终结果与区块头的 Merkle Root 比对即可，无需下载整个区块的所有交易。