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

Користувачі та розробники не взаємодіють із SMT безпосередньо; докази виключення обчислюються та надсилаються автоматично сервісом operator-private-channel. Ця сторінка є довідковим матеріалом для операторів та всіх, хто розробляє інструменти для операторів.

Програма ескроу мігрує з цієї конструкції розрідженого дерева Меркла на побітову карту нонсів у ланцюжку (відстежується upstream). Ця сторінка відповідає поточній програмі ескроу та буде оновлена після впровадження відповідних змін.

Призначення

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.