Question about public key

[kira4light]

This question may not be related to practical usage, but just for curiosity, if I want to know what the public keys of my addresses are, how should I do that? To my understanding, one address corresponds to one public key, right?

For wallet in electrum, there is a so called "master public key". Is it for the whole wallet? Why can't I find public keys for each address?
For wallet in bitcoin_qt, how to find the public key?
For wallet in blockchain.info, how to find the public key?

I know this is not very important for day-to-day transactions, but I'm just curious about what public keys look like.

[mjc]

The address that people send BTC to is the public key.  There is an associated private key for each address.  The pair make up the key set.

[DeathAndTaxes]

The address that people send BTC to is the public key.  There is an associated private key for each address.  The pair make up the key set.

Incorrect.  The address is a checksum hash of the public key.

To OP the public key is generally hidden from view.  Most transactions work with address directly and public key is only used internally when coins are spent.  The public key is included in the tx so that the tx signature (created by the tx body & private key) can be validated.  There really is no reason you need to know the public key but if you really want to see the public key you can use a tool like pywallet to dump the wallet.

On edit:
Another option is to compute the public key from the private key.  Public keys are deterministic.  Given a specific private key, the proper algorithm (ECC), and a choice of compressed or decompressed one will always compute the same public key.  The public key doesn't need to be stored because it can be recomputed as needed from the private key.  Actually the only thing you need to ensure is never lost is the private key.

[DannyHamilton]

As DeathAndTaxes says, the address is not a public key, it is a hash of a hash of a public key with a 4 byte checksum tacked on and reformatted to base 58.

This question may not be related to practical usage, but just for curiosity, if I want to know what the public keys of my addresses are, how should I do that?

There really isn't an easy way to find it.  I haven't used pywallet, so I'm not sure what options it has, but it might be able to compute public keys for you.  You could extract the private key and enter it at bitaddress.org in the "wallet details" section, but one you've typed your private key into a website, I would immediately consider the associated address to be compromised and would never use it to receive bitcoins again (and would make sure to empty the address of any bitcoins before entering the private key).

To my understanding, one address corresponds to one public key, right?

For general use, that's a safe assumption.

Technically, it may be possible for more than one public key to have the same address, but the odds of generating two different public keys that share an address are astronomically small.  It isn't a realistic event, so you can just assume that there won't be more than one public key for each address.

There is more than one way to represent a public key (compressed or uncompressed).  Each representation has its own address.  Depending on whether you consider each representation a different key or not, it might be valid to say that each public key has two different addresses.

For wallet in electrum, there is a so called "master public key". Is it for the whole wallet? Why can't I find public keys for each address?

I'm not an expert on Electrum, but I believe that it uses a deterministic algorithm for generating addresses.  This means that each new address is based on knowledge of the previously generated private/public key pair.  The "master public key" is simply the first public key in the chain of private/public key pairs. The next address will have it's own public key, but as long as the original "master" key is known all the new keys (and therefore their addresses) can be computed.

For wallet in bitcoin_qt, how to find the public key?
For wallet in blockchain.info, how to find the public key?

I'm not aware of any user tools built into either of these wallets that will display the public key for you.  It isn't a useful piece of information, so nobody has bothered to create an interface to display it.  As I mentioned earlier, pywallet might have a tool for determining public keys, there may be other software that you can find that can compute a secp256k1 ECDSA public key when given the private key.  Generally, I'd recommend not attempting to do so with any address that currently has (or will ever in the future have) any bitcoins.

[J35st3r]

I've been learning about keys (private, public) and addresses this last week and I've put together a python script that will take a private key (in raw hex format, just a 256 bit number) and print the public key, WIF private key (both uncompressed and compressed) and addresses (again both types). Its basically the same functionality as the bitaddress.org wallet details panel, but not tied to a web browser. Its a bit big, but I can paste it up here if anyone is interested (it shows the steps needed to generate each key, though I've not quite got the address generation right yet as it omits any extra leading 1's)

Another useful tool is keyconv (bundled with vanitygen), which will take a private key (WIF format) and print its public key (use the -v option).

[jackjack]

As DeathAndTaxes says, the address is not a public key, it is a hash of a hash of a public key with a 4 byte checksum tacked on and reformatted to base 58.

This question may not be related to practical usage, but just for curiosity, if I want to know what the public keys of my addresses are, how should I do that?

There really isn't an easy way to find it.  I haven't used pywallet, so I'm not sure what options it has, but it might be able to compute public keys for you.  You could extract the private key and enter it at bitaddress.org in the "wallet details" section, but one you've typed your private key into a website, I would immediately consider the associated address to be compromised and would never use it to receive bitcoins again (and would make sure to empty the address of any bitcoins before entering the private key).

