kips/kip-0021.md at master · coderofstuff/kips

KIP: 21
Layer: Consensus (hard fork), Chain-Block UTXO Validation
Title: Partitioned Sequencing Commitment with O(activity) Proving
Authors: Michael Sutton <msutton@cs.huji.ac.il>, Maxim Biryukov (@biryukovmaxim), Hans Moog <hans.moog@kaspafoundation.org>
Status: Implemented and activated in TN10
Created: 2026-02-17
Updated: 2026-05-28

Abstract

This KIP replaces the current per-chain-block linear sequencing commitment recurrence with a partitioned sequencing commitment scheme.

Instead of committing to all accepted transactions in every chain block as one global append-only stream, consensus maintains a commitment over the tips of active application lanes (defined in Section 1). Each active lane has its own recursive tip hash and last-touch blue score. Global order remains reconstructible via merge_idx (Section 10.1), but is no longer directly committed as one monolithic per-block list. The block header continues to expose a single accepted_id_merkle_root value (consumed by OpChainblockSeqCommit), but post-activation it commits to (i) the active-lanes sparse Merkle tree (SMT) root and (ii) per-block context and mergeset miner payloads, chained through selected-parent recursion.

The primary goal is prover cost proportional to relevant lane activity (O(activity)) for zk proving systems that consume chain-block sequencing commitments as anchors, while preserving global anchoring and enabling bounded-memory eviction of inactive lanes. In addition, SeqStateRoot(B) commits block-level context needed by based zk systems (selected-parent timestamp, DAA score, and blue score) and mergeset miner payloads, under the same chained commitment, and touched lane-tip updates include the same context hash.

Motivation

ZK provers for application-level state machines, based computation lanes, and other “app-local” systems often need to prove statements that are naturally scoped to a single application lane.

Under the current linear per-block recurrence, proving correctness for lane-specific execution can require processing or committing to global activity in every block, even if a prover only cares about one lane. This creates prover cost proportional to global throughput.

By committing to lane tips (and lane-local block activity digests) rather than to the entire global stream, this KIP makes lane proofs proportional to lane activity, enabling O(activity)-style proving.

This scheme does not assume a fixed bound on historical lane-ID diversity. The committed active set is bounded by recent admitted lane activity within the activity window F, and F is strictly less than pruning depth. Therefore, node storage is not increased asymptotically: the “hot” commitment set scales with recent activity, not with historical diversity of lane IDs.

Goals

Keep a single 32-byte header commitment consumable by OpChainblockSeqCommit.
Make per-lane proving scale with that lane’s own activity.
Enable bounded-memory behavior via inactivity purge keyed by blue score.
Define a deterministic selected-parent state transition whose committed result is stable under DAG reorg processing.
Commit additional block context and mergeset miner payloads needed by based zk systems under the same chained commitment.
Keep pre-activation behavior unchanged.

Requirements:

Remain forward-compatible with future vProg-based lanes and richer lane-local update rules without replacing the core recurrence.

Document Scope

This KIP is the consensus specification for KIP-21. It defines the post-activation state transition, committed values, header semantics, and pruning-point bootstrap requirements.

Detailed implementation and proving guidance is split into companion documents:

Implementation Spec: rusty-kaspa implementation structure, versioned SMT state, pruning mechanics, and IBD import/export details.
Seqcommit Accessor: OpChainblockSeqCommit, selected-parent point of view, depth thresholds, reorg handling, and headers-proof interaction.
Proving Spec: lane proofs, inactivity proofs, guest algorithms, and witness formats.

Sections explicitly marked (Informative) explain rationale or intended use and do not add consensus rules.

Mental Model (Reader Map)

The shortest way to think about the construction is:

start from the accepted transaction sequence AcceptedTxList(B) (selected-parent coinbase first);
extract lane IDs (lane_id) from transactions;
group transactions by lane;
compute one activity_digest_lane(B, lane_id) per touched lane, with merge_idx committed per tx;
update each touched lane tip recursively (existing lane uses previous lane tip; re-appearing lane after purge anchors to SeqCommit(parent(B)));
commit updated active-lane entries in the active-lanes SMT to get ActiveLanesRoot(B);
compute block context hash (selected-parent timestamp, daa_score, blue_score) and miner-payload root;
combine these into SeqStateRoot(B);
chain through selected parent to get SeqCommit(B);
publish SeqCommit(B) in accepted_id_merkle_root.

This yields one header commitment for consensus, while preserving lane-local witnesses for O(activity) proving between anchors.

The following diagram illustrates the underlying proving scheme:

