On the Limits of Consensus under Dynamic Availability and Reconfiguration

• URL: http://arxiv.org/abs/2510.03625v1
• Date: Sat, 04 Oct 2025 02:19:25 GMT
• Title: On the Limits of Consensus under Dynamic Availability and Reconfiguration
• Abstract summary: We provide a bootstrapping gadget that is particularly simple and efficient in the common optimistic case of few reconfigurations and no double-spending attempts.<n>We then introduce a new and realistic additional assumption: honest nodes dispose of their cryptographic keys the moment they express intent to exit from the set of operating nodes.
• Score: 18.465539741088197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Proof-of-stake blockchains require consensus protocols that support Dynamic Availability and Reconfiguration (so-called DAR setting), where the former means that the consensus protocol should remain live even if a large number of nodes temporarily crash, and the latter means it should be possible to change the set of operating nodes over time. State-of-the-art protocols for the DAR setting, such as Ethereum, Cardano's Ouroboros, or Snow White, require unrealistic additional assumptions, such as social consensus, or that key evolution is performed even while nodes are not participating. In this paper, we identify the necessary and sufficient adversarial condition under which consensus can be achieved in the DAR setting without additional assumptions. We then introduce a new and realistic additional assumption: honest nodes dispose of their cryptographic keys the moment they express intent to exit from the set of operating nodes. To add reconfiguration to any dynamically available consensus protocol, we provide a bootstrapping gadget that is particularly simple and efficient in the common optimistic case of few reconfigurations and no double-spending attempts.

Related papers

• OptChain: Achieving Optimal Throughput of Permissionless Blockchains [22.07619176972099]
  We introduce OptChain, a permissionless blockchain state machine replication (SMR) protocol that achieves optimal throughput.<n>We first establish a theoretical upper bound on the throughput of any SMR protocol under a fixed error probability, and OptChain is the first protocol to approach this limit.<n>We implement a full prototype of OptChain and deploy it on AWS EC2 nodes across various regions.
  arXiv  Detail & Related papers  (2026-06-22T14:30:10Z)
• AetherWeave: Sybil-Resistant Robust Peer Discovery with Stake [3.9189409002585553]
  We present AetherWeave, a stake-backed peer-discovery protocol that ties network participation to deposited stake.<n>We prove that, with high probability, either the honest overlay remains connected or a $(ssqrtn)$-fraction of nodes in every smaller component raise an attack-detection flag.<n>AetherWeave is the first peer-discovery protocol to simultaneously provide Sybil resistance and privacy.
  arXiv  Detail & Related papers  (2026-03-24T23:50:17Z)
• Security bounds for unidimensional discrete-modulated CV-QKD: a Gaussian extremality approach [36.94429692322632]
  Security bounds for 1D discrete-modulated quantum key distribution protocols are determined.<n>We show that the Gaussian extremality assumption systematically overestimates Eve's information with increasing constellation size.<n>Our results highlight the necessity of alternative methods or optimized non-modulated constellation designs for this class of protocols.
  arXiv  Detail & Related papers  (2026-03-05T13:45:55Z)
• SoK: Speedy Secure Finality [0.0]
  This paper surveys the state of the art in fast finality protocol design.<n>We introduce the core theoretical primitives underlying this space.<n>We then analyze the communication and aggregation bottlenecks faced by single-slot finality protocols.
  arXiv  Detail & Related papers  (2025-12-23T19:25:02Z)
• Sedna: Sharding transactions in multiple concurrent proposer blockchains [42.71280924071485]
  We present Sedna, a user-facing protocol that replaces naive transaction replication with verifiable, rateless coding.<n>We prove Sedna guarantees liveness and emphuntil-decode privacy, significantly reducing MEV exposure.
  arXiv  Detail & Related papers  (2025-12-18T20:12:55Z)
• Voting-Based Semi-Parallel Proof-of-Work Protocol [45.776687601070705]
  We first consider the existing parallel PoW protocols and develop hard-coded incentive attack structures.<n>We introduce a voting-based semi-parallel PoW protocol that outperforms both Nakamoto consensus and the existing parallel PoW protocols.
  arXiv  Detail & Related papers  (2025-08-08T17:57:35Z)
