Lesson 71: 简化工作量证明 — Proof of Work (SHA-256)

练习任务

难度：中

实现简化但完整的 SHA-256 密码学 hash 函数，并用它构建一个 3 区块工作量证明（Proof-of-Work）区块链系统。你需要完成 7 个核心组件：

序号	组件	功能	约行数
1	sha256_init()	用标准 IV 初始化 SHA-256 上下文	~6
2	sha256_update()	喂入数据，满 64 字节时调用压缩函数	~10
3	sha256_final()	消息填充、处理最后一块、输出 32 字节摘要	~25
4	sha256_string()	便捷函数：hash 字符串，返回 64 字符 hex	~10
5	mine_block()	PoW 挖矿：递增 nonce 直到 hash 前缀 "0000"	~18
6	print_block()	打印单个区块的完整信息	~8
7	main()	构建 3 区块链、挖矿、验证链完整性	~45

已提供的骨架（约 150 行，无需修改）：SHA256_IV[8] / SHA256_K[64] 常量、SHA256_CTX 上下文结构体、rotr32() 循环右移、sha256_transform() 64 轮压缩函数（完整实现）、Block 结构体、block_data[]、hash_meets_target()、build_block_input()。

区块数据：Block 0 "Genesis"（prev_hash = 64 个 '0'）、Block 1 "Alice pays Bob 10"、Block 2 "Bob pays Carol 5"。难度目标：SHA-256 hash 前 4 hex 字符为 "0000"。

验证：make && ./pow_chain | diff - expected_output.txt

提示：SHA-256 的核心是 Merkle-Damgård 构造——init/update/final 是"胶水代码"，transform 是"引擎"。填充的关键在于追加 0x80 后判断 block_idx 是否超过 56（放不下 8 字节长度）。挖矿的 nonce 声明为 uint64_t，打印用 %lu。创世区块 prev_hash 用 memset(prev_hash, '0', 64) 填充字符 '0'（不是字节 0x00）。

---

核心知识点

• SHA-256 Merkle-Damgård 结构 — init 设置 IV → update 逐块吸收 → final 填充并输出。压缩函数已提供，学员聚焦"胶水"逻辑
• 消息填充（FIPS 180-4 §5.1.1） — 追加 0x80 → 零填充至剩余 8 字节 → 64 位大端长度字段。block_idx > 56 时需跨块处理
• SHA-256 64 轮压缩概述 — 消息调度 W[0..63] 扩展 + Σ0/Σ1/Ch/Maj 位混合 + Davies-Meyer 状态更新
• 工作量证明（PoW） — 通过暴力枚举 nonce 寻找满足难度目标的 hash。计算不可逆，验证容易
• Hash 指针的双重身份 — 每个 hash 既是区块内容的"指纹"（完整性），又是前一区块的"指针"（链式结构）
• 区块链不可篡改性 — 修改任一区块会改变其 hash，后续所有 prev_hash 失配，需重挖整条链
• 链完整性验证 — 重新计算 hash、检查难度目标、验证 prev_hash 链接。三个条件全部通过才接受链

---

代码框架

pow_chain.c

#include <stdint.h>
#include <stdio.h>
#include <string.h>

/* ─── SHA-256 常量（已提供）───────────────────────────── */
static const uint32_t SHA256_IV[8] = {...};  /* 初始哈希值 */
static const uint32_t SHA256_K[64] = {...};  /* 64 轮常量 */

/* ─── SHA-256 上下文（已提供）─────────────────────────── */
typedef struct {
    uint32_t state[8];  /* 当前哈希状态 */
    uint64_t bitlen;    /* 已处理总位数 */
    uint8_t block[64];  /* 当前 512 位块 */
    int block_idx;      /* 块内累积字节数 */
} SHA256_CTX;

/* ─── 32 位循环右移（已提供）──────────────────────────── */
static uint32_t rotr32(uint32_t x, unsigned int n) {
    return (x >> n) | (x << (32 - n));
}

/* ─── sha256_transform — 64 轮压缩（已提供，约 70 行）──── */
static void sha256_transform(SHA256_CTX *ctx) { ... }

/* ─── TODO 1: sha256_init ───────────────────────────────
 * 将 SHA256_IV 复制到 ctx->state; bitlen=0; block_idx=0 */
#error TODO 1: Implement sha256_init(ctx).

/* ─── TODO 2: sha256_update ─────────────────────────────
 * 逐字节喂入 data，累积到 block; 满 64 字节调用 transform */
#error TODO 2: Implement sha256_update(ctx, data, len).

/* ─── TODO 3: sha256_final ──────────────────────────────
 * 0x80 填充 → 判断跨块 → 零填充 → 64 位大端长度 → transform → 大端输出 digest */