Selected-parent SeqCommit chain (global, deep):

  SeqCommit(B0) -> SeqCommit(B1) -> SeqCommit(B2) -> SeqCommit(B3) -> ... -> SeqCommit(BN)
       |               |               |               |                               |
       v               v               v               v                               v
   ActiveLanes0    ActiveLanes1    ActiveLanes2    ActiveLanes3                   ActiveLanesN

For one target lane `L`, proofs only touch the two anchors and lane-local transition:

  anchor start                                                      anchor end
      |                                                                 |
      v                                                                 v
  include lane_key(L) under ActiveLanes0                    include lane_key(L) under ActiveLanesN
      |                                                                 ^
      |                                                                 |
      +------------ compressed lane-local tip transition ---------------+
                   lane_tip(L, B0)  =>  ... lane activity ...  =>  lane_tip(L, BN)

Interpretation:

The global chain remains linear and deep.
Lane proving uses two global anchors plus a lane-local compressed transition.
Proof size tracks lane activity between anchors, rather than all intermediate chain blocks.

Specification

This specification is written in two passes so readers can first follow the state transition mechanics and then see exactly how that state is committed in the header:

Active lane management: how lane tips are updated and purged as a function of accepted transactions.
What the header commits to: how we commit those tips (and additional context) into SeqCommit(B).

1. Terminology

Lane (lane): an ordered subset of AcceptedTxList(B) identified by a lane ID. In this KIP, the lane ID is tx.subnetwork_id, so each lane contains exactly the accepted transactions with the same subnetwork_id, in their AcceptedTxList(B) order. Future KIPs may define additional lane families such as vProg-based lanes.
Lane Tip: the current recursive hash tip for one lane.
Active Lane: a lane whose lane tip is currently present in the commitment set.
Last-Touch Blue Score: blue score of the chain block that last updated the lane tip.
Active Lanes Root (ActiveLanesRoot(B)): the sparse-Merkle root committing to the active lane tips at chain block B (Section 6.3).
Sequencing State Root (SeqStateRoot(B)): commits to the active-lanes root and additional context/miner-payload data at chain block B (Section 6.6). This is distinct from the UTXO commitment (utxo_commitment).
Sequencing Commitment (SeqCommit(B)): the value stored in B.header.accepted_id_merkle_root post-activation (Section 6.7).
Mergeset Index (merge_idx): the 0-based index of a transaction within AcceptedTxList(B) (Section 4.2).
Accepting Block (B): the chain block whose SeqCommit(B) is being computed.
Mergeset Miner Payload: raw coinbase payload bytes from mergeset blocks, committed by this KIP (Section 6.5.2).

2. Lane Extraction

For this KIP, lanes are extracted from accepted transactions as follows:

For each accepted transaction tx, lane_id(tx) = tx.subnetwork_id.
This includes the selected-parent coinbase transaction, which uses the dedicated coinbase subnetwork ID.
This KIP does not merge system lanes into a single SYS lane; each valid subnetwork ID maps to its own lane.

This keeps the mechanism consensus-native and deterministic with current transaction structure. Future KIPs may define additional lane families and lane-local update rules (e.g., vProg-based CD commitments), while reusing the same outer commitment machinery.

2.1 Canonical Lane ID Encoding (Normative)

In this KIP, lane_id denotes the transaction subnetwork_id.

It is a 20-byte value.

Post-activation, valid transaction subnetwork IDs are:

Native: 0x00 || 0x00..0x00 (one zero byte followed by 19 zero bytes).
Coinbase: 0x01 || 0x00..0x00 (one byte 0x01 followed by 19 zero bytes).
User lane: namespace || 0x00..0x00, where namespace is 4 bytes, the suffix is 16 zero bytes, and at least one byte in namespace[1..=3] is non-zero.

Equivalently, the only valid 19-zero-suffix IDs are native and coinbase. Other IDs of the form x || 0x00..0x00 are reserved for future system use and are invalid as transaction subnetwork IDs. Any shape other than the three valid forms listed above is invalid.

Rationale for keying:

The committed SMT key is lane_key(lane_id) = H_lane_key(lane_id) (Section 6.1).
Hashing lane_id produces the fixed-width 256-bit key used by the active-lanes SMT.
This also keeps lane-ID encoding decoupled from SMT keyspace layout and leaves room for future composite lane IDs, including vProg-derived lane identifiers.

2.2 Block Lane and Gas Limits (Normative)

For block admission, consensus applies the following lane limits to non-coinbase transactions:

A block may contain transactions from at most 50 distinct non-coinbase lanes.
For each non-coinbase lane, the sum of tx.gas over all transactions in that lane may not exceed 1_000_000_000.
Native and reserved system lanes must use tx.gas = 0.

The per-block lane cap bounds local SMT update work. At 10 BPS, the default limit of 50 non-coinbase lanes per block bounds worst-case user-lane updates to 500 per second. Its motivation is local compute and incremental state cost, not the asymptotic boundedness of the active set, which follows from the activity window F and inactivity purge.

The selected-parent coinbase transaction is included in AcceptedTxList(B) and therefore participates in SeqCommit(B), but it is not counted toward the block lane/gas admission limits above.

3. Data Model

Consensus maintains a per-block state S(B) derived from S(parent(B)):

S(B) = {
  ActiveLanes: map lane_id -> (lane_tip_hash, last_touch_blue_score)
}

Only lanes that are currently “active” (not purged) appear in ActiveLanes.

4. Hashing and Encodings

This section defines byte-level hashing and encoding rules used by per-lane activity and tip updates.

4.0 Encoding and Hash Domain Definitions

All hash functions in this KIP are BLAKE3 with explicit domain separation tags.

Keyed-hash notation:

H_tag(m) = BLAKE3(key = tag, input = m)

Domain tags:

Symbol	Domain tag
`H_lane_key`	`"SeqCommitLaneKey"`
`H_lane_tip`	`"SeqCommitLaneTip"`
`H_activity_leaf`	`"SeqCommitActivityLeaf"`
`H_mergeset_context`	`"SeqCommitMergesetContext"`
`H_payload_digest`	`"PayloadDigest"`
`H_miner_payload_leaf`	`"SeqCommitMinerPayloadLeaf"`
`H_activity_root`	`"SeqCommitActivityRoot"`
`H_leaf`	`"SeqCommitActiveLeaf"`
`H_node`	`"SeqCommitActiveNode"`
`H_collapsed`	`"SeqCommitActiveCollapsedNode"`
`H_seq`	`"SeqCommitmentMerkleBranchHash"`

H_seq is the same branch hasher domain separator used by the currently deployed post-covenants sequencing commitment path (SeqCommitmentMerkleBranchHash). This KIP formalizes that behavior and extends it with lane/state commitments.

For convenience, H_seq(x, y) means H_seq(x || y) where x and y are 32-byte values.

4.1 Primitive Encodings

Primitive encodings:

le_u{32,64}(x): fixed-width little-endian encoding.
var_bytes(b): le_u64(len(b)) || b.
blue_work_bytes(work): big-endian bytes of work with leading zero bytes removed (empty byte-string for work = 0).
blue_work_encoding(work): var_bytes(blue_work_bytes(work)).

blue_work_encoding matches the consensus hashing semantics used by rusty-kaspa header hashing (write_blue_work).

4.2 Per-Lane Block Activity Digest

Intuition: This section defines what happened for the lane identified by lane_id in block B as a single hash. We do this by committing to (i) the transaction ID and version and (ii) a block-local index (merge_idx) which lets upper layers reconstruct global order when needed.

Let AcceptedTxList(B) be the ordered list of all accepted transactions in chain block B, in canonical acceptance order. The sequence starts with the selected-parent coinbase transaction, followed by accepted non-coinbase transactions in consensus order.

For each tx in AcceptedTxList(B), define its mergeset index:

Definition:

merge_idx(tx) = position of tx in AcceptedTxList(B)   // 0..len-1

For a lane identifier lane_id, define LaneTxList(B, lane_id) to be the list of all accepted transactions in B whose lane ID is lane_id, in the same relative order they appear in AcceptedTxList(B).

Define the per-lane activity leaf for each transaction:

activity_leaf(tx) =
    H_activity_leaf(
        tx.id
        || le_u16(tx.version)
        || le_u32(merge_idx(tx))
    )

Define the per-lane activity digest as a Merkle root over the leaf list:

activity_digest_lane(B, lane_id) = MerkleRoot([activity_leaf(tx) for tx in LaneTxList(B, lane_id)])

Merkle-root semantics match the sequencing commitment Merkle-root behavior specified by this KIP:

Empty list root is ZERO_HASH (32 zero bytes).
Single entry root is the entry itself.
Internal nodes are H_seq(left, right).

4.3 Tip Update Hash

For a lane identifier lane_id in accepting block B, define a recursive update step:

TipUpdateHash(parent_ref, lane_key, activity_digest, MergesetContextHash(B)) =
    H_lane_tip(parent_ref || lane_key || activity_digest || MergesetContextHash(B))

Local lane-tip hash structure:

lane_tip_hash
└── H_lane_tip
    ├── parent_ref
    ├── lane_key = H_lane_key(lane_id)
    ├── activity_digest = activity_digest_lane(B, lane_id)
    └── context_hash = MergesetContextHash(B)

