BitShares X Status Update

[bytemaster]

I would aim to get about 100 nodes on the UNL list hosted in countries around the world.

This sounds very centralized to me.
Even international banks would have more branches (I know thats comparing apples and oranges) but 100 nodes sounds scary little (even though it would be more decentralized than bitcoin). Why would there only be 100, are their barriers to becoming a node.

Already with my limited technical knowledge I feel I will not be able to support the network by becoming a node. Am I missing something there?

The number of nodes can grow to any number that can support the bandwidth and latency requirements.
What is your concern regarding centralization with 100 nodes?  What attack do you see being possible? 

[MrJeans]

I would aim to get about 100 nodes on the UNL list hosted in countries around the world.

This sounds very centralized to me.
Even international banks would have more branches (I know thats comparing apples and oranges) but 100 nodes sounds scary little (even though it would be more decentralized than bitcoin). Why would there only be 100, are their barriers to becoming a node.

Already with my limited technical knowledge I feel I will not be able to support the network by becoming a node. Am I missing something there?

[bytemaster]

Today I made more progress on the Unity algorithm and have nodes talking to each other and am in the process of debugging the algorithm now so hopefully some time tomorrow I will have the bugs worked out.

[theoretical]

Why is this necessary at all?  What's wrong with just having every node do its own proof-of-stake on the set of transactions it knows about?

All nodes must AGREE on the next block to make sure the block chain doesn't diverge.  Bitcoin uses the lowest hash to decide what to agree on.

What's wrong with arbitrating between two different forks by accepting the one with the "better" proof-of-stake (compare hash divided by target for all competing forks)?

As a result bitcoin is centralized one block at a time.

I see what you're trying to say, but only because I think (earlier in this thread, or maybe somewhere else) you said that a single miner can "dictate" a block.  This is true, but it's a strength, not a weakness.  If you have some transaction T that a censor wants the network to permanently reject [1] [2] , with UNL it suffices for the censor to control some fraction of the UNL (maybe a majority, maybe a supermajority, maybe less -- need a simulation or detailed mathematical analysis to say for sure).  With PoS, we can assume 50% of the PoS-power will accept T [3], so the probability that T is not included in any of the next n blocks is at most (1/2)^n, which of course rapidly goes to zero.  Why allow a transaction censorship attack to succeed by compromising the UNL, when we can force them to meet the much higher bar of a 51% attack?

Bitcoin is also centralized by 10 mining pools which approve 90% of the blocks and just 2 or 3 are required for 51% or more of the blocks. 

I thought that PoS is supposed to be resistant to this phenomenon, because it's much harder to accumulate a significant fraction of a cryptocoin in circulation than it is to pool mining hardware.

[1] For example, the censor is a democratic government who believes, through due process of law, including good evidence obtained by Constitutionally approved methods and presented to an impartial judge / grand jury, that this transaction should be suppressed because it will be used for some despicable criminal activity.

[2] For example, the censor is an oppressive government whose intelligence service wants to invade privacy on a global scale by data-mining every financial transaction performed by every person in the world, and believes that this transaction should be suppressed because it does not contain sufficiently detailed information for its data mining system to confidently identify the sender, recipient, and nature of the transaction.  NB, technology cannot distinguish this case from [1].

[3] If 51% of nodes reject the transaction the censor wants to be rejected, then the censor has successfully carried out a 51% attack.  Because a 51% attack on PoS system implies that 51% of the money agrees with the censor, I would say this situation is better described as "the network voluntarily complied with the censor's desired policy" than "the censor launched a successful attack".

[theoretical]

The UNL list is a set of keys, not IPs.

A hard fork is the market solution to a misbehaving UNL set.  Bitcoin would have to perform a hardfork if the government ever got enough control over miners to enforce tainted coins.  The difference is that any bitcoin fork would also have to adopt a new POW that the government does not control and thus mean a massive coding change to something along the lines of a UNL.

This is the most informative thing I've heard yet.  I was thinking of the UNL along the lines of "a hardcoded list of network addresses which facilitates bootstrapping peer connections for a distributed peer-to-peer network service."  Instead, it seems it's more like "a set of authoritative signing keys which valid blocks will require."

