//! The output tree (`extensions/staged-measurement.md` Appendix C): a commitment to
//! every presentation a sink made, one leaf per (unit, layers), so that a record or a
//! session claim commits to its outputs by the tree's root and its leaf count
//! ([`OutputCommitment`]) and any one output is provable by an inclusion path.
//!
//! ```text
//! out_digest = SHA-256(canonical output)          SPEC §7 Digests: RGB8, s16le PCM, …
//! leaf = SHA-256("wai:out-leaf\x01" ‖ u64_be(unit) ‖ u16_be(layers) ‖ u16_be(decoder) ‖ out_digest)
//! node = SHA-256("wai:out-node\x01" ‖ left ‖ right)
//! ```
//!
//! Leaves are ordered by (unit, layers), and a (unit, layers) given twice is refused.
//! The root over `n ≥ 1` leaves is RFC 6962's Merkle tree hash: one leaf is itself;
//! otherwise `node(MTH(D[0:k]), MTH(D[k:n]))` with `k` the largest power of two below
//! `n`. No leaf is ever duplicated, so two different leaf lists never give one root and
//! the leaf count is fixed by the tree. An inclusion proof is RFC 6962's audit path,
//! checked as RFC 9162 §2.1.3.2 checks one, against the leaf count the commitment
//! states: one audit path can verify against one root under two tree sizes, so a root
//! without its leaf count fixes neither a leaf's position nor the tree's size, and
//! [`verify_proof`] takes no size from the proof's holder.

use crate::pin::sha256;

/// The leaf domain.
pub const LEAF_DOMAIN: &[u8] = b"wai:out-leaf\x01";
/// The node domain.
pub const NODE_DOMAIN: &[u8] = b"wai:out-node\x01";

/// One presentation: a unit, the layers it was presented at (the base alone is 1),
/// the index of the decoder entry that produced it, and its output's digest.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Presentation {
    pub unit: u64,
    pub layers: u16,
    pub decoder: u16,
    pub out_digest: [u8; 32],
}

/// Why no root or proof was given.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TreeError {
    /// The same (unit, layers) was presented twice.
    Duplicate { unit: u64, layers: u16 },
    /// A proof was asked for a leaf the tree does not have.
    IndexOutOfRange,
}

impl std::fmt::Display for TreeError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Duplicate { unit, layers } => write!(f, "unit {unit} at {layers} layers is presented twice"),
            Self::IndexOutOfRange => f.write_str("no leaf at that index"),
        }
    }
}

impl std::error::Error for TreeError {}

/// The SHA-256 of an output's canonical buffer.
pub fn out_digest(canonical: &[u8]) -> [u8; 32] {
    sha256(canonical)
}

/// A presentation's leaf hash.
pub fn leaf(p: &Presentation) -> [u8; 32] {
    let mut b = Vec::with_capacity(LEAF_DOMAIN.len() + 8 + 2 + 2 + 32);
    b.extend_from_slice(LEAF_DOMAIN);
    b.extend_from_slice(&p.unit.to_be_bytes());
    b.extend_from_slice(&p.layers.to_be_bytes());
    b.extend_from_slice(&p.decoder.to_be_bytes());
    b.extend_from_slice(&p.out_digest);
    sha256(&b)
}

/// The tree's interior node, `SHA-256("wai:out-node\x01" ‖ left ‖ right)`. A tree of
/// another leaf domain built with this node (capture-binding's take tree) is this
/// construction over its own leaves.
pub fn node(l: &[u8; 32], r: &[u8; 32]) -> [u8; 32] {
    let mut b = Vec::with_capacity(NODE_DOMAIN.len() + 64);
    b.extend_from_slice(NODE_DOMAIN);
    b.extend_from_slice(l);
    b.extend_from_slice(r);
    sha256(&b)
}

/// The largest power of two below `n` (`n ≥ 2`).
fn split(n: usize) -> usize {
    let mut k = 1;
    while k * 2 < n {
        k *= 2;
    }
    k
}

/// RFC 6962's Merkle tree hash over leaf hashes `d` (`d` not empty), with [`node`].
pub fn tree_hash(d: &[[u8; 32]]) -> [u8; 32] {
    mth(d)
}

fn mth(d: &[[u8; 32]]) -> [u8; 32] {
    if d.len() == 1 {
        return d[0];
    }
    let k = split(d.len());
    node(&mth(&d[..k]), &mth(&d[k..]))
}

