//! Amounts of funds, and nonzero amounts per account committed with a binary Merkle tree. use super::{Amount, Lookup}; use bytes::BufMut; use commonware_codec::{Buf, EncodeSize, Error as CodecError, RangeCfg, Read, Write}; use commonware_cryptography::{Digest, Hasher, PublicKey}; use commonware_storage::bmt::{Builder, Tree}; use commonware_utils::Widen; use core::cmp::Ordering; use thiserror::Error; /// Why entries do not form amounts, or two amounts do not add up. #[derive(Debug, Error)] pub enum AmountsError { /// An amount is zero. #[error("amount is zero")] ZeroAmount, /// An account appears more than once. #[error("account appears more than once")] Duplicate, /// There are more entries than a tree can commit to. #[error("too many entries")] TooManyEntries, /// A sum overflows. #[error("arithmetic overflow")] Overflow, } /// Computes the leaf committing to `amount` for `account`, encoding the amount into `scratch`. fn leaf_with( account: &P, amount: A, scratch: &mut Vec, ) -> H::Digest { scratch.clear(); amount.write(scratch); H::hash(&[account.as_ref(), scratch]) } /// Computes the leaf committing to `amount` for `account`. pub(crate) fn leaf(account: &P, amount: A) -> H::Digest { leaf_with::(account, amount, &mut Vec::with_capacity(A::SIZE)) } /// Nonzero amounts per account, sorted by account. /// /// Their root ([Amounts::root]) is the root of a binary Merkle tree whose leaves are the `(account, /// amount)` entries in account order. Each leaf is bound to its position, so a [Lookup] of two /// adjacent entries proves that an account between them has no amount, and the first entry alone /// proves the same for an account before it. The root also binds the number of entries, so the last /// entry alone proves the same for an account after it. #[derive(Clone, Debug, PartialEq, Eq, Hash)] pub struct Amounts { entries: Vec<(P, A)>, } impl Default for Amounts { fn default() -> Self { Self::empty() } } impl Amounts { /// Returns amounts with no entries. pub const fn empty() -> Self { Self { entries: Vec::new(), } } /// Collects `entries` in account order. pub fn new(entries: impl IntoIterator) -> Result { let mut entries: Vec<_> = entries.into_iter().collect(); entries.sort_unstable_by(|(a, _), (b, _)| a.cmp(b)); Self::from_sorted(entries) } /// Wraps `entries` already in account order. pub(crate) fn from_sorted(entries: Vec<(P, A)>) -> Result { let widest: usize = Widen::widen(u32::MAX); if entries.len() > widest { return Err(AmountsError::TooManyEntries); } if entries.iter().any(|(_, amount)| *amount == A::ZERO) { return Err(AmountsError::ZeroAmount); } if entries.windows(2).any(|pair| pair[0].0 >= pair[1].0) { return Err(AmountsError::Duplicate); } Ok(Self { entries }) } /// Returns whether there are no entries. pub const fn is_empty(&self) -> bool { self.entries.is_empty() } /// Returns the number of accounts with an amount. pub const fn len(&self) -> usize { self.entries.len() } /// Returns the amount of `account`, or zero if it has none. pub fn get(&self, account: &P) -> A { self.position(account) .map_or(A::ZERO, |position| self.entries[position].1) } /// Iterates over the entries in account order. pub fn iter(&self) -> impl ExactSizeIterator { self.entries .iter() .map(|(account, amount)| (account, *amount)) } /// Returns the sum of all amounts, or `None` if it overflows. pub fn total(&self) -> Option { self.entries .iter() .try_fold(A::ZERO, |total, (_, amount)| total.checked_add(*amount)) } /// Returns the amounts with `other` added entry by entry. pub fn combine(&self, other: &Self) -> Result { let mut entries = Vec::with_capacity(self.entries.len() + other.entries.len()); let mut left = self.entries.iter().peekable(); let mut right = other.entries.iter().peekable(); loop { let entry = match (left.peek(), right.peek()) { (None, None) => break, (Some(_), None) => left.next().cloned(), (None, Some(_)) => right.next().cloned(), (Some((a, x)), Some((b, y))) => match a.cmp(b) { Ordering::Less => left.next().cloned(), Ordering::Greater => right.next().cloned(), Ordering::Equal => { let sum = x.checked_add(*y).ok_or(AmountsError::Overflow)?; let account = a.clone(); left.next(); right.next(); Some((account, sum)) } }, }; entries.extend(entry); } Self::from_sorted(entries) } /// Returns the position of `account` among the entries in account order, or `None` if it has /// no amount. pub fn position(&self, account: &P) -> Option { self.entries .binary_search_by(|(candidate, _)| candidate.cmp(account)) .ok() } /// Builds the tree committing to the entries. pub(crate) fn tree(&self) -> Tree { let mut builder = Builder::::new(self.entries.len()); let mut scratch = Vec::with_capacity(A::SIZE); for (account, amount) in &self.entries { builder.add(&leaf_with::(account, *amount, &mut scratch)); } builder.build() } /// Returns the commitment to the entries. pub fn root(&self) -> H::Digest { self.tree::().root() } /// Opens the amount of `account` under `tree`. The tree must come from [Self::tree]. pub(crate) fn lookup(&self, tree: &Tree, account: &P) -> Lookup { Lookup::new(&self.entries, tree, account) } } impl Write for Amounts { fn write(&self, buf: &mut impl BufMut) { self.entries.write(buf); } } impl EncodeSize for Amounts { fn encode_size(&self) -> usize { self.entries.encode_size() } } impl Read for Amounts { /// The accepted number of entries. type Cfg = RangeCfg; fn read_cfg(buf: &mut impl Buf, range: &Self::Cfg) -> Result { let entries = Vec::<(P, A)>::read_cfg(buf, &(*range, ((), ())))?; Self::from_sorted(entries).map_err(|_| { CodecError::Invalid( "clearing::bajillion::Amounts", "entries must be strictly increasing by account with nonzero amounts", ) }) } } #[cfg(feature = "arbitrary")] impl arbitrary::Arbitrary<'_> for Amounts where P: for<'a> arbitrary::Arbitrary<'a>, A: for<'a> arbitrary::Arbitrary<'a>, { fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result { let mut entries: Vec<(P, A)> = u.arbitrary()?; entries.retain(|(_, amount)| *amount != A::ZERO); entries.sort_by(|(a, _), (b, _)| a.cmp(b)); entries.dedup_by(|(a, _), (b, _)| a == b); Ok(Self { entries }) } } /// Draws arbitrary amounts that pay at least one account. #[cfg(feature = "arbitrary")] pub(crate) fn arbitrary_nonempty( u: &mut arbitrary::Unstructured<'_>, ) -> arbitrary::Result> where P: PublicKey + for<'a> arbitrary::Arbitrary<'a>, A: Amount + for<'a> arbitrary::Arbitrary<'a>, { let amounts = u.arbitrary::>()?; if amounts.is_empty() { return Err(arbitrary::Error::IncorrectFormat); } Ok(amounts) } #[cfg(test)] mod tests { use super::*; use crate::bajillion::tests::accounts; use commonware_codec::{Decode as _, Encode as _, U256}; use commonware_cryptography::{Sha256, ed25519::PublicKey}; type TestAmounts = Amounts; /// Building amounts sorts the entries by account. An account reads back its amount and /// position, or zero and no position when it has no amount. #[test] fn test_new_sorts_entries() { let keys = accounts(4); let amounts = TestAmounts::new([ (keys[2].clone(), 3), (keys[0].clone(), 1), (keys[1].clone(), 2), ]) .unwrap(); let entries: Vec<_> = amounts .iter() .map(|(key, amount)| (key.clone(), amount)) .collect(); assert_eq!( entries, vec![ (keys[0].clone(), 1), (keys[1].clone(), 2), (keys[2].clone(), 3) ] ); assert_eq!(amounts.len(), 3); assert_eq!(amounts.total(), Some(6)); assert_eq!(amounts.get(&keys[1]), 2); assert_eq!(amounts.get(&keys[3]), 0); assert_eq!(amounts.position(&keys[2]), Some(2)); assert_eq!(amounts.position(&keys[3]), None); } /// Zero amounts and repeated accounts are refused, and no entries form the empty amounts. #[test] fn test_new_rejects_invalid_entries() { let keys = accounts(2); assert!(matches!( TestAmounts::new([(keys[0].clone(), 0)]), Err(AmountsError::ZeroAmount) )); assert!(matches!( TestAmounts::new([(keys[0].clone(), 1), (keys[0].clone(), 2)]), Err(AmountsError::Duplicate) )); assert!(TestAmounts::new([]).unwrap().is_empty()); } /// Combining adds amounts per account in either order and refuses a sum that overflows. #[test] fn test_combine() { let keys = accounts(3); let left = TestAmounts::new([(keys[0].clone(), 1), (keys[1].clone(), 2)]).unwrap(); let right = TestAmounts::new([(keys[1].clone(), 3), (keys[2].clone(), 4)]).unwrap(); let combined = left.combine(&right).unwrap(); assert_eq!(combined, right.combine(&left).unwrap()); assert_eq!( combined, TestAmounts::new([ (keys[0].clone(), 1), (keys[1].clone(), 5), (keys[2].clone(), 4) ]) .unwrap() ); assert_eq!(left.combine(&TestAmounts::empty()).unwrap(), left); let full = TestAmounts::new([(keys[0].clone(), u64::MAX)]).unwrap(); let one = TestAmounts::new([(keys[0].clone(), 1)]).unwrap(); assert!(matches!(full.combine(&one), Err(AmountsError::Overflow))); let overflowing = TestAmounts::new([(keys[0].clone(), u64::MAX), (keys[1].clone(), 1)]); assert_eq!(overflowing.unwrap().total(), None); } /// A leaf hashes the account and the amount's big-endian encoding, for primitive and wide /// amounts alike. #[test] fn test_leaf_hashes_account_and_big_endian_amount() { let key = &accounts(1)[0]; assert_eq!( leaf::(key, 5), Sha256::hash(&[key.as_ref(), &5u64.to_be_bytes()]) ); assert_eq!( leaf::(key, 5), Sha256::hash(&[key.as_ref(), &5u128.to_be_bytes()]) ); let mut five = [0u8; 32]; five[31] = 5; assert_eq!( leaf::(key, U256::from(5)), Sha256::hash(&[key.as_ref(), &five]) ); } /// The root changes with every account, every amount, and the number of entries. #[test] fn test_root_commits_to_entries() { let keys = accounts(2); let empty = TestAmounts::empty(); assert_eq!( empty.root::(), Builder::::new(0).build().root() ); let one = TestAmounts::new([(keys[0].clone(), 1)]).unwrap(); let roots = [ empty.root::(), one.root::(), TestAmounts::new([(keys[0].clone(), 2)]) .unwrap() .root::(), TestAmounts::new([(keys[1].clone(), 1)]) .unwrap() .root::(), one.combine(&TestAmounts::new([(keys[1].clone(), 1)]).unwrap()) .unwrap() .root::(), ]; for (i, a) in roots.iter().enumerate() { for b in &roots[i + 1..] { assert_ne!(a, b); } } } /// Every account, present or absent, opens to its amount under the root. #[test] fn test_lookup() { let keys = accounts(5); let amounts = TestAmounts::new([(keys[1].clone(), 10), (keys[3].clone(), 30)]).unwrap(); let root = amounts.root::(); let tree = amounts.tree::(); for key in &keys { let lookup = amounts.lookup(&tree, key); let value = lookup .verify::(&root, key, |key, amount| leaf::(key, *amount)) .unwrap() .copied(); assert_eq!(value.unwrap_or(0), amounts.get(key)); } } /// Decoding refuses unsorted, repeated, and zero entries, and more entries than the limit. #[test] fn test_decode_rejects_non_canonical_entries() { let keys = accounts(2); let range = RangeCfg::new(..=8); for entries in [ vec![(keys[1].clone(), 1u64), (keys[0].clone(), 1)], vec![(keys[0].clone(), 1), (keys[0].clone(), 2)], vec![(keys[0].clone(), 0)], ] { assert!(TestAmounts::decode_cfg(entries.encode(), &range).is_err()); } let amounts = TestAmounts::new([(keys[0].clone(), 1), (keys[1].clone(), 2)]).unwrap(); let encoded = amounts.encode(); assert_eq!( TestAmounts::decode_cfg(encoded.clone(), &range).unwrap(), amounts ); assert!(TestAmounts::decode_cfg(encoded, &RangeCfg::new(..=1)).is_err()); } #[cfg(feature = "arbitrary")] mod conformance { use super::*; use commonware_codec::conformance::CodecConformance; commonware_conformance::conformance_tests! { CodecConformance>, } } }