where:

parent_ref is either the previous lane tip hash (if lane is already active) or a global anchor (Section 5.2).
lane_key is the sparse-Merkle key defined in Section 6.1.
activity_digest is activity_digest_lane(B, lane_id).
MergesetContextHash(B) is defined in Section 6.5.1.

5. Per-Block State Transition

This section defines the deterministic state transition from S(parent(B)) to S(B). Conceptually, only two things can change at block B: touched lanes are updated, and stale lanes are purged.

Let S_prev = S(parent(B)).

5.1 Group Activity by Lane

Define the set of touched lanes in block B:

TouchedLanes(B) = { lane_id | exists tx in AcceptedTxList(B) with lane_id(tx) = lane_id }

For each lane_id in TouchedLanes(B), compute activity_digest_lane(B, lane_id) as in Section 4.2.

5.2 Update or Initialize Lane Tips

Before iterating touched lanes, compute:

ctx_hash_B = MergesetContextHash(B)

For each lane_id in TouchedLanes(B):

Compute activity_digest_lane(B, lane_id).
If lane_id exists in S_prev.ActiveLanes:
- parent_ref = S_prev.ActiveLanes[lane_id].lane_tip_hash
Else:
- parent_ref = SeqCommit(parent(B))
Compute lk = lane_key(lane_id).
Compute tip_next = TipUpdateHash(parent_ref, lk, activity_digest_lane(B, lane_id), ctx_hash_B).
Set:
- ActiveLanes[lane_id].lane_tip_hash = tip_next
- ActiveLanes[lane_id].last_touch_blue_score = B.blue_score

This gives:

continuity for already-active lanes,
and global anchoring for lanes re-appearing after inactivity purge.

Rationale: a lane that has been purged has no committed tip in the active-set root. Anchoring a re-appearing lane to SeqCommit(parent(B)) re-attaches it to a globally committed point without requiring retention of inactive lane tips. Reactivation proving with non-inclusion checkpoints is described in Section 10.3.

5.3 Inactivity Purge

To allow bounded memory, lanes are purged after a fixed inactivity threshold.

Let F be a protocol parameter measured in blue score units.

A lane identified by lane_id is purged at block B if:

ActiveLanes[lane_id].last_touch_blue_score + F <= B.blue_score

Purged lanes are removed from ActiveLanes.

5.4 Inactivity Shortcut

Let F be the same inactivity threshold used for lane purge.

For each chain block B, define InactivityShortcutBlock(B) as follows:

If B.blue_score < F + 1, then InactivityShortcutBlock(B) = genesis.
Otherwise, let target = B.blue_score - F - 1. InactivityShortcutBlock(B) is the highest selected-parent-chain ancestor A of B such that A.blue_score <= target.

The committed shortcut value is:

InactivityShortcut(B) =
    ZERO_HASH                                  if InactivityShortcutBlock(B) is pre-activation
    SeqCommit(InactivityShortcutBlock(B))      otherwise

Note: SeqCommit(genesis) is defined as ZERO_HASH.

The shortcut points to the last selected-parent-chain block not covered by an exclusion proof at B: if a lane is absent from ActiveLanesRoot(B), then by the purge rule it had no activity in the blocks after InactivityShortcutBlock(B) up to B. An inactivity proof can therefore hop from B to InactivityShortcutBlock(B) as its next proving target.

This lets guests walk inactivity spans in O(N/F) hops instead of O(N), without knowing F.

The shortcut is committed next to ActiveLanesRoot(B) inside ActivityRoot(B) (Section 6.6).

6. Commitment Structure

This section defines how state is projected into the single header commitment. The structure is intentionally layered: active-lanes state first, then per-block context/miner payloads, then selected-parent chaining.

At a high level:

Commit the active lanes map into ActiveLanesRoot(B) via an SMT.
Combine ActiveLanesRoot(B) with the inactivity shortcut into ActivityRoot(B).
Commit additional per-block context and miner payload data into PayloadAndContextDigest(B).
Hash these together into SeqStateRoot(B).
Chain the state root through selected-parent ancestry into SeqCommit(B).

The resulting tree shape is:

SeqCommit(B)
└── H_seq
    ├── parent_seq_commit = SeqCommit(selected_parent(B))
    └── state_root
        └── H_seq
            ├── activity_root
            │   └── H_activity_root
            │       ├── inactivity_shortcut
            │       └── lanes_root
            │           └── SMT root over active lane entries 1..N
            │               ├── ...
            │               ├── entry_i = leaf_hash_i as defined in Section 6.2
            │               └── ...
            │
            └── payload_and_ctx_digest
                └── H_seq
                    ├── context_hash
                    └── payload_root

