Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience

Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience

Speakers: Yuan Su

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=e5wF1NfadSk

Overview

This talk introduces Dumbo-MPC, a novel framework for Secure Multi-Party Computation (MPC) designed to achieve both high efficiency and optimal resilience in fully asynchronous network environments. Presented by Yuan Su, Dumbo-MPC addresses critical limitations of existing MPC protocols, which often struggle with either performance or robustness when operating over unreliable, globally distributed networks like the internet. The core innovation lies in its dual-mode triple generation framework, which intelligently combines a fast, optimistic path with a robust, pessimistic fallback mechanism.

The significance of Dumbo-MPC is particularly pronounced in applications demanding both privacy and guaranteed output delivery, such as private smart contracts on a blockchain. In such scenarios, the inherent unreliability of global networks can lead to censorship attacks or computation failures if the underlying MPC protocol cannot withstand network interruptions, attacks, or misconfigurations. By providing a concretely efficient and robust solution for fully asynchronous networks, Dumbo-MPC offers a practical pathway for deploying secure and private computations in real-world, adversarial settings, moving beyond the idealized synchronous network assumptions of much prior work.

Background

▶ Watch: Problem: Need for practical asynchronous MPC (0:35)

Secure Multi-Party Computation (MPC) enables a group of servers to jointly compute a function on their private inputs without revealing those inputs to each other. The goal is to ensure both correctness of the computation and privacy of the inputs, even in the presence of malicious or "batting" (Byzantine) servers. The standard MPC-as-a-service framework typically involves two phases: an offline phase for generating essential cryptographic primitives like Beaver triples and random shares, and an online phase where these precomputed resources are used to quickly evaluate predetermined functions based on provided inputs.

A critical challenge for MPC deployment, especially in distributed applications like blockchain-based smart contracts, is the underlying network model. Most early and even many modern MPC protocols, such as the classic BGW (Ben-Or, Goldwasser, Wigderson) protocol, rely on a synchronous network model. This model assumes a known upper bound on network delay, allowing parties to wait for all honest participants' messages before proceeding. However, real-world internet deployments often operate under asynchronous network conditions, where network delays are unknown, and messages are only guaranteed to be eventually delivered. In such environments, synchronous protocols can fail: waiting for all honest parties' shares becomes impossible if delays are unbounded, leading to potential compromises in privacy or even outright failure to complete the computation. Malicious parties can exploit this by simply withholding messages, causing a censorship attack where robust output delivery is not guaranteed.

Prior attempts to construct asynchronous MPC protocols, such as those by Goldreich and Ostrovsky (GR98) and Gennaro and Su (GS23), made progress but faced significant efficiency hurdles. These protocols often involved complex procedures like verifiable secret sharing, polynomial commitment, and degree reduction, leading to high communication complexity—often cubic per triple in the worst case. Additionally, they might require parties to share multiple secrets (e.g., three secrets per triple) to achieve robustness. While these protocols offered robustness, their inefficiency made them impractical for many applications. Conversely, some protocols, like "Honey PC," provided efficient triple generation in a "good case" (i.e., when all parties behave honestly) but lacked robustness in their offline phase, meaning they could not guarantee output delivery if malicious parties were present. This created a dilemma: either robust but inefficient, or efficient but non-robust. The problem Dumbo-MPC aims to solve is to bridge this gap, offering a concretely efficient and robust MPC solution that operates effectively in fully asynchronous networks with optimal resilience.

Key Findings

▶ Watch: Introducing Dumbo-MPC's dual-path architecture (5:30)

The central contribution of Dumbo-MPC is its innovative dual-mode triple generation framework, designed to overcome the long-standing trade-off between efficiency and robustness in asynchronous MPC. The system is structured around two primary operational modes: a Fast Pass and a Pessimistic Pass, seamlessly integrated with a secure fallback mechanism.

The key findings and contributions include:

1. Dual-Mode Framework for Optimal Resilience and Efficiency: Dumbo-MPC introduces a hybrid approach where the Fast Pass prioritizes speed and efficiency, offering linear overhead and outperforming existing efficient but non-robust schemes like Honey PC in good network conditions. If the Fast Pass encounters misbehavior or timeouts, the system transitions to a Pessimistic Pass, which is designed for robust, guaranteed output delivery, even in the presence of adversaries. This dual approach ensures that the protocol is both fast when possible and robust when necessary.

