* This series of articles is a high-quality blockchain research article output by The core blockchain research group of Blockchain, aiming to study and share the underlying blockchain technology principle analysis, new technology trends, and refuse to discuss any token, market and investment advice.

In the previous article “In-depth Blockchain Consensus (III)”, we took BurstCoin as an example to introduce the implementation of PoC consensus algorithm in the project in detail, mainly focusing on the generation of Plot file content, detailed interaction with block generation and calculation process.

In this article, we will extract several core issues of PoC consensus process, compare Stefan Dziembowski’s model, and discuss the similarities and differences between it and Burst. Combined with the introduction of BASIC PoC file structure and mining process, it can help us better understand PoC algorithm.

How to solve the time synchronization problem in distributed nodes in the process of block generation based on Deadline

As a special type of distributed system, blockchain system inherits the characteristics and problems of distributed system. Readers familiar with distributed systems may know that there is an important distributed system feature that must be taken into account when designing distributed systems, namely lack of global clock.

In BurstCoin system, different miners broadcast blocks with different deadlines to different nodes, and different nodes have different understandings of the current clock. How does the node determine whether the current block can meet the broadcast conditions? How can I verify that the deadline of a synchronized block received from the network is valid?

In order to solve the problem of out of sync caused by different clocks, in distributed systems, it is generally necessary to form a logical “clock” so that everyone recognizes this “clock” rather than their own clock.

The first implementation of this logical clock is Lamport Timestamps. Although the academic value of Lamport timestamps is greater than the actual value and they are not actually used by the system, the Vector clocks in and out of Lamport timestamps are widely used by AWS S3, DynamoDB, Riak and other systems to ensure the causality of the same object.

Vector Clock’s algorithm relies heavily on trust between nodes, so it can only be used in a trusted distributed environment. Blockchain systems, which run on P2P networks where nodes do not trust each other, cannot ensure this. So how does a distributed system like Bitcoin determine time? In the design of Bitcoin, Satoshi Nakamoto cleverly applied the product of PoW, block, as the logical time of the system (quoted in the Bitcoin white paper) :

The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post.[2][3][4][5] The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

Each block contains a Unix time timestamp. 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 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. Whenever a node connects to another node, it gets a UTC timestamp from it, and stores its offset from node-local UTC. The network-adjusted time is then the node-local UTC plus the median offset from all connected nodes. Network time is never adjusted more than 70 minutes from local system time, however. Bitcoin uses an unsigned integer for the timestamp, so the year 2038 problem is delayed for another 68 years.

BurstCoin also inherited the core idea of BitCoin to some extent, timestamp exists as a logical sequence rather than a real exact time.

It is generally allowed to be off by 1-2 hours from the actual UTC time. At the same time, the particularity of BurstCoin is that whether a block can be successfully linked is directly related to the deadline calculated. Therefore, we can find the following verification process in BurstCoin source code:

This compares the value of the current block deadline with the difference between the current block TIMESTAMP and its precursor TIMESTAMP. Timestamp, which is the time offset relative to the first block with block height 0, allows a certain degree of error. To the extent that error permits, there is no need for a global clock, and blockchain systems form a consensus about “timing”.

Verify the validity of Deadline

When I began to read BurstCoin’s source code, I once wondered how to verify the validity of the deadline of a block without Scoop, which is used for the current block production, and does not involve Merkle’s operation in the block database.

Remember that in the second article in the series we discussed Stefan Dziembowski’s PoC system, which uses the Merkle Tree to simplify the verification process, and there is no Merkle Tree calculation in BurstCoin.

After a thorough reading of BurstCoin’s source code, the author found that BurstCoin adopted a more ingenious calculation method to verify the consensus parameter Deadline calculated based on the stored content in PoC consensus. Let’s expand the explanation below:

  1. When a node receives a historical block from a P2P network, or a minted block broadcast by a miner, it first performs a preVerify operation on the block, where scoopData is always null in the parameters submitted by the caller, because in the data store used by burstCoin, The block field does not store scoopData. So how do you do that?

  1. The answer lies in the calculateHit method. BurstCoin put part of its node’s function methods into a separate JAR package of burstKit. After finding its calculateHit method, we find that it calls the initialization method of MiningPlot.
  2. In the MiningPlot method, we can see that two nonce files can be completely generated by nonce Id and accountId, using the nonce Id and accountId parameters. Therefore, in BurstCoin, the miner does not need to send the 256KB Nonce file to the node, but only needs to send the block content and these two parameters to the wallet node when participating in the block production, and the wallet can calculate the entire Nonce value. At the same time, after receiving each block, each node on the whole network calculates its deadline by calculating this Nonce.

After understanding the validity verification process of Deadline in BurstCoin, let’s compare it with Stefan Dziembowski’s protocol process. In BurstCoin, the initialization of BurstCoin’s storage file F is completely non-interactive because there is no Merkle tree calculation.

Miners simply follow the protocol and generate Nonce files with a specific graph structure. In Burst, Nonce files are algorithmatically generated in batches. In fact, the calculation process of Nonce file is completely consistent with Stefan Dziembowski’s graph model, where each Hash is the W value in the Nonce graph structure, and the graph structure used in BurstCoin is not exactly the same as Stefan Dziembowski’s. But it also has complex precursor and successor and connection relations. Burst did not provide the theoretical proof, but the general proof idea is similar. Interested readers can explore it here.)

