A New Protocol for Block Propagation Using Set Reconciliation
A. Pinar Ozisik, Gavin Andresen, George Bissias, Amir Houmansadr, Brian N. Levine
“1 INTRODUCTION
We propose an efficient method of announcing new blocks
called Graphene. This document summarizes a more detailed
description of Graphene that has been published previously
and includes additional experiments.
Graphene blocks are a fraction of the size of related methods,
such as Compact Blocks and Xtreme Thinblocks.
For example, in a detailed example below, we show that a
17.5 KB Xtreme Thinblock can be encoded in 10 KB with
Compact Blocks, and encodedin 2.6 KB with Graphene. In
simulations, we find that Graphene encodes information in
about 10% of the space of Compact Blocks. We use a novel
interactive combination of Bloom filters [2] and Invertible
bloom lookup tables (IBLTs) [5], providing an efficient solution
to the problem of set reconciliation in Bitcoin’s p2p
network.
Block announcements are validated using the transaction
content comprising the block. However, it is likely that the
majority of peers have already received these transactions,
and they only need to discern them from those in their mempool.
In principle, a block announcement needs to include
only the IDs of those transactions. For example, Corallo’s
Compact Block design [3] significantly reduces block size by
including a transaction ID list, though the cost is increased
coordination between peers. Xtreme Thinblocks [9] works
similarly to Compact Blocks but has greater data overhead.
Specifically, if an inv is sent for a block that is not in the
receiver’s mempool, the receiver sends a Bloom filter of her
IDpool along with the request for the missing block. As a result,
Xtreme Thinblocks are larger than Compact Blocks. The
community has discussed in forums the use of IBLTs (without
Bloom Filters) for reducing block announcements [1, 8],
but these schemes have not been formally evaluated and are
less efficient than our approach. Our method is novel; we
have proven and demonstrated that it is smaller than all of
these recent works, and still requires 3 messages between
sender and receiver for coordination: an inv, a getdata, and
a response.
2 THE GRAPHENE PROTOCOL
Unlike other approaches, Graphene never sends an explicit
list of transaction IDs. Instead it sends a small Bloom filter
and a very small IBLT. The intuition behind Graphene is as
follows; a summary appears in Figure 1.
The sender creates an IBLT I from the set of transaction
(txn) IDs in the block. To help the receiver create the same
IBLT (or similar), he also creates a Bloom filter S of the
transaction IDs in the block. The receiver uses S to filter out
transaction IDs from her pool of received transaction IDs
(which we call the IDpool) and creates her own IBLT …”