nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 25 Sep 2020 07:32



Reply to topic  [ 15 posts ] 
[Realm] децентрализованные виртуальные миры 
Author Message
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Децентрализованное ответвление от темы Виртбурга (который был виртуальным миром с центральным сервером):
http://www.nedopc.org/forum/viewtopic.php?f=81&t=9043
http://www.nedopc.org/forum/viewtopic.php?f=81&t=10939
P.S. Линки для ознакомления на тему Peer-2-Peer MMO:
https://en.wikipedia.org/wiki/Massively_multiplayer_online_game (под спойлером линк на русскую вики-страничку)
Quote:
Some recent attempts to build peer-to-peer (P2P) MMOGs have been made. Outback Online may be the first commercial one,[17] however, so far most of the efforts have been academic studies.[18] A P2P MMOG may potentially be more scalable and cheaper to build, but notable issues with P2P MMOGs include security and consistency control, which can be difficult to address given that clients are easily hacked. Some MMOGs such as Vindictus use P2P networking and client-server networking together.
https://en.wikipedia.org/wiki/Vindictus
[17] https://www.theage.com.au/technology/yoicks-its-another-virtual-world-20070227-gdpk0o.html
[18] http://vast.sourceforge.net/relatedwork.php
Классификация из последнего линка:
Quote:
  • Neighbor discovery - the method a peer learns of relevant neighbors to interact with, including these types:
    • server introduction: the server knows all nodes, and tells a newly joined node all neighbors.
    • server notification: the server maintains all nodes, notifies a peer of its AOI neighbors.
    • supernode notification: selected peers with knowledge of entire region notify other regular peers.
    • peer notification: peers mutually notify each other of new AOI neighbors.
    • list exchange: peers exchange the neighbor list they maintain to discover new AOI neighbors.
    • DHT query: peers form a DHT overlay, and search for relevant neighbors or supernodes for new AOI neighbors.
    • overlay multicast: peers multicast their positions regularly to allow other nodes learn of their positions.
  • Connectivity - which other nodes does a single node connects within the P2P environment, including these types:
    • server: each peer connects only to the server (a provisioned machine).
    • all: each peer maintains contacts with all other nodes in the world.
    • supernode: each peer connects to certain selected peers.
    • AOI neighbors: each peer connects to all other nodes within the AOI.
    • nearest neighbors: each peer connects to its nearest 1-hop neighbors (according to Voronoi/Delaunay mapping)
    • quadrant neighbors: each peer connects with one neighbor within each of the four quadrants.
    • tree: each peer connects to a parent node and several children nodes.
    • mesh: each peer connects to a few nearby nodes to ensure a connected mesh
  • Partitioning - whether the entire virtual world is partitioned into various regions, including the following types:
    • none: there's no partitioning.
    • AOI: no explicit partitioning exists, but each node generally interacts only with their AOI neighbors.
    • static: world is partitioned beforehand, and the partitions cannot changed during run-time.
    • dynamic: the partitioning occurs dynamically according to loading or node density.
  • AOI type - definition of area of interest (AOI) used, including the following types:
    • aura: sphere of interaction, if two aura intersect then interaction is mutual
    • focus: sphere of reception (subscriber-like), the AOI indicates an area where all events within should be received
    • nimbus: sphere of influence (publisher-like), the AOI indicates an area the node or event may affect
  • Latency - number of end-to-end hops to send an update message to a visible neighbor
AOI = area of interest
DHT = distributed hash table
https://en.wikipedia.org/wiki/Distributed_hash_table

_________________
:eugeek: https://twitter.com/Shaos1973


16 Sep 2020 16:01
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Вобщем как я себе это вижу - виртуальный мир разделён на сектора, которые представляют из себя наборы 3D-объектов, текстур, спрайтов и скриптов (это уже как бы есть). По идее любой человек может открыть такой сектор даже локально у себя на компьютере и бродить там в одиночестве. Более того - много разных людей могут открыть у себя этот сектор и бродить не пересекаясь. Получается у каждого из них существует своя альтернативная виртуальная реальность, в которой он единственный пользователь. Чтобы разделить виртуальную реальность с кем-то ещё надо не только иметь одну и ту же карту с объектами, но и способ попасть именно в ту виртуальную реальность, в которой уже кто-то есть - иметь возможность посылать сообщения в эту виртуальную реальность и получать оттуда сообщения от других (и события - по сути создавая свою локальную копию общей виртуальной реальности). И лучше чтобы это была "официальная" виртуальная реальность от создателей проекта, а не левая реальность от одинокого хакера - поэтому нужны ключи и подписка. Потом пока в секторе нет ни одного посетителя (нет наблюдателей) там может ничего не происходить - как только появился наблюдатель, то надо запускать поезда, блуждающих ботов и т.д. Далее локальное общение внутри сектора может оставаться лишь между теми кто там присутствует и вновь входящий не обязан видеть историю сообщений - его интересует только то, что говориться с момента его захода. Если пользователь перешёл из одного сектора в соседний, то виртуальность должна быть уведомлена об этом как и все присутствующие в обоих секторах. История активности виртуальности может быть доставлена с разных узлов на главный сервер для дальнейшего анализа.

P.S. Распределённая среда должна предоставлять хранилище файлов (описатели секторов, текстуры, спрайты, скрипты), доступных по содержимому (адресуемо хэшем скажем MD5) и хранилище событий, привязанных ко времени (включая сообщения чата) и фильтруемых по идентификатору сектора (причём узлы находящиеся близко к друг другу в пределах сектора должны иметь большую частоту обмена событиями друг с другом).

_________________
:eugeek: https://twitter.com/Shaos1973


16 Sep 2020 20:49
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
Shaos wrote:
Вобщем как я себе это вижу - виртуальный мир разделён на сектора, ...

Что-то мне это чем-то напомнило популярную ныне (как пишут) игрушку «Годвилль» -
«прямого потомка Progress Quest».
Там вроде как тоже у каждого игрока - свой индивидуальный мирок...
Сам я, конечно, не играл, но уж больно часто встречал упоминания в Интернете...

_________________
iLavr


16 Sep 2020 23:21
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Lavr wrote:
Там вроде как тоже у каждого игрока - свой индивидуальный мирок...
Сам я, конечно, не играл, но уж больно часто встречал упоминания в Интернете...

Ну свой индивидуальный мирок это не виртуальные миры - это просто локальная игра на одного - для виртуальных миров надо видеть друг друга и быть как бы одновременно в одном секторе...

_________________
:eugeek: https://twitter.com/Shaos1973


16 Sep 2020 23:24
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Предположим, что главный сервер выдаёт идентификатор виртуальной реальности для каждого дня (скажем на три дня вперёд) и эти идентификаторы распространяются по узлам вместе со списком хешей файлов (возможно списки запрещённых хешей запрещённых или устаревших файлов тоже дожны распостраняться тем же путём). Когда юзер включает клиента, то клиент может поискать узлы в локальной сети, чтобы спросить у них сегодняшний идентификатор виртуальной реальности либо может пойти на главный сервер и качнуть манифест оттуда (возможно клиент будет помнить IP-адреса других узлов, с которыми он общался до этого, и может поспрашивать у них). Соответственно алгоритм включения такой:
1) поискать узлы в локальной сети делая широковещательный UDP запрос по известному порту, используя последний известный идентификатор виртуальной реальности;
2) если никто не ответил, то выбрать случайные адреса из списка IP-адресов, с которыми общался этот узел в предыдущие разы - набрать 3 ответивших и спросить у них обновления, используя известный идентификатор виртуальной реальности (устаревший);
3) если не удалось найти живых узлов за определённое количество попыток, то идём на главный сервер по HTTP (тоже самое делаем, если не удалось получить непротиворечивую информацию от ответивших узлов).
Ничего не мешает кому-то взять инициативу в свои руки, если главный сервер вдруг умрёт - надо просто убедить людей идти в альтернативную виртуальную реальность с другим идентификатором :mrgreen:
P.S. "Официальный" сервер должен предоставлять списки "одобренных" файлов с их хэшами, чтобы исключить возможность такой ситуации, что какой-то узел вдруг подменит все текстуры на всякие непотребства
P.P.S. Можно задействовать новые быстрые алгоритмы цифровой подписи как http://ed25519.cr.yp.to/index.html (Public Domain) или даже "Post-Quantum Cryptography" (который нельзя взломать на квантовом компьютере, по крайней мере теоретически) https://falcon-sign.info/ (MIT License).

_________________
:eugeek: https://twitter.com/Shaos1973


17 Sep 2020 00:41
Profile WWW
Doomed
User avatar

Joined: 21 Mar 2017 13:50
Posts: 613
Location: Spb
Reply with quote
Shaos wrote:
Вобщем как я себе это вижу - виртуальный мир разделён на сектора

Диптаун? :mrgreen:


17 Sep 2020 05:06
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
AlexanderZh wrote:
Shaos wrote:
Вобщем как я себе это вижу - виртуальный мир разделён на сектора

Диптаун? :mrgreen:
Ну да - если почитать тему с архивами переписки по Виртбургу, то можно увидеть, что Диптаун там вылезал достаточно часто :)

http://www.nedopc.org/forum/viewtopic.php?f=81&t=10939

Quote:
Shaos, 24 авг 2000:
...
Итак, имеется виртуальный город, вход в который
осуществляется посредстовом некоторого программного
обеспечения (назовем его 3DM-бродилка).
Идея такого города зародилась у меня пару лет
назад и окончательно окрепла и получила реальные
очертания после прочтения "Лабиринта отражений".

_________________
:eugeek: https://twitter.com/Shaos1973


17 Sep 2020 12:52
Profile WWW
Doomed
User avatar

Joined: 21 Mar 2017 13:50
Posts: 613
Location: Spb
Reply with quote
Shaos wrote:
если почитать тему с архивами переписки по Виртбургу

Скорее всего читал, но забыл. Но когда коснулось распределенных данных сразу вспомнил это произведение :mrgreen: . Было там про храм дайверов, именно по подобной технологии.
ЗЫ: Сань, спрятай ссылку (на вики.орг) в первом посте под тег, страничка ужасно растягивается в ширину...


17 Sep 2020 15:11
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
убрал под спойлер

_________________
:eugeek: https://twitter.com/Shaos1973


17 Sep 2020 17:00
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Shaos wrote:
P.S. "Официальный" сервер должен предоставлять списки "одобренных" файлов с их хэшами, чтобы исключить возможность такой ситуации, что какой-то узел вдруг подменит все текстуры на всякие непотребства
P.P.S. Можно задействовать новые быстрые алгоритмы цифровой подписи как http://ed25519.cr.yp.to/index.html (Public Domain) или даже "Post-Quantum Cryptography" (который нельзя взломать на квантовом компьютере, по крайней мере теоретически) https://falcon-sign.info/ (MIT License).

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

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

Главный сервер должен уметь отвечать на запрос выдачи номера текущей виртуальности, к которой он может присовокупить номера виртуальности на завтра и на послезавтра (время будет считаться в GMT). У виртуальности должен быть список файлов (возможно с доступом по секторам) с сигнатурами и список пользователей с открытыми ключами (наверное с доступом по имени). Каждый пользователь, кроме открытого ключа должен иметь пароль (для доступа к ресурсам главного сервера), e-mail (для связи в случае проблем) и описатель аватара (скорее всего это будет набор битов) плюс на будущее можно завести количество виртуальных денег и коэффициент везения (карма), а также координаты места, где пользователь просыпается после подключения к виртуальному миру. Удалённые или забаненные пользователи убираются из списка пользователей текущей виртуальности.

Основная задача ухода в распределённость это минимизация траффика главного сервера, который стоит денег.

P.S. Когда добавится финансовая система, то там по аналогии с блокчейном можно хранить все транзакции (в распределённом хранилище).

_________________
:eugeek: https://twitter.com/Shaos1973


18 Sep 2020 01:52
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Оказывается уже есть децентрализованный виртуальный мир на блокчейне - Decentraland (запущен в сентябре 2019):
https://decentraland.org/
https://market.decentraland.org/
https://twitter.com/decentraland
и местами напоминает Виртбург (просто пройдитесь по видеороликам в ихнем твиттере)!
Правда там всё-таки многое делается на главном сайте (типа выбор аватара, покупки-продажи ассетов и постройки зданий), плюс своя криптовалюта замешана...
P.S. Некоторым этот момент сильно не понравился:
Quote:
Your average virtual worlds consumer does not want to fuss with crypto wallets and transaction gas fees and seed phrases and private keys. They just want things to work.
https://ryanschultz.com/2020/02/20/a-step-by-step-guide-on-how-to-get-started-in-decentraland-and-some-caveats-for-new-users/
P.P.S. Этот же блог утверждает, что таких проектов 4:
Attachment:
Comparison.png
Comparison.png [ 44.47 KiB | Viewed 220 times ]
https://somniumspace.com/
http://www.cryptovoxels.com/
https://www.sandbox.game/en/
Интересно что все 4 представляют примерно тот же самый набор активностей - marketplace, builder и т.д.
(похоже зря я Виртбург прибил в 2010 - теперь придётся догонять паровоз)
P.P.P.S. Полный список виртуальных миров (не только блокчейновых) от тогоже блоггера:
https://ryanschultz.com/list-of-social-vr-virtual-worlds/
И ещё некоторые определения и понятия от него же:
https://ryanschultz.com/definitions-of-terms-used-in-this-blog/

