Thread by @MichaelSuttonIL

Dagknight (DK) is a new protocol recently published by myself and @hashdag eprint.iacr.org/2022/1494.pdf

In this 🧵 I try describing why on earth does PoW mining translate into mathematic optimization, and why one might think that DK optimization is a fundamental point in this >

> optimization space.

#Kaspa enthusiasts have come to be familiar with the live DAG visualization kgi.kaspad.net where blocks rapidly arrive at a single-second rate. It seems natural that the observed structure of blocks is not a chaotic mesh of blocks, but >

> rather appears as a “thick” chain with nearly constant width. Let’s try and break down the process which leads to this familiar structure.

In a DAG mining environment, an honest miner constantly attempts at mining new blocks, where the new block template always >

> references all DAG leafs (i.e. blocks which no one has referenced yet – at least from the point-of-view of the local node). Once a miner finds a block, it is broadcasted to the entire network asap through his P2P peers. Essentially the honest miner wishes to minimize >

> latency and avoids censorship (by referencing all known blocks) or withholding (by publishing asap).

One can notice that indeed the observed DAG “width” is a result of both the block rate and the average network latency. Assume D is the maximum time in seconds between >

> finding a block and until the entire net is aware of it. A node mining a block can only be missing blocks mined in the last D seconds. Similarly, only blocks mined in the following D seconds might be unaware of this block. This bounds the average number of parallel >

> blocks (“the width”) by a constant which correlates to D and to the block rate λ (specifically 2Dλ).

This fact was noticed in the Ghostdag (GD) paper by @hashdag, @DesheShai and @Avivz78 eprint.iacr.org/2018/104.pdf (the current Kaspa protocol), in which they suggested to >

> formulate the DAG ordering problem as an optimization seeking to find the largest set of blocks which are sufficiently connected, where “sufficiently connected” means that for each block in this set, there are no more than “K” parallel blocks (within the set). Since >

> honest miners hold a majority, we recognize that this largest set is the set of honest blocks (w.h.p.) – hence they (aka the Kaspa blue blocks) proceed in consensus ordering other relatively-disconnected blocks (red blocks).

But what is the value of K?
The reasoning I >

> described above gives a natural answer to this question. As the protocol designer, you estimate – based on maximal block sizes – the maximal latency D, you plug-in the block rate λ, and with simple probability calculations you come up with a value of K which is >

> sufficiently large to incorporate all honestly-mined blocks.

What happens if your estimation D’ is smaller than the real D? Well, you compromise security. Consider for instance a tight D’=2 seconds estimation, leading to K’=5, while the real D=10 and following K=18. Hence >

by allowing at most 5 parallel blue blocks, you actually miss out a large percentage of honestly-mined blocks. Which means that an attacker with less than 50% can now overcome this overly-trimmed honest set 😐

This is the reason D’ must be estimated with a large safety margin >

> such that it will never be lower than the actual network D.

But do we lose anything from this overly-estimated margin? The answer is yes, we lose in confirmation times. Consider that we overestimated and set D’=10, K’=18 (in fact, this is the Kaspa selection), however >

> the actual average delay is D=2 and the DAG width appears to hardly surpass 5. This means that effectively an attacker can deviate from honest mining by censoring or withholding blocks in the previous/next 10 seconds (which are more than the natural real D=2 seconds), and >

> the protocol will still consider her blocks as “good” blocks. Intuitively, the protocol is blind to the “amount of connectivity” below the hardcoded K bound, which gives the attacker a slight surface to work with. In order to overcome this, the confirmation policy of the >

> protocol must literally consider D’=10 to be the latency and must approve transactions in time which is proportional to D’ units.

But can we do better? This seems like an inevitable protocol decision…

THIS is where the DAG Knight optimization rises to provide answers. >

> DK seeks to define the optimization in a way that favors both having “more connectivity” and being a “majority”.

In order to deeply understand this subtlety, note that DAG mining and the resulting DAG structure, is unaware of any protocol >

parameter **. This property of DAG >

** Unlike other scalable PoW frameworks which are not based on a pure DAG but rather introduce a parametrized mining space – usually based on a combination of multiple chains, where the number of chains is a function of the overestimated D.

> mining was coined by previous work as the “direct revelation principle”; I personally like to “abuse terms” and say that DAG mining is “responsive” to actual network latency.

This property of DAG frameworks means that the real optimization target, i.e. the largest >

> K-connected set for the *correct and tight K*, is still hiding in the observed structure and we just need to find the way to reveal it. The attached screenshot describes the optimization target we eventually arrived at. On the one hand we wish to maximize >

> connectivity, hence minimizing K is a target, however we cannot tolerate finding a K-cluster which does not hold a majority of the observed DAG, hence we increase K until finding such a set. Henceforth the set of blocks found by DK, is not the dichotomic “honest set” – DK >

> lives in a world of relativity, it finds a sufficient portion of honest blocks which are maximally connected and large enough to counter the attack.

––––––––––

This thread, though long, basically covers only the foundational idea of DK. The initial “sparkle”. In following >

> writeups I hope to introduce the additional complexities we faced when realizing DK into a secure protocol – or of course, you can find these details in the paper linked above.