328 lines
12 KiB
PHP
328 lines
12 KiB
PHP
<?php
|
|
|
|
namespace App\Polls;
|
|
|
|
use App\Models\Poll;
|
|
use App\Models\PollLedgerEntry;
|
|
use Illuminate\Support\Collection;
|
|
use Illuminate\Support\Facades\DB;
|
|
use Illuminate\Support\Str;
|
|
|
|
/**
|
|
* The append-only ballot ledger of a poll: a SHA-256 hash chain.
|
|
*
|
|
* hash = SHA-256 of the canonical JSON of
|
|
* {v, poll_id, sequence, entry_type, fingerprint, refers_to_sequence, payload, recorded_at, previous_hash}
|
|
* Canonical JSON: object keys sorted (byte order), lists kept in order, no whitespace,
|
|
* unicode and slashes unescaped. The first entry's previous_hash is 64 zeros.
|
|
* This format is published on the verification page and recomputed there in the browser.
|
|
* Each entry stores the format_version it was hashed with; a new format must bump
|
|
* FORMAT_VERSION and keep hashing older entries the old way.
|
|
*/
|
|
class Ledger
|
|
{
|
|
public const FORMAT_VERSION = 1;
|
|
public const GENESIS_HASH = '0000000000000000000000000000000000000000000000000000000000000000';
|
|
|
|
/** Receipt alphabet without look-alikes (no 0/O, 1/I/L). */
|
|
private const RECEIPT_ALPHABET = '23456789ABCDEFGHJKMNPQRSTUVWXYZ';
|
|
|
|
/**
|
|
* Append an entry. Must run inside the caller's DB transaction, so the ledger entry
|
|
* and the poll_responses / poll_answers rows are written together or not at all.
|
|
*/
|
|
public function append(
|
|
Poll $poll,
|
|
string $type,
|
|
?array $payload = null,
|
|
?string $fingerprint = null,
|
|
?int $refersToSequence = null
|
|
): PollLedgerEntry {
|
|
if (DB::transactionLevel() === 0) {
|
|
throw new \LogicException('Ledger::append() must run inside a database transaction.');
|
|
}
|
|
|
|
// Serialize appends per poll: the row lock makes concurrent votes queue up
|
|
Poll::whereKey($poll->id)->lockForUpdate()->value('id');
|
|
|
|
$last = PollLedgerEntry::where('poll_id', $poll->id)->orderByDesc('sequence')->first();
|
|
|
|
$attributes = [
|
|
'poll_id' => $poll->id,
|
|
'sequence' => $last ? $last->sequence + 1 : 1,
|
|
'format_version' => self::FORMAT_VERSION,
|
|
'entry_type' => $type,
|
|
'fingerprint' => $fingerprint,
|
|
'refers_to_sequence' => $refersToSequence,
|
|
'payload' => $payload,
|
|
'recorded_at' => $this->recordedAt(),
|
|
'previous_hash' => $last ? $last->hash : self::GENESIS_HASH,
|
|
];
|
|
$attributes['hash'] = $this->hash($attributes);
|
|
|
|
return PollLedgerEntry::create($attributes);
|
|
}
|
|
|
|
/**
|
|
* Ballot payload: the normalized answers as a list ordered by question id.
|
|
* Free text is stored as its SHA-256 only: the public ledger must not reveal it (it could
|
|
* identify people), while the hash still commits to it. The text itself is in poll_answers.
|
|
*
|
|
* @param array<int, array{value: mixed, text: ?string}> $normalized keyed by question id
|
|
*/
|
|
public function ballotPayload(array $normalized): array
|
|
{
|
|
ksort($normalized);
|
|
$answers = [];
|
|
foreach ($normalized as $questionId => $answer) {
|
|
$text = $answer['text'] ?? null;
|
|
$answers[] = [
|
|
'question_id' => (int) $questionId,
|
|
'value' => $answer['value'] ?? null,
|
|
'text_sha256' => $text !== null && $text !== '' ? hash('sha256', $text) : null,
|
|
];
|
|
}
|
|
|
|
return ['answers' => $answers];
|
|
}
|
|
|
|
/**
|
|
* Type-neutral tally: how often each distinct value was given per question, as a sorted list of
|
|
* {question_id, value (canonical JSON), count}. A list rather than a map, so PHP and the browser
|
|
* encode it identically (PHP turns maps with keys 0, 1, 2... into JSON lists).
|
|
*
|
|
* @param iterable<array{question_id: int, value: mixed}> $answers
|
|
* @return array<int, array{question_id: int, value: string, count: int}>
|
|
*/
|
|
public function tally(iterable $answers): array
|
|
{
|
|
$counts = [];
|
|
foreach ($answers as $answer) {
|
|
if (($answer['value'] ?? null) === null) {
|
|
continue;
|
|
}
|
|
$key = (int) $answer['question_id'] . "\0" . $this->canonical($answer['value']);
|
|
$counts[$key] = ($counts[$key] ?? 0) + 1;
|
|
}
|
|
|
|
$tally = [];
|
|
foreach ($counts as $key => $count) {
|
|
[$questionId, $value] = explode("\0", $key, 2);
|
|
$tally[] = ['question_id' => (int) $questionId, 'value' => $value, 'count' => $count];
|
|
}
|
|
// Byte order (strcmp), not PHP's numeric-string comparison: the browser sorts the same way
|
|
usort($tally, fn ($a, $b) => ($a['question_id'] <=> $b['question_id']) ?: strcmp($a['value'], $b['value']));
|
|
|
|
return $tally;
|
|
}
|
|
|
|
/** Tally of the ballots that count in the ledger. */
|
|
public function ledgerTally(Poll $poll): array
|
|
{
|
|
return $this->tally($this->activeBallots($poll)->flatMap(fn ($entry) => $entry->payload['answers'] ?? []));
|
|
}
|
|
|
|
/** Tally of the published results (poll_answers of the current votes). */
|
|
public function publishedTally(Poll $poll): array
|
|
{
|
|
$answers = \App\Models\PollAnswer::whereIn('poll_response_id', $poll->responses()->select('id'))
|
|
->get(['poll_question_id', 'value'])
|
|
->map(fn ($answer) => ['question_id' => $answer->poll_question_id, 'value' => $answer->value]);
|
|
|
|
return $this->tally($answers);
|
|
}
|
|
|
|
/**
|
|
* Seal a closed poll: a final entry committing to the number of counted ballots and the tally.
|
|
* Idempotent; withdrawals after the seal (deleted profiles) are appended after it.
|
|
*/
|
|
public function seal(Poll $poll): ?PollLedgerEntry
|
|
{
|
|
return DB::transaction(function () use ($poll) {
|
|
$poll = Poll::whereKey($poll->id)->lockForUpdate()->first();
|
|
if (!$poll || $poll->sealed_at) {
|
|
return null;
|
|
}
|
|
|
|
$entry = $this->append($poll, PollLedgerEntry::SEAL, [
|
|
'active_ballots' => $this->activeBallots($poll)->count(),
|
|
'tally_sha256' => hash('sha256', $this->canonical($this->ledgerTally($poll))),
|
|
]);
|
|
$poll->update(['sealed_at' => now(), 'seal_hash' => $entry->hash]);
|
|
|
|
return $entry;
|
|
});
|
|
}
|
|
|
|
/**
|
|
* An entry as published in the ledger JSON: exactly the hashed fields, plus its hash.
|
|
*/
|
|
public function publicEntry(PollLedgerEntry $entry): array
|
|
{
|
|
return [
|
|
'v' => (int) $entry->format_version,
|
|
'poll_id' => (int) $entry->poll_id,
|
|
'sequence' => (int) $entry->sequence,
|
|
'entry_type' => $entry->entry_type,
|
|
'fingerprint' => $entry->fingerprint,
|
|
'refers_to_sequence' => $entry->refers_to_sequence !== null ? (int) $entry->refers_to_sequence : null,
|
|
'payload' => $entry->payload,
|
|
'recorded_at' => $entry->recorded_at,
|
|
'previous_hash' => $entry->previous_hash,
|
|
'hash' => $entry->hash,
|
|
];
|
|
}
|
|
|
|
/** SHA-256 of the canonical form of an entry. */
|
|
public function hash(array $entry): string
|
|
{
|
|
$version = (int) ($entry['format_version'] ?? self::FORMAT_VERSION);
|
|
if ($version !== self::FORMAT_VERSION) {
|
|
throw new \UnexpectedValueException("Unknown poll ledger format version [$version]");
|
|
}
|
|
|
|
return hash('sha256', $this->canonical([
|
|
'v' => $version,
|
|
'poll_id' => (int) $entry['poll_id'],
|
|
'sequence' => (int) $entry['sequence'],
|
|
'entry_type' => $entry['entry_type'],
|
|
'fingerprint' => $entry['fingerprint'] ?? null,
|
|
'refers_to_sequence' => isset($entry['refers_to_sequence']) ? (int) $entry['refers_to_sequence'] : null,
|
|
'payload' => $entry['payload'] ?? null,
|
|
'recorded_at' => $this->timestamp($entry['recorded_at']),
|
|
'previous_hash' => $entry['previous_hash'],
|
|
]));
|
|
}
|
|
|
|
public function canonical($value): string
|
|
{
|
|
return json_encode(
|
|
$this->sortKeys($value),
|
|
JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES | JSON_UNESCAPED_LINE_TERMINATORS | JSON_THROW_ON_ERROR
|
|
);
|
|
}
|
|
|
|
private function sortKeys($value)
|
|
{
|
|
if (!is_array($value)) {
|
|
return $value;
|
|
}
|
|
if (!array_is_list($value)) {
|
|
ksort($value, SORT_STRING);
|
|
}
|
|
|
|
return array_map(fn ($item) => $this->sortKeys($item), $value);
|
|
}
|
|
|
|
/**
|
|
* When an entry is recorded: the start of the day, in the site's time zone (security audit
|
|
* F10). The ledger is public and an exact time could link a ballot to someone known to
|
|
* have voted then; the order is kept by the sequence numbers. Part of the hash, so it is
|
|
* rounded when recorded, not when shown.
|
|
*/
|
|
public function recordedAt(): string
|
|
{
|
|
return $this->timestamp(now(config('app.timezone'))->startOfDay());
|
|
}
|
|
|
|
/** UTC, second precision: 2026-10-10T17:00:00Z (stored as is, so no timezone conversion on read) */
|
|
public function timestamp(\DateTimeInterface|string $dateTime): string
|
|
{
|
|
if (is_string($dateTime)) {
|
|
return $dateTime;
|
|
}
|
|
|
|
return \Illuminate\Support\Carbon::instance($dateTime)->utc()->format('Y-m-d\TH:i:s\Z');
|
|
}
|
|
|
|
/**
|
|
* A new receipt code: 20 characters in groups of five, e.g. 7KQ2M-XH4PD-...
|
|
*/
|
|
public function newReceiptCode(): string
|
|
{
|
|
$code = '';
|
|
$max = strlen(self::RECEIPT_ALPHABET) - 1;
|
|
for ($i = 0; $i < 20; $i++) {
|
|
$code .= self::RECEIPT_ALPHABET[random_int(0, $max)];
|
|
}
|
|
|
|
return implode('-', str_split($code, 5));
|
|
}
|
|
|
|
/** Fingerprint stored in the ledger; tolerant of case, spaces and dashes in the entered code. */
|
|
public function fingerprint(string $receiptCode): string
|
|
{
|
|
return hash('sha256', preg_replace('/[^A-Z0-9]/', '', Str::upper($receiptCode)));
|
|
}
|
|
|
|
/**
|
|
* Recompute the whole chain.
|
|
*
|
|
* @return array{valid: bool, entries: int, broken_at: ?int, head: string}
|
|
*/
|
|
public function verifyChain(Poll $poll): array
|
|
{
|
|
$previous = self::GENESIS_HASH;
|
|
$expectedSequence = 1;
|
|
$count = 0;
|
|
|
|
foreach (PollLedgerEntry::where('poll_id', $poll->id)->orderBy('sequence')->cursor() as $entry) {
|
|
$attributes = $entry->getAttributes();
|
|
$attributes['payload'] = $entry->payload;
|
|
|
|
if ($entry->sequence !== $expectedSequence
|
|
|| $entry->previous_hash !== $previous
|
|
|| !hash_equals($this->hash($attributes), $entry->hash)) {
|
|
return ['valid' => false, 'entries' => $count, 'broken_at' => $entry->sequence, 'head' => $previous];
|
|
}
|
|
|
|
$previous = $entry->hash;
|
|
$expectedSequence++;
|
|
$count++;
|
|
}
|
|
|
|
return ['valid' => true, 'entries' => $count, 'broken_at' => null, 'head' => $previous];
|
|
}
|
|
|
|
/**
|
|
* Ballots that count: cast / change entries not replaced by a later change or withdraw.
|
|
*
|
|
* @return Collection<int, PollLedgerEntry>
|
|
*/
|
|
public function activeBallots(Poll $poll): Collection
|
|
{
|
|
$entries = PollLedgerEntry::where('poll_id', $poll->id)->orderBy('sequence')->get();
|
|
$replaced = $entries->pluck('refers_to_sequence')->filter()->flip();
|
|
|
|
return $entries->filter(fn ($entry) => $entry->isBallot() && !$replaced->has($entry->sequence))->values();
|
|
}
|
|
|
|
/**
|
|
* Status of the ballot behind a receipt code.
|
|
*
|
|
* @return array{entry: PollLedgerEntry, status: string, replaced_by: ?PollLedgerEntry}|null
|
|
* status: 'counted' | 'replaced' | 'withdrawn'; null when the code is unknown for this poll
|
|
*/
|
|
public function lookupReceipt(Poll $poll, string $receiptCode): ?array
|
|
{
|
|
$entry = PollLedgerEntry::where('poll_id', $poll->id)
|
|
->where('fingerprint', $this->fingerprint($receiptCode))
|
|
->first();
|
|
if ($entry === null) {
|
|
return null;
|
|
}
|
|
|
|
$replacedBy = PollLedgerEntry::where('poll_id', $poll->id)
|
|
->where('refers_to_sequence', $entry->sequence)
|
|
->first();
|
|
|
|
$status = match ($replacedBy?->entry_type) {
|
|
null => 'counted',
|
|
PollLedgerEntry::WITHDRAW => 'withdrawn',
|
|
default => 'replaced',
|
|
};
|
|
|
|
return ['entry' => $entry, 'status' => $status, 'replaced_by' => $replacedBy];
|
|
}
|
|
}
|