Это конкретное предложение (и эталонная реализация) для Merkle дерева неизрасходованных-выходов (UTXOs). В конце концов, идея состоит в том, чтобы включить в корневой хеш текущего UTXO дерева в каждом блоке. Это позволит полную проверку (нулевого доверия) облегчённые клиентов, которые используют только константу O (1) объем хранения - например, клиент, который подходит на смарт-карты - и O (журнал N) количество усилий на txOut (где N представляет собой общее количество UTXOs в любой момент времени).

**РЕДАКТИРОВАТЬ**Я включал несколько изменений по сравнению с прослеживание сообщение которые повышают сложность транзакций проверки.

обзор
Проверка сделки требует проверки того, что каждый ТХ-вход не был уже израсходованы. Один из способов сделать это, чтобы перебирать, для каждого TX-вход, от головы цепи обратной, ищет сделки, которая проводит его. Это было бы неэффективным - вместо этого, стандартный клиента (в том числе Питера Wuille-х UltraPrune изменение) создает и поддерживает базу данных, содержащие (по крайней мере) всю доступную в настоящее время монеты. Предлагаю хранить неизрасходованные выходы, а также в качестве дополнительного "запросов по-адрес" Индекс, в сбалансированном Merkle дерева поиска, (то есть, дерево RedBlack дополнен хешами). Это приведет к ряд преимуществ:

• узлы Full-проверки (особенно облегченный клиентов) нужно будет только для хранения (и доверия) в O (1) хэш текущего блока головки. Данные проверки могут быть запрошены по мере необходимости из (полностью ненадежного) распределенной хеш-таблицы (DHT) (например, сеть сплетен-слой).
• Lite клиенты могут "начальная загрузка" сами немедленно, просто выбрав правильную голову.
• Клиенты могут безопасно запросить DHT для получения полного списка расходуемого (стандарт) UTXOs, связанного с данным адресом, без необходимости "пересканировать" blockchain.
• Произвольная длина вилка может быть допущена без необходимости выработки "REORG."
• "Доказательств" недействительных сделок (например, двойной потратить) может быть подтверждено в O (N журнал), а также.

Это предложение предусматривает один дополнительный хэш для размещения в каждом блоке: корень хэш дерева UTXO Merkle. Как таковая, она принадлежит в HardFork лист пожеланий. Тем не менее, он также может быть включен в (необязательно слияние-добытого) альт-цепи. Это потребует дополнительных вычислений для проверки транзакции - добавление будет постоянным фактор, так как каждый обработано txinput / txoutput уже требует (даже в UltraPrune), уплотнительный (журнал N) обновление таблицы ВТКЕЯ из UTXOs. На данный момент, это предложение просто описывает автономную структуру данных, которая может быть получена на основе имеющихся данных blockchain.

Нормативная спецификация для этого протокола состоит из A) (сериализация и переваривает) формат для узлов в сбалансированном дереве, где каждый узел листа содержит одну UTXO, а узлы ветвления содержат хеши своих детей; и B) алгоритмы вставки / удаления, которые сохраняют инварианты RedBlack (балансировочный) дерев, гарантирующий O (журнал N) наихудшее усилие каждого обновления.

Эталонная реализация написана на Python, и состоит из 1) модульных, расширяемых, и побочного эффекта свободной RedBlack дерево (в том числе модульных тестов), которые могут быть дополнены произвольно «переварить» функции, 2) экземпляр этой структуры с указанная функция переваривать, и 3) скрипт, который обрабатывает фактические данные blockchain и применяет каждое обновление (каждый txinput и txoutput) к дереву Merkle. Эталонная реализация не совсем оптимизированы, но вместо этого предназначен для простой в анализе и обеспечить побитно правильный золотой стандарт для дерева Merkle на каждом шагу.

Это предложение также является предшественником "В конце концов, Zero-Trust Вероятностный Validation" Схема I описана в более ранняя нить.

