Maxwell’s Merkle-sum-tree proof of reserves (2013)

An exchange can show that it holds coins by moving them, but holding coins proves nothing unless one also knows what it owes. Gregory Maxwell proposed in 2013 that the exchange publish the root of a Merkle tree over its customers’ balances in which every node also carries the sum below it,

\[\text{node} = \big(H(s_L \,\|\, s_R \,\|\, h_L \,\|\, h_R),\; s_L + s_R\big),\]

so that the root commits to the total liabilities. Each customer checks a short proof that its own balance is counted, and the public checks that the reserves cover the root’s total. Leaving out customers lowers the total, but each one left out may notice: if every customer checks independently with probability \(f\), cheating \(k\) of them goes unnoticed with probability \((1 - f)^k\).

import matplotlib.pyplot as plt

import blockchainkit as bk

Publish, prove, verify

owed = {f"customer{i:03}": 10 + 37 * i % 500 for i in range(200)}
tree = bk.fraud.liability_tree(owed, salt=b"2013-snapshot")
print(tree, "root", tree.root.hex()[:16])
index = tree.index("customer042")
proof = tree.proof(index)
print("customer042's proof has", len(proof.steps), "siblings, each with its sum")
assert bk.fraud.verify_sum_proof(
    "customer042", owed["customer042"], proof, tree.root, tree.total, salt=tree.salt
)
assert tree.total == sum(owed.values())

MerkleSumTree(leaves=200, total=52300) root 1466a1fa1acba543
customer042's proof has 8 siblings, each with its sum

Hiding liabilities

The exchange leaves out its ten largest customers, hiding a tenth of what it owes. Only those ten can notice.

largest = sorted(owed, key=owed.get)[-10:]
cheat = bk.fraud.liability_tree(
    {c: v for c, v in owed.items() if c not in largest}, salt=b"2013-snapshot"
)
print(f"declared {cheat.total:,} instead of {tree.total:,}")
result = bk.fraud.audit(cheat, owed, checking=0.1, seed=1)
print("customers who checked:", len(result.checked), "complaints:", result.complaints)

fractions = [0.01, 0.02, 0.05, 0.1, 0.2, 0.3, 0.5]
caught = [
    sum(bk.fraud.audit(cheat, owed, checking=f, seed=s).caught for s in range(200)) / 200
    for f in fractions
]
predicted = [bk.fraud.detection_probability(10, f) for f in fractions]
assert all(abs(c - p) < 0.12 for c, p in zip(caught, predicted, strict=True))

fig, ax = plt.subplots(figsize=(7, 4))
ax.plot(fractions, caught, "o", color="#dc2626", label="simulated audits")
ax.plot(fractions, predicted, color="black", label="1 - (1 - f)^10")
ax.set(xlabel="fraction f of customers who check", ylabel="chance the cheat is caught")
ax.set_title("Ten customers left out")
ax.legend()
fig.tight_layout()

plt.show()

declared 47,288 instead of 52,300
customers who checked: 23 complaints: ('customer013',)

Exercise

Instead of leaving customers out, the exchange adds a fake account with a balance of minus 5,000. Which customers can notice, and why does verify_sum_proof() reject negative sibling sums? A worked solution is in Exercises: fraud.