Choosing a Secure Exchange

Go: open a terminal in a folder you can write to, e.g. cd ~/Desktop (Windows: cd %USERPROFILE%\Desktop).

Do: save this as merkle.py. It prints nothing by itself — it is the toolbox for the whole exercise.

import hashlib

def h(x: bytes) -> str:
    return hashlib.sha256(x).hexdigest()

def leaf(user, balance):
    return h(f"{user}:{balance}".encode())

def build(leaves):
    """Return every level of the tree, bottom first."""
    levels = [leaves]
    while len(levels[-1]) > 1:
        row = levels[-1]
        if len(row) % 2:
            row = row + [row[-1]]
        levels.append([h((row[i] + row[i + 1]).encode())
                       for i in range(0, len(row), 2)])
    return levels

def proof_for(levels, index):
    """The sibling hashes needed to climb from one leaf to the root."""
    path = []
    for level in levels[:-1]:
        row = level + ([level[-1]] if len(level) % 2 else [])
        sibling = index ^ 1
        path.append((("right" if index % 2 == 0 else "left"), row[sibling]))
        index //= 2
    return path

def replay(leaf_hash, path):
    node = leaf_hash
    for side, sibling in path:
        node = h((node + sibling).encode()) if side == "right" else h((sibling + node).encode())
    return node

Now save this as publish.py and run python3 publish.py:

from merkle import leaf, build

accounts = [("alice", 12), ("bob", 3), ("carol", 40), ("dan", 7),
            ("erin", 25), ("frank", 1), ("grace", 60), ("you", 15)]

levels = build([leaf(u, b) for u, b in accounts])
print("customers in the tree :", len(accounts))
print("total customer coins  :", sum(b for _, b in accounts))
print("published root        :", levels[-1][0])

You should see: eight customers reduced to a single 64-character number:

customers in the tree : 8
total customer coins  : 163
published root        : f105808937c5aa1d93c49ab615c9e82ebc730654bdb8c71ed6bcb9cb5a3c9acd

That root is what an exchange puts on its website. It reveals nobody’s balance, and it cannot be changed without changing the number — which is the entire idea.

If not: ModuleNotFoundError: No module named 'merkle' means the two files are not in the same folder. A different root means a balance or a name was mistyped; every character feeds the hash.

Go: same folder. This is the part a real exchange gives you in your account settings, usually behind a button called “Merkle proof”.

Do: save this as myproof.py and run it.

from merkle import leaf, build, proof_for, replay

accounts = [("alice", 12), ("bob", 3), ("carol", 40), ("dan", 7),
            ("erin", 25), ("frank", 1), ("grace", 60), ("you", 15)]
leaves = [leaf(u, b) for u, b in accounts]
levels = build(leaves)
root = levels[-1][0]

path = proof_for(levels, 7)                 # "you" are account number 7
print("your leaf     :", leaves[7][:16], "...")
for side, sib in path:
    print(f"  sibling on the {side:5s}: {sib[:16]}...")
print("replayed root :", replay(leaves[7], path)[:16], "...")
print("matches the published root:", replay(leaves[7], path) == root)

You should see: three sibling hashes carrying you up to the same root:

your leaf     : b15b14a576c0fc2f ...
  sibling on the left : ef3a84e4dacf2aef...
  sibling on the left : c2c942c1b0ea17c6...
  sibling on the left : f93547ce69b99b82...
replayed root : f105808937c5aa1d ...
matches the published root: True

Three hashes proved your balance is in a set of eight; for eight million customers it would take twenty-three. You learned nothing about anyone else’s money, and the exchange proved something it cannot take back.

If not: False on the last line means the index and the leaf disagree — both must be 7. If the sibling sides read “right”, you are proving a different account; that is fine, but the root must still match.

Go: same folder. Now make the exchange dishonest and see whether the proof notices.

Do: save this as shaved.py and run it. The exchange builds its tree recording you as holding 5 coins while your account page still says 15.

from merkle import leaf, build, proof_for, replay

