Claire: On August 8th, we made a theme sharing entitled "DAG's Past and Present (1)", which received enthusiastic attention and discussions from many friends, and many people in the same way also joined [Magic Piper Community] . Today, the guest speaker Mr. Wu Min will continue the theme sharing of "DAG's Past and Present (2)", further explaining more technical details, difficulties, solutions and tools of BlockDAG, in order to let everyone have a deeper understanding of BlockDAG, welcome You can ask questions later in the Q&A section to dig deeper. Now Mr. Wu Min... 👏👏👏
Today's sharing is mainly aimed at developers, and many programmers only know slang (slang). I try to share it in an easy-to-understand way, so that everyone can benefit.
1: Soteria is the infrastructure technology of "Self Sustainable Decentralized Economy" (SSDE - Self Sustainable Decentralized Economy).
2: Soteria is developing a holistic solution to solve some of the pressing problems of the current generation of blockchains, while providing an adequate feature set for the decentralized economy it envisions - such as a blockDAG based scalable throughput.
3: DAG is called a directed acyclic graph.
4: BlockDAG is called a block graph. There is a huge difference between BlockDAG and TransactionDAG. For details, see the part about transaction DAG in the previous sharing.
5: Soteria DAG is actually an extension of the Bitcoin Nakamoto consensus algorithm, making it inclusive and providing flexible and scalable features on the basis of ensuring security.
The block diagram looks like this:
In this example. At the bottom is the GENESIS block, and the arrows point from a block to its parent. If a block is not a parent of any other block, it (they) are called tips of the current block graph. For example, the tips in the picture above are M, J and L. Genesis, parent, and tips are all very important concepts, which we will repeatedly mention next.
On the premise of inclusiveness, how to ensure safety? For example, what about malicious mining? Here we will talk about Phantom and Greedy Phantom.
What are Phantoms?
Phantom is a staining/sorting protocol invented by Yonatan Sompolinsky and Aviv Zohar. Its implementation is the following three main steps:
1: A set of well-connected blocks is identified. This is called the blue set. Other blocks, such as only referencing older blocks, or blocks that have been hidden for a period of time, will be excluded from the blue set with a high probability.
2: Perform topological sorting on the block diagram, giving priority to the blocks in the blue set, and lagging behind the blocks that are not in the blue set.
3: When sorting and checking transactions, the sorting of the block diagram will be used, legal transactions will be adopted and malicious transactions will be discarded.
Let's see what the colors of this graphic might look like with a Phantom or Greedy Phantom.
The picture above shows the result after coloring with Phantom (Greedy Phantom is similar), we look at how to color from the perspective of block M. In the middle part of the block diagram, there is a set of well-connected blocks; at the same time, some blocks (red) at the border of the block diagram are not so well-connected.
We use a system internal constant (k) to make this decision. How k is selected will be explained in the future technology sharing. This means that the blocks of the same level of red set will be arranged behind the blue set of blocks. Note that not all the red blocks are arranged behind all the blue blocks. Blocks without color (J and L) do not belong to M's "past set", they will be sorted behind M.
The sorting result (from M's point of view) is:
GENESIS, C, D, E, H, B, I, K, F, M, J, L
During the dyeing and sorting process, the Phantom needs to:
1: Determine whether it is well-connected by analyzing the past and future of a block.
2: Traverse the block graph and color each block.
3: Sort.
Let's take a look at what is Greedy Phantom, authored by Aviv Yaish:
1: Basically the same concept as Phantom, the goal of Greedy Phantom is to be simpler and more effective.
2: The coloring part is inherited from the bluest parent.
3: Coloring and sorting are incremental modes.
The coloring part is inherited from the bluest parent, also known as the coloring parent. The collection of colored parents will continue from the current block to the genesis block (genesis), which is also called the coloring chain of the current block.
The difference from Phantom is that the coloring of Greedy Phantom is inherited, and the sorting of the blocks before the bluest parent is unchanged. On the contrary, in the Phantom algorithm, since each block needs to consider the past ( past) and future (future), so the color of each block may change in the future, depending entirely on how connected the block is in the future.
Let's take a look at the coloring process of Greedy Phantom as blocks are added to the block map.
GIF
In this animation, in addition to the blue, red, and transparent blocks, there are green and dashed border blocks.
Green: represents the dyed tip
Dotted: the dyed chain of the current block. (the bluest parent set)
Blue: The collection of blue blocks, which refers to the perspective of the latest block (well-connected, well-connected)
Red: Blocks outside the set of blue blocks, from the point of view of the latest block (not very well connected)
It can be observed that some blocks change color (between red and blue) from the perspective of the latest block. It can also be observed that when the angles are different, the dyed strands are also different.
At the beginning of the DAG, when B, C, D, and E were added, the colored chain did not become these new blocks. This is because of an internal tie-breaking rule where when two or more blocks are equally blue, the block with the lower hash wins. In this example, B is the first (lowest) of the letters, so B wins.
To summarize the calculation differences between Phantom and Greedy Phantom (affecting engineering practice):
When Phantom dyes, it will use the past and future of a block. As the block graph grows, the future of a block will grow infinitely.
Greedy Phantom will only consider the past of a block when dyeing, because the block graph continues to grow, making Greedy Phantom a better choice for dyeing/sorting engineering.
If you have to use Phantom, you can achieve a similar effect by setting the lower and upper bounds of the node's past and future traversal
However, restricting the past and future of nodes may affect the coloring effect, so it is not ideal.
Our code base contains the implementation of the two, the purpose is to compare their differences in the future, and also provide more reference for other developers.
Next, I will explain in detail how we modify the code to achieve the purpose of expanding the blockchain into a block diagram.
The project implementation block diagram (BlockDAG) includes the following contents:
Prune the existing code, remove the code that can only serve the blockchain scenario, and include a lot of code that will complicate the development of BlockDAG and not help much.
Implement the core module, which represents the block diagram (the old code represents the blockchain), and provides the same or similar service functions as the blockchain module, such as:
Find the function of tips;
Find the parent block according to the existing block;
Retrieves the block map for the specified range.
Updated the block data structure (this is the most important data structure in all blockchain projects😯).
Adding an area can store more parent information, because in the block diagram, each block can have multiple parents (Bitcoin can only have one).
Updated the encoding and parsing methods of the protocol layer (encoding/decoding)
Updated and added tests (test)
Mining procedures updated, there are other places where it is possible to traverse the blockchain/blockgraph:
Added new P2P and RPC calls
getdagtips rpc call
renderdag rpc call
addrcache p2p call
Updated the code for the network synchronization section
Added system integration tests,
Generate a block graph (originally the blockchain), confirming that each block can have more than one parent block.
Confirm that the block graph can be synchronized across different full nodes.
Confirm that the mined SOTO can be used for transactions.
(Actually, there are a lot of long-winded words. For those who don’t write programs, just remember that changing the public chain code is not an easy task. It’s better for programmers. :P… Programmer friends, see our github for details )
The above changes were made through several different stages, mainly because the amount of changes at one time was too large and the risk was too high. We have also developed a lot of tools to help understand + analyze block diagrams and troubleshoot. The tools will be shared later.
I know that everyone has watched the text live broadcast for so long, and it has been very hard. One of the big questions in your mind is,"A picture is worth a thousand words". Dude, where's your picture? ? ?
Picture coming soon.
ok let's continue...
Challenges encountered:
In the development process of the project, many blockchain codes need to be updated to support the block graph. Generally, there are three different types of challenges:
Blockchain assumptions.
In the existing code, due to the different system design, many places assume the blockchain by default.
Peer-to-peer (p2p) synchronization.
Encoding and parsing at the protocol layer.
Blockchain assumptions:
Part of the code needs to be refactored. For example, in the blockchain, the height of a block is the number of blocks between the current block and the genesis block. In the block graph, a block can have multiple parent blocks, some of which may be more directly connected to Genesis than others. So in the block graph, the height of the block is now the maximum height in the parent block + 1.
In the figure above, the height of block K is 2 if it passes through the path of B; it is 3 if it passes through C, D, and E. So we consider its height to be 3.
Orphan block processing:
Z-shaped dag
An orphan block is like this. When a full node receives a reasonable block, but cannot find the past (past) of the block, so it cannot be connected to the existing block graph, the block is blocked. called orphan blocks.
In a blockchain, orphaned blocks are processed from the top down, starting with the orphaned block and then its parents. In the block graph, this traversal method is problematic, especially if there is a Z-saped dag in the block graph, some blocks will be ignored. We have made adjustments to this algorithm, using depth-first sorting of search results to include all blocks.
(I know this passage seems very brain-inducing, and you just think, how pitiful are orphans, of course they have to be treated differently)
Duplicate issues in orphan block handling (knots)
For parts of the block graph with high connectivity between blocks, orphan block processing will take longer because each path
Connections will be retraced. We have built a cache for this, recording orphan blocks that have been processed and their past.
(That is to say, too much special treatment for orphans will also have an impact on the system)
tool:
Below we introduce some development tools. We have added the coloring function to the code of soterd for the purpose of:
1: It helps to check the implementation of the block diagram or synchronization problems. It is much more useful to see the block diagram intuitively than to only see a set of hash values in the log file.
2: Provide an interface for upper-layer applications (such as browsers).
dagviz:
Dagviz : https://github.com/soteria-dag/soterd/tree/master/cmd/dagvizDagviz is a command-line tool that
It will start several soterd full nodes (yes, full nodes), let them mine and exchange blocks, and record the results step by step, which you can playback (via browser). Each block is colored according to their miners, so that it is very intuitive to see that each miner contributes to the network. Dagviz can be used to display soterd and block diagrams, and can be used to measure the impact of algorithm changes on mining fairness.
min :
(Remember, dagviz will let several full nodes run on your computer, so the CPU requirements are not low)
dagparam Related Links dagparam https://github.com/soteria-dag/soterd/tree/master/cmd/dagparam Dagparam is a tool for exploring different peer-to-peer network parameters. Such as targetTimespan and targetTimePerBlock, and how these parameters affect the composition and propagation of the block graph.
Dagparam is a tool for exploring different peer-to-peer network parameters. Such as targetTimespan and targetTimePerBlock, and how these parameters affect the composition and propagation of the block graph.
For example, when the block generation speed exceeds 62.5blocks/second, that is, one block every 16 milliseconds, the synchronous code will have unstable performance.
Soterdash is a web UI for browsing block graphs and full nodes in the soterd network. It can display all or part of the block diagram, and clicking on each block will provide more detailed information, such as Header, MerkleRoot, etc. During our development, Soterdash helped a lot, especially when troubleshooting.
The last tool, the last must be the best.
go repo sync
The vast majority of our codebase is written in Go. Go does not allow relative import paths, which makes sharing code between different forked/copied codebases a very complicated process. Our development process involves multiple versions and code sharing in different directions, so we developed this tool ourselves to help synchronize between different code bases. It automatically transfers the changed part to the target code library, and makes necessary changes at the same time, for example, the place that originally referenced the old code library will be replaced with a new one. The specific steps are as follows:
- Processes the current project and the predecessor projects it depends on.
-Copy the current project and the target project to the staging area.
- Synchronize current and target projects with git archive.
- Remove unwanted files in the target project with git rm.
-Replace referenced files and links.
- Update module names for go.
- Add the new files needed to the target project.
-Submit to local
- Commit to target git tree.
- This tool is currently in a private repository (private repo), but we can provide open source on demand. This project can be helpful to the majority of go programmers.
(Repeat, not only blockchain programmers, all go programmers are helpful, of course, there are many blockchain programmers who don’t use go)
Thank you for participating in our sharing today. Technology grows in the process of continuous discussion. That's all for today's sharing, the following is the Q&A session, please ask questions.
The following is an excerpt from the Q&A highlights:
seabook: @min@soteria shared a lot of depth today, what is your economic model?
min : Oh, that's the topic of our next sharing:
SSDE (SELF SUSTAINABLE DECENTRALIZED ECONOMY)...You read my mind.
seabook: Please give a brief reminder.
min : https://www.ssde.io/ It is now in English, and the shared content will be in Chinese. We have also specially recorded two podcasts, talking about UBI.
@min@soteria i enjoy reading your article.
Zhu Jiang²⁰¹⁹: seabook, the economic model you mentioned refers to the macro model or the micro model. On the macro level, as @min@soteria mentioned, our SSDE proposal is on the ecology of the soteria dag itself, such as the reward mechanism incentive design, etc. We will cover this in the technology sharing later.
seabook: incentive design
Zhu Jiang²⁰¹⁹: seabook, SSDE and soteria are neither UBI nor communism, they still advocate the spirit of struggle and distribution according to work. It is just some decentralized enhancements to the existing centralized economic system: fairness, tolerance, security, privacy and scalability. Incentive design, you are also a fan of game theory, right? Please pay attention to our sharing later.
seabook: I will pay attention.
Claire: Thank you very much for your attention, and thank you for all the broadcasting platforms. You are welcome to continue to discuss Blockdag's technology in depth later. This is the end of this topic sharing. After sharing two very hard-core topics, we will continue to share with you other topics closely related to our lives, including economy, finance, privacy protection, big data analysis, business models of blockchain projects, etc. Everyone is very happy If you care about the content, please continue to pay attention to the follow-up topic sharing. . . Thanks again to the guest speaker Mr. Wu Min for his careful preparation and detailed sharing!
