Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 556EEC002B for ; Thu, 23 Feb 2023 18:26:32 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 2FFFC41C49 for ; Thu, 23 Feb 2023 18:26:32 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 2FFFC41C49 Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key) header.d=blockstream-com.20210112.gappssmtp.com header.i=@blockstream-com.20210112.gappssmtp.com header.a=rsa-sha256 header.s=20210112 header.b=gDxPxb0o X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.899 X-Spam-Level: X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gkmyS10linxh for ; Thu, 23 Feb 2023 18:26:30 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 1C52741BDB Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by smtp4.osuosl.org (Postfix) with ESMTPS id 1C52741BDB for ; Thu, 23 Feb 2023 18:26:29 +0000 (UTC) Received: by mail-pf1-x42c.google.com with SMTP id d7so6460059pfu.4 for ; Thu, 23 Feb 2023 10:26:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream-com.20210112.gappssmtp.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=/6G8/uFRF4SFsG5mhStJ0yGzxPGJyi6qWArTNfahGWQ=; b=gDxPxb0ouEtwM9bFUgxhHCasdlUpgOe7SQzqQfdrbOUIm7w/XaKTtuVTtmEB33h2MD ui2bYg53W3mIPlfx1WUy3we6ZTYwkk/Bh8ttjSXjceY+Fu9Y4CwvXw0EFW6gAQNqgKaE mNxU1TxVwgpU+eH+p9Vt57jOhnJ3oB3+vMkl0pXnLTk71+Au65C9UD8cK2ytCS23P2s/ 0J8ZMUkRGH/1Ki7zb18fU5W2AWYZbrK+a4GV2k5X11u72PQwwsB+wOfUwrJrbr/cc+iP kSxnIqnopr/LuiRQDzrOfkHyFZxsHSgnJ+VIvprzVugVTae+tYzdA23VtTA7Y2VzTXF0 HYVQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=/6G8/uFRF4SFsG5mhStJ0yGzxPGJyi6qWArTNfahGWQ=; b=cXKxTBMAzACDUWWnraa6jMmNPLSoKwvB9e55PaC3WP93MoXGqnFJr67cC1pswVFo0s YmcrQ1VhHieZWbUqy7tmC2kVuMVB/TWwE/yE/Xkb9cUefjz7RegJwcdn8SHqRs/fMql5 wHuYcfnny848hzi/WO32flE93ztaKkqsoXv0yk85R5LvUoGtz7cWN3DJAMPbYYislbQd D9LSbnaqwVaz4s/fopv7ZkHfc4tco+t8FHoWma5RAgB7mBO2iz1uVELnUOVPlR3tJB0K o9U+R0AW1Kdaido2a7rwc2kJ1SD2MLEdfxOq2BUZqN5UtUMB17LzM/cjrgiAxauHoD1r fjIg== X-Gm-Message-State: AO0yUKXR1LgpnzQcrS2qW3bxJ12GIYc/uO8450HGkgQGH0rVzb1M0sXN b3gMkQL1KH6d7kKAxx76LSy5QUNYeO5NmAJbjLxif50u05/N6m8D X-Google-Smtp-Source: AK7set8aQjj8pdCQSiKFL8QYvWxLuQOtVGzzQbk+g4EikjfetKzyetXBWHpoelSv6L3O1jjRYwnlIaaL0/AJDUnupeE= X-Received: by 2002:a63:3543:0:b0:4fd:5105:eb93 with SMTP id c64-20020a633543000000b004fd5105eb93mr1935740pga.3.1677176788920; Thu, 23 Feb 2023 10:26:28 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: "Russell O'Connor" Date: Thu, 23 Feb 2023 13:26:17 -0500 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000bac28405f5622656" Subject: Re: [bitcoin-dev] Codex32 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: Thu, 23 Feb 2023 18:26:32 -0000 --000000000000bac28405f5622656 Content-Type: text/plain; charset="UTF-8" One more thing (Again apologies. This idea of doing partial verification is novel to me, and I see now that I should have just waited to give a consolidated reply). Focusing in on the example of performing 2 character quick checks. There are 7 different ways of building the table used in this quick check verification process (actually there are 8, but we only need 7 of them for our purposes here). Fun fact: If you perform the 2 character quick check in all 7 different ways, this is equivalent to doing a full checksum verification. This suggests a strategy of visiting your shares on a regular basis and performing a different 2 character quick check each time, rotating through the 7 different ways of performing it. Moreover, these 7 different 2 character quick checks come with a prescribed order that will accumulate BCH guarantees as you go along. Assuming the string isn't changing between visits then * After the 1st table you are guaranteed to detect any 1 character error. * After the 2nd table you are guaranteed to detect any 2 character error. * After the 3rd table you are guaranteed to detect any 4 character error. * After the 4th table you are guaranteed to detect any 5 character error. * After the 5th table you are guaranteed to detect any 6 character error. * After the 6th table you are guaranteed to detect any 7 character error. * After the 7th table you are guaranteed to detect any 8 character error, which is the guarantee of the full 13 character checksum. You are also guaranteed that the full 13 character checksum is now correct. You could perform the checks out of order, and that is okay. You will eventually reach these BCH levels of guarantees, just not as quickly as if you follow the prescribed order. Of course, doing a series of 7 different 2 character quick checks is overall more work than doing the full 13 character checksum validation. But there is certainly an advantage in spreading the work out over time. Each time you visit you still have the guarantee of catching any new 1 character error introduced since the last time you visited and a 99.9% chance of catching any other random errors introduced since your last visit. Personally I am likely to follow such a validation strategy myself, now that I am aware of it. On Wed, Feb 22, 2023 at 10:30 PM Russell O'Connor wrote: > After some consultation, I now see that generators for all degree 2 BCH > codes, such as ours, are smooth and factor into quadratic and linear > components. > > Anyhow the upshot of all this is that you can perform a "quickcheck" > verification of the codex32 strings for whatever size of verification you > want to do, 1 character, 2 characters, 3 characters, upto the full 13 > characters. Each of these partial verifications will have BCH properties. > A 1 character quickchecksum will guarantee to detect any 1 character > error. A 3 character quickchecksum will guarantee to detect any 2 > character error, etc. There remains a 1 in 32^n chance of failing to > detect larger numbers of errors where n is the size of your quickcheck. > > To illustrate, let's consider a quickcheck of size 2. This can detect any > 1 character error and will only have a 1/1024 chance of failing to detect > other random errors. Let's take the second test vector as our example: " > MS12NAMEA320ZYXWVUTSRQPNMLKJHGFEDCAXRPP870HKKQRM" > > You start in a specified initial state with a pair of bech32 characters. > For MS1 strings and a size 2 quickcheck it would be the pair of Bech32 > characters 'AS'. > > Next we "add" the first character after the prefix, which is '2' by using > the addition volvelle or lookup table. "Adding" '2' to 'S' yields '6' and > our state becomes 'A6'. > > Next we have to look up 'A6' in a lookup table. This table is too big to > fit in the margin of this email, so I will have to omit it. But it would > have an entry mapping 'A6' -> 'QM'. Our state becomes 'QM' > > From this point we have an even number of remaining characters in the > input string and we can work 2 characters at a time. We "add" the next two > data characters from our string, which are 'NA'. Again, using the volvelle > or lookup table we get that adding 'N' to 'Q' yields 'N', and adding 'A' to > 'M' yields 'X'. So our state is now 'NX' > > Next we look up 'NX' in this table I haven't given you and we will find an > entry mapping 'NX' -> 'DX', making 'DX' our new state. > > We keep repeating this process alternating between adding pairs of > characters and using this unstated lookup table all the way until the end > where we will reach a final state which will be 'H9'. > > If you follow this procedure with any string (upto 400 bit master seeds) > you will always end up in the state 'H9'. > > A specialized worksheet would help guide the process making the process > easier to follow. > > > This process is somewhat close to Peter Todd's suggestion of using a > lookup table on "words", which in this case would be pairs of bech32 > characters, and adding values together. The catch is that the addition is > done with Bech32 addition rather than calculator addition, which I accept > is a moderately large catch. > > Anyhow, the point is that you can do this sort of partial verification by > hand to whatever degree you like, if you are in a rush and are willing to > accept larger chances of failing to catch random errors. > > > On Wed, Feb 22, 2023 at 2:01 PM Russell O'Connor > wrote: > >> After some poking around at the math, I do see that the 13 character >> generator (for regular sized shares) is reasonably "smooth", having roots >> at T{11}, S{16}, and C{24}. >> >> This means we could build a "quick check" worksheet to evaluate the >> string modulo (x - T) to verify a 5 bit checksum, whose operation would be >> similar to the existing checksum worksheet in structure but significantly >> less work. >> >> Perhaps 5 bits is too short, and it is more reasonable working modulo (x >> - T)*(x - S) to get a 10 bit checksum. A worksheet for a 15 bit checksum >> is also an option, and possibly others well depending on the size of the >> other factors. I think this process is would be about as simple as any >> other comparable hand operated checksum over the bech32 alphabet would be. >> >> I haven't looked into the smoothness of the long generator for seeds that >> are greater than 400 bits. If it isn't smooth and smoother options are >> available, perhaps it should be changed. >> >> On Wed, Feb 22, 2023 at 11:29 AM Peter Todd via bitcoin-dev < >> bitcoin-dev@lists.linuxfoundation.org> wrote: >> >>> On Sun, Feb 19, 2023 at 10:12:51PM +0000, Andrew Poelstra via >>> bitcoin-dev wrote: >>> > > What really did catch my attention, but which was kind of buried in >>> the >>> > > project documentation, is the ability to verify the integrity of each >>> > > share independently without using a computer. For example, if I >>> store a >>> > > share with some relative who lives thousands of kilometers away, >>> I'll be >>> > > able to take that share out of its tamper-evident bag on my annual >>> > > holiday visit, verify that I can still read it accurately by >>> validating >>> > > its checksum, and put it into a new bag for another year. For this >>> > > procedure, I don't need to bring copies of any of my other shares, >>> > > allowing them (and my seed) to stay safe. >>> > > >>> > >>> > This is good feedback. I strongly agree that this is the big selling >>> > point for this -- that you can vet shares/seeds which *aren't* being >>> > actively used, without exposing them to the sorts of threats associated >>> > with active use. >>> > >>> > We should make this more prominent in the BIP motivation. >>> >>> I don't think that use-case is a good selling point. The checksum that >>> Codex32 >>> uses is much more complex than necessary if you are simply verifying a >>> share by >>> itself. >>> >>> A *much* simpler approach would be to use a simple mod N = 0 checksum, >>> either >>> by creating the seed such that each share passes, or by just storing an >>> additional word/symbol with the seed in such a way that sum(words) mod N >>> = 0 >>> passes. This approach is not only possible to compute by hand with a >>> word/symbol->number lookup table, and pen and paper or a calculator. >>> It's so >>> simple they could probably *remember* how to do it themselves. >>> >>> >>> Secondly, if all shares have mod N checksums, it may be sufficient for >>> everyone >>> to write down the checksums of the *other* shares, to verify they are the >>> correct ones and a different (otherwise correct) share hasn't >>> accidentally been >>> substituted. >>> >>> Indeed, with some brute forcing and small checksums, I'd expect it to be >>> mathematically possible to generate Shamir's secret sharing shards such >>> that >>> every shard can share the *same* checksum. In which case the share >>> verification >>> procedure would be to simply ask every share holder to verify the >>> checksum >>> manually using the mod N procedure, and then verify that each share >>> holder has >>> the same checksum. This would be less error prone in terms of leaking >>> information accidentally if the checksum was obviously *not* part of the >>> share: >>> eg by encoding the share with words, and the checksum with a number. >>> >>> Obviously, small checksums aren't fool proof. But we're probably better >>> off >>> creating a relatively easy procedure with a 1-in-1000 chance of an error >>> going >>> undetected than a complex procedure that people don't actually do at all. >>> >>> -- >>> https://petertodd.org 'peter'[:-1]@petertodd.org >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists.linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> >> --000000000000bac28405f5622656 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
One more thing (Again apologies. This idea of doing p= artial verification is novel to me, and I see now that I should have just w= aited to give a consolidated reply).