6.1 Keying

Define the sparse-Merkle key for a lane identifier lane_id:

lane_key(lane_id) = H_lane_key(lane_id)    // 32-byte key

where lane_id is the lane identifier (Section 2.1).

6.2 Leaf Value

Leaf payload for a lane identifier lane_id:

leaf_payload(lane_id) =
    lane_tip_hash
    || le_u64(last_touch_blue_score)

where:

lane_id is the lane identifier (Section 2.1).
lane_tip_hash and last_touch_blue_score are taken from ActiveLanes[lane_id].

Leaf hash:

leaf_hash(lane_id) = H_leaf(leaf_payload(lane_id))

6.3 Root

The sparse Merkle root over all active leaves is the active lanes root:

ActiveLanesRoot(B) = SMT_Root({ lane_key(lane_id) -> leaf_hash(lane_id) | lane_id in ActiveLanes })

6.4 Sparse Merkle Tree Definition (Normative)

This KIP defines SMT_Root as a 256-bit sparse Merkle map with collapsed single-leaf subtrees.

Keys are 256-bit strings (lane_key), interpreted MSB-first as a path. Empty subtree hashes are defined by:

EMPTY_0 = ZERO_HASH

and:

EMPTY_{i+1} = H_node(EMPTY_i || EMPTY_i)

Let SubRoot(d, M) be the root of the subtree at bit depth d, where M is the set of active entries whose keys share that subtree prefix.

If M is empty:
```
SubRoot(d, M) = EMPTY_{256-d}
```

If M contains exactly one entry key -> leaf_hash:

SubRoot(d, M) = H_collapsed(key || leaf_hash)

Otherwise, split M by bit d of key into M_left and M_right:

SubRoot(d, M) = H_node(SubRoot(d+1, M_left) || SubRoot(d+1, M_right))

Then:

SMT_Root(M) = SubRoot(0, M)

The collapsed case is part of the consensus root semantics, not only a storage optimization. It avoids committing a chain of empty siblings below a subtree that contains a single active lane, while the full 256-bit key remains committed inside H_collapsed.

Rationale: lane_key values are hashes, so active lane keys are expected to branch like uniformly distributed 256-bit strings. Long shared-prefix collisions are therefore rare, and deliberately constructing them is bounded by the difficulty of finding suitable H_lane_key preimages. The subnetwork ID rules further restrict that preimage space. In normal operation, collapsed single-leaf subtrees make inclusion/exclusion witnesses scale with the branching depth of the actual active set, effectively O(log n), and make the tree representation scale as O(n log n), where n is the number of active entries. Without collapsed single-leaf subtrees, the corresponding factors are tied to the fixed 256-bit key depth.

6.5 Additional Committed Data (Normative)

This KIP additionally commits (i) accepting-block header context and (ii) miner payloads from all mergeset blocks.

6.5.1 Accepting Block Context Commitment

Upper layers often need a verifiable "clock" and height-like indices relative to SeqCommit(B).

Define:

MergesetContextHash(B) =
    H_mergeset_context(
        le_u64(selected_parent(B).header.timestamp)
        || le_u64(B.header.daa_score)
        || le_u64(B.blue_score)
    )

MergesetContextHash(B) commits the selected-parent timestamp, accepting-block DAA score, and accepting-block blue score. It is committed both as part of SeqStateRoot(B) and inside each touched lane-tip update in B.

Rationale: the accepting block timestamp is not yet available when building a deterministic block template, while the selected-parent timestamp is already fixed from the template's point of view. At Kaspa's high BPS rate, the timestamp difference from the selected parent is normally sub-second.

Note: Kaspa timestamps are not strictly monotonic along the selected-parent chain. Applications that need monotonic time should enforce that rule at their own layer.

6.5.2 Miner Payload Commitment (Mergeset Blocks)

To support based zk systems, this KIP commits raw coinbase payload bytes from all mergeset blocks of the accepting block B, including blocks whose coinbase transactions are not accepted.

Rationale:

Non-selected-parent coinbase transactions are not accepted into AcceptedTxList(B), but their coinbase payloads still carry consensus-relevant data: the accepting block's reward construction uses mergeset coinbase payload fields (e.g., payout destination data).
In practice, coinbase payloads are also the conventional place where miners signal extra metadata (e.g., software/pool identity), so these payload bytes can be relevant for L2 applications.
Therefore, this KIP commits these payload bytes via a dedicated block-level path, rather than through accepted-transaction sequencing.
Each committed payload is bound to block identity (X.hash) and blue_work to provide secure topological metadata.

