How to Implement Beaver Triples for Secure MPC Multiplication in Python (2025)

What You'll Build: A Working Beaver Triple MPC Multiplication Protocol

By the end of this article you'll have a Python script that lets two parties multiply their private integers together — without either party ever learning the other's input. This is the foundational multiplication gadget used in SPDZ, MP-SPDZ, and virtually every practical secure multiparty computation (MPC) framework in production today.

Here's what you'll learn:

1. Why multiplying secret-shared values is fundamentally harder than adding them
2. The exact algebra behind Beaver's multiplication protocol (the offline/online split)
3. A self-contained FiniteField class and a trusted-dealer simulation in Python
4. How to chain multiple multiplication gates into an arithmetic circuit
5. A pytest suite that validates correctness against plaintext results

Tech stack: Python 3.10+, no external MPC library. Everything runs in a single file you can audit line by line.

Here's the high-level interaction between the two parties:

  ┌─────────────┐   d = x - a (masked input)   ┌─────────────┐
  │   Party A   │ ─────────────────────────────▶│   Party B   │
  │  holds x0   │ ◀─────────────────────────────│  holds x1   │
  │  holds y0   │   e = y - b (masked input)    │  holds y1   │
  │             │                               │             │
  │  computes   │  (no raw inputs ever cross)   │  computes   │
  │  z0 locally │                               │  z1 locally │
  └─────────────┘                               └─────────────┘
        │                                               │
        └───────────── open z0 + z1 = x*y ─────────────┘

The trusted dealer hands each party their shares of a Beaver triple before any inputs are known. The online phase is then a single round of communication.

---

Background: Secret Sharing and Why Multiplication Is Hard

Additive Secret Sharing over a Finite Field (mod p)

In additive secret sharing, a secret x is split into two shares x0 and x1 such that x0 + x1 ≡ x (mod p). Neither share alone reveals anything about x — both are uniformly random in ℤ_p. Party 0 gets x0, Party 1 gets x1.

Addition is trivially free: if Party 0 holds (x0, y0) and Party 1 holds (x1, y1), they each add their shares locally — z0 = x0 + y0, z1 = x1 + y1 — and z0 + z1 = x + y. Zero rounds of communication.

Why Addition Is Free but Multiplication Leaks Information

Naive multiplication breaks this. If each party just multiplies their own shares — z0 = x0 * y0, z1 = x1 * y1 — then z0 + z1 = x0*y0 + x1*y1, which is not x*y. Expanding x*y = (x0+x1)(y0+y1) = x0*y0 + x0*y1 + x1*y0 + x1*y1 shows the cross terms x0*y1 + x1*y0 are missing.

You could try to compute those cross terms interactively, but that requires Party 0 to send x0 to Party 1 (or vice versa), immediately leaking the secret.

| Operation | Communication Rounds | Security Risk | |-----------|---------------------|---------------| | Addition | 0 | None — local computation | | Naive multiplication | 1 | Reveals one party's share directly | | Beaver triple multiplication | 1 | None — masked values reveal nothing | | Shamir-based multiplication | 2+ | Degree-doubling requires resharing |

The Role of a Trusted Dealer

Beaver's insight is to pre-compute correlated randomness — a triple (a, b, c) where c = a*b mod p — in an offline phase before inputs exist. This offline phase requires either a trusted dealer or an expensive cryptographic protocol (OT, VOLE). Once you have the triple, the online multiplication consumes only one round of communication and reveals nothing about x or y.

Shamir secret sharing offers a different approach (polynomial interpolation, threshold schemes) but additive shares are simpler to implement and sufficient for the two-party case we're building here.

---

Understanding Beaver Triples: The Core Concept

Definition: A Correlated Randomness Triple

A Beaver triple is three values (a, b, c) sampled uniformly at random in ℤ_p subject to the single constraint c = a * b mod p. The values are unknown to both parties — they only hold shares of them.

How the Triple Is Split into Shares

The dealer splits each element additively:

• Party 0 gets (a0, b0, c0)
• Party 1 gets (a1, b1, c1)

Such that a0 + a1 ≡ a, b0 + b1 ≡ b, c0 + c1 ≡ c (all mod p). Neither party can reconstruct a, b, or c individually.

The Offline Phase

The offline phase happens before inputs are known. The dealer generates as many triples as there are multiplication gates in the circuit. This phase can be batched, pipelined, and even done weeks in advance. In production systems (SPDZ, MASCOT, VOLE-based protocols), this phase uses oblivious transfer or vector OLE to remove the trusted dealer entirely.

The Online Phase: Evaluating One Multiplication Gate

Parties want to compute shares of z = x * y. They hold [x] = (x0, x1) and [y] = (y0, y1), plus a fresh triple ([a], [b], [c]).

The Beaver Multiplication Formula:

1. Each party i computes d_i = x_i - a_i and e_i = y_i - b_i
2. Parties exchange d_i and e_i, then each reconstructs d = d0 + d1 and e = e0 + e1
3. Party 0 sets: z0 = c0 + d*b0 + e*a0 + d*e
4. Party 1 sets: z1 = c1 + d*b1 + e*a1
5. Then z0 + z1 = c + d*b + e*a + d*e = (a+d)(b+e) = x*y ✓

Note that d = x - a and e = y - b are computationally indistinguishable from random in ℤ_p — they leak nothing about x or y individually because a and b are uniformly random masks.

---

Setting Up Your Python Environment

Prerequisites

You need Python 3.10+. No pip installs required for the core implementation. For tests you'll want pytest: pip install pytest. That's it.

Project Structure

beaver_mpc/
├── finite_field.py
├── beaver.py
├── circuit.py
└── tests/
    └── test_beaver.py

Choosing a Prime Modulus

We'll use the Mersenne prime 2^61 - 1 = 2305843009213693951. It's a 61-bit prime, large enough that secrets are computationally hidden, and Python's arbitrary precision integers handle it natively. Reduction mod a Mersenne prime can also be done efficiently with bit tricks, though we'll use the % operator for clarity.

# finite_field.py
import random

# 2^61 - 1, a Mersenne prime
DEFAULT_PRIME = (1 << 61) - 1


class FieldElement:
    """
    An element of Z_p with mod-p arithmetic.
    """
    def __init__(self, value: int, prime: int = DEFAULT_PRIME):
        self.prime = prime
        self.value = int(value) % prime

    def __add__(self, other: "FieldElement") -> "FieldElement":
        assert self.prime == other.prime
        return FieldElement((self.value + other.value) % self.prime, self.prime)

    def __sub__(self, other: "FieldElement") -> "FieldElement":
        assert self.prime == other.prime
        return FieldElement((self.value - other.value) % self.prime, self.prime)

    def __mul__(self, other: "FieldElement") -> "FieldElement":
        assert self.prime == other.prime
        return FieldElement((self.value * other.value) % self.prime, self.prime)

    def __eq__(self, other: object) -> bool:
        if isinstance(other, FieldElement):
            return self.value == other.value and self.prime == other.prime
        return NotImplemented

    def __repr__(self) -> str:
        return f"FieldElement({self.value}, p={self.prime})"

    @classmethod
    def random(cls, prime: int = DEFAULT_PRIME) -> "FieldElement":
        return cls(random.randrange(0, prime), prime)

    @classmethod
    def from_int(cls, v: int, prime: int = DEFAULT_PRIME) -> "FieldElement":
        return cls(v % prime, prime)

FieldElement.__add__ and __mul__ both reduce mod p immediately, so there's never an overflow concern. random.randrange(0, prime) gives a uniform sample — note that Python's random module is not cryptographically secure; for production use secrets.randbelow(prime) instead.

---

Step 1 — Offline Phase: Generating and Distributing Beaver Triples

Goal: simulate a trusted dealer that produces a single Beaver triple split into additive shares for two parties.

# beaver.py  (top portion — offline phase)
from finite_field import FieldElement, DEFAULT_PRIME
from typing import Tuple

TripleShare = Tuple[FieldElement, FieldElement, FieldElement]  # (a_i, b_i, c_i)


def generate_beaver_triple(
    prime: int = DEFAULT_PRIME,
) -> Tuple[TripleShare, TripleShare]:
    """
    Trusted dealer: samples a, b uniformly in Z_p, computes c = a*b,
    then additively splits each into two shares for Party 0 and Party 1.
    Returns ((a0, b0, c0), (a1, b1, c1)).
    """
    # Sample the triple
    a = FieldElement.random(prime)
    b = FieldElement.random(prime)
    c = a * b  # c = a*b mod p

    # Additively split a -> (a0, a1) such that a0 + a1 = a
    a0 = FieldElement.random(prime)
    a1 = a - a0

    # Split b
    b0 = FieldElement.random(prime)
    b1 = b - b0

    # Split c
    c0 = FieldElement.random(prime)
    c1 = c - c0

    # --- Correctness assertions (remove in production hot paths) ---
    assert (a0 + a1) == a, "Share split for a is incorrect"
    assert (b0 + b1) == b, "Share split for b is incorrect"
    assert (c0 + c1) == c, "Share split for c is incorrect"
    assert (a * b) == c,   "Triple invariant a*b = c violated"

    return (a0, b0, c0), (a1, b1, c1)

