Рандомный алгоритм что это
Что такое ГСЧ – как работает генератор случайных чисел
Алгоритм генератора случайных чисел часто используется в видеоиграх, где он устанавливает разные результаты каждый раз, когда его запускают. Возможно, вы заметили, что даже если вы играете на одном уровне в игре, каждый раз, когда вы пытаетесь выполнить миссию, он не будет одинаковым. Различия не будут наблюдаться в локации или требованиях к миссии, но они будут наблюдаться в количестве приближающихся врагов и областях их появления, изменениях климата и различных препятствиях, которые встречаются между ними. Это делает игру более захватывающей и интересной.
В противном случае, после нескольких попыток игра покажется скучной, так как вы сможете предсказать события, которые произойдут дальше. Это может показаться простым, но для компьютера – генерировать случайные числа – это сложная задача, требующая следовать точным инструкциям, закодированным в нём.
Истинный ГСЧ против псевдо ГСЧ
Есть два типа генераторов случайных чисел: истинные и псевдо.
Какие приложения используют ГСЧ
Не во всех играх используется генератор случайных чисел, что делает их менее конкурентоспособными и часто утомительными, однако, новые игры почти всегда идут с генератором случайных чисел. Многие приложения и игры выигрывают от случайности, поскольку они могут приносить интерес и прибыль только в том случае, если они случайны:
Помимо игровых приложений, есть код случайных чисел в JavaScript, используемый разработчиками и кодировщиками во всём мире для включения генератора случайных чисел в их программы. У Google есть свой очень интересный инструмент, который также основан на теории случайных чисел JavaScript и может генерировать случайные числа. Этот инструмент может пригодиться, когда вы играете в игры с друзьями и семьей. Чтобы посмотреть ГСЧ Google, нажмите здесь.
Манипуляции с ГСЧ
Я уже обсуждал различия между истинным ГСЧ и псевдо ГСЧ и тот факт, что в играх используется псевдо ГСЧ, основанный на алгоритме. Некоторые увлеченные геймеры используют утилиты эмуляции для анализа игр и выявления лазеек, которые можно использовать для управления результатами, даже если используется алгоритм генератора случайных чисел.
ГСЧ на основе алгоритма использует начальное число, которое представляет собой комбинацию определенных факторов и генерирует результат в игре. Это применяемые законы математики, и поскольку 1+1 всегда равно 2, аналогично, если известны факторы в игре, которые приносят желаемый результат, то вы всегда можете достичь того же результата.
Например, если игра требует от игрока выбрать определенного персонажа с определенными усилениями, и результатом будет легкая битва с боссом, то этот шаблон будет постоянным, и все, кто выберет одни и те же варианты, будут иметь одинаковые результаты. Но, для обычного игрока это было бы невозможно, и псевдо-ГСЧ всегда казался бы истинным ГСЧ.
Почему геймеры ненавидят ГСЧ
Геймеров можно разделить на соревнующихся игроков, спидраннеров и средних игроков. Любой конкурентоспособный игрок, овладевший техникой игры и движениями, захочет бросить вызов другим игрокам и побеждать на основе навыков и, несомненно, возненавидит игру, если на результат повлияет генератор случайных чисел. Точно так же спидраннер хотел бы завершить игру как можно скорее, но алгоритм генератора случайных чисел включает тормоза, создавая каждый раз неизвестные и неожиданные сценарии в игре.
В идеале геймеры хотели бы уменьшить количество случаев, когда они сталкиваются со средством генерации случайных чисел в игре, чтобы держать весь игровой процесс и результат под своим контролем. Но, это возможно лишь до определенной степени. И когда геймер часами осваивает игрового персонажа и его движения, он больше всего расстраивается, когда случается что-то случайное, и вся стратегия нарушается. Иногда это тоже действует как благословение, но обычно это проклятие.
Кто такой RNGesus?
Обычные игроки, которые играют только для того, чтобы развлечься или скоротать время, не заботятся о результате игры. Но, опытные профессиональные игроки ненавидят проигрывать только потому, что удача была не в их пользу.
Игроки, которые проигрывают, часто винят в своих поражениях злой ГСЧ, который выгоден их противникам. Там где зло, должен быть Бог – RNGesus.
Среди геймеров во всем мире появился новый термин, RNGesus, который больше соответствует игре слов с «Иисусом». Поскольку Иисус Христос считается нашим спасителем в реальном мире, RNGesus – это вообразимая сущность, созданная для спасения игроков от пагубных последствий ГСЧ. Это нигде не доказывается, но началось как миф, а теперь распространилось по игровому сообществу, как лесной пожар.
Окончательный вердикт по ГСЧ – хорошо или плохо?
На этот вопрос сложно ответить, и определенно не может быть одного и того же ответа для всех. В то время как среднестатистические геймеры утверждают, что это хорошо, другим нравится соревновательный дух.
Алгоритм генератора случайных чисел действительно сохраняет непредсказуемость и интересность каждый раз, когда вы играете на одном уровне. Он стал важной частью многих игр, предлагая разнообразие, например, головоломки, карточные игры, ролевые игры и многие другие. Но, для геймеров, которые верят в навыки как в единственный способ пройти игру, ГСЧ подрывает их потенциал, когда вытаскивает что-то случайное из коробки.
Игры предназначены для развлечения и удовольствия. Если у вас хороший ГСЧ, вы сможете получить лучшие варианты, несмотря на низкие шансы. В случае плохого ГСЧ, вы получите худший результат, даже если вы играли в игру именно так, как должно. Правда в том, что это не то, что можно воспринимать так серьёзно, особенно если оно основано на алгоритме генератора случайных чисел.
Случайные числа и децентрализованные сети: практическое применение
Введение
«Генерация случайных чисел слишком важна, чтобы оставлять её на волю случая»
Роберт Кавью, 1970
Эта статья посвящена практическому применению решений, использующих коллективную генерацию случайных чисел в недоверенной среде. Если кратко — как и для чего используется рандом в блокчейнах, и немного про то, как отличить “хороший” рандом от “плохого”. Генерация действительно случайного числа является крайне непростой проблемой даже на отдельном компьютере, и давно изучается криптографами. Ну а в децентрализованных сетях генерация случайных чисел еще более сложна и важна.
Именно в сетях, где участники не доверяют друг другу, возможность сгенерировать неоспоримое случайное число позволяет эффективно решать множество важнейших задач и значительно улучшить уже существующие схемы. Причем азартные игры и лотереи тут вовсе не являются целью номер один, как сначала может показаться неискушенному читателю.
Генерация случайных чисел
Компьютеры не умеют сами производить случайные числа, для этого им требуется помощь извне. Компьютер может получать некоторое случайное значение используя, к примеру, движения мышью, количество использованной памяти, паразитные токи на контактах процессора и множество других источников, называемых источниками энтропии. Сами эти значения не совсем случайны, так как находятся в определенном диапазоне или имеют предсказуемый характер изменений. Чтобы превратить такие числа в действительно случайное число в заданном диапазоне, к ним применяют криптопреобразования, чтобы из неравномерно распределенных значений источника энтропии получить равномерно распределенные псевдослучайные значения. Полученные значения называют псевдослучайными, так как они не являются истинно случайными, а детерминистически произведены из энтропии. Любой хороший криптоалгоритм, зашифровывая данные производит шифротексты, которые статистически должны быть неотличимы от случайной последовательности, так что для производства рандома можно брать источник энтропии, который обеспечивает лишь хорошую неповторяемость и непредсказуемость значений даже в небольших диапазонах, остальную часть работы по рассеиванию и перемешиванию битов в результирующем значении возьмет на себя алгоритм шифрования.
Чтобы завершить краткий ликбез, добавлю, что генерация случайных чисел даже на одном устройстве — один из столпов обеспечения безопасности наших с вами данных, сгенерированные псевдослучайные числа используются при установлении защищенных соединений в различных сетях, для генерации криптографических ключей, для балансировки нагрузки, контроля целостности, и еще для множества применений. Безопасность многих протоколов зависит от возможности сгенерировать надежный, непредсказуемый извне рандом, сохранить его, и не раскрывать его до следующего шага протокола, иначе безопасность будет поставлена под угрозу. Атака на генератор псевдослучайных значений является крайне опасной и ставит под угрозу сразу все ПО, использующее генерацию рандомов.
Все это вы должны знать, если проходили базовый курс по криптографии, поэтому продолжим про децентрализованные сети.
Рандом в блокчейнах
В первую очередь я буду говорить про блокчейны с поддержкой смарт-контрактов, именно они могут в полной мере использовать возможности, предоставляемые качественным неоспоримым рандомом. Далее, для краткости, я буду называть эту технологию “Publicly Verifiable Random Beacons” или PVRB. Так как блокчейны — это сети, информацию в которой может проверить любой участник, ключевой частью названия является “Publicly Verifiable”, т.е. любой желающий может при помощи вычислений получить доказательство того, что полученное число, размещенное в блокчейне, обладает такими свойствами:
Любая возможность сговорившейся минорной группы участников произвести даже контролируемый чётный/нечётный рандом — дыра в безопасности. Любая возможность группы остановить выдачу рандома — дыра в безопасности. В общем, проблем много, и эта задачка не из легких.
Кажется, что наиболее важное применение для PVRB, это различные игры, лотереи, и вообще любые виду gambling-а на блокчейне. Действительно, это важное направление, но у рандома в блокчейнах есть применения и поважнее. Рассмотрим их.
Алгоритмы консенсуса
PVRB для организации сетевого консенсуса играет огромное значение. Транзакции в блокчейнах защищены электронной подписью, поэтому “атака на транзакцию” это всегда включение/исключение транзакции в блок (или в несколько блоков). А главной задачей алгоритма консенсуса является договориться о порядке этих транзакций и о порядке блоков, которые включают в себя эти транзакции. Также, необходимым свойством для реальных блокчейнов является финальность — возможность сети договориться о том, что цепочка до финализированного блока является окончательной, и никогда не будет исключена из за появления нового форка. Обычно, чтобы договориться о том, что блок является валидным и, главное, финальным, требуется собрать подписи с большинства производителей блоков (далее BP — block-producers), что требует как минимум доставить цепочку блоков на все BP, а подписи распространить между всеми BP. При росте числа BP, количество необходимых сообщений в сети экспоненциально растет, поэтому, алгоритмы консенсуса, требующие финальность, используемые например в pBFT-консенсусе Hyperledger, не работают с нужной скоростью, начиная уже с нескольких десятков BP, требуя огромного числа соединений.
Также, в реальных имплементациях, схема протокола сложнее — голосования за предлагаемые блоки проводятся в несколько этапов, чтобы поддерживать работу сети в случае пропуска блоков и проблем с сетью, но даже с учетом этого, алгоритмы консенсуса с использованием PVRB требуют существенно меньше сообщений между BP, что позволяет сделать их быстрее, чем традиционный PВFT, или различные его модификации.
Наиболее яркий представитель таких алгоритмов: Ouroboros от команды Cardano, который, как объявлено, обладает математически доказуемой стойкостью к наличию сговора среди BP.
В Ouroboros PVRB используется для определения так называемого “BP schedule” — расписания, согласно которому каждому BP назначается свой временной слот для публикации блока. Большим преимуществом использования PVRB является полное “равноправие” BP (согласно размерам их балансов). Честность PVRB гарантирует, что зловредные BP не могут контролировать расписание временных слотов, и, поэтому не могут манипулировать цепочкой, заранее подготавливая и анализируя форки цепочки, а для выбора форка достаточно полагаться просто на длину цепочки, не оперируя хитрыми способами вычисления “полезности” BP и “веса” его блоков.
Вообще во всех случаях, когда в децентрализованной сети нужно выбрать случайного участника, почти всегда лучшим выбором будет PVRB, а не детерминистический вариант на основе, к примеру, хеша блока. Без PVRB возможность повлиять на выбор участника ведет к появлению атак, в которых атакующий может, выбирая из нескольких вариантов будущего, выбирать следующего коррумпированного участника или сразу нескольких, чтобы обеспечить более весомую долю в принятии решения. Использование PVRB дискредитирует эти типы атак.
Масштабирование и балансировка нагрузки
PVRB может принести серьезную пользу также в задачах для снижения нагрузки, масштабирования платежей. Для начала имеет смысл ознакомиться со статьей Ривеста “Electronic Lottery Tickets as Micropayments”. Общая суть такова, что вместо того чтобы делать 100 платежей по 1c от плательщика получателю, можно сыграть в честную лотерею с призом 1$ = 100c, где плательщик при каждом платеже в 1c передает банку один из 100 своих “лотерейных билетов”. Один из этих билетов выигрывает банку 1$, и именно этот билет получатель может фиксировать в блокчейне. Самое важное, что остальные 99 билетов передаются между получателем и плательщиком без всякого внешнего участия, по приватному каналу и с любой нужной скоростью. Хорошее описание протокола на базе этой схемы в сети Emercoin можно прочитать здесь.
У этой схемы есть несколько проблем, например получатель может перестать обслуживать плательщика сразу же после получения выигрышного билета, но для множества особых применений, вроде поминутной тарификации или электронных подписок на сервисы, ими можно пренебречь. Главным же требованием, конечно, является честность проводимой лотереи, а для ее проведения совершенно необходим PVRB.
Выбор случайного участника крайне важен также для протоколов шардинга, целью которых является горизонтальное масштабирование цепочки блоков, позволяя разным BP процессить лишь свой scope транзакций. Это крайне сложная задача, особенно в вопросах безопасности при объединении шардов. Честный выбор случайного BP с целью назначения его ответственных за конкретный шард, как и в алгоритмах консенсуса — также задача PVRB. В централизованных системах шарды назначаются балансировщиком, он просто вычисляет хеш от запроса и отправляет необходимому исполнителю. В блокчейнах, возможность влиять на это назначение может вести к атаке на консенсус. Например, содержимое транзакций может контролироваться атакующим, он может контролировать какие транзакции попадают в контролируемый им шард и манипулировать цепочкой блоков в нем. Обсуждение проблемы использования случайных чисел для задач шардинга в Ethereum можно почитать здесь
Шардинг — это одна из самых амбициозных и серьезных задач в области блокчейн, ее решение позволит строить децентрализованные сети фантастической производительности и объема. PVRB — это лишь один из важных блоков, для ее решения.
Игры, экономические протоколы, арбитраж
Роль случайных чисел в игровой индустрии сложно переоценить. Явное использование в онлайн казино, и неявное при расчете эффектов того или иного действия игрока — всё это крайне сложные проблемы для децентрализованных сетей, где нет возможности положиться на центральный источник случайности. Но, случайный выбор может решать и многие экономические проблемы и помогать строить более простые и эффективные протоколы. Предположим в нашем протоколе имеют место диспуты насчет оплаты каких нибудь недорогих услуг, и эти диспуты происходят достаточно редко. В этом случае, если есть неоспоримый PVRB, клиенты и продавцы могут договориться о случайном разрешении диспутов, но с заданной вероятностью. К примеру с вероятностью 60% побеждает клиент, а с вероятностью 40% — продавец. Такой, с первой точки зрения абсурдный, подход позволяет автоматически решать диспуты с точно предсказуемой долей выигрышей/проигрышей, устраивающий обе стороны без всякого участия третьей стороны и ненужной траты времени. Более того, соотношение вероятностей может быть динамическим и зависеть от некоторых глобальных переменных. К примеру, если у компании дела идут хорошо, отмечается низкое число диспутов и высокая доходность, компания может автоматически сдвигать вероятность разрешения диспута в сторону клиент-ориентированности, к примеру 70/30 или 80/20, и наоборот, если диспуты отнимают много средств и являются мошенническими или неадекватными, можно сдвигать вероятность в другую сторону.
Большое количество интересных децентрализованных протоколов, таких как token currated registries, prediction markets, bonding curves и многие другие представляют собой экономические игры, в которых награждается хорошее поведение, и штрафуется плохое. В них часто встречаются проблемы безопасности, защиты от которых противоречат друг другу. То, что защищено от атаки “китов” с миллиардами токенов (“big stake”), уязвимо к атакам тысячами аккаунтов с небольшими балансами (“sybil stake”), и меры, принимаемые против одной атаки, например нелинейные комиссии, созданные для того, чтобы сделать работу большим стейком невыгодной, обычно дискредитируются другой атакой. Так как речь идет об экономической игре, соответствующие статистические веса можно рассчитать заранее, и просто заменить комиссии на рандомизированные с соответствующим распределением. Такие вероятностные комиссии реализуются крайне просто, если в блокчейне есть надежный источник рандома и не требуют никаких сложных вычислений, осложняя жизнь и китам и sybil-ам.
При этом необходимо продолжать помнить, что контроль над единственным битом в этом рандоме позволяет обманывать, уменьшая и увеличивая вероятности вдвое, так что честный PVRB — важнейшая составляющая таких протоколов.
Где найти правильный рандом?
В теории, честный случайный выбор в децентрализованных сетях позволяет обеспечить доказуемую безопасность почти любого протокола от сговора. Обоснование довольно простое — если сеть договаривается об одном бите 0 или 1, и среди участников менее половины являются нечестными, то, при достаточном количестве итераций, сеть гарантированно придет к консенсусу относительно этого бита с фиксированной вероятностью. Просто потому что честный рандом будет выбирать 51 из 100 участников в 51% случаев. Но это в теории, т.к. в реальных сетях, для обеспечения такого уровня безопасности, как в статьях, требуется множество сообщений между хостами, сложная многоходовая криптография, а любое усложнение протокола сразу же добавляет новые вектора атак.
Именно поэтому мы пока не видим в блокчейнах доказанно стойкого PVRB, который использовался бы уже достаточно времени, чтобы пройти испытания настоящими приложениями, множественными аудитами, нагрузками, и конечно, же, реальными атаками, без которых трудно назвать продукт по настоящему безопасным.
Тем не менее, есть сразу несколько перспективных подходов, они отличаются множеством деталей, и какой-то из них точно решит проблему. При современных вычислительных ресурсах, криптографическая теория способна довольно ловко превращаться в практические применения. В дальнейшем, мы с удовольствием расскажем об имплементациях PVRB: их сейчас несколько, каждая обладает своим набором важных свойств и особенностей в реализации, и за каждой стоит хорошая идея. Рандомом занимается не так много команд, и опыт каждой из них крайне важен для всех остальных. Надеемся, что наша информация позволит остальным командам двигаться быстрее, с учетом опыта предшественников.
Способы использования Math.random() в JavaScript
Math.random() — это один из API JavaScript. Это — функция, которая возвращает случайные числа. Диапазон возвращаемых чисел представлен значениями от 0 (включая 0, то есть, она может вернуть 0) до 1 (не включая 1, то есть — единицу она вернуть не может).
Эта функция чрезвычайно полезна при разработке игр, при описании анимаций, при создании наборов данных с использованием метода случайного выбора. Случайные числа применяются в процедуральном искусстве, при создании текстов и во многих других случаях. Эти числа можно использовать в веб-разработке, в мобильной разработке, в обычных настольных приложениях.
Вот пример, размещённый на CodePen, позволяющий генерировать случайные числа в диапазоне от 0 до 1 и от 0 до 10 (включая 0 и 10).
Пример использования Math.random()
Анимация
Вот пример, в котором Math.random() используется для создания анимации.
Музыка, сгенерированная компьютером
Вот проект, демонстрирующий пример использования Math.random() в деле создания компьютерной музыки.
Здесь за основу взята традиционная мелодия «Auld Lang Syne» («Старое доброе время»). Программа строит итоговую композицию, обрабатывая исходный материал по особому алгоритму, основанному на использовании случайных чисел.
Вывод случайного изображения
В данном проекте возможности генератора случайных чисел используются для выбора изображений.
Вывод изображения, выбранного случайным образом
Случайный фоновый цвет
Здесь можно найти проект, в котором показан случайный выбор фонового цвета.
Случайный выбор фонового цвета
Самое интересное происходит в этом фрагменте кода:
Эта функция возвращает случайное целочисленное значение из заданного диапазона. Она используется для настройки характеристик цветов, таких, как тон, насыщенность и светлота.
Если вас интересует вопрос случайного генерирования цветов — взгляните на этот материал.
Процедуральное искусство
Вот проект, в котором случайные числа используются для создания изображения по заданным правилам.
При построении этих необычных кривых функция Math.random() используется дважды. Первый раз — для выбора цветов градиента. Второй раз — для настройки максимального радиуса кривых. Это — прекрасный пример того, как при каждом запуске процесса создания изображения получается что-то новое.
Случайный выбор слов из заранее созданного списка
Здесь можно найти программу, которая выводит на экран слова, случайным образом выбираемые из заранее созданного массива.
Случайный выбор слов
Вот код, который используется для выбора слова:
Этот пример очень похож на тот, где на странице выводится изображение, выбранное случайным образом. Пожалуй, разработка подобной программы хорошо подойдёт новичкам, которые хотят попрактиковаться в работе с веб-технологиями.
Генератор ключей API
Вот проект, в котором случайные числа используются для создания ключей API.
Система для создания случайных ключей API
Это — пример использования генератора случайных чисел, имеющий практическое применение в разработке реальных приложений. Здесь для создания UUID (Universally Unique IDentifier, универсальный уникальный идентификатор) программа генерирует 16 случайных чисел. Такой UUID можно использовать в роли ключа для доступа к некоему API.
Вывод фрагментов текста с использованием переходов, сформированных случайными символами
Здесь можно найти проект, в котором случайные числа используются при выводе текстов.
Переходы между фразами, сформированные с использованием генератора случайных чисел
Игра «Камень, ножницы, бумага»
Здесь можно найти реализацию игры «Камень, ножницы, бумага».
Камень, ножницы, бумага
В этой классической игре Math.random() используется в качестве основы игровой логики. Компьютер делает ход, случайным образом выбирая один из трёх вариантов действий.
Генератор надёжных паролей
Вот программа, представляющая собой генератор надёжных паролей.
Генератор надёжных паролей
Заметки о Math.random()
▍По-настоящему ли случайны числа, которые выдаёт Math.random()?
Они, так сказать, не совсем случайны. Эта функция возвращает псевдослучайные числа. Алгоритм, на котором она основана, называется «генератор псевдослучайных чисел» (Pseudo-Random Number Generator, PRNG). Это значит, что последовательность выдаваемых им чисел может быть, в определённых условиях, воспроизведена.