For each mergeset block X:

Let payload_bytes(X) be the raw payload bytes of the coinbase transaction of X.

For each mergeset block X, define:

miner_payload_hash(X) = H_payload_digest(payload_bytes(X))

miner_payload_leaf(X) = H_miner_payload_leaf(
    X.hash
    || blue_work_encoding(X.header.blue_work)
    || miner_payload_hash(X)
)

Let MinerPayloadLeaves(B) be the list of miner_payload_leaf(X) over all included mergeset blocks X, ordered by the deterministic mergeset traversal order used by consensus (selected parent first, then the remaining mergeset blocks in consensus topological order).

Define:

MinerPayloadRoot(B) = MerkleRoot(MinerPayloadLeaves(B))

Merkle-root branching uses H_seq semantics (Section 4.2).

6.6 Sequencing State Root (Normative)

Define:

$$ \mathrm{ActivityRoot}(B) = H_{\mathrm{activity_root}}\big( \mathrm{InactivityShortcut}(B), \mathrm{ActiveLanesRoot}(B) \big). $$

$$ \mathrm{PayloadAndContextDigest}(B) = H_{\mathrm{seq}}\big(\mathrm{MergesetContextHash}(B), \mathrm{MinerPayloadRoot}(B)\big). $$

$$ \mathrm{SeqStateRoot}(B) = H_{\mathrm{seq}}\Big( \mathrm{ActivityRoot}(B), \mathrm{PayloadAndContextDigest}(B) \Big). $$

Notes:

ActiveLanesRoot(B) is committed inside ActivityRoot(B) together with InactivityShortcut(B).
InactivityShortcut(B) is defined in Section 5.4.
MergesetContextHash(B) and MinerPayloadRoot(B) are committed inside PayloadAndContextDigest(B).

6.7 Sequencing Commitment Recurrence (Normative)

Define:

$$ \mathrm{SeqCommit}(B) = H_{\mathrm{seq}}\big(\mathrm{SeqCommit}(\mathrm{parent}(B)), \mathrm{SeqStateRoot}(B)\big). $$

where parent(B) is B's selected parent.

Notes:

SeqCommit(B) is chained through selected-parent ancestry (KIP-15 style recurrence).
SeqStateRoot(B) is not directly exposed in the header; it is committed by SeqCommit(B).
ActiveLanesRoot(B) is not directly exposed in the header; it is committed through ActivityRoot(B), SeqStateRoot(B), and SeqCommit(B).

Post-activation, consensus sets:

B.header.accepted_id_merkle_root = SeqCommit(B)

7. Script Semantics

OpChainblockSeqCommit (aka OpChainBlockHistoryRoot in [4, 5]) returns the 32-byte commitment value stored in the header field accepted_id_merkle_root of a chain block, subject to existing chain-ancestor and depth checks.

This KIP defines post-activation accepted_id_merkle_root semantics for OpChainblockSeqCommit.

8. Consensus State Maintenance

Implementations must maintain enough sequencing-commitment state to deterministically compute SeqCommit(B) from SeqCommit(parent(B)), the active lane set at parent(B), and block B's accepted transaction and mergeset data.

Implementations must also support selected-parent reorgs without changing the resulting committed state. The concrete diff, cache, index, and storage layout are implementation details and are not part of this KIP. The rusty-kaspa implementation strategy is described separately in Implementation Spec.

9. Pruning-Point Bootstrap Requirements (Normative)

IBD from the pruning point (PP) must provide enough sequencing-commitment state for a new node to continue normal chain-block processing from PP onward.

At PP, a node must have (or reconstruct) the following minimum data:

Full active-lane state at PP, sufficient to reconstruct ActiveLanesRoot(PP) in full. For each active entry this includes the SMT key, lane tip hash, and last-touch blue score.
A selected-parent-chain header segment ending at PP and extending far enough below PP to include InactivityShortcutBlock(PP).
PayloadAndContextDigest(PP), or MergesetContextHash(PP) and MinerPayloadRoot(PP) from which to recompute it.
SeqCommit(parent(PP)) (equivalently, PP selected-parent accepted_id_merkle_root).

The header segment is required not only to verify InactivityShortcut(PP), but also to derive shortcut values for chain blocks processed immediately after PP, until locally processed blocks are deep enough to supply the shortcut path without relying on the imported boundary segment. This coincides with the selected-parent-chain header segment required for OpChainblockSeqCommit access around the pruning-point boundary; that accessor-specific requirement is specified in Seqcommit Accessor.

