Topic: Miner advantage for empty blocks ? (Read 2038 times)

kjj's explanation is good.  Here are a few more details.

camem seems concerned that this attack will become easier as the difficulty increases, but that is not the case.  Let's assume you are trying to precompute a block that will occur at a specific future block number.  Suppose that at the future difficulty the first n bits of the 256-bit hash must be zero.  Then there are 2^(256-n) possible previous block hashes you must try to build on, and for each of them you must try 2^n hashes to find a block that meets the difficulty.  Therefore the total number of hashes required is 2^256, enough to thoroughly break SHA256.

If you don't care which specific future block number you are precomputing, you can try fewer previous block hashes and wait until you see one of those hashes, but because the timestamp only has a few hours of flexibility, the difficulty of the attack only improves to about 2^252.

Guessing the subsidy is not a big problem.  Guessing the nBits is harder (assuming you are precomputing a block after the next difficulty adjustment), but not as hard as you might think.  Because of inefficiencies in the compact representation used for the nBits, it only has about 16 bits of precision when the high byte of the hash target has a high bit of 1.  Assuming you can guess the difficulty within a factor of 256, the total difficulty of the attack becomes about 2^268.

Actually, the Merkle root is the easiest part.  All you need to do is never accept transactions into your block candidate and your Merkle root will always be valid, at least as long as the claimed subsidy isn't greater than the network's approved subsidy.

You can't create a future block because of the four things I listed earlier.

To generate a future block, you need to pick a random prevHash value to include in the header, and then wait until a real block comes in with an actual hash value that matches the one you picked.  Right now, each block has roughly a 1 in 2^203 of matching your chosen prevHash value.  By itself, this is much harder than merely finding a hash of the current block, which is about a 1 in 2^53 chance, and you still have to do that too.

Note: a 1 in 2^203 chance means never, ever, ever, not in billions of years, not before the sun burns out, not before the entire universe ends.  If "never" is good enough for you, you can stop reading right now, because it actually gets worse.

And then you need to guess when (to within a few hours) that block is going to come up, because you need to pick a timestamp before you start hashing, and you can't change it after.  So, 1 in 2^203 isn't bad enough, it also has to happen at the right time.

And then the subsidy you claim has to be less than or equal to the subsidy accepted by the network at that time.  If your timestamp is towards the end of a leap year, you'd better halve it, just to be safe.

But wait, there's more.  Your block header also must include the exact difficulty that the network expects when the block is to be accepted.  You can't cheat and go high, you have to get it exactly dead on.

Ok, I finally got it. Sure you can play tricks with the previous block hash, but you'll never get the right merkle root. The time stamp is tricky too, but the merkle root completely nails it. Nothing to see here, our mystery miner indeed does have lots of hashing power (and that satoshi chap thought of everything). Thanks for your corrections, will read more of the wiki next time...

You could, but no sane person would, because the cost of saving it would be hundreds of trillions of times greater than its potential utility.

Mining a block that will fit somewhere in the hash chain without knowing the previous block is about a billion, billion, billion times harder than mining a block knowing the hash of the previous block.

Sorry, this won't work, for four reasons:  Timestamp.  Difficulty.  Previous hash.  Subsidy.

You could, I just don't think it's feasible.  You could look for a new block using a prior hash of 0x000000000000000064, but that doesn't mean such a block would ever show up.  And even if it did show up, you'd somehow have to come up with enough processing power to find a hash that meets the same difficulty criteria (in other words, find a block with a hash of 0x00000000000000064 or lower), which with today's processing power, is all but impossible.

The previous transactions are only secured via the hash of the block they are included in.  In other words, if you find a no-transaction block hash that includes a hash for a potential previous block, you could theoretically save it for use in the future, if a future block hash happens to match up with the potential previous block hash you based it on.

Thinking about it more though, I don't see it being feasible.  The ending hash would still have to be below the difficulty level in the future, and you'd spend just as much time trying to find a hash for a future block that doesn't exist yet (and may never exist) instead of just trying for the current block anyway.  You could pick whatever prior block hash you wanted, sure, but that doesn't make it any easier to find a "next block" that meets the current difficulty standards.  And even then, you have no assurance that a block matching that prior block hash will ever show up anyway.

