rhdl_ubft/
checkpoint.rs

1//! Certified checkpoints and state transfer (W5; docs/rhdl_ubft-checkpoints.md).
2//!
3//! **Problem.** A replica that falls behind cannot catch up: ubft_new has
4//! no checkpoints (N18); upstream throws "state transfer not implemented"
5//! (U12), spins on a tail gap (U09), and accepts a checkpoint equal to its
6//! own without binding the certificate to the content (UE-C20).
7//!
8//! **Idea.**
9//! - At every `C = 2^CS` decided instances the application reports the
10//!   digest `a` of its state; the replica signs `CHECKPOINT(low, a)` (role
11//!   5, share context with view 0, instance `low >> CS`, digest `a`) and
12//!   sends the share to every replica. `q` verified shares certify exactly
13//!   `(low, a)`.
14//! - A replica behind a checkpoint it never computed takes a peer's offer
15//!   `(low, a)` with its shares (forwarded into the same collector), and
16//!   adopts it only once every share verifies here.
17//! - Behind a certified checkpoint, it requests the state at `low`, hashes
18//!   the `K` chunks as they arrive (a chain, one SHA-512 block each), writes
19//!   them to the application's shadow copy, and commits only if the digest
20//!   equals `a`; otherwise it aborts and asks the next peer. Then consensus
21//!   jumps to `low`.
22//! - Every index, length and peer id from the network is range-checked
23//!   before use; every wait has a deadline.
24use rhdl::prelude::*;
25
26use crate::cert::share_context;
27use crate::ctb::bswap64;
28
29/// Role byte of a checkpoint share.
30pub const ROLE_CHECKPOINT: u128 = 5;
31/// `"RUB2-STA"` as a little-endian word.
32pub const STA_DOMAIN: u128 = 0x4154_532D_3242_5552;
33/// Words per state chunk (64 bytes).
34pub const CHUNK: usize = 16;
35
36/// Configuration.
37#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
38pub struct CkConfig {
39    pub init: bool,
40    pub n: b5,
41    pub me: b5,
42    pub session: b64,
43    /// Cycles to wait for an offer to certify or a peer to send state.
44    pub deadline: b32,
45}
46
47/// The application's digest at a checkpoint.
48#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
49pub struct AppDigest {
50    pub valid: bool,
51    pub low: b32,
52    pub digest: [b64; 4],
53}
54
55/// A peer's offer of a certified checkpoint (its shares follow on the
56/// collector's share input).
57#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
58pub struct Offer {
59    pub valid: bool,
60    pub from: b5,
61    pub low: b32,
62    pub digest: [b64; 4],
63}
64
65/// One state chunk from a peer.
66#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
67pub struct Chunk {
68    pub valid: bool,
69    pub from: b5,
70    pub low: b32,
71    pub j: b8,
72    pub data: [b32; CHUNK],
73}
74
75/// A chain digest answer.
76#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
77pub struct CkDigest {
78    pub valid: bool,
79    pub epoch: b32,
80    pub j: b8,
81    pub digest: [b64; 4],
82}
83
84/// Inputs.
85#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
86pub struct CkIn {
87    pub cfg: CkConfig,
88    pub app: AppDigest,
89    pub offer: Offer,
90    pub chunk: Chunk,
91    /// Consensus's next instance to decide.
92    pub next_decide: b32,
93    /// The collector's status for the key we opened, and its signed share.
94    pub certified: bool,
95    pub signed: bool,
96    pub sig: [b64; 8],
97    pub digest: CkDigest,
98    pub sign_ready: bool,
99    pub key_ready: bool,
100    pub share_ready: bool,
101    pub req_ready: bool,
102    pub digest_ready: bool,
103    pub shadow_ready: bool,
104}
105
106/// Open a checkpoint-collector key `(0, low >> CS, digest)`, or give it our
107/// own share.
108#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
109pub struct CkKey {
110    pub valid: bool,
111    pub instance: b32,
112    pub digest: [b64; 4],
113    pub sig: [b64; 8],
114}
115
116/// Outputs (holding registers).
117#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
118pub struct CkOut {
119    pub offer_ready: bool,
120    pub chunk_ready: bool,
121    pub sign_req: CkSignReq,
122    pub open: CkKey,
123    pub own: CkKey,
124    /// Send our checkpoint share to every replica.
125    pub share_send: CkKey,
126    /// Ask peer `to` for the state at `low`.
127    pub state_req: StateReq,
128    pub digest_req: CkDigestReq,
129    /// Write a chunk into the application's shadow copy.
130    pub shadow_write: ShadowWrite,
131    /// Commit (or discard) the shadow copy as the state at `low`.
132    pub shadow_commit: ShadowCommit,
133    /// The highest certified checkpoint: consensus may forget below `low`.
134    pub cert_valid: bool,
135    pub cert_low: b32,
136    pub cert_digest: [b64; 4],
137    /// Consensus jumps to `low` (state installed).
138    pub jump: bool,
139    pub jump_low: b32,
140    pub refused: b32,
141}
142
143/// Sign request.
144#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
145pub struct CkSignReq {
146    pub valid: bool,
147    pub epoch: b32,
148    pub context: [b64; 6],
149}
150
151/// State request.
152#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
153pub struct StateReq {
154    pub valid: bool,
155    pub to: b5,
156    pub low: b32,
157}
158
159/// Chain digest request (a 128-byte block; the job adds the pad block).
160#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
161pub struct CkDigestReq {
162    pub valid: bool,
163    pub epoch: b32,
164    pub j: b8,
165    pub block: [b64; 16],
166}
167
168/// Shadow write.
169#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
170pub struct ShadowWrite {
171    pub valid: bool,
172    pub j: b8,
173    pub data: [b32; CHUNK],
174}
175
176/// Shadow commit or discard.
177#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
178pub struct ShadowCommit {
179    pub valid: bool,
180    pub commit: bool,
181    pub low: b32,
182}
183
184/// Phases of the catch-up.
185pub mod phase {
186    pub const IDLE: u128 = 0;
187    /// An offer's key is open; waiting for its certificate.
188    pub const OFFER: u128 = 1;
189    /// Requesting state from `peer`.
190    pub const REQUEST: u128 = 2;
191    /// Receiving chunk `j`, its digest in flight or done.
192    pub const CHUNKS: u128 = 3;
193    /// The final commit is out.
194    pub const COMMIT: u128 = 4;
195}
196
197/// State.
198#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
199pub struct CkState {
200    pub configured: bool,
201    pub epoch: b32,
202    pub n: b5,
203    pub me: b5,
204    pub session: b64,
205    pub deadline: b32,
206    pub clock: b32,
207    /// Our own latest checkpoint.
208    pub own_valid: bool,
209    pub own_low: b32,
210    pub own_digest: [b64; 4],
211    pub own_sign_sent: bool,
212    pub own_opened: bool,
213    pub own_given: bool,
214    pub own_shared: bool,
215    pub own_sig: [b64; 8],
216    pub own_signed: bool,
217    /// The key the collector holds now (own, or an offer's).
218    pub key_low: b32,
219    pub key_digest: [b64; 4],
220    pub key_open: bool,
221    /// The highest certified checkpoint.
222    pub cert_valid: bool,
223    pub cert_low: b32,
224    pub cert_digest: [b64; 4],
225    /// The state installed by the last catch-up (behind means below both
226    /// this and `next_decide`).
227    pub have_low: b32,
228    /// Catch-up.
229    pub phase: b3,
230    pub since: b32,
231    pub peer: b5,
232    pub j: b8,
233    pub chain_sent: bool,
234    pub acc: [b64; 4],
235    pub h_sign: CkSignReq,
236    pub h_open: CkKey,
237    pub h_own: CkKey,
238    pub h_share: CkKey,
239    pub h_req: StateReq,
240    pub h_dig: CkDigestReq,
241    pub h_shadow: ShadowWrite,
242    pub h_commit: ShadowCommit,
243    pub jump: bool,
244    pub refused: b32,
245}
246
247/// One link of the state chain: `"RUB2-STA" ‖ session ‖ low ‖ j ‖ h_j ‖
248/// chunk_j` (128 bytes, big-endian SHA-512 words).
249#[kernel]
250pub fn state_block(session: b64, low: b32, j: b8, acc: [b64; 4], data: [b32; CHUNK]) -> [b64; 16] {
251    let mut le = [b64(0); 16];
252    le[0] = b64(STA_DOMAIN);
253    le[1] = session;
254    le[2] = low.resize::<64>() | (j.resize::<64>() << b64(32));
255    for k in 0..4 {
256        le[3 + k] = acc[k];
257    }
258    for k in 0..CHUNK {
259        let w = (k >> 1) + 7;
260        let sh = (k & 1) * 32;
261        le[w] = le[w] | (data[k].resize::<64>() << b64(sh as u128));
262    }
263    let mut be = [b64(0); 16];
264    for k in 0..16 {
265        be[k] = bswap64(le[k]);
266    }
267    be
268}
269
270/// One cycle of checkpointing and catch-up. `K` chunks make a state;
271/// `CS` is log2 of the checkpoint interval.
272#[kernel]
273pub fn ck_step<const K: usize, const CS: usize>(i: CkIn, r: CkState) -> (CkOut, CkState) {
274    let mut s = r;
275    if i.cfg.init {
276        s.own_valid = false;
277        s.own_sign_sent = false;
278        s.own_opened = false;
279        s.own_given = false;
280        s.own_shared = false;
281        s.own_signed = false;
282        s.key_open = false;
283        s.cert_valid = false;
284        s.cert_low = b32(0);
285        s.have_low = b32(0);
286        s.phase = b3(phase::IDLE);
287        s.clock = b32(0);
288        s.h_sign.valid = false;
289        s.h_open.valid = false;
290        s.h_own.valid = false;
291        s.h_share.valid = false;
292        s.h_req.valid = false;
293        s.h_dig.valid = false;
294        s.h_shadow.valid = false;
295        s.h_commit.valid = false;
296        s.jump = false;
297        s.refused = b32(0);
298        s.configured = i.cfg.n >= b5(3) && i.cfg.n <= b5(16) && i.cfg.me < i.cfg.n && i.cfg.session != b64(0) && i.cfg.deadline != b32(0);
299        s.epoch = r.epoch + b32(1);
300        s.n = i.cfg.n;
301        s.me = i.cfg.me;
302        s.session = i.cfg.session;
303        s.deadline = i.cfg.deadline;
304    }
305    let run = r.configured && !i.cfg.init;
306    s.clock = r.clock + b32(1);
307    let mut cmask = b32(0);
308    for k in 0..CS {
309        cmask = cmask | (b32(1) << b32(k as u128));
310    }
311    let mut o = CkOut {
312        offer_ready: false,
313        chunk_ready: false,
314        sign_req: r.h_sign,
315        open: r.h_open,
316        own: r.h_own,
317        share_send: r.h_share,
318        state_req: r.h_req,
319        digest_req: r.h_dig,
320        shadow_write: r.h_shadow,
321        shadow_commit: r.h_commit,
322        cert_valid: r.cert_valid,
323        cert_low: r.cert_low,
324        cert_digest: r.cert_digest,
325        jump: r.jump,
326        jump_low: r.cert_low,
327        refused: r.refused,
328    };
329    if i.cfg.init {
330        o.sign_req.valid = false;
331        o.open.valid = false;
332        o.own.valid = false;
333        o.share_send.valid = false;
334        o.state_req.valid = false;
335        o.digest_req.valid = false;
336        o.shadow_write.valid = false;
337        o.shadow_commit.valid = false;
338        o.jump = false;
339    }
340    if !i.cfg.init {
341        if r.h_sign.valid && i.sign_ready {
342            s.h_sign.valid = false;
343        }
344        if r.h_open.valid && i.key_ready {
345            s.h_open.valid = false;
346        }
347        if r.h_own.valid && i.key_ready && !r.h_open.valid {
348            s.h_own.valid = false;
349        }
350        if r.h_share.valid && i.share_ready {
351            s.h_share.valid = false;
352        }
353        if r.h_req.valid && i.req_ready {
354            s.h_req.valid = false;
355        }
356        if r.h_dig.valid && i.digest_ready {
357            s.h_dig.valid = false;
358        }
359        if r.h_shadow.valid && i.shadow_ready {
360            s.h_shadow.valid = false;
361        }
362        if r.h_commit.valid && i.shadow_ready && !r.h_shadow.valid {
363            s.h_commit.valid = false;
364        }
365        s.jump = false;
366    }
367    if r.h_open.valid {
368        o.own.valid = false;
369    }
370    if r.h_shadow.valid {
371        o.shadow_commit.valid = false;
372    }
373
374    // ---------------------------------------------------- our checkpoint
375    // Only at a checkpoint boundary, only forward.
376    if run && i.app.valid && (i.app.low & cmask) == b32(0) && i.app.low != b32(0) && (!r.own_valid || i.app.low > r.own_low) && r.phase == b3(phase::IDLE) {
377        s.own_valid = true;
378        s.own_low = i.app.low;
379        s.own_digest = i.app.digest;
380        s.own_sign_sent = false;
381        s.own_opened = false;
382        s.own_given = false;
383        s.own_shared = false;
384        s.own_signed = false;
385    }
386    let own_seq: b32 = r.own_low >> b32(CS as u128);
387    if run && r.own_valid && !r.own_sign_sent && !r.h_sign.valid {
388        s.h_sign = CkSignReq { valid: true, epoch: r.epoch, context: share_context(b8(ROLE_CHECKPOINT), b32(0), own_seq, r.own_digest) };
389        s.own_sign_sent = true;
390    }
391    if run && i.signed && r.own_sign_sent && !r.own_signed {
392        s.own_signed = true;
393        s.own_sig = i.sig;
394    }
395    if run && r.own_valid && !r.own_opened && !r.h_open.valid && r.phase == b3(phase::IDLE) {
396        s.h_open = CkKey { valid: true, instance: own_seq, digest: r.own_digest, sig: [b64(0); 8] };
397        s.own_opened = true;
398        s.key_low = r.own_low;
399        s.key_digest = r.own_digest;
400        s.key_open = true;
401    }
402    if run && r.own_signed && r.own_opened && !r.own_given && !r.h_own.valid && !r.h_open.valid {
403        s.h_own = CkKey { valid: true, instance: own_seq, digest: r.own_digest, sig: r.own_sig };
404        s.own_given = true;
405    }
406    if run && r.own_signed && !r.own_shared && !r.h_share.valid {
407        s.h_share = CkKey { valid: true, instance: own_seq, digest: r.own_digest, sig: r.own_sig };
408        s.own_shared = true;
409    }
410
411    // ---------------------------------------------------- certification
412    // The certificate is for exactly the open key (UE-C20).
413    if run && r.key_open && i.certified && !r.h_open.valid && (!r.cert_valid || r.key_low > r.cert_low) {
414        s.cert_valid = true;
415        s.cert_low = r.key_low;
416        s.cert_digest = r.key_digest;
417        if r.phase == b3(phase::OFFER) {
418            s.phase = b3(phase::REQUEST);
419            s.since = r.clock;
420        }
421    }
422
423    // ---------------------------------------------------- offers
424    // Taken only when idle and useful: a checkpoint above what we have.
425    let useful = i.offer.from < r.n && i.offer.from != r.me && (i.offer.low & cmask) == b32(0) && i.offer.low > i.next_decide && (!r.cert_valid || i.offer.low > r.cert_low);
426    o.offer_ready = run && r.phase == b3(phase::IDLE) && !r.h_open.valid;
427    if run && i.offer.valid && o.offer_ready {
428        if useful {
429            s.h_open = CkKey { valid: true, instance: i.offer.low >> b32(CS as u128), digest: i.offer.digest, sig: [b64(0); 8] };
430            s.key_low = i.offer.low;
431            s.key_digest = i.offer.digest;
432            s.key_open = true;
433            s.phase = b3(phase::OFFER);
434            s.since = r.clock;
435            s.peer = i.offer.from;
436        } else {
437            s.refused = r.refused + b32(1);
438        }
439    }
440    // An offer that does not certify in time is dropped.
441    if run && r.phase == b3(phase::OFFER) && r.clock - r.since >= r.deadline {
442        s.phase = b3(phase::IDLE);
443        s.key_open = false;
444        s.refused = r.refused + b32(1);
445    }
446
447    // ---------------------------------------------------- behind: fetch state
448    if run && r.phase == b3(phase::IDLE) && r.cert_valid && i.next_decide < r.cert_low && r.have_low < r.cert_low {
449        s.phase = b3(phase::REQUEST);
450        s.since = r.clock;
451    }
452    if run && r.phase == b3(phase::REQUEST) && !r.h_req.valid {
453        // Ask the current peer, then move on to the next if it is us.
454        let peer = if r.peer == r.me { if r.peer + b5(1) >= r.n { b5(0) } else { r.peer + b5(1) } } else { r.peer };
455        s.peer = peer;
456        s.h_req = StateReq { valid: true, to: peer, low: r.cert_low };
457        s.phase = b3(phase::CHUNKS);
458        s.j = b8(0);
459        s.acc = [b64(0); 4];
460        s.chain_sent = false;
461        s.since = r.clock;
462    }
463    // Chunks: only from the asked peer, for this low, in order.
464    o.chunk_ready = run && r.phase == b3(phase::CHUNKS) && !r.chain_sent && !r.h_dig.valid && !r.h_shadow.valid;
465    if run && i.chunk.valid && o.chunk_ready {
466        let c = i.chunk;
467        if c.from == r.peer && c.low == r.cert_low && c.j == r.j && c.j < b8(K as u128) {
468            s.h_dig = CkDigestReq { valid: true, epoch: r.epoch, j: c.j, block: state_block(r.session, c.low, c.j, r.acc, c.data) };
469            s.h_shadow = ShadowWrite { valid: true, j: c.j, data: c.data };
470            s.chain_sent = true;
471            // The deadline is per chunk, so a long state is not cut off.
472            s.since = r.clock;
473        } else {
474            s.refused = r.refused + b32(1);
475        }
476    }
477    if run && i.digest.valid && i.digest.epoch == r.epoch && r.phase == b3(phase::CHUNKS) && r.chain_sent && i.digest.j == r.j {
478        s.acc = i.digest.digest;
479        s.chain_sent = false;
480        if r.j == b8((K - 1) as u128) {
481            // The whole state: commit it only if it is the certified one.
482            let good = i.digest.digest == r.cert_digest;
483            s.h_commit = ShadowCommit { valid: true, commit: good, low: r.cert_low };
484            if good {
485                s.phase = b3(phase::COMMIT);
486                s.have_low = r.cert_low;
487            } else {
488                // A bad state from this peer: discard and ask the next.
489                s.refused = r.refused + b32(1);
490                s.peer = if r.peer + b5(1) >= r.n { b5(0) } else { r.peer + b5(1) };
491                s.phase = b3(phase::REQUEST);
492            }
493        } else {
494            s.j = r.j + b8(1);
495        }
496    }
497    // A peer that does not deliver in time is replaced by the next.
498    if run && r.phase == b3(phase::CHUNKS) && !r.chain_sent && r.clock - r.since >= r.deadline {
499        s.h_commit = ShadowCommit { valid: true, commit: false, low: r.cert_low };
500        s.peer = if r.peer + b5(1) >= r.n { b5(0) } else { r.peer + b5(1) };
501        s.phase = b3(phase::REQUEST);
502        s.refused = r.refused + b32(1);
503    }
504    // The commit was taken: consensus jumps to `low`, once.
505    if run && r.phase == b3(phase::COMMIT) && !r.h_commit.valid {
506        s.jump = true;
507        s.phase = b3(phase::IDLE);
508    }
509    (o, s)
510}
rhdl_ubft/checkpoint.rs

rhdl_ubft/
checkpoint.rs
