PaperlayerView exact revision on arXiv

Source-linked AI summary

Seamless Reconfiguration for DAG-BFT

Michael Yiqing Hu, Leander Jehl, Paul Franke-Bergmann, Jialin Li, Christian Berger

arXiv:2610.00896v1cs.DC

TL;DR

DAG-based Byzantine atomic broadcast protocols generally assume fixed membership, while deployed systems need to change membership and existing approaches pause dissemination or defer changes to epoch boundaries. The paper presents a seamless reconfiguration protocol that changes membership and quorum thresholds while dissemination continues. It proves the protocol implements dynamic DAG-based Byzantine atomic broadcast under its stated model and assumptions.

  • Problem

    DAG-based protocols largely assume fixed membership, while deployed systems need to add and remove nodes and adjust quorum thresholds without pausing dissemination or waiting for epoch boundaries.

    Source: §1 · p. 2

  • Method

    The protocol extends multi-configuration operation to the DAG, recording installed, pending, and enabled configurations in blocks and using a four-round transition window with state transfer.

    Source: §1 · p. 2

  • Results

    For every finite sequence of reconfiguration messages with no a priori length bound, the protocol implements leader-level Dynamic DAG Byzantine Atomic Broadcast under the stated model and conditional probability requirement.

    Source: §5 · p. 15

  • Takeaways & Limitations

    Membership and quorum thresholds can change while dissemination continues, with processes locally interpreting their view of the DAG.

    Source: §6 · p. 16

    The paper leaves open whether seamless, non-blocking transitions can overlap and whether a reconfiguration can add or remove multiple processes at once.

    Source: §6 · p. 16

Abstract

from arXiv · show

Byzantine Atomic Broadcast in Asynchronous networks has been studied extensively for decades. The FLP impossibility result rules out deterministic consensus in a fully asynchronous setting, motivating randomized protocols that combine reliable broadcast with private coins to achieve termination with probability one. More recently, DAG-Rider popularized a new abstraction in which processes continuously reliably broadcast blocks to construct a directed acyclic graph (DAG) and then locally derive a total order using a randomized perfect coin. This separation of dissemination from ordering has renewed interest in asynchronous DAG-based Byzantine fault tolerance and inspired numerous protocols that improve expected latency or throughput. Reconfiguration, however, remains largely unexplored. Existing DAG-based BFT protocols generally assume a static set of processes, whereas deployed systems must occasionally add or remove nodes in response to operational demands. Existing solutions are not seamless; they either pause the system or delay membership changes until a predetermined epoch boundary. This may be impractical and can introduce downtime. However, a seamless solution is non-trivial; agreement on when to start utilizing a new configuration may yield a logical round number that was already surpassed by the concurrent asynchronous dissemination. In this work, we present a seamless reconfiguration protocol for asynchronous DAG-based Byzantine atomic broadcast. Our protocol allows the DAG to continue growing while the membership and corresponding quorum thresholds change, without halting the system. To the best of our knowledge, ours is the first protocol to provide seamless reconfiguration for DAG-based Byzantine atomic broadcast in a fully asynchronous network.

1 Introduction

DAG-based Byzantine atomic broadcast separates continuous dissemination from ordering, but existing reconfiguration approaches pause the protocol or wait for an epoch boundary. This work presents a seamless reconfiguration protocol that keeps dissemination running as membership and quorum thresholds change.

1 Introduction

  • Existing DAG-based protocols largely assume fixed membership, while deployments need to add and remove nodes and adjust quorum thresholds.Current deployments either pause the protocol during changes or defer them to predetermined epoch boundaries [2, 9, 24].Source: §1 · p. 2
  • A single consensus-layer switching point can leave asynchronous processes producing blocks past that point under the old configuration, forcing dissemination to wait or discard blocks.Reconfiguration without consensus avoids needing such a point, but DAG-based broadcast must also reconfigure DAG thresholds and the randomized perfect coin while preserving reliable broadcast.Source: §1 · p. 2
  • Each block records its broadcaster’s installed configuration, pending reconfiguration, and configurations enabled in its round.Old members enable both configurations for four rounds after installing a transition; retained processes keep producing blocks and delivered blocks remain in the DAG.Source: §1 · pp. 2–3
  • The protocol is presented as the first provably correct seamless reconfiguration for DAG-based Byzantine atomic broadcast in a fully asynchronous network.Processes locally interpret their DAG view while membership and quorum thresholds change.Source: §1 · pp. 2–3
  • The work defines a reconfigurable dissemination abstraction and builds seamless reconfiguration from configuration-scoped reliable broadcast, a four-round transition window, and state transfer for joining processes.Its ordering adaptation scopes DAG-Rider’s randomized perfect coin to one configuration, and the composition is proved to satisfy the stated definitions.Source: §1 · p. 3

2 Background

DAG-Rider constructs a round-based DAG through reliable broadcast, then derives a total order by selecting leaders from the DAG. The paper uses DAG-Rider as a framework for seamless reconfiguration.

2 Background

  • Each process contributes at most one block per round, and each block references at least a quorum of blocks from the preceding round.Reliable broadcast ensures non-equivocation, and eventual completion by correct processes leaves sufficient blocks to proceed.Source: §2 · p. 3
  • DAG-Rider selects leaders with a perfect coin using signature shares from the wave’s last-round blocks, yielding a canonical leader list whose causal histories determine total order.The ordering layer uses already disseminated information and requires no additional communication.Source: §2 · p. 3
  • The paper adapts DAG-Rider’s reliable broadcast, DAG construction, and leader election components to support seamless addition and removal of processes.Source: §2 · p. 3

3 Problem Definition and Primitives

This section defines a configuration-scoped model for asynchronous DAG dissemination and reconfiguration, including transition-aware validity and progress requirements, and introduces the BRB, DAG-BB, and coin primitives. It also defines a configuration-scoped perfect coin and dynamic leader-level Byzantine atomic-broadcast abstraction, specifying its safety and progress requirements and stating that the protocol components implement it.

3.4 Rounds and DAG notation

  • The protocol organizes dissemination into logical rounds grouped in four-round waves, with each DAG block carrying its payload, round, certificate, parent references, and configuration-related metadata.Logical rounds are protocol indices rather than timing bounds; the block metadata includes local configuration, pending reconfiguration, and enabled configurations.Source: §3.4 · p. 5

3.5 Reconfiguration Model

  • The reconfiguration model assumes authenticated, sequential changes of at most one member, with earliest-round constraints preventing overlap and only finitely many changes per execution.The membership-selection mechanism is out of scope; the assumed dealer distributes valid changes, and at least qL correct members of the final configuration remain active.Source: §3.2 · p. 4, §3.5 · pp. 5–6
  • Enabled configurations are recorded per process and round as either a singleton or a valid transition pair, defining transition windows while allowing processes to advance asynchronously.Once assigned, each enabled-configurations value is immutable; after all finite reconfigurations complete, all subsequent waves are stable under the final configuration.Source: §3.5 · p. 6

3.6 Configuration-scoped Byzantine Reliable Broadcast

  • Configuration-scoped BRB certifies delivered blocks and provides agreement and integrity for each round-broadcaster slot, including when certification occurs during a transition.Participation is restricted to members of the declared configuration that is enabled for that round, and delivered values carry a certificate under that configuration’s key.Source: §3.6 · p. 7

3.7 Dynamic DAG-structured Byzantine Broadcast

  • Dynamic DAG-BB requires integrity, consistency, and causal closure, plus quorum-based round progress and eventual completion of valid transitions, even while processes occupy different transition stages.The applicable quorum during a transition may be either configuration’s threshold; after the finite reconfiguration sequence, continued activity in the final configuration yields stable waves.Source: §3.7 · p. 8

BRB to DAG

  • A process DAG-delivers a block only after validating its certificate and metadata and obtaining its referenced parents and ancestors; joining processes validate transferred ancestor-closed state first.BRB delivery alone does not insert a block into the DAG.Source: BRB to DAG · p. 8
  • Dynamic DAG-BB omits universal Validity and Totality during reconfiguration, relying instead on quorum progress and safety properties; totality and validity can be ensured again in stable waves.Strong departure-oblivious Validity and Totality are impossible in an asynchronous dynamic system even with reliable links and one possible crash failure [12, Appendix A.6].Source: §3.7 · p. 8, BRB to DAG · p. 9

3.8.1 Configuration-scoped Perfect Coin

  • Each configuration-scoped perfect-coin instance selects one member of that configuration, using separate keys and shares for different configurations.The coin provides agreement, termination when at least fl + 1 correct members invoke it, and unpredictability until that invocation threshold is reached.Source: §3.8.1 · p. 9
  • The configuration-scoped coin selects each member of Π_l with probability 1/n_l, while coin unpredictability is used only for probabilistic progress, not safety.For a correct process’s block at the last round of a wave, its coin share is scoped to the local configuration; safety uses Agreement and signature uniqueness.Source: §3.8.1 · p. 9

3.8.2 Atomic-broadcast Abstraction

  • Finalized leaders are DAG blocks selected by the ordering layer and appended to each active correct process’s local finalized-values sequence.A finalized block must already be in that process’s DAG; the abstraction requires at most one block per wave and no repeated block.Source: §3.8.2 · pp. 9–10
  • The abstraction requires prefix-comparable finalized sequences and, with probability one, infinitely many finalized blocks for correct processes in the final configuration that remain active.It omits proposal validity and eventual agreement for removed processes; after leaving, a removed process has no requirement for further sequence extensions.Source: §3.8.2 · p. 10
  • The protocol’s broadcast, DAG, state-transfer, and reconfiguration algorithms implement Dynamic DAG-BB, and the stated leader properties compose into Dynamic DAG Byzantine Atomic Broadcast.The section points to Lemma 51, Corollary 64, Theorems 65 and 72, and Theorem 3 for these claims.Source: §3.8.2 · p. 10

