Consensus and Equilibrium in the DAG-chain

DAG链上的共识机制与均衡

江航

11749023

硕士

概率论与数理统计

夏志宏

2019-05-24

2019-07-10

哈尔滨工业大学

深圳

With the rise of the concept of blockchain in recent years, more and more people begin to engage in the crypto industry.The entire crypto industry is devoted into figuring out how to open the door to a decentralized world, allowing people to securely trade without relying on third parties. The so-called technology is also collectively referred to as distributed ledger technology. A distributed ledger is similar to a synchronous database that records the transfer of value between network participants. The significance of distribution is that third-party arbitration institutions are eliminated for this value transfer.The entire ledger records the history of valid transactions and cannot be tampered with. As early as 2008, Satoshi Nakamoto first published the Bitcoin white paper, which caught the attention of the world in the subsequent events. By the end of 2017, the price of Bitcoin once exceeded 100,000 RMB.But with the experience gained from practice and new cognitive updates, the use of bitcoin alone is far from satisfying people's ideal trading scenarios. The problems of the Bitcoin system itself also limit its application scenarios and development, and the mechanism itself determines its scope of use.Low throughput, high latency, and its inherent workload certification mechanism and high transaction fees make it impossible to meet small payments, just as no one wants to go to Starbucks to buy a cup of coffee for an hour to confirm that the transaction is successful and then have to pay Bitcoin twice the price of coffee in RMB. In addition, its own workload proof mechanism has also led to a large amount of energy consumption. Bitcoin's annual mining power consumption has exceeded the national electricity consumption in Iraq for one year. The occurrence of these problems has made people think about new systems and new mechanisms. In the more than ten years since 2008, a large number of programs have been introduced. Not only that, but many scholars and engineers have also released new consensus plans. For example, in 2012, Sunny King first proposed a proof-of-stake mechanism and applied it to the Peercoin. The proof-of-stake can effectively solve the problem of energy consumption and increase the speed of the block-issuing process. Later, there was a delegated-proof-of-stake algorithm, which greatly improved the speed of the system.For example, the subsequent EOS project adopted the delegated-proof-of-stake mechanism. However, all kinds of mechanisms are based on block chain, and no one seems to think about the problem of the chain-structure itself.In the inherent block chain structure, due to the existence of the block concept, transactions must undergo a process of package screening. Therefore, no matter which consensus algorithm is based, this part will inevitably produce partial consumption. Not only that, but the result of packing blocks will also cause some waste. For example, only the longest chain in the bitcoin is retained, and all the remaining branches will be ignored. And we know that the process of packing the block is a difficult process, which is labor or financial or energy. Therefore, if improvements are made under this structure, the inherent cost of the block cannot be avoided. Therefore, thinking about its own chain structure becomes meaningful.Until 2015, Sergio Demian Lerner proposed a new chain structure: a directed acyclic graph (DAG). This underlying structure breaks the inherent thinking of the original block, allowing each transaction to be immediately chained, and the entire network can be constrained by a new consensus algorithm. The topology of the entire network is more complex than the blockchain structure, which also makes the consensus algorithm more critical. A number of distributed ledger techniques based on directed acyclic graph structures, such as the IOTA released in 2016, and the subsequent Byteball, followed. Currently, for distributed ledger technology based on directed acyclic graph structure, the two are in a leading position. However, both of them have shortcomings in practice and theory. Among them, IOTA has a tendency to be centralized on the issue of final consistency.he agreement uses a manager similar to “dictator” to determine whether the transaction is consistent. In the Byteball project, both the double-spend problem and the final consistency issue are controversial. For example, the protocol talks about the choice of the main chain. Each main chain is relative to a certain node. From the different nodes back to the initial point, different main chains will appear. Therefore, in the white paper given by Byteball, the only main chain recognized by the whole network may not exist, and many main chains may not be unified in the end.Therefore, solving the double-spend problem through the order defined by the main chain may not work. In addition, for the final consistency problem, if it is not completely determined that the main chain will be normalized, it cannot be proved that all the main chains relative to the leaf nodes will eventually pass through. For the structure itself, the scheme given by Byteball may have a good effect on the specific implementation, but it is not rigorous from a mathematical point of view. In addition, from an economic point of view, the only main chain will also bring a lot of waste of resources. Events that are not in the single main chain will always be ignored, which is much the same as the waste caused by Bitcoin, even if there is no block packaging process.Similarly, from the perspective of specific implementation, the main network that it has established in the past two years has almost developed into a single chain. The results of this implementation also confirm that the agreement itself has certain problems, and it also shows that efficiency has not been achieved. Also, there are many uncontrollable factors, all of which depend on the imperfections of the agreement itself. However, it is worth mentioning that the witness mechanism and the choice of the backbone provide a good idea and vision for the distributed ledger technology based on the directed acyclic graph structure. Therefore, for this new underlying structure, although the related projects are emerging one after another, the consensus mechanism is still the focus of the discussion. Until now, there has been no practice to prove that there is a perfect solution based on the directed acyclic graph structure to efficiently meet the needs of real-world applications and to be as safe and decentralized as possible. In this article, we will focus on the consensus issue based on the directed acyclic graph chain structure. This paper will provide a new consensus solution to solve the double-spend problem and the final consistency(finality) problem. Some necessary definitions will be given at the beginning, and a detailed description of the distributed ledger will follow. The core and key points are how to effectively solve the double-spend problem and the final consistency problem, at the same time as safe, efficient and decentralized as possible, so that the whole network node can get more participation.Therefore, in the double-spend problem, a number of reputable proxy nodes are defined as endorsements of transactions. These credibility nodes generally act as credible characters in real life, similar to witnesses in Byteball, but the way to solve double-spend is different. Due to the structure itself, the transaction-issuing process will become very fast and easy, so the complexity should be reduced as much as possible in the double-spend problem, and the bad transaction between the two should be quickly eliminated.. For the final consistency issue, since it is uniquely determined and cannot be tampered with, it should be treated with emphasis and as many nodes as possible involved.At the same time, it is also necessary to reach a consensus on the whole network. When most of the credit nodes and non-reputation nodes recognize it, the transaction will assume part of the entire network, so it is fully agreed. Different from Byteball, there is no unique main chain in the consensus mechanism introduced in this paper. This unique main chain is difficult to achieve due to its structural limitations. If there is a unique main chain, the final effective structure of the whole network. Will be tantamount to bitcoin or other primitive blockchain structure, which loses the meaning of the directed acyclic graph structure itself. Therefore, it is easy to achieve a unique main chain is a blockchain structure, such as bitcoin always chooses the longest chain as the main chain, and the packing blocks on it and the deliberately manufactured uplink delay are also for its structural service. In the directed acyclic graph structure, the goal is to achieve high efficiency and low cost while ensuring security and decentralization. Therefore, it is not necessary to find a unique main chain to add complexity to the entire network, and only need to reach a structural consensus. However, compared with the final consistency mechanism of Bitcoin, the scheme given in this paper can reach 100 percent consensus while in the mechanism given by Bitcoin, the probability that any transaction is confirmed by the final consistency will not reach 1.In addition, in all distributed ledgers, according to the blockchain "impossible triangle", the three points of scalability, security and decentralization cannot be achieved at the same time. Therefore, you can only sacrifice one of them to save the remaining two as much as possible. The idea of ​​using the agent "eyes" is equivalent to sacrificing partial decentralization, resulting in relatively weak inequalities between nodes, but greatly guaranteeing security and scalability.With the structure of the directed acyclic graph itself, it is hoped that the performance will be relatively large. At the same time, under the consensus mechanism of the text, almost all honest and effective transactions issued by effective nodes can be recognized, and it is difficult to have such a large number of neglected situations in Bitcoin. After the introduction of the consensus part, the paper gives some incentives for the node, as well as the function and release of the token. This also plays a decisive role in the entire system. Just like the real world, the economy maintains the stability of the entire industrial society. In this distributed system, the economy acts as a way to maintain system balance. Nodes that receive incentives will be more willing to serve the system, and penalties for bad nodes will also eliminate some of the system's adverse events. At the end of this article, we discuss some possible attacks, such as agent attacks, and consider malicious nodes to buy proxy reputation nodes.This situation is unlikely to happen, but it must rely on the system's own constraints to eliminate it.For dynamic systems, the imaginary attack methods often do not occur. History tells us that attack methods are often not thought of by system builders.The main contribution of this paper is to provide a feasible consensus mechanism reference scheme for distributed ledger technology based on directed acyclic graphs. The program incorporates the advantages of previous projects such as Byteball, EOS Bitcoin, etc., and effectively avoids the shortcomings known in previous scenarios. In the specific implementation process, it is only necessary to arbitrarily transform the parameters according to the method in the text.

