Unfreezable blockchain

[EhVedadoOAnonimato]

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

[HostFat]

There is already a solution: move to P2Pool

[Akemashite Omedetou]

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)

[EhVedadoOAnonimato]

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

[EhVedadoOAnonimato]

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.

[DeathAndTaxes]

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.

[EhVedadoOAnonimato]

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.

[casascius]

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.

[EhVedadoOAnonimato]

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.

[Maged]

Just so it's clear what I'm responding to...

Interestingly, it looks like there is actually a way of making coins immune from this particular attack that doesn't require any kind of trusted central authorities and can't be used to fork the blockchain. Unfortunately it'd be a huge pain to implement correctly and wouldn't be able to deal with 51% double-spending attacks.

The trick is that there's no inherent reason why the Bitcoin blockchain actually had to be in the form of a chain. Simply add a rule that blocks can merge multiple non-conflicting forks of the blockchain by having multiple parents, calculating its total work as the sum of its work and work done for all its ancestor blocks. That way, it doesn't matter that Eligius is mining faster than the rest of the network because we can use the attacker's work against him - our non-attack versions of the best chain are counted as having the strength of all his work plus all ours, and the only way he can benefit from this effect is if he includes other's blocks and transactions which is what we wanted in the first place!

There's almost certainly some subtle flaw in this and it'd be a nightmare to implement correctly and in a way that couldn't be exploited, but on paper it seems like a clever idea. Don't think I'm going to go through with it though. (There are a whole bunch of subtle details that have to be taken care of. For example, we need to cap how far back a fork that's being merged can come from to block spam, but this limits the power of this scheme against denial-of-service.)

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)

Code:

Attacker:     1----2----3----4----5
             / \    \    \    \    \
Main:       0   2----4----6----8----10

[EhVedadoOAnonimato]

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.

[Meni Rosenfeld]

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.

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.

This is most definitely more complicated than it's worth for Bitcoin

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

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.

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

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.

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.

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

[EhVedadoOAnonimato]

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.

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?

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.

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

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"?

[EhVedadoOAnonimato]

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:

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.

[EhVedadoOAnonimato]

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

[sadpandatech]

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

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.

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.

[EhVedadoOAnonimato]

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.

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.

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

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.

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

[EhVedadoOAnonimato]

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.

An attacker could easily fill a block with fake transactions.

And is there a technical reason why blocks reported more than a few minutes after they were solved are not dropped completely?

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

[DeathAndTaxes]

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.

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

[Meni Rosenfeld]

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.

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.