
Гетерогенный Paxos использует высокую степень пересечения наборов валидаторов разных блокчейнов для создания гетерогенного консенсусного протокола для атомарных многоцепочных транзакций и транзакций. расширяет возможности IBC, позволяя осуществлять произвольную связь между цепочками в рамках атомарной транзакции.
При некоторых условиях Heterogeneous Paxos допускает атомарные междоменные транзакции, при этом учащиеся не обязательно разделяют одни и те же предположения об ошибках. Опираясь на гетерогенный Paxos, мы надеемся использовать высокую степень пересечения наборов валидаторов разных блокчейнов для создания гетерогенного консенсусного протокола для атомарных многоцепочных транзакций. Это расширит возможности IBC, позволяя осуществлять произвольную связь между цепочками в рамках атомарной транзакции.
Цель
Мы хотим включить атомарно фиксацию пакетов транзакций в нескольких цепочках. Другой способ рассматривать каждый пакет — как единую многоцепочечную транзакцию, состоящую из субтранзакций в каждой цепочке и связи между ними.
Пример отеля и поезда
Рассмотрим классический пример: пользователь хочет купить билет на поезд тогда и только тогда, когда он также может купить номер в отеле в пункте назначения. Они хотят выполнить эти две транзакции атомарно. Если они купят один, а другой станет недоступен, пользователю будет грустно.
Представьте, что система бронирования отелей и система бронирования билетов на поезд управляются на отдельных блокчейнах (красная цепочка и синяя цепочка). Каждая цепочка может иметь несколько предлагаемых следующих блоков, каждый из которых содержит несколько транзакций. В некоторых из этих блоков пользователю удается совершить покупку, а в некоторых — нет:


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


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

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

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

Гетерогенный Paxos — это один из протоколов консенсуса, который может позволить нам создавать такие многоцепочные атомарные транзакции.
Зачем вмешиваться в консенсус для многоцепочечных атомарных транзакций?
Хотя IBC позволяет проверенную передачу информации между цепочками, он может взаимодействовать только между транзакциями а><а я=4>. В частности, IBC не может поддерживать транзакцию, в которой смарт-контракт в цепочке A отправляет сообщение контракту в цепочке B, а затем цепочка B отвечает обратно. в цепочку А, и все это в рамках одной транзакции.
Почему бы не использовать многофазные фиксации?
Конечно, мы могли бы моделировать атомарные транзакции, создав протокол многофазной фиксации с различными цепочками' конечные автоматы в качестве участников и IBC в качестве сети. По сути, это подход, использованный в Атомарных межцепочных свопах. У этого плана есть три недостатка: скорость, живучесть и проблема теории игр.
Скорость
Многофазная фиксация требует как минимум двух раундов консенсуса для каждой цепочки. Мы предлагаем совершить все в рамках одного объединенного раунда.
Последняя фаза фиксации протокола многофазной фиксации может продолжиться только после того, как все цепочки завершили предыдущие фазы. Это означает, что каждая цепочка (или, по крайней мере, любые активы, участвующие в многоцепочечной атомарной транзакции) становится максимально доступной, как Задействована наименьшая доступная цепочка: если какая-либо цепочка выйдет из строя, ни одна из них не сможет продолжить работу. Мы надеемся добиться более детального компромисса между соглашением и жизнеспособностью, при котором транзакции и цепочки смогут точно указывать условия, при которых они требуют соглашения и прекращения действия.
Теоретико-игровая задача
Некоторая цепочка должна выполнить окончательный переход состояния, прежде чем начнется фаза фиксации. Это дает этой цепочке, в некотором смысле, бесплатную опцию: она может выбирать, когда (или будет ли) завершаться атомарная транзакция между цепочками. Это может быть полезно в случаях перекрестной торговли и колебаний цен. Атомарные межцепочные свопы пытаются решить эту проблему с помощью хеш-блокированных активов, чтобы лишить цепочку стимулов к постоянной задержке транзакции. К сожалению, это нельзя распространить на все возможные межцепочные транзакции (с произвольными смарт-контрактами). Конечно, это «последнее предварительное подтверждение»; Проблема существует и в алгоритме консенсуса каждой цепочки, поэтому мы надеемся расширить существующие методы обеспечения справедливости консенсуса, включив в них межцепочные атомарные коммиты.
Любой консенсус с немедленной окончательностью можно описать с точки зрения кворума. Кворум — это любой набор участников (машин, также называемых узлами, валидаторами, акцепторами или избирателями), которые могут общаться между собой и раз и навсегда решать, какой блок будет следующим в цепочке, не общаясь ни с кем другим. Часто любой набор, содержащий более двух третей участников (или участников, владеющих более чем двумя третями доли), является кворумом. Важно отметить, что каждая пара кворумов в рамках одного консенсуса должна иметь честного участника в их пересечении, чтобы гарантировать, что цепочка не разветвится. В противном случае, если все участники пересечения кворумов A и B нечестны, они могут бисимулировать и вести себя одним образом для целей кворума A, и еще один способ для целей кворума B, поэтому ничто не может гарантировать, что кворумы A и B примут решение по одному и тому же блоку. Если каждый из двух кворумов принимает решение о разных блоках, цепочка разветвляется.
Пример
Рассмотрим красную и синюю цепочки. Красная цепочка имеет 3 кворума, обозначенных ниже красными треугольниками. Каждый красный кворум пересекает красный кворум друг друга, и пользователи красной цепочки признают, что если в одном из этих пересечений нет честных участников, красная цепочка может разветвиться.
Аналогично, синяя цепочка имеет 3 кворума, изображенных ниже в виде синих прямоугольников. Каждый синий кворум пересекает синий кворум друг друга, и пользователи синей цепочки признают, что если в одном из этих пересечений нет честных участников, синяя цепочка может разделиться.
Обратите внимание, что ни в одной цепочке нет единой точки отказа: ни один участник не входит во все кворумы какой-либо цепочки.


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

