PaperlayerView exact revision on arXiv

Source-linked AI summary

How Not to Be Censored: Inclusion Safety in Client-Led Consensus

Yackolley Amoussou-Guenou, Andrea Canidio

arXiv:2610.29497v1cs.DC

TL;DR

Consensus models often leave clients passive, obscuring how a client can secure timely inclusion of its transaction. This paper introduces a client-led leaderless protocol and defines inclusion safety. It finds that client and replica connectivity can substitute for one another, though poorly connected clients require longer epochs.

  • Problem

    Consensus models often omit clients, leaving unresolved what client behavior guarantees timely inclusion of its own transaction.

    Source: §1 · p. 1

  • Method

    The paper introduces a leaderless protocol in which client transactions reference prior-epoch blocks and defines inclusion safety across blocks and eventual fork abandonment.

    Source: §1 · pp. 1–2

  • Results

    A compliant client can achieve inclusion safety by reaching sufficiently many honest replicas within an epoch or relaying a containing block across epochs; client and replica connectivity substitute, but poor client connectivity requires twice-long epochs in the model.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Inclusion guarantees depend on client reachability as well as replica connectivity, and relying on replicas for poorly connected clients lengthens the required epoch.

    Source: §1 · p. 2

    The generalized network model treats unreliable links as allowing arbitrary but not indefinite message delays.

    Source: §2 · p. 4

Abstract

from arXiv · show

Blockchain consensus protocols implicitly follow a client-server architecture: validators are the only active participants, while clients (i.e., users) merely submit transactions and rely on validators to include them. This abstraction obscures a fundamental question: what should a client do to guarantee the timely inclusion of its own transaction? We study this question by introducing a leaderless consensus protocol in which clients are active. We define inclusion safety: the guarantee that a client's transaction enters some of the blocks produced for an epoch, and that every block omitting it belongs to a fork that is eventually abandoned. Because every transaction carries a reference to a block of the previous epoch, clients help select the surviving fork. This yields two paths to inclusion: reaching sufficiently many honest replicas within an epoch, or relaying a block containing the transaction across epochs until the corresponding fork becomes canonical. In a generalized model spanning synchrony and asynchrony, the client's and the replicas' connectivity are substitutes for inclusion safety: it is achieved either if the client is well connected, or if the client is poorly connected but honest replicas communicate reliably, provided the client reaches at least one of them. However, the substitution is imperfect: when inclusion safety rests on the replicas' connectivity, it requires a longer epoch compared to when the client is well connected.

1 Introduction

Consensus models often treat clients as passive and omit how transactions reach validators, leaving client-side censorship resistance unaddressed. This paper makes clients active in a leaderless protocol and defines conditions for transaction inclusion and eventual fork agreement.

1 Introduction

  • The paper defines inclusion safety as transaction inclusion in some blocks of an epoch, with every block omitting it confined to a fork eventually abandoned.Source: §1 · pp. 1–2
  • Clients attach references to previous-epoch blocks, helping select the surviving fork; a compliant client can secure inclusion within an epoch or by relaying a containing block across epochs.Source: §1 · p. 2
  • A well-connected client achieves inclusion safety regardless of inter-replica communication, while a poorly connected client can achieve it if honest replicas communicate reliably and it reaches at least one.Source: §1 · p. 2
  • When client connectivity is poor, information passes through an intermediate replica and inclusion safety requires an epoch twice as long in the model.Source: §1 · p. 2
  • With adversarially controlled latency, either enough honest replicas include a transaction and all epoch blocks contain it, or an attacker can prevent its inclusion altogether.Source: §1 · p. 2
  • Under random latency, some blocks may include a transaction while others omit it, activating cross-epoch relaying; simulations quantify the epoch-length trade-off between within-epoch inclusion and recovery.Source: §1 · p. 2

Related literature

  • Prior multi-proposer work guarantees inclusion for transactions held by honest replicas, leaving the client's path to such a replica unstated; inclusion-list and economic approaches also frame guarantees or costs differently.Inclusion-list designs state guarantees at the committee level, while the economic literature considers the cost of exclusion; this paper assumes Byzantine replicas that censor at any price.Source: Related literature · p. 3

2 Model

The model includes replica validators and clients submitting transactions, operating in asynchronous epochs over links that may or may not deliver within a known bound. Blocks form predecessor chains, and multiple active forks may coexist.