Each call to generate_beaver_triple consumes one multiplication gate. The shares are distributed: Party 0 gets (a0, b0, c0), Party 1 gets (a1, b1, c1). Neither share reveals a, b, or c individually because both a0 and a1 are uniform — together they're a one-time pad over ℤ_p.

---

Step 2 — Online Phase: Performing Multiplication with Secret Inputs

Goal: implement beaver_multiply, the function each party runs locally during the online phase, taking their input shares and triple shares and returning their output share.

# beaver.py  (continued — online phase)

def beaver_multiply(
    x_share: FieldElement,
    y_share: FieldElement,
    triple_share: TripleShare,
    d: FieldElement,  # reconstructed d = x - a (public after broadcast)
    e: FieldElement,  # reconstructed e = y - b (public after broadcast)
    party_id: int,    # 0 or 1
) -> FieldElement:
    """
    Online phase: each party computes their share of z = x * y.
    Parties must exchange (d_i, e_i) and reconstruct d, e before calling this.
    """
    a_share, b_share, c_share = triple_share

    # [z] = [c] + d*[b] + e*[a] + (d*e if party_id == 0 else 0)
    z_share = c_share
    z_share = z_share + FieldElement.from_int(d.value, d.prime) * b_share
    z_share = z_share + FieldElement.from_int(e.value, e.prime) * a_share

    # The d*e term is a public scalar — only ONE party adds it (avoid double-counting)
    if party_id == 0:
        z_share = z_share + d * e

    return z_share


def simulate_two_party_multiply(
    x: int,
    y: int,
    prime: int = DEFAULT_PRIME,
) -> int:
    """
    Full two-party simulation of z = x * y using a Beaver triple.
    Returns the plaintext product for verification.
    """
    # --- Secret-share the inputs ---
    x0 = FieldElement.random(prime)
    x1 = FieldElement.from_int(x, prime) - x0

    y0 = FieldElement.random(prime)
    y1 = FieldElement.from_int(y, prime) - y0

    # --- Offline phase: get a fresh triple ---
    (a0, b0, c0), (a1, b1, c1) = generate_beaver_triple(prime)

    # --- Online phase: mask inputs ---
    d0 = x0 - a0  # Party 0 computes
    e0 = y0 - b0

    d1 = x1 - a1  # Party 1 computes
    e1 = y1 - b1

    # --- Broadcast: reconstruct d and e (these are safe to reveal) ---
    d = d0 + d1
    e = e0 + e1

    # --- Each party computes their output share ---
    z0 = beaver_multiply(x0, y0, (a0, b0, c0), d, e, party_id=0)
    z1 = beaver_multiply(x1, y1, (a1, b1, c1), d, e, party_id=1)

    # --- Open the result ---
    result = (z0 + z1).value
    return result


# Quick sanity check
if __name__ == "__main__":
    for x_val, y_val in [(3, 7), (100, 200), (0, 999), (DEFAULT_PRIME - 1, 2)]:
        result = simulate_two_party_multiply(x_val, y_val)
        expected = (x_val * y_val) % DEFAULT_PRIME
        status = "✓" if result == expected else "✗"
        print(f"{status} {x_val} * {y_val} = {result} (expected {expected})")

Key points about beaver_multiply:

• d and e are reconstructed publicly — both parties know them. They're safe because a and b are fresh random masks.
• The d*e scalar correction is added by exactly one party (Party 0). If both added it, the product would be off by d*e.
• x_share and y_share are passed in but not used in the formula — they're implicitly encoded in the shares of [c], [a], [b] combined with d and e.

---

Step 3 — Chaining Multiple Multiplications in a Circuit

Goal: evaluate a two-gate arithmetic circuit z = (x*y)*w by pre-generating a batch of Beaver triples and consuming them sequentially.

Each multiplication gate in your circuit needs exactly one fresh triple. Pre-generate them all at circuit compile time (the offline phase), then consume them one by one during the online phase.

# circuit.py
from collections import deque
from finite_field import FieldElement, DEFAULT_PRIME
from beaver import generate_beaver_triple, beaver_multiply, TripleShare
from typing import Deque, Tuple


def build_triple_queue(n: int, prime: int = DEFAULT_PRIME) -> Deque[Tuple[TripleShare, TripleShare]]:
    """Pre-generate n Beaver triples for a circuit with n multiplication gates."""
    return deque(generate_beaver_triple(prime) for _ in range(n))


def mpc_circuit_x_times_y_times_w(
    x: int, y: int, w: int,
    prime: int = DEFAULT_PRIME,
) -> int:
    """
    Evaluates (x * y) * w using two Beaver triples.
    Checklist:
      [x] One triple per multiplication gate
      [x] Output shares of gate 1 become input shares of gate 2
      [x] No secret value is ever reconstructed mid-circuit
    """
    # --- Offline phase: pre-generate 2 triples ---
    triple_queue = build_triple_queue(2, prime)

    # --- Secret-share all inputs ---
    def share(v):
        s0 = FieldElement.random(prime)
        s1 = FieldElement.from_int(v, prime) - s0
        return s0, s1

    x0, x1 = share(x)
    y0, y1 = share(y)
    w0, w1 = share(w)

    # --- Gate 1: compute [t] = [x] * [y] ---
    (a0, b0, c0), (a1, b1, c1) = triple_queue.popleft()

    d = (x0 - a0) + (x1 - a1)  # reconstruct d = x - a
    e = (y0 - b0) + (y1 - b1)  # reconstruct e = y - b

    t0 = beaver_multiply(x0, y0, (a0, b0, c0), d, e, party_id=0)
    t1 = beaver_multiply(x1, y1, (a1, b1, c1), d, e, party_id=1)
    # Now t0 + t1 = x*y, but neither party knows this value.

    # --- Gate 2: compute [z] = [t] * [w] ---
    (a0, b0, c0), (a1, b1, c1) = triple_queue.popleft()

    d2 = (t0 - a0) + (t1 - a1)  # masked intermediate, still safe
    e2 = (w0 - b0) + (w1 - b1)

    z0 = beaver_multiply(t0, w0, (a0, b0, c0), d2, e2, party_id=0)
    z1 = beaver_multiply(t1, w1, (a1, b1, c1), d2, e2, party_id=1)

    # --- Open final result only ---
    return (z0 + z1).value


if __name__ == "__main__":
    test_cases = [(2, 3, 4), (5, 6, 7), (0, 100, 200)]
    for x_v, y_v, w_v in test_cases:
        result = mpc_circuit_x_times_y_times_w(x_v, y_v, w_v)
        expected = (x_v * y_v * w_v) % DEFAULT_PRIME
        print(f"({x_v}*{y_v})*{w_v} = {result}, expected {expected}, {'✓' if result == expected else '✗'}")

The critical pattern here: t0, t1 are the output shares of Gate 1 and become the input shares of Gate 2 directly. You never reconstruct the intermediate value x*y mid-circuit. The security of the whole computation rests on this: partial results stay in secret-shared form until the very end.

---

Testing and Validating Your Implementation

Run the suite with pytest tests/ -v. Expected output: all tests pass in under 2 seconds.

# tests/test_beaver.py
import random
import pytest
from finite_field import FieldElement, DEFAULT_PRIME
from beaver import generate_beaver_triple, simulate_two_party_multiply
from circuit import mpc_circuit_x_times_y_times_w

PRIME = DEFAULT_PRIME


# ── Test 1: Triple invariant ─────────────────────────────────────────────────

def test_triple_invariant():
    """Verify c = a*b mod p for 50 independently generated triples."""
    for _ in range(50):
        (a0, b0, c0), (a1, b1, c1) = generate_beaver_triple(PRIME)
        a = a0 + a1
        b = b0 + b1
        c = c0 + c1
        assert a * b == c, f"Invariant violated: {a.value} * {b.value} != {c.value} mod {PRIME}"


# ── Test 2: MPC result matches plaintext ─────────────────────────────────────

@pytest.mark.parametrize("_", range(100))
def test_mpc_multiply_matches_plaintext(_):
    """Parametrized over 100 random pairs: MPC result must equal x*y mod p."""
    x = random.randrange(0, PRIME)
    y = random.randrange(0, PRIME)
    result = simulate_two_party_multiply(x, y, PRIME)
    expected = (x * y) % PRIME
    assert result == expected, (
        f"MPC multiplication failed: {x} * {y} = {result}, expected {expected}"
    )


# ── Test 3: Edge cases ───────────────────────────────────────────────────────

