A World of Trust – eMunie Consensus Primer

[monsterer]

4 of these nodes suddenly loose communication from the other 11, but can communicate between themselves. These 4 nodes will likely get "stuck" immediately.  They are not able to achieve a majority regarding any pending committals as they are not able to receive the votes from the other 11 voters.

Even in the case where there are no committals pending, the split of 4 will be aware that something is amiss upon one of them presenting a new transaction, as the set of nodes those 4 expects to acknowledge the next transaction, 11 will not respond.

And what happens when some edge case means that the 4 are not aware of their previous connections to the other 11?

This kind of reactionary design is very fragile because it relies on state transitions. If you start from scratch with two groups, one of 5, one of 11 which operate independently (for whatever reason), forming separate valid consensuses but are supposed to be on the same network, what happens when they rejoin?

This IMO is a critical issue that proves block chains & POW are not truly Byzantine tolerant, because there isn't a majority agreement that can prevent changes to history.  Bitcoin's use of POW results in an asynchronous network, as there is no mechanism to vote and thus prevent historical changes, and it has been proven that asyncronous networks can not tolerate even 1 Byzantine failure.  

In Bitcoin's case the single Byzantine failure is when someone produces a Proof of Work that exceeds the one currently in place.  In essence by presenting it, they are disagreeing with the rest of the network about what the state should be, and thus it can be classed as a Byzantine failure.

In POW the votes are the blocks. The chain with the most votes becomes the canonical chain. The reason for this choice is that it is very robust, simple and doesn't rely on any state transition, reactionary design and is resistant to sybil attack.

It has been argued that POW is ,in fact, *the only* solution to the byzantine generals problem:

https://gist.github.com/oleganza/8cc921e48f396515c6d6

[1714772526]

1714772526

[1714772526]

1714772526

[1714772526]

1714772526

[1714772526]

1714772526

[1714772526]

1714772526

[TPTB_need_war]

Indeed it appears his system needs to be modeled as a complex state machine.

You can't just make a claim out-of-context that an "honest" majority of the trust reputation will decide the winner of a double-spend. You have to model the state machine holistically before you can make any claim.

Proof-of-work eliminates that requirement because each new iteration of a block solution is independent (trials, often simplistically modeled as a Poisson distribution) from the prior one (except to some small extent in selfish mining which is also easily modeled with a few equations). See the selfish-mining paper for the state machine and then imagine how complex the model for his design will be.

This is independence is what I mean when I say the entropy of PoW is open (unbounded), while it is closed for PoS.[1]

[1]	https://bitcointalk.org/index.php?topic=1159691.msg12242278#msg12242278 https://bitcointalk.org/index.php?topic=1159691.msg12227357#msg12227357

Imagine this highly technical discussion comparing PoW and PoS can't happen in the Bitcoin Technical & Discussion forum, because the overlord Gregory Maxwell moves it to the Altcoin Discussion thread.

[Come-from-Beyond]

It has been argued that POW is ,in fact, *the only* solution to the byzantine generals problem:

You can't prove that without iteration through all possible alternatives. Even unknown yet.

[Ix]

This kind of reactionary design is very fragile because it relies on state transitions. If you start from scratch with two groups, one of 5, one of 11 which operate independently (for whatever reason), forming separate valid consensuses but are supposed to be on the same network, what happens when they rejoin?

If you started with two groups, how could they rejoin?

It has been argued that POW is ,in fact, *the only* solution to the byzantine generals problem:

https://gist.github.com/oleganza/8cc921e48f396515c6d6

Generally by people with a lot to lose if it isn't.

[monsterer]

It has been argued that POW is ,in fact, *the only* solution to the byzantine generals problem:

You can't prove that without iteration through all possible alternatives. Even unknown yet.

You can prove that the average of all random numbers between 0 and 1 is exactly 0.5 without averaging every possible number. That is the definition of a 'proof'

[monsterer]

If you started with two groups, how could they rejoin?

Nodes crash and need to be restarted. Temporary loss of network routing could keep them separated from the main group of nodes until time X, when they rejoin.

[Come-from-Beyond]

You can prove that the average of all random numbers between 0 and 1 is exactly 0.5 without averaging every possible number. That is the definition of a 'proof'

I meant big asymmetry in efforts required to prove existence or absence of something.

[Come-from-Beyond]

Imagine this highly technical discussion comparing PoW and PoS can't happen in the Bitcoin Technical & Discussion forum, because the overlord Gregory Maxwell moves it to the Altcoin Discussion thread.

This forum is private property. Its owner and moderators have the right to do anything they wish. Is Gregory Maxwell bad because he moved your topic? I wouldn't judge without hearing his reasons.

[Fuserleer]

4 of these nodes suddenly loose communication from the other 11, but can communicate between themselves. These 4 nodes will likely get "stuck" immediately.  They are not able to achieve a majority regarding any pending committals as they are not able to receive the votes from the other 11 voters.

Even in the case where there are no committals pending, the split of 4 will be aware that something is amiss upon one of them presenting a new transaction, as the set of nodes those 4 expects to acknowledge the next transaction, 11 will not respond.

And what happens when some edge case means that the 4 are not aware of their previous connections to the other 11?

This kind of reactionary design is very fragile because it relies on state transitions. If you start from scratch with two groups, one of 5, one of 11 which operate independently (for whatever reason), forming separate valid consensuses but are supposed to be on the same network, what happens when they rejoin?

This IMO is a critical issue that proves block chains & POW are not truly Byzantine tolerant, because there isn't a majority agreement that can prevent changes to history.  Bitcoin's use of POW results in an asynchronous network, as there is no mechanism to vote and thus prevent historical changes, and it has been proven that asyncronous networks can not tolerate even 1 Byzantine failure.  

In Bitcoin's case the single Byzantine failure is when someone produces a Proof of Work that exceeds the one currently in place.  In essence by presenting it, they are disagreeing with the rest of the network about what the state should be, and thus it can be classed as a Byzantine failure.

In POW the votes are the blocks. The chain with the most votes becomes the canonical chain. The reason for this choice is that it is very robust, simple and doesn't rely on any state transition, reactionary design and is resistant to sybil attack.

It has been argued that POW is ,in fact, *the only* solution to the byzantine generals problem:

https://gist.github.com/oleganza/8cc921e48f396515c6d6

The 4 are always aware of the other 11, because if they werent how could they know what where the majority should be?

You are very mistaken about how Byzantine agreement consensus works and the requirements needed for a robust one.  Bitcoins blocks are not votes, if they were classed and acting as such, then a record would be kept by the network of all votes (orphans).  The network doesn't, so they aren't votes, it is a dictation instead.

The argument that POW is the only solution to the Byzantine problem is ridiculous as it doesn't even meet all the criteria.

Edit:  All distributed applications operate as a state machine, Bitcoin's ledger is a state machine also, as is Ripples ledger and everyone elses.   If it wasn't a state-machine, then new nodes couldn't download the ledger, replay all the states and end up at the same place as everyone else.

I'm beginning to feel like no matter what argument I present here, even arguments that have been proven by minds smarter than what are behind Bitcoin, they are going to be dismissed just for the sake of arguing.

[TPTB_need_war]

Bitcoin's ledger is a state machine also

A very simplified state machine of the longest chain. The block solutions are nearly independent events which can be approximated by the Poisson distribution.

One exception is the selfish mining attack where in the longest chain rule is subjected to selfish hiding of the dominate hash power. Yet even this state machine is reasonably simple, just a few simple equations.

Whereas the state of your system is numerous agents and states. It is not yet clear to me this model can be modeled with some simplifying assumptions. Perhaps you can work with your academic researchers to see if they can.

Yet my design maintains the simple state machine of proof-of-work, while removing virtually all the bandwidth scaling restrictions. You say you can't do 100,000 transactions per second microtransactions. I can easily.

[Fuserleer]

Bitcoin's ledger is a state machine also

A very simplified state machine of the longest chain. The block solutions are nearly independent events which can be approximated by the Poisson distribution.

One exception is the selfish mining attack where in the longest chain rule is subjected to selfish hiding of the dominate hash power. Yet even this state machine is reasonably simple, just a few simple equations.

Whereas the state of your system is numerous agents and states. It is not yet clear to me this model can be modeled with some simplifying assumptions. Perhaps you can work with your academic researchers to see if they can.

Yet my design maintains the simple state machine of proof-of-work, while removing virtually all the bandwidth scaling restrictions. You say you can't do 100,000 transactions per second microtransactions. I can easily.

All these grandiose claims of what you have, that seemingly defy proven limits of information theory, yet not an ounce of information to back it up.

If you have it, show it, if you don't want to show it, send me any binding legal document of your choice that protects you, I'll review it, and if you have what you claim, I'll back you up in any arena for the rest of my life.  You could even hash whatever document presents your algorithms and timestamp that in the block chain.

Until then, I would suggest a little restraint, because as you have said to me, until it is peer reviewed you don't have anything.  If it is proven to be the case that you don't have what you claim, even for legit reasons or oversights, then you are going to have a severe case of egg on face if you don't apply a little humility.

