Proof-of-storage

Currently, we are relying on two distinct mechanims to induce storage providers to actually replicate what bags the chain obliges them to

1. Risk of being detected as not doing so, and slashed by discretion of storage working group lead.
2. Lost revenue from not being picked to be synched from

These incentives are fine, but they are obviously imperfect. There is monitoring cost and collusion risk in 1) and for very low popularity content the net marginal bandwidth revenue could hypothetical be lower than expected storage costs in 2).

We could throw one additional, relatively simple, incentive into the mix, which is to use the same proving mechanism that Sia has, where basically the chain will probabilistically challenge a storage provider to submit a fragment of the data it is supposed to store on-chain, and the validity of that data is authenticated in the runtime using a Merkle proof and the root hash initially committed to. No valid reply will result in a slashing. Here it is worth nothing that it could make sense to have two distinct commitments per object, one with large chunks, useful for doing iterative validation of dataobjects during p2p synching, and one with small chunks, used for on-chain challenges, to minimize total footprint on-chain. Conceptually this is super simple, and we are very well placed to do the same in v2, as we are literally storing a data hash in the state as well (for other temporary reasons actually). This mechanism is of-course also not perfect, e.g. there is a risk of

• storage providers attempting to opportunistically download the data on-demand form other providers to respond to the challenge. This risk can be partially mitigated by making the time bound on the response very tight, e.g. 2-3 blocks, which imposes serious risk of peer providers not responding in time.
• it adds size to the ledger, as the size of the data and the proof, takes some space. To minimise this problem we really need tocome up with some decent scheme for making the original Merkle commitments so that the tradeoff between the size of the challenge data and the merkle branch leads to the minimal total size.

The main complexity would be in dealing with the fact that the liason may, in order to maliciously get peers slashed, confirm uploads that have invalid hashes, or simply withhold synching to peer providers so they don't actually get the data. This could be addressed by either

a) only challenging liasons, if they exist. This is a bad alternative, as over time liasons will tend to not be part of the system any longer, or not part of that same bag.
b) re-introduce the concept of storage providers signalling when they have replicated a data object, so that the runtime knows who it can asks with what challenge. It also has the added benefit of making this knowledge publicly verifiable, so that you restrict what providers can claim is causing their malfunction after they have confirmed. The downside is obviously that it adds lots of extra transactions, and additional state. You can avoid the very worst problem of all the cleanup you would have to do when setting a new operator for a bucket, by simply having the runtime assume that anyone set as an active provider for a bucket is opting into having all confirmed objects of the prior provider.
c) introduce the leaner concept of providers having to signal that they are fully synchronized with a given bag every time it has had one or more new objects added. So you only need to associate a block number with the relationship between a storage bucket and a bag, if this block number exceeds the block number in the bag for last it was updated, then the runtime knows the bucket operator should have anything in that bag. This signaling has the added benefit of being a nice liveness indicator, and the chain could even slash providers that start to lag too far behind on their synching overall across all bags, something that presumably would not be easy for other providers to cause unless there was a large coordinated censorship effort.
d) if one assumes that most of the time, that is during honest faults, a given bucket will only rarely find that it is unable to get some object, or get up to speed with a full bag, despite it being > 24 hours (lets say) since there was a change,then one could flip the representation and instead permit a bucket operator to have a sort of exception list of say 100-1000 things that it is still not able to get. The on-chain challenge protocol will ignore anything on this list. Since the list is so much smaller than the overall set of obligations a bucket has, it is no way to circumvent the probabilistic challenge, it really only works to avoid rare genuine issues. One could imagine a large number of providers trying to quickly censor a given provider, perhaps by even starting to do lots of uploads, so as to try to fill the exception list of a victim provider. This will not be easy or cheap at scale, as the attacks would consistently need to occupy all other buckets on the same bags as the victim, but not impossible, and there is no payoff to the attacker directly. But to deal with this, it could be possible for a provider to enable a circuit breaker signal of some kind, opting out of being challenged, at which point the lead has to step in. Importantly, this emergency signal is not a way of opportunistically getting out of a challenge, as you have to do it a certain amount of time in advance, and you never know when the challenge will hit.

One additional, but quite narrow, technical question is how to make the probabilistic on-chain sampling efficient, and how to make it sample over the storage space, rather than object space. Sampling over the storage space means that each byte of data has an equal chance of getting audited, while sampling over objects means that storage providers can speculate and try to only store small objects, since they are cheaper. Its not at all clear how much of a difference this distinction makes, and one can calibrate the challenge protocol to have probabilities and penalties tuned to hit large objects sufficiently frequently.

┆Issue is synchronized with this Asana task by Unito

The issue names no implementation files, tests, or entry points. Start by locating the v2 runtime code for storage-provider obligations, data-hash commitments, and bag synchronization, then compare the proposed challenge and provider-signalling alternatives; done means an agreed protocol and implementation scope, not yet specified here.