@pytest.mark.parametrize("x,y", [
    (0, 0),
    (0, 12345),
    (12345, 0),
    (PRIME - 1, 1),
    (PRIME - 1, PRIME - 1),
    (PRIME - 1, 2),
    (1, 1),
    (2, PRIME // 2),
])
def test_edge_cases(x, y):
    """Boundary values: zero inputs, p-1, wrap-around behaviour."""
    result = simulate_two_party_multiply(x, y, PRIME)
    expected = (x * y) % PRIME
    assert result == expected, (
        f"Edge case failed: {x} * {y} = {result}, expected {expected}"
    )


# ── Test 4: Multi-gate circuit ───────────────────────────────────────────────

@pytest.mark.parametrize("x,y,w", [
    (2, 3, 4),
    (0, 5, 9),
    (PRIME - 1, PRIME - 1, PRIME - 1),
    (random.randrange(1, PRIME), random.randrange(1, PRIME), random.randrange(1, PRIME)),
])
def test_circuit_x_times_y_times_w(x, y, w):
    """Two-gate circuit (x*y)*w must match plaintext."""
    result = mpc_circuit_x_times_y_times_w(x, y, w, PRIME)
    expected = (x * y * w) % PRIME
    assert result == expected

Expected terminal output:

$ pytest tests/test_beaver.py -v

tests/test_beaver.py::test_triple_invariant PASSED
tests/test_beaver.py::test_mpc_multiply_matches_plaintext[0] PASSED
...
tests/test_beaver.py::test_mpc_multiply_matches_plaintext[99] PASSED
tests/test_beaver.py::test_edge_cases[0-0] PASSED
tests/test_beaver.py::test_edge_cases[2305843009213693950-1] PASSED
...
tests/test_beaver.py::test_circuit_x_times_y_times_w[2-3-4] PASSED

114 passed in 1.42s

If test_triple_invariant fails, your FieldElement.__sub__ is likely not reducing mod p correctly — check that subtraction wraps: (self.value - other.value) % self.prime. If test_edge_cases fails on (PRIME-1, PRIME-1), verify Python's % operator returns a non-negative result for negative integers (it does, unlike C).

---

Going Further: Real-World MPC Frameworks and Next Steps

Limitations of the Trusted Dealer Model

Our dealer is a single point of trust and failure. In a real deployment you remove it using:

• Oblivious Transfer (OT) extension — the MASCOT protocol uses OT to generate authenticated Beaver triples with malicious security. Communication cost is roughly 10–100KB per triple depending on the OT implementation.
• Vector Oblivious Linear Evaluation (VOLE) — Silent OT and VOLE-based protocols (SilentOT, Ferret) generate millions of triples with sub-millisecond amortized cost. This is what modern frameworks like MP-SPDZ use by default.

Authenticated Triples for Malicious Security

The protocol above provides semi-honest (honest-but-curious) security. A malicious party can substitute wrong shares and corrupt the output without detection. The SPDZ protocol (Damgård et al., 2012) adds a global MAC key: each value [x] is augmented with an authentication tag [α*x] where α is a global secret. Any tampering causes MAC verification to fail with overwhelming probability. This is what the "SPDZ" in MP-SPDZ refers to.

Production Frameworks

| Feature | Trusted Dealer | OT-based (MASCOT) | VOLE-based (SilentOT) | |---------|---------------|--------------------|-----------------------| | Security model | Semi-honest | Malicious | Malicious | | Triple gen cost | O(1) | ~10ms per triple | ~0.01ms amortized | | Setup complexity | Trivial | Medium (OT base) | High (LPN assumption) | | Suited for | Prototyping, simulation | Production 2PC | High-throughput MPC |

MP-SPDZ (github.com/data61/MP-SPDZ) is the most complete open-source MPC framework and compiles high-level circuit descriptions down to Beaver triple-based protocols automatically. SCALE-MAMBA is its predecessor with a different runtime model. The Stoffel MPC framework (stoffelmpc.com) aims to make MPC accessible at the application layer.

Concrete Next Steps

1. Replace the dealer with OT: implement a simple 1-out-of-2 OT using RSA or elliptic curves, then use it to generate correlated randomness. The Simplest OT paper (Chou & Orlandi) is the best starting point.
2. Add MAC authentication: extend FieldElement with a tag field and implement SPDZ-style authentication to harden against malicious parties.
3. Benchmark your triple throughput: how many triples/sec can your Python implementation generate? Swap in gmpy2 for fast modular arithmetic and measure the speedup.
4. Try MP-SPDZ: install it, write a .mpc file that computes x * y, and trace which C++ functions correspond to the Python code you just wrote.
5. Read the original paper: Beaver, D. (1992). "Efficient Multiparty Protocols Using Circuit Randomization." CRYPTO '91. It's 12 pages and the algebra maps directly to the code above.