Security of Permissionless Blockchain
A blockchain is an append only database with the DB management system (DBMS) software running on distributed hardware servers with no part to be more important than any other. A permissionless blockchain is the case for each of these servers to dynamically join providing or quit dropping off its service no need of permission and without causing error or disruption to the DBMS. In fact, resilience of dropping off servers without causing error or disruption to the DBMS is an understatement to characterize robustness and security qualities for a permissionless blockchain. A permissionless blockchain must keep running in good order even if some of its participants are actively attacking the system by running maliciously modified software on their servers. Such a permissionless participant can freely launch attacks on the DBMS since it has the full administration privilege on the servers it “contributes”. Obviously, it is necessary and also a reasonable assumption that a majority of the participants in a permissionless blockchain are not attackers. Bitcoin (Satoshi Nakamoto, 2008, Bitcoin: A peer-to-peer electronic cash system.) is the first permissionless blockchain to manifest these qualities. After Bitcoin, it becames known that members of the public participants can indeed maintain a decentralized DBMS in good order even permitting a smaller fraction of such participants being attackers.
Bitcoin uses a Proof-of-Work (PoW) puzzle solving game for its participants to compete for the exclusive right of writing to the DB. The permissionless competition not only can prevent the DB from being written into with erroneous or conflicting records; it even has an automatic error correction function as follows: when then blockchain forks which means encountering conflicting DB entries, subsequent miners follow the longest chain branch to mine coins and extend the blockchain. This method of error correction works well because only doing so can the coins mined by the longest chain followers be valid. The permissionless competition of the Bitcoin mining has become a very tough bid for power game. Only with the use purposely designed mining hardware, and pooling such in large farms, can a miner enter and stay in the mining competition. Upon a block announcement by a single winning miner, the whole network of other miners have to consede loss and immediately start re-mining by following the newly announced winner. Unlike the usual casino analogy that a low winning probability gambling game should also have a low losing cost, Bitcoin mining is a very low winning probability, and ever growing high cost to participate. In fact, Bitcoin miners have become so highly rare specialists who need exotically single minded enthusiasm and determination to stay in the game. Since these losers’ combined use of electricity, equalling that used by the entire Bitcoin network, is completed wasted, Bitcoin mining has an extremely wasteful energy consumption, to prohibitively limit its suitability and sustainability for most business applications.
Bitcoin Mining: Competing to Writing DB
Satoshi Nakamoto masterminded Bitcoin, the first global digital payment instrument without involving a centralized bank. In order for Bitcoin to be infallible, the system’s transaction database management system (DBMS) runs on globally distributed computers with a very high degree of redundancy, so high that any part of it, were under the control of any centralized body, must be functionally negligible in influencing the rest. Bitcoin has achieved such a globally distributive redundancy by attracting permissionless participation for “mining” digital coins. In hope to succeed coin mining, enthusiastic miners all over the world plugging their computers in and piecing together a globally distributed huge resource pool have provided Bitcoin with the needed redundancy. Although the permissionless plugin style of resource pooling also means free and dynamic dropout of components from the pool, however as the incentive giving Bitcoin mining is quite profitable, usually more additions than dropouts are attracted to the pool for it to steadily grow to a global scale to have strongly secured the DBMS for Bitcoin. Strong security is also a result of mining profitability, since can only profitability drive strong competition among miners for them to enter only the correct transaction records to the DB.
Strong competition among miners may cause concurrent mining outputs being announced by a plural number of miners, and inevitably the DBMS state becomes indistinguishable or disputable on which one of these disseminating miners should enter transaction records to the DB. Having envisaged competition noise and a likelihood of indistinguishable disputes, Nakamoto calculatingly targeted a very high difficulty for Bitcoin’s mining game: Bitcoin mining is brute-force evaluating a cryptographic hash function, until finding a valid output with a publicly agreed and easily measurable amount of computation. This formulation of puzzle solving with a hard to produce (Work) and easy to validate evidence (Proof) is cryptographically strong and elegant. It was originally proposed by Dwork-Naor in 1992 to combat email spam, and the term Proof-of-Work (PoW) was coined by Jakobsson-Juels in 1999. In order to avoid indistinguishable dispute, the difficulty of Bitcoin mining is increasingly adjusted to a level that the combined hash power of all miners in the entire peer-to-peer (P2P) network should make an average one block to appear every 10 minutes. Bitcoin’s mining traffic is very quiet, in fact, too quiet that the bandwidth of the Internet has been way too under used. A number of undesirable consequences of Bitcoin mining have been identified. The following are a few shortcomings of Bitcoin mining which have been widely criticized.
Since Bitcoin mining is a simple bid for power game, Bitcoin miners have been for years in an arms race of using ever increasingly more powerful, with some being purposely designed, e.g., ASIC hardware circuits, and even aggregating a mass number of such, mining machines (aka farming), to compete Bitcoin mining against one another. A status quo of huge centralization for Bitcoin mining has resulted. Only can fewer and fewer miners, and each being more and more powerful, stay surviving the game. The highly centralized Bitcoin miners are factually demanding very strong trust over them, and thereby undermining security, reliability, fairness, service stability, and threatening the very sustainability, of Bitcoin. Moreover, with its infamously low transaction processing throughput and long conformation latency, Bitcoin is not suitable for global online commerce transactions applications. Even for its few exhibited successful applications, e.g., financial investment, Bitcoin has taken the blame for wasteful energy consumption.
An Issue in Bitcoin Mining: Insufficient Competition
We can think of Bitcoin mining as somewhat a mundane “automobile racing”: the racing traffic is very quiet that for most cases after an average 10-minute long silence only one car arrives at the finish line with all other competing cars being far lag behind. All these losers promptly abandon the race at once upon seeing (hearing broadcast) the only one winning car arrives at the finish line. This quiet way to lineup the blockchain mining resource is a winner-takes-all approach. Losers have not even got a chance to disseminate their IDs to the system.
In such an average 10-minute long silence of no block dissemination, no users’ transaction can be recorded to DB, and therefore Bitcoin has a very poor transaction processing capability. Some established large mining farms, in a naive thinking that enlarging block size can batch processing more transactions and thus can improve the transaction processing scalability, have proposed for Bitcoin to process a large block size, e.g., of 8 mega bytes. Some miners, e.g., a “Bitcoin Unlimited”, aka Bitcoin Cash or BCH, even demand to place no limit to the block size, and went a hard-fork split from Bitcoin in August 2017. Ironically, only a little more than one year later in November 2018, the “Bitcoin Unlimited” chain encountered another hard-fork split to “Bitcoin-SV” (Satoshi Version), went back to the oldest version of Bitcoin (Ver 1.0) of 1 mega-byte block size limit. The block size issue has been with controversial disputes and heated power bid in the Bitcoin miners for years. In general, already established large miners prefer, and with more power to mine blocks of, larger block sizes. Unfortunately fairness suffers in this power bid, not only giving larger miners an advantage over smaller miners, but also having led to a heavy mining centralization, where the mining power tends to be concentrated under a single controller, breaking the basic premise and vision of Nakamoto that security, stability, and health growth of blockchain be based on miners’ decentralization. These problems can all be considered as consequences of one issue: Bitcoin mining lacks sufficient competition. This issue of insufficient competition has not been clearly identified and hence not been widely discussed. Our following discussion adds the well needed manifestation.
Among the losers who have to abandon the race in Bitcoin one-winner-takes-all mining, there may well possibly be many of them who have processed users’ transactions in a more correct or desirable sense than that the single won miner has single-handedly done. Since Bitcoin’s mining strongly avoids a plural number of miners winning concurrently, it has not got a mechanism to conduct a horizontal and realtime comparison among a number of miners on who has processed users’ transactions more correctly than those of the rest have. On the contrary, Bitcoin has often been encountering unfair miners who only process the empty set of transaction so that the sizes of their blocks are much smaller than ones that contain full sized batch of transactions which the honest miners tried to enter DB. The hash evaluations of such cheating miners are quicker for them to gain unfair advantages to win PoW mining earlier. We need sufficient competition to exclude cheaters, and hence propose DaoliCloud.
The “car racing racetrack” for the DaoliCloud blockchain shall be much more noisier than that for Bitcoin. The racetrack is much shorter so that the finishing line is much more crowded than the cases for Bitcoin. Most of the times there would be a plural number of miners announcing mining successes which are heard as concurrent and indistinguishable time events. What is indisputably clear is that the IDs of these concurrently won miners are now known to the entire network. This style of noisy mining has a great usefulness: miners of known names lineup to contribute to a much bigger resource pool of cloud servers, in addition to forming a stronger competition resultant DBMS correctness.
With the desirably noisy network traffic at the finish line of the DaoliCloud blockchain, we need a mechanism to avoid disputes on exactly who the unique won miner is. “Car crash” like scenes are indeed avoidable for blockchain mining if the miners can agree to a simple consensus on “what time now is” of a decentralized clock. In the following number of blogs we shall establish how for all miners of a permissionless blockchain to reach consensus on a decentralized global clock in a P2P network.
Haber and Stornetta in 1991 (Stuart Haber and W Scott Stornetta. “How to time-stamp a digital document”. In: Conference on the Theory and Application of Cryptography. Springer. 1990, pp. 437– 455.) made an ingenious observation that repeated chaining a cryptographic hash function can model some basic properties of time very well: easy to forward compute, and difficult to revert or tamper with. They proposed to use their hash-chain data structure to provide a timestamping service. It was the adoption of the hash-chain data structure by Bitcoin that paid a long overdue recognition to the invention of Haber and Stornetta. However, Bitcoin’s inclusion of timestamps in its chained blocks, named “block timestamps”, was not for a serious timekeeping use. Quoted below in the square brackets is Bitcoin’s specification for its block timestamps:
(… timestamps’) In addition to serving as a source of variation for the block hash, they also make it more difficult for an adversary to manipulate the block chain. A block timestamp is accepted as valid if it is greater than the median timestamp of previous 11 blocks, and less than the network-adjusted time + 2 hours. “Network-adjusted time” is the median of the timestamps returned by all nodes connected to you. As a result block timestamps are not exactly accurate, and they do not need to be. Block times are accurate only to within an hour or two.
Bitcoin’s use of timestamps has actually little to do with intending to reach a global time consensus. It is even possible that a block timestamp can be a lower (earlier) value than its predecessor. We can understandably consider a couple of reasons why Bitcoin’s timestamps cannot make a meaningful time sense:
- Bitcoin miners can lie about timestamps, and miners’ private clocks may not be synchronized. There seems not a practical way to implement, execute or maintain a due diligence standard for the permissionlessly participated miners to behave nicely.
- Time ticking forward as state progress obeys unconditionally some natural laws. E.g., it cannot be reverted, and it cannot be overtaken. However, the state of the Bitcoin blockchain can be overtaken by a longer chain fork, and can even be reverted upon revelation of a secretly mined longer chain fork.
It is understandable to see that Bitcoin has not got a good way to use its block timestamps for a credible reference of time. Indeed as admitted in its specification, block timestamps are mainly about to add some noise to the hash function as desirable entropy. As of this writing, such a no-good use of blockchain timestamps has been a status quo situation for blockchains. None of the subsequently proposed PoW mechanism permissionless blockchains in attempt to improve Bitcoin, to the best of our knowledge, has really paid any attention to a meaningful use of timestamps.
However, even permitting a rather coarse error room for miners to record timestamps in their blocks, Bitcoin block timestamps still do inherently contain some property of time. For instance, the block timestamp values do monotonically increase in the time progress direction, and by and large they record time length spent on mining a block plus that on transmitting it throughout the network. What in our view, and to be used in our exploitation, of a very important quality of the collectively defined timestamps by a slide window of previous miners is: the timestamps recorded in the slide window of blocks form an in-writing consensus for reliable use by all peer nodes in the blockchain network.
Global Clock Consensus, Part 1: Stable Local Clocks
The block timestamps specification of Bitcoin, although rather inaccurate, is good enough for permissionless blockchain nodes in a P2P network to reach a consensus, with in-writing reliability, on a time progress gap. Below are a couple of facts as global consensus for all miners.
- To process a number of blocks (e.g., 11 blocks in the case of Bitcoin’s timestamp algorithm), a blockchain must take some length of time. Miners can measure this length of time objectively by listening to the block dissemination and recording the local clock readings upon arrivals of these blocks. Most of the global miners of the P2P network will know this length of time consisdently as the number of the ticking units of their local clocks.
- Each miner’s local clock ticks in a stable pace. Miners’ local clocks need not be synchronized to a global time. Let a clock tick faster or slower than another local clock does. A faster/slower clock will always stably use more/fewer number of ticks to count the same objectively measured length of time that the miners have disseminated to the P2P network.
The title figure shows a common sense that clocks of varied tick-tock speeds can stably measure an objective length of time period. Each of these clocks keeps ticking in its own pace, to tell a collective consensus: “It’s about at 5 o’clock in the afternoon”; the minute hands of these clocks were in, and will return to, more or less the same positions one hour earlier and later.
Fortunately, any digital computer nowadays, be it a high-end server, a personal computer, a smartphone, or even a humble IoT device, has a local clock ticking stably to keep its local time consistently. In the next blog we shall describe how a miner can use its own local stable clock to express to the entire P2P network in the agreed consensus of the global time.
Global Clock Consensus, Part 2: Time Translation Between Local and Global Clocks
The bunch of good old clocks in the figure of the preceding blog post say a common sense: although those antique clocks have different tick-tocking speeds, thankfully, each of them tick-tocks stably for all to reliably reach a consensus on a rough time keeping: “It’s about 5 o’clock!” This common sense also applies to a permissionless blockchain for its miners to use independent local clocks and always reach a consensus on time of a global clock.
A miner who has accepted a number of blocks necessarily implies the following two things: (1) it has accepted the validity of the timestamps which have been recorded, i.e., in-writing, in these blocks, and (2) it can have used its local clock to have recorded, i.e., in-hearing, the local arrival times of these blocks. Notice that the length of time passage gaps between the accepted blocks in (1) has been objectively expressed to the global miners if most of them have also accepted these blocks, and the length of time passage gaps between the accepted blocks in (2) has been subjectively recorded by each of these global miners using their local clocks. Therefore, each of these miners has a mapping in-between the objectively expressed lengths of time passage and the subjectively recorded lengths of time passage. Although different ticking speeds of different local clocks record the objectively expressed length of time passage into different subjectively recorded local measures, thanks to the stable ticking speeds of the local clocks, different miners can use their different mappings to reliably and precisely translate in-between the length of time passage gaps in (1) and (2). The stable ticking speed of a local clock means that the translation function is a simple linear function.
The DaoliCloud blockchain requires a miner to express in-writing the mining time passage gap it has spent to have successfully found a valid PoW block. A dishonest expression of mining time can be easily detected. The fine granularity of the in-writing expressed mining time is sufficient to avoid “car racing crash” like accidents at the finish line of mining competition.
Proof-of-Work? Better Luck than Sweat
Bitcoin’s PoW miners are notoriously hardworking, so hard that the planet scale of mining farms pooling their combined specialized hardware can solve a hash puzzle once in an average 10 minutes. Sadly still, at this level of hardworking, the PoW competition of Bitcoin has been revealed, as discussed in our previous blog post (An Issue in Bitcoin Mining: Insufficient Competition), is insufficient and cannot prevent dishonest miners from cheating and gaining unfair mining advantage. The planet scale of PoW mining farms of Bitcoin, hugely powerful, has no good uses other than specialized hashing for block mining.
DaoliCloud aspires to be not only a blockchain enabled global payment system, but more usefully also a scalable global resource pool for providing cloud services. Permissionless participants in DaoliCloud need not use powerful machines. On the contrary, every little helps, they should use ordinary general-purpose computers to participate in DaoliCloud. Mining in DaoliCloud is only one way to earn money. Providing IT resource by building a cloud and selling cloud services can also earn money.
Block mining in DaoliCloud is also in PoW evaluation of a hash function. However, the DaoliCloud mining traffic will be much much noisier than that of Bitcoin mining. Success in DaoliCloud mining takes much shorter time than 10 minutes, our experiments show that 1 minute level of mining time would provide a nice and sufficiently fair competition to secure the blockchain. At such a level of easy mining, PoW in DaoliCloud is more about luck than power. In fact, the DaoliCloud mining is a matter of Proof of Luck (PoL). A miner’s general-purpose computer participating in DaoliCloud, besides trying luck in PoL mining which would only uses a trivial fraction of its resource, will mainly make more contribution to providing cloud services. Note, the miner is paid, probably more, for the latter!
Earn Money by Luck, Proof-of-Luck (PoL)
As Bitcoin mining, DaoliCloud mining also incentivizes a won miner with cryptocurrency coins. However, unlike Bitcoin miners who are might-is-right believers and only mine with specialized hardware pool into huge farms as huge electricity hogs, DaoliCloud miners win on luck. They mine with software running on general purpose computer such as a PC, a cloud virtual machine or container, a smartphone, or even an IoT device.
Bitcoin PoW mining is brute-force evaluating a hash function H(…, nonce, …) until finding output number being so small with numerous leading zeros (here in input nonce is a random number for a miner to brute-force search with its electricity hog). DaoliCloud mining is also a brute-force evaluating a hash function H(…, nonce, GlobalClockTime, …) until finding output being luckily small with meagerly few number of leading zeros. The additional variable GlobalClockTime input to the hash function stands for the time passage that a miner has spent on finding the valid hash function output. All miners in DaoliCloud can reach an algorithmic consensus on a global clock, so a won miner can express a time passage using GlobalClockTime to claim that it has found the valid block, and all other miners can verify the validity of this claim. (See blog posts “Bitcoin Timestamp”, “Global Clock Consensus, Part 1”, and “Part 2”.) In the next blog post we shall make it clear why a miner must honestly claim that it has spent exactly the claimed time to have luckily found a valid minding output.
DaoliCloud mining is much easier to win than Bitcoin mining. Computing power has no advantage to win DaoliCloud mining. Luck does. DaoliCloud mining is therefore trying Proof-of-Luck (PoL). Our experiments show that by limiting the winning threshold at 10 leading zeros for the brute-force hashing output, mighty computing power would have no advantage over a cloud container, a PC, a smartphone or even an IoT device such as a Raspberry-PI. To limit GlobalClockTime to a rather small value, such as being less than a minute, then a miner must be lucky to find a valid block within the claimed time length. Mining success becomes a sheer matter of luck.
The eased mining difficulty necessarily translates to hash forks which are multiple mining success announcements from multiple of different competing miners. To determine who among these different competing miners has actually won the exclusive right to writing DB is, in fact, an indistinguishable problem. Well, for an unsolvable problem, feature it!
What is a feature that the DaoliCloud mining can reinvent? It is to have sufficiently many PoL winners in a mining session. Let these winners compete who is more correct and more honest in writing the DB. That is how DaoliCloud can fix the dishonest and unfair mining problems in Bitcoin.
Luck Doesn't Lie
What if a miner uses a powerful machine, such as a big server or even a specially designed ASIC hardware, to mine PoL blocks in hope to be much quicker to succeed finding a valid block than expected software-on-meagre-machine miners do? Then the more-powerful-machine miner, upon finding a valid PoL block earlier than other miners, must also claim a respectively smaller value for GlobalClockTime which has been input to the mining hash function to output the earlier found valid block than other later succeeding miners do for GlobalClockTime values inputting to their later found blocks. Notice that the claimed GlobalClockTime is an input to the mining hash function. A miner should always input to the mining hash function an up-to-date GlobalClockTime, as it always inputs a new nonce to the hash function. That is why GlobalClockTime is claimed, since every input value to a hash function is a commitment with validity easily verifiable.
We also know that all miners in DaoliCloud have a globally agreed, i.e., globally shared, consensus on what time it is now in the global clock expression. DaoliCloud uses a pre-specified communication delay threshold, let it be denoted DELTA, to limit the valid travelling time for a block. A block must not travel longer than DELTA. That is, the time passage period between a block’s broadcasting time when a miner claims as GlobalClockTime input in the block, and the time when a block verifier receives the block, must not surpass DELTA. This block travelling time validity is verifiable by all miners in DaoliCloud. Therefore, claiming an earlier GlobalClockTime has no advantage over claiming a later but valid GlobalClockTime. All miners, whether using a more powerful machine or a meagre machine to mine, upon finding a valid block within a valid GlobalClockTime duration should better promptly broadcast the block in order to avoid enlarging the probability for the block to be judged DELTA timeout at the receiving and verification end. Obviously, no one, not even an all-powerfully-mighty-machine miner, can control on the communication delay for a block to travel through the network.
In conclusion: Investing in more powerful mining machines has no good return on investment.
Earn Money Not Only by Luck, But Also More Reliably by Selling Spare IT Resource
Earn money by PoL mining is a low-threshold and permissionless to enter “business”. The winning probability of PoL mining would understandably diminishing along the way of more and more participants joining in. Thankfully, in addition to Bitcoin’s only objective of enabling a global payment system, DaoliCloud also aspires to being a cloud resource platform.
In the very quiet traffic of Bitcoin’s mining dissemination, one won mining announcement will promptly silence all other miners of the whole network leaving them completely address-less exactly like being sucked into a black hole. All these hard PoW competing losers are actually extremely resourceful and desire to sell their resource for money. Unfortunately, the all mighty and planet scale Bitcoin resource pool is only good for one machine to be used in an average 10 minute use to enter a tiny record to the DB.
In each epoch of DaoliCloud’s forky and noisy PoL mining competition, one defork winner becomes the DB writer of the epoch. Nevertheless the “losers” have exposed their addresses in the feature designed sufficient competition. In fact, these mining dissemination exposed addresses of the PoL competition “losers” become IT resource selling data to enter the DB. To be more precisely, DaoliCloud is also an advertisement platform for IT resource owners to sell cloud resources and services over the internet.
Selling IT resources, such as CPU processing power, storage spaces, and networking connections and bandwidths, as cloud services, will become a low-threshold and permissionless to enter business.
Featured Noisy Traffic for DaoliCloud Mining Dissemination
As in Bitcoin PoW mining, DaoliCloud’s PoL mining is also brute-force evaluation of a hash function. However, as DaoliCloud features easy software mining on general purpose computers such as cloud containers, PCs, smartphones, or even IoT devices, the PoL mining of DaoliCloud has a much eased mining difficulty than that of Bitcoin’s PoW mining. Our experiments have shown that the mining dissemination traffic in the DaoliCloud network is much much noisier than that of Bitcoin. A spam prevention controllable mining difficulty for DaoliCloud PoL mining can be adjustable to 10s of blocks to be announced by 200 miners of worldwide depolyed cloud containers within a 30-second mining window for DaoliCloud vs. an average one block announcement in every 10 minutes for Bitcoin.
With the noisy announcements of the competing blocks, a PoL mining result in DaoliCloud is a forky tree from which a consensus defork algorithm will output 1 winner with the exclusive right to writing the DB, plus 10s of “losers.” These mining “losers” have had their public-key addresses widely disseminated to the entire P2P network. In essence, the noisy competing mining dissemination also forms free advertisements for the mining “losers” to, if some of them wish, sell IT resources as the main capability offer out of their mining machines!
In addition to being advertised for the mining “losers” to sell IT resources, there is another and very important usefulness for these whole network known addresses of the mining “losers”. The advertised addresses of the PoL mining “losers” are also entered to the blockchain DB. Therefore they are group lined up with the queuing positions of their public-key addresses known to the entire network of miners including of course themselves. At any occasion of DB inputting error occurrence as a result of whether a malicious attack such as double spending, a cheating action such as selfish mining, or a genuine error of undiligence, these lineup known addressed “losers” become algorithm defined legitimate competitors to correct the DB input error. We shall provide more detailed algorithmic steps in future blog posts on how this competition based noisy mining traffic effectively enables an indispensable error correction mechanism for a permissionless blockchain.
Parallel Comparison on DBMS Correctness: Indispensable for Permissionless Blockchain
In a permissionless blockchain any participant can compete to win the exclusive right to a time period, usually called an epoch, for it to exclusively maintain the DBMS. The exclusive right is of course conditional in that, the winner must perform the DBMS maintenance job correctly. All miners are monitoring the correctness for the DBMS maintenance. Competition is always on to correct error in case of spotting any incorrect conduct. In Bitcoin, this competition based error correction mechanism, as being limited by the quietness of the mining competition traffic, lacks desirable quality for a DBMS. An often discussed quality is latency. Confirming a transaction correctness has to wait for a super long time of 70 minutes. If long latency for correctness is only undesirable, then unfairness is intolerable.
What is a correct transaction for Bitcoin? An empty one is. A “Today is Friday” is too. Bitcoin miners have been maintaining the DBMS this way quite often. This mining behavior is called “selfish mining”, hashing small sized transactions is quicker than doing large sized, and quick winning sky-high overvalue priced coins as mining incentive reward gains much much more than risking lost in slow collecting transaction fees. In time of writing this blog, we have not seen a good solution to this unfair weakness in Bitcoin. Our identification on the essence of the Bitcoin mining unfairness problem can be said as follows. Mining competition in Bitcoin is in series so that there is no way for miners to compare DBMS maintenance conducts in parallel in realtime.
PoW mining is a very good approach to competition. However, PoW mining competition can hardly set a finish line for the competing miners to output blocks in some time concurrent manner for parallel comparison on the fairness in the DBMS maintenance. It is important to understand that PoW mining is competition, but competition is bigger a notion than PoW mining. In fact, PoW, or more precisely PoL, mining is a good way for a controllable non-spam quantity of miners to qualify and expose their public-key defined addresses to all miners in the P2P network. The following figure depicts a method for letting a non-spam quantity of PoL miners win qualification for parallel competition.
Let a winning probability for PoL mining control that PoL mining winners are of a non-spam quantity. Then a parallel competition can let happen amongst this quantity of PoL won miners for them to issue digitally signed blocks which are shown in the figure above as “Non-spam quantity of parallel competing KeyBlocks” which point to, i.e., follow, the “Confirmed block appended to the blockchain”. The respective verification public keys are known to all miners because they were exposed by previously won “Proof-of-Luck KeyBlocks” in the figure, to qualify their miners parallel disseminating their digitally signed MicroBlocks for parallel competition. Then miners in the entire P2P network can not only know who the qualified non-spam quantity of parallel competitors are by verifying the signed blocks using the known qualified public keys, but also pickup in realtime who among these qualified competitors will maintain the DBMS most fairly.
Since issuing a digital signature on a sizeable data for a DB entry (a MicroBlock) is an instant job, the non-spam quantity of PoL won miners can compete in realtime parallel to being the fairest DB maintainer. That’s how DaoliCloud solves the difficult unfair mining problem for Bitcoin.
The names “MicroBlock”, “KeyBlock” are from Bitcoin Next Generation (Bitcoin-NG), a very inspirational previous work we shall introduce in a near future blog post.
Byzantine Fault Tolerance
The noisy block dissemination traffic in the DaoliCloud network determines that a session of PoL mining competition should output a sizeable but not spam-volume-size forky tree at the end of the append-only blockchain for healthy competition. There is a de-forking job to select one block from these competing blocks for its miner to be the eventual winner whose DBMS maintenance job is witnessed in parallel comparison to be most correct and fair. This de-forking job is conducted on the basis of a collective decision to reflect the consensus of all miners. DaoliCloud uses a progressively renewed group of having-won-miners to be these decision makers or trustees. This idea is based on a long and well researched subject: Byzantine Fault Tolerance.
A Byzantine fault (also interactive consistency, source congruency, error avalanche, Byzantine agreement problem, Byzantine generals problem, and Byzantine failure) is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. The term takes its name from an allegory, the “Byzantine Generals Problem”, developed to describe a situation in which, in order to avoid catastrophic failure of the system, the system’s actors must agree on a concerted strategy, but some of these actors are unreliable.
The study of Byzantine Fault Tolerance (BFT), which seminally started with the work of Lamport-Shostak-Pease in 1982, has since then developed to a significant body of work. At a time, the area of study faced a pessimistic low point of a well-known conclusion “FLP Consensus Impossibility” claimed by Fischer-Lynch-Paterson in 1985. The FLP impossibility says that, in an asynchronous network, such as the internet for the case of Bitcoin, a consortium of computing and communication nodes cannot reach a consensus, i.e., a majority agreement, on a correctness condition for messages in dissemination in the consortium. In the FLP impossibility claim, the asynchronous network is considered to have an unreliability to be equivalent to the existence of even one faulty node in the consortium, not to mention a scenario of the faulty node being an active attacker.
Interestingly, Bitcoin’s robust and in good order running for more than a decade, should by now have been widely accepted that Bitcoin is the first successful BFT protocol. At the time of writing this blog post, BFT protocols are widely accepted to be useful for reliable fault tolerance computing. BFT has also found good applications in computer security as a practical approach to multiparty computation (MCP). How can Bitcoin have answered the FLP Consensus Impossibility with an evident refutation? Let us provide our explanation in the next blog.
Incentivization Induced Collaboration
Classical Byzantine Fault Tolerance protocols, e.g., Practical Byzantine Fault Tolerance (PBFT), the work of Castro-Liskov in 1999, are based on all-to-all voting. This voting mechanism typically need a designated leader, also usually called a primary, who initiates the decision process to discuss with a plural number of redundant replicas in a series of rounds of all-to-all communication to ensure that all reach the same decisions with absolute certainty. This all-to-all discussion among n nodes has an n-quadratic level of communication complexity. In the event that the leader fails, the protocol will enter further rounds of all-to-all communication to elect a new leader, and so on. In addition, all nodes need accurate knowledge of membership of all participating nodes in consensus, any errors in maintaining membership in the system, or any difference in the views of the network can lead to safety violations. With highly complex and fragile system design, high communication cost, and strong security assumption on the BFT nodes’ membership authentication, classical BFT protocols have so far found little applications with scale, and would definitely have no use for permissionless blockchain where nodes can join-in and drop-out without pre-arrangement for membership authentication.
Bitcoin’s incentive giving mining began a completely new thought in fault tolerance computing. Classical fault tolerance computing correctly considers consensus failure can be a result of either device fault, communication imperfection, or some malicious attacking action. In a public network setting where nodes need not have a common interest, classical fault tolerance computing is even more correct to point out the (e.g., FLP, see preceding blog) impossibility to differentiate these different causes for consensus failure. Bitcoin uses incentive giving mining to have made the sharp difference: the probability for a genuine fault is practically negligible, whereas that for malicious attacking is practically 1 without incentivization, but can be reduced to practically negligible with incentivization!
When malicious attackers become a smaller fraction in a group in comparison to the larger fraction of incentive seeking collaborators, it is then easy to amplify the effectiveness of the collaborators to always diminish and thwart that of attackers. Then fault tolerance computing becomes really practical. DaoliCloud shall extend Bitcoin’s inefficient non-BFT consensus to a much more efficient incentive earning BFT consensus: Incentive Byzantine Fault Tolerance (I-BFT).
Incentive Byzantine Fault Tolerance
The DaoliCloud blockchain uses a novel Incentive Byzantine Fault Tolerance (IBFT) technology to lineup noisy competing PoL miners. The IBFT group is dynamically formed by lineup miners who have recently won PoL mining and are lined up at the appending tail of the blockchain. Each of these IBFT nodes, upon hearing PoL mining success dissemination, digitally signs the ones which the IBFT node deems to be valid, and broadcast the signed result. Because working in collaboration to gain incentive reward is a bigger probable action of the IBFT group than attacking to achieve no influence and hence no effect, it will be a bigger probability for the IBFT group to usually output an group an agreement consensus, and successfully lineup PoL miners.
With a bigger probability that noisy PoL competing miners are usually lined up, in the smaller probability case when the IBFT fail to output a agreement consensus, the already linedup “losers” are in turn getting the competing right, and the protocol has not only sufficient competing supported fair DB writing correctness, but also liveness.
DaoliCloud blockchain’s formulation to lineup the IBFT group is inspired by the work of ByzCoin, however, with incentive augmentation to the BFT group by our work. The blockchain’s property of sufficiently noisy competition for parallel realtime fairness and correctness checking, and the liveness property, are inspired by the work of Bitcoin Next Generation, Bitcoin-NG. In the next few blog posts, let us review how these two previous works are useful for the DaoliCloud blockchain.
Bitcoin Next Generation
Bitcoin Next Generation (Bitcoin-NG) is among the first blockchain protocols to approach to Bitcoin performance improvement. It decouples blockchain DBMS maintenance into two phases: (1) leader election, named KeyBlock mining, to remain as solving the hard problem of Bitcoin mining, and (2) transaction lineup, named MicroBlock for actual entering data to DB, to become a much eased task with a greatly elevated throughput. Phase (2) is exclusively executed by the elected leader, by posting digitally signed MicroBlocks for the exclusive DB writing right being verifiable with the public key exposed in phase (1). Thus, the much eased phase (2) remains being permissionless yet free from spamming. This decoupling of jobs reveals an important fact: permissionless DBMS maintenance that Nakamoto invented for Bitcoin can have interesting ways to improve quality.
Bitcoin-NG focused on improving transaction lineup performance. It inspired DaoliCloud to improve stronger competition enabled correctness, fairness and more importantly, blockchain liveness. In the next blog post, let us explain how Bitcoin-NG’s idea of KeyBlock-MicroBlock decoupling has more important and more innovative use in DaoliCloud.
DaoliCloud's Innovative Use of Bitcoin-NG
In DaoliCloud, leader (in fact, the proper name is winner, as DaoliCloud is a truly P2P system having no any above-other-role node to be named a leader) election, i.e., PoL mining for KeyBlock, is a much eased job to attract software-on-general-purpose-computer mining. Therefore, KeyBlock mining, i.e., Bitcoin-NG style of DB maintenance phase (1), shall usually output a plural number of KeyBlocks to fork the end of the blockchain, and expose the public keys of the respective winners-yet-to-be. All these winners-yet-to-be are qualified to post competing MicroBlocks in which transactions can have correctness and fairness validated in parallel comparison in realtime, for selecting the best winner with the most correct and fair transactions to append to the blockchain.
Below let us describe the more important quality improvement: blockchain liveness. Blockchain liveness requires that the append only DB must always keep appending blocks in all circumstances. With a permissionless blockchain permitting at-will competition to maintain the DBMS, liveness meaning autonomous organization turns out to be a notoriously difficult problem.
Let the PoL mining won KeyBlocks nodes, i.e., the winners-yet-to-be, compete by broadcasting in parallel MicroBlocks. These winners-yet-to-be are the non-spam quantity of parallel competitors shown in the above figure. Each competing MicroBlock includes, as data to enter in DB, public-key addresses, i.e., IDs, of all other fellow winners-yet-to-be competitors, which have been exposed by their respective KeyBlocks, excluding that of the MicroBlock creator itself. This part of the MicroBlock data to enter in the blockchain DB lines up these winners-yet-to-be but actually “losers-yet-to-be” in the eye of the MicroBlock creator. Most times, a PoL mining phase shall output sufficiently many winners-yet-to-be for a healthy parallel competition for transaction recording correctness and fairness. Occasionally, a PoL mining phase may output not sufficiently many, if not empty, winners-yet-to-be, to risk lowering the competition quality, and more seriously, to risk liveness breakdown. When this happens, those already previous phases (1) lineup winners-yet-to-be qualify to join the parallel competition in a good order.
That’s how the DaoliCloud blockchain will always run with liveness.
The noisy block dissemination traffic in the DaoliCloud network determines that a session of PoL mining competition should output a sizeable but not spam-volume-size forky tree at the end of the append-only blockchain for healthy competition. There is a de-forking job to select one block from these competing blocks for its miner to be the eventual winner whose DBMS maintenance job is witnessed in parallel comparison to be most correct and fair. This de-forking job is conducted on the basis of a collective decision to reflect the consensus of all miners. DaoliCloud uses a progressively renewed group of having-won-miners to be these decision makers or trustees who are called BFT members, and form the BFT (consensus) group or consortium. Therefore, DaoliCloud is a combined protocol of BFT and blockchain, namely a BFT blockchain.
One of BFT blockchains is ByzCoin. In our view, ByzCoin is uniquely innovative among BFT blockchains in that its BFT consensus consortium is open for permissionless participation. That is, like Bitcoin, ByzCoin is a permissionless BFT blockchain. The BFT algorithm that ByzCoin applies is Practical Byzantine Fault Tolerance (PBFT). Like all previous BFT technologies using a close, i.e., permissioned consensus consortium, PBFT also uses closed membership trustees, and therefore is not scalable to supporting permissionless blockchains. ByzCoin opens the close membership of PBFT by stipulating that its BFT trustees are progressively updated using the recently won Bitcoin miners at the tail of the blockchain. The title figure shows this BFT construction: upon appearance of an extremely hard puzzle solving block from the Bitcoin mining competition, this block is appended to the the tail of the blockchain, and the miner of this block is recruited to the BFT trustees’ group. The BFT group which has w trustee members, is updated with the most aging member of w epochs old retires. ByzCoin also uses this newly recruited BFT trustee as the BFT group leader, since the PBFT protocol ByzCoin applies needs a BFT leader to act as the coordinator.
In some very rare occasion when Bitcoin mining outputs a plural number of blocks in indistinguishably close time, which in the case of Bitcoin would disputably split the Bitcoin network, ByzCoin, now with BFT trustees, can let them go through a de-forking consensus computation to select one from the forky disputers.
DaoliCloud’s use of ByzCoin’s permissionless BFT technology can be said as a streamlining simplification. The simplification is possible thanks to the fact that blockchain liveness is no longer an issue for BFT to tackle. (Noisy mining enabled parallel competition among MicroBlocks of Bitcoin-NG guarantees liveness, see the preceding blog post). The use of BFT is then only for a subfunction of multiparty computation for redundancy based reliability, rather than usual applications of BFT for a much harder problem of consensus agreement.
DaoliCloud's Streamlined Use of ByzCoin
Conventional use of the BFT technology is about for a plural number of computers as redundancy replicas to discuss in all-to-all communications and hopefully reach a majority consensus agreement on a computational decision. Many years of research effort has accumulated abundant of knowledge. A consensus seemingly has prevailed: it is a notoriously hard problem for nodes over imperfect network to reach a majority consensus. The situation for any resultant BFT technology to find an application in permissionless blockchain is particularly and factually hopeless. In a permissionless blockchain, there seems no way to discern a malicious attack from network imperfection, true one or in the guise of. That is why so far known applications of BFT in the area of blockchain have been for permissioned cases, such as Proof-of-Stack. The attempt in the case of ByzCoin began in 2016, without success in the time of posting this blog.
Blog post “DaoliCloud’s Innovative Use of Bitcoin-NG” explains that the important property of blockchain liveness for DaoliCloud is provided by noisy mining enabled parallel competition among MicroBlocks of the Bitcoin-NG technology. Provided that a simple majority of DaoliCloud miners follow the protocol, a lineup “winners-yet-to-be” buffer is always stockpiled with plenty of readily competing nodes to keep the blockchain running lively. This liveness assurance measure is in particular applicable to some rare occasion when the BFT trustees fail to output a consensus agreement. Thus, DaoliClous’s use of BFT no longer has a fear of consensus failure. Streamlining simplification for the ByzCoin BFT formulation becomes a reality for first time.
In DaoliCloud’s simplified use of the ByzCoin’s BFT formulation, there is no need of a leader to coordinate an all-to-all communication. Communication in Bitcoin like broadcasting among all miners suffice. BFT members each independently verifies disseminated blocks, certifies valid ones and broadcasts its certification to the P2P network. Notice that these BFT members are incentive motivated, and hence their collective certification should usually reflect the consensus of the whole network of the miners in terms of DBMS maintenance correctness and fairness. When this usual case is the case, the BFT outputs a unique multiparty computation based majority de-forking result, and the blockchain lively appends ahead with the DBMS maintenance in good order. In an unusual case when the BFT fails to output so, the more often usual case lineup “winners-yet-to-be” nodes whose public-key IDs are data in the DB and hence with their qualification status to compete known to the entire P2P network of miners shall come to play in a new round of noisy and healthy MicroBlock competition.