# fair_pick

Deterministic, verifiable draw algorithm for provably fair random selection.

## What it does

`fair_pick` is a pure Elixir library that selects winners from a list of entries. Given entries (with optional weights), a 32-byte seed, and a winner count, it produces an ordered list of winners. Same inputs always produce the same output. No side effects, no network calls, no randomness — the only dependency is `:crypto` from OTP.

This determinism is the foundation of verifiability: anyone can re-run the algorithm with the published seed and entries and confirm the result independently.

## Installation

Add `fair_pick` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:fair_pick, "~> 0.2"}
  ]
end
```

## Usage

```elixir
entries = [
  %{id: "ticket-47", weight: 1},
  %{id: "ticket-48", weight: 1},
  %{id: "ticket-49", weight: 5}
]

seed = :crypto.hash(:sha256, "some-public-entropy")

FairPick.draw(entries, seed, 2)
# => [%{position: 1, entry_id: "ticket-49"}, %{position: 2, entry_id: "ticket-47"}]
```

Each entry requires an `id` (any string) and a `weight` (positive integer). Weight represents the number of tickets an entry holds — an entry with `weight: 5` is five times more likely to be selected than one with `weight: 1`. The `seed` must be a 32-byte binary. The third argument is the number of winners to select.

Winners are returned in draw order (position 1 is the first winner). Each unique entry appears at most once in the results regardless of weight.

## Algorithm

1. **Sort and expand:** Entries are sorted by ID (lexicographic, ascending) and each entry is expanded into `weight` slots in a flat pool. Sorting ensures determinism regardless of input order.
2. **Shuffle:** The pool is shuffled using the Durstenfeld (modern Fisher-Yates) algorithm. Swap indices are generated by a SHA256 counter-mode PRNG seeded with the provided seed.
3. **PRNG:** Each random index is produced by hashing `seed || counter` (where counter is a big-endian 32-bit integer), then applying rejection sampling to avoid modulo bias.
4. **Deduplicate:** After shuffling, the pool is walked in order. The first occurrence of each entry ID is kept; subsequent occurrences are skipped. This ensures each unique entry wins at most once.
5. **Truncate:** Results are truncated to the requested winner count (or fewer, if there are not enough unique entries).

## Test vectors

These vectors are frozen and canonical. Any correct reimplementation must produce identical output.

| Vector | Entries | Seed (hex) | Count | Winners (in order) |
|--------|---------|------------|-------|---------------------|
| A-1 | `a:1, b:1, c:1` | `0000...0000` (32 zero bytes) | 1 | `c` |
| A-2 | `alpha:3, beta:1, gamma:2` | `FFFF...FFFF` (32 `FF` bytes) | 2 | `gamma`, `alpha` |
| A-3 | `x:5, y:1` | `ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789` | 2 | `x`, `y` |
| A-4 | `solo:3` | `1111...1111` (32 `11` bytes) | 5 | `solo` (count capped at unique entries) |
| A-5 | `only:1` | `2222...2222` (32 `22` bytes) | 1 | `only` |

## Spec

The full protocol spec (commit-reveal protocol, entropy sources, API design) lives in the [wallop](https://github.com/electric-lump-software/wallop) repository.

## License

MIT — see [LICENSE](LICENSE).