предложение чтобы помочь SPV узлов проверки блоков, чтобы совершить корень из (несбалансированного) Merkle дерева, содержащего все неизрасходованных (и расходуемые) выходы транзакций.

Можно создать доказательства валидности для каждой модификации набора. Доказательство будет доказать, что вставка записи в дерево с корнем X даст новое дерево с корнем Y. Там также будут доказательства для удаления записей.

Это означает, что каждая модификация набора UTXO может иметь доказательства, связанные с ним. Блок может содержать операции и доказательство. Каждое доказательство будет связан с входом или выходом сделок. Для каждого входа, было бы доказательство удаления из набора, и для каждого выхода, было бы доказательство вставки в набор. Unspendable выходы не будут вставлены в набор. (Для этого потребуется формальное определение unspendable, вероятно, выводит которые тратят на "OP_RETURN ...").

Мысли вслух о доказательствах, это то, что я имел в виду.

Проверяемость Merkle Set

Есть 2 вида узлов, листьев и узлов ветвления. Каждый узел имеет дайджест, связанный с узлом.

Вершины Отрасль

Эти узлы имеют ровно 2 детей. Хранения данных для этих узлов состоит в следующем.


Предполагая, что 4 байта указателей, каждый узел требует 46 байт (или 58 для 8 байт указателей).

Дайджест для узлов ветвления является хэш (0x00 | лево->дайджест | правильно->дайджест | узел->высота ).

Значение высоты считается от уровня листьев. 2 листов, которые различались только в LSB их entry_digest будут иметь высоту 1 родитель. Самая высокая высота 256. Это для листьев, которые различаются по MSB их entry_digest.

Ведущий 0x00 в массиве передается хэш-функции является указание узла ветвления.

листовые Вершины

Эти узлы являются листья дерева. У них нет детей. Хранения данных для этих узлов состоит в следующем.


Дайджест для узла является хэш (0x01 | хэш (entry_value)), но только хеш (entry_value), т.е. entry_digest, хранятся в дереве. переваривать узел может быть пересчитано, по мере необходимости, экономя оперативную память.

Ведущий 0x01 указывает узел листа. Листовые и узлы ветвления можно отличить друг от друга из-за префикс.

Корневая Digest

Если множество пусто, дайджест определяются как все нули. В противном случае, он определяется как дайджест корневого узла дерева.

Доказательство существования

Доказательство существования доказывает, что конкретная запись в наборе. Это доказательство байтовый массив определяется следующим образом.


Доказательство является филиалом Merkle, который начинается с листа и идет по пути к корню. Она включает в себя значение высоты для пути. 

Значение высоты используется для определения того, какой бит в entry_digest использовать, чтобы определить, если путь идет влево или вправо, в этой точке.

Поскольку значение высоты входят в качестве входных данных в хэш в узле ветвления, он является хэш герметизирует.

Если корень дайджест равен нуль, то это означает, что нет записей в наборе, поэтому доказательство существования всегда терпит неудачу.


Доказательства удаления

Можно вычислить новый корневой дайджест из доказательства существования узла листа должны быть удалены. Эффект удаления узла является то, что листовой узел и (узел ветвления) родительский узел будут удалены из дерева. родственный узел можно заменить родитель узла в дереве.

Если длина пути равна нулю, то узел является единственным узлом в дереве.


Вставка Доказательств

Как и с доказательствами удаления, можно вычислить новый корневой дайджест из доказательства существования. В каждой отрасли, доказательство следует выбрать его путь на основе entry_digest вступления вставляется. Расщепление этого листа называется leaf_entry_digest.

Так как entry_digest используется для выбора пути, то leaf_entry_digest должны иметь один и тот же бит в качестве entry_digest для высоты каждого узла ветви вдоль пути.

Все entry_digests листовых узлов, которые decendants узла ветви имеют те же самые старшие биты, День на высоте один больше, чем высота филиальной узла. Это заложено в связи с деревом является бинарным деревом.

Это означает, что наиболее значимые биты leaf_entry_digest могут быть использованы для определения префикса для каждого узла ветви. Биты, начиная с одного выше, чем высота узла ветви указывают префикс для этого узла ветви.

Новый узел ветви должен быть включен непосредственно ниже самого нижнего узла ветви, который имеет префикс, который соответствует entry_digest.

Рассмотрим вставку узла с entry_digest из 01011010b (предполагается, что хэш-функции производится один байт дайджесты). Верхний узел ветви в дереве имеет высоту 7. Так как бит 7 является одним (LSB это бит 1) в entry_digest, используется правильный путь. Это приводит к узлу ветви с высотой 3. Так как бит 3 равен 0, то используется путь влево. Следующий узел является листом. Он имеет leaf_entry_digest из 01110000. Это гарантировано соответствует записи переваривать для бит 7 и 3, но может быть что-нибудь еще для других бит.

Префикс для узла ветви высоты 7 равно 0 (все биты в leaf_entry_digest выше бит 7). Это соответствует entry_digest, так что новый узел будет потомком этого узла ветви.

Приставка для узла ветви высоты 3 составляет 01110. Это не соответствует старшим битого entry_digest. Это означает, что entry_digest не является потомком этого узла ветви.

Новый узел ветви должен быть вставлен в качестве дочернего узла ветви высоты 7 вместо узла ветви высоты 3.

Сравнивая 2 дайджестов:
01011010 (entry_digest)
01110000 (leaf_entry_digest)

Старший бит, который отличается тем, бит с высотой 6. Это означает, что новый узел ветвь имеет высоту 6 (который находится между высотой 3 и 7).

Новый узел листа производится для новой записи. Это левый потомок нового узла ветви. Узел ветвления высоты 3 является правильным ребенком.

Указатель от узла ветви высота 7, указывает на ветви узла высота 3 перенаправляется на новую ветку узла.


замена

Сменные доказательства содержат удаления и вставки доказательство, так как новый листовой узел не может быть помещен в том же месте. Это удваивает доказательства размера.

В эталонном клиенте, набор UTXO сжимаются. Все выходы для одного транзакций будут храниться вместе. Это может быть поддержано путем замены. Когда выход расходуется, старая версия вступления транзакции удаляется, и новый добавляются с этим выходом, помеченным как очищается.

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

Количество узла ветви в дереве равно числу листьев (минус 1). Это означает, что объем оперативной памяти будет примерно в два раза (при условии, данные, связанные с каждым листом вокруг такой же, как размер дайджеста).

В эталонном клиента, набор UTXO хранится в хэш-карте, которая отображает 32 байт TXID в компактное представление выходных транзакций. Жесткое кодирование, что компактный represenation, как правило, сети может быть слишком ограничительным. Если новый тип вывода стал популярным, он не будет уплотнять его много.