lambdasistemi/haskell-mts
GitHub: lambdasistemi/haskell-mts
一个基于 Haskell 的 Merkle Trees 认证键值存储库，提供持久化后端与多类型的默克尔证明。
Stars: 0 | Forks: 0
# MTS - Merkle Tree Store
[](https://github.com/lambdasistemi/haskell-mts/actions/workflows/CI.yaml)
[](https://github.com/lambdasistemi/haskell-mts/actions/workflows/deploy-docs.yaml)
MTS 是一个用 Haskell 实现的 Merkle Trees 庮，提供持久化存储和 Merkle proofs。
## 这是什么
MTS 是一个 Haskell 库，为基于 Merkle tries 的认证 key-value 存储提供了一个共享接口。它内置了两种实现：
- **CSMT** - Compact Sparse Merkle Tree：一种带有路径压缩的二进制 trie，支持 CBOR 编码的 inclusion proof 和 exclusion proof，以及针对前缀分组子树的 completeness proof。
- **MPF** - Merkle Patricia Forest：一种基于十六进制 nibble key 的 16 叉 trie，其 root hash 和 proof-step 编码与 Aiken 参考实现兼容。
这两种实现都公开了相同的、由 mode 索引的 `MerkleTreeStore` GADT。在 `Full` mode 下，每次 mutation 都会更新 trie，并且支持 root hash、inclusion、exclusion 和 completeness proofs。在 `KVOnly` mode 下，mutations 仅追加到 journal 中以实现快速摄入；trie 稍后会通过并行的 journal replay 进行重建。功能对等性由一个共享的 QuickCheck 测试套件来保证：包含 13 个对等性属性和 6 个 journal/replay 属性，每一个都会在两个后端上运行测试。
该仓库还包含一个通用的交换分区回滚库（`mts:rollbacks`），其核心算法已在 Lean 4（`lean/`）中得到正确性证明。此外还包含用于支持浏览器中 demo 的纯写入/验证路径的 WASM 构建版本，以及一个用于 CSMT proofs 的 TypeScript 验证器。
## 架构
```
graph TD
CLI["mts executable
interactive CSMT CLI"] --> CSMT subgraph SUBLIBS["Cabal sublibraries"] MTSI["mts
MTS.Interface + shared properties"] CSMTCORE["mts:csmt-core
types, proof algebra, CBOR"] CSMTW["mts:csmt-write
pure backend, insert/delete, proofs"] CSMT["mts:csmt
RocksDB backend + CLI frontend"] CSMTV["mts:csmt-verify
pure Blake2b verification, WASM-safe"] MPFW["mts:mpf-write
pure backend, Aiken hashing, proofs"] MPF["mts:mpf
RocksDB backend"] ROLL["mts:rollbacks
swap-partition rollback log"] end CSMT --> CSMTW CSMTW --> CSMTCORE CSMTW --> MTSI CSMTW --> CSMTV CSMTV --> CSMTCORE MPF --> MPFW MPFW --> MTSI MPFW --> CSMTV WASM["WASM executables
csmt/mpf write + verify demos"] --> CSMTW WASM --> MPFW WASM --> CSMTV TS["TypeScript verifier
verifiers/typescript"] -. "verifies CSMT proofs" .-> CSMTCORE LEAN["Lean 4 proofs
lean/"] -. "models" .-> ROLL CSMT --> RDB[("RocksDB")] MPF --> RDB ``` ## 安装 ### 发布构件 每个 [GitHub release](https://github.com/lambdasistemi/haskell-mts/releases) 都会提供适用于 `mts` CLI 的 Linux x86_64 构建产物：一个 AppImage、一个 `.deb`、一个 `.rpm` 以及一个 docker 镜像 tarball。 ``` gh release download --repo lambdasistemi/haskell-mts --pattern '*.AppImage' chmod +x mts-v*.AppImage ./mts-v*.AppImage --version ``` 该 docker tarball 可以加载为 `ghcr.io/paolino/mts/mts`： ``` gh release download --repo lambdasistemi/haskell-mts --pattern '*docker*' docker load < mts-v*-docker.tar.gz ``` ### 使用 Nix ``` nix shell nixpkgs#cachix -c cachix use paolino nix shell github:lambdasistemi/haskell-mts --refresh ``` ### 使用 Cabal 需要可用的 Haskell 环境和 RocksDB 开发文件： ``` cabal install ``` ## 快速开始 将 CLI 指向某个数据库目录，并通过管道传入命令： ``` export CSMT_DB_PATH=./mydb mts <<'EOF' i key1 value1 q key1 r EOF ``` ``` AddedKey hJggAAEBAAEAAQEAAQEAAAEAAQABAQEBAAABAAABAQAAAAFYIBCf1UdGHyJjFT9Ie9m6K1UWWQ67U3o15jkbh4ifOE8RgJggAAEBAAEAAQEAAQEAAAEAAQABAQEBAAABAAABAQAAAAE= HZ9W8HqKzlkg3M7y1ivUYtAGm1qJ48zRCU8O3+CCf/A= ``` 直接运行 `mts`（不使用管道传入）即可开启包含相同命令的交互式会话。请查阅 [CLI 手册](https://lambdasistemi.github.io/haskell-mts/manual/) 以获取完整的命令集。 ## 用法 ### 库 `MerkleTreeStore` 由 mode 索引：KV 操作位于 `MtsKV` 记录中（始终可用），树操作位于 `MtsTree` 中（仅在 `Full` mode 下可用）。使用 `csmtMerkleTreeStore` 构建一个基于 CSMT 的存储，这里使用的是内存后端： ``` import CSMT.Backend.Pure (emptyInMemoryDB, pureDatabase, runPure) import CSMT.Hashes (fromKVHashes, hashHashing) import CSMT.Interface (csmtCodecs) import CSMT.MTS (csmtMerkleTreeStore) import Data.IORef (newIORef, readIORef, writeIORef) import MTS.Interface (MtsKV (..), MtsTree (..), mtsKV, mtsTree) main :: IO () main = do ref <- newIORef emptyInMemoryDB let run action = do db <- readIORef ref let (a, db') = runPure db action writeIORef ref db' pure a store <- csmtMerkleTreeStore [] run (pureDatabase csmtCodecs) fromKVHashes hashHashing mtsInsert (mtsKV store) "key" "value" mproof <- mtsMkProof (mtsTree store) "key" mroot <- mtsRootHash (mtsTree store) print (() <$ mproof, () <$ mroot) ``` 第一个参数是 namespace 前缀（根目录使用 `[]`）。对应的 MPF 版本是 `MPF.MTS` 中的 `mpfMerkleTreeStore`，以及 `MPF.Hashes` 中的 `fromHexKVAikenHashes`/`mpfHashing`。如果需要持久化存储，请使用 `CSMT.Backend.RocksDB` 中的 `withRocksDB`（或 `MPF.Backend.RocksDB` 中的 `withMPFRocksDB`）来获取数据库句柄，正如 CLI 前端在 `CSMT.Frontend.CLI.App` 中所做的那样。 当你希望使用与 Aiken 兼容的 proofs 和浏览器 demo 相同的哈希 key 路径时，请使用 `fromHexKVAikenHashes`。`fromHexKVHashes` 则会将原始的 key bytes 直接路由到 nibbles。 ### WASM 产物 该 flake 导出了组合的 WASM bundle 以及各个独立的模块（仅限 x86_64-linux）： ``` nix build .#wasm-artifacts nix build .#csmt-verify-wasm nix build .#csmt-write-wasm nix build .#mpf-verify-wasm nix build .#mpf-write-wasm ``` 它还导出了用于静态 demo bundle 的可运行本地预览命令： ``` PORT=8000 nix run .#csmt-verify-wasm-demo PORT=8001 nix run .#csmt-wasm-write-demo PORT=8002 nix run .#mpf-wasm-write-demo PORT=8003 nix run .#docs ``` ## 文档 完整文档请访问 [lambdasistemi.github.io/haskell-mts](https://lambdasistemi.github.io/haskell-mts/) 常用入口： - [快速入门](https://lambdasistemi.github.io/haskell-mts/installation/) - [CLI 手册](https://lambdasistemi.github.io/haskell-mts/manual/) - [CSMT WASM 验证器 demo](https://lambdasistemi.github.io/haskell-mts/wasm-demo/) - [CSMT WASM 写入 demo](https://lambdasistemi.github.io/haskell-mts/wasm-write-demo/) - [MPF WASM 写入 demo](https://lambdasistemi.github.io/haskell-mts/wasm-mpf-demo/) AI 代理请从 [AGENTS.md](AGENTS.md) 开始阅读。 ## 开发 nix 开发 shell 包含了 GHC、cabal、just、fourmolu、mkdocs 以及 asciinema 工具： ``` nix develop just build # cabal build all (tests + benchmarks) just test # unit tests; just test "pattern" to filter just format # fourmolu + cabal-fmt + nixfmt just lean # build the Lean 4 proofs just serve-docs # mkdocs live preview ``` `just` 列出了所有的配方。CI 会通过该 flake 运行构建、单元测试、benchmark、TypeScript 验证器测试以及格式检查。 ## 许可证 Apache-2.0
interactive CSMT CLI"] --> CSMT subgraph SUBLIBS["Cabal sublibraries"] MTSI["mts
MTS.Interface + shared properties"] CSMTCORE["mts:csmt-core
types, proof algebra, CBOR"] CSMTW["mts:csmt-write
pure backend, insert/delete, proofs"] CSMT["mts:csmt
RocksDB backend + CLI frontend"] CSMTV["mts:csmt-verify
pure Blake2b verification, WASM-safe"] MPFW["mts:mpf-write
pure backend, Aiken hashing, proofs"] MPF["mts:mpf
RocksDB backend"] ROLL["mts:rollbacks
swap-partition rollback log"] end CSMT --> CSMTW CSMTW --> CSMTCORE CSMTW --> MTSI CSMTW --> CSMTV CSMTV --> CSMTCORE MPF --> MPFW MPFW --> MTSI MPFW --> CSMTV WASM["WASM executables
csmt/mpf write + verify demos"] --> CSMTW WASM --> MPFW WASM --> CSMTV TS["TypeScript verifier
verifiers/typescript"] -. "verifies CSMT proofs" .-> CSMTCORE LEAN["Lean 4 proofs
lean/"] -. "models" .-> ROLL CSMT --> RDB[("RocksDB")] MPF --> RDB ``` ## 安装 ### 发布构件 每个 [GitHub release](https://github.com/lambdasistemi/haskell-mts/releases) 都会提供适用于 `mts` CLI 的 Linux x86_64 构建产物：一个 AppImage、一个 `.deb`、一个 `.rpm` 以及一个 docker 镜像 tarball。 ``` gh release download --repo lambdasistemi/haskell-mts --pattern '*.AppImage' chmod +x mts-v*.AppImage ./mts-v*.AppImage --version ``` 该 docker tarball 可以加载为 `ghcr.io/paolino/mts/mts`： ``` gh release download --repo lambdasistemi/haskell-mts --pattern '*docker*' docker load < mts-v*-docker.tar.gz ``` ### 使用 Nix ``` nix shell nixpkgs#cachix -c cachix use paolino nix shell github:lambdasistemi/haskell-mts --refresh ``` ### 使用 Cabal 需要可用的 Haskell 环境和 RocksDB 开发文件： ``` cabal install ``` ## 快速开始 将 CLI 指向某个数据库目录，并通过管道传入命令： ``` export CSMT_DB_PATH=./mydb mts <<'EOF' i key1 value1 q key1 r EOF ``` ``` AddedKey hJggAAEBAAEAAQEAAQEAAAEAAQABAQEBAAABAAABAQAAAAFYIBCf1UdGHyJjFT9Ie9m6K1UWWQ67U3o15jkbh4ifOE8RgJggAAEBAAEAAQEAAQEAAAEAAQABAQEBAAABAAABAQAAAAE= HZ9W8HqKzlkg3M7y1ivUYtAGm1qJ48zRCU8O3+CCf/A= ``` 直接运行 `mts`（不使用管道传入）即可开启包含相同命令的交互式会话。请查阅 [CLI 手册](https://lambdasistemi.github.io/haskell-mts/manual/) 以获取完整的命令集。 ## 用法 ### 库 `MerkleTreeStore` 由 mode 索引：KV 操作位于 `MtsKV` 记录中（始终可用），树操作位于 `MtsTree` 中（仅在 `Full` mode 下可用）。使用 `csmtMerkleTreeStore` 构建一个基于 CSMT 的存储，这里使用的是内存后端： ``` import CSMT.Backend.Pure (emptyInMemoryDB, pureDatabase, runPure) import CSMT.Hashes (fromKVHashes, hashHashing) import CSMT.Interface (csmtCodecs) import CSMT.MTS (csmtMerkleTreeStore) import Data.IORef (newIORef, readIORef, writeIORef) import MTS.Interface (MtsKV (..), MtsTree (..), mtsKV, mtsTree) main :: IO () main = do ref <- newIORef emptyInMemoryDB let run action = do db <- readIORef ref let (a, db') = runPure db action writeIORef ref db' pure a store <- csmtMerkleTreeStore [] run (pureDatabase csmtCodecs) fromKVHashes hashHashing mtsInsert (mtsKV store) "key" "value" mproof <- mtsMkProof (mtsTree store) "key" mroot <- mtsRootHash (mtsTree store) print (() <$ mproof, () <$ mroot) ``` 第一个参数是 namespace 前缀（根目录使用 `[]`）。对应的 MPF 版本是 `MPF.MTS` 中的 `mpfMerkleTreeStore`，以及 `MPF.Hashes` 中的 `fromHexKVAikenHashes`/`mpfHashing`。如果需要持久化存储，请使用 `CSMT.Backend.RocksDB` 中的 `withRocksDB`（或 `MPF.Backend.RocksDB` 中的 `withMPFRocksDB`）来获取数据库句柄，正如 CLI 前端在 `CSMT.Frontend.CLI.App` 中所做的那样。 当你希望使用与 Aiken 兼容的 proofs 和浏览器 demo 相同的哈希 key 路径时，请使用 `fromHexKVAikenHashes`。`fromHexKVHashes` 则会将原始的 key bytes 直接路由到 nibbles。 ### WASM 产物 该 flake 导出了组合的 WASM bundle 以及各个独立的模块（仅限 x86_64-linux）： ``` nix build .#wasm-artifacts nix build .#csmt-verify-wasm nix build .#csmt-write-wasm nix build .#mpf-verify-wasm nix build .#mpf-write-wasm ``` 它还导出了用于静态 demo bundle 的可运行本地预览命令： ``` PORT=8000 nix run .#csmt-verify-wasm-demo PORT=8001 nix run .#csmt-wasm-write-demo PORT=8002 nix run .#mpf-wasm-write-demo PORT=8003 nix run .#docs ``` ## 文档 完整文档请访问 [lambdasistemi.github.io/haskell-mts](https://lambdasistemi.github.io/haskell-mts/) 常用入口： - [快速入门](https://lambdasistemi.github.io/haskell-mts/installation/) - [CLI 手册](https://lambdasistemi.github.io/haskell-mts/manual/) - [CSMT WASM 验证器 demo](https://lambdasistemi.github.io/haskell-mts/wasm-demo/) - [CSMT WASM 写入 demo](https://lambdasistemi.github.io/haskell-mts/wasm-write-demo/) - [MPF WASM 写入 demo](https://lambdasistemi.github.io/haskell-mts/wasm-mpf-demo/) AI 代理请从 [AGENTS.md](AGENTS.md) 开始阅读。 ## 开发 nix 开发 shell 包含了 GHC、cabal、just、fourmolu、mkdocs 以及 asciinema 工具： ``` nix develop just build # cabal build all (tests + benchmarks) just test # unit tests; just test "pattern" to filter just format # fourmolu + cabal-fmt + nixfmt just lean # build the Lean 4 proofs just serve-docs # mkdocs live preview ``` `just` 列出了所有的配方。CI 会通过该 flake 运行构建、单元测试、benchmark、TypeScript 验证器测试以及格式检查。 ## 许可证 Apache-2.0
标签：Haskell, Merkle树, 便携式工具, 区块链, 密码学, 手动系统调用, 数据结构, 键值存储