The condition of the problem and the statement of the problem: Alice pays Bob for the fact that he, at the request of users, gives out files of interest to users. For example, the user is interested in the file #hash1. The user learns from Alice that this file is stored by Bob. The user connects to Bob and asks to start downloading the file #hash1 to his computer. Then there are two possible bad outcomes. Either Bob is dishonest and refuses to transfer the file to the user, or the user is dishonest and, after receiving the file #hash1 from Bob, lies to Alice and tells her that Bob did not send him anything.

My question is: are there any algorithms in cryptography that Alice will be able to determine the truth and not pay money to Bob (if he lies) or not stop cooperating with Bob (if the user lies)? At least partially. Thank you.

Personally, I thought that my problem relates to the topic of fair exchange (when the two sides exchange bit by bit interesting information and if one side begins to behave dishonestly, the second party immediately stops exchanging and the damage for it is minimal). However, this does not solve the problem that the user can simply lie and say that Bob did not send anything. I just want to know if it's possible to control the work of a third-party server for Alice.


Some partial idea: You want to avoid a situation where the user receives the file and claims they didn't.

Bob adds some random padding to the file so that the user doesn't know the size. Bob sends part of the data and waits for a receipt, then sends more data and waits for a receipt. When the file is sent completely, the user doesn't know this. So refusing to send the receipt means they might never get the complete file. When Bob claims the whole file has been received, the user contacts Alice, who has a key to unlock the file.

  • $\begingroup$ Clever idea. I do see one challenge. Consider scenario A, where a malicious Bob who sends the honest user nothing. Now consider scenario B, where a honest Bob sends the malicious user the real file, but the user claims to have not received anything. These scenarios are indistinguishable. Should Alice pay Bob or not? If Alice pays Bob, then a malicious Bob can get paid for doing nothing. If Alice doesn't pay Bob, then a malicious user can prevent Bob from getting paid anything. $\endgroup$ – D.W. May 22 '18 at 1:15
  • $\begingroup$ Perhaps you could partly address this by breaking the file into many small blocks and requiring the user to send a signed receipt after each block, and pay Bob per block delivered? That way Bob might have to send at most one extra block without getting paid, which might be tolerable. But a malicious Bob could still refuse to send the last block of the file and get paid for all but one block of the file, while leaving the user with nothing useful. Bob has no economic incentive to do that, but it allows a malicious Bob to screw over targeted users. $\endgroup$ – D.W. May 22 '18 at 1:15
  • $\begingroup$ Some other details that are probably necessary: (1) the file needs to be encrypted by Alice, under a key not known to Bob (easy enough to achieve), (2) the file needs to be divided into many blocks and Bob needs to require the user to provide a receipt after each block. We need many blocks so the user doesn't guess at which point they have enough and refuse to send Bob a receipt at that point. $\endgroup$ – D.W. May 22 '18 at 1:16

Cryptography probably isn't especially useful for enabling Alice to tell whether the user got the right file, but it is useful for enabling the user to tell whether they got the right file. For instance, Alice can give the user a cryptographic hash of the file to download, and the user can check that what he downloaded matches the hash Alice gave him. Alice can also sign her files.

I don't know of any way that cryptography can allow the user to prove he didn't get the right thing from Bob. As a simple case, suppose the user claims he received nothing from Bob. How are we to distinguish the case where the user is honest and Bob didn't send anything, vs the case where the user is lying and Bob did send it? (Or vs the case where Bob did send it but the user turned off their computer first and thus didn't receive anything; or where Bob did send it, but the user's network connection was down and thus the user didn't receive it.) These seem indistinguishable.

You might be able to use fair exchange to let the user pay Bob for sending the correct file, in such a way that Bob gets paid iff he delivers the file to the user; that seems achievable. It would be plausible that Alice could give the user digital currency, which the user then spends with Bob in exchange for receiving the file from Bob. You could arrange so that the currency is only useful for spending at Bob, and perhaps only for spending to download that particular file. Thus the money is coming from Alice and it doesn't cost the user anything, and Bob does get paid. I'm not going to try to work out the details but you could read about fair exchange and if you're still stuck on how exactly to achieve that, ask on Crypto.SE.


Your Answer

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

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