Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 59
Что если взять от каждого участника уникальное проверяемое значение (возраст, отчество бабушки) и попросить его закодировать, не говоря организаторам.
Затем генерируем случайное число в нашем множестве — и ближайшее к нему объявляем победителем.
Или раздать числа всем участникам и привязать рандомное число к неизвестному заранее фактору — курсу валют, температуре?
Затем генерируем случайное число в нашем множестве — и ближайшее к нему объявляем победителем.
Или раздать числа всем участникам и привязать рандомное число к неизвестному заранее фактору — курсу валют, температуре?
А как мы генерирум число в этом множестве? Кто за это ответственен?
Заранее неизвестный фактор это хорошо. Но нужно искать, чтобы: провайдер данных о этом факторе не мог подменить данные, данные часто менялись (если нужно, например, получить числа уже «сейчас», а следующий биткоин-блок будет только через 10 минут), обладали достаточной длиной (у курса и температуры крайне мало бит и можно предсказать промежуток, что даёт нам возможность потенциально «подсдадить» кучу народа, чтобы выпало в подставных).
Заранее неизвестный фактор это хорошо. Но нужно искать, чтобы: провайдер данных о этом факторе не мог подменить данные, данные часто менялись (если нужно, например, получить числа уже «сейчас», а следующий биткоин-блок будет только через 10 минут), обладали достаточной длиной (у курса и температуры крайне мало бит и можно предсказать промежуток, что даёт нам возможность потенциально «подсдадить» кучу народа, чтобы выпало в подставных).
Под нашим множеством я подразумеваю — все возможные значения закодированных чисел, ответственна за это математика.
Ну я биткоин и не предлагала, всего лишь указала на возможность использования любого неизвестного заранее значения. Естественно можно использовать и несколько одновременно, тогда количество бит будет любым.
По поводу часто меняющихся — это тоже не проблема. Курс на биржах (в том числе биткоиновых) меняется ооочень быстро. Если не устраивает 1 биржа, возьмите 100 + 100 котировок, даже если одна не сработает (биржа ВНЕЗАПНО закроется) — ничего страшного, еще полно в остатке.
Ну я биткоин и не предлагала, всего лишь указала на возможность использования любого неизвестного заранее значения. Естественно можно использовать и несколько одновременно, тогда количество бит будет любым.
По поводу часто меняющихся — это тоже не проблема. Курс на биржах (в том числе биткоиновых) меняется ооочень быстро. Если не устраивает 1 биржа, возьмите 100 + 100 котировок, даже если одна не сработает (биржа ВНЕЗАПНО закроется) — ничего страшного, еще полно в остатке.
Можно договориться взять хеш последнего блока bitcoin в день оглашения результатов.
Доя соц. сетей можно суммировать id участников и брать остаток от деления на кол-во участников. Просто для участников и крайне сложно устроить победу нужному человеку организаторами.
Этот вариант легко взламываем. Просто перед самым закрытием конкурса добавляем своих подсадных участников так, чтобы изменить итоговый результат.
Изменить результат легко, но изменить на нужное значение весьма сложно. Т.к. для этого придется иметь очень много фэйковых аккаунтов и подбирать. В среднем надо в 2 раза меньше фэйков, чем участников, чтобы среди них нашелся нужный id. Учитывая, что в ВК нужно подтверждение по смс, еще сложнее мухлевать.
Если можно сделать много подсадных участников, то тогда вообще нет смысла париться с какими-то протоколами выбора честного случайного победителя. Потому что даже при честном использовании random.org можно просто добавить столько фейковых участников, сколько потребуется и склонить рандом в свою сторону на сколь угодно близкое к 1 значение :)
А смысл? Можно выбрать случайное число ДО конкурса, пожать rar'ом с паролем, в конце просто раскрыть пароль. И самое ближайшее к этому числу назвать победителем.
Как вариант — сделать сервис, на котором произойдёт регистрация участников. Опубликовать заранее ссылку на конкурс в группе, чтобы по ней регистрировались, и установить дату окончания конкурса. Затем в назначенное время поьэтой ссылке на странице отобразится случайный победитель. Главное здесь — чтобы этот сервис голосований принадлежал третьей стороне.
Захотелось это реализовать :)
Тот, кто раскрывает свой секрет последним, может отказаться его раскрывать, увидев что победитель не он
Хотя можно просто выкидывать из конкурса тех, кто отказывается раскрывать секрет
Это проблема, да. Придётся начинать всю операцию сначала (ибо тогда мы можем подсадить какое-то кол-во своих и решить, кто откажется раскрывать, а кто нет и повлиять на итог).
Но в случае с получением приза — мы ему гарантированно его ему не даём (хотя и так и так, это плохо), баним и клеймим позором (и возможно его не берут и в другие конкурсы из-за этого).
А в случае с негативным вариантом (когда тот, кто выпадет, например, «дежурит» по чём-то), просто считаем, что выбран он.
И похоже проблема ещё и с групповым сговором, когда ещё не конкретный последний, а группа видит, что один из них не может выиграть и отказываются вскрываться. Тут тоже отбираем профит, баним локально. При повторении такого поведения — глобально.
Нужно как-то это решить бы.
Но в случае с получением приза — мы ему гарантированно его ему не даём (хотя и так и так, это плохо), баним и клеймим позором (и возможно его не берут и в другие конкурсы из-за этого).
А в случае с негативным вариантом (когда тот, кто выпадет, например, «дежурит» по чём-то), просто считаем, что выбран он.
И похоже проблема ещё и с групповым сговором, когда ещё не конкретный последний, а группа видит, что один из них не может выиграть и отказываются вскрываться. Тут тоже отбираем профит, баним локально. При повторении такого поведения — глобально.
Нужно как-то это решить бы.
Вариант проще — сайт, вроде random.org но с небольшим отличием — можно создать генератор с публичной ссылкой и возможностью выбрать число позже и только определнное количество раз (например, только один раз). Лимит на генерацию и количество попыток видно всем желающим.
Например, в воскресенье прием заявок прикратился, организаторы всех пересчитали и на random.org создали генератор под это событие. Лимит на генерацию — 1. Ссылка на этот генератор публикуется на странице организаторов. Через пару дней запускается рэндом, выбирается победитель. Подменить результаты уже не получится — все видели ссылку.
Например, в воскресенье прием заявок прикратился, организаторы всех пересчитали и на random.org создали генератор под это событие. Лимит на генерацию — 1. Ссылка на этот генератор публикуется на странице организаторов. Через пару дней запускается рэндом, выбирается победитель. Подменить результаты уже не получится — все видели ссылку.
Если генерировать рандом именно в момент определения победителя — нужно доверие к этому сервису. Если же в момент создания страницы — то нужно во-первых доверие к схеме (например, сервис может иметь базу солей, плюс множество коллизий к этой соли и выбранному рандому), а во-вторых это неприменимо к варианту, когда рандом нужен прямо сейчас, ибо тогда нужно доверие к этому сервису.
Алсо, если организаторы в сговоре с сервисом и знают, какой рандом выпадет — ничего не мешает, например, вклиниться на нужную позицию в список по признаку, по которому идёт сортировка.
Алсо, если организаторы в сговоре с сервисом и знают, какой рандом выпадет — ничего не мешает, например, вклиниться на нужную позицию в список по признаку, по которому идёт сортировка.
Я могу в онлайне транслировать видео с камеры, где я демонстрирую всем себя, сегодняшнюю газету, показываю городские часы, показываю /etc/hosts, затем открываю random.org и генерирую число, которое оказывается выбранным мной.
А всё потому что моя ОС была запущена в виртуальной машине и изменён /etc/hosts в машине выше, или вообще на роутере.
megarandom с ссылкой таким не страдает, но это посредник, которому мы должны довериться.
А всё потому что моя ОС была запущена в виртуальной машине и изменён /etc/hosts в машине выше, или вообще на роутере.
megarandom с ссылкой таким не страдает, но это посредник, которому мы должны довериться.
Когда-то разрабатывал онлайн-казино, рандомил целое число от 0 до 36, солил случайной длинной солью, добавлял ник пользователя, дату и т. п. и в начале раунда («делайте ставки, господа») публиковал md5 хэш (тогда он считался надежным) числа и соли и принимал ставки. После «ставки сделаны» открывал число и соль, рядом ссылка на «ман» с описанием алгоритма, ссылками на онлайн-расчтеты, коды на нескольких языках, чтобы каждый мог убедиться, что а) хэш правильный, б) предрасчёт коллизий затруднителен
Подобным способом можно делать и выбор игрока из неизвестного количества, выдав заранее float число и присваивая целые номера участникам. Претензии могут быть только если число будет малым, так что преимущество будет у первых участников, которых может зарегистрировать организатор. Способ борьбы — выбирать не из отсортированного списка номеров, а из отсортированного списка хэшев номеров.
Подобным способом можно делать и выбор игрока из неизвестного количества, выдав заранее float число и присваивая целые номера участникам. Претензии могут быть только если число будет малым, так что преимущество будет у первых участников, которых может зарегистрировать организатор. Способ борьбы — выбирать не из отсортированного списка номеров, а из отсортированного списка хэшев номеров.
Оффтопа ради: не секундант, часом?
Можно даже целое число генерировать, его тоже можно нормализовать. А путь борьбы с нечестным организатором я описал ниже.
Можно и достаточно большое целое, если оно генерируется «нативно», без преобразования из плавающего. Но именно нормализация, а не взятие остатка от деление на число претендентов, как очень часто встречается в играх. Можно вообще случайную строку нормализовывать. Если же преобразование есть, пускай и на уровне библиотеки, то лучше брать плавающее, чтобы избежать возможных побочных эффектов.
1) Генерируем случайное число любым способом.
2) Считаем от него хеш. Можно с солью.
3) Публикуем хеш, начинаем принимать заявки.
4) Как только закончили принимать заявки — нормализуем наше число до 1..<кол-во участников>, узнаем победителя.
5) Публикуем число, соль если есть. Все честно, т. к. генерировали число заранее.
Это, правда, потребует публикации списка участников в правильном порядке, однако этого просто добиться. Если есть недоверие к сгенерированному вначале числу, то собираем любую информацию о заявках (имя пользователя, текст заявки и т. п.), конкатенируем её, считаем хеш, соединяем с нашим числом и используем это как сид для генератора. Последний не сможет подогнать значение под себя, потому что ему неизвестно изначальное число. Организатор не сможет потому, что неизвестен хеш от заявок. Изменить начальное число нельзя, потому что хеш уже опубликован. Все открыто и прозрачно.
2) Считаем от него хеш. Можно с солью.
3) Публикуем хеш, начинаем принимать заявки.
4) Как только закончили принимать заявки — нормализуем наше число до 1..<кол-во участников>, узнаем победителя.
5) Публикуем число, соль если есть. Все честно, т. к. генерировали число заранее.
Это, правда, потребует публикации списка участников в правильном порядке, однако этого просто добиться. Если есть недоверие к сгенерированному вначале числу, то собираем любую информацию о заявках (имя пользователя, текст заявки и т. п.), конкатенируем её, считаем хеш, соединяем с нашим числом и используем это как сид для генератора. Последний не сможет подогнать значение под себя, потому что ему неизвестно изначальное число. Организатор не сможет потому, что неизвестен хеш от заявок. Изменить начальное число нельзя, потому что хеш уже опубликован. Все открыто и прозрачно.
Хеш с числом опубликован. Организатор знает число и может влиять на заявки (добавляя своих людей). В итоге получает власть над результатом.
Для этого им придется решить задачу, подобную тем, что используется в bitcoin (получить хеш в определенном диапазоне). Причем, в отличие от bitcoin их данные еще и выглядеть не должны подозрительно :) А если мы ограничим все именами или id вконтакте/facebook/twitter, а в качестве хеша возьмем медленный и тяжелый scrypt то провернуть такое статистически станет очень трудно.
Мы в любом случае генерируем число в некоем диапазоне. Нормализация работает по определению так: скажем, мы выбрали 75 в диапазоне 0..4294967296 (2^32). Участников, как мы узнали потом — 580. мы разбиваем наш диапазон на 580 равных участков и смотрим номер участка, в который попало число 75.
Ну и как я написал, можно еще считать хеш от заявок, которые можно посчитать только в конце и они не полностью зависят от организатора. И тут чтобы подогнать свои аккаунты под ситуацию им нужно чтобы генератор случайных чисел, при взятии в качестве сида изначального числа + конечного хеша попадал в четко нужный участок. При этом заявки они могут только добавлять (т. к. порядок должен быть прозрачным) и они должны состоять из неподозрительного текста (нельзя взять случайные байты, т. к. их замысел быстро раскроется). При использовании стойкой и медленной хеш-функции это практически невозможно.
Ну и как я написал, можно еще считать хеш от заявок, которые можно посчитать только в конце и они не полностью зависят от организатора. И тут чтобы подогнать свои аккаунты под ситуацию им нужно чтобы генератор случайных чисел, при взятии в качестве сида изначального числа + конечного хеша попадал в четко нужный участок. При этом заявки они могут только добавлять (т. к. порядок должен быть прозрачным) и они должны состоять из неподозрительного текста (нельзя взять случайные байты, т. к. их замысел быстро раскроется). При использовании стойкой и медленной хеш-функции это практически невозможно.
По крайней мере выбор останется случайным. А добавление «фэйков» можно исключить только путем физической верификации и доверием к его организаторам, и то «дропы» могут верифицироваться за бутылку в пользу организаторов.
Мне как-то раз понадобилось приз отправить рандомному человеку из группы вк. Я написал пост:
1. Оставьте любой коммент под постом.
2. Всех прокомментировавших я к полуночи упорядочу в массив
3. На следующий день возьмем семизначное число, где
3.1 Первая цифра будет 1
3.2 Вторая цифра будет взята как последняя цифра индекса Доун-Джонсона на завтрашний день
3.3 Третья цифра будет взята как последняя цифра индекса S&P на завтрашний день
…
4. Получившиеся число поделям на кол-во участников. Возьмем остаток от деления. Это будет номер победителя
5. Если вы читаете это и ничего не поняли, кликните на область комментирования, чтобы оно стало активным, затем просто наклоните голову посильнее, чтобы она соприкоснулась с клавиатурой, а после — нажмите «Enter».
1. Оставьте любой коммент под постом.
2. Всех прокомментировавших я к полуночи упорядочу в массив
3. На следующий день возьмем семизначное число, где
3.1 Первая цифра будет 1
3.2 Вторая цифра будет взята как последняя цифра индекса Доун-Джонсона на завтрашний день
3.3 Третья цифра будет взята как последняя цифра индекса S&P на завтрашний день
…
4. Получившиеся число поделям на кол-во участников. Возьмем остаток от деления. Это будет номер победителя
5. Если вы читаете это и ничего не поняли, кликните на область комментирования, чтобы оно стало активным, затем просто наклоните голову посильнее, чтобы она соприкоснулась с клавиатурой, а после — нажмите «Enter».
О, о большом наборе источников внешних данных я не подумал, это фиксит проблемы из http://habrahabr.ru/post/214325/#comment_7368171
Не работает только в постапокалиптическом мире и при ну совсем громадном заговоре.
Не работает только в постапокалиптическом мире и при ну совсем громадном заговоре.
Совсем громадный заговор менее вероятен намерений организаторов отправлять какой-либо приз вообще. Если вы думаете глобально, то источники рандома нужно брать в разных странах и в узкие промежутки времени.
Лучше использовать мониторируемые в научных целях естественные источники рандома, например значения уровней космических излучений, напряженность магнитного поля планеты и т. д.
4. Лучше нормализовывать, а не брать остаток от деления. Ну и в вашей схеме нет защиты от «дабл постов», в том числе с фэйковых аккаунтов. Но её вообще сложно реализовать без физической верификации.
Что такое нормализация в этом контексте?
Лучше нормализовывать, а не брать остаток от деления
Нам нужно отобразить дискретное значение из ГСЧ m∈[0..M-1] на выбранного участника n∈[0..N-1], N≤M.
И тут без разницы, взять формулу
n = m mod Nили
n = trunc(m*N/M)всё равно у некоторых участников вероятность выигрыша немного выше. Если M mod N > 0, справедливое отображение построить невозможно.
Не могу утверждать, но кажется, что при n = trunc(m*N/M) распределение будет более равномерным.
Возьмите карандаш, бумагу и проверьте на N=3, M=5.
Это очевидно с т.з. множеств — нельзя разделить множество из 5 элементов на 3 множества равной мощности.
Алгоритм с mod оптимален. Мне кажется, улучшить его нельзя.
Это очевидно с т.з. множеств — нельзя разделить множество из 5 элементов на 3 множества равной мощности.
Алгоритм с mod оптимален. Мне кажется, улучшить его нельзя.
Берем N = 100, m∈[0..110]. В результате в n будут в два раза чаще попадаться значения 0..10, чем значения 11..99. Это определенно не равномерно.
Выше показали, что есть разница. То есть и нормирование не идеально, но оно более равномерно.
Что показали? Просто задваиваться будут не 0-9, а 0,10,20,..,90.
Вот пруф:
Выдача:
Например как получается 2 раза десятка:
Два раза ноль:
Вот пруф:
WITH nums(n) AS (
SELECT 1
UNION ALL
SELECT n+1 FROM nums WHERE n < 110
),
VOTES as (SELECT top 110 n-1 as M, (n-1)*100/110 as N FROM nums ORDER BY n)
select N, count(*) from VOTES group by N having count(*) > 1
OPTION (MAXRECURSION 110)Выдача:
N (No column name)
0 2
10 2
20 2
30 2
40 2
50 2
60 2
70 2
80 2
90 2Например как получается 2 раза десятка:
trunc(11*100/110)=trunc(12*100/110)=10.Два раза ноль:
trunc(0*100/110)=trunc(1*100/110)=0.Вот только мне никак не угадать, какие номера удвоятся если я не знаю сколько всего номеров будет в конце. В случае же использования mod, я всегда четко знаю, что чем меньше мой порядковый номер, тем больше шансы.
То есть, на N=100,M=100 как mod, так и «нормализация» даёт 10 человек у которых вдвое больше вероятность выигрыша. Просто номера этих людей разные
Итак, задача сводится к тому, чтобы:
1. Получить надежный источник энтропии.
2. Прошлые значения может проверить любой желающий.
3. Этот источник был независим от заинтересованных лиц, то есть независим от подтасовок.
Конечно, если цена вопроса невысока, например, это какой-нибудь местный конкурс, то источником энтропии могут быть сами люди. Можно взять, например, данные по курсу акций на какой-либо крупной бирже после закрытия торгов, и получить хеш от совокупной стоимости акций, потом этот хеш будет использоваться для получения результирующего значения. Так как результаты торгов жестко зафиксированы и опубликованы, полученное в прошлом случайное значение легко проверяется.
Но, скажем, что делать, если цена вопроса очень высока? Допустим, человечество пришло к демархии, и случайным образом выбирается президент и парламент планеты. Вот…
Тогда источником энтропии может быть природа. Значения (с максимально возможным числом знаков после запятой, но исключая влияние погрешности измерений) солнечной активности, геомагнитной активности, и т.д. Брать значения от надежных лабораторий, которые публикуют такую информацию. Можно брать совокупность таких параметров и считать хеш. Так как лабораторий много по всему миру, подделать этот результат так просто не получится.
1. Получить надежный источник энтропии.
2. Прошлые значения может проверить любой желающий.
3. Этот источник был независим от заинтересованных лиц, то есть независим от подтасовок.
Конечно, если цена вопроса невысока, например, это какой-нибудь местный конкурс, то источником энтропии могут быть сами люди. Можно взять, например, данные по курсу акций на какой-либо крупной бирже после закрытия торгов, и получить хеш от совокупной стоимости акций, потом этот хеш будет использоваться для получения результирующего значения. Так как результаты торгов жестко зафиксированы и опубликованы, полученное в прошлом случайное значение легко проверяется.
Но, скажем, что делать, если цена вопроса очень высока? Допустим, человечество пришло к демархии, и случайным образом выбирается президент и парламент планеты. Вот…
Тогда источником энтропии может быть природа. Значения (с максимально возможным числом знаков после запятой, но исключая влияние погрешности измерений) солнечной активности, геомагнитной активности, и т.д. Брать значения от надежных лабораторий, которые публикуют такую информацию. Можно брать совокупность таких параметров и считать хеш. Так как лабораторий много по всему миру, подделать этот результат так просто не получится.
Я не знаю, почему вам всем так хочется брать данные из внешней среды.
Все алгоритмы, использующие внешние данные ненадёжны по определению (приставив пистолет к виску хотя бы одного учёного из одной лаборатории мы получаем власть над итогом), не могут применяться бесконечное количество раз в конечный промежуток времени в теории (данные измеряются с какой-то частотой и если наши потребности выше этой частоты — у нас проблемы), а так же не работают в вакууме, когда у нас нет ничего, кроме группы людей, которая хочет получить рандома.
Все алгоритмы, использующие внешние данные ненадёжны по определению (приставив пистолет к виску хотя бы одного учёного из одной лаборатории мы получаем власть над итогом), не могут применяться бесконечное количество раз в конечный промежуток времени в теории (данные измеряются с какой-то частотой и если наши потребности выше этой частоты — у нас проблемы), а так же не работают в вакууме, когда у нас нет ничего, кроме группы людей, которая хочет получить рандома.
Немного оффтоп:
Лично меня больше заинтересовало это:
Сразу вспомнилась задача, которую хотел решить ещё в 9 классе школы:
Нужно составить алгоритм написания школьного расписания, учитывая количество преподавателей, график их работы и количество предметов у каждого класса. Учитывая что классов может быть разное количество, преподаватели у многих общие, нельзя ставить школьникам в один день 2 урока, а в другой 10 (т.е. всё должно быть примерно равномерно), и в середине дня школьникам окно в расписании тоже не поставишь.
За ненадобностью про задачу давно забыл, но прочитав эту строчку — вспомнил и стало интересно. Может сейчас я бы и смог что-то придумать, но если есть готовые решения — с радостью послушал бы.
Лично меня больше заинтересовало это:
(по поводу «правильных» графиков дежурств я бы тоже рассказал)
Сразу вспомнилась задача, которую хотел решить ещё в 9 классе школы:
Нужно составить алгоритм написания школьного расписания, учитывая количество преподавателей, график их работы и количество предметов у каждого класса. Учитывая что классов может быть разное количество, преподаватели у многих общие, нельзя ставить школьникам в один день 2 урока, а в другой 10 (т.е. всё должно быть примерно равномерно), и в середине дня школьникам окно в расписании тоже не поставишь.
За ненадобностью про задачу давно забыл, но прочитав эту строчку — вспомнил и стало интересно. Может сейчас я бы и смог что-то придумать, но если есть готовые решения — с радостью послушал бы.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Концепт «правильного» определения случайного победителя