KIP: 6
Layer: Consensus (hard fork), Block Validation
Title: Proof of Chain Membership (PoChM)
Author: Shai Wyborski <[email protected]>
Status: Draft
Type: Informational
The pruning mechanism makes it impossible to prove that a transaction was included in the ledger after it has been pruned. A currently available solution is publicly run archival nodes (in the form of block explorers) that store all historical data. However, this is not a sustainable solution since it relies on centralized service providers, and since the size of the databases increases rapidly with time and adoption.
A better solution is to provide a cryptographically verifiable proof that a transaction was posted to the blockchain. Such a proof could only be generated before the transaction was pruned (or by using an archival node), but could be verified indefinitely.
There are two types of proofs:
- a proof of publication (PoP), proving that a transaction has appeared on the blockchain at a certain time
- a txn receipt (txR), further proving that the published transaction was validated (that is, that there was no conflicting transaction that was eventually accepted) I will refer to these two types of proof collectively as inclusion proofs.
In the current consensus rules, it is technically possible to create inclusion proofs, but such proofs can grow rather large (over 20 megabytes in the worst case). Additionally, generating and validating these proofs needs to be done manually, as these functionalities are not implemented in the node.
I propose a small modification to the block validation rules that extremely reduces the size of inclusion proofs to the order of several kilobytes while incurring very mild costs on the network's performance (in terms of storage costs and block validation complexity). I also provide precise algorithmic descriptions of how inclusion proofs are generated and verified, with the intention that they will be implemented as API calls.
Interestingly, while the notion of txR is strictly stronger than a PoP, it is actually easier to implement in Kaspa. This is because accepted transactions get special treatment: each selected chain block contains the root of a Merkle tree of all transactions that were accepted by the block (the ATMR, see below). Hence, a transaction was accepted if and only if it appears on this Merkle tree on a selected chain block.
Hence, to provide a proof of receipt for txn, it suffices to provide the Merkle proof that a block B accepted txn, along with some proof that B was a selected chain block. To provide a proof of publication, it suffices to provide a proof that a block B was a selected chain block, a chain of headers going from B to some block C and a Merkle proof that C accepted txn.
The common part of these two types of proofs is showing that B is a header of a selected chain block, that is, providing a proof of chain membership (PoChM, pronounced like the latin word pacem). This is the focus of the current proposal.
I stress that the current sizes are calculated with respect to the values of various parameters in the current 1BPS consensus. Changing these parameters would require recalculating these values. However, increasing block rates will only increase the factor by which proposed proofs are improved upon currently possible proofs (roughly because currently possible proofs are as large as the entire ledger stored between two consecutive pruning blocks, whereas the size of proposed proofs grows logarithmically with the number of chain blocks between two consecutive pruning blocks. In particular, increasing BPS will increase the size of current proofs, but not the size of proposed proofs).
In this proposal, it is convenient to use the notation Past(B) (resp. Future(B)) to denote the past (resp. future) of the block B including the block B itself. The method names are capitalized to differentiate them from the common notations past(B) and future(B) which exclude the block B itself.
I use the notation parent(B,n) to note the nth selected parent of B. For brevity, I use parent(B) instead of parent(B,1). For any n>1 we can recursively define parent(B,n)=parent(parent(B,n-1)).
The consensus state of a Kaspa node includes a list of selected chain block headers. These headers are sampled at (approximate) regular intervals and are stored indefinitely. Hence, we call them posterity headers.
Currently, posterity headers are taken from blocks used as pruning blocks, and a posterity header is stored once every 24 hours, whereby they are also commonly referred to as pruning headers. Later in this proposal I consider decoupling pruning headers from posterity headers, though I propose to delay this step to a separate update (mainly due to engineering complexity considerations). That being said, I currently disregard the pruning motivation and refer to these headers as posterity headers for convenience.
Given a block B let posterity(B) be the earliest posterity header such that B ∈ Past(posterity(B)), or null if such a stored header does not exist yet. Let posterity_depth(B) output the integer n satisfying B=parent(posterity(B),n).
For any block B let next_posterity(B) be the block header with the following property: if B is a posterity header, then next_posterity(B) is the next posterity header. Note that this is well-defined even if B is not a posterity header.
Posterity headers have the following important properties:
- They are determined in consensus. That is, all nodes store the same posterity headers.
- They are headers of blocks in the selected chain.
- Each block
Bcontains a pointer toposterity(posterity(posterity(B))). Hence, the chain of posterity headers is verifiable all the way down to genesis. In particular, obtaining and verifying the posterity chain is part of the process of syncing a new node.
The reason that B points to posterity(posterity(posterity(B))) and not is posterity(B) that the original motivation for storing these blocks comes from the pruning mechanism, where these depth-3 pointers are required (for reasons outside the scope of the current discussion).
In Bitcoin, every header contains the root of a Merkle tree of all transactions included in this block. In Kaspa, this Merkle tree is extended to contain all accepted transactions included in this block and its merge set. That is, all transactions that appear either in the block or the merge set of the block, except transactions that conflict with other transactions that precede them in the GHOSTDAG ordering.
To provide a txR for txn, it suffices to provide the following:
- A header of a block
Band a Merkle proof thattxnappears inB's (ATMR) - Proof that
Bappeared in the selected chain
This suffices to prove that txn was validated even if a conflicting transaction txn' (or any number thereof) was also included in the blockDAG: the validation rules imply that txn and txn' both appeared in the anticone of B, and that txn preceded txn' in the GHOSTDAG ordering.
The first item is a straightforward Merkle proof. However, the second item is trickier. I refer to such a proof as a proof of chain membership (PoChM, pronounced like the Latin word pacem) for B. The rest of this document is concerned with providing a PoChM for an arbitrary block B.
Currently, the most straightforward way to construct a PoChM for B is to store the entire set Future(B) ∩ Past(posterity(B)). The result is a "diamond shaped" DAG whose top block is posterity(B) and bottom block is B. Given a DAG of this shape as proof, any node could verify that the top block is a posterity block, and that following the selected parent from the top block leads to the bottom block.
The problem with this proof is its size. In the worst case, it would be about as large as 24 hours worth of headers. At the current 1BPS and header size of 248 bytes, this sums to about 24 megabytes.
Remark: This could be improved slightly by, instead of storing the entire set, only storing the headers of the selected chain blocks and their parents. This data suffices to compute the selected parent of each selected chain block and validate the proof. However, this does not seem to improve the size by much. Also note that proofs for many transactions that were accepted in chain blocks with the same posterity can be aggregated. In particular, a PoChM for a block B is also a PoChM for any chain block C ∈ Future(B) ∩ Past(posterity(B))
Remark: Note that a PoP does not actually require the entire PoChM. It suffices to provide a chain of headers going from any posterity block to any block merging txn. Since in PoP we don't care whether txn was eventually accepted, we are not concerned about whether this chain ever strays from the selected chain. However, the improvement is only by a constant factor (the ratio of chain blocks to total blocks), which is currently estimated to be a factor of around two.
We aim to decrease the size of a PoChM as much as possible while minimizing performance costs. There are two relevant types of costs: header sizes, and block validation complexity.
As an extreme example, one could provide a very small PoChM by including in each posterity header the entire list of headers of all chain blocks down to the next posterity header. This "solution" is obviously prohibitive as it will make block headers huge.
On the other extreme, one could include in each header a Merkle tree of all chain blocks down to the next posterity header, and let the PoChM of B be a Merkle proof for that tree. While this "solution" only increases the size of a block header by 32 bytes (the size of a single hash), it makes it necessary to compute tens of thousands of hashes to validate a single block header, which is prohibitively costly.
Our proposal "balances" the second approach: we add to each header the root of a Merkle tree that only contains logarithmically many headers. This allows generating a PoChM in the form of a logarithmically long chain of headers and Merkle proofs.
In the current parametrization, implementing our proposal requires increasing the size of a header by a single hash (32 bytes), and adds a validation step with constant space complexity and a time complexity of θ(log(N)) where N is the number of chain blocks between two consecutive posterity blocks. The size of a PoChM, as well as the time required to verify it, is θ(log(N)loglog(N)).
We will provide non-asymptotic bounds after specifying the solution. For now we will state that in the current parametrization (without increasing posterity header density), the new block validation step requires computing 33 hashes (and can be skipped for blocks outside the selected chain), and that, in the worst case, the size of a PoChM is about 9.5 kilobytes.
The block header will contain a new field called the PoChM Merkle root (PMR) defined as follows: let k be the least integer such that parent(B,2^k) ∈ Past(next_posterity(B)), then PMR is the root of the Merkle tree containing the headers parent(B,2^i) for i = 0,...,k-1.
Let PMR(B,i) be the function that outputs a Merkle proof that hash(parent(B,2^i)) is in the tree whose root is the PMR of B.
The process of header validation of chain block candidates will include verifying the PMR. I propose that the PMR will not be validated for blocks that are not chain candidates. In particular, a block whose PMR is invalid but is otherwise valid will remain in the DAG but will be disqualified from being a selected tip/parent. A similar approach is employed e.g. when validating UTXO commitments or checking that the block does not contain double spends. (A crucial subtlety is that, eventually, the selected parent of a block is always the parent with the highest blue accumulated work (BAW). If while validating the selected parent the block turns out to be disqualified, then the pointer to this block is removed. This rule allows us to read the selected parent of any block from the headers of its parents alone, without worrying about the parent with the highest BAW is disqualified for some external reason that requires additional data to notice).
The procedure for generating a PoChM for a block B is as follows:
Let C = posterity(B)
If C=null:
Return error
Let d = posterity_depth(B)
Let proof = []
While true:
Let i = floor(log_2(d))
proof.append(PMR(C,i))
d -= 2^i
If d == 0:
Break
C = parent(C,2^i)
proof.append(C)
Return proof
To understand how to validate the proof we first consider it in two simple cases:
If there is some i such that posterity_depth(B) = 2^i then B itself is a member of the PMR of posterity(B) and the entire PoChM is a single Merkle proof.
If there are some i>j such that posterity_depth(B) = 2^i + 2^j then the proof would contain three items:
- A Merkle proof that
hash(parent(posterity(B),2^i))is in the PMR ofposterity(B) - The header
parent(posterity(B),2^i)(that in particular includes its PMR) - A Merkle proof that
hash(B)is in the PMR ofparent(posterity(B),2^i)
By verifying the proofs and hashes above, one verifies that B is indeed a chain block. The general procedure extends similarly.
To generate a validation receipt for txn:
- Find the block
Bthat acceptedtxn - Output: PoChM for
B, Merkle proof thatBis in the ATMR ofB
To generate a PoP for txn:
- Find the block
Cthat in whichtxnwas published - Let
Bbe the earliest selected chain block withCin its past - Output: PoChM for
B, chain of headers fromBtoC, Merkle proof thattxnis inC's ATMR
Note that the PoP can be optimized: instead of using C, find a block C' along the path from B to C' that accepts txn and minimizes the length of chain from B to C', use C' instead of C in the last step. This optimization has the nice property that if txn was accepted, then the resulting PoP will be identical to the validation receipt. However, it might be the case that the increased complexity of implementing the optimization is more substantial than the reduction in proof size, which should be measured in practice.
As a final optimization, I consider increasing the stored block density to once an hour. The main motivation for this optimization is to reduce the time required before a PoChM could be generated. A prerequisite for generating a PoChM is that stored_header(B) already exists, and reducing this time is beneficial. Additionally, this would meaningfully reduce (by around 40%) the complexity of the added verification step and of PoChM verification and the size of a PoChM.
However, this introduces additional costs. Currently, posterity headers double as pruning headers. Decoupling them from each other means that an additional posterity header would have to be added, increasing the header size to 312 bytes. In addition, this decoupling is tricky engineering-wise and is probably more complicated to implement than the entire rest of the KIP.
I recommend first implementing the current KIP using the current posterity/pruning header, and deciding on separating posterity headers with increased density later, based on demand and necessity. It might also be the case that the additional pointer might be removed (i.e. the pruning mechanism will somehow piggyback on the posterity blocks in a way that doesn't have computational costs). This should be subject of an independent discussion, to be concluded in a follow-up KIP.
Computing the actual size of a PoChM is a bit tricky, as it depends on the number of chain blocks between C and next_posterity(C) for several blocks C. Buy staring at the KGI for sufficiently long, one can get convinced that the selected chain grows by about one block every two seconds (that is, in 1BPS we see that about half of the blocks are chain blocks). To provide a reliable upper bound, I will assume that the selected chain grows at a rate of about 1 block per second. Note that the growth of the selected chain is not governed by block rates, but by network conditions. Hence, I assume this holds with overwhelming probability for any block rate. This might not hold if network conditions improve greatly. However, we'll soon see that the growth asymptotics (as a function of the number of chain blocks between two consecutive posterity blocks) are a very mild log*loglog, whereby this is hardly a concern. I will demonstrate this with concrete numbers after we obtain an expression for the size of a PoChM.
Let L_e and L_a denote the size of a header and a hash, respectively. Let N be the number of seconds between two consecutive posterity blocks. For a block B let |B| denote the Hamming weight of the binary representation of posterity_depth(B). It follows that a PaChM for B contains |B| Merkle proofs and |B|-1 headers (in particular, if B=posterity(B) (equivalently posterity_depth(B)=0) then |B|=0, and indeed the "proof" is empty, since the consensus data itself proves that B is a chain block).
The size of each merkle proof is (2*log(logN))+1)*L_a, so the total size of the PaChM is (2*log(logN))+1)*L_a|B| + L_e*(|B|-1). In the worst case, we have that |B| = log(N) so we obtain a bound of (2*log(logN))+1)*logN*L_a + L_e*(logN-1). Assuming L_e=32 Bytes and L_a=280 Bytes and N=86400 (that is, that a posterity block is sampled once every 24 hours), this comes up to 9 kilobytes.
Increasing posterity density to once per hour (that is, setting N=3600) would decrease the largest PoChM size to 6 kilobytes.
If network conditions improve so much that the selected chain grows at a rate of 10 blocks per second (which is unlikely to happen in the foreseeable future), the largest PoChM size would be 11 kilobytes for 24-hour density and 8 kilobytes for one-hour density.
The size of a txR is the same as the size of a PoChM up to a single Merkle proof. Note that the size of such a Merkle proof is not log(logN) as the ATMR does not contain block headers but transactions. Hence, the size of this Merkle proof is logarithmic in the number of transactions accepted by B, and is subject to adoption, and block rates. To get a loose upper bound, consider a scenario where each block contains 300 transactions, and merges 99 blocks (e.g. 100BPS assuming an average network delay of one second). In this scenario, the ATMR would contain around 30000 transactions, so the Merkle proof would contain the transaction itself and 29 hashes, making it about 1KB large.
24-hour posterity density:
- Constant storage: Currently, three days of ledger data are stored, which contain about 260,000 headers. Storing as many headers requires about 8.5 megabytes.
- Accumulated storage: An additional hash to each posterity header increases the state growth by about 11 kilobytes a year
- Block Validation: The new step requires computing a Merkle root of a tree of height
logNcontaining chain blocks. Since there is already fast random access to all chain blocks, the heaviest part of the computation is the number of hashes, where the required number of hashes is2*logN-1. Assuming a selected chain growth rate of one block per second, this becomes 32 hashes. When there are no many reorgs this comes up to 32 hashes/second. If somehow the selected chain growth rate increases to say 10 blocks per second, this would become 39 hashes per block or 390 hashes per second. Using an efficient hash such as blake2, computing this many hashes is negligible even for very weak CPUs.
one-hour posterity density:
- Constant storage: same as above
- Accumulated storage: an additional 23 headers per day accumulate to about 2.3 megabytes per year
- Block Validation: The number of hashes/second will reduce to 23 hashes/second for 1 block/second selected chain growth, or to 300 hashes/second for 10 blocks/second selected chain growth.
It is fair to say that in all scenarios, the resource costs of this upgrade are very marginal.
Breaks consensus rules, requires hardfork. Changes header structure.