path: root/98/d1e214b7fa5b851b5dbdfc8f3fefd38ea322af

Return-Path: <roconnor@blockstream.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id BBFB1C004C
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  3 Aug 2020 22:49:25 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by silver.osuosl.org (Postfix) with ESMTP id 9C71F21574
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  3 Aug 2020 22:49:25 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 8vqITeQrlL+O
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  3 Aug 2020 22:49:23 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail-il1-f169.google.com (mail-il1-f169.google.com
 [209.85.166.169])
 by silver.osuosl.org (Postfix) with ESMTPS id 5B2EE204F1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  3 Aug 2020 22:49:23 +0000 (UTC)
Received: by mail-il1-f169.google.com with SMTP id p16so21772032ile.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 03 Aug 2020 15:49:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=blockstream-com.20150623.gappssmtp.com; s=20150623;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
 bh=52faBX0GjkTkEn1vl8wLC95mgVH6aKMKlfaQWnYxB28=;
 b=LQISM8h2RnKU0u04a8np7h6TFifqu4DNuPIFHSbqTU1bcxe18dHBIaj46bIgvyuPuj
 Eq1sEleWxfo46IQgNgy6Xbnjkc/9JBYLoc7q/alatNo2sYH8G7W5I+12NmcgF0AnEs9U
 pHI5ltAwL0we4VCzu/JwQytwD986Tv1K06YuRG4hnWoN+p+1ztF+PMt16BfXuOwMceFf
 XnDCKzfOtqNipDPG6xFHmgFRy2nRhcSNrjTnd4cx5InT5qipVi2v/mju5FUqXIHA1wIp
 stdy/0Td1IYlOKLF8Q773O6lC6pJp02jvWI1sfRO2VodyksflDdSEsp5w3LiMMB5WbvG
 cTYA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to;
 bh=52faBX0GjkTkEn1vl8wLC95mgVH6aKMKlfaQWnYxB28=;
 b=mFLLnspIhHQ2pvFmtdYvahiubwjnCvo0RmEbMaAmTLCUBKFRNJCvAA1pDpYw5SWvOw
 AoAsY90E8MKI+bZuUvl5LNoCpMEncw7RDhBgwM3AfM2wP/iFHpXkIpQHS3eN9ZRiu4e/
 DBD9fVA26wSs+NPJJPfWC0LQbHEVwZRif8jXeSv7qOWVVWLMBZzMWraQjM+x7+mflJ7H
 RQD++9l3Im/wKed3KkmHUTdcIfpW2bOtLwONNx/99vx2YTQiyzbyrTmEpS5q/+8250VB
 NPcyXlG+ExNwPM5iWLvjw83/3zj0Ca/AqkUWNhr1xKJ2rlsgY18PW4sOv1pK52J8X0ww
 KzDg==
X-Gm-Message-State: AOAM530KxcIGI5wsY7LyB4r9mcMRfwLqcXLdekb7NIFRai9p4prVJspr
 NrJLX/GF2EJtl5Q7/Nq60DWif8JGOmTVD71zPVYZCBkCScs=
X-Google-Smtp-Source: ABdhPJxbqzpjP9eMVo/uuHXCMXE1ep53GRwhghZPwOOU3BQvOkRoSwI37rN5Lfkvblw9MSMR1WvX7z8W9kYD/Sdys6E=
X-Received: by 2002:a92:d60b:: with SMTP id w11mr1610160ilm.156.1596494962195; 
 Mon, 03 Aug 2020 15:49:22 -0700 (PDT)
MIME-Version: 1.0
References: <CAEcfjBRCA1sKcFC5M++WECsgYD-jDBYGuwxLfh0PSzRkCehEDA@mail.gmail.com>
 <CAD5xwhgP=9-AvMOVO+-b9c3DZ_vYd-bPLYM26Qvawmcj28UOZw@mail.gmail.com>
 <CAMZUoKnNK-_shu4BQXK=FbtqYUn8MT=yjNDY1VFx73AAcSAzsQ@mail.gmail.com>