#error TODO 3: Implement sha256_final(ctx, digest).

/* ─── TODO 4: sha256_string ─────────────────────────────
 * init → update → final → sprintf %02x → hex 字符串 */
#error TODO 4: Implement sha256_string(input, hex_out).

/* ─── Block 结构体与辅助函数（已提供）─────────────────── */
typedef struct {
    char prev_hash[65];
    const char *data;
    uint64_t nonce;
    char hash[65];
    uint64_t attempts;
} Block;

const char *block_data[] = {"Genesis", "Alice pays Bob 10", "Bob pays Carol 5"};

static int hash_meets_target(const char hash_hex[65]) {
    return hash_hex[0]=='0' && hash_hex[1]=='0' &&
           hash_hex[2]=='0' && hash_hex[3]=='0';
}

static void build_block_input(const Block *block, uint64_t nonce,
                              char *out, size_t sz) {
    snprintf(out, sz, "%s%s%lu",
             block->prev_hash, block->data, (unsigned long)nonce);
}

/* ─── TODO 5: mine_block — PoW 挖矿 ──┌───────────────────
 * nonce 从 0 递增; build_block_input + sha256_string;
 * hash_meets_target 为真时记录 nonce/hash/attempts 返回 */
#error TODO 5: Implement mine_block(block).

/* ─── TODO 6: print_block — 打印区块 ────────────────────
 * 格式: Block N:\n  prev_hash: ...\n  data: ...\n
 *        nonce: ...\n  hash: ...\n  attempts: ...\n */
#error TODO 6: Implement print_block(index, block).

/* ─── TODO 7: main — 构建 3 区块链并验证 ────────────────
 * 初始化 3 个 Block → 逐个 mine_block → 打印摘要 → 验证 */
#error TODO 7: Implement main().

阅读骨架后，尝试自己填充 7 个 TODO 标记的部分。核心挑战在于：sha256_final 中 block_idx > 56 的跨块逻辑怎么处理？填充中 64 位长度字段为什么必须大端序？mine_block 中 nonce 为什么用 uint64_t 而非 int？链验证时除了重新算 hash 还需要检查什么？

TIP

先不要往下翻看参考解答。在纸上用 data="abc" 手动追踪一遍 SHA-256 填充的全过程——原始数据 3 字节，block 如何填充，长度字段如何写入。

---

深度讲解

1. SHA-256 的 Merkle-Damgård 结构

1.1 为什么需要迭代 hash？

SHA-256 是一种迭代 hash 函数，基于 Merkle-Damgård 构造。它的压缩函数（sha256_transform）只能处理固定 512 位（64 字节）的块，但消息长度可以是任意的。解决方案是：将消息分割成 512 位块，逐块处理，每块的状态输出作为下一块的输入。

┌──────────────────────────────────────────────────────────────┐
│              Merkle-Damgård 结构 (SHA-256)                     │
│                                                                │
│  消息 M ──▶ 填充 ──▶ 分成 512 位块 M₁, M₂, ..., Mₙ             │
│                                                                │
│  ┌───────┐   ┌───────┐   ┌───────┐         ┌───────┐         │
│  │  IV   │   │       │   │       │         │       │         │
│  │ H(0)  │──▶│  C    │──▶│  C    │──▶ ... ─▶│  C    │──▶ H(M)│
│  │256 位 │   │       │   │       │         │       │ 256 位 │
│  └───────┘   └──┬─────┘   └──┬────┘         └──┬────┘         │
│                 │           │                  │              │
│                M₁          M₂                 Mₙ              │
│                                                                │
│  C = 压缩函数 (64 轮, 512 位 → 256 位状态更新)                  │
└──────────────────────────────────────────────────────────────┘

本题中，sha256_init 设置初始状态 H(0)，sha256_update 逐块吸收消息（满 64 字节调用 sha256_transform），sha256_final 填充最后一小块并输出最终 hash。

1.2 三个接口的职责划分

sha256_api_roles.c

/*
 * 三个函数的职责边界清晰——这是理解迭代 hash 的关键
 *
 * init:    设置初始状态 (ctx->state = SHA256_IV)
 * update:  吸收消息（每满 64 字节调用一次 transform）
 * final:   填充 → 最后一次 transform → 输出 digest
 *
 * 严格顺序: init 总是最先调用，update 可调用零次或多次，
 * final 总是在最后调用一次。
 */

/* 典型调用模式 */
SHA256_CTX ctx;
uint8_t digest[32];

sha256_init(&ctx);                        // 初始化
sha256_update(&ctx, data_part1, len1);    // 可分块吸收
sha256_update(&ctx, data_part2, len2);    // 任意次 update
sha256_final(&ctx, digest);               // 最后一块、输出