Связанных с работой
ByteCoin первым предложил в том числе хэш тока "баланс" в каждом блоке (То есть, набор доступных неизрасходованных выходов TX), что делает возможным проверить транзакции без необходимости хранить всю blockchain. Грег Максвелл позже предложил используя дерево Меркла для того, чтобы выполнить запрос, например, этот набор более эффективно. DiThi позже сделал эквивалентное предложение. Совсем недавно, etotheipi предложил используя самобалансирующейся Меркле дерево так что инкрементальная модификация структуры будет более эффективной. Я обыскивал научную литературу, поиск Usenix документ с 1996 года по Moni NaOR и Kobbi Nissim, предполагая, что дерево RedBlack может быть увеличено с хэш вместо указателей. я написал эталонная реализация такого "Структура данных идентифицированных", Насколько мне известно, это единственный доступный (с открытым исходным кодом) реализация самобалансирующегося хэш дерева.

Хэш дерева (сорта без балансировочных) широко используются, например, в Гит И в Тахо-LAFS.

Нормативная Спецификация протокола
А. Сериализация и Digest Формат
Каждый узел в двоичном узле дерева поиска RedBlack состоит из 1) ключа (самый большой ключа в левом поддереве), 2) левый и правый дети (возможно, отсутствующего), и 3) один бит (представляющий красный или черный), используемый для балансировки 4) значения (только листовые узлы). Ключи должны быть упорядоченная в целях поддержки эффективных поисковых запросов к этой структуре. Два вида запросов поддерживаются (хотя еще может быть добавлено): поиск по (TXID, индекс), как это необходимо для подтверждения операций, а также поиск по (адрес, TXID, индекс), который полезен для клиентов для запроса баланс адреса.

Есть два вида отображений, хранящихся в дереве:
1. UTXO проверки:
       (TXID, индекс) -> (Хэш данных проверки)

    Проверки достоверности данных является подмножеством данных о транзакции, соответствующих TXID: один scriptPubKey, а также некоторые необходимые метаданные (isCoinbase и nHeight).

2. Адрес сканирования:
      (Адрес, TXID, индекс) -> ()

    Нет отдельное значение не используется для этого типа, так как вся информация содержится в уникальном ключе.

Два основных типа обозначены префиксом четыре байт, "UTXO" для (TXID, индекс), и "АДРЕСА" для (адрес, TXID, индекс). «Корневого хэш» является дайджестом корневого узла дерева. Каждый гидролизат является SHA256 хэш сериализованного узла. В последовательном формате, левые и правые поддеревья представлены их переваривает. Дайджеста пустого дерева представлена ​​на 32 нулевых байтов (то есть, генезис хэш). Листовые узлы и узлы ветвления упорядочиваются по-другому, со значением дозорного ("," для листьев, "^" для филиалов), чтобы различать между ними.

Промежуточные узлы сериализуются следующим образом:

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


Б. Алгоритм балансировки
Любое бинарное дерево поиска определяет три операции: вставка, удаление и поиск. Алгоритм RedBlack уравновешивает дерево во время каждой вставки и удаления. Каждая операция представляет собой О (N войти) в худшем случае. Поскольку блоки будут содержать обязательства по определенной корневой хэш, и, следовательно, особого дерево, то необходимо указать нормативные особые правила балансировки (есть потенциально несколько допустимых способов сбалансировать дерево RedBlack).

Особые правила балансировки, которые я выбрал, были опубликованы (Stefan Kahrs, "Красно-черные деревья с типами" Журнал функционального программирования, 11 (04), стр 425-432, июль 2001 г.), и полностью определены в этот код Haskell. Этот алгоритм широко используется, например, см LLRB деревья Kāzu Ямамото, этот пост в блоге Мэтт Might, а также этот пост в блоге Марк Чу-Кэррола. Эти правила основаны на знаменитой докторской диссертации Криса Окасаки, в Чисто функциональные структуры данных, которая предусматривает четыре простого правила индивидуального матча достаточно для RedBlack дерева вставка (видеть "баланс" в спецификации Haskell). Для реализации удаление, четыре дополнительные случаи должны быть обработаны (см "balleft" а также "balright" в спецификации Haskell).

Для каждой сделки, сначала все txinputs будут удалены (в последовательном порядке) из дерева, и вторые все новые txoutputs вставляются (также в последовательном порядке). Каждая операция применяется в последовательном порядке в пределах каждого блока, и, конечно, каждый блок применяется для того, как он появляется в цепи.

Ссылка Impementation
Эталонная реализация состоит из трех питона файлов.

