Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id BBFB1C004C for ; 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 ; 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 ; 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 ; Mon, 3 Aug 2020 22:49:23 +0000 (UTC) Received: by mail-il1-f169.google.com with SMTP id p16so21772032ile.0 for ; 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: In-Reply-To: From: "Russell O'Connor" Date: Mon, 3 Aug 2020 18:49:10 -0400 Message-ID: To: Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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
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 for= m a partition of unity.

The consequences of these facts is that when= you perform Shamir'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.

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

Suppose we have a 128-bit ma= ster seed 0xb6721d937d82f238672de4db9= 1b87d0c.=C2=A0 We encode this secret as the following Bech32 codewor= d: "donotusesss321s2name00keepmy= masterseedunderwraps2n89wr".=C2=A0 Let's deconstruct this c= odeword.

"donotusesss32": A Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"s": 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 "s", which stands for "secret".
"<= span style=3D"font-family:monospace">2": 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 2-9 for thresholds upto 9.=C2=A0 W= e use Bech32 characters a-y for thresholds from 10 to 31."name00": The next = 6 characters are an id for this set of shares.=C2=A0 This id isn'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;qqqqqq" if you do no= t want to use it for identification.
"keepmymasterseedunderwraps": This is the 128-bit secre= t master seed 0xb6721d937d82f238672de= 4db91b87d0c encoded in Bech32.=C2=A0 The master seed can be a 128-bi= t, 256-bit or 512-bit value.
"2n89wr" is the Bech32 checksum.

We will generate shares= for a 2-of-3 threshold.=C2=A0 We generate the first share at index "<= span style=3D"font-family:monospace">a".=C2=A0 In this example = we generate "donotusesss321a2nam= e00q0h5aajczn04g9sh0wtsl2f0y0g3vlkr".

"donotusesss32": The Bech32 hrp for t= his example scheme.
"1= ": The Bech32 separator.
"a": The first data character is the index of this share which= we have chosen to be "a&= quot;.
"2": The s= econd 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 se= lected bech32 characters
"g3v= lkr" is the Bech32 checksum.

We generated the next two s= hares at index "c" a= nd and index "d".=C2= =A0 These shares are generated using characterwise Lagrange interpolation o= f the secret share and the above randomly generated share.
The resulting= shares are "donotusesss321c2nam= e00chzu58ep57hd9xmaw6zmuyjeau0kq4mr" and "donotusesss321d2name00ung8rmkf2snftj57zu45g7z84hzmzk4= r"

Notice that the resulting strings have
(1) valid c= hecksums;
(2) have correct indices;
(3) have the correct threshold va= lues;
(4) have the correct ids.

This scheme sti= ll enjoys the perfect information hiding property of Shamir's secret sh= aring.=C2=A0 Even when you know k-1 shares, every possible master se= ed value has exactly one set of shares that includes those particular k<= /i>-1 shares, so knowing k-1 shares tells you nothing about the secr= et data value.

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'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 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, r= ather than simply error detection.

This example sc= heme was inspired in part by SLIP-32 with the intent to be a hand comput= able version of the same idea.

P.S. It is poss= ible that this all could be made obsolete by a threshold musig signature sc= heme.
--0000000000001b9a9105ac00f39d--