Retrievability Protocol

⚠️

Update (17th June 2022): this doc is deprecated, for the last version of the protocol see https://hackmd.io/@irenegia/BkqNihVY5 For more info and link to the App see the website: retriev.org

MVP Protocol

Parties:

Storage Providers
Clients
Blockchain

📌

Protocol Overview: The high level idea is that we want to offer to the client the assurance that if the file is not retrieved then the provider is penalized. To implement this: (1) We choose a set of referees for which we can say that half of them are honest; (2) Client and provider agree on a retrievability deal (aka the assurance policy for the retrieval service); (3) When a client does not get the requested file, it appeals to the referees. One of them tries to retrieve the file asking it again to the provider, if this works the file is forwarded to the client; If not, we try again. After k failed attempts, the provider is penalized; that is the collateral is taken from the provider’s account (k is protocol parameter).

Sign-up: A provider that wants to be part of the consortium needs to sign up (information is on-chain), needs to create an ad hoc collateral account, and moves tokens there.

[Comment: in the MVP prototype the list of providers participating in the consortium is a part of the smart contract that implements the protocol. In particular, this list is created by the contract’s owners and a provider has to communicate its intention to join to the owners]

Referee selection phase: Periodically (eg, once a year) a committee of n referees is chosen and the referee list is published on-chain (n is an integer and protocol parameter).

“Honest majority model”: in this protocol we always assume that at least floor{n/2}+1 of the referees are honest.

How do we choose referees?

[MVP] Option 0 (fixed set of referees): We assume that there is a fixed set of referees, providers join this consortium if they trust at least the majority of them.

[Comment: in the MVP prototype the list of referees is a part of the smart contract that implements the protocol.]

[Future] Option 1 (public election): Providers who are interested propose themself and all consortium members publicly vote for deciding about each candidate (eg, a candidate is elected if it collects half plus 1 of the votes).

[Future] Option 2 (random election): n providers are chosen at random among all the ones that signed up.

Assume that we have that a fraction $\alpha$ of the providers are dishonest (eg, $\alpha < 1/3$ ). Let repeat n extractions for forming the committee. How large n to get honest majority?

X = number of dishonest providers in the committee
E[X] = $\alpha n$ (expected value)
Using the Chernoff Bound, we have

Pr[X ≥ 1/2*n] = $e^{-N(\alpha) n}$
with N( $\alpha$ ) = $\frac{1-4\alpha+4\alpha^2}{4\alpha+2}$
for \alpha = 1/3 , N( $\alpha$ ) = 1/30

n = sec.par * 0.7 * 30

Retrievability deal:

[assumption] There is a public bulletin where clients can read which files are stored by each storage provider (for example, the indexer project).
[deal description] A client who is interested in having assurance for retrieving a file stored by a provider in the consortium sends a signed AssuranceProposal to the provider (or list of providers). The proposal specifies the quantity payment that is going to be paid by the client to the provider if no appeal is made, the duration of the deal and the collateral which specifies how much from the provider account is penalised in case of a slashing appeal. If the proposal is accepted, the provider responds with an signed accept message to the client.

Note, payment from the client’s account is locked down;
~~we need to check that the balance in the provider’s account is higher than~~ ~~deposit_margin x payment.~~
The collateral has to be in the range :

min = payment
max = slashing_multiplier x payment
and the collateral needs to be < = available balance from the provider account

Appeal:

If a provider doesn’t answer the retrieval request, the client can appeal to the referee [note, there is max number of appeal that a client can do per deal]. To do so, the client sends an on-chain message requiring the help of the referees attaching the acceptance message from the provider. This message has a fee of committee_multiplier x payment taken from the client account to pay the referees (token moved to the account of the referee committee). The client initiating an appeal blocks the payment voucher for paying the provider.

Retrieval protocol:

After having seen on-chain the appeal request (note: this moment defines the origin_timestamp) and after having received the payment, the referees start the retrieval protocol. The protocol is made by k rounds (for example, 10 rounds) each one of duration round_duration, in which the referees try to retrieve the file in this way:

Step 1: a retrieval leader is elected (chosen at random). The leader asks the file to the provider.

Step 1.a: If the leader does not get the correct file within leader_waiting time from when the round started, sends a “slash msg” on chain and in the next round Step 1 is repeated (ie, another leader is elected);
Step 1.b: If the leader gets the file it forwards it to the client and the other referees. Each referee does the following:

[optional] if the correct file is received, forward it to the client];
If the correct file is not received within referee_waiting time from when the round started, sign 0 and broadcast the signed message to the committee.
Count the number of 0 messages received, if they are ≥ floor{n/2}+1, then this counts as a “slash msg” on chain and the next round Step 1 is repeated. Otherwise, skip Step 1 for the remaining rounds (ie, no further leader is elected).

After k rounds, we proceed with Step 2;

Step 2: Count the number of “slash messages” on chain, if they are k, then the smart contract to slash the provider is activated and a fee of collateral is taken for the provider’s account to be penalised; if less than k “slash message” are on chain, nothing happen.

After the deal expires, if no appeal was made on chain, the provider can redeem the voucher and gets payment.

[Comment: in the MVP we added a threshold for giving the payment to the provider. So, after the deal expires, the provider gets the payment is the number of appeals is < max_appeals and all the appeals were closed without slashing the miner.]

Leader Election Protocol

[note: no secret election for the MVP]

The leader can be identified by a simple function.
For example:

compute the hash of (deal_id + appeal_id + round_number)

[note: + is used to indicate concatenation]

interpret the hash output as an integer modulo n (check if truncation before modulo is needed in order to be sure that the result is uniform in the set {1,2,... n})

Signature Prefix

When a referee create a “slash message”, it needs to sign (deal_id + appeal_id + round_number + 0).

List of CryptoEcon Parameters

payment:

this is how much is paid by the client to the provider if a retrievability deal is closed with no appeal call.
chosen by the client for each deal;

m_c = committee_multiplier:

the quantity (committee_multiplier x payment) is the fee paid by a client to the committee each time that an appeal is made

Recommended value: 0.2
Why we need this? To prevent malicious client abusing the protocol. A malicious client can send the appeal call for honest provider making the provider working twice and not get the payment it should receive. With the committee_multiplier this strategy has a cost that makes it irrational.

Comment: for now we assume that the fee is equally split among all referees, for the future we can investigate about giving an higher split to referee recovering the file.

protocol parameter, fixed;

(NEW!!) collateral:

Chosen by the client in the deal proposal;
If an appeal fails (ie, an appeal call is closed with slashing the provider) the collateral is taken by from the provider account;
It has a minimum and a maximum allowed value:

min = payment
max = slashing_multiplier x payment

Why we need this? To punish providers that are not serving files.

m_s = slashing_multiplier:

the quantity (slashing_multiplier x payment) is maximum of the collateral that a client can ask for.

Recommended value: 1000
protocol parameter, fixed;

max_appeals:

maximum number of appeals per deal:

Recommended value: 5
protocol parameter, fixed;

~~m_d =~~ ~~deposit_margin~~:

~~a retrievability deal is proposed to providers only if the balance in the provider account is higher than (deposit_margin x payment).~~

~~protocol parameter (but we could make the client choose it for each deal?!)~~
~~note:~~ ~~m_s~~ < ~~m_d~~
~~Possible value: ??~~
~~Why we need this? We want to have some guarantee that if we have to slash the provider, there is enough funds in its deposit account to cover the the quantity (slashing_multiplier x payment).~~

[~~Comment/need discussion]: we could have a per deal collateral (instead of a per provider collateral) to but it would be less efficient (1 on-chain msg per deal)~~ and we think it is not required. Indeed, in practice the per provider collateral can work well if the clients check that there is some margin (eg 10x) between the balance and the burn fee. Also, in the future we can set an additional measure of “provider in debt”, and say that if I need to slash a provider that has no enough collateral, the balance become negative and the provider can not take new deals of payment for existing deals until it repays his debt.

Security analysis:

Assumption (”honest majority”): at least h = floor[n/2]+1 of referees are honest.

Security against a malicious provider:

each one of the k leader will sign a slash message and the miner will be slashed;
malicious provider + malicious referees: If the provider is lucky in one round and the leader is colluding with him, the following vote for the referees will still produce a slash message.

Security against a malicious client (ie, even when the client acts maliciously, an honest provider is not slashed):

a malicious client sending the appeal request anyway makes the honest provider works twice and not get thepayment it should receive. However this costs an extra payment to the client, making this strategy irrational.
malicious client colluding with malicious referees: in this case the colluding referees may send back their part of the payment fee to the client making this attack cheaper, but even in this case the honest provider does not get slashed with high probability. Indeed, if there is at least 1 round where the leader is honest, then the retrieval is successful and the there is no slash message on chain.

Pr(all k leaders are malicious) = (1-h)^k < 1/2 ^k
If k ≥ 10, the probability above is quite small.