Data Structures of Distributed Ledger

A blockchain ledger is composed by a chain of blocks. The simplest implementation admits only one valid linear chain (main chain). In this data structure, block conflicts can generate multiple ramifications but the participants will always select the longest chain when consulting or inserting new blocks in the chain. The Bitcoin network adopts this data structure.

The Greedy Heaviest-Observed Sub-Tree (GHOST) policy defines the best chain of blocks to include orphaned sub-chains (uncle and nephew blocks), that are discarded by design in the simplest implementation. An orphan, or stale block, is created when two nodes find a block at the same time. Both nodes send off their block to be verified and included in others block chains. This recognition of concurrent work allows shorter inter-block times, which can improve throughput. Selection rules can be configured to choose the longest chain or the heaviest sub-tree, by block length or by aggregate difficulty. The Ethereum network adopts a version of GHOST data structure.

The ledger data structure can be a directed acyclic graph (DAG) to allow non-conflicting transactions from uncle blocks to be incorporated in the main chain. It is possible to create a DAG with blocks or without (DAG of transactions). One example of DAG without blocks is tangle, data structure used by IOTA network.

In pair-wise ledgers, like R3’s Corda, each node maintains a separate data set of known facts. As a result, each peer only sees a subset of facts on the ledger, and no peer is aware of the ledger in its entirety. Two peers are always guaranteed to see the exact same version of any on-ledger facts they share. This architecture improves both privacy and scalability by reducing the replication of data across the network. However, this may negatively impact data integrity and availability.

Source:
https://ieeexplore.ieee.org/document/7930224/
https://eprint.iacr.org/2013/881.pdf
https://docs.corda.net/
https://docs.iota.org/introduction