Bitcoin Forum
December 04, 2016, 10:24:42 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2] 3 »  All
  Print  
Author Topic: Unfreezable blockchain  (Read 4358 times)
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 12, 2012, 04:39:22 PM
 #21

But the attacker can always overwrite everything, as he has >50%.

Say the attacker is freezing the trunk. An honest miner manages to branch it with a good block. Now the tree with the good block has a stronger proof-of-work, true.
But the attacker can double-spend anything that was on this branch in the trunk, as long as the original sender signs him a double-spend.

In the case of conflicting transactions, as I said in OP, you need to make a choice. I thought of giving priority to the trunk, it seems Maged prefers to say that a tree with conflicting transactions is entirely invalid. Either way the attacker is in advantage. In my suggestion he just overwrite the transaction. In Maged scenario, he inserts the double-spend in his tree which will not contain the honest branch. The honest tree will be temporarily stronger, but as soon as the attacker makes his trunk stronger than the honest tree (he has >50%), he'll completely invalidate the honest tree, and honest miners will not be able to rebuild on top of his work anymore, unless if they ignore the conflicting transaction. What in practice is the same thing as the attacker overriding the transaction.

Do you see what I mean? In the end, every transaction inserted by honest miners is potentially reversible. You can try to "legitimately double-spend it" as I suggested above, but if it the attacker doesn't bite it, the transaction must be treated as reversible/unconfirmed.
1480847082
Hero Member
*
Offline Offline

Posts: 1480847082

View Profile Personal Message (Offline)

Ignore
1480847082
Reply with quote  #2

1480847082
Report to moderator
1480847082
Hero Member
*
Offline Offline

Posts: 1480847082

View Profile Personal Message (Offline)

Ignore
1480847082
Reply with quote  #2

1480847082
Report to moderator
1480847082
Hero Member
*
Offline Offline

Posts: 1480847082

View Profile Personal Message (Offline)

Ignore
1480847082
Reply with quote  #2

1480847082
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480847082
Hero Member
*
Offline Offline

Posts: 1480847082

View Profile Personal Message (Offline)

Ignore
1480847082
Reply with quote  #2

1480847082
Report to moderator
Meni Rosenfeld
Donator
Legendary
*
Online Online

Activity: 1890



View Profile WWW
January 12, 2012, 04:49:55 PM
 #22

Do you see what I mean? In the end, every transaction inserted by honest miners is potentially reversible. You can try to "legitimately double-spend it" as I suggested above, but if it the attacker doesn't bite it, the transaction must be treated as reversible/unconfirmed.
No, I don't. As I said you shouldn't invalidate a parent if it has a conflicting transaction, you just don't include this transaction. If the attacker references a block with transactions he must include them (which as I said should be a rule), if he consistently doesn't include blocks he will lose the total PoW race.

">50% = Rewrite the block chain" works for the current "one chain" rule, it doesn't work for the the "trunk with side branches" proposal.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 12, 2012, 04:59:15 PM
 #23

How will rewards be handled? Seems the most reasonable way is that only blocks on the main chain get generation rewards and transaction fees. This has the disadvantage that mining rewards will be less predictable because of the high orphan rate. Also might be an opening for denial-of-reward attacks.

I don't see a reason not to credit transaction fees. I talked about this on the OP of this thread:
That's a good point. One requirement of merging might be that the coinbase of the block that is doing the merge must also credit the same coinbase out scripts from the absorbed blocks with the transaction fees. The only problem with that, however, is what do you do about Eligius? You'd have to require that coinbases can only have one output.

You can't credit the whole block reward, because if the difficulty goes up, people would just mine off of older blocks and hope that they get merged. Orphan blocks MUST be practically worthless. That being said, when there is no more block reward, the same difficulty manipulation could be used to get just the transaction fees. Thus, we are left with two choices (both of which are good):
1) Require crediting transaction fees (doing this for the block reward would be a breaking change to the protocol that requires 100% of nodes to upgrade) to the absorbed block's miner if, and only if, the block was mined on the same or higher difficulty.
2) Don't credit anything. (works much better with the existing code)
The only attack I can think of off the top of my head to reduce the effectiveness of this is to send different double-spend transactions to each peer, in the hopes of making any orphans that are created unmergeable. However, this can be reduced if the miners actually choose to communicate with each other and decide which transaction to go with, or use other such heuristics.
This can probably be solved the following way: Decide on a specific order among the parents and scan them in that order. Include any transaction which does not conflict with any previously encountered transaction, but do not invalidate a parent just because a transaction conflicts with one in another parent.
NO! ABSOLUTELY NOT! There's a reason I made it that way in the mini-spec.

Big picture: A block that doesn't conflict with the chain is a vote for that chain. If something in the block DOES conflict, however, that's clearly a vote for another chain.

Possible exploit: A chain made in secret with double-spends could absorb blocks from the main chain, allowing an attacker to overtake the main chain with a mere fraction of the hashrate and a little luck.

Unfortunately, this just made me think of a DANGEROUS exploit against my scheme. An attacker could store up orphan blocks that they mined in order to include them later in a conflicting chain. This can be mitigated by setting my X to a low number, say 2-6. (20-60 minutes worth of blocks on other chains)
When a mining client receives a VALID, unused orphan block/blockchain that connects to the main chain somewhere in the last X blocks (where X is a number that I haven't really decided on),

What's the interest of having a X maximum block delay for merging? Wouldn't it be interesting to allow miners to intentionally branch blocks deep in the past for some reason, like spending an old output with an easier difficulty? I don't see any problems with that.
Originally it was to prevent block spam and to allow pruning, but as you see above, it's now more important than before.

Meni Rosenfeld
Donator
Legendary
*
Online Online

Activity: 1890



View Profile WWW
January 12, 2012, 05:48:09 PM
 #24

Possible exploit: A chain made in secret with double-spends could absorb blocks from the main chain, allowing an attacker to overtake the main chain with a mere fraction of the hashrate and a little luck.
I'm not sure this will work. You'll have a rule saying that the parent with the most PoW contribution is scanned first (and continuing in descending order). So when the attacker absorbs blocks from the main chain, he needs his side chain to be larger if he wants his double-spend transaction to be included. I haven't worked it out but it might turn out that to succeed in the end he needs >50% hashrate.

Of course there's a lot that needs to be thoroughly investigated, but I'm still not convinced my way fails.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 12, 2012, 08:00:01 PM
 #25

Possible exploit: A chain made in secret with double-spends could absorb blocks from the main chain, allowing an attacker to overtake the main chain with a mere fraction of the hashrate and a little luck.
I'm not sure this will work. You'll have a rule saying that the parent with the most PoW contribution is scanned first (and continuing in descending order). So when the attacker absorbs blocks from the main chain, he needs his side chain to be larger if he wants his double-spend transaction to be included. I haven't worked it out but it might turn out that to succeed in the end he needs >50% hashrate.

Of course there's a lot that needs to be thoroughly investigated, but I'm still not convinced my way fails.

Proof by counter-example:
Assume the attacker gets lucky at some point and finds two blocks in a row. They normally find blocks every 6 "-", while the main network finds blocks every 4 "-", thus the attacker has 33% of the network's hash rate. Number indicates total proof-of-work.
Code:
Attacker:
      |------2--3--------6-----------10-------12------15
      |     /    /    /    /    /   /     /    /    /
      |----1----2----3----4----5----6----7----8----9
Main:
With conflicts resulting in unusable blocks...

Code:
Attacker:
      |------2--3--------4-----------5--------6-------7
      |     /                  |(control regained)
      |----1----2----3----4----5----6----7----8----9
Main:
As you can see, in this example, the network regains control from the secret blockchain after 3 blocks (WITHOUT EVEN KNOWING ABOUT IT!), whereas if the only restriction for merging was having a longer chain at the time, the 33%er would likely keep secret control of the blockchain for quite a long time.

How will rewards be handled? Seems the most reasonable way is that only blocks on the main chain get generation rewards and transaction fees. This has the disadvantage that mining rewards will be less predictable because of the high orphan rate. Also might be an opening for denial-of-reward attacks.

I don't see a reason not to credit transaction fees. I talked about this on the OP of this thread:
That's a good point. One requirement of merging might be that the coinbase of the block that is doing the merge must also credit the same coinbase out scripts from the absorbed blocks with the transaction fees. The only problem with that, however, is what do you do about Eligius? You'd have to require that coinbases can only have one output.

You can't credit the whole block reward, because if the difficulty goes up, people would just mine off of older blocks and hope that they get merged. Orphan blocks MUST be practically worthless. That being said, when there is no more block reward, the same difficulty manipulation could be used to get just the transaction fees. Thus, we are left with two choices (both of which are good):
1) Require crediting transaction fees (doing this for the block reward would be a breaking change to the protocol that requires 100% of nodes to upgrade) to the absorbed block's miner if, and only if, the block was mined on the same or higher difficulty.
2) Don't credit anything. (works much better with the existing code)
To add to this, crediting the full block reward, assuming the difficulty is the same or higher and that the block would be taken into consideration when calculating the next difficulty, would be a GREAT idea for the next Bitcoin. Here's why: It successfully solves the problem of interplanetary mining. Think about that. The only issue remaining is to solve the double-spend issue with the lag, and I have some ideas in my head for that.
Unfortunately, this just made me think of a DANGEROUS exploit against my scheme. An attacker could store up orphan blocks that they mined in order to include them later in a conflicting chain. This can be mitigated by setting my X to a low number, say 2-6. (20-60 minutes worth of blocks on other chains)
HA! I'm stupid. The miners just need to "discourage" the blocks from the new chain internally long enough for somebody to make a new block that adds those newly released orphans. Then, the main network has full control again. In fact, clients don't need to even indicate that there's potentially an issue to the user if the orphan came out of nowhere, but before a chain split due to invalid blocks. It's only a temporary problem for anyone who happens to choose just then to sync up with the network, so we'd just have to tell people not to trust full clients that have just re-synchronized to the network.