In-Reply-To: <CAMZUoKnNK-_shu4BQXK=FbtqYUn8MT=yjNDY1VFx73AAcSAzsQ@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Mon, 3 Aug 2020 18:49:10 -0400
Message-ID: <CAMZUoKnA4cMTDYnvcUQo9N+1T9pZCjGg4WGbFgaox4BaXao2QA@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000001b9a9105ac00f39d"
Subject: [bitcoin-dev] On the compatibility of Bech32 and Shamir's Secret
	Sharing
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 03 Aug 2020 22:49:25 -0000

--0000000000001b9a9105ac00f39d
Content-Type: text/plain; charset="UTF-8"

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.

--0000000000001b9a9105ac00f39d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">With the help of Pieter I&#39;ve recently=
 made some interesting mathematical observations about Bech32 codewords and=
 Shamir&#39;s secret sharing:<br><br>(1) Affine combinations of two Bech32 =
codewords is again a valid Bech32 codeword.<br>(2) Lagrange polynomials for=
m a partition of unity.<br><br>The consequences of these facts is that when=
 you perform Shamir&#39;s secret sharing where all your shares have valid B=
ech32 checksums, then the resulting secret will also have a valid Bech32 ch=
ecksum.=C2=A0 Conversely, if your secret has a valid Bech32 checksum, and y=
our random shares have valid Bech32 checksums, then all your derived shares=
 will have valid Bech32 checksums.=C2=A0 This can form a basis on which we =
can build a simple secret sharing scheme for dividing up a BIP-32 master se=
ed.<br><br>In order to illustrate this, I&#39;ll describe an example scheme=
 for <i>k</i>-of-<i>n</i> Shamir&#39;s secret sharing scheme where <i>2 &lt=
;=3D k</i> &lt;=3D <i>n</i> &lt;=3D 31.<br><br>Suppose we have a 128-bit ma=
ster seed <span style=3D"font-family:monospace">0xb6721d937d82f238672de4db9=
1b87d0c</span>.=C2=A0 We encode this secret as the following Bech32 codewor=
d: &quot;<span style=3D"font-family:monospace">donotusesss321s2name00keepmy=
masterseedunderwraps2n89wr</span>&quot;.=C2=A0 Let&#39;s deconstruct this c=
odeword.<br><br>&quot;<span style=3D"font-family:monospace">donotusesss32</=
span>&quot;: A Bech32 hrp for this example scheme.<br>&quot;<span style=3D"=
font-family:monospace">1</span>&quot;: The Bech32 separator.<br>&quot;<span=
 style=3D"font-family:monospace">s</span>&quot;: The first data character i=
s the index of this share. Each index is a Bech32 character.=C2=A0 In this =
scheme the secret share is always at index &quot;<span style=3D"font-family=
:monospace">s</span>&quot;, which stands for &quot;secret&quot;.<br>&quot;<=
span style=3D"font-family:monospace">2</span>&quot;: The second data charac=
ter is the threshold.=C2=A0 In this example we are using a 2-of-n threshold=
.=C2=A0 We use the digits <span style=3D"font-family:monospace">2</span>-<s=
pan style=3D"font-family:monospace">9</span> for thresholds upto 9.=C2=A0 W=
e use Bech32 characters <span style=3D"font-family:monospace">a</span>-<spa=
n style=3D"font-family:monospace">y</span> for thresholds from 10 to 31.<br=
>&quot;<span style=3D"font-family:monospace">name00</span>&quot;: The next =
6 characters are an id for this set of shares.=C2=A0 This id isn&#39;t part=
 of the secret data. It is used to ensure that the shares you are reconstru=
cting were generated for the same secret.=C2=A0 This id just needs to be un=
ique 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 &=
quot;<span style=3D"font-family:monospace">qqqqqq</span>&quot; if you do no=
t want to use it for identification.<br>&quot;<span style=3D"font-family:mo=
nospace">keepmymasterseedunderwraps</span>&quot;: This is the 128-bit secre=
t master seed <span style=3D"font-family:monospace">0xb6721d937d82f238672de=
4db91b87d0c</span> encoded in Bech32.=C2=A0 The master seed can be a 128-bi=
t, 256-bit or 512-bit value.<br>&quot;<span style=3D"font-family:monospace"=
>2n89wr</span>&quot; is the Bech32 checksum.<br><br>We will generate shares=
 for a 2-of-3 threshold.=C2=A0 We generate the first share at index &quot;<=