How can you start securing transactions now when you have no idea which transactions you need to secure? The whole point of mining is to pile calculations on top of the transactions. (And by "transactions" I mean every single transaction from the genesis block up to the ones in the block you're mining.)

if your first comment is right, I've misunderstood what difficulty is for...  On your second, sure you can add in previous real block chain hashes to your attack, but then you're reduced to very unlikely collisions. Why not look for some too, with your prior knowledge that the hashes will get smaller and smaller ?

I don't think you understand how difficult it would be to find any has below 0x00000000000000000000000064.  Go look through the blockchain, and find the lowest hash that has EVER been found.  It won't be anywhere close to 0x0000000000000000000000064, which tells you that it'll take more hashing power than has ever been used over the entire history of Bitcoin to find the hash for that one potential future hash.  And even if you find that one hash, there's no guarantee that the block before it will have such a hash.

EDIT:  I think a more interesting argument would be to generate a dictionary of valid no-transaction block hashes generated from prior hashes, and have each new prior block hash checked against said dictionary to see if it matches any of the already-generated no-transaction blocks.  If it does, then submit the new block.  I don't believe this to be feasible/economical with today's hardware, but maybe I am wrong.

But the difficulty keeps coming down, right ? So by 2021 there aren't very many input hashes you're going to be faced with ? let's say you know any possible remaining input hash is going to be under 0x00000000000000000000000000000064, just for instance ? I can spend more than 100 times longer than you can if I start now based on empty blocks and you wait for the real transactions ? Or do I get scuppered by the timestamp which I have to guess ? Or something else ?

You can't get it down to 100 or 1000 or 100000000. You'll have to do more than 1000000000000x more work, so the amount of time you have doesn't matter at all.

The block is a permenent record of tx.  If tx could be tacked on well that wouldn't make it very permenent would it.

The block header contains 6 elements one of which is the merkle root.
https://en.bitcoin.it/wiki/Block_hashing_algorithm

The merkle root hash is a hash of the tree contains all the tx of the block including the coinbase.

You don't "find" a block.  You find a hash of the block header which meets the difficulty target.   That hash is only good for that EXACT block header and set of block components  Change one bit of the blockheader and you have a completely different hash.

Since the blockheader contains the merkle root you can't change/add/remove any tx (not even one bit of one tx) without ending up with a different merkle tree and thus different merkle root and thus different block header and thus different hash.

If you could then mining wouldn't create a permanent record of anything.

No, and if you could, that would defeat the entire purpose of mining. The whole point of mining is to pile operations on top of the block chain up to and including the mined block in such a way that the proof of work is irrevocably associated with that block and all previous blocks. If there were any way to do the work without information from the entire block chain it proves, it wouldn't be proof anymore.

A miner is trying to do computations to "lock in" a block chain. He can't lock in a block chain until he knows what block chain he's trying to lock in.

Yes you would have more work, but you would also get more time than other people to do it in (you can start ahead of time). If you find a match now, with a timestamp in the future, you'll just be storing it for use in case that hash ever comes up. In fact, if you can find suitable 217 byte matches for each of the last 100 hashes (and you can start this now if you pick a good date), can't you just pull them out of the bag within seconds of each other in 2020 ?

However, I'm convinced by the argument that the bandwidth benefits of skipping transactions are worth it if you have a botnet, so perhaps I'm thinking too hard about the possibility of someone having a cheat rather than a botnet.  

On another note, do we know if the mystery miner just looks as if he does more empty blocks, because he has enormous hashing power so gets there before there are any transactions, and because the empty blocks are easier to spot ? (put another way, are there full tx blocks coming from the same IPs as he uses as well as empty blocks)

If the hashing didn't secure the transactions in the block, it would cease to serve any purpose. The whole point of mining is to pile computations on top of the transactions so that anyone who wanted to claim a different set of transactions for the block would have to do an equal amount of work as the rest of the network.

The block is a list of transactions.  All of the transactions are hashed together in a tree structure called a Merkle tree.  The root hash of that tree depends on the hashes of all of the transactions.  The block header includes that hash.

So, the work that miners do depends on the whole thing.  If you add a transaction, part of the Merkle tree will change, which means the root hash will be different, which means the hash won't match any more, and no one will accept your block as valid.

Also, if he were including transactions, no one would care, from the bitcoin point of view.

Can you tell me how tx are included into a "mined" block, and how this prevents them from being tacked on after a valid header is found? In other words, why can't he have the botnet work on mining headers and then tack on the txs at a single relay point rather than relaying the txs to every node in the network?

If there's some technical reason why this can't be done, it should be relatively easy to fork him out.

He isn't including transactions in the blocks because that would require access to the entire block chain, which is around a gig today, and growing.  By not including transactions, he only needs the hash of the current latest block, which is a couple dozen bytes.  The middle ground is to process the transactions at a central point that has the block chain, and then distribute them to the bots, but that is vastly more traffic, and to/from a central point, which makes it much easier to detect.

Suppose my some magic you could get the space of hashes for the last block down to 100. You'd have to do 100x as much work as everyone else.

But really you can't narrow the space in any meaningful way whatsoever. Not only do you not know the details of the inputs of the previous block, you don't know who will find it or where they will start looking in terms of nonce.

So the mystery miner seems quiet at the moment, nonetheless...

One of the elegant bits of bitcoin is that you can't start hashing a new block until you know the inputs, that is the new transactions you're going to have to hash, amongst other things.

If you decide to mine empty blocks, you take away one of the 'freshness' inputs that mean you can't work on the hash 'before time'. You are left with the hash of the previous block, and the time of your new block (am I right this is an input to your hash too ?) as things you're going to have to guess to get going early.

Normally the previous hash would be a large number, up to 256 bits, infeasible to exhaustively search while also searching for low hashes. However the bitcoin protocol also means that you know something about the previous hash, it meets the difficulty requirement, so your search space is reduced.

With a combination of choosing a time sufficiently far in the future and hashing with low input hashes only (changing the hash rather than the seed for instance), is there an advantage to be gained over other miners by trying to compute before the previous block is published ? Is this advantage increased if you wait until you have two valid hashes in a row before deciding to publish one ( if that's it, this should be easy to spot in the delay between mystery miner after someone else vs after himself) ? If there is an advantage does it increase as difficulty gets harder, making empty blocks trivial to find when difficulty is near the end ? You also have to gamble with the times, did the mystery miner blocks have odd time stamps ?

I'm sure you can set me straight, I have a nagging feeling that one exhaustive search is as hard as another in this case, at least until a long time in the future, so I should just accept that there's a lot of new hashing power, but if there's anything in this I would support moves to restrict empty blocks - this would comprehensively prevent such an attack