Catena: Efficient Non-equivocation via Bitcoin
Authors:
- Alin TomescuATAlin Tomescu
- Srinivas DevadasSDSrinivas Devadas
- 1 May 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 393-409
Abstract
We present Catena, an efficiently-verifiable Bitcoin witnessing scheme. Catena enables any number of thin clients, such as mobile phones, to efficiently agree on a log of application-specific statements managed by an adversarial server. Catena implements a log as an OP_RETURN transaction chain andprevents forks in the log by leveraging Bitcoin's security againstdouble spends. Specifically, if a log server wants to equivocate ithas to double spend a Bitcoin transaction output. Thus, Catena logs are as hard to fork as the Bitcoin blockchain: an adversarywithout a large fraction of the network's computational power cannot fork Bitcoin and thus cannot fork a Catena log either. However, different from previous Bitcoin-based work, Catena decreases the bandwidth requirements of log auditors from 90GB to only tens of megabytes. More precisely, our clients only need to download all Bitcoin block headers (currently less than35 MB) and a small, 600-byte proof for each statement in a block. We implement Catena in Java using the bitcoinj library and use itto extend CONIKS, a recent key transparency scheme, to witnessits public-key directory in the Bitcoin blockchain where it can beefficiently verified by auditors. We show that Catena can secure many systems today, such as public-key directories, Tor directory servers and software transparency schemes.Keywords
This publication has 24 references indexed in Scilit:
- Demystifying Incentives in the Consensus Computer2015
- Liar, Liar, Coins on Fire!2015
- SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies2015
- The Bitcoin P2P Network2014
- Decentralized Anonymous Credentials2014
- Enhanced Certificate Transparency and End-to-End Encrypted Mail2014
- Certified Lies: Detecting and Defeating Government Interception Attacks against SSL (Short Paper)2012
- CommitCoin: Carbon Dating Commitments with Bitcoin2012
- Authenticated DictionariesACM Transactions on Information and System Security, 2011
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970