...unless nTime field is also incremented, which is a permissible optimization...

In the coming months, it is expected that the standard miner will use the algorithm of

     1. server sends new work, interrupting current miner work
     2. miner crunches nonce+ntime
     3. when new block arrives, go to step #1

That completely eliminates polling, unless a new block is not found on the P2P network in ~2 hours or more.

CPU miner supports long polling, as noted in the CPU miner thread:  http://bitcointalk.org/index.php?topic=1925.msg67246#msg67246

Switching CPU miners to long polling will likely have more beneficial effect on server load, versus GPU miners + LP, because CPU miners under long polling change to 60-second polling intervals.

One option is simply to raise the difficulty.

I've been thinking about increasing the difficult by 16 bits, in one of my pool server projects.

Patch and git updated with a new 'scratchoff' RPC, which will redeem a 'sendscratchoff' transaction.

The scratchoff system should now be minimally functional.  Because the hash of the public key is what is seen in the block chain, an attack should not better than brute force of the 64-bit random space.

Current limitations:

• scratchoff should immediately create a new transaction to claim the scratchoff, but it does not.  It only adds the initial spend, and the keys, to your wallet.  Internally, this requires selecting coins for the new transaction very specifically, which the current code does not easily support, unless I'm missing something.
• scratchoff requires full 256bit txid, not the truncated 32bit id returned by 'sendscratchoff'.  Operationally this is fine, but from a consumer-friendliness standpoint, we want to be able to lookup a transaction using as few digits as possible.  Internally, bitcoin stores using a btree, so this is possible, just not yet implemented.
• The 'toaccount' parameter is ignored.

The scheme could be further strengthened by adding brute force bits on top of 64.  Unfortunately, any scratch-off scheme is ultimately limited by what a consumer card might be reasonably expected to show.  Credit cards in the US have 4x 4-digit blocks, so I picked 4x 4-hex blocks == 64 bits.  Suggestions for increasing the bit count in a consumer friendly way are welcomed.

The scratch-card ECDSA private key generation algorithm is the following:

     password = random 64-1024 bits
     salt = user-supplied string, or "bitcoin" if salt is not supplied/zero-length
     pipe1 = SHA256(password, salt)
     pipe2 = SHA256(salt, password)

     for i = 0 to 108333
          pipe1_out = SHA256(pipe1)
          pipe2_out = SHA256(pipe2)
          pipe3_out = SHA512(pipe1_out + pipe2_out)
          pipe1 = first half of pipe3_out
          pipe2 = second half of pipe3_out

     raw ECDSA private key = pipe1

Well, you can see precisely where the 50 BTC from each block goes, at http://blockexplorer.com/

Become an open source hero, and help bitcoin too!

OK, I think this project would see some real return (in BTC) on Linux, for all the miners out there.  It would benefit open source as well.

The Project
-------------------------------------------------------
Successfully load and execute a sha256 "compute shader", using 100% open source video drivers on Linux (using closed source ATI tools to produce shader binary is permitted).  Any Linux OS/distribution, as long as it's a recent version.  Must work on ATI 5870/5970 hardware.


Rationale
-------------------------------------------------------
1. In theory, the closed source ATI SDK and video driver should not be needed, once we have a compiled shader.  It would make life much easier on Linux, and expand our miner base, if stock open source drivers can be used for GPU mining.

2. Open source GPGPU efforts are moving slowly, and this would help jump-start those efforts, by providing a working example.  This has the potential to be a high profile contribution to the OSS community.


Details
-------------------------------------------------------
According to some knowledgeable hackers, it should be possible to upload a "compute shader" using current Linux/OSS video drivers, via the Linux DRI APIs.  The programmer (or team) would need to figure out how to coax ATI's SDK to produce a compiled, binary object that is then loaded into an open source driver, and executed.

The person or team collecting this bounty will need to be able to accomplish tasks such as rebuilding and replacing the kernel, rebuilding and replacing Mesa (OpenGL/DRI), and rebuilding/replacing the X server.  Even though these are non-programming tasks, they are decidedly non-trivial.

This code (from ATI?) should be helpful in demonstrating how to work with 5870/5970 hardware: http://cgit.freedesktop.org/mesa/r600_demo/tree/?h=master

Although this task should be largely a "put together existing pieces and make them work" task, it is still quite complex.


The Pledges (in BTC)
-------------------------------------------------------
I'm hoping to raise at least 200 BTC for this task, if not more.  Miners on Linux, consider pledging a block (or part of a block).

15     jgarzik


If you wish to pledge anonymously, send me a PM and I'll coordinate.

Pledges should be payable within 24 hours of a working example being posted publicly.

If you're using long polling, you should not need a local client, nor get any stales.

I doubt anyone would use a scratch card for a large sum of money.


Think of this as a 192-bit salt.  It is well known how to use multiple salts.

Long polling was just added to git, and I posted a test Windows version here:
     http://yyz.us/bitcoin/cpuminer-installer-0.7.2-lp1.zip

Test feedback appreciated, on Linux (build your own from git) or Windows.  http://deepbit.net/ is known to support long polling, and slush's pool should be able to do it soon, too.

This should increase people's CPU mining efficiency quite a bit, while also reducing network usage (and load on pool servers).

Countermeasure is to laugh as their CPUs barely make a dent in our hash rate.

This feature was written pool servers in mind.  It seems likely that pool operators -- they who mine a lot of blocks anyway -- will upgrade sooner rather than later.

I seriously doubt you can get anything close to checking a trillion combinations per second on any modern GPU.

You can see two 'sendmany' transactions in block 113931:

     http://blockexplorer.com/b/113931

Part of the point is to prevent ugly, useless polling...  ;p


Sure.

It seems some ability to script local bitcoin wallet actions would be useful.  For example, give the user the ability to add "rules" to the local wallet which specify operations such as

• if local block generated, send to address X when it matures
• if money received to account A, move it to account B
• if money received to account A, send it to address Y

Block chains can fork.  The longest, most strong block chain is the one that's trusted.

But with satellite and other means of communication, it seems likely that blocks and TXs would inevitably leak back and forth.

That's how my patch is implemented, yes.

You can make it stronger by, say, having 1000x 176 bits of well known private key, 64 bit password, and 16 bits of brute force required to redeem.

If we are creating new transaction types, a far more elegant approach can be had...  a new 'anybody can claim' transaction added to the client could be made more secure and elegant, but at the disadvantage of being easy to spot in the block chain, and therefore a more likely target for attack.

Would be interesting to have more specific criticisms, now that code's out there.  The main question, as ByteCoin indicated, is whether or not there is an attack that is faster than brute force, if you know a portion of the private key.

As the Variations section hints, the implementation presented was the most simple to implement, not necessarily the most consumer friendly or the most secure.  When deploying this into production, should it make it into the bitcoin client, I would do a couple things, such as

• require some level of brute forcing for all redemptions (have bits neither in well-known private key subset, or the password)
• ship 1,000 well-known 192-bit private key subsets

Each valid redemption would therefore require some amount of brute forcing, while an attacker has a lot of work to do comparatively -- they have to first recognize a scratch-off from a normal spend, in the block chain.  Then they would have to find the remaining ~64+ bits of private key, having only the public key (or a hash thereof) as a starting point.

I readily admit I am no cryptographer or math genius, though!   Hopefully the future will bring more substantive criticisms from #crypto than "exposing part of private key leaves me vaguely unsettled"