Problem solved. X is back to whatever.
When a mining client receives a VALID, unused orphan block/blockchain that connects to the main chain somewhere in the last X blocks (where X is a number that I haven't really decided on),

What's the interest of having a X maximum block delay for merging? Wouldn't it be interesting to allow miners to intentionally branch blocks deep in the past for some reason, like spending an old output with an easier difficulty? I don't see any problems with that.
Originally it was to prevent block spam and to allow pruning, but as you see above, it's now more important than before.
Anyway, this now needs more of an explanation. After a certain number of blocks when you're at the point where you are completely confident that there will never be a chain split that reaches that far, the additional orphans are useless. Thus we can prune them. It would be best for the network if there was a hardcoded point where they would be outright rejected, but it doesn't matter. Your usecase is interesting, though. It would allow you to spend those coins without a transaction fee, since no miner would be stupid enough to reject your free additional proof-of-work out of fear that someone else would accept it and invalidate your block. However, I'm not sure that it's a usecase the should be supported.

Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 12, 2012, 08:31:22 PM
 #26

But the attacker can always overwrite everything, as he has >50%.

Say the attacker is freezing the trunk. An honest miner manages to branch it with a good block. Now the tree with the good block has a stronger proof-of-work, true.
But the attacker can double-spend anything that was on this branch in the trunk, as long as the original sender signs him a double-spend.
Damn, you're good. I was hoping nobody would discover that issue, since, although it can be countered, it makes the system less effective.

In the case of conflicting transactions, as I said in OP, you need to make a choice. I thought of giving priority to the trunk, it seems Maged prefers to say that a tree with conflicting transactions is entirely invalid. Either way the attacker is in advantage. In my suggestion he just overwrite the transaction. In Maged scenario, he inserts the double-spend in his tree which will not contain the honest branch. The honest tree will be temporarily stronger, but as soon as the attacker makes his trunk stronger than the honest tree (he has >50%), he'll completely invalidate the honest tree, and honest miners will not be able to rebuild on top of his work anymore, unless if they ignore the conflicting transaction.
Bingo! All it takes is one decent-size miner who, either through heuristics (guessing which tx-outs the attacker might control, and adding the new transaction(s) that was/were double-spent in the next attacker block to a temporary blacklist when they get it wrong, eventually causing the attacker to run out of outputs), or by taking random samples of unconfirmed transactions, ends up making a block that doesn't contain any transactions that the attacker is able to double-spend. At that point, the attacker has three options:

1) Give up.
2) Merge the block/build off of the block and let those transactions sneak into the chain.
3) Fight it and always be at a 1-block disadvantage requiring him to make 2 blocks for every honest block (until the honest nodes get lucky again, in which case he will need to make 3 blocks for every honest block, etc)

If the attacker chooses 1 or 3, the honest nodes win. If the attacker chooses option 2, the only thing they can do is delay transactions. If the network has a block target time of a few seconds, the delay caused by the attacker could very well be less than the time it normally takes for a single confirmation on the Bitcoin network.

Like I said, it can be countered, but it makes this system slightly less effective.

EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 12, 2012, 09:39:01 PM
 #27

Bingo! All it takes is one decent-size miner who, either through heuristics (guessing which tx-outs the attacker might control, and adding the new transaction(s) that was/were double-spent in the next attacker block to a temporary blacklist when they get it wrong, eventually causing the attacker to run out of outputs), or by taking random samples of unconfirmed transactions, ends up making a block that doesn't contain any transactions that the attacker is able to double-spend.