1. Concretely Efficient Pessimistic Pass: Unlike prior robust asynchronous MPC solutions (e.g., GS23) which suffered from cubic communication complexity, Dumbo-MPC's Pessimistic Pass achieves significantly better efficiency, operating with quadratic overhead. This improvement is largely attributed to the use of compact k-polynomial commitment and other cryptographic optimizations. The Pessimistic Pass is shown to be more efficient than GS23 in "bad case" scenarios (i.e., when misbehavior occurs).

1. Secure and Efficient Fallback Mechanism: A crucial component is the asynchronous fallback protocol, which acts as a conceptual minimum Byzantine Agreement. This mechanism allows honest parties to agree on the state of the Fast Pass, specifically identifying the last round where correct triples were generated, before transitioning to the robust Pessimistic Pass. This ensures seamless and secure recovery from Fast Pass failures.

1. Optimized Triple Generation: The protocol significantly reduces the overhead associated with generating Beaver triples. Specifically, it reduces the number of secrets that need to be shared from an initial three per triple to a more efficient structure, specifically mentioning "A+6" components, indicating a substantial optimization in the sharing process. This, combined with the use of a super invertible matrix for extracting random shares, contributes to the overall efficiency gain.

1. Enhanced Cryptographic Primitives: Dumbo-MPC leverages and extends advanced cryptographic tools, including a novel hidden evaluation interface for KG commitment to enable efficient zero-knowledge proofs of product relations, and an improved construction of Homomorphic Batch AVS (HBACS) that addresses concurrent composability vulnerabilities using NDCCA-secure public encryption with distinct keys for different dealer instances.

In summary, Dumbo-MPC successfully constructs an MPC protocol that is concretely efficient, proactively robust, and guarantees output delivery in fully asynchronous networks with optimal resilience, effectively providing the "best of both worlds" by combining the speed of efficient non-robust protocols with the security guarantees of robust but typically slower ones.

Technical Deep Dive

▶ Watch: Technical innovations: K-polynomial commitment and HBACS (6:20)

Dumbo-MPC's architecture is centered around its dual-mode triple generation framework, ingeniously combining a high-speed, optimistic path with a resilient, pessimistic fallback. This design is crucial for achieving both efficiency and robustness in fully asynchronous networks.

The Fast Pass is the primary mode of operation, designed for continuous, efficient generation of Beaver triples. It boasts linear overhead, making it concretely more efficient than protocols like Honey PC under ideal conditions. The Fast Pass operates on the assumption that parties are largely honest. However, it is designed to abort if timeouts occur or misbehaviors are detected. This abort mechanism is essential, as the Fast Pass does not guarantee robustness on its own. Its purpose is to rapidly generate triples as long as the network and parties cooperate. When the Fast Pass fails in round r, honest parties are guaranteed to have completed round r-2 successfully, providing a consistent state for recovery.

Should the Fast Pass abort, the system transitions via a fallback mechanism. This mechanism is conceptualized as a minimum Byzantine Agreement protocol. Its role is critical: it takes one or two consecutive values as input and enables all honest parties to agree on the specific round in the Fast Pass where all honest parties had successfully generated correct triples. This consensus point is vital for ensuring a smooth and secure handover to the robust Pessimistic Pass without compromising privacy or correctness.

The Pessimistic Pass is the robust core of Dumbo-MPC, designed to guarantee triple generation even in the presence of malicious adversaries in a fully asynchronous environment. This path has quadratic overhead, which, while higher than the Fast Pass, is significantly more efficient than prior robust asynchronous protocols like GS23 that suffered from cubic complexity. The efficiency gains in the Pessimistic Pass stem from several cryptographic innovations:

1. Compact k-Polynomial Commitment: This is a cornerstone of the Pessimistic Pass. Unlike simpler commitments, k-polynomial commitments allow for more convenient interpolation into exponents to derive any evaluation commitment. This compact representation is instrumental in reducing communication and computation overhead.

