Bitcoin Forum

An interesting technical idea has came out on the discussion about the alt chain recently attacked by the Eligius pool.

Probably the idea is not feasible, since otherwise Satoshi would have think of it since the beginning.  :D
But maybe we should discuss it more. Who knows...

This is the post that presented it: https://bitcointalk.org/index.php?topic=56675.msg684088#msg684088

Summarizing, the idea is that we could eliminate the risk of the network being frozen by an attacker by considering shorter chain forks as partially valid blocks as well.

This obviously immediately raises many issues.

First issue, conflicting transactions. Different forks may contain incompatible transactions. A simple solution would be, in case such thing happens, to only consider the conflicting transactions that are on the larger chain. Only non-conflicting transactions of the smaller fork would be recognized as valid. That might solve the conflict issue, but it leaves open another.

Spamming. An attacker wanting to freeze the chain could still send tons of transactions-to-self to honest miners, and then double-spend them all on his longer chain. He achieves the same goal. The only way I see to counter-attack this is by making him pay for the transactions he inserts on the smaller fork as well, by taking their fees, while not crediting the outputs. But then, as the inputs which are paying the fees on the smaller chain also are being fully spent on the larger chain, this is impossible. Unless, perhaps, if we change what was defined above and treat every conflicting transaction as invalid. But then, there are at least two other problems that I can think of:

Reversible transactions: Although freezing the network is not possible anymore, now miners can reverse transactions. This is obviously not desired. A possible solution would be to get severe and consider double-spent coins as sent to /dev/null. The double-spender loses his coins, and no outputs are credited. Discourages double-spends, but we're not over...

Invalidation of a chain of transactions: How to prevent a miner to generate a short chain fork which creates a double-spend with the sole intend of canceling a transaction and all the transactions that follow? I don't have an answer for this one. Unless if we keep the original solution that considers the conflicting transaction of the larger chain as valid, but then some other solution should be found to the spamming problem...

Still one more... inflation. If the coin has inflation in its block reward, then it becomes to easy to Zimbabwelize it, as shorter forks could be produced on tons. That could be solved by making the inflationary reward of shorter-forks not applicable, only the fees get credited to the generation address.

Well, these are the problems I could find, and some solutions I could quickly think of. I think there are more problems, and I'm not very confident that all of them can be solved. But as there are many intelligent people on these forums, I wonder if any of them can elaborate on this idea. If we could find a way to build a chain which is immune against "freezing attacks", that would be great.

Please keep in mind that someone with >50% would still be able to double-spend. Protecting from this kind of attack is not the goal here.

There is already a solution: move to P2Pool ;)