But the attacker doesn't need to control the addresses. The original sender of any of the transactions on the honest branch could create a double-spend and send it to the attacker. The attacker includes it in the trunk and rebuild the tree without the honest branches. He can rinse and repeat, theoretically for any transaction in the honest branch.

The result is that anything in an honest branch is potentially reversible.

3) Fight it and always be at a 1-block disadvantage requiring him to make 2 blocks for every honest block (until the honest nodes get lucky again, in which case he will need to make 3 blocks for every honest block, etc)

I think this would work better if instead of declaring that a blocktree (let's call it this way?) is entirely invalid due to conflicting transactions, you just give priority to what's in the trunk. Because by not allowing conflicts, the attacker can invalidate the proof-of-work of honest miners by inserting a single double-spend. By giving priority to what's on the trunk, at least the non-conflicting transactions remain, so the honest miners are indeed always ahead. (doesn't change the fact that their transactions may be reversed). EDIT: Doesn't work, and Maged already explained what's the danger.
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 12, 2012, 09:56:18 PM
 #28

NO! ABSOLUTELY NOT! There's a reason I made it that way in the mini-spec.

Big picture: A block that doesn't conflict with the chain is a vote for that chain. If something in the block DOES conflict, however, that's clearly a vote for another chain.

Possible exploit: A chain made in secret with double-spends could absorb blocks from the main chain, allowing an attacker to overtake the main chain with a mere fraction of the hashrate and a little luck.

OK, I should have read this with more attention (and your nice example after which helped me understanding it) before having made my post above.

You're right, the tree must be invalid if it contains conflicts. That would make things easier for an attacker trying to freeze the network though. One single double-spend is all he needs.
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 12, 2012, 10:53:18 PM
 #29

You're right, the tree must be invalid if it contains conflicts. That would make things easier for an attacker trying to freeze the network though. One single double-spend is all he needs.
Yes, but they can only possibly have a finite number of transactions that they can double-spend.
Bingo! All it takes is one decent-size miner who, either through heuristics (guessing which tx-outs the attacker might control, and adding the new transaction(s) that was/were double-spent in the next attacker block to a temporary blacklist when they get it wrong, eventually causing the attacker to run out of outputs), or by taking random samples of unconfirmed transactions, ends up making a block that doesn't contain any transactions that the attacker is able to double-spend.

But the attacker doesn't need to control the addresses. The original sender of any of the transactions on the honest branch could create a double-spend and send it to the attacker. The attacker includes it in the trunk and rebuild the tree without the honest branches. He can rinse and repeat, theoretically for any transaction in the honest branch.
Who would do that, though, when they know that as long as the chain is frozen, their coins are useless? But, you do bring up a good point. As long as an attacker controls the chain with 51%, any transaction that the attacker is able to get in the honest chain can cause all of the honest chain's work to be invalidated. For example, a transaction of his makes it into a honest block. The attacker makes people think that block was clean, and doesn't double-spend it right away. They later get lucky and find two more blocks that don't have any rouge transactions. The attacker can then double-spend the transaction from the first block, invalidating the entire chain of three blocks for the cost of exposing a single transaction.

So, would there be an issue with having otherwise valid blocks referencing additional parents considered as a valid proof-of-work if one or more of their additional parents are invalid? I'd have to think through that...

The result is that anything in an honest branch is potentially reversible.
Uhh.... Duh? That's always the case when someone has 51%. This does not solve that issue. All this system does is ensure that every "vote" gets counted.

EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 12, 2012, 11:29:02 PM
 #30

Who would do that, though, when they know that as long as the chain is frozen, their coins are useless?

If this counter-freezing system works for a while, those who manage to get things through would have an incentive to cheat. You spend your coins, get something in return because the chain is not really frozen, then you double-spend it.

So, would there be an issue with having otherwise valid blocks referencing additional parents considered as a valid proof-of-work if one or more of their additional parents are invalid? I'd have to think through that...

I hope there's no issue Smiley I can't think of any but it's too late and I'm not thinking straight anymore.

But, what if instead of linking the honest blocks with each other, they are just linked to those on the trunk, but every time you add one, you do it many blocks deep, so that the attacker can't cheaply rewrite the header of your parent?
That would clash with your X limit though as these never-merged branches would eventually be more than X blocks behind. I haven't yet processed the need for this limit, I will do it tomorrow.

The result is that anything in an honest branch is potentially reversible.
Uhh.... Duh? That's always the case when someone has 51%. This does not solve that issue. All this system does is ensure that every "vote" gets counted.

What do you mean by vote?