调用模式的直观理解:

  sha256_init          sha256_update(1)    sha256_update(2)    sha256_final
  ┌──────────┐         ┌───────────┐       ┌───────────┐       ┌───────────┐
  │ ctx←IV   │  ─────▶ │ 块1→Ctx   │ ────▶ │ 块2→Ctx   │ ────▶ │ 填充→Ctx  │
  │ bitlen=0 │         │ bitlen+=  │       │ bitlen+=  │       │ →digest   │
  └──────────┘         └───────────┘       └───────────┘       └────────────┘

sha256_string 是一个便捷封装，将三步组合成一个调用，直接对字符串做 hash 并返回 hex 字符串——这正是 mine_block 中反复调用的接口。

---

2. SHA-256 消息填充（Padding）

2.1 填充规则详解

消息填充是 SHA-256 安全性的关键。FIPS 180-4 §5.1.1 规定填充步骤如下：

┌──────────────────────────────────────────────────────────────┐
│              SHA-256 填充规则（在 sha256_final 中实现）         │
│                                                                │
│  步骤 1: 追加 0x80                                              │
│    block[block_idx++] = 0x80;                                  │
│                                                                │
│  步骤 2: 如果 block_idx > 56（剩余不足 8 字节）:                 │
│    用 0x00 填满到 64 字节 → sha256_transform → block_idx=0      │
│                                                                │
│  步骤 3: 用 0x00 填充到 block_idx == 56                         │
│    (为 8 字节长度字段预留空间)                                   │
│                                                                │
│  步骤 4: 大端序写入 64 位原始消息长度 (total_bits)               │
│    for (i = 7; i >= 0; i--) {                                  │
│        block[56 + i] = (uint8_t)(total_bits & 0xFF);           │
│        total_bits >>= 8;                                       │
│    }                                                            │
│                                                                │
│  步骤 5: sha256_transform → 最后一次压缩                        │
│                                                                │
│  步骤 6: 从 ctx->state 以大端序输出 32 字节 digest               │
└──────────────────────────────────────────────────────────────┘

2.2 填充实例演示

以 "abc"（3 字节, 24 位）为例：

block[0..2]   = 'a','b','c'  (0x61 0x62 0x63)
block[3]      = 0x80           ← 追加 "1" 位后跟零
block[4..55]  = 0x00           ← 52 字节零填充
block[56..63] = 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x18
                ← 大端序: 高位在前, 0x18 = 24 位

恰好一个 64 字节块 → sha256_transform 一次 → 输e → digest

以 "Genesis"（7 字节, 56 位）为例——注意 block_idx 的起点：

block[0..6]   = 'G','e','n','e','s','i','s'  (7 字节)
block[7]      = 0x80           ← block_idx 从 7 变为 8
block[8] > 56? → 8 ≤ 56, 无需跨块处理
block[8..55]  = 0x00           ← 48 字节零填充
block[56..63] = ...大端 56 位...  → 恰好一个 64 字节块

2.3 关键边界：block_idx > 56 的跨块逻辑

padding_boundary.c

/*
 * 为什么是 56？
 * 64 字节块 - 8 字节长度字段 = 56 字节可用空间
 *
 * 追加 0x80 后如果 block_idx > 56，意味着当前块
 * 剩余空间放不下 8 字节长度，必须再申请一个新块。
 */
void sha256_final(SHA256_CTX *ctx, uint8_t digest[32]) {
    uint64_t total_bits = ctx->bitlen;
    int i;

    /* 追加 0x80 */
    ctx->block[ctx->block_idx++] = 0x80;

    /* 关键判断：block_idx 现在可能 > 56 */
    if (ctx->block_idx > 56) {
        while (ctx->block_idx < 64)      /* 填满当前块 */
            ctx->block[ctx->block_idx++] = 0x00;
        sha256_transform(ctx);           /* 压缩当前块 */
        ctx->block_idx = 0;              /* 开新块 */
    }

    /* 零填充至 56 */
    while (ctx->block_idx < 56)
        ctx->block[ctx->block_idx++] = 0x00;

    /* 大端序写入 64 位总位数 */
    uint64_t bits = total_bits;
    for (i = 7; i >= 0; i--) {
        ctx->block[56 + i] = (uint8_t)(bits & 0xFF);
        bits >>= 8;
    }

    sha256_transform(ctx);

    /* 大端序输出 digest */
    for (i = 0; i < 8; i++) {
        digest[i*4 + 0] = (ctx->state[i] >> 24) & 0xFF;
        digest[i*4 + 1] = (ctx->state[i] >> 16) & 0xFF;
        digest[i*4 + 2] = (ctx->state[i] >>  8) & 0xFF;
        digest[i*4 + 3] = (ctx->state[i]      ) & 0xFF;
    }
}