Your peers cannot find a block

I'd like to elaborate to make sure I understand.  What you're really trying to say is that the validation check for a block involves checking that the block is signed by the hardcoded UNL signing keys, and it is impossible [1] for a node not in possession of a UNL private key to reproduce such a signature.  The code UNL nodes use to put together a block will be published, but the private keys will not.  So, just like anyone can put together a Bitcoin block that's lacking enough leading zero bits in the hash and thus will fail to validate, anyone can put together a Byteshares block that's lacking the UNL signature and thus will fail to validate.

[1] Impossible for an attacker who can't break RSA or ECDSA or whatever signature algorithm you use.

[bytemaster]

- How do nodes outside the UNL know what has been approved by the UNL?  Do UNL nodes have hardcoded keys as well as hardcoded network addresses?  Or is a connection to a UNL node necessary for a client to function?

The UNL list is a set of keys, not IPs.

- Say I'm a node outside the UNL.  One of my peers feeds me a block that has a parent I've accepted and passes proof-of-stake signature, transaction validation, etc., but contains some transaction the UNL has never heard of.  How do I establish that the UNL has never heard of it?  What do I do with the block -- accept it, discard it, hold it for a while and see if the UNL eventually decides to like the transactions it contains, or something else?

Your peers cannot find a block, and all peers check that every block is signed by several of the UNL nodes as UNL nodes are the only ones that can generate a block and they all generate the same block.

- It seems like you might need a condition along the lines of "Most of the regular nodes (outside UNL) have to have nearly identical UNL lists" in order to avoid a fork.  Is this true?  If it is true, doesn't that mean your argument that "players can change the UNL" should be amended to disclose "players can change their UNL, but risk causing a hard-fork"?

A hard fork is the market solution to a misbehaving UNL set.  Bitcoin would have to perform a hardfork if the government ever got enough control over miners to enforce tainted coins.  The difference is that any bitcoin fork would also have to adopt a new POW that the government does not control and thus mean a massive coding change to something along the lines of a UNL.

- Shouldn't we build some kind of simulator or run a bunch of instances on localhost or something to observe e.g. the nodes reaching consensus?

Building that now.

- With respect to step 6 ("Once all transactions in my published proposal have at least 70% of the weighted vote convergence is guaranteed...")  What precisely is meant by convergence, and how is convergence guaranteed?  Mathematical proof, empirical simulation, practical experience (Ripple?), gut feeling, something else?

Assuming all nodes are running the algorithm they will have passed the tipping point where the 'rich get richer' and the 'poor get poorer' in terms of which nodes are included in the set.   This will of course be verified by the test system I am putting together that will push 7 trx per second randomly generated by 100 nodes and insure they reach consensus.

[theoretical]

I buy that Bitcoin's de facto centralization is something to be avoided if possible.  But I also want to be sure that your cure isn't worse than the disease, hence the skeptical questions.

If I'm wasting your time with elementary questions, and there's documentation where this is already explained, please, feel free to point me to those resources instead.

Okay, so here are my next questions:

- How do nodes outside the UNL know what has been approved by the UNL?  Do UNL nodes have hardcoded keys as well as hardcoded network addresses?  Or is a connection to a UNL node necessary for a client to function?

- Say I'm a node outside the UNL.  One of my peers feeds me a block that has a parent I've accepted and passes proof-of-stake signature, transaction validation, etc., but contains some transaction the UNL has never heard of.  How do I establish that the UNL has never heard of it?  What do I do with the block -- accept it, discard it, hold it for a while and see if the UNL eventually decides to like the transactions it contains, or something else?

- It seems like you might need a condition along the lines of "Most of the regular nodes (outside UNL) have to have nearly identical UNL lists" in order to avoid a fork.  Is this true?  If it is true, doesn't that mean your argument that "players can change the UNL" should be amended to disclose "players can change their UNL, but risk causing a hard-fork"?

- Shouldn't we build some kind of simulator or run a bunch of instances on localhost or something to observe e.g. the nodes reaching consensus?

- With respect to step 6 ("Once all transactions in my published proposal have at least 70% of the weighted vote convergence is guaranteed...")  What precisely is meant by convergence, and how is convergence guaranteed?  Mathematical proof, empirical simulation, practical experience (Ripple?), gut feeling, something else?

