consensus
  • README
  • Blockchain Consensus Encyclopedia Infographic
  • CONTRIBUTING
  • Introduction
  • Blockchain Consensus?
  • Glossary
  • Categorizing consensus
  • Chain-based Proof of Work
    • Proof of Work (PoW)
    • Proof of Meaningful Work (PoMW)
    • Hybrid Proof of Work (HPoW)
    • Proof of Work time (PoWT)
    • Delayed Proof of Work (dPoW)
    • Proof of Edit Distance
    • ePoW: equitable chance and energy-saving.
    • Semi-Synchronous Proof of Work (SSPoW)
  • Chain-based Proof of Stake
    • Delegated Proof-of-Contribution (DPoC)
    • Secure Proof of Stake (SPoS)
    • Hybrid PBFT/Aurand
    • Proof of Stake (PoS)
    • Delegated Proof of Stake (DPoS)
    • Proof of Stake Time (PoST)
    • Proof of stake Boo (PoS Boo)
    • High Interest Proof of Stake (HiPoS)
    • Asset PoS (APoS )
    • Traditional Proof of Stake / Tiered Proof Of Stake (TPOS)
    • Casper the Friendly Finality Gadget (FFG)
    • Correct By Construction (CBC) Casper
    • Variable Delayed Proof of Stake (vDPOS)
    • Proof of Stake Velocity
    • Magi's Proof of Stake (mPoS)
    • Leased Proof of Stake (LPoS)
    • Delegated Proof of Importance (DPoI)
    • Leasing Proof of Stake (PoS/LPoS)
  • Chain-based Proof of Capacity/Space
    • Proof of Process
    • Proof of capacity (PoC)
    • Proof of Signature (PoSign)
    • Proof of Retrievability (POR)
    • Proof of Location
    • Proof of Reputation (PoR)
    • Proof of Proof (PoP)
    • Proof of History
    • Proof of Existence
    • Proof of Research (DPoR)
    • Proof of Activity
    • Proof of Weight (PoWeight)
    • Proof of Zero (PoZ)
    • Proof of Importance
    • Proof of Care (PoC)
    • Raft
    • Proof of Value (PoV)
    • Proof of Participation (PoP)
    • Proof of Believability
    • Proof of Stake (POS) / Proof of Presence (PoP)
    • Proof of Ownership
    • Proof of Quality (PoQ)
    • Proof of Space (PoC)
  • Chain-based Hybrid models
    • GRANDPA
    • Proof of authority (PoA)
    • Ethereum Proof of Authority
    • Limited Confidence Proof-of-Activity (LCPoA)
    • Proof of Work (PoW) / Nexus Proof of State (nPoS) or Nexus Proof of Holding (nPOH)
    • Proof of Activity
    • Proof of Work (PoW) / Proof of Stake (PoS) / Proof Of Care (PoC)
    • Proof of work (PoW) / High Interest Proof of Stake (HiPoS)
    • Proof of Work (PoW) / PoM / PoSII
  • Chain-based Proof of Burn
    • Proof of Processed Payments (PoPP)
    • Proof of Burn (PoB)
    • Proof of Time
    • Proof of Stake (PoS) / Proof of Disintegration (PoD)
  • Chain-based Trusted computing algorithms
    • Proof of Elapsed Time (PoET)
  • Chain-based PBFT and BFT-based Proof of Stake
    • leaderless BFT dual ledger architecture
    • Albatross
    • asynchronous BFT protocol
    • BFTree
    • Byzantine Fault Tolerance (BFT)
    • Delegated Byzantine Fault Tolerance
    • Federated Byzantine Agreement
    • HotStuff
    • LibraBFT
    • Modified Federated Byzantine Agreement (mFBA)
    • Ouroboros
    • Practical Byzantine Fault Tolerance
  • Chain-based others
    • Proof of Trust (PoT)
    • Proof of Devotion
    • Snowglobe
    • Avalanche
    • Serialization of Proof-of-work Events (Spectre)
    • Scrypt-adaptive-N (ASIC resistant)
  • Chain-based DAG
    • BlockFlow
    • Direct Acyclic Graph Tangle (DAG)
    • Hashgraph
    • Block-lattice - Directed Acyclic Graphs (DAGs)
  • Magi's proof-of-work (mPoW)
  • Common Attacks
  • Performance indicators
  • ThresholdRelay
  • Holochain
