By: Michael Sutton, Core Developer<\/p>\n
This is a blog series explaining the fundamentals of Kaspa in simple and short language. I will assume the least possible prior knowledge, although some fundamentals in blockchain theory, specifically bitcoin, may benefit the reader.<\/p>\n
<\/p>\n
Kaspa is a pure PoW engine which generalizes and scales bitcoin\u2019s blockchain paradigm.<\/p>\n
<\/p>\n
The first change Kaspa introduces is the block-DAG mining paradigm. In bitcoin, miners first select the longest (or to be precise, the heaviest) chain and mine over its top-most block, aka the selected tip. Thus essentially miners do not share the full information they have \u2013 they do not share the knowledge of other non-selected chains they know of and chose not to mine over.<\/p>\n
In contrast, in the block-DAG paradigm, all information is revealed. We call it \u201cthe revelation principle\u201d. The miner references all tips he knows of. Following, any protocol can be ran to make choices over this knowledge, including for instance the longest chain rule, however the maximization of shared knowledge opens many more opportunities.<\/p>\n
In essence, by each miner mining over all known blocks, a maximal amount of time relations (e.g. this block was mined \u201cafter\u201d this block) is revealed and shared.<\/p>\n
Having each miner mine over many block tips (referencing all their hashes in its header), creates a directed graph of blocks with a link pointing from a block to each of the referenced blocks. The cryptographic irreversibility of the PoW function implies that no cycles can be created in this directed graph, making it a D<\/strong>irected A<\/strong>cyclic G<\/strong>raph.<\/p>\n <\/p>\n The set of blocks referenced by block B<\/strong><\/em> are parents(B)<\/em><\/strong>. The set past(B)<\/strong><\/em> is the set of blocks reachable from block B<\/em><\/strong> through a chain of parent links (coined \u201cpast\u201d because we know they existed before B<\/em><\/strong>). Note that past(B)<\/em><\/strong> is never empty since it always contains genesis which is the initial block defining the begining of the DAG. Likewise, future(B)<\/em><\/strong> is the set of blocks which B<\/em><\/strong> is reachable from. The set anticone(B)<\/em><\/strong> is the set of blocks \u201cparallel\u201d to B<\/strong><\/em>, i.e., not in its past nor in its future. Essentially no time causality information is known between B<\/em><\/strong> and blocks in anticone(B)<\/strong><\/em>. We call it \u201canticone\u201d because both past and future can be seen as \u201ccones\u201d from B<\/em><\/strong>\u2019s perspective.<\/p>\n <\/p>\n Before delving into the specifics of the GHOSTDAG protocol, which is the ordering protocol used by Kaspa, I\u2019ll describe a general structure for ordering a block-DAG based on any parent selection rule.<\/p>\n Assume a parent selection function f<\/em><\/strong> mapping from each block B<\/em><\/strong> to one of its parents P<\/strong><\/em>. The sub-DAG containing only these special \u201cselected\u201d links (from every block B<\/strong><\/em> to its selected parent) is in fact a tree. Let\u2019s name a special non-existing block called \u201cvirtual\u201d, which always points at all DAG tips\/leaves. This virtual block represents the next mined block in the eyes of the local node.<\/p>\n The mapping function f<\/em><\/strong> can be applied on virtual<\/em><\/strong> in order to select a specific DAG tip. We can then walk down starting from this tip through the \u201cselected parent\u201d links until reaching genesis. So a mapping f<\/strong><\/em> can be translated to selecting a chain C<\/strong><\/em> of blocks starting from virtual<\/em><\/strong> and ending at genesis<\/em><\/strong>.<\/p>\n This chain can be used to deterministically order the complete DAG structure.<\/p>\n To accomplish this task we need one more definition. Let\u2019s define the mergeset of B<\/strong><\/em>, mergeset(B)<\/strong><\/em>, to be the set of blocks that B<\/em><\/strong> merged into the DAG. Formally this is the set of blocks which are in past(B)<\/strong><\/em> but not in the past of B<\/strong><\/em>\u2019s selected parent as chosen by the mapping function f<\/em><\/strong>. It\u2019s called a merge-set because it\u2019s the set of blocks that B<\/strong><\/em> merged into the DAG from his perspective relative to its selected parent perspective.<\/p>\n Given a chain C<\/em><\/strong> and the definition of a mergeset, we are ready to describe a complete ordering rule based on f<\/strong><\/em>. The idea is to start from genesis<\/strong><\/em> and walk up this chain, where at each chain-block we add his merge-set to the ordering. Intuitively, the chain here acts as a spine of the DAG, where the merge-sets are layers added one after the other. To see this more clearly note that from the definition of a mergeset and its relation to the proceeding chain block, it follows that all mergesets are disjoint sets and that their union covers the entire DAG.<\/p>\n The simple pseudo-code below describes exactly this and is brought here for reference.<\/p>\n function Order-DAG(G<\/strong><\/em>):<\/p>\n <\/p>\n Understanding the relation between a chain and DAG ordering helps reasoning about the relation between a chain selection protocol and the security properties required from a secure ordering protocol.<\/p>\n For a block-DAG representing a transaction ledger, we\u2019d like that the ordering of the DAG is \u201crobust\u201d in the sense that only a small set of blocks near the tips of the DAG might change their order. In other words, we want the ordering to \u201cstabilize\u201d for any block mined \u201cenough\u201d time ago, where enough depends on the amount of certainty required.<\/p>\n Because ordering is governed by a chain, it follows that if the chain is \u201crobust\u201d, i.e., does not change up to a suffix, then the DAG ordered by it is robust as well. Thus all we need now is a secure way to find a robust chain \u2013 a secure parent mapping function f<\/em><\/strong>.<\/p>\n <\/p>\n In the following post I\u2019ll write about the special parent selection function f<\/strong><\/em> = GHOSTDAG and will give more rigorous definitions for related terms used in Kaspa such as \u201cblue score\u201d, \u201cblue work\u201d, etc.<\/p>\n I chose to explain about the chain structure first, because I think it\u2019s crucial to understand this decomposition for getting a clear understanding of the Kaspa system. Regardless of the f<\/em><\/strong> used, this chain structure is used by our UTXO algebra infrastructure and also plays a role in the framework we implemented for supporting DAG reachability queries.<\/p>\n","protected":false},"excerpt":{"rendered":" The block-DAG paradigm By: Michael Sutton, Core Developer This is a blog series explaining the fundamentals of Kaspa in simple and short language. I will assume the least possible prior knowledge, although some fundamentals in blockchain theory, specifically bitcoin, may benefit the reader. What is Kaspa? Kaspa is a pure PoW engine which generalizes […]<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","inline_featured_image":false},"categories":[4,13],"tags":[],"yoast_head":"\nSome block-DAG terminology<\/h4>\n
Ordering a block-DAG<\/h4>\n
\n
\n
Chain security implies robust DAG ordering<\/h4>\n
Next post in this series<\/h4>\n