Topic: Are GPU's Satoshi's mistake? (Read 8213 times)

What if satoshi is a group of people?

I wonder if Satoshi will ever come out to the open.  Or is he already among us?

Satoshi knew about GPUs back in at least April of 2009, which was only a few months after launch. So for sure he knew about it before the system was designed.

That also shouldnt become a major issue, merely the current implementation scaling badly there.
To increment the extraNonce in the coinbase transaction, we rehash every transaction in the block and rebuild the whole merkle tree, so the whole thing ends up scaling with (blocksize * requestrate). Adding the obvious optimization of storing the opposite side for the merkle branch and only rehashing coinbase and its merkle branch, we need an additional (log2(#tx in block) * 32) bytes of memory but scale roughly with (log2(#tx in block) * requestrate) for getwork.
At something like a current average block (~10kB in ~20 transactions), that comes out to ~240 vs. 8 sha 256 operations for 4Ghps worth of work.
Scaling to visa-level 10 kTX/sec (that'd be 3GB blocks containing ~6M transactions ...), it's ... about 50 sha256 operations for 4Ghps worth of work.
So for a pool roughly the size of the current network that'd be... for current tx volume 24k sha256/sec vs 150k sha256/sec for 10k tx/s.
And using something like "miners increment block time themselves", this can be cut down by another factor of 60.
Scaling this for increasing hashrates due to Moore's law... well... that applies to both sides.
So for the getwork+PoW side, I just don't see any hard issues coming up.
I expect to see way bigger problems on the transaction handling side of things scaling to such massive levels, assuming every tx has 2 inputs + outputs on average, you'd be verifying about 20k ECDSA sigs/second and on every block you're marking ~12M outputs as spent and storing ~12M new outputs in some kind of transactional fashion, probably just the list of current unspent outputs would be on the order of 10s of GB ... ugh.

Satoshi used google servers and Suupah Komputahz! chi chang!

Satoshi understands probability so he clearly expected pools to emerge. It's likely though he didn't think they need any special consideration in the design.

Satoshi didn't see the pool miners coming for sure.  But the algorithm still takes their collective power into account.  The most successful miners still pass on a fair amount of BTC.  I guess in the end it comes down to electricity. 

Good to know.  Never looked inside a getwork request.  I just knew it was 76 bytes of actual header information.  600 for 76 seems kinda "fat" but then again as you point out even at 600b per header the bandwidth is trivial so likely there was no concern with making the getwork more bandwidth efficient.

Nice analysis on complete bandwidth economy.  Really shows bandwidth is a non-issue.  We will hit a wall on larger pools computational power long before bandwidth even becomes a topic of discussion.   I think a 64bit nonce solves the pool efficiency problem more elegantly but the brute force method is just to convert a pool server into an associated collection of independent pool servers (i.e. deepbit goes to a.deepbit, b.deepbit, c.deepbit ... z.deepbit) each processing a portion of pool requests.

Still had Satoshi thought that just a few years into this experiment miners would be getting up to 3GH per machine (30,000X his original performance) he likely would have gone with a 64bit nonce.  When he started a high end CPU got what 100KH/s?  4.2 billion nonce range is good for 11.9 hours @ 100KH/s.  No real reason for a larger nonce since the header changes more frequently than that due to block changes and transactions (even if queued into batches).  A 30,000 increase in performance suddenly shrinked that nonce lifespan though.

Thanks this is how I believed it worked but wasn't sure.  In that case the use of larger nonce value (say 64bit) would make pool server even more efficient.  Then again to those who are opposed to the concept of pool mining likely don't want pools to become more efficient. 

Currently 76 bytes? Not using the getwork protocol. A getwork response without http headers is already close to 600 bytes... to transfer 76 bytes of data.

But yes, optimally it'd be 76 bytes (+ a simple header).

There'd be ways to cut that down even more, version is constant, nBits only changes every 2016 blocks, hashPrevBlock only changes on a new block, why send those every time?
Another option, allow miners to update nTime themselves.
work submits could be cut down in pretty much the same way, requiring only hMerkleRoot, nTime and nNonce. If there's too many increasing share difficulty would be trivial.
So, a simple more efficent protocol would have per 4Ghps:
hMerkleroot + nTime every 60 seconds or whatever the tx update interval is, hPrevblock every 10 minutes avg.
hMerkleroot + nTime + nNonce every second

at 100% efficiency, diff 1 shares and with some overhead that comes out to around 1 byte/second avg send and 45 byte/second or so avg receive for a poolserver for 4Ghps of miners.
Or about 24kbit/s send and 1Mbit/s receive for a pool the size of the whole current bitcoin network. Yeah.
If hashrates increase in the future, increase share difficulty by a few powers of 2 and you cut down the incoming rate accordingly...
So for the pool-miner interface, you can scale it up quite a few orders of magnitude before bandwidth becomes an issue.

For the network side, scaling to transaction volumes that are allowed by the current max network rule of 1MB/block, we need to receive and send the tx in that block and the block itself, that comes out to... 53kbit/s average.
The 1MB block size limit should be enough to fit about 4 tx/second average.
So... your average home DSL will become a problem when scaling up more than an order or magnitude above the current limits, we'd *need* some kind of hub-leaf setup beyond that, and assuming the hubs are decent servers you could easily get another 2-3 orders of magnitude. ... which would be roughly on par with visas peak tx capacity levels...
So doesn't look like bandwidth would become a major issue.

That's what I meant 2 phrases after:


So, yeah, as you said, miners definitely don't need lots of bandwidth, not even on "Visa levels". Only pool operators need.

No, as I explained, the miner doesn't need to get a new header when there's a new transaction. He just keeps mining on a header which doesn't include all the new transactions. When he finishes 4GH he gets a new header with all the recent transactions. That's how it's done right now, it's not a potential future optimization.

Thank you DeathAndTaxes for the full explanation.

So, currently, it's 76 bytes at each 4GH. Easily manageable. And even if we reach "Visa levels" as described here, miners would only have to download, at peaks, 76*4.000 = 304KB/s if I got it right (a new header each time a new transaction arrives and changes the Merkle Tree). I can download at that speed from my home connection today, so it probably wouldn't be a major problem for miners in the future. And even if it was, the Merkle Tree doesn't really need to be updated at each new transaction, that can be done on bulks.
So, nothing that frighting. Only pool operators would need lots of bandwidth, but at this stage, such operators could use local caches distributed in different parts of the world and other techniques to decrease their load.

Interesting.

What DeathAndTaxes said, the Merkle root is the "executive summary" of the transactions. And, inclusion of transactions in the block is on a "best effort" basis - everyone chooses which transactions to include, and currently most miners/pools include all transactions they know. But it's ok if a miner is missing a few recent transactions, he'll get (a header corresponding to) them in the next getwork.

I see what you are saying now.  I was updating my post (above) while you were responding.

Most of the need for header changes comes from nonce exhaustion.  Lets look at the times a miner needs to change headers.
a) block change - once per 600 seconds
b) new transaction - once per 13 seconds (at current transaction volume)
c) nonce exhaustion -  once per 4000/(MH/s)

