Is there a cryptographic protocol that let's me prove someone has a large binary?

Question

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?

Answer 1

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$.