edgecase
Author: StJohn Piano
Published: 2020-12-12
Datafeed Article 196
This article has been digitally signed by Edgecase Datafeed.
1178 words - 389 lines - 10 pages




Description



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




Contents



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










Bitcoin Private Key Formats





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



The corresponding Bitcoin address is:
16ASCUS3s7D4UQh6J9oHGuT19agPvD3PFj



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".

7972 b641 101c 0ad6
7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5



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".

9
ab31
96ed 0029 cb57 1b50

7972 b641 101c 0ad6
7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5



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.










Hexadecimal Addition





Standard human numbers are base 10 and the digits are:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9



Hex numbers are base 16 and the digits are:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f



Hexadecimal addition works in the same way as standard base 10 addition, but in base 16. Some examples:
0 + 0 = 0
0 + 1 = 1
1 + 1 = 2
1 + 9 = a
1 + a = b
5 + a = f
6 + a = 10
1 + f = 10
f + a = 19
f + e = 1d
f + f = 1e
1f + 1 = 20



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.










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





-) 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










Worked Example





Bitcoin private key:
7972b641101c0ad67b0e401b800a9b6f3225c97fc6b8115042cf66968c2fb2e5



Convert to grid format:
7972 b641 101c 0ad6
7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5



Calculate the arithmetic checksum of group 1 in line 1:
group: 7972
- Treating each character as a hex number, sum the numbers:
7 + 9 = 10
10 + 7 = 17
17 + 2 = 19
- Take the last character of the resulting hex number:
9


Calculate the arithmetic checksum of group 2 in line 1:
group: b641
b + 6 = 11
11 + 4 = 15
15 + 1 = 16
last character: 6


Calculate the arithmetic checksums of groups 3 and 4 in line 1:
group: 101c
- checksum: e
group: 0ad6
- checksum: d


The first group in the checksum line is therefore:
96ed


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

Calculate the rest of the checksum line in the same way. Result:
96ed 0029 cb57 1b50


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:

96ed 0029 cb57 1b50

7972 b641 101c 0ad6
7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5



Now, calculate the checksum group from the checksum line.
group: 96ed
9 + 6 = f
f + e = 1d
1d + d = 2a
last character: a

group: 0029
0 + 0 + 2 = 2
2 + 9 = b
last character: b

group: cb57
c + b = 17
17 + 5 = 1c
1c + 7 = 10 + c + 7 = 10 + 13 = 23
last character: 3

group: 1b50
1 + b = c
c + 5 = 11
11 + 0 = 11
last character: 1



So, now we have the checksum group:
ab31



Let's add it above the checksum line:

ab31
96ed 0029 cb57 1b50

7972 b641 101c 0ad6
7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5



Calculate the arithmetic checksum of the checksum group:
a + b = 15
15 + 3 = 18
18 + 1 = 19
last character: 9



The checksum character of the entire private key is:
9



The final storage key is therefore:

9
ab31
96ed 0029 cb57 1b50

7972 b641 101c 0ad6
7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5