[bitcoin-dev] On the compatibility of Bech32 and Shamir's Secret Sharing

["Russell O'Connor" <roconnor@blockstream.com>]

[-- Attachment #1: Type: text/plain, Size: 4930 bytes --]

With the help of Pieter I've recently made some interesting mathematical
observations about Bech32 codewords and Shamir's secret sharing:

(1) Affine combinations of two Bech32 codewords is again a valid Bech32
codeword.
(2) Lagrange polynomials form a partition of unity.

The consequences of these facts is that when you perform Shamir's secret
sharing where all your shares have valid Bech32 checksums, then the
resulting secret will also have a valid Bech32 checksum.  Conversely, if
your secret has a valid Bech32 checksum, and your random shares have valid
Bech32 checksums, then all your derived shares will have valid Bech32
checksums.  This can form a basis on which we can build a simple secret
sharing scheme for dividing up a BIP-32 master seed.

In order to illustrate this, I'll describe an example scheme for *k*-of-*n*
Shamir's secret sharing scheme where *2 <= k* <= *n* <= 31.

Suppose we have a 128-bit master seed 0xb6721d937d82f238672de4db91b87d0c.
We encode this secret as the following Bech32 codeword: "
donotusesss321s2name00keepmymasterseedunderwraps2n89wr".  Let's deconstruct
this codeword.

"donotusesss32": A Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"s": The first data character is the index of this share. Each index is a
Bech32 character.  In this scheme the secret share is always at index "s",
which stands for "secret".
"2": The second data character is the threshold.  In this example we are
using a 2-of-n threshold.  We use the digits 2-9 for thresholds upto 9.  We
use Bech32 characters a-y for thresholds from 10 to 31.
"name00": The next 6 characters are an id for this set of shares.  This id
isn't part of the secret data. It is used to ensure that the shares you are
reconstructing were generated for the same secret.  This id just needs to
be unique for all the secrets that you are dividing up with this scheme.
The id can be chosen randomly, sequentially, or even set to the constant
such as "qqqqqq" if you do not want to use it for identification.
"keepmymasterseedunderwraps": This is the 128-bit secret master seed
0xb6721d937d82f238672de4db91b87d0c encoded in Bech32.  The master seed can
be a 128-bit, 256-bit or 512-bit value.
"2n89wr" is the Bech32 checksum.

We will generate shares for a 2-of-3 threshold.  We generate the first
share at index "a".  In this example we generate "
donotusesss321a2name00q0h5aajczn04g9sh0wtsl2f0y0g3vlkr".

"donotusesss32": The Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"a": The first data character is the index of this share which we have
chosen to be "a".
"2": The second data character is the threshold, which is 2.
"name00": The next 6 characters is the id we chose above for this set of
shares.
"q0h5aajczn04g9sh0wtsl2f0y0": This is 26 randomly selected bech32 characters
"g3vlkr" is the Bech32 checksum.

We generated the next two shares at index "c" and and index "d".  These
shares are generated using characterwise Lagrange interpolation of the
secret share and the above randomly generated share.
The resulting shares are "
donotusesss321c2name00chzu58ep57hd9xmaw6zmuyjeau0kq4mr" and "
donotusesss321d2name00ung8rmkf2snftj57zu45g7z84hzmzk4r"

Notice that the resulting strings have
(1) valid checksums;
(2) have correct indices;
(3) have the correct threshold values;
(4) have the correct ids.

This scheme still enjoys the perfect information hiding property of
Shamir's secret sharing.  Even when you know *k*-1 shares, every possible
master seed value has exactly one set of shares that includes those
particular *k*-1 shares, so knowing *k*-1 shares tells you nothing about
the secret data value.

One nice property of Lagrange interpolation is that it is simple enough to
compute by hand with the help of a few lookup tables.  Bech32 checksums can
also be computed and checked by hand with the help of lookup tables.  While
the majority of users wouldn't do hand computations, those motivated users
who have a healthy distrust of digital devices can generate and manipulate
the secret shares by hand.  The Bech32 checksum property means that after
generating the shares by hand, you can then validate the checksums by hand.
With extremely high probability, you will catch any computation error you
make.  My SSS32 repository at https://github.com/roconnor-blockstream/SSS32
has a postscript file that generates the lookup tables needed for hand
computation, although the document is a bit disorganized at the moment.

The main deficiency of the scheme presented here is that we want a longer
checksum than used in BIP-173 that is more suitable for error correction,
rather than simply error detection.

This example scheme was inspired in part by SLIP-32
<https://github.com/satoshilabs/slips/blob/master/slip-0032.md> with the
intent to be a hand computable version of the same idea.

P.S. It is possible that this all could be made obsolete by a threshold
musig signature scheme.

[-- Attachment #2: Type: text/html, Size: 6922 bytes --]