Traditional Proof-of-Work (abbrev. PoW) blockchains like Litecoin force require clients to verify the entire blockchain linearly in the length of the chain. Client based on Non-Interactive Proofs of Proof-of-Work (abbrev. NIPoPow)[1][2] only requires resources logarithmic in the length of whole chain, making them much more performant in both time and space resources. To enable NIPoPow in Litecoin requires some additions in block headers to track so-called super block interlinks. These interlinks allow for drastically compressing the chain down a small number of blocks sufficient to verify an entire chain prefix.
This proposal explains how block interlinks should be constructed and stored, but also how blocks can be verified securely using the compressed version of the chain obtained as a result. It finally covers some of the known limitations of this approach.
Specification
Overview
At its heart, NIPoPow separate blocks into levels. A level represents the number of leading 0 of a block ID (when encoded in base16), or more formally, for a block B and a chain difficulty target T.
μ = level(B) = floor(log(T) - log(id(B)))
Where id(B) represents the block ID of the block B. Note that a block of level μ (μ > 1) is also of level μ-1. We call block of level μ a μ-superblock and by convention the genesis block is considered to have a level of ∞ in addition to being the root block of every levels. This creates multiple sequences of block ids, from the genesis block and onward. The higher the level, the smaller the sequence; on average each sequence will contain n = L / 2^μ elements, where L is the length of chain. That is, half of blocks are of level 1, 1/4 of the blocks are of level 2, 1/8 of level 3 etc...
Similarly, a subchain containing all the blocks of a certain level μ is called is μ-superchain.
Interlink Construction
In NIPoPow, block headers not only keep track of the previous block header hash, but also keep track of the most recent super blocks of various levels in a dedicated data-structure. We call that data-structure the block interlink which is essentially a vector with the following definition:
∀i > 0: interlink[i] is the hash of the most recent block with ID smaller than T / 2^i.
By convention, interlink[0] refers to the genesis block. For each block block, miners must construct the interlinks as follows (in pseudo-code):
def updateInterlink(block):
interlink = block.interlink
for µ in [ 0 .. level(block) ]:
interlink[µ] = id(block)
return interlink
The interlink must then be stored in each block header.
Chain Validation
NIPoPoW allows for lightweight nodes to rapidly synchronize with the latest state of the blockchain without having to linearly scan the entire chain. The approach also differs from traditional SPV node clients who, despite requiring only block headers, still to process and store every headers of the chain. With NIPoPow, lightweight clients can instead maintain and validate exponentially less headers by only keeping sufficiently high-level superblocks. This is achieved in mainly two steps: compression and comparison.
In the following section, we'll be considering two parameters:
m as the compression parameter
k as the common prefix parameter
The value chosen for k depends in principle on the hashing power of the system, and represents the number of blocks after which one can consider a block immutable (in such way that the suffix of the chain would be too expensive to re-calculate for an attacker). In Bitcoin, k is typically chosen around 6-7. We also conservatively choose m = 3*k
Compression
NIPoPow nodes only need to keep track of a fraction of the entire chain to operate. We therefore define a compression function that prunes unnecessary blocks from the chain as such:
def compress(chain):
superblocks, _, suffix = dissolve(chain)
return flatten(superblocks) + suffix
def dissolve(chain)
prefix = chain[:-k]
suffix = chain[-k:]
superblocks = []
if len(prefix) >= 2 * m:
# Get the highest level for which we have at least 2*m superblocks.
lvl = max([μ for μ in range(0, ∞) if len(superchain(μ, prefix)) > 2 * m ])
# Get all superblocks from that level.
superblocks[lvl] = superchain(lvl, prefix)
# Then for each level downwards
for μ in range(l-1, 0):
# Always include the last -2m super blocks for that level.
superblocks[μ] = superchain(μ, prefix)[-2m:]
# And add up all the block greater than the parent pivot
pivot = superchain(μ+1, prefix)[-m]
superblocks[μ] += [ blk for blk in superchain(μ, prefix) if b >= pivot ]
return superblocks, lvl, suffix
else:
superblocks[0] = prefix
return superblocks, 0, suffix
This algorithm assumes the existence of a function superchain which computes the μ-superchain of a corresponding chain prefix, given some level μ. And also, a function flatten which flattens the list of lists of superblocks into a single list, removing duplicate blocks.
Conceptually, the idea is to get only a fraction of each level, favoring more blocks when near the tip of the chain and less blocks when near the genesis point. The compression is only possible for chains that already have a certain number of blocks (at least 2*m) for which we then try to find the highest level that has at least 2*m blocks. Note that all blocks are at least 0-superblocks, so this is guaranteed to find at least one level with at least 2*m blocks (if only, level 0).
For example, we can represent the algorithm as follows:
[:-k] [-k:]
<------------------------------------------------> <--------->
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
O - O - O - O - O - O - O - O - O - O - O - O - O - O - O - O
O O O O O O O O
O O O O
If we assume m=2 for the sake of the example here.
μ=2: [0,4,8,12]
2 is the maximum level for which we have at least 2*m superblocks. We therefore keep all superblocks of that level.
μ=1: [6,8,10,12]
On the next level, we keep the last 2*m 1-superblocks (reminder than 2-superblocks are also 1-superblocks), so 6, 8, 10 and 12.
Then, we add any 1-superblock which happened after the parent pivot 10, which means 10 and 12 already counted as part of the previous step.
μ=0 [9, 10, 11, 12]
At level 0, there's no more compression going on so we simply keep the last 2*m blocks of the prefix: 9, 10, 11 and 12.
As for the previous case, we also include all blocks greater than the parent pivot 10, which means 10, 11 and 12 already counted as part of the previous step.
The final compressed chain is obtained by merging selected blocks from all the levels (while removing duplicates) and by adding back the suffix, so: [0,4,6,8,9,10,11,12,13,14,15].
As mentioned earlier, the compressed chain is not uniformly compressed, but it is denser near the tip than it is near the beginning. As new blocks gets added, we expect miners to keep compressing
their local chain, possibly removing some old blocks at each step. This approaches ensures that the local chain does only grow poly-logarithmically in terms of the total chain length.
Comparison
Considering now that miners (either full nodes or light nodes leveraging NIPoPow) are computing compressed version of their chain, it should be possible for a new node (a.k.a a verifier) to enter the network and perform a fast synchronization of the chain by only looking at compressed chains. Such a node is expected to gather compressed chains from various already synchronized node which we call provers. We expect that at least one of the chosen prover is honest.
The verifier thereby needs a function to compare the various compressed chains received from provers in order to select the best one, that is, a chain that a full node miner booting from genesis could have plausibly arrived at (the notion of longest chain is a bit different when considering compressed chains, hence the need for a specific comparison function). Once chosen, the new miner can start mining on top of the compressed chain and become itself a prover for future nodes.
def compare(chainA, chainB):
if not (isValidChain(chainA)):
return chainB
if not (isValidChain(chainB)):
return chain A
superblocksA, lvlA, suffixA = dissolve(chainA)
superblocksB, lvlB, suffixB = dissolve(chainB)
diff = [ μ for μ in range (0, ∞) if len(intersection(superblocksA[μ], superblocksB[μ])) > 0 ]
if len(diff) == 0:
if lvlA > lvlB:
return chainA
else
return chainB
else:
μ = min(diff)
clash = intersection(superblocksA[μ], superblocks[B])[-1]
if len(after(clash, superblocksA[μ])) > len(after(clash, superblocksB[μ])):
return chainA
else:
return chainB
def after(point, chain):
return [ blk for blk in chain if blk >= point ]
The idea is sensibly the same as the selection of normal chains based on the longest prefix, except that here, we compare superchains at specific level. The algorithm starts by finding a level at which comparing the two chains. That is, the first level from which both chains are referring to different blocks. In case there's none, the chain with the highest superchain wins. Otherwise, we compare chains according to the longest prefix, but only after the point where they start diverging.
Motivation
As stated in the introduction, NIPoPoW allows for drastically reducing the needs in storage and verification for light nodes. This enables so-called logarithmic mining on top of an existing chain. Note that this approach doesn't fully exempt the network from full nodes since some are still required to keep track of the entire chain history. It however enables a whole class of lightweight clients which can benefits of similar security guarantees while preserving storage and computational resources low.
Beside, the addition required to enable such mining mode is relatively succinct both in terms of changes and in terms of resulting workload for the miners.
Rationale
The proposed protocol is accompanied by a formal analysis which proves security and succinctness.
With respect to security, it is shown that an adversary with less than 1/3 of the total mining power cannot convince a verifier to adopt his own chain instead of an honest one. For such an accomplishment, the adversary should manage to orphan a certain number of honest superblocks of some level μ and simultaneously compute enough of his own. However, as proven in [1], against a 1/3-bounded adversary there will be enough honest blocks that cannot be orphaned by any attack. The contribution of these blocks to the given level μ is shown sufficient to overtake the corresponding adversarial blocks.
Succinctness in the static setting rests on two facts. First, note that a NIPoPoW chain contains a constant number of blocks of each level. Second, the blocks of level μ need to cover about half of the chain that blocks of level μ+1 cover. It follows that a logarithmic number of levels suffices.
Note that it is possible to boost security to a 1/2-bounded adversary, by temporarily hiding the hash value of a block and providing a ZK proof of its validity. We consider this beyond the scope of the current proposal.
Backwards compatibility
This change requires a hard-fork of the current network, since it requires the addition of the interlink structure in block headers. This change is not backward compatible for it is not feasible to modify the existing chain prefix (which would require to re-do the Proof-of-Work for the ENTIRE chain). However, it is still possible to pre-calculate the interlink and a compressed version of the entire prefix pre hard-fork for bootstrapping new lightweight clients. Such prefix would be considered "common knowledge" in a similar fashion to how the genesis hash is considered.
Another alternative to a hard-fork could be to do a so-called Velvet-Fork and to have only some of the miners cooperate to compute and to store the interlink as part of coinbase transactions using OP_RETURN scripts. To operate a NiPoPoW chain, it is not required to have a strict interlink structure (listing exactly all the possible superblocks); it is okay to have holes, just less efficient.
Note that, in the case of a Velvet fork, the size of the interlink is limited by the size of the OP_RETURN and it may not be possible to store interlink with too many (albeit realistic) levels. It is therefore recommended to instead manage interlinks as a Merkle tree, and only store the Merkle tree root in the coinbase transaction. The interlink as well as the compressed chain prefix can be forwarded to light clients for validation.
Abstract
Traditional Proof-of-Work (abbrev. PoW) blockchains like Litecoin force require clients to verify the entire blockchain linearly in the length of the chain. Client based on Non-Interactive Proofs of Proof-of-Work (abbrev. NIPoPow)[1][2] only requires resources logarithmic in the length of whole chain, making them much more performant in both time and space resources. To enable NIPoPow in Litecoin requires some additions in block headers to track so-called super block interlinks. These interlinks allow for drastically compressing the chain down a small number of blocks sufficient to verify an entire chain prefix.
This proposal explains how block interlinks should be constructed and stored, but also how blocks can be verified securely using the compressed version of the chain obtained as a result. It finally covers some of the known limitations of this approach.
Specification
Overview
At its heart, NIPoPow separate blocks into levels. A level represents the number of leading
0of a block ID (when encoded in base16), or more formally, for a blockBand a chain difficulty targetT.Where
id(B)represents the block ID of the blockB. Note that a block of levelμ(μ > 1) is also of levelμ-1. We call block of levelμa μ-superblock and by convention the genesis block is considered to have a level of∞in addition to being the root block of every levels. This creates multiple sequences of block ids, from the genesis block and onward. The higher the level, the smaller the sequence; on average each sequence will containn = L / 2^μelements, whereLis the length of chain. That is, half of blocks are of level 1, 1/4 of the blocks are of level 2, 1/8 of level 3 etc...Similarly, a subchain containing all the blocks of a certain level
μis called is μ-superchain.Interlink Construction
In NIPoPow, block headers not only keep track of the previous block header hash, but also keep track of the most recent super blocks of various levels in a dedicated data-structure. We call that data-structure the block interlink which is essentially a vector with the following definition:
By convention,
interlink[0]refers to the genesis block. For each blockblock, miners must construct the interlinks as follows (in pseudo-code):The interlink must then be stored in each block header.
Chain Validation
NIPoPoW allows for lightweight nodes to rapidly synchronize with the latest state of the blockchain without having to linearly scan the entire chain. The approach also differs from traditional SPV node clients who, despite requiring only block headers, still to process and store every headers of the chain. With NIPoPow, lightweight clients can instead maintain and validate exponentially less headers by only keeping sufficiently high-level superblocks. This is achieved in mainly two steps: compression and comparison.
In the following section, we'll be considering two parameters:
mas the compression parameterkas the common prefix parameterThe value chosen for
kdepends in principle on the hashing power of the system, and represents the number of blocks after which one can consider a block immutable (in such way that the suffix of the chain would be too expensive to re-calculate for an attacker). In Bitcoin,kis typically chosen around 6-7. We also conservatively choosem = 3*kCompression
NIPoPow nodes only need to keep track of a fraction of the entire chain to operate. We therefore define a compression function that prunes unnecessary blocks from the chain as such:
This algorithm assumes the existence of a function
superchainwhich computes the μ-superchain of a corresponding chain prefix, given some levelμ. And also, a functionflattenwhich flattens the list of lists of superblocks into a single list, removing duplicate blocks.Conceptually, the idea is to get only a fraction of each level, favoring more blocks when near the tip of the chain and less blocks when near the genesis point. The compression is only possible for chains that already have a certain number of blocks (at least
2*m) for which we then try to find the highest level that has at least2*mblocks. Note that all blocks are at least 0-superblocks, so this is guaranteed to find at least one level with at least2*mblocks (if only, level 0).For example, we can represent the algorithm as follows:
If we assume
m=2for the sake of the example here.μ=2: [0,4,8,12]2 is the maximum level for which we have at least
2*msuperblocks. We therefore keep all superblocks of that level.μ=1: [6,8,10,12]2*m1-superblocks (reminder than 2-superblocks are also 1-superblocks), so6,8,10and12.10, which means10and12already counted as part of the previous step.μ=0[9, 10, 11, 12]2*mblocks of the prefix:9,10,11and12.10, which means10,11and12already counted as part of the previous step.The final compressed chain is obtained by merging selected blocks from all the levels (while removing duplicates) and by adding back the suffix, so:
[0,4,6,8,9,10,11,12,13,14,15].As mentioned earlier, the compressed chain is not uniformly compressed, but it is denser near the tip than it is near the beginning. As new blocks gets added, we expect miners to keep compressing their local chain, possibly removing some old blocks at each step. This approaches ensures that the local chain does only grow poly-logarithmically in terms of the total chain length.
Comparison
Considering now that miners (either full nodes or light nodes leveraging NIPoPow) are computing compressed version of their chain, it should be possible for a new node (a.k.a a verifier) to enter the network and perform a fast synchronization of the chain by only looking at compressed chains. Such a node is expected to gather compressed chains from various already synchronized node which we call provers. We expect that at least one of the chosen prover is honest.
The verifier thereby needs a function to compare the various compressed chains received from provers in order to select the best one, that is, a chain that a full node miner booting from genesis could have plausibly arrived at (the notion of longest chain is a bit different when considering compressed chains, hence the need for a specific comparison function). Once chosen, the new miner can start mining on top of the compressed chain and become itself a prover for future nodes.
The idea is sensibly the same as the selection of normal chains based on the longest prefix, except that here, we compare superchains at specific level. The algorithm starts by finding a level at which comparing the two chains. That is, the first level from which both chains are referring to different blocks. In case there's none, the chain with the highest superchain wins. Otherwise, we compare chains according to the longest prefix, but only after the point where they start diverging.
Motivation
As stated in the introduction, NIPoPoW allows for drastically reducing the needs in storage and verification for light nodes. This enables so-called logarithmic mining on top of an existing chain. Note that this approach doesn't fully exempt the network from full nodes since some are still required to keep track of the entire chain history. It however enables a whole class of lightweight clients which can benefits of similar security guarantees while preserving storage and computational resources low.
Beside, the addition required to enable such mining mode is relatively succinct both in terms of changes and in terms of resulting workload for the miners.
Rationale
The proposed protocol is accompanied by a formal analysis which proves security and succinctness.
With respect to security, it is shown that an adversary with less than 1/3 of the total mining power cannot convince a verifier to adopt his own chain instead of an honest one. For such an accomplishment, the adversary should manage to orphan a certain number of honest superblocks of some level
μand simultaneously compute enough of his own. However, as proven in [1], against a 1/3-bounded adversary there will be enough honest blocks that cannot be orphaned by any attack. The contribution of these blocks to the given levelμis shown sufficient to overtake the corresponding adversarial blocks.Succinctness in the static setting rests on two facts. First, note that a NIPoPoW chain contains a constant number of blocks of each level. Second, the blocks of level
μneed to cover about half of the chain that blocks of levelμ+1cover. It follows that a logarithmic number of levels suffices.Backwards compatibility
This change requires a hard-fork of the current network, since it requires the addition of the interlink structure in block headers. This change is not backward compatible for it is not feasible to modify the existing chain prefix (which would require to re-do the Proof-of-Work for the ENTIRE chain). However, it is still possible to pre-calculate the interlink and a compressed version of the entire prefix pre hard-fork for bootstrapping new lightweight clients. Such prefix would be considered "common knowledge" in a similar fashion to how the genesis hash is considered.
Another alternative to a hard-fork could be to do a so-called Velvet-Fork and to have only some of the miners cooperate to compute and to store the interlink as part of coinbase transactions using
OP_RETURNscripts. To operate a NiPoPoW chain, it is not required to have a strict interlink structure (listing exactly all the possible superblocks); it is okay to have holes, just less efficient.Note that, in the case of a Velvet fork, the size of the interlink is limited by the size of the
OP_RETURNand it may not be possible to store interlink with too many (albeit realistic) levels. It is therefore recommended to instead manage interlinks as a Merkle tree, and only store the Merkle tree root in the coinbase transaction. The interlink as well as the compressed chain prefix can be forwarded to light clients for validation.Reference implementation
To be done.
References
Copyright
This document is placed in the public domain.