Research Summary - Fair exchange via Contingent Payments

Can two parties who do not trust each other exchange (digital) goods in a way that makes both satisfied?

This is known as the fair exchange problem, which consists of ensuring that both parties receive what they expect, avoiding the undesirable situation in which one them refuses to collaborate after having obtained what they wanted.

To illustrate this problem, consider the following classical example. Alice is willing to pay $1 in order to obtain the solution to a Sudoku puzzle, which Bob claims to have. If Alice sends the money up front, she is not guaranteed to obtain the solution from Bob afterwards. On the other hand, if Bob sends her the solution first, what if Alice does not perform the payment?

They could resolve this deadlock situation by having a third party (trusted by both of them) acting as a mediator. However, what can they do if they do not want to rely on such an intermediary? Actually not much! The problem of fair exchange was proven [3] to be impossible to solve without trusted third parties… Or can they?

Leveraging the Blockchain: Contingent Payments

Despite the known impossibility results, recent works leverage the blockchain as a trusted third party to approach fair exchange. Thanks to the decentralized nature of blockchain-based cryptocurrencies, these new approaches provide a great balance between trustability and security.

A naive approach would be to directly use smart contracts to enforce the payment whenever a solution to the puzzle is published. However, this would not be completely satisfactory:

  • Smart contracts cannot access external data on which the execution of the business logic may depend. (There is another post in this Forum which shows how this limitation could be overcomed with so-called blockchain oracles: https://www.smartcontractresearch.org/t/a-study-of-blockchain-oracles)

  • The secret being sold (that triggers the payment) would be publicly available after the transaction is finished. Clearly, this may be undesirable for many applications.

  • Many popular cryptocurrencies do not support a general scripting language which can capture the desired policy (e.g., that can check whether the Sudoku solution is valid). This is the case of Bitcoin, which supports a very limited language (although it has recently been extended). Namely, Bitcoin supports so-called hash-locked transactions [7], which allow a user to lock an amount of money that will be paid to whoever provides a SHA2 preimage of a value chosen by the user.

TLDR Here comes the idea of zero-knowledge contingent payments (zkCP), first defined and studied by Maxwell in 2011 [6], who developed a protocol for fair exchange, based on the limited scripting language provided by Bitcoin.

Citation

  • Ky Nguyen & Miguel Ambrona & Masayuki Abe. 2020. WI is Almost Enough: Contingent Payment All Over Again. In ACM CCS 2020, Jonathan Katz and Giovanni Vigna (Eds.). ACM Press, 641-656.

Link

Core research question

  • Can fair exchange be implemented in an efficient and secure way that is practical for real world applications? (On top of a blockchain system with a restricted scripted language.)

Background

As we explain below, in order to use the SHA2 preimage functionality to implement fair exchange for more general predicates, zero-knowledge (ZK) proofs of knowledge are needed.

When the notion of zkCP was first introduced, there was still no generic ZK proof system
that was practical enough to implement complex predicates. In 2016, after several improvements in the field of SNARKs (succinct non-interactive arguments of knowledge), Bowe proposed the first realization of zkCP [1], implementing a protocol for selling 9 x 9 Sudoku puzzle solutions (as a proof of concept), based on SNARKs. In this implementation, Bowe lets the buyer (the verifier) generate the common reference string (CRS), a structured piece of information that is used to both generate and verify proofs (which is supposed to be honestly generated). This is supported by the claim that the seller (the prover) cannot violate soundness (prove a false statement) since it has not participated in the CRS generation.

However, in 2017, Campanelli et al. [2] discovered a vulnerability in Bowe’s implementation. In a nutshell, they show how a malicious buyer can generate the CRS in a way that allows them to learn information from the ZK proof without performing the payment (specifically they implement an attack that recovers one cell of the Sudoku solution for free). They also proposed several repairs that involve performing some β€œminimal” checks on the generated CRS. Furthermore,they designed an alternative protocol that would rely on witness indistinguishability (WI) instead of the stronger zero-knowledge property, potentially leading to more efficient protocols.

Nevertheless, in 2019, Fuchsbauer [4] showed that WI was not enough for security in the protocol proposed by Campanelli et al. [2], proposing an explicit attack. Furthermore, he concluded that the minimal checks on the CRS proposed in the same work were not enough for security either and proved that some significantly more involved integrity checks needed to be performed, with an estimated running time of more than 1 hour for the simple Sudoku functionality.

:mag: After such a series of works, it was still not clear how zkCP could be efficiently implemented in a secure way, even for the toy example of selling Sudoku solutions.

Results

This work pursues the study of contingent payment in several directions:

  • It presents formal security definitions for contingent payment, abstracting the needs of both parties (the buyer and the seller) as cryptographic security games.

  • It presents a new security notion called trapdoor subversion witness indistinguishability (tS-WI), and shows that it is enough for the security of the protocol proposed by Campanelli et al. [2] (according to the above security definitions).

  • It proposes a new approach to implement the ZK proof system (other than SNARKs), by extending an interactive protocol from the literature.

  • It presents an implementation (available here) of the mentioned interactive protocol, running experiments that concern selling ECDSA and RSA signatures on a contract. In the case of ECDSA signatures, the whole protocol can be executed in less than 150 ms over a LAN, with less that 5MB of transmitted data.

Method

Consider the scenario where a buyer is willing to pay certain amount of Bitcoins in exchange for a value β€œs” such that f(s) = 1 for certain predicate β€œf”. In order to extend the SHA2 preimage functionality provided by Bitcoin to perform contingent payment for this predicate, we can proceed as follows:

  1. The seller, who knows β€œs”, will encrypt the secret under certain freshly generated key β€œk”, producing c = Enc(k, s), and will hash the key, producing y = SHA2(k). Sending (c,y) to the buyer.

  2. The seller will prove in ZK knowledge of a witness for the following relation:

            

  1. When the buyer is convinced that the seller knows a SHA2 preimage of β€œy” which decrypts β€œc” to a value that satisfies β€œf”, the buyer will perform a hash-locked transaction under value β€œy” for the agreed amount.

  2. As soon as the seller unlocks the transaction by publishing β€œk”, the SHA2 preimage of β€œy”, the buyer will learn β€œk” and, consequently, β€œs”, as desired.

The main challenge is to realize the above ZK proof efficiently for the desired functionality β€œf”. Given that, for fair exchange, the zero knowledge proof need not be non-interactive nor succinct, this work explores an alternative to SNARKs. In particular, it extends a ZK protocol [5] based on garbled circuits to support hybrid statements (that depend on an algebraic part, e.g., a ECDSA verification; and a non-algebraic part, e.g., the evaluation of SHA2). More details can be found in the paper.

Discussion & Key Takeaways

  • After recent developments in the area of ZK proofs and the emerging blockchain based technologies, it has become possible to perform fair exchange in an almost trustless manner, something that a decade ago would have been considered to be science fiction.

  • However, securely implementing zkCP is a challenging and error-prone task, as evidenced by the series of invalid attempts from the literature.

  • Interactive protocols are a good alternative to SNARKs for this specific application of ZK proofs.

Implications & Follow-ups

  • This work tried to leave the toy example of selling Sudoku solutions and proposed a new application of zkCP: selling digital signatures on a document.

  • It would be good to explore other more complex functionalities and investigate how they can be efficiently realized in practice.

Applicability

It would be very interesting to know whether someone from the industry would find this work useful for some actual application. If you do have an answer to the following question, please leave a comment below!

:grey_question: Is there a scenario where selling digital goods without relying on trusted intermediaries is of critical importance? What would be those goods and can their validity be modeled as an NP-relation?

References

[1] Sean Bowe. 2016. Pay-to-sudoku. GitHub - zcash-hackworks/pay-to-sudoku: Pay for the solution to a sudoku puzzle with a zero-knowledge contingent payment.

[2] Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, and Luca Nizzardo. 2017. Zero-Knowledge Contingent Payments Revisited: Attacks and Payments for Services. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, 229–243. https://doi.org/10.1145/3133956.3134060.

[3] Richard Cleve. 1986. Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract). In 18th ACM STOC. ACM Press, 364–369. https://doi.org/10.1145/12130.12168.

[4] Georg Fuchsbauer. 2019. WI Is Not Enough: Zero-Knowledge Contingent (Service) Payments Revisited. In ACM CCS 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, 49–62. https://doi.org/10.1145/3319535.3354234.

[5] Marek Jawurek, Florian Kerschbaum, and Claudio Orlandi. 2013. Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. In ACM CCS 2013, Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung (Eds.). ACM Press, 955–966. https://doi.org/10.1145/2508859.2516662.

[6] Gregory Maxwell. 2011. Zero Knowledge Contingent Payment. Zero Knowledge Contingent Payment - Bitcoin Wiki.

[7] The Bitcoin Wiki. 2019. Hashlock. Hashlock - Bitcoin Wiki.

8 Likes