_________________
:eugeek: https://twitter.com/Shaos1973


18 Sep 2020 18:53
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 09:08
Posts: 7777
Location: Россия
Reply with quote
Shaos wrote:
Оказывается уже есть децентрализованный виртуальный мир на блокчейне -
Decentraland (запущен в сентябре 2019): ...

(c) Всё уже украдено до нас... :lol:

_________________
iLavr


19 Sep 2020 03:52
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Shaos wrote:

Читал про разные алгоритмы распределённых хешей - много думал...

_________________
:eugeek: https://twitter.com/Shaos1973


19 Sep 2020 23:33
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Наверное надо заводить свои собственные определения в рамках этой концепции, итак:

realm - отдельная вселенная, куда помещается игрок (например "realm Virtburg") - все файлы разрешённые в этой вселенной подписываются секретным ключом от realm-а (и каждый узел realm-а получает открытый ключ для проверки подписей);
reality - виртуальная реальность в пределах realm-a (причём реальностей может быть много и разные реальности могут переиспользовать одни и теже файлы);
signature - цифровая подпись, подтверждающая принадлежность файла к тому или иному realm-у (либо подтверждающая авторство сообщения), может также служить для идентификации (файла или сообщения);
asset - файл имеющий цифровую подпись (signature), по которой его можно найти в распределённой среде;
user - игрок, помещённый в тот или иной realm и подключенный к той или иной реальности (reality) - каждый user имеет свой секретный ключ, которым подписывает свои сообщения (также юзер передаёт свой открытый ключ всем, с кем хочет общаться);
node - узел сети, которым владеет user, идентифицируется подписью пользовательской записи полученной от realm-a (узел может быть частью только одного realm-a);
supernode - специализированный узел сети, которым владеет администрация realm-a (этот узел знает закрытый ключ realm-a и может подписывать файлы, а также умеет авторизовывать игроков);
message - сообщения, посылаемые игроками и системой (сообщения имеют время жизни в секундах и если оно 0, то сообщение считается "вечным" и остаётся в истории);
subject - тема, на которую может подписаться user для получения и отправки сообщений (например при заходе в сектор надо подписаться на получение сообщений из этого сектора).

P.S. Может эту концепцию так и назвать - "Realm"? :mrgreen:

_________________
:eugeek: https://twitter.com/Shaos1973


20 Sep 2020 05:02
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18844
Location: Silicon Valley
Reply with quote
Shaos wrote:
Можно задействовать новые быстрые алгоритмы цифровой подписи как http://ed25519.cr.yp.to/index.html (Public Domain)...