[bytemaster]

So all transactions are broadcast by another process, this algorithm is used to try to determine a subset S of the transactions known to the current node, such that all transactions in S are known to a large fraction of other nodes.  And then using this S as the set of transactions in the next block.

Why is this necessary at all?  What's wrong with just having every node do its own proof-of-stake on the set of transactions it knows about?

Also, what exactly are UNL nodes?  What is the process to become a UNL node?  If it's easy to become a UNL node, doesn't that make UNL vulnerable to sibyls?  If it's hard to become a UNL node, doesn't that make the network too centralized?

All nodes must AGREE on the next block to make sure the block chain doesn't diverge.  Bitcoin uses the lowest hash to decide what to agree on.   As a result bitcoin is centralized one block at a time.  Bitcoin is also centralized by 10 mining pools which approve 90% of the blocks and just 2 or 3 are required for 51% or more of the blocks. 

The UNL list is specified manually so is not subject to Sybil attacks.  To get on the list you just have to convince most of the existing nodes to add you to their list.  In effect, new people are 'voted' into the consensus process by the original.   I would aim to get about 100 nodes on the UNL list hosted in countries around the world. 

The free market is the truest form of decentralization as every individual is free to adapt.  The free market is based upon competition and thus freedom to compete must be the primary goal of all decentralized efforts.  Anything that restricts or limits competition is known as a barrier to entry and will result in a move toward centralization.   Mining power represents a form of barrier to entry that will be insurmountable by the average Joe once the government has tax payer funded mining factories full of ASICs, GPUs, and CPU/Memory.   No one will be able to launch a proof of work coin again without these mining factories 'owning' it. 

While the UNL list might appear centralized, all players at all times can change the UNL list and effectively elect a new management team.   If the UNL list consists of nodes in many jurisdictions, owned by many different people, then they will not be able or likely to colude to defraud anyone.  The only thing an 'evil' UNL group could do is 'stop transactions' in which case they can be replaced.

Thus decentralization is achieved through many competing chains with competing UNL groups and at no time does any chain get permanently locked in to one signing authority that just happens to control hash power.

[theoretical]

So all transactions are broadcast by another process, this algorithm is used to try to determine a subset S of the transactions known to the current node, such that all transactions in S are known to a large fraction of other nodes.  And then using this S as the set of transactions in the next block.

Why is this necessary at all?  What's wrong with just having every node do its own proof-of-stake on the set of transactions it knows about?

Also, what exactly are UNL nodes?  What is the process to become a UNL node?  If it's easy to become a UNL node, doesn't that make UNL vulnerable to sibyls?  If it's hard to become a UNL node, doesn't that make the network too centralized?

[bytemaster]

1) Every node publishes their initial transaction set to all other nodes in the UNL
2) A node will then tally the votes each transaction got as a percentage of the maximum (a vote from every node)
3) A node will then calculate the average "consensus" of each proposal by every other node (the average of the values calculated in step 2 for each proposal.   This average will then be used as the weight given to that transactions in that nodes proposal.  The result is that proposals with higher average consensus get a higher weight than proposals with lower average consensus.  If nodes want their opinion to carry weight they need to increase their average consensus in their next proposal.
4) I then recalculate the proposal for the current node by tallying the weighted votes each transaction got based upon the proposals it was included in.
5) I then take all transactions in the top 25% by weighted vote and publish them as my new proposal to all other nodes.
6) Once all transactions in my published proposal have at least 70% of the weighted vote convergence is guaranteed and a block can be produced and the process starts over.

Let's say a transaction is "popular" if it's in a lot of nodes' proposals, "unpopular" if only exists in a few nodes' proposals.

Won't your algorithm make unpopularity stable over time?

In other words, let's say there's a transaction that only exists on one node.  Won't other nodes always choose not to include it in their proposals because it's unpopular?

Of course, in a real network, pretty much all transactions enter the network from a single node.  So this analysis means no transaction will ever be accepted by any node other than its originator, and the network will be totally useless!  This absurd result tells me my analysis is wrong -- but how is it wrong?