Indeed, pywallet gives you the public keys that are inside your wallet

To my understanding, one address corresponds to one public key, right?

For general use, that's a safe assumption.

Technically, it may be possible for more than one public key to have the same address, but the odds of generating two different public keys that share an address are astronomically small.  It isn't a realistic event, so you can just assume that there won't be more than one public key for each address.

Number of valid addresses = 2^160
Number of valid public keys = n-1 ~ 2^256

So:
1 address represents ~2^94 public keys
Odds of generating two different public keys that share an address: ~2^94/2^256 = 1/2^162

PS: This assumes you use only compressed (or uncompressed) keys. The result considering both is very close to this one.

[DrGregMulhauser]

Just to add -- in case the OP might have been wondering about the private key corresponding to an address, which does have a few uses, such as moving from one type of wallet to another -- the private key corresponding to a given address can be extracted from the Bitcoin-Qt client with the console command dumpprivkey followed by the address whose key you're extracting. (The console is available via the 'Debug' window.) The MultiBit client makes this a little easier, with an export function right on the 'Tools' menu.

If you're ever wanting to use the underlying private keys to move from one type of wallet to another, though, you'll need to be fanatically cautious about the hidden change addresses which the clients use to receive change from outgoing transactions. It's entirely possible to copy a slew of private keys, one for each of the receiving addresses you have created, from one client to another, confirm that all the outgoing transactions show up in the new client, and then discover that -- oops -- your balance is lower than it ought to be. (To make matters worse, different clients handle addresses for transaction change in different ways.)

[kira4light]

Just to add -- in case the OP might have been wondering about the private key corresponding to an address,

I was asking about public keys not private keys.

But I think your suggestions are helpful. I'm actually move addresses from bitcoin-qt to electrum. qt is just way too slow...

So you were saying the problems of hidden change addresses, did you personally experience that?

[kira4light]

Its a bit big, but I can paste it up here if anyone is interested

I'm interested

[kira4light]

The address that people send BTC to is the public key.  There is an associated private key for each address.  The pair make up the key set.

Incorrect.  The address is a checksum hash of the public key.

To OP the public key is generally hidden from view.  Most transactions work with address directly and public key is only used internally when coins are spent.  The public key is included in the tx so that the tx signature (created by the tx body & private key) can be validated.  There really is no reason you need to know the public key but if you really want to see the public key you can use a tool like pywallet to dump the wallet.

On edit:
Another option is to compute the public key from the private key.  Public keys are deterministic.  Given a specific private key, the proper algorithm (ECC), and a choice of compressed or decompressed one will always compute the same public key.  The public key doesn't need to be stored because it can be recomputed as needed from the private key.  Actually the only thing you need to ensure is never lost is the private key.

Yeah I know from private key the public key can be computed.

But my acutal question is can you compute public key from just the address? Is there some codes/program to do that?

I guess it's like taking inverse of some hash function...

[DannyHamilton]

I guess it's like taking inverse of some hash function...

That's exactly what it is, and if it was possible then it wouldn't be a very useful hash function.

So, no.  Given only a bitcoin address (and not the private key), it is not currently possible to compute the public key.  Perhaps some day in the future some mathematicians will find serious flaws in both the SHA-256 algorithm AND the RIPEMD-160 algorithm.  Until/unless that ever happens, you can safely assume that the public key cannot be determined from the bitcoin address.

[J35st3r]

Its a bit big, but I can paste it up here if anyone is interested

I'm interested

OK, here it is. I did it mainly as a learning exercise, the code is almost all from pywallet.py so hat tip to jackjack.

Code:

# bitaddr.py - print bitcoin addresses given hex private key
# As a bonus do brainwallet encoding too

# Incorporates code from ...

# jackjack's pywallet.py
# https://github.com/jackjack-jj/pywallet

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

import hashlib

# Code from pywallet.py for bas58 encoding

__b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
__b58base = len(__b58chars)

def b58encode(v):
	""" encode v, which is a string of bytes, to base58.		
	"""

	long_value = 0L
	for (i, c) in enumerate(v[::-1]):
		long_value += (256**i) * ord(c)

	result = ''
	while long_value >= __b58base:
		div, mod = divmod(long_value, __b58base)
		result = __b58chars[mod] + result
		long_value = div
	result = __b58chars[long_value] + result

	# Bitcoin does a little leading-zero-compression:
	# leading 0-bytes in the input become leading-1s
	nPad = 0
	for c in v:
		if c == '\0': nPad += 1
		else: break

	return (__b58chars[0]*nPad) + result

