Посторонним в

Блог-форум Винни Пуха
 
ФорумФорум  ЧаВоЧаВо  ПоискПоиск  ПользователиПользователи  ГруппыГруппы  РегистрацияРегистрация  ВходВход  

Поделиться | 
 

 PARSEC, новый протокол безопасного интернета

Предыдущая тема Следующая тема Перейти вниз 
АвторСообщение
Winnie
Admin


Сообщения : 878
Дата регистрации : 2015-06-10

СообщениеТема: PARSEC, новый протокол безопасного интернета   2018-06-10, 09:37

PARSEC
Protocol for Asynchronous, Reliable, Secure and Efficient Consensus

https://youtu.be/JKagaPUrDsY
https://docs.google.com/presentation/d/1r-6dQ0fyrKObnNweipD5J75eVrhfVLoqe2gKQM9jst4/


Привет, Интернет!
24 мая 2018 года команда маршрутизации компании MaidSAFE выпустила PARSEC (Protocol for Asynchronous, Reliable, Secure and Efficient Consensus): протокол для асинхронного, надежного, безопасного и эффективного консенсуса.
Я Пьер (Pierre), член команды маршрутизации и один из авторов PARSEC.
В этом видео я попытаюсь объяснить, что это такое, и почему этот протокол имеет большое значение.
Также, для тех из вас, кто хочет знать о протоколе подробнее, я подробно объясню его алгоритм.


Византийский консенсус

PARSEC - это протокол византийского консенсуса.
Общая проблема отказоустойчивого византийского консенсуса является классической проблемой распределённых систем.
Впервые её описали Лесли Лампорт, Роберт Шостак и Маршалл Пиз (Leslie Lamport, Robert Shostak and Marshall Pease) в своей статье 1982 года "Проблема византийских генералов" (Задача византийских генералов).

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

В статье Фишера, Линча и Патерсона 1985 года "Невозможность распределённого консенсуса с одним ошибочным процессом" математически доказано, что проблема консенсуса не может быть решена детерминистически в присутствии любого византийского узла.


Сеть SAFE

Здесь, в Maidsafe, мы строим сеть SAFE.
SAFE (Secure Access For Everyone) означает безопасный доступ для всех.

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

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

Если вам интересно узнать больше о полном потенциале сети SAFE, для начала вы можете прочитать введение в сеть SAFE: https://safenetworkprimer.com/.

Сеть SAFE аналогична Интернету, с намерением подключить очень большое количество компьютеров и позволить разработку веб-приложений нового типа, которые уважают приватность пользователей.

Наша децентрализованная сеть разделена на группы, которые мы называем непересекающимися секциями.
Это наш способ обработки данных, в других приложениях похожий подход называется шардингом (техника масштабирования работы с данными, когда данные распределяются между разными физическими серверами).
Это позволяет сети поддерживать очень высокую активность при равномерном распределении нагрузки в сети.
Поскольку узлы являются компьютерами отдельных пользователей, мы не можем ожидать от них очень высокой надёжности, поэтому мы можем ожидать, что узлы могут регулярно отключаться от сети и повторно подключаться.
Этот процесс называется размельчение (churn), и сеть должна обрабатывать его изящно.
Кроме того, поскольку сеть состоит из компьютеров обычных пользователей, мы не можем ожидать что между узлами будут однородные соединения.
Это означает, что одни узлы могут связываться между собой намного быстрее, чем другие.
Это свойство сети называется асинхронность (asynchrony).
Истины, которые мы хотим поддерживать между узлами сети, - это то, что другие узлы в настоящее время подключены к их секции в сети.
Поскольку доступ к SAFE сети неограничен, мы уверены, что часть узлов проявит византийское поведение: их единственной целью будет попытка нарушить работу сети.
Это объясняет нашу потребность в византийской отказоустойчивости.
И последнее, исходный код для SAFE сети разрабатывается открыто и доступен для всех, чтобы любой мог провести аудит, поскольку это единственный способ доказать выполнение требований безопасности по отношению к нашим пользователям.
Это означает, что любой консенсусный алгоритм, который мы используем, должен быть полностью открыт, что не позволяет нам использовать запатентованные решения.
Итак, нам нужна такая категория византийского консенсуса как асинхронная византийская отказоустойчивость, ABFT (Asynchronous Byzantine Fault Tolerant).

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


Блокчейны

На самом деле, блокчейн, лежащий в основе биткоина (2008), является решением проблемы византийских генералов, когда с высокой вероятностью предлагается консенсус с использованием механизма POW (proof of work) - доказательство выполнением работы.
Доказательство выполнением работы требует, чтобы каждый участник консенсусного процесса сжигал столько энергии, что византийским узлам было бы нецелесообразно захватывать сеть.
POW решения не могут работать для сети SAFE, поскольку они приводят к централизации власти участниками сети, которые могут позволить сжигать очень большие количества энергии для участия в консенсусном процессе.
Также это решение на практике не позволит достигать консенсуса достаточно быстро, и не обеспечит необходимую скорость сети SAFE.

В 2016 году Swirlds выпустила закрытый и запатентованный алгоритм HashGraph, который решил проблему асинхронной византийской отказоустойчивости довольно элегантно, используя известную концепцию сплетен (concept of gossip), чтобы решить её очень асинхронным и эластичным способом.

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

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

Конечно, ещё одна проблема с этим подходом заключается в том, что он запатентован, что исключает его как кандидата для применения в сети SAFE, поскольку весь наш код будет выпущен под лицензией GPLv3.

Ещё одно решение с 2016 года - алгоритм Honey Badger (желтый барсук).
Это алгоритм, который состоит из многих существующих алгоритмов, которые обеспечивают высокую вероятность ABFT консенсуса.
Две основные проблемы, которые мы имеем с этим алгоритмом - это довольно сложная задача.
Кроме того, как и HashGraph, для этого требуется использование алгоритма Common Coin.
Проблема, которую мы имеем с алгоритмом Common Coin, заключается в том, что для существующих реализаций обычно требуется надёжная фаза установки каждый раз, когда участники сети меняются.
Эта доверенная фаза установки, как правило, является синхронной.
В SAFE сети, с высокой нестабильностью присутствия узлов в сети, которой мы ожидаем, было бы очень сложно использовать Honey Badger и по-прежнему получать асинхронное поведение на практике.
Для полного решения существует способ, который называется распределённая генерация ключа, но это решение добавляет ещё один уровень математической сложности к уже достаточно сложному алгоритму.
Мы могли бы использовать Boney Badger отказоустойчивый византийский консенсус с распределенным генератором ключей, но мы нашли более элегантное решение.

PARSEC, протокол асинхронного, надёжного, безопасного и эффективного консенсуса является самым изящным решением проблемы ABFT, существующей сегодня.
В отличие от HashGraph, он полностью открыт, и можно доказать, что византийский противник не может долго контролировать консенсус.
Он математически гораздо менее сложный, чем Honey Badger, и консенсус может быть доказан с вероятностью, равной единице, а не полагаться на высокую статистическую вероятность консенсуса.
В отличие от блокчейн POW подхода, он эффективен и не жертвует вычислительными ресурсами пользователя на алтаре безопасности.
Мы опубликовали все подробности об алгоритме в запросе на комментарий и отредактировали краткий документ, который демонстрирует математические доказательства для всех свойств алгоритмов.

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

Как уже было сказано, алгоритм довольно изящный и простой, что даёт мне уверенность, что я смогу передать все его идеи, не погружаясь слишком глубоко в заумные математические концепции.

В первом приближении PARSEC в базируется на двух основных идеях:

Одна из таких идей - применение метода сплетен (Gossip), который очень эффективен для взаимодействия узлов между собой.
Это костяк нескольких современных консенсусных протоколов, таких как HashGraph и Avalanche.

Ещё одна ключевая идея нашего решения - это асинхронное двоичное соглашение или ABA (Asynchronous Binary Agreement).
Этот фрагмент головоломки похож на общую проблему асинхронной византийской отказоустойчивости ABFT, которую решает PARSEC, за исключением того, что соглашение может быть достигнуто только по двоичному значению. Бинарное значение - это значение, которое может быть истинным или ложным; как ответ на вопрос "да / нет". Мы глубоко вдохновляемся работой Мостефауи (Mostefaoui) и других, что даёт элегантное решение для ABA.

