  Lazy blockchains decouple consensus from transaction verification and
execution to increase throughput. Although they can contain invalid
transactions (e.g., double spends) as a result, these can easily be filtered
out by full nodes that check if there have been previous conflicting
transactions. However, creating light (SPV) clients that do not see the whole
transaction history becomes a challenge: A record of a transaction on the chain
does not necessarily entail transaction confirmation. In this paper, we devise
a protocol that enables the creation of efficient light clients for lazy
blockchains. The number of interaction rounds and the communication complexity
of our protocol are logarithmic in the blockchain execution time. Our
construction is based on a bisection game that traverses the Merkle tree
containing the ledger of all - valid or invalid - transactions. We prove that
our proof system is succinct, complete and sound, and empirically demonstrate
the feasibility of our scheme.
