It's not clear at this point whether the coins were stolen or Gox just lost the keys.  If the keys are lost, then I would expect the price of bitcoin to rise.

I bought an Amazon gift card from shiunsai.  No problems.

So actually this won't work.  An attacker can just add an input with a public key that is the multiplicative inverse of your public key.

So if A = y and B = (1/y) the signature is verified as:

g^m = (A*B)^r * r^s
g^m = (y/y)^r * r^s    
g^m = 1^r * r^s    
g^m = r^s

which is trivially forged.


And in elliptic curve arithmetic, you add the inverse, yielding the identity element.  An attacker can then add their own public key to avoid the point at infinity.  The combined "master" public key is insecure.  So this doesn't work.          

So the question is...  Is it possible to have a single signature that requires two public keys to create it?

ECDSA is based on ElGamal signatures.  There are several variants, but let's just consider the basic signature scheme:

Given:

Generator g
Private key x
Public key y=g^x
Message m

A signature (r,s) on message m is valid if g^m = y^r * r^s

As gmaxwell points out, it is possible to compute y (public key) from the signature and message as y=(g^m/r^s)^(1/r).  To validate the signature, you would of course have to check that this public key is the one you expected.

It seems possible to make a signature from two public keys A and B, such that g^m = (A*B)^r * r^s

Obviously this would be incompatible with the current bitcoin protocol, but it does seem possible in theory.  I'm not entirely sure of the security implications of such signatures.  I'd have to think about it some more.

See this for a discussion of what happened to the bitcoins from the pizza:

http://bitcoin.stackexchange.com/questions/450/is-there-any-way-to-track-an-individual-bitcoin-or-satoshi

I placed an order with esadee and got my stuff in 2 days.  Great!

Is there a mining pool that will generally take free transactions?  Even if such transactions are given low priority, it seems it would be useful to prevent these situations.

I tried this... During checkout it gives me a total of $0.00, then says:

Your order cannot be completed at this time as there is no payment methods available for it.

Successful trade with live627

0.7 btc for all.

With Amazon, you can sometimes tell the origin of the code.  The scratch-off cards they sell in the stores are 15 characters and usually start with the letters AQ.  The ones bought online with a credit card are 14 characters. However, the ones from the coinstar machines also have this 14-character format.  If someone claims to have a code from coinstar, ask for the receipt.

There was a thread on bitcoin-development about this too...

http://sourceforge.net/mailarchive/forum.php?thread_name=CABOyFfrPTYeq-g5tgte2HWfvBiBcRLw_Bvyk_X2hXMWVoW3dgQ%40mail.gmail.com&forum_name=bitcoin-development

Blind signatures, as described by David Chaum, are based on RSA.

Anyway, the basic idea is that someone buys a blind signature from the mixer, then some time later uses that signature to get money back, but the mixer can't connect the two.  The blind signature is not used to directly sign bitcoin transactions.

There's a limit to RSA blind signatures - if someone signs a bunch of small prime numbers, then multiplying these together yeilds a valid signature on the product.  Collect enough factors and you can sign anything.  So, if too many blind signatures are made, it effectively leaks the signing key.  Thus, the signing key needs to be changed each time, and you can only mix a limited number per batch.

We're a long way from that.  Even something at the scale of Paypal (~85 tps) could run on an average desktop PC with 1mb/sec internet connection.

The post from Gavin that I was referring to is here:

https://bitcointalk.org/index.php?topic=140233.msg1503099#msg1503099

That is a lot.  That would be more than 1.5 transactions per day for each of the 15,000,000 users.  That's higher than the per capita volume of credit/debit card purchases in the United States.  I think I use bitcoin more than most people, and my average number of transactions is still under 1 per day.

Maybe that is peak volume and not average.

I like Gavin's proposal.  (I mean his actual proposal, not the "half-baked thought" quoted above.)

No hard limit, but nodes ignore or refuse to relay blocks that take too long to verify.  This discourages blocks that are too large, and "spam" blocks containing lots of transactions not seen on the network before.

This might create an incentive to mine empty blocks.  To discourage this, in the case of competing blocks, nodes should favor the block that contains transactions they recognize, and ignore (or delay relaying) the empty block.

bitaddress.org does check.

If bitcoin operated at the scale of PayPal, ~87 transactions per second, that would require roughly 20MB blocks.  That's large, but not unmanageable.

People paid PayPal US$ 5.6 billion in fees last year.  There's no way the bitcoin network is going to cost that much.

Looks like Eligius did it.

Perhaps Coinbase should consider an ongoing offer of a small amount of btc to any mining pool that agrees to take all their transactions, fees or not.