For most miners nonce exhaustion creates the majority of the header changes.  For example a 2GH miner needs a new header every 2 seconds.  For every block change it exhausts it's nonce range 300 times.  For every transaction on the network it exhausts its nonce range 7 times.

Now transaction volume will grow but it is unlikely it will grow longterm faster than Moore's law.  Average hashing power will increase at a rate equal to Moore's law.  That is a doubling every 24 months.  2^5 = 32 fold every decade.  A decade from now that 2GH miner will be a 64GH miner.  That is 16 header requests per second.   

Even with real-time inclusion of transactions nonce exhaustion makes up the majority of the load on a pool server and that will only increase.  If a server were to delay including transactions to once per minute by holding all transactions till the next minute and then including them all in a block change (which would only slightly delay confirmations) then nonce exhaustion makes up an ever greater % of server load.

If we assume that the average transaction happens about 5 minutes before the next block is found, the current system makes it very, very likely that the transaction will be included in the current block.  This means that the expected waiting time for a transaction is just a bit over 5 minutes.

With a 64 bit nonce, all mining clients will only update their work every 10 minutes (on average), when a new longpoll hits.  So, the average transaction will wait 5 minutes before anyone even starts working on a block that includes it, and then 10 minutes more (on average, of course) for that block to be found.  So, the total wait time is then 15 minutes, instead of 5.  The worst case, sending a new transaction just moments after all the pools update their miners, goes from 20 minutes to 30.

