3.2.2.1 Payment

If our scheme was modified to use a hybrid peer-to-peer model where a company charged money to use the software, collecting payment would be easy: just add an extra amount to the monthly bill. Likewise, if low-cost electronic financial transactions were available (e.g., digital cash), payment could consist of a straightforward transfer of money between the attacker and the hurt parties or a suitable charity.

Because we wish to allow for a decentralized peer-to-peer system with almost no administration beyond keeping the matching server running and do not believe low-cost transactions are likely to become available anytime soon, we consider here a different way to make attackers pay: disk-space wasting.

The idea behind disk-space wasting is that we need to impose a cost that balances out the benefit the attacker stands to gain, in this case 2 weeks of a partner holding $s$ blocks of his data. How much is this benefit worth? Clearly, no more than it would cost to obtain it from the next cheapest source, namely our scheme used honestly: the effort required to host $s$ blocks for 2 weeks. Thus forcing someone to waste $s$ blocks of disk space for 2 weeks cancels any benefit they might receive from abusing the grace period.

Assuming computers $\cal A$ and $\cal B$ are already swapping $s$ blocks, $\cal A$ can pay such a cost to $\cal B$ by holding an additional $s$ blocks for $\cal B$ for two weeks, by holding an additional $2{\times} s$ blocks for one week, or by allowing $\cal B$ to hold $s$ fewer of $\cal A$'s blocks for two weeks. The previously described protocols are used to allow $\cal B$ to read, write, and check on her additional blocks. Note that in the fewer blocks case that $\cal B$ is no longer holding $\cal A$'s backup data for the duration, leaving $\cal A$ with one fewer effective backup partner. Also notice that unlike the monetary-payment cases, disk-space payments take time to make--one or two weeks in the examples here.

Such payments may benefit $\cal B$ because she has more storage available to her, and thus represent a transfer of value from $\cal A$ to $\cal B$. A different kind of payment is a commitment-cost payment where $\cal B$ ensures that $\cal A$ either pays an unrelated third party (e.g., a charity in the monetary-payment case) or else simply wastes resources (the disk-space-wasting case). We can convert the previous transfer examples into commitment-cost payments by using low-utility blocks.

A low-utility block is a normal block whose access has been sufficiently restricted so that it is of little or no utility to its lessee. For example, the lessee might be allowed to write any time, but be able to read only an occasional random one of its low-utility blocks for checking purposes. More draconian would be allowing only reads of random words. A transfer can be turned into a commitment-cost payment by either making the additional blocks held be low-utility blocks or by instead of having the partner hold $s$ fewer normal blocks, have her convert those $s$ normal blocks to low-utility blocks for the duration. The low-utility-block lessee stores uncompressible (i.e., encrypted) data in those blocks and checks a random block (or word) periodically to ensure that the data is being kept. The parties must mutually agree on the random block (or word) to be read--see Section 3.3.1 for a protocol to do this--to guard against the lessor always presenting the same block for inspection.

Because we believe that most PCs will not have enough space to hold a large number of extra blocks beyond the ones already needed for backup space, we will assume for the rest of this paper that the ``allow your partner to hold $s$ less normal blocks'' cases are used for disk-space wasting. While this requires no extra space, it does have the drawback of leaving a PC with no backup while it is paying multiple partners. As an optimization, PCs paying commitment costs may continue to backup their data onto their (temporarily) low-utility blocks so that it is immediately accessible once payment is complete and the access restrictions are removed; this optimization is incompatible with restricting access to random words because only entire backup blocks are verifiable.