Using the header segment, the node derives InactivityShortcutBlock(PP) by Section 5.4 and resolves InactivityShortcut(PP). The data above are then sufficient to verify:

ActivityRoot(PP) =
    H_activity_root(InactivityShortcut(PP), ActiveLanesRoot(PP))

SeqStateRoot(PP) =
    H_seq(ActivityRoot(PP), PayloadAndContextDigest(PP))

PP.accepted_id_merkle_root =
    H_seq(SeqCommit(parent(PP)), SeqStateRoot(PP))

From that verified PP state, a node processes subsequent chain blocks by the same consensus state-transition rules in Sections 5-8.

Operational note: concrete retention, reconstruction, and wire-format choices are implementation details. They are described separately in Implementation Spec.

Informative: Proving and Witness Operations

This section gives high-level proving intuition. Detailed guest algorithms, witness formats, and witness-serving strategies are outside the consensus rules and are described separately in Proving Spec.

10. Complexity

Let:

$n = |AcceptedTxList(B)|$
$t = |TouchedLanes(B)|$
$p =$ number of purged lanes at $B$
$a = |ActiveLanes(B)|$

Then:

Grouping activity by lane is $O(n)$.
Updating lane tips is $O(t)$.
Purging $p$ inactive lanes removes $p$ entries from the active-lanes map; concrete discovery and indexing strategies are implementation-specific.
Active-lanes SMT updates and witnesses are capped by the 256-bit key depth, but under the collapsed single-leaf structure and hash-distributed lane keys, their effective size is governed by the branching depth of the active set, typically $O(\log a)$ per changed lane.

10.1 Global Order Reconstruction

If an upper layer needs global order reconstruction, it can reconstruct it by collecting the per-lane transaction sets and sorting by $\mathrm{merge\_idx}$ within the accepting block $B$. Verifying this reconstruction requires lane witnesses under the committed $SeqCommit(B)$ anchor and proving the relevant active-lanes SMT diff, or an equivalent witness relation, between anchors. Concrete witness strategies are outside this consensus document and are described separately in Proving Spec.

10.2 Two-Anchor Lane Proof Model

For lane-local proving, the intended model is:

provide two global anchors: $SeqCommit(B_{start})$ and $SeqCommit(B_{end})$;
provide lane-inclusion witnesses for lane $\ell$ under both anchors (via $ActiveLanesRoot$ / $SeqStateRoot$);
provide a compressed lane-diff witness from $\mathrm{lane\_tip}(\ell, B_{\text{start}})$ to $\mathrm{lane\_tip}(\ell, B_{\text{end}})$.

The lane-diff witness size is proportional to lane activity between anchors, so this path is $O(a)$ rather than $O(\Delta B)$, where $a$ is app activity and $\Delta B$ is the number of chain blocks between anchors.

Including $MergesetContextHash(B)$ in touched lane-tip updates makes the selected-parent timestamp and accepting-block scores available on the lane-local path without forcing per-block global sequencing commitment processing.

Miner payloads remain a block-level commitment ( $MinerPayloadRoot(B)$ ). Apps that rely on this data still track block-level witnesses across intermediate chain blocks.

10.3 Reactivated Lane Proof Pattern

For a lane that was purged and later re-appears, proving continuity typically needs both lane inclusion and lane non-inclusion witnesses:

inclusion at the old anchor for the last pre-purge lane tip;
non-inclusion checkpoints for $\mathrm{lane\_key}(\ell)$ under $ActiveLanesRoot$ while iterating the selected-parent $SeqCommit$ chain, with at least one checkpoint per $F$ blue-score window;
inclusion at/after reactivation for the new lane tip anchored by $SeqCommit(parent(B_{reactivate}))$.

Each non-inclusion checkpoint at blue score $s$ certifies inactivity for the preceding $F$-window ($[s-F, s]$) by the purge rule, so exclusion proofs do not need to be repeated inside that covered segment.

This checkpoint pattern shows that no committed intermediate lane tip for $\ell$ exists between the old tip and the reactivation event.

Future Compatibility with vProgs CD

This KIP is designed to remain compatible with a future full vProgs CD specification.

Expected direction:

A vProg can be modeled as a lane under this KIP, just as subnets are modeled as lanes today.
In that setting, the active-lanes SMT committed under ActivityRoot(B) inside SeqCommit(B) already serves as the global live-vProg tree described in the vProgs DAG-root model (see [3]).
A vProg lane tip would recurse from its previous anchor together with the newly introduced CD tips belonging to that vProg in the accepting block: concretely, the latest unproven account-state vertices written to by that vProg's transactions in the current mergeset.
Thus this KIP already prepares a substantial subset of the vProgs commitment design: the global outer partitioning and anchoring machinery can remain the same, while the lane-local update rule becomes CD-specific.
Subnet-based lanes defined by this KIP remain unchanged, so zk provers built over the current subnet-lane logic can continue to operate as-is after a CD upgrade.
A full CD model may also allow re-anchoring to a previously proven vProg/account commitment, instead of always falling back to SeqCommit(parent(B)) when state is absent from the active set.