随着近年来区块链概念的兴起，越来越多的人投入到加密行业。整个加密行业围绕着如何打开去中心化世界的大门，让人们能够在不依赖第三方的情形下安全交易，所谓的技术也被统称为分布式账本技术。分布式账本类似于一种同步数据库，记录着网络参与者之间的价值转移。分布式的意义则在于为这种价值转移省去了第三方仲裁机构。整个账本记录着有效交易的历史，并且不可篡改。早在2008年，中本聪首次发布比特币白皮书，并在随后的事件中引起了世界关注，一直到2017年年底比特币的价格曾一度突破十万人民币。但随着实践所得的经验以及新的认知更新，仅仅比特币的使用远远无法满足人们的理想交易情景。比特币系统自身的诸多问题也限制了它的应用场景和发展，其机制本身就决定了它的使用范围。低吞吐量，高延迟，以及它固有的工作量证明机制和高额的交易费使其无法满足微小的支付，正如没有人愿意去星巴克买一杯咖啡等上一个小时来确认交易成功然后还得支付两倍于咖啡人民币价格的比特币。此外，其本身的工作量证明机制也导致了大量的能源消耗，比特币一年的挖矿耗电量已经超越伊拉克全国一年的耗电量，种种这些问题的发生让人们不得不去思考新的系统和新的机制。在2008至今十余年的时间里，大量的方案出台，不仅如此，诸多学者工程师也发布了新的共识方案。例如在2012年Sunny King 首次提出了权益量证明机制，并将其应用于点点币。权益量证明能有效解决能源耗费问题，并且提高了出块速度。随后更有委托权益共识算法，更大的提高了出块速度。例如随后出现的EOS项目就采用了权益量证明机制。但种种机制均建立在区块打包的基础上，似乎没有人思考过账本结构本身的问题。在固有的链式结构中，由于区块概念的存在，交易上链必须经历一个打包筛选的过程。因此，无论基于何种共识算法，这部分必然产生部分消耗。不仅如此，打包区块所导致的结果也将造成部分浪费 ，例如比特币中只保留最终的最长链，其余的所有分支都将被忽略。而我们知道打包区块上链这个过程是一个不容易的过程，耗费人力或财力或能源。因此，若一直在这种结构下做改进，区块所带来的固有成本是无法被避免的。因此，对本身链式结构的思考，就变得有意义了。在2015年Sergio Demian Lerner 提出新的链式结构：有向无环图。这种底层结构打破了原先区块的固有思维，可以让每一笔发生的交易立即上链，并且可以通过新的共识算法约束整个网络。整个网络的拓扑结构较之于区块链结构更加复杂，这也导致其中的共识算法更加关键。随后出现了大量基于有向无环图结构的分布式账本技术，如2016年发布的IOTA，以及随后的Byteball。当前对于基于有向无环图结构的分布式账本技术，此二者当处于领先地位。但二者无论是在实践还是理论均存在不足之处。其中IOTA在最终一致性问题上出现了中心化的倾向，协议里采用了一个类似于“独裁者”的管理员决定着交易是否达到一致性稳定。而在 Byteball 项目中，无论是双花问题还是最终一致性问题都有着争议的地方。例如，协议中谈及主链选择，每一个主链都是相对于某一个节点而言的，从不同节点回溯到初始点则会出现不同的主链。因此在Byteball给出的白皮书中，全网公认的唯一主链可能不存在，诸多主链最终可能不会归一。因此通过主链定义的序来解决双花问题不一定能行得通。此外，对于最终一致性问题，若无法完全确定主链会归一化，则无法证明所有相对于叶子节点的主链最终会交于一点。对于结构本身，Byteball给出的方案针对于具体实施可能会有好的效果，但从数学的角度缺乏严密性。此外，在经济角度，唯一的主链也将带来大量资源浪费，不处于唯一主链上的事件将永远被忽视，这和比特币上造成的浪费大同小异，即使没有区块打包的过程。同样的，从具体实施的角度出发，当前它近两年建立的主网也几乎发展成了一个单链，这种实施结果也证实了协议本身就存在一定的问题，同样也表明效率没有做到非常高，同样的还有很多不可控因素，都取决于协议本身的不完善。但值得一提的是，其中的见证人机制和主链选择给基于有向无环图结构的分布式账本技术提供了好的想法和视野。因此针对这种新的底层结构，尽管随后相关的项目层出不穷，但其共识机制依旧是讨论的重点。直到目前，没有实践证明存在一个基于有向无环图结构的完美方案来高效满足现实世界中的应用需求并做到尽可能的安全和去中心化。在本文中，我们将重点讨论基于有向无环图链式结构的共识问题，本文将提供一个新的共识方案来解决双花问题和最终一致性问题。在开始将给出一些必要的定义，此后将对分布式账本做一个详细介绍。而核心和要点则是如何有效解决双花问题和最终一致性问题的同时，达到尽可能安全，高效和尽可能去中心化，让全网节点更多的得到参与。因此在双花问题上，文中定义了一批有信誉的代理节点充当交易的背书。这批信誉节点在现实生活中一般充当大家可信的角色，类似于Byteball中的见证人但解决双花的方式不一样。由于结构本身的缘故，交易的更迭将变得十分快速和容易，因此在双花问题上应当尽可能减少复杂度，快速剔除二者之中的不良交易。而对于最终一致性问题，由于是唯一确定并且不可篡改的，则应当重点对待，并让尽可能多的节点参与其中。同时，也应当做到全网达成共识，当大部分信誉节点和非信誉节点都对其产生认可时，该交易将承担整个网络的一部分，因此得到完全共识。不同于Byteball的是，文中介绍的共识机制不存在唯一的主链，这种唯一的主链由于其结构的限制本来就很难做到，若真正存在唯一的主链，整个网络最终的有效结构将无异于比特币或其它原始的区块链结构，这就失去了有向无环图结构本身的意义。因此，容易做到唯一主链的是区块链结构，如比特币中总是选最长链为主链，并且其上的打包区块和刻意制造的上链延迟，也是为了其结构服务。在有向无环图结构中，目的是达到高效低成本，同时保证安全和去中心化。因此不必强求找到一条唯一的主链来给整个网络增加复杂，而只需要达成结构的一致性共识即可。但和比特币最终一致性机制相比，文中给出的方案能够达到百分之百的共识。相反，在比特币所给出的机制中，任意一笔交易被最终一致性确认的概率都不会达到1。此外，在所有的分布式账本中，根据区块链“不可能三角”，即可扩展性，安全和去中心化这三点必然无法同时达到。因此，只能相对少的牺牲其中一项来尽可能大的保全其余两项。采用代理人“眼睛”的想法就相当于牺牲了部分去中心化，造成了节点之间的相对弱的不平等，但极大的保证了安全性和可扩展性。配合有向无环图本身的结构，则有希望做到性能相对大的提升。与此同时，在文中共识机制下，有效节点所发布的诚实有效交易几乎都能够被认可，很难存在比特币中那样大量被忽视的情形。在介绍完共识部分之后，文中给出了节点的一些激励机制，以及代币的功能和发布。这在整个系统中也起着决定性作用，就如同现实世界一样，经济维持着整个工业社会的稳定。在这个分布式系统中，经济一样充当维持系统均衡的作用。收到激励的节点则会更加乐意为系统服务，相反对于不良节点的惩罚也将杜绝一些系统中的不良事件。系统中的参与者将会根据自身利益，围绕共识机制既定的规则进行活动。因此，一个好的激励机制至关重要。 在本文的最后讨论了部分可能发生的攻击，如代理人攻击，考虑恶意节点收买代理信誉节点，这种情形虽然不大可能发生，但也得依赖系统自身的约束去杜绝，若这种方式是有利可图的，未免不会有人为利益而作恶。而对于动态的系统而言，想象得到的攻击方式往往不会发生，历史告诉我们攻击方法往往是系统构造者没有想到的。本文的主要贡献是为基于有向无环图的分布式账本技术提供了一个可行的共识机制参考方案。该方案吸纳了之前诸多项目的优点，如Byteball，EOS，比特币等等，并有效的避免了之前方案中已知的缺点。在具体实施过程中，只需要按照文中的方法任意变换参数即可。

distributed ledger directed acyclic graph consensus double-spend final consistency incentives

分布式账本 有向无环图 共识机制 双花问题 最终一致性 激励机制

英语

联合培养

南方科技大学

Jiang H. Consensus and Equilibrium in the DAG-chain[D]. 深圳. 哈尔滨工业大学,2019.