Delivery-date: Tue, 14 May 2024 06:00:23 -0700
Received-SPF: pass (google.com: domain of ganrama@proton.me designates 185.70.40.137 as permitted sender) client-ip=185.70.40.137;
Date: Tue, 14 May 2024 12:43:07 +0000
To: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
From: "'Rama Gan' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39
 seed phrases
Message-ID: <9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM=@proton.me>
In-Reply-To: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
Feedback-ID: 79991369:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Reply-To: Rama Gan <ganrama@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

In this message I'm going to briefly describe the cryptographic components of
Penlock.

I won't cover Shamir Secret Sharing here, as it is a well-known algorithm. Note
that A. Poelstra and R. O'Connor previously explained its implementation on
paper-computer, as well as other shenanigans, in codex32's mathematical
companion: https://secretcodex32.com/docs/2023-08-23--math.pdf.

## Overview

Penlock uses a composite secret splitting algorithm: 2-of-M splitting is
implemented with a "paper-friendly" algorithm, whilst for (K>2)-of-M it falls
back to Shamir Secret Sharing. In both cases, GF(29) is used (i.e.: all
arithmetic operations are modulo 29). Using GF(Prime) allows for optimizations
in the paper implementation that were not possible with fields in the form
GF(2^N).

## Character Set

Penlock uses a character set composed of the 26 Latin characters and the symbols
`-`, `=` and `+`. Each character represents a corresponding integer, that I will
write between square brackets in this document; for example: =[0], +[1], A[2],
Z[27], -[28].

## 2-of-M Splitting

The concept behind the 2-of-M algorithm is relatively simple: it encodes a
secret as the difference between two consecutive shares. For example, let's
split "B[3]" into 3 shares:

1.  Pick a random character for Share A: say G[8]
2.  Derive Share B by subtracting the secret from Share A: G[8] - B[3] = D[5]
3.  Derive Share C by subtracting the secret from Share B: D[5] - B[3] = A[2]

We get: ShareA = G[8], ShareB = D[5], ShareC = A[2]

Note that each of the shares taken separately is merely a random number and
doesn't contain any information about the secret.

The secret can be recovered by computing the difference between two shares,
divided by the distance between these shares. For example, let's recover the
previous secret from shares A and C:

```
Secret = (ShareA - ShareC) / distance(ShareA, ShareC)
       = (G[8] - A[2]) / 2
       = E[6] / 2
       = B[3]
```

In this example we did split only one character, but a complete phrase will be
split similarly by splitting its characters one after another.

Cryptographers might recognize that algorithm as a variation of Shamir Secret
Sharing. To summarize, Shamir's 2-of-M encodes the secret at a specific x of
`f(x) = ax + b`, while Penlock's 2-of-M encodes it as the `a` in
`f(x) = -ax + b` (Share A being `b`).

## Checksum

Additionally, Penlock uses a simple checksum that guarantees error-free
results despite potential manipulation errors. For any given piece of data, the
checksum will be composed of the differences between each two consecutive
characters. For example:

```
Data    : C[04] O[16] I[10] N[15]
Checksum: Q[18] K[12] V[23] D[05]

Because : O[16] - C[04] = K[12]
          I[10] - O[16] = V[23] (-6 % 29)
          N[15] - I[10] = D[05]
          C[04] - N[15] = Q[18] (-11 % 29)
```

This checksum has been specifically designed for Penlock needs. It is great at
detecting and locating errors, but unless bech32 it is bad at repairing missing
data. This trade-off seems acceptable because secret splitting already provides
data redundancy (i.e.: if one share gets damaged, it is possible to fix it using
the two other shares).

## Implementation

The arithmetic operations used for 2-of-M splitting and checksumming are
implemented within a single wheel that can be printed from
https://beta.penlock.io/2ofm-wheel.html. The outer rings of the wheel implement
the addition and the subtraction, and the spiral in the middle implements the
division.

A step-by-step guide for computing the checksum shown above, but with the wheel,
can be found in the example of "Generating the Checksums" at
https://beta.penlock.io/2of3-guide.html.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM%3D%40proton.me.