The problem of fair exchange arises often in business transactions — especially when those transactions are conducted anonymously over the internet. Alice would like to buy a widget from Bob, but there’s a circular problem: Alice refuses to pay Bob until she receives the widget whereas Bob refuses to send Alice the widget until he receives payment.
In a previous post, we described the fair-exchange problem and solutions for buying physical goods using Bitcoin. Today is the first of two posts in which we focus on purchasing digital goods and services. In a new paper together with researchers from City University of New York and IMDEA Software Institute, Madrid, we show that Zero-knowledge contingent payments (ZKCP), a well known protocol for the fair exchange of digital goods over the blockchain is insecure in its current form. We show how to fix ZKCP, and also extend it to a new class of problems.
To illustrate the problem, consider Alice, an avid fan of brainteasers who is stumped on a Sudoku puzzle. After days of trying to figure out the solution, she gives up and posts the puzzle on an online message board proclaiming, ”I will pay whoever provides me the solution to this puzzle”. Bob sees the message, finds the solution, and would like to sell it to Alice.
We focus on the class of problems for which the buyer can write a program to verify the authenticity of the digital good they wish to purchase. In the Sudoku example, even though Alice does not know the solution to the puzzle, she can still write a program that verifies the solution as this only requires knowing the rules of Sudoku.
In 2011, Greg Maxwell introduced what would later become known as Zero-Knowledge Contingent Payments, a protocol for trustless fair exchange of this class of problems. We won’t go into the full details of the protocol in this post, but the important part for our purposes is that the seller must provide the buyer with a zero-knowledge proof showing that he has a correct solution.
When Maxwell first proposed ZKCP in 2011 it was only theoretical as there was no known efficient general purpose zero-knowledge protocol that could be used to generate the necessary proofs. Since then, however, advances have been made in this area, and there are now general-purpose Succinct Non-Interactive Arguments of Knowledge (ZK-SNARK) that allow for the practical implementation of the necessary proofs. Maxwell therefore refined his protocol to use SNARKs, and Sean Bowe provided a proof-of-concept implementation for the Sudoku problem. Bowe and Maxwell demonstrated the implementation at the 2016 Financial Cryptography Conference.
We show, however, that the current SNARK-based instantiation of ZKCP is insecure. SNARKs require a trusted setup, which is often problematic in practice. Addressing this issue, Maxwell notes:
The GGPR’12 cryptosystem requires a trusted setup, but for the ZKCP application this is no real limitation since the buyer can perform it. [source]
At first glance, this reasoning seems sound. If the buyer performs the trusted setup, we know that the seller cannot cheat and produce false proofs. But as we will show, there is a flaw with this reasoning.
ZKCP using SNARKs as shown in the FC’16 demo slides. pk, and vk are the trusted parameters that are generated by the Alice, the buyer. [source]
A zero-knowledge proof system has two main properties that need to be preserved: soundness and zero-knowledge. The soundness property states that the prover cannot generate false proofs that convince the buyer of something untrue. The zero-knowledge property states that the proof leaks no information about the inputs other than the statement that is being proven.
In SNARKs, the trusted setup is required to achieve both of these properties. If a malicious party generated the trusted parameters, there is no guarantee that the proof system is either sound or zero-knowledge.
Let’s now consider our Sudoku problem once more. Recall that each party wants to make sure that it doesn’t get cheated by the other party. Thus, when considering who the adversary is in the above protocol, it really depends on whose view we consider. To Alice, a malicious Bob is the adversary as he may try to have Alice pay him even though he does not know a solution to the Sudoku. To Bob, however, a malicious Alice is the adversary as she may try to learn the Sudoku solution (or any part of it) without paying Bob.
A fair exchange protocol must protect against both of these potential adversaries, and indeed these adversaries each map to one of the two properties of zero-knowledge proofs. The soundness property ensures that Bob cannot falsely convince Alice that learning the he has the correct solution to her problem. The zero-knowledge property ensures that Alice can learn nothing about the solution from the proof that Bob provides.
The importance of these two properties to this double-adversarial model is exactly why the buyer cannot perform the trusted setup. While this guarantees that the seller cannot create false proofs, it allows a malicious buyer to generate the trusted parameters in a special way that allows her to break the zero-knowledge property. Alice, in our Sudoku example, can set up the system in a way that Bob’s proof leaks information about the solution. Thus she can learn part of the solution without paying for it, and this is clearly not a fair-exchange.
In the paper, we show concrete attacks that allow Alice to learn information about the solution to demonstrate that the zero-knowledge property is broken. We also provide code that implements a malicious buyer in the sudoku example. Our code interacts with Bowe and Maxwell’s unmodified seller code and allows the buyer to learn part of the Sudoku solution without paying.
Maxwell’s initial proposal of ZKCP is not broken; what is broken is the SNARK-based instantiation that trusts the buyer to perform the setup. We show a few mitigations in the paper of how one can regain the zero-knowledge property and perform secure zero-knowledge contingent payments.
In a follow-up post, we will demonstrate a second contribution of our paper: how we extend ZKCP to a new class of problems that were not realizable by the original protocol.
