Дерево биткойнов Меркле всегда бинарное?

Question

Является ли дерево биткойн Меркле всегда двоичным?

(1) Меня интересует эффективность поиска дерева Меркле.

(2) Я не нашел никаких доказательств того, что деревья Меркля являются обязательными двоичными файлами, что позволило бы использовать алгоритм поиска O (log2 n).

(3) Если узел может иметь произвольное количество дочерних элементов, то функция поиска будет иметь O (logK n * K), где K - максимальное количество разрешенных дочерних узлов (насколько я помню).

Answer 1

Деревья Меркле по определению являются бинарными, посмотрите оригинальный патент здесь . Древовидная структура в биткойнах тоже бинарная.

Деревья не являются деревьями поиска, как традиционные деревья поиска, скорее, они используются как способ избавиться от данных блокчейна позже, но имеют доказательство того, что данные, специфичные для «корневого узла», существуют в блоке.

Вместо того, чтобы передавать весь биткойн-блок с n транзакциями, чтобы показать, что ваша транзакция существует в определенном блоке, вам нужно только предоставить log(n) узлов из дерева меркле.