``` KIP: 21 Layer: Consensus (hard fork), Chain-Block UTXO Validation Title: Partitioned Sequencing Commitment with O(activity) Proving Authors: Michael Sutton , Maxim Biryukov (@biryukovmaxim), Hans Moog 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 1. Keep a single 32-byte header commitment consumable by `OpChainblockSeqCommit`. 2. Make per-lane proving scale with that lane’s own activity. 3. Enable bounded-memory behavior via inactivity purge keyed by blue score. 4. Define a deterministic selected-parent state transition whose committed result is stable under DAG reorg processing. 5. Commit additional block context and mergeset miner payloads needed by based zk systems under the same chained commitment. 6. 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](kip-0021/impl-spec.md): rusty-kaspa implementation structure, versioned SMT state, pruning mechanics, and IBD import/export details. * [Seqcommit Accessor](kip-0021/seqcommit-accessor.md): `OpChainblockSeqCommit`, selected-parent point of view, depth thresholds, reorg handling, and headers-proof interaction. * [Proving Spec](kip-0021/proving-spec.md): 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: 1. start from the accepted transaction sequence `AcceptedTxList(B)` (selected-parent coinbase first); 2. extract lane IDs (`lane_id`) from transactions; 3. group transactions by lane; 4. compute one `activity_digest_lane(B, lane_id)` per touched lane, with `merge_idx` committed per tx; 5. update each touched lane tip recursively (existing lane uses previous lane tip; re-appearing lane after purge anchors to `SeqCommit(parent(B))`); 6. commit updated active-lane entries in the active-lanes SMT to get `ActiveLanesRoot(B)`; 7. compute block context hash (selected-parent `timestamp`, `daa_score`, `blue_score`) and miner-payload root; 8. combine these into `SeqStateRoot(B)`; 9. chain through selected parent to get `SeqCommit(B)`; 10. 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: 1. **Active lane management:** how lane tips are updated and purged as a function of accepted transactions. 2. **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: ```text 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)`: 1. Compute `activity_digest_lane(B, lane_id)`. 2. If `lane_id` exists in `S_prev.ActiveLanes`: * `parent_ref = S_prev.ActiveLanes[lane_id].lane_tip_hash` 3. Else: * `parent_ref = SeqCommit(parent(B))` 4. Compute `lk = lane_key(lane_id)`. 5. Compute `tip_next = TipUpdateHash(parent_ref, lk, activity_digest_lane(B, lane_id), ctx_hash_B)`. 6. 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: 1. Commit the active lanes map into `ActiveLanesRoot(B)` via an SMT. 2. Combine `ActiveLanesRoot(B)` with the inactivity shortcut into `ActivityRoot(B)`. 3. Commit additional per-block context and miner payload data into `PayloadAndContextDigest(B)`. 4. Hash these together into `SeqStateRoot(B)`. 5. Chain the state root through selected-parent ancestry into `SeqCommit(B)`. The resulting tree shape is: ```text 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. 1. If `M` is empty: ``` SubRoot(d, M) = EMPTY_{256-d} ``` 2. If `M` contains exactly one entry `key -> leaf_hash`: ``` SubRoot(d, M) = H_collapsed(key || leaf_hash) ``` 3. 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](kip-0021/impl-spec.md). ### 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](kip-0021/seqcommit-accessor.md). 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](kip-0021/impl-spec.md). ## 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](kip-0021/proving-spec.md). ### 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](kip-0021/proving-spec.md). #### 10.2 Two-Anchor Lane Proof Model For lane-local proving, the intended model is: 1. provide two global anchors: $SeqCommit(B_{start})$ and $SeqCommit(B_{end})$; 2. provide lane-inclusion witnesses for lane $\ell$ under both anchors (via $ActiveLanesRoot$ / $SeqStateRoot$); 3. 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: 1. inclusion at the old anchor for the last pre-purge lane tip; 2. 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; 3. 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](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](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](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](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](https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751)