Topic: Unfreezable blockchain - page 2. (Read 5030 times)

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.

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.

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.

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.

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.

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.

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.

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

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?

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

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.

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.

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

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

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.

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)

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

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.

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.