honest = [("alice", 12), ("bob", 3), ("carol", 40), ("dan", 7),
          ("erin", 25), ("frank", 1), ("grace", 60), ("you", 15)]
shaved = [(u, 5 if u == "you" else b) for u, b in honest]

for label, accounts in (("honest books", honest), ("your balance shaved", shaved)):
    leaves = [leaf(u, b) for u, b in accounts]
    levels = build(leaves)
    mine = leaf("you", 15)                   # what YOUR statement says
    ok = replay(mine, proof_for(levels, 7)) == levels[-1][0]
    print(f"{label:20s} root {levels[-1][0][:16]}...  your proof verifies: {ok}")

You should see: the lie failing your check:

honest books         root f105808937c5aa1d...  your proof verifies: True
your balance shaved  root a659834746a7f592...  your proof verifies: False

This is the one thing proof of reserves genuinely gives you, and it is worth having: if you check your proof after every publication and it always verifies, the exchange cannot be understating what it owes you. The catch is that you have to check — a proof nobody verifies constrains nobody.

If not: if both lines say True, the mine line is being rebuilt from the shaved list instead of your own statement — it must stay leaf("you", 15).

Go: same folder. Your proof verified. Does that mean the tree is complete?

Do: save this as omitted.py and run it. The exchange leaves its largest customer out of the tree entirely.

from merkle import leaf, build

full = [("alice", 12), ("bob", 3), ("carol", 40), ("dan", 7),
        ("erin", 25), ("frank", 1), ("grace", 60), ("you", 15)]
hidden = [a for a in full if a[0] != "grace"]      # a big account quietly left out

for label, accounts in (("all 8 customers", full), ("grace omitted", hidden)):
    levels = build([leaf(u, b) for u, b in accounts])
    print(f"{label:16s} liabilities {sum(b for _, b in accounts):>4}   "
          f"root {levels[-1][0][:16]}...")

You should see: the exchange’s stated obligations dropping by more than a third:

all 8 customers  liabilities  163   root f105808937c5aa1d...
grace omitted    liabilities  103   root 5adcb260557f7342...

Grace’s proof would now fail — but Grace has to look. Everybody else’s proof still verifies perfectly against a tree that understates what the exchange owes by 60 coins. A Merkle proof shows that your account is included; it cannot show that everyone’s is. That gap is why these publications are supposed to be checked by an auditor who can compare the tree against the exchange’s internal ledger.

If not: if both roots are identical, the filter did not remove anything — check the name is spelled "grace" exactly.

Go: same folder. The tree counts what is owed. The wallets show what is held. Compare them.

Do: save this as solvency.py and run it.

liabilities = 163          # the total the tree commits the exchange to
on_chain    = 171          # coins visibly held in the exchange's published wallets

print(f"customer coins owed (from the tree): {liabilities}")
print(f"coins in the published wallets     : {on_chain}")
print(f"reserve ratio                      : {on_chain / liabilities:.1%}")
print()
borrowed = 60
print("but if 60 of those coins were borrowed for the day of the snapshot:")
print(f"  really owned                     : {on_chain - borrowed}")
print(f"  real reserve ratio               : {(on_chain - borrowed) / liabilities:.1%}")

You should see: a healthy-looking exchange turning insolvent on one assumption:

customer coins owed (from the tree): 163
coins in the published wallets     : 171
reserve ratio                      : 104.9%

but if 60 of those coins were borrowed for the day of the snapshot:
  really owned                     : 111
  real reserve ratio               : 68.1%

A snapshot proves coins were in a wallet at one instant, not that they belong to the exchange, and not that they are still there tomorrow. This is not a theoretical worry: borrowing assets to pass a point-in-time check has happened, which is why a proof of reserves without a proof of liabilities and an auditor’s attestation is a marketing page, not an audit.

So what do you actually do? Treat proof of reserves as one input among several: whether your own proof verifies each time, whether an auditor is named, whether withdrawals are working today for other people, and above all how much you leave there. The only reserve you control is the coins you moved off the exchange.

If not: ValueError: Invalid format specifier means the :.1% was mistyped — it is a colon, a dot, a one and a percent sign.