b_verify: Scalable Non-Equivocation for Verifiable Management of Data

MIT DCI graduate thesis by Henry Aspegren (2017) - mentored by DCI Director Neha Narula.

Abstract: Equivocation allows attackers to present inconsistent data to users. This is not just a problem for Internet applications: the global economy relies heavily on verifiable and transferable records of property, liens, and financial securities. Equivocation involving such records has been central to multi-billion-dollar commodities frauds and systemic collapses in asset-backed securities markets. In this work we present b_verify, a new protocol for scalable and efficient non-equivocation using Bitcoin. b_verify provides the abstraction of multiple independent logs of statements in which each log is controlled by a cryptographic keypair and makes equivocating about the log as hard as double spending Bitcoin. Clients in b_verify can add a statement to multiple logs atomically, even if clients do not trust each other. This abstraction can be used to build applications without requiring a central trusted party. b_verify can implement a publicly verifiable registry and, under the assumption that no participant can double spend Bitcoin, guarantees the security of the registry. Unlike prior work, b_verify can scale to one million application logs and commit 1,112 new log statements per second. b_verify accomplishes this by using an untrusted server to commit one hundred thousand new log statements with a single Bitcoin transaction which dramatically reduces the cost per statement. Users in b_verify maintain proofs of non-equivocation which are comparable in size to a Bitcoin SPV proof and require them to download only kilobytes of data per day. We implemented a prototype of b_verify in Java to demonstrate its ability to scale. We then built a registry application proof-of-concept for tradeable commodity receipts on top of our prototype. The client application runs on a mobile phone and can scale to one million users and ten million receipts.