CS Paper Radar

Asynchronous Verifiable and Complete Secret Sharing: From Design Patterns to System-Level Trade-offs

Joachim Bruneau-Queyreix, Martin Zivojinovic, Leo Mendiboure, Tom Claudel, Laurent Réveillère

cs.CR ·submitted 2026-10-27 13:41 UTC · v1

Abstract

Modern secret sharing protocols promise robust secret sharing in fully asynchronous Byzantine systems, but their practical costs remain difficult to compare across papers, assumptions, and workloads. The difficulty is not merely experimental: protocols with similar asymptotic guarantees often place very different work on the critical path through their choices of dissemination, verification, batching, and recovery. This paper turns that fragmented research landscape into a corpus-backed designspace analysis and systems evaluation of asynchronous verifiable and complete secret sharing. We derive a design sieve, select seven representative protocols, and implement them in a common Rust framework. In our experiments on the Grid'5000 platform, we evaluate honest-dealer and faulty-dealer stress executions using latency, throughput, message count, bandwidth, and aggregate CPU-time. The results show that message complexity alone poorly predicts latency, that optimistic paths can be dominated by recovery cost, and that batching or packing helps only when verification stays off the critical path. These findings turn protocol-by-protocol comparisons into design-to-cost guidance for choosing, implementing, and extending asynchronous verifiable and complete sharing protocols.

Closest papers

Nearest neighbours by meaning across the whole index.

Byzantine-Tolerant Causal Unicast with Constant Message Space Overhead

cs.DC cs.DS ·2026-10-05 ·Purv Patel, Ajay D. Kshemkalyani
similarity 0.65
Abstract

Causal message ordering provides essential semantics for distributed applications, yet ensuring it within an asynchronous system subject to Byzantine failures presents fundamental theoretical and practical challenges. Prior research establishes that algorithms cannot guarantee both strong safety and liveness without using cryptography under these conditions. Existing Byzantine-tolerant solutions make synchrony assumptions or suffer from $O(n)$ message space overheads and $O(n^2)$ message complexity, where $n$ is the number of processes in the system, or use cryptography, but may not guarantee strong safety. In this paper, we present a novel Byzantine-tolerant causal ordering algorithm that achieves an optimal $O(1)$ application message space overhead for point-to-point messages. Our approach uses a Sender Permission to Send (SPS) invariant and an \textit{Isolated-Buffer Optimistic Model} for the memory management architecture. To circumvent Byzantine state-pinning and head-of-line blocking attacks, instead of unified causal buffers, we use isolated, per-peer queues equipped with event-driven \textit{Cascading Space Evictions}. We formally prove that our algorithm guarantees system-wide liveness and satisfies a weakened causal safety abstraction called \textit{Congestion-Relaxed Causal Delivery}. Under this model, weak causal safety is strictly preserved for all honest-to-honest communications unless extreme network latency or Byzantine withholding attacks exceed quantifiable local buffer capacities, forcing optimistic queue evictions. This formal guarantee successfully balances causal ordering with high throughput, constant message space overhead, low computational overhead, and strictly bounded local space.

0.03

Cryptographic Security Is Not Enough: Privacy Gaps in the Renegade Decentralized Dark Pool

cs.CR ·2026-09-22 ·Prerna Arote, Adrian Saiz, Oriol Saguillo, Lucianna Kiffer
similarity 0.64
Abstract · 18 pages, 9 figures

Dark pools are designed to provide pre-trade privacy, liveness, and post-trade confidentiality - concealing order flow before execution and limiting information leakage after. Decentralized dark pools, such as Renegade, aim to replicate these properties without custodial risk, using secure multi-party computation (MPC) and zero-knowledge proofs for private order matching and verifiable settlement. We show that Renegade's cryptographic guarantees do not deliver these dark pool properties in practice. MPC-with-abort ensures correctness but not fairness: a party may learn the match result and abort without penalty, breaking pre-trade privacy. We demonstrate that the protocol's discovery layer further leaks trading intent before MPC even begins, and that sustained probing via selective abort can probabilistically reconstruct counterparty order history, threatening post-trade confidentiality. We also show that the absence of input-consistency checks prior to MPC execution enables a griefing attack using invalid state commitments requiring no real token holdings that continuously locks honest users' wallets and wastes compute, breaking liveness under sustained conditions. We further analyze over 700,000 Renegade transactions on Base and probe the P2P layer, finding that the network is effectively centralized: 88% of traffic routes through a handful of relayers, with only four nodes sustaining the P2P layer. Since relayers hold their users' wallet state in plaintext, this concentration means the system operates as a centralized orderbook in practice - reproducing off-chain the information asymmetry that dark pools are designed to eliminate. Together, our results show that cryptographic privacy does not imply dark pool security: pre-trade privacy, liveness, and post-trade confidentiality each require additional protocol-level guarantees beyond MPC correctness.

