search

ArkEcosystem / AIPs

ARK Improvement Proposals
26 stars 25 forks source link

AIP:25 - Discussion #39

Closed moazzamak closed 3 years ago

moazzamak commented 5 years ago

Discussion thread for AIP 25: Providing PoW like guarantees on (D)PoS networks

roks0n commented 5 years ago

c/p discussion between @n4ru and @moazzamak from Slack:

Moon (biz_network) [6:08 AM]
@mak You vastly underestimate the downsides of (D)PoS and the scope of the problem - it 
doesn't just stop at round generation and double forging (which is only an issue for DPoS 
solutions that prioritize liveness over safety). There are also better less complicated 
implementations for preventing double forging, but your solution is a good PRNG method for 
determining rounds. (edited) 

Also since you cannot guarantee identical states across the network in the event of 
multiple submissions, this goes back to square one of the issue and doesn't solve any of 
the consensus issues with PoS, which is the entire reason PoW is seen as superior. This 
is where the entire nothing-at-stake meme comes in and is the largest issue and most 
pertinent issue PoS has. (edited) 

Look into Ethereum's research, they have many years of research built onto PoS systems 
and have thrown out probably half a dozen implementations by now due to flaws. Their 
latest that they are working on is correct by construction which only moves forward 
when CBC-Casper can guarantee that all nodes will agree on the same state in the 
future, which is the only acceptable way to do PoS consensus without compromise. It's 
not perfect yet and they have already discarded Slasher (discarded because of 
eclipse/sybil attack vectors and is why I am against double forge banning), 
consensus-by-bet (discarded due to P + ε attacks and other issues), and other ideas. 
It's a bit naive to think you've made PoW useless just by solving round generation, 
when random round generation is easily the smallest problem PoS has. (edited) 

Moon (biz_network) [6:19 AM]
Nonetheless, using mental poker style PRNG hashes with n-depth is a good way to do 
round determination pseudorandomly and would require a lot of collusion to break, but
becomes incredibly taxing computationally which is likely why DPoS systems which have 
the advantage of short block times don't use it - Ark v2 already has a LOT of crypto 
related performance issues and I'm worried this is a major downside to using such a 
system, especially as you increase the depth requirement to prevent collusion attacks. (edited) 

Moon (biz_network) [6:26 AM]
I like the implementation, but I think the clickbaity title that claims to solve PoS 
issues ("Providing PoW like guarantees") is incredibly disingenuous when it doesn't 
even approach the fundamental consensus problem PoS has. This is a good step in 
preventing double forging from desyncing the network (though it only makes it harder 
to happen accidentally, it doesn't eliminate the problem that other PoS systems already 
have eliminated by sacrificing liveness for safety [see FLP impossibility, nothing is 
"free"] to guarantee the network is always safe), but I think making broad claims like 
that is dangerous. The only way for a PoS system to be as safe as a PoW one is to not 
only agree on a state, but only accept said state when you can mathematically conclude 
that other nodes WILL arrive at the same state as you no matter what, which is the 
basis of Ethereum's correct-by-construction research. (edited) 

mak [6:39 AM]
Hey Moon. Thanks for the feedback. The main inspiration for this AIP comes from from 
dfinity's approach. The point of the AIP is to be able to follow the longest chain 
similar to proof of work but without the proof of work. IMO this approach should allow 
us to do that. And all of the features you mentioned come out as a result of that 
ingredient. Double forging prevention is not really the goal here but only an 
interesting addon. (edited) 

As far as i know only dfinity has tried to replicate the longest chain valid feature 
in a PoS setting though their approach uses a different block propagation algorithm 
that is IMO unproven.

Moon (biz_network) [6:49 AM]
My biggest issue with dfinity's approach is it doesn't seem to solve long range attacks
at all which are arguably the biggest weakness in PoS and PoW's biggest strength. Long 
range attacks are exponentially more likely and easier to do in DPoS specifically.
Even correct by construction has not solved this yet and that is the key piece that can 
actually make PoS as safe as PoW.
Unlike PoW which scales exponentially to make long range attacks impossible, no amount of 
hashing proofs can stop a single actor from overtaking the chain instantly on PoS. Hence 
the whole nothing at stake issue being the biggest problem (because there's no work when 
you can generate all the blocks in a static amount of time!)

