Skip to main content

Crate publet_algorithms

Crate publet_algorithms 

Source
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

ModuleWhat it does
logAn 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
membershipA sorted set with a root hash: prove a value is present, or provably absent
treeGit-style recursive hashing of named, nested content
fixedFixed6, base-10⁶ fixed-point arithmetic with no conversion from floats
propagatePersonalized 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
graphTraversals 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
versionWhether 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:

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.

Crates that do similar jobs, and why this one takes another approach. Each was checked at the version shown.

CrateWhat it isWhy not here
ct-merkle 0.3.0The RFC 6962 append-only logThe 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.0General Merkle treesNot 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.3Graph types and algorithmsIts PageRank uses floating point, which bit-identical results rule out, and its traversals need the graph built as a structure first.
pathfinding 4.16.0Graph algorithms over successor functionsClose 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.0Decimal arithmeticDeterministic, but with different precision and rounding from Fixed6. Switching would change every propagation result.
semver 1.0.28Cargo’s flavour of semantic versioningUse 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§

pub use fixed::Fixed6;
pub use fixed::SCALE;

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 PageRank over 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.