I don't think 'Pi' is a valid public key...

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: Kazimir on March 16, 2014, 05:11:07 PM

Quote from: gmaxwell on March 16, 2014, 03:54:33 PM

It's arguably that bc.i should display something more useful there... but at the end of the day the key point remains that the bitcoin system itself doesn't have addresses— addresses are a wallet layer construct and any attempt at mapping back from the chain to addresses is going to have some limitations.

What do you mean, Bitcoin itself doesn't have addresses? A recipient in a tx is nothing more than an address, right? Regardless of how we represent it, but I mean it's not an actual public key or something.

Or maybe I have a wrong idea of what an address is, but to my knowledge an address is nothing but a RIPEMD160 hash of a SHA256 hash of a public key that corresponds to some private key...?

An address is just a human friendly way to encode a template for a scriptPubKey. Transactions do not contain an address for each of their outputs, however, just the resulting scriptPubKey. There is no guarantee that you can reverse the operation for all transactions.

dbbit

sr. member

Activity: 322

Merit: 250

Quote from: Kazimir on March 16, 2014, 05:11:07 PM

What do you mean, Bitcoin itself doesn't have addresses? A recipient in a tx is nothing more than an address, right? Regardless of how we represent it, but I mean it's not an actual public key or something.

Not always.

There's either a pubkeyhash, or sometimes a pubkey - which is indeed an actual whole public key.

E.g. the bitcoin miner when you solo mine adds a simple ' OP_CHECKSIG' check in for the coinbase tx and doesn't use the hash.

If you look at all of the initial blocks in the blockchain they're all like that for the coinbase tx, but it appears later as well.

Kazimir

legendary

Activity: 1176

Merit: 1011

Quote from: gmaxwell on March 16, 2014, 03:54:33 PM

It's arguably that bc.i should display something more useful there... but at the end of the day the key point remains that the bitcoin system itself doesn't have addresses— addresses are a wallet layer construct and any attempt at mapping back from the chain to addresses is going to have some limitations.

What do you mean, Bitcoin itself doesn't have addresses? A recipient in a tx is nothing more than an address, right? Regardless of how we represent it, but I mean it's not an actual public key or something.

Or maybe I have a wrong idea of what an address is, but to my knowledge an address is nothing but a RIPEMD160 hash of a SHA256 hash of a public key that corresponds to some private key...?

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: dbbit on March 16, 2014, 01:15:40 PM

EC is hard enough - I can't even begin to imagine the consequences of returning a point that's not on the curve. Does it just mean there is no private key? Or is there an infinite number of private keys?

The missing points are on an alternative curve (the quadratic twist) and have a discrete log (a private key). For some curves used for cryptography the twist is not cryptographically strong— meaning the discrete log is 'easily solved' there— though ours is acceptably strong. It's still important that any verifier check the that the pubkey is on the curve (and especially important for anything doing ECDH).

It's arguably that bc.i should display something more useful there... but at the end of the day the key point remains that the bitcoin system itself doesn't have addresses— addresses are a wallet layer construct and any attempt at mapping back from the chain to addresses is going to have some limitations.

dbbit

sr. member

Activity: 322

Merit: 250

Quote from: grau on March 16, 2014, 02:04:12 PM

Recognize that it is not an address that holds a coin, but a transaction output. Most transaction outputs refer to an address, but this is not part of the protocol, but a convention that applies to the vast majority of transactions.

Consequently the client can have money that is not associated with an address.

The client owns those coins (transaction outputs) for which it is able provide input such that the associated script evaluates to true. This means for an output that looks like a regular pay-to-address that it has the private key for a public key that hashes to that address. You see the criteria for ownership of an address is more narrow than having a valid EC point (public key) for an address, but is also much wider in general.

I agree from a purist perspective. You should never assume money is yours unless you know for sure you can supply input that will satisfy the script.

But is that what clients (like bitcoind) actually do before it claims ownership and display it as a balance in your wallet?

It's much easier (and faster) to just hash down the OP_CHECKSIG pubkey to an address and see if it matches one in your wallet, so I can imagine that there would be a lot of software that takes this shortcut.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: dbbit on March 16, 2014, 01:15:40 PM

i.e. If a client doesn't validate the pubkey, yet still hashes it to an address, can it be tricked into thinking that it has money which it really doesn't have?

Recognize that it is not an address that holds a coin, but a transaction output. Most transaction outputs refer to an address, but this is not part of the protocol, but a convention that applies to the vast majority of transactions.

Consequently the client can have money that is not associated with an address.

The client owns those coins (transaction outputs) for which it is able provide input such that the associated script evaluates to true. This means for an output that looks like a regular pay-to-address that it has the private key for a public key that hashes to that address. You see the criteria for ownership of an address is more narrow than having a valid EC point (public key) for an address, but is also much wider in general.

