Alejandro Ranchal-Pedrosa

Benjamin Marsh, Alejandro Ranchal-Pedrosa

A threshold system completes a public task only after $κ$ verifiable shares are publicly committed. If the honest schedule creates \( \Nstar=κ+Δ\) share opportunities by deadline $t^\star$, then $Δ$ shares are slack such that a coalition delays completion if and only if it withholds at least $Δ+1$ shares. The incentive problem is therefore to price the cheapest sabotage set. Agents receive a direct fee $f$ per committed share. A delaying coalition may also obtain delay value at most $L$, and may earn additional fee revenue during recovery after the deadline. Let $R_1^+$ be a pathwise upper bound on the coalition's incremental fee revenue in a recovery slot that completes the task, including any same-slot overshoot. The principal can post a nonnegative completion bounty that depends only on committed shares, uses no deposits or punishments, and expires if completion is late. The optimal rule is uniform, as if completion occurs by $t^\star$, every admissible horizon share receives $B/\Nstar$, otherwise no bounty is paid. Full participation is ex-post strongly delay proof exactly when \( (Δ+1)f+\frac{Δ+1}{\Nstar}B \ge L+R_1^+ . \) Equivalently, the exact worst-case budget is \( B^\star = \frac{\Nstar}{Δ+1} \bigl(L+R_1^+-(Δ+1)f\bigr)^+ . \) The bound is tight for every nonnegative completion measurable bounty, among the $\Nstar$ horizon shares, some $Δ+1$ receive total bounty at most $(Δ+1)B/\Nstar$, and withholding precisely those shares delays completion. The result applies to threshold signatures, data availability certification, coded dissemination, and generic $k$-of-$n$ completion tasks. We also isolate a separate limit, no transfer rule based only on completed shares can remove a final slot race in which a coalition has already observed enough pre-completion shares to act.

Benjamin Marsh, Alejandro Ranchal-Pedrosa

Sedna is a coded multi-proposer consensus protocol in which a sender shards a transaction payload into rateless symbols and disseminates them across parallel proposer lanes, providing high throughput and ``until decode'' privacy. This paper studies a sharp incentive failure in such systems. A cartel of lane proposers can withhold the bundles addressed to its lanes, slowing the chain's symbol accumulation while privately pooling the missing symbols. Because finalized symbols become public, the cartel's multi-slot information lead is governed by a chain level delay event where the chain fails to accumulate the $κ$ bundles needed for decoding by the honest horizon $t^\star=\lceil κ/m\rceil$. We characterize the resulting delay probability with KL-type large deviation bounds and show a knife edge pathology when the slack $Δ=t^\star m-κ$ is zero such that withholding a single bundle suffices to push inclusion into the next slot with high probability. We propose \textsf{PIVOT-$K$}, a Sedna native pivotal bundle bounty that concentrates rewards on the $κ$ bundles that actually trigger decoding, and we derive explicit incentive compatibility conditions against partial and coalition deviations. We further show that an adaptive sender ``ratchet'' that excludes lanes whose tickets were not redeemed collapses multi-slot withholding into a first slot deficit when $t^\star\ge 2$, reducing the required bounty by orders of magnitude. We close by bounding irreducible within slot decode races and providing parameter guidance and numerical illustrations. Our results show that for realistic parameters Sedna can reduce MEV costs to 0.04\% of the transaction value.

Alejandro Ranchal-Pedrosa, Benjamin Marsh

The TRAP protocol solves rational agreement by combining accountable consensus with a one-shot BFTCR finalization phase. We present SNARE (Scalable Nash Agreement via Reward and Exclusion), the adaptation of TRAP to $n=5f{+}1$, and prove $ε$-$(k,t)$-robustness for rational agreement tolerating coalitions up to ${\approx}73\%$ with deposits under $0.5\%$ of the gain. A central finding is that appending a single all-to-all broadcast round with the $4f{+}1$ threshold after predecisions yields $ε$-$(k,t)$-robustness for coalitions up to $3f$ (${\approx}60\%$) without any deposit: we need not model or know the utility function of deviating players, only that they participate in the protocol. These players can be \emph{deceitful} (arbitrary unknown utility), not just rational, and the finalization structure prevents disagreement regardless of their motivation. This observation is protocol-agnostic, applies to any $5f{+}1$ protocol at the cost of one message delay that runs concurrently with the next view, and does not require commit-reveal mechanisms. Above $60\%$, the full baiting mechanism with deposits under $0.5\%$ extends tolerance to ${\approx}73\%$. A second finding is that valid-candidacy, the property preventing reward front-running, holds unconditionally regardless of the quorum threshold, removing both the $n>2(k{+}t)$ and $n>\frac{3}{2}k{+}3t$ constraints from the original TRAP. This retroactively extends the $3f{+}1$ bound from $C<n/2$ to $C<5n/9$. The binding constraint in both models is the winner consensus operating on $2f$ residual players after excluding $3f{+}1$ detected equivocators. We explore avenues for relaxing this limit.

Alejandro Ranchal-Pedrosa, Vincent Gramoli

In the general setting, consensus cannot be solved if an adversary controls a third of the system. Yet, blockchain participants typically reach consensus "eventually" despite an adversary controlling a minority of the system. Exceeding this $\frac{1}{3}$ cap is made possible by tolerating transient disagreements, where distinct participants select distinct blocks for the same index, before eventually agreeing to select the same block. Until now, no blockchain could tolerate an attacker controlling a majority of the system. In this paper, we present Zero-Loss Blockchain (ZLB), the first blockchain that tolerates an adversary controlling more than half of the system. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably deceitful replicas. progressively reduces the portion of deceitful replicas below $\frac{1}{3}$, and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff and is almost as fast as the scalable Red Belly Blockchain that cannot tolerate $n/3$ faults.