//! The payment matrix a close settles. use super::{Amount, Amounts, InvalidOpening, Lookup, amounts}; use bytes::BufMut; use commonware_codec::{Buf, EncodeSize, Error as CodecError, Read, ReadExt, Write}; use commonware_cryptography::{Digest, Hasher, PublicKey}; use commonware_storage::bmt::{Builder, Tree}; use commonware_utils::Widen; use core::fmt::{self, Debug, Formatter}; use std::sync::{Arc, OnceLock}; /// Computes the leaf committing to `sender`'s payment map with root `payments`. fn leaf(sender: &P, payments: &H::Digest) -> H::Digest { H::hash(&[sender.as_ref(), payments.as_ref()]) } /// Builds the tree over rows that are strictly increasing by sender. fn tree<'a, H: Hasher, P: PublicKey>( rows: impl ExactSizeIterator, ) -> Tree { let mut builder = Builder::::new(rows.len()); for (sender, payments) in rows { builder.add(&leaf::(sender, payments)); } builder.build() } /// Computes the root of the matrix with rows that are strictly increasing by sender. pub(crate) fn root<'a, H: Hasher, P: PublicKey>( rows: impl ExactSizeIterator, ) -> H::Digest { tree::(rows).root() } /// The payment maps a close settles, one row per sender. /// /// The matrix commits to a binary Merkle tree of `(sender, payment map root)` leaves in sender /// order, and opens rows with the hasher `H` that committed it. An [Opening] proves what one /// sender paid one receiver, or that it paid nothing. Clones share the rows. pub struct Matrix { inner: Arc>, } struct Inner { /// Senders and the roots of their payment maps, in sender order. rows: Vec<(P, H::Digest)>, /// Payment maps aligned with `rows`. payments: Vec>, /// Trees over the payment maps, built the first time a row is opened. trees: Vec>>, /// Tree over the leaves of `rows`. tree: Tree, } // The hasher is a type parameter only, so the derived traits would bound it. impl Clone for Matrix { fn clone(&self) -> Self { Self { inner: self.inner.clone(), } } } impl Debug for Matrix { fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { f.debug_struct("Matrix") .field("rows", &self.inner.rows) .field("payments", &self.inner.payments) .finish() } } impl Matrix { /// Returns the matrix with no rows. pub fn empty() -> Self { Self::from_sorted(Vec::new()) } /// Builds a matrix from rows that are strictly increasing by sender, each with a nonempty /// payment map and that map's root. pub(crate) fn from_sorted(rows: Vec<(P, Amounts, H::Digest)>) -> Self { let (rows, payments): (Vec<_>, Vec<_>) = rows .into_iter() .map(|(sender, payments, root)| ((sender, root), payments)) .unzip(); let tree = tree::(rows.iter().map(|(sender, root)| (sender, root))); let trees = rows.iter().map(|_| OnceLock::new()).collect(); Self { inner: Arc::new(Inner { rows, payments, trees, tree, }), } } /// Returns the commitment to the matrix. pub fn root(&self) -> H::Digest { self.inner.tree.root() } /// Returns the number of senders with a row. pub fn len(&self) -> usize { self.inner.rows.len() } /// Returns whether no sender has a row. pub fn is_empty(&self) -> bool { self.inner.rows.is_empty() } /// Iterates over every sender's payment map, in sender order. pub fn iter(&self) -> impl ExactSizeIterator)> { self.inner .rows .iter() .zip(&self.inner.payments) .map(|((sender, _), payments)| (sender, payments)) } /// Returns every sender and the root of its payment map, in sender order. pub(crate) fn rows(&self) -> &[(P, H::Digest)] { &self.inner.rows } /// Returns the index of `sender`'s row. fn position(&self, sender: &P) -> Option { self.inner .rows .binary_search_by(|(candidate, _)| candidate.cmp(sender)) .ok() } /// Returns `sender`'s payment map, if it has a row. pub fn payments(&self, sender: &P) -> Option<&Amounts> { self.position(sender) .map(|position| &self.inner.payments[position]) } /// Returns the root of `sender`'s payment map, if it has a row. pub fn payments_root(&self, sender: &P) -> Option { self.position(sender) .map(|position| self.inner.rows[position].1) } /// Opens the amount `sender` paid `receiver`, proving that it paid nothing if it did not. /// /// An opening reveals the payment it opens. When it proves that payment absent, it reveals the /// sender's payments to the receivers on either side or, for a sender without a row, the /// senders on either side and the roots of their payment maps. pub fn open(&self, sender: &P, receiver: &P) -> Opening { let row = Lookup::new(&self.inner.rows, &self.inner.tree, sender); let entry = match &row { Lookup::Member { position, .. } => { let position: usize = Widen::widen(*position); let payments = &self.inner.payments[position]; let tree = self.inner.trees[position].get_or_init(|| payments.tree::()); Some(payments.lookup(tree, receiver)) } Lookup::NonMember { .. } => None, }; Opening { row, entry } } } /// Opening of the amount one sender paid one receiver under a [Matrix] root. #[derive(Clone, Debug, PartialEq, Eq)] pub struct Opening { /// Opening of the sender's row, binding the root of its payment map if it has one. pub row: Lookup, /// Opening of the receiver's entry under the root of the sender's payment map, present if and /// only if the sender has a row. pub entry: Option>, } impl Opening { /// Verifies the opening of `sender`'s row under the matrix root `root`. /// /// Returns the root of `sender`'s payment map, or `None` if it has no row. pub fn verify_row>( &self, root: &D, sender: &P, ) -> Result, InvalidOpening> { let row = self .row .verify::(root, sender, |sender, payments| { leaf::(sender, payments) })? .copied(); if row.is_some() != self.entry.is_some() { return Err(InvalidOpening); } Ok(row) } /// Verifies the opening under the matrix root `root`. /// /// Returns the amount `sender` paid `receiver`, or zero if it paid nothing. pub fn verify>( &self, root: &D, sender: &P, receiver: &P, ) -> Result { let (Some(payments), Some(entry)) = (self.verify_row::(root, sender)?, &self.entry) else { return Ok(A::ZERO); }; let amount = entry.verify::(&payments, receiver, |receiver, amount| { amounts::leaf::(receiver, *amount) })?; Ok(amount.copied().unwrap_or(A::ZERO)) } } impl Write for Opening { fn write(&self, buf: &mut impl BufMut) { self.row.write(buf); self.entry.write(buf); } } impl EncodeSize for Opening { fn encode_size(&self) -> usize { self.row.encode_size() + self.entry.encode_size() } } impl Read for Opening { type Cfg = (); fn read_cfg(buf: &mut impl Buf, _: &()) -> Result { Ok(Self { row: Lookup::read(buf)?, entry: Option::>::read(buf)?, }) } } #[cfg(feature = "arbitrary")] impl arbitrary::Arbitrary<'_> for Opening where P: for<'a> arbitrary::Arbitrary<'a>, D: for<'a> arbitrary::Arbitrary<'a>, A: for<'a> arbitrary::Arbitrary<'a>, { fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result { Ok(Self { row: u.arbitrary()?, entry: u.arbitrary()?, }) } } #[cfg(test)] mod tests { use super::*; use crate::bajillion::tests::accounts; use commonware_codec::{DecodeExt as _, Encode as _}; use commonware_cryptography::{Sha256, ed25519::PublicKey}; /// Returns the payment map paying each `(receiver, amount)`. fn payments(entries: &[(&PublicKey, u64)]) -> Amounts { Amounts::new( entries .iter() .map(|(key, amount)| ((*key).clone(), *amount)), ) .unwrap() } /// Returns the matrix of `rows`. Their senders must strictly increase. fn matrix(rows: &[(PublicKey, Amounts)]) -> Matrix { Matrix::<_, Sha256, _>::from_sorted( rows.iter() .map(|(sender, payments)| { (sender.clone(), payments.clone(), payments.root::()) }) .collect(), ) } /// Every sender and receiver pair opens to the amount paid, or zero, and every sender to the /// root of its row, or to no row. #[test] fn test_opens_every_pair() { let keys = accounts(6); let rows = [ (keys[1].clone(), payments(&[(&keys[0], 5), (&keys[4], 7)])), (keys[3].clone(), payments(&[(&keys[1], 1)])), (keys[4].clone(), payments(&[(&keys[4], 2), (&keys[5], 3)])), ]; let matrix = matrix(&rows); let root = matrix.root(); assert_eq!(matrix.len(), 3); assert!(!matrix.is_empty()); for sender in &keys { let payments = rows .iter() .find(|(candidate, _)| candidate == sender) .map(|(_, payments)| payments); assert_eq!(matrix.payments(sender), payments); for receiver in &keys { let opening = matrix.open(sender, receiver); let expected = payments.map_or(0, |payments| payments.get(receiver)); assert_eq!( opening.verify::(&root, sender, receiver).unwrap(), expected ); assert_eq!( opening.verify_row::(&root, sender).unwrap(), payments.map(Amounts::root::) ); assert_eq!(Opening::decode(opening.encode()).unwrap(), opening); } } let empty = Matrix::::empty(); assert!(empty.is_empty()); let opening = empty.open(&keys[0], &keys[1]); assert_eq!( opening .verify::(&empty.root(), &keys[0], &keys[1]) .unwrap(), 0 ); } /// An opening verifies with an entry from the sender's own row exactly when the sender has a /// row, and an opening of a payment verifies only under its own root and for its own pair. #[test] fn test_rejects_inconsistent_openings() { let keys = accounts(4); let matrix = matrix(&[ (keys[1].clone(), payments(&[(&keys[0], 5)])), (keys[3].clone(), payments(&[(&keys[0], 1)])), ]); let root = matrix.root(); // A sender with a row must open the receiver's entry, and a sender without one must not. let present = matrix.open(&keys[1], &keys[0]); let absent = matrix.open(&keys[2], &keys[0]); for (sender, opening) in [ ( &keys[1], Opening { row: present.row.clone(), entry: None, }, ), ( &keys[2], Opening { row: absent.row, entry: present.entry.clone(), }, ), ] { assert!(matches!( opening.verify::(&root, sender, &keys[0]), Err(InvalidOpening) )); } // A sender that pays cannot be shown to have no row by opening only the row before it. let forged = Opening::<_, _, u64> { row: Lookup::NonMember { position: 1, lower: Some(matrix.inner.rows[0].clone()), upper: None, proof: matrix.inner.tree.proof(0).unwrap(), }, entry: None, }; assert!(matches!( forged.verify::(&root, &keys[3], &keys[0]), Err(InvalidOpening) )); // The entry must open under the sender's own row. let other = matrix.open(&keys[3], &keys[0]); let swapped = Opening { row: present.row.clone(), entry: other.entry, }; assert!(matches!( swapped.verify::(&root, &keys[1], &keys[0]), Err(InvalidOpening) )); // An opening of a payment verifies only under its own root and for its own pair. let other_root = Matrix::::empty().root(); assert!( present .verify::(&other_root, &keys[1], &keys[0]) .is_err() ); assert!(present.verify::(&root, &keys[3], &keys[0]).is_err()); assert!(present.verify::(&root, &keys[1], &keys[2]).is_err()); } #[cfg(feature = "arbitrary")] mod conformance { use super::*; use commonware_codec::conformance::CodecConformance; use commonware_cryptography::sha256::Digest; commonware_conformance::conformance_tests! { CodecConformance>, } } }