🥮 mooncakes.io
    Sign in

    moonappend

    Bounded append-only Merkle log with inclusion and consistency proofs

    merkle
    append-only
    consistency-proof
    rfc9162
    Download zip
    Version
    0.2.0
    License
    Apache-2.0
    Repository
    Last updated
    2 days ago
    Downloads
    32

    #MoonAppend

    MoonAppend 是 MoonBit 的有序追加日志库。它保存记录和 Merkle 节点，支持进程重启后继续追加、历史快照、批量提交，以及包含、一致性和连续区间证明。还提供可合并的 compact range，用少量哈希完成分片构树和状态恢复。

    仓库当前开发版本为 0.2.0，尚未发布。Mooncakes 上的 0.1.0-alpha.1 只有原先的基础内存功能。以下扩展命令需要本仓库源码；正式申报前仍需参赛者核对材料。

    #模块

    导入路径功能后端
    ShiChengxu/moonappend内存日志、批量追加、compact range、三类证明、外部节点读取接口native / wasm-gc / JS
    ShiChengxu/moonappend/wire严格 JSON 快照、证明、十六进制记录交换native / wasm-gc / JS
    ShiChengxu/moonappend/disk磁盘日志、提交检查点、重启恢复、随机读取和全量审计native
    cmd/moonappend上述能力的文件命令行入口native

    树、证明、序列化、提交顺序和恢复判断使用 MoonBit 实现。小型 C 适配层只负责文件偏移读写、同步、原子替换、Unicode 路径和操作系统锁。默认后端改为 native；便携核心也持续在另外两个后端验证。

    #从源码运行

    工具链固定 moon 0.1.20260920、moonc 0.10.14+7d59c7ec9，依赖 moonbitlang/x@0.4.44。native 需要 C 编译环境，Windows 本地使用 MSVC，Linux CI 使用系统 C 工具链。JS 需要 Node.js。

    moon update
moon run cmd/moonappend --target native -- --help
python tools/verify_storage_cli.py

    最后一条命令会在 _build/ 创建独立数据目录，运行 39 次命令行验证，包括进程终止恢复及 7 万、14 万条记录的实际构树。需要 Python 3.12+；详细场景和输入文件见 docs/SCENARIOS.md。

    #三种使用方式

    • 持久化事件日志：分批追加事件，关闭程序后重新打开，保留历史快照并继续写；读取单条记录，或对整个日志做损坏审计。
    • 区间数据回执：导出 [start,end) 的记录和共享证明，接收方只拿这批数据及可信快照即可离线验证内容、顺序和位置。
    • 分片构树与恢复：各任务分别计算相邻区间的 compact range，合并得到总根；保存构树状态后可从新进程继续，无须保留全部叶子。

    这些是可复现的集成示例，不表示已有生产部署。各自的输入、处理步骤、错误案例与输出见 场景说明。

    #核心 API

    在调用方的 moon.pkg 中导入根包并取别名 tree。例如：

    let log = @tree.MemoryLog::new()
    let old = log.append_batch([b"one", b"two"])
    let head = log.append_batch([b"three", b"four"])
    let growth = log.prove_consistency(2UL, 4UL)
    assert_true(@tree.verify_consistency(old, head, growth).is_verified())
    let proof = log.prove_range(1UL, 3UL, 4UL)
    assert_true(@tree.verify_range(head, 1UL, [b"two", b"three"], proof).is_verified())

    上述调用可能抛出错误，应放在可抛出错误的函数或测试中。磁盘调用方导入 ShiChengxu/moonappend/disk，使用 DiskLog::create/open、append_batch、snapshot_at、prove_range、read_entry 和 audit；使用结束必须 close。

    公开 API 由 moon info 生成：根目录、wire/ 和 disk/ 各有 pkg.generated.mbti。外部消费者验证见 tools/verify_consumer.py，不会依赖包内私有字段。

    #存储与信任边界

    磁盘日志写入节点、索引和原始记录，先同步数据，再原子替换检查点。重启时验证检查点和前沿，回收未提交尾部；短于已提交长度的文件直接报错。写入发生 I/O 错误后，该对象禁止继续追加，应关闭重开，并检查最后实际提交的快照。提供六阶段故障注入和实际终止写进程的恢复测试。

    open 只检查恢复所需状态，全历史损坏检查使用 audit。校验和和 Merkle 根不认证来源；调用方要独立保存可信快照、确定记录编码及处理身份认证。库不证明事件真实、没有遗漏或运营方从未分叉。

    持久化支持本地文件系统和单写者；不提供数据库事务、并发线程安全或网络文件系统保证。同步和原子替换的语义仍取决于 OS、文件系统及硬件。进程终止测试不等同于物理断电认证。格式、恢复边界及资源上限见 docs/STORAGE.md。

    #验证与规模记录

    本地已通过 native 98 个测试块，wasm-gc、JS 各 92 个。另有独立 Python/Go 根与 RFC 证明对照、595 个 compact range 和 6,545 个区间证明的 Go 对照、干净消费者及 CLI 验证。测试数量不是覆盖率。

    moon fmt --check
