В прошлой статье по верификации данных от клиента повествование было скомкано, какой-либо новой информации не присутствовало. В этой статье, скорее даже заметке, я попытаюсь подать информацию более целостно. Рассказ пойдёт о алгоритме (придумал его, когда размышлял на тему "как не дублировать игровую логику на клиенте и сервере") который позволяет избавиться от существенной части кода на стороне сервера. Применение его не безгранично, ниже описаны исключительные ситуации.
Алгоритм
Имеется сервер и множество клиентов . При создании игры, сервер создаёт приватный ключ для каждого клиента.
Как происходит выполнение действия (на примере перемещения юнита):
- Клиент отправляет серверу запрос со своим ;
- Сервер проверяет что клиент является активным игроком, т.е. ему принадлежит право хода. Проверка происходит сравнением ;
- Сервер рассылает запрос на остальные клиенты ;
- Каждый клиент при получении запроса, верифицирует его. (Проверяя может ли юнит переместиться на такое расстояние?);
- Клиент отправляет извещает сервер о своём решении;
- Сервер дождавшись верификации действия ото всех клиентов посылает подтверждение клиенту .
В виде анимации это выглядит:
Если представить ситуацию, что в игре сговорились и подменили данные все игроки кроме одного:
- На сервер приходит сообщение о не валидности действия от одного из клиентов;
- Сервер посылает запрос на отмену действия всем клиентам, кто его верифицировал, а так же клиенту который запрос инициировал.
Реализация
Опираться будем на пример из предыдущей статьи. Вынес изменения в отдельную ветку — исходый код. Архитектура кода не прорабатывалась, поэтому он всё еще годиться только как демка.
Главное что тут стоит заметить, снижение кол-ва кода на серверной стророне, в два раза! И чем больше будет проверок в игре, том больше выигрыш от алгоритма.
Ключевые изменения
Теперь при послуплении запроса на выполнение действий вы не проверяем его сами, а отсылаем другим игрокам:
for player in game.players:
if player.connection == conn: continue
await player.connection.send(json.dumps({
'request': data,
}))
Когда все игроки верифицируют действие, посылаем ответ игроку инициирующему действие.
if len(game.active_action.verified_list) == game.COUNT_PLAYERS - 1:
await game.get_active_player().connection.send(json.dumps({
'response': True,
'action': game.active_action.type,
}))
На стороне клиета главное изменение — это верификация данных, когда об этом просит сервер:
if ( data.request.action === 'move' ) {
verified = G._is_empty( ... ) && G._is_distance_available( ... );
G._moving( data.request.new_position );
if ( verified ) {
...
socket.send( JSON.stringify({
'game_key': game_key,
'private_key': private_key,
'verified': true, // Высылаем ответ серверу
'next_player_public_key': data.request.next_player_public_key,
}))
} ...
В каких ситуациях использовать алгоритм нельзя?
Уменьшение кол-ва кода, а особенно отсутствие дублирования. Красота. Легче поддерживать, меньше вероятность ошибки, да что я рассказываю сами всё знаете. Но, всё было бы нереально без "но". Алгоритм использовать нельзя в случае:
- Генерации случайных событий;
- Генерации начального состояния мира игры.
Генерация случайных событий
Что под этим понимается? Например появление различных монстров или вещей на карте и т.д.
Если у юнита есть диапазон урона, т.е. юнит может нанести от 10 до 20 единиц урока, то величину его рассчитать на клиенте нельзя. Тут не поможет проверка что значение подпадает под равномерное распределение, т.к. для одного конкретного запроса в общем случае нельзя проверить сформировал ли клиент значение урона 20 самостоятельно или оно было рассчитано алгоритмом.
Начальное состояние мира игры
Создание начального состояния также опирается на генерацию случайных событий, поэтому подпадает под вышеописанное.
Заключение
На этом всё. Надеюсь что эта статья, хоть и меньшая по объему, но более содержательная.
Комментарии (43)
GerrAlt
23.01.2017 19:40+1У игры получается занятная логика, грубо говоря «если все игроки согласны что конь может пойти e2-e4 то зачем портить людям игру»
degorov
23.01.2017 21:53+1Ну так-то да, но для этого должно получиться так, чтобы все читеры каким-то способом всегда попадали на матч только друг с другом. Не, ну если они так и хотят играть и в игре предусмотрено лобби — флаг им в руки — можно просто при расчёте рейтинга (если в игре вообще такое предполагается) не учитывать матчи, сыгранные одним и тем же набором игроков и всё — проблема решена.
Grief
23.01.2017 20:06+3Я категорически не согласен с тем, что написано в статье, правда, не вижу в ней ничего страшного, подобные мысли появлялись у меня самого. Но тут уже написали (и, возможно, напишут еще) о проблемах:
Если это real-time (что, судя по предыдущей статье, не так):
- Увеличение задержки — это все. Люди стараются сделать фактическую задержку меньше сетевой всякими предсказаниями, эвристиками, а вы предлагаете сразу ее минимум удвоить.
- Возможность клиента задерживать данные. Нет надежного способа отличить клиента, который задерживает данные нарочно от того, кто пользуется мобильным интернетом от мегафона.
- Идея заставить обрабатывать клиенты "чужие" данные вообще сама по себе сомнительна, не только потому что она увеличивает энтропию, а потому что увеличивает требования к вычислительной мощности клиента. Хорошо выглядит на картинке — move > send > accepted > confirm, но самый интересный шаг с проверкой данных далеко не всегда тривиален. Например, это может быть просчет коллизий с объектами, которые клиент еще "не видит".
Если же это пошаговая игра, то это просто overkill. Я не очень понял задачу, какую вы решаете, но если я угадал и главной проблемой вы видите то, что код сервера и клиента копи-пастится, то это легко решается техническими средствами. Достаточно вместе с dedicated-сервером запускать на сервере одного клиента и использовать его для валидации. Выделить код в библиотеку, дать клиенту IPC для взаимодействия с локальным сервером, много чего можно придумать.
Но, вообще, валидации на клиенте быть и не должно, тогда и дублироваться будет нечему. В шутерах клиент отправляет на сервер ввод (отметки времени начала и окончания действий типа "движение", "действие", "огонь"), а сервер в ответ присылает состояние мира. В стратегиях типа starcraft делается плюс-минус также. В пошаговых стратегиях, где нет временных отметок, клиент может присылать действия, которые он совершает на протяжении кода и также принимать изменения состояния игрового мира. Зачем что-либо валидировать?
RokkerRuslan
23.01.2017 20:22Про еще одного клиента — интересное решение, но по остальному, конечно, сомнительно. Если это real-time — нет, не real-time.
а потому что увеличивает требования к вычислительной мощности клиента — вот тут конечно не согласен. Ход в пошаговой игре — расчет пару десятков чисел. Чисто формально, да, операций больше, но реально ресурсов тратиться не больше чем на обработку движения мыши.Grief
23.01.2017 20:25Стоит ли тогда городить сыр-бор ради этих пары десятков чисел? И почему эта пара десятков чисел не может валидироваться только сервером?
RokkerRuslan
23.01.2017 20:42Возможно и не стоит. Я и писал статью чтобы услышать мнение, и ваш комментарий очень полезен.
degorov
23.01.2017 21:50+1Вы сами себе противоречите. Если увеличение задержки — это всё, то тогда без валидации на клиенте не обойтись, иначе как Вы отрендерите результат нажатия на кнопки на клиенте сразу же? Проверить не мешает ли игроку идти стена, например — это тоже валидация, разумеется. По Вашей логике перед тем как определить, что игрок не может идти сквозь стену, шутер должен получить инфу об этом с сервера — так не делается ни в шутерах ни в старкрафте.
Grief
23.01.2017 22:32Да, вы правы, я сознательно опустил этот момент с некоторыми проверками на, так как они являются частью input prediction и, вообще говоря, не являются необходимыми. К примеру, в движке source они легко выключаются на клиенте командой
cl_predict 0
degorov
23.01.2017 21:56Вполне рабочий вариант тем более для пошаговой игры. Сам планировал делать что-то подобное. Правда меня не интересовало количество кода на серверной стороне — в конце концов при реализации сервера и клиента на одном и том же языке при грамотном проектировании этот код был бы одинаковый ;) А вот тот факт, что серверные мощности оплачиваются в случае любительской поделки из кармана создателя — вполне себе аргумент за то, чтобы сервер участвовал в процессе игры минимально = просто сводил игроков вместе и фиксировал результаты матчей.
RokkerRuslan
23.01.2017 22:00Алгоритм явно требует допилки, но в некоторых, возможно очень редких ситуациях может быть полезен. Да и просто как взгляд с другой стороны.
degorov
23.01.2017 22:03Ну на самом деле там возникает много интересных вопросов, можно начать хотя бы с того, как поступать, если игра для механики требует генерацию рандомных чисел.
Grief
23.01.2017 22:26Ну, это просто – нужно инициировать генераторы случайных чисел на всех клиентах seed'ом, установленным сервером. Правда, нужно убедиться, что реализации генераторов у всех клиентов одинаковые. Либо реализовать руками везде самому, например так: https://docs.oracle.com/javase/7/docs/api/java/util/Random.html#next(int). И убедиться, что порядок действий постоянен и события, происходящие одновременно упорядочены одинаково на всех клиентах (по какому-то id)
RokkerRuslan
23.01.2017 22:32Тут дело скорее не в том, что ГСЧ можно «склонить на свою сторону», а в том, что делать если вам пришли координаты нового предмета появившегося на карте? Они были получены с помощью ГСЧ, или «руками подправлены»?
degorov
23.01.2017 22:37Да не ну даже проще пример. Любая ДНД-подобная РПГ, кто мешает просто закомментить генератор в своём клиенте, чтобы кубик всегда выдавал 100% попаданий и все дела.
Grief
23.01.2017 22:40Мы знаем момент в который клиент бросает кубик и знаем что на нем выпадет, так как последовательность чисел псевдослучайна, в чем проблема, я не понимаю.
degorov
23.01.2017 22:43Знаем где? Только на самом бросающем клиенте знаем, как остальные клиенты могут проверить этот бросок?
Grief
23.01.2017 23:02Везде. Последовательность-то одна на всех. Приведите пример, я иначе не понимаю сути проблемы.
degorov
23.01.2017 23:07Нужно бросить кубик, давайте считать обычный с 6 гранями. Как сделать так, чтобы один из клиентов не выбрасывал себе всегда 6? Последовательность одну на всех — это в смысле заранее сгенерировать все рандомы по порядку и выбирать их по порядку? Ну это порождает другую проблему — ты заранее знаешь когда выпадет какая цифра и можешь играть от этого. Выбирать не по порядку = возвращаемся к началу разговора — как узнать, что выбор позиции из ряда был рандомным. Код клиента открыт и свободно модифицируем, исходим из этого.
Grief
23.01.2017 23:21+1Погуглите, как компьютер генерирует числа, как устроен генератор случайных чисел и что такое seed
degorov
23.01.2017 23:24Я вполне представляю что такое seed и как работает генератор псевдослучайных чисел, вопрос совершенно не в этом, а в том, как спалить клиента, который заменил свой генератор на return 6 :)
Grief
23.01.2017 23:27Сравнить 6 со следующим псевдослучайным числом и если оно не 6 — "вернуть false"?
degorov
23.01.2017 23:32Для этого ряд псевдослучайных чисел должен быть известен заранее и одинаков на всех клиентах, числа из него должны вытаскиваться как из стэка по очереди. Я про это выше уже писал — тогда ты заранее знаешь, какая тебе выпадет цифра и можешь играть от этого, какая цифра потом выпадет у соперника ты тоже знаешь. Если есть желание продолжать дискуссию, прочитайте, пожалуйста, ветку сначала — Вы повторяетесь.
Grief
23.01.2017 23:33Так и работает в играх любой генератор псевдослучайных чисел — "ты заранее знаешь, какая тебе выпадет цифра"
degorov
23.01.2017 23:36Это правда только в том случае, если известен источник энтропии и в данном случае ещё и одинаков на всех клиентах, что вообще говоря невозможно — те же часы, которые часто используют в качестве такого источника, у них не обязаны быть синхронизированы, например.
degorov
23.01.2017 23:45Так он работает в сингловых играх, где ты можешь испортить только свой генератор = испортить себе игру. В сетевых играх псевдослучайность генерирует сервер, который считается невзломанным и невзламываемым по умолчанию — сам сервер, безусловно, может знать, какая цифра дальше выпадет в его генераторе, но клиентам от этого ни жарко ни холодно. А мы тут о принципиально иных вводных говорим.
Grief
23.01.2017 23:59Как вы прокомментируете следующую цитату из раздела Synchronizing Pseudo-Random Number Generators из книги Multiplayer Game Programming: Architecting Networked Games?
- Each peer’s random number generator should be seeded to the same initial value. In the case of Robo Cat RTS, the master peer selects a seed when it sends out the start packet. The seed is then included inside the start packet, so every peer will know what seed value to start the game with.
- It must be guaranteed that each peer will always make the same number of calls to the PRNG every turn, in the same order, and in the same location in the code. This means there cannot be different versions of the build that may use the PRNG more or less, such as for different hardware in cross-platform play.
degorov
24.01.2017 00:01+1А что тут комментировать? Тут всё уже прокомментировано — тут же прямо написано, что автор исходит из того, что все клиенты одинаковы и нескомпрометированы. А мы тут исходим из того, что клиент может быть модифицирован в любой его части и задача остальных клиентов понять что это так.
RokkerRuslan
24.01.2017 00:09Ну да, с самого начала разговора, предположение было о том, что одному клиенту доверять нельзя в любом случае (в статье об этом сказано).
degorov
23.01.2017 22:37Правда, нужно убедиться, что реализации генераторов у всех клиентов одинаковы
Ну так речь о том и идёт, что по умолчанию мы клиенту доверять не можем.
RokkerRuslan
23.01.2017 22:43На ходу, не тестил:
Допустим в момент хода игрока р требуется случайное число. Он извещает об этом остальные клиенты, те генерируют случайное число (любым способом, да путь хоть у игрока клиент запросит), числа присылаются на клиент р и между ними проводится какая-либо мат. операция, например сумма по модулю два. И число распространяется всем клиентам, вместе с исходными данными. Каждый игрок может проверить входит ли его число в результат. После того как все клиенты верифицируют число. Оно подтверждается и это число используется в расчётах.
Как выше сказал, придумано на ходу, возможно есть уязвимости.degorov
23.01.2017 22:50Ну тут остаётся ещё вопрос в том, чтобы клиенты-соперники не могли нагенерить такой "рандом", чтобы у клиента p было 0% попаданий :) Нужна такая функция нескольких аргументов, в которую невозможно будет подать один или несколько аргументов так, чтобы гарантированно повлиять на результат этой функции в предсказуемую сторону.
RokkerRuslan
23.01.2017 23:00Думаю тут подойдёт любая функция вычисления хеша. Маленькое изменение входных данных, даёт абсолютно другой результат. Плюс играет роль, что от того клиента где рассчитывается число, само число никак не зависит (я это выше описал). В простейшем случае можно пропустить через хеш все «случайные» числа пришедшие от других клиентов.
degorov
23.01.2017 23:12Я пришёл к тому же умозаключению, если всё же доделаю, в любом случае планировал статью сюда написать по этому вопросу в том числе, тема мне кажется весьма интересной.
TheShock
24.01.2017 05:59В простейшем случае можно пропустить через хеш все «случайные» числа пришедшие от других клиентов.
Тот, который генерирует число с задержкой может попробовать несколько вариантов, посмотреть какой из них выйдет хеш и выбрать найболее выгодный для владельца клиента.RokkerRuslan
24.01.2017 07:59Надо исключить влияние клиента на генерацию. У каждого игрока есть ID, его использовать как порядок, т.е. на клиенте где происходит генерация, известен порядок в котором будут хешироваться числа еще до отправки запроса. А раз он известен всем (у всех клиентов есть ID клиентов), то каждый клиент может проверить результат.
alexeykuzmin0
24.01.2017 11:34К сожалению, такой подход будет работать только в играх с полной информацией.
Пусть, например, идет игра в карточного «дурака», и игрок 1 сходил козырным тузом, которого нет ни у одного из других игроков. Другие игроки получают информацию «игрок 1 хочет сходить козырным тузом» и должны как-то ее проверить. Но как? Я тут вижу следующие варианты:
1. Каждый игрок получает вместе с предполагаемым ходом еще и все содержимое колоды или руки игрока 1. Этот вариант нам не подходит, ведь весь процесс проверки мы делаем из-за того, что не доверяем клиентам, а тут простой сниффер сразу же клиенту даст тонну информации, которой у него быть не должно.
2. Каждый клиент производит лишь слабую проверку, сопоставляя предполагаемый ход с его рукой и историей этой партии. Тут, во-первых, остается возможность чита для игрока 1 (по крайней мере, в начале игры), да еще и приходится как-то разруливать конфликтные ситуации, когда из колоды достается карта, которая уже была.
3. Каждый клиент производит лишь слабую проверку, но есть отдельный «клиент», который олицетворяет колоду (ну и вообще мир вокруг). В любой более или менее реальной игре основная тяжесть проверки ляжет именно на
этого «специального клиента», который, по сути, часть сервера. Так зачем это все городить?
А вот для игр с полной информацией, не особо требовательным к ресурсам и в предположении, что у всех игроков более или менее приличный интернет, а не GPRS из леса — вполне будет работать, и даже ресурсы сервера сэкономит.
inborn_killer
24.01.2017 14:15А как же всем известное правило — «не верить данным, пришедшим от клиента»? А вы тут предлагаете поручить верификацию данных одного клиента другим клиентам. И при этом ещё проваливать верификацию, когда хотя бы один клиент не согласен.
Как выше уже сказали, один клиент будет способен испортить игру всем остальным. Если уж и делать что-то подобное, то количество клиентов, которого будет достаточно для верификации данных, нужно определять либо динамически, либо заранее установив адекватный доверительный интервал.
Ну а вообще, не совсем понятно, зачем уменьшать количество кода на сервере. Если вы не хотите дублировать код, то общую его часть всегда можно вынести в библиотеки, которые будут подключаться и клиентом, и сервером. В этом случае не нужно будет дублировать код.alexeykuzmin0
24.01.2017 14:17+1А мне вот как раз понятно, зачем уменьшать загрузку сервера — чтобы как можно больше пользователей уместить в один бесплатный инстанс t2.micro на AWS на тот период, пока игра только запускается, бесплатна и ее автор не хочет вкладывать в ее развитие большие деньги.
alexkunin
Правильно ли я понимаю, что фактическая сетевая задержка одного клиента (от «игрок нажал кнопку» до «ситуация обновилась») будет равна собственно задержке между этим клиентом и сервером + задержка между сервером и самым медленным клиентом? Т.е. плохое сетевое соединение одного игрока затормозит всю игру?
И правильно ли я понимаю, что один «неправильный» клиент (читер) может тянуть и задерживать всю игу просто отвечая, что запросы не валидны?
Впрочем, для походовки это не так важно, наверное.
AndreyRubankov
Как Вы правильно заметили, читер может фейлить верификацию, а это значит, что кроме огромнейшей задержки на ход будет еще и фейл любого хода, который не устраивает читера. Т.е. читер фактически будет выбирать то, как должен походить противник, чтобы сделать свою победу легче.
Но в данном случае, противники просто будут уходить из игры и будут репортить баги, потому, как Валидный на их клиенте ход, будет не валидным с точки зрения сервера.
RokkerRuslan
Плохое интернет соединение будет тормозить игру вне зависимости от алгоритма (я говорю про пошаговые игры). По второй ситуации, можно просто выкинуть игрока который присылает неправильные запросы.
Dreyk
как отличить "игрока, который присылает неправильные запросы" от "в игре сговорились и подменили данные все игроки кроме одного"?
alexeykuzmin0
А зачем? Если один человек пытается играть в шашки, а все остальные — в Чапаева, ему в этой комнате все равно не место. А те «неправильные» игроки могут играть друг с другом по своим правилам, раз уж они согласуются.