1. Hidden Evaluation Interface: To enable efficient proofs of correctness, the scheme introduces a hidden evaluation interface to the KG commitment. This interface allows for proving correct multiplication by leveraging zero-knowledge proofs of knowledge of product relations. The hidden evaluations satisfy both binding and hiding properties, ensuring that the correctness of computations can be verified without revealing the underlying values. This is a critical component for ensuring the integrity of the Beaver triple generation.

1. Augmented HBACS (Homomorphic Batch AVS): Dumbo-MPC utilizes and augments HBACS, which appears to be a form of Homomorphic Batch Asynchronous Verifiable Secret Sharing. Verifiable Secret Sharing (VSS) is fundamental for distributing secrets among parties in a way that allows verification of correctness. The "batch" aspect implies efficiency when sharing multiple secrets simultaneously. A significant challenge with HBACS is its concurrent composability vulnerability. Dumbo-MPC addresses this by employing NDCCA (Non-malleable Chosen Ciphertext Attack) secure public encryption and leveraging different keys in different dealer instances. This countermeasure patches the vulnerability, ensuring that the HBACS can be safely used in concurrent executions without succumbing to attacks that exploit interactions between multiple instances.

1. Optimized Triple Generation Protocol: Building upon the HBACS and augmented KG commitment, the Pessimistic Pass constructs a highly efficient triple generation protocol. This protocol innovatively extracts random shares using a super invertible matrix. This mathematical tool allows for efficient and verifiable extraction of shares, contributing to the overall performance. Furthermore, the protocol significantly reduces the number of secrets to be shared, moving from three secrets per triple in prior schemes to a more efficient structure, specifically mentioning "A+6" components. This optimization directly reduces the communication and computation burden associated with secret sharing.

In operation, parties continuously attempt to generate triples using the Fast Pass. If this fails, the fallback mechanism ensures agreement on the last successful state, and then all honest parties transition to the Pessimistic Pass to robustly complete the triple generation for the required evaluations. This seamless integration ensures that Dumbo-MPC always provides guaranteed output delivery, while leveraging the speed of the Fast Pass whenever possible.

Demo / Proof of Concept

▶ Watch: Performance evaluation and comparison with prior work (8:20)

While the talk did not feature a live, interactive demonstration of Dumbo-MPC in action, it presented compelling performance evaluations to validate its efficiency and robustness claims. These evaluations serve as the empirical proof of concept, demonstrating how Dumbo-MPC concretely outperforms existing asynchronous MPC protocols.

The performance analysis highlighted several key aspects:

1. Comparison in "Bad Case" Scenarios: Dumbo-MPC was shown to be faster than GS23 (Gennaro and Su, 2023) in scenarios where misbehavior occurs, representing the "bad case" for the Fast Pass where the Pessimistic Pass takes over. This directly addresses the inefficiency of prior robust asynchronous MPC schemes.

1. Comparison in "Good Case" Scenarios: In conditions where the Fast Pass operates without interruption, Dumbo-MPC demonstrated superior performance. It was found to be faster than Honey MPC plus the secure fallback time in the face of dynamic crashes. This indicates that the Fast Pass is indeed highly efficient, and the overhead of the fallback mechanism is manageable, allowing Dumbo-MPC to leverage its speed advantage.

1. Robust Triple Generation for N-Node MPC: The evaluation specifically considered a four-node MPC setup, illustrating that Dumbo-MPC can robustly generate triples while maintaining efficiency. This is a practical validation for smaller-scale, yet critical, distributed applications.

1. Application-Specific Latency Evaluation: The talk further evaluated the latency of pre-processing triples for specific applications, namely victory auctions and mixing nets. The results, presented in accompanying figures, confirmed that Dumbo-MPC is concretely efficient for these real-world use cases. This underscores its applicability and practicality beyond theoretical benchmarks.

These evaluations collectively confirm Dumbo-MPC's ability to deliver both efficiency and robustness in asynchronous environments, making a strong case for its practical utility in scenarios demanding secure and private computation over unreliable networks.

Defensive Implications

▶ Watch: Conclusion: Dumbo-MPC's efficiency and robustness (9:00)

