Sparse Merkle Tree

Utenti e sviluppatori non interagiscono direttamente con l'SMT; le prove di esclusione vengono calcolate e inviate automaticamente dal servizio operator-private-channel. Questa pagina è materiale di riferimento per gli operatori e per chiunque sviluppi strumenti per operatori.

Il programma di escrow sta migrando da questo design Sparse Merkle Tree a una bitmap di nonce on-chain (tracciata upstream). Questa pagina è accurata rispetto al programma di escrow corrente e verrà aggiornata una volta che tale modifica sarà applicata.

Scopo

Private Channels utilizza uno Sparse Merkle Tree (SMT) per garantire che ogni nonce di prelievo possa essere liquidato una sola volta. Quando un operatore chiama ReleaseFunds, deve fornire due prove: una prova di esclusione che il nonce NON esiste ancora rispetto alla root corrente, e una prova di inclusione che il nonce ESISTE nella nuova root fornita dal chiamante. Solo dopo che entrambi i controlli superati il programma memorizza la nuova root, rendendo qualsiasi futuro tentativo di riutilizzo del nonce dimostrabilmente non valido.

Parametri dell'Albero

Altezza dell'albero: 16
Numero massimo di foglie: 65.536 (2^16)
Funzione hash: SHA-256
Valore foglia vuota: [0u8; 32] (32 byte zero)
Valore foglia non vuota: SHA256([1u8; 32]), memorizzato come costante 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)

Struttura delle Foglie

Ogni prelievo occupa esattamente una foglia. La posizione della foglia è determinata da:

leaf_position = transaction_nonce % 65536

Una foglia è considerata non vuota quando il suo valore è uguale a NON_EMPTY_LEAF_HASH (ovvero SHA256([1u8; 32])). Una foglia vuota è composta da tutti zeri.

Nonce e Posizione della Foglia

Il transaction_nonce in ReleaseFunds è un u64. La sua posizione nell'albero è nonce % 65536. Il suo epoch atteso è nonce / 65536. Il programma on-chain convalida che questo epoch calcolato sia uguale a Instance.current_tree_index; una discordanza genera l'errore InvalidTransactionNonceForCurrentTreeIndex.

Rotazione dell'Albero

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)

L'SMT ha una capacità fissa di 65.536 foglie. Il servizio operatore rileva quando è necessaria una rotazione verificando se nonce % 65536 == 0 (per nonce > 0); quel limite segnala l'inizio di un nuovo epoch. A quel punto, operator-private-channel chiama ResetSmtRoot prima di inviare il successivo ReleaseFunds:

Instance.current_tree_index viene incrementato
La root dei prelievi viene reimpostata sull'albero vuoto
I nonce dell'epoch dell'albero precedente vengono invalidati

Il servizio operatore verifica inoltre che la propria root SMT locale corrisponda a Instance.withdrawal_transactions_root on-chain prima di ogni chiamata ReleaseFunds; una discordanza attiva uno spegnimento di sicurezza invece di una potenziale submissione di prove non valide.

La rotazione dell'albero è tracciata da Instance.current_tree_index: u64, memorizzato on-chain.

Verifica in ReleaseFunds

L'argomento sibling_proofs in ReleaseFunds è esattamente [u8; 512]: 16 hash fratello × 32 byte ciascuno, corrispondenti all'altezza dell'albero di 16.

Il processo di verifica on-chain esegue due controlli separati in sequenza:

verify_smt_exclusion_proof prova che la foglia del nonce è attualmente vuota rispetto alla Instance.withdrawal_transactions_root corrente
verify_smt_inclusion_proof prova che la foglia del nonce è presente nella new_withdrawal_root fornita dal chiamante
Solo se entrambi i controlli vengono superati il programma memorizza new_withdrawal_root come nuovo Instance.withdrawal_transactions_root e rilascia i token

Il fallimento di uno dei due controlli genera InvalidSmtProof. L'aggiornamento della root al passaggio 3 è atomico con ogni chiamata ReleaseFunds.