2 Model

  • Each process runs the protocol by epoch, taking observed previous-epoch blocks as input and producing blocks that each point to one predecessor.Source: §2 · p. 3
  • At most f replicas are Byzantine among n = 3f + 1, while the model places no bound on Byzantine clients.Source: §2 · p. 4
  • The generalized network model assigns reliable links to client-replica pairs and subsets of honest replicas; other messages may be delayed arbitrarily, though not indefinitely.Source: §2 · p. 4
  • Honest broadcasts are eventually delivered to every honest process, and delivery by one honest process implies eventual delivery by all honest processes.Source: §2 · p. 4
  • Blocks form a tree rooted at genesis, and following predecessor pointers yields a block’s history; different blocks can have chains that branch into multiple active forks.Source: §2 · p. 4

3 Problem definition

Inclusion safety is a transaction- and epoch-specific guarantee that separates immediate inclusion from eventual agreement across active forks. It applies only where the transaction is valid against at least one previous-epoch block.

3 Problem definition

  • Transaction validity depends on the predecessor block’s state and is distinct from successful execution; a transaction may be valid against one block but invalid against another.Source: §3 · p. 5
  • Inclusion safety requires a valid predecessor, immediate inclusion in at least one block extending it, exclusion from blocks with invalid predecessors, and eventual presence on every active fork.Source: §3 · p. 5
  • The definition separates immediate transaction inclusion from agreement, which may take longer as forks omitting the transaction are pruned epoch by epoch.Source: §3 · p. 5
  • The guarantee requires knowing when the epoch’s submission window is open, and the model assumes blocks have enough space for every admissible transaction.Source: §3 · p. 5

4 Protocol description

The protocol runs client-proposal, witness-construction, and voting rounds within each epoch. Clients advance epochs with certified blocks, while replicas form ordered certificates from growing witnesses of observed proposals.

4 Protocol description

  • Clients enter an epoch after receiving a prior-epoch vote certificate and broadcast proposals containing a transaction and that certificate.Source: §4 · pp. 5–6
  • At time 2A, replicas begin voting on support witnesses built from observed close proposals; later arrivals enlarge witnesses, allowing overlapping witness construction and voting.Source: §4 · p. 5, Figure 1 · p. 6
  • A replica opens an epoch upon its first valid client proposal, accepts proposals until its timer expires, then broadcasts a close proposal representing delivered transactions.Source: §4 · p. 6
  • Witnesses track valid client proposals, predecessors, and flagged and non-flagged replicas; additional close proposals can grow the witness, while equivocation flags a replica or client.Source: §4 · p. 6
  • Replicas vote only after observing close proposals from at least 2f + 1 replicas and only for a witness strictly above their prior lock.Source: §4 · p. 7
  • A quorum of votes certifies a block, and multiple certificates in one epoch form a chain that is totally ordered.Source: §4 · pp. 5, 7

5 Properties

A compliant client can secure inclusion by reaching enough honest replicas early in an epoch, or by carrying a certified block containing its transaction across epochs until omission forks are abandoned. In the generalized network model, client and replica connectivity can substitute imperfectly; under stochastic latency, relaying provides a probabilistic second path.

5 Properties

  • Once an honest replica includes the transaction in a certified block, same-epoch and cross-epoch monotonicity preserve it in every higher certified extension.This follows from the same-epoch monotonicity lemma and its cross-epoch extension.Source: §5 · p. 8
  • Early dissemination to enough honest replicas puts a compliant client’s transaction in every certified block; relaying a block that contains it can instead eliminate omission forks across epochs.The second path delays agreement, not the transaction’s initial inclusion: it enters some certified blocks before the remaining forks are abandoned.Source: §5 · p. 9

5.1 Generalized network model

  • Liveness holds for every client and replica connectivity setting, but inclusion safety requires enough timely reach: direct client connectivity needs A ≥ 2∆, while relayed reach needs A ≥ 4∆.If the client’s reach covers at most f honest replicas, an adversary can prevent inclusion in every certified block, regardless of epoch length; relaying vote certificates cannot restore it.Source: §5.1 · pp. 10–11
  • Client and replica connectivity are imperfect substitutes: relying on replica relays requires twice the epoch length of the direct-connectivity guarantee.The direct path has two communication links, while the relayed path has four.Source: §5.1 · pp. 9, 11

