There is NO 51% Attack in Steem. Is there? Help! Dan! :D

in #steemtron5 years ago (edited)

I don´t care about FUD and I don´t think that our sunny boy will "take over the chain". But I think it is a good time to educate about what dPOS is.

There is no 51% Attack in a dPOS Consensus. Not the fault of the witnesses that most of them don´t know this, there is simply no good documentation in the whitepaper.

dPOS is a synchronous classical consensus or at least a hybrid based on such classical consensus. Classical byzantine fault tolerant (BFT) consensus systems are build into rockets and nuclear power plants and airplanes for decades.

This is how it works in classical consensus

A small and fixed number of nodes/computers is distributed over the airplane or in our case over the world. The set of nodes is small because consensus requires All-to-All communication. 100 nodes --> 100 x 100 messages = 10,000. So more than 100 Witnesses is a baaaad idea because the message complexity increases exponentially.

  • 21 x 21 (all to all in Eos and Steem) = 441 Messages
  • 27 x 27 (Super-representatives in Tron) = allready 729 Messages
  • 100 x 100 (in Bitshares) = 10000 Messages!
  • 210 x 210 = 44100 ... forget it

This is how it works in dPOS

  • in Steems dPOS quadratic message complexity seems not to be the reason for the bottleneck in number of witnesses see discussion with @raycoms in the comment section. It must have something to do with the round-robin algorithm. So Block-time probably comes from Network Delay/Broadcasting Method. I´m not aware of a distributed Clock or FLP-Problem in dPOS ‍♂️ so I would conclude that dPOS is in fact a synchronous or permissioned consortium chain (but much more flexible) and somehow hybridized.


[more Blockproducer means longer round]

This is how it does not work:

Majority consensus in >>Bitcoin<< means: the right chain is the longest chain where >>cumulative<< the most hash-power was applied to (heaviest chain), this is where >50% of the hash-power agrees on. Bitcoin has no concept of nodes, there is just hash-power.

This system has nothing to do with a classical byzantine fault resistant consensus system or hybrids like dPOS!


in Bitcoin the adding of blocks is not like a giant spinning wheel with fixed cabins (witnesses), but more like spinning the bottle. The mining-pool which finds the nonce (a small number - a digital needle in the hay stack) can add the block. The difference is that here everyone can join at anytime. In "Larimer"-Consensus everyone has the same chance to add a block, while in Bitcoin everyone has a chance proportional to the stake (which is applied hashpower).

A majority is not 51% (why percentages anyways? :D)

A majority in dPOS is 2/3 of the nodes respectively the stake. So, in order to tolerate n number of faulty nodes you need 2n + 1 honest nodes! (*for further details scroll down)

“You require a ⅔ majority to have an honest system. Originally BitShares started with 100. There’s not enough oversight of who those 100 people are because there’s not enough bandwidth of voters’ attention to decide. Bringing it down to 21 reduces the cost of the system. The network has to pay each person that runs a full node.” — Daniel Larimer

The Last Irreversible Block (LIB) as Dan Larimer calls it, is the block which has >>2/3<< (~66%) of the nodes behind it. No honest node will move to a fork which is not build on the LIB.

In classical consensus we dont use percentages. I mean your father is not 50% of your parents right? Bitcoin or more correct Nakamoto-Consensus is Node agnostic, it does not care if the Hash-power comes from 200 nodes or from 20000 nodes.

dPOS the flexible Consensus

In computer scientific terms the correctness of the consensus algorithm is made of two immune properties: safety + liveness. One of them guaranties that the chain makes progress and does not halt ;)

dPOS has safety and liveness properties but technically in the case of a byzantine take-over the chain does not halt, it still runs or is in a "pending" state and waits that the stake holders somehow resolve the problem by re-electing.


[yes Vitalik you are right the problem is that not everyone is using his/her votes, this can be changed since the ecosystem of Steem is build around social interaction. We are connected!]