All nodes attempt to fetch the transactions from all other nodes, ie: they are broadcast everywhere.  The consensus process selects transactions that have fully propagated over those that are only partially propagated.  Those not included in one block are likely to be included in the very next block.

[theoretical]

1) Every node publishes their initial transaction set to all other nodes in the UNL
2) A node will then tally the votes each transaction got as a percentage of the maximum (a vote from every node)
3) A node will then calculate the average "consensus" of each proposal by every other node (the average of the values calculated in step 2 for each proposal.   This average will then be used as the weight given to that transactions in that nodes proposal.  The result is that proposals with higher average consensus get a higher weight than proposals with lower average consensus.  If nodes want their opinion to carry weight they need to increase their average consensus in their next proposal.
4) I then recalculate the proposal for the current node by tallying the weighted votes each transaction got based upon the proposals it was included in.
5) I then take all transactions in the top 25% by weighted vote and publish them as my new proposal to all other nodes.
6) Once all transactions in my published proposal have at least 70% of the weighted vote convergence is guaranteed and a block can be produced and the process starts over.

Let's say a transaction is "popular" if it's in a lot of nodes' proposals, "unpopular" if only exists in a few nodes' proposals.

Won't your algorithm make unpopularity stable over time?

In other words, let's say there's a transaction that only exists on one node.  Won't other nodes always choose not to include it in their proposals because it's unpopular?

Of course, in a real network, pretty much all transactions enter the network from a single node.  So this analysis means no transaction will ever be accepted by any node other than its originator, and the network will be totally useless!  This absurd result tells me my analysis is wrong -- but how is it wrong?

[bytemaster]

What's the incentive for a node to have it's opinion carry weight?

How does this interact with POS?

The premise of Ripple's algorithm is that "failure to agree is agreeing to fail" and all nodes on the UNL are presumed to be trusted with the intention to reach an agreement.   A node that does not move toward consensus can be identified, flagged, and removed from everyones UNL. 

The consensus algorithm does not validate transactions, it merely selects a set of transactions some of which may fail to pass validation and thus be pruned by all nodes.  The result is a deterministic generation of a common block.

In other words the UNL nodes are only "trusted" for a small task and no one node ever has as much power as miners get in the Bitcoin network (dictator for a block).   

Once the Unity algorithm has run it will produce a block which must pass validation by everyone else in the network, even those not on the UNL.  The rest of the network (normal users) then confirm the decision of the UNL nodes by referencing the head block's hash in their transactions.  The coin-days-destroyed by everyone else broadcasting transactions after the consensus gradually makes the chain irreversible even by the UNL nodes.

[toast]

What's the incentive for a node to have it's opinion carry weight?

How does this interact with POS?

[bytemaster]

Today I designed and mostly implemented my version of Ripple's consensus algorithm which I am calling Unity.  It uses a slightly different algorithm that I think will converge faster.   I took the view that the nodes in the UNL are like neurons in a fully connected neural network.   The goal is to create a positive feedback loop that moves all nodes toward a stable steady state.  Here is how the algorithm works:

1) Every node publishes their initial transaction set to all other nodes in the UNL
2) A node will then tally the votes each transaction got as a percentage of the maximum (a vote from every node)
3) A node will then calculate the average "consensus" of each proposal by every other node (the average of the values calculated in step 2 for each proposal.   This average will then be used as the weight given to that transactions in that nodes proposal.  The result is that proposals with higher average consensus get a higher weight than proposals with lower average consensus.  If nodes want their opinion to carry weight they need to increase their average consensus in their next proposal.
4) I then recalculate the proposal for the current node by tallying the weighted votes each transaction got based upon the proposals it was included in.
5) I then take all transactions in the top 25% by weighted vote and publish them as my new proposal to all other nodes.
6) Once all transactions in my published proposal have at least 70% of the weighted vote convergence is guaranteed and a block can be produced and the process starts over.

I will be implementing a unit test that will throughly verify that this can be maintained at high speed, high volume, and a large number of nodes in the UNL for reasonable bandwidth.

[toast]

switch to consensus algorithm as soon as you are able please
I'm sure testers and your new hires will have an easier time with market bugs than with ripple/PoS