Криптовалюта и блокчейн часто упоминаются вместе, поскольку они тесно связаны между собой. Криптовалюты, такие как биткойн, представляют собой распределенные цифровые платежные системы, в основе которых используется блокчейн - распределенная бухгалтерская книга.
Возможно, вы уже знаете, что блокчейн используется не только для передачи цифровых активов. Существует множество других потенциальных случаев использования, таких как обмен медицинской информацией, голосование/выборы, владение цифровым искусством (также известным как NFTs) и даже азартные игры. Но учитывая, что это такая мощная технология, может ли она быть излишней только для электронных платежей? Можно ли создать криптовалюту без блокчейна? Да, можно!
В этом посте я хочу рассказать, почему блокчейн и консенсус - не единственное решение для разработки криптовалютного протокола и каковы альтернативы. Сначала мы вспомним немного теории, лежащей в основе биткойна и других криптовалют на базе блокчейна, затем рассмотрим, почему именно блокчейн не является необходимым для реализации децентрализованной системы платежей, и, наконец, сделаем обзор некоторых существующих систем, позволяющих переводить деньги в распределенной системе без использования блокчейна. Мы сосредоточимся в основном на теории, но в довольно легком стиле. Если есть интерес, я буду рад погрузиться глубже в будущих постах!
Проблема биткойна
Давайте сделаем небольшой шаг назад и ответим на фундаментальный вопрос: что является фундаментальной проблемой при разработке протокола для распределенной платежной системы (криптовалюты)?
Чтобы ответить на этот вопрос, обратимся к "белой книге" Биткойна [1]. Автор, Сатоши Накамото (кем бы он ни был), утверждал, что финансовым учреждениям нельзя доверять полностью. Действительно, банки имеют слишком большую власть над торговцами и клиентами, могут заморозить их деньги и являются единой точкой отказа: если в банке что-то пойдет не так, пострадают все (и клиенты, и торговцы). Более того, поскольку финансовые учреждения выступают в роли посредника, это увеличивает транзакционные издержки. Чтобы решить эту проблему, Накомото предложил систему цифровых активов, Биткойн, которая позволила бы перемещать деньги между людьми в одноранговом режиме без какого-либо центрального органа, такого как банк. Вместо этого проблема платежей переносится в распределенную среду, где каждый участник имеет теоретически равные права.
Отказ от центрального органа, обрабатывающего все транзакции, не является уникальной особенностью Биткойна. Все системы передачи цифровых активов так или иначе стремятся сделать то же самое.
Технические детали могут быть разными, но, как отметил Накомото, независимо от того, как кто-то разработает свой криптовалютный протокол, есть одна фундаментальная проблема, которую всем придется решать - двойные траты.
Представьте, что у Алисы есть ровно 10 долларов. Как сделать так, чтобы она не смогла отправить эти 10 долларов Бобу и Кэрол? Конечно, когда у вас есть банк, это довольно просто, поскольку все транзакции проходят через него: транзакция Бобу или Кэрол пройдет первой, а другая не будет разрешена. Но можем ли мы сделать это без банка?
Блокчейн: как биткойн (и другие) решают проблему двойных трат
Итак, как (большинство) криптовалют решают эту проблему? Ну, скорее всего, вы уже знаете ответ - блокчейн!
В "белой книге" Биткойна Накомото предложил, что без централизованного финансового института, который проверяет транзакции, все участники системы (известные как майнеры) действуют как банк. В результате каждый должен знать обо всех транзакциях в системе и хранить свою версию "валовой книги транзакций". Для этого Bitcoin предлагает упорядочить транзакции в глобальном масштабе, используя разновидность широко известной абстракции в распределенных системах под названием распределенная бухгалтерская книга или блокчейн.
Распределенная бухгалтерская книга (блокчейн) - это распределенная структура данных, представляющая собой цепочку блоков данных, которая имеет две операции:
- Append(x) - записать блок данных x в конец цепочки;
- Read(n) - прочитать данные из n-го блока в цепочке.
Можно заметить, что в блокчейне мы строим последовательность блоков, которая определяет общий порядок на множестве блоков. Из теории распределенных вычислений мы знаем, что построение общего порядка в распределенной системе эквивалентно задаче консенсуса (когда участники предлагают значения и принимают решение по одному из них). Таким образом, в каждом блокчейне используется консенсус.
Однако Биткойн не мог взять какой-либо уже существующий протокол распределенной бухгалтерской книги. Это связано с тем, что Биткойн также нацелен на решение проблемы двойной траты в условиях отсутствия разрешений, когда любой может присоединиться к системе в качестве активного участника (известного как майнеры). Системы, работающие в таких условиях, должны быть устойчивы к пресловутым атакам Sybil, когда противник может контролировать неограниченное число злонамеренных (формально называемых византийскими) участников. В то же время традиционные бухгалтерские книги могут выдержать лишь небольшую часть византийских узлов (менее одной трети).
Для борьбы с этой проблемой Накомото предложил печально известный механизм proof-of-work, который искусственно замедляет майнеров, заставляя их решать криптографическую головоломку и делая количество противников несущественным, пока они не обладают большой вычислительной мощностью.
Возможно, вы уже слышали, что доказательство работы известно как очень энергоэффективное решение, и другие механизмы, такие как доказательство ставки (Ethereum, Algorand), доказательство пространства (SpaceMint) или доказательство пространства-времени (Chia) и другие, могут устранить огромное энергопотребление Биткойна, при этом предотвращая атаки Sybil.
Хотя выбор механизма (proof-of-work/stake/space/etc.) может варьироваться от одной системы цифровых активов к другой, а также другие технические детали, их суть остается неизменной. Они используют протоколы консенсуса для согласования общего порядка транзакций, которые обычно разбиваются на дискретные блоки, применяются к некоторому начальному состоянию (генезисному блоку) и формируют блокчейн. Этот подход проиллюстрирован на рисунке выше.
Консенсус - сложно, криптовалюта - легко
Реализации алгоритмов консенсуса, подверженных византийской угрозе, как известно, трудны и сложны. Обычно они требуют больших коммуникационных затрат (т.е. требуют отправки большого количества сообщений в системе) и полагаются на синхронные сети, рандомизацию, нетривиальную криптографию, детекторы сбоев или системы доверенной настройки. Наконец, они относительно сложны для понимания. Итак, проблема заключается в том, что инженеры не нашли способа решить ее простым и надежным способом? Не совсем так - это не просто практический вопрос. Теоретически консенсус является "трудной" проблемой, но что это значит?
Большинство вычислительных задач, с которыми мы сталкиваемся ежедневно (не все), относятся либо к P, которые можно решить за полиномиальное время, либо к NP - скорее всего, их нельзя решить полиномиально. Люди в компьютерной науке иногда называют эти классы "легкими" и "трудными". В распределенных вычислениях существует аналогичное понятие, и, грубо говоря, мир можно разделить на два класса: можете ли вы решить проблему асинхронно, без каких-либо предположений о времени, или она может быть решена только синхронно (т.е. вам нужны предположения о времени). Если вы хотите углубиться в детали, я думаю, что этот ответ на Quora вполне подходит для начала. Асинхронные проблемы "легкие", а те, которые могут быть решены только синхронно, "трудные". А консенсус, согласно фундаментальному результату распределенных вычислений, теореме FLP, является трудной проблемой.
Теорема FLP
В асинхронной системе передачи сообщений не существует детерминированного алгоритма консенсуса, который гарантированно завершится, если хотя бы один узел может выйти из строя.
Однако для проблемы двойной траты все обстоит иначе. В относительно недавней работе [2] было показано, что консенсусное число криптовалюты с k-общим счетом равно k. Проще говоря, если разрешено или предполагается, что счет контролируют не более k различных пользователей (клиентов), то для решения проблемы двойной траты средств необходимо, чтобы только k пользователей пришли к консенсусу. Учитывая, что обычно предполагается, что счет контролируется только 1 человеком, распределенная платежная система имеет консенсус номер 1. И это просто логично: если вы хотите правильно упорядочить транзакции по счету, только владелец этого счета должен прийти к соглашению с самим собой!
Это означает, что фундаментальная проблема double-spending может быть решена асинхронно и, следовательно, является доказуемо "легкой".
Таким образом, для решения проблемы двойной траты нам не нужно решать проблему консенсуса! Но важно сказать, что приведенный в статье факт изначально был доказан только для разрешенных систем: систем, где все активные участники (реплики, хранящие данные транзакций) известны, и можно предположить, что существует менее n/3 византийских пользователей. Например, это распределенные системы со статическим членством или механизмами доверенной установки. В любом случае, к системам без права доступа мы вернемся позже.
Пока же давайте запомним одну вещь:
Для того чтобы решить проблему двойных трат в децентрализованной системе, консенсус, в общем-то, не нужен.
Чтобы успокоить некоторых читателей, позвольте заметить, что приведенный выше факт не означает, что консенсус (и, следовательно, блокчейн) бесполезен в мире DeFi. Он по-прежнему необходим для создания смарт-контрактов общего назначения, однако для просто распределенной платежной системы он не нужен.
Реализация криптовалюты без блокчейна
Но поскольку вы можете реализовать криптовалюту без консенсуса, были ли предложены такие системы? Да! Давайте рассмотрим некоторые из предложенных решений для различных условий. Все они теоретически обоснованы и, более того, большинство из них демонстрируют хорошую производительность на практике).
Некоторые из представленных систем/документов написаны в соавторстве с автором этой заметки.
Безконсенсусная криптовалюта с разрешенным консенсусом
Первая бесконсенсусная система, которую мы рассмотрим, - Astro [3]. Это разрешенная система распределенной передачи активов, которая вместо консенсуса использует другие примитивы. В результате Astro не только превосходит Bitcoin, но и может достичь такой же (и даже большей) пропускной способности, чем платежная система VISA.
Система состоит из клиентов, узлов, которые отправляют транзакции, и реплик, которые подтверждают и хранят историю транзакций. Протокол работает следующим образом:
- Клиент выбирает реплику (представителя) и посылает ей транзакцию tx;
- Представитель рассылает транзакцию tx всем репликам;
- Правильные реплики утверждают транзакцию tx локально, и (опционально) представитель отправляет утверждение клиентам отправителя и получателя.
Здесь основная магия происходит на втором этапе, когда представитель передает транзакцию tx другим. Для этого он использует примитив, называемый византийской надежной трансляцией (Byzantine Reliable Broadcast, BRB). Этот примитив слабее, чем консенсус, и может быть реализован полностью асинхронно. Учитывая, что каждая транзакция имеет номер последовательности (каждый клиент использует свою собственную последовательность), эта абстракция гарантирует, что если реплика передает транзакцию tx с номером последовательности n, все корректные реплики передадут ту же транзакцию tx для номера последовательности n. Таким образом, протокол обеспечивает согласованность, т.е. никакие две корректные реплики не передадут две разные транзакции для одного и того же номера последовательности. Однако, обратите внимание, что если транслируются две противоречивые транзакции, ни одна из них не может быть доставлена. Таким образом, двойное расходование средств в системе невозможно и несет в себе множество рисков: вы можете потерять деньги, или ваш счет может быть заморожен.
Протокол BRB опирается на кворумы - наборы реплик, такие, что (i) существует хотя бы один кворум, где все реплики верны, (ii) любые два кворума пересекаются хотя бы одной верной репликой. Неформально, если каждый шаг распределенного протокола требует подтверждения кворумом реплик, мы гарантируем, что сможем прийти к решениям, которые будут правильными и не будут противоречить друг другу (последнее следует из второго свойства).
Система, основанная на кворумах, будет работать, только если мы можем предположить, что число византийских реплик меньше n / 3. Astro - разрешенная система, и мы можем контролировать реплики, которые входят в систему, такое предположение справедливо.
Вышеизложенное могло насторожить вас: поскольку каждый шаг должен быть подтвержден кворумом, насколько сложно увеличить число реплик в алгоритме? Будет ли он работать хуже? Это обоснованное беспокойство. Однако авторы предлагают способ решения этой проблемы - шардинг. Можно разбить систему на более мелкие подсистемы, называемые шардами, а затем запускать экземпляр протокола в каждом шарде отдельно. Таким образом, если Алиса посылает деньги Бобу и их представительские реплики находятся в одном шарде - ничего в протоколе не изменится. Однако если представитель Алисы находится в осколке А, а Боба - в осколке В, то протокол Astro выполняется в осколке А. Затем представительская реплика Алисы формирует сертификат при наличии кворума одобрения и отправляет его в осколок В, где происходит повторный обмен информацией, и Боб узнает о полученных деньгах.
Существует еще один интересный подход, основанный на вероятностной трансляции и вместо кворумов использующий выборки - реплики, которые представляют систему с достаточно высокой вероятностью. Это может принести пользу системе и свести коммуникационные затраты к логарифмическому размеру сети. Но давайте оставим это на другой раз.
Многие другие безконсенсусные криптовалюты похожи на Astro, например, AT2 (EPFL), FastPay (Facebook Novi) и Zef (Zefchain Labs), и на самом деле показывают очень хорошие практические результаты.
Криптовалюта без разрешения и без консенсуса с доказательством ставки
Система, которую мы описали ранее, интересна, но она разрешена и предполагает статическое членство в системе или доверенный механизм настройки. Обычно этого достаточно, чтобы предположить, что атаки Sybil невозможны. Однако что, если мы хотим реализовать платежную систему, в которой любой может присоединиться к системе без какой-либо проверки? Можем ли мы вообще решить проблему двойных трат без консенсуса в системе без права доступа? Да, можем.
В недавней работе [4], которую я написал в соавторстве, была предложена система Pastro, не требующая разрешения и асинхронная система передачи активов. Она основана на так называемых взвешенных кворумах. Точнее, система полагается на сертификаты, подписанные участниками, владеющими достаточным количеством активов, или долей, вместо традиционных кворумов и учета количества необходимых одобрений. Поверх этого мы создаем абстракцию, называемую Transaction Validation. Она похожа на BRB и гарантирует, что ни одна из двух конфликтующих транзакций никогда не будет подтверждена.
Но как мы можем определить кол в асинхронной системе? Поскольку система не использует механизм консенсуса, мы не можем договориться о том, сколько денег на самом деле есть у каждого участника/счета. Действительно, у нас нет общего порядка, и от него зависит распределение активов.
Поэтому, чтобы ввести понятие ставки, мы используем понятие конфигурации. Традиционно в распределенных вычислениях конфигурации определяют набор реплик, которые поддерживают систему в данный момент времени. Вместо этого в Pastro конфигурация используется для определения распределения доли системы между участниками. Формально, конфигурация - это просто набор транзакций, которые произошли в системе с самого начала. Отметим здесь два важных момента:
- Учитывая такой набор транзакций, можно легко определить активных участников системы и распределение доли между ними;
- Если все такие множества связаны между собой включением (т.е. одно содержится в другом), то они могут представлять динамически изменяющееся распределение доли в системе в течение времени.
Но как это помогает? Идея заключается в том, что участники не договариваются о "текущей конфигурации". Однако все конфигурации, которые они решают лично, могут быть упорядочены по содержанию.
Таким образом, у нас всегда есть "самая большая" конфигурация со строго большим количеством транзакций (по включению), чем в любой другой, которая обозначается как активная конфигурация и в соответствии с которой должно быть рассчитано распределение ставок. Если вы достаточно долго изучали математику и алгебру, вы могли заметить, что это очень близко к алгебраической абстракции решетки (lattice order).
В системе используется разновидность протокола Византийского решетчатого соглашения, который, параметризуясь (полу)решеткой (в нашем случае, набором транзакций), производит элементы решетки, которые сопоставимы (набор транзакций, связанных сдерживанием - именно то, что нам нужно). Эта абстракция собирает все представленные транзакции в набор, или конфигурацию, затем обновляет текущее распределение ставок с учетом созданных конфигураций. Что еще более важно, решетчатое соглашение - это мощный объект, который может быть реализован полностью асинхронно, в отличие от консенсуса.
Используя эти идеи, протокол Pastro может решить проблему двойных расходов в присутствии атак Sybil и так называемого динамического противника, который может выбирать, каких участников скомпрометировать во время исполнения, принимая во внимание их текущую ставку. Хотя существует вариация распространенного предположения: противник может скомпрометировать участников, которые в активной конфигурации владеют менее чем одной третью общей доли системы. Это делает Pastro первой в истории криптовалютой без разрешения и консенсуса.
Мы даже предлагаем способы включения в Pastro механизмов делегирования ставок, сборов и инфляции. Прежде всего, важно отметить, что перед полной реализацией системы необходимо решить некоторые практические инженерные задачи (оптимизация хранения и связи).
Почти свободная от консенсуса криптовалюта с общими счетами
Как разрешенные, так и неразрешенные асинхронные системы передачи активов, описанные в двух предыдущих разделах, могут быть обобщены. На высоком уровне такие системы поддерживают неупорядоченный набор совершенных (или принятых) транзакций. Чтобы быть добавленной в этот набор, новая транзакция должна пройти специальный объект Conflict Detector (в Astro это Byzantine Reliable Broadcast). Этот объект поддерживает инвариант неотрицательных балансов, накладывая понятие парных конфликтов на транзакции и предотвращая принятие нескольких конфликтующих транзакций. Интуитивно понятно, что две транзакции считаются конфликтующими, если они перемещают одни и те же активы. Я проиллюстрировал это ниже.
Однако все существующие реализации без консенсуса имеют определенное ограничение: они предполагают, что каждый счет контролируется одним пользователем, который никогда не проводит несколько транзакций параллельно. Это предположение исключает совместное использование аккаунта несколькими пользователями, например, членами семьи или безопасный доступ к нему с различных устройств. Если честный пользователь случайно выпустит несколько параллельных транзакций, существующие реализации могут заблокировать счет навсегда без возможности восстановления.
Помните, что, как мы узнали, консенсус требуется для криптовалют, где счета могут быть общими, поэтому невозможно реализовать такую систему в асинхронном режиме без консенсуса.
Разрешенная система под названием CryptoConcurrency [5], которую мы недавно предложили, решает эту проблему. Это гибридный протокол, сочетающий в себе преимущества как консенсусного, так и безконсенсусного подходов. Он позволяет разделять счета между несколькими пользователями и избегает использования консенсуса в большинстве случаев.
Неформально, если параллельно выпущенные транзакции по одному и тому же счету могут быть приняты без исчерпания баланса счета, то они обрабатываются одновременно и чисто асинхронно. В этом случае они проходят через так называемый Детектор восстанавливаемого перерасхода, усовершенствованную версию Детектора конфликтов, который пытается обнаружить овердрафт баланса, а не только парный конфликт. В то же время CryptoConcurrency динамически определяет случаи, когда необходимо использовать консенсус, т.е. когда общая стоимость параллельно выпущенных транзакций превышает баланс счета. В таких случаях протокол обращается к экземплярам консенсуса для каждого счета, чтобы выбрать максимально возможное подмножество не конфликтующих транзакций и принять их, отклонив остальные. Результат консенсуса затем используется для восстановления детектора восстанавливаемого перерасхода (поэтому он и называется восстанавливаемым), и система продолжает работать в прежнем режиме.
С точки зрения реализации, Recoverable Overspending Detector - это своего рода комбинация византийского решетчатого соглашения (которого мы уже касались в предыдущем разделе) и известного алгоритма консенсуса Paxos.
Алгоритм, предложенный нами в CryptoConcurrency, в некотором смысле оптимален: счет должен решать консенсус только тогда, когда средств недостаточно для покрытия всех обрабатываемых транзакций.
На мой взгляд, классной особенностью здесь является то, что каждый счет может подключить свою собственную реализацию консенсуса, поскольку когда на счете обнаруживается перерасход средств, то только владельцы этого счета должны прийти к соглашению о том, какие транзакции отменить, а какие принять. Таким образом, теоретически вы можете использовать либо что-то вроде AWS, либо смарт-контракт, развернутый на вашем любимом блокчейне.
Я считаю, что интересной задачей было бы объединение идей, предложенных CryptoConcurrency и Pastro: это была бы интересная теоретическая и инженерная проблема - построить распределенную платежную систему без разрешений, которая разрешала бы использование общего счета без использования глобального консенсуса, а только локальным экземплярам, когда это необходимо.
Вместо заключения
В этом посте мы рассмотрели, почему блокчейн не является единственно возможным способом создания криптовалюты, и сделали обзор некоторых предлагаемых систем для различных условий. Надеюсь, вам понравился материал и вы узнали что-то новое! Также не стесняйтесь оставлять свои вопросы в разделе комментариев. Если будет интерес, я могу опубликовать больше материалов о новых протоколах и концепциях, которые придумали исследователи в области распределенных вычислений.
Ссылки
[1] Биткойн: одноранговая система электронных денег. С. Накомото - pdf-версия
[2] Число консенсуса криптовалюты. R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovic, D-A. Seredinschi - arXiv link
[3] Онлайн-платежи с помощью простой трансляции сообщений. D. Collins, R. Guerraoui, J. Komatovic, M. Monti, A. Xygkis, M. Pavlovic, P. Kuznetsov, Y-A. Pignolet, D-A. Seredinschi, A. Tonkikh - arXiv link
[4] Безразрешительная и асинхронная передача активов. P. Kuznetsov, Y-A. Pignolet, P. Ponomarev, A. Tonkikh - ссылка arXiv
[5] CryptoConcurrency: (почти) бесконсенсусная передача активов с общими счетами. P. Kuznetsov, Y-A. Pignolet, P. Ponomarev, A. Tonkikh - ссылка arXiv
Перевод статьи Павла Пономарева