Also you are mis-quoting me, I said its not possible to do 100,000/s of micro transactions on a block chain, that statement may not apply to other architectures.

[bitsire]

Bitcoin's ledger is a state machine also

Whereas the state of your system is numerous agents and states. It is not yet clear to me this model can be modeled with some simplifying assumptions. Perhaps you can work with your academic researchers to see if they can.

Yet my design maintains the simple state machine of proof-of-work, while removing virtually all the bandwidth scaling restrictions. You say you can't do 100,000 transactions per second microtransactions. I can easily.

Translation:

Derp derp derp, this Fuserleer guy might be smart, but not as smart as me... derp derp derp, emunie sounds interesting, but my vaporware will solve all the problems with cryptos that those before me weren't smart enough to figure out... derp derp derp, don't pay attention to this Fuserleer guy and the almost ready to launch emunie, pay attention to me and my theoretical cryptocurrency which, while I can't reveal any details, will definitely be much better and faster than emunie in every regard... derp, derp, derp...

[r0ach]

While the original network regards the sudden non-response of these nodes as failures, it is below the maximum of (n/3)-1, and can continue operating.  The network split containing 4 nodes regards the sudden non-response of 11 nodes as a critical issue as there has been > than (n/3)-1 failures which is easily detectable.  That split network can then act accordingly, pausing operation and perhaps even informing users of the sudden critical issue until reconnection to the main network partition.

How does this function if you're releasing something as open source where people will be running their own custom clients?  Is it safe to say this relies on hard coded client level restrictions rather than protocol based restrictions?  Instead of relying on resources (51%) to attack the base protocol, you have a resourceless attack of people just modifying the client?  Am I missing something here?

If I do this in Bitcoin, I have to expend gigantic resources in order to make my decision or my decision doesn't exist, which by all metrics, I would consider a "vote".  Also, as you said, eMunie nodes are very cheap to run, you can create a huge number of Sybil nodes at the start of the network, then diverge your nodes from the real (but smaller) network and render it non-functional?

[patmast3r]

Please excuse me if this is ignorant but if there are no blocks how does one know when a tx is "confirmed" ?

How do I know there is not another tx around the corner that has an even highter consensus value that some of the trusted nodes just haven't seen yet ?

Is there a specific time that a tx needs to be on the ledger for so it can be considered confirmed ?
Is there a certain threshhold of consensus value that a tx needs before it is actually added to the ledger at which point every future tx will be disregarded ?

[monsterer]

The 4 are always aware of the other 11, because if they werent how could they know what where the majority should be?

And if they started isolated from the main group, for whatever reason?

There are so many ways this can happen, the protocol must be able to recover from this position, otherwise you'll end up like Stellar... frantically searching for a new consensus algorithm while they run one validating node, because they cannot handle forks.

You are very mistaken about how Byzantine agreement consensus works and the requirements needed for a robust one.  Bitcoins blocks are not votes, if they were classed and acting as such, then a record would be kept by the network of all votes (orphans).  The network doesn't, so they aren't votes, it is a dictation instead.

Blocks are votes (sybil proof votes at that) in a very real sense. New blocks added to a chain are a vote for that chain, plain and simple. Chains with the most votes win.

The argument that POW is the only solution to the Byzantine problem is ridiculous as it doesn't even meet all the criteria.

In fact, POW is a very robust solution to this problem, able to handle up to 50% byzantine failures, which is the highest I know of. In this thread you state that eMunie is capable of resolving up to (n/3)-1 failures, which is 33%.

Edit:  All distributed applications operate as a state machine, Bitcoin's ledger is a state machine also, as is Ripples ledger and everyone elses.   If it wasn't a state-machine, then new nodes couldn't download the ledger, replay all the states and end up at the same place as everyone else.

I'm beginning to feel like no matter what argument I present here, even arguments that have been proven by minds smarter than what are behind Bitcoin, they are going to be dismissed just for the sake of arguing.

Quite the contrary - the only reason I'm able to present these counter arguments is that I've been down this theoretical ripple a-like road, in a search for my own fast, energy efficient consensus mechanism. I hope to offer you some food for thought before you go to all that effort of implementation.

You can fix a lot of these problems; here I what I suggest:

* Throw away the trust model completely
* Make votes for transactions cost something (either POW, or burn)
* Handle forks

[Fuserleer]

While the original network regards the sudden non-response of these nodes as failures, it is below the maximum of (n/3)-1, and can continue operating.  The network split containing 4 nodes regards the sudden non-response of 11 nodes as a critical issue as there has been > than (n/3)-1 failures which is easily detectable.  That split network can then act accordingly, pausing operation and perhaps even informing users of the sudden critical issue until reconnection to the main network partition.