/// The presentations in leaf order, refusing a (unit, layers) given twice.
pub fn ordered(ps: &[Presentation]) -> Result<Vec<Presentation>, TreeError> {
    let mut v = ps.to_vec();
    v.sort_by_key(|p| (p.unit, p.layers));
    if let Some(w) = v.windows(2).find(|w| (w[0].unit, w[0].layers) == (w[1].unit, w[1].layers)) {
        return Err(TreeError::Duplicate { unit: w[0].unit, layers: w[0].layers });
    }
    Ok(v)
}

/// The root over `ps`, in any order; `None` for no presentation. A root alone is not a
/// commitment: [`commit`] gives it with its leaf count.
pub fn root(ps: &[Presentation]) -> Result<Option<[u8; 32]>, TreeError> {
    let v = ordered(ps)?;
    if v.is_empty() {
        return Ok(None);
    }
    let leaves: Vec<[u8; 32]> = v.iter().map(leaf).collect();
    Ok(Some(mth(&leaves)))
}

/// What a record or a claim commits to: the tree's root and its leaf count.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct OutputCommitment {
    pub root: [u8; 32],
    pub leaf_count: u64,
}

/// The commitment to `ps`, in any order; `None` for no presentation.
pub fn commit(ps: &[Presentation]) -> Result<Option<OutputCommitment>, TreeError> {
    Ok(root(ps)?.map(|root| OutputCommitment { root, leaf_count: ps.len() as u64 }))
}

fn path(m: usize, d: &[[u8; 32]], out: &mut Vec<[u8; 32]>) {
    if d.len() <= 1 {
        return;
    }
    let k = split(d.len());
    if m < k {
        path(m, &d[..k], out);
        out.push(mth(&d[k..]));
    } else {
        path(m - k, &d[k..], out);
        out.push(mth(&d[..k]));
    }
}

/// The audit path of the leaf at `index` in leaf order (RFC 6962 §2.1.1), from the leaf
/// up.
pub fn proof(ps: &[Presentation], index: usize) -> Result<Vec<[u8; 32]>, TreeError> {
    let v = ordered(ps)?;
    if index >= v.len() {
        return Err(TreeError::IndexOutOfRange);
    }
    let leaves: Vec<[u8; 32]> = v.iter().map(leaf).collect();
    let mut out = Vec::new();
    path(index, &leaves, &mut out);
    Ok(out)
}

/// Whether `path` proves the leaf hash `leaf` at `index` in the tree `c` commits to: its
/// root, under its leaf count (RFC 9162 §2.1.3.2).
pub fn verify_proof(leaf: [u8; 32], index: u64, path: &[[u8; 32]], c: &OutputCommitment) -> bool {
    let (n, root) = (c.leaf_count, c.root);
    if index >= n {
        return false;
    }
    let (mut fnn, mut sn) = (index, n - 1);
    let mut r = leaf;
    for p in path {
        if sn == 0 {
            return false;
        }
        if fnn & 1 == 1 || fnn == sn {
            r = node(p, &r);
            while fnn & 1 == 0 && fnn != 0 {
                fnn >>= 1;
                sn >>= 1;
            }
        } else {
            r = node(&r, p);
        }
        fnn >>= 1;
        sn >>= 1;
    }
    sn == 0 && r == root
}

/// The audit path of leaf `index` among the leaf hashes `d` (RFC 6962 §2.1.1, RFC 9162
/// §2.1.3.1), from the leaf up: [`proof`] over leaves of any domain. `None` when `index`
/// is not below `d.len()`.
pub fn audit_path(index: usize, d: &[[u8; 32]]) -> Option<Vec<[u8; 32]>> {
    if index >= d.len() {
        return None;
    }
    let mut out = Vec::new();
    path(index, d, &mut out);
    Some(out)
}

/// The largest power of two below `n` (`n ≥ 2`), on `u64`.
fn split64(n: u64) -> u64 {
    1u64 << (63 - (n - 1).leading_zeros())
}

fn range_nodes(a: usize, b: usize, d: &[[u8; 32]], out: &mut Vec<[u8; 32]>) {
    let n = d.len();
    if a == 0 && b == n {
        return;
    }
    let k = split(n);
    if b <= k {
        range_nodes(a, b, &d[..k], out);
        out.push(mth(&d[k..]));
    } else if a >= k {
        range_nodes(a - k, b - k, &d[k..], out);
        out.push(mth(&d[..k]));
    } else {
        range_nodes(a, k, &d[..k], out);
        range_nodes(0, b - k, &d[k..], out);
    }
}

