So Sarchar and I were talking about his Bitstorage scheme(1) and we came
to the conclusion that it wouldn't work. However he came up with a less
abitious idea that I thought would work: force people to prove they were
still holding your data D by publishing transactions with scriptPubKeys
of the form:

    HASH160 H(D[i:i+n]) EQUALVERIFY {<pubkey> OP_CHECKSIG}

Where pubkey optionally lets you pick a specific person to hold your
data. (so the scheme isn't restricted to miners - hash-only
scriptPubKeys aren't secure) Basically you'd publish the data and store
a much smaller random set of D[] samples. If you ever needed the data in
full, you know it's out there, so it's just a matter of haggling on the
price to get it back. (you may want to do some dry-runs for negotiation
leverage...)

However, I realized you can improve upon this greatly by deriving the
ECC privkeys from the random samples of data instead using H(E_k(D)),
that is, use a block cipher with key k, and then hash that to form the
privkey. Then create a perfectly normal txout paying to the appropriate
pubkey. Now only people who actually have the data can claim the txout,
and everyone doesn't even know the scheme exists at all.

Furthermore you can create key k using k_i=HMAC(i, K), where i in [0,
n], so rewards for the proof can be released incrementally while only
storing a single secret key. Again, actual retrivial isn't necessarily
guaranteed, but the odd dry-run is simple enough.

One last issue is how to distribute k_i, although this is made easier by
the fact that they can be tiny 128-bit numbers - they should however be
signed to avoid DoS attacks as only by processing all the data can the
storage node know if k_i works for the given txout.


1) https://bitcointalk.org/index.php?topic=348868.new#new

-- 
'peter'[:-1]@petertodd.org
00000000000000056738baba2d1f0fb2638555529e0735e41e1ce9e0c946d48a