span style=3D"font-family:monospace">a</span>&quot;.=C2=A0 In this example =
we generate &quot;<span style=3D"font-family:monospace">donotusesss321a2nam=
e00q0h5aajczn04g9sh0wtsl2f0y0g3vlkr</span>&quot;.<br><br>&quot;<span style=
=3D"font-family:monospace">donotusesss32</span>&quot;: The Bech32 hrp for t=
his example scheme.<br>&quot;<span style=3D"font-family:monospace">1</span>=
&quot;: The Bech32 separator.<br>&quot;<span style=3D"font-family:monospace=
">a</span>&quot;: The first data character is the index of this share which=
 we have chosen to be &quot;<span style=3D"font-family:monospace">a</span>&=
quot;.<br>&quot;<span style=3D"font-family:monospace">2</span>&quot;: The s=
econd data character is the threshold, which is 2.<br>&quot;<span style=3D"=
font-family:monospace">name00</span>&quot;: The next 6 characters is the id=
 we chose above for this set of shares.<br>&quot;<span style=3D"font-family=
:monospace">q0h5aajczn04g9sh0wtsl2f0y0</span>&quot;: This is 26 randomly se=
lected bech32 characters<br>&quot;<span style=3D"font-family:monospace">g3v=
lkr</span>&quot; is the Bech32 checksum.<br><br>We generated the next two s=
hares at index &quot;<span style=3D"font-family:monospace">c</span>&quot; a=
nd and index &quot;<span style=3D"font-family:monospace">d</span>&quot;.=C2=
=A0 These shares are generated using characterwise Lagrange interpolation o=
f the secret share and the above randomly generated share.<br>The resulting=
 shares are &quot;<span style=3D"font-family:monospace">donotusesss321c2nam=
e00chzu58ep57hd9xmaw6zmuyjeau0kq4mr</span>&quot; and &quot;<span style=3D"f=
ont-family:monospace">donotusesss321d2name00ung8rmkf2snftj57zu45g7z84hzmzk4=
r</span>&quot;<br><br>Notice that the resulting strings have<br>(1) valid c=
hecksums;<br>(2) have correct indices;<br>(3) have the correct threshold va=
lues;<br>(4) have the correct ids.</div><div><br></div><div>This scheme sti=
ll enjoys the perfect information hiding property of Shamir&#39;s secret sh=
aring.=C2=A0 Even when you know <i>k</i>-1 shares, every possible master se=
ed value has exactly one set of shares that includes those particular <i>k<=
/i>-1 shares, so knowing <i>k</i>-1 shares tells you nothing about the secr=
et data value.</div><div><br></div><div>One nice property of Lagrange inter=
polation is that it is simple enough to compute by hand with the help of a =
few lookup tables.=C2=A0 Bech32 checksums can also be computed and checked =
by hand with the help of lookup tables.=C2=A0 While the majority of users w=
ouldn&#39;t do hand computations, those motivated users who have a healthy =
distrust of digital devices can generate and manipulate the secret shares b=
y hand.=C2=A0 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.=C2=A0 My =
SSS32 repository at <a href=3D"https://github.com/roconnor-blockstream/SSS3=
2">https://github.com/roconnor-blockstream/SSS32</a> has a postscript file =
that generates the lookup tables needed for hand computation, although the =
document is a bit disorganized at the moment.<br></div><div><br></div><div>=
 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, r=
ather than simply error detection.</div><div><br></div><div>This example sc=
heme was inspired in part by <a href=3D"https://github.com/satoshilabs/slip=
s/blob/master/slip-0032.md">SLIP-32</a> with the intent to be a hand comput=
able version of the same idea.<br></div><div><br></div><div>P.S. It is poss=
ible that this all could be made obsolete by a threshold musig signature sc=
heme.<br></div></div>

--0000000000001b9a9105ac00f39d--