Коммуникация внутри блокчейна через доказательства Меркла с EOS.IO
Оригинал: https://steemit.com/eos/@dan/inter-blockchain-communication-via-merkle-proofs-with-eos-io
Деревья Меркла используются для обеспечения доказательств пользовательских действий легким клиентам. Легкие клиенты представляют основу коммуникации внутри блокчейна, где один блокчейн существует в роли легкого клиента для другого блокчейна.
Каждое пользовательское действие может рассматриваться как выписка чека, который обрабатывается банком (в данном случае, блокчейном), и регистрируется если он принят. Коммуникация внутри блокчейна заключается в генерации доказательств того, что определенный чек был принят, и процесс его принятия относительно других чеков, выписанных тем же отправителем или получателем.
Цепочка A может получать сообщения от Цепочки B, следуя заголовкам блоков Цепочки B и доказательствам обработки действий. Каждое доказательство действия имеет один или несколько порядковых номеров, которые использует Цепочка A, чтобы проверить, что в обработке нет пробелов.
Когда другие цепочки генерируют дерево Меркла на основе статуса (баланс на аккаунте), EOS.IO генерирует дерево Меркла на основе последовательных действий. Легкий клиент может вывести баланс на определенном аккаунте, обработав все последовательные действия на этом аккаунте, не обрабатывая при этом никаких действий на других аккаунтах.
Во многих случаях нет необходимости знать баланс аккаунта, все, что должен сделать легкий клиент, это верифицировать платеж. Это можно сделать через доказательство одного действия.
Блокчейны строятся над детерминистическими государственными машинами; поэтому коммуникация внутри блокчейна наиболее эффективна, когда можно предоставить гарантии завершенности и порядка. Протокол EOS.IO создает TCP как коммуникационный канал между цепями. Это означает, что отсутствующие или неработающие доказательства могут быть обнаружены.
Хоть вы и можете создавать доказательства гарантирующие, что никакие действия не будут пропущены, невозможно доказать, что у вас есть все действия вплоть до настоящего момента. Чтобы доказать завершенность до настоящего момента, нужно сгенерировать транзакцию, включить ее, а затем создать доказательство того, что последняя транзакция была подтверждена соответствующим порядковым номером.
Целевая аудитория
Этот пост предназначен для тех, кто интересуется криптографическим дизайном коммуникации внутри блокчейна EOS.IO. С помощью этой информации вы можете создавать и строить кошельки легкого клиента или интегрироваться со своим блокчейном. Этот текст был первоначально написан для внутренней документации, но мы выкладываем его здесь для того, чтобы сообщество и все кому интересно могли изучить информацию.
Канонические деревья и доказательства
Все вычисления Меркла в EOS.IO обьеденяет несколько соглашений, которые устраняют неоднозначность записей в доказательстве, не требуя дополнительного пространства. Учитываем два листа с соответствующими дайджестами Da и Db. Их общий родительский узел в базовом дереве Меркла был бы дайджестом конкатенации Da и Db (Da | Db). Однако, если только выбранный дайджест расчет не является коммутативным, Da | Db не совпадает с Db | Da. Это означает, что доказательство в виде «пути» от листа к корню дерева Меркла (иногда называемого «лог доказательством») должно указывать какую конкатенацию представляют записи в «пути», левую или правую.
Чтобы избежать этой лишней информации на «пути» в доказательстве, 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);
(pseudocode for generating a hash form a left and right leaf)
Кроме того, если для построения дерева Меркла необходимо хэширование узла с неизвестным значением, например, в сбалансированном дереве из 3 узлов, итоговый дайджест является результатом сцепления дайджеста с самим собой.
Корень:
Dabcc
/ \
Dab Dcc <- Dc concatenates with itself
/ \ /
Da Db Dc
Блок Меркла
Заголовок любого блока N включает в себя корень сбалансированного дерева Меркла, где листы являются блок идентификаторами для всех предыдущих блоков 0..N-1: Block Root. Это служит обязательством содержимому блокчейна, от происхождения и блок за блоком.
Рассматриваем любой блок идентификатор для блока в блокчейне, а заголовки - надежный необратимый блок. Можно доказать, что блок включен в блокчейн. Это доказательство берет ceil (log2 (N)) дайджесты для своего пути, где N - число блоков в цепочке. Учитывая метод дайджеста SHA256, вы можете доказать существование любого блока в цепочке, который содержит 100 миллионов блоков в 864 байтах.
Действие Меркла
Заголовки любого блока N включают в себя корень сбалансированного дерева Меркла, где листья являются обязательствами данным, сгенерированным при обработке действий: Action Root. Это можно использовать для доказательства существования и упорядочения действий. Кроме того, его можно использовать для доказательства завершенности транскриптов действий, которые влияют на данный объем.
Данные по обязательствам для каждого действия, или Action Commitment:
receiver: название аккаунта, контракт которого получил данное действие
scope: область действия, в которой это действие определено
name: имя действия (например: «передача»)
data: полезная нагрузка кодирования данных двоичным кодом, переданная на контракт
data_access: ряд порядковых номеров для областей, доступных при обработке этого действия
Это можно использовать для доказательства полных транскриптов путем предоставления действий и доказательств для порядковых номеров между двумя заданными действиями.
Последовательные номера всегда растут на операции записи и никогда не операции прочтения. Всегда будет только одно действие с записью для заданного (последовательность, область действия, получатель)
region_id: регион, в котором было обработано действие
cycle_index: цикл, в котором было обработано действие
Это можно использовать для доказательства порядковых ограничений.
Осколки внутри цикла могут выполняться параллельно; не может быть детерминированного порядка между действиями в одном и том же цикле, но разных осколках.
(Example Action Commitment)
{
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
}
Для каждого осколка (единицы параллелизуемого выполнения в цикле) строится сбалансированное дерево Меркла из обязательств по действиям чтобы создать временный общий корень Меркла. Это делается чтобы ускорить параллельные вычисления. Заголовок блока содержит корень сбалансированного дерева Меркла, листья которого являются корнями этих отдельных осколков деревьев Меркла. Это означает, что полученное дерево Меркла, представленное Action Root, не обязательно является сбалансированным деревом Меркла, однако, в большинстве случаев, это что-то очень похожее.
Учитывая действие, где-то на блокчейне, можно сжато продемонстрировать отозвание этого действия, доказав сначала, что оно было привержено блоком Action Root, а затем, что данный блок был привержен доверенным необратимым заголовком блока Block Root. Эти два доказательства называются «Action Path» и «Block Path» соответственно.
Action Path включает все данные (родственные дайджесты из дерева Меркла), необходимые для пересчета корня дерева Меркла в отношении одного обязательства действия. Этот корень дерева Меркла должен точно соответствовать Action Root, к которому привержен заголовок блока, который отозвал действие.
Block Path включает все данные, необходимы для пересчета корня дерева Меркла по отношению к одному Block ID. Этот корень дерева Меркла должен точно соответствовать Block Root, к которому привержен заголовок доверенного необратимого блока.
Например,
Учитывая действие выше, отозван в блок с ID:
00000033e4f902358b1d43918d197652fc01baaf0e6ca8ee38cda2e8780b7dbd
Чей Action Root был:
067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57
И надежный необратимый блок, чей Block Root представляет следующее:
1ae092ea41e70982b56b9673f990346876ba535595df16dc1094740c144aaae6
Данные по доказательствам выглядят следующим образом:
Action Path:
9b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91
9cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
C65abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
4cf39dfbe8a0fdc2540c8f0b68037484051a20d6ca00b891bbfc66d826503677
A8773db30f3733063352d1abec5fea265115bdf646a69d21545746a4f7cff3f3
Block Path:
8000003418a608c3704f80cdfed2793a055cc13993eea67ccdd018d9df027101
2351ee036c6a4052e18c9ded8d35c1b1dfb330531e163039847797d38e9babd2
De1996e5c23c73fa212abaaf423b9038e289fc7a19be5a7f395c7727a5266168
Ccd7c6e10b398fd27cfc4d29f339806593d614c736ae1af8a47908e44d2fe924
1e95b55e98d329bda8f2c79d1f969650716207a03f13f540931ab5a6a80f4d0b
369d86219b35e493a4fda3649c9f3a546809add40462c4b5ddca185f75cfe05c
9067c63043027831fbc7ba046d5bd7d9a0c23e1baa6fe0ac16a911ff7c3acd74
Чтобы проверить это доказательство, сначала выполните сериализацию заявленного обязательства действия в стандартном для EOS.IO двоичном формате. Это приводит к следующему двоичному представлению (в шестнадцатеричном виде):
000000000095dd740000000000ea3055000000572d3ccdcd1d000000000095dd74000000000093dd741027000000000000046d656d6f0000000000000000020100000000000000000000000095dd7401000000000000000100000000000000000000000093dd740000000000000000
EOS.IO, в настоящее время, использует SHA256 для своего дайджест метода (HASH_FN), поэтому дайджест листа - это SHA256 двоичного представления указанного выше:
1b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91
Используя этот дайджест листа, примените Block Path, обращаясь к разделу канонических путей и подписей, чтобы определить требует вхождение на пути левой или правой конкатенации. После применения полного пути, корневой дайджест, который мы получим в результате должен быть равен Action Root в заголовке блока, который отозвал действие:
C_HASH(
1b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279
bd0ca91,
9b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91)
=> 1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
C_HASH(
1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067,
9cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067)
=> 465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
C_HASH(
465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167,
C65abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167)
=> dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab
C_HASH(
4cf39dfbe8a0fdc2540c8f0b68037484051a20d6ca00b891bbfc66d826503677,
dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab)
=> ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996
C_HASH(
ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996,
a8773db30f3733063352d1abec5fea265115bdf646a69d21545746a4f7cff3f3)
=> 067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57
После того, как мы проверили, что блок имеет обязательство отозвать действие как описано, мы также должны убедиться, что отозванный блок включен в блокчейн с использованием Block Path и ID отозванного блока. После применения полного пути корневой дайджест, который получаем в результате, должен быть точно равен Block Root в заголовке доверенного необратимого блока:
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 репозитории.
CryptoLions