Conclusion

IS this worse or better? I mean "33%" sounds worse... Neither! It is more flexible.
This is why dPOS will never be used for storing Trillions of Dollars but it is perfect for DAOs and to have fun. Vitalik is realistically destroying dPOS as something on the level of Bitcoin. Of course he is right, but for anything sub-decentralized gold or sub-decentralized law it is fine or perfect for a community which wants to improve!

Here is my point. Most witnesses know very little about the consensus in Steem. They know how Steem works technically, but they don´t know the computer-scientific/mathematical laws governing dPOS. I see them doing their home-work. In the end the big guys like Nakamoto, Larimer, Buterin and Zamfir, Gürer, Team Rocket, Ignotus Peverell Poelstra, ... they are about game mechanics and not about having a nice front end or nicely separated wallet.

probably sooner or later we will need a real technical peer-reviewed paper. Investors need such Information. Yeah ok, sun ...I mean some don´t care, but huge venture funds do.

where the 1/3 treshold comes from

I could list you the decades old literature on BFT-Consensus but you would not read them anyways (because you think the math behind consensus is difficult af). Lets call the honest nodes h and the dishonest nodes d. Now the treshold t is simply t > (h/2) + d

imagine there is a consensus fork and the honest nodes are evenly distributed on both sides: one side has h/2 and the other side has h/2 + d. When honest nodes are 60% and dishonest nodes are 40% your are fucked. Lets say we have 100 in total and 60 are honest (hey majority...fuck majority!) now 30 are on the right side of the consensus and 30+40=70 are dominating. For the single node there is no reference to know what it is right, it just has what the other node say.

h >= t > (h/2) + d
h > (h/2) + d
(h/2) > d
d < (h/2)

So the honest nodes must be more than half the honest nodes + dishonest nodes together. Now go brave witnesses protect our chain with informed decisions, don´t fall for FUD.

Literature:

GABRIEL BRACHA 1987 Asynchronous Byzantine Agreement Protocols
LARIMER 2017 The Problem with Byzantine Generals
LARIMER 2017 DPOS Loss of Consensus due to conflicting Last Irreversible Block
BUTERIN 2017 Engineering Security Through Coordination Problems
INTERCHAIN FOUNDATION 2017 Consensus Compare: Tendermint BFT vs. EOS dPoS

A general introduction to distributed Consensus Let’s Take a Crack at Understanding Distributed Consensus

Sort:  

hab zwar nur die hälfte verstanden, aber das war auch schon einen resteem wert :D

danke ich versteh grad auch nur die Hälfte :D Steems dPOS scheint noch etwas eigenartiger als ich dachte

Hab nicht mal die Hälfte verstanden, aber wie es aussieht, kann also Sun mit seinen 20% aller Steem nicht viel anrichten, oder? Zumindest was die Richtung der Chain betrifft, den Aktienkurs könnte er auch wieder nach unten schicken.

Weil nicht 100% des stakes fuer Witnesses voten, kann er mit 20% Stake, praktisch 100% der witnesses auswaehlen und dann machen was er will.

Oh!
Aber lassen sich die so einfach kaufen?

Kann ja 10 accounts aufmachen und sich selber waehlen. Das ist ja kein Problem.

Ganz davon abgesehen finde ich das ein unwahrscheinliches Szenario, bei Tron hat er ueber 50% und macht das nicht.

wie raycoms sagte gehts ja leider um den Stake der wirklich wählen geht (eines der Nachteile von demokratischen Systemen), theoretisch könnte er aber nicht viel erreichen wenn dPOS seine Stärke ausspielt und die Nutzer gemeinsam koordiniert Witnesses wählen.

Denke auch nicht dass er es macht da er es bei Tron nicht macht und vorallem kein Interesse haben dürfte das System hier nach den Regeln zu dominieren. Und wenn ich nicht ganz falsch liege können beide Nutzer Gemeinschaften über Steemit.com vereint werden so dass der Condenser beide Ketten bedient.

