DEP 0008: Transaction-local state

status: draft

Motivation

In DarkFi, spending a coin requires a Merkle inclusion proof against the global incremental Merkle tree. When a transaction contains multiple calls where one call’s output is spent by a subsequent call, the intermediate coin hasn’t been inserted into the global tree yet. The global tree’s state at verification time depends on block ordering, so the prover and verifier cannot agree on a root.

Proposal

We can build a small, deterministic Merkle tree from the intermediate output commitments produced within the transaction itself. For intra-tx spends, the burn proof demonstrates inclusion in this local tree rather than the global one. Since the transaction defines the order of calls and their outputs, both prover and verifier will always construct the same tree and arrive at the same root.

Construction

Given a transaction with ordered calls [C0, C1, C2]:

• C0 produces output commitments [O0, O1]
• C1 wants to spend O1, so the prover builds a local tree from {O0, O1}
• C1 generates a standard Merkle inclusion proof for O1 in this local tree
• If C1 also produces O2, and C2 wants to spend it, a new local tree is built from {O0, O1, O2} (all outputs preceding C2)

The local tree root becomes the public merkle_root input to the burn proof, replacing the global anchor.

The burn circuit itself remains unchanged. The Merkle path verification logic is identical - the only difference is which root the verifier expects.

We have to add a public mode_flag (0 = global, 1 = local) so the verifier knows which root check to perform. This would be added to the Output struct in the Money contract and the smart contract would then be able to select the correct code path for verification.

Privacy

The Merkle proof hides which leaf is being proven. If the local tree contains multiple leaves, an observer knows “this spend consumed one of the outputs from previous calls” but not which one. If there’s only a single preceding output, the privacy set is 1 and the link is trivially visible, but in that case the transaction structure already reveals it.

Nullifier Handling

Intermediate coins must still emit nullifiers. The verifier checks:

• No two nullifiers within the same transaction collide (prevents intra-tx double spend)
• No nullifier collides with any previously spent nullifier in the global state.

Global Tree Updates

After a transaction is finalized, only the surviving output commitments (those not consumed by an intra-tx spend) need to be inserted into the global Merkle tree. Intermediate coins that were both created and destroyed within the transaction can be omitted from the global tree to save space. The nullifiers still need to be recorded to prevent replay.

Transaction Validity Rules

• A call at index K may only spend outputs from calls at indices 0..K-1. Circular dependencies are impossible by construction.
• Proofs must be generated sequentially: call 0 first (to produce outputs), then call 1 (which may reference those outputs), and so on.
• If any call in the transaction fails verification, the entire transaction is rejected atomically.