5.2 Stochastic latency and the role of the second path to inclusion

  • Partial inclusion requires Byzantine participation: without Byzantine close proposals omitting the transaction, it is included in every certified block or none.When Byzantine replicas do provide omissions, a compliant client can have its transaction included in only some certified blocks.Source: §5.2 · p. 12
  • Under stochastic latency, increasing epoch length raises the chance that a relayed block arrives before its fork is abandoned; simulations find that relay success is near one at A ≈ 4.The simulation uses f = 2 and delays uniformly drawn from [1, 3]; certainty returns at A ≥ 2p̄.Source: §5.2 · pp. 12–13

6 Conclusion

The paper studies censorship resistance from the client’s perspective by defining inclusion safety and introducing a leaderless, client-led protocol. It identifies two inclusion paths and finds that client and replica connectivity are imperfect substitutes, while stochastic latency gives the second path a probabilistic role.

6 Conclusion

  • The paper defines inclusion safety as a transaction entering some blocks of an epoch while every block omitting it belongs to a fork eventually abandoned.The protocol is leaderless, and each transaction references a block from the previous epoch.Source: §6 · p. 13
  • Clients have two paths to inclusion safety: reach enough honest replicas within an epoch, or relay a block containing the transaction across epochs until its fork becomes canonical.Source: §6 · p. 13
  • Client and replica connectivity are imperfect substitutes for inclusion safety, and stochastic latency gives the second path a probabilistic role.Source: §6 · p. 13

B.1 Proof of Lemma 1

Vote certificates are comparable because their quorum overlap includes an honest replica, whose votes are themselves comparable.

B.1 Proof of Lemma 1

  • With n = 3f + 1 replicas, any two vote certificates of 2f + 1 votes intersect in at least f + 1 replicas, including at least one honest replica.Source: §B.1 · p. 16
  • An honest replica’s votes are for comparable witnesses because each later vote is strictly above its previous one and the witness ordering is transitive.Source: §B.1 · p. 16
  • The honest voter shared by two certificates therefore links them through comparable witnesses.Source: §B.1 · p. 16

B.2 Proof of Lemma 2

The proof shows that an honest replica’s close proposal containing the client’s proposal remains present in later witnesses. Monotone validity and compliant signing then ensure the transaction is retained in the resulting block.

B.2 Proof of Lemma 2

  • Monotone validity keeps the transaction valid against later witnesses whose predecessor is at least the block referenced by the proposal.The argument follows because the honest replica remains non-flagged and its close proposal remains in the witness.Source: §B.2 · p. 16
  • Compliant signing prevents a second distinct proposal from the client, so the valid transaction is not removed when the block is constructed.The proof concludes that the transaction belongs to both the selected proposal set and the resulting block.Source: §B.2 · p. 16
  • The same reasoning covers the original witness as a degenerate case, establishing inclusion in its block as well.The passage applies the claim to B(We) as the degenerate case.Source: §B.2 · p. 16

B.3 Proof of Lemma 3

The appendices prove the ancestry, inclusion, and liveness properties needed by the protocol. The proofs establish that certified blocks preserve predecessor-chain relationships, transactions can persist across epochs, and honest replicas eventually certify a witness.

B.3 Proof of Lemma 3

  • Induction on epoch steps shows that when a later certified block extends an earlier one, the corresponding predecessor block remains in its predecessor chain.The proof handles a base case and induction step, using monotonicity of Predecessor.Source: §B.3 · p. 17

B.4 Proof of Lemma 4

  • A certificate contains an honest replica that observed the client’s proposal, so the proposal survives witness construction and appears in every certified block of its epoch.The proof also establishes cross-epoch persistence through the predecessor relationship.Source: §B.4 · p. 17

B.5 Proof of Proposition 1

  • With finite message delays, honest replicas’ observations converge to a common final view and they eventually form a vote certificate for its witness.Honest replicas eventually receive valid proposals, rebroadcast observations, and vote for the converged witness.Source: §B.5 · p. 18

B.6 Proof of Proposition 2

The proof gives direct and relayed conditions for inclusion, then shows a boundary where inclusion cannot be guaranteed. The sufficient routes rely on reaching enough replicas before their close boundaries; with too few carriers, an adversarially timed quorum can exclude the transaction.

B.6 Proof of Proposition 2

  • If the client reliably reaches at least f + 1 replicas, including at least f + 1 honest replicas, its proposal arrives before their close boundaries and is included in every certified block.The proof uses a 2∆ delivery bound and A ≥2∆.Source: §B.6 · p. 18
  • If the client’s reliable set and the reliably communicating replicas together reach enough carriers, A ≥4∆ lets the proposal reach them before their close boundaries.The proof concludes that the proposal is included when the carrier set N has size at least f + 1.Source: §B.6 · p. 18
  • When the carrier set has size at most f, an adversarial quorum can certify a block omitting the transaction and open the next epoch before the carriers participate.The construction delays messages to and from the compliant client until the coalition’s voting has ended; all delays remain finite.Source: §B.6 · pp. 18–19