moon check --target native --deny-warn
moon build --target native --deny-warn
moon test --target native --deny-warn
python tools/verify_reference.py --target native --go go
python tools/verify_expanded_reference.py --target native --go go
python tools/verify_consumer.py --target native
python tools/verify_storage_cli.py

    核心命令也分别替换为 wasm-gc 和 js 运行；磁盘与 CLI 仅 native。Go 对照使用仓库保留的锁定源码，离线 -mod=vendor 构建，需要 Go 1.22.7+。CI 使用 Go 1.27.2、Python 3.12、Node.js 22，并保存参考与存储实测附件。

    完整结果和限制见 docs/EXTENDED_VALIDATION.md。原先 0.1 的发布及初验记录保存在 docs/VALIDATION.md。

    #来源与许可

    Apache-2.0。算法依据 RFC 9162；compact ranges 参考 transparency-dev/merkle 的公开设计及其锁定 Go 实现进行对照。pymerkle 的公开文档用于了解可插拔存储设计，未引入其代码或运行时依赖。

    详见 THIRD_PARTY.md、AI_USAGE.md、docs/TOPIC_RECHECK.md。本项目不宣称发明 Merkle 算法，也不宣称生态中绝无同类。

    AppendError

    source
    pub(all) suberror AppendError {
      InvalidHashLength(Int)
      InvalidHex
      InvalidSize
      InvalidIndex
      InvalidLimits
      LeafLimit
      ByteLimit
      InvalidProofLength
      InvalidRange
      NonContiguous
      InvalidCheckpoint
    } derive(Eq, 
    Debug    )

    Invalid construction, bounds or resource request. Proof mismatch is a result.

    AppendError::equal

    source
    fn AppendError::equal(AppendError, AppendError) -> Bool

    AppendError::not_equal

    source
    fn AppendError::not_equal(x : AppendError, y : AppendError) -> Bool

    AppendError::to_repr

    source

    CompactRange

    source
    pub struct CompactRange {
      // private fields
    } derive(Eq, 
    Debug    )

    Canonical maximal aligned perfect subtrees covering exactly [start, end). Hashes are unauthenticated until compared with an independently trusted root.

    CompactRange::append

    source
    fn CompactRange::append(self : CompactRange, leaf : Bytes) -> CompactRange raise AppendError

    CompactRange::append_hash

    source
    fn CompactRange::append_hash(self : CompactRange, leaf : Hash32) -> CompactRange raise AppendError

    CompactRange::checkpoint

    source
    fn CompactRange::checkpoint(self : CompactRange) -> Bytes

    Versioned bounded state, with a corruption checksum (not a signature).

    CompactRange::empty

    source
    fn CompactRange::empty(start? : UInt64) -> CompactRange raise AppendError

    CompactRange::end

    source
    fn CompactRange::end(self : CompactRange) -> UInt64

    CompactRange::equal

    source

    CompactRange::from_leaves

    source
    fn CompactRange::from_leaves(start : UInt64, leaves : Array[Bytes]) -> CompactRange raise AppendError

    CompactRange::merge

    source
    fn CompactRange::merge(self : CompactRange, right : CompactRange) -> CompactRange raise AppendError

    Merge adjacent shards without needing their payloads or internal nodes.

    CompactRange::new

    source
    fn CompactRange::new(start : UInt64, end : UInt64, nodes : Array[Hash32]) -> CompactRange raise AppendError

    CompactRange::nodes

    source
    fn CompactRange::nodes(self : CompactRange) -> Array[Hash32]

    CompactRange::not_equal

    source
    fn CompactRange::not_equal(x : CompactRange, y : CompactRange) -> Bool

    CompactRange::restore

    source
    fn CompactRange::restore(input : Bytes) -> CompactRange raise AppendError

    CompactRange::snapshot

    source
    fn CompactRange::snapshot(self : CompactRange) -> Snapshot raise AppendError

    CompactRange::start

    source
    fn CompactRange::start(self : CompactRange) -> UInt64

    CompactRange::to_repr

    source

    ConsistencyProof

    source
    pub struct ConsistencyProof {
      // private fields
    } derive(Eq, 
    Debug    )

    ConsistencyProof::equal

    source

    ConsistencyProof::new

    source
    fn ConsistencyProof::new(old_size : UInt64, new_size : UInt64, nodes : Array[Hash32]) -> ConsistencyProof raise AppendError

    ConsistencyProof::new_size

    source
    fn ConsistencyProof::new_size(self : ConsistencyProof) -> UInt64

    ConsistencyProof::nodes

    source

    ConsistencyProof::not_equal

    source
    fn ConsistencyProof::not_equal(x : ConsistencyProof, y : ConsistencyProof) -> Bool

    ConsistencyProof::old_size

    source
    fn ConsistencyProof::old_size(self : ConsistencyProof) -> UInt64

    ConsistencyProof::to_repr

    source

    Hash32

    source
    pub struct Hash32 {
      // private fields
    } derive(Eq, 
    Debug    )

    A validated SHA-256 digest. Internal byte storage is not exposed.

    Hash32::bytes

    source
    fn Hash32::bytes(self : Hash32) -> Bytes

    Hash32::equal

    source
    fn Hash32::equal(Hash32, Hash32) -> Bool

    Hash32::from_bytes

    source
    fn Hash32::from_bytes(value : Bytes) -> Hash32 raise AppendError

    Hash32::from_hex

    source
    fn Hash32::from_hex(value : String) -> Hash32 raise AppendError

    Strict lowercase 64-digit hexadecimal encoding.

    Hash32::hex

    source
    fn Hash32::hex(self : Hash32) -> String

    Hash32::not_equal

    source
    fn Hash32::not_equal(x : Hash32, y : Hash32) -> Bool

    Hash32::to_repr

    source

    InclusionProof

    source
    pub struct InclusionProof {
      // private fields
    } derive(Eq, 
    Debug    )

    InclusionProof::equal

    source

    InclusionProof::leaf_index

    source
    fn InclusionProof::leaf_index(self : InclusionProof) -> UInt64

    InclusionProof::new

    source
    fn InclusionProof::new(index : UInt64, size : UInt64, nodes : Array[Hash32]) -> InclusionProof raise AppendError

    Copy the caller's array so later mutation cannot alter this proof.

    InclusionProof::nodes

    source

    InclusionProof::not_equal

    source
    fn InclusionProof::not_equal(x : InclusionProof, y : InclusionProof) -> Bool

    InclusionProof::to_repr

    source

    InclusionProof::tree_size

    source
    fn InclusionProof::tree_size(self : InclusionProof) -> UInt64

    Limits

    source
    pub struct Limits {
      // private fields
    }

    Generation limits may only tighten the absolute alpha caps.

    Limits::max_leaves

    source
    fn Limits::max_leaves(self : Limits) -> Int

    Limits::max_total_bytes

    source
    fn Limits::max_total_bytes(self : Limits) -> Int

    Limits::new

    source
    fn Limits::new(max_leaves? : Int, max_total_bytes? : Int) -> Limits raise AppendError

    MemoryLog

    source
    pub struct MemoryLog {
      // private fields
    }

    In-memory complete-subtree store. Payloads are not retained after hashing.

    MemoryLog::append

    source
    fn MemoryLog::append(self : MemoryLog, leaf : Bytes) -> UInt64 raise AppendError

    Validation precedes mutation: a rejected append leaves the log unchanged.

    MemoryLog::append_batch

    source
    fn MemoryLog::append_batch(self : MemoryLog, leaves : Array[Bytes]) -> Snapshot raise AppendError

    Validate the entire batch before changing the log (allocation failures excluded).

    MemoryLog::input_bytes

    source
    fn MemoryLog::input_bytes(self : MemoryLog) -> Int

    MemoryLog::new

    source
    fn MemoryLog::new(limits? : Limits) -> MemoryLog

    MemoryLog::prove_consistency

    source
    fn MemoryLog::prove_consistency(self : MemoryLog, old_size : UInt64, new_size : UInt64) -> ConsistencyProof raise AppendError

    MemoryLog::prove_inclusion

    source
    fn MemoryLog::prove_inclusion(self : MemoryLog, index : UInt64, size : UInt64) -> InclusionProof raise AppendError

    MemoryLog::prove_range

    source
    fn MemoryLog::prove_range(self : MemoryLog, start : UInt64, end : UInt64, size : UInt64) -> RangeProof raise

    MemoryLog::read_node

    source
    fn MemoryLog::read_node(self : MemoryLog, level : Int, index : UInt64) -> Hash32 raise AppendError

    A completed perfect subtree, addressed by its height and horizontal index.

    MemoryLog::size

    source
    fn MemoryLog::size(self : MemoryLog) -> UInt64

    MemoryLog::snapshot

    source
    fn MemoryLog::snapshot(self : MemoryLog) -> Snapshot

    MemoryLog::snapshot_at

    source
    fn MemoryLog::snapshot_at(self : MemoryLog, size : UInt64) -> Snapshot raise AppendError

    RangeProof

    source
    pub struct RangeProof {
      // private fields
    } derive(Eq, 
    Debug    )

    Custom compact-range multiproof of one nonempty contiguous interval. Nodes are the canonical left gap followed by the canonical right gap.

    RangeProof::end

    source
    fn RangeProof::end(self : RangeProof) -> UInt64

    RangeProof::equal

    source
    fn RangeProof::equal(RangeProof, RangeProof) -> Bool

    RangeProof::new

    source
    fn RangeProof::new(start : UInt64, end : UInt64, size : UInt64, nodes : Array[Hash32]) -> RangeProof raise AppendError

    RangeProof::nodes

    source
    fn RangeProof::nodes(self : RangeProof) -> Array[Hash32]

    RangeProof::not_equal

    source
    fn RangeProof::not_equal(x : RangeProof, y : RangeProof) -> Bool

    RangeProof::start

    source
    fn RangeProof::start(self : RangeProof) -> UInt64

    RangeProof::to_repr

    source

    RangeProof::tree_size

    source
    fn RangeProof::tree_size(self : RangeProof) -> UInt64

    Snapshot

    source
    pub struct Snapshot {
      // private fields
    } derive(Eq, 
    Debug    )

    An unsigned, unauthenticated commitment. Trust is supplied by the caller.

    Snapshot::equal

    source
    fn Snapshot::equal(Snapshot, Snapshot) -> Bool

    Snapshot::new

    source
    fn Snapshot::new(size : UInt64, root : Hash32) -> Snapshot raise AppendError

    Snapshot::not_equal

    source
    fn Snapshot::not_equal(x : Snapshot, y : Snapshot) -> Bool

    Snapshot::root

    source
    fn Snapshot::root(self : Snapshot) -> Hash32

    Snapshot::size

    source
    fn Snapshot::size(self : Snapshot) -> UInt64

    Snapshot::to_repr

    source

    Verification

    source
    pub(all) enum Verification {
      Verified
      Rejected(String)
      NoPriorHistory
    } derive(Eq, 
    Debug    )

    This result does not authenticate the supplied snapshots.

    Verification::code

    source
    fn Verification::code(self : Verification) -> String

    Verification::equal

    source

    Verification::is_verified

    source
    fn Verification::is_verified(self : Verification) -> Bool

    Verification::not_equal

    source
    fn Verification::not_equal(x : Verification, y : Verification) -> Bool

    Verification::to_repr

    source

    MAX_TREE_SIZE

    source
    let MAX_TREE_SIZE : UInt64

    compact_from_reader

    source
    fn compact_from_reader(start : UInt64, end : UInt64, read_node : (Int, UInt64) -> Hash32 raise) -> CompactRange raise

    Read only O(log n) immutable nodes from an application's storage backend.

    consistency_from_reader

    source
    fn consistency_from_reader(old : UInt64, size : UInt64, reader : (Int, UInt64) -> Hash32 raise) -> ConsistencyProof raise

    empty_root

    source
    fn empty_root() -> Hash32

    HASH(empty); distinct from the hash of an empty leaf.

    hash_leaf

    source
    fn hash_leaf(data : Bytes) -> Hash32

    hash_node

    source
    fn hash_node(left : Hash32, right : Hash32) -> Hash32

    inclusion_from_reader

    source
    fn inclusion_from_reader(index : UInt64, size : UInt64, reader : (Int, UInt64) -> Hash32 raise) -> InclusionProof raise

    range_from_reader

    source
    fn range_from_reader(start : UInt64, end : UInt64, size : UInt64, reader : (Int, UInt64) -> Hash32 raise) -> RangeProof raise

    snapshot_from_reader

    source
    fn snapshot_from_reader(size : UInt64, read_node : (Int, UInt64) -> Hash32 raise) -> Snapshot raise

    tree_root

    source
    fn tree_root(leaves : Array[Bytes], limits? : Limits) -> Hash32 raise AppendError

    Bounded reference-style construction. Leaf order is never sorted or padded.

    verify_consistency

    source
    fn verify_consistency(trusted_old : Snapshot, trusted_new : Snapshot, proof : ConsistencyProof) -> Verification

    Verify preservation of an old committed prefix. Snapshots are not signed here.

    verify_inclusion

    source
    fn verify_inclusion(trusted : Snapshot, index : UInt64, leaf : Bytes, proof : InclusionProof) -> Verification

    The expected snapshot and index must come from the caller, not the proof.

    verify_range

    source
    fn verify_range(trusted : Snapshot, start : UInt64, leaves : Array[Bytes], proof : RangeProof) -> Verification

    Binds every supplied record and its order to a caller-selected tree and start.

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io