📝 Алгоритм консенсуса делегированного доказательства долей (DPOS) - недостающая белая бумага (перевод статьи @dantheman)

Перед вами недостающая белая бумага и анализ алгоритма делегированного доказательства долей (DPOS). Цель этой бумаги - предоставить анализ работы DPOS и того, что делает его столь надежным. Давнее описание DPOS можно найти на bitshares.org; тем не менее, то описание включает в себя множество аспектов, на самом деле не являющихся частью процесса достижения консенсуса.

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

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

Кратко об алгоритме DPOS

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

Чтобы упростить объяснение работы этого алгоритма, я предлагаю взять трех производителей блоков: A, B и C. Так как для разрешения всех ситуаций консенсус требует согласия 2⁄3 + 1, в этой упрощенной модели мы будем считать, что производитель C является нарушителем порядка. В реальном мире обычно есть 21 или более производителей блоков.

Нормальное функционирование

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

Форк меньшинства

Вплоть до 1⁄3 всех нод могут быть вредоносными или неисправными и создать форк меньшинства. В таком случае форк меньшинства будет производить только один блок каждые 9 секунд, тогда как форк большинства будет производить 2 блока каждые 9 секунд. И опять же, честные 2⁄3 большинства всегда будут создавать более длинную цепь, нежели меньшинство.

Двойное производство изолированным меньшинством

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

Фрагментация сети

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

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

Двойное производство присоединенным меньшинством

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

Последний необратимый блок

Существует возможность, что в случае фрагментации сети несколько форков продолжат расти в течение длительного периода времени. В перспективе самая длинная цепь выиграет, но наблюдателям нужен способ узнать наверняка, когда блок точно является частью самой быстрорастущей цепи. Это можно определить, увидев подтверждение от 2⁄3+1 производителя блоков.

На рисунке ниже блок B был подтвержден C и A, что представляет собой подтверждение от 2⁄3+1, а значит, мы можем заключить, что никакие другие цепи не могут быть длиннее, если эти 2⁄3 производителей честны.

Заметьте, что это “правило” схоже с 6-блочным “правилом” подтверждения в Биткойне. Некоторые смышленые индивиды могут создать такую последовательность событий, когда две ноды могут оказаться на разных последних необратимых блоках. Этот пограничный случай требует от атакующего обладанием тотальным контролем над задержкой в коммуникации и способностью воспользоваться этим контролем не единожды, а дважды и с разрывом в несколько минут. Если бы такое случилось, долгосрочное правило самой длинной цепи всё равно осталось бы применимо. Мы считаем, что вероятность такой атаки стремится к нулю, а ее экономические последствия столь незначительны, что не стоит и беспокоиться.

Отсутствие кворума производителей

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

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

Коррумпированность большинства производителей

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

Транзакции как доказательство долей (Transactions as Proof of Stake - TaPoS)

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

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

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

Детерминированная перетасовка производителей

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

Заключение

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

В итоге DPOS достигает значительного уровня безопасности за счет алгоритмов выбора производителей блоков и проверки высокого качества нод и индивидуальности их владельца. Задействуя процесс утверждения, голосование обеспечивает, что даже некто с 50% активной силы голоса не сможет выбрать в одиночку хоть одного производителя.

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

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

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

Оригинал поста: ЗДЕСЬ