Како функционира извлекувањето — конкретен пример

Чекор 1 — Соберете ги и филтрирајте ги записите

Апликацијата презема секој коментар од Facebook или Instagram објавата што сте ја поврзале, потоа ги применува филтрите на натпреварот — дупликати, забранети зборови, правила за возраста на сметката, што и да било конфигурирано. Она што преживува е квалификуваниот сет. Во нашето сценарио тоа е 1.000 коментари. Секој има ред во базата со уникатно нумеричко ID; тие 1.000 ID-а се она врз што работи остатокот од извлекувањето.

Чекор 2 — Сортирајте ги во канонски редослед

Пред да се случи нешто случајно, апликацијата ги сортира 1.000-те ID-а во строг растечки нумерички редослед — 17, 142, 203, 1058, 9941, … — и го отфрла редоследот по кој пристигнале. Зошто? Бидејќи Facebook може да враќа коментари во различен редослед во зависност од пагинирањето, времето од денот или промените во позадината. Ако извлекувањето го користеше редоследот на Facebook, две преземања би можеле да произведат различни победници од истата случајна семка. Сортирањето прво го фиксира влезот на една канонска листа, така што семката само го одредува исходот.

Чекор 3 — Заклучете ја влезната листа со SHA-256 хеш

Сортираната листа се проследува низ SHA-256 — криптографска хеш функција — производувајќи 64-карактерен отпечаток. Отпечатокот, заедно со целата листа, се зачувува во записот на натпреварот. Од овој момент натаму, секој кој го испитува натпреварот може да потврди дека квалификуваната листа не е изменета: повторно хеширајте ја објавената листа, споредете со зачуваниот отпечаток, и едно променето ID дава сосема различен хеш. Не постои начин тивко да се додаде или отстрани коментар по овој чекор без тоа да биде видливо.

Чекор 4 — Генерирајте 256-битна случајна семка

Апликацијата го бара криптографскиот случаен извор на оперативниот систем (SecureRandom.hex(32)) за 32 бајти непредвидлива случајност и го зачувува резултатот како 64-карактерна хексадецимална низа — на пример a3f1…ce. 256 бита значи 2²⁵⁶ ≈ 10⁷⁷ можни семки. За перспектива, видливата вселена содржи приближно 10⁸⁰ атоми. Никој — ниту креаторот на натпреварот, ниту операторот, ниту напаѓач од надвор — не може да ја предвиди или погоди оваа семка пред да биде генерирана.

Чекор 5 — Размешајте ги 1.000-те ID-а, потоа земете ги првите 12

Семката иницијализира детерминистички мотор за размешување, кој потоа изведува Fisher–Yates размешување врз 1.000-те сортирани ID-а. Fisher–Yates е стандардниот алгоритам за фер размешување — секој од 1.000-те записи има еднаква шанса да заврши на секоја позиција. По размешувањето, апликацијата ги зема првите 12 записи од врвот. Тоа е целиот чекор на избор: размешај, отсечи 12.

Чекор 6 — Доделете позиции

12-те избрани записи се земаат по редослед. Првите три стануваат победници 1, 2 и 3, а следните девет стануваат резерви од 1 до 9. Преостанатите 988 квалификувани записи се запишуваат како неизбрани. Коментарите кои биле филтрирани претходно се означени како дисквалификувани со специфичната причина зошто не се квалификувале.

Чекор 7 — Објавете сè

Конечно, апликацијата зачувува пет дела на доказ во записот на натпреварот — сите јавно читливи. Без нив, резултатот би бил црна кутија. Со нив, секој може да го репродуцира целото извлекување дома и да потврди дека објавените победници се единствените победници кои семката можело да ги произведе.

Повторете ја математиката сами — во пет линии

Ако имате инсталиран Ruby (доаѓа со macOS и повеќето Linux дистрибуции), можете да го репродуцирате точното извлекување дома. Секој натпревар објавува сопствен eligible-ids.txt на својата страница за верификација (URL шаблон: /results/<token>/verify) — водичот за верификација ве води чекор-по-чекор низ симнувањето. Копирајте го објавената семка и залепете го ова во irb:

require "digest"
seed = "PASTE_THE_PUBLISHED_SEED_HERE"
ids  = File.read("eligible-ids.txt").split("\n").map(&:to_i).sort

# (1) Sanity check the input: must equal the published SHA-256.
Digest::SHA256.hexdigest(ids.join("\n"))

# (2) Re-run the shuffle. First 3 items are winners 1..3 (in order);
#     the next 9 items are reserves 1..9.
ids.shuffle(random: Random.new(seed.to_i(16))).first(12)

12-те ID-а излегуваат во точно истиот редослед како натпреварот објавил. Три победници, девет резерви, бит-по-бит идентични. Тоа е она што прави Pick a Winner извлекувањето да биде проверливо, наместо само ветено — математиката ја врши работата, не зборот на операторот.

Зошто ова е тешко да се намести

• Семката е непогодлива. 2²⁵⁶ можности, генерирани само по фиксирањето на квалификуваната листа. Никој не може однапред да пресмета кои ID-а би ги фаворизирала семката, бидејќи семката не постои до моментот на извлекувањето.
• Влезот е заклучен. SHA-256 отпечатокот значи дека не можете тивко да додадете коментар од пријател откако ќе го видите семката — отпечатокот би се променил и извлекувањето повеќе не би се репродуцирало.
• Размешувањето е механичко. Откако семката и сортираната листа постојат, победниците се одредени. Никаква човечка одлука не седи помеѓу нив. Секое накнадно поправање би се појавило како несовпаѓање во моментот кога некој ќе ја повтори математиката.
• Потврдата е јавна. Семка, листа, хеш, верзија на алгоритам, Ruby верзија — сите пет се објавени. Не постои приватен дел од извлекувањето кој операторот би можел да го промени без сите да можат да видат.