Author Topic: One possible attack to POS mining  (Read 3820 times)

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

Quote
In the long term the network is far more secure and the best fork can be unambiguously chosen.

This appears true to me, but I'm not aware of a formal proof. Is there one? The TaPoS paper appears to be out of date, mentioning CDD as an absolute measure on the chain rather than a measure per block.


Formal proof... yes one exists... no it is not written down... but it comes down to this:

At least once per year everyone most move their balance.  When they do this they also 'vote' on the current chain which cements everything before it.   Once 51% of the shares have moved you have a non-ambiguous vote for everyone on every transaction prior to that point.   The only question is how long does it take to get to 51% and this depends upon the average shares in circulation and the velocity of trading.   Worst-case average is about 6 months to get to 51%.  But I think you could get to 25% in less than 1 month and 10% in a day or two.   

For all practical purposes though there is no reason to suspect that the network would ever collude to rewrite the transaction history barring a real physical network split...  For a large anonymous transaction simply waiting until enough votes had piled on top of the transaction to make it irreversible is all that matters.

Think of TaPOS as continuous checkpointing. 
 


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 jaekwon

  • Newbie
  • *
  • Posts: 2
    • View Profile
Quote
In the long term the network is far more secure and the best fork can be unambiguously chosen.

This appears true to me, but I'm not aware of a formal proof. Is there one? The TaPoS paper appears to be out of date, mentioning CDD as an absolute measure on the chain rather than a measure per block.

Quote
1) Double Spend - requires someone with significant money to make an anonymous transaction to avoid getting caught.   Large anonymous transactions will likely require hours of confirmation.

Why must large anonymous transactions require hours of confirmation?

Quote
If a large share holder were to execute a double spend attack the value of their shares would likely fall by more than they could steal.   If the transaction were not anonymous then everyone would know who to avoid doing business with.

The fall would presumably be temporary, otherwise I can argue that a small investment of $15M may be sufficient to crash the value of the coin, even if BTS were to reach the market cap of BTC.

There may be externalities that incentivize a large share holder to intentionally lose value in exchange for a double spend.  There are many examples, but a few that comes to mind: the attacker may have short positions in external markets, e.g. in those of companies that utilize this coin.  Or, the attacker may have an incentive to promote another currency system.

Offline bytemaster

Hi bytemaster, and BitShares crew. I was just at the CoinSummit conference & met Brian who suggested that I look into BitShares.

My primary concern is in determining whether the TaPoS would work as promised, and it looks like some answers are here.

Suppose someone with 1 share, holds it for 1 year, and then creates a fork with 100,000 CDD.   In reality there is only 1 share worth of support for that fork.   The rest of the 99,999 CDD is voting for the global consensus on the first 99,999 blocks prior to the fork.

This significantly raises the bar for an attacker.   Worst case, everyone on average moves their funds once per year.  This means that the average votes cast per block is 40 BTS.  To produce a chain that is 12 blocks longer (1 hour) would require 480 BTS to tie the honest chain.

So I take it that there are about 4 million BTS in total. (~100K blocks in a year * 40 BTS per block).
It sounds like you determine the honest chain by some algorithm like this: Given that you are on an honest block, the next honest block is the block with the most votes.

Now the attack isn't actually guaranteed even when an attacker has 2500 BTS.  Honest nodes would recognize an attempted fork when there was no perceived loss of network connectivity.   Someone with a lot at stake (say an exchange, a day trader, etc) would not want a fork under any circumstances if they could help it.   These players could secure the network (and their recent trades) by moving a 1000 BTS per block to themselves.   This would increase the cost of an attack significantly.

It sounds like the short term security of the chain (proof against double-spends) is determined by how many BTS are available for signing by internet connected hot-wallets that are ready to jump in when a malicious blockchain-fork is detected. Exchanges can't do this with their cold wallet private keys, but they could with hot wallet keys which would amount to maybe 2000 BTS per major exchange. Let's say that in the worst case, 10,000 BTS is available for reactive signing to secure the honest chain. Then, anyone with more than 10,000 BTS can launch an attack. If BTS equaled BTC in market cap, that is around $15M?

Furthermore, based on the first quoted line above, an attack can be continuous, so a larger sustained attack would require people to keep funds that would have been in cold storage on a hot wallet.

Thanks for your feedback and questions, let me address them.... 

In the long term the network is far more secure and the best fork can be unambiguously chosen.  The challenge how do we secure the network in the short term.  To achieve this we need to make some assumptions:

1) Attackers must keep their chain secret for a double spend attack to work.
2) If you are well connected and 2-3 blocks have passed then you assume you have seen the public chain and alternatives are attacks.
3) If alternatives are attacks you only care about them if they have an insurmountable lead in votes cast over your fork.
4) The existence of a fork beyond 2-3 blocks as a result of a network split is cause for every member of the network (not just exchanges) to take an interest in resolving the fork in favor of the majority of the shareholders. 

Now lets consider what kind of attacks are possible:

1) Double Spend - requires someone with significant money to make an anonymous transaction to avoid getting caught.   Large anonymous transactions will likely require hours of confirmation.  If a large share holder were to execute a double spend attack the value of their shares would likely fall by more than they could steal.   If the transaction were not anonymous then everyone would know who to avoid doing business with.

2) Denial of Service - this attack would fail because blocks that contain more transactions automatically outrank everyone else.

The biggest challenge is actually deciding who gets to produce the block and not in securing the network once blocks are produced.   I actually think that having a single trusted block signer would allow a faster network without compromising the security of the network.   The reason for this is that the block signer would not be able to reverse the transaction ledger once a transaction had been made.   The only down side to a single signer is that they could perform Denial of Service attacks if they failed to sign or include blocks.  However, once it became known that the trustee of the network was a bad actor any competitor could crop up and take over that role. 

The trustee model has the downside of a central point of failure... but the upside of huge performance gains and savings (profits) for the users of the network.  Right now Ripple is operating under the trustee model as their network is secured by 5 nodes all controlled by them.   In the case of Ripple though the network is reversible if the nodes colluded.   

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 jaekwon

  • Newbie
  • *
  • Posts: 2
    • View Profile
Hi bytemaster, and BitShares crew. I was just at the CoinSummit conference & met Brian who suggested that I look into BitShares.

My primary concern is in determining whether the TaPoS would work as promised, and it looks like some answers are here.

Suppose someone with 1 share, holds it for 1 year, and then creates a fork with 100,000 CDD.   In reality there is only 1 share worth of support for that fork.   The rest of the 99,999 CDD is voting for the global consensus on the first 99,999 blocks prior to the fork.

This significantly raises the bar for an attacker.   Worst case, everyone on average moves their funds once per year.  This means that the average votes cast per block is 40 BTS.  To produce a chain that is 12 blocks longer (1 hour) would require 480 BTS to tie the honest chain.

So I take it that there are about 4 million BTS in total. (~100K blocks in a year * 40 BTS per block).
It sounds like you determine the honest chain by some algorithm like this: Given that you are on an honest block, the next honest block is the block with the most votes.

Now the attack isn't actually guaranteed even when an attacker has 2500 BTS.  Honest nodes would recognize an attempted fork when there was no perceived loss of network connectivity.   Someone with a lot at stake (say an exchange, a day trader, etc) would not want a fork under any circumstances if they could help it.   These players could secure the network (and their recent trades) by moving a 1000 BTS per block to themselves.   This would increase the cost of an attack significantly.

It sounds like the short term security of the chain (proof against double-spends) is determined by how many BTS are available for signing by internet connected hot-wallets that are ready to jump in when a malicious blockchain-fork is detected. Exchanges can't do this with their cold wallet private keys, but they could with hot wallet keys which would amount to maybe 2000 BTS per major exchange. Let's say that in the worst case, 10,000 BTS is available for reactive signing to secure the honest chain. Then, anyone with more than 10,000 BTS can launch an attack. If BTS equaled BTC in market cap, that is around $15M?

Furthermore, based on the first quoted line above, an attack can be continuous, so a larger sustained attack would require people to keep funds that would have been in cold storage on a hot wallet.


Offline bytemaster

Nodes never automatically replace anything but the head block and only replace this with in a small window of time to account for 2 blocks being found 'at the same time'.   

Wouldn't there be a non-negligible probability of a fork, if for example a small subset of nodes becomes isolated from the network and produces two blocks in a row?

A fundamental design principle of Bitcoin is that the network can recover automatically from a fork caused by a network split; everyone picks the chain with more blocks.  Unless I'm missing something, your scheme always assumes the local fork is the correct one, and therefore any temporary split which causes a branch to get two blocks ahead becomes permanent.

This is a very good point and so I want to consider it carefully. 

Using the shareholder voting analogy, we can easily resolve any dispute with a shareholder vote.  Any block that has the majority of shareholder votes is automatically accepted as the best block.    Lets forget CDD for a second, because it is an approximation that I think confuses what is really going on.    When someone moves 100 BTS from block 60 to block 100, they are really casting 100 votes for each block (60,61,62..99).   We can therefore see where CDD comes from, it is the total votes cast. 

When it comes to resolving a fork, we do not care about 'longest chain' or even 'most CDD'.... we care about what percent of the shareholders are on each fork.   Let give an example:

Suppose someone with 1 share, holds it for 1 year, and then creates a fork with 100,000 CDD.   In reality there is only 1 share worth of support for that fork.   The rest of the 99,999 CDD is voting for the global consensus on the first 99,999 blocks prior to the fork.

This significantly raises the bar for an attacker.   Worst case, everyone on average moves their funds once per year.  This means that the average votes cast per block is 40 BTS.  To produce a chain that is 12 blocks longer (1 hour) would require 480 BTS to tie the honest chain.    Once again this is worst case.  I think we can assume that with mining, trading, etc, the average velocity will be some significant multiple of this.  For the sake of argument i will assume 5x the minimal.  This would increase the cost of the attack to 2500 BTS.   Based upon the PTS price drop that would indicate a $25,000 attack and once this grows to be the size of Bitcoin the cost of the attack would be almost $2 million.   

Now the attack isn't actually guaranteed even when an attacker has 2500 BTS.  Honest nodes would recognize an attempted fork when there was no perceived loss of network connectivity.   Someone with a lot at stake (say an exchange, a day trader, etc) would not want a fork under any circumstances if they could help it.   These players could secure the network (and their recent trades) by moving a 1000 BTS per block to themselves.   This would increase the cost of an attack significantly.

So we have a means to uniquely identify he best chain based not upon how many blocks, but how many votes it has.  An attacker may get the lead for a sort period of time, but at any time honest nodes can simply vote for a better chain.    Generally speaking the honest nodes will only want to vote for the chain they have seen until there is overwhelming evidence that the alternative chain has more support than any reasonable attacker would generate. 

So when the client notices a fork, it notifies the user of yellow alert.  If the fork has more votes then you are in red alert.  You do not switch over to the fork until it has 5% (of total possible votes: share supply) more of the share holders on its side than your fork.   When this happens, those in the know will quickly act to resolve the issue and all clients will move on.
 
   

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 theoretical

Nodes never automatically replace anything but the head block and only replace this with in a small window of time to account for 2 blocks being found 'at the same time'.   

Wouldn't there be a non-negligible probability of a fork, if for example a small subset of nodes becomes isolated from the network and produces two blocks in a row?

A fundamental design principle of Bitcoin is that the network can recover automatically from a fork caused by a network split; everyone picks the chain with more blocks.  Unless I'm missing something, your scheme always assumes the local fork is the correct one, and therefore any temporary split which causes a branch to get two blocks ahead becomes permanent.

BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk

Offline bytemaster

The TaPOS paper is slightly out of date from the implementation I am using.

1) Every block requires at least a minimum number of CDD (equal to AVAILABLE_CDD/ BLOCKS_PER_YEAR)
2) Nodes never automatically replace anything but the head block and only replace this with in a small window of time to account for 2 blocks being found 'at the same time'.   

Given these two rules no one can generate a secret chain and much of the speculation on potential attacks go away. 

Next I embed IP:PORT of peer nodes in the blockchain as a means of protecting new individuals who join the network.   This limits the ability to flood the network with bogus nodes and establishes a history for nodes. 

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 HackFisher

  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Quote
Bitcoin’s security metric of 6 confirmations indicating near certainty that the transaction
is final only applies to proof-of-work based security. Absent proof-of-work the number of
blocks that have confirmed your transaction is meaningless. Instead, the metric users
should care about is coin-days-destroyed since your transaction. The higher this
number, the more expensive a ‘random’ double spend would become. In theory it is
possible to have security against a double spend attack equivalent to Bitcoin after a
single confirmation if that block destroyed enough coin-days. !

I have some question about this part in TaPOS paper, but it will not affect your major idea about the different metric between POW and TaPOS
Which is the key to decide which blockchain will be chosen by other honest nodes for mining or validating transactions?
the length of the blockchain or the accumulated CDD before that block?

Is it possible that someone use less CDD to achieve same block length in another secret blockchain? For example, in first period, transaction CDD are too much, and the difficulty go up,  then in second period, the difficulty go down, this give the attacker a chance to use less CDD relative to first period to achieve same length blocks. From this perspective, with the consideration of changing difficulty,  "coin-days-destroyed since your transaction" seems not the exactly security metric for users? Am I right?