/// The range proof that leaves `a` to `b` − 1 of the leaf hashes `d` are those of the
/// tree over `d` (extensions/live-recording.md §5.3): RFC 6962 §2.1.1's `PATH` taken over
/// a run of leaves instead of one. With `n` = `d.len()` and `k` the largest power of two
/// below `n`, `RANGE(a, b, D[n])` is empty when `a` is 0 and `b` is `n`, and otherwise
/// `RANGE(a, b, D[0:k]) : MTH(D[k:n])` when `b ≤ k`, `RANGE(a − k, b − k, D[k:n]) :
/// MTH(D[0:k])` when `a ≥ k`, and `RANGE(a, k, D[0:k]) : RANGE(0, b − k, D[k:n])`
/// otherwise. A run of one leaf is never split, so `range_proof(i, i + 1, d)` is leaf
/// `i`'s audit path, node for node. `None` unless `a < b ≤ n`.
pub fn range_proof(a: usize, b: usize, d: &[[u8; 32]]) -> Option<Vec<[u8; 32]>> {
    if a >= b || b > d.len() {
        return None;
    }
    let mut out = Vec::new();
    range_nodes(a, b, d, &mut out);
    Some(out)
}

/// The root a range proof walks to, consuming `proof` from the front in the order
/// [`range_proof`] writes it; `None` when it runs out.
fn range_root(a: u64, b: u64, n: u64, leaves: &[[u8; 32]], proof: &mut std::slice::Iter<'_, [u8; 32]>) -> Option<[u8; 32]> {
    if a == 0 && b == n {
        return Some(mth(leaves));
    }
    let k = split64(n);
    if b <= k {
        let x = range_root(a, b, k, leaves, proof)?;
        Some(node(&x, proof.next()?))
    } else if a >= k {
        let x = range_root(a - k, b - k, n - k, leaves, proof)?;
        Some(node(proof.next()?, &x))
    } else {
        let at = (k - a) as usize;
        let x = range_root(a, k, k, &leaves[..at], proof)?;
        let y = range_root(0, b - k, n - k, &leaves[at..], proof)?;
        Some(node(&x, &y))
    }
}

/// Whether `proof` shows that the leaf hashes `leaves` are leaves `first` onward of the
/// tree `c` commits to, under its leaf count: the tree's root rebuilt by the recursion of
/// [`range_proof`], every node of the proof used once, in order, and none left over
/// (extensions/live-recording.md §5.3). For one leaf it gives what [`verify_proof`], RFC
/// 9162 §2.1.3.2's check, gives for that leaf's audit path. The leaf count is the
/// commitment's, never the proof holder's, as for an audit path.
pub fn verify_range(first: u64, leaves: &[[u8; 32]], proof: &[[u8; 32]], c: &OutputCommitment) -> bool {
    let n = c.leaf_count;
    let Some(b) = first.checked_add(leaves.len() as u64) else { return false };
    if leaves.is_empty() || b > n {
        return false;
    }
    let mut it = proof.iter();
    match range_root(first, b, n, leaves, &mut it) {
        Some(r) => it.next().is_none() && r == c.root,
        None => false,
    }
}

fn subproof(m: usize, d: &[[u8; 32]], b: bool, out: &mut Vec<[u8; 32]>) {
    let n = d.len();
    if m == n {
        if !b {
            out.push(mth(d));
        }
        return;
    }
    let k = split(n);
    if m <= k {
        subproof(m, &d[..k], b, out);
        out.push(mth(&d[k..]));
    } else {
        subproof(m - k, &d[k..], false, out);
        out.push(mth(&d[..k]));
    }
}

/// The consistency proof (RFC 9162 §2.1.4.1, RFC 6962 §2.1.2's `PROOF(m, D[n])`) that the
/// tree over the first `m` leaf hashes of `d` is a prefix of the tree over all of them:
/// empty when `m` is 0 or `d.len()`.
pub fn consistency_proof(m: usize, d: &[[u8; 32]]) -> Vec<[u8; 32]> {
    let mut out = Vec::new();
    if 0 < m && m < d.len() {
        subproof(m, d, true, &mut out);
    }
    out
}

/// Whether `proof` shows the tree of `first` leaves whose root is `first_root` is a prefix
/// of the tree of `second` leaves whose root is `second_root`, checked as RFC 9162
/// §2.1.4.2 checks one, with [`node`] for its `HASH(0x01 ‖ …)`. `0 < first < second`; the
/// caller decides the cases RFC 9162 leaves to it (an empty first tree, or equal sizes).
pub fn verify_consistency(first: u64, second: u64, first_root: &[u8; 32], second_root: &[u8; 32], proof: &[[u8; 32]]) -> bool {
    if first == 0 || first >= second || proof.is_empty() {
        return false;
    }
    let mut path: Vec<[u8; 32]> = Vec::with_capacity(proof.len() + 1);
    if first.is_power_of_two() {
        path.push(*first_root);
    }
    path.extend_from_slice(proof);
    let (mut fnn, mut sn) = (first - 1, second - 1);
    while fnn & 1 == 1 {
        fnn >>= 1;
        sn >>= 1;
    }
    let (mut fr, mut sr) = (path[0], path[0]);
    for c in &path[1..] {
        if sn == 0 {
            return false;
        }
        if fnn & 1 == 1 || fnn == sn {
            fr = node(c, &fr);
            sr = node(c, &sr);
            if fnn & 1 == 0 {
                while fnn & 1 == 0 && fnn != 0 {
                    fnn >>= 1;
                    sn >>= 1;
                }
            }
        } else {
            sr = node(&sr, c);
        }
        fnn >>= 1;
        sn >>= 1;
    }
    fr == *first_root && sr == *second_root && sn == 0
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::BTreeSet;

    fn hex(b: &[u8]) -> String {
        b.iter().map(|x| format!("{x:02x}")).collect()
    }

    /// The leaves the independent reference builds: unit `i`, `1 + i mod 3` layers,
    /// decoder `i mod 2`, the output digest SHA-256 of the one byte `i`.
    fn ps(n: usize) -> Vec<Presentation> {
        (0..n).map(|i| Presentation { unit: i as u64, layers: 1 + (i % 3) as u16, decoder: (i % 2) as u16, out_digest: sha256(&[i as u8]) }).collect()
    }

    #[test]
    fn rfc6962_shape() {
        let want = [
            "327b97c1dd3a9f79f5e895d4e1ee9e3effbad78c8e10621446e596e07b29c509",
            "fde25c8d3bb8ed348cb33af1afec1540030f1c893f98a7dfa7527e435081becd",
            "e4e9974c8bb77c1e6fbe06db3104cfbc1e75eddd981d0cd9f020c6db7aa0d0d3",
            "cdbccfb7b7c445d27226aa3d76982b7c852c59945f3ec337cdcfdbb9d3c29214",
            "769801393e51285b485e0dc26425ceb7bb1e43a4f769c270720ee95244f0131b",
            "0c593a450f2cca51bd29198e6c896139bf9e88d90b67aebc587047268cd1e300",
            "8bf0aebf1ce0fdc1c4325c81a2c327ec24be8b63d567dc7d6592b6a83075aae0",
            "a8a37cd9ebf83637962e84a13b929c9279e0fb79736fd60b692091ce43f86661",
            "d73a02a24875919cec4c06e4bc7c7a20f5da9be2dccd1754820be5994ef93410",
        ];
        for (n, w) in (1..=9).zip(want) {
            assert_eq!(hex(&root(&ps(n)).unwrap().unwrap()), w, "n = {n}");
        }
        // Leaf order is (unit, layers), whatever order the list comes in.
        let mut rev = ps(7);
        rev.reverse();
        assert_eq!(root(&rev).unwrap(), root(&ps(7)).unwrap());
        assert_eq!(root(&[]).unwrap(), None);
    }

    #[test]
    fn proof_roundtrip() {
        for n in 1..=33usize {
            let p = ps(n);
            let c = commit(&p).unwrap().unwrap();
            assert_eq!(c, OutputCommitment { root: root(&p).unwrap().unwrap(), leaf_count: n as u64 });
            let v = ordered(&p).unwrap();
            for i in 0..n {
                let path = proof(&p, i).unwrap();
                let l = leaf(&v[i]);
                assert!(verify_proof(l, i as u64, &path, &c), "n = {n}, i = {i}");
                // A flipped bit anywhere or a wrong index fails.
                let mut bad = l;
                bad[0] ^= 1;
                assert!(!verify_proof(bad, i as u64, &path, &c));
                if n > 1 {
                    assert!(!verify_proof(l, ((i + 1) % n) as u64, &path, &c), "n = {n}, i = {i}");
                    let mut p2 = path.clone();
                    p2[0][31] ^= 0x80;
                    assert!(!verify_proof(l, i as u64, &p2, &c));
                }
            }
            assert_eq!(proof(&p, n), Err(TreeError::IndexOutOfRange));
        }
    }

    #[test]
    fn a_proof_verifies_only_under_the_committed_leaf_count() {
        // An audit path does not fix the tree's size: RFC 9162's check walks it against
        // whatever size it is given. So a claim commits to (root, leaf_count), and the
        // size a proof is checked under is the commitment's.
        let p = ps(7);
        let c = commit(&p).unwrap().unwrap();
        assert_eq!(c.leaf_count, 7);
        let v = ordered(&p).unwrap();
        let paths: Vec<_> = (0..7).map(|i| proof(&p, i).unwrap()).collect();
        // A 7-leaf proof does not verify against the commitment to 8 leaves, whose root
        // differs.
        let c8 = commit(&ps(8)).unwrap().unwrap();
        assert_ne!(c8.root, c.root);
        for i in 0..7 {
            assert!(verify_proof(leaf(&v[i]), i as u64, &paths[i], &c));
            assert!(!verify_proof(leaf(&v[i]), i as u64, &paths[i], &c8), "i = {i}");
        }
        // Why the count is committed: under this root with 8 stated as its size, leaf 0's
        // path still walks to the root (MTH(D[4:7]) stands where MTH(D[4:8]) would), and
        // only leaf 6's is refused. A root alone would let the proof's holder pick the size.
        let as8 = OutputCommitment { leaf_count: 8, ..c };
        assert!(verify_proof(leaf(&v[0]), 0, &paths[0], &as8));
        assert!(!verify_proof(leaf(&v[6]), 6, &paths[6], &as8));
    }

    /// Every prefix of trees of 1 to 33 leaves is proved consistent with the whole, and a
    /// flipped bit, a rewritten history or the next tree's root is refused. A proof does
    /// not fix the second tree's size, as an audit path does not (Appendix C): the 1-to-3
    /// proof also walks to the 3-leaf root under a stated size of 4, so a commitment states
    /// its size and a holder of the leaves recomputes the root under it.
    #[test]
    fn consistency_proofs_roundtrip() {
        let leaves: Vec<[u8; 32]> = (0..34u8).map(|i| sha256(&[b'c', i])).collect();
        let three = tree_hash(&leaves[..3]);
        let p13 = consistency_proof(1, &leaves[..3]);
        assert!(verify_consistency(1, 4, &leaves[0], &three, &p13), "a proof does not fix the size");
        for n in 2..=33usize {
            let d = &leaves[..n];
            let second = tree_hash(d);
            let next = tree_hash(&leaves[..n + 1]);
            for m in 1..n {
                let first = tree_hash(&d[..m]);
                let p = consistency_proof(m, d);
                assert!(verify_consistency(m as u64, n as u64, &first, &second, &p), "m = {m}, n = {n}");
                assert!(!verify_consistency(m as u64, n as u64 + 1, &first, &next, &p), "m = {m}, n = {n}, next tree");
                let mut bad = p.clone();
                bad[0][7] ^= 0x10;
                assert!(!verify_consistency(m as u64, n as u64, &first, &second, &bad), "m = {m}, n = {n}, bit");
                let mut other = d.to_vec();
                other[0][0] ^= 1;
                let rewritten = tree_hash(&other);
                assert!(!verify_consistency(m as u64, n as u64, &first, &rewritten, &p), "m = {m}, n = {n}, history");
            }
            assert!(consistency_proof(0, d).is_empty() && consistency_proof(n, d).is_empty());
        }
    }

    /// The range proof of every run of leaves of trees of 1 to 33 leaves verifies; a run
    /// of one leaf is its RFC 6962 audit path, node for node, and RFC 9162 §2.1.3.2's check
    /// (`verify_proof`) gives the same answer over it as the range check does, whatever is
    /// changed; and a flipped bit, a node added or dropped, a leaf replaced, the run moved,
    /// or the next tree's root under the next size is refused.
    #[test]
    fn range_proofs_generalise_the_audit_path() {
        let leaves: Vec<[u8; 32]> = (0..34u8).map(|i| sha256(&[b'r', i])).collect();
        for n in 1..=33usize {
            let d = &leaves[..n];
            let c = OutputCommitment { root: tree_hash(d), leaf_count: n as u64 };
            let next = OutputCommitment { root: tree_hash(&leaves[..n + 1]), leaf_count: n as u64 + 1 };
            for a in 0..n {
                let path = audit_path(a, d).unwrap();
                assert_eq!(range_proof(a, a + 1, d).unwrap(), path, "n = {n}, a = {a}");
                assert!(verify_proof(d[a], a as u64, &path, &c));
                assert!(verify_range(a as u64, &d[a..a + 1], &path, &c));
                // The two checks agree on every single-leaf change.
                let mut bad = path.clone();
                if let Some(x) = bad.first_mut() {
                    x[3] ^= 0x40;
                    assert_eq!(verify_proof(d[a], a as u64, &bad, &c), verify_range(a as u64, &d[a..a + 1], &bad, &c));
                    assert!(!verify_range(a as u64, &d[a..a + 1], &bad, &c));
                }
                let other = sha256(b"not a leaf");
                assert_eq!(verify_proof(other, a as u64, &path, &c), verify_range(a as u64, &[other], &path, &c));
                for b in a + 1..=n {
                    let p = range_proof(a, b, d).unwrap();
                    let run = &d[a..b];
                    assert!(verify_range(a as u64, run, &p, &c), "n = {n}, [{a}, {b})");
                    assert!(p.len() <= 2 * (usize::BITS - (n - 1).leading_zeros()) as usize, "n = {n}, [{a}, {b}): {} nodes", p.len());
                    assert!(!verify_range(a as u64, run, &p, &next), "n = {n}, [{a}, {b}), next tree");
                    let mut extra = p.clone();
                    extra.push([0; 32]);
                    assert!(!verify_range(a as u64, run, &extra, &c), "a node left over");
                    if !p.is_empty() {
                        let mut flipped = p.clone();
                        let last = flipped.len() - 1;
                        flipped[last][0] ^= 1;
                        assert!(!verify_range(a as u64, run, &flipped, &c), "n = {n}, [{a}, {b}), bit");
                        assert!(!verify_range(a as u64, run, &p[..last], &c), "a node dropped");
                    }
                    let mut swapped = run.to_vec();
                    swapped[run.len() / 2][31] ^= 2;
                    assert!(!verify_range(a as u64, &swapped, &p, &c), "n = {n}, [{a}, {b}), leaf");
                    if b < n {
                        assert!(!verify_range(a as u64 + 1, run, &p, &c), "n = {n}, [{a}, {b}), moved");
                    }
                }
            }
            assert_eq!(range_proof(0, 0, d), None);
            assert_eq!(range_proof(0, n + 1, d), None);
            assert!(!verify_range(0, &[], &[], &c));
            assert!(!verify_range(n as u64, &[d[0]], &[], &c));
            assert!(!verify_range(u64::MAX, &[d[0]], &[], &c));
            // The whole tree needs no node: its root is the leaves' tree hash.
            assert!(range_proof(0, n, d).unwrap().is_empty());
        }
    }

    /// The nodes of a range proof are nodes some audit path of a leaf in the range holds:
    /// it proves no more than the audit paths of its leaves do, with the nodes they share
    /// written once and those the run's own leaves give left out.
    #[test]
    fn a_range_proof_is_drawn_from_its_leaves_audit_paths() {
        let leaves: Vec<[u8; 32]> = (0..21u8).map(|i| sha256(&[b'p', i])).collect();
        for n in 1..=21usize {
            let d = &leaves[..n];
            for a in 0..n {
                for b in a + 1..=n {
                    let union: BTreeSet<[u8; 32]> = (a..b).flat_map(|i| audit_path(i, d).unwrap()).collect();
                    for x in range_proof(a, b, d).unwrap() {
                        assert!(union.contains(&x), "n = {n}, [{a}, {b})");
                    }
                }
            }
        }
    }

    #[test]
    fn duplicate_presentation_is_refused() {
        let mut p = ps(4);
        p.push(Presentation { decoder: 1, ..p[2] });
        assert_eq!(root(&p), Err(TreeError::Duplicate { unit: 2, layers: 3 }));
    }
}
