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.
_______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
