1use sha2::{Digest, Sha256};
10
11use crate::core::error::CoreError;
12
13#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct StewardListConfig {
20 pub sn_min: usize,
22 pub sn_max: usize,
24 pub allow_subset_candidates: bool,
26}
27
28impl Default for StewardListConfig {
29 fn default() -> Self {
32 Self::new(1, 2).expect("1..=2 is always a valid StewardListConfig range")
33 }
34}
35
36impl StewardListConfig {
37 pub fn new(sn_min: usize, sn_max: usize) -> Result<Self, CoreError> {
41 if sn_min < 1 || sn_min > sn_max {
42 return Err(CoreError::InvalidConfigSize);
43 }
44 Ok(Self {
45 sn_min,
46 sn_max,
47 allow_subset_candidates: false,
48 })
49 }
50
51 fn size_bounds(&self, total_members: usize) -> std::ops::RangeInclusive<usize> {
55 if total_members < self.sn_min {
56 total_members..=total_members
57 } else {
58 self.sn_min..=self.sn_max.min(total_members)
59 }
60 }
61
62 pub fn compute_list_size(&self, total_members: usize) -> usize {
64 *self.size_bounds(total_members).end()
65 }
66
67 pub fn is_valid_size(&self, size: usize, total_members: usize) -> bool {
69 self.size_bounds(total_members).contains(&size)
70 }
71}
72
73#[derive(Debug, Clone, PartialEq, Eq)]
80pub struct StewardList {
81 members: Vec<Vec<u8>>,
83 config: StewardListConfig,
85 election_epoch: u64,
87 retry_round: u32,
91}
92
93impl StewardList {
94 pub fn generate(
99 election_epoch: u64,
100 conversation_id: &[u8],
101 member_ids: &[Vec<u8>],
102 sn: usize,
103 config: StewardListConfig,
104 retry_round: u32,
105 ) -> Result<Self, CoreError> {
106 check_generation_inputs(&config, member_ids, sn)?;
107 let ordered =
108 sorted_steward_indices(election_epoch, retry_round, conversation_id, member_ids);
109 let members = ordered
110 .into_iter()
111 .take(sn)
112 .map(|i| member_ids[i].clone())
113 .collect();
114 Ok(Self {
115 members,
116 config,
117 election_epoch,
118 retry_round,
119 })
120 }
121
122 pub fn validate(
126 proposed: &[Vec<u8>],
127 election_epoch: u64,
128 conversation_id: &[u8],
129 member_ids: &[Vec<u8>],
130 config: &StewardListConfig,
131 retry_round: u32,
132 ) -> Result<bool, CoreError> {
133 let sn = proposed.len();
134 check_generation_inputs(config, member_ids, sn)?;
135 let ordered =
136 sorted_steward_indices(election_epoch, retry_round, conversation_id, member_ids);
137 Ok(ordered
138 .iter()
139 .take(sn)
140 .zip(proposed.iter())
141 .all(|(&i, want)| &member_ids[i] == want))
142 }
143
144 pub fn epoch_steward(&self, epoch: u64) -> Option<&[u8]> {
148 if self.is_exhausted(epoch) {
149 return None;
150 }
151 let index = ((epoch - self.election_epoch) as usize) % self.members.len();
152 Some(&self.members[index])
153 }
154
155 pub fn backup_steward(&self, epoch: u64) -> Option<&[u8]> {
157 if self.is_exhausted(epoch) {
158 return None;
159 }
160 let index = ((epoch - self.election_epoch) as usize + 1) % self.members.len();
161 Some(&self.members[index])
162 }
163
164 pub fn live_epoch_and_backup<F: Fn(&[u8]) -> bool>(
169 &self,
170 epoch: u64,
171 eligible: F,
172 ) -> (Option<&[u8]>, Option<&[u8]>) {
173 let epoch_steward = self.live_steward_from(epoch, 0, &eligible);
174 let backup = epoch_steward
175 .and_then(|es| self.live_steward_from(epoch, 1, |c| c != es && eligible(c)));
176 (epoch_steward, backup)
177 }
178
179 pub fn live_steward_from<F: Fn(&[u8]) -> bool>(
184 &self,
185 epoch: u64,
186 offset: usize,
187 eligible: F,
188 ) -> Option<&[u8]> {
189 if self.is_exhausted(epoch) {
190 return None;
191 }
192 let len = self.members.len();
193 let start = ((epoch - self.election_epoch) as usize + offset) % len;
194 for step in 0..len {
195 let idx = (start + step) % len;
196 let candidate = &self.members[idx];
197 if eligible(candidate) {
198 return Some(candidate);
199 }
200 }
201 None
202 }
203
204 pub fn is_exhausted(&self, epoch: u64) -> bool {
207 if epoch < self.election_epoch {
208 return true;
209 }
210 (epoch - self.election_epoch) >= self.members.len() as u64
211 }
212
213 pub fn contains(&self, member_id: &[u8]) -> bool {
214 self.members.iter().any(|m| m.as_slice() == member_id)
215 }
216
217 pub fn members(&self) -> &[Vec<u8>] {
218 &self.members
219 }
220
221 pub fn len(&self) -> usize {
222 self.members.len()
223 }
224
225 pub fn is_empty(&self) -> bool {
226 self.members.is_empty()
227 }
228
229 pub fn config(&self) -> &StewardListConfig {
230 &self.config
231 }
232
233 pub fn election_epoch(&self) -> u64 {
234 self.election_epoch
235 }
236
237 pub fn retry_round(&self) -> u32 {
241 self.retry_round
242 }
243}
244
245fn check_generation_inputs(
248 config: &StewardListConfig,
249 member_ids: &[Vec<u8>],
250 sn: usize,
251) -> Result<(), CoreError> {
252 if member_ids.is_empty() {
253 return Err(CoreError::EmptyMembersList);
254 }
255 if !config.is_valid_size(sn, member_ids.len()) {
256 return Err(CoreError::InvalidConfigSize);
257 }
258 Ok(())
259}
260
261fn sorted_steward_indices(
264 election_epoch: u64,
265 retry_round: u32,
266 conversation_id: &[u8],
267 member_ids: &[Vec<u8>],
268) -> Vec<usize> {
269 let mut scored: Vec<(Vec<u8>, usize)> = member_ids
270 .iter()
271 .enumerate()
272 .map(|(i, id)| {
273 (
274 compute_steward_hash(election_epoch, retry_round, id, conversation_id),
275 i,
276 )
277 })
278 .collect();
279 scored.sort_by(|(a, _), (b, _)| a.cmp(b));
280 scored.into_iter().map(|(_, i)| i).collect()
281}
282
283fn compute_steward_hash(
287 epoch: u64,
288 retry_round: u32,
289 member_id: &[u8],
290 conversation_id: &[u8],
291) -> Vec<u8> {
292 let mut hasher = Sha256::new();
293 hasher.update(epoch.to_be_bytes());
294 hasher.update(retry_round.to_be_bytes());
295 hasher.update(member_id);
296 hasher.update(conversation_id);
297 hasher.finalize().to_vec()
298}
299
300#[cfg(test)]
301mod tests {
302 use super::*;
303
304 fn member(id: u8) -> Vec<u8> {
305 vec![id; 20]
306 }
307
308 fn members(ids: &[u8]) -> Vec<Vec<u8>> {
309 ids.iter().map(|&id| member(id)).collect()
310 }
311
312 #[test]
313 fn test_config_validation() {
314 let config = StewardListConfig::new(2, 5).unwrap();
315
316 assert!(config.is_valid_size(3, 10));
318 assert!(config.is_valid_size(2, 10));
319 assert!(config.is_valid_size(5, 10));
320 assert!(!config.is_valid_size(1, 10));
321 assert!(!config.is_valid_size(6, 10));
322
323 assert!(config.is_valid_size(1, 1));
325 assert!(!config.is_valid_size(2, 1));
326 }
327
328 #[test]
329 fn test_new_rejects_bad_bounds() {
330 assert!(StewardListConfig::new(0, 5).is_err(), "sn_min == 0");
331 assert!(StewardListConfig::new(5, 3).is_err(), "sn_min > sn_max");
332 }
333
334 #[test]
335 fn test_generate_empty_members() {
336 let config = StewardListConfig::new(1, 3).unwrap();
337 assert!(StewardList::generate(0, b"conversation1", &[], 1, config, 0).is_err());
338 }
339
340 #[test]
341 fn test_generate_invalid_sn() {
342 let config = StewardListConfig::new(2, 5).unwrap();
343 let mems = members(&[1, 2, 3, 4, 5]);
344
345 assert!(
346 StewardList::generate(0, b"conversation1", &mems, 1, config.clone(), 0).is_err(),
347 "below sn_min"
348 );
349 assert!(
350 StewardList::generate(0, b"conversation1", &mems, 6, config, 0).is_err(),
351 "above sn_max"
352 );
353 }
354
355 #[test]
356 fn test_deterministic_generation() {
357 let config = StewardListConfig::new(2, 5).unwrap();
358 let mems = members(&[1, 2, 3, 4, 5]);
359 let conversation_id = b"test-conversation";
360
361 let list1 = StewardList::generate(0, conversation_id, &mems, 3, config.clone(), 0).unwrap();
362 let list2 = StewardList::generate(0, conversation_id, &mems, 3, config, 0).unwrap();
363
364 assert_eq!(list1.members(), list2.members());
365 assert_eq!(list1.len(), 3);
366 }
367
368 #[test]
371 fn test_different_epoch_shuffles() {
372 let config = StewardListConfig::new(5, 5).unwrap();
373 let mems = members(&[1, 2, 3, 4, 5]);
374
375 let base = StewardList::generate(0, b"conversation", &mems, 5, config.clone(), 0).unwrap();
376 let any_diff = (1..10).any(|e| {
377 let other =
378 StewardList::generate(e, b"conversation", &mems, 5, config.clone(), 0).unwrap();
379 other.members() != base.members()
380 });
381 assert!(any_diff);
382 }
383
384 #[test]
385 fn test_different_conversation_shuffles() {
386 let config = StewardListConfig::new(5, 5).unwrap();
387 let mems = members(&[1, 2, 3, 4, 5]);
388
389 let base = StewardList::generate(0, b"conversation1", &mems, 5, config.clone(), 0).unwrap();
390 let other = StewardList::generate(0, b"conversation2", &mems, 5, config, 0).unwrap();
391 assert_ne!(base.members(), other.members());
392 }
393
394 #[test]
395 fn test_member_order_does_not_affect_result() {
396 let config = StewardListConfig::new(2, 5).unwrap();
397 let mems_a = members(&[1, 2, 3, 4, 5]);
398 let mems_b = members(&[5, 3, 1, 4, 2]);
399
400 let list_a =
401 StewardList::generate(0, b"conversation", &mems_a, 3, config.clone(), 0).unwrap();
402 let list_b = StewardList::generate(0, b"conversation", &mems_b, 3, config, 0).unwrap();
403
404 assert_eq!(list_a.members(), list_b.members());
405 }
406
407 #[test]
408 fn test_epoch_steward_rotation() {
409 let config = StewardListConfig::new(3, 3).unwrap();
410 let mems = members(&[1, 2, 3]);
411
412 let list = StewardList::generate(0, b"conversation", &mems, 3, config, 0).unwrap();
413 let s0 = list.epoch_steward(0).unwrap().to_vec();
414 let s1 = list.epoch_steward(1).unwrap().to_vec();
415 let s2 = list.epoch_steward(2).unwrap().to_vec();
416
417 assert_ne!(s0, s1);
418 assert_ne!(s1, s2);
419 assert_ne!(s0, s2);
420 }
421
422 #[test]
424 fn test_backup_steward() {
425 let config = StewardListConfig::new(3, 3).unwrap();
426 let mems = members(&[1, 2, 3]);
427
428 let list = StewardList::generate(0, b"conversation", &mems, 3, config, 0).unwrap();
429
430 assert_eq!(list.backup_steward(0), list.epoch_steward(1));
431 assert_eq!(list.backup_steward(1), list.epoch_steward(2));
432 assert_eq!(list.backup_steward(2), list.epoch_steward(0));
433 }
434
435 #[test]
436 fn test_list_exhaustion() {
437 let config = StewardListConfig::new(2, 3).unwrap();
438 let mems = members(&[1, 2, 3]);
439
440 let list = StewardList::generate(5, b"conversation", &mems, 3, config, 0).unwrap();
441 assert_eq!(list.election_epoch(), 5);
442
443 assert!(!list.is_exhausted(5));
445 assert!(!list.is_exhausted(7));
446 assert!(list.is_exhausted(8));
447 assert!(
448 list.is_exhausted(4),
449 "epochs before election_epoch are exhausted"
450 );
451
452 assert!(list.epoch_steward(8).is_none());
454 assert!(list.backup_steward(8).is_none());
455 }
456
457 #[test]
458 fn test_validate_correct_list() {
459 let config = StewardListConfig::new(2, 5).unwrap();
460 let mems = members(&[1, 2, 3, 4, 5]);
461
462 let list = StewardList::generate(0, b"conversation", &mems, 3, config.clone(), 0).unwrap();
463 let valid = StewardList::validate(list.members(), 0, b"conversation", &mems, &config, 0);
464 assert!(valid.is_ok());
465 assert!(valid.unwrap())
466 }
467
468 #[test]
469 fn test_validate_tampered_list() {
470 let config = StewardListConfig::new(2, 5).unwrap();
471 let mems = members(&[1, 2, 3, 4, 5]);
472
473 let mut list =
474 StewardList::generate(0, b"conversation", &mems, 3, config.clone(), 0).unwrap();
475 list.members.swap(0, 1);
477
478 let valid = StewardList::validate(list.members(), 0, b"conversation", &mems, &config, 0);
479 assert!(valid.is_ok());
480 assert!(!valid.unwrap())
481 }
482
483 #[test]
484 fn test_validate_wrong_epoch() {
485 let config = StewardListConfig::new(5, 5).unwrap();
486 let mems = members(&[1, 2, 3, 4, 5]);
487
488 let list = StewardList::generate(0, b"conversation", &mems, 5, config.clone(), 0).unwrap();
489 let diff_epoch = (1..100u64)
491 .find(|&e| {
492 let o =
493 StewardList::generate(e, b"conversation", &mems, 5, config.clone(), 0).unwrap();
494 o.members() != list.members()
495 })
496 .expect("should differ within 100 epochs");
497
498 let valid = StewardList::validate(
499 list.members(),
500 diff_epoch,
501 b"conversation",
502 &mems,
503 &config,
504 0,
505 );
506 assert!(valid.is_ok());
507 assert!(!valid.unwrap());
508 }
509
510 #[test]
513 fn test_validate_wrong_members() {
514 let config = StewardListConfig::new(5, 5).unwrap();
515 let mems = members(&[1, 2, 3, 4, 5]);
516 let other_mems = members(&[1, 2, 3, 4, 6]);
517
518 let list = StewardList::generate(0, b"conversation", &mems, 5, config.clone(), 0).unwrap();
519 let valid =
520 StewardList::validate(list.members(), 0, b"conversation", &other_mems, &config, 0);
521 assert!(valid.is_ok());
522 assert!(!valid.unwrap())
523 }
524
525 #[test]
526 fn test_single_member() {
527 let config = StewardListConfig::new(1, 3).unwrap();
528 let mems = members(&[1]);
529
530 let list = StewardList::generate(0, b"conversation", &mems, 1, config, 0).unwrap();
531 assert_eq!(list.len(), 1);
532 assert_eq!(list.epoch_steward(0), list.backup_steward(0));
534 assert!(list.is_exhausted(1));
535 }
536
537 #[test]
540 fn test_live_steward_from_skips_ineligible() {
541 let config = StewardListConfig::new(3, 3).unwrap();
542 let mems = members(&[1, 2, 3]);
543
544 let list = StewardList::generate(0, b"conversation", &mems, 3, config, 0).unwrap();
545 let nominal = list.epoch_steward(0).unwrap().to_vec();
546
547 let all_eligible = |c: &[u8]| mems.iter().any(|m| m == c);
548 assert_eq!(
549 list.live_steward_from(0, 0, all_eligible),
550 Some(nominal.as_slice())
551 );
552
553 let after: Vec<Vec<u8>> = mems.iter().filter(|m| **m != nominal).cloned().collect();
554 let live = list
555 .live_steward_from(0, 0, |c| after.iter().any(|m| m == c))
556 .unwrap();
557 assert_ne!(live, nominal.as_slice());
558 assert!(after.iter().any(|m| m == live));
559 }
560
561 #[test]
564 fn test_live_epoch_and_backup_all_ineligible_and_single_survivor() {
565 let config = StewardListConfig::new(2, 2).unwrap();
566 let mems = members(&[1, 2]);
567 let list = StewardList::generate(0, b"conversation", &mems, 2, config, 0).unwrap();
568
569 let (e, b) = list.live_epoch_and_backup(0, |_| false);
570 assert!(e.is_none() && b.is_none());
571
572 let survivor = mems[0].clone();
573 let (e, b) = list.live_epoch_and_backup(0, |c| c == survivor.as_slice());
574 assert_eq!(e.unwrap(), survivor.as_slice());
575 assert!(b.is_none());
576 }
577
578 #[test]
581 fn test_live_epoch_and_backup_rotates_when_epoch_leaves() {
582 let config = StewardListConfig::new(3, 3).unwrap();
583 let mems = members(&[1, 2, 3]);
584 let list = StewardList::generate(0, b"conversation", &mems, 3, config, 0).unwrap();
585
586 let nominal = list.epoch_steward(0).unwrap().to_vec();
587 let (e, b) = list.live_epoch_and_backup(0, |c| c != nominal.as_slice());
588 assert!(e.is_some() && b.is_some());
589 assert_ne!(e.unwrap(), b.unwrap());
590 assert_ne!(e.unwrap(), nominal.as_slice());
591 assert_ne!(b.unwrap(), nominal.as_slice());
592 }
593
594 #[test]
597 fn test_live_epoch_and_backup_matches_nominal_when_all_eligible() {
598 let config = StewardListConfig::new(3, 3).unwrap();
599 let mems = members(&[1, 2, 3]);
600 let list = StewardList::generate(0, b"conversation", &mems, 3, config, 0).unwrap();
601
602 let (e, b) = list.live_epoch_and_backup(0, |_| true);
603 assert_eq!(e, list.epoch_steward(0));
604 assert_eq!(b, list.backup_steward(0));
605 }
606
607 #[test]
608 fn test_sha256_sorting_is_ascending() {
609 let config = StewardListConfig::new(5, 5).unwrap();
610 let mems = members(&[1, 2, 3, 4, 5]);
611
612 let list = StewardList::generate(0, b"conversation", &mems, 5, config, 0).unwrap();
613 let hashes: Vec<Vec<u8>> = list
614 .members()
615 .iter()
616 .map(|m| compute_steward_hash(0, 0, m, b"conversation"))
617 .collect();
618
619 for window in hashes.windows(2) {
620 assert!(window[0] < window[1], "hashes must be ascending");
621 }
622 }
623
624 #[test]
625 fn test_validate_rejects_empty_list() {
626 let config = StewardListConfig::new(3, 5).unwrap();
627 let mems = members(&[1, 2, 3, 4, 5]);
628 let empty: Vec<Vec<u8>> = vec![];
629
630 assert!(StewardList::validate(&empty, 0, b"conversation", &mems, &config, 0).is_err());
631 }
632
633 #[test]
635 fn test_below_sn_min_uses_all_members() {
636 let config = StewardListConfig::new(5, 10).unwrap();
637 let mems = members(&[1, 2, 3]);
638
639 let list = StewardList::generate(0, b"conversation", &mems, 3, config, 0).unwrap();
640 assert_eq!(list.len(), 3);
641 }
642
643 #[test]
644 fn test_large_conversation_subset_selection() {
645 let config = StewardListConfig::new(3, 5).unwrap();
646 let mems: Vec<Vec<u8>> = (1..=20).map(member).collect();
647
648 let list = StewardList::generate(0, b"conversation", &mems, 5, config, 0).unwrap();
649 assert_eq!(list.len(), 5);
650 for steward in list.members() {
651 assert!(mems.contains(steward));
652 }
653 }
654
655 #[test]
658 fn test_retry_rounds_produce_different_lists() {
659 let config = StewardListConfig::new(1, 2).unwrap();
660 let mems: Vec<Vec<u8>> = (1..=4u8).map(member).collect();
661
662 let base = StewardList::generate(1, b"conversation", &mems, 2, config.clone(), 0).unwrap();
663 let any_diff = (1..10u32).any(|r| {
664 let other =
665 StewardList::generate(1, b"conversation", &mems, 2, config.clone(), r).unwrap();
666 other.members() != base.members()
667 });
668 assert!(
669 any_diff,
670 "retries should produce at least one different list"
671 );
672 }
673
674 #[test]
680 fn retry_round_seed_persists_independently_of_caller_counter() {
681 let config = StewardListConfig::new(2, 4).unwrap();
682 let mems: Vec<Vec<u8>> = (1..=4u8).map(member).collect();
683 let epoch = 7;
684 let accepted_round: u32 = 2;
685
686 let list = StewardList::generate(epoch, b"conv", &mems, 4, config.clone(), accepted_round)
687 .unwrap();
688 assert_eq!(list.retry_round(), accepted_round, "list keeps its seed");
689
690 let round0 = StewardList::generate(epoch, b"conv", &mems, 4, config.clone(), 0).unwrap();
691 assert_ne!(
692 list.members(),
693 round0.members(),
694 "retry_round must shuffle the ordering for this test to be meaningful"
695 );
696
697 assert!(
698 StewardList::validate(
699 list.members(),
700 epoch,
701 b"conv",
702 list.members(),
703 &config,
704 accepted_round,
705 )
706 .unwrap(),
707 "validate succeeds when the seed matches the list's recorded retry_round"
708 );
709
710 assert!(
711 !StewardList::validate(list.members(), epoch, b"conv", list.members(), &config, 0,)
712 .unwrap(),
713 "validate fails when the seed differs — caller's counter is not the source of truth"
714 );
715 }
716}