How does this function if you're releasing something as open source where people will be running their own custom clients?  Is it safe to say this relies on hard coded client level restrictions rather than protocol based restrictions?  Instead of relying on resources (51%) to attack the base protocol, you have a resourceless attack of people just modifying the client?  Am I missing something here?

If I do this in Bitcoin, I have to expend gigantic resources in order to make my decision or my decision doesn't exist, which by all metrics, I would consider a "vote".  Also, as you said, eMunie nodes are very cheap to run, you can create a huge number of Sybil nodes at the start of the network, then diverge your nodes from the real (but smaller) network and render it non-functional?

(n/3)-1 is neither a client nor protocol restriction, it is an information theory restriction.  

In all true Byzantine agreement solutions there has to exist a either a set of trusted parties that can come to a majority, or a leader ( a set of 1) has to be elected to decide for everyone else based on their inputs ( it should be apparent in both cases that (n/3)-1 applies to both as does f3+1).  In the case of non-leader solutions, that set can be a defined list that never changes, a set that is built from neighboring nodes, or a set that is deterministic from some globally agreed upon inputs.

Changes to the client, or protocol would do nothing other than cause those modified to fail, either immediately or some time in the future, as they would not be operating in line with everyone else.

Regarding the Sybil nodes you are forgetting about trust decay, and the need to replenish it to continue holding whatever position you currently do.  Nodes with high trust at day-0 will not have high trust at day-90 unless they maintain it, due to decay and possible network growth.  As I've said many times in the this thread, to do that has a cost, both in effort and financial terms.  But lets get into detail about what is required in a natural environment to build/hold trust in and the potential "costs".

For a Sybil attack to be able to gain enough trust for an adversary to be in a position of influence, no matter how many nodes you have, the collective network penetration of these nodes should be 1 to be the most efficient.

Network penetration of value 1 is defined as: all attackers nodes are connected to all non-SN transaction producing nodes (TXPN) at all times and that the attacker has an equal presence at all TXPNs as that TXPN has honest SN connections.  For example if all TXPNs have 3 honest SN connections, you need to have 3 connections there also, all coming from different nodes you own.

A penetration of 1 would ensure that all of your nodes have a 50% chance of receiving an endorsement, less than 1 means that some of your nodes are not connected to TXPNs, so the probability of that TXPN endorsing an honest SN instead of yours if/when it creates a transaction is higher, thus making it harder for you to build trust.

Generally the maximum penetration you could achieve would be around 0.8 in a natural environment, maybe 0.85 with a lot of effort.

Achieving a penetration anywhere near 1 in a natural environment will be very hard:

• logistics of ensuring the required amount of all your SNs are connected all TXPNs
• you wont know how many honest SNs any TXPN has, as nodes can change the default # accepted connections
• TXPNs coming online, going offline, rotating connections and all manner of other activities you can't preempt

If your network penetration is < 1, then you need more connections/nodes to ensure you are receiving a as many of the endorsements as possible to gain trust.  More nodes = more effort/cost.

Because you need connections to all present TXPNs in the network, the quantity of TXPNs defines how many nodes you will need depending on what each node can support.  In our tests, an SN with an i7 Intel processor can support 100-150 connections concurrently, perform work requests presented by connected TXPNs as its advertising a service, process ALL POW challenges from connected TXPNs correctly, and keep sync with the network.  A node of that performance with 100-150 connections is pretty much flat out and burning 100-150w of electricity, sounds quite costly, just like mining!

In a natural Sybil attack its worse than that, as attackers need multiple connections to all TXPNs to acquire a good portion of any trust being endorsed from these TXPNs, and these additional connections need to support the associated work that comes with them, as TXPNs do not, of course, know that you are the same entity.  By default 8 connections are accepted per TXPN, both inbound and outbound, so you need to hold at least 4 of those connections on all TXPNs at all times to get close to a penetration of 1.  Your nodes are doing at least 4x more work in the network other SNs, and so cost 4x as much to operate.  Any earnings from doing the work requested to ensure a chance of endorsement will be less than it costs you to operate them.

Finally he will have to foot the cost of operating those nodes in that manner for almost 90 days until he reaches peak trust, as before 90 days, he may not have enough influence to direct any conflicts in the network towards his preferred outcome.

Manipulated Sybil attacks, are much easier!  An attacker can guarantee a network penetration of very close to 1, because the attacker is also in control of the TXPNs making the transactions and can easily ensure that his TXPNs are always connected to one of his SNs.  Manipulated Sybil attacks are costly in fees though, but can build trust much more rapidly.

