rhdl_ubft/
consensus.rs

1//! Consensus over CTB, the normal case (W4 step 2;
2//! docs/rhdl_ubft-view-change.md). The view change is added on top.
3//!
4//! **Problem.** ubft_new's leader never sees a fast decision (UN-F4), its
5//! slow path needs every replica (N06), it re-reads the decided value from
6//! mutable memory after certifying it (UN-F5), and its votes and commits
7//! are counted without their view or value (U08, UE-C1).
8//!
9//! **Idea.** One step kernel over one state value, with ports instead of
10//! mailboxes:
11//! - PREPAREs and COMMITs arrive as CTB deliveries (consistent: no replica
12//!   is shown a different one), PROMISEs, FASTCOMMITs and shares
13//!   point-to-point. Every message names `(view, instance, digest)`, and
14//!   counts only if that equals the slot's stored prepare.
15//! - The leader runs the same path as everyone else, so it sees its own
16//!   decisions; it stays leader for the whole view.
17//! - Fast path: promises from all `n`, then fast-commits from all `n`.
18//! - Slow path (after the slot's deadline): our share goes to the
19//!   collector and to every replica; with a certificate we CTB a COMMIT,
20//!   and a replica's COMMIT counts once we hold the certificate ourselves.
21//!   `q = f + 1` commits decide.
22//! - The decided value is the one stored when the prepare was accepted.
23//!   Nothing reads it from anywhere else afterwards.
24//! - Decisions leave in instance order, each exactly once.
25//! - A message that cannot be matched yet (its instance is in the window
26//!   and this view, but our prepare or its digest is not here yet) is not
27//!   taken: `ctb_ready`/`p2p_ready` stay low for it, so it waits in its own
28//!   source's channel (the caller's mux serves the other sources meanwhile)
29//!   instead of being dropped. Upstream buffers early promises the same way.
30//! - Our own CTB sends are delivered back to us by the caller (upstream
31//!   `handleCbMessage(local_index, ...)`), so the leader's PREPARE and our
32//!   COMMIT take the same path as everyone else's.
33use rhdl::prelude::*;
34
35use crate::cert::{ROLE_PREPARE, share_context};
36use crate::cert::collector::popcount16;
37
38/// Message kinds on CTB and point-to-point channels.
39pub mod kind {
40    pub const PREPARE: u128 = 1;
41    pub const COMMIT: u128 = 2;
42    pub const PROMISE: u128 = 3;
43    pub const FASTCOMMIT: u128 = 4;
44}
45
46/// Configuration.
47#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
48pub struct ConsConfig {
49    pub init: bool,
50    pub n: b5,
51    pub me: b5,
52    pub session: b64,
53    /// Cycles a slot waits for the fast path before the slow path.
54    pub fast_wait: b32,
55}
56
57/// A message: a CTB delivery or a point-to-point record, from `from`.
58#[derive(Clone, Copy, Debug, PartialEq, Digital)]
59pub struct ConsMsg<const P: usize> {
60    pub valid: bool,
61    pub from: b5,
62    pub kind: b4,
63    pub view: b32,
64    pub instance: b32,
65    pub digest: [b64; 4],
66    pub len: b5,
67    pub value: [b32; P],
68}
69
70/// A proposal from the client side (the leader takes it).
71#[derive(Clone, Copy, Debug, PartialEq, Digital)]
72pub struct Proposal<const P: usize> {
73    pub valid: bool,
74    pub len: b5,
75    pub value: [b32; P],
76}
77
78/// A digest answer for `(slot, instance)`.
79#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
80pub struct ConsDigest {
81    pub valid: bool,
82    pub epoch: b32,
83    pub slot: b3,
84    pub instance: b32,
85    pub digest: [b64; 4],
86}
87
88/// Our signed share for `(slot, instance)`.
89#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
90pub struct ConsSigned {
91    pub valid: bool,
92    pub epoch: b32,
93    pub slot: b3,
94    pub instance: b32,
95    pub sig: [b64; 8],
96}
97
98/// A safe value fixed by a NEWVIEW for one window slot.
99#[derive(Clone, Copy, Debug, PartialEq, Digital)]
100pub struct Constraint<const P: usize> {
101    pub set: bool,
102    pub instance: b32,
103    pub digest: [b64; 4],
104    pub len: b5,
105    pub value: [b32; P],
106}
107
108/// Enter `view` with its safe values (from the view change), or, with
109/// `skip`, enter it without a NEWVIEW: its leader never delivered one in
110/// time, so nothing can be prepared or committed in it, and it will be
111/// sealed in turn (as upstream advances the view at sealing).
112#[derive(Clone, Copy, Debug, PartialEq, Digital)]
113pub struct Install<const G: usize, const P: usize> {
114    pub valid: bool,
115    pub skip: bool,
116    /// R-28: a NEWVIEW for the view we already entered by skip, taken late.
117    pub late: bool,
118    pub view: b32,
119    pub c: [Constraint<P>; G],
120}
121
122/// What the view change sees of a window slot.
123#[derive(Clone, Copy, Debug, PartialEq, Digital)]
124pub struct SlotView<const P: usize> {
125    pub active: bool,
126    pub instance: b32,
127    pub dig_have: bool,
128    pub digest: [b64; 4],
129    pub len: b5,
130    pub value: [b32; P],
131    /// The view of the key the prepare collector certifies for this slot.
132    pub kview: b32,
133}
134
135/// Inputs.
136#[derive(Clone, Copy, Debug, PartialEq, Digital)]
137pub struct ConsIn<const G: usize, const P: usize> {
138    pub cfg: ConsConfig,
139    /// The view is being sealed: take no new PREPARE, and certify every
140    /// slot we fast-committed (the bridge).
141    pub sealing: bool,
142    pub install: Install<G, P>,
143    /// Client requests are outstanding (clients send every request to
144    /// every replica, as in uBFT): with no progress for two fast windows,
145    /// the view is stalled even if no PREPARE arrived at all.
146    pub pending: bool,
147    /// A CTB delivery (PREPARE, COMMIT).
148    pub ctb: ConsMsg<P>,
149    /// A point-to-point record (PROMISE, FASTCOMMIT).
150    pub p2p: ConsMsg<P>,
151    pub proposal: Proposal<P>,
152    pub digest: ConsDigest,
153    pub signed: ConsSigned,
154    /// The collector's per-slot certificate status, for our current keys.
155    pub certified: [bool; G],
156    pub ctb_ready: bool,
157    pub p2p_ready: bool,
158    pub digest_ready: bool,
159    pub sign_ready: bool,
160    pub own_ready: bool,
161    pub open_ready: bool,
162    pub decide_ready: bool,
163}
164
165/// A digest request: the value-block of `(instance, len, value)`.
166#[derive(Clone, Copy, Debug, PartialEq, Digital)]
167pub struct ConsDigestReq<const P: usize> {
168    pub valid: bool,
169    pub epoch: b32,
170    pub slot: b3,
171    pub instance: b32,
172    pub len: b5,
173    pub value: [b32; P],
174}
175
176/// Sign the share context for `(slot, instance)`.
177#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
178pub struct ConsSignReq {
179    pub valid: bool,
180    pub epoch: b32,
181    pub slot: b3,
182    pub instance: b32,
183    pub context: [b64; 6],
184}
185
186/// Open a collector key, or hand it our own share.
187#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
188pub struct ConsKey {
189    pub valid: bool,
190    pub view: b32,
191    pub instance: b32,
192    pub digest: [b64; 4],
193    pub sig: [b64; 8],
194}
195
196/// One decision.
197#[derive(Clone, Copy, Debug, PartialEq, Digital)]
198pub struct Decision<const P: usize> {
199    pub valid: bool,
200    pub instance: b32,
201    pub view: b32,
202    pub len: b5,
203    pub value: [b32; P],
204    pub slow: bool,
205}
206
207/// Outputs. Every request is a holding register (unchanged until taken).
208#[derive(Clone, Copy, Debug, PartialEq, Digital)]
209pub struct ConsOut<const G: usize, const P: usize> {
210    pub ctb_ready: bool,
211    pub p2p_ready: bool,
212    pub proposal_ready: bool,
213    /// CTB-broadcast this (PREPARE, COMMIT).
214    pub ctb_send: ConsMsg<P>,
215    /// Send this to every other replica (PROMISE, FASTCOMMIT, and our
216    /// share as `kind = 0` with the signature in `value`).
217    pub p2p_send: ConsMsg<P>,
218    pub share_send: ConsKey,
219    pub digest_req: ConsDigestReq<P>,
220    pub sign_req: ConsSignReq,
221    pub open: ConsKey,
222    pub own: ConsKey,
223    pub decide: Decision<P>,
224    pub view: b32,
225    pub leader: b5,
226    /// The oldest undecided slot passed its view-change deadline.
227    pub stalled: bool,
228    /// Sealing: every slot we fast-committed has its COMMIT sent.
229    pub bridge_done: bool,
230    pub slots: [SlotView<P>; G],
231    pub dropped: b32,
232}
233
234/// One window slot.
235#[derive(Clone, Copy, Debug, PartialEq, Digital)]
236pub struct CSlot<const P: usize> {
237    pub active: bool,
238    pub instance: b32,
239    pub len: b5,
240    pub value: [b32; P],
241    pub dig_sent: bool,
242    pub dig_have: bool,
243    pub digest: [b64; 4],
244    pub start: b32,
245    pub promised: b16,
246    pub promise_sent: bool,
247    pub fastc: b16,
248    pub fastc_sent: bool,
249    pub opened: bool,
250    pub sign_sent: bool,
251    pub signed: bool,
252    pub sig: [b64; 8],
253    pub own_given: bool,
254    pub share_sent: bool,
255    pub commit_sent: bool,
256    /// Replicas whose COMMIT for our key was delivered.
257    pub commits: b16,
258    pub decided: bool,
259    pub slow: bool,
260    /// Built from a COMMIT (the PREPARE was missed): no promises, votes or
261    /// shares from us; it decides only on certified COMMITs.
262    pub from_commit: bool,
263    /// The view of this slot's key: the current view for a PREPARE, or the
264    /// COMMIT's own view for a slot learned from certified COMMITs (a
265    /// decision certified in any view is final, so a replica behind on
266    /// decisions learns it whatever view it is in now).
267    pub kview: b32,
268    /// The digest the first COMMIT claimed, until ours is computed.
269    pub claim_set: bool,
270    pub claimed: [b64; 4],
271}
272
273/// State.
274#[derive(Clone, Copy, Debug, PartialEq, Digital)]
275pub struct ConsState<const G: usize, const P: usize> {
276    pub configured: bool,
277    pub epoch: b32,
278    pub n: b5,
279    pub me: b5,
280    pub q: b5,
281    pub all: b16,
282    pub session: b64,
283    pub fast_wait: b32,
284    pub view: b32,
285    pub clock: b32,
286    /// Clock of the last decision or view entry.
287    pub progress: b32,
288    /// This view was entered without a NEWVIEW: no PREPARE or COMMIT counts.
289    pub no_nv: bool,
290    /// Consecutive views entered without a decision: the stall timeout
291    /// doubles with each (as PBFT backs off), so a lagging or isolated
292    /// replica does not race ahead through views alone.
293    pub backoff: b3,
294    /// The next instance to decide, and the next the leader proposes.
295    pub next_decide: b32,
296    pub next_propose: b32,
297    pub s: [CSlot<P>; G],
298    /// Safe values of the current view (from its NEWVIEW).
299    pub c: [Constraint<P>; G],
300    pub h_ctb: ConsMsg<P>,
301    pub h_p2p: ConsMsg<P>,
302    pub h_share: ConsKey,
303    pub h_dig: ConsDigestReq<P>,
304    pub h_sign: ConsSignReq,
305    pub h_open: ConsKey,
306    pub h_own: ConsKey,
307    pub h_dec: Decision<P>,
308    pub dropped: b32,
309}
310
311/// A cleared slot, for kernels.
312#[kernel]
313pub fn empty_cslot<const P: usize>() -> CSlot<P> {
314    CSlot::<P> {
315        active: false,
316        instance: b32(0),
317        len: b5(0),
318        value: [b32(0); P],
319        dig_sent: false,
320        dig_have: false,
321        digest: [b64(0); 4],
322        start: b32(0),
323        promised: b16(0),
324        promise_sent: false,
325        fastc: b16(0),
326        fastc_sent: false,
327        opened: false,
328        sign_sent: false,
329        signed: false,
330        sig: [b64(0); 8],
331        own_given: false,
332        share_sent: false,
333        commit_sent: false,
334        commits: b16(0),
335        decided: false,
336        slow: false,
337        from_commit: false,
338        kview: b32(0),
339        claim_set: false,
340        claimed: [b64(0); 4],
341    }
342}
343
344/// No constraint, for kernels.
345#[kernel]
346pub fn empty_constraint<const P: usize>() -> Constraint<P> {
347    Constraint::<P> { set: false, instance: b32(0), digest: [b64(0); 4], len: b5(0), value: [b32(0); P] }
348}
349
350/// An idle message, for kernels.
351#[kernel]
352pub fn idle_msg<const P: usize>() -> ConsMsg<P> {
353    ConsMsg::<P> { valid: false, from: b5(0), kind: b4(0), view: b32(0), instance: b32(0), digest: [b64(0); 4], len: b5(0), value: [b32(0); P] }
354}
355
356/// An idle key, for kernels.
357#[kernel]
358pub fn idle_key() -> ConsKey {
359    ConsKey { valid: false, view: b32(0), instance: b32(0), digest: [b64(0); 4], sig: [b64(0); 8] }
360}
361
362/// An idle decision, for kernels.
363#[kernel]
364pub fn idle_decision<const P: usize>() -> Decision<P> {
365    Decision::<P> { valid: false, instance: b32(0), view: b32(0), len: b5(0), value: [b32(0); P], slow: false }
366}
367
368/// `leader(view) = view mod n`, without `%` (n ≤ 16, view < 2^32).
369#[kernel]
370pub fn leader_of(view: b32, n: b5) -> b5 {
371    // Long division by a small divisor, one bit at a time.
372    let d: b32 = n.resize();
373    let mut rem = b32(0);
374    for k in 0..32 {
375        rem = (rem << b32(1)) | ((view >> b32((31 - k) as u128)) & b32(1));
376        if rem >= d {
377            rem = rem - d;
378        }
379    }
380    rem.resize()
381}
382
383impl<const G: usize, const P: usize> ConsState<G, P> {
384    pub fn idle() -> Self {
385        Self {
386            configured: false,
387            epoch: b32(0),
388            n: b5(0),
389            me: b5(0),
390            q: b5(0),
391            all: b16(0),
392            session: b64(0),
393            fast_wait: b32(0),
394            view: b32(0),
395            clock: b32(0),
396            progress: b32(0),
397            no_nv: false,
398            backoff: b3(0),
399            next_decide: b32(0),
400            next_propose: b32(0),
401            s: [empty_cslot::<P>(); G],
402            c: [empty_constraint::<P>(); G],
403            h_ctb: idle_msg::<P>(),
404            h_p2p: idle_msg::<P>(),
405            h_share: idle_key(),
406            h_dig: ConsDigestReq::<P> { valid: false, epoch: b32(0), slot: b3(0), instance: b32(0), len: b5(0), value: [b32(0); P] },
407            h_sign: ConsSignReq::default(),
408            h_open: idle_key(),
409            h_own: idle_key(),
410            h_dec: idle_decision::<P>(),
411            dropped: b32(0),
412        }
413    }
414}
415
416impl<const G: usize, const P: usize> Default for ConsState<G, P> {
417    fn default() -> Self {
418        Self::idle()
419    }
420}
421
422impl<const P: usize> Default for ConsMsg<P> {
423    fn default() -> Self {
424        idle_msg::<P>()
425    }
426}
427
428impl<const P: usize> Default for Proposal<P> {
429    fn default() -> Self {
430        Self { valid: false, len: b5(0), value: [b32(0); P] }
431    }
432}
433
434impl<const G: usize, const P: usize> Default for ConsIn<G, P> {
435    fn default() -> Self {
436        Self {
437            cfg: ConsConfig::default(),
438            ctb: ConsMsg::default(),
439            p2p: ConsMsg::default(),
440            proposal: Proposal::default(),
441            digest: ConsDigest::default(),
442            signed: ConsSigned::default(),
443            certified: [false; G],
444            sealing: false,
445            pending: false,
446            install: Install::<G, P> { valid: false, skip: false, late: false, view: b32(0), c: [empty_constraint::<P>(); G] },
447            ctb_ready: false,
448            p2p_ready: false,
449            digest_ready: false,
450            sign_ready: false,
451            own_ready: false,
452            open_ready: false,
453            decide_ready: false,
454        }
455    }
456}
457
458/// One cycle of the normal case.
459#[kernel]
460pub fn cons_step<const G: usize, const P: usize>(i: ConsIn<G, P>, r: ConsState<G, P>) -> (ConsOut<G, P>, ConsState<G, P>) {
461    let mut s = r;
462    let gmask = b32(G as u128) - b32(1);
463    let g32 = b32(G as u128);
464    if i.cfg.init {
465        s = r;
466        s.configured = i.cfg.n >= b5(3) && i.cfg.n <= b5(16) && i.cfg.me < i.cfg.n && (i.cfg.n & b5(1)) == b5(1) && i.cfg.session != b64(0);
467        s.epoch = r.epoch + b32(1);
468        s.n = i.cfg.n;
469        s.me = i.cfg.me;
470        s.q = (i.cfg.n >> b5(1)) + b5(1);
471        let mut all = b16(0);
472        for k in 0..16 {
473            if b5(k as u128) < i.cfg.n {
474                all = all | (b16(1) << b16(k as u128));
475            }
476        }
477        s.all = all;
478        s.session = i.cfg.session;
479        s.fast_wait = i.cfg.fast_wait;
480        s.view = b32(0);
481        s.clock = b32(0);
482        s.progress = b32(0);
483        s.no_nv = false;
484        s.backoff = b3(0);
485        s.next_decide = b32(0);
486        s.next_propose = b32(0);
487        for k in 0..G {
488            s.s[k] = empty_cslot::<P>();
489            s.c[k] = empty_constraint::<P>();
490        }
491        s.h_ctb = idle_msg::<P>();
492        s.h_p2p = idle_msg::<P>();
493        s.h_share = idle_key();
494        s.h_dig.valid = false;
495        s.h_sign.valid = false;
496        s.h_open = idle_key();
497        s.h_own = idle_key();
498        s.h_dec = idle_decision::<P>();
499        s.dropped = b32(0);
500    }
501    let run = r.configured && !i.cfg.init;
502    let leader = leader_of(r.view, r.n);
503    let me_bit = b16(1) << r.me.resize::<16>();
504    s.clock = r.clock + b32(1);
505
506    // Early messages wait (see the module docs).
507    let ck: b3 = (i.ctb.instance & gmask).resize();
508    let ce = r.s[ck];
509    let c_win = i.ctb.instance >= r.next_decide && i.ctb.instance < r.next_decide + g32;
510    // Ahead of our window (faster replicas run ahead): wait, never drop.
511    let c_ahead = i.ctb.instance >= r.next_decide + g32;
512    // Replicas install a view at slightly different times: a PREPARE,
513    // COMMIT or vote for exactly the next view waits until we install it
514    // (R-23). Anything further ahead is dropped, so a far-future view only
515    // ever blocks its own sender's channel (UE-C6).
516    let next_view = r.view + b32(1);
517    let ctb_next = i.ctb.valid && i.ctb.view == next_view && (i.ctb.kind == b4(kind::PREPARE) || i.ctb.kind == b4(kind::COMMIT));
518    let is_commit = i.ctb.kind == b4(kind::COMMIT);
519    let ctb_early = ctb_next
520        || (i.ctb.valid && i.ctb.view == r.view && i.ctb.instance >= r.next_decide && c_ahead)
521        // A COMMIT of this or an earlier view waits while its instance is
522        // ahead of our window, or its slot's digest is still computing.
523        || (i.ctb.valid
524            && is_commit
525            && i.ctb.view <= r.view
526            && i.ctb.instance >= r.next_decide
527            && (c_ahead || (c_win && ce.active && ce.instance == i.ctb.instance && !ce.dig_have)));
528    let pk: b3 = (i.p2p.instance & gmask).resize();
529    let pe = r.s[pk];
530    let p_win = i.p2p.instance >= r.next_decide && i.p2p.instance < r.next_decide + g32;
531    let p2p_early = (i.p2p.valid && i.p2p.view == next_view)
532        || (i.p2p.valid && i.p2p.view == r.view && i.p2p.instance >= r.next_decide && (!p_win || !(pe.active && pe.instance == i.p2p.instance && pe.dig_have)));
533    let mut o = ConsOut::<G, P> {
534        ctb_ready: run && !ctb_early,
535        p2p_ready: run && !p2p_early,
536        proposal_ready: false,
537        ctb_send: r.h_ctb,
538        p2p_send: r.h_p2p,
539        share_send: r.h_share,
540        digest_req: r.h_dig,
541        sign_req: r.h_sign,
542        open: r.h_open,
543        own: r.h_own,
544        decide: r.h_dec,
545        view: r.view,
546        leader: leader,
547        stalled: false,
548        bridge_done: false,
549        slots: [SlotView::<P> { active: false, instance: b32(0), dig_have: false, digest: [b64(0); 4], len: b5(0), value: [b32(0); P], kview: b32(0) }; G],
550        dropped: r.dropped,
551    };
552    for k in 0..G {
553        let e = r.s[k];
554        o.slots[k] = SlotView::<P> { active: e.active, instance: e.instance, dig_have: e.dig_have, digest: e.digest, len: e.len, value: e.value, kview: e.kview };
555    }
556    if i.cfg.init {
557        o.ctb_send.valid = false;
558        o.p2p_send.valid = false;
559        o.share_send.valid = false;
560        o.digest_req.valid = false;
561        o.sign_req.valid = false;
562        o.open.valid = false;
563        o.own.valid = false;
564        o.decide.valid = false;
565    }
566    // Takes.
567    if !i.cfg.init {
568        if r.h_ctb.valid && i.ctb_ready {
569            s.h_ctb.valid = false;
570        }
571        if r.h_p2p.valid && i.p2p_ready {
572            s.h_p2p.valid = false;
573        }
574        if r.h_share.valid && i.p2p_ready && !r.h_p2p.valid {
575            s.h_share.valid = false;
576        }
577        if r.h_dig.valid && i.digest_ready {
578            s.h_dig.valid = false;
579        }
580        if r.h_sign.valid && i.sign_ready {
581            s.h_sign.valid = false;
582        }
583        if r.h_open.valid && i.open_ready {
584            s.h_open.valid = false;
585        }
586        if r.h_own.valid && i.own_ready {
587            s.h_own.valid = false;
588        }
589        if r.h_dec.valid && i.decide_ready {
590            s.h_dec.valid = false;
591        }
592    }
593    // Shares share the point-to-point port, after the records.
594    if r.h_p2p.valid {
595        o.share_send.valid = false;
596    }
597
598    // ---------------------------------------------------- responses
599    if run && i.digest.valid && i.digest.epoch == r.epoch {
600        let k = i.digest.slot;
601        if s.s[k].active && s.s[k].instance == i.digest.instance && s.s[k].dig_sent && !s.s[k].dig_have {
602            s.s[k].dig_have = true;
603            s.s[k].digest = i.digest.digest;
604            // A view's safe value is binding: a PREPARE for a constrained
605            // instance with another value is discarded.
606            let cc = s.c[k];
607            if cc.set && cc.instance == i.digest.instance && cc.digest != i.digest.digest && !s.s[k].from_commit {
608                s.s[k] = empty_cslot::<P>();
609                s.dropped = s.dropped + b32(1);
610            }
611            // COMMITs counted before our digest was known were for the
612            // claimed digest: keep them only if it is ours.
613            if s.s[k].claim_set && s.s[k].claimed != i.digest.digest {
614                s.s[k].commits = b16(0);
615                if s.s[k].from_commit {
616                    // The value a COMMIT carried does not hash to the digest
617                    // it claimed: discard the slot.
618                    s.s[k] = empty_cslot::<P>();
619                }
620            }
621        }
622    }
623    if run && i.signed.valid && i.signed.epoch == r.epoch {
624        let k = i.signed.slot;
625        if s.s[k].active && s.s[k].instance == i.signed.instance && s.s[k].sign_sent && !s.s[k].signed {
626            s.s[k].signed = true;
627            s.s[k].sig = i.signed.sig;
628        }
629    }
630
631    // ---------------------------------------------------- CTB deliveries
632    if run && i.ctb.valid && !ctb_early {
633        let m = i.ctb;
634        let in_window = m.instance >= r.next_decide && m.instance < r.next_decide + g32;
635        let k: b3 = (m.instance & gmask).resize();
636        let e = s.s[k];
637        if m.kind == b4(kind::PREPARE) {
638            // Only the view's leader, only this view, only inside the
639            // window, only once per instance.
640            // Only an undecided learned slot may be replaced by a PREPARE.
641            let fresh = !(e.active && e.instance == m.instance) || (e.from_commit && !e.decided);
642            let ok = m.from == leader && m.view == r.view && in_window && fresh && m.len <= b5(P as u128) && !i.sealing && !r.no_nv;
643            if ok {
644                let mut n = empty_cslot::<P>();
645                n.active = true;
646                n.instance = m.instance;
647                n.len = m.len;
648                n.value = m.value;
649                n.start = r.clock;
650                // COMMITs already counted from a slot built from a COMMIT
651                // carry over as claims, checked against our digest.
652                n.kview = r.view;
653                if e.active && e.instance == m.instance && e.from_commit && e.kview == r.view {
654                    n.commits = e.commits;
655                    n.claim_set = true;
656                    n.claimed = if e.dig_have { e.digest } else { e.claimed };
657                }
658                s.s[k] = n;
659            } else {
660                s.dropped = s.dropped + b32(1);
661            }
662        } else if m.kind == b4(kind::COMMIT) {
663            // A certified COMMIT is safe to count even in a view entered
664            // without a NEWVIEW: its q shares include an honest replica that
665            // checked the view's safe values (R-25: without this, such a
666            // replica could never certify others' records).
667            let key = e.active && e.instance == m.instance && e.dig_have && m.view == e.kview && m.digest == e.digest;
668            // A COMMIT of this view or an earlier one for an instance we hold
669            // nothing for: learn from it (its certificate is checked here).
670            let missed = !(e.active && e.instance == m.instance) && m.view <= r.view && in_window && m.len <= b5(P as u128);
671            if key && m.from < r.n {
672                s.s[k].commits = e.commits | (b16(1) << m.from.resize::<16>());
673            } else if missed && m.from < r.n {
674                // We missed the PREPARE: build the slot from the COMMIT's
675                // value, to be checked against its digest.
676                let mut n = empty_cslot::<P>();
677                n.active = true;
678                n.from_commit = true;
679                n.kview = m.view;
680                n.instance = m.instance;
681                n.len = m.len;
682                n.value = m.value;
683                n.start = r.clock;
684                n.claim_set = true;
685                n.claimed = m.digest;
686                n.commits = b16(1) << m.from.resize::<16>();
687                // No promise, fast-commit or share from us for this slot.
688                n.promise_sent = true;
689                n.fastc_sent = true;
690                n.sign_sent = true;
691                n.signed = true;
692                n.own_given = true;
693                n.share_sent = true;
694                n.commit_sent = true;
695                s.s[k] = n;
696            } else {
697                s.dropped = s.dropped + b32(1);
698            }
699        } else {
700            s.dropped = s.dropped + b32(1);
701        }
702    }
703
704    // ---------------------------------------------------- point-to-point
705    if run && i.p2p.valid && !p2p_early {
706        let m = i.p2p;
707        let k: b3 = (m.instance & gmask).resize();
708        let e = s.s[k];
709        // The record counts only for exactly the stored prepare's key.
710        let key = e.active && e.instance == m.instance && e.dig_have && e.kview == r.view && m.view == r.view && m.digest == e.digest && m.from < r.n && m.from != r.me;
711        let bit = b16(1) << m.from.resize::<16>();
712        if key && m.kind == b4(kind::PROMISE) {
713            s.s[k].promised = e.promised | bit;
714        } else if key && m.kind == b4(kind::FASTCOMMIT) {
715            s.s[k].fastc = e.fastc | bit;
716        } else {
717            s.dropped = s.dropped + b32(1);
718        }
719    }
720
721    // ---------------------------------------------------- the leader
722    // Proposals become PREPAREs in instance order, inside the window.
723    let room = r.next_propose < r.next_decide + g32;
724    let am_leader = r.me == leader && !r.no_nv;
725    if run && am_leader && room && !r.h_ctb.valid {
726        let pk: b3 = (r.next_propose & gmask).resize();
727        let pc = r.c[pk];
728        let constrained = pc.set && pc.instance == r.next_propose;
729        o.proposal_ready = !constrained && !i.sealing;
730        if constrained && !i.sealing {
731            s.h_ctb = ConsMsg::<P> { valid: true, from: r.me, kind: b4(kind::PREPARE), view: r.view, instance: r.next_propose, digest: [b64(0); 4], len: pc.len, value: pc.value };
732            s.next_propose = r.next_propose + b32(1);
733        } else if i.proposal.valid && i.proposal.len <= b5(P as u128) && !i.sealing {
734            s.h_ctb = ConsMsg::<P> {
735                valid: true,
736                from: r.me,
737                kind: b4(kind::PREPARE),
738                view: r.view,
739                instance: r.next_propose,
740                digest: [b64(0); 4],
741                len: i.proposal.len,
742                value: i.proposal.value,
743            };
744            s.next_propose = r.next_propose + b32(1);
745        }
746    }
747
748    // ---------------------------------------------------- slot work
749    let mut d_done = r.h_dig.valid;
750    let mut x_done = r.h_p2p.valid;
751    let mut g_done = r.h_sign.valid;
752    let mut k_done = r.h_open.valid;
753    let mut w_done = r.h_own.valid;
754    let mut h_done = r.h_share.valid;
755    let mut c_done = r.h_ctb.valid || s.h_ctb.valid;
756    for k in 0..G {
757        let e = r.s[k];
758        let slot = b3(k as u128);
759        // Decided slots stay until reused, so the bridge can still certify
760        // a fast decision before sealing.
761        if run && e.active && (!e.decided || (i.sealing && e.fastc_sent)) {
762            if !d_done && !e.dig_sent {
763                d_done = true;
764                s.h_dig = ConsDigestReq::<P> { valid: true, epoch: r.epoch, slot: slot, instance: e.instance, len: e.len, value: e.value };
765                s.s[k].dig_sent = true;
766            }
767            if !k_done && e.dig_have && !e.opened {
768                k_done = true;
769                s.h_open = ConsKey { valid: true, view: e.kview, instance: e.instance, digest: e.digest, sig: [b64(0); 8] };
770                s.s[k].opened = true;
771            }
772            if !x_done && e.dig_have && !e.promise_sent {
773                x_done = true;
774                s.h_p2p = ConsMsg::<P> { valid: true, from: r.me, kind: b4(kind::PROMISE), view: r.view, instance: e.instance, digest: e.digest, len: b5(0), value: [b32(0); P] };
775                s.s[k].promise_sent = true;
776                s.s[k].promised = s.s[k].promised | me_bit;
777            } else if !x_done && e.promise_sent && (e.promised | me_bit) == r.all && !e.fastc_sent {
778                x_done = true;
779                s.h_p2p = ConsMsg::<P> { valid: true, from: r.me, kind: b4(kind::FASTCOMMIT), view: r.view, instance: e.instance, digest: e.digest, len: b5(0), value: [b32(0); P] };
780                s.s[k].fastc_sent = true;
781                s.s[k].fastc = s.s[k].fastc | me_bit;
782            }
783            // Slow path after the deadline.
784            // The slow path starts at the deadline, or at once when sealing
785            // a slot we fast-committed.
786            let late = r.clock - e.start >= r.fast_wait || (i.sealing && e.fastc_sent);
787            if !g_done && e.dig_have && e.opened && late && !e.sign_sent {
788                g_done = true;
789                s.h_sign = ConsSignReq { valid: true, epoch: r.epoch, slot: slot, instance: e.instance, context: share_context(b8(ROLE_PREPARE), r.view, e.instance, e.digest) };
790                s.s[k].sign_sent = true;
791            }
792            if !w_done && e.signed && !e.own_given {
793                w_done = true;
794                s.h_own = ConsKey { valid: true, view: r.view, instance: e.instance, digest: e.digest, sig: e.sig };
795                s.s[k].own_given = true;
796            }
797            if !h_done && e.signed && !e.share_sent {
798                h_done = true;
799                s.h_share = ConsKey { valid: true, view: r.view, instance: e.instance, digest: e.digest, sig: e.sig };
800                s.s[k].share_sent = true;
801            }
802            if !c_done && e.own_given && i.certified[k] && !e.commit_sent {
803                c_done = true;
804                s.h_ctb = ConsMsg::<P> { valid: true, from: r.me, kind: b4(kind::COMMIT), view: r.view, instance: e.instance, digest: e.digest, len: e.len, value: e.value };
805                s.s[k].commit_sent = true;
806            }
807        }
808    }
809
810    // ---------------------------------------------------- decision
811    // In order: the slot of `next_decide`, from its stored bytes.
812    let hk: b3 = (r.next_decide & gmask).resize();
813    let h = r.s[hk];
814    let held = h.active && h.instance == r.next_decide && h.dig_have;
815    // A COMMIT counts only with our own certificate for the same key.
816    let commits = if i.certified[hk] { popcount16(h.commits) } else { b5(0) };
817    let fast = held && h.fastc == r.all;
818    let slow = held && commits >= r.q;
819    if run && held && !h.decided && (fast || slow) && !r.h_dec.valid {
820        s.h_dec = Decision::<P> { valid: true, instance: h.instance, view: h.kview, len: h.len, value: h.value, slow: !fast };
821        s.s[hk].decided = true;
822        s.next_decide = r.next_decide + b32(1);
823        s.progress = r.clock;
824        s.backoff = b3(0);
825    }
826    // The view-change deadline: the oldest undecided slot waited twice
827    // the fast window without deciding (W4 step 3 acts on this).
828    let window2 = (r.fast_wait + r.fast_wait) << r.backoff.resize::<32>();
829    o.stalled = run && ((held && !h.decided && (r.clock - h.start >= window2)) || (i.pending && r.clock - r.progress >= window2));
830    let mut bridge = true;
831    for k in 0..G {
832        let e = r.s[k];
833        if e.active && e.fastc_sent && !e.from_commit && !e.commit_sent {
834            bridge = false;
835        }
836    }
837    o.bridge_done = run && i.sealing && bridge;
838
839    // ---------------------------------------------------- a new view
840    // Only the next view; the window restarts at our next instance, with
841    // its safe values. (The view change checked the NEWVIEW.)
842    if run && i.install.valid && i.install.view == r.view + b32(1) {
843        s.view = i.install.view;
844        s.next_propose = r.next_decide;
845        s.progress = r.clock;
846        s.no_nv = i.install.skip;
847        s.backoff = if r.backoff < b3(6) { r.backoff + b3(1) } else { r.backoff };
848        for k in 0..G {
849            // A slot learning a certified decision of an earlier view stays
850            // (a real PREPARE of the new view still replaces it).
851            let keep = r.s[k].active && r.s[k].from_commit && !r.s[k].decided;
852            if !keep {
853                s.s[k] = empty_cslot::<P>();
854            }
855            s.c[k] = i.install.c[k];
856        }
857        s.h_ctb.valid = false;
858        s.h_p2p.valid = false;
859        s.h_share.valid = false;
860        s.h_sign.valid = false;
861        s.h_open.valid = false;
862        s.h_own.valid = false;
863        s.epoch = r.epoch + b32(1);
864    }
865    // R-28: a late NEWVIEW for the view we entered by skip. Nothing was
866    // prepared in a skipped view, so nothing conflicts: take its constraints
867    // and accept PREPAREs from now on.
868    if run && i.install.valid && i.install.late && i.install.view == r.view && r.no_nv {
869        s.no_nv = false;
870        s.next_propose = r.next_decide;
871        s.progress = r.clock;
872        for k in 0..G {
873            let keep = r.s[k].active && r.s[k].from_commit && !r.s[k].decided;
874            if !keep {
875                s.s[k] = empty_cslot::<P>();
876            }
877            s.c[k] = i.install.c[k];
878        }
879        s.h_ctb.valid = false;
880        s.h_p2p.valid = false;
881        s.h_share.valid = false;
882        s.h_sign.valid = false;
883        s.h_open.valid = false;
884        s.h_own.valid = false;
885        s.epoch = r.epoch + b32(1);
886    }
887    (o, s)
888}
rhdl_ubft/consensus.rs

rhdl_ubft/
consensus.rs
