Merkle trees

use merkle.qweruse merkle_leaf, merkle_root from merkle      // Quillo 0.6: only these

sha2 = "0.10"

// An audit log that publishes one root a day: a receipt that proves an entry is in it, and a proof// that today's log only added entries after yesterday's.////   quillo run merkle.qwe      then open http://localhost:8080/receipt and http://localhost:8080/grewuse "merkle.qwer"let LOG = [    "2026-10-01 alice paid invoice 1041: 120.00",    "2026-10-01 bob refunded order 88: 15.50",    "2026-10-02 carol changed her email",    "2026-10-02 admin granted dave the role auditor",    "2026-10-03 alice paid invoice 1042: 80.00",    "2026-10-03 erin closed her account",    "2026-10-04 frank paid invoice 1043: 310.25",]// The receipt for entry 2: whoever holds it checks it against the published root alone.route GET /receipt {    let root = merkle_root(LOG)?    let proof = merkle_proof(LOG, 2)?    {        root: root,        steps: len(proof.path),        holds: merkle_verify(LOG[2], proof, root)?,        changed_entry: merkle_verify("2026-10-02 carol changed her name", proof, root)?,        leaf_alone: merkle_verify_leaf(merkle_leaf(LOG[2]), proof, root)?,    }}// Yesterday 4 entries were published; today 7. The proof shows the first 4 were left alone.route GET /grew {    let yesterday = merkle_root(slice(LOG, 0, 4))?    let today = merkle_root(LOG)?    let proof = merkle_consistency(LOG, 4)?    let rewritten = merkle_root(["2026-10-01 alice paid invoice 1041: 12.00"] + slice(LOG, 1, 7))?    {        yesterday: yesterday,        only_added: merkle_verify_consistency(proof, yesterday, today)?,        history_rewritten: merkle_verify_consistency(merkle_consistency(["2026-10-01 alice paid invoice 1041: 12.00"] + slice(LOG, 1, 7), 4)?, yesterday, rewritten)?,    }}// A file's root over 1 KB pieces, and one piece proved.route GET /file {    write_file("data/merkle-demo.txt", join(for i in range(100) => LOG[i % 7], "\n"))    let f = merkle_file("data/merkle-demo.txt", 1)?    { root: f.root, chunks: f.chunks, bytes: f.bytes, piece_2: merkle_verify_leaf(f.leaves[2], merkle_proof_of_leaves(f.leaves, 2)?, f.root)?, wrong_piece: merkle_verify_leaf(f.leaves[1], merkle_proof_of_leaves(f.leaves, 2)?, f.root)? }}

//! Merkle trees as Certificate Transparency makes them (RFC 9162): a root for a list, a short proof that one item is in it, and a proof that a later list only added to an earlier one.//! version: 1.0.0//!//! [dependencies]//! sha2 = "0.10"use serde_json::{json, Value};use sha2::{Digest, Sha256};use std::io::Read;type H = [u8; 32];const MAX_ITEMS: usize = 10_000_000;fn leaf(data: &[u8]) -> H {    let mut h = Sha256::new();    h.update([0u8]);    h.update(data);    h.finalize().into()}fn node(l: &H, r: &H) -> H {    let mut h = Sha256::new();    h.update([1u8]);    h.update(l);    h.update(r);    h.finalize().into()}fn hex(h: &H) -> String {    h.iter().map(|b| format!("{:02x}", b)).collect()}fn unhex(s: &str) -> Result<H, String> {    let s = s.trim();    if s.len() != 64 {        return Err(format!("`{}` is not a SHA-256 hash in hex (64 characters)", s));    }    let mut out = [0u8; 32];    for i in 0..32 {        out[i] = u8::from_str_radix(&s[2 * i..2 * i + 2], 16).map_err(|_| format!("`{}` is not hex", s))?;    }    Ok(out)}/// The largest power of two below `n` (n > 1).fn split(n: usize) -> usize {    let mut k = 1;    while k << 1 < n {        k <<= 1;    }    k}fn mth(d: &[H]) -> H {    match d.len() {        0 => Sha256::digest([]).into(),        1 => d[0],        n => {            let k = split(n);            node(&mth(&d[..k]), &mth(&d[k..]))        }    }}fn path(m: usize, d: &[H]) -> Vec<H> {    let n = d.len();    if n <= 1 {        return vec![];    }    let k = split(n);    if m < k {        let mut p = path(m, &d[..k]);        p.push(mth(&d[k..]));        p    } else {        let mut p = path(m - k, &d[k..]);        p.push(mth(&d[..k]));        p    }}fn subproof(m: usize, d: &[H], whole: bool) -> Vec<H> {    let n = d.len();    if m == n {        return if whole { vec![] } else { vec![mth(d)] };    }    let k = split(n);    if m <= k {        let mut p = subproof(m, &d[..k], whole);        p.push(mth(&d[k..]));        p    } else {        let mut p = subproof(m - k, &d[k..], false);        p.push(mth(&d[..k]));        p    }}fn leaves(items: &[String]) -> Result<Vec<H>, String> {    if items.len() > MAX_ITEMS {        return Err("up to 10 million items".into());    }    Ok(items.iter().map(|s| leaf(s.as_bytes())).collect())}fn hashes(list: &[String]) -> Result<Vec<H>, String> {    if list.len() > MAX_ITEMS {        return Err("up to 10 million hashes".into());    }    list.iter().map(|s| unhex(s)).collect()}fn verify_path(index: u64, size: u64, leaf_hash: H, p: &[H], root: &H) -> bool {    if index >= size {        return false;    }    let (mut f, mut s) = (index, size - 1);    let mut r = leaf_hash;    for x in p {        if s == 0 {            return false;        }        if f & 1 == 1 || f == s {            r = node(x, &r);            if f & 1 == 0 {                while f & 1 == 0 && f != 0 {                    f >>= 1;                    s >>= 1;                }            }        } else {            r = node(&r, x);        }        f >>= 1;        s >>= 1;    }    s == 0 && &r == root}fn field_u64(v: &Value, k: &str) -> Result<u64, String> {    v.get(k).and_then(|x| x.as_u64()).ok_or_else(|| format!("the proof has no `{}` (a whole number from 0)", k))}fn field_path(v: &Value) -> Result<Vec<H>, String> {    let a = v.get("path").and_then(|x| x.as_array()).ok_or("the proof has no `path` (a list of hashes)")?;    a.iter().map(|x| x.as_str().ok_or_else(|| "each step of `path` is a hash in hex".to_string()).and_then(unhex)).collect()}/// The leaf hash of one item, as the tree keeps it: SHA-256 of a 0 byte and the item's UTF-8 text, in hex. Store it beside a log entry, then build roots from these with `merkle_root_of_leaves`.pub fn merkle_leaf(item: &str) -> String {    hex(&leaf(item.as_bytes()))}/// The root of the tree over `items` (each item's text, in order), in hex: 64 characters that change when any item changes, moves, or is added or removed. An empty list has SHA-256 of nothing as its root.pub fn merkle_root(items: Vec<String>) -> Result<String, String> {    Ok(hex(&mth(&leaves(&items)?)))}/// The root over leaf hashes already worked out (`merkle_leaf` of each item, in order): for long logs kept as hashes.pub fn merkle_root_of_leaves(leaf_hashes: Vec<String>) -> Result<String, String> {    Ok(hex(&mth(&hashes(&leaf_hashes)?)))}/// The proof that `items[index]` (counted from 0) is in the tree over `items`: `{ index, size, leaf, root, path }`, `path` the/// sibling hashes from the leaf up (about log2(size) of them: 20 for a million items). Give it to whoever holds the item; they/// check it against a root they trust with `merkle_verify`, without seeing the other items.pub fn merkle_proof(items: Vec<String>, index: i64) -> Result<Value, String> {    let d = leaves(&items)?;    if index < 0 || index as usize >= d.len() {        return Err(format!("index {} is outside the list of {} items", index, d.len()));    }    let i = index as usize;    Ok(json!({        "index": i,        "size": d.len(),        "leaf": hex(&d[i]),        "root": hex(&mth(&d)),        "path": path(i, &d).iter().map(hex).collect::<Vec<_>>(),    }))}/// Whether `item` is in the tree whose root is `root`, by `proof` (a map with `index`, `size` and `path`, as `merkle_proof` gives;/// its own `root` and `leaf` are not trusted). False for a changed item, another index or size, a changed path, or another root.pub fn merkle_verify(item: &str, proof: serde_json::Value, root: &str) -> Result<bool, String> {    let root = unhex(root)?;    Ok(verify_path(field_u64(&proof, "index")?, field_u64(&proof, "size")?, leaf(item.as_bytes()), &field_path(&proof)?, &root))}/// `merkle_proof` over leaf hashes already worked out (`merkle_leaf` of each item, or `merkle_file`'s `leaves`).pub fn merkle_proof_of_leaves(leaf_hashes: Vec<String>, index: i64) -> Result<Value, String> {    let d = hashes(&leaf_hashes)?;    if index < 0 || index as usize >= d.len() {        return Err(format!("index {} is outside the list of {} leaves", index, d.len()));    }    let i = index as usize;    Ok(json!({ "index": i, "size": d.len(), "leaf": hex(&d[i]), "root": hex(&mth(&d)), "path": path(i, &d).iter().map(hex).collect::<Vec<_>>() }))}/// `merkle_verify` for a leaf hash rather than the item: a file's piece hashed by the downloader, or an entry stored as its hash.pub fn merkle_verify_leaf(leaf_hash: &str, proof: serde_json::Value, root: &str) -> Result<bool, String> {    let root = unhex(root)?;    Ok(verify_path(field_u64(&proof, "index")?, field_u64(&proof, "size")?, unhex(leaf_hash)?, &field_path(&proof)?, &root))}/// The proof that the list's first `old_size` items are the whole of an earlier tree, unchanged: `{ old_size, size, old_root, root, path }`./// An audit log publishes its root each day; this shows today's log only added entries after yesterday's.pub fn merkle_consistency(items: Vec<String>, old_size: i64) -> Result<Value, String> {    let d = leaves(&items)?;    if old_size < 1 || old_size as usize > d.len() {        return Err(format!("old_size is from 1 to the list's length ({})", d.len()));    }    let m = old_size as usize;    Ok(json!({        "old_size": m,        "size": d.len(),        "old_root": hex(&mth(&d[..m])),        "root": hex(&mth(&d)),        "path": subproof(m, &d, true).iter().map(hex).collect::<Vec<_>>(),    }))}/// Whether the tree with root `root` grew from the one with root `old_root` by adding items only, by `proof` (a map with/// `old_size`, `size` and `path`, as `merkle_consistency` gives; its roots are not trusted).pub fn merkle_verify_consistency(proof: serde_json::Value, old_root: &str, root: &str) -> Result<bool, String> {    let (first, second) = (field_u64(&proof, "old_size")?, field_u64(&proof, "size")?);    let (old, new) = (unhex(old_root)?, unhex(root)?);    let mut p = field_path(&proof)?;    if first == 0 || first > second {        return Ok(false);    }    if first == second {        return Ok(p.is_empty() && old == new);    }    if p.is_empty() {        return Ok(false);    }    if first.is_power_of_two() {        p.insert(0, old);    }    let (mut f, mut s) = (first - 1, second - 1);    while f & 1 == 1 {        f >>= 1;        s >>= 1;    }    let (mut fr, mut sr) = (p[0], p[0]);    for c in &p[1..] {        if s == 0 {            return Ok(false);        }        if f & 1 == 1 || f == s {            fr = node(c, &fr);            sr = node(c, &sr);            if f & 1 == 0 {                while f & 1 == 0 && f != 0 {                    f >>= 1;                    s >>= 1;                }            }        } else {            sr = node(&sr, c);        }        f >>= 1;        s >>= 1;    }    Ok(fr == old && sr == new && s == 0)}/// A file's tree over pieces of `chunk_kb` KB (1 to 65,536): `{ root, chunks, bytes, leaves }`, `leaves` each piece's leaf hash./// Publish the root; `merkle_proof_of_leaves` over `leaves` then proves one piece, which a downloader checks with `merkle_verify_leaf`.pub fn merkle_file(path: &str, chunk_kb: i64) -> Result<Value, String> {    if !(1..=65_536).contains(&chunk_kb) {        return Err("chunk_kb is from 1 to 65,536".into());    }    let mut f = std::fs::File::open(path).map_err(|e| format!("{}: {}", path, e))?;    let size = chunk_kb as usize * 1024;    let mut buf = vec![0u8; size];    let (mut d, mut bytes) = (Vec::new(), 0u64);    loop {        let mut got = 0;        while got < size {            let n = f.read(&mut buf[got..]).map_err(|e| format!("{}: {}", path, e))?;            if n == 0 {                break;            }            got += n;        }        if got == 0 {            break;        }        bytes += got as u64;        d.push(leaf(&buf[..got]));        if d.len() > MAX_ITEMS {            return Err("more than 10 million pieces: take bigger ones".into());        }        if got < size {            break;        }    }    Ok(json!({ "root": hex(&mth(&d)), "chunks": d.len(), "bytes": bytes, "leaves": d.iter().map(hex).collect::<Vec<_>>() }))}