[Fuserleer]

And if they started isolated from the main group, for whatever reason?

There are so many ways this can happen, the protocol must be able to recover from this position, otherwise you'll end up like Stellar... frantically searching for a new consensus algorithm while they run one validating node, because they cannot handle forks.

If they start not connected to the main group they can not make transactions for a 2 simple reasons, there are no transactions for them to process because no one has any assets to send, and if anyone does have any assets to send, the initial set of allowed counter-signers isn't present because they are on the main group.

Blocks are votes (sybil proof votes at that) in a very real sense. New blocks added to a chain are a vote for that chain, plain and simple. Chains with the most votes win.

A block is 1 persons vote, the miner who made it.  There can not be a majority in a set of 1, and I can come and change that "vote" at any time providing I produce a block(s) with a greater amount of work done.

In fact, POW is a very robust solution to this problem, able to handle up to 50% byzantine failures, which is the highest I know of. In this thread you state that eMunie is capable of resolving up to (n/3)-1 failures, which is 33%.

Are you sure?  Who is presenting all these Byzantine failures that total 50%?  It is proven by people many times smarter than you, I and everyone else here that the limit of true Byzantine tolerance in any trustless information system is 33%.  Are you saying they are wrong?  That Satoshi has achieved the equivalent of faster than light travel in information theory?

Bitcoin gives the illusion that it is more tolerant than 33%, but it isn't, because its impossible as it is an asynchronous, anonymous system.

Quite the contrary - the only reason I'm able to present these counter arguments is that I've been down this theoretical ripple a-like road, in a search for my own fast, energy efficient consensus mechanism. I hope to offer you some food for thought before you go to all that effort of implementation.

You can fix a lot of these problems; here I what I suggest:

* Throw away the trust model completely
* Make votes for transactions cost something (either POW, or burn)
* Handle forks

With all due respect, I'm not going to throw away 2 years of work on the say so of someone I've never even spoken to before 3 days ago.  This isn't theoretical work, as we've been actively testing this model for failures for 9 months or more now.

[Fuserleer]

Just to clarify, Byzantine solutions can achieve 50% tolerance (2f+1) in certain environments, but those are generally trusted environments with many restrictions in place.

Distributed P2P network are not a trusted environment, so they can not achieve 50% tolerance.

[monsterer]

If they start not connected to the main group they can not make transactions for a 2 simple reasons, there are no transactions for them to process because no one has any assets to send, and if anyone does have any assets to send, the initial set of allowed counter-signers isn't present because they are on the main group.

How can the smaller group know about the main group until it rejoins it?

I maintain that unless you have a fixed set of ledger producing nodes, or a deterministic selection policy (which has its own set of problems), you must be able to deal with forks, because they will be inevitable.

A block is 1 persons vote, the miner who made it.  There can not be a majority in a set of 1, and I can come and change that "vote" at any time providing I produce a block(s) with a greater amount of work done.

1 block represents 25 BTC of hashing power, not one person. In addition, subsequent blocks placed on top of that block are *additional votes* for that chain.

Are you sure?  Who is presenting all these Byzantine failures that total 50%?  It is proven by people many times smarter than you, I and everyone else here that the limit of true Byzantine tolerance in any trustless information system is 33%.  Are you saying they are wrong?  That Satoshi has achieved the equivalent of faster than light travel in information theory?

Byzantine failures are basically misinformation, through whatever means. The truth in POW is the longest chain of work, and since a majority is >50%, POW can withstand 50% byzantine failures. That is the true genius of satoshi.

With all due respect, I'm not going to throw away 2 years of work on the say so of someone I've never even spoken to before 3 days ago.  This isn't theoretical work, as we've been actively testing this model for failures for 9 months or more now.

That is your prerogative, of course. I know it is very hard to look at your own work objectively, but it is also essential to do so, no matter the cost.

[r0ach]

Slightly unrelated issue, and I'm not exactly a pro-IPO guy in the first place either, but how exactly is the eMunie IPO going to avoid the Satoshi stash issue I outlined here where anyone who can smash the order books down to 0 is a "trusted 3rd party" by default?

https://bitcointalk.org/index.php?topic=1162416.0

IPO/ICO would have to be limited to something like 1% per person max, and even that's not verifiable.  Since you're not anonymous, people's acceptance might be a bit higher, but if you had something like 10-20%+ equity, you can short your own coin, smash the order books to nothing, and ride off into the sunset.

I'm honestly surprised we haven't seen this happen in alt coins already.  Maybe it has but just wasn't documented heh.