Focusing in o= n the example of performing 2 character quick checks.=C2=A0 There are 7 dif= ferent ways of building the table used in this quick check verification pro= cess (actually there are 8, but we only need 7 of them for our purposes her= e).=C2=A0 Fun fact: If you perform the 2 character quick check in all 7 dif= ferent ways, this is equivalent to doing a full checksum verification.

This suggests a strategy of visiting your shares on a = regular basis and performing a different 2 character quick check each time,= rotating through the 7 different ways of performing it.

=
Moreover, these 7 different 2 character quick checks come with a= prescribed order that will accumulate BCH guarantees as you go along.=C2= =A0 Assuming the string isn't changing between visits then

* After the 1st table you are guaranteed to detect any 1 c= haracter error.
* After the 2nd table you are guaranteed to detec= t any 2 character error.
* After the 3rd table you are guara= nteed to detect any 4 character error.
* After the 4th table= you are guaranteed to detect any 5 character error.
* After= the 5th table you are guaranteed to detect any 6 character error.
* After the 6th table you are guaranteed to detect any 7 character e= rror.
* After the 7th table you are guaranteed to detect any= 8 character error, which is the guarantee of the full 13 character checksu= m.=C2=A0 You are also guaranteed that the full 13 character checksum is now= correct.

You could perform the checks out of = order, and that is okay.=C2=A0 You will eventually reach these BCH levels o= f guarantees, just not as quickly as if you follow the prescribed order.

