Деревья Меркла используются для создания доказательств пользовательских действий в легких клиентах. Легкие клиенты — основа взаимодействия между блокчейнами, где один блокчейн выступает в роли легкого клиента для другого.
Каждое действие пользователя можно рассматривать как выписанный кем-либо чек, который обрабатывается банком (блокчейном) и записывается в реестр, если он принят. Взаимодействие между блокчейнами заключается в создании доказательств того, что конкретный чек был принят, и сохранении порядка принятия относительно других чеков, выписанных тем же отправителем или получателем.
Чейн А может получать сообщения от Чейна Б, читая заголовки его блоков и обрабатывая доказательства действий. Каждое из доказательств действий имеет номер (или несколько номеров) последовательности, который используется Чейном А, чтобы убедиться, что их обработка была непрерывной.
Тогда как другие чейны создают дерево Меркла от состояния (балансов аккаунтов), EOS.IO создает дерево Меркла от последовательности действий. Легкий клиент может получить баланс любого аккаунта, обработав последовательность всех действий с этим аккаунтом, без необходимости в обработке действий для всех других аккаунтов.
Во многих случаях нет нужды знать баланс аккаунта, вместо этого всё, что требуется легкому клиенту – это подтвердить оплату. Это может быть сделано через доказательство единственного действия.
Блокчейны строятся поверх детерминистичных конечных автоматов, поэтому взаимодействие между блокчейнами максимально эффективно тогда, когда имеются гарантии полноты и последовательности. Протокол EOS.IO создает канал связи между чейнами, сходный с TCP. Таким образом можно обнаружить отсутствующие и внеочередные доказательства.
Несмотря на то, что можно создать доказательства отсутствия пропусков в действиях, невозможно доказать, что у вас имеются все действия на текущий момент. Для доказательства полноты на текущий момент требуется создать транзакцию, добиться её включения [в чейн/блок] и создать доказательство того, что самая последняя транзакция была подтверждена с правильным номером последовательности.
Целевая аудитория
Этот пост для тех, кто интересуется криптографической архитектурой межчейнового взаимодействия в EOS.IO. Используя эту информацию вы сможете разрабатывать и внедрять легкие кошельки, или провести интеграцию с собственным блокчейном. В начале этот текст был написан для нашей внутренней документации, но мы решили опубликовать его здесь для оценки сообществом и всеми любопытствующими.
Канонические деревья и доказательства
Все подсчеты, связанные с деревьями Меркла в EOS.IO, объединены несколькими условиями, которые позволяют убрать неоднозначности данных в доказательствах, не требуя дополнительного места. Возьмем два листовых узла с дайджестами Da и Db соответственно. Их совместный родительский узел в простом дереве Меркла будет дайджестом от конкатенации Da и Db (Da|Db). При этом, Da|Db – не то же самое, что Db|Da, кроме случаев, когда выбранный подсчет дайджеста обладает свойством коммутативности. Это означает, что доказательство в форме “пути” от листа к корню дерева Меркла (иногда называемое “журнальным доказательством” – “log proof”) должно указывать на то, относятся ли записи в этом “пути” к левой или правой конкатенации.
Для того, чтобы избавиться от этих дополнительных “путевых” данных в доказательстве, EOS.IO преобразует листовые дайджесты перед тем как конкатенировать их в новый дайджест. Это преобразование указывает на то, находится ли дайджест слева или справа в конкатенации. Таким образом, “путевое” доказательство включает в себя дайджесты до преобразования и дает возможность с легкостью делать заключение о правильной конкатенации.
Точнее, EOS.IO использует первый бит листового дайджеста для определения положения: 0 для “левых” и 1 для “правых” дайджестов соответственно. При чтении любого путевого доказательства (Dp) и использовании его с имеющимся дайджестом (Dn), если первый бит в Dp – 0, тогда результирующий дайджест – это хэш (Dp|Dn), иначе это хэш (Dn|Dp)
C_HASH(left,right)
LET canonical_left := CLEAR_FIRST_BIT(left),
LET canonical_right := SET_FIRST_BIT(right),
LET data := CONCATENATE(canonical_left,canonical_right),
HASH_FN(data);
(псевдокод для генерации хэша от левого и правого листов)
Также, если для построения дерева Меркла потребуется хэширование узла с неизвестным значением, например, в сбалансированном дереве с тремя узлами, результирующий дайджест – это конкатенация узла с самим собой.
Корень:
Dabcc
/ \
Dab Dcc <- Dc конкатенируется сам с собой
/ \ /
Da Db Dc
Меркл блока
Заголовок любого Блока N включает в себя корень сбалансированного дерева Меркла, в котором листьями являются идентификаторы всех предыдущих блоков 0..N-1: Корень Блоков. Это служит добавлением в содержимое блокчейна, начиная с генезиса и с каждым новым блоком.
Имея идентификатор любого блока в блокчейне и заголовки доверенного необратимого блока, возможно доказать, что этот блок включен в блокчейн. Такое доказательство проходит ceil(log2(N)) дайджестов на своем пути, где N – это число блоков в чейне. При использовании SHA256 в качестве метода получения дайджестов можно уместить в 864 байта доказательство существования любого блока в цепи, которая содержит 100 миллионов блоков.
Меркл действия
Для любого блока N заголовки включают Корень действия — корень почти сбалансированного дерева Меркла, где листьями выступают подтверждения для данных, созданных во время обработки действий. Он может быть использован для доказательства существования и порядка действий. Также он может быть использован для доказательства полноты записей действий, которые затрагивают какую-либо область.
Данные, фиксируемые для каждого Действия или Подтверждения действия, включают в себя:
receiver (получатель): имя аккаунта, чей контракт получил конкретное действие
scope (область): область, в которой определено это действие
name (имя): имя действия (например, “перевод”)
data (данные): полезные данные, доставляемые контракту бинарно закодированными
data_access (доступ к данным): массив порядковых номеров для областей, к которым осуществлялся доступ во время обработки этого действия
Это может быть использовано для доказательства полноты записей путем предоставления действий и доказательств для номеров последовательности любых двух действий.
Номера последовательности всегда возрастают при операции записи и никогда не возрастают при чтении. Всегда будет существовать только одно действие с записью для любой последовательности, области, получателя.
region_id (идентификатор региона): регион, в котором это действие было обработано.
cycle_index (индекс цикла): цикл, в котором это действие было обработано.
Это позволяет доказывать порядковые ограничения.
Шарды в цикле могут исполняться параллельно; действия в одном цикле, но в разных шардах, не имеют детерминистического упорядочивания.
(Пример Подтверждения Действия)
{
receiver:inite,
scope:eosio,
name:transfer,
data:{
"from":"inite",
"to":"inita",
"amount":10000,
"memo":"memo"
},
data_access:[
{"type":"write","scope":"inite","sequence":1},
{"type":"write","scope":"inita","sequence":0}
],
region:0,
cycle:0
}
Для каждого шарда (единицы распараллеливаемого исполнения в цикле) создается сбалансированное дерево Меркла, состоящее из этих подтверждений действий для создания временного общего корня Меркла. Это сделано для быстроты параллельного вычисления. Заголовок блока содержит корень сбалансированного дерева Меркла, у которого листьями являются корни этих конкретных общих деревьев Меркла. Это означает, что результирующее дерево Меркла, представленное Корнем Действия, не может гарантированно быть полностью сбалансированным, но должно быть максимально к этому близким в большинстве случаев.
Для любого действия где-либо в блокчейне возможно кратко доказать исполнение этого действия, вначале доказав, что оно было зафиксировано в Корне Действия блока, а потом, что данный блок был зафиксирован в Корне Блока, находящегося в заголовке доверяемого необратимого блока. Эти два доказательства называются “Путь Действия” и “Путь Блока” соответственно.
Путь Действия содержит все данные (одноуровневые дайджесты из дерева Меркла), необходимые для воссоздания корня Дерева Меркла относительно единственного Подтверждения Действия. Корень этого дерева Меркла должен в точности совпадать с Корнем Действия, добавленным в заголовок блока, зафиксировавшего это действие.
Путь Блока содержит все необходимые данные для пересчета корня дерева Меркла относительно единственного Идентификатора Блока. Корень этого дерева Меркла должен в точности совпадать с Корнем Блока, добавленным в заголовок доверенного необратимого блока.
Например,
Если взять приведенное выше действие, зафиксированное в блоке со следующим идентификатором:
00000033e4f902358b1d43918d197652fc01baaf0e6ca8ee38cda2e8780b7dbd
Корень Действия которого был:
067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57
где Корень Блока доверенного необратимого блока:
1ae092ea41e70982b56b9673f990346876ba535595df16dc1094740c144aaae6
тогда доказательство будет выглядеть так:
Путь Действия:
9b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91
9cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
C65abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
4cf39dfbe8a0fdc2540c8f0b68037484051a20d6ca00b891bbfc66d826503677
A8773db30f3733063352d1abec5fea265115bdf646a69d21545746a4f7cff3f3
Путь Блока:
8000003418a608c3704f80cdfed2793a055cc13993eea67ccdd018d9df027101
2351ee036c6a4052e18c9ded8d35c1b1dfb330531e163039847797d38e9babd2
De1996e5c23c73fa212abaaf423b9038e289fc7a19be5a7f395c7727a5266168
Ccd7c6e10b398fd27cfc4d29f339806593d614c736ae1af8a47908e44d2fe924
1e95b55e98d329bda8f2c79d1f969650716207a03f13f540931ab5a6a80f4d0b
369d86219b35e493a4fda3649c9f3a546809add40462c4b5ddca185f75cfe05c
9067c63043027831fbc7ba046d5bd7d9a0c23e1baa6fe0ac16a911ff7c3acd74
Для проверки этого доказательства вначале сериализуем проверяемое Подтверждение Действия в стандартный бинарный формат EOS.IO. В результате получится следующее бинарное представление (в шестнадцатиричном формате):
000000000095dd740000000000ea3055000000572d3ccdcd1d000000000095dd74000000000093dd741027000000000000046d656d6f0000000000000000020100000000000000000000000095dd7401000000000000000100000000000000000000000093dd740000000000000000
На данный момент EOS.IO использует SHA256 в качестве метода получения дайджестов (HASH_FN), так что листовым дайджестом будет SHA256 вышеприведенного бинарного представления:
1b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91
Используя этот листовой дайджест, применим Путь Блока, посмотрев в раздел про каноничные пути и подписи, чтобы определить, требует ли запись в пути левую или правую конкатенацию. После применения полного пути корневой дайджест должен в точности совпадать с Корнем Действия в блоке, который зафиксировал это действие:
C_HASH(
1b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91,
9b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91)
=> 1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
C_HASH(
1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067,
9cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067)
=> 465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
C_HASH(
465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167,
C65abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167)
=> dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab
C_HASH(
4cf39dfbe8a0fdc2540c8f0b68037484051a20d6ca00b891bbfc66d826503677,
dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab)
=> ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996
C_HASH(
ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996,
a8773db30f3733063352d1abec5fea265115bdf646a69d21545746a4f7cff3f3)
=> 067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57
После того, как мы проверили, что блок имеет подтверждение фиксации действия, как описано выше, мы также должны проверить, что фиксирующий блок имеется в блокчейне, используя Путь Блока и идентификатор фиксирующего блока. После применения полного пути результирующий корневой дайджест должен в точности совпасть с Корнем Блока в заголовке доверенного необратимого блока:
C_HASH(
00000033e4f902358b1d43918d197652fc01baaf0e6ca8ee38cda2e8780b7dbd,
8000003418a608c3704f80cdfed2793a055cc13993eea67ccdd018d9df027101)
=> da16dd856cbb888545c0ed248f2acbbed57037cf407e258849d4600c8f074739
C_HASH(
2351ee036c6a4052e18c9ded8d35c1b1dfb330531e163039847797d38e9babd2,
da16dd856cbb888545c0ed248f2acbbed57037cf407e258849d4600c8f074739)
=> da1a4326c7d83cc86f1154e76000ae94a7579833e75d9378972c6f034e044c11
C_HASH(
da1a4326c7d83cc86f1154e76000ae94a7579833e75d9378972c6f034e044c11,
de1996e5c23c73fa212abaaf423b9038e289fc7a19be5a7f395c7727a5266168)
=> d2d0abf4e6d8b771f8de27413ce7c9ca9e443c89fd10c4d42cb37bcc47cb3598
C_HASH(
d2d0abf4e6d8b771f8de27413ce7c9ca9e443c89fd10c4d42cb37bcc47cb3598,
ccd7c6e10b398fd27cfc4d29f339806593d614c736ae1af8a47908e44d2fe924)
=> c36045ffee9c98eb419077aa356d65fb6a928914c40ec88aadcf634781e56c23
C_HASH(
1e95b55e98d329bda8f2c79d1f969650716207a03f13f540931ab5a6a80f4d0b,
c36045ffee9c98eb419077aa356d65fb6a928914c40ec88aadcf634781e56c23)
=> 4432bce7431f676ed704f2d3367cb33407898b70f51fea2dfa014b97ac37a97b
C_HASH(
369d86219b35e493a4fda3649c9f3a546809add40462c4b5ddca185f75cfe05c,
4432bce7431f676ed704f2d3367cb33407898b70f51fea2dfa014b97ac37a97b)
=> 94f5ba720b886515ada9c0f73ab393dffc43beaeac7be6f7f86bce808834dfde
C_HASH(
94f5ba720b886515ada9c0f73ab393dffc43beaeac7be6f7f86bce808834dfde,
9067c63043027831fbc7ba046d5bd7d9a0c23e1baa6fe0ac16a911ff7c3acd74)
=> 1ae092ea41e70982b56b9673f990346876ba535595df16dc1094740c144aaae6
Благодарность
Я бы хотел поблагодарить Барта В. за его помощь в написании этого поста и внедрении этого протокола в ветку eos-noon нашего github репозитория.
Disclaimer
block.one является компанией-разработчиком ПО и выпускает программное обеспечение EOS.IO в качестве бесплатного программного обеспечения с открытым исходным кодом. Это программное обеспечение может позволить тем, кто его устанавливает, запустить блокчейн или децентрализованное приложение с функциями, описанными выше. block.one не будет запускать публичный блокчейн на основе программного обеспечения EOS.IO. За реализацию функций и/или предоставление услуг, описанных выше, по своему усмотрению, будут нести ответственность исключительно третьи стороны и сообщество, а также те, кто захочет стать производителями блоков. block.one не гарантирует, что кто-либо будет реализовывать эти функции или предоставлять такие услуги, или что программное обеспечение EOS.IO будет принято и применено каким-либо определенным образом.
Все заявления в этом документе, за исключением заявлений об исторических фактах, включая любые заявления о бизнес-стратегии block.one, ее планах, перспективах, разработках и целях, являются лишь прогнозными заявлениями. Эти утверждения носят сугубо предсказательный характер и отражают текущие убеждения и ожидания block.one относительно будущих событий, которые основаны на предположениях и подвержены рискам, неопределенностям и изменениям в любое время. Мы работаем в быстро меняющейся среде. Время от времени появляются новые риски. Учитывая эти риски и неопределенности, мы предостерегаем вас от всецелого полагания на эти прогнозные заявления. Фактические результаты, производительность или события могут существенно отличаться от тех, которые содержатся в прогнозных заявлениях. Некоторые из факторов, которые могут привести к существенным отличиям фактических результатов, производительности или событий от прогнозных заявлений, содержащихся в настоящем документе, включают в себя, без ограничений: волатильность рынка; постоянную доступность капитала, финансирования и персонала; принятие продукта; коммерческий успех любых новых продуктов или технологий; конкуренцию; государственное регулирование и законы; а также общие экономические, рыночные или деловые условия. Любое прогнозное заявление, сделанное block.one, актуально только в дату его публикации, и block.one не несет никакой ответственности и прямо отказывается от каких-либо обязательств по обновлению или изменению своих прогнозных заявлений, будь то в результате появления новой информации, последующих событий или иных факторов.
Оригинал поста: ЗДЕСЬ