And, if no transaction can be trusted to be irreversible, than there's no point in any of this. Even with a normal, frozen blockchain, people could still deal only with unconfirmed transactions. We must find a way to make older transactions "deeper" and harder to overwrite.
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 13, 2012, 12:32:54 AM
 #31

So, would there be an issue with having otherwise valid blocks referencing additional parents considered as a valid proof-of-work if one or more of their additional parents are invalid? I'd have to think through that...
I thought about it. I couldn't think up any specific examples, but intuitively is just seems wrong. Just like a miner making a block is saying that they completely believe (or should I say, confirm...) that the block's parent is accurate, so should the additional parents. It says, "this block here wasn't wrong, either; it was just unlucky". Thus, the thing that miners should do in this situation is, until they believe that they have enough orphans stored up, don't have them link with the other orphans. Make them all have completely different transactions. Then, when you're ready to take back the chain, merge them all in a single block.

And, now that I click "post"...
But, what if instead of linking the honest blocks with each other, they are just linked to those on the trunk, but every time you add one, you do it many blocks deep, so that the attacker can't cheaply rewrite the header of your parent?
That would clash with your X limit though as these never-merged branches would eventually be more than X blocks behind. I haven't yet processed the need for this limit, I will do it tomorrow.
Smiley
I honestly haven't put much thought in the X limit. The main thing is to prevent spam blocks from being made at difficulty 1, so maybe instead of blocks, it could be based on the difficulty the block was originally made at. Maybe a combination of both. It might not even need to be handled at the protocol level. I don't know...

Who would do that, though, when they know that as long as the chain is frozen, their coins are useless?

If this counter-freezing system works for a while, those who manage to get things through would have an incentive to cheat. You spend your coins, get something in return because the chain is not really frozen, then you double-spend it.
That's a really good point that I never even thought about. However, thinking about it further, I think you're fine. In order to counter the freeze, you need a bunch of orphan blocks that the attacker REFUSES to merge into their chain. For the sake of example, let's say six. The second that a block is made that does the merge, the honest chain is 6 blocks ahead of the attacker. A double-spend on the attack chain is now completely ignored, since they are no longer the longest chain. This leaves the attacker with three options:

1) Merge enough of the orphans into your own chain so that you can catch up. This will still take out several transactions, true, but the ones that get merged would then be permanent. (Your own empty blocks ensure that!)
2) Give up and start trying to freeze the chain again at the new tip.
3) Wait to catch up, and then double-spend to invalidate the other chain.

Now, if you are up to speed with your Satoshi white paper reading, you'll notice how hard #3 is. This is literally the same thing as rewriting historical blocks. The further behind you are, the more time or hash power you'll need to catch up. Oh, and those orphan that were used to jumpstart the chain? They can be reused again if you do catch up. But, that shouldn't happen. What happens is the community makes it so that there are enough orphan blocks to cause you to take at least a few hours to catch up, and then they release an update to the client that hardcodes in a checkpoint to their chain. Oh, and by the way, if you continue despite that, since this would be a large reorganization at this point, you would just trigger safe mode on any client that doesn't upgrade immediately. You lose and have to start back over with option #2.


The result is that anything in an honest branch is potentially reversible.
Uhh.... Duh? That's always the case when someone has 51%. This does not solve that issue. All this system does is ensure that every "vote" gets counted.

What do you mean by vote?
Vote as in hash. The system would ensure that the legitimate chain doesn't lose apparent hashing power because of an orphan.

And, if no transaction can be trusted to be irreversible, than there's no point in any of this. Even with a normal, frozen blockchain, people could still deal only with unconfirmed transactions. We must find a way to make older transactions "deeper" and harder to overwrite.
Even with an attacker, transactions can still be irreversible. You just might have to wait longer (days) and depend on manual checkpoints.

EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 13, 2012, 09:05:06 AM
 #32

That's a really good point that I never even thought about. However, thinking about it further, I think you're fine. In order to counter the freeze, you need a bunch of orphan blocks that the attacker REFUSES to merge into their chain. For the sake of example, let's say six. The second that a block is made that does the merge, the honest chain is 6 blocks ahead of the attacker. A double-spend on the attack chain is now completely ignored, since they are no longer the longest chain. This leaves the attacker with three options:

1) Merge enough of the orphans into your own chain so that you can catch up. This will still take out several transactions, true, but the ones that get merged would then be permanent. (Your own empty blocks ensure that!)
2) Give up and start trying to freeze the chain again at the new tip.
3) Wait to catch up, and then double-spend to invalidate the other chain.

Now, if you are up to speed with your Satoshi white paper reading, you'll notice how hard #3 is. This is literally the same thing as rewriting historical blocks. The further behind you are, the more time or hash power you'll need to catch up. Oh, and those orphan that were used to jumpstart the chain? They can be reused again if you do catch up. But, that shouldn't happen. What happens is the community makes it so that there are enough orphan blocks to cause you to take at least a few hours to catch up, and then they release an update to the client that hardcodes in a checkpoint to their chain. Oh, and by the way, if you continue despite that, since this would be a large reorganization at this point, you would just trigger safe mode on any client that doesn't upgrade immediately. You lose and have to start back over with option #2.

That's really clever. I was blocking the ckeckpoints solution from my head for considering it a "centralized" solution, but it isn't too centralized. I mean, you only update to it if you have an interest in being able to keep using the chain. And no rogue developer would be able to easily create fake checkpoints. After all, it is a consensus, as the very use of bitcoin is a consensus. It is not a single point of failure since the developers of such checkpoints could easily be hidden in the dark corners of the cyberspace, unreachable by the attacker so they don't get their legs broken, and that poses no big trust issue as everybody with enough technical understanding can see what's going on. And plus, in the future, most people should be expected not to be running actual p2p clients, those will be for the experts, which would understand what's going on in an attack situation, I hope.

"Safe mode" was also something interesting. Had never read this expression before around here. It is true, a client could generate some sort of alerts if it sees deep reorgs. That's always suspicious.

But for this to work well, I find it really important that the attacker is not able to destroy the entire honest effort by finding a single double-spend. It sounds too risky. True, honest miners could add some trust on their decisions, like only including transactions of famous eWallets or reputable "bitcoin servers" that would not double-spend. But still. One jerk with a transaction deep behind in the honest branch and we're screwed. Seeing what happened with that OP_EVAL alt chain, we can conclude the supply of jerks is really huge.
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 13, 2012, 10:28:32 AM
 #33

Thus, the thing that miners should do in this situation is, until they believe that they have enough orphans stored up, don't have them link with the other orphans. Make them all have completely different transactions. Then, when you're ready to take back the chain, merge them all in a single block.

That's what I meant yesterday. The link should be done with several blocks deep behind though, otherwise the attacker can just rewrite the headers and breaks the link.
And the X merge limit would have to be really big for this to be feasible.

I don't know, I feel uneasy with "arbitrary constants" like this in a protocol. It is like that block size limit thing in bitcoin, always provoking some discussion.
It is true that spamming would be cheaper if you have coins deep behind when the difficulty was very low. Botnets could use this to kind of DDoS the network.

I've seen people proposing the idea of "soft limits" for the block size. The idea is that, instead of a hard limit that cannot be broken no matter what, miners choose their own "soft limits". For each soft limit, there's a "give up" limit as well. Suppose you receive a block which is larger than a soft limit of yours. You refuse to build on top of it. But if others keep building on top of that block and the total PoW of the chain with the large block is higher than yours by a value greater than your "give up limit" linked to that "soft size limit" broken by the big block, then you accept to include the large block anyway, as you don't want to fork the chain either. You could have multiple pairs of "soft limits" and "give up limits". And, yes, at the end you could add a true hard limit, but really huge.

Couldn't the same idea be applied to this merge distance limit? And in this case, maybe the limits could automatically increase when you detect an attack is ongoing.
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 13, 2012, 10:54:53 AM
 #34

By the way, I was rethinking about your explanation on why does a tree with any conflicting transaction must be deemed entirely invalid instead of setting a priority to pick a correct transaction version.

If I understood correctly, the danger is only to add the PoW of the conflicting block to the tree total, isn't it? What if we ignore the PoW of this block but we keep everything which is not conflicting, namely, the links to other blocks and the good transactions?
Doesn't the fact that the conflicting block has a PoW nevertheless allows us to see that some valid work was done, and thus we are safe to preserve what can be preserved?

Does this allow an attacker to overtake the network more easily?
I can't see how, but I had not seen the exploit you saw either, so I rather ask... Smiley
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 13, 2012, 06:25:30 PM
 #35

Thus, the thing that miners should do in this situation is, until they believe that they have enough orphans stored up, don't have them link with the other orphans. Make them all have completely different transactions. Then, when you're ready to take back the chain, merge them all in a single block.

That's what I meant yesterday. The link should be done with several blocks deep behind though, otherwise the attacker can just rewrite the headers and breaks the link.
Great! If they do that, they just screwed themselves. They can't "rewrite the headers", since the block was already released. All the can do is replace the block. And do you know what that means? They just made another valid orphan. Valid orphans can be merged.

And the X merge limit would have to be really big for this to be feasible.

I don't know, I feel uneasy with "arbitrary constants" like this in a protocol. It is like that block size limit thing in bitcoin, always provoking some discussion.
It is true that spamming would be cheaper if you have coins deep behind when the difficulty was very low. Botnets could use this to kind of DDoS the network.
You see the dilemma. I am honestly not very good at picking magic constants. I'll leave that to someone who knows more math than me.

I've seen people proposing the idea of "soft limits" for the block size. The idea is that, instead of a hard limit that cannot be broken no matter what, miners choose their own "soft limits". For each soft limit, there's a "give up" limit as well. Suppose you receive a block which is larger than a soft limit of yours. You refuse to build on top of it. But if others keep building on top of that block and the total PoW of the chain with the large block is higher than yours by a value greater than your "give up limit" linked to that "soft size limit" broken by the big block, then you accept to include the large block anyway, as you don't want to fork the chain either. You could have multiple pairs of "soft limits" and "give up limits". And, yes, at the end you could add a true hard limit, but really huge.

Couldn't the same idea be applied to this merge distance limit? And in this case, maybe the limits could automatically increase when you detect an attack is ongoing.
I wish that we could apply that, but unlike Bitcoin, if we assume a new currency that grants full rewards for orphans (once they are merged), there's no downside for the side that wants the merge. If someone wants to merge difficulty 1 blocks, they can just keep on trying until the people stopping them give up. And they would have to give up. Just like how this prevents a blockchain freeze, it also prevents miners from not acknowledging valid blocks.

Even if we assume that people don't get paid for orphans, an attacker trying to spam the chain could do the same thing. Eventually, you end up having so many uncollected orphans that the main chain is forced to give in and merge them, at the risk of an attacker taking advantage of the orphans and double-spending.

Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 13, 2012, 06:30:12 PM
 #36

By the way, I was rethinking about your explanation on why does a tree with any conflicting transaction must be deemed entirely invalid instead of setting a priority to pick a correct transaction version.

If I understood correctly, the danger is only to add the PoW of the conflicting block to the tree total, isn't it? What if we ignore the PoW of this block but we keep everything which is not conflicting, namely, the links to other blocks and the good transactions?
Doesn't the fact that the conflicting block has a PoW nevertheless allows us to see that some valid work was done, and thus we are safe to preserve what can be preserved?

Does this allow an attacker to overtake the network more easily?
I can't see how, but I had not seen the exploit you saw either, so I rather ask... Smiley
If you ignore the Proof-of-work, all you end up with are the transactions. In a reorganization in Bitcoin, transactions from the other chain are already added to the memory pool of each client to be worked on for the next block. All this would do is acknowledge the parent that the transactions came from, but that's totally unnecessary.

EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 13, 2012, 09:18:15 PM
 #37

Great! If they do that, they just screwed themselves. They can't "rewrite the headers", since the block was already released. All the can do is replace the block. And do you know what that means? They just made another valid orphan. Valid orphans can be merged.

hehehe, true, I haven't thought that, we could use his block again in the honest branch just to reuse his PoW. Resistance is futile. Cheesy

I wish that we could apply that, but unlike Bitcoin, if we assume a new currency that grants full rewards for orphans (once they are merged), there's no downside for the side that wants the merge. If someone wants to merge difficulty 1 blocks, they can just keep on trying until the people stopping them give up. And they would have to give up. Just like how this prevents a blockchain freeze, it also prevents miners from not acknowledging valid blocks.

Even if we assume that people don't get paid for orphans, an attacker trying to spam the chain could do the same thing. Eventually, you end up having so many uncollected orphans that the main chain is forced to give in and merge them, at the risk of an attacker taking advantage of the orphans and double-spending.

You're right. Damn.

What if instead of a block limit like that, we try to use the difficulty level somehow?
If there's no inflationary reward for branches, then there's not a strong economic incentive to mine them on purpose. Hardly someone would mine on, say, half or more of the current difficulty just for spamming. It would be a big waste just for spamming, even for botnets.

True, the % limit is still an arbitrary constant, but it sounds a bit more "adaptive" than the number of blocks.
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 13, 2012, 09:35:44 PM
 #38

If you ignore the Proof-of-work, all you end up with are the transactions. In a reorganization in Bitcoin, transactions from the other chain are already added to the memory pool of each client to be worked on for the next block. All this would do is acknowledge the parent that the transactions came from, but that's totally unnecessary.

