"""Bit commitment, coin flipping by telephone, and commitment from oblivious transfer.

A companion to "Is a qubit better than a bit at everything?" on highentropy001.com.
Python 3.8+, standard library only. Run it: python bit-commitment.py
"""

import hashlib
import secrets


# 1. A hash-based commitment: the sealed envelope.
#    Hiding: the digest reveals nothing useful about the bit, because the random nonce is secret.
#    Binding: opening to the other bit would need a second input with the same SHA-256 digest.
#    Both rest on assumptions about SHA-256, not on physics.

def commit(bit):
    nonce = secrets.token_bytes(32)
    digest = hashlib.sha256(nonce + bytes([bit])).hexdigest()
    return digest, nonce  # send the digest now, keep the nonce to open later


def verify(digest, bit, nonce):
    return hashlib.sha256(nonce + bytes([bit])).hexdigest() == digest


# 2. Blum's coin flipping by telephone.
#    Alice commits to a, Bob announces b, Alice opens, and the coin is a XOR b.

def coin_flip():
    a = secrets.randbits(1)
    digest, nonce = commit(a)        # Alice -> Bob: the envelope
    b = secrets.randbits(1)          # Bob -> Alice: his bit, chosen without seeing a
    assert verify(digest, a, nonce)  # Alice -> Bob: she opens, Bob checks
    return a ^ b


# 3. Commitment built from oblivious transfer.
#    In 1-out-of-2 OT the sender offers two messages; the receiver learns one of them,
#    and the sender never learns which. Here an ideal OT box stands in for the protocol.

def ideal_ot(m0, m1, choice):
    return m1 if choice else m0


def commit_from_ot(bit, n=20):
    """Alice commits to bit by acting as the OT sender n times."""
    pads = [secrets.randbits(1) for _ in range(n)]
    choices = [secrets.randbits(1) for _ in range(n)]  # Bob's secret choices
    seen = [ideal_ot(r, r ^ bit, c) for r, c in zip(pads, choices)]
    # Bob holds one share of every pair: alone, each looks like a fair coin, so the bit is hidden.
    return pads, (choices, seen)


def open_from_ot(bob_view, bit, pads):
    """Alice reveals bit and her pads; Bob checks them against the shares he received."""
    choices, seen = bob_view
    return all(s == (r ^ (bit & c)) for r, c, s in zip(pads, choices, seen))


def cheat(bob_view, bit, pads):
    """Alice tries to open to the other bit. She must flip the pads where Bob chose 1,
    but she doesn't know where that was, so she can only guess."""
    guesses = [secrets.randbits(1) for _ in pads]
    forged = [r ^ g for r, g in zip(pads, guesses)]
    return open_from_ot(bob_view, 1 - bit, forged)


if __name__ == "__main__":
    digest, nonce = commit(1)
    print("honest opening accepted:", verify(digest, 1, nonce))
    print("opening to the other bit accepted:", verify(digest, 0, nonce))

    flips = [coin_flip() for _ in range(10_000)]
    print(f"coin flips: {sum(flips)} heads out of {len(flips)}")

    pads, view = commit_from_ot(1)
    print("OT commitment, honest opening accepted:", open_from_ot(view, 1, pads))
    for n in (1, 2, 4, 8):
        trials = 20_000
        wins = sum(cheat(v, 1, p) for p, v in (commit_from_ot(1, n) for _ in range(trials)))
        print(f"n = {n}: cheating succeeded {wins / trials:.4f} of the time (theory {2 ** -n:.4f})")