What is round robin mining? Is a 51% attack on Komodo possible?

komodo

#1

Easier to read version: http://coremedia.info/index.php/blockchain-news/item/383-james-lee-and-juan-s-galt-on-dpow-s-security-vs-51-attack

js.galt [7:10 AM]

Hello everyone. I got some questions about DPOW, for a follow up video I want to do on the topic.

@jl777 who’s game?

[7:10]

I’ll start with this one. What is round robin?

jl777 [7:25 AM]

originally blocks were mined in strict order by the eligible notary

[7:26]

however that led to a dependency on all notaries to be always mining

[7:26]

but that is how the name round robin started

[7:27]

the algo was changed to allow any notary that hasnt mined a block in the last 65 blocks to mine at easy diff. it isnt exactly round robin, but the net effect is that blocks would go to notary nodes 1 at a time

js.galt [7:46 AM]

so now notary nodes don’t always have to be mining? or is it to account for temporary interruptions in up time

[7:47]

with the current algo, notary nodes now mine at normal difficulty, untile they reach the 65 block threshold and then it gets lowered?

jl777 [7:49 AM]

notary nodes mine at normal diff, unless they havent mined a block in the last 65

[7:49]

that means each notary only gets one easy diff block per 65

[7:50]

there is also a 63 block free for all starting at 2000 block boundaries

[7:50]

if a notary node doesnt mine, then an external miner will mine that block at normal diff

[7:51]

it is a fairly simple algo that has evolved, but it handles all the requirements, including not allowing a diff explosion as the few percent of blocks that have to be mined at normal diff ensures that the diff stays close to mineable difficulty

[7:53]

it also makes any 51% mining attack quite unlikely as the more external mining there is, the more effective mining the notary nodes get, but the notary nodes dont incur any costs. It will be quite difficult to dominate 51% of mining power when 97% of blocks are able to be mined at easy diff

js.galt [7:56 AM]

ok. here’s an interesting question. given this algo. is it possible for notary nodes to collude and do a 51% onto komodo non notary nodes?

jl777 [7:56 AM]

notary nodes are not mining new blocks, so all you know about 51% attacks via mining does not apply

[7:57]

51% of notary nodes could prevent notarizations

[7:57]

if they try to notarize garbage hashes, it is just ignored

[7:58]

basically notary nodes notarize, so a 51% attack of notary nodes would have the power to notarize whatever they wanted. however, all nodes make sure that the notarizations are for valid blocks as anything else wont make sense, so this means 51% of notary nodes can notarize any valid blockhash, ie the attacker can do proper notarizations

[7:59]

more likely scenario is for 51% notary attacker to just not notarize at all, weakening the security of KMD. However, in this case, we can revise the list of pubkeys to valid notaries with a new version

js.galt [8:00 AM]

so, when we talked about notary nodes (NN for short) mining a block easily at the 65% mark. what are they actually doing? are they including mem pool transactions to the KMD ledger, or something else?

jl777 [8:01 AM]

a better attack vector for such an attacker is to try to change the paxprice feed. however this attack has a problem as all such modified prices are signed and therefore the attacker will be identified and it wont have any effect until many hours of price feed is corrupted

[8:01]

not 65% mark

[8:01]

most recent 65 blocks

[8:01]

they are mining like normal, they just get to use a minimum difficulty

[8:02]

the notary nodes mining is normal mining, only difference is the difficulty that is required, ie lowest diff

js.galt [8:03 AM]

so, if say 33 of all nns are compromised. they could potentially mine 33 blocks in a row to their convenience. would the normal nodes follow their version of the chain?

jl777 [8:04 AM]

yes

[8:04]

a mined block is a mined block

[8:04]

but you can only mine validly signed transactions

[8:04]

so an attacker could prevent a valid tx from being mined

[8:05]

but its not like since they can mine blocks, they can put whatever they want into the blocks

[8:05]

the blocks must be valid

[8:06]

any attempt at double spends is avoided by waiting for notarization as the notarization will select only one of the two conflicting spends

[8:06]

without the ability to double spend, taking over notary’s economic value seems to be the value of the mined KMD

[8:07]

and also, there is no assurance that the attacker would get 33 in a row as there are the 31 honest notaries still mining

js.galt [8:07 AM]

so to succeed at a double spend. they would have to sign two conflicting transactions. the fraud one and the selfish one. and time it with the 51% attack. so they get say a big KMD to btc trade. and get to keep the KMD as well.

jl777 [8:08 AM]

how does it work if the user waits for notarization"

js.galt [8:08 AM]

how long is the wait for notarization?

jl777 [8:08 AM]

only one of the spends can be part of the notarized blockhash

[8:08]

10 minutes

js.galt [8:08 AM]

how long are kmd block times?

jl777 [8:09 AM]

1 minute

js.galt [8:11 AM]

and the notarization process, its basically backing up a valid transaction onto bitcoin.

So 33 compromised NNs could at 1 KMD block a minute, do about 33 minutes of the double spend chain. aka 3 notarized blocks. no? worst case scenario (edited)

[8:11]

backing up a valid block

[8:11]

onto bitcoin

[8:13]

so there’s a near 50 50 chance that they will fail. since it is 33 blocks in a row . there’d be a fork in the network.

jl777 [8:15 AM]

the chances of 33 blocks in a row by attacker is infinitesimal. as an attacker gets a block, that node is not eligible to mine another for 65 blocks, so the more in a row they get, the lower their chances for the next one. Say a 1:1000 10 blocks in a row happens, now there are only 23 attackers left and 31 honest nodes

[8:16]

also, not sure how you postulate a fork in the network

[8:16]

having a low diff block does not allow you to mine an invalid block

js.galt [8:18 AM]

a double spend would have valid transactions. when you sign to separate transactions, to two different public addresses. one gets sent to the victim in exchange for say btc. And the other to your self. then you start the 51% attack. and reject mining the tx sent to your victim. after they have sent the btc to you.

jl777 [8:19 AM]

if we assume that people are waiting for their tx to be notarized, then how do you double spend?

js.galt [8:19 AM]

they would have to wait for more then 3 notarized blocks

jl777 [8:19 AM]

i dont understand. once a block is notarized it is locked in

[8:20]

so if the valid tx is notarized, it cant be undone

js.galt [8:20 AM]

but a double spend block could be notarized no?

jl777 [8:20 AM]

since it cant be undone, how to double spend?

js.galt [8:20 AM]

oh i see

jl777 [8:20 AM]

no

js.galt [8:20 AM]

so all of KMD waits for notarized transactions

[8:20]

gotchsa

jl777 [8:20 AM]

it is up to the user

js.galt [8:20 AM]

right

jl777 [8:20 AM]

if you are doing a 100BTC transaction, just wait for it to be notarized

js.galt [8:21 AM]

right

jl777 [8:21 AM]

then any attempt at doublespend is invalid

[8:22]

KMD dPoW and round robin mining changes the playing field in a somewhat subtle way, but the end result is a system that allows users to be much more secure and where the attack vectors are there but of much smaller impact

[8:23]

if you dont wait for notarization, then all the 51% attack scenarios are possible, with the twist of the notary’s mining at easy diff. hard to compete against a node that has a free pass at a block, so really for any sort of pre-notarization attack to have a good chance of success, you need much much more than 51% of notaries

[8:23]

80%, 90%, something like that

[8:23]

plus a careless victim that doesnt wait for notarization

js.galt [8:25 AM]

ok well. i see now how notarization brings btc’s security to an altcoin chain. and how waiting for notarization gives you bitcoin level security to your transaction.

jl777 [8:25 AM]

and assetchains that notarize to KMD piggyback on this

[8:25]

but without any BTC fees

js.galt [8:25 AM]

as far as pre notarization attacks. I’m still not clear on that. why it would have to be so high. Would have to do the math.

[8:26]

right

jl777 [8:26 AM]

if 33 attacker nodes, it mines a block, now 32 vs 31

[8:26]

it gets another, 31 vs 31

[8:26]

the more blocks in a row, the less eligible attackers left

js.galt [8:26 AM]

riiiiight

jl777 [8:26 AM]

at some point it is down to 10 attackers against 20+ honest nodes, so 2/3rds chance of not getting a block

[8:27]

so that is why you need 80%

[8:27]

to get an effective 51% chance

[8:27]

but i havent done the math, it might be 90% needed, i guess it depends on the length of the chain trying to be rewritten

[8:27]

but here is another problem for the attacker

[8:28]

after 10 blocks, it is notarized and cant be changed

[8:28]

so the attacker has a 10 block window to conduct the attack

[8:28]

i guess if majority of notaries are compromised then they can stop notarizing to expand their attack window

[8:28]

however, then everybody notices that notarizations are not happening

[8:29]

and anybody doing large tx should be very careful if notarizations have stopped

js.galt [8:29 AM]

yeah.

[8:30]

lets say notarization is offline. just because.

what would be the recomended confirmation times for KMD?

jl777 [8:30 AM]

I just dont see any practical chance of a double spend attack in the context of regular notarizations every 10 blocks

[8:30]

wait for notarization for any tx you consider big

js.galt [8:30 AM]

yeah, I see your point. you’d need a great majority of nns

jl777 [8:30 AM]

wait for 2 for something you consider really big tx

[8:31]

lets say you have all the NN’s compromised. you still cant do a double spend

[8:31]

as long as people are waiting for notarization

new messages

js.galt [8:31 AM]

true

[8:32]

cuz now they are secured by btc. attackers would have to double spend on btc as well.

8:32]

or get a fake block mined

jl777 [8:32 AM]

so the practical function of compromising majority of NN is to stop notarizations, degrading the security level

js.galt [8:32 AM]

which raises the costs dramatically

jl777 [8:33 AM]

if you can rewrite the BTC chain, why would you bother with KMD or notaries?

js.galt [8:33 AM]

indeed

[8:33]

cool. glad we got through that PHEW.

[8:33]

hehe

jl777 [8:33 AM]

all the implications of dPoW are not immediately obvious

js.galt [8:34 AM]

yeah, it’s a kind of sidechains really. with its own independent mining network. very interesting

jl777 [8:34 AM]

when combined with the round robin implementation, it is especially difficult to see all the improvements as it comes from somewhat complex dynamical system

[8:35]

and the independent mining is very energy efficient 95% of the time as it is via minimum diff

[8:36]

yet it still allows external mining and has a seamless transition from ordinary PoW mining vs round robin

[8:36]

I am quite pleased at how everything came out


How does Komodo mining work (technically)?