А какие у вас ассоциации от слов «лотерея» и «розыгрыш»? У меня — разноцветные шары с номерами и лотерейная машина, из которой разноцветные шары выпадают по одному и определяют победителя.
Вот и мне некоторое время назад понадобилось “определить” победителей розыгрыша бесплатных места на курс “Разработчик Java” в Otus.ru. Задача звучала просто: есть N email-ов, нужно выбрать среди них случайным образом M email-ов тех, кто будет учиться бесплатно.
Сложность задачи была в том, что это были email-ы всех, кто успешно прошел входное тестирование курса. То есть email-ы программистов. Я представил себе, как я “достаю из кармана” M email-ов и говорю: “Вот эти победили”. И… мне никто не верит. Даже если победители начинают радостно писать в общий чат: “Спасибо, как мы рады!”, мне все равно никто из оставшихся не поверит. Да я бы и сам не поверил, если бы мне просто сказали «победили эти».
Программистам мало сказать кто победил, надо доказать что это действительно случайные победители, и что в общем списке действительно был их email, и что вероятность попасть в победители у всех равна.
Вот в таких условиях нужно было придумать как разыграть места. В этой заметке, я хочу предложить вам мое решение этой задачи. Буду рад комментариям и особенно замечаниями об убедительности моего решения. Вы бы стали обоснованно спорить с результатами, если бы ваш email был в общем списке?
Итак, как провести розыгрыш призов среди программистов:
- Убрать из выбора организатора розыгрыша. Выбирать должен робот.
- Сделать робота открытым, чтобы любой мог посмотреть как он выбирает.
- Сделать случайный выбор псевдослучайным. Так, чтобы любой, кто знает зерно последовательности, его мог повторить.
- И при этом, формировать зерно псевдослучайности на случайности материальной.
- Выложить в общий доступ… email-ы? Чтобы каждый мог найти себя в списке? Нет, этого наши пользователи не оценили бы. Но каким-то образом дать проверить, что ты в списке, нужно.
Первое, что было логично сделать — поручить выбор программе. Написать лотерейную машину, которая бы решала кто победил. Коды моей машины вы можете посмотреть в моем аккаунте на github.
Она состоит из класса для чтения email-ов, класса который производит выбор “шаров” с индексами победителей и класса, который все запускает.
С получением списка email-ов все просто. Их надо прочитать из файла. Сначала я хотел читать email-ы и имена из csv файла, но потом оставил только email-ы, а csv и библиотека, которая его читает, остались.
Результат прочтения email-ов — List я передаю в лотерейную машину. Кроме этого, она на вход получает количество победителей. И еще ей можно задать seed — зерно псевдослучайной последовательности. Его можно задать числом, или строкой. Во втором случае зерном будет hash от строки.
Если у вас есть seed, то лотерейная машина будет выдавать одну и туже “случайную” последовательность победителей при каждом запуске. Случайную, но псевдо. Что, собственно, нам и надо.
Хорошо, список с email-ми у нас есть, лотерейная машина есть, и она использует в работе класс java.util.Random, который дает нам псевдослучайную последовательность на основе seed-а.
Теперь, для успеха нам недостает простой вещи: случайного seed-a — зерна последовательности. Так чтобы он был случайный, но чтобы мы могли его запомнить. Я решил в качестве источника такой материальной случайности использовать содержимое чата. Последние несколько сообщений передать в машину, чтобы она вычислила себе seed.
Все, кто пришли на розыгрыш, могли писать в чат когда угодно и что угодно. Подделать сообщения в чате, так чтобы подгадать с определением hash-а? Я не знаю как это сделать. Кроме того, я попросил желающих что-нибудь в чат написать прямо перед запуском машины.
Как это было, можно посмотреть в записи Дня открытых дверей на youtube.
Мы запустили лотерейную машину и получили победителей. Потом запустили ее еще раз и получили тех же самых.
После чего я предложил изменить текст, и удалил последнее сообщение. Со словами: “а теперь посмотрим как повлиял этот последний комментарий на результат”, я запустил машину и среди результатов был email того кто этот последний комментарий написал. Если бы он его не писал, приз был бы у него. Конечно он это заметил. Конечно мы все это заметили. И победители поблагодарили автора комментария за подарок.
Выкладывать в github email-ы мы конечно не стали. Но в репо вы можете посмотреть файл в котором записаны “обфусцированные” email-ы.
А как бы вы разыграли призы среди программистов? Понятен ли код и принцип работы машины?
Комментарии (25)
maximw
23.06.2017 14:37+21) Каждый может проверить что он есть в списке емейлов под определенным номером
Хешируем все емейлы, публикуем упорядоченный список хешей, использованный алгоритм (например, SHA-256) и использованную соль. Каждый может посчитать хеш для своего емейла, и найти его в списке под определенным нормером.
2) Выбираем ГПСЧ.
Не надо изобретать велосипед. Публикуем, что будет использоваться ГПСЧ из такой-то библиотеки такой-то версии. Каждый может запустить и проверить потом.
3) Выбор seed ГПСЧ.
Публикуем алгоритм выбора seed. Он должен быть легко-верифицируемым и трудно-подделываемым. Как вариант, алгоритм должен быть основан на публичных данных, которые еще не известны на момент публикации самого алгоритма.
Например, берем газету New York Times, номер который должен выйти в день розыгрыша, выбираем первые буквы первых 10 слов на 2 странице. Легко проверить даже спустя годы после розыгрыша (найти архив газеты), трудно подделать (если нет знакомого редактора в NY Times)vesper-bot
23.06.2017 16:26+1Пункт 3 "трудно подделываемый" должно значить "трудно сформировать желаемый seed", а не "трудно подменить seed постфактум".
Regis
23.06.2017 19:47+1Эм… У вас в коде для выбора email-ов нет защиты от многократного попадания одного и того же ящика в список победителей.
List<String> draw(List<String> emails) { System.out.println("Draw for the seed: " + seed); Random rnd = new Random(seed); Set<String> winners = new HashSet<>(); while (winners.size() < Math.min(winnersCount, emails.size())) { int index = rnd.nextInt(emails.size()); System.out.println("Ball: " + index); winners.add(emails.get(index)); } return new ArrayList<>(winners); }
martin_wanderer
29.06.2017 10:47Даже выкладка файла email'ов ничего не гарантирует — нет уверенности, что запущена программе на вход был дан настоящий список.
Для достоверности надо опубликовать список хэшей адресов, скажем, SHA-256. Ну выбирать, соответственно, хеши победителей. В качестве долполнительного теста — пусть сами проверяют, не их ли почта выиграла. При таком подходе каждый сможет убедиться, что его почта действительно участвовала в розыгрыше.
LionZXY
Появилась идея… Возможно, немного бредовая. Выдавать зашифрованный пакет на запрос с сервера, клиент пытается его расшифровать.
В пакете содержится уникальный ключ. Потом клиент отправляет серверу свой email с этим ключём.
Случайность заключается именно в расшифровке пакета на стороне клиента.
Итого, пойдут те первые %n% кто пришлет свой email.
Как вариант, написал по "фану" :)
LionZXY
P.S. Ну а варианту автора я всеравно не доверяю. Кто его знает, может он демона в фоне запустил, который в рантайме байткод меняет или компилятор кастомный
Tully
Ну так запустите на своей машине. Со своим компилятором и своими демонами. Строку для seed-а я запушил.
Email-ы возьмите из eparts.txt
Идея прикольная, кстати. Но мы хотели чтобы участвовали все, а не только те кто пришел посмотреть дод.
LionZXY
Ну можно на сервере проверять есть ли email в этом самом списке
LionZXY
А как вы Сид генерировали? Что мешало это сфабриковать?)
Tully
Сид формировал через вызов hashCode() у строки
Вот так
Проверьте, у вас hash для строки из чата будет тот же что и у меня. В логах на видео он есть.
LionZXY
Что мешало подменить код?) Сфабриковать можно все что угодно :)
Tully
Ну вы же можете запустить на своем компе. И получите тот же результат. Проверьте, если не верите.
LionZXY
С вашим сидом?)
Tully
Да, с моим. Который получен из текста случайно взятого из чата. И запушен в репо.
LionZXY
Откуда берется строка?
Tully
Из чата. Я об этом написал в статье и на видео говорю. Вы бы смогли сфабриковать чат в youtube?
Если да, идемте к нам преподавать ИБ.
LionZXY
Что мешает подговорить людей, которые пишут в чат?
Tully
Ну, тут мне нечего ответить. Подговорить всех? Ну наверное можно. Я не пробовал.
Если у вас нет паранои, это не значит что за вами не следят.
LionZXY
Ага :) Я не пытаюсь вас очернить, просто интересно спорить :)
Tully
А я не пытаюсь оправдаться.: о)
Я сторонник фальсифицируемости по Попперу
Regis
Достаточно подговорить последнего, чтобы он написал определенную фразу, которая скорректирует значение до "нужного".
xotta6bl4
Подговорить одних писать определенный текст, а других подговорить не писать? так проще тупо всем билеты раздать. Стоимость защиты, как и стомость взлома не должна превышать стоимости защищаемого/взламываемого.
dimkss
С этим можно бороться так:
брать hash не последней строки, а всего чата с какого-то времени до какого-то времени.
Или суммы первых слов, всех первых букв всех слов или как-то так…
Тогда будет достаточно любого лишнего комментария что-бы сид изменился.