def b58decode(v, length):
	""" decode v into a string of len bytes
	"""
	long_value = 0L
	for (i, c) in enumerate(v[::-1]):
		long_value += __b58chars.find(c) * (__b58base**i)

	result = ''
	while long_value >= 256:
		div, mod = divmod(long_value, 256)
		result = chr(mod) + result
		long_value = div
	result = chr(long_value) + result

	nPad = 0
	for c in v:
		if c == __b58chars[0]: nPad += 1
		else: break

	result = chr(0)*nPad + result
	if length is not None and len(result) != length:
		return None

	return result

# end of bitcointools base58 implementation

# https://bitcointalk.org/index.php?topic=23241.0
# Actually this is also from pywallet.py

class CurveFp( object ):
		def __init__( self, p, a, b ):
		 	self.__p = p
		 	self.__a = a
		 	self.__b = b

		def p( self ):
		 	return self.__p

		def a( self ):
		 	return self.__a

		def b( self ):
		 	return self.__b

		def contains_point( self, x, y ):
		 	return ( y * y - ( x * x * x + self.__a * x + self.__b ) ) % self.__p == 0

class Point( object ):
		def __init__( self, curve, x, y, order = None ):
		 	self.__curve = curve
		 	self.__x = x
		 	self.__y = y
		 	self.__order = order
		 	if self.__curve: assert self.__curve.contains_point( x, y )
		 	if order: assert self * order == INFINITY
	
		def __add__( self, other ):
		 	if other == INFINITY: return self
		 	if self == INFINITY: return other
		 	assert self.__curve == other.__curve
		 	if self.__x == other.__x:
		 	 	if ( self.__y + other.__y ) % self.__curve.p() == 0:
		 	 	 	return INFINITY
		 	 	else:
		 	 	 	return self.double()

		 	p = self.__curve.p()
		 	l = ( ( other.__y - self.__y ) * \
		 	 	 	 	inverse_mod( other.__x - self.__x, p ) ) % p
		 	x3 = ( l * l - self.__x - other.__x ) % p
		 	y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
		 	return Point( self.__curve, x3, y3 )

		def __mul__( self, other ):
		 	def leftmost_bit( x ):
		 	 	assert x > 0
		 	 	result = 1L
		 	 	while result <= x: result = 2 * result
		 	 	return result / 2

		 	e = other
		 	if self.__order: e = e % self.__order
		 	if e == 0: return INFINITY
		 	if self == INFINITY: return INFINITY
		 	assert e > 0
		 	e3 = 3 * e
		 	negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
		 	i = leftmost_bit( e3 ) / 2
		 	result = self
		 	while i > 1:
		 	 	result = result.double()
		 	 	if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
		 	 	if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
		 	 	i = i / 2
		 	return result

		def __rmul__( self, other ):
		 	return self * other

		def __str__( self ):
		 	if self == INFINITY: return "infinity"
		 	return "(%d,%d)" % ( self.__x, self.__y )

		def double( self ):
		 	if self == INFINITY:
		 	 	return INFINITY

		 	p = self.__curve.p()
		 	a = self.__curve.a()
		 	l = ( ( 3 * self.__x * self.__x + a ) * \
		 	 	 	 	inverse_mod( 2 * self.__y, p ) ) % p
		 	x3 = ( l * l - 2 * self.__x ) % p
		 	y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
		 	return Point( self.__curve, x3, y3 )

		def x( self ):
		 	return self.__x

		def y( self ):
		 	return self.__y

		def curve( self ):
		 	return self.__curve
		
		def order( self ):
		 	return self.__order
		 	
INFINITY = Point( None, None, None )

def inverse_mod( a, m ):
		if a < 0 or m <= a: a = a % m
		c, d = a, m
		uc, vc, ud, vd = 1, 0, 0, 1
		while c != 0:
		 	q, c, d = divmod( d, c ) + ( c, )
		 	uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
		assert d == 1
		if ud > 0: return ud
		else: return ud + m

# secp256k1
_p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL
_r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L
_b = 0x0000000000000000000000000000000000000000000000000000000000000007L
_a = 0x0000000000000000000000000000000000000000000000000000000000000000L
_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L
_Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

class Signature( object ):
		def __init__( self, r, s ):
		 	self.r = r
		 	self.s = s
		 	
class Public_key( object ):
		def __init__( self, generator, point ):
		 	self.curve = generator.curve()
		 	self.generator = generator
		 	self.point = point
		 	n = generator.order()
		 	if not n:
		 	 	raise RuntimeError, "Generator point must have order."
		 	if not n * point == INFINITY:
		 	 	raise RuntimeError, "Generator point order is bad."
		 	if point.x() < 0 or n <= point.x() or point.y() < 0 or n <= point.y():
		 	 	raise RuntimeError, "Generator point has x or y out of range."

		def verifies( self, hash, signature ):
		 	G = self.generator
		 	n = G.order()
		 	r = signature.r
		 	s = signature.s
		 	if r < 1 or r > n-1: return False
		 	if s < 1 or s > n-1: return False
		 	c = inverse_mod( s, n )
		 	u1 = ( hash * c ) % n
		 	u2 = ( r * c ) % n
		 	xy = u1 * G + u2 * self.point
		 	v = xy.x() % n
		 	return v == r

class Private_key( object ):
		def __init__( self, public_key, secret_multiplier ):
		 	self.public_key = public_key
		 	self.secret_multiplier = secret_multiplier

		def der( self ):
		 	hex_der_key = '06052b8104000a30740201010420' + \
		 	 	 	 	 	 	 	 	'%064x' % self.secret_multiplier + \
		 	 	 	 	 	 	 	 	'a00706052b8104000aa14403420004' + \
		 	 	 	 	 	 	 	 	'%064x' % self.public_key.point.x() + \
		 	 	 	 	 	 	 	 	'%064x' % self.public_key.point.y()
		 	return hex_der_key.decode('hex')

		def sign( self, hash, random_k ):
		 	G = self.public_key.generator
		 	n = G.order()
		 	k = random_k % n
		 	p1 = k * G
		 	r = p1.x()
		 	if r == 0: raise RuntimeError, "amazingly unlucky random number r"
		 	s = ( inverse_mod( k, n ) * \
		 	 	 	 	( hash + ( self.secret_multiplier * r ) % n ) ) % n
		 	if s == 0: raise RuntimeError, "amazingly unlucky random number s"
		 	return Signature( r, s )

curve_256 = CurveFp( _p, _a, _b )
generator_256 = Point( curve_256, _Gx, _Gy, _r )
g = generator_256

def hexprivkey2addr(privkey_hex):
	print privkey_hex, " priv key HEX"

	# Encode the private key in WIF see https://en.bitcoin.it/wiki/Base58Check_encoding

	data_hex = "80" + privkey_hex
	data_bin = data_hex.decode('hex')

	hash = hashlib.sha256(hashlib.sha256(data_bin).digest()).digest()
	sha_hex = hash.encode('hex_codec')

	step2_hex = data_hex + sha_hex[:8]

	privkey = b58encode(step2_hex.decode('hex'))
	print privkey, " private key WIF"

	# Now print the compressed WIF private key
	# bitaddress.org appends 01 so try that ...

	data_hex = "80" + privkey_hex + "01"
	data_bin = data_hex.decode('hex')

	hash = hashlib.sha256(hashlib.sha256(data_bin).digest()).digest()
	sha_hex = hash.encode('hex_codec')

	step2_hex = data_hex + sha_hex[:8]

	privkey = b58encode(step2_hex.decode('hex'))
	print privkey, " private key WIF (comp)"
	
	
	# ===========================================
	# The next step is to convert to a public key
	# ===========================================
	
	secret = int(privkey_hex,16)	# Need this as decimal number

	# generate pubkey
	pubkey = Public_key( g, g * secret )
	# print 'pubkey', hex(pubkey.point.x()), hex(pubkey.point.y())
	
	# This is clunky, there is probably a better way ...
	x_hex = hex(pubkey.point.x())
	x_hex = x_hex[2:]	# Remove leading 0x
	x_hex = x_hex[:-1]	# Remove trailing L
	# Pad with leading 0's to 64 chars...
	x_hex = x_hex.zfill(64)
	# print "x", x_hex
	y_hex = hex(pubkey.point.y())
	y_hex = y_hex[2:]	# Remove leading 0x
	y_hex = y_hex[:-1]	# Remove trailing L
	# Probably need to pad with leading 0's to 64 chars...
	y_hex = y_hex.zfill(64)
	# print "y", y_hex
	
	pubkey_hex = "04" + x_hex + y_hex
	print pubkey_hex, " public key"
	
	# ==================
	# Address generation
	# ==================
	
	pubkey = pubkey_hex

	data_bin = pubkey.decode('hex')

	# First step is a SHA256
	data_bin = hashlib.sha256(data_bin).digest()

	# Second step is RIPEMD160
	hash = hashlib.new('ripemd160')
	hash.update(data_bin)
	hash_digest = hash.digest()
	hash_hex = hash.hexdigest()

	print hash_hex + "  uncompressed hash (pubkey)"

	# Now encode the address

	data_hex = "00" + hash_hex	# 00 is version byte, could also be 05
	data_bin = data_hex.decode('hex')

	hash = hashlib.sha256(hashlib.sha256(data_bin).digest()).digest()
	sha_hex = hash.encode('hex_codec')
	step2_hex = data_hex + sha_hex[:8]

	print b58encode(step2_hex.decode('hex')), " address"

	# ============================================================================================
	# Now do the same for the COMPRESSED public key (see https://bitcointalk.org/index.php?topic=205490.0)
	# ============================================================================================

	lastchar = pubkey[-2:]
	val = lastchar.decode('hex')
	if (ord(val)%2):
		# print "odd"
		xpubkey = "03" + pubkey[2:66]	
	else:
		# print "even"
		xpubkey = "02" + pubkey[2:66]	

	print xpubkey + "  comp pubkey"

	data_bin = xpubkey.decode('hex')

	# First step is a SHA256
	data_bin = hashlib.sha256(data_bin).digest()

	# Second step is RIPEMD160
	hash = hashlib.new('ripemd160')
	hash.update(data_bin)
	hash_digest = hash.digest()
	hash_hex = hash.hexdigest()		# Saves the encoding step

	print hash_hex + "  hash (compressed pubkey)"

	# Now encode the address

	data_hex = "00" + hash_hex	# 00 is version byte, could also be 05
	data_bin = data_hex.decode('hex')

	hash = hashlib.sha256(hashlib.sha256(data_bin).digest()).digest()
	sha_hex = hash.encode('hex_codec')
	step2_hex = data_hex + sha_hex[:8]

	print b58encode(step2_hex.decode('hex')), " compressed address"
	
def brainwallet(keyphrase):
	print "keyphrase=[" + keyphrase + "]"
	privkey_bin = hashlib.sha256(keyphrase).digest()		# Single sha256 (standard brain algorithm)
	# privkey_bin = hashlib.sha256(privkey_bin).digest()	# Double sha256 (not useful)

	# privkey_hex = hashlib.sha256(keyphrase).hexdigest()	# Can generate hex directly
	privkey_hex = privkey_bin.encode('hex_codec')			# Alternatively from bin
	hexprivkey2addr(privkey_hex)
	
	# ============================= main ==============================
if __name__ == "__main__":
	# Examples
	hexprivkey2addr("0000000000000000000000000000000000000000000000000000000000000001")
	print
	hexprivkey2addr("00000000000000000000000000000000000000000000000000000000000000b6")	# Has a 11 prefix address
	print
	hexprivkey2addr("deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef")
	print
	brainwallet("correct horse battery staple")

[DrGregMulhauser]

But I think your suggestions are helpful. I'm actually move addresses from bitcoin-qt to electrum. qt is just way too slow...

So you were saying the problems of hidden change addresses, did you personally experience that?

Just to follow up -- yes, I personally experienced this when experimenting with a move from Bitcoin-Qt to Multibit. If you dump the private keys only for the addresses displayed in the Bitcoin-Qt GUI list of receiving addresses and then import them into anything else (e.g., Multibit), you can watch the transaction list rebuild in the new client, and everything will look OK at first as those transactions reappear, yet the total balance will be wrong.

The reason?

The list of receiving addresses displayed in the main interface of Bitcoin-QT does not include all the extra addresses created behind the scenes for receiving change. Those addresses are not displayed directly in the main GUI. So, exporting the private keys only for the receiving addresses which you can see in the GUI does not give you a complete set. As a result, if you move that partial set to a new client, your total balance will be missing all the amounts you received back to those hidden change addresses.

Although this is just a basic feature of how Bitcoin transactions work -- total inputs and outputs need to balance out -- the result when trying to move between clients can be a little counter-intuitive if you're not expecting it and look only at the GUI list of receiving addresses. This also explains some of the horror stories about people spending a small amount from a paper wallet and then accidentally losing the rest of their balance: they didn't realise that spending a small amount from the paper wallet meant that wallet became worthless, because the remaining balance from their transaction went to a different change address. (These kinds of details also mean it's often more straightforward just to transfer an entire balance to yourself when moving between wallets, rather than trying to preserve all of the original wallet's transaction history, addresses, etc.)

[AliceWonder]

http://gobittest.appspot.com/Address

You can put a private key in there and it will spit out all kinds of groovy things including public key.

However, putting your private key into web forms is probably not a habit you want to get into.
But that website is great for debugging code, to validate that code you write produces the right results along the way to base58 address generation.