4 Seamless DAG Reconfiguration

The section specifies a four-round transition that lets DAG block production continue while configurations change, and adapts ordinary operation, joining, leaving, and leader election to that transition.

4 Seamless DAG Reconfiguration

  • A four-round transition lets retained processes keep producing blocks while the joining process connects old causal history to blocks declared under the new configuration.Blocks record enabled configurations; leader-voting shares and support thresholds are scoped to one configuration.Source: §4 · p. 10, §4.3 · p. 14

4.1 Ordinary DAG Operation

  • Each append snapshots installed, pending, and enabled configuration metadata; recipients insert a certified block only after validating it and obtaining its complete causal history.Processes advance when the preceding layer meets the applicable parent quorum, which changes during the final transition round.Source: §4.1 · pp. 10–11

State Availability

  • Blocks are sent to known identities after certification, DAG insertion, or FloodDAG, and received blocks are buffered until admissible.Source: State Availability · p. 11

4.2 Beginning and Completing a Configuration Change

  • After marked blocks trigger installation, old members enable both configurations for four rounds and install the new one at r+4, although their install rounds may differ by at most one.Figure 1 shows p5 producing transition blocks in r+5 and r+6 before normal operation in r+7.Source: §4.2 · pp. 11–12, Figure 1 · p. 12

Joining Procedure

  • Joiners obtain validated ancestor-closed history, remain passive in u+1, produce two transition blocks, and install the new configuration at u+4.They continue requesting blocks until the local DAG contains a qualifying old-configuration round and enough following-round blocks.Source: Joining Procedure · pp. 12–13

Leaving Procedure

  • A leaving process stops producing blocks after transition installation but continues helping reliable broadcasts and serving DAG requests until enough next-configuration blocks exist.It then performs a final FloodDAG before stopping its remaining tasks.Source: Leaving Procedure · p. 13, Figure 2 · p. 13

4.3 Configuration-scoped Leader Election

  • Leader-election shares and support thresholds are configuration-scoped; transition blocks may be candidates but do not count as leader-voting blocks, and shares from different configurations are never combined.The protocol relies on reconfigurations eventually ceasing for leader-election liveness.Source: §4.3 · pp. 14–15
  • A reconstructed configuration-scoped coin selects a leader candidate, and backward scans of its causal history produce nested finalized leader prefixes.A later-wave scan accepts an earlier candidate only when the required same-configuration voting blocks support it.Source: §4.3 · p. 14

5 Correctness

The correctness theorem covers every finite sequence of reconfigurations, with no a priori length bound. The proof establishes broadcast and ordering properties, and probabilistic progress under the stated assumptions.

Theorem 3

  • For every finite sequence of reconfiguration messages, with no a priori bound on its length, the protocol implements leader-level Dynamic DAG Byzantine Atomic Broadcast under the stated assumptions.Probabilistic Progress additionally assumes the conditional probability requirement of Section B.3.Source: §5 · p. 15

Broadcast safety

  • Certificate checks and quorum intersection establish BRB integrity and agreement; validating each parent and ancestor before insertion gives DAG integrity, consistency, and causal closure.Source: §5 · p. 15

Reconfiguration progress

  • Transition marking and history dissemination ensure old members install within one round and joiners broadcast transition blocks; the fault bound preserves quorum progress despite Byzantine additions or removals.Source: §5 · p. 15

Ordering and probabilistic progress

  • Configuration-scoped voting yields unique leaders and nested finalized prefixes; after transitions cease, every active correct final member finalizes infinitely many blocks with probability one.Source: §5 · p. 16

6 Conclusion and Open Questions

This section summarizes how the seamless reconfiguration protocol maintains DAG operation across configuration transitions, including cross-transition appending, DAG-state transfer and validation, staged joining, and leader election and finalization. It also identifies open questions about overlapping transitions, adding or removing multiple processes at once, and partial synchrony.

6 Conclusion and Open Questions

  • The protocol enables membership and quorum thresholds to change while DAG dissemination continues, with processes interpreting their DAG view locally.The authors describe it as the first seamless reconfiguration protocol for DAG-based Byzantine atomic broadcast in a fully asynchronous network.Source: §6 · p. 16
  • Open questions include overlapping non-blocking transitions, changing multiple memberships at once, and whether partial synchrony could yield more elegant solutions.Source: §6 · p. 16

A.1 Local Variables and Threshold Functions

  • Validations check reconfiguration authorization and membership changes, while a joining-process parent-count exception depends on the process’s enabled configuration for that round.Ordinarily, a block requires the declared configuration’s quorum of parents; the exception permits the old configuration’s quorum for qualifying joining blocks.Source: §A.1 · p. 19

A.2 Configuration-Scoped Byzantine Reliable Broadcast

  • Configuration-scoped BRB sends proposals to enabled-configuration members and forms a certificate after quorum votes, then floods the certified block to known identities.A quorum of valid echoes triggers voting, while f_c + 1 valid votes can also prompt a process to vote.Source: §A.2 · p. 21

A.3 DAG Append and DAG Delivery

  • DAG append fixes a quorum of parent references before setting any coin share, and delivery validates certificates and metadata, fetches missing parents, then inserts admissible blocks.FloodDAG sends stored certified blocks to known identities, and active correct processes continue invoking it while active.Source: §A.3 · p. 22

A.4 Reconfiguration

  • When enough blocks mark a pending transition, processes enable both configurations for rounds r + 1 through r + 4, then install the successor before ordinary production in round r + 4.The threshold is f_l + 1 marked blocks; round advancement also has a rule allowing a transitioning process to use later DAG layers in specified rounds.Source: §A.4 · p. 24

A.5.1 Transition Append

  • A joining process appends transition blocks only in rounds r0 + 2 and r0 + 3, using q_l parents, declaring the successor configuration and enabling pair, and setting no coin share.Source: §A.5.1 · p. 24
  • A transition enables both configurations for rounds r+1 through r+4; at round r+4, departing members finish pending appends and cease protocol work.Before stopping, a departing member waits for enough admissible identifiers under the new configuration and floods the DAG. Joining processes finish the transition at round r+4 before starting post-join tasks.Source: §A.5.1 · p. 25, §A.5.3 · p. 28

A.5.2 State Transfer

  • State transfer repeatedly requests peers’ histories, validates finite ancestor-closed DAG state against the incoming configuration, merges parents before children, and discovers the least qualifying old-configuration round.Discovery requires at least q_l old-configuration blocks and f_l + 1 blocks marked by the incoming configuration in the same layer.Source: §A.5.2 · p. 26

A.5.3 Joining Operation

  • Joining is staged: history tasks start before discovery, catch-up tasks start after discovery and round-(u + 1) blocks are obtained, and post-join tasks start after the transition completes.History tasks may insert and deliver certified blocks but do not append blocks, echo, vote, or advance rounds.Source: §A.5.3 · pp. 26, 28

A.6 Leader Election and Finalization

  • Leader election combines exactly f_l + 1 valid configuration-scoped coin shares, then finalizes elected blocks by scanning earlier waves backward and accepting uniquely supported candidates.The backward scan requires history support of at least f_l + 1; ambiguous skipped waves are not reconsidered.Source: §A.6 · p. 28

B Proofs

This part proves the protocol’s broadcast, reconfiguration, ordering, and probabilistic-progress guarantees using a configuration-level induction. It also establishes safeguards on when transitions can be installed and how old-configuration contributions are bounded for removal transitions.

B Proofs

  • The six-step proof plan culminates in Dynamic DAG Byzantine Atomic Broadcast, combining reconfiguration completion and broadcast, leader integrity and total order, and probabilistic progress.The final probabilistic-progress result states that each correct RL-member that remains active finalizes infinitely many blocks with probability one.Source: B Proofs · p. 32

B.1 Dynamic DAG-structured Byzantine Broadcast Progress and Reconfiguration

  • BRB preserves integrity, and when certificates for a slot use one configuration or the two configurations of one valid transition, they cannot bind conflicting values.For a correct broadcaster, every valid certificate binds the value supplied to its prescribed BRB invocation.Source: §B.1 · p. 34

B.1.1 Consequences of the Issuance Rule for Earliest-Inclusion and Install Transition Rounds

  • No certified block below δl+1 can carry Rl+1 in its pending field; before acting in round δl+1−1, an active correct Rl-member has installed Rl and, if l > 1, completed its transition into Rl.The installation and completion guarantee assumes the configuration-level induction hypothesis and the established conclusions for preceding transitions.Source: §B.1.1 · p. 35
  • Every assigned round-δl+1 enabled-configs value of a correct Rl-member is {Rl}.This follows from the absence of earlier Rl+1 markings and the rule that installation assigns the transition pair only to later rounds.Source: §B.1.1 · p. 36
  • Until it invokes FinishTransition, a correct process’s blocks counted toward an Rl parent quorum have broadcasters belonging to members(Rl).The lemma applies from round δl+1−1 onward and assumes the induction hypothesis and conclusions for preceding transitions.Source: §B.1.1 · p. 36
  • For a removal transition, rounds s ≥ δ_{l+1} − 1 exclude R_{l−1}, so its round-s BRB instances receive fewer than q_l − 1 vote shares.Blocks declared under R_{l+1} cannot be counted as parents under R_l; every remaining counted block has a broadcaster in R_l, including a member removed by the transition.Source: §B.1.1 · pp. 36–37
  • No correct process invokes InstallTransition for R_l → R_{l+1} with an install round below δ_{l+1}, the earliest inclusion round of R_{l+1}.An invocation requires round-a_i blocks marked for the transition or discovery of those blocks; their causal history would need a certified block pending R_{l+1}, which cannot occur before δ_{l+1}.Source: §B.1.1 · p. 37

B.1.2 Enabled-Configs Alignment and BRB Agreement During Rl →Rl+1