mak [7:02 AM]
Thats not really true in the case of my aip or dfinity's approach. At least as long as 
you have a significant minority following concensus properly. The reason is that both 
approaches use PRNG to give the right to forge next block to a certain miner for a 
limited time slot. Also in my AIP the idea is to have a mandatory cooldown period after
a block is forged but perhaps i forgot to mention that in the aip ifself. And in the 
normal mode a node wont accept blocks that arent close in time to its own clock. 
Therefore you would need majority of nodes misbehaving to allow someone to catch up 
in terms of blockheight with a long range attack.

Moon (biz_network) [7:02 AM]
You don't need anyone to catch up, that's how a long range attack works.
"Time" is not consensus.
Just because you SAY you forged at timestamp n doesn't make it true
In PoW consensus does not take time into account, only PoW
PoS systems and especially DPoS systems heavily rely on agreements on time.
I will forge a longer chain instantly and claim fake timestamps that you can't 
prove after voting in all my delegates.
You will never be able to prove you have the valid chain.

mak [7:04 AM]
My node wont accept a block to be valid unless i received it in a certain amount of time. 
Combined with the cooldown it will prevent long range. (edited) 

Moon (biz_network) [7:04 AM]
Then you have weak subjectivity and are relying on checkpoints from a trusted source and 
new nodes cannot sync trustlessly

Which just dodges the problem with centralization unless you find a way to do consensus 
from block 1

Centralization is the opposite of a solution to PoW

mak [7:06 AM]
No. The only assumption being made here is that 51% majority of the nodes in the network 
are reachable and live at any given time.

Moon (biz_network) [7:06 AM]
No it isn't.
You cannot sync from 0 without centralized trust, you said so yourself you won't accept 
blocks too far back
Once you drop thta barrier you can be long range attacked.
If you don't drop it you're trusting a centralized source.
If you just give up and say "just use the majority" then you immediately die to sybil.

mak [7:08 AM]
Sync mode ignores the above restrictions. I do accept that if there is a major data 
corruption on the chain which knocks out majority of nodes then sure you can carry 
out long range attack.

Moon (biz_network) [7:09 AM]
You don't need to corrupt anyone or knock anyone out.
I can sybil any PoS network in seconds.
If your final defense is relying on "proof of IP" then your network is fucked.

mak [7:10 AM]
You wont have a valid claim if you try to sybil using relays

Moon (biz_network) [7:10 AM]
You don't just sybil
You combine it with a long range attack
A sybil will guarantee your long range attack goes through
And it will become not just the longest chain but also the majority valid one.
And then GG
Until long range is solved PoS is dead on arrival

mak [7:17 AM]
Hmmm. Now that i think about it, you are correct about the approach being susceptible 
to long range. I will see if i can figure something out that might solve that issue.

Moon (biz_network) [7:18 AM]
If you figure it out you'd be a millionaire sooooo
The problem is complicated enough that the entire PoS community can't solve it yet
after years of research
It's the only reason I remain pro-PoW

mak [7:19 AM]
The fact that nobody has been able to do it yet just means i need to try harder ;)
moazzamak commented 5 years ago

Thanks for posting this. I was going to do so if you didn't :) As shown in the discussion with moon the longest chain rule can't be followed because of concerns regarding long range attacks. I will see what I can do regarding that.

fix commented 5 years ago

Long range attack (LRA), similar to nothing at stake (NAS) issue is still an open issue on PoS like system. DPoS has the same issue.

There are 3 ways to tackle the issue: option 1 - making this attack more difficult option 2 - making this attack impossible theoretically option 3 - trade-off on decentralisation

DPoS is already a trade-off on decentralisation of pure PoS to max N delegates (in ark N=51), so in essence performing a long range attack should be done by

Solutions S1 - Casper is a take to tackle the option 2. S2 - Inclusion of PoW has been already tried on different chains to make it harder. This is the option 1. S3 - Other possibility is to 'force consensus' the id of a block every 1000k for instance (aka checkpoints). Force consensus means 'publish on bitcoin' like kmd, or 'upgrade the code'. This is option 3.

S1: I won't go down this path now as too controversial.

S2: This is the essence of AIP25. I have one remark: in DPoS, the blocks SHOULD happen within time slot and to prevent fork, it means it needs maximum 4 seconds of mining. (anyway quite less than the time slot). Also, only one delegates is mining, there is no concurrent mining (ie difficulty is the sole decision of the delegate). The issues it is easy to match such mining effort by a attacker that would anyway perform a long range attack with each block produced less than the time slot. While more difficult to perform (ie more expensive), the bottleneck is still being able to respect the time slot off the blockchain (ie having hacked one delegate key, i can only forge a block every 6 mins on average)

