Background: along with the proof of archival storage the Subspace protocol also make use of proof of time. Proof of time (PoT) has several merits:
- On the practical side, it makes deploying long-range attacks much harder.
- It can be used to resolve the predictability issue that comes with the c-correlation approach, an approach to address the costless-simulation attack (for more on the latter, see this thread).
- On the theoretical side, it can be used to remove additional security assumptions for non-proof-of-work consensus protocols (see this thread for more details).
Proof of time is used in practice in proof-of-space-based blockchains like Chia and Spacemesh and is also covered in academic work.
Long-range attacks
Long-range attacks is a type of attack where an adversary chooses some historical point in the blockchain and forks the chain from that point. Typically, the adversary has much more resources (e.g. storage or hash power) than the weight of the chain in that point and in some circumstances may be able to produce a heavier fork than the current chain (still under the assumption they have less than 50% of the current honest resource). This is possible since unlike PoWork, producing blocks in PoSpace- or PoStake-based blockchains has no physical constraints, and so it is an easy process.
Having provable elapsed-time mechanism is not enough to prevent long-range attacks. It is important to integrate the blockchain itself into the “proof of time chain”. For example, while it is possible to use the Bitcoin blockchain as a source of reliable timestamping service (and so to derive challenges from Bitcoin blocks), any long-range attacker can use the exact same randomness to grow their chain without additional physical constraints.
We use the term “injection” for the integration of the blockchain into the timechain (readers familiar with Chia would know this as “infusion”).
What part of the blockchain should be injected into the timechain?
We suppose some block is chosen, a part of which will be injected into the timechain. We do not expand here how this block is chosen (interested readers can find some design choices in this thread).
We discuss 3 options for this part of the block:
- The proof of space (PoS) that gave the farmer an eligibility to produce the block.
- A block header that does not refer to any list of transaction (in that block or in previous blocks). This can include the farmer id, PoS, PoT and crucially (for our discussion) the hash of the previous header.
- The block hash.
The aim of the following is to analyse in what circumstances the long-range attacker could use the historical timechain as part of their attack when constructing a new chain.
Block hash: it is easy to see that if the block hash is injected, then any change to the blockchain history would result in a different hash, forcing the long-range attacker to evaluate a new timechain (from the injection point) to deploy the attack.
On the other hand, injecting the block hash gives rise to an issue where an attacker (either long- or short-range attacker) that produces this block can grind on the block content (the list of transactions) to generate different hashes, thus different block hashes, resulting in the possibility to run different timechains and choose a favourable one.
For the other options, block header and proof of space, suppose the attacker is the farmer that originaly produced the block. Note that the attacker can change the block’s list of transactions and that would not affect the timechain, as in the general case the header and PoS do not reflect the blockchain content. We try to explain how severe this is.
First, notice that even if the timechain is not affected, the timechain does not live in isolation. Let b_0 be the original block and let b'_0 be “that block” after the attacker modify its content (b_0, b'_0 share the same PoS and the so-called header). Let b_1 be the subsequent injected block. As a chain, b_1 refers (possibly indirectly) to b_0, but since b_0 is not part of the attacker’s chain, they could not include the block b_1 in their chain, as the block would not validate.
If the attacker wishes to use the injected part of b_1, the attacker would have to control the private key for the farmer that generated b_1, in order to sign a modified block b'_1 corresponding to b_1's farmer id (we clarify that PoS includes the farmer id). The modified block b'_1 refers to (the modified block) b'_0.
Block header: since block headers forms a “chain of headers”, the attacker would need to have in their possession the farmers’ private keys for all of the blocks between two injected blocks. Indeed, in the example above consider some block b between b_0 and b_1. We stress that b is part of the honest “historical” chain, and recall that the headers of b_0 and b_1 are the same as the headers of blocks b'_0 and b'_1, respectively. As a chain, the header of block b'_1 refers to the header of b, however the full block b refers to the full block b_0. We get that on one hand the attacker must include the header of b in their blockchain, otherwise b'_1 would not validate, while on the other the block b is not valid in the attacker fork. As above, the attacker would need to keep the header of b but change the block itself to obtain b', and this can be done if they have the private key for the farmer that generated b.
Proof of space: unlike the previous case, PoS in successive blocks are not chained. As explained above, in this case the attacker would need to modify b_0 and b_1, so they need to obtain the corresponding private keys.
Luckily, the proof of archival storage used in Subspace is a special type of proof of space where PoS refers to the blockchain content. If the attacker tries to use the Subspace PoS (either directly or as part of the header) of blocks b_0, b_1, . . . , b_n for the timechain injection, they need to make sure that all of these proofs of space contain parts of the blockchain history prior to the point in time the attacker forked the chain (and in particular, prior to b_0).
Note that in the block header case, the attacker would need this condition to hold for all blocks after b_0. Moreover, observe that in this case, unlike the typical long-range attack, the attacker cannot use any free storage they may have.
We leave for future analysis the option of injecting the (PoS,PoT) tuple from the chosen block. The upside of this approach is that since PoT is updated according to the blockchain progression, it may be that the PoT in block b_1, for example, is no longer relevant to the private chain that the attacker farmed after block b_0. If this is the case then it may be possible to show that the attacker’s only measure against this is to use for each and every block in their fork the exact same (PoS,PoT) tuples from the original chain, equating it to to the block header case.
Another interesting avenue to research is an “hybrid” attack where the attacker does run some proofs of time but tries to find a way to run them in parallel.
Lastly, for readers interested how the topic in this post is handled in other proof-of-space protocols, we remark that Chia mainly follows the block header approach, but occasionally infuses their blockchain into their timechain (see Objective 3).