Expand description
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));§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: a short cookbook.
- Why this crate?: what belongs here, and why exactness.
- Related crates: what was considered instead, and why not.
- Crate features, Minimum Rust version and Versioning.
Longer documents live in _documentation: how every item is
tested, how each dependency is
vouched for, the project’s
security policy, and the
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 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 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 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 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 1.43.0 | Decimal arithmetic | Deterministic, but with different precision and rounding from Fixed6. Switching would change every propagation result. |
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,
so a release cannot break the API without the
changelog saying so.
Re-exports§
Modules§
- _documentation
- Longer documents: testing, the supply chain, security, and the changelog.
- fixed
- Fixed-point arithmetic scaled by 10^6.
- graph
- Traversals over a directed graph of string labels.
- log
- Append-only Merkle log with inclusion and consistency proofs.
- membership
- Sorted membership tree with inclusion and absence proofs.
- propagate
- Personalized
PageRankover a weighted, labelled graph. - tree
- Recursive Merkle trees over named, nested content – the shape git’s own tree objects use (a directory’s hash commits to its entries’ names and hashes, recursively), generalized past files and directories to any leaf-or-branch structure.
- version
- Whether a tool’s version meets a requirement.