And, I have the idea that CDD is approximately linear to blocks length from user transaction to now, if the difficulty was not changed in this period.
Otherwise, the security metric (CDD the attacker need to accumulated exactly) should be something like
(avg_next_difficulty/avg_last_difficulty) * last_CDD

please point the flaws in my conclusion.
« Last Edit: March 11, 2014, 08:51:14 am by HackFisher »
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 zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
http://the-iland.net/static/downloads/TransactionsAsProofOfStake.pdf

Pages 5 and 6 seem to address these issues.  Also, I suspect that there's a maximum on coin day accumulation.  When the inactivity fee is charged, doesn't this effectively reset the coin age to 0?

Yes it does.

Thanks for the clarification and this does eliminate the risk quite a lot.

What if I carefully choose time when large CDD just happened which means my percentage of CDD grows relatively? Also consider the diversity of shares, even if you find my attack in short time, it will be difficult to collect enough coin days to beat my alternative chain in time. It turns worse as time goes on when this alternative chain grows as I'm in the longest chain and all the following transactions are protecting me.

I think the point here is that comparing with total CDD in a block, I don't need much percentage of shares to make an attack. I suspect one block will destroy less than 1% of coin days in average. This means the cost of an attack is low. If I have 10% shares, even if it's defeated to discarded branch chain, it's relatively easy to roll back several blocks and make it survive 1 or 2 future blocks. To defeat it, you may need manual processes. This will not happen in POW if you own 10% power and it will be quite impossible that you can roll back 1 block because to do so, you'll need to win at least 2 sequencial blocks and it contains randomness. But with POS, you'll be assured your attack can work as I don't see any randomness in POS mining. Maybe we should inject some randomness in the mining to solve this issue.
« Last Edit: March 11, 2014, 08:24:30 am by zhangweis »
Weibo:http://weibo.com/zhangweis

Offline zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
Hmm, I think the answer is that your CDD can only accumulate on the current longest chain, you can't make an alternate longer chain because if you start building off of an old block then your coins will look much younger with respect to that block.

Let's say I want to roll back 10 blocks and my CDD will be just a little younger than the current longest chain.
Weibo:http://weibo.com/zhangweis

Offline bytemaster

http://the-iland.net/static/downloads/TransactionsAsProofOfStake.pdf

Pages 5 and 6 seem to address these issues.  Also, I suspect that there's a maximum on coin day accumulation.  When the inactivity fee is charged, doesn't this effectively reset the coin age to 0?

Yes it does.
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: 960
    • View Profile
http://the-iland.net/static/downloads/TransactionsAsProofOfStake.pdf

Pages 5 and 6 seem to address these issues.  Also, I suspect that there's a maximum on coin day accumulation.  When the inactivity fee is charged, doesn't this effectively reset the coin age to 0?

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
Hmm, I think the answer is that your CDD can only accumulate on the current longest chain, you can't make an alternate longer chain because if you start building off of an old block then your coins will look much younger with respect to that block.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
Even if the coin days are cut to be less than 365 days, I guess 20% of the shares can be enough to make such an attack if I carefully choose time to attack.

I can spend the coins before my attack and roll them back so that I lose very little no matter the value of shares drops or not after the attack.
« Last Edit: March 11, 2014, 04:04:23 am by zhangweis »
Weibo:http://weibo.com/zhangweis

Offline zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
Please correct me as I'm not a native speaker and could have some wrong understandings.
Suppose I'm a bad miner, what can I do? I can
1. Exclude some transactions. This doesn't harm much as I can only make few attacks in a short period of time. In fact, you can't even tell whether I'm a bad miner excluding some transactions or I'm a good miner who hasn't received the transactions yet.
2. Roll back some transactions by rolling back some blocks. This is interesting. But how can I do that?
Well, I need some percentage of shares. Let's say I have 10% shares. As the yearly inactivity fees exist, most of shares will have (maybe much) less than 365 coin days. I can easily accumulate my coin days to 50% by not destorying the coin days for 5.x years. Using the coin days I accumulated, I can roll back a large number of blocks. The number can be really large (like 100) as I have 50% of coin days. How many confirmations do you need to feel safe for a transaction? 6, 10? I would say at least 100. Considering I can choose time when large CDD happened one day before and the diversity of the shares, the percentage of shares I need will be much less.
Weibo:http://weibo.com/zhangweis