Fairness & Verify

// Winner Picker verifier. Recomputes the list fingerprint, the selection key and the winners.
const enc = new TextEncoder()
const hex = b => Array.from(new Uint8Array(b), x => x.toString(16).padStart(2, '0')).join('')
const sha256 = async s => new Uint8Array(await crypto.subtle.digest('SHA-256', typeof s === 'string' ? enc.encode(s) : s))
const cmp = (a, b) => a.length - b.length || (a < b ? -1 : a > b ? 1 : 0)
const canon = v => v === null || typeof v !== 'object' ? JSON.stringify(v)
  : Array.isArray(v) ? '[' + v.map(canon).join(',') + ']'
  : '{' + Object.keys(v).filter(k => v[k] !== undefined).sort().map(k => JSON.stringify(k) + ':' + canon(v[k])).join(',') + '}'

// Proof formats xcrop-winner-v1 and v2. Rules (filters) only decide who is in the list, which the
// fingerprint fixes; the pick algorithm is the same for both. v2 adds followTargets and rerolls.
async function verifyXcropDraw(proof, ids) {
  const c = proof.commitment
  const sorted = Array.from(new Set(ids.map(s => String(s).trim().replace(/^0+(?=\d)/, '')))).sort(cmp)
  const digest = hex(await sha256(sorted.join('\n')))
  const commitHash = hex(await sha256(canon(c)))
  const keyBytes = await sha256(proof.beacon.randomness + ':' + digest + ':')
  const key = await crypto.subtle.importKey('raw', keyBytes, { name: 'HMAC', hash: 'SHA-256' }, false, ['sign'])
  const pool = sorted.slice(), seq = [], TWO256 = 1n << 256n
  let counter = 0
  while (pool.length && seq.length < proof.sequence.length) {
    const n = BigInt(pool.length), limit = (TWO256 / n) * n
    let r
    do { r = BigInt('0x' + hex(await crypto.subtle.sign('HMAC', key, enc.encode('pick:' + counter++)))) } while (r >= limit)
    seq.push(pool.splice(Number(r % n), 1)[0])
  }
  const followRule = (c.followTargets || []).length > 0 || !!c.conditions.mustFollowAuthor
  const passes = id => !followRule || (proof.followChecks || {})[id] === true
  const N = Math.min(c.winnerCount, sorted.length), winners = [], rejected = []
  let i = 0
  for (; i < seq.length && winners.length < N; i++) (passes(seq[i]) ? winners : rejected).push(seq[i])
  // A proof cut short must fail: N winners, unless every eligible entry was picked. Re-rolls never change the count.
  const completeOk = winners.length === N || seq.length === sorted.length
  // Re-rolls: each replacement must be the next unused pick (follow failures skipped), in order.
  let rerollsOk = true
  for (const r of proof.rerolls || []) {
    if (winners[r.rank - 1] !== r.replacedId) { rerollsOk = false; break }
    const skipped = []
    let next
    while (i < seq.length) { const x = seq[i++]; if (passes(x)) { next = x; break } skipped.push(x) }
    if (next !== r.replacementId || skipped.join() !== (r.skipped || []).join()) { rerollsOk = false; break }
    winners[r.rank - 1] = next
    rejected.push(...skipped)
  }
  const result = {
    digestOk: digest === c.participantsDigest,
    commitHashOk: commitHash === proof.commitHash,
    randomnessMatchesSignature: !!proof.beacon.signature && hex(await sha256(Uint8Array.from(proof.beacon.signature.match(/../g), h => parseInt(h, 16)))) === proof.beacon.randomness,
    // The beacon must be the committed round, and the commit must predate it (drand quicknet: genesis 1692803367, 3 s rounds).
    roundOk: proof.beacon.round === c.targetRound,
    committedBeforeRound: Date.parse(c.committedAt) < (1692803367 + (c.targetRound - 1) * 3) * 1000,
    sequenceOk: seq.join() === proof.sequence.join(),
    completeOk,
    winnersOk: winners.join() === proof.winners.join(),
    rejectedOk: rejected.join() === (proof.rejected || []).join(),
    rerollsOk,
    winners,
    // The commitment must name drand quicknet (lib/winner/drand.ts DRAND_QUICKNET.chainHash): the round timing above
    // and the beacon check assume that chain.
    chainOk: c.chainHash === '52db9ba70e0cc0f6eaf7803dd07447a1f5477735fd3f661792ba94600c84e971',
    checkRoundAt: 'https://api.drand.sh/' + c.chainHash + '/public/' + c.targetRound,
  }
  result.ok = result.chainOk && result.digestOk && result.commitHashOk && result.randomnessMatchesSignature && result.roundOk
    && result.committedBeforeRound && result.sequenceOk && result.completeOk && result.winnersOk && result.rejectedOk && result.rerollsOk
  return result
}

// RFC 4180 reader (quoted fields may contain commas and line breaks).
function parseCsv(t) {
  const rows = [[]]
  let f = '', q = false
  for (let i = 0; i < t.length; i++) {
    const ch = t[i]
    if (q) { if (ch === '"') { if (t[i + 1] === '"') { f += '"'; i++ } else q = false } else f += ch }
    else if (ch === '"' && f === '') q = true
    else if (ch === ',') { rows[rows.length - 1].push(f); f = '' }
    else if (ch === '\n') { rows[rows.length - 1].push(f.replace(/\r$/, '')); f = ''; rows.push([]) }
    else f += ch
  }
  rows[rows.length - 1].push(f)
  return rows.filter(r => r.join('') !== '')
}

// Node: node verify.mjs proof.json eligible.csv  (reads the "id" column of the CSV)
if (typeof process !== 'undefined' && process.argv && process.argv[3]) {
  const fs = await import('node:fs')
  const raw = JSON.parse(fs.readFileSync(process.argv[2], 'utf8'))
  const proof = raw && raw.proof && raw.proof.commitment ? raw.proof : raw // accepts the bare proof or the public record JSON
  const rows = parseCsv(fs.readFileSync(process.argv[3], 'utf8').replace(/^\uFEFF/, ''))
  const col = rows[0].indexOf('id')
  const ids = (col >= 0 ? rows.slice(1) : rows).map(r => r[Math.max(col, 0)].replace(/^'/, ''))
  console.log(JSON.stringify(await verifyXcropDraw(proof, ids), null, 2))
}