This is undoubtedly very important optimization, because in distributed system, complex interaction often brings complexity of protocol, and because there are a large number of nodes in the network, the complexity of interaction often becomes difficult to achieve because of the network delay and network fluctuation in P2P network.

Stefan Dziembowski’s use of Merkle’s structure in the verification phase makes it extremely efficient, but in real distributed systems with large networks, fewer interactive steps and simpler protocols often mean higher reliability.

At this point, BurstCoin chose the additional 8192 Hash computations required by the nodes during the validation phase to bring about a completely non-interactive file initialization during the initial phase, and a smaller network data transfer during the validation phase (just a few fixed parameters like the node sending including the Nonce Id, accountId), Undoubtedly, it is more suitable for the blockchain system itself.

On the other hand, the relatively complex initialization process proposed by Stefan Dziembowski is more suitable for federated chain systems and blockchain systems with permissions, and some peer-to-peer systems with better network conditions.

How does BurstCoin handle forks

In a PoW consensus blockchain system, the logic for dealing with forks is simple and unambiguous, and all honest nodes should assume that the longest chain in the current network is the main chain. But things are not so obvious in the PoC consensus. Compared to the Bitcoin block time of ten minutes, most of the time was spent on the miner’s calculation of the nonce for the current block, which consumes a lot of CPU time.

Since BurstCoin mining itself does not require intensive CPU computing time, miners can often complete disk traversal within 30 seconds, and the deadline calculated is the real control of block time. Therefore, the judgment of main chain cannot only be based on the longest chain.

In Bitcoin consensus, the length of the chain reflects the CPU computation amount invested on the current chain, while in Burst, the indicator reflecting the disk space occupancy is the number of valid deadline accumulated. Of all the competitors for a block with a high plus one, the miner producing the block with a smaller deadline is likely to use more storage space and thus gain block casting rights.

Similarly, if you consider forking scenarios, how does Burst determine which chain is the primary chain? How would an honest miner choose two branched sub-chains?

In the real Burstcoin system, the concept of CumulativeDifficulty was introduced.

Its calculation formula is as follows:

Meanwhile, baseTarget needs to recalculate for each block:

In BurstCoin, all honest nodes should consider the current chain with the greatest CumulativeDifficulty as the main chain of PoC consensus.

This conclusion is not complicated to understand.

By observing the calculation process of baseTarget, we can see that the deadline of the current block will affect the mining difficulty of the next block, that is, the smaller the current deadline is, the smaller the baseTarget of the next block will be. At the same time, CumulativeDifficulty reflects the sum of the difficulty of all blocks of each sliver chain because the difficulty added to the current block is greater.

Like the PoW idea, the length of a chain essentially represents the amount of computing resources invested in that chain. In PoC, CumulativeDifficulty intuitively reflects the number of storage resources used on the current chain through the index.

Through the detailed discussion of these three issues, combined with the source analysis, I believe that readers can understand the content of PoC consensus, ideas and algorithm details by thorough and detailed understanding.

This is the end of the PoC series of articles. In the future, we will discuss more technical topics in the field of blockchain. If you are interested in a specific field, please feel free to comment.

Blockchain series articles are dedicated to sharing the underlying technical knowledge in the blockchain field, and strive to provide original and in-depth technical content.

While exploring blockchain innovation from a technical perspective, Chainbo Technology also thinks deeply from the perspective of industrial integration, promoting the construction of blockchain projects, and providing professional, easy-to-use, full-stack blockchain chain reform services for enterprises.

Follow our previous articles and leave your thoughts in the comments section.

—————–

Reference source

  • [1.]Spacemint:A Cryptocurrency Based on Proofs of Space
  • [2.]BHD whitepaper
  • [3.]BurstCoin Introduction Serious
  • [4.]Proof of Space
  • [5.]Burstcoinist
  • [6.]Proof of Space from Stacked Expanders
  • [7.]The Burst Dymaxion
  • [8.]burstforum
  • [9.]mining tutorials
  • [10.] Cynthia DworkMoni Naor,Pricing via Processing or Combatting Junk Mail
  • [11.] Giuseppe Ateniese, Randal C. Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary N. J. Peterson, and Dawn Song. Provable data possession at untrusted stores. In Peng Ning, Sabrina De Capitani di Vimercati, And Paul F. Syverson, Editors, ACM CCS 07, Pages 598 — 609. ACM Press, October 2007
  • [12.] Kevin D. Bowers, Ari Juels, and Alina Oprea. Proofs of retrievability: Theory and Implementation. In CCSW, Pages 43 — 54, 2009
  • [13.] Nikolaos P. Karvelas and Aggelos Kiayias. Efficient proofs of secure erasure. In Security and Cryptography for 9th International Conference on Networks – 9th International Conference, SCN 2014, Italy, September 3-5, 2014. Proceedings, Pages 520-537, 2014]
  • [14.] Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015). Proofs of space. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9216(616160), 585 — 605.
  • [15]Bitcoin White Paper