Sparse Merkle Tree

Benutzer und Entwickler interagieren nicht direkt mit dem SMT; Ausschlussnachweise werden automatisch vom operator-private-channel-Dienst berechnet und übermittelt. Diese Seite dient als Referenzmaterial für Operatoren und alle, die Operator-Tooling entwickeln.

Das Escrow-Programm migriert von diesem Sparse Merkle Tree-Design zu einer On-Chain-Nonce-Bitmap (upstream verfolgt). Diese Seite ist korrekt bezüglich des aktuellen Escrow-Programms und wird überarbeitet, sobald diese Änderung eingeführt wird.

Zweck

Private Channels verwendet einen Sparse Merkle Tree (SMT), um sicherzustellen, dass jede Auszahlungs-Nonce nur einmal abgerechnet werden kann. Wenn ein Operator ReleaseFunds aufruft, muss er zwei Nachweise erbringen: einen Ausschlussnachweis, dass die Nonce noch NICHT in der aktuellen Root existiert, und einen Einschlussnachweis, dass die Nonce in der vom Aufrufer angegebenen neuen Root VORHANDEN ist. Erst nachdem beide Prüfungen bestanden sind, speichert das Programm die neue Root, wodurch jeder zukünftige Versuch, die Nonce wiederzuverwenden, nachweislich ungültig wird.

Baumparameter

Baumhöhe: 16
Maximale Blätter: 65.536 (2^16)
Hash-Funktion: SHA-256
Leerer Blattwert: [0u8; 32] (32 Null-Bytes)
Nicht-leerer Blattwert: SHA256([1u8; 32]), gespeichert als Konstante 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)

Blattstruktur

Jede Auszahlung belegt genau ein Blatt. Die Blattposition wird bestimmt durch:

leaf_position = transaction_nonce % 65536

Ein Blatt gilt als nicht leer, wenn sein Wert NON_EMPTY_LEAF_HASH (d. h. SHA256([1u8; 32])) entspricht. Ein leeres Blatt besteht aus lauter Nullen.

Nonce und Blattposition

Die transaction_nonce in ReleaseFunds ist ein u64. Ihre Position im Baum beträgt nonce % 65536. Die erwartete epoch ist nonce / 65536. Das On-Chain-Programm validiert, dass diese berechnete epoch Instance.current_tree_index entspricht; bei Abweichung wird InvalidTransactionNonceForCurrentTreeIndex ausgelöst.

Baumrotation

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)

Der SMT hat eine feste Kapazität von 65.536 Blättern. Der Operatordienst erkennt, wann eine Rotation erforderlich ist, indem er prüft, ob nonce % 65536 == 0 gilt (für nonce > 0); dieser Grenzwert signalisiert den Beginn einer neuen epoch. Zu diesem Zeitpunkt ruft operator-private-channel ResetSmtRoot auf, bevor das nächste ReleaseFunds übermittelt wird:

Instance.current_tree_index wird inkrementiert
Die Auszahlungs-Root wird auf den leeren Baum zurückgesetzt
Nonces aus der vorherigen Baum-epoch werden ungültig

Der Operatordienst überprüft außerdem, ob seine lokale SMT-Root mit Instance.withdrawal_transactions_root auf der Chain übereinstimmt, bevor jeder ReleaseFunds- Aufruf erfolgt; eine Abweichung löst einen Sicherheits-Shutdown aus, anstatt einen potenziell ungültigen Nachweis einzureichen.

Die Baumrotation wird durch Instance.current_tree_index: u64 verfolgt, on-chain gespeichert.

Verifizierung in ReleaseFunds

Das sibling_proofs-Argument in ReleaseFunds hat genau die Länge [u8; 512]: 16 Geschwister-Hashes × 32 Bytes jeweils, entsprechend der Baumhöhe von 16.

Der On-Chain-Verifizierungsprozess führt zwei separate Prüfungen nacheinander durch:

verify_smt_exclusion_proof beweist, dass das Nonce-Blatt aktuell leer ist, bezogen auf die aktuelle Instance.withdrawal_transactions_root
verify_smt_inclusion_proof beweist, dass das Nonce-Blatt im vom Aufrufer angegebenen Argument new_withdrawal_root vorhanden ist
Nur wenn beide Prüfungen bestanden sind, speichert das Programm new_withdrawal_root als neue Instance.withdrawal_transactions_root und gibt die Token frei

Schlägt eine der Prüfungen fehl, wird InvalidSmtProof ausgelöst. Die Root-Aktualisierung in Schritt 3 ist atomar mit jedem ReleaseFunds-Aufruf.