#!/usr/bin/env python3
"""The Genesis Miner draw: 20 winners of 10 ZMR each, from the frozen Genesis
Miners list, seeded by a Bitcoin block hash nobody knew when the list was frozen.

Anyone can rerun it and get the same winners. Python 3.8+, standard library only.

    scripts/genesis-draw.py genesis.json <bitcoin block hash>
    scripts/genesis-draw.py --test

genesis.json is the frozen copy of https://pool.zecnero.org/genesis.json whose
SHA-256 the Mainnet date announcement publishes. The block hash is the one
block explorers show for the Bitcoin height that announcement names (64 hex
digits, starting with zeros).

The algorithm, as https://zecnero.org/rewards states it:

1. Eligible list: the "miners" entries of the frozen file, sorted by "height"
   (ascending, as a number), then by "address" (the short address, compared
   by Unicode code point). Entries that tie on both keep their order in the file.
2. Seed: SHA-256 of the 32 bytes of the block hash (hex-decoded, in the order
   explorers display it) followed by the 20 ASCII bytes "zecnero-genesis-draw".
3. Random numbers: the i-th number (i = 0, 1, 2, ...) is the first 8 bytes, read
   as a big-endian unsigned integer, of SHA-256(seed || i), with i as 8 bytes
   big-endian.
4. A number below n: take the next random number r. If r >= 2^64 - (2^64 mod n),
   discard it and take the next one. Otherwise the result is r mod n.
5. Shuffle: Fisher-Yates from the end. For i = N-1 down to 1, pick j, a number
   below i+1, and swap entries i and j.
6. Winners: the first 20 entries of the shuffled list, in that order (all of
   them if there are 20 or fewer).
"""

import argparse
import hashlib
import json
import os
import sys

DOMAIN = b"zecnero-genesis-draw"
WINNERS = 20
VECTOR = os.path.join(os.path.dirname(os.path.abspath(__file__)), "genesis-draw-vector.json")


def eligible(document):
    """The eligible list: the frozen file's entries, sorted by height then short address."""
    miners = document["miners"]
    for entry in miners:
        if not isinstance(entry.get("height"), int) or not isinstance(entry.get("address"), str):
            raise ValueError(f"entry without an integer height and a string address: {entry!r}")
    return sorted(miners, key=lambda e: (e["height"], e["address"]))


def seed_from(block_hash):
    """SHA-256(block hash bytes || "zecnero-genesis-draw")."""
    block_hash = block_hash.strip().lower()
    if len(block_hash) != 64 or any(c not in "0123456789abcdef" for c in block_hash):
        raise ValueError("the block hash is 64 hex digits")
    return hashlib.sha256(bytes.fromhex(block_hash) + DOMAIN).digest()


class Stream:
    """SHA-256 in counter mode: number i is the first 8 bytes of SHA-256(seed || i)."""

    def __init__(self, seed):
        self.seed = seed
        self.counter = 0

    def next64(self):
        block = hashlib.sha256(self.seed + self.counter.to_bytes(8, "big")).digest()
        self.counter += 1
        return int.from_bytes(block[:8], "big")

    def below(self, n):
        """A uniform integer in [0, n), by rejection."""
        limit = 2**64 - (2**64 % n)
        while True:
            r = self.next64()
            if r < limit:
                return r % n


def draw(document, block_hash, count=WINNERS):
    """Returns (seed, winners)."""
    entries = eligible(document)
    seed = seed_from(block_hash)
    stream = Stream(seed)
    for i in range(len(entries) - 1, 0, -1):
        j = stream.below(i + 1)
        entries[i], entries[j] = entries[j], entries[i]
    return seed, entries[:count]


def run(path, block_hash):
    with open(path, "rb") as f:
        raw = f.read()
    document = json.loads(raw.decode("utf-8"))
    seed, winners = draw(document, block_hash)
    print(f"file      {path}")
    print(f"sha256    {hashlib.sha256(raw).hexdigest()}")
    print(f"eligible  {len(document['miners'])}")
    print(f"block     {block_hash.strip().lower()}")
    print(f"seed      {seed.hex()}")
    print()
    for place, entry in enumerate(winners, 1):
        print(f"{place:>2}  {entry['address']}  block {entry['height']:>9,}  {entry['name']}")


def test():
    with open(VECTOR, encoding="utf-8") as f:
        vector = json.load(f)
    seed, winners = draw(vector["genesis"], vector["block_hash"])
    got = [f"{w['address']} {w['name']}" for w in winners]
    ok = seed.hex() == vector["seed"] and got == vector["winners"]
    # The stream itself, so an implementation in another language can check each step.
    stream = Stream(seed)
    first = [stream.next64() for _ in range(3)]
    ok = ok and [format(x, "016x") for x in first] == vector["first_numbers"]
    print("genesis-draw test vector:", "ok" if ok else "FAILED")
    if not ok:
        print("  seed   ", seed.hex())
        print("  numbers", [format(x, "016x") for x in first])
        for line in got:
            print("  ", line)
    return 0 if ok else 1


def main():
    parser = argparse.ArgumentParser(description="The Genesis Miner draw (zecnero.org/rewards).")
    parser.add_argument("genesis", nargs="?", help="the frozen genesis.json")
    parser.add_argument("block_hash", nargs="?", help="the named Bitcoin block's hash, 64 hex digits")
    parser.add_argument("--test", action="store_true", help="check the published test vector")
    args = parser.parse_args()
    if args.test:
        return test()
    if not args.genesis or not args.block_hash:
        parser.error("give the frozen genesis.json and the block hash, or --test")
    run(args.genesis, args.block_hash)
    return 0


if __name__ == "__main__":
    sys.exit(main())