Well, actually, the main reason I wanted to preserve the block is not to lose everything with a single double-spend, as we've discussed above. We probably either have to preserve the block links, or make it possible to merge branches which are many blocks behind (like, several days behind, perhaps even some weeks behind).
I think this is critical, otherwise the risk of losing the honest effort is considerable. Don't you think so?
Maged
Legendary
*
Offline Offline

Activity: 1260


View Profile
January 13, 2012, 11:23:52 PM
 #39

What if instead of a block limit like that, we try to use the difficulty level somehow?
If there's no inflationary reward for branches, then there's not a strong economic incentive to mine them on purpose. Hardly someone would mine on, say, half or more of the current difficulty just for spamming. It would be a big waste just for spamming, even for botnets.

True, the % limit is still an arbitrary constant, but it sounds a bit more "adaptive" than the number of blocks.
That's along the lines of what I was thinking.

If you ignore the Proof-of-work, all you end up with are the transactions. In a reorganization in Bitcoin, transactions from the other chain are already added to the memory pool of each client to be worked on for the next block. All this would do is acknowledge the parent that the transactions came from, but that's totally unnecessary.

Well, actually, the main reason I wanted to preserve the block is not to lose everything with a single double-spend, as we've discussed above. We probably either have to preserve the block links, or make it possible to merge branches which are many blocks behind (like, several days behind, perhaps even some weeks behind).
I think this is critical, otherwise the risk of losing the honest effort is considerable. Don't you think so?
If you aren't preserving the proof-of-work, then what are you preserving?


I also just realized something. This chain-strengthening system is a little too powerful, and it took that example about "soft limits" for me to see it. Anything that can be "gracefully upgraded" today on Bitcoin by making the blockchain more restrictive in some way would be consumed by this, causing a chain fork. The people who upgrade would be fine, but the people who don't - miners and users alike - could be easily scammed because the upgraded chain is mergeable to them, but the reverse isn't true. They'll always have the longer chain.

You can't build heuristics to detect whether there was a protocol upgrade because the attacker could just make their chain appear to do exactly what the heuristics require. Thus, we're forced into the trust model. If we want the network to be upgradable, we'd have to allow certain people to hold a kill switch (it'd likely be something that several pre-defined trusted people would have to sign) that would revert the old clients back to the old rules for calculating total PoW. Luckily, when you really think about it, even if someone fires off this kill switch with malicious intent, they'd still require over 50% of the network's hashing power to cause any damage.

EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 616



View Profile
January 14, 2012, 12:20:28 AM
 #40

If you aren't preserving the proof-of-work, then what are you preserving?

I was just saying that either we preserve conflicting blocks like this:

So, would there be an issue with having otherwise valid blocks referencing additional parents considered as a valid proof-of-work if one or more of their additional parents are invalid? I'd have to think through that...

Or we don't link them like this:

Thus, the thing that miners should do in this situation is, until they believe that they have enough orphans stored up, don't have them link with the other orphans. Make them all have completely different transactions. Then, when you're ready to take back the chain, merge them all in a single block.

But for the latter to be possible, miners would need to be able to keep unmerged blocks days/weeks behind in the chain.

I also just realized something. This chain-strengthening system is a little too powerful, and it took that example about "soft limits" for me to see it. Anything that can be "gracefully upgraded" today on Bitcoin by making the blockchain more restrictive in some way would be consumed by this, causing a chain fork. The people who upgrade would be fine, but the people who don't - miners and users alike - could be easily scammed because the upgraded chain is mergeable to them, but the reverse isn't true. They'll always have the longer chain.

That's true. But, is it really that big of a problem? Have such protocol restrictions been made so far?

I think I'd trade the benefit of not "fearing" a chain freeze over this restriction... That's actually the only >50% attack I think we should worry about, the for-profit double-spend isn't nearly as dangerous.

Thus, we're forced into the trust model. If we want the network to be upgradable, we'd have to allow certain people to hold a kill switch (it'd likely be something that several pre-defined trusted people would have to sign) that would revert the old clients back to the old rules for calculating total PoW. Luckily, when you really think about it, even if someone fires off this kill switch with malicious intent, they'd still require over 50% of the network's hashing power to cause any damage.

No, that sounds bad... even if it isn't dangerous, I don't think it would be received well.

I don't think it is such of a drawback to have every "chain rules change" being a backward incompatible change (specially when you compare with the potential benefits of what's being discussed here). These changes would need to be scheduled months in advance, intensively communicated to the main pool operators, developers of p2p pools etc.
Such a thing will inevitably have to happen for the block size limit one day anyway. We should be prepared for more backward incompatible changes, if they are really needed.
Pages: « 1 [2] 3 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!