besonders weil dann würde es doch einen fork kommen oder nicht? Dann würde er einen grßteil seiner investierten kohle verlieren.

Der sollte einfach mal ne press Release machen ( mit vorab Beratung was steem ist)

Ich habe noch nicht ganz verstanden ob sich zwei Forks parallel entwickeln können. Soweit ich es verstanden habe würde die Kette mit weniger Blockproduzenten einfach verkümmern. Also müssten wir "manuell" Forken und einfach ein neues System aufsetzen. Und dann wäre sein Verlust so groß wie die Anzahl der Leute die auf den neuen Steem migrieren. Bei einem 50:50 Splitt verlieren beide Seiten zunächst, da beide nur noch ein Viertel des gesammten Netzwerkes wert sind. Klar weil beide Inhalt und somit Attraktivität verlieren. Aber dann gewinnt langsam die Seite welche durch den Fork mehr Freiheit erlangt hat. So beschreibt es zumindest Vitalik.

naja ich denke das sun wenige steem nutzer abgreifen könnte, da sein Image gerade wie der Steemteufel ist.

Ich denke er hat am meisten zu verlieren.

Außer die ganzen coolen Dapps würden mit gehen. Aber das denke ich ist am unwahrscheinlichsten.

Ja stimmt, er hat ja nicht mal Follower auf YouTube 🤷‍♂️ vermutlich gibt es kaum echte Nutzer.

alles Glückspiel, wo es auch bots sein können. Während der Steem Steemit, Steemmonsters und Co hat die überwiegend echte Nutzer

schwer zu sagen. Aber ich vermute es auch.

Only thing missing is the explanation how it is possible that a fork happens and the correct nodes are split between both of them.

However, I did not know that Graphene blockchains use a Pos/PBFT hybrid. Are you sure about that? Do they gather two quorums? Is there a view change algorithm?

Additionally, there are already protocols that scale traditional consensus linearly (HotStuff, Byzcoin, etc) that could scale easily too much bigger numbers of witnesses.

However, I did not know that Graphene blockchains use a Pos/PBFT hybrid. Are you sure about that? Do they gather two quorums? Is there a view change algorithm?

right, no not POS/PBFT thats the point! The POS in dPOS is not the same as POS in Proof-of-Stake or Proof-of-Work (which is POS), which both are no consensus algorithms but ways to ship around the FLP-Impossibility theorem.

Besides the function of leader election oracle and Sybil-resistance mechanism and incentive-estimator both are clocks in the first place. Instead of time Nakamoto-Consensus uses entropy of the memory-less Hashfunktion. This is why we have synchronicity assumption in an open hence asynchronous network. One does not simply assume synchronicity. Same goes for POS

the POS in dPOS is just Sybil-resistance mechanism. Not more not less. Not related to "real" POS. The hybridization I refer to is that Steem can additionaly incorporate a Proof-of-Work sheme (which it had until 2017).

Additionally, there are already protocols that scale traditional consensus linearly (HotStuff, Byzcoin, etc) that could scale easily too much bigger numbers of witnesses.

yeah or like Tendermint BFT but they are asynchronous? As far as I have understood the point with "Larimer-Consensus" is that it sacrifices open consesus setup for the property of "pending"-state in the case that the correctness of the algorithm gets violated.

and that it has no 100% finality but an probabilistic escape hedge like the lasvegas algorithms.

Yes I know what PoS here is used for compared to the "real PoS".
I still didn't know that Steem/EOS/Bitshare use a 2phase protocol that collects two quorums from the majority (2f+1) of witnesses (I will have to read up on this).
In the end that would make it a permissioned blockchain.

HotStuff is like PBFT, it has partial synchrony and is still linear (an adaptation of it will be used in Libra afaik).

