Почему дерево Меркла более эффективно, если ветви дерева не хранятся в блокчейне?

Предположим, у нас есть 8 транзакций в блоке X, как показано ниже, и мы знаем хэш-значение каждого узла всего дерева Меркла (то есть включая промежуточные узлы, такие как 45). Затем, если кто-то утверждает, что транзакция tсуществует Xи находится по адресу 6. Чтобы убедиться в этом, нам нужно только найти хэш-значения в 7, 45, 0123 и хешировать вверх и сравнить с корнем Merkle 01234567.

Я предполагаю (исходя из этого ), что дерево Меркла быстрее, чем непосредственное хеширование конкатенации TXID0 ~ TXID7, потому что алгоритм хэширования работает быстрее на небольших файлах (даже при запуске ~log(N)), чем на большом файле (т.е. конкатенация NTXID, Nздесь 8 ) в одно время.

Но, читая этот пост, кажется, что Nв блоке хранятся только корень Merkle и TXID, и нам приходится воссоздавать древовидную структуру каждый раз, когда мы проверяем транзакцию, что на самом деле будет запускать хеш-функции ~Nраз, а не ~log(N)раз (если я был прав математически).

Мои вопросы:

  1. Время хеширования по- ~Nпрежнему быстрее, чем однократное хеширование для Nконкатенированных хэш-значений?
  2. Почему дерево Меркла не сохраняется? Это связано с соображениями хранения?

введите описание изображения здесь

Ответы (1)

Скорость хеширования примерно линейна по количеству обработанных байтов: SHA2 обрабатывает блок из 64 байтов за раз, а затрачиваемое время равно количеству обработанных блоков. При вычислении хеш-дерева обрабатывается больше блоков из-за промежуточных уровней, но почти вся обработка может выполняться параллельно, в отличие от линейного хеширования, которое должно выполняться последовательно.

Узел проверяет блок только один раз. Для этой цели не имеет большого значения, является ли хэш деревом или линейным, хотя, если используется параллелизм, вычисление хэша дерева происходит быстрее.

[А Bitcoin Core использует векторные инструкции для параллельной обработки хэшей дерева для ускорения в несколько раз. В настоящее время он не беспокоится об использовании нескольких ядер для этого, хотя мог бы.]

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

Дерево не сохраняется в текущих реализациях Биткойн, потому что нет операции, которая действительно выиграла бы от его хранения в реализациях. Доказательство того, что облегченный клиент был оплачен, является относительно нечастой операцией, а пересчет хеш-дерева стоит недорого. Реализация могла бы начать хранить его, если бы у нее была на то причина. TXID также не сохраняются, поскольку их можно просто вычислить из самих транзакций.

Почему дерево Меркла более эффективно, если ветви дерева не хранятся в блокчейне?
СпросиСетьПолитика конфиденциальности1y, 0v