checking address or pubkey of unspendable bitcoins

[akaki]

Hi,

I would like to understand how one can verify that bitcoins in a given address are unspendable.

To me, there are N points on the field of the elleptic curve. That makes (N+1)/2 points with distinct x coordinates (=half side of the symetrical field)

Therefore, there are (N+1)/2 points left, such as (x,y)!=k*G with k in [0,N].

For example:

If I pick x=0 (for which I'm almost sure it cannot result from k*G), we can derive two points :

P1=(0 , 64828261740814840065360381756190772627110652128289340260788836867053167272156)
Adress1=15wJjXvfQzo3SXqoWGbWZmNYND1Si4siqV

P2=(0 , 50963827496501355358210603252497135226159332537351223778668747140855667399507)
Adress2=1MqALQs6ea1ACgwRurqgaBDWzxYPoXCXzu

These adresses are valid (even active in the blockchain). However, they don't have a private key.

Then, is it possible to be sure that a public key has a private key (i.e. derived from k*G) ?

Regards,

Mr. Akaki

[j2002ba2]

There are (N-1)/2 x coordinates. The point at infinity - corresponding to private key 0 - has no representation in affine coordinates, and ususally is designated as (0,0).

In secp256k1 x=0 is not on the curve. One could check if point is on the curve by checking the equation y² = x³ + 7 (mod P).

When having only x coordinate, check if x³ + 7 is quadratic residue (mod P). The easiest way is to check if (x³ + 7)^(P-1)/2 = 1 (mod P).

Each P2PKH is spendable in about 2⁹⁷ ways - this is the number of private keys giving the address - both with compressed and uncompressed public keys.
Standard P2WPK ~2⁹⁶ - only compressed public keys are relayed.
P2SH and P2WSH can be spent with every key, in multiple ways.
Valid P2TR is spendable in even more ways.

Given only the address one cannot know if it's spendable by someone.

Edit: missing link

[o_e_l_e_o]

As j2002ba2 has alluded to, you cannot prove that someone does not have a private key for a specific address. Even addresses generated from the public key of 0, or vanity addresses such as 1BitcoinEaterAddressDontSendf59kuE, will have many private keys which allows them to be spent. Although it is incredibly unlikely anyone knows one of the private keys (or indeed, will ever know one of the private keys), you cannot prove that this is the case.

There are other examples of provably unspendable coins, though. For example, OP_RETURN scripts are invalid, meaning there is no way to spend coins sent to such outputs. Another good example is this address: https://blockchair.com/bitcoin/address/s-272edf45031dd498e7b3ae89e11ff21b. Someone has failed to push the public key to the script, instead entering 0x00 and pushing 0 to the stack, which is nonredeemable and therefore these 2,609 BTC are unspendable.

[BlackHatCoiner]

In short: Unless the script is OP_RETURN, there's no way to provably know they're gone for good. Even if you used P2PK for an uncompressed public key that does not fulfill the known equation (unsure if it'll be accepted) or failed to push the public key to stack as said above, you can't know if there's another public key that once hashed gives the same RIPEMD-160.

[o_e_l_e_o]

Unless the script is OP_RETURN, there's no way to provably know they're gone for good.

That's not correct.

Even if you used P2PK for an uncompressed public key that does not fulfill the known equation (unsure if it'll be accepted)

If you succeed in broadcasting a transaction which sends coins to an invalid public key, then those coins are provably lost, since the network will not accept a transaction which spends coins from an invalid public key.

or failed to push the public key to stack as said above, you can't know if there's another public key that once hashed gives the same RIPEMD-160.

In the transaction I linked to above, there is simply no RIPEMD-160 result to compare to. If you click on "Additional info" and then "Op" on the left hand side of the link, you'll see the following opcodes:

Code:

OP_DUP OP_HASH160 0 OP_EQUALVERIFY OP_CHECKSIG

Instead of using 0x14 and pushing the pubkeyhash, they have used 0x00 to push "0" to the stack. If they had used 0x14 and pushed a pubkeyhash of 0000000000000000000000000000000000000000, then that would be the equivalent of sending to the address 1111111111111111111114oLvT2, and could potentially be spent. Instead they have essentially sent coins to nowhere. There is no way to find a pubkeyhash of 0, since RIPEMD-160 always returns a 20 byte output, and so these coins are provably unspendable.

[BlackHatCoiner]

If you succeed in broadcasting a transaction which sends coins to an invalid public key, then those coins are provably lost, since the network will not accept a transaction which spends coins from an invalid public key.

You couldn't spend from the given, invalid public key, but you could spend from a valid public key that once hashed gives the same RIPEMD-160 hash with the hash of the invalid public key. Just like when you can spend from an address with two different private keys (collision) of the same script (P2PKH) I suspect the same can happen using two different scripts. (P2PK & P2PKH even if you didn't lock outputs to a hash)

No?

In the transaction I linked to above, there is simply no RIPEMD-160 result to compare to. If you click on "Additional info" and then "Op" on the left hand side of the link, you'll see the following opcodes

Right... So why did the network accept such scriptPubKey?

[o_e_l_e_o]

You couldn't spend from the given, invalid public key, but you could spend from a valid public key that once hashed gives the same RIPEMD-160 hash with the hash of the invalid public key.

Sending to P2PK does not involve a RIPEMD-160. The locking script is simply a public key followed by OP_CHECKSIG. If the public key is invalid, then you will never find a private key which generates a valid signature.

Right... So why did the network accept such scriptPubKey?

Because it's still a perfectly valid transaction. The network doesn't care about your locking script. It doesn't care if you send coins to an address you cannot access, or to a script hash you can't redeem, or to some other locking script you can't redeem (as in this case). The transaction is still valid.

[BlackHatCoiner]

Sending to P2PK does not involve a RIPEMD-160. The locking script is simply a public key followed by OP_CHECKSIG. If the public key is invalid, then you will never find a private key which generates a valid signature.

Oh, so when you lock funds to a (valid) public key, there's only one private key that satisfies the conditions of creating a valid signature, got it. So, if say, you found a hash collision, you couldn't spend those UTXOs.

The transaction is still valid.

Why is the transaction valid? Why should the funds be burnt completely if the user didn't officially want them burnt?

[o_e_l_e_o]

Why is the transaction valid?

Because the protocol doesn't check output scripts. There are near enough infinite ways that a user can mess up a script and lock themselves out of their funds. There is no possible way to check for every possible error. We use wallet software and clients which only generate transactions in a certain way to protect against this, but if you go outside of this and start trying to generate your own transactions manually, then there is nothing to stop you messing up.

[garlonicon]

As an example, you can look at testnet transaction 43a28148a09582e345af4d8adaf10f48bd8a796196daf439e26f2f8b23722e6f: everything is sent into invalid public key, so the first output is unspendable, but the second is spendable only if you can find another valid public key that hashes to the same value.

[o_e_l_e_o]

As an example, you can look at testnet transaction 43a28148a09582e345af4d8adaf10f48bd8a796196daf439e26f2f8b23722e6f: everything is sent into invalid public key, so the first output is unspendable, but the second is spendable only if you can find another valid public key that hashes to the same value.

So, let's look at the part of the transaction which deals with the outputs, which is as follows:

Code:

0200000000000000002321020000000000000000000000000000000000000000000000000000000000000000ac00000000000000001976a9143625c4a2ea974760a816368fd15de771594476e788ac

02	2 outputs
-----------------------------------------------------------	--------------------------------------------------
0000000000000000	value in satoshis to pay to the first output
23	size of script (35 bytes)
21	push 33 bytes
02000000.....00000000	public key
ac	OP_CHECKSIG
-----------------------------------------------------------	--------------------------------------------------
0000000000000000	value in satoshis to pay the second output
19	size of script (25 bytes)
76	OP_DUP
a9	OP_HASH160
14	push 20 bytes
3625c4a2ea974760a816368fd15de771594476e7	pubkey hash
88	OP_EQUALVERIFY
ac	OP_CHECKSIG

The public key used in the first output hashes to the pubkey hash used in the second output. As garlonicon has said, the first output which is P2PK with an invalid public key is unspendable, whereas the second output with a pubkey hash generated from from the invalid public key would be spendable if you find an address collision (obviously ignoring the fact that both outputs are empty).