Лучший сценарий
Если пользователь считает, что в каждом из этих красно-синих пересечений есть честный участник, он должен иметь возможность совершать атомарные многоцепочные пакеты транзакций с красными и синими цепочками. Кворум каждой цепочки остается прежним: красного кворума достаточно для принятия решения красной цепочкой, а синего кворума достаточно для принятия решения синей цепочкой. Однако нам необходимо адаптировать алгоритмы консенсуса как красного, так и синего, чтобы честный участник обоих мог гарантировать, что у них нет разногласий по поводу того, следует ли фиксировать общий пакет транзакций. Именно это и делает Heterogeneous Paxos.
Когда предположения неверны
Важно отметить, что каждая такая атомарная многоцепочечная партия транзакций сопровождается предположениями об условиях, при которых она будет атомарной: в данном случае каждое красно-синее пересечение имеет честного участника. Если такой пакет имеет неверное предположение, возможно, что одна цепочка зафиксирует пакет с несколькими цепочками, а другая — нет. В приведенном выше примере с поездом и гостиничным номером пользователь может получить билет на поезд, но не номер в отеле.
К счастью, гетерогенный Paxos не может привести к зависанию какой-либо цепочки из-за того, что что-то пошло не так в другой цепочке: каждого кворума все еще достаточно, чтобы пусть его цепочка решит. Это отличается, например, от Stellar Consensus Protocol, в котором пользователи заранее не знают, каковы будут их кворумы, а их кворумы зависят от других участники' доверять выбору.
Это что-то вроде моста
В некотором смысле наш гетерогенный консенсус может создать что-то вроде доверенного моста: он позволяет выполнять операции между несколькими цепочками при определенных предположениях о доверии. Другие конструкции мостов, как правило, основаны на многофазной фиксации, поэтому наша будет быстрее и не потребует блокировки ресурсов.
Проблемы
Решение о том, какой гетерогенный консенсус реализовать
Наивно, одна цепочка может попытаться одновременно зафиксировать пакеты из нескольких цепочек с несколькими другими цепочками (коллекциями) и при этом зайти в тупик.
Пример
Предположим, у нас есть 3 цепочки: красная, синяя и зеленая. Каждая цепочка имеет 3 кворума.
- Красная цепочка имеет 3 кворума, нарисованных в виде красных треугольников. Каждая пара кворумов красной цепочки пересекается, и пользователи красной цепочки могут быть уверены, что цепочка не разветвится, пока в каждом из этих пересечений есть честный участник.
- Синяя цепочка имеет 3 кворума, обозначенных синими треугольниками. Каждая пара кворумов синей цепочки пересекается, и пользователи синей цепочки могут быть уверены, что цепочка не разветвится, пока в каждом из этих пересечений есть честный участник.
- Зеленая цепочка имеет 3 кворума, нарисованных зелеными прямоугольниками. Каждая пара кворумов зеленой цепочки пересекается, и пользователи зеленой цепочки могут быть уверены, что цепочка не разветвится, пока в каждом из этих пересечений есть честный участник.

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

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

