Крипто Марк Дмитриев
88

Новый алгоритм консенсуса: Доказательство события

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

В закладки

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

Radix - Tempo

Блокчейн Radix состоит из трех основных компонентов:

  • Группы узлов;
  • Распределенной базы данных, которая хранится на всех узлах;
  • Криптографическая защита данных.

В сети Radix существуют объекты, называемые Universe, любое событие происходящие внутри Universe (сообщение / транзакция) представляется объектом, называемым - Атом.

Все Атомы должны иметь минимум одно место назначения / получателя.

Структура атома
  • Payload Atom - Атом, который хранит внутри себя данные;

  • Payload - хранящиеся в атоме данные;

  • Encrypted Data - зашифрованные данные;

  • Participants - участники транзакции;

  • Destinations - получатель;

  • Signature - подпись отправителя;

  • Consumers - получатель;

  • Consumables - отправляемый объект (валюта, криптокотик и т.д);

  • Logic / Script - порядок действий.

Пользователи могут создавать и отправлять атомы в сеть через любой узел, к которому они подключены. Отправленный Атом обрабатывается сетью и, если он действителен, Temporal Proof (доказательство временем) связывает с Атомом, куда должен быть доставлен объект.

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

Транзакции

Право собственности на объект, называемым Consumables - определятся последовательностью передачи данного объекта. В сети хранится проверяемая история владельцев, которые в определенный момент времени были собственниками этого объекта.

Для передачи права собственности объекта(An) находящемуся в атоме(Аn) Бобу, Алиса создает Consumer(Ах), который ссылается на Consumable(Аn), что определяет ее как нынешнего владельца и идентифицирует ее.

Она также создает новый Consumable(Ax), который содержит передаваемый объект(Аn) вместе с идентификатором нового владельца Боба. Consumer’s и Consumable перемещаются в новый атом(Ах) и отправляются в сеть для проверки.

Передача прав собственности

Любой узел, который получает атом Алисы(Ах), может проверить, что Алиса действительно является текущим владельцем объекта(An). Это выполняется путем проверки подписи отправленного Consumer(Ах) относительно информации о владельце, числящимся в последнем Consumable для элемента хранящемся в локальной базе данных узла; Если подпись успешно подтверждена, Алиса должна быть текущим владельцем. Затем передача будет выполнена и Боб станет новым владельцем.

Для некоторых операций передачи может потребоваться, чтобы объект(Аn) не передавался полностью, например, валюта. Consumables можно разрешить частичную передачу объекта, если свойства объекта позволяют это. В этом случае Алиса создаст два Consumables: один для Боба и другой для себя или других получателей. Аналогичным образом, несколько Consumers могут быть использованы для ссылки на другие Consumables принадлежащих Алисе, и передать их все Бобу в одном действии, гарантируя атомарность и уменьшая нагрузку на сеть.

Передача информации

Для быстрой отправки данных на все узлы в шарде, Tempo использует протокол обмена данными – Gossip. Данный протокол оказался эффективным и надежным средством массового распространения информации в p2p сети.

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

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

Чтобы устранить эти несоответствия, узлы полагаются на проверку "событий", которые происходили в сети в определенный момент времени. Таким образом, если в сети обнаружено несоответствие, узлы начинают проверять исторические данные об объекте, к которому возникли вопросы об его честности.

Пример передачи прав собственности

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