The proof establishes that enabled-configuration assignments remain aligned and BRB Agreement holds while a correct old member still enables Rl. It also bounds when later configurations can become active, preventing transition windows from overlapping.

B.1.2 Enabled-Configs Alignment and BRB Agreement During Rl →Rl+1

  • The next transition’s earliest inclusion round is at least t + 6, so distinct transition windows do not overlap and well-spacing is derived rather than assumed.Issuing Rl+2 requires a correct Rl-member to invoke InstallTransition for Rl → Rl+1.Source: §B.1.2 · pp. 37–38
  • A correct Rl-member’s round-(t + 1) block is marked when delivered, and a correct member advancing to t + 2 installs in round t or t + 1.Marked round-t blocks that justify the earliest installation propagate through DAG delivery; a member that advances without installing at t obtains marked parents and installs at t + 1.Source: §B.1.2 · pp. 38–39
  • Under Lemma 14’s assumptions, any correct process in members(Rl) that advances to round t + 2 has invoked InstallTransitioni(Rl, Rl+1, ai) for some ai in {t, t + 1}.Source: §B.1.2 · p. 39
  • Every valid round-r certificate during this transition is declared under Rl or Rl+1, excluding certificates from earlier or later configurations.The proof uses the transition’s earliest-inclusion bounds and rejection of configurations before their authenticated earliest-inclusion rounds.Source: §B.1.2 · pp. 37, 39, 40
  • While a correct Rl-member’s assigned value contains Rl, correct members’ enabled-configs values stay aligned and BRB Agreement holds for every round-broadcaster slot.The proof proceeds by ruling out a first round of misalignment or failed BRB Agreement.Source: §B.1.2 · p. 41

B.1.3 DAG Progress and Round Advancement under BRB Agreement

The section establishes conditional DAG delivery and round advancement under BRB Agreement, including ordinary and transition-specific quorum paths. It also specifies how transferred state is validated and how delivery guarantees are bounded for removed processes.

B.1.3 DAG Progress and Round Advancement under BRB Agreement

  • Transition-round iterations terminate through ordinary quorum advancement or, in the final transition rounds, an additional condition requiring q_l+1 admissible blocks from the next round.A correct process may advance from its final transition round by delivering q_l+1 admissible blocks there or in the following round and using the additional condition.Source: §B.1.3 · p. 42
  • Transferred state is validated independently of its sender: inserted blocks have valid certificates and checked parents, are ancestor-closed, and contain no duplicate round-broadcaster slots.Accepted blocks are merged in increasing round order, inserting parents before children.Source: §B.1.3 · p. 43
  • A correct process eventually DAG-delivers a finite ancestor-closed set when it is known to the sender and the recipient remains active, processes messages, and passes metadata, parent, and slot checks.For a correct removed recipient, delivery is guaranteed only before it leaves; its receive and fetch tasks must remain active until the needed blocks and ancestors arrive.Source: §B.1.3 · pp. 43–44
  • With BRB Agreement, q_l active correct broadcasters that continue their BRB tasks eventually form valid certificates, and active R_l members DAG-deliver the resulting blocks.Delivery requires recipients to remain active and process certified-block messages and FetchAndDeliver while a block is missing.Source: §B.1.3 · pp. 44–45
  • In rounds r0+2 or r0+3, a transitioning process eventually advances after DAG-delivering q_l+1 admissible next-round blocks while it remains active and fetches.The blocks must occupy distinct round-broadcaster slots; delivery of them satisfies the additional transition-round condition.Source: §B.1.3 · pp. 45–46
  • A correct R_l member that stays active and processes certified blocks and fetches eventually DAG-delivers q_l admissible round-r blocks from distinct slots when q_l correct broadcasters continue their BRB tasks.Those blocks satisfy the ordinary parent-quorum condition for round advancement.Source: §B.1.3 · p. 46

B.1.4 Install-Transition-Round Bounds and BRB Agreement for a Correct Joining Process

This section bounds transition-round installation and advancement for old and joining processes, including ordinary and final iterations and continued departure tasks for correct removed processes. Under the stated assumptions, it also establishes BRB Agreement under a specified handoff condition and conditional parent-quorum progress during reconfiguration.

B.1.4 Install-Transition-Round Bounds and BRB Agreement for a Correct Joining Process

  • The earliest correct old-member install round t lies in {u−1, u, u+1}, and every correct old member installs in round t or t+1.Here u is the round returned by the correct joining process’s DiscoverBegin call.Source: §B.1.4 · pp. 47–48
  • A correct joining process’s install round differs from t by at most one; when t=u−1, u, or u+1, its round is respectively {u−1,u}, {u,u+1}, or u+1.Every correct old member’s install round also differs from the joining process’s by at most one.Source: §B.1.4 · pp. 48–49
  • When the joining process enables both configurations after correct old members stop voting under Rl, configuration-scoped BRB Agreement holds for every round-broadcaster.The proof shows every round-s certificate is declared under Rl+1, where quorum intersection gives Agreement.Source: §B.1.4 · pp. 49–50