How?  Regardless of the nonce size a block will be confirmed on average every 10 minutes. At worst case scenario transactions can always be included in the next block.  

Are new transactions after the start of a block included in the current block (as opposed to next block)?  If so then on average never updating transaction list would add 5 minutes to first confirmation and nothing to subsequent confirmations.   If not then confirmations are no slower.

Still even w/ 64bit nonce there is no reason you couldn't update merkle tree between blocks. Look at it this way.  Take a hypothetical 1TH/s pool.  On average it needs to compute and issue 15,000 header per minute for it's pool members.  Looking @ block explorer the last 24 hours had 6407 total transactions.  That is one average 4 per minute.  If the pool had 1000 members using a 64bit nonce and only changing header on transactions would cut that down to 4,000 headers per minute.  If pool only updated headers once per minute (on average adding a few seconds to each transaction confirmation time) it would be only 1,000 headers per second.

This would also slow transactions, and/or not decrease traffic by nearly as much as you expect.  The mining pool node is constantly updating its Merkle tree, so a new getwork request includes not just a different coinbase with a new extranonce, but also a different set of transactions, some new.  A 64 bit nonce would roughly triple the average transaction confirmation time, unless the node trips the long polling system, which makes extra traffic.

There are subtle, er, issues with this idea.  I think they are actually problems, but I haven't worked through all the details yet, so I'm not confident enough to use that label yet.  Think carefully about the coinbase transactions, and how those are included (or not) in the half signatures.  I'm pretty sure that this system ends up being no better than just the second half system, but it could be modified to be as good as whichever system was slower at the moment.

It is a hash of the header which contains the Merkle Root of all transactions in the block plus the hash of the last block.  That is how the "chain" is efficiently created.  If you know a previous block is valid and each block contains the hash of the prior block in the current block then you know the current block is valid by following the chain from the genesis block. Every transaction in the current block is confirmed because the merkle root is the hash that contains all the hashes of the transaction in the block.  If an extra transaction was added or one taken away the merkle root hash would be invalid.

https://en.bitcoin.it/wiki/Block_hashing_algorithm

All together the only thing that is hashed is the header which is 80 bytes.  The nonce is determined by the miner so the pool actually only transmits 76 bytes.  The miner then tries all nonces from 0 to 2^32 -1 (roughly 4 billion attempted hashes).  A shares is 2^32 hashes so 1 share ~= 1 header transmitted.

Since nonce only has 2^32 possibilities the pool server needs to provide a new header (containing extra nonnce) after every 4 billion hashes.

Thus bandwidth requirement (without any overhead) is ~ 72 bytes every 4 GH (the same header can be used for 4 billion hashes) of hashing power that the miner has.   Even a 40GH miner wouldn't require very much bandwidth.  It would require 10 headers per second and would produce 10 shares (lower difficulty solutions) per second.  The headers would require ~800 bps inbound and the outgoing shares would require ~2kbps outbound.

Now for the server that bandwidth requirement can be larger as they will have significantly more aggregate traffic.  A 5TH/s mining pool would need to issue 23,283 headers per second but even that is only 1.8Mbps.

Still bandwidth is really a non-issue.  As difficulty rise and the pool gets larger the computational load on server becomes the larger bottleneck.  Every 2^32 hashes a miner will need a new header and that requires the pool to change the generation transaction and thus requires a new hash and that changes the merkle root which requires a new hash.

If it ever became a problem where pools simply couldn't handle the load, changing the size of the nonce could make the problem more manageable.  The Nonce is only 32 bit and is the only element a pool miner changes thus every pool miner needs a new header ever 4 billion hashes. A 100MH/s miner needs a new header every 40 seconds.  A 4GH/s miner needs a new header every second.  If the nonce value was larger more hashes could be attempted without changing the header.  For example if nonce value was 64bit a 4GH miner would only need a ONE header every 17 minutes instead of one every second (unless a block was found).  Most miners would never change headers except when a block is found.  The load on pool server could be cut by a factor of billions.