Delivery-date: Thu, 16 May 2024 08:22:01 -0700
Received-SPF: pass (google.com: domain of ganrama@proton.me designates 185.70.43.19 as permitted sender) client-ip=185.70.43.19;
Date: Thu, 16 May 2024 07:43:29 +0000
To: Andrew Poelstra <apoelstra@wpsoftware.net>
From: "'Rama Gan' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Cc: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39
 seed phrases
Message-ID: <e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me>
In-Reply-To: <ZkNqVZFNBNTq7mAL@camus>
References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me> <ZkIYXs7PgbjazVFk@camus> <GqYxqTBUgHl6yq1UAaOc2O9Ea4-5yKnM-jGZzGaKC19c-k3KcUN_Bo2e7XPYUrNaX3NMJC0tCMudgSl0_l1BCRUz4DIYBR1ecL2ifopzs98=@proton.me> <ZkNqVZFNBNTq7mAL@camus>
Feedback-ID: 79991369:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Reply-To: Rama Gan <ganrama@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

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.