Skip to content

kip-0015.md

Latest commit

 

History

History
119 lines (99 loc) · 6.98 KB

kip-0015.md

File metadata and controls

119 lines (99 loc) · 6.98 KB
Raw
KIP: 15
Layer: Consensus (hard fork)
Title: Canonical Transaction Ordering and SelectedParent Accepted Transactions Commitment
Type: Consensus change (block format)
Author: Mike Zak <feanorr@gmail.com>, Ro Ma @reshmem
Comments-URI: https://research.kas.pa/t/kip-15-discussion-thread/303
created: 2025-02-01
updated: 2025-02-23
Status: Active

Motivation

L2 networks on top of Kaspa rely on Kaspa for both consensus and data availability.
In other words, the Kaspa L1 provides the list of accepted transactions and their order, while L2 interprets the transaction payloads and executes corresponding logic. In such cases the ordering of transaction acceptance in L1 has to be the ordering of transaction execution on L2.
As such, the acceptance and ordering of transactions on L1 is of utmost importance to L2 applications.

In addition, a Kaspa node prunes the transaction and header data after c. 52 hours ( 30 hours post-Crescendo ) of their publication. This is made possible by a UTXO-commitment posted in the Kaspa block header, which allows a new client to download the state of the network (it's UTXO set) at some block B from an untrusted source, than validate it against B's UTXO-commitment.

However, general-execution L2 networks can not have a cryptographical commitment easily available on-DAG and verified by the L1 consensus layer.
Creating such a commitment to a general-execution account-model state is a non-trivial problem requiring ZK-proofs. Kaspa has plans for supporting such commitments, posted to the DAG and verified by L1 opcodes, but the specifics of this design are still under discussion, with currently no clear timeline or complete understanding of the solution's properties.

Accepted Transactions Archival Node

As an intermediary solution, as well as in other cases where ZK-proofs are not viable for the L2 for any reason, a new type of archival node might be utilized: This node does not archive the DAG structure or block data, it only archives the accepted transactions' data, as well as their order of acceptance. For the sake of this document, we shall call such a node an Accepted Transactions Archival Node (ATAN).

An ATAN would listen to VirtualSelectedParentChainChanged, noting the RpcAcceptedTransactionIds and extracting the transaction data from the (still un-pruned) block data.
This way it is currently possible to collect and store all data required by the L2 network, assuming the ATAN has been online since the L2 network's launch, with only intermittent downtimes up to the size of the pruning window at a time.

Bootstrapping a new ATAN from an existing, untrusted ATAN would require downloading the transactions data and their ordering, as well as a downloading and validating a cryptographic proof testifying to the above against a commitment commonly available to any pruning Kaspa node.

A naive design could go along the following lines:

1. Download the Selected Parent Chain block headers from tip up to the inception of L2
2. For each block in the Selected Parent Chain bottom-to-top:
   1. Download the list of accepted transactions
   2. Validate it against the block's AcceptedIDMerkleRoot

The above design has two faults:

  1. There is much data in the block headers which is redundant for this process
  2. Currently, AcceptedIDMerkleRoot does not commit to transaction ordering. (See more on this in the following section)

AcceptedIDMerkleRoot sorting

Currently, after collecting all transactions accepted by a block, a Kaspa node sorts these transactions according to their hash before calculating AcceptedIDMerkleRoot.

This was done as an optimization, to facilitate future proofs of exclusion:
A proof of exclusion in a non-sorted merkle tree requires the revelation of all the tree's nodes (O(n)), while a proof of exclusion in a sorted merkle tree only requires the revelation of a single branch within the tree (O(log n)), showing two adjacent nodes, one lesser and one greater than the node we wish to prove its exclusion.

As far as we know, there is currently no application on top of Kaspa using the above feature. Additionally, a proof of exclusion from the mergeset of a specific chain block seems unuseful, while for proving exclusion from a period such as a day you would need a linearly long proof for showing exclusion from each and every chain block. We would also wish to argue that the above optimization is of lesser importance than the ability to prove transaction acceptance order.

Our Proposal

We propose a new block-header field named SequencingCommitment to replace AcceptedIDMerkleRoot.

SequencingCommitment will be calculated as following:

1. **AcceptedIDMerkleRoot** = the root of a tree constructed from the block's AcceptanceData keeping canonical order 
(in other words - the same way AcceptedIDMerkleRoot was calculated up until now, but skipping the order by hash)
2. **SequencingCommitment** = hash(*SelectedParent.SequencingCommitment*, *AcceptedIDMerkleRoot*).

The hashing algorithm that should be used is the same hashing algorithm used throughout Kaspa for merkle trees (currently blake2b).

Accepted Transactions Archival Node Design

Given the above changes in Kaspa, the following design for an ATAN can be proposed: As mentioned above, the node listens to VirtualSelectedParentChainChanged and stores for every chain block B:

  1. B.TxList - The list of transactions accepted by B, in their order of acceptance.
  2. B.SequencingCommitment.

This should be stored starting from some block P, ordered bottom-to-top.
P must be a pruning point, so that any untrusting client that has access to a Kaspa full node will be able to recognize it. P should be chosen as the most recent pruning point for which either all L2 transactions are in P's future, or there is some sort of commitment for the state of L2 in P's future.

Note that the above is enough to provide a list of all Kaspa transactions and their order of acceptance to a trusting client, even if said client has no access to a Kaspa full node.

A synced ATAN X can bootstrap an untrusting ATAN Y, assuming that Y does have access to a Kaspa full node as follows:

1. X sends to Y: P.Hash and P.SequencingCommitment.
2. Y verifies that it recognizes P as a pruning point.
3. For each chain block B from P.SelectedChild up to Tip:
   1. X sends to Y: B.TxList and B.SequencingCommitment (excluding P.TxList)
   2. Y does:
       1. B.ExpectedAcceptedIDMerkleRoot = B.TxList.MerkleRoot()
       2. B.ExpectedSequencingCommitment = hash(B.SelectedParent.SequencingCommitment, B.ExpectedAcceptedIDMerkleRoot)
       3. Verify that B.ExpectedSequencingCommitment == SequencingCommitment

Note we start from P.SelectedChild, because P.SequencingCommitment can not be verified without it's SelectedParent.

Sample Code

KIP-15 implementation can be found in the following PR: kaspanet/rusty-kaspa#636

Backwards compatibility

Breaks consensus rules, requires a hardfork.

Acknowledgements

Thanks to Michael Sutton @michaelsutton for the discussions leading to this KIP.