Albatross: An optimistic consensus algorithm

• URL: http://arxiv.org/abs/1903.01589v5
• Date: Thu, 8 Aug 2024 08:47:49 GMT
• Title: Albatross: An optimistic consensus algorithm
• Abstract summary: We introduce Albatross, a Proof-of-Stake (PoS) blockchain consensus algorithm that aims to combine the best of both worlds. At its heart, Albatross is a high-performing, speculative BFT algorithm that offers strong probabilistic finality. We prove our protocol to be secure under standard BFT assumptions and analyze its performance both on a theoretical and practical level.
• Score: 1.1775652117617563
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The consensus protocol is a critical component of distributed ledgers and blockchains. Achieving consensus over a decentralized network poses challenges to transaction finality and performance. Currently, the highest-performing consensus algorithms are speculative BFT algorithms, which, however, compromise on the transaction finality guarantees offered by their non-speculative counterparts. In this paper, we introduce Albatross, a Proof-of-Stake (PoS) blockchain consensus algorithm that aims to combine the best of both worlds. At its heart, Albatross is a high-performing, speculative BFT algorithm that offers strong probabilistic finality. We complement this by periodically guaranteeing finality through the Tendermint protocol. We prove our protocol to be secure under standard BFT assumptions and analyze its performance both on a theoretical and practical level. For that, we provide an open-source Rust implementation of Albatross. Our real-world measurements support that our protocol has a performance close to the theoretical maximum for single-chain Proof-of-Stake consensus algorithms.

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)
• GoAT-X: A Graph of Auditing Thoughts for Securing Token Transactions in Cross-Chain Contracts [52.51342355102833]
  Cross-chain bridges, the critical infrastructure of the multi-chain ecosystem, have become a primary target for attackers.<n>Existing defenses, such as bytecode-level static analysis, are ill-equipped to handle the semantic complexity of cross-chain interactions.<n>We propose GoAT-X, a framework that shifts automated cross-chain smart contracts auditing from pattern matching toward systematic first-principles verification.
  arXiv  Detail & Related papers  (2026-04-27T11:34:21Z)
• Proof of Trusted Execution: A Consensus Paradigm for Deterministic Blockchain Finality [0.391985484065646]
  We propose Proof of Trusted Execution (PoTE), a consensus paradigm where agreement emerges from verifiable execution rather than replicated re-execution.<n>Because the execution is deterministic and the proposer is uniquely derived from public randomness, PoTE avoids forks, eliminates slot.time bottlenecks, and commits blocks in a single round of verification.
  arXiv  Detail & Related papers  (2025-12-10T08:04:38Z)
• 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)
• FairDAG: Consensus Fairness over Multi-Proposer Causal Design [4.261985028097139]
  Research has shown that adversaries exploit transaction ordering to extract profits through attacks like front-running, sandwich attacks, and liquidation manipulation.<n>This issue affects blockchain databases in which block proposers have full control over transaction ordering.<n>Existing fairness protocols operate on leader-based consensus protocols, which not only suffer from low throughput, but also allow adversaries to manipulate transaction ordering.<n>We propose FairDAG-AB and FairDAG-RL that run fairness protocols on top of DAG-based consensus protocols, which improve protocol performance in both throughput and fairness quality.
  arXiv  Detail & Related papers  (2025-04-03T00:38:03Z)
• Unraveling Responsiveness of Chained BFT Consensus with Network Delay [22.287511037444265]
  Chained Byzantine Fault Tolerant (BFT) protocols have been increasingly adopted in practical systems. We introduce a unified framework utilizing Markov Decision Processes (MDP) to model and assess the performance of three prominent chained BFT protocols.
  arXiv  Detail & Related papers  (2025-01-07T10:50:15Z)
• A Study on Asynchronous Vote-based Blockchains [4.79997217554732]
  Vote-based blockchains use Byzantine Fault Tolerance consensus protocols to transition from one state to another. This paper proposes a emphvalidated strong BFT consensus model that allows leader-based coordination in asynchronous settings. 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)
• Convergent Differential Privacy Analysis for General Federated Learning: the $f$-DP Perspective [57.35402286842029]
  Federated learning (FL) is an efficient collaborative training paradigm with a focus on local privacy. differential privacy (DP) is a classical approach to capture and ensure the reliability of private protections.
  arXiv  Detail & Related papers  (2024-08-28T08:22:21Z)
• 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. Existing approaches for threshold cryptosystems introduce a latency overhead of at least one message delay for running the threshold cryptographic protocol. We propose a mechanism to eliminate this overhead for blockchain-native threshold cryptosystems with tight thresholds.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus [1.6364535330823093]
  TetraBFT is a Byzantine fault tolerant protocol for solving consensus in partial synchrony. We validate the correctness of TetraBFT through rigorous security analysis and formal verification. We extend TetraBFT into a multi-shot, chained consensus protocol.
  arXiv  Detail & Related papers  (2024-05-04T08:54:42Z)
• A Novel Endorsement Protocol to Secure BFT-Based Consensus in Permissionless Blockchain [1.3723120574076126]
  BFT-based consensus mechanisms are widely adopted in the permissioned blockchain to meet the high scalability requirements of the network. Sybil attacks are one of the most potential threats when applying BFT-based consensus mechanisms in permissionless blockchain. This paper presents a novel endorsement-based bootstrapping protocol with a signature algorithm that offers a streamlined, scalable identity endorsement and verification process.
  arXiv  Detail & Related papers  (2024-05-04T03:00:33Z)
• FedChain: An Efficient and Secure Consensus Protocol based on Proof of Useful Federated Learning for Blockchain [0.3480973072524161]
  The core of the blockchain is the consensus protocol, which establishes consensus among all the participants. We propose an efficient and secure consensus protocol based on proof of useful federated learning for blockchain (called FedChain) Our approach has been tested and validated through extensive experiments, demonstrating its performance.
  arXiv  Detail & Related papers  (2023-08-29T08:04:07Z)
• ACon$^2$: Adaptive Conformal Consensus for Provable Blockchain Oracles [31.439376852065713]
  Power of smart contracts is enabled by interacting with off-chain data, which in turn opens the possibility to undermine the block state consistency. We propose an adaptive conformal consensus (ACon$2$) algorithm, which derives consensus from multiple oracle contracts. In particular, the proposed algorithm returns a consensus set, which quantifies the uncertainty of data and achieves a desired correctness guarantee.
  arXiv  Detail & Related papers  (2022-11-17T04:37:24Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees [123.0401978870009]
  We propose Byzantine-robust federated learning protocols with nearly optimal statistical rates. We benchmark against competing protocols and show the empirical superiority of the proposed protocols. Our protocols with bucketing can be naturally combined with privacy-guaranteeing procedures to introduce security against a semi-honest server.
  arXiv  Detail & Related papers  (2022-05-24T04:03:07Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  We study multi-objective reinforcement learning (RL) where an agent's reward is represented as a vector. In settings where an agent competes against opponents, its performance is measured by the distance of its average return vector to a target set. We develop statistically and computationally efficient algorithms to approach the associated target set.
  arXiv  Detail & Related papers  (2021-02-05T14:26:00Z)

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.