BUIP093: Graphene v.2 Improvements and Extensions
Proposers: George Bissias <gbiss@cs.umass.edu>, Brian Levine <levine@cs.umass.edu>
Created: 2018-09-21
Status: Passed


## Motivation

Graphene is a block relay protocol that is capable of transmitting
blocks across the Bitcoin Cash network much more compactly than previous
solutions such as Xtreme Thinblocks (XThin) and Compact Blocks. We
designed and helped code for Bitcoin Unlimited an initial implementation
of Graphene, which was released with Bitcoin Unlimited version.

### Limitations to Graphene v.1

• Graphene decode failures are not entirely independent among peers.
• Cheap hashes used in the IBLT are susceptible to random or
intentional collisions.
• Decode failures can occur quite frequently when peer mempools are
out-of-sync.
• Existing failover solutions do not leverage partial information from
the failed Graphene block.
• Graphene block optimization and creation could be made less CPU
intensive.
• Currently there is no way to send an expedited Graphene block.
• Some fields in the Graphene data structure have been
“over-engineered” and could potentially be reduced in size.

## Objectives

The project will proceed in two phases: *Improvements* and
*Extensions*.

## Phase 1: Improvements

The following items will be prototyped as functional patches based on
the dev branch of the BitcoinUnlimited (BU) software repository. In the
event that the BU team agrees that a patch meets satisfactory
performance, security, and utility requirements, we will submit it as a
pull request (PR) against the dev branch. Our team will work with the BU
team to refine the PR until the latter team deems that the PR is
suitable to be merged or otherwise abandoned.

• Protocol specification for current IBLT implementation: This is
absent from the Graphene v.1 specification and it is unreasonable to
expect other teams to implement a fairly new data structure without
a specification.
• Use SipHash plus salt for generating Graphene cheap hashes: By
passing the 32-byte transaction ID through a SipHash with a unique
salt, cheap hash collisions can be made to occur independently
between instantiations of Graphene blocks.
• Allow arbitrary random seeds to be used for IBLT hash functions: The
current IBLT implementation uses a fixed set of i seeds for the i
hash functions. This static setting makes a Graphene block at the
same block height more likely to fail to decode for multiple
receiving peers.
• Use filterInventoryKnown Bloom filter: Graphene currently assumes
that the receiver’s mempool contains all transactions in the block.
When this assumption is grossly inaccurate, the block will fail to
decode. However, by first passing transactions in the block through
the filterInventoryKnown Bloom filter, the sender can estimate what
transactions the receiver is likely missing and send them to the
• Improve Graphene optimization algorithm: During the creation of a
Graphene block, the sender must find the optimal sizes for the IBLT
and Bloom filter data structures. In the original Graphene paper we
introduce a simple equation for choosing these sizes, but for small
blocks it can be somewhat inaccurate. To address this problem, the
current implementation uses a brute-force search, but it would be
better to search only over small blocks and use the simple equation
for larger blocks.
• Re-tune Graphene parameters: In research that will be presented in a
forthcoming paper, we have identified that for larger blocks, the
computation of optimal IBLT settings should account for the natural
variance of the Bloom filter. By accounting for this variance, we
hope to improve the decode rate of Graphene blocks.
• Implement Expedited Graphene: Unlike other block formats such as
XThin, the sender of a Graphene block must have a good idea about
the size of the receiver’s mempool in order to properly construct
the block, which complicates the process of sending an expedited
block. We will explore the use of heuristics to estimate the size of
the receiver’s mempool and enable expedited Graphene blocks.
• Use CFastFilter: Graphene places 32-byte transaction IDs into a
CBloomFilter object. Each insertion requires that the ID be hashed
once for each hash function. In contrast, the CFastFilter
implementation avoids hashing by simply using entropy from the ID
itself to serve as hash values. It is possible that we can replace
our CBloomFilter instance with CFastFilter.
• Reduce IBLT checksum: The current IBLT implementation uses a 4-byte
checksum field to detect decode errors, but this is likely more than
is necessary. A preliminary investigation suggests that it may be
possible to achieve additional space savings against a minimal
increase in failure rate by giving the checksum field a variable
value.
• Update protocol specification for Graphene: We will update the
Graphene specification to reflect the changes made above.

## Phase 2: Extensions

We propose to extend the Graphene protocol to provide a means for
size-efficient mempool synchronization and to allow Graphene to better
handle decode failures. The proposed extensions have been carefully
evaluated by our team in a forthcoming paper. Distinct from Phase 1,
some additional research will likely be necessary to support the
development of that implementation. We would like to reserve 25% of the
overall time in this phase to writing, executing, and evaluating
numerical simulations of associated data structures as well as
theoretical analysis useful for improving the safety, performance, or
usability of the implementation. Similar to Phase 1, we commit to
delivering prototypes as functional patches based on the dev branch of
the BU software repository. Upon request from the BU team, we will
furthermore submit these patches as PRs against the dev branch and see
them through to the point where they are either merged to dev or abandon
by the BU team.

### Major deliverables

For both mempool synchronization and Graphene Extended we propose to

• Initial specification of the protocol and iteration with BU team and
• Any new theoretical or experimental analysis necessary to determine
proper constants and settings needed for protocol operation
• Prototype implementation based off the dev branch of the BU codebase
• Prototype testing and refinement
• Productize prototype, release code as PR against BU’s dev branch,
and iterate with BU developers until PR can be merged

### Overview of Graphene-based mempool synchronization

In addition to efficient block propagation, Graphene can be used for
intermittent mempool synchronization. In our approach, peers will
maintain an additional e neighbors. Intermittently, from the auxiliary
pool of e known (and willing) peers on the network, a remote peer is
selected randomly to perform a mempool synchronization. The protocol
description can be found in the our draft publication.

### Overview of Graphene Extended

The current version of Graphene assumes the receiver has all block
transactions. However, this is not always the case when mempools are
significantly desynchronized. In order to greatly mollify this problem,
we will implement Graphene Extended, which uses the same core logic as
mempool synchronization described above. Thus, with the exception of
network messaging, much of the associated code will be reusable. A
detailed description of the Graphene Extended protocol can be found in
our draft publication.

## Project Duration

The total anticipated project duration is 10 months (based on part-time
work):

• Phase 1: 4 months total
• Phase 2: 6 months total: 4.5 months for mempool synchronization and
1.5 months for Graphene Extended

## Budget

The total requested budget for this project is $50,000, or$5,000 per
month of the anticipated project duration.

### Phase 1

• $1K: Protocol specification for current IBLT implementation •$2K: Use SipHash plus salt for generating Graphene cheap hashes
• $1.5K: Allow arbitrary random seeds to be used for IBLT hash functions •$4K: Use filterInventoryKnown to anticipate and mitigate Graphene
block decode failures
• $1.5K: Improve Graphene optimization algorithm •$2K: Re-tune Graphene parameters based on results from new paper
• $3.5K: Implement Expedited Graphene •$2K: Use CFastFilter instead of CBloomFilter
• $1.5K: Reduce IBLT checksum •$1K: Update protocol specification for Graphene

### Phase 2

Mempool synchronization:

• $2K: Protocol specification •$6K: Theoretical and experimental analysis
• $8K: Prototype implementation •$4K: Prototype testing and refinement
• $2.5K: Productize prototype Graphene Extended •$1K: Protocol specification
• $1.5K: Theoretical and experimental analysis •$2.5: Prototype implementation
• $1.5: Prototype testing and refinement •$1K: Productize prototype