Про консенсус, PoS и PoW и распределенные системы
«Ни Proof-of-Work, ни Proof-of-Stake не являются алгоритмами консенсуса — это лишь механизмы»
Автор: Соня Сун
14 января
«Ни Proof-of-Work, ни Proof-of-Stake не являются алгоритмами консенсуса — это лишь механизмы»
Про бэкграунд
Я попал в программу от Ethereum Foundation. Это было во время пандемии — тогда оборвались некоторые планы, но вместе с этим появились новые возможности. Ethereum Foundation в некотором смысле отвечает за протокол Ethereum и заботится о его комьюнити. Идея программы была набрать группу людей, в основном студентов, и помочь им изучать основы распределенных систем, блокчейнов, протокола и экосистемы Ethereum.
Это был интересный опыт. Я тогда уже что-то да понимал в распределенных системах, но только после этой программы мне на практике раскрылась их мощь. У нас даже была возможность пообщаться с Виталиком Бутериным во время презентаций наших финальных проектов.
После этого я увлекся распределенными вычислениями. Написал свою выпускную работу на тему из области распределенных систем передачи активов вместе с Петром Кузнецовым, профессором в Telecom Paris и исследователем в области распределенных систем.
Мы доказали, что криптовалюта возможна без консенсуса. В работе было отражено, что открытую криптовалюту можно реализовать на основе Proof-of-Stake и без использования консенсуса. С того момента я и Петр Кузнецов начали работать в этой сфере вместе.
Сейчас у меня два рода деятельности. Во-первых, я разработчик в одной крупной компании. Во-вторых, я занимаюсь рисерчем в области распределенных вычислений совместно с исследовательской группой из университета Telecom Paris.
В распределенные вычисления попал случайно. Никогда не думал, чтобы достаточное время уделять науке и исследованиям. Мне нравилась математика и компьютерные науки, но это не выходило за рамки университета.
Но я всё-таки разработчик — в одной из компаний FAANG. Задача моей команды там — поддержание integrity-платформы, с точки зрения технических задач — это микс ml, distributed systems и data analysis. Уже дополнительно к этому я занимаюсь рисерчем в сфере распределенных вычислений и крипты.
Про распределенные вычисления
Распределенные вычисления — это такая область компьютерных наук, которая изучает распределенные системы. Распределенная система — система, когда у вас есть много компьютеров (машин), которые решают вместе какую-то задачу. Они решают ее путем произведения локальных вычислений и коммуникаций между друг другом.гом. То есть они могут локально что-то сделать, как любые обычные программы, но при этом так же общаться между друг другом.
Распределенные системы — про масштабируемость и корректность. Например, нам важно, чтобы система могла работать с большим количеством клиентов и делать это корректно или консистентно.
Сейчас все сервисы построены на распределенных системах — почти все, с которыми мы работаем. Стандартный пример задачи, которая решается в распределенных системах, — это репликация данных.
Возьмем Youtube и представим, что он работает на одном компьютере с одним сервером, который хостит запросы всех клиентов. Понятно, что мы так далеко не уедем, ведь такой подход не масштабируется. Наша идея —вместо одного компьютера, производящего вычисления, использовать несколько. Несколько серверов, которые будут отвечать на запросы/хранить данные. Но тут возникают проблемы: например, разные данные могут храниться на разных серверах, поэтому запрос на один сервер может теоретически дать ответ, отличный от аналогичного запроса на другой сервер. Теория распределенных вычислений здесь предлагает варианты того, как фундаментально эти проблемы можно решить и можно ли вообще.
Можно провести аналогию с Биткоин. Там нет центральной финансовой системы — банка, — которая бы обрабатывала платежи. Вместо этого все активные участники сети, то есть майнеры, проверяют, можно ли подтвердить транзакцию или нет — и договариваются об этом.
Транзакция в распределенной системе — это не самая очевидная задача. Нужно понять, например, использовала ли уже Алиса те деньги, которые она переводит Бобу в данный момент. Возможно, что да, — она уже потратила все свои деньги, но активные участники сети об этом просто не знают.
Децентрализованные и распределенные системы — синонимы. Почти. Точнее, это может зависеть от трактовки. Например, под распределенной системой иногда могут понимать систему, состоящую из несколько серверов, но при этом все эти сервера координируются одной единой машиной. А когда говорят «децентрализованная», уточняют, что все устройства системы участвуют для решения задачи/принятия решения.
Про академический рисерч
Под рисерчем можно понимать что угодно: маркетинговый или UX. Но в данном случае мы говорим про академический/научный рисерч. Научная деятельность обычно ставит перед собой главной задачей понять что-то новое. Так, мы пытаемся понять, как решить новую задачу, как это сделать быстрее/эффективнее или другим способом, или, наоборот, показать, что это сделать нельзя.
Мы занимаемся научным рисерчем в области распределенных вычислений. Конкретно я изучаю темы, которые связаны с распределенными системами передачи — криптовалютами. С появлением Биткоина к области появился очень большой интерес. Сатоши Накамото, кто бы он ни был, предложил систему, в которой можно делать платежи, обмениваться деньгами при отсутствии какого-то центрального банка.
Сатоши рассмотрел задачу онлайн-платежей в распределенной системе. Там абсолютно нет регулятора — отсутствует банк и централизованное место обработки транзакций, и при этом в открытой системе кто угодно может присоединиться к ней, чтобы отправлять и верифицировать транзакции.
До Биткоина никто решением такой задачи в такой модели не занимался вообще. При этом, все элементы системы, которую предложил Сатоши, так или иначе существовали: теория распределенных систем в модели, где могут существовать плохие, или, как обычно говорят, Византийские участники, существовала много десятилетий. И, как ни странно, казалась многим несколько бесполезной; Merkle Trees появились в 1979 году; Proof-of-Work был предложен в 90-х как средство борьбы со спамом.
Но никто не собирал эти части вместе. Не пытались построить системы децентрализованной системы платежей. Исследователи заметили Биткоин, стали предлагать какие-то улучшения, придумывать новые протоколы, которые привносили бы улучшения в изначальный дизайн.
Тогда появились альткоины. Они используют улучшенные технологии. Но между ними были общие моменты — они использовали блокчейн, чтобы реализовать систему децентрализованных платежей.
Но тут речь не совсем о форках. В целом, появилось множество других криптовалют. Например, Ethereum. Все предлагали свои улучшения и реализации. Но все они так или иначе использовали блокчейн.
Блокчейн — это довольно известная распределенная структура данных, если связывать это всё с распределенными вычислениями. В этой системе можно что-то записать в конец и прочитать информацию по индексу блока. Фундаментальная задача — сделать такую распределенную структуру данных консистентной. Клиенты взаимодействуют с такой структурой данных, и у них должно создаваться впечатление, будто они обращаются к структуре данных, которая реализована на одном сервере/компьютере.
Из определения блокчейна можно видеть, что это структура данных, которая строит линейный порядок, в данном случае на множестве записываемых блоков. Из теории распределенных вычислений мы знаем, что для построения линейного порядка нужно уметь решать задачу консенсуса.
Про алгоритмы достижения консенсуса
Консенсус — это просто задача в распределенных системах. Она формулируется так: есть множество участников системы, они предлагают какие-то значения, и всем корректным участниками системы нужно согласиться на одном из этих значений. Эта задача в некотором плане доказуемо сложная. И в некотором плане она разделяет мир задач в распределенных вычислениях на те, в которых нужно использовать консенсус, и те, где его использовать не обязательно. Можно их условно называть сложными и простыми.
Когда я только знакомился с криптой, меня удивляла одна вещь. Тогда я уже немного знал про консенсус и распределенные системы и каждый раз, когда люди говорили, что proof-of-work — это консенсус, а proof-of-stake — это такой-то вид алгоритма консенсуса, я впадал в ступор. Потому что это не так.
Proof-of-Work — не консенсус. Консенсус — это, как мы уже выяснили, просто задача в мире распределенных вычислений. Ее можно решать разными алгоритмами, но ни Proof-of-Work, ни Proof-of-Stake не являются алгоритмами консенсуса. Это лишь некоторые механизмы, которые нам помогают гарантировать корректность алгоритма в определенной модели.
Есть открытые и закрытые распределенные системы. Условно. Их еще называют permissionless и permissioned. Открытая система — это такая система, в которой мы считаем, что к нам может добавиться кто угодно. В случае криптовалют — кто угодно может начать посылать и валидировать транзакции. В закрытой системе мы считаем, что можем контролировать, кто может валидировать транзакции.
Между ними есть одна главная разница. В закрытых системах мы можем сделать предположение о том, что условно не больше ⅓ всех участников сети являются Византийскими репликами. В открытых системах такого предположения делать нельзя — по сути, плохие акторы могут создать неограниченное число виртуальных реплик и количественно доминировать в системе — так называемая атака Сивиллы.
На что это влияет на практике? В закрытых системах мы можем решить задачу по достижению консенсуса, не прибегая ни к каким дополнительным механизмам. Так как мы можем сделать обоснованными свойствами системы предположение об относительном малом количестве Византийских реплик (меньше трети), и в таком случае все задача решается без каких-то дополнительных механизмов. Примеры алгоритмов — Paxos и Raft. В открытых системах же нам нужно добиться того, чтобы большое количество плохих акторов не повлияли на корректность алгоритма консенсуса. Для этого мы можем использовать какие-то механизмы, которые смогут отсечь большую часть плохих участников сети.
Один из таких механизмов — это Proof-of-Work. В чем идея: если участник хочет что-то сделать, например провалидировать транзакции, он должен обладать какой-то вычислительной мощностью. Создавая виртуальных участников, плохие акторы не увеличивают свою вычислительную мощность — она остается такой же.
Proof-of-Work можно отделить от самого механизма консенсуса. Как и другие механизмы предотвращения атаки Сивиллы, такие как Proof-of-Stake, Proof-of-Work, Proof-of-Space, Proof-of-Space-time, они развиваются в целом несколько раздельно. Можно отдельно подобрать механизм, который поможет гарантировать корректность консенсуса в открытой сети и отдельно выбрать алгоритм консенсуса.
Механизм Proof-of-Work — энергозатратный. Предположим, вы добросовестный участник, который хочет просто обслуживать систему, то есть валидировать транзакции, и получать за это какое-то предусмотренное протоколом вознаграждение.
Для того, чтобы «доказать» системе, что вы не пытаетесь ее атаковать, вы тратите много компьютерных мощностей, решая какие-то очень большие криптографические пазлы методом подбора. Такой механизм позволяет избавиться от участников, у которых за собой ничего нет в плане вычислительной мощности. Именно таких обычно могут контролировать Византийские участники. Да, такой механизм позволяет обезопасить систему, но ничего полезного майнеры не производят. Они просто тратят энергию, чтоб доказать, что они являются реальными сущностями и им в каком-то смысле можно верить.
Про отличия алгоритмов консенсуса
PoW влияет на пропускную способность протокола. Количество операций, завершающихся за единицу времени, уменьшается. Не важно, что реализовано с помощью этого механизма в распределенной системе — обычная криптовалюта или какая-то более общая задача, например state machine replication. Проблемы остаются те же: непропорциональная задаче энергозатратность, а также низкая пропускная способность/скорость протокола.
PoS основан на базовых аспектах теории игр. Главная идея проста: привязать количество голосов или же вес участника системы к количеству его средств в системе — так называемый stake. Смысл в том, что завладеть достаточным количеством средств Византийским участникам сложно.
В то же время, чем больше у участника денег, то есть чем больше его stake, тем меньше он хочет отклоняться от протокола, то есть становиться Византийским участником. Почему же увеличивается мотивация следовать протоколу при большом количестве средств? В PoS-системах подорвать корректность системы можно, только если Византийские участника аккумулируют большое количество средств. Но в таком случае они будут первыми, кто от этого пострадает, ведь ценность «монет» в скомпрометированной системе упадет до нуля. По сути, чем больше активов у участника сети, тем больше он заинтересован в том, чтобы всё работало так, как задумано.
PoS — не энергозатратный и может обеспечить защиту от атаки Сивиллы — так же, как и PoW. А еще он позволяет увеличить количество операций, выполняемых в системе.
Это более интересный механизм, как по мне. И не только ввиду своей эффективности, но и в плане своей идеи. Дополнительно он привносит хорошую экономическую базу, позволяя легче перенести многие финансовые механизмы из реальной жизни.
Про протоколы без консенсуса
Лично я люблю решать задачи вовсе без алгоритмов консенсуса. В частности, мне интересны протоколы криптовалют, которые не используют консенсуса вообще или предлагают какие-то гибридные алгоритмы, где использование консенсуса минимально. Они пока что не так часто встречаются на практике, но появляется всё больше и больше научных работ на эти темы. Это интересно в теоретическом плане. По сути, мы пытаемся ответить на вопрос о том, что еще мы можем сделать без использования такого мощного механизма как консенсус, о чем до этого даже никто не думал.
Есть несколько моделей-противников (adversary/attackers). Это в теоретическом плане. Первая модель называется static adversary. В такой модели мы предполагаем, что наш противник захватывает определенные реплики с самого начала, но мы не знаем, кого именно.
Например, из 11 участников сети adversary управляет 3 Византийскими репликами с самого начала. Стоит заметить, что Византийские реплики какое-то время могут быть неотличимы от корректных, то есть некоторый внешний наблюдатель за системой будет видеть, что реплики полностью следуют протоколу. Однако, если какой-то участник вдруг отклоняется от алгоритма, который ему был дан, считается что он всегда был Византийским. Обычно такая модель используется в permissioned-системах.
Другая модель — это dynamic adversary. В такой системе мы считаем, что противник может сам выбирать, каких участников захватить/коррумпировать в зависимости от исполнения. В некотором плане множество участников, которые являются Византийскими, постоянно эволюционирует. Обычно считается, что это множество может только расти, то есть, если участник однажды стал Византийским, то он остается таким навсегда. Такая модель обычно предполагается в permissionless-системах.
Пример: в PoS-системе участник владеет большим количеством средств, — он корректный. Через какое-то время он переводит все свои средства кому-то другому, например в качестве платы за товар/услуги. Теперь, так как он ничем не рискует, он может либо просто попытаться навредить системе, либо просто ослабить защиту своего устройства, и оно может быть взломано.
Распределенные протоколы в обеих системах одинаковы. Они реализованы таким образом, чтобы предотвращать/не допускать ошибки в системе. Каждая реплика, которой приходит сообщение, может каким-то образом его проверить и понять, валидно ли оно. Один из способов это сделать — использовать криптографические примитивы.
Криптографические примитивы помогают установить, что сообщение действительно было отправлено репликой, — это особенно важно, если сообщение приходит не напрямую, а через какой-то алгоритм бродкаста через посредников. Каждая реплика также понимает, какие действия должна совершить другая реплика, чтобы ответить на сообщение, так как алгоритм публичный. Поэтому мы почти всегда можем проверить, что сообщение, которое пришло нам, имеет смысл.
Есть еще другое направление в распределенных системах. Оно изучает способы обнаружить ошибки в системе. Мы допускаем, что протокол может сломаться, но при этом мы можем установить, что результат протокола не соответствует гарантиям найти участника, который попытался скомпрометировать систему, а затем вывести его из системы. По сути, для каждого нарушения протокола корректные реплики могут найти доказательство того, что нарушение произошло, а затем произвести самовосстановление системы. Я сам этим детально не занимался, но я знаю хорошую статью на эту тему: Accountability and Reconfiguration: Self-Healing Lattice Agreement.
Задача консенсуса сама по себе является «доказуемо сложной». Фундаментальный результат в теории распределенных вычислений, теорема Фишера-Линча-Патерсона (FLP Theorem), говорит следующее: «Нельзя реализовать детерминированный алгоритм консенсуса, который бы гарантированно завершался, если хотя бы одна реплика может отказать». Таким образом, практически любой алгоритм консенсуса так или иначе пытается обойти результат Теоремы FLP одним из следующих путей:
– алгоритм предполагает, что система синхронна и использует тайминги на время отправки/получения сообщений;
– алгоритм предполагает, что система синхронна и использует тайминги на время отправки/получения сообщений;
– алгоритм использует рандомизацию и тем самым становится вероятностным, и гарантии предоставляются с некоторой вероятностью;
– алгоритм реализуется таким образом, что в наихудшем варианте исполнение он может не завершиться, а участники системы никогда не придут к результату.
В целом, это основные фундаментальные факторы, которые могут повлиять на корректность алгоритмов. Что касается практики, то при правильной реализации алгоритма, аккуратном обосновании гарантии его свойств, обычно всего этого получается избежать, а точнее свести вероятность плохих исходов к минимуму — и все как-то с этим живут.
Что касается конкретного алгоритма, то тут надо внимательно читать статьи про каждый из них и смотреть, какие предположения о системе делают авторы, какие свойства/гарантии протокол предлагает и доказательства того, почему всё работает именно так.
Я не изучаю область использования ИИ в распределенных вычислениях, но в целом знаю, что довольно-таки интересной научной и инженерной задачами является проблема того, как перенести алгоритмы глубокого обучения на распределенные системы, чтобы получить буст в плане перформанса.
А если просто спекулировать, то интересно, как алгоритмы deep learning могут помочь в задачах безопасности системы и выявления потенциальных Византийских реплик.
Буткемп: Solidity-разработчик
От основ Solidity до деплоя на мейннете.
Поделиться
Вам может понравиться
Инфа уже у менеджера
Выйдем на вас быстрее шести подтверждений последнего блока Ethereum
Интересно погрузиться в крипту?
Поможем выбрать буткемп!
или
Или свяжитесь