publet_algorithms/lib.rs
1/*!
2The generic algorithms the [publet] tools are built on: an append-only Merkle
3log, sorted-set membership with absence proofs, recursive content trees, exact
4fixed-point arithmetic, deterministic trust propagation, graph traversals, and
5version requirements.
6
7None of them knows anything about publet. Nodes are strings, hashes are
832-byte arrays and weights are [`Fixed6`]; a caller with richer identifiers
9converts at its own boundary. Here is an entry proved to be in a log, by
10someone holding only the log's root:
11
12```
13use publet_algorithms::log::{inclusion_proof, leaf_hash, root, verify_inclusion};
14
15let leaves: Vec<_> = ["first", "second", "third"]
16 .iter()
17 .map(|entry| leaf_hash(entry.as_bytes()))
18 .collect();
19let head = root(&leaves);
20
21let path = inclusion_proof(&leaves, 1);
22assert!(verify_inclusion(&leaves[1], 1, leaves.len() as u64, &path, &head));
23assert!(!verify_inclusion(&leaf_hash(b"forged"), 1, leaves.len() as u64, &path, &head));
24```
25
26[publet]: https://github.com/schryer/publet
27
28# Overview
29
30| Module | What it does |
31|---|---|
32| [`log`] | An append-only Merkle log as in RFC 6962: inclusion proofs, consistency proofs that a later log extends an earlier one, and a power-of-two checkpoint schedule for catching up |
33| [`membership`] | A sorted set with a root hash: prove a value is present, or provably absent |
34| [`tree`] | Git-style recursive hashing of named, nested content |
35| [`fixed`] | [`Fixed6`], base-10⁶ fixed-point arithmetic with no conversion from floats |
36| [`propagate`] | Personalized `PageRank` over a weighted graph, run for an exact number of iterations, with edges that can be limited to subjects and lose weight with age |
37| [`graph`] | Traversals over a neighbour function: reachability, a closure that refuses a cycle, a chain's root, and a topological order that names the cycle when there is one |
38| [`version`] | Whether a tool's version meets a requirement: `^X.Y` as Cargo reads it, `X.Y+`, or a prefix |
39
40Every traversal and accumulation runs in a fixed order, so the same input
41always gives the same output, down to the bit. That is the property publet
42needs most: two people evaluating the same objects must get the same answer.
43
44The rest of this page is:
45
46* [Examples](#examples): a short cookbook.
47* [Why this crate?](#why-this-crate): what belongs here, and why exactness.
48* [Related crates](#related-crates): what was considered instead, and why not.
49* [Crate features](#crate-features), [Minimum Rust version](#minimum-rust-version)
50 and [Versioning](#versioning).
51
52Longer documents live in [`_documentation`]: how every item is
53[tested](crate::_documentation::testing), how each dependency is
54[vouched for](crate::_documentation::supply_chain), the project's
55[security](crate::_documentation::security) policy, and the
56[changelog](crate::_documentation::changelog).
57
58# Examples
59
60## Example: prove something is absent from a set
61
62```
63use publet_algorithms::membership::{Membership, Proof, verify};
64
65let members = Membership::new(["apple", "cherry", "plum"].map(String::from));
66let root = members.root();
67
68let proof = members.prove("banana");
69assert!(matches!(proof, Proof::Absent { .. }));
70// "apple" and "cherry" are adjacent, so nothing lies between them.
71assert!(verify("banana", &proof, &root));
72```
73
74## Example: order work by its dependencies
75
76```
77use std::collections::BTreeMap;
78use publet_algorithms::graph::topological_order;
79
80let deps = BTreeMap::from([("app", vec!["lib", "util"]), ("lib", vec!["util"])]);
81let needs = |id: &str| -> Vec<String> {
82 deps.get(id).into_iter().flatten().map(|d| d.to_string()).collect()
83};
84assert_eq!(topological_order(["app", "lib", "util"], needs).unwrap(), ["util", "lib", "app"]);
85
86// A cycle is reported as the path that closes it.
87let cyclic = |id: &str| vec![if id == "a" { "b" } else { "a" }.to_string()];
88assert_eq!(topological_order(["a"], cyclic).unwrap_err(), ["a", "b", "a"]);
89```
90
91## Example: exact arithmetic
92
93```
94use publet_algorithms::Fixed6;
95
96let third = Fixed6::ONE.ratio(Fixed6::from_integer(3));
97// Truncated, never rounded, so every implementation agrees.
98assert_eq!(third.to_string(), "0.333333");
99```
100
101# Why this crate?
102
103**What belongs here.** An algorithm belongs here when it needs nothing of
104publet's. The crate depends on no other publet crate, and the workspace
105checks that mechanically (`tools/check-deps.py`), so no content identifier,
106signed object or specification type can reach it. Its only dependency is
107`sha2`. The code began inside publet and was extracted after an audit for
108coupling to publet's types; that audit's rule is now the dependency check.
109
110**Why exactness.** Results that decide whether a claim stands must come out
111the same for everyone who computes them. Floating point cannot promise that:
112the result can depend on the platform, the compiler and the order of
113operations. So weights are [`Fixed6`] (integers scaled by 10⁶, truncating),
114propagation runs an exact number of iterations rather than to a tolerance,
115and every map is ordered.
116
117# Related crates
118
119Crates that do similar jobs, and why this one takes another approach. Each
120was checked at the version shown.
121
122| Crate | What it is | Why not here |
123|---|---|---|
124| [`ct-merkle`](https://crates.io/crates/ct-merkle) 0.3.0 | The RFC 6962 append-only log | The same construction as [`log`]. This crate exposes it as plain functions over a slice of leaf hashes, which [`membership`]'s sorted tree is built from, rather than a tree type. |
125| [`rs_merkle`](https://crates.io/crates/rs_merkle) 1.5.0 | General Merkle trees | Not RFC 6962: interior nodes are hashed without the RFC's domain separation, so its root for the same leaves differs and its proofs cannot be checked against a transparency log's. |
126| [`petgraph`](https://crates.io/crates/petgraph) 0.8.3 | Graph types and algorithms | Its `PageRank` uses floating point, which bit-identical results rule out, and its traversals need the graph built as a structure first. |
127| [`pathfinding`](https://crates.io/crates/pathfinding) 4.16.0 | Graph algorithms over successor functions | Close to [`graph`]'s design, but its topological sort reports a cycle as a single node rather than the path, and its visit order is not a documented guarantee. Results here depend on that order. |
128| [`rust_decimal`](https://crates.io/crates/rust_decimal) 1.43.0 | Decimal arithmetic | Deterministic, but with different precision and rounding from [`Fixed6`]. Switching would change every propagation result. |
129| [`semver`](https://crates.io/crates/semver) 1.0.28 | Cargo's flavour of semantic versioning | Use it for release arithmetic on strict `MAJOR.MINOR.PATCH` versions, as pubrel does; this crate keeps no version type of its own. [`version::satisfies`] exists because tool versions such as `0.15` aren't semver. |
130
131# Crate features
132
133None. Everything in the crate is always available.
134
135# Minimum Rust version
136
137This crate requires Rust 1.85 (its `rust-version`), the first release with
138the 2024 edition; CI builds it there. The minimum may rise in a release that
139bumps the minor version, and never in a patch release.
140
141# Versioning
142
143Versions follow Cargo's convention: below 1.0, a breaking change bumps the
144minor version (`0.1.x` to `0.2.0`) and anything compatible bumps the patch.
145Each change to the public API is checked against the last release (its
146`publet-algorithms-v` tag) by [`cargo-semver-checks`](https://crates.io/crates/cargo-semver-checks),
147so a release cannot break the API without the
148[changelog](crate::_documentation::changelog) saying so.
149*/
150
151#![deny(missing_docs)]
152#![warn(missing_debug_implementations)]
153
154pub mod fixed;
155pub mod graph;
156pub mod log;
157pub mod membership;
158pub mod propagate;
159pub mod tree;
160pub mod version;
161
162pub use fixed::{Fixed6, SCALE};
163
164/// Longer documents: testing, the supply chain, security, and the changelog.
165///
166/// These modules hold no code. Each is a document, kept in the repository as
167/// Markdown and rendered here so it is versioned with the crate.
168// Prose documents, one of them generated from release records: clippy's
169// backtick rule for API docs does not fit them.
170#[allow(clippy::doc_markdown)]
171pub mod _documentation {
172 /// How every public item is tested: the examples in its documentation, and
173 /// the tests that say they cover it.
174 #[doc = include_str!("../TESTING.md")]
175 pub mod testing {}
176
177 /// Every crate this one depends on, and how its code is vouched for.
178 #[doc = include_str!("../SUPPLY-CHAIN.md")]
179 pub mod supply_chain {}
180
181 /// How to report a vulnerability, and what is checked before each release.
182 #[doc = include_str!("../SECURITY.md")]
183 pub mod security {}
184
185 /// Every release, newest first, generated from the package publet.
186 #[doc = include_str!("../CHANGELOG.md")]
187 pub mod changelog {}
188}
189
190/// The README's examples, run as tests without being rendered twice.
191#[cfg(doctest)]
192#[doc = include_str!("../README.md")]
193struct ReadmeDoctests;