• Advanced DAG-Based Ranking (ADR) Protocol for Blockchain Scalability [2.6649708444847677]
  This paper proposes the Advanced DAG-based Ranking protocol to enhance blockchain scalability and throughput.<n>It follows a three-step approach to secure the network against double-spending and enhance performance.<n> Simulation results demonstrate that ADR significantly improves transaction throughput and network liveness compared to existing DAG-based blockchains.
  arXiv  Detail & Related papers  (2025-08-06T01:27:33Z)
• Constitutional Consensus [2.226236493672377]
  Constitutional Consensus protocol introduces constitutional self-governance to consensus.<n>We achieve this by enhancing a DAG-based protocol with participant-controlled reconfiguration.<n>The protocol achieves consensus in $3delta$, maintains O(n) amortized communication complexity during high throughput, and seamlessly transitions between modes.
  arXiv  Detail & Related papers  (2025-05-25T16:23:44Z)
• Validated Strong Consensus Protocol for Asynchronous Vote-based Blockchains [4.79997217554732]
  Vote-based blockchains use Byzantine Fault Tolerance consensus protocols to transition from one state to another.<n>This paper proposes a emphvalidated strong BFT consensus model that allows leader-based coordination in asynchronous settings.<n>Our protocol greatly reduces message complexity and is the first one to achieve linear view changes without relying on threshold signatures.
  arXiv  Detail & Related papers  (2024-09-12T15:54:40Z)
• The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
  We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols.<n>Our measurements from the Aptos mainnet show that the optimistic approach reduces latency overhead by 71%.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• Conformal Inductive Graph Neural Networks [58.450154976190795]
  Conformal prediction (CP) transforms any model's output into prediction sets guaranteed to include (cover) the true label. CP requires exchangeability, a relaxation of the i.i.d. assumption, to obtain a valid distribution-free coverage guarantee. conventional CP cannot be applied in inductive settings due to the implicit shift in the (calibration) scores caused by message passing with the new nodes. We prove that the guarantee holds independently of the prediction time, e.g. upon arrival of a new node/edge or at any subsequent moment.
  arXiv  Detail & Related papers  (2024-07-12T11:12:49Z)
• Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks [59.43433767253956]
  We consider the problem of privately estimating the mean of vectors distributed across different nodes of an unreliable wireless network. In a semi-decentralized setup, nodes can collaborate with their neighbors to compute a local consensus, which they relay to a central server. We study the tradeoff between collaborative relaying and privacy leakage due to the data sharing among nodes.
  arXiv  Detail & Related papers  (2024-06-06T06:12:15Z)
• Generative Semi-supervised Graph Anomaly Detection [42.02691404704764]
  This work considers a practical semi-supervised graph anomaly detection (GAD) scenario, where part of the nodes in a graph are known to be normal.<n>We propose a novel Generative GAD approach (namely GGAD) for the semi-supervised scenario to better exploit the normal nodes.<n>GGAD is designed to leverage two important priors about the anomaly nodes -- asymmetric local affinity and egocentric closeness.
  arXiv  Detail & Related papers  (2024-02-19T06:55:50Z)
• Scalable and Adaptively Secure Any-Trust Distributed Key Generation and All-hands Checkpointing [3.1771413727096154]
  We propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear and communication per-node cost with the help of a common coin. Our protocol is secure against adaptive adversaries, which can corrupt less than half of all nodes. We present a generic transformer that enables us to efficiently deploy a conventional distributed protocol like our DKG, even when the participants have different weights.
  arXiv  Detail & Related papers  (2023-11-16T06:05:01Z)
• Feedback-assisted quantum search by continuous-time quantum walks [58.720142291102135]
  We address the quantum search of a target node on a cycle graph by means of a quantum walk assisted by continuous measurement and feedback. In particular, our protocol is able to drive the walker to a desired target node.
  arXiv  Detail & Related papers  (2022-01-12T16:59:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.