Blockchain – Graphene: Efficient Interactive Set Reconciliation Applied to Blockchain Propagation

This article give a brief summary of the idea of Graphene on sending block data to a single peer that would take less bandwidth.

1 – Introduction

When broadcasting information across the blockchain network, the node has to send the whole block of transactions to its neighbors. As the number of nodes grows more prominent, the message exchanging process can take a lot of bandwidth. Therefore, the need for minimizing the network bandwidth and increasing the network performance among peers in the network for better synchronization is a requirement in the blockchain system.

The goal here is to transmit the least amount of information between the sender and receiver through the network connection.

When the network is utilized optimally, we can increase the block size. Hence, more transactions are processed simultaneously. Besides, we can also reduce the propagation delay in the system, which allows the miners to reach consensus faster. Finally, using less bandwidth means the blockchain system allows greater participants, especially those who have limited network connection speed.

2 – Graphene Protocol

The Graphene protocol solves the problem of sending as little data over the wire by focusing on how to reconcile the set of transactions in the mempool and the newly created block between two peers in the network.

The main ideas behind the Graphene Protocol can be divided into two scenarios:

  1. The receiver’s mem-pool contains the all the transactions in the sender’s block (the left figure).
  2. The receiver’s mem-pool contains parts of the transactions in the sender’s block (the right figure).

As can be seen in the above figure, in the first scenario, the goal will be finding the transactions present in both the mempool of the receiver and the the block of the sender. While in the second scenario, we will also have to find the missing transactions in the receiver’s mempool. From this information, the receiver will reconstruct the whole block of transactions.

The Graphene Protocol is the combination of the two probabilistic data structures:

  1. Bloom Filters (BFs)
  2. Invertible Bloom Lookup Tables (IBLTs)

Bloom Filters

Bloom Filters is effectively used to test the set membership of an item. In the Bloom Filters, there can be two different outcomes when testing a membership of an item:

  1. The item return a negative result: the item is a True Negative and it does not exist in the set
  2. The item return a positive result: the item can either be a True Positive or False Positive. Hence, it is not confirmable whether it exists in the set

(The False Positive Rate of Bloom Filters is tunable. It depends on the size of the Bloom Filters – the number of bits used to represent the data structure)

Invertible Bloom Lookup Tables

Invertible Bloom Lookup Tables are generalization of Bloom Filters. The IBLTs subtraction provides the differences between two set. If the subtraction recovers the entire symmetric differences, then we say that the subtraction decoded.

Graphene Protocol

The Graphene Protocol uses:

  • Bloom Filter to reduce the symmetric between block and mempool
  • IBLT to recover from the small error in the Bloom Filter (False Positives)

Scenario 1

Let have a look at the first scenario where the receiver’s mempool contain the entire block.

First of all, the sender in this case will send two things to the receiver:

  1. The Bloom Filter of the transaction in the block – Bloom Filter S
  2. The IBLT of the transaction in the block – IBLT I

On receiving the Bloom Filter S, the receiver will test the membership of all the transactions in the mempool to pick out the ones that are probably present in the block. As the characteristics of the Bloom Filters, there will be False Positives. The receiver will then compute the IBLT from the positive transactions when applying the Bloom Filter on the mempool.

Finally, based on the subtraction between the two IBLTs, the receiver can retrieve which transactions are the true positives and which ones are false positives to reconstruct the block from the sender.

Scenario 2

Now, moving on to the second scenario where the receiver’s mempool contains only parts of the sender’s blocks. There are missing transactions.

The sender and the receiver will repeat the same protocol as in the first scenario. The sender will also send the Bloom Filter S and the IBLT I of the transactions in the block. The receiver will apply the Bloom Filter on the mempool and compute the IBLT I’ from the positive transactions. However, this time, the subtraction between I and I’ cannot be decoded (cannot recover the entire symmetric differences).

As the result, the receiver will now compute the Bloom Filter R of the positive transactions received from the Bloom Filter S. The receiver sends R to the sender.

The sender applies the Bloom Filter R on the transactions in the blocks. The result from this will show which transactions are in the mempool of S and which transactions are not (the missing ones). Nevertheless, there are still False Positive ones. To get rid of the FPs, the sender computes the IBLT J of the transactions from the block.

The sender sends over to the receiver:

  1. IBLT J
  2. True Negative results when applying Bloom Filter R

The receiver compute the IBLT J’ from:

  1. True Negative results sent from the sender
  2. Positives (TP + FP) result when applying Bloom Filter S

The subtraction between IBLT J and IBLT J’ can be decoded. Based on that, the receiver now can reconstruct the original block.

3 – Conclusion

Graphene Protocol utilizes two probabilistic data structures to reduce the amount of data that need to be sent over the network. There can be two scenarios where the mempool of the receiver contains the entire block or only a part of the block. The Graphene Protocol reduces the bandwidth usage comparing with other methods.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s