Graphene Block Propagation Protocol

Increasing Throughput With the Use of Bloom Filters

Grayblock
Coinmonks
Published in
5 min readSep 11, 2018

--

INT is currently testing their main net which includes proving many things from proper wallet function and transaction broadcasting to block production and block propagation. But one of the more important characteristics, especially for an IoT network of this scale, is the throughput of the network.

Several weeks ago, INT released an update saying they had stress tested the network and it fell short of their TPS expectations.

As we know from the previous article on PoW scaling, a Bitcoin-type blockchain with 1 MB blocks (which is what INT’s main chain is built upon) with 10 second blocks would allow 2,000ish transactions per block or ~200 transactions per second (assuming simple transactions). At this speed, transaction and block propagation becomes an issue and can slow down the network. In testing, this is exactly what they saw. At 10 second blocks, throughput never exceeded 100 TPS.

That is not going to cut it for an IoT ecosystem.

What INT has decided to do was to look into reducing node to node bandwidth issues that was inhibiting transaction throughput. In a normal blockchain network, nodes are constantly broadcasting sets of hashes of new transactions and new blocks that it has to other nodes in the network. These messages (inv messages) allow nodes to get the most up-to-date transactions and blocks by responding to them with a getdata request with the hashes of the data it needs. The node receiving the getdata message will then send the block or transactions the node has requested. [Fig. 1] Each block or transaction is introduced to the network at the node of it’s origin and is propagated through the network using the above broadcast mechanism.

Fig. 1 Bitcoin block propagation protocol. inv message is broadcasted containing transactions or blocks that it has, getdata message is returned requesting data to be sent to the node, node responds by sending the block in it’s entirety. Taken from Decker et al. 2013 “Information Propagation in the Bitcoin Network”

When a new block has been created and a node requests the block, the header and the transaction raw data is downloaded from the connected node. These messages can get quite large (equal to the size of the block), clog the network and impede the propagation of transactions. In most cases, nodes already have received a majority of the transactions that are included in the newest block so the raw transaction data downloaded from the block transaction is duplicated effort and wasted bandwidth. This doesn’t create issues until you start trying to push the boundaries of what is possible with the throughput of a network.

This is, in fact, what hindered INT from reaching the transaction throughput they were expecting and led them to begin testing with Graphene.

Graphene

Graphene is a novel and highly efficient protocol for the transmission of blocks (developed by A. Pinar Ozisik, Gavin Andresen and more) that proposes the use of Bloom filters to identify transactions within a block from the local mempool (short for memory pool, this is the set of all Bitcoin transactions in the network that are awaiting verification and to be included in a block). This means that instead of a node responding to a block getdata request with the block header and set of raw transaction data, it responds with a header and a set of filters that can be applied to the local node mempool to identify the transactions it needs to include in that block.* [Fig. 2]

Fig. 2 Graphene block propagation protocol. The getdata request is responded to with the block header and set of Bloom filters to be applied to the mempool, thus avoiding the duplication of effort in downloading transactions already possessed by the node. Taken from the 2017 presentation of Graphene protocol by Ozisik et al. titled “Graphene: A New Protocol for Block Propagation Using Set Reconciliation”

This method reduces the size of block announcements tremendously, down to 2 kB for a Graphene block compared to the same 1 MB Bitcoin block, 20 kB for a 10 MB block, thereby fitting the entirety of a block into a single IP packet. [Fig. 3]

Fig. 3 Graphene block size growth comparison with original and new transmission methods. Taken from the 2017 presentation of Graphene protocol by Ozisik et al. titled “Graphene: A New Protocol for Block Propagation Using Set Reconciliation”

This opens up bandwidth for higher transaction rate, reduces orphan block generation and enables faster block times.

Preliminary Results

As stated before, in the first round of stress testing, the INT main chain was only capable of less than 100 transactions per second with it’s 10 second block time. The implementation of Graphene increased this to over 600 transactions per second and allowed a INT to reduce the block time to 5 seconds. Additional testing is being done to increase this further and with several other changes to node protocol, namely:

  • Keeping blockchain and mempool in memory
  • Segregating cryptographic and consensus operations to separate CPU threads
  • Dividing validation between state-dependent and state-independent checks

INT may be able to increase this throughput by an order of magnitude or more.

It is important to note here that it may be not accurate to compare an INT IoT transaction rate to a simple asset transaction rate. While some INT transactions will be simple asset exchange, a portion of them will be the transmission of data in the IoT. These will be weighed down with not only transaction details but data, reducing the total number of transactions able to be processed in the network.

Impact on Finality

If you recall from the article on finality, finality is defined as the probability that a transaction will not be reverted. In a PoW network, this increases over time but never reaches 100%. However, in a BFT PoS network, finality reaches 100% after 2/3 of the block validator nodes sign the block. Finality is therefore related to the number of validator nodes, n, and the block time, B, as:

Where overhead, ω, is:

for BFT protocols. This reduces finality, f, to 1/B.

I previously stated INT’s finality as 5 seconds with a block time of 10 seconds but the above changes to the block time decreases the time to finality to 2.5 seconds. That means 2.5 seconds after you send your transaction, whether assets or data, that transaction is guaranteed to never be reverted.

Notes

*Now you might think well doesn’t this filter get larger with the size of the mempool? Yes it does, but it is a very slow growth.

http://www.gsd.inesc-id.pt/~ler/docencia/rcs1314/papers/P2P2013_041.pdf

http://cryptoeconomics.cs.umass.edu/graphene/#expl

Get Best Software Deals Directly In Your Inbox

--

--