B.1.5 Parent-Quorum Progress During Reconfiguration

  • Under the stated installation and discovery assumptions, each AdvanceRound iteration before ai+4 eventually terminates, and a correct joiner’s specified discovery wait eventually ends.If two correct Rl+1 members complete at consecutive round beginnings, the earlier one eventually satisfies its ordinary round-c parent-quorum condition.Source: §B.1.5 · pp. 50, 52, 53
  • Given the stated parent-block quorum in round ai+2 or ai+3, a correct process eventually reaches round ai+4 and invokes FinishTransition.The required quorum is ql+1 blocks in ParentBlocks(Rl+1, ai+4).Source: §B.1.5 · pp. 50–51
  • Before stopping, FloodDAG’s DAG_h contains, for a correct p_i, the required ordinary-round blocks when r=a_i+1; for r∈{a_i+2,a_i+3}, either those blocks or at least q_l+1 blocks in ParentBlocks_h(R_l+1,r+1).Source: §B.1.5 · p. 51
  • For a correct addition, the joining process’s round-(u + 1) q_l wait terminates, and certified dissemination plus BRB Agreement supplies its parent quorum without conflicting selected blocks.The two prescribed joining-process transition appends reach BRB-Broadcast once their waits are satisfied.Source: §B.1.5 · pp. 54–55
  • For iterations with an ordinary q_l threshold, each correct process advances by meeting q_l or, in round ai + 2, the additional q_l+1 condition; joining-process append invocations reach BRB-Broadcast.For a correct joining process, both prescribed transition appends reach BRB-Broadcast.Source: §B.1.5 · p. 55
  • A final transition-round iteration advances after q_l+1 admissible blocks arrive in that round or in round ai + 4 via the additional condition; consecutive completions preserve the earlier process’s ordinary round-c quorum.The consecutive-completion claim concerns correct Rl+1-members completing at the beginnings of rounds c and c + 1.Source: §B.1.5 · pp. 55–56
  • Every correct retained, joining, or removed process eventually reaches the beginning of round ai + 4; a correct removed process then continues its prescribed departure tasks.This corollary applies under the premises of Lemma 39.Source: §B.1.5 · p. 56

B.1.6 Transition Completion

The transition-completion proofs establish that every correct member of Rl+1 eventually completes the transition and that enough correct members eventually broadcast appends in a common round. When a correct member is removed, it waits for a qualifying new-configuration block before stopping its remaining tasks.

B.1.6 Transition Completion

  • Every correct Rl+1 member eventually completes the transition under the issuance-rule and configuration-level induction assumptions, with discovery required when adding a correct process.The joining process's DiscoverBegin return is assumed to be a round.Source: §B.1.6 · p. 56
  • Retained members install in t or t+1 and finish at ai+4; all correct retained members have completed by the beginning of t+5.A joining process invokes InstallTransition in the round returned by DiscoverBegin.Source: §B.1.6 · pp. 56–57
  • A removed correct process waits for an admissible round-(ai+5) block from an Rl+1 member in its DAG, then performs a final FloodDAG before leaving.While waiting, it continues processing certified-block messages and running FetchAndDeliver.Source: §B.1.6 · pp. 56, 57, 59
  • For a removal, at least ql+1 admissible round-v blocks occupy distinct Rl+1-member broadcaster slots.The proof excludes slots belonging only to earlier configurations and does not enable a later configuration in round v.Source: §B.1.6 · pp. 57–58
  • Eventually, all correct Rl+1 members enter a common round s, where at least ql+1 active correct members broadcast their prescribed appends.If all enter through the ordinary condition, s is the completion round; if a member uses the additional condition, dissemination lets them advance to the next round and append.Source: §B.1.6 · p. 59

B.1.7 Establishing the Prerequisites and Applying the Configuration-Level Induction

This section establishes prerequisites for carrying configuration-level induction through valid transitions, including correctness properties for dynamic DAG broadcast and bounds on overlapping transition windows. It also characterizes enabled-configuration values per logical round, showing that at most one valid transition can be involved and that singleton values are identical.

B.1.7 Establishing the Prerequisites and Applying the Configuration-Level Induction

  • A correct old member eventually invokes InstallTransition, and a correct joining process eventually obtains a qualifying round through DiscoverBegin.DiscoverBegin returns the least qualifying round then present in the joining process’s DAG, containing at least q_l old-member slots and f_l+1 marked blocks.Source: §B.1.7 · pp. 60–61
  • Every valid transition eventually completes at correct retained or joining processes and permits correct removed processes to leave, while establishing the induction hypothesis for a successor configuration.Correct retained or joining processes invoke InstallTransition and FinishTransition; the transition also guarantees progress by at least q_l+1 active correct members and extends BRB Agreement over the required rounds.Source: §B.1.7 · pp. 62–63

