Pruning safety in the vProgs architecture

L1/L2
1

For simplicity, below I assume L1 has full access to the Computation Dag structure, and can calculate the corresponding scopes of all VProgs. I will not concern myself much with how this is done. This assumption might eventually be relaxed using an enshrined L2, or just pushing the issue to each L2 individually.

Pruning in Kaspa consists of throwing away transaction data. If a transaction scope requires executing transaction data from below the pruning point, it could fail or succeed depending on the real time performance of the node, and it is clear such a transaction should not be allowed. I will argue below that the effects of disallowing this on the functionality are non crucial:

For a potential transaction x, let W_x denote the set of vertices created by x, let F_x denote the set of witnesses provided to the Prog_v, and let P_x denote all the paths from W_x to a vertex in F_x. Finally, let Y denote the set of vertices which are currently proven.

Observation: let C\subseteq Y be a covering of all paths in P_x. Then there is an equivalent transaction x’ creating the same set of vertices W_x, which provides the witnesses C instead, and introduces a scope of computation contained in the one originally introduced in X.

Remark: there is no guarantee that the number of witnesses (i.e. the size of C) provided by x’ will be smaller than in x, and it in fact can be bigger. As a sidenote, it may be beneficial on general to determine heuristics to find a set which does reasonably well for both the “width” of the cut and the scope size.

The above observation implies that in order to obtain the same functionality as a transaction x, one can equivalently provide witnesses for “later” vertices, so that the scope will be contained within the pruning period. This however requires these later vertices to be “proven”, but all this requires is that a recent proof of the corresponding account exists up to this pruning period. It is a reasonable requirement to expect that VProgs aiming to be composed with recent proofs, will provide proofs within the latest pruning period. It is remarked that under our design, a prover can always prove old data even after an extended period of inactivity (see On the design of based ZK rollups over Kaspa's UTXO-based DAG consensus)

Correspondingly, the data of a vertex in the computation Dag lying below the pruning point can be discarded. Pruning of the Dag structure is ignored for now, but as an afterthought we could prune it as well and only store membership proofs of its pre-pruned structure.

Discarding long-proven account data

While the above limits the number of vertices data need to be stored, storing intermediary states for the entire pruning period remains a big load. For this reason we should also introduce regular pruning of vertices lying far below a recent zk proof.
Specifically, extend the definition of a vertex to (a,t,T), with the last entry denoting at which block number the transaction was accepted, i.e. its “round”.
Let then v=(a,t,T) be a vertex, and \pi_a be the latest proof submitted for the account a, then v shouldbe discarded when T<T’-\Delta (\Delta=500 for example) where T’ denotes the “round” of the latest transaction proven by \pi_a.
This scheme is logical because:

a) The more time surpasses following it, the less likely it is a vertex will need to be read.
b) if such a vertex absolutely must be read, witnesses for it could still be provided for it via the intermediary states commitment on \pi_a. I.e. the functionality remains possible, but merely requires including witnesses again.

There is a case for including another condition - that if a vertex was recently read, it will not be discarded for \Gamma (=50) rounds. Logic being that sometimes transaction scopes will be rebuilt in parts, hence reerasing them immediately will be detrimental. This however further complicates the objective inferring of a transaction scope.

*The numbers 50, 500 etc. are pure placeholders.

2 Likes
2

In practice, your model turns “old history” into “recent proof obligations.” Any transaction that would otherwise fail because its scope dips below the pruning point can succeed by anchoring its logic to a recent zk proof of the account instead. The trade-off is larger proofs/witnesses, but much smaller storage requirements for nodes.

:small_blue_diamond: Example 1: Smart Contract with Old Transaction History

Suppose account A deployed a VProg (like a simple token contract) 10,000 blocks ago.
A new transaction x wants to read some intermediate balance changes that happened 9,500 blocks ago (well below the pruning horizon).

Without your pruning model:

  • Node tries to fetch the old transaction data.
  • If it’s pruned, the scope fails → transaction breaks.

With your pruning model:

  • Instead of reading the ancient balance updates, x can be reformulated as x′.
  • Provide witnesses from a more recent proof of A’s account state (e.g., a zk proof that the balance at block 9,800 already incorporates the old events).
  • Result: The node only needs to check recent proofs (within Δ=500 blocks), not store the whole 10,000-block history.

:small_blue_diamond: Example 2: Batch Payment Program

A VProg batches 1,000 payments into small chunks.
Some of those payments touch states 600 rounds old.
By the Δ=500 rule, those old vertices are discarded.

How it works:

  • Instead of providing witnesses for the ancient payment states, the transaction provides a witness to the account’s latest zk proof (say round 9,950).
  • The computation scope shrinks to the last Δ blocks, and the proof shows that all prior history is “absorbed” into the proven account state.

:small_blue_diamond: Example 3: DeFi Program with Reuse of Scopes

A lending VProg frequently rebuilds transaction scopes (e.g., when users roll over loans).
A scope references a state 400 blocks back.
A zk proof for that account was just refreshed 10 blocks ago.

Your Γ safeguard kicks in:

  • Because that vertex was “recently read,” it isn’t pruned for another Γ=50 rounds.
  • When the loan rollover transaction arrives, it can still reference that intermediate state without being forced to re-supply a long witness.

:small_blue_diamond: Example 4: Cold Account Wakes Up

Account B hasn’t been active in months. Its old vertices are far below pruning.
A new transaction wants to interact with B’s state.

With your model:

  • Transaction provides a zk proof for B’s state at a recent pruning boundary (e.g., “as of block 1,000,000, B had balance 50”).
  • No need to replay months of transactions — just prove membership of that final state.
  • Node discards all of B’s old vertices once Δ is exceeded.

VProg Scope with Pruning: Substitute Recent Proof

vprog_pruning_delta_gamma
vprog_pruning_delta_gamma2000Ă—1200 56.3 KB

Top: Tx depends on pruned old state → breaks. Bottom: Tx uses a recent zk proof inside the pruning window → succeeds.

Δ / Γ Discard Rules for Vertices

vprog_pruning_example
vprog_pruning_example2000Ă—1200 64.9 KB

Top: Discard vertices older than Δ rounds once a new proof exists. Bottom: If a vertex was recently read, preserve it temporarily for Γ rounds.