Catena: Efficient Non-equivocation via Bitcoin

Alin Tomescu; Srinivas Devadas

Paper 2016/1062

Catena: Efficient Non-equivocation via Bitcoin

Alin Tomescu and Srinivas Devadas

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 and prevents forks in the log by leveraging Bitcoin’s security against double spends. Specifically, if a log server wants to equivocate it has to double spend a Bitcoin transaction output. Thus, Catena logs are as hard to fork as the Bitcoin blockchain: an adversary without 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 90 GB to only tens of megabytes. More precisely, our clients only need to download all Bitcoin block headers (currently less than 35 MB) and a small, 600-byte proof for each statement in a block. We implement Catena in Java using the bitcoinj library and use it to extend CONIKS, a recent key transparency scheme, to witness its public-key directory in the Bitcoin blockchain where it can be efficiently verified by auditors. We show that Catena can secure many systems today, such as public-key directories, Tor directory servers and software transparency schemes.

Note: Included additional related work and improved writing.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. IEEE Security & Privacy 2017
Keywords: bitcoin distributed cryptography implementation
Contact author(s): alinush @ mit edu
History: 2017-03-19: revised; 2016-11-15: received; See all versions
Short URL: https://ia.cr/2016/1062
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1062,
      author = {Alin Tomescu and Srinivas Devadas},
      title = {Catena: Efficient Non-equivocation via Bitcoin},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1062},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1062}
}