While not providing definitive answers, this post explores similar issues (penalizing double spends), maybe my posts there can help you come to some new ideas. (https://bitcointalk.org/index.php?topic=54746.0)

That's interesting, but it is a different problem I think. There it seems you want to have a way to penalize double-spends done on the same chain. An interesting idea to be discussed. But here, the problem is how to

• Consider shorter-forks (have a "blocktree" instead of a "blockchain")
• Eliminate conflicting transactions
• Prevent the attacker from doing the freezing by spamming with conflicting transactions

I thought of multiple things last night, but it's hard to come out with a good solution. If we send conflicting coins to /dev/null, that gives miners the power to invalidate big transaction chains. Maybe we could say that a blockchain which contains a transaction T2 in a block N2 which spends outputs credited by a conflicting transaction T1 in block N1 where N1 + C < N2, is invalid. This would make it so that once a transaction has all its inputs credited more than C blocks deep, it cannot be reversed anymore. But then, what's to stop the attacker to create a longer chain with this configuration which does not have the legit short-fork? How would you decide which is the good tree?

It seems to me that we cannot penalize conflicting transactions like this. The longer chain must always be entirely valid. Only the shorter forks may contain transactions to be ignored. The spamming problem should be dealt some other way, maybe with heuristics? Honest miners have an interest in not including the conflicting transactions sent by the attacker, since they'll not be able to collect fees on them. If they could identify these transactions somehow they could simply ignore them. And it's probably possible to do some good guesses, as the attacker cannot double-spend money he never owned. Once an honest miner detects a freezing attack is going on, he could start tracing every coin used on conflicting transactions and refuse to include them on his blocks. Additional techniques like tracking and blocking the IPs of the attacker, decreasing the priority of nodes which send to many transactions, decreasing the priority of tiny inputs (as the attacker could have prepared millions of them before the attack) etc, may also help. But of course heuristics are never fail-safe. The important thing is to make sure they are not arbitrarily bad.


Anybody has anything to add? I'm probably missing something, but I can't see it now on my own...

Yeah, I was missing a big problem with this blocktree idea.

You can't really know which tree is the correct one. Actually you can't be sure you have the entire tree, there could be a branch that just wasn't sent to you. For honest splits that could be easy to solve, by treating it like version control systems, with merge points. The larger chain is the "trunk" and the others are branches leave the trunk at a certain point but merge back into it after. The merge point would be in the header so there's no way to miss it.
But for a tree under attack - what's precisely what we want to cover - you wouldn't have the honest blocks being merged into the trunk.

That makes every transaction on shorter, non merged branches potentially reversible if the sender of the transaction colludes with the attacker. Actually no organized cooperation is needed. The attacker would gladly include double-spends of shorter forks which haven't been merged just to make his attack more destructive.

I'm stuck. Can't find a solution to that one.

A solution already exists.

Increase hashing power of network so an attack is not viable.
Use methods like p2pool which remove control of hashing power from a small number of individuals.

Yeah, right, "easy" solution.  :)
And authoritarian governments like the Chinese or even USA could outcome that, I guess. Particularly if they collude. Actually, "freezing the chain" is the only >50% threat that we should worry about. For-profit double-spends are indeed not likely.

Not to mention that if we manage to have a chain which is more secure by design, then less processing power could be spent on its maintenance. It would be a cheaper, more efficient system.

But yeah, so far I can't think of a way to do it. Maybe it's just impossible.

The easiest way I would think to build a chain that's resistant to attack is to go and set up your own node that works exactly the way you want it to, and persistently tell people you did so.

Nobody will care... until an attack occurs.

Then during the mayhem, you simply say: "I've already got this figured out, I'm still running with the valid chain and am ignoring/censoring the attack chains.".  Invite people to connect directly to your node with the -connect parameter, which causes them to connect to you and nobody else.  Have them refuse incoming connections.  Hopefully, their client will see the block chain the same way you do.

Nobody will be happy about a centralized node, but it will sure be a whole lot better than everyone sitting on their hands adrift!  Meanwhile, somebody will figure something out to get everybody back in business without needing a centralized node.

That's what I'm trying to figure out here, but I can't yet be sure if it's even possible.

Just so it's clear what I'm responding to...
Dear God. You may have just solved the latency problem. By the latency problem, I'm talking about the fact that an attacker can generate blocks on a low-latency network without orphans, whereas the main network is more likely to have orphans. If this problem is solved, there would no longer be as much risk in lowering the target block generation time to a few seconds. Think about the implications of that for a second. The Finney attack would become almost useless, since you could no longer hold onto a pre-generated block while you spend coins elsewhere. A smart person would still wait for 60 minutes worth of confirmations, but it would definitely reduce the risk of accepting transactions quickly.

Here's a quick spec. Interestingly enough, it would be possible to merge it with Bitcoin as a recommendation for clients by replacing certain MUSTs with SHOULDs. However, it would be most effective on alt-chains.

---

Definitions:
VALID -  means that the orphan would have passed all block/transaction validation checks at the point where it would have ended up in the chain. The orphan MUST be from a chain that, when you add the orphan, has a lower total proof-of-work than the current chain. Additionally, to prevent an attacker from using this against the main chain, the transactions in the orphan chain (ignoring coinbases, which are discarded) MUST NOT conflict with the current chain.

To start, this spec only affects a blockchain's total proof-of-work. All other blockchain rules remain in effect.

Assumption: all VALID orphans would have increased the total proof-of-work of the main chain if the network had zero latency.

