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