IMPORTANT

长度字段必须用大端序写入——for (i = 7; i >= 0; i--) 从高字节到低字节。如果误用小端序，不同长度消息可能产生不同 hash 值，导致与标准 SHA-256 不一致。

---

3. SHA-256 64 轮压缩概述

本题中 sha256_transform 已完整提供（约 70 行），学员只需理解其调用时机和结构：

┌──────────────────────────────────────────────────────────────┐
│               sha256_transform 工作流程                         │
│                                                                │
│  阶段 1 — 消息调度 (Message Schedule):                          │
│    W[0..15]  = 大端拆解 block[0..63] 为 16 个 uint32_t         │
│    W[16..63] = W[i-16] + σ0(W[i-15]) + W[i-7] + σ1(W[i-2])    │
│    其中 σ0(x) = ROTR(x,7) ^ ROTR(x,18) ^ (x >> 3)             │
│         σ1(x) = ROTR(x,17) ^ ROTR(x,19) ^ (x >> 10)           │
│                                                                │
│  阶段 2 — 64 轮迭代 (i = 0..63):                                │
│    Σ0(a) = ROTR(a,2) ^ ROTR(a,13) ^ ROTR(a,22)                │
│    Σ1(e) = ROTR(e,6) ^ ROTR(e,11) ^ ROTR(e,25)                │
│    Ch(e,f,g)  = (e & f) ^ (~e & g)        ← 选择函数           │
│    Maj(a,b,c) = (a & b) ^ (a & c) ^ (b & c) ← 多数函数         │
│    temp1 = h + Σ1(e) + Ch + K[i] + W[i]                        │
│    temp2 = Σ0(a) + Maj                                          │
│    变量轮转: h=g, g=f, f=e, e=d+temp1, d=c, c=b, b=a,          │
│              a = temp1 + temp2                                  │
│                                                                │
│  阶段 3 — Davies-Meyer 更新:                                    │
│    state[0..7] += 工作变量 a..h                                 │
└──────────────────────────────────────────────────────────────┘

NOTE

SHA-256 的 IV 和 K 常量来自质数的平方根/立方根："Nothing up my sleeve" 原则确保 NSA 未在常量中埋后门。IV 来自前 8 个质数 (2..19) 的平方根小数部分前 32 位；K 来自前 64 个质数 (2..311) 的立方根小数部分前 32 位。

---

4. 工作量证明（Proof-of-Work）

4.1 PoW 的核心原理

PoW 是一种共识机制——矿工通过计算来"证明"自己付出了工作。本题中，矿工需要找到一个 nonce 值，使得 SHA256(prev_hash || data || nonce) 的前 4 个 hex 字符为 "0000"：

┌──────────────────────────────────────────────────────────────┐
│              PoW 挖矿流程                                      │
│                                                                │
│  nonce = 0                                                     │
│  while (1):                                                    │
│      input = prev_hash + data + toString(nonce)                │
│      hash = SHA256(input)                                      │
│      if hash[0..3] == "0000":                                  │
│          return nonce      ← 挖到啦！                          │
│      nonce++              ← 继续尝试                           │
│                                                                │
│  期望尝试次数: 2^16 = 65536 次                                  │
│  (前 4 hex = 16 位, 每个 nonce 有 1/65536 概率满足)             │
└──────────────────────────────────────────────────────────────┘

4.2 mine_block 实现解析

mine_block.c

static uint64_t mine_block(Block *block) {
    uint64_t nonce = 0;
    uint64_t attempts = 0;
    char input[512], hex[65];

    while (1) {
        build_block_input(block, nonce, input, sizeof(input));
        sha256_string(input, hex);
        attempts++;

        if (hash_meets_target(hex)) {
            block->nonce = nonce;
            strcpy(block->hash, hex);
            block->attempts = attempts;
            return attempts;
        }
        nonce++;
    }
}

这个函数展示了 PoW 的两个关键特性：

1. 计算不可逆：没有办法"反推"哪个 nonce 满足目标——必须暴力枚举直到找到。平均需要 1 / 2^(-16) = 65536 次尝试。
2. **验证只需一次 sha256_string 并检查前 4 字符——O(1) vs 挖矿 O(2^16)。

CAUTION

nonce 必须声明为 uint64_t。如果误用 int，挖矿可能溢出（本题 Block 0 的 nonce=47863，Block 2 的 nonce=96168——都在 int 范围内，但语义上这是 64 位的无符号循环计数器）。打印时用 %lu 配合 (unsigned long) 转换。

4.3 SHA-256 字节序：从 block 到 hex 的完整路径

SHA-256 中所有整数运算使用大端序。三个关键转换点：

┌──────────────────────────────────────────────────────────────┐
│              字节序转换位置                                    │
│                                                                │
│  1. block[64] → W[0..15] (在 sha256_transform 中):             │
│     W[i] = (block[p]<<24) | (block[p+1]<<16) |                 │
│             (block[p+2]<<8) | block[p+3]                       │
│     → 大端序: 高字节对齐到 MSB                                  │
│                                                                │
│  2. 填充中的 64 位长度 (在 sha256_final 中):                     │
│     for (i = 7; i >= 0; i--)  ← 从高位到低位写入                 │
│                                                                │
│  3. state → digest (在 sha256_final 中):                        │
│     digest[i*4+0] = state[i] >> 24   (MSB→低索引)              │
│     → digest 数组索引 0 存 MSB，索引 31 存 LSB                  │
│                                                                │
│  4. digest → hex 字符串 (在 sha256_string 中):                  │
│     sprintf(hex + i*2, "%02x", digest[i])                      │
│     → digest[0] 的 hex 在最前面                                 │
└───────────────────────────────────────────────────────────────┘

---

5. 区块链的链式结构与验证

5.1 Hash 指针的双重身份

┌──────────────────────────────────────────────────────────────┐
│              Hash 指针的双重身份                                │
│                                                                │
│  ┌─────────┐    ┌──────────┐    ┌─────────┐                   │
│  │ Block 0 │───▶│ Hash(0)  │───▶│ Block 1 │───▶ ...           │
│  │ 数据     │    │ = H(0)   │    │ 数据     │                   │
│  └─────────┘    └──────────┘    └─────────┘                   │
│                                                                │
│  H(0) 同时是一把双刃剑:                                         │
│    1. 作为"指纹": 唯一标识 Block 0 的内容，任何微调都改 hash     │
│    2. 作为"指针": Block 1 通过 H(0) 引用 Block 0               │
│                                                                │
│  这赋予身份是区块链不可篡改性——改任何历史区块，后续所有 hash 失配     │
└──────────────────────────────────────────────────────────────┘

5.2 链验证的三角法则

验证一条区块链时，需要对每个区块同时检查三个条件：

chain_verification.c

/*
 * 链验证的三角法则——三个条件缺一不可:
 *
 *   (1) Hash 正确性: recomp = SHA256(prev_hash + data + nonce)
 *                    必须等于 stored_hash
 *   (2) 难度目标: hash 前 4 hex == "0000" (即 hash_meets_target)
 *   (3) 链链接: 对 i>0, chain[i].prev_hash == chain[i-1].hash
 *
 *   只验证 (1): 可能接受了不满足难度的区块（伪造的 nonce）
 *   只验证 (2): 可能接受了 hash 和内容不匹配的区块
 *   只验证 (3): 链条看起来连上了，但没检查内容
 *
 *   三者齐备才打印 [VALID]。
 */

/* 验证 Block i */
char recomp_hash[65];
char input[512];
build_block_input(&chain[i], chain[i].nonce, input, sizeof(input));
sha256_string(input, recomp_hash);

int block_valid = 1;
if (strcmp(recomp_hash, chain[i].hash) != 0) block_valid = 0;
if (!hash_meets_target(recomp_hash))         block_valid = 0;
if (i > 0 && strcmp(chain[i].prev_hash, chain[i-1].hash) != 0)
    block_valid = 0;

printf("Block %d: computed=%s  stored=%s  [%s]\n",
       i, recomp_hash, chain[i].hash,
       block_valid ? "VALID" : "INVALID");

WARNING

字符串用 %s（hex 已经是字符串），nonce/attempts 用 %lu。Hash 比较用 strcmp（不是 ==）。注意输出出标签严格为 [VALID]（不是 [OK] 或 [PASS]），否则 diff 比对失败。

5.3 创世区块的特殊处理

创世区块（Block 0）没有前驱，prev_hash 约定为 64 个 '0' 字符：

genesis_block.c

/* 创世区块的 prev_hash */
memset(chain[0].prev_hash, '0', 64);  /* 填充字符 '0' (0x30)，不是字节 0x00 */
chain[0].prev_hash[64] = '\0';        /* 字符串终止符 */

/* 对比错误做法 */
// memset(chain[0].prev_hash, 0, 64);  ← 错误！这会产生空字符串而非 64 个 '0'

---

参考解答

TODO 1-4: SHA-256 完整实现

solution_sha256.c

#include <stdint.h>
#include <stdio.h>
#include <string.h>

/* ─── sha256_init ─────────────────────────────────────── */
static void sha256_init(SHA256_CTX *ctx) {
    for (int i = 0; i < 8; i++)
        ctx->state[i] = SHA256_IV[i];
    ctx->bitlen = 0;
    ctx->block_idx = 0;
}

