Topic: Unfreezable blockchain (Read 5089 times)

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.

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.

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.

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.

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.

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.

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.

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.

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?

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.


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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.