Pick a depth. Each prompt opens in your AI pre-loaded with the lesson. Click a row to preview the prompt.
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.
(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.# 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