• redblack.py: Реализация красно-черного дерева Стефана Kahrs', с расширяемой "дайджест" увеличение. Два "режимы" предусмотрены для каждой из трех операций: режим записи работает на полном дереве (представлен в виде вложенных питона кортежи), и производит Проверочное Object (VO) (т.е. O (журнал N) путь, состоящий только из узлов, которые были доступ во время этой операции), в то время как режим воспроизведения принимает в корневой хэш и ненадежного VO и проверяет операцию пересчета хэш на каждом шаге.
• utxo_merkle.py: Специализация RedBlack по definining протокола / сериализации дайджеста описана выше
• merkle_scan.py: Скрипт, который перебирает весь blockchain, от генезиса блока к голове, постепенно обновляя Merkle дерево, как она идет (требует Гэвин Андресен-х питон bitcointools)

Кроме того, некоторые модульные тесты предоставляются, а также Graphviz-инструмент визуализации, который производит изображения, как те, в этом посте.

Эталонная реализация не оптимизирована. До сих пор я только запустить его на первых 140K блоков перед нетерпением. Это займет всего несколько минут, чтобы пробежать первые 200k сделок. Я спасу обсуждение оптимизированных реализаций для последующих сообщений в этой теме (я предлагаю вам помочь!), Хотя я планирую обновлять этот пост, по крайней мере с оценками производительности, как я иду вперед.

Тизер изображения (два байта хэш)
До и после вставки элемента 10 (дерева полного O (N), режим записи)


До и после вставки элемента 10 (только O (1) корневой хэш и О (журнал N), ненадежный В.О., режим воспроизведения)


Что теперь?
Это не новое предложение; вариации этой идеи были подпрыгивая с 2010 года Из-за свой потенциал для повышения безопасности и масштабируемости облегченных клиентов, важно развивать это раньше, чем позже. Моя цель состоит в том, чтобы подтолкнуть этот процесс вместе, предлагая конкретный протокол и обеспечивает эталонную реализацию. Этот поток должен быть о спецификации и детали реализации (прежде, чем сделать "Зачем беспокоиться?" сообщение, пожалуйста, прочитайте нить etotheipi или какой-либо другой я уже упоминал в произведении).

Эта нормативная спецификация очень мало говорит о том, как данные должны фактически быть сохранены или переданы, так что это может варьироваться в зависимости от реализации. Поскольку корневой узел будет меняться для каждого обновления, но листовые узлы будут меняться нечасто, это имело бы смысл использовать эвристический / вероятностный кэш. Нормативная спецификация очень проста, поэтому я ожидаю, другие разработчики не испытывают особые трудности решений, совместимые реализаций на других языках. Самая трудная часть, вероятно, будет реализация самого алгоритма RedBlack, поэтому я пытался сделать мою реализацию проста в использовании в качестве руководства и золотого стандарта. Если вы можете думать о поддерживающей функции я могу построить, чтобы помочь, (схемы, объяснения, например, код и т.д.), пожалуйста, спросите его в этой теме, и я охотно вмещать вас.

Я планирую постепенно оптимизировать эталонную реализацию, и для O (1) -Хранение Lite-клиентов и полный O (N) -Хранение (UltraPrune) клиентов, а также для обеспечения масштабируемого (ненадежный) DHT, который может служить дерево данные для любой точки в blockchain истории. Мне нужно будет сделать по крайней мере, некоторому прогрессу в этом направлении, прежде чем я могу предложить какую-либо оценку производительности. Вот профиль / для граф вызовов текущей реализации, предполагая, что менее чем 2% времени тратится на вычисления хэшей (большую часть времени тратится на моей эскизной функции сопоставления с образцом, так что это первое, что нужно работать над).

Оба etotheipi и gmaxwell предпочел бы использовать вместо попыток сбалансированных бинарных деревьев по причинам, я считаю uncompelling. Пытается (по крайней мере те, с Merkle хэшей), вероятно, потребуется больше пространства и вычислений, чем сбалансированных деревьев. Etototheipi любит вставную-заказ-независимость в синтаксическом дереве, хотя это не имеет значения, если каждые из них содержит обязательство к корневому хэшу (так как вы можете найти предыдущий корневой хэш в предыдущем блоке). Я не знаю, почему gmaxwell предпочитает попытку. В любом случае, это их очередь обеспечить конкурирующую реализацию!