B.7 Proof of Proposition 3

The proof establishes direct and relayed guarantees for proposals referencing a target block, and constructs an impossibility case when the target’s carriers are too few. In the sufficient cases, certified blocks retain a predecessor at least as high as the target.

B.7 Proof of Proposition 3

  • When the family’s clients reliably reach enough replicas, every certified block has a predecessor at least as high as the referenced block M.The proof uses the reliable sets of family clients and the presence of at least f + 1 honest carriers.Source: §B.7 · p. 19
  • When a family client also reaches a reliably communicating replica, relaying spreads the proposal so that every replica in NM carries it, yielding the same predecessor guarantee.The argument requires A ≥4∆ and |NM| ≥f + 1.Source: §B.7 · p. 19
  • If |NM| ≤f, an adversary can form a quorum that certifies a predecessor below M while delaying family-client messages until voting ends.The construction uses a Byzantine client to open the epoch for that quorum and completes its certificate with Byzantine votes.Source: §B.7 · p. 19

B.8 Proof of Lemma 5

The proof constructs executions in which a certified block omits a compliant client's transaction, both when the compliant client opens the epoch and when a Byzantine client opens it. It then shows how a later certified block can restore the transaction, and characterizes inclusion when Byzantine replicas send no close proposals.

B.8 Proof of Lemma 5

  • When a compliant client opens the epoch and A < 2p̄−p, an event of positive probability lets a quorum certify a witness that excludes the transaction.The proposal reaches one replica before its close boundary but the other close proposals omit it; the quorum forms without that replica's close proposal.Source: §B.8 · p. 20
  • For every A < 2p̄, withholding the opening proposal from one replica enables a quorum to certify a witness whose block omits the transaction.The delayed close proposal from that replica arrives too late to prevent the excluding witness from forming.Source: §B.8 · p. 20
  • After the delayed close proposal arrives, honest replicas can certify a later witness containing the transaction, whose block extends the earlier excluding block.The later witness is built from all close proposals, and monotone validity preserves the transaction relative to its predecessor.Source: §B.8 · p. 20
  • If Byzantine replicas send no close proposals, every certified block contains the transaction exactly when some honest close proposal contains it.Every witness receiving an honest vote must include all honest close proposals.Source: §B.8 · p. 21

C Simulation details

The simulation studies how the close boundary A affects immediate inclusion and recovery through relaying across epochs. Recovery is almost certain around A≈4 in the simulated setting, while inclusion safety is probabilistic below 2p̄ and certain at or above it.

C Simulation details

  • Relaying a block containing the transaction across epochs can make every active fork include it permanently when the relay reaches every honest replica before its close boundary.Recovery in an epoch supplies the eventual-agreement condition for inclusion safety; abandonment means the active forks contain no block with the transaction.Source: C Simulation details · pp. 21–23
  • q(A), the probability that all certified blocks carry the transaction, is weakly increasing, equals 1 for A > 2p̄, and is positive for A > 3p−p̄.A larger A can only add replicas whose close proposals carry the client proposal and can make first witnesses richer.Source: C Simulation details · p. 21
  • Choosing A trades faster settlement against a lower q(A), increasing the chance of partial inclusion; relay recovery can make that smaller boundary tolerable, but costs waiting.The relay path does not restore immediacy; recovery depends on a later epoch with favorable draws.Source: C Simulation details · p. 21
  • At A≈4 recovery is almost certain, below 2p̄=6; the intermediate state is thin, and relay fallback rarely waits more than one epoch.Inclusion safety remains probabilistic below A=2p̄ and becomes certain at or above that boundary.Source: C Simulation details · pp. 21–22, Figure 4 · p. 22
  • The simulation uses 7 replicas, 2 Byzantine replicas, uniform delays in [1, 3], and a representative adversary that neither equivocates nor injects higher-block proposals.The setup runs 6,000 epochs per grid point and assumes the relayed transaction is valid against every preceding block.Source: C Simulation details · p. 22
  • The representative adversary removes partial inclusion once A ≥ 2p̄−p, whereas a worst-case adversary can sustain it for every A < 2p̄.The simulated behavior is therefore not a worst-case account of partial inclusion.Source: C Simulation details · p. 22
Loading 2610.29497v1…