Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: TaPOS Consensus / Fork Management  (Read 961 times)

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

TaPOS Consensus / Fork Management
« on: March 14, 2014, 10:22:24 PM »

Consensus with Proof of Stake

The technology at the core of Bitcoin was a means to reach decentralized consensus on the state of transaction ledger.   Bitcoin defined one simple metric by which the best transaction ledger could be identified: the longest ledger.   

On average every ten minutes someone on the Bitcoin network would win a block as a result of their computational effort.   If blocks are found more frequently than every ten minutes the network would automatically adjust the difficulty of winning a block to maintain the desired rate.   As the number of people competing grows the difficulty becomes so high that no one individual (in theory) can produce blocks as fast as everyone working together. 

Bitcoin uses the policy ‘one-hash, one-vote’ for deciding which transaction ledger is the best ledger.  The more votes that are behind a particular blockchain, the more people support that chain.  That is the theory anyway.  In practice a small number of individuals control the vast majority of the votes.

With Proof of Stake systems each shareholder gets one vote per block.  As owners of the chain and parties interested in the outcome this process is also an effective means of reaching consensus if it can be implemented efficiently.   When ever there is a disagreement about which change should be applied to the ledger then the dispute must be resolved by shareholder votes.

Every time a transaction is made by the network, the individual making the transaction simultaneously cast one vote per share transacted for every block produced since the last time they voted.   Every users is required to transact at least once per year or face a 5% inactivity fee and a loss of their opportunity to vote. 

The result of this process is that after 12 months every block in the block chain has been either voted for (or against) by almost every.  It can therefore be proven beyond a doubt which block had the majority of shareholder consensus.   

Ideally everyone would vote on every block so that immutable consensus could be reached as quickly as possible.  In practice, this would be expensive and overkill as everyone would have to sign every block.  To resolve this process voting is done on a continual basis as users make transactions.   This means that for recent blocks there are not enough votes cast to be considered irreversible. 

Bitcoin considers transactions to be irreversible after 6 blocks; however, this is only true if you assume the network is able to maintain its hash power and that the attacker’s hash power is only 49% of then network hash power.   

Under proof-of-stake, a transaction is considered irreversible when it becomes highly unlikely that other shareholders could achieve 51% of the votes for an alternative chain.   There are generally three cases where shareholders would end up voting for an alternative chain:

  1) The network has split at an infrastructure level and causes entire continents to start producing their own alternative chains.   When network connectivity is restored many transactions will have to migrate from one chain to another and in many cases a lot of transactions will become invalid in the process.   Because no one wants their transactions to become invalid, everyone competes to resolve the fork by casting votes (making transactions) on one chain or the other.    Eventually the block at which the chains diverged will accumulate 51% of the votes and the fork will be resolved.

 2) The network has split because an attacker is attempting to double spend.  In this case, the attacker is attempting to take advantage of the fact that only a small percentage of shareholders are voting every block.  The attacker users all of their votes in one go in an attempt to hijack the network with an alternative chain that no one but the attacker was aware of.

To resolve such an attack nodes on the network simply ignore all alternative chains that fork more than 6 blocks ago, unless said alternative chain has at least 25% of the shareholders voting for it and it has at least 10% more votes than the chain the node is currently on, or 51% of all shareholders.
 
3) Latency can also cause forks in the short-term.  These forks are caused when propagation delay and randomness associated with the time between finding consecutive blocks causes part of the network to see 2 or 3 blocks before the rest of the network.  This use case if by far the most common and must be resolved quickly in order to prevent the fork from becoming a problem for the users.     

