  Popular Ethereum wallets (like MetaMask) entrust centralized infrastructure
providers (e.g., Infura) to run the consensus client logic on their behalf. As
a result, these wallets are light-weight and high-performant, but come with
security risks. A malicious provider can mislead the wallet by faking payments
and balances, or censoring transactions. On the other hand, light clients,
which are not in popular use today, allow decentralization, but are concretely
inefficient, often with asymptotically linear bootstrapping complexity. This
poses a dilemma between decentralization and performance.
  We design, implement, and evaluate a new proof-of-stake (PoS) superlight
client with concretely efficient and asymptotically logarithmic bootstrapping
complexity. Our proofs of proof-of-stake (PoPoS) take the form of a Merkle tree
of PoS epochs. The verifier enrolls the provers in a bisection game, in which
honest provers are destined to win once an adversarial Merkle tree is
challenged at sufficient depth. We provide an implementation for mainnet
Ethereum: compared to the state-of-the-art light client construction of
Ethereum, our client improves time-to-completion by 9x, communication by 180x,
and energy usage by 30x (when bootstrapping after 10 years of consensus
execution). As an important additional application, our construction can be
used to realize trustless cross-chain bridges, in which the superlight client
runs within a smart contract and takes the role of an on-chain verifier. We
prove our construction is secure and show how to employ it for other PoS
systems such as Cardano (with fully adaptive adversary), Algorand, and Snow
White.
