README
¶
sm3merkle
基于 SM3（GB/T 32905-2016） 的 RFC 6962 Merkle 树，全国密场景可用。
哈希策略与 RFC 6962 逐字对齐，只把 SHA-256 换成 SM3：
| 用途 | 公式 |
|---|---|
| 空树根 | SM3() |
| 叶子节点 | SM3(0x00 ‖ 数据) |
| 内部节点 | SM3(0x01 ‖ 左子哈希 ‖ 右子哈希) |
0x00 / 0x01 是域分离前缀，用来阻断第二原像攻击 —— 没有它，攻击者可以把一个内部节点的哈希当作叶子数据提交，伪造出同样的树根。
为什么不是从零实现
Merkle 证明的下标数学（哪些节点进证明、怎么重算）是这类库最容易写错的部分。本项目不重写它，而是直接复用 transparency-dev/merkle —— Certificate Transparency 的上游实现，经过多年生产验证和 fuzz。
本项目只提供两样东西：
- SM3 哈希层（
hasher.go，约 30 行）—— 实现上游的merkle.LogHasher接口 - 一棵内存树（
tree.go）—— 上游刻意不提供存储，这里补上，并把越界 panic 换成错误返回
上游那个 testonly 包里确实有一棵可用的内存树，但它的名字就是契约：随时可能变、越界直接 panic。所以这部分自己写，底下调用的仍是上游的稳定 API（proof.Inclusion / proof.Consistency / Nodes.Rehash / compact.RangeNodes）。
安装
go get github.com/LR2006-Robot/sm3merkle
快速开始
tree := sm3merkle.New()
for _, entry := range []string{"cert-A", "cert-B", "cert-C", "cert-D"} {
tree.Append([]byte(entry))
}
size, root := tree.Size(), tree.Root() // 对外发布的树根
// 日志方生成证明
pf, err := tree.InclusionProof(2, size)
// 审计方只凭 root / size / pf 校验，不需要整棵树
err = sm3merkle.VerifyInclusionData(2, size, []byte("cert-C"), pf, root)
完整用法见 docs/USAGE.md，含持久化恢复、SM2 签名树根、超出内存的日志三节。
API
哈希层
| 名称 | 说明 |
|---|---|
Hasher / DefaultHasher |
SM3 版 RFC 6962 哈希策略，实现 merkle.LogHasher |
HashSize |
32 |
LeafPrefix / NodePrefix |
0x00 / 0x01 |
树（需要持有全部数据的一方使用）
| 方法 | 说明 |
|---|---|
New() / NewWithHasher(h) |
构造空树 |
Append(data) uint64 |
追加数据，返回叶子下标 |
AppendHash(leafHash) (uint64, error) |
追加已算好的叶子哈希，用于从存储重建；长度不符则报错 |
Size() / Root() |
当前叶子数 / 当前树根 |
RootAt(size) |
历史某个大小时的树根 |
LeafHash(index) |
指定叶子的哈希 |
InclusionProof(index, size) |
包含证明 |
ConsistencyProof(size1, size2) |
一致性证明 |
校验（审计方 / 轻客户端使用，不需要树）
| 函数 | 说明 |
|---|---|
VerifyInclusion(index, size, leafHash, pf, root) |
校验包含证明 |
VerifyInclusionData(index, size, data, pf, root) |
同上，直接收原始数据 |
VerifyConsistency(size1, size2, pf, root1, root2) |
校验仅追加性质 |
测试
go test ./...
验证分四层：
- 树逻辑（对 CT 官方向量） —— 把 SHA-256 哈希器塞进同一棵
Tree，逐一比对 CT 黄金根哈希与叶子哈希（testonly.RootHashes/NodeHashes）。树的形状、进位、证明组装有任何偏差都会暴露，这一层与 SM3 无关。 - 树逻辑（对独立实现） —— 用上游的参考树实现配本包的 SM3 哈希器，在 1..64 全规模上逐项比对根、历史根、全部包含证明、全部一致性证明与叶子哈希，另有 2049 叶子的跨层压力测试。两套树代码彼此独立，这条用例的作用是消除固定向量的循环论证。
- SM3 层 —— 三条哈希公式逐条对照
sm3.Sum手算；另有一条 4 叶子树根完全手工按 RFC 6962 结构算出，不经过Tree的进位逻辑；并确认域分离前缀确实阻断了叶子与内部节点的碰撞。 - 接口契约 —— 1..17 全规模 × 全下标的证明均附反向用例（改数据、翻 bit、换错根必须验不过）；持久化重建一致性；越界返回错误而非 panic；
AppendHash拒绝错误长度且不改动树；切片别名（调用方复用入参缓冲区、或修改Root/LeafHash/证明的返回值，都不得穿透到树内部）。
已知边界
Tree全部节点常驻内存，约2N个哈希，每个连切片头约 56 字节 —— 实测百万叶子约 114MB（约 114 字节/叶子）。更大的日志见 USAGE 最后一节。Tree非并发安全，多 goroutine 访问请自行加锁。AppendHash只校验哈希长度，长度对但内容被改过的哈希无法识别。从存储恢复后请比对树根与上次发布的值。- 树根本身不含签名。生产用法应由 SM2 对
(size, root, 时间戳)签名后发布，否则日志方可以随意换根。见 USAGE。
许可
Documentation
¶
Overview ¶
Package sm3merkle 实现基于 SM3（GB/T 32905-2016）的 RFC 6962 Merkle 树。
哈希策略与 RFC 6962 完全一致，只把 SHA-256 换成 SM3：
空树根 = SM3() 叶子节点 = SM3(0x00 || 数据) 内部节点 = SM3(0x01 || 左子哈希 || 右子哈希)
0x00 / 0x01 前缀是域分离标记，用来阻断第二原像攻击——没有它， 攻击者可以把一个内部节点的哈希冒充成某个叶子的哈希。
证明的生成与校验直接复用 github.com/transparency-dev/merkle （Certificate Transparency 的上游实现），本包只提供 SM3 哈希层和 一棵内存树，不重写任何 Merkle 数学。
Example (Consistency) ¶
一致性证明用来确认日志只做了追加，历史条目没有被悄悄改写。
package main
import (
"fmt"
"github.com/LR2006-Robot/sm3merkle"
)
func main() {
tree := sm3merkle.New()
for _, entry := range []string{"v1", "v2", "v3"} {
tree.Append([]byte(entry))
}
oldSize, oldRoot := tree.Size(), tree.Root()
for _, entry := range []string{"v4", "v5"} {
tree.Append([]byte(entry))
}
newSize, newRoot := tree.Size(), tree.Root()
pf, err := tree.ConsistencyProof(oldSize, newSize)
if err != nil {
panic(err)
}
err = sm3merkle.VerifyConsistency(oldSize, newSize, pf, oldRoot, newRoot)
fmt.Println("仅追加校验:", err)
}
Output: 仅追加校验: <nil>
Example (Inclusion) ¶
日志方追加数据、发布树根，审计方只凭树根和证明验证某条数据确实在日志里。
package main
import (
"fmt"
"github.com/LR2006-Robot/sm3merkle"
)
func main() {
tree := sm3merkle.New()
for _, entry := range []string{"cert-A", "cert-B", "cert-C", "cert-D"} {
tree.Append([]byte(entry))
}
size := tree.Size()
root := tree.Root() // 对外发布的树根（实际场景中由 SM2 签名背书）
// 证明第 2 条数据在日志中。
pf, err := tree.InclusionProof(2, size)
if err != nil {
panic(err)
}
// 审计方手里只有 root、size 和这份证明。
err = sm3merkle.VerifyInclusionData(2, size, []byte("cert-C"), pf, root)
fmt.Println("cert-C 校验:", err)
err = sm3merkle.VerifyInclusionData(2, size, []byte("cert-X"), pf, root)
fmt.Println("伪造数据校验通过:", err == nil)
}
Output: cert-C 校验: <nil> 伪造数据校验通过: false
Index ¶
- Constants
- Variables
- func VerifyConsistency(size1, size2 uint64, pf [][]byte, root1, root2 []byte) error
- func VerifyInclusion(index, size uint64, leafHash []byte, pf [][]byte, root []byte) error
- func VerifyInclusionData(index, size uint64, data []byte, pf [][]byte, root []byte) error
- type Hasher
- type Tree
- func (t *Tree) Append(data []byte) uint64
- func (t *Tree) AppendHash(leafHash []byte) (uint64, error)
- func (t *Tree) ConsistencyProof(size1, size2 uint64) ([][]byte, error)
- func (t *Tree) InclusionProof(index, size uint64) ([][]byte, error)
- func (t *Tree) LeafHash(index uint64) ([]byte, error)
- func (t *Tree) Root() []byte
- func (t *Tree) RootAt(size uint64) ([]byte, error)
- func (t *Tree) Size() uint64
Examples ¶
Constants ¶
const ( LeafPrefix = 0x00 NodePrefix = 0x01 )
RFC 6962 域分离前缀。
const HashSize = sm3.Size
HashSize 是 SM3 摘要长度，32 字节。
Variables ¶
var DefaultHasher = Hasher{}
DefaultHasher 是本包各处默认使用的 SM3 哈希器。
Functions ¶
func VerifyConsistency ¶
VerifyConsistency 校验一致性证明：根为 root1、大小为 size1 的树， 是根为 root2、大小为 size2 的树的前缀。校验通过返回 nil。
func VerifyInclusion ¶
VerifyInclusion 校验包含证明：leafHash 确实是大小为 size 的树中下标 index 的叶子， 且该树的根为 root。校验通过返回 nil。
Types ¶
type Hasher ¶
type Hasher struct{}
Hasher 是 SM3 版本的 RFC 6962 哈希策略，实现 merkle.LogHasher。
func (Hasher) HashChildren ¶
HashChildren 返回内部节点哈希 SM3(0x01 || l || r)。
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree 是一棵仅追加（append-only）的内存 Merkle 树。
零值不可用，请用 New 或 NewWithHasher 构造。Tree 不是并发安全的， 多 goroutine 访问需自行加锁。
ponytail: 全部节点哈希常驻内存，约 2*N 个哈希，每个连 []byte 切片头约 56 字节， 实测百万叶子约 114MB。 日志规模超出内存时，改用 compact.Range 配合外部节点存储（见 docs/USAGE.md “超出内存的日志”一节），本包的 Hasher 可以原样复用。
func NewWithHasher ¶
NewWithHasher 用指定哈希策略构造空树。
正常使用国密场景请用 New。这个入口的存在是为了能塞入 RFC 6962 的 SHA-256 哈希器，拿 CT 官方黄金向量验证树本身的逻辑（见 tree_test.go）。
func (*Tree) AppendHash ¶
AppendHash 追加一个已经算好的叶子哈希，返回它的下标。
用于从持久化存储重建整棵树：把库里存的叶子哈希按下标顺序喂进来即可， 不需要原始数据。
哈希长度必须等于 hasher 的 Size()，否则返回错误且树不被修改。这个检查 拦的是恢复路径上最坏的一类事故——存储里的字节被截断、或误把原始数据当 哈希传入时，树会静默地长出一个错误的根，所有证明随之失效却没有任何报错。 长度对但内容错仍然无法在这里发现，恢复后请比对树根与上次发布的值。
leafHash 会被复制一份，调用方可以安全地复用传入的缓冲区。
func (*Tree) ConsistencyProof ¶
ConsistencyProof 返回「大小 size1 的树是大小 size2 的树的前缀」的一致性证明， 要求 0 <= size1 <= size2 <= Size()。这是仅追加性质的证据：老根没被改写过。
func (*Tree) InclusionProof ¶
InclusionProof 返回「下标 index 的叶子确实在大小为 size 的树里」的包含证明， 要求 0 <= index < size <= Size()。
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
verify
|
|
|
dumpproofs
command
把本包算出的树根与包含证明打印出来，供 verify.py 与独立实现比对。
|
把本包算出的树根与包含证明打印出来，供 verify.py 与独立实现比对。 |