In this paper they assume DPoS got 51% as well:
https://ieeexplore.ieee.org/abstract/document/8400278/

It is a permissioned Blockchain this is Vitaliks critique

Dan's EOS achieves its high scalability by relying on a small number of what are essentially master nodes of a consortium chain, removing Merkle proofs and any other protections that would allow regular users to audit any part of the system's execution unless they want to personally run a full node themselves. See http://vitalik.ca/general/2017/05/08/coordination_problems.html for why I think this is undesirable.

Du meinst weil die Witnesses im Rundverfahren arbeiten und an den LIB ansetzen ist es kein 2Phasen Quorum? Warum skaliert es dann nicht in der Anzahl der Validatoren. Werde es auch nochmal durchlesen. Super Einwand

@anonymint

Hast du mir den Link zum whitepaper wo das beschrieben ist?

das ist nur ein reddit Eintrag von Vitalik Buterin welchen er auf seinem Blog ausführt.

Hier spricht Larimer selber über 2f + 1

We then introduced a new concept known as the Last Irreversible Block (LIB). This is a block which has been confirmed by ⅔ or more of the elected block producers. No node will automatically switch to a fork that isn’t built on top of the LIB.

Wo soll der Schwellenwert herkommen wenn es kein klasisches Quorum ist. Ich bin überfragt. Hoffentlich findest du was raus

Confirmed ist wahrscheinlich wenn ein witness ueber dem block nen anderen block produced hat. Dass ein block von weniger confirmed sein kann heisst das es kein quorum haben kann.

Ja stimmt das wäre dann ein solcher Minority-Fork. Aber hier produziert die Minderheit einen Block nur alle 9 Sekunden und verliert das Rennen um die längste Kette.

sry ich habe ganz vergessen es gibt ja ein missing Whitepaper von Larimer zu dPOS:

To help explain this algorithm I want to assume 3 block producers, A, B, and C. Because consensus requires 2⁄3 + 1 to resolve all cases, this simplified model will assume that producer C is deemed the tie breaker. In the real world there would be 21 or more block producers. Like proof of work, the general rule is that longest chain wins. Any time an honest peer sees a valid strictly longer chain it will switch from its current fork to the longer one.

🤯
das meint Gün Sirer mit hybrid es nutzt longest chain rule und ist kein Quorum im klassischen Sinne aber ein permissioned consortium welches im Round robin verfahren Blöcke produziert, dann ergibt sich doch 2f+1

Unfortunately this analyis neglects how the witnesses are elected. All it takes to control all 20 consensus witnesses is 51% of the stake voting for witnesses.

See this discussion for specific details.

Sorry I missed this post earlier.

Thanks!

page don´t work. If this is what people mean when they say "51% attack", than this is not the same as a 51%-attack in the scientific/mathematical sense.

Steem is a dPOS + Byzantine Fault Tolerance Protocol (dPOS-BFT). Where the security assumption is: that there are no more than [(n-1)/3] malicious nodes, hence for f faulty nodes it needs at least a 3f + 1 honest majority (which is 2/3 + 1 nodes). This is when you want transaction finality/irreversibly. Those systems are used in rockets and nuclear power plants for decades. What Nakamoto did was "OK I cant give you finality, but I can give you 99.99% irreversibly after n rounds, if you are OK with this 0.001% probability of chain-reversibility, than here is a system with only2f + 1 honest majority assumption (>1/2 aka. "51%")". Which was a revolution in decentralized consensus.

Well, if 51% of the voting stake can elect 20 of the nodes then this is simply bad design, while the 1/3 threshold for consensus systems with finality and 1/2 threshold for systems like Bitcoin with "only" a 99.999% finality (las-vegas algorithms) is a physical limit.

