diff options
Diffstat (limited to 'src/document')
| -rw-r--r-- | src/document/signatures.rs | 135 |
1 files changed, 101 insertions, 34 deletions
diff --git a/src/document/signatures.rs b/src/document/signatures.rs index 4554420..4f34ecb 100644 --- a/src/document/signatures.rs +++ b/src/document/signatures.rs @@ -198,16 +198,26 @@ pub(crate) fn unpack(bytes: &[u8]) -> Option<Vec<(ChangeHash, [u8; 64])>> { /// 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. +/// Received signatures of changes not there yet, kept at most (`offer`): the oldest +/// changes' 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; +/// Different signatures of one change waiting for it, kept at most: the first that came, +/// and the latest others. Ed25519 signatures are deterministic, so every honest copy of +/// a change's signature is the same bytes: one that doesn't verify, sent first or after, +/// puts none aside. +const CANDIDATES: usize = 3; + /// Received signatures of changes the document doesn't hold yet, `MAX_PENDING` at most: -/// the oldest go, so junk a peer sent once (signatures of changes that never come) -/// makes way for those that keep coming. +/// the oldest changes' go, so junk a peer sent once (signatures of changes that never +/// come) makes way for those that keep coming. #[derive(Debug, Default, Clone)] struct Pending { - by_change: HashMap<ChangeHash, [u8; 64]>, + /// By change, its different signatures (`CANDIDATES`), the first that came first. + by_change: HashMap<ChangeHash, Vec<[u8; 64]>>, + /// The signatures in `by_change`. + count: usize, /// The changes, oldest first; some may have left `by_change` since. order: std::collections::VecDeque<ChangeHash>, /// The document's heads when `offer` last looked for those whose changes came: as @@ -217,13 +227,25 @@ struct Pending { impl Pending { fn insert(&mut self, hash: ChangeHash, signature: [u8; 64]) { - if self.by_change.insert(hash, signature).is_none() { + let candidates = self.by_change.entry(hash).or_default(); + if candidates.contains(&signature) { + return; + } + if candidates.is_empty() { self.order.push_back(hash); } - while self.by_change.len() > MAX_PENDING { + if candidates.len() < CANDIDATES { + self.count += 1; + } else { + candidates.remove(1); + } + candidates.push(signature); + while self.count > MAX_PENDING { match self.order.pop_front() { Some(oldest) => { - self.by_change.remove(&oldest); + if let Some(gone) = self.by_change.remove(&oldest) { + self.count -= gone.len(); + } } None => break, } @@ -234,8 +256,11 @@ impl Pending { } } - fn remove(&mut self, hash: &ChangeHash) -> Option<[u8; 64]> { - self.by_change.remove(hash) + /// The signatures waiting for `hash`'s change, the first that came first. + fn remove(&mut self, hash: &ChangeHash) -> Vec<[u8; 64]> { + let candidates = self.by_change.remove(hash).unwrap_or_default(); + self.count -= candidates.len(); + candidates } /// Those whose changes `doc` holds now: none where its heads are those of the last @@ -394,19 +419,19 @@ impl Signatures { // Their own budget: what waited came from any peer, not only this one. let mut invalid_waiting = 0; for hash in arrived { - 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; + for signature in self.pending.remove(&hash) { + if invalid_waiting >= MAX_INVALID { + break; + } + match self.vouch(doc, hash, &signature) { + Vouched::More => { + self.insert(hash, signature); + kept += 1; + break; + } + Vouched::Invalid => invalid_waiting += 1, + Vouched::Nothing => break, } - Vouched::Invalid => invalid_waiting += 1, - Vouched::Nothing => {} } } let invalid = invalid + invalid_waiting; @@ -494,20 +519,28 @@ impl Signatures { 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 { + let candidates = self.pending.remove(&hash); + if candidates.is_empty() || 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 { + let key = committer.as_deref().and_then(crate::identity::public_of); + let mut valid = None; + for signature in candidates { + if invalid >= MAX_INVALID { + break; + } + if key + .as_ref() + .is_some_and(|key| crate::identity::verify(key, &message(&hash), &signature)) + { + valid = Some(signature); + break; + } invalid += 1; - continue; } + let Some(signature) = valid else { + continue; + }; self.insert(hash, signature); let actor = change.actor_id(); if self @@ -887,6 +920,40 @@ mod tests { assert_eq!(signatures.offer(&doc, vec![valid]), 1); } + /// A signature waiting for its change stays beside others of it that came before or + /// after: the first that came and the latest others. + #[test] + fn a_waiting_signature_stays_beside_forged_ones() { + let key = NodeKey::from_seed([1; 32]); + let mut theirs = Document::new(); + write(&mut theirs, &key.id(), &["a"], json!(1)); + let head = theirs.get_heads()[0]; + let actor = theirs.get_actor().clone(); + let forged = |i: u8| (head, NodeKey::from_seed([10 + i; 32]).sign(&message(&head))); + let valid = (head, key.sign(&message(&head))); + for received in [ + vec![valid, forged(0), forged(1), forged(2)], + vec![forged(0), forged(1), valid], + vec![forged(0), forged(1), forged(2), valid, valid], + ] { + let mut ours = Document::new(); + let mut signatures = Signatures::default(); + assert_eq!(signatures.offer(&ours, received), 0); + ours.load_incremental(&theirs.save_after(&[])).unwrap(); + assert_eq!(signatures.offer(&ours, Vec::new()), 1); + assert!(signatures.verified(&actor, 1)); + } + // Not the first, and others came after: put aside. + let mut pending = Pending::default(); + for (hash, signature) in [forged(0), valid, forged(1), forged(2)] { + pending.insert(hash, signature); + } + assert_eq!( + pending.remove(&head), + vec![forged(0).1, forged(1).1, forged(2).1] + ); + } + /// Signatures waiting for their changes: past the bound, the oldest go. #[test] fn the_oldest_waiting_signatures_go() { @@ -900,8 +967,8 @@ mod tests { pending.insert(hash(i), [0; 64]); } assert_eq!(pending.by_change.len(), MAX_PENDING); - assert!(pending.remove(&hash(0)).is_none()); - assert!(pending.remove(&hash(MAX_PENDING)).is_some()); + assert!(pending.remove(&hash(0)).is_empty()); + assert_eq!(pending.remove(&hash(MAX_PENDING)).len(), 1); } /// Protocol data, listed paths (within or above them) and asked-for writes are |