Рассмотрим пример передачи Алисой объекта(A) Бобу.

  1. Алиса указала конечную точку назначения, которая указывает, что она отправляет объект из шарда(1), и точку назначения Боба, которая указывает, что она будет отправлена в шард(3);
  2. Узлы, хранящие шард (1||3) должны знать об этом событии;
  3. Алиса отправляет объект; Боб получает состояние объекта(А) хранящийся в каждом шарде ;
  4. После этого события, узлам хранящим шард(1), больше не нужно знать о каких-либо будущих изменениях состояния объекта(А) (если он снова не будет отправлен в шард(1);
  5. Ответственность за состояние объекта(А) перешла к узлам, хранящим шард(3);
  6. Если Боб хочет отправить объект(А) владельцу в другом шарде, ответственность за поддержание состояния объекта(А) снова изменится.

Обработка только тех событий, которые влияют на состояние в подмножестве узлов, и перенос ответственности за поддержания состояния значительно сокращают общие затраты на обработку данных - это ключ к производительности масштабирования Tempo.

Логические часы

Основа консенсуса Tempo основана на логических часах, которые являются простым средством обеспечения относительного частичного упорядочения событий в распределенной системе.

В Tempo все узлы имеют локальные логические часы; постоянно увеличивающееся целочисленное значение, представляющее количество событий, наблюдаемых этим узлом. Узлы увеличивают свои локальные логические часы при наблюдении события, которое не было замечено ранее. При сохранении события узел также сохраняет его текущее значение логических часов с ним. При необходимости эта запись может использоваться для проверки временного порядка прошлых событий.

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

Доказательство времени

Univers разделяется на Шарды, где узлам не требуется хранить полную копию сети и ее состояния. Тем не менее, без подходящего консенсусного алгоритма, который позволит узлам проверять изменения состояния на обслуживаемых им сегментах, "двойные траты" были бы простым способом, когда нечестный субъект мог бы потратить один и тот же объект на двух разных шардах.

Например, отправка объекта(А) Алисы Бобу. Процесс начинается с выбора Алисой узла, к которому она подключена - узла(N) и отправляет атом(Ах) с запросом создать временное доказательство определенной длины.

  1. После получения запроса узел(N), если он хранит шард Алисы или Боба выполнит проверку атома(Ах);

  2. В случае, если у него есть копия шарда(1) для Алисы, он гарантирует, что объект(А) еще не был отправлен Алисой;

  3. Если какое-либо доказуемое несоответствие найдено, например, объект(А) уже был отправлен Алисой или атом плохо настроен, обработка атома не будет выполнена

  4. В противном случае, узел(N) определит набор непосредственно связанных узлов, которые либо хранят Шард(1 || 3) или выберет один в случайном порядке и перешлет ему запрос на отправку.

  5. Если подходящий узел не найден, узел(N) будет искать через свой граф узлов и связанные метаданные, чтобы обнаружить работающие ретрансляторы с подключёнными узлами, поддерживающим Шард(1 || 3). После узел(N) находит подходящего кандидата узла(P), он добавит пространственную временную координату (L, e, o, n) и сигнатуру Хеша (L, e, o, n) доказательства случившегося события (создает новую, если ее еще нет).

Пример отправки 1 BTC
Доказательство временем gossip протокола и атома

Доказательство события и gossip протокол атома

Полученные данные о доказательстве времени Атома(Ах) в приведенном выше примере даст следующие координаты.

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

Говоря простыми словами, если Алиса посылает объект(А) к Бобу, и Боб отправляет объект(А) к Кэрол, это очень просто для сети, если один из узлов, которые участвовали в создании доказательства произошедшего события для Алисы → Боба, он также является частью доказательства для Боба → Кэрол.

Достижение доказательства случившегося события причинно-следственной истории является относительно простым: если, принимая участие в доказательстве события, любой из узлов, доступных для узла(N) также являются частью доказательства временем любых зависимостей атома(Аn). Узел (N) случайным образом выберет один из них в качестве приоритета, если он еще не является частью временного доказательства для атом(Ах).

Векторные часы

В случае возникновения конфликта (двойная трата) или отклонения между двумя событиями (L, E, O, N) координаты временного доказательства могут быть использованы, чтобы построить векторные часы с помощью логических часов(L) c использованием каждого компонента, которые они хранят.

Даны двое векторных часов VC(Ax) и VC(Ay), для двух атомов (Ах) и (Ау) где логическое значение часов для соответствующего события каждого узла {A,B,D,F,G,L,P} приведено в массиве ниже.

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

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

Двое параллельных часов, которые получил узел(N)

Чтобы определить, какое из них является более ранним событием, узел(N) имеет в своем распоряжении два механизма.

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

Узел ищет события позже VC(Ax), где узлы {A,D,F,S} участвовали в попытках обнаружить узлы {B,G,L,V} VC(Ay), которые являются частью этих временных доказательств и сравнивают значения логических часов.

Узел обнаруживает в своей локальной книге событие, которое имеет векторные часы формы:

Временной порядок VC(Ax) и VC(Ay) может быть определен из-за присутствия S и V. Логические часы для (узлов) в VC(Az) больше, чем в VC(Ax), поэтому VC (Az) был создан после VC(Ax). Логические часы для узла(V) в VC(Аz) меньше, чем в VC(Ay), поэтому VC(Ax) и VC(Az) были созданы до VC(Ay).

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

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

Если во время конфликта решение не найдено, узел(N) будет хранить как атом(Ах), так и атом(Ау) в своей локальной базе, маркируя их, в соответствии с которыми он видел первый, и используя второй механизм определения событий: определение порядка принятия обязательств.

Свидетельство

Чтобы помочь с определением общего порядка событий, узлы объявляют в сети периодическое свидетельство всех событий, которые они видели.

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

Последовательность свидетельства

Если узел принимает участие в проверке события, обязательство включается во временную координату узла как координата C, в результате чего получается расширенная пространственно-временная координата (L,E,O,N,C) Обязательство защищено от несанкционированного доступа, поскольку координаты подписываются свидетельствующими событию узлами.

Доказательство события с меткой о свидетельстве данного события

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

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

Например, если значение L для свидетельства(1) было и значение L для обязательства(2) составило 200, то обязательство(1) должно содержать 100 элементов. Если запрашивающий узел не возвращает 100 хэшей при проверке, может произойти фальсификация логических часов. Свидетельства также используются для обеспечения вторичного механизма для определения временного порядка событий.

  1. Узел(N) получил атои(Ay), который конфликтует с атомом(Ax). Узел(N) связывается с одним из своих соседей, узлом(P) и запрашивает у него информацию об свидетельствах, соответствующей атому(Ax).
  2. Узел(P) отвечает: свидетельства атома(Ax), подтверждаются набором атомов(B), которые были засвидетельствованы после атома(Ax) в рамках одного и того же свидетельства, и его логическое значение часов для атома(Ax) и атома(B) подтверждается Merkle Hash.

С помощью этой информации узел(N) может проверять логические значения часов атомов, их целостность, свидетельства.

Проверка свидетельства

Как только эта информация была получена от узла(P), узел(N) может запросить узел(Q), который доставил атом(Ay).Он запрашивает, чтобы узел(Q) отправил ему свидетельство и информацию логических часов для атома(Ay) и любого из атомов(B), а также листья Merkle Hash позволяя узлу(N) проверить.

Поэтому атом(Ax) появился в сети раньше атома(Ay).

Поскольку у нас теперь есть свидетельства события и логические значения часов, решение простое: атом(Ах) был обнаружен раньше атома(Ау), если любые атомы(BS), возвращаемые узлом(P), присутствуют в свидетельствах, предоставленных узлом(Q), где логическое значение часов любого атома(BS) из узла(Q) меньше логического тактового значения атома(Ау) для узла(Q). Если атом(Ах) был последним в рамках свидетельства, узел(P) может вернуть последующее свидетельство, или узел(N) может связаться с другим соседним узлом. Вероятность того, что атом(Ах) является последним в рамках всех свидетельств для всех узлов, стремится к минимальному значению. Если узел(Q) не знает ни одного из атомов(BS), доступных в его локальной базе, узел(P) может запросить другие соседние узлы относительно атома(Ау). Если в момент конфликта не существует решения, узел(N) будет хранить атом(Ах) и атом(Ау) в своей локальной базе данных, маркируя их, в соответствии с их свидетельствами, которые он получил.

Вывод

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

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

Узлы могут присоединяться и покидать сеть по своему желанию и полагаться на обнаруженные события для синхронизации и обновления.

__________________________________________________________________________________

Материал подготовлен техническим специалистом инвестиционного фонда GT Blockchain Investments

__________________________________________________________________________________

Данная статья носит исключительно ИНФОРМАЦИОННЫЙ характер. Настоящая статья ни в коей мере не является предложением или приглашением к предложению купить или продать какие-либо криптовалюты, обсуждаемые здесь. Инвесторы должны провести независимую проверку всех криптовалют, обсуждаемых в этой статье, и сложить мнение о соответствующем рынке до принятия любого инвестиционного решения. Ни один из авторов, соавторов или кто-либо еще, связанный с GT Blockchain Investments никоим образом не может нести ответственность за использование вами информации, содержащейся в данной статье.

Материал опубликован пользователем. Нажмите кнопку «Написать», чтобы поделиться мнением или рассказать о своём проекте.

Написать
{ "author_name": "Марк Дмитриев", "author_type": "self", "tags": [], "comments": 0, "likes": 1, "favorites": 0, "is_advertisement": false, "subsite_label": "crypto", "id": 47931, "is_wide": false, "is_ugc": true, "date": "Fri, 12 Oct 2018 13:56:42 +0300" }
{ "id": 47931, "author_id": 205350, "diff_limit": 1000, "urls": {"diff":"\/comments\/47931\/get","add":"\/comments\/47931\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/47931"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 199126 }

Комментариев нет 0 комм.

Популярные

По порядку

0

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fizc" } } }, { "id": 4, "label": "240х200_mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "flbq" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "bugf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjog" } } }, { "id": 10, "disable": true, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "disable": true, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "bscsh", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "bugf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-223676-0", "render_to": "inpage_VI-223676-0-1104503429", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=bugf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Плашка на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudx", "p2": "ftjf" } } }, { "id": 16, "label": "Кнопка в шапке мобайл", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byzqf", "p2": "ftwx" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fzvc" } } }, { "id": 19, "label": "Тизер на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "p1": "cbltd", "p2": "gazs" } } } ]
Приложение-плацебо скачали
больше миллиона раз
Подписаться на push-уведомления