/* ─── sha256_update ───────────────────────────────────── */
static void sha256_update(SHA256_CTX *ctx, const uint8_t *data, size_t len) {
    for (size_t i = 0; i < len; i++) {
        ctx->block[ctx->block_idx++] = data[i];
        ctx->bitlen += 8;
        if (ctx->block_idx == 64) {
            sha256_transform(ctx);
            ctx->block_idx = 0;
        }
    }
}

/* ─── sha256_final ────────────────────────────────────── */
static void sha256_final(SHA256_CTX *ctx, uint8_t digest[32]) {
    uint64_t total_bits = ctx->bitlen;

    /* 追加 0x80 */
    ctx->block[ctx->block_idx++] = 0x80;

    /* 如果剩余空间不足 8 字节，填满当前块并压缩 */
    if (ctx->block_idx > 56) {
        while (ctx->block_idx < 64)
            ctx->block[ctx->block_idx++] = 0x00;
        sha256_transform(ctx);
        ctx->block_idx = 0;
    }

    /* 零填充至 56 字节（为 8 字节长度预留空间） */
    while (ctx->block_idx < 56)
        ctx->block[ctx->block_idx++] = 0x00;

    /* 大端序写入 64 位总位数 */
    uint64_t bits = total_bits;
    for (int i = 7; i >= 0; i--) {
        ctx->block[56 + i] = (uint8_t)(bits & 0xFF);
        bits >>= 8;
    }

    sha256_transform(ctx);

    /* 大端序输出 digest: state[i] 的 MSB 在 digest 的低索引位置 */
    for (int i = 0; i < 8; i++) {
        digest[i*4 + 0] = (ctx->state[i] >> 24) & 0xFF;
        digest[i*4 + 1] = (ctx->state[i] >> 16) & 0xFF;
        digest[i*4 + 2] = (ctx->state[i] >>  8) & 0xFF;
        digest[i*4 + 3] = (ctx->state[i]      ) & 0xFF;
    }
}

/* ─── sha256_string ──────────────────────────────────── */
static void sha256_string(const char *input, char hex_out[65]) {
    SHA256_CTX ctx;
    uint8_t digest[32];

    sha256_init(&ctx);
    sha256_update(&ctx, (const uint8_t *)input, strlen(input));
    sha256_final(&ctx, digest);

    for (int i = 0; i < 32; i++)
        sprintf(hex_out + i*2, "%02x", digest[i]);
    hex_out[64] = '\0';
}

要点：(1) sha256_final 中追加 0x80 后必须检查 block_idx > 56；(2) 64 位长度用大端序 for (i = 7; i >= 0; i--)；(3) digest 输出也是大端序——state[i] 的 MSB 在前。

TODO 5-6: mine_block 和 print_block

solution_mine_print.c

/* ─── mine_block ──────────────────────────────────────── */
static uint64_t mine_block(Block *block) {
    uint64_t nonce = 0;
    uint64_t attempts = 0;
    char input[512], hex[65];

    while (1) {
        build_block_input(block, nonce, input, sizeof(input));
        sha256_string(input, hex);
        attempts++;

        if (hash_meets_target(hex)) {
            block->nonce = nonce;
            strcpy(block->hash, hex);
            block->attempts = attempts;
            return attempts;
        }
        nonce++;
    }
}

/* ─── print_block ─────────────────────────────────────── */
static void print_block(int index, const Block *block) {
    printf("Block %d:\n", index);
    printf("  prev_hash: %s\n", block->prev_hash);
    printf("  data:      %s\n", block->data);
    printf("  nonce:     %lu\n", (unsigned long)block->nonce);
    printf("  hash:      %s\n", block->hash);
    printf("  attempts:  %lu\n", (unsigned long)block->attempts);
}

要点：(1) mine_block 中 nonce 从 0 开始递增，找到目标后记录并返回；(2) print_block 严格按格式输出 5 行，每行缩进 2 空格；(3) nonce/attempts 用 %lu + (unsigned long) 转换。

TODO 7: main — 构建区块链并验证

solution_main.c

int main(void) {
    Block chain[3];
    uint64_t total_attempts = 0;

    printf("=== Simple Proof-of-Work Blockchain (SHA-256) ===\n");
    printf("Difficulty: hash prefix must be \"0000\"\n\n");

    for (int i = 0; i < 3; i++) {
        /* 设置 prev_hash */
        if (i == 0) {
            memset(chain[i].prev_hash, '0', 64);
            chain[i].prev_hash[64] = '\0';
        } else {
            strcpy(chain[i].prev_hash, chain[i-1].hash);
        }

        chain[i].data = block_data[i];

        printf("Mining block %d: \"%s\"...\n", i, block_data[i]);
        mine_block(&chain[i]);
        total_attempts += chain[i].attempts;

        print_block(i, &chain[i]);
        printf("\n");
    }

    /* 摘要 */
    printf("=== Chain Summary ===\n");
    printf("Total blocks:     3\n");
    printf("Total attempts:   %lu\n", (unsigned long)total_attempts);
    printf("Average attempts: %.1f\n", total_attempts / 3.0);

    /* 验证 */
    printf("\n=== Chain Verification ===\n");
    int valid = 1;
    for (int i = 0; i < 3; i++) {
        char recomp[65], input[512];
        build_block_input(&chain[i], chain[i].nonce, input, sizeof(input));
        sha256_string(input, recomp);

        int ok = (strcmp(recomp, chain[i].hash) == 0) &&
                 hash_meets_target(recomp);
        printf("Block %d: computed=%s  stored=%s  [%s]\n",
               i, recomp, chain[i].hash, ok ? "VALID" : "INVALID");
        if (!ok) valid = 0;

        if (i > 0) {
            int link_ok = (strcmp(chain[i].prev_hash, chain[i-1].hash) == 0);
            printf("  Chain link %d->%d: %s  [%s]\n",
                   i-1, i, chain[i-1].hash, link_ok ? "OK" : "BROKEN");
            if (!link_ok) valid = 0;
        }
    }

    printf("\nChain integrity: %s\n", valid ? "VALID" : "INVALID");
    return 0;
}

要点：(1) 创世区块 prev_hash 用 memset(..., '0', 64) 填充字符 '0'；(2) 验证三条件：重新算 hash 匹配、难度目标满足、链链接正确；(3) [VALID] 和 [OK] 标签严格匹配 expected_output.txt。

---

课堂讨论

1. 如果攻击者想篡改 Block 1 的数据，他需要做什么？为什么区块链越长越安全？
2. 为什么本题提供 sha256_transform 而让学生写 init/update/final？
3. 如果难度目标改为前 8 hex 为 "00000000"，期望尝试次数会变为多少？在普通 CPU 上需要多长时间？
4. SHA-256 消息填充中为什么用 0x80 而不是直接写二进制 1？block_idx > 56 的跨块逻辑为什么不可省略？
5. sha256_string 中 digest 输出用 sprintf(hex_out + i*2, "%02x", digest[i])——为什么按 digest 的顺序（索引 0 到 31）就能得到正确的 hex 字符串？这和字节序有什么关系？

讨论答案

Q1: 篡改 Block 1 需要做什么？

攻击者需要：(1) 修改 Block 1 的 data 字段；(2) 重新为 Block 1 挖矿（找到新 nonce 使 hash 满足 "0000"）；(3) 由于 Block 1 的 hash 变了，Block 2 的 prev_hash 不再匹配，需要重新为 Block 2 挖矿；(4) 如果链更长，需要重新挖所有后续区块。这就是为什么区块链越长越安全——篡改一份的成本随确认数指数增长。在比特币中，建议等 6 个确认（约 60 分钟）后视交易不可逆。

Q2: 为什么提供 transform 而让学生写 init/update/final？

sha256_transform 是 SHA-256 最复杂的部分——消息调度 + 64 轮位混合，实现需要约 70 行精确的位操作代码，一次性写对难度极大。而 init/update/final 是 Merkle-Damgård 结构的"胶水代码"——它们展示了 hash 函数如何接受任意长度输入转化为固定长度输出。这种分工让学生专注于理解迭代 hash 的架构，而不被位操作细节淹没。

Q3: 难度增大后的期望尝试次数

前 8 hex 为零意味着前 32 位为零。成功概率 = 2^(-32) ≈ 1/43 亿。期望需要约 43 亿次 SHA-256 尝试。在普通 CPU 上（~10M hash/s），单个区块约需 4.3×10^9 / 10^7 ≈ 430 秒 ≈ 7 分钟。三个区块需约 21 分钟。这远低于比特币当前难度（约 2^72），但已足够让学生体验 PoW 的计算成本。

Q4: 为什么用 0x80？跨块逻辑为什么不可省略？

0x80 = 10000000 表示在消息末尾追加一个 1 位然后跟若干 0 位——这是"位填充"的字节级实现。所有 SHA-2 变体都使用相同的填充约定。

当 block_idx > 56 时，追加 0x80 后当前块只剩不到 8 字节，放不下 64 位长度字段。如果不做跨块处理（填满当前块并压缩），长度会写错位置，hash 将完全错误。例如原始消息 57 字节时：block_idx=57，加 0x80 后=58，>56 → 必须填满压缩再开新块。这是 sha256_final 最容易遗漏的边界情况。

Q5: digest 输出顺序与字节序的理解

