Разреженное дерево Меркла

Пользователи и разработчики не взаимодействуют с SMT напрямую — доказательства исключения вычисляются и отправляются автоматически сервисом operator-private-channel. Эта страница является справочным материалом для операторов и всех, кто разрабатывает инструментарий для них.

Программа эскроу переходит от этой схемы разреженного дерева Меркла к побитовой карте нонсов на блокчейне (отслеживается в основной ветке). Эта страница актуальна для текущей версии программы эскроу и будет переработана после внедрения указанных изменений.

Назначение

Private Channels использует разреженное дерево Меркла (SMT), чтобы гарантировать однократное исполнение каждого нонса вывода средств. Когда оператор вызывает ReleaseFunds, он должен предоставить два доказательства: доказательство исключения того, что нонс ещё НЕ существует относительно текущего корня, и доказательство включения того, что нонс СУЩЕСТВУЕТ в новом корне, переданном вызывающей стороной. Только после успешного прохождения обеих проверок программа сохраняет новый корень, делая любую будущую попытку повторного использования нонса доказуемо недействительной.

Параметры дерева

Высота дерева: 16
Максимальное количество листьев: 65 536 (2^16)
Хэш-функция: SHA-256
Значение пустого листа: [0u8; 32] (32 нулевых байта)
Значение непустого листа: SHA256([1u8; 32]), хранится как константа NON_EMPTY_LEAF_HASH

                        Root Hash (32 bytes)
                       /                    \
                 Hash(L, R)                Hash(L, R)
                /         \                /         \
          Hash(L, R)   Hash(L, R)   Hash(L, R)   Hash(L, R)
          /      \      /      \      /      \      /      \
        ...    ...    ...    ...    ...    ...    ...    ...
       /  \   /  \   /  \   /  \   /  \   /  \   /  \   /  \
   Leaf0  1  2   3  4   5  6   7  8   9  10 11 12 13 14 15 ...
   (nonces recorded as leaf positions using their value modulo 65536)

Структура листа

Каждый вывод средств занимает ровно один лист. Позиция листа определяется следующим образом:

leaf_position = transaction_nonce % 65536

Лист считается непустым, если его значение равно NON_EMPTY_LEAF_HASH (то есть SHA256([1u8; 32])). Пустой лист состоит из одних нулей.

Нонс и позиция листа

transaction_nonce в ReleaseFunds имеет тип u64. Его позиция в дереве равна nonce % 65536. Ожидаемый epoch — nonce / 65536. Программа на блокчейне проверяет, что вычисленный epoch совпадает с Instance.current_tree_index; при несоответствии выбрасывается исключение InvalidTransactionNonceForCurrentTreeIndex.

Ротация дерева

Tree Index 0 (nonces 0-65,535)              Tree Index 1 (nonces 65,536-131,071)
┌────────────────────────────┐             ┌────────────────────────────┐
│ Root: 0x8fe6...            │             │  Root: 0x8fe6... (reset)   │
│ Nonces Used: 65,536/65,536 │   Rotate    │  Nonces Used: 0/65,536     │
│ Status: FULL               │   ──────>   │  Status: ACTIVE            │
└────────────────────────────┘             └────────────────────────────┘
         (Tree exhausted)                          (Fresh tree)

SMT имеет фиксированную ёмкость в 65 536 листьев. Сервис оператора определяет необходимость ротации, проверяя условие nonce % 65536 == 0 (при nonce > 0); эта граница сигнализирует о начале нового epoch. В этот момент operator-private-channel вызывает ResetSmtRoot перед отправкой следующего ReleaseFunds:

Значение Instance.current_tree_index увеличивается на единицу
Корень выводов сбрасывается до пустого дерева
Нонсы из предыдущего epoch дерева аннулируются

Сервис оператора также проверяет, что локальный корень SMT совпадает с Instance.withdrawal_transactions_root на блокчейне перед каждым вызовом ReleaseFunds; при несоответствии инициируется аварийное отключение, а не потенциально некорректная отправка доказательства.

Ротация дерева отслеживается через Instance.current_tree_index: u64, хранящийся на блокчейне.

Верификация в ReleaseFunds

Аргумент sibling_proofs в ReleaseFunds имеет строго фиксированный размер [u8; 512]: 16 хэшей смежных узлов × 32 байта каждый, что соответствует высоте дерева 16.

Процесс верификации на блокчейне выполняет две отдельные проверки последовательно:

verify_smt_exclusion_proof доказывает, что лист нонса в данный момент пуст относительно текущего Instance.withdrawal_transactions_root
verify_smt_inclusion_proof доказывает, что лист нонса присутствует в переданном вызывающей стороной аргументе new_withdrawal_root
Только при успешном прохождении обеих проверок программа сохраняет new_withdrawal_root как новый Instance.withdrawal_transactions_root и высвобождает токены

Провал любой из проверок вызывает исключение InvalidSmtProof. Обновление корня на шаге 3 является атомарным с каждым вызовом ReleaseFunds.