Revealing Every Story of Data in Blockchain Systems

The success of Bitcoin and other cryptocurrencies bring enormous interest to blockchains. A blockchain system implements a tamper-evident ledger for recording transactions that modify some global states. The system captures the entire evolution history of the states. The management of that history, also known as data provenance or lineage, has been studied extensively in database systems. However, querying data history in existing blockchains can only be done by replaying all transactions. This approach is feasible for large-scale, offline analysis, but is not suitable for online transaction processing. We present LineageChain, a fine-grained, secure, and efficient provenance system for blockchains. LineageChain exposes provenance information to smart contracts via simple interfaces, thereby enabling a new class of blockchain applications whose execution logics depend on provenance information at runtime. LineageChain captures provenance during contract execution and stores it in a Merkle tree. LineageChain provides a novel skip list index that supports efficient provenance queries. We have implemented LineageChain on top of Hyperledger Fabric and a blockchainoptimized storage system called ForkBase. We conduct extensive evaluation, demonstrating benefits of LineageChain, its efficient querying, and its small storage overhead.