sha256_final 中 digest[i*4+0] = state[i] >> 24（MSB 在前），已正确以大端序写入数组。sprintf("%02x", digest[i]) 从数组索引 0 开始遍历，输出顺序正是 state[0] 的 MSB 字节的 hex 在最前面。这是正确顺序——因为 SHA-256 输出的 hex 字符串传统上按字节顺序从左到右排列。如果在 final 中误写成了小端序（LSB 在前），则 hex 字符串也会错乱。

---

课后练习

1. 验证 SHA-256 的雪崩效应。用 sha256_string 计算 "hello" 和 "Hello"（仅首字母大写差异）的 hash 值。统计两个 64 字符 hex 中有多少位不同。SHA-256 的目标是输出中约一半的位发生翻转。

   知识点提示：将 hex 转为二进制，逐位比较。也可以比较 hex 字符串中不同的 hex 字符数，乘以 4 估算差异位数。雪崩效应是密码学 hash 的核心安全属性。

   参考解答

   ex1_avalanche.c

   #include <stdio.h>
   #include <string.h>
   #include <stdint.h>
   
   /* 复用 pow_chain.c 中的 SHA-256 函数 */
   /* sha256_string("hello", h1) 和 sha256_string("Hello", h2) */
   
   int count_bit_diff(const char *h1, const char *h2) {
       int diff = 0;
       uint8_t digest1[32], digest2[32];
   
       /* hex → bytes */
       for (int i = 0; i < 32; i++) {
           unsigned int a, b;
           sscanf(h1 + i*2, "%02x", &a);
           sscanf(h2 + i*2, "%02x", &b);
           digest1[i] = (uint8_t)a;
           digest2[i] = (uint8_t)b;
       }
   
       for (int i = 0; i < 32; i++) {
           uint8_t xor = digest1[i] ^ digest2[i];
           while (xor) { diff++; xor &= xor - 1; }
       }
       return diff;
   }
   
   int main(void) {
       char h1[65], h2[65];
       sha256_string("hello", h1);
       sha256_string("Hello", h2);
       printf("SHA256(\"hello\"): %s\n", h1);
       printf("SHA256(\"Hello\"): %s\n", h2);
       printf("Bit differences: %d / 256 (expect ~128)\n",
              count_bit_diff(h1, h2));
       return 0;
   }

2. 用 SHA-256 实现简单 MAC（消息认证码）。将密钥 key 和消息 msg 拼接后计整的 SHA-256。验证攻击者不知道 key 时能否伪造有效的 MAC。

   知识点提示：MAC = SHA256(key || msg)。由于 SHA-256 的抗原像性，不知道 key 就无法构造有效的 (msg, MAC) 对。

   参考解答

   ex2_simple_mac.c

   void simple_mac(const char *key, const char *msg, char mac[65]) {
       char input[1024];
       snprintf(input, sizeof(input), "%s%s", key, msg);
       sha256_string(input, mac);
   }
   
   int verify_mac(const char *key, const char *msg, const char *mac) {
       char recomputed[65];
       simple_mac(key, msg, recomputed);
       return strcmp(recomputed, mac) == 0;
   }

3. 修改难度目标。将 hash_meets_target 的条件改为前 6 个 hex 为 "000000"，重新挖矿。记录每个区块的 attempts 并与原难度对比。验证期望尝试次数的预测公式 2^(4 × zeros)。

   知识点提示：期望次数 = 2^(4 × 前导零个数)。6 个零 → 2^24 ≈ 1677 万次。需要更长的计算时间。

   参考解答

   ex3_harder_target.c

   static int hash_meets_target_tough(const char hash_hex[65]) {
       return hash_hex[0]=='0' && hash_hex[1]=='0' &&
              hash_hex[2]=='0' && hash_hex[3]=='0' &&
              hash_hex[4]=='0' && hash_hex[5]=='0';
   }
   /* 预期: 约 2^24 = 16,777,216 次尝试/区块 */

---

参考资料

• NIST. (2015). FIPS 180-4: Secure Hash Standard (SHS). — SHA-256 官方规范，第 5.1.1 节（填充）、第 6.2 节（算法描述）
• Nakamoto, S. (2008). Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf — 比特币白皮书，第 3-4 节描述 PoW
• Antonopoulos, A. M. (2017). Mastering Bitcoin, 2nd Edition. O'Reilly Media. Chapter 8 (Mining), Chapter 10 (Blockchain)
• RFC 6234: US Secure Hash Algorithms — SHA-256 的 C 参考实现
• Bitcoin Core 源码：src/crypto/sha256.h, src/crypto/sha256.cpp — 优化的 SHA-256 生产级实现

"The Times 03/Jan/2009 Chancellor on brink of second bailout for banks." — Satoshi Nakamoto, Bitcoin 创世区块 coinbase