Latency induced forks can be mitigated by following some simple logic on determining the best chain in the short term.

    a) All blocks must have  a time stamp at least 1 minute after the previous block and must not have a timestamp in the future.   Nodes are synchronized via NTP.    This simple rule gives at least one minute of propagation time between blocks.

    b) To produce a block in the first place requires at least a minimum number of votes and the accumulation of enough transaction fees to be worth the ‘miners’ time.   This will serve as a delay on producing blocks. 

   c) The head block can always be replaced if a better head block is found.  This means that if two (or more) blocks are found at once, then only one of them will be accepted by the network and there will be at least a minute between blocks for the network to converge. 

    Despite these protections, there is still the potential for there to be short 2 or 3 block forks.  In this case nodes in the network defer to a trusted peer list which operates on a basis similar to Ripple’s consensus algorithm. 

   Perhaps the most important and critical factor in resolving forks is that the shareholders can always take action if necessary and unambiguously resolve the fork.  Everything else is simply measures to reach consensus quicker.   

   All of that said, we will have a single trusted key broadcast the official fork after 2 blocks so that any nodes that end up on a different fork can switch to the proper fork without much delay.  This will be for training wheels and security while the network is in its testing phase.   

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline Troglodactyl

  • Hero Member
  • *****
  • Posts: 958
    • View Profile
Re: TaPOS Consensus / Fork Management
« Reply #1 on: March 14, 2014, 10:52:46 PM »
Nice, great overview!

First sentence in paragraph 4 I think should be: "With Proof of Stake systems each shareholder gets one vote per block per share held."

Offline biophil

  • Hero Member
  • *****
  • Posts: 814
  • Incentives run the world
    • View Profile
    • Sign up for a Bitshares account!
  • BTS: zebulon
Re: TaPOS Consensus / Fork Management
« Reply #2 on: March 14, 2014, 11:33:35 PM »
Thanks, this is great.

I have one slight cosmetic criticism: I found myself initially very uneasy about the concept of "voting" until I realized that it's just a word that means "every transaction that I send, my wallet automatically says which chain it thinks is the correct chain."

I think the problem is that "voting" conjures up images of human choice, and I initially felt like I was going to have to go in and personally cast a vote, which is really intimidating idea, though clearly absurd and not what you're talking about.

I wonder if there might be a friendlier word than "vote" that you could use here, just to avoid the connotations of human choice, and increase the intuitive clarity of the documentation. Or even just calling it an "automatic vote" here and there. Or since each transaction has a vote, call it a "tx-vote" or something un-pronounceable like that.

Ok, I'm done nitpicking. I really did appreciate the write-up!

Offline bytemaster

Re: TaPOS Consensus / Fork Management
« Reply #3 on: March 14, 2014, 11:56:09 PM »
Thanks, this is great.

I have one slight cosmetic criticism: I found myself initially very uneasy about the concept of "voting" until I realized that it's just a word that means "every transaction that I send, my wallet automatically says which chain it thinks is the correct chain."

I think the problem is that "voting" conjures up images of human choice, and I initially felt like I was going to have to go in and personally cast a vote, which is really intimidating idea, though clearly absurd and not what you're talking about.

I wonder if there might be a friendlier word than "vote" that you could use here, just to avoid the connotations of human choice, and increase the intuitive clarity of the documentation. Or even just calling it an "automatic vote" here and there. Or since each transaction has a vote, call it a "tx-vote" or something un-pronounceable like that.

Ok, I'm done nitpicking. I really did appreciate the write-up!

This is great feedback and I will incorporate it into future versions.   I wanted to use the term 'voting' despite my dislike of all things voting because it is generally well understood. 

There is still an element of human choice here, just like there is with bit coin.  People can choose which 'fork' they want to be on and then make transactions on that fork.   Generally speaking though the software will choose and it will be entirely transparent.
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline MolonLabe

  • Full Member
  • ***
  • Posts: 58
    • View Profile
Re: TaPOS Consensus / Fork Management
« Reply #4 on: April 03, 2014, 06:48:19 PM »
I actually don't understand how blocks are constructed after reading this.

Say I want the transaction fees, there are enough votes, and it has been a minute since the last block.

How do I mine the block and get the fees? Am I submitting any PoW at all? Is it first come first serve?

Offline bytemaster