S3: essentially centralise blockchain every 1000k blocks (equivalent to hardfork). There are several ways to make it less 'centralised':

Note that right now with the status of ark development, pushing a block id every 1000k is not more centralised than what is ongoing now (with hardforks). We can start with this solution (easy to implement) while moving on the next implementation when we agree on some solution.

fix commented 5 years ago

One last comment: The other way is to decide differently what a 'winning chain' means. Let's say we let the possibility to LRA and don't prevent it. We have historical chain HC and Long Range Attack Chain LC and add the following rules:

Now LC is performing sybil attack to HC.

I am fine with several LCs because the only issue will be on exchanges. They will have to deal with which fork they will manage, like what happens with bitcoin hardfork. And this is fine AS SOON AS THEY GET NOTIFIED RIGHT WHEN A LC IS DETECTED to prevent double spend attacks. Note that LRA dedicated to hack exchange is slightly more complex, because the new LC needs to be able to account for all exchanges wallets (clients and hot/cold wallets) and replay transactions on them.

fix commented 5 years ago

OK my comments was based on previous discussion between @n4ru and @moazzamak added by @roks0n

However for the content of AIP25, it is a slightly different goal that is being tried to achieve. My comprehension:

As i stated before, DDoS is only a component to make the LRA faster (by slowing dow the HC). Sybil attack to force a new LC chain.

While being able to predict the future forgers, this is not a fundamental flaw for the NRA, ie fixing it does not prevent NRA.

moazzamak commented 5 years ago

I understood the long range attack argument as old delegates that are no longer forging having an incentive to collude and create a longer chain from an old point where they had the majority. This is an issue in every current model but since no (D)PoS model follows the longest chain rule it's not a threat. However since I intended AIP25 to make it so you could take advantage of the longest chain rule @n4ru correctly pointed out that it will be susceptible to long range attack.

it is possible to predict with some relative reliability who will forge in the future.

Just to clarify only the delegate that submitted the claim knows their secret number in AIP25. Everyone else sees random jibberish until the delegate has published their block so the next block's forger can't be predicted and therefore can't be DDoSed.

