Previous Entry Share Next Entry
Лотерея без обмана
Smooth green tea
sanmai


Что делать, если вы хотите разыграть лотерею, но хотите исключить "фактор веры" в устроителя лотереи и всякую возможность для манипуляции результатами лотереи?

Это возможно сделать математическими методами, для чего перед началом регистрации участников (продажей билетов) следует получить и опубликовать случайную строку символов произвольной длины, которая будет служить случайным начальным вектором при раздаче призов. Если участникам разрешить в определенной мере самим выбирать номера билетов, например, используя свои уже существующие до начала розыгрыша имена, то публикация этого вектора практически полностью исключает возможность манипуляции результатами розыгрыша любыми сторонами при соблюдении некоторых условий.

Для раздачи призов мы берем криптографический хеш от строки, состоящей из опубликованного случайного вектора и "билета" участника (имени пользователя). Особенностью таких функций является то, что практически невозможно из хеша получить обратно исходное значение. Также эти функции обладают лавинным эффектом, что означает что смена даже одного бита в векторе или в "номере" билета ведет к существенной смене итогового хеша и изменению результата лотереи для конкретного участника.

Полученный список билетов (имен пользователей) с хешами мы сортируем и получаем список победителей, который, с одной стороны, один единственный для заданного вектора и, с другой стороны, неизвестен, пока не определен список участников.

Конечно, сам факт публикации случайного вектора не гарантирует того, что он не был специально подобран под известного победителя, потому в расчет итогового списка стоит внести зависимость от исходного списка участников. Таким образом смена списка участников изменит и победителя. Включая список участников в функцию расчета победителя мы даем некоторую власть вам над результатами розыгрыша, откуда естественно следует требование прозрачности отбора участников: у каждого должна быть возможность проверить наличие воли того или иного участника к участию, например, при помощи перепоста.

Предлагаю вам маленькую программу на чистом JavaScript, которая делает ровно то, что описано выше.

Программа идет с исходным кодом, а значит каждый может ознакомиться с ним и убедиться что программа делает именно то, что она делает и ничего больше.



Выражаю благодарность eugenyshultz за наводку на этот метод розыгрыша.

  • 1
Устроитель может подобрать список участников так, чтобы выигрыш достался нужному человеку.
Берем список реальных участников, добавляем к нему несуществующего игрока смотрим выиграл ли наш протеже, если нет меняем подставному фамилию, повторяем. Статистически будет достаточно придумать столько фамилий сколько участников.

И выиграет какой-нибудь a0cxzxmgmel или n01s3nk1ss3s, да? С одной стороны такое, конечно, возможно, но... Очень много вопросов появится у других участников.

В сто раз проще обмануть без всякого подбора имен если использовать традиционный метод барабана с номерками.

Edited at 2012-12-31 11:05 am (UTC)

Нет. Выигрываю я. Берем топ10 ЖЖ по соц капиталу, добавляю себя, пытаюсь выиграть добавлением 12 игрока. Михаил Задорнов поможет мне в этом -
Список участников -
drugoi
sergeydolya
tema
zyalt
navalny
shpilenok
mi3ch
prostitutka_ket
pesen_net
miumau
cdesz
mzadornov

Смотрим Ваш скрипт и поздравляем меня с победой

Какой случайный вектор использовался?
Попробуйте с таким, например, подобрать:
GlJwBGX7l37FftvqBkG8ctnFROl7cpzbWXaoVmG0J21KPnPe7fQtBsyPluPbwwoC

Edited at 2012-12-31 11:16 am (UTC)

Легко.
В этот раз вместо задорного пригласим какого-то podakuni
[Список участников]Всего 12: cdesz, drugoi, mi3ch, miumau, navalny, pesen_net, podakuni, prostitutka_ket, sergeydolya, shpilenok, tema, varlamov.ru

Только вот у podakuni нет перепоста (регистрации, проданного билета - назовите как хотите), который требуется для участия, а потому вы зря старались. Если публикуется полный список участников, как в нашем конкретном случае, который можно проверить - нет проблемы. Дополнил пост этим моментом.

Edited at 2012-12-31 01:54 pm (UTC)

drugoi
sergeydolya
tema
zyalt
navalny
shpilenok
mi3ch
prostitutka_ket
pesen_net
miumau
zverolov
piony

Пожалуйста, с вашим вектором и с помощью юзера piony (только что из моей фленты). Я победил!

Только вот у piony нет перепоста, который требуется для участия, а потому вы зря старались. Вашу подставу будет легко вывести на чистую воду используя полный список участников. Дополнил пост этим требованием.

Если вы собираетесь скрывать список участников, то эти криптографические ухищрения вам не нужны. Вы и без них можете замечательно поставить нужного человека на нужное место.

Edited at 2012-12-31 01:55 pm (UTC)

Так мы же говорим о возможности подтасовок со стороны организатора, а не участников, правильно? Я на месте организатора легко мог бы найти незанятый ЖЖ-юзернейм и "подарить" ему "билет"/участие для победы zverolov.

В нашем конкретном случае не получится такое провернуть, т.к. юзернейм должен быть занят до начала розыгрыша. Это прописано в правилах.

Как уже говорил, организаторы могут дать выиграть своем и без всех этих плясок с хеш-функциями. Барабан с номерками и никто носа не подточит, ибо дареному коню, как известно... :-)

> В нашем конкретном случае не получится такое провернуть, т.к. юзернейм должен быть занят до начала розыгрыша. Это прописано в правилах.

Почему бы вам тогда не зарегистрировать пару сотен юзернеймов, чтобы успеть к началу следующего розыгрыша? ))) Многие боты, кстати, действительно регистрируются сильно загодя начала своей активности.

>Как уже говорил, организаторы могут дать выиграть своем и без всех этих плясок с хеш-функциями.
О чём и речь! Я бы больше доверял барабану.

Если удалять реальных участников из общего списка, то результатом можно манипулировать.
А если один из участников удалит свой перепост - окажется что он лишний в списке.
Без доверия всё равно не обойтись :)

Ваша правда, но над этими факторами мы не властны :)

Спасибо, очень интересно)

Недурно! Очень познавательно и интересно. Был приятно удивлён.

"Справедливая лотерея" подразумевает наличие внутреннего арбитража. Т.е. возможности любого участника проверить отсутствие обмана со стороны организатора, а так же возможность организатора доказать отсутствие обмана. И математически такая задача разрешима, правда она не разрешима при условии однократной передачи информации. Вообще-то вы как раз и пытаетесь ввести дополнительные циклы передачи вводя проверку перепостов после лотереи. Но в таком виде это не защитит организатора от незаслуженных обвинений. Организатору придется проверить каждый перепост и сделать снимок чтобы оправдаться от обвинения. Но это все равно никак не спасает от манипуляции с подставными людьми, причем манипулировать может любой участник если список участников публичен.
За минуту до конца регистрации берем список, подбираем ник обеспечивающий победу, регистрируем его, делаем перепост, профит.
Вообщем математическое решение есть но оно вряд ли интересно, т.к. участники лотереи не всегда будут готовы делать дополнительные действия между заявкой на участие и розыгрышем. Но есть вполне качественная замена - источник энтропии неподконтрольный организатору. Нужно что-то публичное, проверяемое, непредсказуемое во время сбора ставок но известное к розыгрышу. Например хеш от первых 20 существительных в выпуске новостей в день розыгрыша, или хеш всех телефонов на 18 странице газеты бесплатных объявлений или количество букв а в топ3 постах ЖЖ на момент розыгрыша.




  • 1
?

Log in

No account? Create an account