We have briefly described the StreamNet of the DAG and the transaction implementation processes in Trias in the article How the DAG Is Used in the Trias Network to Increase the Throughput that we published we published previously. The transaction rate of the DAG structure has significantly increased compared with that of the chain structure. However, a new problem accompanies the increase and it is how to select a tip.
If a random walker algorithm is used, a new transaction will go unpunished for approving an old transaction. If a super weight algorithm such as assigning a weight value to each transaction is adopted, the transactions with high weight values are always approved as new transactions and many transactions with low weight values will never validated.
I. Transaction consensuses in DAGs
At present, there are mainly three methods to validate transactions in the StreamNet:
First method: All the common sites of the tip coverage are completely validated. For example, in the following figure, the transactions referenced or indirectly referenced by Tip 1 are covered with blue lines and yellow lines, the transactions referenced or indirectly referenced by Tip 2 are covered with yellow lines, then the transactions commonly covered by Tip 1 and Tip 2 are the transactions that have been marked green and they are the completely validated transactions.
Second method: The system sends a tip of the coordinator every other minute and attaches it to the StreamNet. The tip is called a milestone. All the transactions referenced by the coordinator are the validated transactions.
Third method: It is the Markov Chain Monte Carlo (MCMC) method. A tip is selected by using a basic random tip selection algorithm in the method. If a transaction is referenced by the tip, 1 is added to its credibility value. If the selection has been carried out for N times and a transaction has been referenced for M times, then its credibility is M/N.
II. Main algorithms of StreamNet
The centrality-based selection algorithm without the COO starting point
At the present stage, when a tip is selected in the DAG, the selection does not start with a genesis, but simply with a coordinator as the starting point, which causes a centrality problem. Therefore, when we design the StreamNet, we firstly consider how to weaken the COO to achieve the real distributed DAG. We need to find a consensus transaction and use it as the starting point, rather than use the coordinator compulsorily specified by a centralized site as the starting point. We hereby select the Katz centrality as the standard for starting point selection. Because the transactions of the StreamNet constantly enter the network, the computation amount will be huge if the Katz centrality computation is carried out for each new transaction selection. Therefore, we do the calculation by using an incremental algorithm:
Where A denotes the link relation between transactions, the kth power denotes the k-order link matrix, α denotes the importance weight vector and I is a matrix with all its values being 1s.
It is worth noting that it is not necessary to find the transaction with the maximum Katz centrality in the calculation results for it is always a genesis. Therefore, we should find the initial site from the transactions closest to the current time in the Katz centrality.
The transaction weight algorithm considering the edge information
The double-spending problem is a typical scenario side chain attack. The attacker often sends multiple side chains with rapidly increasing transactions and they approve each other. A series of fraudulent side chains may cause a double-spending attack successful.
To prevent this from occurring, we use weighted Set Join between two approval transactions. The judgment of the weight value is determined by the edge information and the edge information is validated by the time. The edge information is used to re-adjust the transactions to weaken the attack effects and maintain the stable operation of the network.
The weight update algorithm based on the streaming graph computation
When a static graph algorithm is used to update the weight of a site, it is necessary to calculate the weights of all the sites and the computation complexity is extremely high. If we cache the information for the static calculation and update the cached information only when a new tip is added, the computation complexity when a new tip is added will decrease greatly.
III. Conclusion
At present, the DAG solutions have gradually shifted from the discussion to the implementation and many new DAG solutions are being proposed in the industry. Viewing from the technical angle, the DAG may impact the existing blockchain projects and to some extent change the existing ideas on the blockchain design.
The DAG has the advantages of a fast rate and high throughput capacity. As more and more projects participate in the ecological development of the DAG, the DAG is a mechanism with a very promising future in the long run. As the first public chain that has adopted the DAG technology, Trias has creatively designed DAG-based throughput cache layer, it has been the first to make some breakthrough in the theory and reality and it has gained some advantages in the public chain competition.