Powered by GitBook
On this page
  • Chain-based DAG
  • Chanllenges of DAG-based ledger implementation
  • 1. Ordering
  • 2. Randomness and Delay
  • 3. Block Efficiency

Chain-based DAG

Chain-based DAG

A significant limitation of a single-chain topology is its ability to accept only one block at a time. But what if the network could accept multiple blocks simultaneously? This would not only increase the number of transactions processed but also reduce the waste incurred when the network discards all branches except one.

A directed acyclic graph (DAG)

Instead of constructing a linear chain, we can represent this more inclusive approach by building a graph. Many people think of a blockchain as a linear chain, but classic single chains like bitocoin and ethereum actually consist of branches and resemble a tree more than a linear chain. This tree-like structure is a type of graph, specifically a directed acyclic graph (DAG).

A DAG might sound complex, but it simply means:

  • Blocks (vertices in mathematical terms) in this graph are connected.

  • These connections (edges in mathematical terms) have directions — e.g., block A points to block B

  • Following these directed connections from any block, you cannot end up at the same block no matter what path you take — i.e., there are no cycles in this graph

Chanllenges of DAG-based ledger implementation

Let’s investigate some of the problems we face into while making these design decisions.

1. Ordering

In a single chain, the relative order of blocks is clear, as each block is linearly ordered with a defined parent. In a block DAG, only a subset of blocks has a clear relative order, while others do not. This is called partial ordering, which is unacceptable in blockchain.

Blue: clear relative ordering; Orange: ambiguous relative ordering

In the illustration above, blue blocks have a clear relative order since they are directly or indirectly connected. If block A points to block B, block A knows about block B at its construction, indicating block B came before block A. However, orange blocks have ambiguous relative ordering, as there are no direct or indirect connections between them. Thus, some blocks have a clear order, while others do not.

Ordering is crucial because different transaction orders can produce very different outcomes. For example, if A has 1 coin, and we have these transactions:

  1. A sends B 1 coin

  2. A sends C 1 coin

  3. D sends A 1 coin

Processing these in different orders results in different outcomes:

  • Order (1, 2, 3): transaction 1 succeeds, 2 fails since A now has no more money, 3 succeeds

  • Order (2, 3, 1): transaction 2 succeeds, 3 succeeds, 1 succeeds

In blockchain, ordering is a critical attribute for network consensus; thus, partial ordering is unacceptable.

2. Randomness and Delay

Randomness involves randomly selecting the next node to produce a block. There is no central entity "selecting" the node; it’s a matter of luck which node solves the puzzle first, given comparable hashing power.

Randomness is vital to prevent targeted attacks, bribery, and other malicious activities. If block producers were known ahead of time, they could be incentivized to cheat or collude—e.g., prioritizing their own trades or attempting double-spends. Randomness ensures the network remains fair and honest.

Delay refers to the time taken to create a new block in DLT, controlling the block creation frequency. Every block DAG must incorporate a delay.

But why do we need a delay at all? No network can handle infinitely many blocks; each node would eventually run out of bandwidth, storage, memory, or CPU. There aren’t infinite transactions to fill infinite blocks. The block production rate and the number of transactions per block should adjust dynamically to network conditions, but zero delay is never feasible.

3. Block Efficiency

When a node is producing a block, it is deciding which transactions the network will process next. At any given time, each node on the network maintains a list of pending transactions which were sent to the network for processing but haven’t made it into a block yet. When a new block is being produced, a node looks at this pending transaction queue and selects a subset to place into the block.

Packing a block efficiently

Different networks have developed various conventions for transaction selection, mostly driven by economic incentives.

If there are no severe network issues, each full node should have similar pending transaction queues, as critical information circulates quickly in a peer-to-peer (P2P) network. Nodes generally have heard about the same set of transactions, building similar pending transaction queues.

If every node sees nearly the same set of pending transactions, they will produce blocks containing similar sets of transactions. This redundancy is undesirable, as redundant transactions represent wasted work, which is inefficient.

PreviousScrypt-adaptive-N (ASIC resistant)NextBlockFlow

Last updated 4 months ago