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:

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

Usage

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

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.
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.
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.
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.
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 repository.

License

MIT — see LICENSE.