in Steem there is the longest chain rule. Which means the longest chain is the valid chain. Nodes add blocks in a ***round-robin scheduling ***scheme. One block every 3 seconds. When you posses up to 1/3 of the nodes you can create a minority fork. The malicious branch will never be the valid chain because 1/3 of a 20 witness round-robin creates block on the malicious chain only every 9 seconds, while the honest 2/3 creates blocks still every 6 seconds. When you posses one single node more than 1/3 it becomes undecidable which fork is the valid chain because you can posses positions in the round-robin where you can add blocks every 6 seconds - a minority is undecidable from a majority. This is why you don´t need all 20/21. When you say 51% of the voting stake can elect all nodes this is horribly bad for a system which can be majority forked with 1/3 + 1 .

Apparently I dunno how to link properly, so here's a screenshot:

51attack.png

And I am certain that a bare majority of stake will elect all top 30 witnesses, given each account has 30 witness votes.

I advocate for 100% depletion of witness votes with 0% recharge until the vote is rescinded, as one way to prevent this from happening. It isn't a complete solution when one user has nearly 1/3 of the stake extant, but it does prevent a supermajority from being created by that one user competent to force hard forks.

It also ends the multiplication of weight advantage substantial stakeholders have over lesser plebs. They already have an advantage. They don't need it multiplied 30x.

Edit: despite my challenges in math, I was able to follow your clear explanation of the math regarding how witnesses submitting blocks established a 'right' chain.

Thanks!

oye..
Very Long time....
it is about science ...

danke für die starke Unterstützung! Ich hoffe dass es auch bei den richtigen ankommt dass dPOS wesentlich flexibler unter Attacken ist.

wird ja gerade an allen möglichen Fronten gebastelt wegen der Sun Übernahme.. und evtl steemit stake Missbrauch oder Wegfall der Node etc. pp.

War gerade in ner Konvo und in der ging es darum alle Bilder am besten über ipfs abzusichern, da steemitimages auch wegfallen könnte.. und um scripts um seine Blogs offline zu backupen..^^

Und da hab ich mich gefragt.. könnte man nicht irgendwie steem und scuttlebutt verbinden?
Quasi Scuttlebutt als offline p2p backup seines Steem Blogs nutzen?

greets ;)

klar kann man das. scuttlebut ist aber keine cloud, das ist dann schon noch auf deinem pc sofern die witnesses es nicht auch so machen. Die Blochain ist ja eher decentrale server cloud. Du lädst patchwork runter und dann kannst du relativ einfach deinen Blogg einrichten, und dann kannst du über das Gossip Protokoll mit jedem anderen verbinden der es auch so macht und du siehst dann informationen von den Leuten in meiner Nähe, ich sehe die Blogs der Leute in der deiner "Nähe" und es ensteht ein social Network.

Man könnte sicher auch das ganze so einrichten dass die Artikel nicht auf der Blockchain erscheinen sondern nur die Tips, die Tips im Prinzip auf leere Artikel, die dann in secure scuttle butt gelesen werden. Man müsste es ja nur verlinken.

Utopia hat eingebaute Wallet aber das ist dann natürlich kein Proof of Brain aber sicher ließe sich auch hier eine Verbindung herstellen.

Ich glaube wenn mehr Leute Interesse an anarchistischeren Lösungen hätten, welche maximale autonomie ermöglichen, dann wäre das längst möglich.

Hi @luegenbaron

what a close fight

I've noticed that that we're both playing Holybread. What's your impression so far?

I play as @project.hope and so far I found this game quite entertaining. Perhaps it will get boring soon, but right now it's still loads of fun :)

Yours,
Piotr

yea, it's fun but I sadly gotta stop in a few days..
cuz I'm going to stationary pain therapy for a few weeks and have no time..

Hi again @luegenbaron

Sorry for changing the topic ....

Can I ask you for little favour? I joined contest called "Community of the week" with project I manage and I would be grateful if you could RESTEEM it and help me get some exposure and drop some encouraging comment :)

Link to my post: on steemit or on steempeak

Thanks :)
Yours, Piotr