Zero-Knowledge Contingent Payments Revisited
Published 27 October 2017
Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, Luca Nizzardo
Citations120
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An attack is shown that allows a buyer to learn partial information about the digital good being sold, without paying for it, and ways to fix this attack that do not require a trusted third party are presented.
Abstract
Zero Knowledge Contingent Payment (ZKCP) protocols allow fair exchange of sold goods and payments over the Bitcoin network. In this paper we point out two main shortcomings of current proposals for ZKCP, and propose ways to address them.
Keywords
Computer Science
SSRN Electronic JournalBitcoin: A Peer-to-Peer Electronic Cash System
11,175 Citations2008Spongebob Squarepants
This document focuses on proofs-of-work security, specifically around double-spending and smart-contracts.
Ethereum: A Secure Decentralised Generalised Transaction Ledger
5,312 Citations2013Gavin Wood
Protocols for secure computations
3,014 Citations1982Andrew Chi-Chih Yao
Lecture notes in computer scienceShort Signatures from the Weil Pairing
2,950 Citations2001Dan Boneh, Ben Lynn +1 more
Foundations of Computer ScienceProtocols for secure computations
2,715 Citations1982Andrew Chi-Chih Yao
The author gives a precise formulation of this general problem and describes three ways of solving it by use of one-way functions, which have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc.
Pors
1,856 Citations2007Ari Juels, Burton S. Kaliski
This paper defines and explores proofs of retrievability (PORs), a POR scheme that enables an archive or back-up service to produce a concise proof that a user can retrieve a target file F, that is, that the archive retains and reliably transmits file data sufficient for the user to recover F in its entirety.
Zerocash: Decentralized Anonymous Payments from Bitcoin
1,829 Citations2014Eli Ben Sasson, Alessandro Chiesa +5 more
This paper formulate and construct decentralized anonymous payment schemes (DAP schemes) and builds Zero cash, a practical instantiation of the DAP scheme construction that is orders of magnitude more efficient than the less-anonymous Zero coin and competitive with plain Bit coin.
Journal of Computer and System SciencesNew hash functions and their use in authentication and set equality
1,433 Citations1981Mark N. Wegman, J.Lawrence Carter
Several new classes of hash functions with certain desirable properties are exhibited, and two novel applications for hashing which make use of these functions are introduced, including a provably secure authentication technique for sending messages over insecure lines and the application of testing sets for equality.
Lecture notes in computer scienceCompact Proofs of Retrievability
1,391 Citations2008Hovav Shacham, Brent Waters
SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies
1,186 Citations2015Joseph Bonneau, Andrew Miller +4 more
This work identifies three key components of Bit coin's design that can be decoupled, and maps the design space for numerous proposed modifications, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools.
Pinocchio: Nearly Practical Verifiable Computation
835 Citations2013Bryan Parno, Jon Howell +2 more
Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction
824 Citations2016Arvind Narayanan, Joseph Bonneau +3 more
The history and development of Bitcoin and cryptocurrencies are traced, and the conceptual and practical foundations you need to engineer secure software that interacts with the Bitcoin network are given as well as to integrate ideas from Bitcoin into your own projects.
Lecture notes in computer scienceImproved Garbled Circuit: Free XOR Gates and Applications
738 Citations2008Vladimir Kolesnikov, Thomas Schneider
In this one-round protocol, XOR gates are evaluated "for free", which results in the corresponding improvement over the best garbled circuit implementations (e.g. Fairplay) and improves integer addition and equality testing by factor of up to 2.
Lecture notes in computer scienceQuadratic Span Programs and Succinct NIZKs without PCPs
693 Citations2013Rosario Gennaro, Craig Gentry +2 more
A new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), is introduced, which is a natural extension of span programs defined by Karchmer and Wigderson.
Journal of CryptologyDefinitions and properties of zero-knowledge proof systems
601 Citations1994Oded Goldreich, Yair Oren
It is shown that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.
Witness indistinguishable and witness hiding protocols
526 Citations1990Uriel Feige, Adi Shamir
This work proves two central results: Unlike zero knowledge protocols, witness indistinguishablity is preserved under arbi t rary composition of protocols, including parallel execution, and any witness indistinguishable protocol for this s ta tement is also.
Lecture notes in computer scienceLFSR-based Hashing and Authentication
503 Citations2007Hugo Krawczyk
The characterization of the properties required from a family of hash functions in order to be secure for authentication when combined with a (secure) stream cipher is characterization.
Lecture notes in computer scienceAn Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries
427 Citations2007Yehuda Lindell, Benny Pinkas
SIAM Journal on ComputingOn the Composition of Zero-Knowledge Proof Systems
425 Citations1996Oded Goldreich, Hugo Krawczyk
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture
353 Citations2013Eli Ben‐Sasson, Alessandro Chiesa +2 more
A system that provides succinct noninteractive zero-knowledge proofs (zk-SNARKs) for program executions on a von Neumann RISC architecture and is the first to be universal: it does not need to know the program, but only a bound on its running time.
Lecture notes in computer scienceOptimistic fair exchange of digital signatures
305 Citations1998N. Asokan, Victor Shoup +1 more
Introduction to Coding Theory
222 Citations1992J. H. van Lint
Lecture notes in computer scienceScalable Zero Knowledge via Cycles of Elliptic Curves
175 Citations2014Eli Ben‐Sasson, Alessandro Chiesa +2 more
Zero-knowledge proofs of knowledge without interaction
161 Citations1992Alfredo De Santis, Giuseppe Persiano
The authors investigate the concept of a zero-knowledge proof of knowledge with a non-interactive model, where the prover and the verifier share a short random string and the only communication allowed is from the provers to the verifiers.
Lecture notes in computer scienceFair Two-Party Computations via Bitcoin Deposits
157 Citations2014Marcin Andrychowicz, Stefan Dziembowski +2 more
The Bitcoin currency system can be used to obtain fairness in any two-party secure computation protocol in the following sense: if one party aborts the protocol after learning the output then the other party gets a financial compensation (in bitcoins).
Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs
129 Citations2015Eli Ben‐Sasson, Alessandro Chiesa +3 more
This work shows how public parameters for a class of NIZKs can be generated by a multi-party protocol, such that if at least one of the parties is honest, then the result is secure and can be subsequently used for generating and verifying numerous proofs without any further trust.
Lecture notes in computer scienceA Multi-party Protocol for Constructing the Public Parameters of the Pinocchio zk-SNARK
96 Citations2019Sean Bowe, Ariel Gabizon +1 more
Recent efficient constructions of zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs), require a setup phase in which a common-reference string (CRS) with a certain structure is generated.
Lecture notes in computer scienceSquare Span Programs with Applications to Succinct NIZK Arguments
93 Citations2014George Danezis, Cédric Fournet +2 more
This work first characterize NP as affine map constraints on small vectors, and then relates this characterization to SSPs, which are similar but simpler than Quadratic Span Programs (QSPs), since they use a single series of polynomials rather than 2 or 3.
Lecture notes in computer scienceOn the Malleability of Bitcoin Transactions
82 Citations2015Marcin Andrychowicz, Stefan Dziembowski +2 more
The behavior of the popular Bitcoin wallets in the situation when their transactions are mauled is analyzed; it is concluded that most of them are to some extend not able to handle this situation correctly.
Sealed-Glass Proofs: Using Transparent Enclaves to Prove and Sell Knowledge
81 Citations2017Florian Tramèr, Fan Zhang +4 more
This work shows how trusted hardware systems such as SGX can support trustworthy applications even in the presence of side channels, and proposes, formalize, and explores a cryptographic primitive called a Sealed-Glass Proof (SGP) that models computation possible in an isolated execution environment with unbounded leakage, and thus in the face of arbitrary side-channels.
Provisions
80 Citations2015Gaby G. Dagher, Benedikt Bünz +3 more
Provisions is introduced, a privacy-preserving proof of solvency whereby an exchange does not have to disclose its Bitcoin addresses; total holdings or liabilities; or any information about its customers; or an extension which prevents exchanges from colluding to cover for each other's losses.
Lecture notes in computer scienceSubversion-Zero-Knowledge SNARKs
78 Citations2018Georg Fuchsbauer
SNarks are proof systems with succinct proofs, which are at the core of the cryptocurrency Zcash, whose anonymity relies on ZK-SNARKs; they are also used for ZK contingent payments in Bitcoin.
Lecture notes in computer scienceEfficient Zero-Knowledge Contingent Payments in Cryptocurrencies Without Scripts
76 Citations2016Wacław Banasik, Stefan Dziembowski +1 more
Although smart contracts are believed to have a huge potential, for the moment they are not widely used in practice, because most of Bitcoin miners allow only to post standard transactions on the blockchain, it is currently very hard to create non-trivial smart contracts in Bitcoin.
Lecture notes in computer scienceA Subversion-Resistant SNARK
60 Citations2017Behzad Abdolmaleki, Karim Baghery +2 more
This work makes Groth’s zk-SNARK for Circuit-SAT from EUROCRYPT 2016 computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes and provides a definitional framework for sound and Sub- zk SNARKs and describes implementation results of the new Sub- ZK SNARK.
IACR Cryptology ePrint ArchiveSCAPI: The Secure Computation Application Programming Interface.
60 Citations2012Yael Ejgenberg, Moriya Farbstein +2 more
Lecture notes in computer scienceFaster Secure Two-Party Computation in the Single-Execution Setting
49 Citations2017Xiao Wang, Alex J. Malozemoff +1 more
A new protocol for two-party computation, secure against malicious adversaries, that is significantly faster than prior work in the single-execution setting (i.e., non-amortized and with no pre-processing).
Foundations of Computer ScienceZero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract)
47 Citations1992Alfredo De Santis, Giuseppe Persiano
This paper investigates the concept of a zero-knowledge proof of knowledge in the noninteractive model of [5, 61], where the prover and the verifier share a short random string and the only communication allowed is from the provers to the verifiers.
Lecture notes in computer scienceUsable Optimistic Fair Exchange
36 Citations2010Alptekın Küpçü, Anna Lysyanskaya
A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK.
16 Citations2017Sean Bowe, Ariel Gabizon +1 more
