Discussion about dPoW solution (part 2)

Justin Ehrenhofer came back in Komodo Discord for another round of conversation (see previous post). Here’s the edited transcript

######BEGIN

sgp
Hey @jl777c, thanks for talking with me yesterday. I’m back with two diagrams and one simple question: which chain would nodes consider to be valid?

Diagram 1: https://i.imgur.com/ySkCOOr.png

Diagram 2: https://i.imgur.com/oRHME4s.png

jl777
ChainB won’t be accepted by nodes. Even evil notaries won’t be able to convince them to accept it as the notarization already happened after the third block. Anything at or prior to the notarization will be rejected, by nodes that have validated a notarization

sgp
Let’s take diagram 1 and say a specific node saw chain B first. Would it reject chain A?

jl777
First you need to realize the second slide scenario won’t happen, as both A and B can’t be notarized

sgp
I’m talking about diagram 1 right now, chain B doesn’t have a notarization in diagram 1

jl777
Ok, in that case a node sees chain B, but it won’t be notarized

sgp
Right, so the node would accept chain B as correct, and ignore chain A, correct?

jl777
Chain B node will be operating as normal rules. When chain A becomes longer than chain B, the normal rules apply and chain B node will reorg to the longer chain A. At that point it sees the chain A notarization and won’t switch back to B

sgp
All right, I understand where you are coming from there

jl777
So in a chain split, nodes on the non-notarized chain can switch to the notarized one, but not the other way around. This reduces the time it takes for the “eventual consensus”

sgp
Understood. Now on to diagram 2, can you explain why a notarization of the second chain isn’t possible?

jl777
All the notaries are running a full node and they need to reach consensus as to the (height + blockhash) since we have a chain A notarization after the third block, that means chain B is dead to the notaries and from the above discussion we see that a node won’t switch from notarized to non-notarized, so the notaries won’t switch to chain B and thus can’t reach consensus for the chain B notarization

sgp
By “they need to reach consensus“, are you referring to all the notary nodes or the 13 nodes?

jl777
All the notary nodes reach consensus and 13 of them sign

sgp
Can you speak more about the consensus process where they all get on the same page?

jl777
For a given notarization, the notaries are numbered from 0 to 63, the one that is 0 changes each notarization to give each notary equal chance over time to participate in notarization. Now all 64 nodes broadcast to each other their notarization data, along with the info they got from the other notary nodes. Based on this, nodes propose the 13 signers for this round such that all of them are in agreement. At first there is maybe not so many nodes that agree on all details but the proposal with the most support is switched to by notaries that are not already there, so after several rounds things converge so that we get 13 nodes all in agreement. Then this is latched and the 13 nodes generate signatures, broadcast them and all the nodes reconstruct the 13 way signed tx and broadcast it. It is actually quite a process and took a while to get it efficient with a high completion rate. The notaries are tuning their systems to maximize the number of notarizations they participate in and you can ask them about the randomness, it is not possible to know ahead of time which 13 nodes the group will converge to

sgp
So if even 1 node disagrees on the notarization, they can’t notarize anything? Actually wait let me think more…

jl777
It is resistant to a single node disagreeing. All nodes can make proposals for the selected 13

sgp
All right, so of the 64, 13 are selected who get to make decisions. All nodes propose blocks to notarize. Do you need all 13 people to agree for a proposed block to be notarized?

jl777
Yes but it is the 64 as a group that decides. There are a LOT of possible 13 signers of 64, mathematically 13 choose 64…

sgp
What do the 64 as a group decide?

jl777
…so a deterministic algo is used to reduce the selected 13 for each notarization round, but still there are thousands of possible 13. A 64 bit number is used as a bitmask to denote the chose 13.
The requirement is that it starts from the current iterations node 0, must have 13 bits set and each node in the bitmask must have the identical data. So this bitmask can’t be created until several iterations of communications between all the nodes, then nodes start proposing the mask to use. Nodes tally what the other nodes see and determine which is most popular, they then switch if they are not already using the most popular mask. Critical is that all 13 signers agree on the mask, as if the other nodes select a bitmask, but any of the 13 are not also in agreement, it won’t sign it and the notarization won’t work. It is somewhat similar to mining, randomized and hard to predict which 13 “win”

sgp
Yes, the 64 have a process for randomly selecting the 13 and, if even 1 of the 13 disagrees, then it does not get approved

jl777
Over the years, the algo was improved to select the 13 that are all in agreement

sgp
Is there some sort of time-out process? What if 1 node disagrees with everything in perpetuity? Can the 64 nodes select 13 other random nodes?

jl777
I must not have explained clearly… it is not about 1 node agreeing or not. Every node broadcasts to all other nodes what it thinks should be the 13, also it broadcasts what the other nodes sent to it. So all the nodes can see what they get directly and also what the other nodes are seeing. Given that, they are able to select the 13 who are in agreement and converge to the 13. If a node doesn’t agree, and doesn’t shift to the winning 13 bitmask, it is just ignored

sgp
Ok, it makes more sense, thank you. You always select 13 nodes that are in agreement

jl777
The group does, using what is basically a decentralized process, even if only 64 nodes

sgp
Suppose there are two factions, each with 30 nodes, that are in disagreement. How would the selection process work?

jl777
In a chain split scenario, consensus is not reached. 13 out of 64 does not sound like a giant percentage, but if there is any significant disagreement, the notaries won’t be able to settle on a bitmask for 13, with all 13 signers agreeing to it

sgp
How many nodes need to be in disagreement for them not to agree on selecting the 13 nodes?

jl777
There is not exact threshold, but I estimate approx one quarter to one third. You have to understand that unless there is a chainsplit, there is agreement on all nodes

sgp
Yes, but that’s sort of like a statement like “there is no disagreement if everyone agrees.” I’m trying to predict attacks that could happen if people disagree. Thanks for answering my questions so far. I will think more about the situation and get back to you if I have any other questions

jl777
To create disagreement, the chain needs to be split. If you are mining in private, then none of the notaries would have that chain, so it needs to be broadcast, but if it is broadcast then it is subject to the notarization rules. I guess if an attacker starts mining from the last notarization and propagates it to many nodes, well if they do that, it becomes the mainchain and gets notarized

Emmanuel
Chain split… I imagine that could be possible in extreme cases, like worldwide broken internet, with continents isolated from each other, but 13 out of 64 not reaching consensus… for no reason, not so likely.

jl777
Basically everything needs to be working properly for notarizations to happen. The notary operators can attest to this. So absence of notarization is a good signal that some sort of blockchain event is happening

sgp
One last question: let’s assume the unlikely event of 100% notary collusion. Would they be able to notarize chain B as shown in figure 2, and if so, would nodes on chain A reorg to chain B?

Emmanuel
Interesting question @sgp, like contradicting themselves

sgp
Yes, exactly. I want to know what other nodes would do in that scenario

Emmanuel
Well, you could do that, in a scenario like I described above, but artificial, and then I guess that manual resync would be required (according to what jl777 explained yesterday)

sgp
Would the process of switching to chain B from A be automatic?

Emmanuel
I don’t think so, it would be manual resync, as jl777 explained yesterday. So yes, notaries could create havoc, but destroying their business at the same time, it would be a suicide and the damage (inflicted to the chain) wouldn’t be permanent, as a manual resync would fix the issue

sgp
It seems to me that it would depend on how the code was written. if it’s written for a node to never reorg past the last notarized block it has in its cache, then it would have to be manual. But if it’s written for a node to never reorg past the latest notarized block it can find, then it could be automatic as it finds the latest one on the other chain

Emmanuel
We discussed this yesterday, remember?

sgp
I’m reading the logs now

Emmanuel
I think that the answer to that question was given implicitly yesterday

sgp
From what I can tell, the answer was to a different scenario

Emmanuel
Maybe a third protection layer could be activated? Against this very improbable attack?

jl777
If the chain B is the real chain and becomes much longer than chain A, then nodes will switch automatically

sgp
Even if chain A has a valid notarization after the split point?

jl777
I mean for new nodes. If a node got the chain A notarization, then they are stuck on that chain until they invalidateblock the one with the notarization

sgp
So that would require a manual pop process

jl777
Usually a resync won’t be needed, just to invalidate the chain A notarization, but that is up to each node. So any attempt to switch the main chain from A to B via notarizing B, this is a very noticeable process

sgp
I understand it is very noticeable

jl777
And there would need to be overall consensus on which chain it is the correct chain, trying to get a double spend through via this mechanism is not very practical. It would be much easier to 51% attack a non-notarized chain. My claim is that dPoW isn’t perfect, but it sure is better than without having dPoW for a chain without a large hashrate

sgp
Yeah, but it by no means lives up to KMD’s marketing that it has the security of KMD+BTC. In our discussions these past two days, we’ve talked about limitations where the attacker doesn’t touch BTC at all. I plan to make another writeup that more clearly indicates the situations that can occur and what the possible damages are. I appreciate your time

jl777
The notary nodes are validating to BTC

Emmanuel
@sgp it’s better security than KMD+BTC, because, how many BTC pool operators are out there?
Is it more probable that they will collude? Or 64 notary nodes? dPoW security is KMD+BTC*Notary network. Try to break that.

polycryptoblog
And the consensus of the protected chain

Emmanuel
( KMD + BTC * Notary-Network ) + Notarized-Chain

jl777
@sgp point is that if the notaries collude they can create confusion

Emmanuel
Same could be said about BTC, if the pool owners collude… bad things would happen. If a meteorite hits the earth… we could probably have many chain splits… Earth is not safe. Proven.

sgp
Even without notary collusion, a 51% attack with the longest chain would create confusion for nodes

jl777
Even without notarization, a 51% attack can cause confusion AND double spends

sgp
And with notary collusion, they could notarize a different chain, contradicting their previous notarizations

jl777
The evil notaries can 51% attack a chain easier than if it is a notarized chain

sgp
Yes, a 51% can create double spends even without notary collusion for dPoW. That’s the main point I’m trying to get across

jl777
No, i mean a chain without dPoW. You have not shown any case where a double spend can happen on a dPoW’ed chain and just because you repeat that over and over, it does not make it true

sgp
This is exactly what figures 1 and 2 show the opportunity for

polycryptoblog
Just do the attack if you can

jl777
Where is the double spend?

sgp
Figure 1 shows you can convince the network to use a different chain, even before the point of last notarization.
Figure 2 shows you can convince the network also, but with added notary node collusion

Emmanuel
No, @polycryptoblog he’s saying that the notary nodes could, not an external attacker

jl777
You can convince a node that didn’t see the notarized chain that there is chain B. Once it is notarized, it can’t be double spent

sgp
If they resync, that’s not true

jl777
If they resync, chain A wins as it has the notarization. Chain B would never get above 1 “confirmations” as it never got a notarization. So anybody on chain B wouldn’t honor any payment

sgp
That’s a local user config though

jl777
I think you are ignoring the part of following whether a tx is notarized or not. Ok, so if the user (exchange) allows deposits after 1 confirmation, then maybe you can double spend on the non-notarized chain

sgp
I understand there are limitations that are put in place, but these simply make the attack harder, they do not make it impossible

jl777
You are only talking about attacking the non-notarized chain, which doesn’t have a notarization, so doesn’t have the notarization protection. dPoW protects the notarized chain, not the non-notarized chain! You shouldn’t be misrepresenting that notarization doesn’t prevent double spends. You can clarify that non-notarized chains can be double spent. Practically speaking what exchange credits altcoins after 1 confirmation?? I would say the attack even on the non-notarized chain is MUCH harder and for the notarized blocks, not possible

sgp
jl777 that’s semantics though, since you could replace the notarized chain with a non-notarized or even a different notarized one. That argument is basically saying that you can’t double-spend if you only use one chain, which we know is false since an attacker spins up a different chain

jl777
There is only one notarized chain, it is either notarized or not notarized

sgp
Unless collusion, which we discussed

Emmanuel
meteorites
aliens

sgp
@Emmanuel you could say the same for a 51% attack

jl777
That attacker can spin up a different chain, but it is either notarized or not

Emmanuel
@sgp not true, 51% attack on BTC would require what? 4 people to collude?

Alright
What’s the proposed attack vector of the day?

jl777
He has some chart that shows impossible states and claims it shows a double spend

sgp
@Emmanuel how about this: VPS/server infrastructure providers colluding?

Emmanuel
@Alright: split chains, both notarized, generated by split iguana network

Alright
Can someone link to chart please? Did you make a new medium post?

sgp
@Alright I did not make a new post yet

jl777
Chain B was never notarized

sgp
It is in figure 2

Emmanuel
@sgp that is more serious talking, and that’s a good point that could be improved (infra provider attack)

jl777
So it never gets the protection from notarization. Ok, so you finally agree that in figure 1, there is no double spend?

Alright
Chain B would never get notarized, that is indeed an impossible state. Your “what if” is a chain split due to differing consensus rules

sgp
Figure 1 is a double spend to people who do not require a notarization, or simply count the # of block confirmations. It is not a double spend for people who count notarizations

Emmanuel
@Alright unless 100% of notary node operators collude to split iguana network.

Alright
@sgp you get it now

sgp
@Emmanuel not 100%, that was just the example

Alright
Transactions aren’t truly secure until they’re notarized, so don’t accept them as a deposit until they are

jl777
But even if figure 2 happens, where is the double spend? Each node is either on chain A or chain B and there is a massive chain split event for the community to resolve

sgp
jl777 if an attacker makes a payment in chain A that is notarized (and therefore confirmed), then creates chain B with no transaction included

Alright
Chain B doesn’t exist, doesn’t matter at all

Emmanuel
No double spend

Alright
It’s orphaned by the entire network

jl777
He is talking about the impossible state of figure 2, where there are two notarized chains

sgp
“Improbable”, but even there would be issues with figure 1

Alright
Again, your “what if” is based on a chain split due to differing consensus rules

Emmanuel
no, @Alright he’s talking about all notaries colluding to purposely break a chain

jl777
But the evil notaries would have an easier time to attack a chain if it wasn’t notarized at all

Alright
What if all BTC pools colluded to break BTC? Oh what, they have no reason to do that?

jl777
So even by this fantasy scenario, dPoW is making it harder to attack a chain

Alright
That’d be them working against their best interest, huh? Weird

sgp
jl777 sure, but they could need it for a deposit, or a number of other scenarios, such that it was after a recent notary election, etc. In this case, the attackers could use the notarization to their advantage, since services look for one notarized block confirmation rather than several normal blocks, itbgives a 51% attacker an easier time since they need to produce fewer blocks

jl777
Again you don’t understand and leap to conclusion. The number of confirmations stays at 1, until there is a notarization, after that it is normal. So if an exchange makes no changes to the existing confirmations, it only makes it wait for notarization and never any easier

Alright
Back to work, excited to see tomorrow’s proposed attack vector 🙂

sgp
I understand that. My point is that instead of waiting for 10 or so blocks, they only wait for 1 notarized block, which is less total work to attack

jl777
No, they should wait for 10 confirmations as normal, it just stays at 1 confirmation until a notarization. So 10 is still 10, unless it is more than 10 if the notarization took longer. A notarized “10” is NEVER less than 10. It seems you are so eager to find some horrible flaw, which is fine, but if you are not basing it on facts then it is fantasy

sgp
Can you explain again the conditions where the software reports 1 or 2 confirmations?

jl777
The logic is that it reports as 1 confirmation until it is notarized, it might never report 2 confirmations

Emmanuel
1 dpow-conf, (2 conf, 3 conf, 4 conf, 5 conf+notarized)=>2 dpow-conf, (6 conf)=>3 dpow-conf …

jl777
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 12

sgp
Thanks @Emmanuel, I take my point regarding reducing total work back

jl777
So for chain B it stays at 1

sgp
It could still be an issue of elections or some other situation though

jl777
What does elections have to do with anything? The worst that happens with new notaries is that maybe there are not enough and there are no notarizations until there are

sgp
The elections would change the pool of notary node participants. If someone is not currently a notary node but knows they will be one in a few days, they could attempt this

jl777
Attempt what?

Emmanuel
huh?

sgp
Figure 2, where they make a deposit on chain A, then attempt to notarize chain B

jl777
Convince all the others to do a difficult to do chain split, dual notarization, combined with a double spend and convince the community to adopt the chain where they didn’t deposit to the exchange that was 51% attacked? That scenario?

sgp
You asked why someone would do so after creating a false notarization, and I’m giving some examples

Alright
@sgp best to just ask us how the election works instead of making assumptions about it then basing attack vectors on those assumptions

sgp
I never claimed they were practical

jl777
So impractical and uneconomic fantasy attacks? That is what you are making a big deal out of?

sgp
No, I still find figure 1 concerning, since even if an attack isn’t successful, it would severely slow down the network. There are other considerations, but you only seem interested in talking about a 51% attack

sgp
I have shown situations where they are possible, though they are unlikely

jl777
Slow down the network? Having competing chains is normal

sgp
I appreciate this conversation, I will write up another article later. Have a nice day

jl777
How does it slow down the network? Plz try to keep it factual

Alright
what situations did he show were possible?

jl777
Notaries collude to do chain split, dual notarization, combined with a simultaneous double spend and convince the community to adopt the chain where they didn’t deposit to the exchange that was 51% attacked

Alright
Is there some way of preventing a chain split even if notaries do collude? A split notary network, however unlikely, could be a problem. It could happen with no malicious intent, again unlikely

jl777
Yes, but it needs to be combined with a precisely timed 51% attack and then to convince the community to allow the double spend as the split chain will need to be resolved by the community

Alright
Get an exchange on each chain, sell same coins on both, no 51% attack involved at all

jl777
The important thing to observe is that even though it is theoretically possible, it would be much easier to 51% attack a chain without dPoW. Why add notarization to make things harder to attack?

Alright
In the event of a chain split, it’d be fairly hard to send the same coins to different addresses on each fork

jl777
So it doesn’t really increase the risk exposure to 51% attacks, in fact it seems to reduce the potential 51% attackers to the notaries

Alright
Not really related to what I was just saying, but I was trying to think of how you would even do that

jl777
In a chain split, it splits really cleanly into two independent chains

Alright
We’ve seen chainsplits that share mempool, never understood how that happened: DEX split in ~Feb

jl777
So using the chain split notarization for 51% attack, reduces the possible attackers to notaries, from everyone. It seems an improvement. @alright mempool can have tx that haven’t been spent on either chain

Emmanuel
@sgp you would need at least 26 suicidal notary nodes colluding, to perform such an attack, I think, and I doubt it is possible. Please elaborate more on exactly how such attack would work. It is too theoretical to even take it seriously. I say 26 because you need two groups of 13 isolating themselves from the rest

grewalsatinder
@sgp even in case you are intentionally trying to find a problem in dPoW while there is nothing found, I enjoyed the whole conversation. Would love to see more of such conversations here again. I agree on the point that dPoW is not perfect, but I absolutely disagree with you that any of the marketing that Komodo Platform Team has done is either false or misleading. I still encourage you to feel free to ask as many scenario you can make up. If you could find any legitimate loophole in the dPoW you for sure be even rewarded for your findings. So far I see you couldn’t find any.


######END

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s