Of course, doing a series of 7 different 2 character= quick checks is overall more work than doing the full 13 character checksu= m validation.=C2=A0 But there is certainly an advantage in spreading the wo= rk out over time.=C2=A0 Each time you visit you still have the guarantee of= catching any new 1 character error introduced since the last time you visi= ted and a 99.9% chance of catching any other random errors introduced since= your last visit.=C2=A0 Personally I am likely to follow such a validation = strategy myself, now that I am aware of it.

<= /div>

On Wed, Feb 22, 2023 at 10:30 PM Russell O'Conno= r <roconnor@blockstream.com<= /a>> wrote:
<= div dir=3D"ltr">
After some consultation, I now see that generators for= all degree 2 BCH codes, such as ours, are smooth and factor into quadratic= and linear components.

Anyhow the upshot of all t= his is that you can perform a "quickcheck" verification of the co= dex32 strings for whatever size of verification you want to do, 1 character= , 2 characters, 3 characters, upto the full 13 characters.=C2=A0 Each of th= ese partial verifications will have BCH properties.=C2=A0 A 1 character qui= ckchecksum will guarantee to detect any 1 character error.=C2=A0 A 3 charac= ter quickchecksum will guarantee to detect any 2 character error, etc.=C2= =A0 There remains a 1 in 32^n chance of failing to detect larger numbers of= errors where n is the size of your quickcheck.

To= illustrate, let's consider a quickcheck of size 2.=C2=A0 This can dete= ct any 1 character error and will only have a 1/1024 chance of failing to d= etect other random errors.=C2=A0 Let's take the second test vector as o= ur example: "MS12NAMEA320ZYXWVUTSRQPNMLKJHGFEDCAXRPP870HKK= QRM"

= You start in a specified initial state with a pair of bech32 characters.=C2= =A0 For MS1 strings and a size 2 quickcheck it would be the pair of Bech32 = characters 'AS'.

Next we "add" t= he first character after the prefix, which is '2' by using the addi= tion volvelle or lookup table.=C2=A0 "Adding" '2' to '= ;S' yields '6' and our state becomes 'A6'.
Next we have to look up 'A6' in a lookup table.=C2=A0 = This table is too big to fit in the margin of this email, so I will have to= omit it.=C2=A0 But it would have an entry mapping 'A6' -> '= QM'.=C2=A0 Our state becomes 'QM'

= From this point we have an even number of remaining characters in the input= string and we can work 2 characters at a time. We "add" the next= two data characters from our string, which are 'NA'.=C2=A0 Again, = using the volvelle or lookup table we get that adding 'N' to 'Q= ' yields 'N', and adding 'A' to 'M' yields '= ;X'.=C2=A0 So our state is now 'NX'

