Paper 2019/1431

Cross-Chain Communication Using Receipts

Arasu Arun and C. Pandu Rangan

Abstract

The functioning of blockchain networks can be analyzed and abstracted into simple properties that allow for their usage as blackboxes in cryptographic protocols. One such abstraction is that of the growth of the blockchain over time. In this work, we build on the analysis of Garay et al. to develop an interface of functions that allow us to predict which block a submitted transaction will be added by. For cross-chain applications, we develop similar prediction functions for submitting related transactions to multiple independent networks in parallel. We then define a general ``receipt functionality'' for blockchains that provides a proof, in the form of a short string, that a particular transaction was added to the blockchain. We use these tools to obtain an efficient solution to the Train-and-Hotel Problem, which asks for a cross-chain booking protocol that allows a user to atomically book a train ticket on one blockchain and a hotel room on another. We formally prove that our protocol satisfies atomicity and liveness. We further highlight the versatility of blockchain receipts by discussing their applicability to general cross-chain communication and multi-party computation. We then detail a construction of ``Proof-of-Work receipts'' for Proof-of-Work blockchains using efficient and compact zero-knowledge proofs for arithmetic circuits.