K. HPChain: TFLOP/s, Redefined.¶

在 AI 时代，浮点算力（ FLOPs ）是唯一的硬通货。

注: 本题不计分，仅作为娱乐题目。

题目背景¶

在去年的画板题中，小鸣成功在画板上留下了属于自己浓墨重彩的一笔，并获得了纪念 T 恤。小鸣因此深受鼓舞，决定投身于更具挑战性的区块链技术—— HPChain 。

HPChain 是一个去中心化的算力调度与交易账本。在 HPChain 中，每个参与者都是算力供应商。通过解决基于 SM3d 算法的计算难题，供应商可以证明其设备的实时计算效能，从而获得可交易的算力单位 TFLOPS 。算力提供商通过将自己的算力证明在区块链上，从而可以均衡调度不同地区、不同时间的算力，达到东数西算、南水北调的效果。

题目描述¶

给定一个包含 100 笔交易（ 1 笔 Coinbase 交易 + 99 笔普通交易）的交易池，你的任务是构建一个有效的区块，使得该区块头的 SM3d 哈希值小于或等于给定的目标值。

区块头结构 (80 Bytes)¶

核心逻辑¶

你需要：

1. 构建 Merkle Root ：从给定的 100 笔交易中构建 Merkle 树。
2. Coinbase 交易必须是第一笔交易
3. 其余 99 笔普通交易可以 任意重新排序
4. 所有 100 笔交易都 必须包含 在区块中
5. Merkle 树构建使用 双重 SHA256 算法（ SHA256(SHA256(data)) ）
6. 选择时间戳 ：时间戳必须满足：
7. 大于等于 problem.dat 中指定的基准时间戳
8. 小于等于提交时间 + 2 小时
9. 寻找 Nonce ：不断尝试修改 Nonce 字段，计算：

当满足 $ Result \le Target $ 时，即代表你成功捕捉到了一个有效的算力块。

Merkle Root 构建规则¶

Merkle 树的构建遵循：

1. 对每笔交易计算双重 SHA256 ： txid = SHA256(SHA256(tx_data))
2. 将所有 txid 作为叶子节点
3. 两两配对计算父节点： parent = SHA256(SHA256(left || right))
4. 如果节点数为奇数，最后一个节点与自己配对
5. 重复直到得到根节点（ Merkle Root ）

注意 ：

• 交易哈希（ txid ）计算使用 SHA256d
• Merkle 树内部节点计算使用 SHA256d
• 只有最终的区块头哈希使用 SM3d

输入格式¶

程序从 /tmp/problem.dat 读取二进制格式的问题数据：

[ 4 bytes ] version ( little-endian uint32 )
[ 32 bytes ] previous_block_hash
[ 4 bytes ] nbits ( little-endian uint32 )
[ 4 bytes ] base_timestamp ( little-endian uint32 )
[ 4 bytes ] num_transactions ( little-endian uint32, always 100 )
[ for each transaction: ]
  [ 4 bytes ] tx_length ( little-endian uint32 )
  [ tx_length bytes ] transaction_data

说明 ：

• version: 区块版本号
• previous_block_hash: 前一个区块的哈希值（ 32 字节）
• nbits: 难度目标的压缩表示（ 4 字节）
• base_timestamp: 基准时间戳，你选择的时间戳必须 ≥ 此值
• num_transactions: 交易数量（固定为 100 ）
• 每笔交易以长度前缀的方式存储

nBits 到 Target 的转换¶

nBits 是难度目标的压缩表示，转换公式：

exponent = ( nbits >> 24 ) & 0xFF
mantissa = nbits & 0x00FFFFFF
target = mantissa * 256 ^ ( exponent - 3 )

输出格式¶

输出到标准输出，共五行：

1. 第一行：找到的符合条件的Nonce 值（十六进制， 8 位）
2. 第二行：使用的Merkle Root （十六进制， 64 位）
3. 第三行：使用的Timestamp （十进制）
4. 第四行：计算出的完整Block Hash 值（十六进制， 64 位）
5. 第五行 ：交易顺序（空格分隔的交易索引，第一个必须是 0 表示 coinbase ）

你可以在 Handout 中找到基准程序、示例输入与输出日志。

运行环境与评分¶

• 硬件: Kunpeng 920F (4 核心)
• 编译器: g++ -O3 -fopenmp -pthread -std=c++17 -march=native -o hpchain hpchain.cpp -lssl -lcrypto
• 评分:
• 正确性:
  • 必须包含所有 100 笔交易
  • Coinbase 交易必须在第一位
  • Merkle Root 计算正确
  • 时间戳在有效范围内
  • 区块哈希满足难度目标
• 性能: 寻找有效区块的耗时越短，排名越高
• Judger 会给出 9 个测例，分别有不同的难度值及目标优化时间。

提示与优化方向¶

1. 并行计算: 充分利用pthread或OpenMP ，将 Nonce 空间划分给不同核心
2. Merkle Root 优化:
3. 预先计算所有可能的 Merkle Root （通过重排交易）
4. 或者固定一个交易顺序，专注于 Nonce 搜索
5. SM3d 算法优化:
6. 区块头前 64 字节（ version + prev_hash + merkle_root 前半部分）可以预计算
7. 考虑内联汇编优化关键路径
8. Kunpeng 处理器支持硬件 SM3 加速
9. 时间戳策略:
10. 时间戳的变化会改变区块头，提供额外的搜索空间
11. 可以在 Nonce 空间耗尽时更新时间戳
12. 交易重排序:
13. 虽然可以重排交易来改变 Merkle Root ，但计算成本较高
14. 建议优先优化 Nonce 搜索速度

附件¶

• handout-hpchain