Напомним, что зеленого кворума достаточно, чтобы зеленая цепочка приняла решение о блоке без связи с кем-либо еще, а красного кворма достаточно заставить красную цепочку принять решение не общаясь ни с кем. Это означает, что возможно (даже если все участники честны) красный кворум примет решение по сине-красному комбинированному блоку, а зеленый кворум примет решение по сине-зеленому комбинированному блоку: кворумы не ;t пересекаются, поэтому они могут просто никогда не услышать друг друга.


В этой ситуации синие кворумы не могут решить ничего, кроме сине-зеленого блока, поскольку каждый синий кворум имеет честный узел в пересечении с зеленым кворумом, который уже принял решение по сине-зеленому блоку. Аналогично, синие кворумы не могут принять решение ни по чему, кроме красно-синего блока, поскольку каждый синий кворум имеет честный узел в пересечении с красным кворумом, который уже принял решение по красно-синему блоку. Поскольку красно-синий блок и сине-зеленый блок не одинаковы (и в данном случае мы предполагаем, что они конфликтуют), синяя цепочка застряла: она не может ни на что решиться.
Обратите внимание, что это не было бы проблемой, если бы каждый красный кворум имел пересечение (с участием честного участника) с каждым зеленым кворумом: красный и зеленый могли бы избежать принятия противоречивых решений.
Фундаментальные ограничения
Как и в нашем примере выше, то, что цепь A может иметь гетерогенный консенсус с цепью B, а цепь B может иметь гетерогенный консенсус с цепью C, не означает, что цепь A может иметь гетерогенный консенсус с цепью C. Ключевым моментом является избежание возможности возникновения конкурирующих блоков в несовместимых консенсусах. В некотором смысле, каждый раунд консенсуса должен знать заранее, какой гетерогенный консенсус он собирается запустить. По наивности это очень обескураживает: кажется, мы уже что-то решили, прежде чем начинаем принимать решение. К счастью, у нас есть несколько многообещающих способов решения этой загадки.
Примечание
Дэвид Мазирес предположил, что если вы заранее не знаете состав участников, для достижения консенсуса требуется как минимум 4 раунда общения. Гетерогенный Paxos, который предполагает, что мы заранее знаем все используемые кворумы, требует всего 3 раунда общения. Это говорит о том, что в какой-то момент нам может понадобиться как минимум еще один раунд, чтобы «решить, какой гетерогенный консенсус использовать». Напротив, Протокол Stellar Consensus, который работает по несколько иной модели, требует 4 раундов. В Stellar у участников есть мнение о том, кого они хотят видеть в кворумах, а кворумы зависят от других участников' мнения тоже. В отличие от гетерогенного Paxos, невозможно заранее узнать, насколько велик ваш кворум (и, следовательно, насколько велика вероятность того, что вы сможете принять решение или даже точно определить, с кем вы гарантированно согласны).
Возможные направления решения
Запланируйте согласование заранее
В принципе, каждая цепочка может заранее решить для каждого блока, какой гетерогенный консенсус они будут использовать для этого блока, а гетерогенный консенсус выбирает общий блок только в том случае, если все цепочки пришли к согласию с этим гетерогенным консенсусом. Наивно это звучит как многофазная фиксация: каждый блок требует одного (предварительного) раунда консенсуса, а затем одного раунда гетерогенного консенсуса. Однако есть 2 ключевых отличия:
- Набор транзакций не нужно указывать до тех пор, пока не начнется гетерогенный консенсус.
- Цепочки могут планировать произвольное количество гетерогенных раундов консенсуса сколь угодно далеко вперед: амортизируя стоимость этого «первого раунда консенсуса».
Цепочка для каждого возможного консенсуса
Учитывая кворумы для любого набора блокчейнов, мы могли бы создать новый блокчейн для каждого возможного гетерогенного консенсуса между их различными кворумами. В приведенном выше примере это означало бы, что будет "красно-синий" цвет. цепочка и «сине-зеленый»; цепочка в дополнение к красной, синей и зеленой цепочкам:
- красные транзакции в красно-синей цепочке будут приниматься красными кворумами, а синие транзакции в красно-синей цепочке будут приниматься синими кворумами, поэтому, если существует пересечение красно-синего кворума без честный участник, цепочка может разветвиться, но любой, кто следует только синим транзакциям или только красным транзакциям, не увидит разветвление.
- зеленые транзакции в сине-зеленой цепочке будут приниматься зелеными кворумами, а синие транзакции в сине-зеленой цепочке будут приниматься синими кворумами, поэтому, если существует пересечение сине-зеленого кворума без честный участник, цепочка может разветвиться, но любой, кто следует только синим транзакциям или только зеленым транзакциям, не увидит разветвление.
Между синей цепочкой и красно-синей цепочкой, а также между синей цепочкой и сине-зеленой цепочкой мы можем обеспечить прямую, надежную связь (возможно, на основе IBC), которая гарантированно прибудет в пределах фиксированного количества блоков. Это просто потому, что решения по синим транзакциям во всех цепочках принимаются одними и теми же кворумами. В принципе, смарт-контракты могут «перемещать состояние». скажем, от чисто синей цепочки к сине-зеленой цепочке, когда они хотят вести бизнес с зелеными смарт-контрактами, а затем обратно к синей цепочке, когда они закончат.
Один из способов представить себе программирование в такой «цепочке для каждого возможного консенсуса» мир должен был бы думать о цепочках как об эксклюзивных блокировках состояния. В частности, только одна цепочка может одновременно удерживать блокировку некоторого состояния, и единственными возможными цепочками являются те, для которых существует гетерогенный консенсус. Каждой части состояния (каждому смарт-контракту) нужен код, специфичный для приложения, чтобы решить, какая цепочка в какое время удерживает блокировку. Например, пользователь может разрешить сети отелей, поездов и банков временно заблокировать его банковский счет, пока он пытается автоматически забронировать номер в отеле и билет на поезд.
Снижение живучести или повышение безопасности
До сих пор мы рассматривали возможность использования только тех кворумов, которым уже доверяют сети. Однако пользователь может согласиться с тем, что какое-то состояние будет немного менее активным, если он сможет включить больше возможных атомарных транзакций или повысить безопасность этой атомарности. Например, мы можем представить пользователя, который хочет атомарно зафиксировать некоторые транзакции в красной, зеленой и синей цепочках выше. Используя только цепи' в местных кворумах это невозможно: красная цепочка не желает ждать, пока кто-либо из участников зеленой цепочки примет решение, и наоборот. Однако предположим, что пользователь владеет всем состоянием, участвующим в этих транзакциях, и готов использовать это состояние только тогда, когда все три цепочки работают.
Мы можем представить себе создание новой цепочки, где каждый кворум включает в себя кворум из красной, кворум из зеленой и кворум из синей цепочки. Эта цепочка более безопасна, чем любая из красных, зеленых или синих цепочек: она может разветвляться только при условии, что все красного, синего и вилка зеленых цепей. Эта цепочка также менее активна, чем любая из красных, зеленых или синих цепочек: она может фиксировать новые блоки только при условии, что все красного, синего , а зеленые цепочки фиксируют новые блоки. Однако, безусловно, было бы безопасно переместить состояние из любой из красных, зеленых или синих цепочек в комбинированную цепочку и обратно: данные не будут подвержены риску повреждения, а, в лучшем случае, застрянут. Если у пользователя есть на это право, он может это сделать.
Это прекрасно вписывается в нашу «цепочку для каждого возможного консенсуса». модель. В нашем «как замки» модели, мы можем представить, что некоторые держатели замков подвергаются штрафам за живучесть, но могут быть более безопасными. Приложениям придется самим определять, когда они хотят, какие цепочки блокировать их данные.
Изменение кворума
До сих пор мы рассматривали каждую цепочку так, как будто она имеет статический набор кворумов. Однако, это не так. Например, в цепочках с доказательством доли кворумы меняются каждый раз, когда доля переходит из рук в руки. Если мы поддерживаем набор «мостов»; цепочки, которые используют гетерогенные консенсусы для каждого возможного гетерогенного консенсуса, то всем этим цепочкам необходимо синхронно обновлять свои кворумы, чтобы сохранить одинаковые гарантии доверия. Это означает, что любую транзакцию, которая может изменить кворум цепочки, чрезвычайно сложно совершить.
Модель программирования
Чтобы воспользоваться преимуществами любых атомарных коммитов с несколькими цепочками, нам необходимо предоставить эту функциональность транзакциям внутри цепочек. Какие API или функции языка мы должны предоставить для максимальной гибкости, сохраняя при этом всю мощь гетерогенных многоцепочных коммитов? Как мы можем сделать это максимально простым в использовании, не заставляя разработчиков стрелять себе в ногу?
Атомарные многоцепочечные пакеты транзакций
Для самих наших транзакций мы хотим сохранить гибкость конечного автомата каждой исходной цепочки. Чтобы сделать как можно меньше предположений об их конечных автоматах, можно подумать о взаимодействии между их транзакциями так же, как взаимодействуют различные компьютеры: как о сетевой связи. Мы могли бы написать API (возможно, аналогичный IBC), в котором каждая транзакция может отправлять и получать байты в другие транзакции в пакете и обратно. Такое общение будет синхронным: транзакции фактически выполняются вместе с одними и теми же участниками, возможно, даже в одном потоке выполнения. Есть две ключевые особенности, которые отличают «атомную сеть» от сети. коммуникация от традиционной связи между блокчейнами.
- Атомарная сетевая связь допускает циклы связи в рамках одних и тех же транзакций: транзакция A в синей цепочке может отправить сообщение транзакции B в красной цепочке, а затем B может отправить сообщение обратно в A, и все это может происходить атомарно. . IBC этого не допускает: вся связь должна осуществляться между транзакциями.
- Атомная сетевая связь опирается на честные узлы в пересечениях кворума, чтобы доказать, какие сообщения отправляются. В общем, мы не предполагаем, что все участники могут вычислять все транзакции для всех конечных автоматов: только те конечные автоматы, для которых они находятся в кворуме. В нашем красно-синем примере синий кворум не может дождаться, чтобы прослушать весь красный кворум, чтобы узнать, какие сообщения красные транзакции отправили синим транзакциям. Единственные красные участники, от которых они могут гарантировать выслушивание, — это те, кто находится на пересечении с решающим синим кворумом. Нет гарантии, что большинство таких участников честны, только один из них есть. Этот честный участник должен быть в состоянии доказать какие сообщения красной транзакции отправлены синим транзакциям в пакете, чтобы участники, вычисляющие синие транзакции, могли правильно вычислить .
Одна цепочка для каждой возможной модели консенсуса
Любой может в любое время начать новую цепочку с использованием гетерогенного консенсуса с любым кворумом. Гетерогенные консенсусные цепочки могут иметь разные кворумы для каждой транзакции (при условии, что все они пересекаются, и мы признаем, что могут быть нарушения атомарности для транзакций, в пересечениях кворума которых отсутствуют честные участники). Мы должны иметь возможность устанавливать доверительную связь (возможно, с помощью IBC) между транзакциями в разных цепочках с одинаковыми кворумами. Это позволит приложениям «перемещать данные»; в общие цепочки, где возможны атомарные фиксации, а затем обратно. Что нам нужно, так это специальный интерфейс, показывающий, когда такие перемещения безопасны, когда сохраняется атомарность в пакетах, и способ легко перемещать состояние из одной цепочки в другую.
Это еще больше усложняется транзакциями, которые могут захотеть изменить гарантии безопасности или жизнеспособности (см. выше), которым необходимо будет специально подтвердить, что они переходят на менее активную или даже менее безопасную цепочку. В некотором смысле это не так уж сильно отличается от одобрения в системах управления информационными потоками.
Заключение
Пакеты транзакций с несколькими цепочками фундаментально полезны: они расширяют одно из ключевых преимуществ блокчейнов (атомарные транзакции) на многоцепочную среду, освобождая приложения от ограничений одной цепочки для глобального упорядочения. У нас есть основные инструменты для достижения этой цели, но остаются некоторые проблемы. Мы должны выяснить, как мы собираемся решать, какой консенсус использовать в какое время, и предоставить соответствующую модель программирования. Если мы сделаем это правильно, будущее для кроссчейн-приложений будет намного светлее.
Написано Исааком Шеффом, руководителем Typhon, исследователем распределенных систем и разработчиком протоколов в Heliax, команде по построению команды Анома.
Если вы заинтересованы в новейших исследованиях распределенных систем и создании протоколов для их развертывания, ознакомьтесь открытыми вакансиями в Heliax .