Bitcoin algorithms, need help with base58 encoding

[jrowe47]

I'm writing some code to learn more about the bitcoin processes. I've got most of everything figured out, but I'm wondering about base58 encoding. https://en.bitcoin.it/wiki/Base58Check_encoding
Let's say I have the following bitcoin address and private key (obviously I won't be using this one for anything important.)

Address: 1JHYG91McMgviqDDLSXq1TsPvZB7LYxV1s
PrivKey: 5JczEN6uCWESxHLyvnLbCWtjBJkTmHCtZBYcQztspvDJctmdKmF

If I use the chart on the base58 page linked above, then I convert each character of the private key into a number from 0 to 57. Do I use 6 bits to represent each number, and the concatenate the result?

If so, then , I end up with something like this:

Code:

000001010001110001100111001011010101000101001011001101010111001011010011111011000001011001000111101011101101011001010001001101010111110011010101000101010001110101001011001101000001001101110011000001000101011111110001011101100111110011010011111101101011000011010001110001110011001101001001001001001101000111

Or in hex,

Code:

28E3396A8A59AB969F60B23D76B289ABE6A8A8EA59A09B9822BF8BB3E69FB5868E399A49268E

Since that doesnt really bear any resemblance to anything else I've encountered, I'm wondering - how exactly do I get a private key from the WIF and vice versa? Is there an easy "for dummies" link somewhere around from which I can get the rundown?

What I'd like to do ultimately is have a function that I can enter an arbitrary 256 bit number and then be able to transform it into the WIF, and take a WIF value and convert it back into the 256 bit number.

My mindset so far essentially goes like the following - Convert each character of the private key into a 6 bit number, concatenate each successive value into a single string.
I'm guessing this is the wrong approach, and would love a little bit of help (yeah, pun intended.)

I have a SHA256 library and everything else that's necessary pretty much ready to go, at this point I'm just stuck on base58. Thanks!

[DannyHamilton]

From that same page that you linked to:

. . . convert to base-58 using normal mathematical steps (bignumber division) . . .


code_string = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
   x = convert_bytes_to_big_integer(hash_result)
  
   output_string = ""
  
   while(x > 0)
       {
           (x, remainder) = divide(x, 58)
           output_string.append(code_string[remainder])
       }
  
   repeat(number_of_leading_zero_bytes_in_hash)
       {
       output_string.append(code_string[0]);
       }
  
   output_string.reverse();

So if you just represent each number with 6 bits, you are still in base58 you are just using your own new made up alphabet to represent each base58 digit.

If you want a 256 bit number, then you have to convert to binary (not represent the characters in binary).

Example:

Base58Check number 35 = base58 value 24 = 2 x 58¹ + 4 x 58⁰ = base10 value 120 = Hex value 0x78

I assume there may be some method of converting directly from base58 to base16 (hex) without passing through base10 first, but I included the base10 conversion here so you can see that you are looking at 3 different representations of the decimal number 120 (35 in Base58Check, 24 in base 58, and 78 in base16).

[Onichan]

I am trying to figure out how to get to base58 as well and am a bit confused. I have read a few implementations on going to base58 from current apps such as https://github.com/pointbiz/bitaddress.org and the one posted on the bitcoin.it site and they all seem to take the value needing to change and convert it to a big integer. Then divide it by 58 and the integer is converted to base58 with the remainder going through the process again. Well looking at https://en.bitcoin.it/wiki/Wallet_import_format I understand the first 6 steps, but if I take number 6 and convert it to a base 10 number it's an insanely massive number. Trying to divide that by 58 would equal a massive number so that is where I am getting confused.

Example: step 6 = 800C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D507A5B8D

to decimal ~= 6368099731808814328175274076776670756354696346421856450745089246076352148867543 0192536461

/58 ~= 1.09794822962220936692677139254770185454391316317618214668018780104764692221854 1899871318293103448275862068965517241... × 10^87

I assume I am going about this the wrong way.

[DannyHamilton]

- snip -
they all seem to take the value needing to change and convert it to a big integer. Then divide it by 58 and the integer is converted to base58 with the remainder going through the process again.
- snip -

I think you've got that backwards.

Take the big integer, divide it by 58.  The remainder represents the Base 58 "digit", the quotient goes through the process again.  Since the remainder will always have to be less than 58 (or it wouldn't be a remainder), all your digits will be one of the 58 digits used in base 58.

[Onichan]

Ok that does make more sense, but I still think I am getting the wrong big integer as 6368099731808814328175274076776670756354696346421856450745089246076352148867543 0192536461 is bigger than a 128bit number.

Edit: I figured out I need to use a language that supports arbitrary precision.

[cjp]

I just happen to be working on my own base58 implementation, and I saw this is quite a recent thread. I think I can help you.
First some links:

• Bitcoin Wiki: https://en.bitcoin.it/wiki/Base58Check
• Bitcoin source code: https://github.com/bitcoin/bitcoin/blob/master/src/base58.h
• My source code: https://github.com/cornwarecjp/amiko-pay/blob/master/bitcoinaddress.cpp

Note that my source code includes a very small "arbitrary size"/"big integer" implementation, which contains just enough functionality for Bitcoin base58 encoding. Also note that I only have encoding, not decoding; this is because I don't expect my application will ever need decoding.