Консенсус в распределённых системах: чем он отличается от PoW и PoS

Интервью вышло в январе 2023 года. Состояние исследований описано на тот момент.

Путь в распределённые вычисления

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

Это был интересный опыт. Я тогда уже кое-что понимал в распределённых системах, но только после этой программы увидел на практике, какая в них мощь. У нас даже была возможность пообщаться с Виталиком Бутериным на презентациях наших финальных проектов.

После этого я увлёкся распределёнными вычислениями. Выпускную работу по распределённым системам передачи активов я написал вместе с Петром Кузнецовым, профессором Télécom Paris и исследователем распределённых систем.

Мы доказали, что открытую криптовалюту можно реализовать на основе Proof-of-Stake вообще без консенсуса. С тех пор мы с Петром Кузнецовым работаем в этой области вместе.

Сейчас у меня два занятия. Во-первых, я разработчик в одной крупной компании. Во-вторых, занимаюсь рисерчем в области распределённых вычислений вместе с исследовательской группой Télécom Paris.

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

Основная работа у меня всё-таки инженерная, в одной из компаний FAANG. Моя команда там поддерживает integrity-платформу, а по технической части это микс ML, распределённых систем и анализа данных. Рисерч в распределённых вычислениях и крипте идёт дополнительно к этому.

Что такое распределённые вычисления

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

Распределённые системы — это про масштабируемость и корректность. Например, нам важно, чтобы система работала с большим количеством клиентов и делала это корректно, или, как говорят, консистентно.

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

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

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

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

Децентрализованные и распределённые системы — почти синонимы. Точнее, это зависит от трактовки. Иногда распределённой называют систему из нескольких серверов, которые координирует одна главная машина. А когда говорят «децентрализованная», подчёркивают, что в решении задачи и принятии решений участвуют все устройства системы.

Академический рисерч и биткоин

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

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

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

До биткоина задачу в такой модели не решал вообще никто. При этом все элементы системы Сатоши так или иначе уже существовали. Теория распределённых систем в модели, где могут быть плохие, или, как обычно говорят, византийские, участники, существовала много десятилетий и, как ни странно, многим казалась несколько бесполезной. Деревья Меркла появились в 1979 году. Proof-of-Work предложили в 90-х как средство борьбы со спамом.

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

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

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

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

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

Консенсус как задача

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

Когда я только знакомился с криптой, меня удивляла одна вещь. Я уже немного знал про консенсус и распределённые системы и каждый раз впадал в ступор, когда слышал, что Proof-of-Work — это консенсус, а Proof-of-Stake — такой-то вид алгоритма консенсуса. Потому что это не так.

Proof-of-Work — не консенсус. Консенсус, как мы уже выяснили, — это задача в мире распределённых вычислений. Её можно решать разными алгоритмами, но ни Proof-of-Work, ни Proof-of-Stake не алгоритмы консенсуса. Это лишь механизмы, которые помогают гарантировать корректность алгоритма в определённой модели.

Распределённые системы условно делятся на открытые и закрытые, их ещё называют permissionless и permissioned. В открытой системе мы считаем, что к ней может присоединиться кто угодно. В случае криптовалют это значит, что кто угодно может начать отправлять и валидировать транзакции. В закрытой системе мы считаем, что можем контролировать, кто валидирует транзакции.

Главная разница между ними такая. В закрытых системах можно предположить, что, условно, не больше ⅓ всех участников сети — византийские реплики. В открытых системах такое предположение делать нельзя: плохие акторы могут создать неограниченное число виртуальных реплик и численно доминировать в системе. Это так называемая атака Сивиллы.

Один из таких механизмов — Proof-of-Work. Идея в том, что участник, который хочет что-то сделать, например провалидировать транзакции, должен обладать вычислительной мощностью. Создавая виртуальных участников, плохие акторы свою вычислительную мощность не увеличивают, она остаётся прежней.

Proof-of-Work можно отделить от самого алгоритма консенсуса. Он, как и другие механизмы защиты от атаки Сивиллы, например Proof-of-Stake, Proof-of-Space и Proof-of-Spacetime, развивается отдельно. Можно отдельно подобрать механизм, который поможет гарантировать корректность консенсуса в открытой сети, и отдельно выбрать алгоритм консенсуса.

Proof-of-Work — энергозатратный механизм. Предположим, вы добросовестный участник, который просто хочет обслуживать систему, то есть валидировать транзакции, и получать за это предусмотренное протоколом вознаграждение.

Чтобы «доказать» системе, что вы не пытаетесь её атаковать, вы тратите много вычислительных мощностей и методом перебора решаете очень трудоёмкие криптографические пазлы. Такой механизм отсекает участников, за которыми не стоит никакая вычислительная мощность, а именно такими участниками обычно и управляет византийский противник. Да, это обезопасит систему, но ничего полезного майнеры не производят. Они просто тратят энергию, чтобы доказать, что они реальные сущности и им в каком-то смысле можно доверять.

Чем PoW отличается от PoS

PoW снижает пропускную способность протокола: за единицу времени завершается меньше операций. Неважно, что реализовано с помощью этого механизма: обычная криптовалюта или более общая задача, например state machine replication. Проблемы остаются те же: энергозатраты, непропорциональные задаче, и низкая пропускная способность протокола.

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

При этом чем больше у участника денег, то есть чем больше его стейк, тем меньше ему хочется отклоняться от протокола, то есть становиться византийским. Почему мотивация следовать протоколу растёт вместе со средствами? В PoS-системах подорвать корректность системы можно, только если византийские участники накопят много средств. Но тогда они первыми пострадают, ведь ценность «монет» в скомпрометированной системе упадёт до нуля. Чем больше у участника активов, тем сильнее он заинтересован в том, чтобы всё работало так, как задумано.

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

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

Протоколы без консенсуса