I think the 100k limit rule presented by @fix is a nice practical rule to follow and would allow chain to remain stable during normal times but in times of contention there still might be a possibility for delegates to try and force their will on others by altering recent history (take BSV's recent attempts for example). I would expect such a situation should never occur within the Ark Ecosystem but when planning we have to take into consideration every possibility.

fix commented 5 years ago

sorry my bullet points were about to explain what you want to solve ie you want to make sure that it is not possible to predict next forger.

fix commented 5 years ago

Another possibility is randomized the next forger at each block. ie taking the id of last block to tell which is the next forger (excluding the delegate itself). However it is more complex as it can be gamed by the forger itself

zillionn commented 5 years ago

Not sure if this is relevant, but can we somehow make the new peer/node/relay/forger or whatever, have a lower weight in any decisions? And after time it weight increases when sends/receives blocks or something... 😄

So we don't trust it that much if it's a new player and when it proofs itself, we start to trust.

moazzamak commented 5 years ago

@zillionn I don't think doing that would help preventing long range attacks. It might make it worse since older delegates who are no longer forging can then overpower the newly elected delegates even easier than before and hijack the chain.

n4ru commented 5 years ago

@fix

I'll circle back to your other points as I just woke up, but a LRA is incredibly easy specifically on chains like Ark and Lisk.

There's a reason myself and several others asked about nonces many times. You can replay any future txs to fund your wallet, including sending Ark back and forth to a wallet you own using an exchange on the real chain and then funding it via replay on the LC.

Even if nonces were implemented now, it's too late as old txs wouldn't be signed with them and would have to be included, which also means they could still be replayed.

I did the math. With just Axi's passphrase (who started forging day 2 and everyone has!) you can compromise the entire chain very easily with a LRA using TEC wallets that funded Bittrex, and then just sending money to your own wallet from Bittrex and not including the sends back to the exchange. Rinse and repeat until you can control all 51 delegates on day 2 a few rounds after 11693.

As you also mentioned, DPoS chains make long range attacks EASIER as time goes on, not harder like PoW! Ark has ~300k missed blocks I believe (could be wrong, but the number is significant), which is 300k extra blocks to forge free Ark to overtake the 51. But this isn't even necessary given the Bittrex replay strategy.

Given nothing but Axi's passphrase and a Bittrex account, a theoretical but fully functional Long Range Attack can overtake the chain as follows:

Voila. I am now the longest valid chain. This is a real attack that really works on Ark and can be executed by anybody, and it becomes slightly easier the more blocks are forged on the real chain. There is no fix for it that doesn't involve very hacky hard coding of checkpoints into the clients and nodes to force a specific chain. This should work on Lisk as well as any forks of either chain.

If nonces were implemented, the LRA would be infinitely harder since you would not be able to replay transactions out of order and would only be able to count on forging blocks with a single delegate to attempt to overtake the network (which would make this LRA only possible in a very distant future unless you get a delegate key from day 1 or find a gap where the math is in your favor to control all delegates). As it is now, you just need to replay transactions that favor you pushing yourself into a position to control every delegate (no need to wait "several billions of blocks").

My nitpicking isn't towards the AIP25 idea itself, only towards the claims made for it. It introduces a good way to prevent delegate collusion and protect delegates from being attacked by "late blocks" coming before their own, which can force delegates to miss blocks and can be done on purpose. It also prevents targeted (D)DoS attacks. It's a good step. I only tore apart the "PoW-like" aspect here because those are the claims @moazzamak made for it.

zillionn commented 5 years ago

@moazzamak Just an example: delegate weight = DB / (10200 / 51)

DB = forged blocks by the delegate in the last 10200 blocks

So, if you've forged only 5 blocks in the last 10200 blocks, your weight will be: 5 / (10200 / 51) = 0.025

moazzamak commented 5 years ago

Coming back to the long range attack. In my opinion this is not an issue in the consensus layer but in the meta consensus layer so we essentially need to change the incentive structure by changing acceptance probabilities. One way to do this would be to follow the rules @fix suggested earlier and not accept chains which have the common block further back then depth 100k etc but this a abrupt limit. I would try to spread that out into continuous function and say that the probability to accept a competing chain and switch from current one should be equal to p_switch = 1/A^(D+1) where D is the depth of the common block in current chain's length and A is some constant value greater than 1. In other words a node must be prepared to have their pledges+claims and their fees lost for the last D blocks if they bid on the wrong chain with the probability of having their wrong bid accepted by other nodes specified by p_switch. I think this should solve our problem probabilistically. image

Best thing about this approach is that we can hardcode as a part of consensus the value of A to get a desired probabilistic finality. Though we shouldn't keep this value too high because then forks happening due to uncled blocks can't be resolved at all. One final thing to note here is that we can take advantage of the lack of replay protection and execute the pledge+claim transactions in either of the chains which basically adds further incentive to bid on the right chain or avoid bidding at all until a fork has been resolved.

fix commented 5 years ago

This attack works on any PoS unfortunately. But in the end this attack does not change immutability of the HC if we implement what i suggested. This can be used to:

As for solutions, i still believe hardcoded block ids is intermediary solution waiting for a more real solution

as for 100k limit, the idea is that with 100k you can not stake for you more than 200k arks to perform attacks using forging rewards.

moazzamak commented 5 years ago

I believe we should be able to use it for following longest chain (PoW like strength) if we apply the probabilistic method that I specified in the last comment. Let me know what you think about it.

fix commented 5 years ago

well i could not grasp the idea to be honest, so i could not answer.

moazzamak commented 5 years ago

The idea is to extend your rules to make them more continuous instead of abrupt

As a node the winning chain is the one that is the biggest height and i a find common block within the last 100k If i detect a new winning chain with maximum common block id > 100k blocks, i tag it with [height of maximum common block id, hash256(nethash + maximum common blockid)] and disregard all nodes in this topology

You specified a single common block depth limit of 100k after which a longest chain would not be accepted. Instead I suggest that we reject based on common block depth probabilistically. And the probability to reject a topology is as a function of the depth specified as p_reject = 1-(1/A^(D+1)). So for a single node a fork at 0 depth will have a 50% chance of being accepted but forks at 100 depth will have a much much smaller chance of being accepted. This simulates the behavior we see in bitcoin with fork depths. I remember Andreas Antonoupoulos mentioning that roughly every day a 1 block fork is made and 2 block fork happens every week or so and that a 6 block fork should only happen once every 100 years etc.

moazzamak commented 5 years ago

44 Section added to discuss approaches that might be useful to address long range attacks. Last remaining solution is the sybil attack scenario using relay spam. I think it should be solvable as well and will spend some time figuring out how to do it though I'm open to ideas about it.

github-actions[bot] commented 3 years ago

Stale issue message