Penlock, a paper-computer for secret-splitting BIP39 seed phrases

[Rama Gan]

I am excited to introduce Penlock, a printable paper-computer that guides users
through secret-splitting their BIP39 seed phrase without an electronic device. A
beta release is now available for peer-reviewing and early testing:
https://beta.penlock.io.

There are a growing number of people storing a significant portion of their
savings on the blockchain. Most people use a BIP39 seed phrase to back up their
wallet, but this method has disadvantages. If the seed phrase is lost or stolen,
then the funds are at risk of being irremediably lost. Additionally, planning
for inheritance would require entrusting the phrase to a third party, something
that is not advisable.

Secret splitting is a straightforward cryptographic concept that solves these
issues. A 2-of-3 split produces 3 "shares"; Any 2 of these shares can be used to
recover the seed phrase. Each share can be stored in a separate location and no
single share can be used to reveal information about the seed phrase.
Trust-minized inheritance is then possible, as one share can be given directly
to an heir, and another left in the will.

Unfortunately, despite commendable efforts with SLIP39, we still lack a
wallet-agnostic secret splitting standard. Moreover, users who already produced
their BIP39 seed phrase might be legitimately reluctant to enter it into an
electronic device for the purpose of secret splitting.

This is were Penlock enters the scene! Secret-splitting BIP39 seed phrases
guarantees compatibility with all existing wallets. Using the analog
implementation, one can run the algorithm without exposing the seed phrase to an
additional electronic device. You only need a printer, a craft knife, some
scissors, a pencil and paper, and a few hours of free time.

Penlock was inspired by Codex32, a similar project from A. Poelstra and R.
O'Connor. From there, I tried to map the design space by exploring different
trade-offs, producing prototypes, benchmarking their execution speed, their ease
of use, etc. While there is always room for improvement, I believe that the
design of Penlock is now close enough to optimal and deserves to be released.

Penlock is an open-source project that will always remain free to use.
Cryptographers, developers and enthusiasts are very welcome to test and
peer-review Penlock until its public release date, which is currently planned
for Q3 2024. Please share any feedback or comments you may have! :)


Rama Gan

[Andrew Poelstra]

On Sun, May 12, 2024 at 06:04:09PM +0000, 'Rama Gan' via Bitcoin Development Mailing List wrote:
> I am excited to introduce Penlock, a printable paper-computer that guides users
> through secret-splitting their BIP39 seed phrase without an electronic device. A
> beta release is now available for peer-reviewing and early testing:
> https://beta.penlock.io.
>

> <snip>
>


Hi Rama,


Very interesting project. I have a few unordered thoughts about this:

* You have instructions for generating BIP39 seed words, but if the goal
is to be compatible with existing setups, this really isn't necessary
(or even desireable). If somebody is willing to generate a whole new
seed and is willing to sweep their coins, they might as well just use
codex32. (Perhaps they have an urgent need to do so, and cannot wait
for codex32 support to arrive in mainstream wallets. Ok. But it's a
pretty niche user who is panickedly updating their coins while having
the patience to hand-compute things!)

* Furthermore, the "just grind checksum words til the string works"
approach, while ergonomic for 12 words (16 iterations max), is
unrealistic for 16 words (64 iterations) and basically impossible for
24 words (256 iterations). Probably worth mentioning this.

* The math underlying this all seems sound -- you map BIP39 characters
directly into the field of integers mod 29, then compute lines in this
field. However, the resulting checksum is then as long as your
original set of words. Again, probably ok for 12 words but
unreasonable for 24. (BTW, we have an unofficial BIP39 compatibility
layer for codex32 which has the same issue -- everything is horrible
for the 24-word case. But it is possible to do, and I've done it.)

* However, the use of a characteristic-greater-than-2 field means that
addition and subtraction are different operations and suddenly you
need to be careful about the exact order in which your read things
off the volvelles. It also makes recovering your share more
complicated. I see that you currently have a table for the 2-of-3
case where you read the volvelle in different ways depending on which
shares you have. Clever, but this will not extend to 2-of-n and I
suspect you'll basically need to implement the full "recovery wheel"
from codex32 (or the "recovery tables" which are faster to use for the
2-of-n case, though easier to use wrong).

Recovery is not really that important because you only do it when
you're going to put your seed into a computer, and in that case you
might as well make the computer do the recovery for you, but it is
unfortunate. Especially in this case where a stated goal is that the
computer -won't- do anything for you because it doesn't know about the
scheme.

* Furthermore, this encoding into GF29 is nonstandard. I think, for the
checksum construction this doesn't matter -- if the encoding becomes
lost then you can just forget about the checksum, and if it doesn't,
then you have a pretty great checksum (which can recover any number of
errors as long as they don't hit both the data and the checksum in the
same place). My feeling is that it's probably a good idea for people
to use your checksum scheme on top of their existing BIP39 words, but
the splitting stuff I'm less comfortable with.

Possibly you would rather just combine your checksum scheme with
seedxor? Though seedxor has the unfortunate need to convert your data
to binary before xoring, which is time-consuming and error-prone and
not compatible with the checksum so you don't have any good way to
catch or fix mistakes. (The "unofficial compatibility layer for
codex32" I mentioned works this way as well and it's horrible. But as
you say, for users who really don't want to sweep their coins, maybe
they are willing to make ugly tradeoffs..) Though I believe that
seedxor only works for 2-of-3 and cannot be generalized without making
the scheme unrecognizable.

Alternately, if you switched to a binary field, and chose a checksum
whose target residue was 0 (normally *not* recommended because it
allows some classes of errors, in particular prefixes of zeroes)
(though it does not allow any more substitution or erasure errors,
which is what we care about for short fixed-length like this) then
you could use an addition volvelle in the same way, the computation
would secretly be identical to the seedxor computation, and your
checksum would be preserved by it. So this is another way in which you
could try to make a "seedxor-compatible checksum". But by adding a
multiplicaion wheel that can do Lagrange multipliers you could
generalize it to 2-of-n in a "natural" way which would break seedxor
compatibility only for people who wanted more than 3 shares, and
possibly even only when actually using shares beyond the third..

As a final note about seedxor, they have as a design goal that the
shares look identical to full seeds; they preserve the broken bip39
checksum, have no extra characters, etc. Personally I think this goal
is terrible. If you are going to use obscure hand-computation tricks
you are far more likely to lose your data (or forget how to manipulate
it) than you are to be robbed by a thief who understands your scheme.

* More generally, you need to write up a specification and description
of the math and maybe even a PDF :). I learned the scheme by
reverse-engineering your Javascript, which is well-written and
dependency-free, but still pretty abstract and indirect and anyway JS
is not my language (nor is it likely to be the language for the
typical hand-computer user). Sadly your volvelles also don't render
properly in my browser (qutebrowser) which is chromium-based but maybe
I have some settings wrong.



Best
Andrew


--
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster

[Rama Gan]

Hello Andrew,

Thank you for sharing your thoughts.

I think I fixed the biggest compatibility issues. Most browsers should now
display the documents correctly, but there still are issues when using the
"Print to PDF" feature. Chromium, Brave and Firefox do it well. With qutebrowser
5.x and 6.x, I get weirdly pixelated results and the wrong page margins. I'm not
sure yet if it is something that I can fix, or how it will look when actually
printing; I'll investigate further as soon as I can.

- The "Generate a Seed Phrase" guide is useful for initializing a new hardware
wallet that only supports BIP39. The guide and the worksheet only support
the 12-word variant, because as you said grinding for the checksum is
otherwise tedious. I guess I should add an explainer for that. I also expect
that most Penlock users will already have a seed phrase and that's why I
didn't mention this feature in the presentation.

- About seedxor: I am not familiar with it, but it looks like something I'd
want to dig in. About BIP39->binary conversion: even double-checking can't
fully guarantee its correctness, so it can lead to dramatic failures.

- About GF(27) being non-standard: the documents for analog computations will
remain valid and available, so it's not like a software implementation that
requires routine maintenance or might be discontinued.

- Penlock implements arithmetic operations differently than Codex32. Additions
and subtractions are implemented with a slider-wheel (only possible with
GF(P)); Multiplications and "divisions" are done with volvelles. There is
indeed a risk of using the slider-wheel in the wrong direction, and this is
mitigated by 2-of-N not using additions at all.

- An experienced user can compute a 12-words checksum in 4mins, and verify its
correctness in 3 mins. Checksumming 24-word is quite doable, but then the
difficulty comes with the shares derivation part that takes close to an hour
and feels really tedious (again, for 24 words). For reference, an
experienced user can secret-split a 12-words sentence in 45 minutes. A
24-words sentence will more than double that due to getting tired and losing
focus.

