From: "'Rama Gan' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Andrew Poelstra <apoelstra@wpsoftware•net>
Cc: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases
Date: Thu, 16 May 2024 07:43:29 +0000 [thread overview]
Message-ID: <e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me> (raw)
In-Reply-To: <ZkNqVZFNBNTq7mAL@camus>
I don't know if you have seen my previous email describing how 2-of-M is
implemented in Penlock? I sent two mails the same day, I suspect that the second
one went unnoticed; My reply below could be confusing without that piece of
context.
> FYI even in GF(P), you can do multiplication and division using slide wheels.
> I'm not sure if doing so would interfere with your other multipurpose volvelle
> constructions. (Every nonzero number in your field is 2^n for some n, so you
> can do multiplication/division by adding in the exponent.)
>
> The resulting slide wheel would not have a natural ordering.
I used this for the (K>2)-of-M case. In fact, by mapping the recovery symbols to
the right values, it is possible to achieve natural ordering (which is indeed
faster to compute). For Penlock, I used numbers instead of symbols and the
mapping `n -> (2^n) % 29`.
[1]: Recovery "symbols" mapping:
https://github.com/penlock-io/beta.penlock.io/blob/master/sdk/data/penlock-bip39.js#L92
[2]: "fusion" is done by summing the exponents using the big wheel:
https://beta.penlock.io/kofm-wheels.html
> Interesting that the splitting and recovery processes take such a long time.
> 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.
> 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
> 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?
-- Rama Gan
--
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/e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y%3D%40proton.me.
next prev parent reply other threads:[~2024-05-16 15:22 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-05-12 18:04 'Rama Gan' via Bitcoin Development Mailing List
2024-05-13 13:40 ` Andrew Poelstra
2024-05-14 12:03 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-14 13:42 ` Andrew Poelstra
2024-05-16 7:43 ` 'Rama Gan' via Bitcoin Development Mailing List [this message]
2024-05-16 13:27 ` Andrew Poelstra
2024-05-16 17:24 ` Andrew Poelstra
2024-05-24 10:39 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-24 14:14 ` Andrew Poelstra
2024-05-24 15:02 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-14 12:43 ` 'Rama Gan' via Bitcoin Development Mailing List
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me' \
--to=bitcoindev@googlegroups.com \
--cc=apoelstra@wpsoftware$(echo .)net \
--cc=ganrama@proton$(echo .)me \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox