path: root/d9/92347ecf832fdd63c10790f1e52933c231c34c

Return-Path: <roconnor@blockstream.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 9FD5BC002B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 22 Feb 2023 19:01:26 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 663F5419BC
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 22 Feb 2023 19:01:26 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 663F5419BC
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=r0Kt9+xB
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 fvXWZwI1713C
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 22 Feb 2023 19:01:23 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 37EDD419BB
Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com
 [IPv6:2607:f8b0:4864:20::102e])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 37EDD419BB
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 22 Feb 2023 19:01:23 +0000 (UTC)
Received: by mail-pj1-x102e.google.com with SMTP id
 nw10-20020a17090b254a00b00233d7314c1cso10056916pjb.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 22 Feb 2023 11:01:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=blockstream-com.20210112.gappssmtp.com; s=20210112;
 h=cc:to:subject:message-id:date:from:in-reply-to:references
 :mime-version:from:to:cc:subject:date:message-id:reply-to;
 bh=BbNvUyCiEq+Nom9AQFXA5Uokcy2ZixzDcf4XQ4DgPsg=;
 b=r0Kt9+xBrMdedvfJoeDawTIxN+CoNnqW8WVi8L0WSrVQPUxFgJ4DEOeFenqiYDZp56
 bZ3OQ/9xyDyyPWnPXkvv3bVff+j7e1/FRWRlXV1Dlpt3lQ3zNTSRZGnYoWW6tYQ7KTwi
 67tlhWV6pNsy5t00u8Ad6KqmAQ11p05E8qEsB6t7YM12rsa0A6Jv2xczmqbcuK3IcTsr
 iuJwDr9OZY4SbK8prOqg1jwbYQxyYprJyzucQny5yIiYbaWBE3i6xd+MFJ34TpACXkwa
 fhBcXhpzYbmFJ1H0A6eAuhREFmKEbKvL3GI7jetHNiKFdsUtZghWGKXxzNjwxo39oPgD
 OIww==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=cc: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=BbNvUyCiEq+Nom9AQFXA5Uokcy2ZixzDcf4XQ4DgPsg=;
 b=0HpfXADljQToYYnIZO1bWRUdFfLJ6UMS2mTyB8DG2tR3Gy15HumBage76bdFIcG/vm
 igk8Ti8hacOQYQr3rI42JHPf47mfxWB13X/w+2Taw0gmgH853TZ+n7fR2snlCh1JHJqX
 WjXY+HlRC/WWbFair3jZqsSG/paIoP50+GdC/vmkakc6EAtGWaxQeH4ID7SDdqStrVQL
 HRDLWHum8eiMTXnrIEs5FF2RAZ6ZY1TlpHPJAWjdYFkoEUQvP/b18XQdVeNNLQW74EH0
 5UlA63uzOKKKKEsgPtXlXDGD2asdjvDgUiGh8UfX1JjmvD8KNBvuiW/Q8KqxygYPd24R
 ZYMA==
X-Gm-Message-State: AO0yUKVQuEnJjZpXr3reGeFpWWzFv1u1zCBHViclbxn8RqB/hi7Iotl0
 MLQZHuG92t5qjDrHJcgt7YHP+ObFdZtzBtWO18xyksjecK6UZ/bC
X-Google-Smtp-Source: AK7set/V+4wo0umS47Ozpxrkddem4LyBDXJTWnMKst+eW0otOAndcKV8P7/6vv+zrqGjKy7I7W2RprDBwv4jf/8CkDk=
X-Received: by 2002:a17:90b:4cd0:b0:234:690:cf7c with SMTP id
 nd16-20020a17090b4cd000b002340690cf7cmr2253028pjb.37.1677092482508; Wed, 22
 Feb 2023 11:01:22 -0800 (PST)
MIME-Version: 1.0
References: <CAMZUoKmiwXW50F2onqNUZO8HXQa4+Z=z3s3WyN7-rAMV=KiSgw@mail.gmail.com>
 <CAF90AvmaRYO6HKn9npyfzO6M6FZnN6DRhqopLpeSnHJNK=5i9g@mail.gmail.com>
 <Y+40gVnMpj0prfQk@camus> <f19acdabd3fbc0ff389669131acbb79e@dtrt.org>
 <Y/Ke4yV7eV/87Kat@camus> <Y/ZCz2JlYiQ1MvaG@petertodd.org>
In-Reply-To: <Y/ZCz2JlYiQ1MvaG@petertodd.org>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Wed, 22 Feb 2023 14:01:10 -0500
Message-ID: <CAMZUoK=j8spJv8UEu1WoThWL=gSrU=Gq+=mg3i9yA7V8+6susw@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000ad0c3705f54e85c6"
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 <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: Wed, 22 Feb 2023 19:01:26 -0000

--000000000000ad0c3705f54e85c6
Content-Type: text/plain; charset="UTF-8"

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
>

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

<div dir=3D"ltr"><div>After some poking around at the math, I do see that t=
he 13 character generator (for regular sized shares) is reasonably &quot;sm=
ooth&quot;, having roots at T{11}, S{16}, and C{24}.</div><div><br></div><d=
iv>This means we could build a &quot;quick check&quot; worksheet to evaluat=
e the string modulo (x - T) to verify a 5 bit checksum, whose operation wou=
ld be similar to the existing checksum worksheet in structure but significa=
ntly less work.</div><div><br></div><div>Perhaps 5 bits is too short, and i=
t is more reasonable working modulo (x - T)*(x - S) to get a 10 bit checksu=
m.=C2=A0 A worksheet for a 15 bit checksum is also an option, and possibly =
others well depending on the size of the other factors.=C2=A0 I think this =
process is would be about as simple as any other comparable hand operated c=
hecksum over the bech32 alphabet would be.<br></div><div><br></div><div>I h=
aven&#39;t looked into the smoothness of the long generator for seeds that =
are greater than 400 bits.=C2=A0 If it isn&#39;t smooth and smoother option=
s are available, perhaps it should be changed.<br></div><div dir=3D"ltr"></=
div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On=
 Wed, Feb 22, 2023 at 11:29 AM Peter Todd via bitcoin-dev &lt;<a href=3D"ma=
ilto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundati=
on.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left: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:<br>
&gt; &gt; What really did catch my attention, but which was kind of buried =
in the<br>
&gt; &gt; project documentation, is the ability to verify the integrity of =
each<br>
&gt; &gt; share independently without using a computer.=C2=A0 For example, =
if I store a<br>
&gt; &gt; share with some relative who lives thousands of kilometers away, =
I&#39;ll be<br>
&gt; &gt; able to take that share out of its tamper-evident bag on my annua=
l<br>
&gt; &gt; holiday visit, verify that I can still read it accurately by vali=
dating<br>
&gt; &gt; its checksum, and put it into a new bag for another year.=C2=A0 F=
or this<br>
&gt; &gt; procedure, I don&#39;t need to bring copies of any of my other sh=
ares,<br>
&gt; &gt; allowing them (and my seed) to stay safe.<br>
&gt; &gt; <br>
&gt; <br>
&gt; This is good feedback. I strongly agree that this is the big selling<b=
r>
&gt; point for this -- that you can vet shares/seeds which *aren&#39;t* bei=
ng<br>
&gt; actively used, without exposing them to the sorts of threats associate=
d<br>
&gt; with active use.<br>
&gt; <br>
&gt; We should make this more prominent in the BIP motivation.<br>
<br>
I don&#39;t think that use-case is a good selling point. The checksum that =
Codex32<br>
uses is much more complex than necessary if you are simply verifying a shar=
e by<br>
itself.<br>
<br>
A *much* simpler approach would be to use a simple mod N =3D 0 checksum, ei=
ther<br>
by creating the seed such that each share passes, or by just storing an<br>
additional word/symbol with the seed in such a way that sum(words) mod N =
=3D 0<br>
passes. This approach is not only possible to compute by hand with a<br>
word/symbol-&gt;number lookup table, and pen and paper or a calculator. It&=
#39;s so<br>
simple they could probably *remember* how to do it themselves.<br>
<br>
<br>
Secondly, if all shares have mod N checksums, it may be sufficient for ever=
yone<br>
to write down the checksums of the *other* shares, to verify they are the<b=
r>
correct ones and a different (otherwise correct) share hasn&#39;t accidenta=
lly been<br>
substituted.<br>
<br>
Indeed, with some brute forcing and small checksums, I&#39;d expect it to b=
e<br>
mathematically possible to generate Shamir&#39;s secret sharing shards such=
 that<br>
every shard can share the *same* checksum. In which case the share verifica=
tion<br>
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<br>
the same checksum. This would be less error prone in terms of leaking<br>
information accidentally if the checksum was obviously *not* part of the sh=
are:<br>
eg by encoding the share with words, and the checksum with a number.<br>
<br>
Obviously, small checksums aren&#39;t fool proof. But we&#39;re probably be=
tter off<br>
creating a relatively easy procedure with a 1-in-1000 chance of an error go=
ing<br>
undetected than a complex procedure that people don&#39;t actually do at al=
l.<br>
<br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>

--000000000000ad0c3705f54e85c6--