//! Summaries of closes, certified by validators and posted to the ledger. use super::{Amount, Epoch, Namespace, Payout, matrix}; use bytes::{BufMut, Bytes}; use commonware_codec::{ Buf, Encode, EncodeSize, Error as CodecError, FixedSize, Read, ReadExt, Write, varint::UInt, }; use commonware_cryptography::{ Digest, Digestible, Hasher, PublicKey, certificate::{self, Verifier}, }; use commonware_parallel::Strategy; use commonware_storage::{ merkle::{Location, mmr}, qmdb::{chain::Commitment, keyless, value::FixedEncoding}, }; use commonware_utils::Widen; use core::{ fmt::{self, Debug, Formatter}, ops::RangeInclusive, }; use rand_core::CryptoRng; use thiserror::Error; /// A ledger queue's requests that one close processes, as their count and the queue's running hash. /// /// `hash` extends the parent summary's hash by `H(hash || request)` for each request's encoding in /// queue order, so it covers every request the queue has processed since genesis. #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] pub struct Processed { /// Number of queued requests the close processes. pub count: u64, /// Running hash of the queue after the close, over every request the queue has processed. pub hash: D, } impl Processed { /// Returns the record of a close that processes `requests` after the close `self` records. Its /// count is the length of `requests`, and its hash extends `self`'s hash over them. pub(crate) fn next, R: Write + FixedSize>(&self, requests: &[R]) -> Self { let mut encoded = Vec::with_capacity(R::SIZE); let hash = requests.iter().fold(self.hash, |hash, request| { encoded.clear(); request.write(&mut encoded); H::hash(&[hash.as_ref(), &encoded]) }); Self { count: Widen::widen(requests.len()), hash, } } } impl Write for Processed { fn write(&self, buf: &mut impl BufMut) { UInt(self.count).write(buf); self.hash.write(buf); } } impl EncodeSize for Processed { fn encode_size(&self) -> usize { UInt(self.count).encode_size() + self.hash.encode_size() } } impl Read for Processed { type Cfg = (); fn read_cfg(buf: &mut impl Buf, _: &()) -> Result { Ok(Self { count: UInt::read(buf)?.into(), hash: D::read(buf)?, }) } } #[cfg(feature = "arbitrary")] impl arbitrary::Arbitrary<'_> for Processed where D: for<'a> arbitrary::Arbitrary<'a>, { fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result { Ok(Self { count: u.arbitrary()?, hash: u.arbitrary()?, }) } } /// Why the ledger refuses a post. #[derive(Debug, Error)] pub enum SummaryError { /// The summary is for another epoch. #[error("wrong epoch: expected {expected}, found {found}")] WrongEpoch { /// The epoch whose close the ledger expects. expected: Epoch, /// The epoch of the summary. found: Epoch, }, /// The summary does not follow the last posted one. #[error("summary does not follow the last posted one")] WrongParent, /// A count is outside the range given. #[error("invalid number of queued requests")] InvalidCount, /// The certificate does not verify. #[error("invalid certificate")] InvalidCertificate, } /// The effects of one close, as certified by validators and posted to the ledger. /// /// A summary's digest ([Digestible]) is what the next summary names as its parent, so the hasher /// `H` is part of the type. A certificate scheme over summaries comes from the certificate macros /// of `commonware_cryptography` and names the hasher along with the signature scheme and its fault /// model: /// /// ``` /// mod scheme { /// use commonware_clearing::bajillion::{Namespace, Summary}; /// use commonware_cryptography::{Sha256, impl_certificate_ed25519}; /// use commonware_utils::N3f1; /// /// impl_certificate_ed25519!(&'a Summary, Namespace, N3f1); /// } /// ``` pub struct Summary { /// Epoch the close finalizes. pub epoch: Epoch, /// Digest of the summary of the previous close. pub parent: H::Digest, /// Root of the payment matrix the close settles. pub matrix: H::Digest, /// Root of the balances after the close. pub balances: H::Digest, /// The payout log after the close, as its size and root. Each posted close appends its payouts /// to the [Payouts](super::Payouts) database in account order, then a commit, and the size /// counts the initial commit, so the close's commit sits at `size - 1`. pub payouts: Commitment, /// The deposits the close processes, as their count and the queue's running hash. pub deposits: Processed, /// The forced withdrawals the close processes, as their count and the queue's running hash. pub forced_withdrawals: Processed, } impl Summary { /// Returns the summary of the state before the first close, with balances committed by /// `balances`, accounts of type `P`, and amounts of type `A`. Both running hashes start at all /// zeros, and the payout log holds only its initial commit. pub fn genesis(balances: H::Digest) -> Self { let start = Processed { count: 0, hash: H::Digest::EMPTY, }; Self { epoch: 0, parent: H::Digest::EMPTY, matrix: matrix::root::(core::iter::empty()), balances, payouts: Commitment { size: Location::new(1), root: keyless::initial_root::>, H>(), }, deposits: start, forced_withdrawals: start, } } /// Checks that a ledger expecting the close of `epoch` after the post with digest `parent` may /// post this summary under `certificate`. `deposits` and `forced_withdrawals` each range from /// the queue's required count to its length. /// /// The certificate is checked last, and it alone vouches for the matrix and balances roots, /// the payouts size and root, and the running hashes. #[allow(clippy::too_many_arguments)] pub fn verify( &self, rng: &mut R, verifier: &V, certificate: &V::Certificate, epoch: Epoch, parent: &H::Digest, deposits: RangeInclusive, forced_withdrawals: RangeInclusive, strategy: &impl Strategy, ) -> Result<(), SummaryError> where V: for<'a> Verifier = &'a Self>, R: CryptoRng, { if self.epoch != epoch { return Err(SummaryError::WrongEpoch { expected: epoch, found: self.epoch, }); } if self.parent != *parent { return Err(SummaryError::WrongParent); } if !deposits.contains(&self.deposits.count) || !forced_withdrawals.contains(&self.forced_withdrawals.count) { return Err(SummaryError::InvalidCount); } if !verifier.verify_certificate::<_, H::Digest>(rng, self, certificate, strategy) { return Err(SummaryError::InvalidCertificate); } Ok(()) } } // The hasher is a type parameter only, so the derived traits would bound it. impl Clone for Summary { fn clone(&self) -> Self { *self } } impl Copy for Summary {} impl Debug for Summary { fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { f.debug_struct("Summary") .field("epoch", &self.epoch) .field("parent", &self.parent) .field("matrix", &self.matrix) .field("balances", &self.balances) .field("payouts", &self.payouts) .field("deposits", &self.deposits) .field("forced_withdrawals", &self.forced_withdrawals) .finish() } } impl PartialEq for Summary { fn eq(&self, other: &Self) -> bool { self.epoch == other.epoch && self.parent == other.parent && self.matrix == other.matrix && self.balances == other.balances && self.payouts == other.payouts && self.deposits == other.deposits && self.forced_withdrawals == other.forced_withdrawals } } impl Eq for Summary {} impl Digestible for Summary { type Digest = H::Digest; fn digest(&self) -> H::Digest { H::hash(&[&self.encode()]) } } impl Write for Summary { fn write(&self, buf: &mut impl BufMut) { self.epoch.write(buf); self.parent.write(buf); self.matrix.write(buf); self.balances.write(buf); self.payouts.write(buf); self.deposits.write(buf); self.forced_withdrawals.write(buf); } } impl EncodeSize for Summary { fn encode_size(&self) -> usize { Epoch::SIZE + 3 * H::Digest::SIZE + self.payouts.encode_size() + self.deposits.encode_size() + self.forced_withdrawals.encode_size() } } impl Read for Summary { type Cfg = (); fn read_cfg(buf: &mut impl Buf, _: &()) -> Result { Ok(Self { epoch: Epoch::read(buf)?, parent: H::Digest::read(buf)?, matrix: H::Digest::read(buf)?, balances: H::Digest::read(buf)?, payouts: Commitment::read(buf)?, deposits: Processed::read(buf)?, forced_withdrawals: Processed::read(buf)?, }) } } #[cfg(feature = "arbitrary")] impl arbitrary::Arbitrary<'_> for Summary where H::Digest: for<'a> arbitrary::Arbitrary<'a>, { fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result { Ok(Self { epoch: u.arbitrary()?, parent: u.arbitrary()?, matrix: u.arbitrary()?, balances: u.arbitrary()?, payouts: u.arbitrary()?, deposits: u.arbitrary()?, forced_withdrawals: u.arbitrary()?, }) } } impl certificate::Subject for &Summary { type Namespace = Namespace; fn namespace<'a>(&self, derived: &'a Self::Namespace) -> &'a [u8] { &derived.summary } fn message(&self) -> Bytes { self.encode() } } #[cfg(test)] mod tests { use super::*; use crate::bajillion::{ Deposit, ForcedWithdrawal, Matrix, tests::{NAMESPACE, account, certify, chain, scheme}, }; use commonware_codec::DecodeExt as _; use commonware_cryptography::{Digest as _, Sha256, ed25519::PublicKey, sha256::Digest}; use commonware_parallel::Sequential; use commonware_storage::merkle::Family as _; use commonware_utils::test_rng; /// Returns the summary before the first close, on top of balances with a fixed root. fn genesis() -> Summary { Summary::::genesis::(Sha256::hash(&[b"balances"])) } /// The genesis summary records the empty matrix and a payout log holding only its initial /// commit, with nothing paid out. #[test] fn test_genesis_and_digest() { let genesis = genesis(); assert_eq!(genesis.epoch, 0); assert_eq!(genesis.parent, Digest::EMPTY); assert_eq!(genesis.balances, Sha256::hash(&[b"balances"])); assert_eq!( genesis.matrix, Matrix::::empty().root() ); let log = keyless::initial_root::>, Sha256>(); let expected = Commitment { size: Location::new(1), root: log, }; assert_eq!(genesis.payouts, expected); assert_eq!(Summary::decode(genesis.encode()).unwrap(), genesis); // Every field changes the digest and decodes back unchanged. let other = Sha256::hash(&[b"other"]); let digest = genesis.digest(); for changed in [ Summary { epoch: 1, ..genesis }, Summary { parent: other, ..genesis }, Summary { matrix: other, ..genesis }, Summary { balances: other, ..genesis }, Summary { payouts: Commitment { size: Location::new(2), ..genesis.payouts }, ..genesis }, Summary { payouts: Commitment { root: other, ..genesis.payouts }, ..genesis }, Summary { deposits: Processed { count: 1, ..genesis.deposits }, ..genesis }, Summary { deposits: Processed { hash: other, ..genesis.deposits }, ..genesis }, Summary { forced_withdrawals: Processed { count: 1, ..genesis.forced_withdrawals }, ..genesis }, Summary { forced_withdrawals: Processed { hash: other, ..genesis.forced_withdrawals }, ..genesis }, ] { assert_ne!(changed.digest(), digest); assert_eq!(Summary::decode(changed.encode()).unwrap(), changed); } // A payouts size the log cannot reach does not decode. let beyond = Summary { payouts: Commitment { size: mmr::Family::MAX_LEAVES + 1, ..genesis.payouts }, ..genesis }; assert!(matches!( Summary::::decode(beyond.encode()), Err(CodecError::Invalid("Location", _)) )); } /// Validators certify a summary's encoding in the summary namespace. #[test] fn test_certificate_covers_the_encoding_in_the_summary_namespace() { let genesis = genesis(); let subject = &genesis; let namespace = Namespace::new(NAMESPACE); assert_eq!(certificate::Subject::message(&subject), genesis.encode()); assert_eq!( certificate::Subject::namespace(&subject, &namespace), namespace.summary.as_slice() ); } /// Both running hashes start at all zeros. Each extends its parent's by `H(hash || request)` /// for every request processed in queue order. #[test] fn test_running_hashes_chain_processed_requests() { let genesis = genesis(); let start = Processed { count: 0, hash: Digest::EMPTY, }; assert_eq!( (genesis.deposits, genesis.forced_withdrawals), (start, start) ); let deposit = |index, amount| Deposit::<_, u64> { account: account(index), amount, }; let (first, second) = (deposit(0, 5), deposit(1, 7)); // One request extends the hash by H(hash || request). let one = start.next::(std::slice::from_ref(&first)); assert_eq!(one.count, 1); assert_eq!( one.hash, Sha256::hash(&[start.hash.as_ref(), &first.encode()]) ); assert_eq!(one.hash, chain(start.hash, std::slice::from_ref(&first))); assert_eq!(Processed::decode(one.encode()).unwrap(), one); // A close that processes nothing carries its parent's hash. let none = one.next::>(&[]); assert_eq!((none.count, none.hash), (0, one.hash)); // Two closes chain to the hash of one close processing both batches. let both = start.next::(&[first.clone(), second.clone()]); let next = one.next::(std::slice::from_ref(&second)); assert_eq!((both.count, next.count), (2, 1)); assert_eq!(next.hash, both.hash); // Reordering or repeating requests changes the hash. let reversed = start.next::(&[second, first.clone()]); let repeated = start.next::(&[first.clone(), first]); assert_ne!(reversed.hash, both.hash); assert_ne!(repeated.hash, one.hash); // Forced withdrawals chain the same way over their own encoding. let forced = ForcedWithdrawal::<_, u64> { account: account(2), amount: 3, }; let one = start.next::(std::slice::from_ref(&forced)); assert_eq!(one.hash, chain(start.hash, std::slice::from_ref(&forced))); } /// The posted summary must follow the ledger's last post and process its queues within their /// bounds, with a certificate over it. The certificate is checked only once everything else /// holds, and it covers the payouts size and root. #[test] fn test_verify_checks_every_field_before_the_certificate() { let mut rng = test_rng(); let fixture = scheme::fixture(&mut rng, NAMESPACE, 4); let genesis = genesis(); let parent = genesis.digest(); let summary = Summary { epoch: 1, parent, matrix: Sha256::hash(&[b"matrix"]), balances: Sha256::hash(&[b"after"]), payouts: Commitment { size: Location::new(3), root: Sha256::hash(&[b"payouts"]), }, deposits: Processed { count: 2, hash: Sha256::hash(&[b"deposits"]), }, forced_withdrawals: Processed { count: 1, hash: Sha256::hash(&[b"forced withdrawals"]), }, }; let certificate = certify(&fixture.schemes, &summary); let other = certify(&fixture.schemes, &genesis); let mut verify = |summary: &Summary, certificate, parent: &Digest, deposits, forced_withdrawals| { summary.verify( &mut rng, &fixture.verifier, certificate, 1, parent, deposits, forced_withdrawals, &Sequential, ) }; // Each count may lie anywhere from the queue's required count to its length. for (deposits, forced_withdrawals) in [(0..=2, 1..=1), (2..=5, 0..=3)] { verify( &summary, &certificate, &parent, deposits, forced_withdrawals, ) .unwrap(); } // Every other refusal comes before the certificate's. for certificate in [&certificate, &other] { let wrong = Summary { epoch: 2, ..summary }; assert!(matches!( verify(&wrong, certificate, &parent, 0..=2, 0..=1), Err(SummaryError::WrongEpoch { expected: 1, found: 2 }) )); assert!(matches!( verify(&summary, certificate, &Digest::EMPTY, 0..=2, 0..=1), Err(SummaryError::WrongParent) )); for (deposits, forced_withdrawals) in [(3..=4, 0..=1), (0..=1, 0..=1), (0..=2, 2..=2)] { assert!(matches!( verify(&summary, certificate, &parent, deposits, forced_withdrawals), Err(SummaryError::InvalidCount) )); } } // A summary that differs in its payouts size or root is not certified. let changed = [ Commitment { size: Location::new(4), ..summary.payouts }, Commitment { root: Sha256::hash(&[b"other"]), ..summary.payouts }, ]; for payouts in changed { let changed = Summary { payouts, ..summary }; assert!(matches!( verify(&changed, &certificate, &parent, 0..=2, 0..=1), Err(SummaryError::InvalidCertificate) )); } assert!(matches!( verify(&summary, &other, &parent, 0..=2, 0..=1), Err(SummaryError::InvalidCertificate) )); } #[cfg(feature = "arbitrary")] mod conformance { use super::*; use commonware_codec::conformance::CodecConformance; commonware_conformance::conformance_tests! { CodecConformance>, CodecConformance>, } } }