From 10d73d81bb919d9d9d938f763c83b7c6761c69fa Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 9 Nov 2026 22:36:06 +0000 Subject: signatures: check a bounded number of invalid received signatures MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit A sync message carries up to 65536 signatures (MAX_PER_MESSAGE), and the receiver checks, under the document's write lock, each one of a held change that would vouch for more of its actor's changes than the one before: about 30 µs each. A member sending that many signatures that don't verify cost the receiver about two seconds of writes per message. Signatures::offer and vouch_batch now stop checking after 64 found invalid (MAX_INVALID) and drop the rest unchecked, with a warning. A node forwards only signatures it verified, so an honest peer sends none. offer counts those a message brings apart from those that waited for their changes, which came from any peer. Signatures::vouch says which it found (Vouched): more vouched for, nothing more, or invalid. --- src/document/signatures.rs | 107 ++++++++++++++++++++++++++++++++++++++------- 1 file changed, 90 insertions(+), 17 deletions(-) (limited to 'src') diff --git a/src/document/signatures.rs b/src/document/signatures.rs index b62e545..8577619 100644 --- a/src/document/signatures.rs +++ b/src/document/signatures.rs @@ -191,6 +191,13 @@ pub(crate) fn unpack(bytes: &[u8]) -> Option> { .collect(), ) } +/// Received signatures found invalid that one call of `offer` (for those it brings, and +/// again for those that waited) or `vouch_batch` checks at most: the rest are dropped +/// unchecked. A node forwards only signatures it +/// verified, so an honest peer sends none; checking one costs about 30 µs, under the +/// document's write lock, and a message carries `MAX_PER_MESSAGE`. +const MAX_INVALID: usize = 64; + /// Received signatures of changes not there yet, kept at most (`offer`): the oldest go. /// As many as a message carries, so a delta's (whose changes come after it) all wait. const MAX_PENDING: usize = MAX_PER_MESSAGE; @@ -233,6 +240,18 @@ impl Pending { } } +/// What `Signatures::vouch` made of a signature. +#[derive(Debug, PartialEq, Eq)] +enum Vouched { + /// Valid, and its actor's latest verified change now. + More, + /// Its change isn't there, or it couldn't vouch for more than the one before: not + /// checked, or valid and no later. + Nothing, + /// Checked, and not made by its change's committer. + Invalid, +} + /// A document's signatures, by change. #[derive(Debug, Default)] pub(crate) struct Signatures { @@ -305,45 +324,56 @@ impl Signatures { } /// `signature` of `hash`, if valid (`check`), as its actor's latest verified change - /// where it is later than the one before; whether it is. - fn vouch(&mut self, doc: &Document, hash: ChangeHash, signature: &[u8; 64]) -> bool { + /// where it is later than the one before. + fn vouch(&mut self, doc: &Document, hash: ChangeHash, signature: &[u8; 64]) -> Vouched { // Not checked where it couldn't vouch for more: a signature costs about 30 µs. let Some(meta) = doc.get_change_meta_by_hash(&hash) else { - return false; + return Vouched::Nothing; }; if self .latest .get(meta.actor.as_ref()) .is_some_and(|latest| latest.seq >= meta.seq) { - return false; + return Vouched::Nothing; } let Some((actor, seq)) = check(doc, &hash, signature) else { - return false; + return Vouched::Invalid; }; if self .latest .get(&actor) .is_some_and(|latest| latest.seq >= seq) { - return false; + return Vouched::Nothing; } self.latest.insert(actor, Latest { seq, hash }); - true + Vouched::More } /// Received signatures, from a peer: each checked once its change is in `doc`, kept /// if it vouches for more of its actor's changes than any before; those of changes /// not there yet wait, a bounded number. Then those waiting whose changes came - /// meanwhile. How many were kept. + /// meanwhile. How many were kept. Past `MAX_INVALID` found invalid, the rest are + /// dropped unchecked. pub(crate) fn offer(&mut self, doc: &Document, received: Vec<(ChangeHash, [u8; 64])>) -> usize { let mut kept = 0; + let mut invalid = 0; for (hash, signature) in received { if !super::changes::holds(doc, &hash) { self.pending.insert(hash, signature); - } else if self.vouch(doc, hash, &signature) { - self.insert(hash, signature); - kept += 1; + continue; + } + if invalid >= MAX_INVALID { + continue; + } + match self.vouch(doc, hash, &signature) { + Vouched::More => { + self.insert(hash, signature); + kept += 1; + } + Vouched::Invalid => invalid += 1, + Vouched::Nothing => {} } } let arrived: Vec = self @@ -352,13 +382,30 @@ impl Signatures { .filter(|hash| super::changes::holds(doc, hash)) .copied() .collect(); + // Their own budget: what waited came from any peer, not only this one. + let mut invalid_waiting = 0; for hash in arrived { - if let Some(signature) = self.pending.remove(&hash) - && self.vouch(doc, hash, &signature) - { - self.insert(hash, signature); - kept += 1; + let Some(signature) = self.pending.remove(&hash) else { + continue; + }; + if invalid_waiting >= MAX_INVALID { + continue; } + match self.vouch(doc, hash, &signature) { + Vouched::More => { + self.insert(hash, signature); + kept += 1; + } + Vouched::Invalid => invalid_waiting += 1, + Vouched::Nothing => {} + } + } + let invalid = invalid + invalid_waiting; + if invalid >= MAX_INVALID { + tracing::warn!( + invalid, + "Received signatures that don't verify: the rest of them dropped unchecked" + ); } kept } @@ -432,18 +479,24 @@ impl Signatures { /// Received signatures waiting for their changes (`offer`) checked against /// `changes`, not in the document yet, each made by its committer (`committers`, as /// `access::screen` finds them): one valid vouches for its actor's changes up to it, - /// these among them. + /// these among them. Past `MAX_INVALID` found invalid, the rest are dropped + /// unchecked. pub(crate) fn vouch_batch(&mut self, changes: &[super::Change], committers: &[Option]) { + let mut invalid = 0; for (change, committer) in changes.iter().zip(committers) { let hash = change.hash(); let Some(signature) = self.pending.remove(&hash) else { continue; }; + if invalid >= MAX_INVALID { + continue; + } let valid = committer .as_deref() .and_then(crate::identity::public_of) .is_some_and(|key| crate::identity::verify(&key, &message(&hash), &signature)); if !valid { + invalid += 1; continue; } self.insert(hash, signature); @@ -805,6 +858,26 @@ mod tests { assert_eq!(kept.since(0), vec![signed(second)]); } + /// Past `MAX_INVALID` invalid signatures, the rest a peer brings go unchecked, a + /// valid one among them too. + #[test] + fn invalid_signatures_checked_a_bounded_number() { + let key = NodeKey::from_seed([1; 32]); + let other = NodeKey::from_seed([2; 32]); + let mut doc = Document::new(); + write(&mut doc, &key.id(), &["a"], json!(1)); + let head = doc.get_heads()[0]; + let actor = doc.get_actor().clone(); + let forged = (head, other.sign(&message(&head))); + let valid = (head, key.sign(&message(&head))); + let mut signatures = Signatures::default(); + let mut received = vec![forged; MAX_INVALID]; + received.push(valid); + assert_eq!(signatures.offer(&doc, received), 0); + assert!(!signatures.verified(&actor, 1)); + assert_eq!(signatures.offer(&doc, vec![valid]), 1); + } + /// Signatures waiting for their changes: past the bound, the oldest go. #[test] fn the_oldest_waiting_signatures_go() { -- cgit v1.3.1