Next we look up 'NX' in this table I haven't given you and we= will find an entry mapping 'NX' -> 'DX', making 'DX= ' our new state.





=

Anyhow, the point is that you can do this sort of parti= al verification by hand to whatever degree you like, if you are in a rush a= nd are willing to accept larger chances of failing to catch random errors.<= br>


On Wed, Feb 22, 2023 at 2:01 PM Russell O'= ;Connor <r= oconnor@blockstream.com> wrote:
After some poking around at th= e math, I do see that the 13 character generator (for regular sized shares)= is reasonably "smooth", having roots at T{11}, S{16}, and C{24}.=

This means we could build a "quick check&quo= t; worksheet to evaluate the string modulo (x - T) to verify a 5 bit checks= um, whose operation would be similar to the existing checksum worksheet in = structure but significantly less work.

Perhaps 5 b= its is too short, and it is more reasonable working modulo (x - T)*(x - S) = to get a 10 bit checksum.=C2=A0 A worksheet for a 15 bit checksum is also a= n option, and possibly others well depending on the size of the other facto= rs.=C2=A0 I think this process is would be about as simple as any other com= parable hand operated checksum over the bech32 alphabet would be.
=

I haven't looked into the smoothness of the long ge= nerator for seeds that are greater than 400 bits.=C2=A0 If it isn't smo= oth and smoother options are available, perhaps it should be changed.

On Wed, Feb 22, 2023 at 11:29 AM Peter Todd via bitcoi= n-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">On Sun, Feb 19, 2023 at 10= :12:51PM +0000, Andrew Poelstra via bitcoin-dev wrote:
> > What really did catch my attention, but which was kind of buried = in the
> > project documentation, is the ability to verify the integrity of = each
> > share independently without using a computer.=C2=A0 For example, = if I store a
> > share with some relative who lives thousands of kilometers away, = I'll be
> > able to take that share out of its tamper-evident bag on my annua= l
> > holiday visit, verify that I can still read it accurately by vali= dating
> > its checksum, and put it into a new bag for another year.=C2=A0 F= or this
> > procedure, I don't need to bring copies of any of my other sh= ares,
> > allowing them (and my seed) to stay safe.
> >
>
> This is good feedback. I strongly agree that this is the big selling > point for this -- that you can vet shares/seeds which *aren't* bei= ng
> actively used, without exposing them to the sorts of threats associate= d
> with active use.
>
> We should make this more prominent in the BIP motivation.

I don't think that use-case is a good selling point. The checksum that = Codex32
uses is much more complex than necessary if you are simply verifying a shar= e by
itself.

A *much* simpler approach would be to use a simple mod N =3D 0 checksum, ei= ther
by creating the seed such that each share passes, or by just storing an
additional word/symbol with the seed in such a way that sum(words) mod N = =3D 0
passes. This approach is not only possible to compute by hand with a
word/symbol->number lookup table, and pen and paper or a calculator. It&= #39;s so
simple they could probably *remember* how to do it themselves.


Secondly, if all shares have mod N checksums, it may be sufficient for ever= yone
to write down the checksums of the *other* shares, to verify they are the correct ones and a different (otherwise correct) share hasn't accidenta= lly been
substituted.

Indeed, with some brute forcing and small checksums, I'd expect it to b= e
mathematically possible to generate Shamir's secret sharing shards such= that
every shard can share the *same* checksum. In which case the share verifica= tion
procedure would be to simply ask every share holder to verify the checksum<= br> manually using the mod N procedure, and then verify that each share holder = has
the same checksum. This would be less error prone in terms of leaking
information accidentally if the checksum was obviously *not* part of the sh= are:
eg by encoding the share with words, and the checksum with a number.

Obviously, small checksums aren't fool proof. But we're probably be= tter off
creating a relatively easy procedure with a 1-in-1000 chance of an error go= ing
undetected than a complex procedure that people don't actually do at al= l.

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000bac28405f5622656--