- The 2-of-(N<=26) case is handled with a variant of Shamir's algorithm that
can be fully implemented in a single wheel. I'm about to post a presentation
that will go into more details about that. For (K>=3)-of-M cases there's
indeed a recovery wheel, plus a volvelle that does translation+fusion on the
same side (see: https://beta.penlock.io/kofm-wheels.html).

Best regards,
Rama Gan

[Rama Gan]

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.

[Andrew Poelstra]

On Tue, May 14, 2024 at 12:03:45PM +0000, Rama Gan wrote:
> Hello Andrew,
>
> Thank you for sharing your thoughts.
>

> - Penlock implements arithmetic operations differently than Codex32. Additions
> and subtractions are implemented with a slider-wheel (only possible with
> GF(P)); Multiplications and "divisions" are done with volvelles. There is
> indeed a risk of using the slider-wheel in the wrong direction, and this is
> mitigated by 2-of-N not using additions at all.
>

FYI even in GF(P), you can do multiplication and division using slide
wheels. I'm not sure if doing so would interfere with your other
multipurpose volvelle constructions. (Every nonzero number in your field
is 2^n for some n, so you can do multiplication/division by adding in
the exponent.)

The resulting slide wheel would not have a natural ordering.

> - An experienced user can compute a 12-words checksum in 4mins, and verify its
> correctness in 3 mins. Checksumming 24-word is quite doable, but then the
> difficulty comes with the shares derivation part that takes close to an hour
> and feels really tedious (again, for 24 words). For reference, an
> experienced user can secret-split a 12-words sentence in 45 minutes. A
> 24-words sentence will more than double that due to getting tired and losing
> focus.
>

The checksumming numbers are impressive but a little surprising -- in
codex32, "translation" is a process of similar complexity on fewer
characters and it takes me 5 minutes or so. Perhaps the difference is
that you can use a slide wheel with a natural ordering, while we are
using a slide chart? At some point I will work through your process and
see how it feels.

For what it's worth, codex32 quickchecks can be done in ~5 minutes as
well. Though of course they are much less powerful than your checksum.

Interesting that the splitting and recovery processes take such a long
time. But I guess this is explained by the large number of characters
produced by the checksum.

> - The 2-of-(N<=26) case is handled with a variant of Shamir's algorithm that
> can be fully implemented in a single wheel. I'm about to post a presentation
> that will go into more details about that. For (K>=3)-of-M cases there's
> indeed a recovery wheel, plus a volvelle that does translation+fusion on the
> same side (see: https://beta.penlock.io/kofm-wheels.html).

Very cool. Though you say "single wheel" but you actually need two --
one to get the solving window and one to actually do the recovery. If I
understand correctly, the "solving window" is equivalent to a "recovery
symbol" in codex32.

If so, despite the simple interpretation as "the difference between the
shares", this object is secretly a Lagrange polynomial and you can
*also* compute it using a slide wheel rather than a full lookup-table
volvelle. (The reason for this is not so simple, and described in the
codex32 math companion [1] ... but possibly if you believe it's true you
can just "brute force" it without understanding why by just
progressively constructing a wheel, doing various recoveries and filling
in blank spaces by cross-referencing against your existing volvelle.)


[1] https://secretcodex32.com/docs/2023-08-23--math.pdf

[Rama Gan]

I don't know if you have seen my previous email describing how 2-of-M is
implemented in Penlock? I sent two mails the same day, I suspect that the second
one went unnoticed; My reply below could be confusing without that piece of
context.

> FYI even in GF(P), you can do multiplication and division using slide wheels.
> I'm not sure if doing so would interfere with your other multipurpose volvelle
> constructions. (Every nonzero number in your field is 2^n for some n, so you
> can do multiplication/division by adding in the exponent.)
>
> The resulting slide wheel would not have a natural ordering.

I used this for the (K>2)-of-M case. In fact, by mapping the recovery symbols to
the right values, it is possible to achieve natural ordering (which is indeed
faster to compute). For Penlock, I used numbers instead of symbols and the
mapping `n -> (2^n) % 29`.

[1]: Recovery "symbols" mapping:
https://github.com/penlock-io/beta.penlock.io/blob/master/sdk/data/penlock-bip39.js#L92
[2]: "fusion" is done by summing the exponents using the big wheel:
https://beta.penlock.io/kofm-wheels.html

> Interesting that the splitting and recovery processes take such a long time.
> But I guess this is explained by the large number of characters produced by
> the checksum.

For clarity, 45 mins was from a benchmark in real conditions. It includes the
whole process of copying the seed phrase, checksumming it, generating the random
share A, checksumming it, deriving both shares B and C, verifying the checksums
and finally correcting a few mistakes. Recovery took 20 minutes.

The checksum is the second source of inefficiency, the first one being that
BIP39 isn't compact. GF(29) can encode 128 bits within 7 words, and the checksum
would cost 7 more words. In comparison, BIP39 low density of information costs
10 more words (5 data + 5 checksum). With a compact data format, the entire
2-of-3 split process would take less than 30 minutes; and recovery with
verification would be under 15 minutes. I don't know if it can be optimized
further, but we're already looking at figures that the general public might find
acceptable.

> Very cool. Though you say "single wheel" but you actually need two -- one to
> get the solving window and one to actually do the recovery. If I understand
> correctly, the "solving window" is equivalent to a "recovery symbol" in
> codex32.

The solving window is the is the distance between two shares, and not a Lagrange
basis (to the best of my knowledge). It can be determined from the same single
wheel, that already implements subtraction.

[3]: The 2-of-M wheel "Recovery" window shows the distance between two shares:
https://beta.penlock.io/2ofm-wheel.html

> If so, despite the simple interpretation as "the difference between the

> shares", this object is secretly a Lagrange polynomial and you can _also_

> compute it using a slide wheel rather than a full lookup-table volvelle.

I'm not sure if I understand that, but it sounds like I missed an optimization
opportunity there. Can I ask you to develop that point a little?


-- Rama Gan

[Andrew Poelstra]

On Thu, May 16, 2024 at 07:43:29AM +0000, Rama Gan wrote:
> > But I guess this is explained by the large number of characters produced by
> > the checksum.
>
> For clarity, 45 mins was from a benchmark in real conditions. It includes the
> whole process of copying the seed phrase, checksumming it, generating the random
> share A, checksumming it, deriving both shares B and C, verifying the checksums
> and finally correcting a few mistakes. Recovery took 20 minutes.
>
> The checksum is the second source of inefficiency, the first one being that
> BIP39 isn't compact. GF(29) can encode 128 bits within 7 words, and the checksum
> would cost 7 more words. In comparison, BIP39 low density of information costs
> 10 more words (5 data + 5 checksum). With a compact data format, the entire
> 2-of-3 split process would take less than 30 minutes; and recovery with
> verification would be under 15 minutes. I don't know if it can be optimized
> further, but we're already looking at figures that the general public might find
> acceptable.
>

With BIP39 density you have 24 words (96 characters). With GF29
compaction you could get this down to 14 words (56 characters). But
codex32 does the same in 45 characters, plus a fixed/preprinted HRP.
(And 6 of those 45 are a header which is usually faster to deal with
since you're always dealing with the same characters.)

In your case, since there's no way to get down to 48 characters, I
wouldn't bother trying to compress any further. Either you fit in one
side of a cryptosteel (no) or you fit in two sides of a cryptosteel or
into a tube (yes, even without compression).

And I agree that the existing figures are not bad, especially because
the checksumming (which is the most common and also the least fun) is so
fast.

I think if you were able to squeeze an extra word of header data or
version info, that would be worth doing, but probably not at the expense
of making the user do a re-encoding phase. Which I suspect would be
needed to try to get more information density out of your characters.

> > Very cool. Though you say "single wheel" but you actually need two -- one to
> > get the solving window and one to actually do the recovery. If I understand
> > correctly, the "solving window" is equivalent to a "recovery symbol" in
> > codex32.
>
> The solving window is the is the distance between two shares, and not a Lagrange
> basis (to the best of my knowledge). It can be determined from the same single
> wheel, that already implements subtraction.
>
> [3]: The 2-of-M wheel "Recovery" window shows the distance between two shares:
> https://beta.penlock.io/2ofm-wheel.html
>

Ah, I understand. Looking again at your wheel, I see that it's a
combination slide wheel (for addition/subtraction) and slide chart (for
"recovery windows").

What I'm saying is that you don't need to have extra cutout windows for
the recovery windows. You should be able to just label the characters on
the inner wheel with them, similar to how you have already labeled =
with (1).

> > If so, despite the simple interpretation as "the difference between the
> > shares", this object is secretly a Lagrange polynomial and you can _also_
> > compute it using a slide wheel rather than a full lookup-table volvelle.
>
> I'm not sure if I understand that, but it sounds like I missed an optimization
> opportunity there. Can I ask you to develop that point a little?
>

I don't think this discussion of Lagrange polynomials is relevant
actually. My point is that you don't need the cutout squares, and I
think this is clearer if you think in terms of share index differences
than if you think in terms of Lagrange polynomials.

But. What I'm saying is that if you do the Lagrange polynomial
calculation using the formula from Wikipedia, magically your differences
will appear. They're the same thing, just expressed differently.

[Andrew Poelstra]

On Thu, May 16, 2024 at 01:27:55PM +0000, Andrew Poelstra wrote:
> >
> > [3]: The 2-of-M wheel "Recovery" window shows the distance between two shares:
> > https://beta.penlock.io/2ofm-wheel.html
> >
>
> Ah, I understand. Looking again at your wheel, I see that it's a
> combination slide wheel (for addition/subtraction) and slide chart (for
> "recovery windows").
>
> What I'm saying is that you don't need to have extra cutout windows for
> the recovery windows. You should be able to just label the characters on
> the inner wheel with them, similar to how you have already labeled =
> with (1).
>

Ah, I am incorrect. You can put the recovery windows on a slide wheel
but it needs to use a different ordering than the one used for addition.
So you would need a second wheel and possibly some relabelling of
recovery windows.

I don't see why this is ... it seems that the recovery windows, being
differences of characters, should follow exactly the same pattern as
addition (possibly in the opposite direction). So worth investigating.

But assuming that it isn't possible and would require you introduce
another wheel, it's probably not worth the extra "simplicity". After
all, you only need to look up the windows once per share (so volvelle
ergonomics are not so important) and you only need to cut out as many
windows as you have shares (so setup/construction time is not bad).

[Rama Gan]

> Ah, I am incorrect. You can put the recovery windows on a slide wheel
> but it needs to use a different ordering than the one used for addition.
> So you would need a second wheel and possibly some relabelling of
> recovery windows.
>
> I don't see why this is ... it seems that the recovery windows, being
> differences of characters, should follow exactly the same pattern as
> addition (possibly in the opposite direction). So worth investigating.

No, no, you were right, it can be done.

If you want to find the difference between A[2] and D[5], you can place the
pointer on A, find D on the outer ring and the corresponding inner-ring
character will be B[3]. Then, it is possible to write the numerical values under
the first 14 characters as you suggested before. (We only care about the
_shortest_ distance.)

I chose to use a window because it's less "verbose". I didn't want to clutter
the wheel with information that you'd use only once per recovery. (Using the
window is in fact more compact.)

About a header, the problem is that the fast 2-of-M algorithm won't preserve
constant values across shares as Codex32 does. In Penlock, the header
information is simply printed/written on the share instead of being encoded. The
best I can do is to tweak both algorithm so that you can derive the secret and
share's index correctly, by using "-[28]" as the secret's index. (But the secret
is not a point on the line, and the share at X=28 would have a different value,
so that might be more confusing than anything)

-- Rama Gan

[Andrew Poelstra]

On Fri, May 24, 2024 at 10:39:57AM +0000, Rama Gan wrote:
>
> About a header, the problem is that the fast 2-of-M algorithm won't preserve
> constant values across shares as Codex32 does.
>

Are you sure? It seems that if two shares have the same value in a given
position, the line through them should be constant, meaning that every
other share will have the same constant value.

[Rama Gan]

> Are you sure? It seems that if two shares have the same value in a given
> position, the line through them should be constant, meaning that every
> other share will have the same constant value.

For the 2-of-M split, the secret is encoded as the difference between two
consecutive shares instead of being a point at a given index. If both the secret
and share A have a header `HEAD`, then share B will start with `====` (zeros)
and share C will be the additive inverse of `HEAD`.

The secret is the "slope" of the line; for the shares headers to be constant,
the solution would be to fill the corresponding spots with zeros on the secret.
So yes it _is_ possible, but then the 2-of-M and the K-of-M cases will behave
differently which could be a source of confusion. I guess it is the
cons of going for a composite scheme.

-- Rama Gan