Dumbo-MPC offers significant defensive implications for organizations and developers grappling with the challenges of secure multi-party computation in real-world, unreliable network environments. Its design provides robust guarantees against various attack vectors and practical solutions for deploying privacy-preserving technologies.

1. Guaranteed Output Delivery Against Censorship Attacks: For applications like private smart contracts on blockchains, where malicious miners or network disruptions could prevent the completion of computations, Dumbo-MPC provides guaranteed output delivery. This is a crucial defensive property, as it prevents adversaries from launching censorship attacks by simply withholding messages or causing timeouts. The protocol's optimal resilience ensures that even with a significant fraction of malicious parties (up to the optimal threshold for asynchronous MPC), honest parties will eventually complete the computation.

1. Enhanced Robustness for Critical Infrastructure: Deploying MPC in critical infrastructures, especially those distributed globally over the internet, requires strong guarantees against network unreliability and attacks. Dumbo-MPC's focus on fully asynchronous networks means it can withstand transmission interruptions, internet attacks, and network misconfigurations, which are common in real-world scenarios. This makes it a more suitable foundation for secure computation services than protocols reliant on idealized synchronous assumptions.

1. Practical Efficiency for Adoption: The concrete efficiency of Dumbo-MPC, particularly its fast pass and optimized pessimistic pass, lowers the barrier to entry for adopting robust MPC. High overhead has historically been a deterrent for widespread MPC deployment. By offering a solution that is both robust and practically efficient, Dumbo-MPC enables developers to build and deploy privacy-preserving applications without incurring prohibitive performance costs.

1. Foundation for Future Secure Systems: The novel cryptographic primitives and techniques introduced by Dumbo-MPC, such as compact k-polynomial commitments, hidden evaluation interfaces, and enhanced HBACS, provide a stronger foundation for building future secure systems. Researchers and practitioners can leverage these advancements to develop even more efficient and secure protocols, pushing the boundaries of what is possible in confidential computing.

1. Mitigation of Privacy Compromises in Asynchronous Settings: Earlier synchronous robust MPC attempts in asynchronous settings could "inject unresponsible parties," which could compromise privacy if honest parties eventually revealed their shares due to waiting indefinitely. Dumbo-MPC, by design for asynchronous networks, prevents such scenarios, maintaining privacy even when parties are unresponsive or malicious.

In essence, Dumbo-MPC equips defenders with a powerful tool to ensure the integrity, privacy, and availability of sensitive computations in the face of network adversity and malicious actors, making robust MPC a more tangible and deployable reality.

Key Takeaways

• Dual-Mode Approach for Optimal Balance: Dumbo-MPC introduces a novel dual-mode framework, combining a fast, optimistic "Fast Pass" for efficiency with a robust, "Pessimistic Pass" for guaranteed output delivery, effectively balancing speed and security in asynchronous networks.
• Robustness in Asynchronous Environments: It is explicitly designed for fully asynchronous networks, providing optimal resilience and guaranteed output delivery against network interruptions, attacks, and misconfigurations, crucial for global deployments like blockchain.
• Significant Efficiency Gains: The protocol achieves concrete efficiency, with a linear overhead Fast Pass and a quadratic overhead Pessimistic Pass, outperforming prior asynchronous MPC schemes like GS23 in bad cases and Honey PC in good cases.
• Advanced Cryptographic Primitives: Key innovations include compact k-polynomial commitments, a hidden evaluation interface for zero-knowledge proofs of product relations, and an augmented HBACS (Homomorphic Batch AVS) secured against concurrent composability vulnerabilities.
• Practical for Real-World Applications: Dumbo-MPC's performance evaluations for applications like victory auctions and mixing nets demonstrate its practical applicability and efficiency for real-world scenarios demanding privacy-preserving computations.
• Critical for Decentralized Finance and Privacy: The framework is particularly relevant for enabling robust and private smart contracts in decentralized finance (DeFi) and other blockchain applications, preventing censorship attacks and ensuring privacy in untrustworthy network environments.

About the Speaker(s)

Yuan Su presented the Dumbo-MPC framework. Based on the provided information, Yuan Su is a researcher in the field of secure multi-party computation, contributing to advancements in efficient and robust cryptographic protocols.