What is “DAG + Smart Contract”?
Introduction
Compared to traditional Blockchain, implementing smart contracts based on a DAG (Directed Acyclic Graph) ledger is undoubtedly more challenging. So what exactly are these difficulties and where do they come from?
Cryptocurrency
First, let’s start with the most basic scenario — cryptocurrency. The concept of a cryptocurrency is a distributed database that stores the balance information for each account. The computers running in a cryptocurrency network are referred to as Nodes. Each node stores a piece of data about the account balance, which is often referred to as State.
Unlike traditional centralized banking systems, the distributed ledger requires all nodes to reach consensus on the state. In other words, the balance for each account stored on each computer in the network is the same. Since state data may be large in certain systems, transmitting full states causes huge network overhead, therefore, in such systems only events that change states are transmitted, called Transactions. To extrapolate on this fact, your money will not increase or decrease without. The account balance will only change when you pay someone or you are paid. Therefore, as long as you have all the historical transaction records of an account, you can calculate the balance at ease.
In the cryptocurrency system, all transactions are recorded in a data structure called the ledger. The ledger is encrypted by cryptography so that each node can verify whether the data transmitted from other nodes have been tampered with. Blockchain is a classic book structure, and DAG is another.
Blockchain-Based Cryptocurrency
Here the question comes, if the ledger obtained by each node is exactly the same, are they able to calculate out the same states? First, let’s look at the ledger structure of the blockchain. In this structure, all transactions are ordered. Changing the order of any two arbitrary transactions will crash the hash reference relationship of the blockchain, thus creating an invalid ledger. Therefore, starting from the same initial state no matter which node performs the calculation, the same result will always present after the same transaction sequence. Exactly perfect, isn’t it? No matter whether it is Bitcoin or Ethereum, there is no need to transfer and compare huge state data between nodes, instead, all that is necessary to do is to reach a consensus on the ledger data. The information contained in the ledger is adequate for a node to calculate the correct state.
DAG-Based Cryptocurrency
Let’s see if the DAG ledger has such a feature. Fortunately, in a DAG ledger, although the order between some transactions is not deterministic, correct ledger state calculation is not yet impacted because the addition and subtraction of cryptocurrency balance can satisfy the commutative law. As long as the balance of any account is not less than 0, the order of the transaction is not essential at all. Therefore, no matter how the DAG ledger is traversed, the final calculated account balance will be the same. In other words, any node can restore the correct state from the DAG ledger.
Smart Contract
After talking about the cryptocurrency, let’s take a look at smart contracts. In the real world, there are plenty of scenarios require more than just recording the balance of all accounts. For example, a flight ticket booking application needs to record the seat information in the state. At this time, the transaction is no longer just currency transfer, but may contain request data for a smart contract, such as a ticket booking request. At this time, changing the order of the two transactions may result in different states. For example, if both Alice and Bob try to book the same flight seat, this seat will only be allocated to the person who books first. In a smart contract scenario, the commutative law is no longer satisfied between transactions, so it must also take into account transaction sequence.
So how is it determined which transactions must be ordered and which transactions are ordered irrelevant? An ideal solution is writing a function to determine whether exchanging any two arbitrary transactions order will affect the final state, according to the smart contract logic. If such a function exists, we would know which transactions must be linked by hash reference in the DAG ledger, as the above diagram shows any two order-relevant transactions are connected by an arrow. Unfortunately, this function is computationally expensive and cannot be adopted in the real world, therefore, we have to skip this ‘perfect’ solution and look for a simpler and more practical method instead.
Transaction Collation
In order to obtain simple transaction ordering, we could create restrictions on the system:
First, we consider the state of the system, or ‘world state’, as the combination of the states for each account. The status of any two accounts is independent and does not affect another. The balance of one user account will not change due to the change of the balance of another account, and the data of one contract will not be affected by another contract.
Second, we limit each transaction to only change the state of one account. For example, within our scheme a transfer transaction, it either reduces the balance of one account or increases it. The balance of the two accounts is not allowed to be changed at the same time. In other words, transfer transactions are split into ‘sending transactions’ and ‘receiving transactions’. Similarly, transactions invoked by smart contracts are split into ‘request transactions’ and ‘response transactions’.
When you combine the two restrictions, the collation becomes simple — Transactions that affect the state of the same account must be ordered, plus a pair of ‘request’ and ‘response’ transactions must also comply, as the request transaction happens prior to the response transaction.
Block Lattice
Following the collation described in the previous section, in a DAG ledger, each account has an ordered transaction list, or has its own blockchain, called an ‘account chain’. In addition, different account chains may also establish links with each other via request-response transaction pairs. The DAG ledger having this structure is also known as ‘block lattice’.
Transactions are ordered in block-lattice. Regardless of the order in which the DAG ledger is traversed, the same world state can always be calculated by following the order of transactions recorded in the ledger, which is why Vite employs block-lattice as the ledger structure to build smart contracts on. Other DAG structures used by other blockchain projects (such as ‘Tangle’) are unfortunately not smart-contract friendly and additional transaction collation must be introduced to support smart contracts. This would be the equivalent to adding another DAG specifically for smart contracts outside of the original DAG ledger, which would be very challenging and complex to implement.
Summary
This article briefly describes a DAG ledger structure suitable for implementing smart contracts, and why it is adopted. For more detailed information please refer to Vite whitepaper at www.vite.org.
No comments:
Post a Comment