SNARKs Vector Commitments Collision-resistant Hash Function Merckle Trees
Security in the Cost Model
To model the security of Proof of Space, we consider a rational attacker.
The intuition is that since storage providers cannot save any costs by misbehaving, then they are likely to simply behave honestly. Therefore, a rational provider or attacker will chose the honest strategy.
In PoS case, the advantage of the adversary depends on the relation between storage costs and other resources (such as computation), and on the availability of these resources to the adversary.
An adversary will be bounded to a certain number of concurrent threads of execution. This restriction is justified by the fact that a rational adversary would only invest in extra computing resources that would incur additional costs, if such a strategy would result in lower total costs (including the underlying costs of storage).
We consider two different resources for the prover:
- computation: a CPU unit required when executing some tasks
- storage (over time): a space unit that is “reserved” for a unit of time
Storage as well as computation are directly convertible to cost.
In the following, we will consider rational adversaries, that chose their strategy based on cost consumption, in order to minimize their cost.
To measure the total cost incurred by a prover, regardless of the type of resource we introduce a ratio between computation units and storage units (in terms of real-worlds prices):
= cost ratio between a computation unit and a storage unit (this value may change over time)
Adversarial provers could exploit to get rewarded for storage they are not providing: Sybil attack, outsourcing attacks, generation attacks.
- Sybil Attacks: Malicious provers could pretend to store (and get paid for) more copies than the ones physically stored by creating multiple Sybil identities, but storing the data only once.
- Outsourcing Attacks: Malicious provers could commit to store more data than the amount they can physically store, relying on quickly fetching data from other storage providers.
- Generation Attacks: Malicious provers could claim to be storing a large amount of data which they are instead efficiently generating on-demand using a small program.