Delivery-date: Thu, 16 May 2024 08:22:07 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) client-ip=66.183.0.205;
Date: Thu, 16 May 2024 13:27:55 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Rama Gan <ganrama@proton.me>
Cc: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39
 seed phrases
Message-ID: <ZkYJ21cloqyvT93G@camus>
References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
 <ZkIYXs7PgbjazVFk@camus>
 <GqYxqTBUgHl6yq1UAaOc2O9Ea4-5yKnM-jGZzGaKC19c-k3KcUN_Bo2e7XPYUrNaX3NMJC0tCMudgSl0_l1BCRUz4DIYBR1ecL2ifopzs98=@proton.me>
 <ZkNqVZFNBNTq7mAL@camus>
 <e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="0W3JydEiLSLDNNv1"
Content-Disposition: inline
In-Reply-To: <e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com


--0W3JydEiLSLDNNv1
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline

On Thu, May 16, 2024 at 07:43:29AM +0000, Rama Gan wrote:
> > But I guess this is explained by the large number of characters produced by
> > the checksum.
> 
> For clarity, 45 mins was from a benchmark in real conditions. It includes the
> whole process of copying the seed phrase, checksumming it, generating the random
> share A, checksumming it, deriving both shares B and C, verifying the checksums
> and finally correcting a few mistakes. Recovery took 20 minutes.
> 
> The checksum is the second source of inefficiency, the first one being that
> BIP39 isn't compact. GF(29) can encode 128 bits within 7 words, and the checksum
> would cost 7 more words. In comparison, BIP39 low density of information costs
> 10 more words (5 data + 5 checksum). With a compact data format, the entire
> 2-of-3 split process would take less than 30 minutes; and recovery with
> verification would be under 15 minutes. I don't know if it can be optimized
> further, but we're already looking at figures that the general public might find
> acceptable.
>

With BIP39 density you have 24 words (96 characters). With GF29
compaction you could get this down to 14 words (56 characters). But
codex32 does the same in 45 characters, plus a fixed/preprinted HRP.
(And 6 of those 45 are a header which is usually faster to deal with
since you're always dealing with the same characters.)

In your case, since there's no way to get down to 48 characters, I
wouldn't bother trying to compress any further. Either you fit in one
side of a cryptosteel (no) or you fit in two sides of a cryptosteel or
into a tube (yes, even without compression).

And I agree that the existing figures are not bad, especially because
the checksumming (which is the most common and also the least fun) is so
fast.

I think if you were able to squeeze an extra word of header data or
version info, that would be worth doing, but probably not at the expense
of making the user do a re-encoding phase. Which I suspect would be
needed to try to get more information density out of your characters.

> > Very cool. Though you say "single wheel" but you actually need two -- one to
> > get the solving window and one to actually do the recovery. If I understand
> > correctly, the "solving window" is equivalent to a "recovery symbol" in
> > codex32.
> 
> The solving window is the is the distance between two shares, and not a Lagrange
> basis (to the best of my knowledge). It can be determined from the same single
> wheel, that already implements subtraction.
>
> [3]: The 2-of-M wheel "Recovery" window shows the distance between two shares:
> https://beta.penlock.io/2ofm-wheel.html
>

Ah, I understand. Looking again at your wheel, I see that it's a
combination slide wheel (for addition/subtraction) and slide chart (for
"recovery windows").

What I'm saying is that you don't need to have extra cutout windows for
the recovery windows. You should be able to just label the characters on
the inner wheel with them, similar to how you have already labeled =
with (1).

> > If so, despite the simple interpretation as "the difference between the
> > shares", this object is secretly a Lagrange polynomial and you can _also_
> > compute it using a slide wheel rather than a full lookup-table volvelle.
> 
> I'm not sure if I understand that, but it sounds like I missed an optimization
> opportunity there. Can I ask you to develop that point a little?
>

I don't think this discussion of Lagrange polynomials is relevant
actually. My point is that you don't need the cutout squares, and I
think this is clearer if you think in terms of share index differences
than if you think in terms of Lagrange polynomials.

But. What I'm saying is that if you do the Lagrange polynomial
calculation using the formula from Wikipedia, magically your differences
will appear. They're the same thing, just expressed differently.

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZkYJ21cloqyvT93G%40camus.

--0W3JydEiLSLDNNv1
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmZGCdsACgkQxYjWPOQb
l8EHqQf8D7rFLlb9u92OB1SkmeAm5UhZx5Gt7NlJyGg1pfkm3I3P5vrqJNfjmO4v
nMP4bWruJ6DlINYkEAmi034nm+gbkWfzzFB+cW5Adx1iSCXVFepChaMAmY0GCKPh
g9cXf4wNlkDeqy3tX2ZUeXYVuB0DBKwePGHrQXgN/g1zKyAX92OhSggzNsLhzq2r
zv65QBC9o213OlXmeuxmq5AqH6btpWnN1Bdx+O2/TEOTiT9zgZQU21ojfyPOkPbz
Qe4DIlML56ga3IoS75MgDl4ae54eLl+jnZWQ6QvalsjQhvejzpaxRx+04dRnx6ft
/eMPKoDd4jo3MTfcSu/P4hbtXEVHmg==
=fvPO
-----END PGP SIGNATURE-----

--0W3JydEiLSLDNNv1--