COTI

We express our gratitude to the COTI and Soda Labs team for the collaborative engagement that enabled the execution of this Garbling-Based MPC Protocol Security Assessment.

The MPC protocol leverages garblers and dual evaluators to privately compute smart contracts, preserving privacy and security for Ethereum Virtual Machine (EVM) execution in a blockchain setup.

The system users should acknowledge all the risks summed up in the risks section of the report

Documentation quality

• Documentation is accessible within the codebase, offering clear explanations for components like input wire types and method functionalities.

• Efforts to articulate intent are evident, providing a solid starting point for a complex cryptographic system.

• The client provides a comprehensive whitepaper, "Soda Labs MPC Specification for: A Protocol for Two Evaluators" (December 2024), detailing the system design, including security assumptions for IT-MACs, label authentication, and high-level protocol overviews for both semi-honest and malicious threat models. This enhances the effectiveness of security analysis, though minor gaps in implementation specifics remain.

• README and building instructions are present but outdated, requiring revision to reflect current developments.

• Recommendations include completing TODOs, adding security notes, unifying comment depth, and providing a protocol summary.

Code quality

• Codebase demonstrates high potential with advanced techniques like Half Gates and Free XOR for private smart contract computation.

• Core cryptographic logic shows thoughtful design.

• Issues include unowned pointers, hardcoded values, and missing input validation/buffer checks.

• Non-constant-time operations and unresolved TODOs highlight areas needing attention for robustness.

• Modularity is maintained, but edge cases and integrity checks require further specification to ensure security.

Architecture quality

• Architecture leverages innovative separation and distribution of the garbling and evaluation design with Half Gates and Free XOR, enhancing privacy and decentralization.

• Cryptographic whitepaper provides a clear foundation, supporting maintainability of the garbling process.

• The Garbler’s central role in generating garbled circuits and reliance on fixed cryptographic seeds for key derivation suggest opportunities for dynamic key management enhancements, such as periodic key rotation or distributed key generation, to enhance security and resilience.

Soda MPC Protocol is designed to facilitate privacy-preserving execution of user-defined smart contracts. Built on Yao’s Garbled Circuits with Half Gates optimization and Free XOR techniques, it operates as an MPC-as-a-service platform. Users onboard with a symmetric encryption key, shared among MPC nodes, to encrypt private transaction data, ensuring confidentiality even from individual nodes. The protocol supports malicious mode  - tailored to different threat models, aiming to guarantee correctness and privacy under limited adversarial corruption.

System Architecture

The architecture of the version under this audit revolves around a distributed setup involving two Garblers with different signing keys, two Evaluators, and a Key Management Service (KMS). These components collaborate across offline and online phases to prepare, distribute, and compute garbled circuits representing EVM opcodes of encrypted arguments. The design emphasizes privacy by splitting sensitive data and computation across parties, with no single node gaining full visibility into user inputs or outputs.

Garbler Replicas

Role: Acts as the circuit generators and coordinators, responsible for transforming EVM opcodes into a garbled form that obscures its execution.

Function: A Garbler produces garbled circuits using a randomized process, incorporating optimizations like Half Gates to reduce computational overhead. It generates and distributes shares of input labels, permutation bits, and authentication data to the Evaluators. To protect against a single malicious Garbler, two Garblers operate as replicas to protect against single-point compromise, ensuring consistency in circuit generation.

Evaluators E and E

Role: Serve as the computational engines, jointly evaluating garbled circuits to produce contract outputs without learning the underlying private data.

Function: Receive garbled circuits and shares from the Garbler, reconstruct necessary labels based on input types (public, private prior outputs, or secret-shared), and verify the authenticity of data using cryptographic checks. The dual-evaluator setup ensures that each party holds only partial information, requiring cooperation to complete the computation and maintain privacy.

Key Management Service KMS

Role: Initiating user key generation and authentication, mitigating risks from dishonest Evaluators.

Function: Generates pseudorandom key shares for users, encrypts them for delivery, and provides authentication data to Evaluators to ensure key consistency across uses. Typically co-located with the Garbler, it acts as a trusted intermediary to prevent Evaluators from supplying incorrect shares or disrupting the protocol. In order to mitigate a single malicious KMS node, this function is replicated twice and the Evaluators match their response before proceeding to the next steps.

Major Components and Workflow

• Garbled Circuits: Represent EVM opcodes as cryptographic constructs, using Half Gates to optimize AND gates (two ciphertexts per gate) and Free XOR to eliminate XOR gate overhead. The Garbler creates these circuits offline, embedding a per circuit offset (Δ) to maintain label relationships.

• Label and Bit Sharing: Inputs and outputs are represented by labels (e.g., L{i,0},  L{i,1}) and permutation bits (p_i), split into shares between Evaluators. This ensures no single party can encode or decode private values without collaboration.

• Authentication Mechanisms: Information-theoretic MACs (IT-MACs) secure permutation bits, leveraging XOR-homomorphism for efficient verification, while AES-based PRP authenticate labels, ensuring integrity against tampering.

• User Key Management: Users receive a symmetric AES key (k_U) during onboarding, split into shares held by Evaluators. In the semi-honest variant, Evaluators generate and deliver shares directly; in the malicious variant, the KMS ensures authenticated, consistent shares.

Protocol Phases

• Offline Phase: The Garbler prepares garbled circuits and distributes them, along with shares and authentication data, to the Evaluators. This phase uses pseudorandom generation from seeds to enable matching of GCs from Garbler's replicas, enabling scalable circuit preparation.

• Online Phase: Evaluators consume garbled circuits as needed, reconstructing labels for current inputs, verifying authenticity, and evaluating the circuit to compute outputs. The process supports public, private, and secret-shared inputs, adapting to each type’s privacy requirements.

• User Onboarding: Users join the system by obtaining a symmetric key, shared among Evaluators, which they use to encrypt transaction data.

Threat Models and Security Goals

• Malicious Variant (2 Garblers, 2 Evaluators): Handles active corruption of one Garbler or Evaluator, maintaining correctness and privacy (though availability may suffer); multiple corruptions can compromise both properties.

Summary

The Garbling-based MPC Protocol enables private smart contract execution by distributing trust across Garblers and Evaluators, with optional KMS support for malicious settings. It leverages optimized garbling, shared labels, and robust authentication to balance privacy, efficiency, and security, making it a specialized MPC solution for decentralized applications.

The scope of the project includes the following components from the provided repository:

The remediation check has been conducted based on commit hash 649eb99 →, which reflects the status of each issue following this process. It is important to acknowledge that this commit may include changes made subsequent to the initial review commit, which were not part of the audit assessment.

Assets in Scope