The Graphene Block Propagation Protocol: Advantages and Limitations/Challenges

[ZionRTZ]

In order for a blockchain network to work well, new blocks need to be distributed to other nodes quickly. Lots of research has been done into how to transmit blocks using as little bandwidth as possible. The less bandwidth that is used, the quicker the messages will propagate. The Graphene protocol transmits blocks with what is believed to be the least amount of bandwidth possible.


How block propagation works, and the bandwidth chokepoint
When a Dash user makes a transaction, that transaction is submitted to one or more computers or nodes. Those nodes will send that transaction to other nodes and so on. Eventually almost every node will have that transaction. The nodes store that transaction for processing. All of the transactions that are not yet processed are stored in memory and collectively referred to as the mempool. Eventually, usually in two an a half minutes the transaction is included in a block. When the transaction is included in a block, it is generally considered valid and processed by the network.

So if one node is to communicate all the transactions in a block there are a few options. One way is to just transmit the whole block with all transaction. The first Bitcoin implementation did this. Another way is to communicate identifiers for all the transactions in a block and the order. The expectation is that the receiving node would be able to construct the block from the transactions it already has in the mempool. Compact Blocks, Xthin, and Graphene use this second idea to reduce the bandwidth needed to transmit blocks.


How Graphene mitigates bandwidth issues
A node with a new block that uses that Graphene protocol will construct two data structures. First, a Bloom filter with all the transactions in a block is constructed. Then an IBLT (invertible bloom lookup tables) with all the transactions in a block is constructed. Then this will be sent to nodes without the block. The receiving node will then pass all transactions in the mempool through the bloom filter. This should provide a list of all transactions in the block. However there could be too many transactions as the Bloom filter could have a false positive. There could also be transactions missing from the mempool. The receiver will then unpack the candidate transactions from the IBLT. This will identify any false positives and any missing transactions. Lastly if needed, the receiver will query other nodes for the missing transactions.

The result is that the set of transactions in a block can be recovered from just these two data structures. The only thing left to do is put the transactions in the correct order. The first version of the Graphene protocol would transmit order information with the Bloom filter and IBLT. The order information is not huge, but grows with the number of transactions in the block. For example a block with fewer than 256 transactions will take less than 1 bytes per transaction. A block with fewer than 65 thousand transactions will take less than 2 bytes per transaction. A block with fewer than 16 million transactions will take less than 3 bytes per transaction. For comparison, if Dash blocks could handle 16 million transactions that would provide 24 times the average transaction volume of Visa.

Bitcoin unlimited has taken this protocol one step further. November of last year the Bitcoin Cash chain hard forked to change a consensus rule to require blocks have transactions in a given, predetermined order. Such a choice of order is called a canonical order. After this change, Graphene can be used without including the order information. This is where Graphene shines. Blocks can become very large and the optimal bloom filter and IBLT stay very small.


Challenges to Graphene
However, the situation is more complected than that. The implementation of Graphene developed by researchers from the University of Massachusetts at Amherst assumes that all memory pools all transactions. Meanwhile our research at ASU research suggests that mempools will inevitably have some discrepancies, which can be refereed to as mempool divergence. Further, our research suggests that mempool divergence gets worse as the network grows. This means that the probability of decoding the IBLT calculated by Umass researchers will in practice be smaller. This means that performance of Graphene will not be as great as expected.

During a summer internship with Nakul Chawla funded by Dash Core Group, we explored how to fail gracefully in the event of an IBLT failure to decode. It is a fact that another bloom filter and IBLT could be requested from any other node. Once two are acquired, they can be put together, and have an almost certain chance of decoding both put together. We can even take a cue from BitcoinXT that asks three nodes for the block at the same time. Try to decode the first full response and if there is a decode failure, most likely there would be a supplemental response that could be combined with the first. During this internship malformed IBLTs were identified that would cause a infinite loop. That was easy to deal with. During this internship a working Dash Core implementation was made that would employ the Graphene protocol. We were able to do some testing with this client. There were a few clean up things that needed to be done before network wide distribution. It would also be nice to have this graceful fail implemented before going live. However, I feel that this work led to an even better idea.


SOURCE: https://dashnews.org/the-graphene-block-propagation-protocol-advantages-and-limitations-challenges/