Topic: How to verify the ownership of Bitcoins? (Read 1451 times)

"millionaires problem" is just comparing integers. Not exactly whats wanted there (requires the millionaires to be honest!)... SMP could be used, sure, but requires the particpants to be online, has horrible performance (I'm imagining days to verify a SPV proof) and ultimately, SMP systems depend on cryptographic assumptions not dissimilar to ECC... if your SMP implementation fails the other parties may learn your private key.

Simple signmessages are easy and have a simple security story which is not obviously any worse.

Secure multiparty computation. That is called the millionaires problem and it has been solved.

I don't know whether or not it's solved in the Bitcoin protocol but theoretically it has been solved.

I take a very slight exception to this.  Signing a message, which is all that a transaction is, has a cost.  One, it requires you to publish your public key, and two it requires you to publish a signature.  Publishing your pubkey is a huge hit to the security of the key, as it entirely strips one layer of our elaborate defensive structure (the hash) from that key.  Once the pubkey is widely known, the incremental cost of publishing another signature is slight, but not zero.

These are very tiny, but real, costs to the security of that key.  We believe that our system is secure against key-reuse, but history teaches us that multiply used keys are the first to fall when a system starts to show weaknesses.  The problem is even worse with low quality keys, which I consider all so-called brain wallets to be, and those are the very ones that people are most likely to use to store their largest stashes, and the ones they'll most likely be tempted into weakening in this way.*

A user should not publish their public key until they are ready to stop using it.  Signing a message to prove that you control the key that controls some coins is not the final use of that key and should not be encouraged.

The safe way to prove ownership of a key is to transfer it all funds available to that key to a new key/address with an unpublished pubkey.  This is how gox proved the safety of their stash a while back, and this is how the FBI proved confiscation of DPR's wallet.

* I see proof of address systems mainly used as e-peen comparison tools.  Perhaps I've overlooked some serious usage?

Signing doesn't cost anything other than time to do it. So just have them sign a message with multiple addresses.

You can sign as long as you have access to the private key. In the case of a paper wallet you will need to load it into a client and then sign using that. In the case of hosted wallets it depends on whether they give you access to the private key or not. blockchain.info does let you sign messages. Exchange wallets don't.

Most of the people have their Bitcoins in wallets spread across multiple addresses, right? How would a single tx be sufficient to verify the ownership? This wouldn't work for paper wallets either, right?

I guess this problem applies to verifying by signing as well. Also, I'm not sure how well signing is supported by hosted wallets and how well Bitcoin users know this feature. But signing would work for paper wallets, correct?

Yea, I think it (probably) was me. We actually use this in our sign-message stuff.

The downside (beyond the fact that we don't do it now) is that it's somewhat slower than basic validation, obviously this is mostly irrelevant for sign-message... but its a potentially interesting tradeoff in Bitcoin.  Though the size reduction of using a hash over an X-coordinate only ('compressed') pubkey is not really significant. (though I have some preference for the hashed form because symmetric cryptographic seems to be less brittle generally).

It wouldn't be technically hard to add to Bitcoin, however, as it would just be a soft-forking change to add a new checksig operator that was usable for this.

There are much more interesting (and similarly) easy cryptographic ideas out there than this.   But really we're hardly even using a fraction of Bitcoin's potential. Many of the popular wallet programs can't even send to P2SH addresses. In light of the absence of technical innovation, in practice, in our community any further protocol additions would be a hard sell right now.

IIRC it was gmaxwell? (or maybe I am just getting him confused with another hardcore cryptographer) who edumacated me when I was looking into how an altcoin could improve tx efficiency last summer.


This is just my opinion but Satoshi probably wasn't that great of a cryptographer.  There are a lot of questionable decisions made in the early protocol that we are essentially stuck with today.   The use of uncompressed keys is one example.  Had Bitcoin been explicitly defined to use compressed keys the code would not only be simpler it would have made everything more compact.  Another example would be not requiring a canonical signature format.  This has created a whole host of potential bugs and security issues that simply wouldn't exist if the protocol had been more explicit from day one.

Of course today trying to implement a change would be tough.   However if altcoins were about innovation and not just pump and dump scams tightening up the protocol could pay real dividends.  Then again I don't expect much of any innovation from altcoins.

Ah!  See, no matter how much I think I've learned about bitcoin and cryptography, it seems there's always more to learn.  Thanks D&T.

Of course this does leave me wondering why the public key is included with the signature in bitcoin transactions?  Seems like quite a waste.  I'd have expected that this fact about ECDSA should have been well known by anyone working on the early versions of Bitcoin.  It really surprises me that they would go to the wasted effort of including the public key if it can be computed.

A little ECDSA magic.  Given a signature and original message one can compute the public key.  It is called public key recovery.  Technically Bitcoin (or some superior future altcoin) could make txs smaller by using this to remove the explicit pubkey and computing it instead. 

There's a way to sign it, a site like that might get a lot of beggars though.

How does that work?

Given a message and signature, how can someone verify the signature without the public key?  The address is a hash and irreversible.  The public key can't be computed from the signature, can it?

You do not need the public key to verify the signature. The address, signature, and message are sufficient.

Same way paypal verify..

Yes, get them to send 0.0000 to your address

As long as the signature includes the public key (or the public key is already in the blockchain), yes.

..can I check signature with bitcoin address?

would be quite a simple site to make actually.

getting people to know about it and use it would be the problem.

Yes, they can sign a statement using the private key associated with the bitcoin address.

Say, a person says he owns 100BTC in certain addresses / wallets. Is there a way to verify the ownership without asking the owner to jeopardize his coins?

I'm thinking about developing a casual website that would allow Bitcoin users to brag about their wealth, but I'm not sure if it would be possible to verify that the users actually own the Bitcoins they claim to have.