# 算法、资源与信任边界

规范目标：RFC 9162 §2.1，SHA-256 配置；与 RFC 6962 的树算法兼容。
根：空树 `H("")`；叶 `H(0x00 || data)`；节点 `H(0x01 || left || right)`。
非完整树以严格小于当前大小的最大二次幂分割，不对最后一叶复制补齐。

## 状态与复杂度

MemoryLog 每一层只存完整且对齐的子树。追加第 i 个叶子时沿右边界合并完成的节点，
保留已有完整子树供历史根和证明生成复用。历史快照只是不可变的大小与哈希值。

- 已存节点总数小于 `2N`，输入只哈希不保留。追加一次最多 O(log N) 次节点哈希，
  总计 N 次追加只建立线性数量的节点；载荷哈希还需 O(载荷字节数)。
- 当前快照通过前沿归并，O(log N) 节点哈希。
- 历史前缀根只组合被截断前沿，O(log N) 节点哈希。
- 包含/一致性证明有 O(log N) 个节点；当前生成器在递归各层组合范围根，
  保守上界 O(log² N)，不宣称每个生成操作都达到 O(log N)。
- 验证处理 O(log N) 证明节点；包含验证还需哈希输入叶子。

生成器绝对上限 65,536 叶、64 MiB 累计输入；配置只可收紧。
追加失败在状态变更前返回。上限不包含调用方自己的载荷数组、哈希依赖内部临时分配、
GC 和进程其他对象，不是 RSS 上限。当前批量 tree_root 需要额外 O(N) 叶哈希数组。

## API 契约

- 全部外部大小/索引使用 UInt64，限制到 `2^63−1`，检查后才转换生成器内的 Int。
- 证明构造器复制数组，getter 返回独立数组；验证器无日志状态依赖。
- 包含验证单独接收可信快照、预期索引和原始叶字节，并校验与证明元数据一致。
- 一致性验证同时接收两端快照，校验大小绑定、严格消耗路径并检查两个根。
- 空旧树返回 `NoPriorHistory`，不会将平凡空前缀称为有意义的历史验证。
- 同大小：仅空路径且两根相同通过。反向大小拒绝。
- 最大路径 128 节点；每节点为经过构造器校验的 32 字节摘要。
- 资源/构造错误抛出 AppendError；格式良好但不匹配返回 Rejected(code)。

稳定结果码：`VERIFIED`、`NO_PRIOR_HISTORY`、`METADATA_MISMATCH`、
`INDEX_OUT_OF_RANGE`、`LEAF_TOO_LARGE`、`SIZE_REVERSED`、`PATH_LENGTH`、`ROOT_MISMATCH`。
当前 alpha 没有最终 JSON 协议或 native 文件 CLI；examples/interop 的 TSV 仅是验收夹具输出。

## 信任含义

快照未签名，自报根不自证可信。验证成功意味着给定承诺关系与证明一致，
并不保证业务记录真实、没有遗漏、时间准确或未向他人提供不同历史。
只改变相同字节记录的身份标签但不改变哈希输入，不可能靠本库发现。
应用要固定记录编码与顺序、保留可信旧快照，并独立处理签名、存储和并发。

后续严格 JSON 将把大小编码为十进制字符串；初验核心接口不经过 Double。
生成器与验证器使用同一种有序树配置；Bitcoin 奇数叶复制式树、稀疏状态树和自定义哈希树
不能直接混用证明。