rhdl_ubft/cert/
collector.rs

1//! Share collector: a certificate is `q` verified shares from distinct
2//! replicas over one exact key (docs/rhdl_ubft-view-change.md).
3//!
4//! **Problem.** Upstream counts a cached signature as verified without
5//! checking the message (U01), checks certificates on a thread that races
6//! the cache (U34), re-verifies every share on every poll (UN-F10), and
7//! counts votes without their view (U08, UE-C1).
8//!
9//! **Idea.**
10//! - A window of `G` slots, each collecting for one key `(view, instance,
11//!   digest)` of one role. A share counts only for exactly its slot's key.
12//! - Each incoming share is verified once, through a scoreboard of `PQ`
13//!   pending verifications. The verdict comes back with its tag and the
14//!   collector's epoch, and counts only if the slot still has the same key
15//!   (there is no cache to go stale).
16//! - Signers are a bitmask of distinct, in-range replicas. A signer whose
17//!   share fails verification is barred for that key, so a Byzantine
18//!   replica cannot make the collector verify without bound.
19//! - Verified shares go to an external share RAM (`slot · 16 + signer`), so
20//!   a certificate can be forwarded (a NEWVIEW carries other replicas'
21//!   history certificates).
22use rhdl::prelude::*;
23
24use super::share_context;
25
26/// Pending verifications.
27pub const PQ: usize = 4;
28
29/// One-time configuration.
30#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
31pub struct CollConfig {
32    /// Configure (honored only when no verification is pending).
33    pub init: bool,
34    pub n: b5,
35    pub me: b5,
36    /// Role byte of the shares this collector takes.
37    pub role: b8,
38}
39
40/// Start collecting for a key (clears its slot, `instance mod G`).
41#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
42pub struct Open {
43    pub valid: bool,
44    pub view: b32,
45    pub instance: b32,
46    pub digest: [b64; 4],
47}
48
49/// A share: from the network, or our own (`own`, trusted, not verified).
50#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
51pub struct ShareIn {
52    pub valid: bool,
53    pub from: b5,
54    pub view: b32,
55    pub instance: b32,
56    pub digest: [b64; 4],
57    pub sig: [b64; 8],
58}
59
60/// Verify `sig` under replica `signer`'s key for the share context.
61#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
62pub struct CollVerify {
63    pub valid: bool,
64    pub epoch: b32,
65    pub tag: b2,
66    pub signer: b5,
67    pub context: [b64; 6],
68    pub sig: [b64; 8],
69}
70
71/// A verdict for a tag.
72#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
73pub struct CollVerdict {
74    pub valid: bool,
75    pub epoch: b32,
76    pub tag: b2,
77    pub ok: bool,
78}
79
80/// Store a verified share.
81#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
82pub struct ShareWrite {
83    pub we: bool,
84    pub slot: b3,
85    pub signer: b5,
86    pub sig: [b64; 8],
87}
88
89/// Inputs.
90#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
91pub struct CollIn {
92    pub cfg: CollConfig,
93    pub open: Open,
94    pub share: ShareIn,
95    pub own: ShareIn,
96    pub verdict: CollVerdict,
97    pub verify_ready: bool,
98}
99
100/// Outputs.
101#[derive(Clone, Copy, Debug, PartialEq, Digital)]
102pub struct CollOut<const G: usize> {
103    pub share_ready: bool,
104    pub own_ready: bool,
105    pub verify: CollVerify,
106    pub write: ShareWrite,
107    /// Per slot: certified (at least `q` distinct verified signers).
108    pub certified: [bool; G],
109    /// Per slot: the verified signers.
110    pub signers: [b16; G],
111    pub quiescent: bool,
112    /// Counters: shares dropped (wrong key, out of range, duplicate, barred)
113    /// and shares that failed verification.
114    pub dropped: b32,
115    pub bad: b32,
116}
117
118/// One slot.
119#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
120pub struct Slot {
121    pub open: bool,
122    pub view: b32,
123    pub instance: b32,
124    pub digest: [b64; 4],
125    pub got: b16,
126    pub inflight: b16,
127    pub barred: b16,
128}
129
130/// One pending verification.
131#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
132pub struct Pending {
133    pub busy: bool,
134    pub sent: bool,
135    pub slot: b3,
136    pub from: b5,
137    pub view: b32,
138    pub instance: b32,
139    pub digest: [b64; 4],
140    pub sig: [b64; 8],
141}
142
143/// State.
144#[derive(Clone, Copy, Debug, PartialEq, Digital)]
145pub struct CollState<const G: usize> {
146    pub configured: bool,
147    pub epoch: b32,
148    pub n: b5,
149    pub me: b5,
150    pub q: b5,
151    pub role: b8,
152    pub s: [Slot; G],
153    pub p: [Pending; PQ],
154    pub hold: CollVerify,
155    pub dropped: b32,
156    pub bad: b32,
157}
158
159impl<const G: usize> CollState<G> {
160    pub fn idle() -> Self {
161        Self {
162            configured: false,
163            epoch: b32(0),
164            n: b5(0),
165            me: b5(0),
166            q: b5(0),
167            role: b8(0),
168            s: [Slot::default(); G],
169            p: [Pending::default(); PQ],
170            hold: CollVerify::default(),
171            dropped: b32(0),
172            bad: b32(0),
173        }
174    }
175}
176
177impl<const G: usize> Default for CollState<G> {
178    fn default() -> Self {
179        Self::idle()
180    }
181}
182
183/// Number of set bits.
184#[kernel]
185pub fn popcount16(x: b16) -> b5 {
186    let mut c = b5(0);
187    for k in 0..16 {
188        if ((x >> b16(k as u128)) & b16(1)) != b16(0) {
189            c = c + b5(1);
190        }
191    }
192    c
193}
194
195/// A cleared slot, for kernels.
196#[kernel]
197pub fn empty_slot() -> Slot {
198    Slot { open: false, view: b32(0), instance: b32(0), digest: [b64(0); 4], got: b16(0), inflight: b16(0), barred: b16(0) }
199}
200
201/// A free pending entry, for kernels.
202#[kernel]
203pub fn free_pending() -> Pending {
204    Pending { busy: false, sent: false, slot: b3(0), from: b5(0), view: b32(0), instance: b32(0), digest: [b64(0); 4], sig: [b64(0); 8] }
205}
206
207/// One cycle of the collector.
208#[kernel]
209pub fn coll_step<const G: usize>(i: CollIn, r: CollState<G>) -> (CollOut<G>, CollState<G>) {
210    let mut s = r;
211    let gmask = b32(G as u128) - b32(1);
212    let mut quiescent = true;
213    for k in 0..PQ {
214        if r.p[k].busy {
215            quiescent = false;
216        }
217    }
218    let init = i.cfg.init && quiescent;
219    if init {
220        s.configured = i.cfg.n >= b5(3) && i.cfg.n <= b5(16) && i.cfg.me < i.cfg.n;
221        s.epoch = r.epoch + b32(1);
222        s.n = i.cfg.n;
223        s.me = i.cfg.me;
224        // A majority: floor(n / 2) + 1.
225        s.q = (i.cfg.n >> b5(1)) + b5(1);
226        s.role = i.cfg.role;
227        for k in 0..G {
228            s.s[k] = empty_slot();
229        }
230        for k in 0..PQ {
231            s.p[k] = free_pending();
232        }
233        s.hold = CollVerify { valid: false, epoch: b32(0), tag: b2(0), signer: b5(0), context: [b64(0); 6], sig: [b64(0); 8] };
234        s.dropped = b32(0);
235        s.bad = b32(0);
236    }
237    let run = r.configured && !init;
238
239    // A free pending entry (from registers), for the share port's ready.
240    let mut have_free = false;
241    let mut free_k = b2(0);
242    for k in 0..PQ {
243        if !have_free && !r.p[k].busy {
244            have_free = true;
245            free_k = b2(k as u128);
246        }
247    }
248
249    // A share for a key not opened yet (ours is not computed yet, or a
250    // later instance or view) waits instead of being dropped.
251    let wk: b3 = (i.share.instance & gmask).resize();
252    let ws = r.s[wk];
253    let share_early = i.share.valid && (!ws.open || i.share.instance > ws.instance || (i.share.instance == ws.instance && i.share.view > ws.view));
254    let mut o = CollOut::<G> {
255        share_ready: run && have_free && !share_early,
256        own_ready: run && !i.verdict.valid,
257        verify: r.hold,
258        write: ShareWrite { we: false, slot: b3(0), signer: b5(0), sig: [b64(0); 8] },
259        certified: [false; G],
260        signers: [b16(0); G],
261        quiescent: quiescent,
262        dropped: r.dropped,
263        bad: r.bad,
264    };
265    if init {
266        o.verify.valid = false;
267    }
268
269    // ---------------------------------------------------- verdicts
270    if run && i.verdict.valid && i.verdict.epoch == r.epoch {
271        let k = i.verdict.tag;
272        let p = r.p[k];
273        if p.busy && p.sent {
274            s.p[k] = free_pending();
275            let sl = s.s[p.slot];
276            let same = sl.open && sl.view == p.view && sl.instance == p.instance && sl.digest == p.digest;
277            let bit = b16(1) << p.from.resize::<16>();
278            if same {
279                s.s[p.slot].inflight = sl.inflight & !bit;
280                if i.verdict.ok {
281                    s.s[p.slot].got = sl.got | bit;
282                    o.write = ShareWrite { we: true, slot: p.slot, signer: p.from, sig: p.sig };
283                } else {
284                    s.s[p.slot].barred = sl.barred | bit;
285                    s.bad = r.bad + b32(1);
286                }
287            }
288        }
289    }
290
291    // ---------------------------------------------------- open
292    if run && i.open.valid {
293        let mut n = empty_slot();
294        n.open = true;
295        n.view = i.open.view;
296        n.instance = i.open.instance;
297        n.digest = i.open.digest;
298        let k: b3 = (i.open.instance & gmask).resize();
299        s.s[k] = n;
300    }
301
302    // ---------------------------------------------------- our own share
303    if run && i.own.valid && !i.verdict.valid {
304        let k: b3 = (i.own.instance & gmask).resize();
305        let sl = s.s[k];
306        let bit = b16(1) << r.me.resize::<16>();
307        if sl.open && sl.view == i.own.view && sl.instance == i.own.instance && sl.digest == i.own.digest {
308            s.s[k].got = sl.got | bit;
309            o.write = ShareWrite { we: true, slot: k, signer: r.me, sig: i.own.sig };
310        }
311    }
312
313    // ---------------------------------------------------- network shares
314    if run && i.share.valid && have_free && !share_early {
315        let k: b3 = (i.share.instance & gmask).resize();
316        let sl = s.s[k];
317        let bit = b16(1) << i.share.from.resize::<16>();
318        let in_range = i.share.from < r.n && i.share.from != r.me;
319        let key = sl.open && sl.view == i.share.view && sl.instance == i.share.instance && sl.digest == i.share.digest;
320        let fresh = ((sl.got | sl.inflight | sl.barred) & bit) == b16(0);
321        if in_range && key && fresh {
322            s.s[k].inflight = sl.inflight | bit;
323            s.p[free_k] = Pending {
324                busy: true,
325                sent: false,
326                slot: k,
327                from: i.share.from,
328                view: i.share.view,
329                instance: i.share.instance,
330                digest: i.share.digest,
331                sig: i.share.sig,
332            };
333        } else {
334            s.dropped = s.dropped + b32(1);
335        }
336    }
337
338    // ---------------------------------------------------- verify requests
339    if !init && r.hold.valid && i.verify_ready {
340        s.hold.valid = false;
341    }
342    if run && !r.hold.valid {
343        let mut found = false;
344        for k in 0..PQ {
345            let p = r.p[k];
346            if !found && p.busy && !p.sent {
347                found = true;
348                s.hold = CollVerify {
349                    valid: true,
350                    epoch: r.epoch,
351                    tag: b2(k as u128),
352                    signer: p.from,
353                    context: share_context(r.role, p.view, p.instance, p.digest),
354                    sig: p.sig,
355                };
356                s.p[k].sent = true;
357            }
358        }
359    }
360
361    // ---------------------------------------------------- certificates
362    for k in 0..G {
363        o.signers[k] = r.s[k].got;
364        o.certified[k] = r.s[k].open && popcount16(r.s[k].got) >= r.q && r.configured;
365    }
366    (o, s)
367}
rhdl_ubft/cert/collector.rs

rhdl_ubft/cert/
collector.rs