0.50

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

cs.DC ·2026-08-27 ·Austin T. Li, Daniel H. Lee, Lorenzo Alvisi, Natacha Crooks, Florian Suri-Payer
top venueposition similarity 0.64
Abstract

Byzantine fault-tolerant (BFT) systems are, in principle, an appealing foundation for transactional applications involving mutually distrustful participants. Yet their adoption has been hampered by two persistent stumbling blocks-performance and developer convenience-which are often in tension with one another. Recent systems show promising progress on both fronts by shifting to a client-centric architecture; clients execute transactions locally and concurrently, while the system resolves any data conflicts to maintain database serializability. We argue that, in its current form, this approach introduces a critical vulnerability: it leaves the integrity of the database exposed to Byzantine clients, which may issue malicious or incorrect transactions. We address this threat with Sintr, a framework that prevents Byzantine clients from compromising database integrity by executing rogue transactions. Sintr combines redundant execution to validate transaction outcomes with a flexible, heterogeneous policy framework for expressing an application's data-integrity requirements. We apply Sintr to harden several existing BFT database systems and find that it imposes only modest overheads-3%-16% in throughput and 3%-21% in latency.

0.30

Scalable Composition of Byzantine Agreements under Reorder Attacks

cs.CR cs.DS ·2026-09-09 ·Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, Wentao Zhou
publishedtheory similarity 0.64
Abstract · A preliminary version of this work appeared in the Proceedings of the 7th international conference on Advances in Financial Technologies (AF…

Byzantine agreement (BA) is a foundational building block in distributed systems, and the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol's security guarantees, In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when $n \leq 3t$ or $n \leq 2c + 2t + 1$, where $t$ and $c$ denote the number of corrupted parties and communication channels, respectively, and $n$ is the number of parties. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when $n > \max\{3t, 2c+2t+1\}$. We first provide general black-box compilers that transform any single-instance secure BA protocol into one that is secure under parallel and concurrent executions without additional security assumptions. To optimize performance, we further design refined compilers using erasure-correcting codes. These refined versions significantly reduce communication overhead, particularly for long messages, where they achieve a constant multiplicative overhead compared with the original protocol, thus achieving the same asymptotic communication complexity.

0.22

StateSync-GKR: Design and Evaluation of a Reusable Sparse GKR Engine

cs.CR cs.PF ·2026-10-10 ·Jinwook Kim
code/data similarity 0.64
Abstract · 167 pages; 12 main figures and a detailed experimental atlas appendix. v2 evaluates release 1.2.0 (new serving path; reorganized prover arit…

Authenticated state transitions need proof engines that conserve memory, avoid repeated setup, keep every result bound to its request under parallel execution and return complete proofs at service rates. We present StateSync-GKR, a reusable Rust sumcheck/GKR core with a sparse-Merkle frontend, and evaluate release 1.2.0 against release 1.1 measured on the same day on the same instance types, request corpus and latency budgets. Sparse layer reduction keeps additional requested allocation 3,242-fold and peak process memory about 89-fold below the engine's dense reference at width 4,096. Release 1.2 changes two parts of the software while proof bytes and verifier acceptance stay fixed: reorganized round arithmetic raises prepared proving throughput 2.4 to 2.7-fold on a 192-core bare-metal host, and a new serving path starts each job as soon as a worker is free, bounds queued work and buffered replies, and returns proofs in completion order bound to request identifiers. On a 192-core VM at 1,000 requests/s, 99th-percentile latency to verified acceptance falls from 440 to 34 ms. One connection carries 3,300 requests/s with every request inside one second, confirmed in three 60-second runs and a 30-minute run of 5.94 million requests without a latency or queue trend; at 3,400 requests/s reply traffic reaches the provider's documented 5-Gbit/s single-flow limit, and two connections passed 5,000 requests/s in 15-second screens. In single 15-second screens on 48 cores, the highest passing rate rose from 500 to 2,000/s. Offered 1.5 times its highest screened one-connection rate under a memory limit, with excess offers held back by the client, the worker held its resident memory near a fifth of that limit and left no submitted request unresolved. For an integrating service, fewer servers deliver the same proof rate with bounded tail latency, and existing verifiers accept the GKR proofs unchanged.

0.58

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

cs.DC cs.DS ·2026-09-21 ·Purv Patel, Ajay D. Kshemkalyani
theory similarity 0.64
Abstract

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. In this paper, we address Byzantine Causal Reliable Broadcast (BCRB), which builds on BRB to enforce causal message ordering. We present a novel BCRB protocol that decouples causal ordering from the BRB layer, achieving constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ communication word complexity as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols; here $n$ is the number of processes. We present two variants of our protocol: a cryptographic version using a threshold encryption scheme and sequence gating, and its non-cryptographic version. In the cryptographic version, senders broadcast ciphertexts immediately, and decryption shares are piggybacked on out-of-band ACKs, preventing early decryption and front-running. In both versions, causal safety is achieved probabilistically. We evaluate the probability of causal safety violations using a random variable path analysis under independent exponential link delay distributions. We show that both variants satisfy liveness and the probability of weak safety violation is bounded by $\mathcal{O}(f^{-3}\cdot\ln^3 f)$, where $f$ is the upper bound on the number of Byzantine processes, and $f < n/3$ and $f=\mathcal{O}(n)$. Further, for the crypto version, we show that the probability of strong safety violation is bounded by $\mathcal{O}(f^{-1} \cdot \ln^2 f)$. We also show how to modify our two protocols to guarantee 100\% weak safety keeping $\mathcal{O}(1)$ message space overhead but with $\mathcal{O}(n^3)$ messages and $\mathcal{O}(n^3)$ communication word complexity.

0.29

Modular Responsiveness Verification of Rust Async Runtimes

cs.PL ·2026-10-06 ·Yanze Li, Ivan Beschastnikh, Alexander J. Summers
published similarity 0.63
Abstract · To appear at ESOP 2027, preprint with appendix

Asynchronous (async) programming is a popular paradigm for managing concurrency. Languages that provide async support typically have a runtime to manage asynchronous executions. These runtimes are critical infrastructure, yet verifying them has received little attention. One reason is that a property that users care most about from an async runtime is a liveness property: tasks submitted to the runtime eventually make progress. Verifying liveness is challenging for libraries that are both concurrent and highly optimized. We present a lightweight and modular proof technique for verifying eventual progression guarantees for Rust async runtimes. We describe this technique in the context of a simple language based on Rust and Rust's async model. We then realize this proof technique as a set of static analyses for Rust and use these to verify eventual progression of several key components of multiple Rust async runtime implementations.

0.19

Seal, Then Sample: Sampled Layerwise Proofs for Verifiable LLM Inference from GPT-2 to 70B

cs.CR cs.IR ·2026-09-23 ·Youki Lim, Sam Yong
code/data similarity 0.62
Abstract · 15 pages, 4 figures, 8 tables. Raw experiment logs and data tables: https://github.com/TrueOpen/slp-experiments

Verifying outsourced language-model inference requires a precisely identified computation and an audit whose cost a service can afford. We present Sampled Layerwise Proofs (SLP), a protocol and prototype that commits the boundary activations of every chunk of an inference trace, absorbs all commitments before any challenge is drawn, and then proves a verifier-selected subset of chunks together with the chunks that bind the prompt and the answer. Audit coverage becomes a runtime parameter over one set of commitments: on a TinyLlama-1.1B trace, proving seven of 47 chunks takes 22.0% of the time and 6.8% of the proof size of proving all 47. Because proof cost is dominated by weights rather than tokens, SLP packs concurrent requests into one trace under a block-diagonal causal mask and binds the prompt and answer of each request to its slot. Twelve packed requests are proved in 181.9 s, 6.5 times less than twelve separate proofs at the measured single-proof cost, and a simulated service proves twelve requests at 30.6 s per request with 0.6 s of verification each, rejecting a tampered answer. Disk-backed integer weights and streamed polynomial commitments let a single Llama-2-70B run complete on a 2 TB CPU host: 163 chunks sealed, five proved, a 4.34 MiB proof in 1,259 s, verified in 46.3 s without the weights. The proven object is a fixed-point canonical model; we trace a severe fidelity loss to the residual-stream bit width, repair it with an LLM-aware observer, and measure 84.8-84.9% argmax agreement with the floating-point reference over 334,705 WikiText-2 test positions. The limits are stated as precisely: guarantees cover proven chunks only, a fixed invalid chunk in the 70B setting is covered with probability 3/161, a manifest-only Fiat-Shamir schedule can be ground at 12.5 ms per attempt and needs an externally ordered challenge, and all measurements use a test reference string.

0.60