Prize for importing private key [WON]

[Hal]

This is a base58 encoded plain private key (256 bit value from a "key" entry in my wallet) worth 20 BTC. We're now at block 109180. Let's see how long it takes for someone to input the key and collect the bitcoins.

2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

ETA: this is wrong, the correct value is later in the thread

[1714928339]

1714928339

[1714928339]

1714928339

[Hal]

The corresponding bitcoin address is 17kzeh4N8g49GFvdDzSf8PjaPfyoD1MndL. Here's the blockexplorer link: http://blockexplorer.com/address/17kzeh4N8g49GFvdDzSf8PjaPfyoD1MndL. When the balance goes to zero, someone's got it.

[grondilu]

Damn it Hal, that's very mean.  Now we have to work on this or we'll look like fools.

I think I could manage to do that by tweaking the bitcoin code and recompiling.  But I'd have to use a brand new wallet cause I don't like to mess with my wallet.

PS.  pff  I give up.  I've tried to tweak the code for generating a new address.

Code:

vector<unsigned char> GenerateNewKey()
{
    RandAddSeedPerfmon();
    CKey key;
    key.MakeNewKey();
    if (!AddKey(key))
	throw runtime_error("GenerateNewKey() : AddKey failed");

    //  this is what I tried
    unsigned int nSize = i2d_ECPrivateKey(key.pkey, NULL);  // I had to set pkey public in Ckey
    if (!nSize)
	throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey failed");
    CPrivKey vchPrivKey(nSize, 0);
    unsigned char* pbegin = &vchPrivKey[0];
    vector<unsigned char>& vchRet;
    DecodeBase58("2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy", vchRet);
    strcpy(pbegin, vchRet);  
    key.SetPrivKey(vchRet); 
    //  end of what I tried

    return key.GetPubKey();
}

The idea was to create the private key with the getnewaddress command.

It doesn't compile since vchRet is not a CPrivKey object.   I don't understand well enough what CPrivKey is.

Good luck to other people who will try.

[myrkul]

Correct me if I'm wrong, but aren't Bitcoin private keys 279 bytes long?

Base 58. Each digit in that string can hold a lot of numbers: 123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ

It's a great way to have a LOT of possibilities, in a small space, with little chance of error when hand-entering data.

So, it is 279 bytes long, if it were converted out. (or, it should be. I don't feel like doing the math at the moment)

[theymos]

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

[kvk]

As far i understand the bitcoin, it's not really possible to redeem the coins with only private key, the script expects full public key to compare with hash160 and to verify signature. Since no coins were redeemed with this address, the pubkey is not known and the task of reversing the hash is impossible.

[myrkul]

The corresponding bitcoin address is 17kzeh4N8g49GFvdDzSf8PjaPfyoD1MndL. Here's the blockexplorer link: http://blockexplorer.com/address/17kzeh4N8g49GFvdDzSf8PjaPfyoD1MndL. When the balance goes to zero, someone's got it.

Address is the public key. He's given us everything we need, we just need to figure out how to stick the private key into a wallet, and then send ourselves the coins.

[theymos]

As far i understand the bitcoin, it's not really possible to redeem the coins with only private key, the script expects full public key to compare with hash160 and to verify signature. Since no coins were redeemed with this address, the pubkey is not known and the task of reversing the hash is impossible.

ECDSA public keys are derived from their private keys. It makes the challenge even more difficult, though.

Address is the public key. He's given us everything we need, we just need to figure out how to stick the private key into a wallet, and then send ourselves the coins.

The address is the hash of the public key. You need the full public key to spend it.

[Binford 6100]

so it goes like this?
1) base58decode the private key
2) find out the public key
3) modify your wallet.dat to include the key pair
4) rescan the blockchain
5) spend

btw added a btc to the bounty (hope hal does not spend it

[myrkul]

The address is the hash of the public key. You need the full public key to spend it.

Ahhh... Interesting. Deceptively simple problem he's given us... essentially, we need to re-mine his block, then?

[m0mchil]

Hal, could you please provide HEX encoded private key ?

[0x6763]

As far i understand the bitcoin, it's not really possible to redeem the coins with only private key, the script expects full public key to compare with hash160 and to verify signature. Since no coins were redeemed with this address, the pubkey is not known and the task of reversing the hash is impossible.

ECDSA public keys are derived from their private keys. It makes the challenge even more difficult, though.

I wrote some code (that I'll share after I get the 20 BTC, haha) that will generate a public key from a private key.  I've tested it on multiple private keys in my wallet and it always generated the correct public key.  The problem is that it doesn't generate a public key that makes the address Hal provided.  Either my base58 decoding function is wrong, or Hal's base58 encoding function is wrong, or he gave us the wrong private key.

Address is the public key. He's given us everything we need, we just need to figure out how to stick the private key into a wallet, and then send ourselves the coins.

The address is the hash of the public key. You need the full public key to spend it.

The private key was really the only info we needed, since the public key could be calculated from that, and then the address created from that, and the block chain could be searched for any payments to that address.

[m0mchil]

0x6763, what public key do you get?

17KzV7RfQnmqcFC3cnS3RqWXQm1CREtNmj or something else?

[0x6763]

0x6763, what public key do you get?

17KzV7RfQnmqcFC3cnS3RqWXQm1CREtNmj or something else?

Yeah, that's it.

[Pieter Wuille]

Correct me if I'm wrong, but aren't Bitcoin private keys 279 bytes long?

As I understand it, private keys are indeed 279 bytes long (though with some redundancy in them), public keys are 0x04 + 32-byte X-coordinate + 32-byte Y-coordinate (totalling 65 bytes, 520 bits), and addresses contain a 20-byte (160 bit) hash of the public key.

Not sure what you've given us Hal, but as it is only 256 bit, I doubt it's a private key.

PS: base58 encoding is more efficient than hex encoding, but it still can't turn a 279-byte key into a 44-character string...

[0x6763]

Correct me if I'm wrong, but aren't Bitcoin private keys 279 bytes long?

As I understand it, private keys are indeed 279 bytes long (though with some redundancy in them), public keys are 0x04 + 32-byte X-coordinate + 32-byte Y-coordinate (totalling 65 bytes, 520 bits), and addresses contain a 20-byte (160 bit) hash of the public key.

Not sure what you've given us Hal, but as it is only 256 bit, I doubt it's a private key.

PS: base58 encoding is more efficient than hex encoding, but it still can't turn a 279-byte key into a 44-character string...

The private key is actually just a 256-bit number. The public key is two 256-bit numbers.  All of those other bytes that Bitcoin is using just contains redundant information about the elliptic curve (redundant since Bitcoin already knows the curve info anyway, and therefore doesn't need it stored with the key).

[0x6763]

If Hal did give us the wrong private key on accident, he might want to remove that key pair from his wallet so he doesn't accidentally give that address out in the future, since anyone else could spend any money sent to that address.

[0x6763]

Haha, the stakes are a little higher now. Another 1.05 BTC went to that address. http://blockexplorer.com/address/17kzeh4N8g49GFvdDzSf8PjaPfyoD1MndL

[jav]

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

That website claims 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46 is the hash version.
What exactly is being calculated there? I wrote my own decode58 code and I get this value:
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

Represented in binary the blockexplorer hex is only 215 bit, whereas my hex is 253 bit. Add another 3 leading zeroes and you get 256 bit.

Here is the Haskell code I used to decode the string:


import Maybe

decode :: [Char] -> [(Char, Integer)] -> Integer
decode s mapping = worker (reverse s) mapping bases
    where
    bases = iterate (58 *) 1
    worker :: [Char] -> [(Char, Integer)] -> [Integer] -> Integer
    worker [] _ _ = 0
    worker (c:cs) mapping (b:bs) =
        (fromJust (lookup c mapping)) * b + (worker cs mapping bs)

main = do
    let chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    let mapping = zip chars [0..]
    print $ decode "2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy" mapping

[0x6763]

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

That website claims 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46 is the hash version.
What exactly is being calculated there? I wrote my own decode58 code and I get this value:
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

Represented in binary the blockexplorer hex is only 215 bit, whereas my hex is 253 bit. Add another 3 leading zeroes and you get 256 bit.

Theymos's link doesn't make any sense, since 2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy is not an address, but is instead a base58 encoded 256-bit number.  Bitcoin addresses are much shorter than that base58 encoded number.

I'm also getting 1b66ff9f63ace537b537be1f7f0cb585649c226c72eeff43d59fac4677be50ca when I decode the base58 string.

[0x6763]

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

That website claims 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46 is the hash version.
What exactly is being calculated there? I wrote my own decode58 code and I get this value:
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

Represented in binary the blockexplorer hex is only 215 bit, whereas my hex is 253 bit. Add another 3 leading zeroes and you get 256 bit.

Theymos's link doesn't make any sense, since 2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy is not an address, but is instead a base58 encoded 256-bit number.  Bitcoin addresses are much shorter than that base58 encoded number.

I'm also getting 1b66ff9f63ace537b537be1f7f0cb585649c226c72eeff43d59fac4677be50ca when I decode the base58 string.

However it does show that our base58 decoding functions must be functioning the same as Theymos's (which I suspect is correct as it's consistent with other instances of the base58 decoding that I've seen):

Code:

Ours:  1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA
Theymos: 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46

(the first and last 4 bytes are removed after decoding the base58 encoded data in attempt to extract the hash of the public key, which is obviously incorrect here)

Currently my conclusion is that Hal made an error either in finding the correct private key that goes along with the address he shared, or in encoding the key in base58.

[m0mchil]

Last four bytes of address are check sum. Not sure what happens to first byte though.

I guess there is some minor discrepancy between what Hal used to 'encode' his private key and what we use.

[grondilu]

To me the difficult part is the modification of the wallet.dat file.

To decode base58, one can use my bash library:

Code:

#!/bin/bash
# 
# Requires bc, dc, openssl, xxd
#

base58=({1..9} {A..H} {J..N} {P..Z} {a..k} {m..z})
bitcoinregex="^[$(printf "%s" "${base58[@]}")]{34}$"

decodeBase58() {
    local s=$1
    for i in {0..57}
    do s="${s//${base58[i]}/ $i}"
    done
    dc <<< "16o0d${s// /+58*}+f" 
}

encodeBase58() {
    # 58 = 0x3A
    bc <<<"ibase=16; n=${1^^}; while(n>0) { n%3A ; n/=3A }" |
    tac |
    while read n
    do echo -n ${base58[n]}
    done
}

checksum() {
    xxd -p -r <<<"$1" |
    openssl dgst -sha256 -binary |
    openssl dgst -sha256 -hex |
    sed 's/^.* //' |
    head -c 8
}

checkBitcoinAddress() {
    if [[ "$1" =~ $bitcoinregex ]]
    then
        h=$(decodeBase58 "$1")
        checksum "00${h::${#h}-8}" |
        grep -qi "^${h: -8}$"
    else return 2
    fi
}

hash160() {
    openssl dgst -sha256 -binary |
    openssl dgst -rmd160 -hex |
    sed 's/^.* //'
}

hash160ToAddress() {
    printf "%34s\n" "$(encodeBase58 "00$1$(checksum "00$1")")" |
    sed "y/ /1/"
}

publicKeyToAddress() {
    hash160ToAddress $(
    openssl ec -pubin -pubout -outform DER |
    tail -c 65 |
    hash160
    )
}

timestamp() {
    hash160ToAddress "$(hash160)"
}

$ decodeBase58 2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

$ !! |xxd -r -p |base64
G2b/n2Os5Te1N74ffwy1hWScImxy7v9D1Z+sRne+UMo=


FWIW

[0x6763]

I'm not even bothering to put it in my wallet.  I'm just going to create a transaction that spends it (sending it to one of the addresses already in my wallet) as soon as I get the correct private key.  Putting it in my wallet would mean requiring bitcoin to rescan the block chain so it knows that it has another 21.05+ BTC to spend, and then after it's finally done doing that, I'd have to spend my entire bitcoin balance to a new address just to make sure that the official Bitcoin software spends the specific bitcoins we're all trying to get.  Just sending out a transaction with my own custom code is a lot easier and faster. 

[grondilu]

Ok but how do you plan on making a transaction without having the key in your wallet ?

[xenon481]

When trying to decode the Private Key, I'm not getting the same hex that y'all are. But that's because, apparently, our base58 alphabets are different from eachother.

My base58 alphabet (the one I see all over Google): "123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

When I use your alphabet, I get the same thing y'all are. Why are the cases reversed between yours and my alphabets?

[Pieter Wuille]

I've also created some code that generates a "full" (279-byte) private key based on a given 256-bit private key number (using openssl's EC_KEY_generate_key after setting the private key as a parameter). The problem is (more or less expected?) that the corresponding public key varies each time.

Are we sure that a public key can be generated deterministically from *just* the 256-bit private number? It is stored in full in the 279-byte version, which may be becsause multiple public keys can correspond to the same private number.

I do wonder why/how 0x6763 and m0mchil managed to get the same (wrong?) public key from that private number. Maybe I'm still not getting something

[grondilu]

My base58 alphabet (the one I see all over Google): "123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

Just use Satoshi's alphabet:

$ grep abcde bitcoin/src/base58.h
static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

[0x6763]

Ok but how do you plan on making a transaction without having the key in your wallet ?

I've written almost a complete bitcoin client in Clojure.  And since Clojure has a REPL, I can build any Bitcoin data structure I want as fast as I can type the function name and the pieces of information that needs to go in it, and can send it out on the wire just as easily.  I don't have to bother with the write, compile, run cycle.  I just write, and it evaluates when I press "Enter", like Python's REPL.  And for this little challenge I quickly wrote up a function that already has all of the needed information, except for the public key, to build a transaction to spend these 21.05+ BTC.  All I have to do is give the function the correct private key, and it will calculate the public key, put it in the script in the transaction input, and spend those bitcoins.

I suppose I didn't update my function for the two new payments that address received, yet, though, so unless I do that, that money will still be available for others.

One thing to note is that if I don't put it in my wallet, it means that any future money going to that address won't automatically become part of my balance.  Another thing to note is that if I someone to put it in their wallet, their balance could go up or down as other people pay that address money, and others that have the private key spend the money available to that address.

[0x6763]

Someone sent another 0.01 BTC to that address, lol.

[alkor]

Someone sent another 0.01 BTC to that address, lol.

Yes, that was my one cent.

[ribuck]

My base58 alphabet (the one I see all over Google): "123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

That alphabet is "all over Google" because it's the one that Flickr uses. But if you search for "base 58" bitcoin then the correct variation will be "all over Google".

Better still, ask the source code for the authoritative answer:
https://github.com/bitcoin/bitcoin/blob/master/base58.h

[Mike Hearn]

Yeah, I got to the same point :-( Looks like either we're all missing something fundamental, or Hal gave out an incorrect private key.

Seems we're all doing it with private code, interesting.

[Hal]

Sorry! I did screw up the encoding. Here is the 256-bit private key in big-endian hex:

C85AFBACCF3E1EE40BDCD721A9AD1341344775D51840EFC0511E0182AE92F78E

My new attempt to base58 encode this is:

EV71KQfoePBeWT79sV1VE7fWRgv1KNUxTNapH6ZbaRfB

That's custom code, maybe somebody could check it.

To apologize, I've added 30 BTC to the address. We're now at block 109352.

The reason I did it this way is that it would be a good format for passing around or backing up bitcoins.

BTW the new version of Bitcoin has a -rescan switch to find all txns that are for wallet keys. Only takes a couple minutes.

[Mike Hearn]

Why thankyou Hal, you are a scholar and a gentleman. That was an unexpectedly profitable Sunday evening! If we ever meet I will be glad to buy you drinks for the evening.

Now I'm wondering what I should do with this ⓑ50 ? I quite like this challenge concept ... I'm thinking I should make the coins available to somebody who can craft a particular type of transaction, but it'd need a miner willing to incorporate it.

Anyone else got ideas for the next step for these coins?

[tcatm]

Donate them to someone making a patch for importing private keys into the wallet.

[Binford 6100]

The reason I did it this way is that it would be a good format for passing around or backing up bitcoins.

yes, this way is much more convenient than dealing with all the wallet data

a private key could fit into a QR code while the smallest amount of space needed by a wallet is always around 30 kB

Now I'm wondering what I should do ...

could you, please, publish your code? : )

[m0mchil]

I really can't hide my disappointment   waited hours for Hal to provide the correct key - and to see that someone got it 3 blocks earlier. Should master my 'F5' key.

There is a rather old patch (SVN 195) at https://github.com/m0mchil/bitcoin-impex-keys which supports RPC initiated exporting and importing of keys in PEM format. It also exports corresponding block numbers to speed up import.

The reason I didn't announce it back then is that it doesn't solve the double spend problem. The patch could be easily modified to not remove exported key from wallet (it does so at the moment) allowing copying of keys.

If anyone's interested I can easily add import method using just private key.

[Mike Hearn]

Sorry m0mchil, I have to admit I was surprised when I reloaded the page and saw Hal had replied. I just got lucky.

(edit to rephrase question)

Though fun I don't really understand the point of this. For backing your wallet you can just shut down the software and make a copy of wallet.dat. For moving coins between different wallets you can just send them as regular transactions.

Is there a use case for exporting private keys I haven't grokked yet?

[Mike Hearn]

By the way, I did this with a private Java implementation of BitCoin. I'm working on getting it open sourced, but because my employer owns the code I have to get various approvals from them first.  So right now I can't release the code, sorry.

[0x6763]

Darn, I missed it!  And it even had another 30 BTC!

Oh well, at least it was interesting.  Congratulations, [mike]!

[Hal]

Congratulations Mike! That was fast, you got the bitcoins only two blocks later. Not only that, you had to create a transaction with 5 inputs, corresponding to the 5 payments into the address. Do you mind telling how you did it?

As far as use cases, you could email someone some bitcoins without knowing their address, or even if they hadn't tried Bitcoin yet. Some people want to print bitcoins on paper and put them in a safe for long term security. If you could pay bitcoins to a newly created key, and export the private key, it would be a backup that would be safe against wallet theft. Lots of people have asked for this.

[Mike Hearn]

I have an implementation of the BitCoin protocol written in Java that is fairly easy to use. The code I wrote to take these coins looked like:

Code:

        ECKey halsKey = new ECKey(Base58.decodeToBigInteger("2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy"));
        wallet.addKey(halsKey);

        NetworkConnection conn = new NetworkConnection(params);
        BlockChain chain = new BlockChain(params, wallet);
        Peer peer = new Peer(params, conn, chain);
        peer.start();
        peer.startBlockChainDownload().await();
        
        Address dest = new Address(params, "my address");
        Transaction tx = wallet.createSend(dest, wallet.getBalance(), dest);
        peer.broadcastTransaction(tx);
        wallet.confirmSend(tx);

....

    public ECKey(BigInteger privKey) {
        priv = privKey;
        pub = ecParams.getG().multiply(priv).getEncoded();
    }

I know I'm not the only one with an independent implementation of the system by this point. Like I said, I'm hoping to be able to open source it, but still need some approvals.

On use cases: I wonder if it would be easier to make the client support having multiple independent wallets. Import/export of private keys isn't enough for those use cases, you have to be able to delete the key from your own wallet too.

I'm still not 100% convinced, but OK, I will defer to the wisdom of the crowd on this one. It can't hurt. I wouldn't normally post bounties as you have to be pretty precise when specifying them, but here we go. If somebody can see a better design or more precise spec let me know.

Bounty for the 50 coins

The first person to get a patch merged by Gavin into the core software that allows import/export of wallet files, via the GUI on all 3 supported platforms, defined in the following manner wins the coins.

Export should write out the private keys and simultaneously delete those keys from the wallet. You are required to do the export, then the import, then only do the delete if the import passes. This is to guard against trivial failures like out of disk space. The bounty already requires import to be written so this is not much more work.

The format should be a text file with unix line endings and a default extension of .bitkeys that looks like this:

Code:

# Comment
v=1
base58 encoded privkey,block number  # comment
base58 encoded privkey,block number
base58 encoded privkey,block number
# Comment

where the block number is the earliest block in which that address received coins, to make scanning for transactions faster by avoiding the need to check the entire block chain. Characters after a hash symbol should be ignored, the first non-comment line should be v=1. If the first line is not v=1 then the file should be rejected and the user told to upgrade their software.

I'll also throw in 50 of my own coins for a web page that, in JavaScript, accepts such a file (copy/paste into a text area), formats a file like the above into binary and then generates a QRcode using the html5 canvas library available here:

   http://www.cipherbrain.be/qrcode/

In other words, I should be able to take a .bitkeys file, copy/paste it into a web page and without any network traffic be then able to print my keys out onto paper. Don't cheat and use your own server side code or Google chartserver - I want to be able to trust that the keys never left my computer. HTML5 app because that way it'll work on everyones systems.

[edits: complicate the text format a bit to allow for future upgrades, require key deletion]

[ribuck]

Is there a use case for exporting private keys I haven't grokked yet?

Suppose you want to export all your generated coins to another wallet, while keeping them pristine (i.e. without a transaction history).

[Gavin Andresen]

Bounty for the 50 coins. The first person to get a patch merged by Gavin into the core software that allows import/export of wallet files, via the GUI on all 3 supported platforms, defined in the following manner wins the coins. Obviously not very much but I guess it's symbolic

The format should be a CSV file (unix line endings) that looks like this:

Code:

base58 encoded privkey,block number,block number....
base58 encoded privkey,block number,block number....
base58 encoded privkey,block number,block number....

where the block numbers are the blocks in which there are unspent outputs sending to that key.

CSV file with the private key and block numbers is a good idea, although for it to be a valid CSV file then it needs to have a fixed number of columns.

I'd modify the design slightly to be just:
base58 encoded privkey,block number
... where block number is the block number of the earliest input (that'll save rescanning time-- you probably always want to rescan from the earliest block number, anyway, in case more payments were sent after you exported the key).

Also what do you mean by "export" -- write and then remove the keys from the wallet?  Write a newly generated key and generate a payment-to-that-key for a given amount of coins?

I think any code that removes keys from the wallet (or generates payments to keys that are never added to the wallet) needs to be structured as two distinct steps:
1. Write the keys to <destination>
2. Read <destination> to make sure it is valid, and, if it is, delete the corresponding keys from the wallet (or generate the send-to-self txn).

[Binford 6100]

i had no problems to read the message in the bigger QR code with a cheap smartphone.
i believe the message was bigger as the private key from Hal that started this quest.
this is how i imagine to print bitcoins : )))

i tried the paperback tool but with the size of wallet and the fact that paperback is more a joke than a usefull tool it was a dead end research. with the existing key dump tool

handling multiple wallets would require massive gui changes.
i'd rather
- tap/untap keys in wallet (not to delete them right away, just mark them as do not use/spend balances with those keys)
- import/export key from clipboard/dialog/file
- import keys from CSV file

[Mike Hearn]

Also what do you mean by "export" -- write and then remove the keys from the wallet?  Write a newly generated key and generate a payment-to-that-key for a given amount of coins?

Good point. For now I think just get the data out (50 coins isn't that much after all). Being able to simultaneously export and delete the keys seems like a nice improvement. No need to have the new key functionality as you can always just make a payment to yourself in the GUI and then export that, it can be done with existing tools.

I will update the spec to reflect your suggested changes. BTW valid CSV also requires DOS line endings, technically, but ... ew

[Mike Hearn]

Actually I changed my mind, deletion of the keys will have to be a requirement, otherwise exporting them will render your wallet useless as bitcoin will try and spend those coins and you can't stop it ....

[LZ]

If anyone's interested I can easily add import method using just private key.

Yeah, it will be good.

[Binford 6100]

Actually I changed my mind, deletion of the keys will have to be a requirement, otherwise exporting them will render your wallet useless as bitcoin will try and spend those coins and you can't stop it ....

that is a valid point
but "delete" only when export returns OK (the key is written somewhere)

i can imagine to click esc on the export dialog (lack of coffee?) and the key could be lost

[pla]

The format should be a CSV file (unix line endings) that looks like this:

Out of curiosity, why does the wallet use an external dependency (Berkeley DB, now "owned" by known-open-source-killer Oracle) in the first place, rather than something ubiquitous like XML (or if purely flat, even CSV as you mention)?

[LZ]

Only Satoshi knows.

[Hal]

I'm kind of surprised that Mike's transactions didn't show up in my wallet. Instead it still counts that address as having a positive balance. Granted it is non-standard for payments from my wallet keys to originate elsewhere, but there are other ways it could happen, involving restoring from backup.

Well I just looked at the code, and it does only watch for transactions that pay me. However it looks like the new release will rescan the block chain on startup; that will probably fix it. I wonder how costly it would be to watch for outgoing transactions all the time.

[jgarzik]

Out of curiosity, why does the wallet use an external dependency (Berkeley DB, now "owned" by known-open-source-killer Oracle) in the first place, rather than something ubiquitous like XML (or if purely flat, even CSV as you mention)?

Because it's a database, and thus easy to use, compared to building your own file format.

[pla]

Because it's a database, and thus easy to use, compared to building your own file format.

That explains why we don't use a roll-your-own binary format.  It doesn't explain why we don't use something a bit more common, such as XML.

_{You could also turn that argument around - By using a relatively uncommon DB, we've still "rolled our own" with the negative of having an external build dependency.  Even if we want insist on FOSS, why not connect to a "real" DB like MySQL?}

[theymos]

That explains why we don't use a roll-your-own binary format.  It doesn't explain why we don't use something a bit more common, such as XML.

_{You could also turn that argument around - By using a relatively uncommon DB, we've still "rolled our own" with the negative of having an external build dependency.  Even if we want insist on FOSS, why not connect to a "real" DB like MySQL?}

XML offers no reliability guarantees.

Berkeley DB is quite common on Linux -- certainly more common than xSQL. It's also easy to compile, and it has no dependencies of its own.

[jgarzik]

Berkeley DB is quite common on Linux -- certainly more common than xSQL. It's also easy to compile, and it has no dependencies of its own.

BDB is common on Windows, too, but nobody sees it because it's embedded in your applications.

And because BDB is embedded (linked) into your application, no external server is required (unlike MySQL).

[[Tycho]]

Though fun I don't really understand the point of this. For backing your wallet you can just shut down the software and make a copy of wallet.dat. For moving coins between different wallets you can just send them as regular transactions.

Is there a use case for exporting private keys I haven't grokked yet?

It would be funny to have the possibility of taking bitcoins to base reality.
Like printing on a paper and giving to someone or making a QR-code.
Also they can be embedded in files like pictures and so on - mostly for fun, but not only.

P.S.: After Wolrd War III, when there will be no internet, we will have to consider other ways of bitcoin exchange.

[Mike Hearn]

XML isn't a good format to use for storing large, binary data structures which is what BitCoin is based on.

As to the idea of passing BitCoins around on bits of paper, well, I still think that without the internet Bitcoin is pointless so that doesn't hold a lot of appeal to me. You'd be much better off using existing currencies which have a lot of time invested in making the paper hard to forge ...

[myrkul]

After WWIII, Whenever or IF it should come, any survivors are NOT going to be using bitcoins. They'll be using the next best thing: precious metals, or failing that, straight barter. Or perhaps something that the world lacks the production capability to make any more, such as bottlecaps, to make a game reference.

A QR-code would be good, but you wouldn't want to QR-code your wallet. You WOULD want to QR-code your address, though.

[alikim]

instead of speaking Chinese here, you'd better help normal people to understand in plain English how bitcoin wallets work...  

bitcoins will never be popular if it will be a toy for a bunch of programmers

[Mike Hearn]

Yeah, we need to do a better job of explaining the mechanics of Bitcoin to a non-technical audience. It's important if only so more people can learn to trust it. Right now unless you're fluent in computer science Bitcoin is a black box and the existing explanations boil down to "trust us, it works".

This is a well discussed problem. It's just a case of how to do it.

[Binford 6100]

Yeah, we need to do a better job of explaining the mechanics of Bitcoin to a non-technical audience. It's important if only so more people can learn to trust it. Right now unless you're fluent in computer science Bitcoin is a black box and the existing explanations boil down to "trust us, it works".

http://prezi.com/tbpky5fm7qbl/bitcoin-new-p2p-currency/

what do you think of this ^^ presentation?
suitable for lay men? still too complicated? where/how would you modify it for non-techies?
audience for that presentation was a local hackerspace meeting. mostly tech savvy folks.

[hendi]

I'll also throw in 50 of my own coins for a web page that, in JavaScript, accepts such a file (copy/paste into a text area), formats a file like the above into binary and then generates a QRcode using the html5 canvas library available here:

   http://www.cipherbrain.be/qrcode/

In other words, I should be able to take a .bitkeys file, copy/paste it into a web page and without any network traffic be then able to print my keys out onto paper. Don't cheat and use your own server side code or Google chartserver - I want to be able to trust that the keys never left my computer. HTML5 app because that way it'll work on everyones systems.

http://hendi.name/bitcoin/ Like that?

You paste your .bitkeys file into the textarea, then for each key a QRcode is generated. Each generated code is labeld with its heading, so you can print everything on paper and then cut out individually keys. If you decode an QRcode, each restores to a valid .bitkeys file, i.e. starting with the v=1 line, then including the key and comment.

[Hal]

I'm kind of surprised that Mike's transactions didn't show up in my wallet. Instead it still counts that address as having a positive balance. Granted it is non-standard for payments from my wallet keys to originate elsewhere, but there are other ways it could happen, involving restoring from backup.

Well I just looked at the code, and it does only watch for transactions that pay me. However it looks like the new release will rescan the block chain on startup; that will probably fix it. I wonder how costly it would be to watch for outgoing transactions all the time.

I just upgraded to 0.3.20, and while it didn't find Mike's transaction automatically, I ran with the new -rescan switch and that picked it up. Only took 10 or 15 seconds on my Macbook Air.

[Mike Hearn]

http://hendi.name/bitcoin/ Like that?

Yes, very close!

There's a small bug. If there are empty lines you generate qrcodes that contain only "v=1" and nothing else. That's not a valid .bitkeys file going by my totally informal specification.

The format it prints to is not quite what I had in mind, it includes all the GUI stuff. You might want to make it hide the text area and button after the button is pressed, so when I print I only get a sheet of QRcodes.

Fix those two things and I'll send you 50 coins.

[riX]

Yeah, we need to do a better job of explaining the mechanics of Bitcoin to a non-technical audience. It's important if only so more people can learn to trust it. Right now unless you're fluent in computer science Bitcoin is a black box and the existing explanations boil down to "trust us, it works".

http://prezi.com/tbpky5fm7qbl/bitcoin-new-p2p-currency/

what do you think of this ^^ presentation?
suitable for lay men? still too complicated? where/how would you modify it for non-techies?
audience for that presentation was a local hackerspace meeting. mostly tech savvy folks.

Very nice, you should make a new thread, people will miss it here.

[Binford 6100]

Yeah, we need to do a better job of explaining the mechanics of Bitcoin to a non-technical audience. It's important if only so more people can learn to trust it. Right now unless you're fluent in computer science Bitcoin is a black box and the existing explanations boil down to "trust us, it works".

http://prezi.com/tbpky5fm7qbl/bitcoin-new-p2p-currency/

what do you think of this ^^ presentation?
suitable for lay men? still too complicated? where/how would you modify it for non-techies?
audience for that presentation was a local hackerspace meeting. mostly tech savvy folks.

Very nice, you should make a new thread, people will miss it here.

i'm ok with not reaching the full potential audience by hiding the link here
i could just add it to my signature and see who picks up the link

[hendi]

http://hendi.name/bitcoin/ Like that?

Yes, very close!

Cool! If there's anything else you (or someone else) wants this small script to do, don't hesitate to ask

There's a small bug. If there are empty lines you generate qrcodes that contain only "v=1" and nothing else. That's not a valid .bitkeys file going by my totally informal specification.

I now validate each line by checking for a valid base58 bitcoin address followed by the blocknumber. If an invalid line is found, you'll get notified with a popup. I'm not sure if this is the best notification style, I'll try later with showing the .bitkeys file and highlight wrong formatted lines, maybe that's better?

The format it prints to is not quite what I had in mind, it includes all the GUI stuff. You might want to make it hide the text area and button after the button is pressed, so when I print I only get a sheet of QRcodes.

Done.

[JollyGreen]

Yeah, we need to do a better job of explaining the mechanics of Bitcoin to a non-technical audience. It's important if only so more people can learn to trust it. Right now unless you're fluent in computer science Bitcoin is a black box and the existing explanations boil down to "trust us, it works".

This is a well discussed problem. It's just a case of how to do it.

Did anyone ever come up with an algorithm they wanted to release that generates a public key from a private key? 

[Mike Hearn]

I sent you 50 coins Hendi, thanks. That program is still kind of useless without the implementation of key import/export. Perhaps somebody will step up at some point and implement it.

[Mike Hearn]

JollyGreen, I posted the (single) line of code you need to do that with the Bouncy Castle implementation above, see here:

   pub = ecParams.getG().multiply(priv).getEncoded();

Note that the multiply method here is an elliptic curve point multiplication, not an arithmetic multiply.

If you're asking what an EC point multiply is, I suggest reading this:

  http://www.imperialviolet.org/2010/12/04/ecc.html

or possibly asking Hal, as he is the professional cryptographer on this forum not me

[hendi]

I sent you 50 coins Hendi, thanks. That program is still kind of useless without the implementation of key import/export. Perhaps somebody will step up at some point and implement it.

Cool, thanks! My first earned bitcoins

After exams I'll have a look at the bitcoin c++ source code and try to come up with the import/export.

[JollyGreen]

JollyGreen, I posted the (single) line of code you need to do that with the Bouncy Castle implementation above, see here:

   pub = ecParams.getG().multiply(priv).getEncoded();

Note that the multiply method here is an elliptic curve point multiplication, not an arithmetic multiply.

If you're asking what an EC point multiply is, I suggest reading this:

  http://www.imperialviolet.org/2010/12/04/ecc.html

or possibly asking Hal, as he is the professional cryptographer on this forum not me

How was Hal able to get the private key?  It seems the private key is stored in a CPrivKey structure in bitcoin and that is stored in the wallet.  Are the bytes that make up the CPrivKey structure the same as the base58 decoded bytes of Hal's private key?

I'm new to all this, but it looks like CPrivKey structures are DER encoded private keys.  Can you explain what it means to DER encode or decode something and is Hal's private key DER encoded?

[Mike Hearn]

Presumably Hal modified his copy of BitCoin to extract the private key, or maybe he used Gavins bitcointools package which reads the database directly.

DER encoding is just a way of wrapping up a binary data structure in a 'somewhat' self describing form. If you read up on Google protocol buffers, DER/ASN1 encoding is a very similar concept to that but much older and not at all widely used, as it's kind of a pain to deal with. The key Hal posted is not DER encoded. The DER encoded privkey structure has some goop in there that isn't necessary, it's only the 256 bit value that is important.

[JollyGreen]

Presumably Hal modified his copy of BitCoin to extract the private key, or maybe he used Gavins bitcointools package which reads the database directly.

DER encoding is just a way of wrapping up a binary data structure in a 'somewhat' self describing form. If you read up on Google protocol buffers, DER/ASN1 encoding is a very similar concept to that but much older and not at all widely used, as it's kind of a pain to deal with. The key Hal posted is not DER encoded. The DER encoded privkey structure has some goop in there that isn't necessary, it's only the 256 bit value that is important.

It seems from the bitcoin code that the private keys are stored in CPrivKey structures as DER encoded private keys.  Is there a way to decode these out of the DER structure?  Is there a way to pull just the private key from the EC_KEY structure?

If you look at the CKey class, they store the private key in the EC_KEY* pkey structure, but the only way it gets into or out of that class is through a CPrivKey, which looks to be DER encoded or decoded into pkey.

I'm trying to figure out how to get the raw 256 bit value from the private keys stored in the wallet.  There seems to be no direct route, so I'm trying to create one.

I think the basic idea is that people want to backup their coins on paper, so it seems one way to do that is to store the private key on paper in a few different methods.  I can also see it being useful if the bitcoin client offered this paper backup method as an option.

[Binford 6100]

How was Hal able to get the private key?  It seems the private key is stored in a CPrivKey structure in bitcoin and that is stored in the wallet.  Are the bytes that make up the CPrivKey structure the same as the base58 decoded bytes of Hal's private key?

I'm new to all this, but it looks like CPrivKey structures are DER encoded private keys.  Can you explain what it means to DER encode or decode something and is Hal's private key DER encoded?

search for forum where a bounty was for wallet key dump tool
keywords grondilu, wallet dump key ...

or as mike wrote, try to mod the client. i'm not sure if bitcointools are as userfriendly as the solution of grondilu

not answering how to remove the key from a wallet.
if you need to get hands on private keys, please start with an empty new wallet to avoid any losses

unless you know what you're doing

I think the basic idea is that people want to backup their coins on paper, so it seems one way to do that is to store the private key on paper in a few different methods.  I can also see it being useful if the bitcoin client offered this paper backup method as an option.

imho no way to get this to the main client. dump keys maybe but no print outs.
this ain't steampunk

[mgiuca]

@JollyGreen: I have had a closer look at the DER structure for the 279-byte private key. Not looking at the OpenSSL code -- it is rat nests of macros. Just experimenting with my own data. Looks like the 256-bit "actual private key" is located in bytes 9 through 40 (inclusive) of the DER key. The public key is located in bytes 214 through 279. All of the remaining bytes (0 through 8 and 41 through 213) are constant.

Therefore, grabbing out bytes 9 through 40 of the private key dumped by bitcointools is sufficient for getting the 256-bit key. What I don't understand still is how to derive the public key from this private key. I know you are supposed to find a number called "G" and elliptically-multiply it with the private key. But I have no idea how to a) find G, or b) do elliptic curve multiplication.

[Mike Hearn]

G is a constant specified by the curve parameters. BitCoin uses the secp256k1 curve in which G is equal to

  02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

in compressed form.

If you want to do what we've been doing on this thread I suggest you either:

a) Wait for me or somebody else to release code showing how to do it

b) Study the lightweight Bouncy Castle API and see how to do EC crypto with that, as it's probably easier to understand than OpenSSL

[JollyGreen]

G is a constant specified by the curve parameters. BitCoin uses the secp256k1 curve in which G is equal to

  02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

in compressed form.

If you want to do what we've been doing on this thread I suggest you either:

a) Wait for me or somebody else to release code showing how to do it

b) Study the lightweight Bouncy Castle API and see how to do EC crypto with that, as it's probably easier to understand than OpenSSL

Hey mike,
Thanks for the help once again   I actually have gotten some java code to run that is ready to do the math for generating a public key from the private key.  I just don't have the Base58.decodeToBigInteger function.  Is that something you could release?   It would save me some time.

[mgiuca]

Thanks for your help mike. Actually I just spent ... fricking ... too many hours to admit ... trawling through OpenSSL to figure out how to do it.

My code is online here:
https://code.launchpad.net/~mgiuca/+junk/bitcoin-import

It depends on OpenSSL and BitcoinTools, and is otherwise fairly automatic. It takes a 32-bit private key in base58 and automatically inserts it into your Bitcoin wallet. Yay!

[chromicant]

Little late to this party...

...I was also working on the challenge, and I found that Crypto++ worked really well for this. What I found was a nice surprise was that the ECDSA classes were nice enough to generate public keys from a private one if you had the data:

http://www.cryptopp.com/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Found it much, MUCH easier to use than OpenSSL. Downside is, well, you gotta know C++.

[JollyGreen]

Little late to this party...

...I was also working on the challenge, and I found that Crypto++ worked really well for this. What I found was a nice surprise was that the ECDSA classes were nice enough to generate public keys from a private one if you had the data:

http://www.cryptopp.com/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Found it much, MUCH easier to use than OpenSSL. Downside is, well, you gotta know C++.

I looked into this library and I couldn't find that it supported ecdsa 256k1.  Maybe it's just a matter of adding the curve constants to their library....

[JollyGreen]

Thanks for your help mike. Actually I just spent ... fricking ... too many hours to admit ... trawling through OpenSSL to figure out how to do it.

My code is online here:
https://code.launchpad.net/~mgiuca/+junk/bitcoin-import

It depends on OpenSSL and BitcoinTools, and is otherwise fairly automatic. It takes a 32-bit private key in base58 and automatically inserts it into your Bitcoin wallet. Yay!

Nice work again, python just seems so much easier to deal with than these other libraries, I guess just preference though

[chromicant]

I looked into this library and I couldn't find that it supported ecdsa 256k1.  Maybe it's just a matter of adding the curve constants to their library....

It's in there. My code looked a little something like this (from memory, so it may very well be WRONG):

AutoSeededRandomPool prng;
Integer pkey("TheHexStringOfTheKeyUnhashed");
ECDSA<ECP, SHA256>::PrivateKey privateKey;
ECDSA<ECP, SHA256>::PublicKey publicKey;

privateKey.Initialize(prng, ASN1::secp256k1());
privateKey.SetPrivateExponent(pkey);
privateKey.MakePublicKey(publicKey);


And volia, a public key from a private key.

[mgiuca]

Nice work again, python just seems so much easier to deal with than these other libraries, I guess just preference though

I agree. I always choose Python if I can In this case, I chose a mixture of Python and C. I am glad I stuck with C/OpenSSL when other people are using Java/Bouncy Castle or other approaches. My code can be integrated into the main Bitcoin codebase without introducing any new dependencies. I am interested to see if I can extend it to deal with this .bitkey format people are talking about.

I have stated elsewhere that I wanted to replace the Wallet format (which I regard as an ugly black box with way too much unnecessary data in it -- data like transactions and public keys are redundant and are not necessary for restoring precious coins from a backup) with a new one. I see now (having worked with the wallet) that it's quite integral to Bitcoin and it isn't going to be replaced any time soon.

Therefore, I am thinking that Bitcoin should be reading and writing two formats simultaneously. It keeps a wallet.bitkey file in the home directory. Whenever it writes a new private key to the wallet.dat, it also appends it to wallet.bitkey in human-readable format. When it starts up, it scans wallet.bitkey and if it sees any private keys which aren't in the wallet, it loads them in. That way, you can always check your wallet.bitkey file to see what keys you have in human readable format. And you can import/merge such files manually, and Bitcoin will slurp them in at startup.

In this case, my code would be useful because it uses OpenSSL to read in a private key and make a full DER key which is required by wallet.dat. The code to read wallet.bitkey and insert keys into wallet.dat would need this mechanism.

[netrin]

I think the advantages of base58 (unambigous 1lLiI for humans) is lost in a QR encoded message. Base93 (x21-x7E) is more data dense. Base10 (decimal) is almost as dense due to the four encoding types (numeric, alpha, pseudo-binary, and kanji). Data Matrix (as opposed to QR) has the advantage of a true binary format.