Problem

Similar to proof-of-stake, proof-of-space protocols are susceptible to long-range (aka history rewriting) attacks. Specifically, an attacker does not need 51% of the storage today to mount a private double-spend attack, instead, they only need 51% of the time-average storage over the life of the protocol. We discuss these attacks in our technical white paper and postulate that these attacks are infeasible due to the proof-of-archival-storage (PoAS) consensus mechanism. This was later discovered to be incorrect.

The rest of this document includes

• An analysis on why these attacks are feasible and under what circumstances
• A proposed protocol extension to add a proof-of-time to the randomness construction, preventing long-range attacks
• A Rust library that implements an AES based proof-of-time using AES-NI and VAES
• An initial analysis of the potential for hardware speedups over the above implementation, which impacts the security assumptions of the protocol.

Key Questions for Supranational

1. Provide general feedback on the architecture of the proof-of-time protocol and the implications for protocol security. A
2. Review the code and performance of our proof-of-time primitive. Is there anything that can be done to make the implementation faster? Are there any security concerns?
3. Analyze our literature review on hardware speedups. Evaluate the potential performance of a low-latency AES ASIC engine. Provide a comparison of theoretical AES ASIC performance vs AES-NI. Provide a 1-2 page report detailing theoretical performance.

Using old history

Should be detectable. But what is the exact verification procedure? If verification is probabilistic, can the adversary "cheat" by only replotting a little? How exactly does an adversary "cheat"?

Using new history — constrained by re-plotting (compute) and re-salting (I/O)

How much storage is required?

To create a chain with the same difficulty as the honest chain, the attacker needs the average storage of the honest network over the entire history of the fork. Then the solution range adjustment mechanism makes sure that the total difficulty of the chain matches that of the honest chain. If the total honest storage increased rapidly at the end of a long time interval, the average storage can be a small fraction of the total storage at the end of this interval, making this attack easier than a 51% attack. Let this required storage be denoted $S$.