Rzadkie drzewo Merkle'a

Użytkownicy i deweloperzy nie wchodzą bezpośrednio w interakcję z SMT; dowody wykluczenia są obliczane i przesyłane automatycznie przez usługę operator-private-channel. Ta strona stanowi materiał referencyjny dla operatorów oraz osób budujących narzędzia operatorskie.

Program escrow jest migrowany z tego projektu rzadkiego drzewa Merkle'a do mapy bitowej nonce przechowywanej w łańcuchu (śledzonej upstream). Ta strona jest zgodna z aktualnym programem escrow i zostanie zaktualizowana po wdrożeniu tej zmiany.

Cel

Private Channels wykorzystuje rzadkie drzewo Merkle'a (SMT), aby zagwarantować, że każdy nonce wypłaty może zostać rozliczony tylko raz. Gdy operator wywołuje ReleaseFunds, musi dostarczyć dwa dowody: dowód wykluczenia, że nonce NIE istnieje jeszcze względem bieżącego korzenia, oraz dowód włączenia, że nonce ISTNIEJE w nowym korzeniu dostarczonym przez wywołującego. Dopiero po przejściu obu weryfikacji program zapisuje nowy korzeń, czyniąc każdą przyszłą próbę ponownego użycia nonce dowodliwie nieważną.

Parametry drzewa

Wysokość drzewa: 16
Maksymalna liczba liści: 65 536 (2^16)
Funkcja skrótu: SHA-256
Wartość pustego liścia: [0u8; 32] (32 bajty zerowe)
Wartość niepustego liścia: SHA256([1u8; 32]), przechowywana jako stała 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)

Struktura liścia

Każda wypłata zajmuje dokładnie jeden liść. Pozycja liścia jest określana przez:

leaf_position = transaction_nonce % 65536

Liść jest uznawany za niepusty, gdy jego wartość jest równa NON_EMPTY_LEAF_HASH (tj. SHA256([1u8; 32])). Pusty liść zawiera same zera.

Nonce i pozycja liścia

transaction_nonce w ReleaseFunds jest typu u64. Jego pozycja w drzewie to nonce % 65536. Oczekiwany epoch to nonce / 65536. Program w łańcuchu weryfikuje, czy obliczony epoch jest równy Instance.current_tree_index; niezgodność powoduje zgłoszenie błędu InvalidTransactionNonceForCurrentTreeIndex.

Rotacja drzewa

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 ma stałą pojemność 65 536 liści. Usługa operatora wykrywa konieczność rotacji, sprawdzając, czy nonce % 65536 == 0 (dla nonce > 0); ta granica sygnalizuje początek nowego epoch. W tym momencie operator-private-channel wywołuje ResetSmtRoot przed przesłaniem kolejnego ReleaseFunds:

Instance.current_tree_index jest inkrementowany
Korzeń wypłat jest resetowany do pustego drzewa
Nonce z poprzedniego epoch drzewa są unieważniane

Usługa operatora weryfikuje również, czy lokalny korzeń SMT odpowiada Instance.withdrawal_transactions_root w łańcuchu przed każdym wywołaniem ReleaseFunds; niezgodność powoduje bezpieczne wyłączenie zamiast potencjalnie nieprawidłowego przesłania dowodu.

Rotacja drzewa jest śledzona przez Instance.current_tree_index: u64, przechowywany w łańcuchu.

Weryfikacja w ReleaseFunds

Argument sibling_proofs w ReleaseFunds ma dokładnie rozmiar [u8; 512]: 16 skrótów rodzeństwa × 32 bajty każdy, odpowiadający wysokości drzewa równej 16.

Proces weryfikacji w łańcuchu wykonuje dwie oddzielne kontrole sekwencyjnie:

verify_smt_exclusion_proof dowodzi, że liść nonce jest aktualnie pusty względem bieżącego Instance.withdrawal_transactions_root
verify_smt_inclusion_proof dowodzi, że liść nonce jest obecny w argumencie new_withdrawal_root dostarczonym przez wywołującego
Tylko jeśli obie kontrole przejdą pomyślnie, program zapisuje new_withdrawal_root jako nowy Instance.withdrawal_transactions_root i zwalnia tokeny

Niepowodzenie którejkolwiek kontroli powoduje zgłoszenie błędu InvalidSmtProof. Aktualizacja korzenia w kroku 3 jest atomowa z każdym wywołaniem ReleaseFunds.