Reusable Formal Verification of DAG-based Consensus Protocols

• URL: http://arxiv.org/abs/2407.02167v2
• Date: Tue, 18 Mar 2025 16:10:48 GMT
• Title: Reusable Formal Verification of DAG-based Consensus Protocols
• Authors: Nathalie Bertrand, Pranav Ghorpade, Sasha Rubin, Bernhard Scholz, Pavle Subotic,
• Abstract summary: This paper presents safety-verified specifications for five DAG-based consensus protocols.<n>Four of these protocols -- DAG-Rider, Cordial Miners, Hashgraph, and Eventualous BullShark -- are well-established in the literature.<n>We employ TLA+ for specifying the protocols and writing their proofs, and the TLAPS proof system to automatically check the proofs.
• Score: 8.277981465630377
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Blockchains use consensus protocols to reach agreement, e.g., on the ordering of transactions. DAG-based consensus protocols are increasingly adopted by blockchain companies to reduce energy consumption and enhance security. These protocols collaboratively construct a partial order of blocks (DAG construction) and produce a linear sequence of blocks (DAG ordering). Given the strategic significance of blockchains, formal proofs of the correctness of key components such as consensus protocols are essential. This paper presents safety-verified specifications for five DAG-based consensus protocols. Four of these protocols -- DAG-Rider, Cordial Miners, Hashgraph, and Eventual Synchronous BullShark -- are well-established in the literature. The fifth protocol is a minor variation of Aleph, another well-established protocol. Our framework enables proof reuse, reducing proof efforts by almost half. It achieves this by providing various independent, formally verified, specifications of DAG construction and ordering variations, which can be combined to express all five protocols. We employ TLA+ for specifying the protocols and writing their proofs, and the TLAPS proof system to automatically check the proofs. Each TLA+ specification is relatively compact, and TLAPS efficiently verifies hundreds to thousands of obligations within minutes. The significance of our work is two-fold: first, it supports the adoption of DAG-based systems by providing robust safety assurances; second, it illustrates that DAG-based consensus protocols are amenable to practical, reusable, and compositional formal methods.

Related papers

• Atomic Transfer Graphs: Secure-by-design Protocols for Heterogeneous Blockchain Ecosystems [7.312229214872541]
  We propose a framework for generating secure-by-design protocols that realize common security and functionality goals. The resulting protocols build upon Timelock Contracts (CTLCs), a novel minimal smart contract functionality. Our framework is the first to provide generic and provably secure protocols for all these use cases while matching or improving the performance of existing use-case-specific protocols.
  arXiv  Detail & Related papers  (2025-01-29T17:25:53Z)
• Automated Selfish Mining Analysis for DAG-based PoW Consensus Protocols [0.0]
  Selfish mining is strategic rule-breaking to maximize rewards in proof-of-work protocols. We propose a generic attack model that covers a wide range of protocols, including Proof-of-Work, GhostDAG, and Parallel Proof-of-Work.
  arXiv  Detail & Related papers  (2025-01-18T21:57:02Z)
• Formal Model Guided Conformance Testing for Blockchains [1.4838910416636741]
  We present a framework that performs protocol conformance testing using a formal model of the protocol. Our framework consists of two complementary components that use the components as trace generators and checkers.
  arXiv  Detail & Related papers  (2025-01-15T03:20:13Z)
• CryptoFormalEval: Integrating LLMs and Formal Verification for Automated Cryptographic Protocol Vulnerability Detection [41.94295877935867]
  We introduce a benchmark to assess the ability of Large Language Models to autonomously identify vulnerabilities in new cryptographic protocols. We created a dataset of novel, flawed, communication protocols and designed a method to automatically verify the vulnerabilities found by the AI agents.
  arXiv  Detail & Related papers  (2024-11-20T14:16:55Z)
• Quantum digital signature based on single-qubit without a trusted third-party [45.41082277680607]
  We propose a novel quantum digital signature protocol without a trusted third-party. We prove that the protocol has information-theoretical unforgeability.
  arXiv  Detail & Related papers  (2024-10-17T09:49:29Z)
• 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)
• On the Design and Security of Collective Remote Attestation Protocols [5.01030444913319]
  Collective remote attestation (CRA) is a security service that aims to efficiently identify compromised devices in a (heterogeneous) network. The last few years have seen an extensive growth in CRA protocol proposals, showing a variety of designs guided by different network topologies. We present Catt, a unifying framework for CRA protocols that enables them to be compared systematically.
  arXiv  Detail & Related papers  (2024-07-12T12:06:49Z)
• Protocols to Code: Formal Verification of a Next-Generation Internet Router [9.971817718196997]
  SCION routers run a cryptographic protocol for secure packet forwarding in an adversarial environment. We verify both the protocol's network-wide security properties and low-level properties of its implementation. This paper explains our approach, summarizes the main results, and distills lessons for the design and implementation of verifiable systems.
  arXiv  Detail & Related papers  (2024-05-09T19:57:59Z)
• Security of hybrid BB84 with heterodyne detection [0.0]
  Quantum key distribution (QKD) promises everlasting security based on the laws of physics. Recent hybrid QKD protocols have been introduced to leverage advantages from both categories. We provide a rigorous security proof for a protocol introduced by Qi in 2021, where information is encoded in discrete variables.
  arXiv  Detail & Related papers  (2024-02-26T19:00:01Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• A Survey and Comparative Analysis of Security Properties of CAN Authentication Protocols [92.81385447582882]
  The Controller Area Network (CAN) bus leaves in-vehicle communications inherently non-secure. This paper reviews and compares the 15 most prominent authentication protocols for the CAN bus. We evaluate protocols based on essential operational criteria that contribute to ease of implementation.
  arXiv  Detail & Related papers  (2024-01-19T14:52:04Z)
• Short Paper: Accountable Safety Implies Finality [10.589723476970443]
  Two key desiderata have been studied for Byzantine-fault tolerant (BFT) state-machine replication (SMR) consensus protocols. We show that accountable safety implies finality, thereby unifying earlier results.
  arXiv  Detail & Related papers  (2023-08-31T17:58:38Z)
• Provably Secure Commitment-based Protocols over Unauthenticated Channels [0.0]
  We build a theoretic security framework to cover protocols whose characteristics may not always concur with existing models for authenticated exchanges. We propose a number of Commitment-based protocols to establish a shared secret between two parties, and study their resistance over unauthenticated channels. This means analyzing the security robustness of the protocol itself, and its robustness against Man-in-the-Middle attacks.
  arXiv  Detail & Related papers  (2023-07-28T10:35:35Z)
• A Security Verification Framework of Cryptographic Protocols Using Machine Learning [0.0]
  We propose a security verification framework for cryptographic protocols using machine learning. We create arbitrarily large datasets by automatically generating random protocols and assigning security labels to them. We evaluate the proposed method by applying it to verification of practical cryptographic protocols.
  arXiv  Detail & Related papers  (2023-04-26T02:37:43Z)
• 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)
• Data post-processing for the one-way heterodyne protocol under composable finite-size security [62.997667081978825]
  We study the performance of a practical continuous-variable (CV) quantum key distribution protocol. We focus on the Gaussian-modulated coherent-state protocol with heterodyne detection in a high signal-to-noise ratio regime. This allows us to study the performance for practical implementations of the protocol and optimize the parameters connected to the steps above.
  arXiv  Detail & Related papers  (2022-05-20T12:37:09Z)
• Round-robin differential phase-time-shifting protocol for quantum key distribution: theory and experiment [58.03659958248968]
  Quantum key distribution (QKD) allows the establishment of common cryptographic keys among distant parties. Recently, a QKD protocol that circumvents the need for monitoring signal disturbance, has been proposed and demonstrated in initial experiments. We derive the security proofs of the round-robin differential phase-time-shifting protocol in the collective attack scenario. Our results show that the RRDPTS protocol can achieve higher secret key rate in comparison with the RRDPS, in the condition of high quantum bit error rate.
  arXiv  Detail & Related papers  (2021-03-15T15:20:09Z)
• Twin-field quantum digital signatures [4.503555294002338]
  Digital signature is a key technique in information security, especially for identity authentications. Quantum digital signatures (QDSs) provide a considerably higher level of security, i.e., information-theoretic security.
  arXiv  Detail & Related papers  (2020-03-25T08:04:59Z)

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.