<aside> ⚠️ 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

</aside>

MVP Protocol

Parties:

• Storage Providers
• Clients
• Blockchain

<aside> 📌 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).

</aside>

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.
  1. Note, payment from the client’s account is locked down;
  2. we need to check that the balance in the provider’s account is higher than deposit_margin x payment.
  3. 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