Re: TaPOS Consensus / Fork Management
« Reply #5 on: April 04, 2014, 02:10:48 AM »
This thread is no longer relevant and has been replaced by a soon to be release paper on Delegated Proof of Stake + TaPOS
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12339
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BTS: xeroc
  • GitHub: xeroc
Give BitShares a try! Use the http://testnet.bitshares.eu provided by http://bitshares.eu powered by ChainSquad GmbH

Offline fuzzy

Re: TaPOS Consensus / Fork Management
« Reply #7 on: April 06, 2014, 04:43:30 AM »
discussion:
https://bitsharestalk.org/index.php?topic=4009.0;topicseen

paper:
http://107.170.30.182/security/delegated-proof-of-stake.php

If only Electing our "representatives" worked this way in the current political system.  Is this analogy fair?  I'd like to hear opinions...

If so, we might right now be looking at the beginnings of something truly amazing. 
« Last Edit: April 06, 2014, 04:47:12 AM by fuznuts »
WhaleShares==DKP; BitShares is our Community! 
ShareBits and WhaleShares = Love :D

Offline sfinder

  • Hero Member
  • *****
  • Posts: 1205
  • 4 Cores CPU+100GB SSD+anti-DDoS Pro
    • View Profile
Re: TaPOS Consensus / Fork Management
« Reply #8 on: April 06, 2014, 09:39:54 AM »
i found wrong numbering sub-titles in DPOS white paper as shown below in red

Quote
2.5 Are 100 Representatives Decentralized?

The definition of decentralized is hard to pin down because it has become a buzzword. We consider the free market to be the ultimate form of decentralization and barriers to entry to be the basis of all centralization. Like many things, there are degrees of centralization so we will instead compare the relative centralization of Delegated Proof of Stake to the other alternatives.
2.3.1 Bitcoin  ---change to 2.5.1

Bitcoin currently operates on the basis of Delegated Proof of Work (DPOW) and therefore has about 10 representatives that control the vast majority of the hashing power. Hashing power is itself centralized in the hands of those who can employee economies of scale to make mining unprofitable for their competition. Lastly, proof of work creates a barrier to entry that prevents incumbents from being easily displaced. Compared to Bitcoin, DPOS is at least 10x more decentralized in block production and perhaps infinitely more decentralized relative to market competition.

Despite a limited amount of decentralization in hashing power, when it comes to percentage of shareholders (bitcoin holders) who are in control of Bitcoin we estimate it is clearly the most centralized. If you consider the population of everyone who uses Bitcoin probably less than a fraction of a percent currently participate in mining.
2.3.2 Peercoin---change to 2.5.2

Peercoin is a hybrid coin and is thus partial centralized by the proof of work. Like Bitcoin it also has mining pools. Compared to Bitcoin the Peercoin is certainly more decentralized; however, because proof of stake mining requires users to keep their computers on and wallets unlocked, only a small percentage of the shareholders participate in any kind of mining.
2.3.3 Nxt---change to 2.5.3

Nxt uses transparent forging where the next node is deterministically selected. It can be compared to using Delegated Proof of Stake where the only person you can delegate to is yourself and the frequency in which you have the opportunity to forge a block is directly related to your balance. In this sense Nxt is more decentralized than Peercoin and Bitcoin, but still suffers poor user participation due to security risks and the fact that most regular users do not leave their computers on all day to take advantage of the opportunity.

From this perspective we can conclude that the Nxt network is being secured by a small minority of the shareholders. In effect, if you don’t show up to vote you lose your vote. To resolve this issue some Nxt users pool their funds and trust a 3rd party to mine for them. This increases shareholder participation by being a form of Delegated Proof of Stake, but also risks their balance while they are participating in the pool.


« Last Edit: April 06, 2014, 09:43:37 AM by sfinder »
微博:星在飘我在找|BTS X 受托人delegate ID:baidu
中国教育书店合作将20%收入捐献给贫困山区学生。
Cooperating with China Education Bookstore and will donate 20% of delegate income to the poor students

 

Google+