B.1.8 BRB Agreement for Every Round-Broadcaster Slot and Dynamic DAG-Structured Byzantine Broadcast Correctness

  • The configuration-scoped BRB algorithm satisfies Agreement across every round-broadcaster slot, and algorithms 2–7 implement Dynamic DAG-structured Byzantine Broadcast under the stated assumptions.The correctness proof covers integrity, DAG integrity and consistency, causal closure, per-round quorum progress, and transition completion.Source: §B.1.8 · pp. 63–65

B.2.1 Alignment of Enabled-Configs Values Across Correct Processes in the Same Logical Round

  • Each nonempty transition window lies within [t_l, t_l+5], and windows for distinct issued transitions are strictly ordered and disjoint.Thus, for any logical round, at most one transition can have correct processes assigning its configuration pair in that round.Source: §B.2.1 · p. 65
  • Correct processes cannot assign the two different singleton values for a transition in the same round.When all values are singletons, adjacent configurations are excluded by the transition-pair result, and nonadjacent configurations by the earliest-inclusion bounds.Source: §B.2.1 · pp. 66, 68
  • In any logical round, correct processes’ enabled-configs values involve at most one valid transition, and singleton values cannot differ.The values are either the same singleton or the endpoints and transition pair for one adjacent configuration transition.Source: §B.2.1 · pp. 67–68
  • For each transition, a process’s enabled-configs values progress from the old singleton to the transition pair and then the new singleton.The proof rules out earlier or later configurations in that round using install-transition and earliest-inclusion round bounds.Source: §B.2.1 · p. 67

B.2.2 Leader Uniqueness and Direct-Anchor Reachability

The section establishes that correct processes identify the same leader for a wave despite configuration changes. It then proves that later blocks retain enough causal support for backward scans to accept earlier direct anchors.

B.2.2 Leader Uniqueness and Direct-Anchor Reachability

  • All correct processes identify the same block as a direct anchor or accept it during a backward scan for a given wave.Threshold-signature uniqueness selects the same leader slot, and DAG consistency makes the block in that slot unique.Source: §B.2.2 · p. 69
  • When an Rl-typed direct anchor is identified, every valid certificate in that wave’s last round is declared under Rl, with its broadcaster a member of Rl.The result applies to valid BRB certificates for blocks in the direct anchor’s last round.Source: §B.2.2 · p. 69
  • Every later-wave block delivered by a correct process reaches at least 2fl + 1 distinct blocks broadcast by Rl members in the direct anchor’s last round.The reached blocks have distinct broadcaster identifiers.Source: §B.2.2 · p. 70
  • A later-wave block’s causal history contains at least fl + 1 distinct Rl-typed leader-voting blocks that reach the earlier direct anchor.This support satisfies the backward-scan acceptance condition, so a correct process accepts that anchor when its scan reaches the wave.Source: §B.2.2 · p. 72

B.2.3 Backward Scans, Finalized Leader Sequences, and Total Order

Backward scans produce consistent leader sequences across processes, and sequences rooted at later direct anchors extend those rooted earlier. Finalized sequences remain prefixes of one canonical sequence, yielding a shared total order.

B.2.3 Backward Scans, Finalized Leader Sequences, and Total Order

  • Full backward scans rooted at the same direct anchor produce the same sequence, independent of the process and later-delivered blocks outside that anchor’s causal history.The candidate set depends on the anchor’s causal history; matching history support and unique coin selection give matching candidates.Source: §B.2.3 · p. 73
  • The sequence from an earlier direct anchor is a prefix of the sequence from a later one, yielding a canonical leader sequence of which every such sequence is a prefix.The canonical sequence may be finite or infinite.Source: §B.2.3 · p. 74
  • At every local state, a correct process’s finalized leader sequence is the canonical prefix associated with its greatest completed election wave.When a later wave is elected, the process appends the suffix extending its existing prefix.Source: §B.2.3 · p. 74
  • Finalized sequences contain at most one block per wave, never repeat a block, and include only blocks already inserted into the local DAG.These properties establish the stated Integrity requirements.Source: §B.2.3 · pp. 74–75
  • At every time, finalized leader sequences of active correct processes are prefix-comparable, preserving the stated total-order property.If one sequence contains B before B′, every active correct process whose sequence contains B′ also contains B before B′.Source: §B.2.3 · p. 75

B.3.1 Progress After Stabilization at RL

After reconfiguration finishes, sufficiently late rounds use only the final configuration RL. Every correct RL-member that remains active then completes every round and advances indefinitely.

B.3.1 Progress After Stabilization at RL

  • Once active correct RL-members have installed RL, they enable only RL after a sufficiently late round.Corollary 66 establishes a round r⋆ after which this holds for every such member.Source: §B.3.1 · pp. 75–76
  • Beyond a finite round cutoff, every certificate is declared under RL and names a broadcaster in members(RL).Earlier configurations have finite cutoffs; after the transition into RL, active correct RL-members assign only {RL}.Source: §B.3.1 · pp. 75–76
  • A final configuration RL exists because the reconfiguration sequence is finite; if there is only one configuration, it is installed at initialization.With multiple configurations, the transition into RL completes.Source: §B.3.1 · p. 75
  • Every active correct RL-member eventually DAG-delivers at least qL admissible blocks in each round r ≥ r⋆, completes that round, and enters r + 1.The proof proceeds by induction, using at least qL active correct broadcasters to supply the blocks needed for advancement.Source: §B.3.1 · p. 76

B.3.2 A Common Core in Every Stable Wave

In each stable wave under RL, fixed parent sets determine a shared set of certified blocks before fL + 1 distinct broadcasters release valid coin shares. Every active correct RL-member eventually DAG-delivers that same set.

B.3.2 A Common Core in Every Stable Wave

  • The common-core lemma establishes the core before the share threshold, and the following corollary establishes its eventual delivery by every active correct RL-member.The core contains qL blocks in distinct slots, and every round-r4 DAG block reaches each of them.Source: §B.3.2 · p. 77
  • Before fL + 1 distinct broadcasters release valid coin shares, fixed parent sets determine a common core Kw of exactly qL certified round-r1 blocks from distinct broadcaster slots.The result assumes correct singleton-enabled last-round broadcasters release their prescribed valid shares, and uncorrupted broadcasters fix their parents before releasing a share.Source: §B.3.2 · p. 77
  • For every correct process and every round-r4 block Y in its DAG, Kw is already in its round-r1 DAG and each core block is an ancestor of Y.This is the common-core property for a stable wave whose first round is at least r⋆.Source: §B.3.2 · p. 77
  • The proof fixes a first uncorrupted share-releasing broadcaster among the first fL + 1 distinct broadcasters, whose block's parents were fixed before share release.Its certified parent set and recursively certified ancestors cannot later change.Source: §B.3.2 · p. 77
  • Every active correct RL-member eventually DAG-delivers every block in Kw and at least qL distinct RL-typed leader-voting blocks that reach the core.Thus the same common core is eventually present in each such member's DAG.Source: §B.3.2 · p. 78

B.3.3 Direct-Anchor Recurrence and Progress

Under the stated conditional coin-probability requirement, active correct members identify direct anchors in arbitrarily late stable waves with probability one. This yields infinitely many finalized blocks; a computational unpredictability bound alone does not establish the required conditional guarantee.

B.3.3 Direct-Anchor Recurrence and Progress

  • The same positive lower bound applies after prior histories, including earlier failed waves, so the coin outcomes need not be independent.The adversary's view includes prior scheduling decisions and coin outcomes.Source: §B.3.3 · p. 79
  • Computational Unpredictability bounds overall failure probability across polynomially many waves, but does not itself imply the conditional bound after every finite prefix.The proof's probability-one progress conclusion uses that conditional requirement.Source: §B.3.3 · pp. 78–79
  • After any qualifying finite prefix, a conditional probability of at least εL yields eventual identification of a direct anchor in that wave or a later one.When the coin selects a broadcaster from Kw, delivery of the core and enough leader-voting blocks lets the process reconstruct the coin and identify the anchor.Source: §B.3.3 · p. 79
  • With probability one, every active correct RL-member identifies a direct anchor in a stable wave at or after any chosen starting index.The argument requires each stable wave's coin to select a broadcaster from its common core with conditional probability at least εL.Source: §B.3.3 · p. 79
  • With probability one, every active correct RL-member finalizes infinitely many blocks.The proof uses direct anchors in distinct waves to make finalized leader-sequence lengths unbounded.Source: §B.3.3 · p. 80

B.4 Dynamic DAG Byzantine Atomic Broadcast

Under the stated model and dealer issuance rule, the protocol implements leader-level Dynamic DAG Byzantine Atomic Broadcast for any finite reconfiguration sequence, without an a priori length bound. Probabilistic Progress additionally requires the conditional probability condition; Integrity and Total Order do not depend on coin Unpredictability or Fairness.

B.4 Dynamic DAG Byzantine Atomic Broadcast

  • Deterministic Integrity and Total Order do not use the configuration-scoped coin's Unpredictability or Fairness properties.The theorem's probability-one progress conclusion separately relies on the conditional probability requirement.Source: §B.4 · pp. 80–81
  • For every finite reconfiguration sequence, with no a priori bound on its length, the protocol implements leader-level Dynamic DAG Byzantine Atomic Broadcast.The theorem assumes the model conditions and that the dealer follows the issuance rule; Probabilistic Progress also assumes the conditional probability requirement.Source: §B.4 · p. 80
  • Integrity holds: processes finalize at most one leader per wave, do not duplicate blocks in finalized sequences, and finalize only blocks already in their local DAGs.These are the Integrity clauses of the leader-level abstraction.Source: §B.4 · p. 80
  • Total Order holds throughout every transition because canonical leader prefixes are nested.This conclusion is independent of eventual stability.Source: §B.4 · p. 80
  • Probabilistic Progress follows from the eventual stable waves and the common-core and conditional-probability premises.With probability one, every correct RL-member that remains active finalizes infinitely many blocks.Source: §B.4 · p. 81
Loading 2610.00896v1…