dig_block/types/signer_bitmap.rs
1//! Compact validator participation bitmap ([SPEC §2.10](docs/resources/SPEC.md)).
2//!
3//! ## Requirements trace
4//!
5//! - **[ATT-004](docs/requirements/domains/attestation/specs/ATT-004.md)** — struct shape, `MAX_VALIDATORS`,
6//! `new` / `from_bytes` / bit accessors / counts / thresholds / `as_bytes`.
7//! - **[ATT-005](docs/requirements/domains/attestation/specs/ATT-005.md)** — [`SignerBitmap::merge`],
8//! [`SignerBitmap::signer_indices`] (bitwise OR aggregation + sorted index list).
9//! - **[NORMATIVE](docs/requirements/domains/attestation/NORMATIVE.md)** — ATT-004 / ATT-005 API obligations.
10//!
11//! ## Encoding
12//!
13//! - **Byte length:** `ceil(validator_count / 8)` — see [`SignerBitmap::new`].
14//! - **Bit order:** LSB-first within each byte (validator `i` → byte `i/8`, bit `i % 8`). This matches the
15//! pseudocode in ATT-004 and keeps popcount-based [`SignerBitmap::signer_count`] aligned with the spec.
16//!
17//! ## Usage
18//!
19//! Construct with [`SignerBitmap::new`], mark signers with [`SignerBitmap::set_signed`], query with
20//! [`SignerBitmap::has_signed`], [`SignerBitmap::signer_count`], [`SignerBitmap::signing_percentage`], and
21//! [`SignerBitmap::has_threshold`]. Combine peer views with [`SignerBitmap::merge`] and enumerate participants
22//! in order via [`SignerBitmap::signer_indices`]. Raw wire bytes are exposed through [`SignerBitmap::as_bytes`]
23//! / [`SignerBitmap::from_bytes`] for bincode payloads ([SER-001](docs/requirements/domains/serialization/specs/SER-001.md)).
24//!
25//! ## Safety / limits
26//!
27//! [`SignerBitmap::new`] and [`SignerBitmap::from_bytes`] **assert** `validator_count <= MAX_VALIDATORS` so a
28//! single `u32` cannot force multi-gigabyte allocations in this crate; the protocol cap is **65536** validators.
29
30use crate::SignerBitmapError;
31use serde::{Deserialize, Serialize};
32
33/// Maximum number of validators representable in protocol bitmaps ([SPEC §2.10](docs/resources/SPEC.md), ATT-004).
34pub const MAX_VALIDATORS: u32 = 65_536;
35
36/// Bit vector of “which validators signed,” sized for a fixed validator set ([SPEC §2.10](docs/resources/SPEC.md)).
37#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
38pub struct SignerBitmap {
39 /// Raw little-endian bit-packed bytes (see module docs).
40 bits: Vec<u8>,
41 /// Logical validator cardinality; indices are `0 .. validator_count`.
42 validator_count: u32,
43}
44
45impl SignerBitmap {
46 /// Empty bitmap: all bits zero, sized for `validator_count` validators.
47 ///
48 /// **Panics** if `validator_count > MAX_VALIDATORS` (see [`MAX_VALIDATORS`]).
49 #[must_use]
50 pub fn new(validator_count: u32) -> Self {
51 assert!(
52 validator_count <= MAX_VALIDATORS,
53 "SignerBitmap::new: validator_count {validator_count} exceeds MAX_VALIDATORS ({MAX_VALIDATORS})"
54 );
55 let byte_count = (validator_count as usize).div_ceil(8);
56 Self {
57 bits: vec![0u8; byte_count],
58 validator_count,
59 }
60 }
61
62 /// Wrap existing bytes (e.g. after deserialization) with a validator count.
63 ///
64 /// Does **not** copy-truncate `bytes` to the canonical length; callers should supply `ceil(n/8)` bytes
65 /// consistent with `validator_count`. [`Self::as_bytes`] on a value from [`Self::new`] always matches.
66 ///
67 /// **Panics** if `validator_count > MAX_VALIDATORS`.
68 #[must_use]
69 pub fn from_bytes(bytes: &[u8], validator_count: u32) -> Self {
70 assert!(
71 validator_count <= MAX_VALIDATORS,
72 "SignerBitmap::from_bytes: validator_count {validator_count} exceeds MAX_VALIDATORS ({MAX_VALIDATORS})"
73 );
74 Self {
75 bits: bytes.to_vec(),
76 validator_count,
77 }
78 }
79
80 /// `true` if validator `index` has a raised bit and `index < validator_count`.
81 ///
82 /// Out-of-range indices return `false` (no panic); short [`Self::bits`] tails read as zero.
83 #[must_use]
84 pub fn has_signed(&self, index: u32) -> bool {
85 if index >= self.validator_count {
86 return false;
87 }
88 let byte_index = (index / 8) as usize;
89 let bit_index = index % 8;
90 let Some(&byte) = self.bits.get(byte_index) else {
91 return false;
92 };
93 byte & (1 << bit_index) != 0
94 }
95
96 /// Sets the bit for `index`. **Error** if `index >= validator_count` ([`SignerBitmapError::IndexOutOfBounds`]).
97 pub fn set_signed(&mut self, index: u32) -> Result<(), SignerBitmapError> {
98 if index >= self.validator_count {
99 return Err(SignerBitmapError::IndexOutOfBounds {
100 index,
101 max: self.validator_count,
102 });
103 }
104 let byte_index = (index / 8) as usize;
105 let bit_index = index % 8;
106 let canonical_len = (self.validator_count as usize).div_ceil(8);
107 if self.bits.len() < canonical_len {
108 self.bits.resize(canonical_len, 0);
109 }
110 self.bits[byte_index] |= 1 << bit_index;
111 Ok(())
112 }
113
114 /// Popcount over **all** stored bytes (ATT-004 spec algorithm).
115 ///
116 /// For bitmaps produced only via [`Self::new`] + [`Self::set_signed`], unused high bits in the last
117 /// byte stay zero, so the count matches “number of validators signed.”
118 #[must_use]
119 pub fn signer_count(&self) -> u32 {
120 self.bits.iter().map(|b| b.count_ones()).sum()
121 }
122
123 /// Integer percentage `0..=100`: `(signer_count * 100) / validator_count`, or `0` if `validator_count == 0`
124 /// ([SPEC §2.10](docs/resources/SPEC.md) `signing_percentage` method).
125 #[must_use]
126 pub fn signing_percentage(&self) -> u64 {
127 if self.validator_count == 0 {
128 return 0;
129 }
130 (u64::from(self.signer_count()) * 100) / u64::from(self.validator_count)
131 }
132
133 /// `true` iff [`Self::signing_percentage`] `>= threshold_pct`.
134 #[must_use]
135 pub fn has_threshold(&self, threshold_pct: u64) -> bool {
136 self.signing_percentage() >= threshold_pct
137 }
138
139 /// Borrow raw bitmap bytes (serialization / hashing helpers).
140 #[must_use]
141 pub fn as_bytes(&self) -> &[u8] {
142 &self.bits
143 }
144
145 /// Validator cardinality configured for this bitmap (NORMATIVE field).
146 #[must_use]
147 pub fn validator_count(&self) -> u32 {
148 self.validator_count
149 }
150
151 /// Bitwise OR of `other` into `self` (union of signer sets).
152 ///
153 /// **ATT-005:** [`Self::validator_count`] MUST match on both operands; otherwise [`SignerBitmapError::ValidatorCountMismatch`].
154 ///
155 /// ## Rationale (vs. spec pseudocode)
156 ///
157 /// The ATT-005 snippet zips byte vectors; if `self.bits` is shorter than `other.bits` (e.g. odd
158 /// [`Self::from_bytes`] layouts), zip would **drop** trailing OR contributions. This implementation resizes
159 /// `self.bits` to the canonical `ceil(validator_count / 8)` length, then ORs each index `i` with
160 /// `other.bits.get(i).unwrap_or(0)`, matching “combine all signers” intent while staying commutative on
161 /// well-formed bitmaps.
162 pub fn merge(&mut self, other: &SignerBitmap) -> Result<(), SignerBitmapError> {
163 if self.validator_count != other.validator_count {
164 return Err(SignerBitmapError::ValidatorCountMismatch {
165 expected: self.validator_count,
166 got: other.validator_count,
167 });
168 }
169 let n = (self.validator_count as usize).div_ceil(8);
170 self.bits.resize(n, 0);
171 for i in 0..n {
172 let ob = other.bits.get(i).copied().unwrap_or(0);
173 self.bits[i] |= ob;
174 }
175 Ok(())
176 }
177
178 /// All validator indices with a set bit, in **ascending** order (`0 .. validator_count` scan).
179 ///
180 /// **ATT-005:** Order follows the spec loop (`i` increasing); callers rely on this for deterministic
181 /// serialization, tests, and UX (e.g. display). Empty bitmap → empty [`Vec`].
182 #[must_use]
183 pub fn signer_indices(&self) -> Vec<u32> {
184 (0..self.validator_count)
185 .filter(|&i| self.has_signed(i))
186 .collect()
187 }
188}