Итак, наше описание алгоритма будет выглядеть следующим образом: во-первых, мы объясним что такое протокол Gossip и некоторые его свойства.
Затем мы объясним, как использование Gossip позволит свести асинхронное византийское соглашение к асинхронному бинарному византийскому соглашению (Asynchronous Binary Byzantine Agreement).
Наконец, мы объясним, как мы перенесли элегантное существующее решение проблемы ABA, чтобы оно интегрировалось с методом сплетен и решило еще одно серьёзное препятствие в этом подходе.


Сплетни (gossip)


Как я уже дал понять, наш алгоритм глубоко укоренён в метод сплетен.
Теперь я объясню, что это значит.

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

В компьютерной модели каждый узел для сплетен выбирает другие узлы случайным образом со случайной периодичностью и делится с ними всеми новостями о том, что они не знают, но известно этому узлу.
Узел, с которым произошла коммуникация, фиксирует новую для себя информацию, а также делится своей информацией.
Мы называем эту запись сообщений графом сплетен. Это ориентированный ациклический граф (DAG, Directed Acyclic Graph).


Работа протокола сплетен на примере


Но картинки говорят громче слов, поэтому позвольте мне объяснить метод сплетен на примере.
Назовём наши узлы Alice, Bob, Carol и Dave (A, B, C и D).
Они готовы сплетничать друг с другом.


Alice случайно выбирает Bob и посылает ему запрос сплетни.
Затем она выкладывает всю информацию, которую знает к текущему моменту, но которая неизвестна Bob.


Bob записывает информацию, полученную им от Alice, создавая событие Gossip и добавляя его в свой граф сплетен.

Событие сплетни содержит:
- Хэш последнего события сплетни Alice
- Хэш последнего события сплетни Bob
- Вся информация, которую он узнал от Alice, и тот факт, что это она инициировала сплетни
- Доказательство Bob (он подписывает вышеперечисленную информацию своим криптографическим открытым ключом, поэтому любой, кто видит это событие, может точно знать, что его создал он)


Теперь, когда Bob получил запрос GossipRequest от Alice, он обязан отреагировать на него как можно скорее.


Но поскольку сеть асинхронна, до того, как Bob собрался ответить Alice, Dave случайным образом выбрал для обмена сплетнями Carol. Точно так же он посылает ей запрос на сплетню, который требует, чтобы Carol ответила, как только сможет.


Теперь Bob рассказывает свои сплетни Alice.
Зелёная стрелка означает что это ответ.
Он сообщает ей всю информацию, которая была известна только ему.
Она записывает это, создавая событие Gossip и добавляя его к своему графу сплетен.


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


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


Dave случайным образом выбирает для разговора Bob, который теперь знает, что узнал Dave.


Carol отвечает на более ранние сплетни Dave, и Dave записывает это в своём графе сплетен.


Bob отвечает на предшествующие сплетни Dave, и Dave записывает это в своём графе сплетен.
Мы остановимся на этом, так как больше сплетен будет тяжело поместить на иллюстрации, но это ограничение не касается нашего протокола, этот процесс продолжается со временем, и граф сплетен каждого узла постоянно растёт, поскольку протокол сплетен продолжает работать.


Свойства сплетен

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


Возьмём два произвольных события: b2 и d0.

Мы говорим, что b2 видит d0, поскольку существует направленный путь через граф сплетен, идущий от d0 к b2.


Здесь мы отметим свойство события сплетен сильно видеть другое событие (strongly seeing).

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

Супербольшинство означает больше, чем 2/3 узлов, поэтому в нашем примере супербольшинством будет 3 узла.

Заметим, что здесь b2 видит (seeing) d0, но не сильно, поскольку путь между b2 и d0 связывает только Bob и Dave.
Это всего лишь 2 узла, что меньше супербольшинства.
Однако мы видим, что a2 сильно видит d0, поскольку путь между a2 и d0 связывает Alice, Carol и Dave, что является супербольшинством.

Обратите внимание, что это не должен быть только один путь.


Например, здесь d3 также сильно видит d0, поскольку, рассматривая все пути между d3 и d0, эти пути содержат события сплетен, созданные Bob, Carol и Dave, которые составляют супербольшинство узлов.


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

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

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

Сплетни:
- метод коммуникации
- эффективность
- асинхронность

Граф сплетен:
- все узлы движутся к одному общему графу событий сети

Свойства сплетен:
- видение (seen)
- сильное видение (strongly seen)


Преодоление разрыва: от сплетен к консенсусу

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

Однако до сих пор остаётся большой разрыв между сплетнями и соглашением с определенным порядком всех событий.

Чтобы преодолеть этот пробел, давайте определим одно дополнительное понятие: событие интересной сплетни.


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

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

В более общем контексте интересными событиями сплетен могут быть те, которые несут голосование за определенное действие или, как правило, определённый вид информации.
Короче говоря, то, что делает сплетню интересной - это информация, которую она несёт.

Эта та информация, которую мы пытаемся упорядочить через отказоустойчивый византийский консенсус.

В контексте событий интересных сплетен в графе сплетен византийский консенсус может быть выражен следующим образом:

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

Меня просят выбрать следующее событие интересной сплетни для согласования в сети.

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

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

ОК. Мы переформулировали проблему византийского консенсуса применительно к контексту сплетен.

Это хорошее начало, поскольку сплетни обладают некоторыми хорошими свойствами, два из которых:
- хорошее масштабирование
- это эффективный способ асинхронной работы

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

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

Эта более простая проблема называется бинарным византийским консенсусом, это удобно для записи, но давайте не будем опережать себя.

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


Наблюдатель

Первая из этих двух концепций - это Наблюдатели.

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

Я понимаю, что это звучит немного абстрактно, поэтому приведу иллюстрацию.


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

Событие сплетни, обозначенное d3, является наблюдателем.
Давайте убедимся в этом!


Событие сплетни d3 видит интересное прямоугольное событие Dave через пути, проходящие через Bob, Carol и самого Dave. Это 3 из 4 узлов, что является супербольшинством.

Таким образом, d3 сильно видит прямоугольное событие Dave.


d3 также сильно видит событие прямоугольной сплетни Alice, поскольку он может видеть его через Alice, Bob и Dave.


Наконец, d3 сильно видит событие прямоугольной сплетни Carol через Bob, Carol и Dave.


Поэтому d3 сильно видит прямоугольные события Alice, Carol и Dave.

Он сильно видит интересные события, созданные супербольшинством узлов.

Следовательно, b3 удовлетворяет нашему определению наблюдателя.

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

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


Мета голосование

Второй дополнительной концепцией будет мета-голосование.

Каждый раз, когда узел (скажем, Dave) пытается найти следующее событие интересной сплетни, он может проголосовать за любой узел (например, Alice).

Dave в мета-голосовании за Alice - это ответ Dave на вопрос:
Мой старший наблюдатель сильно видит интересное событие, созданное этим узлом?


Так, старший наблюдатель Dave сильно видит интересное событие, созданное Alice?

Да, это так, мы видели это несколько слайдов назад.

Следовательно, Dave мета голос за Alice это правда.


Старший наблюдатель Dave сильно видит интересное событие, которое создал Bob?

Нет!
Я выделил все направленные пути между d3 и событием сплетен прямоугольника Bob.
Они проходят только через Bob и Dave, что меньше 2/3 узлов, такое количество узлов не является супербольшинством.

Мета голос Dave за Bob ложный.


Соединение отдельных частей воедино


Я обещал упростить византийский консенсус до бинарного византийского консенсуса после двух дополнительных определений.
Определения я дал. Теперь пришло время выполнить моё обещание.

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

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

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

Это значение является ответом на вопрос истинно / ложно, и это двоичное значение.

Теперь, как мы перейдём от достигнутого бинарного соглашения к полному консенсусу, к которому мы стремимся?

Вот как это делается:
Как только все придут к согласию по каждому мета голосу, выберите все те узлы, для которых согласованный мета-голос является истинным.
Рассмотрим старейшее событие интересной сплетни от каждого из этих узлов.

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


Почему это работает?


to be continue...
Вернуться к началу Перейти вниз
Посмотреть профиль http://free.userboard.net
 
PARSEC, новый протокол безопасного интернета
Предыдущая тема Следующая тема Вернуться к началу 
Страница 1 из 1
 Похожие темы
-
» Сказка про репку на новый лад
» голуби не могут привыкнуть к голубятне.

Права доступа к этому форуму:Вы не можете отвечать на сообщения
Посторонним в :: Децентрализованные сети :: MaidSafe-
Перейти: