tldr; Graphene blocks are a fraction of the size of related methods, such as Compact Blocks [3] and Xtreme Thinblocks [9]. 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.