This section is informative only; it does not change the normative subnet-lane rules specified above.

Relationship to Covenants++ Workstream

This KIP is a standalone consensus specification for partitioned sequencing commitments.

Within the Covenants++ workstream, it complements KIP-16, KIP-17, and KIP-20. TN12 (the experimental testnet for Covenants++) already includes those KIPs and OpChainblockSeqCommit (earlier named OpChainBlockHistoryRoot, see [4, 5]). This KIP specifies the commitment semantics consumed by that opcode.

Backward Compatibility

This KIP is a consensus-changing hard fork: post-activation blocks are not consensus-compatible with nodes that do not implement these rules.
Post-activation, accepted_id_merkle_root follows SeqCommit(B) as defined here, and OpChainblockSeqCommit consumes this commitment path.

Why SMT

The active-lanes commitment is a sparse authenticated map from lane_key(lane_id) to active-lane leaf hash. The map is sparse because only recently active lanes are present, while keys live in a 256-bit hash-derived space.

SMT is chosen because it gives deterministic bitwise keying over fixed hash-derived keys and simple inclusion/exclusion relations. Patricia-style tries would also be possible, but they compress shared internal paths, which significantly complicates the committed structure and implementation.

The collapsed single-leaf rule in Section 6.4 keeps the easy and most relevant part of that optimization: when a subtree contains only one active key, the subtree commits directly to that key and leaf hash instead of carrying empty siblings down to depth 256. Since lane keys are hash-distributed and the subnetwork rules restrict the preimage space, this gives the same practical witness-size benefit expected from Patricia-style compression for normal active sets, while avoiding compressed interim shared paths. Under the usual random-oracle intuition for the key bits, where n = |ActiveLanes|, the relevant shared-prefix length is governed by n, so witnesses normally contain O(log n) non-empty branching hashes rather than one hash per key bit; see [6].

References

[1] KIP-15: Canonical Transaction Ordering and Sequencing Commitments.
[2] Subnets sequencing commitments (original seed to this design): https://research.kas.pa/t/subnets-sequencing-commitments/274
[3] vProgs yellow paper: https://github.com/kaspanet/research/blob/main/vProgs/vProgs_yellow_paper.pdf
[4] On the design of based zk-rollups over Kaspa's UTXO-based DAG consensus: https://research.kas.pa/t/on-the-design-of-based-zk-rollups-over-kaspas-utxo-based-dag-consensus/208
[5] L1/L2 canonical bridge entry/exit mechanism: https://research.kas.pa/t/l1-l2-canonical-bridge-entry-exit-mechanism/258
[6] Optimizing Sparse Merkle Trees: https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751

FilesExpand file tree

kip-0021.md

Latest commit

History

kip-0021.md

File metadata and controls

Abstract

Motivation

Goals

Document Scope

Mental Model (Reader Map)

Specification

1. Terminology

2. Lane Extraction

2.1 Canonical Lane ID Encoding (Normative)

2.2 Block Lane and Gas Limits (Normative)

3. Data Model

4. Hashing and Encodings

4.0 Encoding and Hash Domain Definitions

4.1 Primitive Encodings

4.2 Per-Lane Block Activity Digest

4.3 Tip Update Hash

5. Per-Block State Transition

5.1 Group Activity by Lane

5.2 Update or Initialize Lane Tips

5.3 Inactivity Purge

5.4 Inactivity Shortcut

6. Commitment Structure

6.1 Keying

6.2 Leaf Value

6.3 Root

6.4 Sparse Merkle Tree Definition (Normative)

6.5 Additional Committed Data (Normative)

6.5.1 Accepting Block Context Commitment

6.5.2 Miner Payload Commitment (Mergeset Blocks)

6.6 Sequencing State Root (Normative)

6.7 Sequencing Commitment Recurrence (Normative)

7. Script Semantics

8. Consensus State Maintenance

9. Pruning-Point Bootstrap Requirements (Normative)

Informative: Proving and Witness Operations

10. Complexity

10.1 Global Order Reconstruction

10.2 Two-Anchor Lane Proof Model

10.3 Reactivated Lane Proof Pattern

Future Compatibility with vProgs CD

Relationship to Covenants++ Workstream

Backward Compatibility

Why SMT

References