Alice pays Bob $5/month to host a gigantic file for her. She wants to occasionally verify that Bob is actually hosting the file. To do this, she selects random blocks from the file, and challenges Bob to hash those same blocks with her chosen salt. The digests should match.

This is a solved problem because Bob won't know what blocks in the file Alice will audit next. But what can be done if Bob decides to host in multiple places?

Bob proposes to Alice that he can host the file on four more hosts, for a total of $25/month. Alice agrees, and continues using her old audit method. But Bob never actually hosted the files in more than one place; every time Alice audited a host without the file, that host asked Bob's main host for the answers, and sent them to Alice.

  • $\begingroup$ Alice can get a very low ping connection to one of the places and require that she receives a response faster than it would take for a light-speed signal to go back and forth between that place and the closest other relevant place. $\;$ $\endgroup$ – user991 Jul 10 '14 at 15:46
  • 1
    $\begingroup$ Or she could store different copies of the data encrypted with e.g. separate keys. Since Bob knows neither the plaintext nor the keys, he can't show a hash of the ciphertext without storing all the copies. $\endgroup$ – otus Jul 10 '14 at 23:06
  • $\begingroup$ @otus This requires sending to Bob $m$ encryptions of the same file, where $m$ is the number of mirrors. $\endgroup$ – Dmitry Khovratovich Jul 11 '14 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy