CS Paper Radar

Playing the SMR Game with Existential Honesty

Zeta Avarikioti, Odysseas Sofikitis, Christos Stefo

cs.CR ·submitted 2026-11-18 15:14 UTC · v1

Abstract

State machine replication protocols are usually proven secure in the honest-Byzantine setting, which requires an honest supermajority of validators. Deployed systems offer no such guarantee: validators participate for profit and may deviate from the protocol whenever doing so increases their gains. In our work, every validator is rational or Byzantine, and none is honest. Rational validators may collude with each other and with the Byzantine ones, who may also bribe them to deviate. Known impossibility results show that, without honest validators, clients that decide whether to accept a transaction based on a non-interactive certificate and without further communication cannot be kept safe. To bypass these results, we let clients relay the certificates they receive to full nodes and wait before confirming transactions. We also assume that one full node, whose identity is unknown, is honest and always online. Under this assumption, we build a finalization layer over any certifiable quorum-based protocol in a synchronous network. Clients run an existing freezing gadget and fetch past certificates from the honest full node, which makes the protocol \emph{always-safe}: no two honest clients confirm conflicting ledgers, for any strategy of the validators. We incentivize participation through rewards, which the adversary may use to bribe rational validators into censoring transactions. In this setting, we formalize censorship and characterize it tightly: paying only with his rewards, the adversary censors less than a $\bw$ fraction of the available fees at each height, where $\bw$ is the fraction of the quorum he signs, and every coin of censorship beyond that comes from his own funds.

Closest papers

Nearest neighbours by meaning across the whole index.

Brief Announcement: Fair Binding for Hidden-State Authorization in Byzantine SMR

cs.DC ·2026-08-18 ·Arnab Mallick, Indraveni Chebolu
publishedhot direction similarity 0.66
Abstract · Accepted at DISC 2026

Validated Byzantine SMR assumes that replicas can evaluate the validity of an ordered command. Agent authorization creates a different regime: a command may be valid only relative to a committed policy state that validators cannot reconstruct from the log. A proof that an action was authorized at an old commitment is then only a historical attestation, it does not by itself reserve the hidden resource for later use. We isolate two independent requirements for safe live allocation of a hidden consumable resource under a Byzantine leader. First, arrival order at correct replicas must constrain commit order, the gap addressed by fair-ordering protocols. Second, a committed first request must bind later validity: it must make conflicting later requests invalid, not merely record that the first request was once authorized. The second requirement is non-vacuous precisely because the current policy state is hidden and not prefix-recoverable. Using an explicit authorization-witness interface, we characterize the two distinct obligations in this one-shot reservation model and give a fair reserve/use protocol satisfying both authorization safety and first-arrival liveness. Under trusted FIFO admission the two requirements collapse because admission and execution are atomic, Byzantine SMR separates request commitment from use.

0.43

Resource Locks and Fast Unlock for Shared Balances in Certificate-Based Payment Systems

cs.DC ·2026-10-30 ·Lingkang Shangguan
theorycode/data similarity 0.65
Abstract · 13 pages, 2 tables, 1 algorithm. TLA+ specification: https://github.com/sglk123/resource-lock-tla

Certificate-based payment systems such as FastPay settle a payment with one round of signatures from a quorum of validators and avoid global ordering. The client collects the signatures, and validators never talk to each other. We observe that this client-driven design is complete only as long as no lock is ever undone. Each account has a single writer, a conflict can only come from that writer's own misbehavior, and the account stays locked as the penalty. Stablecoin payments routinely need balances that several accounts debit: treasuries, merchant pools, allowances and subscriptions. There, honest accounts race, locks must be undone, and a quorum certificate held privately by a client can be silently overridden. We prove that no unlock rule is safe in this setting unless certificate formation is visible to validators. We present a hybrid protocol. Personal accounts keep the client-driven FastPay path unchanged. A shared resource is a balance with its own version number and a set of authorized accounts. Transactions on shared resources are submitted to any validator and certified by a two-phase broadcast, ECHO then READY. The admission check requires both the sender's nonce and the resource's nonce to be free. Without contention, this path needs no consensus. When concurrent debits split the votes in any proportion, validators detect the split themselves, freeze the affected resource version, and resolve it with one agreement instance scoped to that version. Losing transactions return their sender nonce. We prove consistency, no overdraft, validity, finality and liveness. The protocol composes with the PDCC reconfiguration protocol.

0.44

STAKE: Preventing a colluding majority from double spending

cs.GT ·2026-10-01 ·Zahra Naderi, Vincent Gramoli
similarity 0.64
Abstract

Blockchains typically operate in open networks where it is hard to control the delay of messages. While classic blockchain protocols assumed synchrony, newer protocols try to remain secure despite unexpected network delays. Unfortunately, in the traditional model where $n$ participants can either be honest or Byzantine, we need a supermajority, or $\lfloor 2n/3\rfloor + 1$, of them to be honest. Recent work have explored the question of reducing the number of needed honest nodes in a game theory model to a majority sometimes by introducing $k$ rational players and $t$ Byzantine players. Yet, to our knowledge, no blockchain protocol managed to reduce it further. In this paper, we offer a blockchain protocol called Secure and Tolerant Algorithm through ($k,t$)-robust Equilibrium (STAKE) that works with only $\lfloor n/3\rfloor + 1$ honest players. STAKE requires each consensus participant to stake a sufficiently large amount $s$ compared to their liquidity $\ell$. We show that the probability that a coalition manages to execute $ζ$ double spending attacks (we call them a $ζ$-uple attack) drops exponentially fast with $ζ$. This allows us to demonstrate that STAKE reaches a ($k,t$)-robust equilibrium, or that rational players do not collude with Byzantine, even with a relatively low $s/\ell$ ratio.

0.12

Slow and Steady: Preventing MEV with Verifiable Delays

cs.CR ·2026-08-13 ·Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, Shreekara Shastry
similarity 0.64
Abstract · A revised version is accepted for publication at the 10th International Workshop on Cryptocurrencies and Blockchain Technology (CBT 2026)

Our work presents a defense mechanism against Maximal Extractable Value (MEV) opportunities in distributed ledgers. The mechanism relies on the idea of enforcing a verifiable delay when generating transactions, such that a block creator cannot react to the appearance of a MEV opportunity without breaking liveness. We present positive results both in the Byzantine setting and in a game theoretic model of rational participants. We additionally present negative bounds that outline the limitations of this line of defense. Finally, we explore real-world implementation details of verifiable delays and show that, based on historical MEV data, our mechanism could realistically help prevent most existing MEV threats.

0.13

Vantage: Availability-Graded Broadcast for Signature-Free BFT

cs.DC cs.CR ·2026-08-17 ·Nikita Polyanskii
hot direction similarity 0.63
Abstract · 65 pages

Digital signatures make blocks and votes transferable evidence: one party can prove to another what a third party said. Authenticated channels convince only the direct receiver, so a proposer that references another party's block cannot prove to the voters who published it. High-throughput signature-free protocols therefore complete an availability vote or a reliable broadcast for every published data block before a proposer may reference it. We present Vantage, a partially synchronous Byzantine fault-tolerant protocol for $n \ge 3f+1$ parties, at most $f$ Byzantine, that uses only authenticated channels and collision-resistant hashing. Parties publish blocks on hash-linked author lanes; each view's proposer pairs a core manifest of lane prefixes that a quorum has acknowledged to it with an optimistic tip manifest of blocks it has just received. A new primitive, Availability-Graded Broadcast (AGB), makes the core irrevocable on a quorum of directly received acknowledgments while grading, rather than blocking on, the tip. A view that AGB leaves open or silent is decided by an on-demand instance of information-theoretic agreement. A block may thus be referenced in a proposal one message delay after publication, as in signed optimistic designs. Let $δ$ be the message delay after global stabilization (GST). With all parties correct, a proposal commits within $2δ$ of its send if all $n$ parties support it, and within $3δ$ on the quorum path, so a block published in time for the next proposal is sequenced $3δ$ to $4δ$ after publication. Safety holds under asynchrony; liveness holds after GST. On an emulated ten-region WAN with 100 parties, Vantage has the lowest p50 latency among compared signed and signature-free protocols at every offered load up to its peak, and sequences 250k 512-byte transactions per second at median end-to-end latency below 500 ms.

0.48

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

cs.DC ·2026-10-21 ·Yackolley Amoussou-Guenou, Andrea Canidio
similarity 0.63
Abstract

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.

0.29

Fortress: Fork Resistant Transparency logs Relying on Social graph Structure

cs.CR ·2026-10-19 ·Anastasiia Kucherenko, Melissa Chase, Esha Ghosh
theory similarity 0.62
Abstract

Transparency systems -- such as Key Transparency (KT), Certificate Transparency, and binary transparency -- require that all honest participants see the same view of an untrusted server's directory, or, failing that, that the misbehaviour is publicly detected. Every existing design closes this gap with an external trust anchor: a publicly available bulletin board (BB), a blockchain, or an out-of-band (OOB) gossip network among auditors. We observe that transparency systems already have a built-in resource that has so far been overlooked: the social graph induced by the users themselves. We ask whether it can replace the bulletin board or the external gossip channel entirely, and answer in the affirmative (if occasional out-of-band interactions are allowed). We formalise a new primitive, Social-Graph based Forking-Resilient Transparency (sg-FORT), which captures the security guarantees of a BB-free transparency system and we construct Fortress Fork Resistant Transparency logs Relying on Social graph Structure, to our knowledge the first such protocol. In every epoch either all users output the same post, or at least one honest user produces a publicly verifiable Proof of Misbehaviour. Our guarantees hold against an arbitrary malicious server, including a snapshot adversary that may compromise a user and learn its secret state, as long as the server does not compromise close users. In honest executions, OOB interactions occur only when a user resets their secrets, so the total OOB cost approaches the natural lower bound of one call per reset -- dramatically below the full-gossip alternative. We prove security under standard cryptographic assumptions on signatures and dictionary commitment. Under simplifying assumptions (synchronous epochs, always-online users), we view this as a first feasibility result that opens up the design space of social-graph-based transparency systems.

0.23

State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State

cs.CR cs.DC ·2026-09-15 ·Luca Maraschi, Matteo Collina
similarity 0.60
Abstract · 51 pages, 8 figures

Durable-execution frameworks commonly journal execution steps of a long-running function and reconstruct state by deterministic replay; the journal is therefore the workflow's authoritative state, and in current deployments it typically resides with whichever provider hosts the run. This paper examines what changes if the journal is instead an authenticated, append-only log replicated among the parties to the workflow. We propose an architecture in which runs are chains of single-writer epoch cores; executor succession is governed by quorum-finalized closure certificates; durability, timeout, and checkpoint decisions are carried by explicit certificates rather than implicit trust; and large payloads travel a separate content-addressed distribution plane. A threat model separates what signatures establish (authorship and order) from what they do not (truth of recorded effects). We state the design as a set of typed artifacts and invariants, identify which claims are established by existing systems and which are proposals requiring validation, and define the prototype experiments, including specific adversarial cases, that would validate or falsify the proposal's central mechanisms.

0.38