4
$\begingroup$

I'm working on a system that has a P2P component. When an individual downloads a binary and decides to mirror it, they advertise themselves in a providers set. The binaries can range from 1-1000MB. I need a mechanism to prevent the abuse use case where they flood the provider set without ever having the binary, and serving up bad data.

The client trying to prove the blob only has some small metadata about the blob <1MB. They need to ensure that the provider actually has the blob before initiating download.

Alice, Bob, and Malorie

Alice, Bob, and Malorie are trying to share large files. Both Alice and Bob have high bandwidth links to Malorie. There also exists an unencrypted HAM radio link between the three agents, so Malorie can see everything Bob and Alice send to one another.

Sometimes Malorie lies. Everyone knows the SHA1 hash of the file. Bob shares the file with Malorie. How can Alice check if Malorie has the file once Bob goes offline, without transmitting the entire contents of the file from Bob to Alice?

Is there a protocol for this?

Improve this question
$\endgroup$
4
  • $\begingroup$ Is it possible for Malorie to have the file even if she did not recieve it from Bob, or could she have it from a source outside of your system? In other words, is Malorie not being able to prove she received the file from Bob (or another provider) a "fair" restriction on her being able to advertise herself in the set? $\endgroup$
    – sju
    Commented Oct 9, 2015 at 4:33
  • 1
    $\begingroup$ I don't have a full answer but I feel like a Merkle tree could probably tackle this kind of problem, maybe as part of some randomized protocol. Maybe someone else is more familiar with this. $\endgroup$
    – Thomas
    Commented Oct 9, 2015 at 4:36
  • $\begingroup$ maybe you try a google search for "provable data possession" $\endgroup$
    – user27950
    Commented Oct 9, 2015 at 5:29
  • $\begingroup$ Related question: Proof of storage scheme $\endgroup$
    – CodesInChaos
    Commented Oct 9, 2015 at 7:54

1 Answer 1

Reset to default
1
$\begingroup$

Like Thomas suggests in the comments, a Merkle tree would help here. As would a simple hash list.

Calculate the hash tree/list over suitably sized blocks of the file and let the recipient know it. As data comes in it can be verified to match. With file size $n$, block size $b$ and SHA-256 as the hash, a hash list takes about $n/b \cdot 256$ bits. So with up to gigabyte files you would want to use at least 2 MB blocks to keep the metadata below 1 MB.

This is similar to how BitTorrent works.

If you need to verify someone has the file you can request they produce a random block. If they have fraction $p$ of the blocks, they will be able to do it with probability $p$, so if that is a problem you can request $m$ blocks for a probability $p^m$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.