Tim Ruffing
Aniket Kate
Dominique Schröder
ABSTRACT
We show that equivocation, i.e., making conflicting statements to others in a distributed protocol, can be monetarily disincentivized by the use of crypto-currencies such as Bitcoin. To this end, we design completely decentralized non-equivocation contracts, which make it possible to penalize an equivocating party by the loss of its money. At the core of these contracts, there is a novel cryptographic primitive called accountable assertions, which reveals the party's Bitcoin credentials if it equivocates. Non-equivocation contracts are particularly useful for distributed systems that employ public append-only logs to protect data integrity, e.g., in cloud storage and social networks. Moreover, as double-spending in Bitcoin is a special case of equivocation, the contracts enable us to design a payment protocol that allows a payee to receive funds at several unsynchronized points of sale, while being able to penalize a double-spending payer after the fact.
- M. Andrychowicz, S. Dziembowski, D. Malinowski, and L. Mazurek. How to deal with malleability of BitCoin transactions, 2013. arXiv: 1312.3230 {CoRR}.Google Scholar
- M. Andrychowicz, S. Dziembowski, D. Malinowski, and L. Mazurek. Secure multiparty computations on Bitcoin. S&P'14. IEEE. Google ScholarDigital Library
- G. Ateniese and B. d. Medeiros. On the key exposure problem in chameleon hashes. SCN'04. Springer. Google ScholarDigital Library
- M. Backes, F. Bendun, A. Choudhury, and A. Kate. Asynchronous MPC with a strict honest majority using non-equivocation. PODC'14. ACM. Google ScholarDigital Library
- F. Baldimtsi and A. Lysyanskaya. Anonymous credentials light. CCS'13. ACM. Google ScholarDigital Library
- I. Bentov and R. Kumaresan. How to use Bitcoin to design fair protocols. CRYPTO'14. Springer.Google Scholar
- Bitcoin Project. Bitcoin developer guide. https://bitcoin.org/en/developer-guide.Google Scholar
- Block timestamp. Entry in Bitcoin Wiki. https://en.bitcoin.it/w/index.php?title=Block_timestamp&oldid=51392.Google Scholar
- B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7), 1970. Google ScholarDigital Library
- J. Bonneau et al. SoK: Research perspectives and challenges for Bitcoin and cryptocurrencies. S&P'15. IEEE.Google Scholar
- V. Buterin. A next-generation smart contract and decentralized application platform. https://github.com/ethereum/wiki/wiki/White-Paper.Google Scholar
- C. Cachin, A. Shelat, and A. Shraer. Efficient fork-linearizable access to untrusted shared memory. PODC'07. ACM. Google ScholarDigital Library
- J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact e-cash. EUROCRYPT'05. Springer. Google ScholarDigital Library
- J. Camenisch and A. Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. EUROCRYPT'01. Springer. Google ScholarDigital Library
- Certicom. SEC 2: Recommended elliptic curve domain parameters. http://www.secg.org/sec2-v2.pdf.Google Scholar
- D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. CRYPTO'88. Springer. Google ScholarDigital Library
- CHECKLOCKTIMEVERIFY (BIP65) IsSuperMajority() soft-fork. Pull request for Bitcoin client. https://github.com/bitcoin/bitcoin/pull/6351.Google Scholar
- X. Chen, F. Zhang, and K. Kim. Chameleon hashing without key exposure. ISC'04. Springer.Google Scholar
- B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz. Attested append-only memory: Making adversaries stick to their word. SOSP'07. ACM. Google ScholarDigital Library
- A. Clement, F. Junqueira, A. Kate, and R. Rodrigues. On the (limited) power of non-equivocation. PODC'12. ACM. Google ScholarDigital Library
- C. Decker and R. Wattenhofer. Information propagation in the Bitcoin network. P2P'13. IEEE.Google Scholar
- S. Fahl et al. Hey, NSA: Stay away from my market! Future proofing app markets against powerful attackers. CCS '14. ACM. Google ScholarDigital Library
- A. J. Feldman, A. Blankstein, M. J. Freedman, and E. W. Felten. Social networking with Frientegrity: privacy and integrity with an untrusted provider. USENIX Security'12. USENIX. Google ScholarDigital Library
- A. J. Feldman, W. P. Zeller, M. J. Freedman, and E. W. Felten. SPORC: Group collaboration using untrusted cloud resources. OSDI'10. USENIX. Google ScholarDigital Library
- H. Finney. Re: Best practice for fast transaction acceptance - how high is the risk? Post on Bitcoin forum. https://bitcointalk.org/index.php?topic=3441.msg48384#msg48384.Google Scholar
- M. Fitzi and U. M. Maurer. From partial consistency to global broadcast. STOC'00. ACM. Google ScholarDigital Library
- C. Ho, R. v. Renesse, M. Bickford, and D. Dolev. Nysiad: Practical protocol transformation to tolerate byzantine failures. NSDI'08. USENIX. Google ScholarDigital Library
- Implementation of accountable assertion scheme. http://crypsys.mmci.uni-saarland.de/projects/PenalizingEquivocation/.Google Scholar
- A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: the blockchain model of cryptography and privacy-preserving smart contracts. IACR: 2015/675.Google Scholar
- H. Krawczyk and T. Rabin. Chameleon signatures. NDSS'00. The Internet Society.Google Scholar
- J. Krupp et al. Nearly optimal verifiable data streaming (full version). 2015. IACR: 2015/333.Google Scholar
- R. Kumaresan and I. Bentov. How to use Bitcoin to incentivize correct computations. CCS'14. ACM. Google ScholarDigital Library
- D. Levin, J. R. Douceur, J. R. Lorch, and T. Moscibroda. TrInc: Small trusted hardware for large distributed systems. NSDI'09. USENIX. Google ScholarDigital Library
- Liar, liar, coins on fire! -- Penalizing equivocation by loss of bitcoins. Full version of this paper. Additionally available in IACR ePrint Archive. 2015. http://crypsys.mmci.unisaarland.de/projects/PenalizingEquivocation/penalizing.pdf.Google Scholar
- D. Mazières and D. Shasha. Building secure file systems out of byzantine storage. PODC'02. ACM. Google ScholarDigital Library
- S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. 2008. https://bitcoin.org/bitcoin.pdf.Google Scholar
- M. Peyravian, A. Roginsky, and A. Kshemkalyani. On probabilities of hash value matches. Comput. secur., 17(2), 1998. Google ScholarDigital Library
- B. Poettering and D. Stebila. Double-authentication-preventing signatures. ESORICS'14. Springer.Google Scholar
- J. Poon and T. Dryja. The Bitcoin Lightning Network: Scalable off-chain instant payments. Technical Report (draft). https://lightning.network/.Google Scholar
- Providing a deposit. Entry in Bitcoin Wiki. https://en.bitcoin.it/w/index.php?title=Contracts&oldid=50633#Example_1:_Providing_a_deposit.Google Scholar
- M. Rosenfeld. Analysis of hashrate-based double spending, 2014. arXiv: 1402.2009 {CoRR}.Google Scholar
- D. Schröder and H. Schröder. Verifiable data streaming. CCS'12. ACM.Google Scholar
- D. Schröder and M. Simkin. VeriStream - A framework for verifiable data streaming. FC'15.Google Scholar
- S. Song. Why I left Sina Weibo. 2011. http://songshinan.blog.caixin.com/archives/22322.Google Scholar
- J. Spilmann. Re: Anti DoS for tx replacement. Bitcoin development mailing list. https://www.mail-archive.com/[email protected]/msg02028.html.Google Scholar
- S. Tarkoma, C. Rothenberg, and E. Lagerspetz. Theory and practice of bloom filters for distributed systems. IEEE Commun. surveys and tutorials, 14(1), 2012.Google ScholarCross Ref
- P. Todd. Near-zero fee transactions with hub-and-spoke micropayments. Bitcoin development mailing list. https://www.mail-archive.com/[email protected]/msg06576.html.Google Scholar
- P. Todd. OP_CHECKLOCKTIMEVERIFY. Draft for Bitcoin Improvement Proposal. https://github.com/petertodd/bips/blob/checklocktimeverify/bip-checklocktimeverify.mediawiki.Google Scholar
- P. Wuille et al. libsecp256k1: Optimized C library for EC operations on curve secp256k1. https://github.com/bitcoin/secp256k1.Google Scholar
Index Terms
- Liar, Liar, Coins on Fire!: Penalizing Equivocation By Loss of Bitcoins
Recommendations
Double-spending fast payments in bitcoin
CCS '12: Proceedings of the 2012 ACM conference on Computer and communications securityBitcoin is a decentralized payment system that relies on Proof-of-Work (PoW) to verify payments. Nowadays, Bitcoin is increasingly used in a number of fast payment scenarios, where the time between the exchange of currency and goods is short (in the ...
Misbehavior in Bitcoin: A Study of Double-Spending and Accountability
Bitcoin is a decentralized payment system that relies on Proof-of-Work (PoW) to resist double-spending through a distributed timestamping service. To ensure the operation and security of Bitcoin, it is essential that all transactions and their order of ...
Collusion attacks and fair time-locked deposits for fast-payment transactions in Bitcoin1
In Bitcoin network, the distributed storage of multiple copies of the block chain opens up possibilities for double-spending, i.e., a payer issues two separate transactions to two different payees transferring the same coins. While Bitcoin has inherent ...
Comments