edgecase
Author: StJohn Piano
Published: 2020-12-12
Datafeed Article 196
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
- 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):

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

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

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.

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

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:

Convert to grid format:
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
- 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

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

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

7b0e 401b 800a 9b6f
3225 c97f c6b8 1150
42cf 6696 8c2f b2e5

[start of footnotes]