Algorithm: Generate an arithmetic checksum tree for a Bitcoin private key.







- Description
- Contents
- Bitcoin Private Key Formats
- Hexadecimal Addition
- Algorithm: Generate an arithmetic checksum tree for a Bitcoin private key.
- Worked Example















Example Bitcoin private key (64 characters, 32 bytes):



The corresponding Bitcoin address is:



It's easier to read the private key if it is written in a grid pattern, divided into groups of 4 characters and lines of 4 groups.

Here is the example private key in this grid format. I call this a "grid key".




A few errors in the private key can make it impossible to recover the actual private key within a reasonable time frame. I therefore prefer to generate an arithmetic checksum tree for the private key in order to make it more robust - errors can be located more precisely, and key recovery time is drastically improved.


Note: I originally developed this approach in the project An investigation into recovering from transcription errors in Bitcoin private keys. More detail is available there.


Here is the example private key, in grid format with the added arithmetic checksum tree. I call this a "storage key".




The checksum values are produced by hexadecimal addition. The primary reason for doing this instead of using a hash checksum is that, if necessary, the checksum tree can calculated manually using pencil, paper, and a hexadecimal addition table. Note: The table itself could be generated manually with pencil and paper.















Standard human numbers are base 10 and the digits are:



Hex numbers are base 16 and the digits are:



Hexadecimal addition works in the same way as standard base 10 addition, but in base 16. Some examples:



This hexadecimal addition table [0] shows all the possible results for adding two single-digit hex numbers:



Description of hexadecimal addition table: Two axes, X and Y. X runs horizontally along the top of the table. Y runs vertically down the left side of the table. Both X and Y contain the hex values 0-f. Each entry in the table is the hex sum of the relevant X and Y values. Examples: 0 + 0 = 0, f + f = 1e.















-) Take a Bitcoin private key and convert it into grid format.

-) Arithmetic checksum function: For a group of 4 characters, treat each character as a hex number, sum the characters, and take the last character of the resulting hex number.

-) Calculate the arithmetic checksum of each group in the first line of the private key. This will produce 4 checksum characters. Write this new group on a new line above the key.

-) Do the previous step for the remaining 3 lines in the private key, writing each new group on the same new line above the key. Result: A single new "checksum line" of 4 groups.

-) Apply the same technique to the checksum line itself. Calculate the arithmetic checksum of each of its 4 groups. This will produce a single "checksum group" of 4 characters. Write this on a new line above the checksum line.

-) Apply the same technique to the checksum group. Calculate the arithmetic checksum of the single checksum group. This will produce a single "checksum character". Write this on a new line above the checksum group.




Notes:

- I use this format when writing a Bitcoin private key on paper

- I have developed tools that rely on this algorithm to convert a private key to and from the checksum tree storage format:
Tools for storing a Bitcoin private key with a checksum tree















Bitcoin private key:



Convert to grid format:



Calculate the arithmetic checksum of group 1 in line 1:


Calculate the arithmetic checksum of group 2 in line 1:


Calculate the arithmetic checksums of groups 3 and 4 in line 1:


The first group in the checksum line is therefore:


This first group corresponds to the first line of the private key.

Calculate the rest of the checksum line in the same way. Result:


Group 2 in the checksum line corresponds to line 2 of the private key. Group 3 corresponds to line 3, and group 4 to line 4.


Let's add the checksum line above the private key:




Now, calculate the checksum group from the checksum line.



So, now we have the checksum group:



Let's add it above the checksum line:




Calculate the arithmetic checksum of the checksum group:



The checksum character of the entire private key is:



The final storage key is therefore: