  Lightweight Bitcoin clients execute a Simple Payment Verification (SPV)
protocol to verify the validity of transactions related to a particular user.
Currently, lightweight clients use Bloom filters to significantly reduce the
amount of bandwidth required to validate a particular transaction. This is
despite the fact that research has shown that Bloom filters are insufficient at
preserving the privacy of clients' queries.
  In this paper we describe our design of an SPV protocol that leverages
Private Information Retrieval (PIR) to create fully private and performant
queries. We show that our protocol has a low bandwidth and latency cost;
properties that make our protocol a viable alternative for lightweight Bitcoin
clients and other cryptocurrencies with a similar SPV model. In contract to
Bloom filters, our PIR-based approach offers deterministic privacy to the user.
  Among our results, we show that in the worst case, clients who would like to
verify 100 transactions occurring in the past week incurs a bandwidth cost of
33.54 MB with an associated latency of approximately 4.8 minutes, when using
our protocol. The same query executed using the Bloom-filter-based SPV protocol
incurs a bandwidth cost of 12.85 MB; this is a modest overhead considering the
privacy guarantees it provides.