dbbit

sr. member

Activity: 322

Merit: 250

Thanks.

For those crypto experts, is there a danger here? I assume a lot of software isn't going to check it either and just allow it.

EC is hard enough - I can't even begin to imagine the consequences of returning a point that's not on the curve. Does it just mean there is no private key? Or is there an infinite number of private keys?

The other issue is the address that it hashes to. I think that remains secure, but it now has an almost infinite number of more inputs that it used to if it just allowed points on the graph.

Is it possible/any easier to send money to a person's address, but give it an off-curve pubkey CHECKSIG that hashes to the same address but that they would in fact not be able to spend?

i.e. If a client doesn't validate the pubkey, yet still hashes it to an address, can it be tricked into thinking that it has money which it really doesn't have?

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: dbbit on March 16, 2014, 06:41:46 AM

Quote from: gmaxwell on March 16, 2014, 06:34:45 AM

It's an output, and it's unspent. Bitcoin blockchain rules do absolutely nothing with the content of scriptpubkey until its spent.

Argh.

Can I at least complain that blockchain.info reduced that to this address:
1EXpM1kseQJSudJEhMUT1SGzNrGtJADjp4

That address doesn't and can't exist - they just skipped the EC point validation. It should have said something like 'invalid key' instead.

I was on a wild goose chase for quite a while thinking BlockChain.info is correct and my formulas were wrong.

Didn't help that I was looking at the number in decimal and binary and didn't realize it was hex-represented pi Embarrassed

.

EDIT: Just saw decoderawtransaction on bitcoind does the same thing. Also hashes down an 'address' without validation. Sigh.

That is correct. Addresses are not existent at the protocol level. An address is just a data element in a script.

Remember remember the 5th of November

legendary

Activity: 1862

Merit: 1011

Reverse engineer from time to time

Quote from: piotr_n on March 16, 2014, 08:21:14 AM

Quote from: dbbit on March 16, 2014, 06:41:46 AM

That address doesn't and can't exist - they just skipped the EC point validation. It should have said something like 'invalid key' instead.

Bitcoin protocol does not validate points, in the uncompressed public keys, so there is not reason for blockchain.info to do so.

Though, that might be a good tip for another rule to purge more unspendable outputs from a client's UTXO database.
But, at the other hand, probably there will not be so many of them to even bother writing the code - not too mention a time needed for the calculations.

We don't need to worry about the calculations, the computing power will suffice. 5-30 minutes more? So?

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: dbbit on March 16, 2014, 06:41:46 AM

That address doesn't and can't exist - they just skipped the EC point validation. It should have said something like 'invalid key' instead.

Bitcoin protocol does not validate points, in the uncompressed public keys, so there is not reason for blockchain.info to do so.

Though, that might be a good tip for another rule to purge more unspendable outputs from a client's UTXO database.
But, at the other hand, probably there will not be so many of them to even bother writing the code - not too mention a time needed for the calculations.

dbbit

sr. member

Activity: 322

Merit: 250

Quote from: gmaxwell on March 16, 2014, 06:34:45 AM

It's an output, and it's unspent. Bitcoin blockchain rules do absolutely nothing with the content of scriptpubkey until its spent.

Argh.

Can I at least complain that blockchain.info reduced that to this address:
1EXpM1kseQJSudJEhMUT1SGzNrGtJADjp4

That address doesn't and can't exist - they just skipped the EC point validation. It should have said something like 'invalid key' instead.

I was on a wild goose chase for quite a while thinking BlockChain.info is correct and my formulas were wrong.

Didn't help that I was looking at the number in decimal and binary and didn't realize it was hex-represented pi Embarrassed

.

EDIT: Just saw decoderawtransaction on bitcoind does the same thing. Also hashes down an 'address' without validation. Sigh.

gmaxwell

staff

Activity: 4284

Merit: 8808

It's an output, and it's unspent. Bitcoin blockchain rules do absolutely nothing with the content of scriptpubkey until its spent.

dbbit

sr. member

Activity: 322

Merit: 250

The following block:
https://blockchain.info/tx/c94f41c1177b22ffff461808e62e31b3211352c78b6d550d445583c721eb48ca

Has a OP_CHECKSIG on n=1 for:
0431415926535897932384626433832795028841971693993751058209749445923078164062862 089986280348253421170679821480865132823066470938446

Taking out the '04' uncompressed form marker, and you've got yourself pi to 128 digits. (Sort'a. That's really a hex number. Whatever.)

Not surprisingly, it fails the elliptical curve equation (and had me swearing at Bouncy Castle all night).

How did this make it into the blockchain?

Topic: I don't think 'Pi' is a valid public key... (Read 1134 times)