A block would be redefined to allow additional parents. However, there will still be a main parent, just like today. In Bitcoin, this could be added to the coinbase instead of making a new field in the header. (I wonder if the merged-mining format could help here...)

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), they SHOULD add that orphan as an additional parent to the current block they are working on. Additionally, they MUST(/SHOULD) add all transactions that haven't been confirmed yet to the current block.

When a client receives a block with an additional parent, it checks that the additional parent is VALID and connects to the main chain somewhere in the last X blocks. If the additional parent doesn't connect directly to the main chain, the client MUST recursively lookup that orphan's main parent until it finds a block that has either already been merged with the current chain or was part of the current chain. From there, the orphan chain's proof-of-work is added to the current chain. Any additional parents included in the orphan chain are then also processed in the same manner.

---

This is most definitely more complicated than it's worth for Bitcoin, but it might be useful for an alt-chain. 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.

Also, there's a neat side-effect if you require a merge to also include the unconfirmed transactions from the merged chain: an attacker making empty blocks, and thus refusing to do a merge, would be beaten every time a real block is released by an ever-increasing amount of work.

Example: (number indicates total proof-of-work)

Maged, could explain more what's this latency problem or link me to an explanation?

By the way, when you say orphan, I believe you mean childless, right? By definition, the only orphan block is the genesis block, all the others have a block that preceded them.

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 disagree, the branch selection rules will have to be changed at some point (could be 5 or 10 years from now), Bitcoin will not be secure against attack in the long term with the current rules. I think a combination of cementing with proof-of-stake will solve double spending, this suggestion can potentially solve the remaining problem of denial of service (as well as allow shorter block times, which allow quicker confirmation and improve mining variance).

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.


If the time between blocks is too short, communication latency between nodes will cause many orphan blocks, so the honest network will waste some portion of their hashrate. Meanwhile, an attacker will run on a localized low-latency network, thus have an advantage and it will be easier to attack with a given hashrate.

Maybe the terminology is confusing but "orphan block" generally refers to one which is not on the main chain.

If I understood well, the attack is an exploit of the fact that during a split, the strength of the network as a whole is reduced to the strength of the stronger subset of miners. With very short delays between blocks, splits would happen all the time thus the strength of the network would be most of the time smaller than the total processing power of all miners.

Is that it?


Indeed doesn't make sense. Does the "terminology" also says that a recent block is the parent of the one coming before it or just the meaning of orphan that was "switched"?

I don't see a reason not to credit transaction fees. I talked about this on the OP of this thread:

I thought a bit more about this, and actually, if the attacker really behaves this way, it can be used against him.

Say you want to buy something, and the network is under attack. Your transaction goes to a branch which is not the trunk ("orphan"). As this branch is not merged, your transaction is still reversible, and the receiver knows it. He could provide you another address, and you double-spend the transaction to this other address of the same owner. If the attacker is indeed including double-spends just for the fun of it, he'll end up including your double-spend which in the case is a legit transaction to the person that should receive the money.

So I predict the attacker would not do such a thing. But the simple fact that he may include a double-spend, makes every transaction on branches not merged to the trunk potentially reversible. It's like only having unconfirmed transactions. So it is pretty much the same thing that would happen right now during a freezing attack.

How short of a time are we talking before it becomes an issue?  Would more nodes and more 'trusted' super nodes help avoid some of the latency?

At the risk of possibly being considered more 'centralized', could we not afford more paramaters for the blocks that could stop some of the bullshit? Is there a reason why blocks/solutions are even accepted that include zero transactions? I'd think having atleast a n% minimum of outstanding transactions should be a requirement for blocks to be paid out. Maybe still accept them but stop the bitcoin generation if less than n% outstanding transactions or give partial generation according to the blocks included n% of available transactions.

And is there a technical reason why blocks reported more than a few minutes after they were solved are not dropped completely? Have the nodes strip and rebroadcast any included transactions. Ideally, make sure the nodes do not 'forget' transactions until they are sucessfully written to an accepted block, rebroadcasting transactions every x seconds until they are included. So as to avoid someone solving, filling with transactions, and then purposly hoding until denied to try and delay the transactions.

I can think of a lot more, but with almost zero knowledge of the coding aspect of the nodes and Bitcoin in general I realize my ideas are probably pretty fuggin stupid.

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.


Just to be sure I get this right, by parent you actually mean a leaf on the tree, right?


This "neat side-effect" is precisely the point of this topic. :)

But it's not that simple. As I said on the other posts above, we cannot consider transactions on branches which are not the trunk as confirmed, because they can be reversed on the trunk, which is under the control of the attacker. And the attacker would never accept to merge branches back to the trunk.

Maybe if we only consider the branch proof-of-work in the total if it is merged into the trunk?
That would allow any honest miner that finds a leaf to the trunk to force the merge as it would have a stronger proof-of-work (that of the tree the attacker has built so far + the honest branch). But then, the attacker still has >50%, he could overrun the tree by one without the honest branches and a longer trunk. The honest miners would try to force the merge again, the attacker would overrun it again, and so on. An infinite loop of "reorgs" (that's the term when one chain is overridden, right?). The honest transactions would oscilate from confirmed to unconfirmed constantly, and during the unconfirmed periods an opportunist could insert a double-spend on the trunk.

Still doesn't solve the problem, but I feel you're getting closer...

An attacker could easily fill a block with fake transactions.


If you just started, or has been disconnected for a while, how do you know when a block was reported?

Yes.  Bitcoin is designed to survive even w/ nodes leaving at random, network disruptions, even subnets being isolated and reconnected.

Say I have a node, you have a node.
You go offline.

A block comes it.  I verify it as valid.

You come online.
You receive the block x minutes late and determine it is invalid.

You just forked the network.  There is an irreconcilable split in what different parts of the network consider valid blocks.  Now that is just a system example imagine all the complexities of nodes all over the globe, internet disruptions, intentional DDOS attacks, etc.  Now you could use some kind of consensus system between nodes where they vote and agree w/ the majority but you significantly weaken the 51% protection.  Now w/ 51% of the nodes the attacker has some interesting attack vectors. 

A side note you just created an ECONOMIC INCENTIVE to disrupt the network.  Say I am a medium sized mining pool but I want to get bigger and deepbit is keeping me down.  Well if blocks can be invalidated because they are "old" I have multiple options.  I could pay people to NOT forward and discard blocks from deepbit and kill their hashing power.  I could also spam the network w/ massive number of nodes which "cheat" and always vote "invalid" on competitors blocks.  Now obviously every other pool will do that and maybe even form "alliances" but you can imagine the utter chaos that would cause to the network.

Sure you could use something like a trusted time server and include that in a digital signature of the block but now you have introduced a reliance on a trusted third party.

Satoshi never said his system was "best".  His system satifies the requirement of not needing to trust ANY third party (no matter how trustworthy they may be).

The attacker is not in control of the trunk. If the attacker tries to build his own branch without referencing the honest blocks, he will be beat by the honest network which references both honest blocks and the attacker's blocks.

And, you can make a rule that non-conflicting transactions from parallel parent blocks must be included as I described above, so the attacker can't absorb the honest node's PoW without including their transactions.

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.

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.

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)
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)
Originally it was to prevent block spam and to allow pruning, but as you see above, it's now more important than before.

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.
With conflicts resulting in unusable blocks...

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.

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.
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.
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.

Damn, you're good. I was hoping nobody would discover that issue, since, although it can be countered, it makes the system less effective.

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.

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.


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.

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.

Yes, but they can only possibly have a finite number of transactions that they can double-spend.
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...

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.

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.


I hope there's no issue :) 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.


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.

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"...
:)
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...

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.


Vote as in hash. The system would ensure that the legitimate chain doesn't lose apparent hashing power because of an orphan.

Even with an attacker, transactions can still be irreversible. You just might have to wait longer (days) and depend on manual checkpoints.

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.

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.

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... :)

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.

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 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.

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.

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. :D


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.

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?

That's along the lines of what I was thinking.

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.

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


Or we don't link them like this:


But for the latter to be possible, miners would need to be able to keep unmerged blocks days/weeks behind in the 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.


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.

Sorry, I'm still not understanding this. Even if I did, I fear that it'd make my head hurt...

That's really the big philosophical question, isn't it? There's no right answer to it.

I know, but I can't think of any other way to do it...

Would your opinion about this change if I were to tell you that this very change that we're describing is, itself, one of those backwards compatible changes? It could be implemented in Bitcoin today with just 50% miner support. Do we want to force such innovation to wait until the next backward incompatible change?
Which is a blessing and a curse. On the plus side, Satoshi left us the perfect reason to go back and fix our mistakes. If PayToScriptHash ends up being something we regret, we can undo it then.

On the downside, we will wait as long as possible before we do such changes. You need to have a VERY, VERY good reason to do a backward incompatible change. The system in this very thread would not qualify if it required that. Also, did you know that Bitcoin calculates the next difficulty level incorrectly, and that it can be exploited to reduce the difficulty? Did you also know that it isn't scheduled to be fixed until we hit the block size limit? That's why I consider this to be a difficult issue.

We really only have two logical choices here:
1) We shelve this idea for at least 20 years so that Bitcoin can finish maturing.
2) We add a kill switch that allows the network the benefit of this additional protection, but without the downside of making everything a backwards incompatible change. If necessary, the kill switch itself could have a permanent kill switch that requires fewer people to activate.

Well, it'd require a few hacks to be backward compatible, wouldn't it? You'd need to use transactions somehow to express the links between blocks, instead of the header themselves... And miners which do not update would not know how to identify and react to the attack, they would not recognize the strong PoW of the tree in comparison to the attacker's chain etc. It would be complicated and messy.

I wasn't hoping such change to be done in bitcoin in a backward compatible way, actually.


I didn't know about this. How serious is this bug? Would a serious deviation from the correct value be possible?


May I add a third?
3) "We"* try to make an alternative coin which implements this from scratch (links on the header, clean), and with it we may even test other things like fast confirmations for example. We make this alt coin support merged mining. We tell Luke-Jr about the new coin, and see how well it resists his attack. If it survives, it will be living proof that this works, and that cryptocurrencies need no more to fear the "freezing attack". From this point on, bitcoin developers may or may not add the technique to bitcoin. I'm sure that if such an attack ever happens on bitcoin, and there's an alt coin out there which has proven to be immune against it, then people would react quite quickly to adapt bitcoin to this scheme. Actually, I'd expect "emergency patches" to be already written and tested, only waiting to be included.

* I quoted "We" because I don't believe I'm qualified for the task.

It would be no more of a hack than merged mining. The data could be stored in the coinbase.

Not too serious. Someone can just make the 2016 blocks appear to have taken up to two hours less than they actually did.

Oh, I fully intended this to be used by an alt coin, at least at first. It'd be cooler if it could be added to Bitcoin someday, though, especially when we have a colony on Mars. That's what I feel is the real endgame for this proposal.

LOL, you don't need to get that "science-fiction" to imagine a good use case for this.
Imagine the Chinese government decides to get offensive against bitcoin. First, they would likely have the resources to try to freeze it. But even if they just use their great firewall, they could try to isolate Chinese miners from those outside. Granted, there will always be a few clever hackers able to get through, but if for a couple hours the great firewall cuts all links with the outside world, such a system could prove very useful to allow things to keep going on each side of the wall and then get everything merged whenever someone finds a hole.

Unless you can think of a good double-spend protection system for both sides of the split, that won't work. The only one that I can think of only works the following is true:

1) You know the maximum latency between you and the true tip of the chain.
2) (optional if you want faster transaction processing) You know which side of the chain "owns" each input.

Again, I haven't thought this through completely, so I'm not ready to publish it. But, that's the gist of how I'd solve the Mars problem.

True. I was imagining that, as nothing would pass through, that would be valid for transactions as well. But I naively forgot that the Chinese government itself could be the one sending the double-spends to both sides. Plus, the bitcoin protocol isn't the only way transactions can travel.