use std::collections::{BTreeMap, BTreeSet};
use serde::{Deserialize, Serialize};
use serde_json::{json, Value};
use sha2::{Digest, Sha256};
use unicode_normalization::UnicodeNormalization;
pub const MAX_PATH_BYTES: usize = 1_024;
pub const MAX_COMPONENT_BYTES: usize = 255;
pub const CONTENT_TREE_HASH_DOMAIN: &str = "v2/content-tree-node";
pub const ASSET_TREE_HASH_DOMAIN: &str = "v2/asset-tree-node";
#[derive(Debug, thiserror::Error)]
pub enum V2Error {
#[error("invalid portable path: {0}")]
InvalidPath(String),
#[error("invalid v2 tree: {0}")]
InvalidTree(String),
#[error("missing v2 tree object {0}")]
MissingNode(String),
}
pub type V2Result<T> = Result<T, V2Error>;
pub fn sha256_hex(bytes: &[u8]) -> String {
format!("{:x}", Sha256::digest(bytes))
}
pub fn canonical_bytes(value: &Value) -> V2Result<Vec<u8>> {
let mut bytes = serde_json::to_vec(value)
.map_err(|error| V2Error::InvalidTree(format!("canonical JSON failed: {error}")))?;
bytes.push(b'\n');
Ok(bytes)
}
pub fn domain_hash_bytes(domain: &str, bytes: &[u8]) -> V2Result<String> {
if domain.is_empty()
|| domain.len() > 128
|| !domain.bytes().enumerate().all(|(index, byte)| {
byte.is_ascii_lowercase()
|| byte.is_ascii_digit()
|| (index > 0 && matches!(byte, b'.' | b'_' | b'/' | b'-'))
})
{
return Err(V2Error::InvalidTree("invalid hash domain".to_string()));
}
let mut hasher = Sha256::new();
hasher.update(b"link.md\0");
hasher.update(domain.as_bytes());
hasher.update(b"\0");
hasher.update(bytes);
Ok(format!("{:x}", hasher.finalize()))
}
pub fn domain_hash(domain: &str, value: &Value) -> V2Result<String> {
if domain.is_empty()
|| domain.len() > 128
|| !domain.bytes().enumerate().all(|(index, byte)| {
byte.is_ascii_lowercase()
|| byte.is_ascii_digit()
|| (index > 0 && matches!(byte, b'.' | b'_' | b'/' | b'-'))
})
{
return Err(V2Error::InvalidTree("invalid hash domain".to_string()));
}
let mut hasher = Sha256::new();
hasher.update(b"link.md\0");
hasher.update(domain.as_bytes());
hasher.update(b"\0");
hasher.update(canonical_bytes(value)?);
Ok(format!("{:x}", hasher.finalize()))
}
fn portable_alias(component: &str) -> String {
component
.nfc()
.flat_map(char::to_lowercase)
.collect::<String>()
.nfc()
.collect()
}
fn windows_device(component: &str) -> bool {
let stem = component
.split('.')
.next()
.unwrap_or(component)
.to_ascii_lowercase();
matches!(stem.as_str(), "con" | "prn" | "aux" | "nul")
|| stem
.strip_prefix("com")
.or_else(|| stem.strip_prefix("lpt"))
.is_some_and(|digit| digit.len() == 1 && matches!(digit.as_bytes()[0], b'1'..=b'9'))
}
pub fn normalize_path(input: &str) -> V2Result<String> {
if input.is_empty()
|| input.len() > MAX_PATH_BYTES
|| input.starts_with('/')
|| input.contains(['\\', ':', '\0'])
|| input.nfc().collect::<String>() != input
{
return Err(V2Error::InvalidPath(input.to_string()));
}
for component in input.split('/') {
let alias = portable_alias(component);
if component.is_empty()
|| matches!(component, "." | "..")
|| component.ends_with(['.', ' '])
|| component.bytes().any(|byte| byte < 0x20 || byte == 0x7f)
|| component.len() > MAX_COMPONENT_BYTES
|| alias.len() > MAX_COMPONENT_BYTES
|| windows_device(component)
{
return Err(V2Error::InvalidPath(input.to_string()));
}
}
Ok(input.to_string())
}
pub fn validate_path_set<'a>(paths: impl IntoIterator<Item = &'a str>) -> V2Result<Vec<String>> {
let normalized = paths
.into_iter()
.map(normalize_path)
.collect::<V2Result<Vec<_>>>()?;
let mut exact = BTreeSet::new();
let mut aliases = BTreeMap::new();
for path in &normalized {
if !exact.insert(path.clone()) {
return Err(V2Error::InvalidPath(format!("duplicate path: {path}")));
}
let alias = path
.split('/')
.map(portable_alias)
.collect::<Vec<_>>()
.join("/");
if let Some(prior) = aliases.insert(alias, path.clone()) {
if prior != *path {
return Err(V2Error::InvalidPath(format!(
"portable alias collision: {prior} and {path}"
)));
}
}
}
for path in &normalized {
let components = path.split('/').collect::<Vec<_>>();
for index in 1..components.len() {
let prefix = components[..index].join("/");
if exact.contains(&prefix) {
return Err(V2Error::InvalidPath(format!(
"file/directory prefix collision: {prefix}"
)));
}
}
}
Ok(normalized)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Deserialize, Serialize)]
#[serde(rename_all = "lowercase")]
pub enum EntryKind {
Blob,
Tree,
}
#[derive(Debug, Clone, PartialEq, Eq, Deserialize, Serialize)]
pub struct TreeEntry {
pub name: String,
pub kind: EntryKind,
pub child_hash: String,
pub bytes: Option<u64>,
pub nonce: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum HamtNode {
Leaf {
route: String,
entry: TreeEntry,
},
Branch {
depth: usize,
children: Vec<(u8, String)>,
},
Compressed {
depth: usize,
run: String,
child: String,
},
}
fn node_value(node: &HamtNode) -> Value {
match node {
HamtNode::Leaf { route, entry } => json!({
"entry": {
"bytes": entry.bytes,
"child_hash": entry.child_hash,
"kind": entry.kind,
"name": entry.name,
"nonce": entry.nonce,
},
"kind": "leaf",
"route": route,
"v": 1,
}),
HamtNode::Branch { depth, children } => json!({
"children": children,
"depth": depth,
"kind": "branch",
"v": 1,
}),
HamtNode::Compressed { depth, run, child } => json!({
"child": child,
"depth": depth,
"kind": "compressed",
"run": run,
"v": 1,
}),
}
}
pub fn encode_node(node: &HamtNode) -> V2Result<Vec<u8>> {
canonical_bytes(&node_value(node))
}
pub fn hash_node(node: &HamtNode) -> V2Result<String> {
hash_node_with_domain(node, CONTENT_TREE_HASH_DOMAIN)
}
pub fn hash_node_with_domain(node: &HamtNode, domain: &str) -> V2Result<String> {
domain_hash(domain, &node_value(node))
}
pub fn decode_node(bytes: &[u8]) -> V2Result<HamtNode> {
let value: Value = serde_json::from_slice(bytes)
.map_err(|error| V2Error::InvalidTree(format!("node JSON failed: {error}")))?;
let object = value
.as_object()
.ok_or_else(|| V2Error::InvalidTree("node is not an object".to_string()))?;
if object.get("v").and_then(Value::as_u64) != Some(1) {
return Err(V2Error::InvalidTree("unsupported node version".to_string()));
}
let node = match object.get("kind").and_then(Value::as_str) {
Some("leaf") => {
let route = object
.get("route")
.and_then(Value::as_str)
.ok_or_else(|| V2Error::InvalidTree("leaf route missing".to_string()))?;
let entry_value = object
.get("entry")
.ok_or_else(|| V2Error::InvalidTree("leaf entry missing".to_string()))?;
let entry: TreeEntry = serde_json::from_value(entry_value.clone())
.map_err(|error| V2Error::InvalidTree(format!("leaf entry failed: {error}")))?;
HamtNode::Leaf {
route: route.to_string(),
entry,
}
}
Some("branch") => {
let depth = object
.get("depth")
.and_then(Value::as_u64)
.and_then(|value| usize::try_from(value).ok())
.ok_or_else(|| V2Error::InvalidTree("branch depth missing".to_string()))?;
let children = serde_json::from_value(
object
.get("children")
.cloned()
.ok_or_else(|| V2Error::InvalidTree("branch children missing".to_string()))?,
)
.map_err(|error| V2Error::InvalidTree(format!("branch children failed: {error}")))?;
HamtNode::Branch { depth, children }
}
Some("compressed") => HamtNode::Compressed {
depth: object
.get("depth")
.and_then(Value::as_u64)
.and_then(|value| usize::try_from(value).ok())
.ok_or_else(|| V2Error::InvalidTree("compressed depth missing".to_string()))?,
run: object
.get("run")
.and_then(Value::as_str)
.ok_or_else(|| V2Error::InvalidTree("compressed run missing".to_string()))?
.to_string(),
child: object
.get("child")
.and_then(Value::as_str)
.ok_or_else(|| V2Error::InvalidTree("compressed child missing".to_string()))?
.to_string(),
},
_ => return Err(V2Error::InvalidTree("unknown node kind".to_string())),
};
if encode_node(&node)? != bytes {
return Err(V2Error::InvalidTree("non-canonical node".to_string()));
}
Ok(node)
}
fn put_node(nodes: &mut BTreeMap<String, Vec<u8>>, node: HamtNode) -> V2Result<String> {
let hash = hash_node(&node)?;
let bytes = encode_node(&node)?;
if let Some(prior) = nodes.get(&hash) {
if prior != &bytes {
return Err(V2Error::InvalidTree("node hash collision".to_string()));
}
}
nodes.insert(hash.clone(), bytes);
Ok(hash)
}
fn common_run(routes: &[String], depth: usize) -> String {
if routes.len() == 1 {
return routes[0][depth..].to_string();
}
let mut end = depth;
while end < 64 {
let byte = routes[0].as_bytes()[end];
if routes.iter().any(|route| route.as_bytes()[end] != byte) {
break;
}
end += 1;
}
routes[0][depth..end].to_string()
}
fn build_node(
leaves: &[(String, TreeEntry)],
depth: usize,
nodes: &mut BTreeMap<String, Vec<u8>>,
) -> V2Result<String> {
if leaves.is_empty() || depth > 64 {
return Err(V2Error::InvalidTree(
"invalid HAMT build bounds".to_string(),
));
}
if leaves.len() == 1 {
let leaf_hash = put_node(
nodes,
HamtNode::Leaf {
route: leaves[0].0.clone(),
entry: leaves[0].1.clone(),
},
)?;
let run = leaves[0].0[depth..].to_string();
return if run.is_empty() {
Ok(leaf_hash)
} else {
put_node(
nodes,
HamtNode::Compressed {
depth,
run,
child: leaf_hash,
},
)
};
}
let run = common_run(
&leaves
.iter()
.map(|(route, _)| route.clone())
.collect::<Vec<_>>(),
depth,
);
if !run.is_empty() {
let child = build_node(leaves, depth + run.len(), nodes)?;
return put_node(nodes, HamtNode::Compressed { depth, run, child });
}
if depth >= 64 {
return Err(V2Error::InvalidTree(
"distinct names have a SHA-256 route collision".to_string(),
));
}
let mut groups: BTreeMap<u8, Vec<(String, TreeEntry)>> = BTreeMap::new();
for leaf in leaves {
let slot = u8::from_str_radix(&leaf.0[depth..=depth], 16)
.map_err(|_| V2Error::InvalidTree("invalid route nibble".to_string()))?;
groups.entry(slot).or_default().push(leaf.clone());
}
let mut children = Vec::new();
for (slot, group) in groups {
children.push((slot, build_node(&group, depth + 1, nodes)?));
}
put_node(nodes, HamtNode::Branch { depth, children })
}
pub fn build_hamt(
entries: &[TreeEntry],
nodes: &mut BTreeMap<String, Vec<u8>>,
) -> V2Result<Option<String>> {
if entries.is_empty() {
return Ok(None);
}
let mut names = BTreeSet::new();
let mut routes = BTreeSet::new();
let mut leaves = Vec::new();
for entry in entries {
if entry.name.nfc().collect::<String>() != entry.name
|| entry.nonce.len() != 32
|| !entry
.nonce
.bytes()
.all(|byte| byte.is_ascii_hexdigit() && !byte.is_ascii_uppercase())
{
return Err(V2Error::InvalidTree("invalid leaf state".to_string()));
}
if !names.insert(entry.name.clone()) {
return Err(V2Error::InvalidTree("duplicate child name".to_string()));
}
let route = sha256_hex(entry.name.as_bytes());
if !routes.insert(route.clone()) {
return Err(V2Error::InvalidTree(
"child-name route collision".to_string(),
));
}
leaves.push((route, entry.clone()));
}
leaves.sort_by(|left, right| left.0.cmp(&right.0));
build_node(&leaves, 0, nodes).map(Some)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ContentFile {
pub path: String,
pub blob_hash: String,
pub bytes: u64,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EntryState {
pub path: String,
pub entry: TreeEntry,
}
#[derive(Debug, Clone)]
pub struct BuiltTree {
pub root: Option<String>,
pub nodes: BTreeMap<String, Vec<u8>>,
pub entries: BTreeMap<String, EntryState>,
pub files: BTreeMap<String, ContentFile>,
}
#[derive(Default)]
struct Directory {
files: BTreeMap<String, ContentFile>,
dirs: BTreeMap<String, Directory>,
}
fn next_nonce(factory: &mut impl FnMut() -> String, prior: Option<&str>) -> V2Result<String> {
for _ in 0..8 {
let nonce = factory();
if nonce.len() != 32 || !nonce.bytes().all(|byte| byte.is_ascii_hexdigit()) {
return Err(V2Error::InvalidTree(
"nonce factory returned invalid bytes".to_string(),
));
}
if Some(nonce.as_str()) != prior {
return Ok(nonce);
}
}
Err(V2Error::InvalidTree(
"nonce factory repeated the prior nonce".to_string(),
))
}
pub fn build_content_tree(
input: &[ContentFile],
prior: Option<&BuiltTree>,
nonce_factory: &mut impl FnMut() -> String,
) -> V2Result<BuiltTree> {
let paths = validate_path_set(input.iter().map(|file| file.path.as_str()))?;
let mut directory = Directory::default();
let mut files = BTreeMap::new();
for (index, file) in input.iter().enumerate() {
if file.blob_hash.len() != 64
|| !file.blob_hash.bytes().all(|byte| byte.is_ascii_hexdigit())
{
return Err(V2Error::InvalidTree("invalid blob hash".to_string()));
}
let normalized = ContentFile {
path: paths[index].clone(),
blob_hash: file.blob_hash.clone(),
bytes: file.bytes,
};
files.insert(normalized.path.clone(), normalized.clone());
let components = normalized.path.split('/').collect::<Vec<_>>();
let mut current = &mut directory;
for component in &components[..components.len() - 1] {
current = current.dirs.entry((*component).to_string()).or_default();
}
current.files.insert(
components.last().expect("path has a component").to_string(),
normalized,
);
}
fn recurse(
directory: &Directory,
prefix: &str,
prior: Option<&BuiltTree>,
nonce_factory: &mut impl FnMut() -> String,
nodes: &mut BTreeMap<String, Vec<u8>>,
states: &mut BTreeMap<String, EntryState>,
) -> V2Result<Option<String>> {
let mut entries = Vec::new();
for (name, child) in &directory.dirs {
let path = if prefix.is_empty() {
name.clone()
} else {
format!("{prefix}/{name}")
};
let Some(child_hash) = recurse(child, &path, prior, nonce_factory, nodes, states)?
else {
continue;
};
let old = prior.and_then(|tree| tree.entries.get(&path));
let unchanged = old.is_some_and(|state| {
state.entry.name == *name
&& state.entry.kind == EntryKind::Tree
&& state.entry.child_hash == child_hash
&& state.entry.bytes.is_none()
});
let nonce = if unchanged {
old.expect("checked").entry.nonce.clone()
} else {
next_nonce(nonce_factory, old.map(|state| state.entry.nonce.as_str()))?
};
let entry = TreeEntry {
name: name.clone(),
kind: EntryKind::Tree,
child_hash,
bytes: None,
nonce,
};
states.insert(
path.clone(),
EntryState {
path,
entry: entry.clone(),
},
);
entries.push(entry);
}
for (name, file) in &directory.files {
let path = if prefix.is_empty() {
name.clone()
} else {
format!("{prefix}/{name}")
};
let old = prior.and_then(|tree| tree.entries.get(&path));
let unchanged = old.is_some_and(|state| {
state.entry.name == *name
&& state.entry.kind == EntryKind::Blob
&& state.entry.child_hash == file.blob_hash
&& state.entry.bytes == Some(file.bytes)
});
let nonce = if unchanged {
old.expect("checked").entry.nonce.clone()
} else {
next_nonce(nonce_factory, old.map(|state| state.entry.nonce.as_str()))?
};
let entry = TreeEntry {
name: name.clone(),
kind: EntryKind::Blob,
child_hash: file.blob_hash.clone(),
bytes: Some(file.bytes),
nonce,
};
states.insert(
path.clone(),
EntryState {
path,
entry: entry.clone(),
},
);
entries.push(entry);
}
build_hamt(&entries, nodes)
}
let mut nodes = BTreeMap::new();
let mut entries = BTreeMap::new();
let root = recurse(
&directory,
"",
prior,
nonce_factory,
&mut nodes,
&mut entries,
)?;
Ok(BuiltTree {
root,
nodes,
entries,
files,
})
}
#[derive(Debug, Clone, Deserialize, Serialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum ProofFrame {
Branch {
depth: usize,
slot: u8,
siblings: Vec<(u8, String)>,
},
Compressed {
depth: usize,
run: String,
},
}
#[derive(Debug, Clone, Deserialize, Serialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum NonInclusionTerminal {
EmptyBranch {
depth: usize,
slot: u8,
siblings: Vec<(u8, String)>,
},
CompressedMismatch {
depth: usize,
run: String,
child: String,
},
}
#[derive(Debug, Clone, Deserialize, Serialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum HamtProof {
Inclusion {
entry: TreeEntry,
route: String,
frames: Vec<ProofFrame>,
},
NonInclusion {
name: String,
route: String,
terminal: NonInclusionTerminal,
frames: Vec<ProofFrame>,
},
}
pub fn create_proof(
root: &str,
name: &str,
nodes: &BTreeMap<String, Vec<u8>>,
) -> V2Result<HamtProof> {
let route = sha256_hex(name.nfc().collect::<String>().as_bytes());
let mut frames = Vec::new();
let mut hash = root.to_string();
loop {
let bytes = nodes
.get(&hash)
.ok_or_else(|| V2Error::MissingNode(hash.clone()))?;
let node = decode_node(bytes)?;
if hash_node(&node)? != hash {
return Err(V2Error::InvalidTree("node address mismatch".to_string()));
}
match node {
HamtNode::Leaf {
route: leaf_route,
entry,
} => {
if leaf_route != route || entry.name != name {
return Err(V2Error::InvalidTree(
"cryptographic name-route collision".to_string(),
));
}
return Ok(HamtProof::Inclusion {
entry,
route,
frames,
});
}
HamtNode::Compressed { depth, run, child } => {
if route[depth..depth + run.len()] != run {
return Ok(HamtProof::NonInclusion {
name: name.to_string(),
route,
terminal: NonInclusionTerminal::CompressedMismatch { depth, run, child },
frames,
});
}
frames.push(ProofFrame::Compressed {
depth,
run: run.clone(),
});
hash = child;
}
HamtNode::Branch { depth, children } => {
let slot = u8::from_str_radix(&route[depth..=depth], 16)
.map_err(|_| V2Error::InvalidTree("invalid route nibble".to_string()))?;
let child = children.iter().find(|(candidate, _)| *candidate == slot);
let siblings = children
.iter()
.filter(|(candidate, _)| *candidate != slot)
.cloned()
.collect::<Vec<_>>();
let Some((_, child_hash)) = child else {
return Ok(HamtProof::NonInclusion {
name: name.to_string(),
route,
terminal: NonInclusionTerminal::EmptyBranch {
depth,
slot,
siblings,
},
frames,
});
};
frames.push(ProofFrame::Branch {
depth,
slot,
siblings,
});
hash = child_hash.clone();
}
}
}
}
pub fn verify_proof(root: &str, name: &str, proof: &HamtProof) -> V2Result<bool> {
verify_proof_with_domain(root, name, proof, CONTENT_TREE_HASH_DOMAIN)
}
pub fn verify_proof_with_domain(
root: &str,
name: &str,
proof: &HamtProof,
domain: &str,
) -> V2Result<bool> {
let normalized = name.nfc().collect::<String>();
let route = sha256_hex(normalized.as_bytes());
let (mut current, frames) = match proof {
HamtProof::Inclusion {
entry,
route: proof_route,
frames,
} => {
if proof_route != &route || entry.name != normalized {
return Ok(false);
}
(
hash_node_with_domain(
&HamtNode::Leaf {
route: route.clone(),
entry: entry.clone(),
},
domain,
)?,
frames,
)
}
HamtProof::NonInclusion {
route: proof_route,
terminal,
frames,
..
} => {
if proof_route != &route {
return Ok(false);
}
let hash = match terminal {
NonInclusionTerminal::CompressedMismatch { depth, run, child } => {
if route[*depth..*depth + run.len()] == *run {
return Ok(false);
}
hash_node_with_domain(
&HamtNode::Compressed {
depth: *depth,
run: run.clone(),
child: child.clone(),
},
domain,
)?
}
NonInclusionTerminal::EmptyBranch {
depth,
slot,
siblings,
} => {
let wanted = u8::from_str_radix(&route[*depth..=*depth], 16)
.map_err(|_| V2Error::InvalidTree("invalid route nibble".to_string()))?;
if wanted != *slot || siblings.iter().any(|(candidate, _)| candidate == slot) {
return Ok(false);
}
hash_node_with_domain(
&HamtNode::Branch {
depth: *depth,
children: siblings.clone(),
},
domain,
)?
}
};
(hash, frames)
}
};
for frame in frames.iter().rev() {
current = match frame {
ProofFrame::Compressed { depth, run } => hash_node_with_domain(
&HamtNode::Compressed {
depth: *depth,
run: run.clone(),
child: current,
},
domain,
)?,
ProofFrame::Branch {
depth,
slot,
siblings,
} => {
let mut children = siblings.clone();
children.push((*slot, current));
children.sort_by_key(|(candidate, _)| *candidate);
if children.windows(2).any(|window| window[0].0 == window[1].0) {
return Ok(false);
}
hash_node_with_domain(
&HamtNode::Branch {
depth: *depth,
children,
},
domain,
)?
}
}
}
Ok(current == root)
}
#[cfg(test)]
mod tests {
use super::*;
#[derive(Deserialize)]
struct PathCorpus {
v: u8,
valid: Vec<String>,
invalid: Vec<String>,
invalid_sets: Vec<Vec<String>>,
}
fn nonce_sequence() -> impl FnMut() -> String {
let mut value = 0u128;
move || {
let nonce = format!("{value:032x}");
value += 1;
nonce
}
}
fn file(path: &str, bytes: &[u8]) -> ContentFile {
ContentFile {
path: path.to_string(),
blob_hash: sha256_hex(bytes),
bytes: bytes.len() as u64,
}
}
#[test]
fn canonical_tree_and_proofs() {
let mut nonces = nonce_sequence();
let tree = build_content_tree(
&[
file("DB.md", b"db"),
file("secret.md", b"secret"),
file("visible.md", b"visible"),
],
None,
&mut nonces,
)
.unwrap();
let root = tree.root.as_deref().unwrap();
assert_eq!(
root,
"82bcc02847453aac64310ad0ab83a2cce3f79ec7bac7664f0e6760cb38bc3d53"
);
let proof = create_proof(root, "visible.md", &tree.nodes).unwrap();
assert!(verify_proof(root, "visible.md", &proof).unwrap());
let encoded = serde_json::to_string(&proof).unwrap();
assert!(!encoded.contains("secret.md"));
assert!(!encoded.contains(&tree.entries["secret.md"].entry.nonce));
let missing = create_proof(root, "missing.md", &tree.nodes).unwrap();
assert!(verify_proof(root, "missing.md", &missing).unwrap());
}
#[test]
fn changed_sibling_rotates_the_nonce_hidden_from_retained_readers() {
let vector: serde_json::Value =
serde_json::from_str(include_str!("../tests/vectors/linkmd-v2-content-tree.json"))
.unwrap();
let privacy = &vector["changed_sibling"];
let mut before_nonces = nonce_sequence();
let before = build_content_tree(
&[
file("DB.md", b"db"),
file("secret.md", b"old secret"),
file("visible.md", b"visible"),
],
None,
&mut before_nonces,
)
.unwrap();
assert_eq!(before.root.as_deref().unwrap(), privacy["before_root"]);
let changed_path = privacy["changed_path"].as_str().unwrap();
let old_nonce = before.entries[changed_path].entry.nonce.clone();
let mut value =
u128::from_str_radix(privacy["after_nonce_start_hex"].as_str().unwrap(), 16).unwrap();
let mut after_nonces = move || {
let nonce = format!("{value:032x}");
value += 1;
nonce
};
let after = build_content_tree(
&[
file("DB.md", b"db"),
file("secret.md", b"new secret"),
file("visible.md", b"visible"),
],
Some(&before),
&mut after_nonces,
)
.unwrap();
assert_eq!(after.root.as_deref().unwrap(), privacy["after_root"]);
let new_nonce = &after.entries[changed_path].entry.nonce;
assert_eq!(old_nonce, privacy["old_nonce"].as_str().unwrap());
assert_eq!(new_nonce, privacy["new_nonce"].as_str().unwrap());
let root = after.root.as_deref().unwrap();
let proof_target = privacy["proof_target"].as_str().unwrap();
let proof = create_proof(root, proof_target, &after.nodes).unwrap();
assert!(verify_proof(root, proof_target, &proof).unwrap());
let encoded = serde_json::to_string(&proof).unwrap();
for forbidden in privacy["privacy_forbidden_strings"].as_array().unwrap() {
assert!(!encoded.contains(forbidden.as_str().unwrap()));
}
}
#[test]
fn rejects_portability_collisions() {
assert!(validate_path_set(["Records/a.md", "records/a.md"]).is_err());
assert!(validate_path_set(["records", "records/a.md"]).is_err());
assert!(normalize_path("CON").is_err());
assert!(validate_path_set(["Å.md", "å.md"]).is_err());
for path in [
"/absolute",
"a/../b",
"a\\b",
"a:b",
"nul.txt",
"folder/COM9.log",
"folder/LPT1",
"a.",
"a ",
"e\u{301}.md",
"control\u{1}.md",
] {
assert!(normalize_path(path).is_err(), "accepted {path:?}");
}
for path in [
"é.md",
".hidden.md",
"records/COM0.md",
"records/LPT10.md",
"records/emoji-🦓.md",
] {
assert_eq!(normalize_path(path).unwrap(), path);
}
assert!(normalize_path(&format!("{}.md", "a".repeat(256))).is_err());
assert!(normalize_path(&format!("{}x.md", "a/".repeat(512))).is_err());
}
#[test]
fn shared_portable_path_corpus_matches_rust() {
let corpus: PathCorpus = serde_json::from_str(include_str!(
"../tests/vectors/linkmd-v2-portable-paths.json"
))
.unwrap();
assert_eq!(corpus.v, 1);
for path in corpus.valid {
assert_eq!(normalize_path(&path).unwrap(), path);
}
for path in corpus.invalid {
assert!(normalize_path(&path).is_err(), "accepted {path:?}");
}
for paths in corpus.invalid_sets {
assert!(validate_path_set(paths.iter().map(String::as_str)).is_err());
}
}
#[test]
fn randomized_map_build_is_order_independent() {
let mut random_state = 0x51e7_9b3d_u32;
let mut random = || {
random_state = random_state
.wrapping_mul(1_664_525)
.wrapping_add(1_013_904_223);
random_state
};
let mut model = BTreeMap::from([("DB.md".to_string(), b"contract".to_vec())]);
for step in 0..400 {
let path = format!("records/property/{:02}.md", random() % 64);
if model.contains_key(&path) && random() % 4 == 0 {
model.remove(&path);
} else {
model.insert(path, format!("value:{step}:{}", random()).into_bytes());
}
let files = model
.iter()
.map(|(path, bytes)| file(path, bytes))
.collect::<Vec<_>>();
let mut forward_nonces = nonce_sequence();
let forward = build_content_tree(&files, None, &mut forward_nonces).unwrap();
let mut reverse_files = files.clone();
reverse_files.reverse();
let mut reverse_nonces = nonce_sequence();
let reverse = build_content_tree(&reverse_files, None, &mut reverse_nonces).unwrap();
assert_eq!(forward.root, reverse.root);
let root = forward.root.as_deref().unwrap();
let proof = create_proof(root, "records", &forward.nodes).unwrap();
assert!(verify_proof(root, "records", &proof).unwrap());
}
}
}