Ordering Transactions in a Blockchain

Overview

As outlined in this section, transactions are propagated by a flooding algorithm, such that every transaction passes node by node through the network. However, this approach is problematic since the underlying system is, in fact, a fully asynchronous peer-to-peer network, such that the message order is also asynchronous (cf. this definition :Synchronous_model ).

Therefore, there’s no guarantee that the order of transactions that a node receives actually corresponds to the order in which the transactions were originally released. As a consequence, there’s a need to develop a mechanism for the ability to maintain the order of the transactions, whereas the entire network should agree on a single version regarding the history of orders of transactions. Of course, the naive solution is to mark each transaction with a timestamp such that the nodes would be allowed to order them based on an objective criterion, namely time. But this approach doesn’t work because the clocks aren’t synchronized in an asynchronous system.

Nakamoto (2008)Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin. org/bitcoin.pdf, Dec 2008. Accessed: 2015-07-01. solved this problem by introducing a consensus mechanism, which is now popularly known as blockchain technology. The transactions are collected by the network by placing them in groups that are called blocks, publishing them in an agreed-upon time interval to the network, whereas all transactions within one single block are considered as having happened at the same time.

Definition:

Transactions are the primitives that allow the transfer of value, whereas blocks are used to synchronize the state across all nodes in the network (Christian Decker et al. (2016)vChristian Decker, Jochen Seidel, and Roger Wattenhofer. Bitcoin meets strong consistency. In Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN '16, pages 13:1-10, New York, NY, USA, 2016. ACM.).

Note: From this point of view, a blockchain network is a distributed system that exhibits partial synchrony as we defined in this section.

In the next step, the blocks are connected with each other like a chain, which is typically done with a back-linking pointer from a block to its preceding block, as shown in this figure. This results in an ordered list of blocks and, therefore in a total ordering of transactions. Consequently, we obtain a single, unique history of transactions. This is why a blockchain is also called a ledger of transactions.

Figure 1