I have looked into this, and you do need the public key to break it. (Also I was wrong about Pollard rho being suitable, but the other two are.) Bitcoin does not reveal the public key until the tx is spent; only a hash is revealed until then. However the spending tx is vulnerable while moving through the network on its way to a block. A miner or peer could hold the transaction, break the key in 2^32 work, and substitute their own spend.

As far as the algorithmic details, here is baby step giant step. Public key Y, private key x, and generator G satisfy:

Y = xG

x is of the form s + k, where s is known salt and k is unknown 64 bits. Split k into left and right halves l, r:

k = l*2^32 + r

with l and r 32 bits. Then we have, substituting for x in the first eqn:

Y = (s + l*2^32 + r)G

Y + l(2^32(G_inv)) = (s + r)G

We precompute all 2^32 values of the RHS and store them in a hash table. Then we sequentially try the 2^32 values for l in the LHS and look for a match in the table. That gives us l and r, which gives us the private key x.

One case to consider is when you have addresses A and B in your wallet but don't want them linked. Jollygreen's code will allow making sure you never spend from A and B together, I think, so that's good.

But suppose someone uses the multipay patch to send to both A and B together, because they suspect that the addresses are linked. There are a few ways this could go wrong. Suppose he told you he was sending 10 to A, but also includes 1 to B in the transaction. I'm not sure what the client would do, but it might show you receiving 11. Then you'd be like, dude, you sent me 11 not 10. And he'd be like, you're busted.

Another way it could go wrong is that you could spend them together, and again, you're busted. I think Jollygreen is protecting against this.

Yet another failure mode would make it impossible to spend the funds, because it would break the rules. So sipa's patch needs to be part of this, allowing the outputs to be split.

We know that Bitcoin's resistance to attack is based on the cost for the attacker to overwhelm the network, or at least to control a large fraction of its computing power. We assume this cost will continue to rise in the future so attacks will be infeasible even for well-funded attackers.

But the computational power of the network is proportional to difficulty; and it appears that difficulty is proportional to bitcoin price. It follows that unless bitcoins become substantially more valuable than they are today, the Bitcoin network will never be substantially more resistant to attack than it is today.

For Bitcoin to succeed and become secure, bitcoins must become vastly more expensive.

The unit of spending in Bitcoin is the output of a transaction. That's the closest thing in the system to a "coin".

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

It's an artifact of the coin choice algorithm, not an inherent property of transactions. Sipa offered a patch in that thread, but I don't know what it does.

Follow the rules!

I've put up a wiki page listing the rules used by the client to process transactions and blocks. It's a bit linear and could benefit from some refactoring, but I didn't want to go too far in terms of pseudocode, because IMO it obscures the logic.

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

You're conflating two issues: using bitcoins to buy things on eBay; and using eBay to sell bitcoins for dollars.

I would focus on use cases.

1. Back up all the keys in a wallet, and later restore the wallet state if the wallet is deleted or corrupted.

2. Merge two wallets by exporting all the keys in one, and importing to another.

3. Export and remove selected keys from wallet, for moving to safe long-term storage in case the wallet is hacked; later, move the keys back to a wallet for spending.

4. Export selected keys for transferring their funds to someone else; the recipient imports the keys and gains access to the funds.

Any others?

I wonder whether it makes sense to use bitkeys format for case 1 and 2. Wallets do have other things, which is part of your problem. I'd suggest that case 1 & 2 should use wallet formats.

This would mean you don't have to worry about reserve keys. I'd treat the other key classes the same.

Case 3 & 4 are very similar. They suggest you should have an export-and-delete function. Gavin suggested: 1. export key to disk file; 2. read disk file, make sure key is there; 3. delete key from wallet.

Case 4 probably should delete the exported key. You can save a copy and re-import it if the recipient never uses it.

For the case 4 import you really want to do: 1. import keys; 2. do a spend from these keys to one of yours; 3. delete imported keys. That assures that ownership transfers. You don't need this for case 3 import as it's your key.

Finally, as far as the address and balance: I don't like putting them into CSV fields, because they are redundant and unnecessary. Your comment fields seem okay, but note that the balance may be out of date. How about a command that would take a bitkeys file, and display the address and current balance? Then you could leave the comments out.

Here's how I would approach this idea. The concept would be to function in max-anonymity mode by default as now, but to also specify a certain address as being associated with an identity. Receiving coins to that address is trivial, just give out that address for payment. Add a feature to make identified payments from that address as you propose. Important, payments from that address should use that same address for change. Equally important, make sure that regular "anonymous" payments DO NOT use the identified address, otherwise your anonymity will be compromised. That way, anonymous and identified payments can coexist.

You could also have more than one identified address, keeping each separate. Probably you'd want to use the address label to choose which to pay with. But the same principles would apply: change back to the same address, and never use it for regular payments.

As far as getting started, I'd like to see a sticky walking through the steps to create a pull request. But yeah, you can check out from sourceforge using svn, get your changes working, and post the output of svn diff as a patch.

There was quite a bounty for this at one time

http://bitcointalk.org/index.php?topic=1812.0

Can't you store the block chain somewhere else?

The block file is 90MB. So you'd have to do 11,000 initial block downloads.

I had the impression the roadmap called for a BitDNS-like decentralized mapping system, since Gavin asked to map "strings" to addresses. Maybe I misunderstood.

Wow, do you mean your bitcoin client communicated a terabyte in a month??? That doesn't sound right.

Average block size is about 3.5 kB, that makes about 15 MB/month. If you had 100 peers that could be maybe 2 GB/month.

This can be done using the TPM chip and Intel's Trusted Execution Technology. http://www.intel.com/technology/security/

Newbie chodpaba has discovered a strong correlation between lagged btc price and difficulty: http://bitcointalk.org/index.php?topic=4339.0. It predicts that difficulty should stay level or decrease slightly for the next month. We'll see!

Very nice analysis! Since the price has been at or near 1 for a month now, this would predict that difficulty should now level off for at least a month. Should be interesting to see!

Well, I can always pay you to work on my block, just like I can pay you to work on my car. So it can certainly be arranged, outside the Bitcoin protocol.

I'm not sure I've seen a convincing analysis of the optimal strategy for miners in the era of no block creation fees, even ignoring these kinds of side payments.

Plug your hash rate into the Bitcoin Calculator to see how often you can expect to find a block. 400 kh/s will take over two years. That's if difficulty doesn't go up.

http://www.alloscomp.com/bitcoin/calculator.php

Here is a rather exhaustive analysis of the legality of private currencies in the U.S., by GWU law professor Lewis Solomon:

http://www.smallisbeautiful.org/local_currencies/Book.pdf

He focusses on community "scrip" currencies like Ithaca Hours, and concludes that they are probably legal. One caveat is that the book is from 1995, and of course financial regulations have changed since then. Still community currencies operate in the open, unmolested by the Feds.