Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
This is the problem that started the field. Two parties want to know who is richer without revealing net worth. It is also the canonical pedagogical test for any new MPC learner: if you can explain the protocol and trace a round, you understand 2PC's shape. Every richer protocol — garbled circuits for SHA-256, threshold ECDSA, private ML inference — is a harder instance of the same pattern: express the function as a circuit, evaluate it via OT calls.
A working greater-than protocol using bit-decomposition + a series of 1-of-2 OTs. For 32-bit inputs, this is 32 OTs of tiny messages. In later modules you'll see how garbled circuits evaluate the same comparison with a single round-trip instead of 32.
# Yao's Millionaires — the *circuit* a real OT-based 2PC would evaluate gate-by-gate.
# We compute the comparison logic in plaintext so you can read off exactly which Boolean
# operations are paid (each AND becomes one OT in GMW, or one garbled row in Yao+free-XOR).
#
# Recurrence (MSB -> LSB):
# gt[k] = (a_k AND NOT b_k) XOR ((a_k XNOR b_k) AND gt[k-1])
# = "strictly greater at this bit" XOR "equal so far AND running gt"
# Initial: gt[-1] = 0 (no prefix is "greater" yet).
# The two terms are mutually exclusive so OR/XOR are interchangeable here.
def millionaires_circuit(a: int, b: int, bits: int = 32) -> bool:
gt = 0 # accumulator for "a > b on the prefix scanned so far"
for k in range(bits - 1, -1, -1):
a_k = (a >> k) & 1
b_k = (b >> k) & 1
# In real GMW: each AND below = 1 preprocessed Beaver triple + 1 OT round.
strictly_gt = a_k & (1 ^ b_k) # 1 AND (paid)
equal = 1 ^ (a_k ^ b_k) # XOR (free)
propagate = equal & gt # 1 AND (paid; on critical path)
gt = strictly_gt ^ propagate # XOR (free)
return gt == 1
# Sanity: must agree with Python's > on every boundary case.
for a, b, expected in [
(1_000_000, 5_000_000, False),
(5_000_000, 1_000_000, True),
(42, 42, False),
(0xFFFF_FFFF, 0, True),
(0x8000_0000, 0x7FFF_FFFF, True), # sign-bit boundary; unsigned semantics
]:
got = millionaires_circuit(a, b)
assert got == expected, (a, b, got, expected)
print(f"{a:>10} > {b:<10} -> {got}")
# Cost ledger you'll re-derive across the course:
# ANDs along the dependency chain: 32 (one per bit) -> 32 sequential OT rounds in GMW.
# Yao+free-XOR+half-gates: 32 garbled rows * 2 ciphertexts/row = 1024 bytes; 1 round.
# Plaintext '>' on a CPU: ~1 ns. MPC overhead is roughly 10^7. Internalize that.python3 main.py(a_i > b_i) OR (a_i == b_i AND prefix_greater). Trace what each party's OT input/output is for that gate.Compiler.types.sint.greater_than implementation — it doesn't do bitwise OT. Instead it uses masked-random-bit tricks over a shared arithmetic representation. Read the ~40 lines and note how the trade-off shifts when you have arithmetic sharing instead of boolean.Use these three in order. Each builds on the one before.
Explain Yao's Millionaires problem in one paragraph, then explain in one more paragraph how it reduces to a sequence of 1-of-2 oblivious transfers. Don't use the word 'circuit' yet — build intuition bit-by-bit.
Walk me through the greater-than circuit gate by gate. For each gate, what does Alice contribute, what does Bob contribute, which party is the OT sender, which is the OT receiver, and what does each learn after the gate? End with the final output gate.
Real production MPC does not evaluate a 32-bit comparison bit-by-bit with 32 OT rounds. Explain the three main alternatives — garbled circuits (constant rounds), arithmetic-share comparison via masked randomness, and GMW with Beaver triples. For each, what's the bandwidth, round count, and what assumption on corruption threshold drops the cost?