Итак, я читаю это (отличный ресурс) о дереве Меркла Биткойн для транзакции.
Дерево Меркла строится снизу вверх. В следующем примере мы начинаем с четырех транзакций, A, B, C и D, которые образуют листья дерева Меркла, как показано в разделе «Вычисление узлов в дереве Меркла». Транзакции не хранятся в дереве Меркле; скорее, их данные хешируются, и полученный хэш сохраняется в каждом конечном узле как HA, HB, HC и HD:
HA = SHA256(SHA256(Transaction A))Затем последовательные пары листовых узлов суммируются в родительском узле путем объединения двух хэшей и их хэширования. Например, чтобы создать HAB родительского узла, два 32-байтовых хэша дочерних узлов объединяются для создания 64-байтовой строки. Затем эта строка подвергается двойному хэшированию для получения хэша родительского узла:
HAB = SHA256(SHA256(HA + HB))Процесс продолжается до тех пор, пока наверху не останется только один узел, известный как корень Меркла. Этот 32-байтовый хэш хранится в заголовке блока и суммирует все данные всех четырех транзакций.
Это логично, но у меня есть несколько вопросов. Во-первых, как хешируется транзакция, такая как транзакция A, и что на практике включается в транзакцию. Например, если это строковый объект JSON или byteArray в JavaScript, или если данные должны быть в определенном формате и т. д. Я хотел бы, например, посмотреть, как запись будет хэшироваться, например, или что-то в этом роде { a: 'foo', b: 'bar', c: 123, ... }.
Во-вторых, если именно здесь возникает идея дерева Патрисии Меркл (или, возможно, даже Merkle DAG, которую я где-то видел), чтобы сократить количество вещей, которые вы должны хранить в памяти, потому что хэши не полностью перекрываются. и поэтому будет много пустых узлов дерева.
Наконец, как будет выглядеть примерный набор транзакций в одном блоке, где они говорят, что в среднем у них 1900 транзакций. Это будет довольно глубокое дерево Меркла, и я хотел бы увидеть, как на самом деле называются транзакции, и немного больше информации об их структуре данных. Например, если они доходят до операций ISA (архитектура набора инструкций) или находятся на гораздо более высоком уровне. Вот, в принципе, и все, что я хотел бы знать. Я еще не видел этого в книге, указанной выше, но посмотрю поближе .
Листья в дереве Меркла — это идентификаторы транзакций ( txid) транзакции, которые, в свою очередь, являются двойным SHA256 полной сериализованной транзакции в ее двоичной (с прямым порядком байтов) форме, которая является тем же форматом, что и полученная по сети. .
Глава 06 той же книги описывает сериализацию структур txinи txout. Я не уверен, почему сам формат транзакции отсутствует в книге. Транзакция — это сериализация последовательности txinи txoutструктур с дополнительной версией и временем блокировки.
tx {
version : int32
txin_count : VarInt
txins : txin[]
txout_count : VarInt
txouts : txout[]
nLockTime : uint32
}
Тот VarIntсамый, что используется в книге. В исходном коде ядра Биткойн он называется CompactSize.
Существует альтернативный формат для транзакций-свидетелей, который используется клиентами, поддерживающими этот формат, который использует трюк, который txin_countобычно должен быть >= 1, потому что все транзакции должны использовать существующий ввод (кроме coinbase tx). Таким образом, если байт, где txin_countожидается выше, имеет значение 0, это говорит о наличии свидетельской транзакции, где есть какие-то дополнительные поля.
witness_tx {
version : int32
witness_marker : byte //always 0
witness_flag : byte
txin_count : VarInt
txins : txin[]
txout_count : VarInt
txouts : txout[]
witnesses : witness[] //list always has the same length of txin_count
nLockTime : uint32
}
Даже если транзакция является транзакцией-свидетелем, txформат используется для создания txidэтой транзакции, которая будет использоваться при расчете корня Меркла. Это необходимо для обеспечения обратной совместимости транзакций-свидетелей со старым форматом транзакций. Клиент, поддерживающий SegWit, который взаимодействует с клиентом, который его не поддерживает, будет отправлять формат txсвоему партнеру для транзакций-свидетелей, а не witness_txформат.
1) Транзакции не содержат мерклехэшей. Хэши транзакций до SegWit рассчитываются путем сериализации транзакции (вы можете искать «шестнадцатеричный формат»), а затем хеширования массива байтов. После SegWit подписи исключаются из хэшей транзакций.
2) (не могу понять, что вы просите)
3) 1900 транзакций - это не так уж и глубоко. Высоту можно рассчитать ceil(log_2(number_of_tx))+1. Подставьте 1900, и высота будет 12. Если вы хотите узнать, как можно использовать деревья Меркла для ISA, я бы посоветовал поискать MAST . Это позволяет скрыть невыполненные части скрипта.
Джо
Марк Х
txin_countобычно используется устаревший формат tx, и просто указывает, что транзакция является транзакцией-свидетелем, поэтому оставшиеся байты анализируются во втором формате-свидетеле.