2025-11-21T20:28:23.433071

OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA

Chen
In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message $\boldsymbol{w}$ with expected $O(n |\boldsymbol{w}|\log n + n^2 \log q)$ communication bits, expected $O(n^2)$ messages, expected $O(\log n)$ rounds, and expected $O(\log n)$ common coins, under optimal resilience $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, $q$ becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^2 \log n)$ communication bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under a relaxed resilience (RR) of $n \geq 5t + 1$. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^3)$ bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under optimal resilience $n \geq 3t + 1$.
academic

OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA

Basic Information

  • Paper ID: 2501.00214
  • Title: OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA
  • Author: Jinyuan Chen
  • Classification: cs.CR (Cryptography and Security), cs.DC (Distributed Computing), cs.IT (Information Theory), math.IT (Information Theory)
  • Publication Date: December 31, 2024 (arXiv preprint)
  • Paper Link: https://arxiv.org/abs/2501.00214

Abstract

This paper proposes OciorMVBA, an error-free, information-theoretically secure asynchronous multi-valued validated Byzantine agreement (MVBA) protocol. The protocol achieves MVBA consensus on message w in an n-node network with optimal fault tolerance n ≥ 3t + 1, with expected communication complexity of O(n|w|log n + n²log q) bits, expected O(n²) messages, expected O(log n) rounds, and expected O(log n) common coin invocations. Additionally, two variant protocols are proposed: OciorMVBArr achieving O(1) round complexity under relaxed fault tolerance n ≥ 5t + 1, and hash-based OciorMVBAh achieving O(1) round complexity under optimal fault tolerance.

Research Background and Motivation

Problem Definition

Multi-valued validated Byzantine agreement (MVBA) is a critical building block in distributed systems and cryptography, introduced by Cachin et al. in 2001. In MVBA, distributed nodes propose their respective input values and seek consensus on one value satisfying a predefined predicate function (external validity).

Research Significance

  1. Theoretical Foundation: The seminal work of Fischer, Lynch, and Paterson demonstrates that no deterministic MVBA protocol exists in asynchronous environments; therefore, any asynchronous MVBA protocol must introduce randomness.
  2. Practical Demand: Distributed systems require reliable consensus achievement in asynchronous networks with Byzantine faults.
  3. Security Requirements: Information-theoretic security must be guaranteed without relying on cryptographic assumptions (except for common coin).

Limitations of Existing Approaches

As shown in Table I comparison, existing MVBA protocols face the following issues:

  • Most rely on cryptographic assumptions such as threshold signatures or hashing
  • High communication complexity, particularly without cryptographic assumptions
  • Room for improvement in round complexity and common coin usage efficiency

Core Contributions

  1. Proposed OciorMVBA Protocol: The first error-free, information-theoretically secure asynchronous MVBA protocol achieving near-optimal communication complexity O(n|w|log n + n²log q) under optimal fault tolerance n ≥ 3t + 1.
  2. Designed OciorMVBArr Protocol: A protocol achieving O(n|w| + n²log n) communication complexity and O(1) round complexity under relaxed fault tolerance n ≥ 5t + 1.
  3. Constructed OciorMVBAh Protocol: A hash-based protocol achieving O(n|w| + n³) communication complexity and O(1) round complexity under optimal fault tolerance.
  4. Introduced New Primitives: Proposed asynchronous biased binary Byzantine agreement (ABBBA) and asynchronous complete information dispersal (ACID) as new building blocks.

Methodology Details

Task Definition

Input: Each honest node proposes an input value w satisfying Predicate(w) = true Output: All honest nodes eventually output the same value w', with Predicate(w') = true Constraints: Satisfy three properties: consistency, termination, and external validity

OciorMVBA Protocol Architecture

Overall Design

OciorMVBA is a recursive protocol with main components including:

  • RMVBA(ID, p): Recursive MVBA protocol
  • SHMDM: Strong honest majority distributed multicast
  • OciorRBA: Reliable Byzantine agreement
  • ABBBA: Asynchronous biased binary Byzantine agreement
  • ABBA: Asynchronous binary Byzantine agreement

Core Algorithm Flow

  1. Network Partitioning: Partition network Sp into two disjoint subsets S2p and S2p+1
  2. Recursive Invocation: Execute RMVBA sub-protocols in parallel on sub-networks
  3. Message Propagation: Propagate sub-protocol outputs through SHMDM protocol
  4. Consistency Verification: Verify message reliability using OciorRBA
  5. Election Mechanism: Determine final output through ordered election and ABBBA/ABBA protocols

Key Technical Details

Ready-Finish-Confirm Process:

Step 1: Sub-protocol output → SHMDM propagation
Step 2: SHMDM output → OciorRBA verification
Step 3: OciorRBA output vi=1 → Set Iready[θ]=1, send READY message
Step 4: Receive sufficient READY messages → Set Ifinish[θ]=1, send FINISH message
Step 5: Receive sufficient FINISH messages → Set Iconfirm[θ]=1

ABBBA Protocol:

  • Input: Binary pair (a1, a2)
  • Biased Validity: If t+1 honest nodes input a2=1, then output 1
  • Biased Completeness: If output 1, then at least one honest node inputs a1=1 or a2=1

OciorRBA Protocol Design

Extended from COOL and OciorCOOL protocols, comprising three phases:

  1. Phase 1: Symbol exchange and link indicator update
  2. Phase 2: Success indicator processing
  3. Phase 3: Online error correction and message reconstruction

Technical Innovations

  1. Recursive Architecture: Achieves logarithmic round complexity through network partitioning and recursive invocation
  2. Biased Agreement: ABBBA protocol provides fast termination under specific conditions
  3. Online Error Correction: Uses Reed-Solomon codes or Expander codes for efficient error correction
  4. Cryptography-Free: Depends on no cryptographic primitives except common coin

Experimental Setup

Theoretical Analysis Framework

The paper primarily conducts theoretical analysis, verifying protocol properties through:

Complexity Analysis:

  • Communication Complexity: Recursive relation analysis
  • Round Complexity: Network tree depth analysis
  • Message Complexity: Protocol interaction count statistics

Security Proof:

  • Consistency: Proven via Lemma 3
  • Termination: Proven via network chain analysis (Lemma 2, 4)
  • External Validity: Guaranteed through predicate verification

Comparison Benchmarks

Compared with existing MVBA protocols, including:

  • Cachin et al. 1 - Seminal threshold signature-based work
  • Abraham et al. 8 - Optimized threshold signature scheme
  • Dumbo-MVBA 9 - Efficient threshold signature protocol
  • Duan et al. 10 - Hash-based and cryptography-free protocol

Experimental Results

Main Theoretical Results

OciorMVBA Performance:

  • Communication Complexity: O(n|w|log n + n²log q) bits
  • Message Complexity: O(n²)
  • Round Complexity: O(log n)
  • Common Coin: O(log n)

OciorMVBArr Performance (n ≥ 5t + 1):

  • Communication Complexity: O(n|w| + n²log n) bits
  • Round Complexity: O(1)
  • Common Coin: O(1)

OciorMVBAh Performance:

  • Communication Complexity: O(n|w| + n³) bits
  • Round Complexity: O(1)
  • Common Coin: O(1)

Complexity Analysis

Through recursive relation:

fTB(ñp) = β1ñp|w| + β2ñp²log q + fTB(⌊ñp/2⌋) + fTB(⌈ñp/2⌉)

The total communication complexity is proven to be O(n|w|log n + n²log q).

Protocol Correctness

Through a series of lemmas, the protocol is proven to satisfy three core MVBA properties:

  • Theorem 1: Consistency and Termination
  • Theorem 2: External Validity
  • Theorem 3: Communication and Round Complexity

Related Work

MVBA Protocol Development

  1. Early Work: Cachin et al. first introduced the MVBA concept
  2. Signature-Based Methods: Abraham et al., Dumbo-MVBA, and others optimized threshold signature-based protocols
  3. Signature-Free Methods: Duan et al. proposed hash-based signature-free protocols
  4. Information-Theoretic Security: This paper is the first to achieve near-optimal performance with information-theoretic security under optimal fault tolerance

Technical Foundation

  • COOL/OciorCOOL Protocols: Provide UA and HMDM primitives
  • Error-Correcting Code Theory: Application of Reed-Solomon codes and Expander codes
  • Byzantine Agreement: Development from classical work by Pease, Shostak, and Lamport

Conclusions and Discussion

Main Conclusions

  1. Under optimal fault tolerance n ≥ 3t + 1, achieved the first near-optimal error-free, information-theoretically secure asynchronous MVBA protocol.
  2. By relaxing fault tolerance or introducing hash assumptions, constant round complexity can be achieved.
  3. Recursive design and biased agreement mechanisms are key to achieving efficient performance.

Limitations

  1. Constant Factors: Although asymptotically optimal, constant factors may be large.
  2. Common Coin Dependency: Still requires O(log n) common coin invocations.
  3. Network Partitioning: Recursive partitioning may introduce additional overhead in practical networks.
  4. Error-Correcting Code Selection: Performance depends on the alphabet size q of error-correcting codes.

Future Directions

  1. Constant Optimization: Reduce constant factors in the protocol.
  2. Common Coin Efficiency: Further reduce common coin usage.
  3. Practical Implementation: Develop efficient practical implementations and conduct performance evaluation.
  4. Application Extension: Apply the protocol to concrete distributed systems.

In-Depth Evaluation

Strengths

  1. Theoretical Breakthrough: Achieves near-optimal communication complexity under information-theoretic security setting.
  2. Clever Design: The combination of recursive architecture and biased agreement is highly innovative.
  3. Rigorous Analysis: Provides complete correctness proofs and complexity analysis.
  4. Practical Value: Offers multiple variants to accommodate different application scenarios.

Weaknesses

  1. Lack of Experimental Validation: The paper is primarily theoretical analysis, lacking practical implementation and performance testing.
  2. Constant Complexity: Although asymptotically optimal, practical constants may affect usability.
  3. Assumption Conditions: Common coin assumptions may be difficult to realize in practical systems.
  4. Readability: Protocol descriptions are complex, with high difficulty in understanding and implementation.

Impact

  1. Theoretical Contribution: Provides new theoretical benchmarks for the MVBA field.
  2. Technical Inspiration: Recursive design approach may inspire design of other distributed protocols.
  3. Practical Potential: Has application value in scenarios requiring extremely high security guarantees.
  4. Research Direction: Provides new insights for subsequent MVBA protocol optimization.

Applicable Scenarios

  1. High Security Requirements: Critical systems requiring information-theoretic security guarantees.
  2. Large-Scale Networks: Distributed systems with large numbers of nodes.
  3. Asynchronous Environments: Environments with unpredictable network delays.
  4. Fault-Tolerant Systems: Systems requiring Byzantine fault tolerance.

References

The paper cites 17 related references, primarily including:

  • 1 Cachin et al. - Seminal MVBA work
  • 5-7 Chen - COOL and OciorCOOL protocol series
  • 8-12 Recent important advances in MVBA protocols
  • 13-15 Error-correcting code theory foundations
  • 17 Li-Chen's asynchronous Byzantine agreement protocol