A primer on the Fair Exchange Problem

Selling goods and services is all about trust. You are able to sell your worn and used guitar to someone on the other side of the globe, and be sure that he will pay you conveniently because there is a third-party (let’s call it eBay for now), orchestrating the exchange. Of course, our friend eBay is also being paid for his mediation services. But what if we had to go without this third-party for the exchange, what would be the outcome? The conversation would go something like this:

• Me (the seller): “I am selling this awesome guitar that has served me well in many of my gigs since 1992”
• Alice (the buyer): “Really cool! I pay you 240$ for it”.
• Me: “400$”
• Alice: “300$”
• Me: “Deal!”
• Alice: “Ok, this is my address, ship the guitar and the moment I receive it and check everything is alright I’ll send you the payment”
• Me: “No way! How can I be sure that you will pay me then? First, send the payment, and then I send the guitar”
• Alice: “And how can I be sure that you’ll send the guitar and you don’t want to stick with it?”
• Me: “So what do we do?”
• Alice: “Let’s call our friend eBay to mediate between us”.

You see where I am trying to get at, right? I don’t personally know Alice, and in order for us to be able to go through the exchange, there needs to be a minimum level of trust. There will always be an unbalance in the exchange for the party that sends its part first, because he can’t be sure that the other will fulfil its part of the bargain. This, my dearest readers, is the problem of fair exchange, and there are companies out there such as eBay (and think of any other second-hand marketplace) earning a lot of money with this problem.

On the need of third-parties

As early as 1999, this paper already showed the impossibility of performing a fair-exchange without a third party. As stated in the paper: An exchange is fair if, at the end of the exchange, either each player receives the item it expects or neither player receives any additional information about the other's item.

So that’s it? End of story? We will have to be depending on the eBays of the world to perform fair exchanges forever? That could have seemed that way until 2008, but on the 31st of October of that year, the whitepaper for a third-party everyone could trust was released. You guessed right, I am referring to Bitcoin and blockchain technology.

Bitcoin was designed to remove some of the largest third-parties there are in the financial system, central banks. And the same way Bitcoin is able to supersede central banks, it can also become our more than needed third-party to perform fair-exchanges.

Fair exchange of digital woods

Now that I got you hooked on this fair-exchange problem, you may be wondering can we leverage Bitcoin to perform a fair exchange. The answer to this is a protocol called Zero Knowledge Contingent Payments (a.k.a ZKCP protocol). To illustrate how the ZKCP protocol works, we are going to consider a good more easily digitized than a guitar such as the solution to a Sudoku puzzle. This is actually the toy example you will recurrently find in the fair-exchange literature published on ZKCP protocols.

In this example, Alice sends the sudoku puzzle P to Bob. Bob is able to find a solution S to P, and wants to sell it to Alice. Alice is willing to pay for the solution because the sudoku was hard as f... really hard. But how can she indeed be sure that Bob managed to find the right solution before she sends her payment? And the other way around, how can Bob show he has the right solution without leaking any information about the solution? We are facing this evil problem again.

Before we jump into how ZKCP protocols work, let’s make a small detour to explain hash-lock transactions for those of you unfamiliar with the concept. A Hashlock is a type of encumbrance that restricts the spending of an output until a specified piece of data is publicly revealed. So with a hashlock transaction, Alice will be able to send a payment that can only be redeemed by someone able to reveal the secret pre-image to the hash used to lock the transaction. Thus, if Alice locks the transaction with SHA256(d), only someone disclosing d will be able to access the payment.

Hashlock transactions are one of the building blocks of a ZKCP protocol. The other one is zero-knowledge proofs. A zero-knowledge proof lets someone prove a mathematical fact to another person without teaching them anything about the fact itself. Now we are ready to introduce ZKCP protocols.

Zero-Knowledge Contingent Payments

The step of a ZKCP protocol are generally the following:

• When Bob finds the solution S to the Sudoku, it encrypts it with a symmetric key k, c = Enc_k{S}. It then computes the hash for that key, y = SHA256(k), and generates a zero-knowledge proof showing that the ciphertext c was indeed encrypted using a key k whose hash is y, and that S is the solution of the puzzle P, i.e. the proof shows thatSHA256^-1(k) = y; Enc_k ^ -1 = c; Sol(P) = S..
• Bob then sends the ciphertext, the hash of the key, and the generated proof to Alice, (c, y, proof). At this point, Alice has the encrypted solution of the Sudoku, and a proof that validates that what it is hidden behind the ciphertext is the solution that Alice is looking for.
• Alice, convinced that the solution is correct, sends a hashlock transaction where the lock is y, SHA256(k), so Bob will have to reveal k in order to access the payment, revealing the encryption key of the solution sent in the process.
• Alice can then grab k and recover S from the ciphertext and be happy with her solution to the hard Sudoku. Time to show off!

There you go! With this ZKCP protocol and the help of Bitcoin, we managed to perform a fair-exchange of a digital good. The blockchain became our third-party mediating the exchange. If you want to go deep into the internals of ZKCP protocols I’d suggest starting with this paper. If you still want more, ping me and I can share more references (this has been a topic I’ve been extensively reading about these past few months).

Do you want to also tinker with some code? Here are a few implementations of ZKCP protocols (I haven’t tried them myself yet, but let me know if you do, I’d be interested in knowing your thoughts):

• https://github.com/zcash-hackworks/pay-to-sudoku
• https://github.com/matteocam/zkcsp-over-bitcoin

Any blockchain can be your third-party

Some of you may be wondering, can we have a ZKCP protocol over any kind of blockchain network, not only Bitcoin? Of course, as long your blockchain network supports hashlock transactions or smart contracts you are covered. Actually, let me briefly share a paper that proposes an alternative to a ZKCP protocol to perform a fair-exchange over the Etheruem blockchain using no zkSNARKs: FairSwap: How to fairly exchange digital goods.

The paper proposes an optimistic approach to the exchange. In this approach, the blockchain orchestrates the exchange but really comes into action only when there is a dispute between the two parties. Oversimplifying it a bit, the protocol would operate as follows for our sudoku example:

• The seller S encrypts the solution to the puzzle and generates some additional information that the buyer can use to verify the integrity of the information sent (this time it doesn’t necessarily need to be zero-knowledge proof, it can be partial outcomes from a Merkle Tree as proposed in the paper). S then sends this auxiliary information and the ciphertext of the solution to R (step 1a in the figure).
• S then sends the hash of the key used to encrypt the solution to the judge contract (step 1b).
• With the information received, the buyer checks that the commitment received and the complementary information to the auxiliary data to be used in case of the dispute are conveniently registered in the judge contract. If this is the case, the buyer R accepts the deal and sends the payment for the solution to the judge contract (step 2).
• S then reveals the key to the judge contract for R to see it. R recovers the solution from the ciphertext with the key and performs the pertinent verifications. If everything is fine, R sends an “ok” message to the judge contract to release the payment. If there was some misbehaviour from S, R can complain to the judge contract showing some proofs for the misbehaviour of S. These proofs are generated from the auxiliary verification information initially sent by S to R, and registered in the judge contract in steps 1a and 1b. If the complaint is successful, R recovers his funds without any harm, but if R was trying to cheat with its complaint, the payment is sent to S (as it was supposed). (step 4)
• But wait, what happens if R disappears and never tells the judge contract if the exchange was ok or not? After some time without a response from R, S is able to finalize the exchange and recover its funds without having to wait for R. Fair exchange performed (step 5).

In this case, the judge contract was the one responsible for orchestrating the fair exchange, and we didn’t need any hashlock transaction or zero-knowledge proofs. I’ve hidden some of the details of the protocol, but you can always check the paper shared above to get a better understanding of what is happening under the hood. But there you go, another example of a fair exchange protocol leveraging the capabilities of blockchain networks.

Fair exchanges are possible!

I really hope you’ve enjoyed this brief introduction to the decade-old problem of fair exchange. Research on new cryptographic protocols and constructions to make efficient fair-exchanges using blockchain networks is booming, so do not hesitate to have a quick look at all the exciting work being done in this field. Fair exchanges without trust are impossible without involving a third party, so we better select the third-party wisely. Fortunately, as shown in this publication, blockchains can be our best third-party friends.

Sign up to Blockchain Works for more articles, jobs and open source issues!