Официально оно оказывается называется EdDSA (см. https://en.wikipedia.org/wiki/EdDSA и https://ru.wikipedia.org/wiki/EdDSA) - Ed25519 является его частным случаем с хеш-алгоритмом SHA-512 и кривой Curve25519. Поигрался с reference implementation взятой вместе с sha512 из supercop-20200906.tar.xz (замерялка скорости работы кучи разных крипто-алгоритмов) сделав самодельные утилиты командной строки - поправленные исходники с примером использования можно найти в приаттаченном архиве:

Attachment:
Ed25519src.zip [818.97 KiB]
Downloaded 2 times

Если развернуть архив в линухе и запустить скриптик ed25519_mk, то он соберёт 3 бинаря - ed25519keys для случайной генерации ключей (64-байтовый секретный ключ и 32-байтовый публичный) и ed25519 для подписи (генерирует 64-байтовую подпись по содержимому файла используя секретный ключ) и проверки подлинности файла (по содержимому файла используя подпись и публичный ключ - печатает Valid/Invalid), а также тестовый ed25519test для прогона 1024 заранее известных ключей, блоков данных и подписей из sign.input (взято из питоновского варианта алгоритма) для проверки корректности сборки (там ещё хеш sha512 тоже можно как утилиту собрать, если сильно хочется - опять же для проверки, что оно работает также как обычный линуксовый sha512sum).

Рандомно генерим ключи:

./ed25519keys

Ed25519 secret key:
023246c8b5b948894ae9b285f5b15a2bc5250302c96770c0ee977ad964531350342a6369075aca00c4c3674a408a65380ab75daa2b8da912b3edd3da14056c92

Ed25519 public key:
342a6369075aca00c4c3674a408a65380ab75daa2b8da912b3edd3da14056c92

Подписываем файл ed25519.h используя секретный ключ (ed25519 filename skey):

./ed25519 ed25519.h 023246c8b5b948894ae9b285f5b15a2bc5250302c96770c0ee977ad964531350342a6369075aca00c4c3674a408a65380ab75daa2b8da912b3edd3da14056c92

Ed25519 signature for ed25519.h:
7cac183bc2cb71e69a65dbd03af3a58db281cbae4edaf6427cbde264a23790809d59b44dfe35e1998c31374e564e2936c1e8ca969100970015eeb3ca1300dc03

Проверяем подлинность файла с помощью только что сгенерённой подписи и публичного ключа (ed25519 filename sign pkey):

./ed25519 ed25519.h 7cac183bc2cb71e69a65dbd03af3a58db281cbae4edaf6427cbde264a23790809d59b44dfe35e1998c31374e564e2936c1e8ca969100970015eeb3ca1300dc03 342a6369075aca00c4c3674a408a65380ab75daa2b8da912b3edd3da14056c92
Valid

Можно попробовать испортить подпись и убедиться, что ответ будет невалидным:

./ed25519 ed25519.h 8cac183bc2cb71e69a65dbd03af3a58db281cbae4edaf6427cbde264a23790809d59b44dfe35e1998c31374e564e2936c1e8ca969100970015eeb3ca1300dc03 342a6369075aca00c4c3674a408a65380ab75daa2b8da912b3edd3da14056c92
Invalid

Если подменить проверяемый файл, то также будет ошибка:

./ed25519 ed25519_mk 7cac183bc2cb71e69a65dbd03af3a58db281cbae4edaf6427cbde264a23790809d59b44dfe35e1998c31374e564e2936c1e8ca969100970015eeb3ca1300dc03 342a6369075aca00c4c3674a408a65380ab75daa2b8da912b3edd3da14056c92
Invalid

P.S. Могу виндоуз версию попробовать собрать если кому интересно (ну или досовскую)

P.P.S. Ed25519 уже оказывается много где используется: https://ianix.com/pub/ed25519-deployment.html

P.P.P.S. А вообще автор этого алгоритма (и многих других) Daniel J. Bernstein жутко умный чел 1971 года рождения (я почему-то думал, что он сильно старше), который в 15-летнем возрасте (1987) закончил школу (т.е. вундеркинд) на Лонг-Айленде (где я жил 13 лет), далее в 20-летнем возрасте (1991) закончил универ NYU (где я тоже учился), потом в 24-летнем возрасте (1995) получил PhD по математике от университета Беркли в Калифорнии (где я теперь живу) и с тех пор работает профессором в университете штата Иллинойс в Чикаго (а также в каком-то голландском универе) - сильно выступает против софтверных патентов и ограничений шифрования (несколько раз в 90х успешно засудил федеральное правительство США в результате чего федералы отменили ограничение на распостранение длинных ключей шифрования за пределами США), все свои программы выкладывает в Public Domain (т.е. берите и пользуйте все кому не лень в любых целях в том числе коммерческих и даже под собственным именем)
https://en.wikipedia.org/wiki/Daniel_J._Bernstein
http://cr.yp.to/djb.html
Attachment:
Bernstein.jpg
Bernstein.jpg [ 15.21 KiB | Viewed 129 times ]
Вот интересная история про то как он в Питер слетал на конференцию летом 2000 года :mrgreen:
http://cr.yp.to/conferences/russia.html

P.P.P.P.S. В архив выше добавил тестовую утилитку, которая 1024 примера прогоняет через подписку и верификацию (типа автоматическое регресс тестирование по известным тест-кейсам взятым из питоновской версии алгоритма)

_________________
:eugeek: https://twitter.com/Shaos1973


20 Sep 2020 09:14
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 15 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.