* [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases @ 2024-05-12 18:04 'Rama Gan' via Bitcoin Development Mailing List 2024-05-13 13:40 ` Andrew Poelstra 2024-05-14 12:43 ` 'Rama Gan' via Bitcoin Development Mailing List 0 siblings, 2 replies; 11+ messages in thread From: 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-12 18:04 UTC (permalink / raw) To: bitcoindev I am excited to introduce Penlock, a printable paper-computer that guides users through secret-splitting their BIP39 seed phrase without an electronic device. A beta release is now available for peer-reviewing and early testing: https://beta.penlock.io. There are a growing number of people storing a significant portion of their savings on the blockchain. Most people use a BIP39 seed phrase to back up their wallet, but this method has disadvantages. If the seed phrase is lost or stolen, then the funds are at risk of being irremediably lost. Additionally, planning for inheritance would require entrusting the phrase to a third party, something that is not advisable. Secret splitting is a straightforward cryptographic concept that solves these issues. A 2-of-3 split produces 3 "shares"; Any 2 of these shares can be used to recover the seed phrase. Each share can be stored in a separate location and no single share can be used to reveal information about the seed phrase. Trust-minized inheritance is then possible, as one share can be given directly to an heir, and another left in the will. Unfortunately, despite commendable efforts with SLIP39, we still lack a wallet-agnostic secret splitting standard. Moreover, users who already produced their BIP39 seed phrase might be legitimately reluctant to enter it into an electronic device for the purpose of secret splitting. This is were Penlock enters the scene! Secret-splitting BIP39 seed phrases guarantees compatibility with all existing wallets. Using the analog implementation, one can run the algorithm without exposing the seed phrase to an additional electronic device. You only need a printer, a craft knife, some scissors, a pencil and paper, and a few hours of free time. Penlock was inspired by Codex32, a similar project from A. Poelstra and R. O'Connor. From there, I tried to map the design space by exploring different trade-offs, producing prototypes, benchmarking their execution speed, their ease of use, etc. While there is always room for improvement, I believe that the design of Penlock is now close enough to optimal and deserves to be released. Penlock is an open-source project that will always remain free to use. Cryptographers, developers and enthusiasts are very welcome to test and peer-review Penlock until its public release date, which is currently planned for Q3 2024. Please share any feedback or comments you may have! :) 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/9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM%3D%40proton.me. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 2024-05-12 18:04 [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases '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 12:43 ` 'Rama Gan' via Bitcoin Development Mailing List 1 sibling, 1 reply; 11+ messages in thread From: Andrew Poelstra @ 2024-05-13 13:40 UTC (permalink / raw) To: Rama Gan; +Cc: bitcoindev [-- Attachment #1: Type: text/plain, Size: 6384 bytes --] On Sun, May 12, 2024 at 06:04:09PM +0000, 'Rama Gan' via Bitcoin Development Mailing List wrote: > I am excited to introduce Penlock, a printable paper-computer that guides users > through secret-splitting their BIP39 seed phrase without an electronic device. A > beta release is now available for peer-reviewing and early testing: > https://beta.penlock.io. > > <snip> > Hi Rama, Very interesting project. I have a few unordered thoughts about this: * You have instructions for generating BIP39 seed words, but if the goal is to be compatible with existing setups, this really isn't necessary (or even desireable). If somebody is willing to generate a whole new seed and is willing to sweep their coins, they might as well just use codex32. (Perhaps they have an urgent need to do so, and cannot wait for codex32 support to arrive in mainstream wallets. Ok. But it's a pretty niche user who is panickedly updating their coins while having the patience to hand-compute things!) * Furthermore, the "just grind checksum words til the string works" approach, while ergonomic for 12 words (16 iterations max), is unrealistic for 16 words (64 iterations) and basically impossible for 24 words (256 iterations). Probably worth mentioning this. * The math underlying this all seems sound -- you map BIP39 characters directly into the field of integers mod 29, then compute lines in this field. However, the resulting checksum is then as long as your original set of words. Again, probably ok for 12 words but unreasonable for 24. (BTW, we have an unofficial BIP39 compatibility layer for codex32 which has the same issue -- everything is horrible for the 24-word case. But it is possible to do, and I've done it.) * However, the use of a characteristic-greater-than-2 field means that addition and subtraction are different operations and suddenly you need to be careful about the exact order in which your read things off the volvelles. It also makes recovering your share more complicated. I see that you currently have a table for the 2-of-3 case where you read the volvelle in different ways depending on which shares you have. Clever, but this will not extend to 2-of-n and I suspect you'll basically need to implement the full "recovery wheel" from codex32 (or the "recovery tables" which are faster to use for the 2-of-n case, though easier to use wrong). Recovery is not really that important because you only do it when you're going to put your seed into a computer, and in that case you might as well make the computer do the recovery for you, but it is unfortunate. Especially in this case where a stated goal is that the computer -won't- do anything for you because it doesn't know about the scheme. * Furthermore, this encoding into GF29 is nonstandard. I think, for the checksum construction this doesn't matter -- if the encoding becomes lost then you can just forget about the checksum, and if it doesn't, then you have a pretty great checksum (which can recover any number of errors as long as they don't hit both the data and the checksum in the same place). My feeling is that it's probably a good idea for people to use your checksum scheme on top of their existing BIP39 words, but the splitting stuff I'm less comfortable with. Possibly you would rather just combine your checksum scheme with seedxor? Though seedxor has the unfortunate need to convert your data to binary before xoring, which is time-consuming and error-prone and not compatible with the checksum so you don't have any good way to catch or fix mistakes. (The "unofficial compatibility layer for codex32" I mentioned works this way as well and it's horrible. But as you say, for users who really don't want to sweep their coins, maybe they are willing to make ugly tradeoffs..) Though I believe that seedxor only works for 2-of-3 and cannot be generalized without making the scheme unrecognizable. Alternately, if you switched to a binary field, and chose a checksum whose target residue was 0 (normally *not* recommended because it allows some classes of errors, in particular prefixes of zeroes) (though it does not allow any more substitution or erasure errors, which is what we care about for short fixed-length like this) then you could use an addition volvelle in the same way, the computation would secretly be identical to the seedxor computation, and your checksum would be preserved by it. So this is another way in which you could try to make a "seedxor-compatible checksum". But by adding a multiplicaion wheel that can do Lagrange multipliers you could generalize it to 2-of-n in a "natural" way which would break seedxor compatibility only for people who wanted more than 3 shares, and possibly even only when actually using shares beyond the third.. As a final note about seedxor, they have as a design goal that the shares look identical to full seeds; they preserve the broken bip39 checksum, have no extra characters, etc. Personally I think this goal is terrible. If you are going to use obscure hand-computation tricks you are far more likely to lose your data (or forget how to manipulate it) than you are to be robbed by a thief who understands your scheme. * More generally, you need to write up a specification and description of the math and maybe even a PDF :). I learned the scheme by reverse-engineering your Javascript, which is well-written and dependency-free, but still pretty abstract and indirect and anyway JS is not my language (nor is it likely to be the language for the typical hand-computer user). Sadly your volvelles also don't render properly in my browser (qutebrowser) which is chromium-based but maybe I have some settings wrong. Best Andrew -- 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/ZkIYXs7PgbjazVFk%40camus. [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 488 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 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 0 siblings, 1 reply; 11+ messages in thread From: 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-14 12:03 UTC (permalink / raw) To: Andrew Poelstra; +Cc: bitcoindev Hello Andrew, Thank you for sharing your thoughts. I think I fixed the biggest compatibility issues. Most browsers should now display the documents correctly, but there still are issues when using the "Print to PDF" feature. Chromium, Brave and Firefox do it well. With qutebrowser 5.x and 6.x, I get weirdly pixelated results and the wrong page margins. I'm not sure yet if it is something that I can fix, or how it will look when actually printing; I'll investigate further as soon as I can. - The "Generate a Seed Phrase" guide is useful for initializing a new hardware wallet that only supports BIP39. The guide and the worksheet only support the 12-word variant, because as you said grinding for the checksum is otherwise tedious. I guess I should add an explainer for that. I also expect that most Penlock users will already have a seed phrase and that's why I didn't mention this feature in the presentation. - About seedxor: I am not familiar with it, but it looks like something I'd want to dig in. About BIP39->binary conversion: even double-checking can't fully guarantee its correctness, so it can lead to dramatic failures. - About GF(27) being non-standard: the documents for analog computations will remain valid and available, so it's not like a software implementation that requires routine maintenance or might be discontinued. - Penlock implements arithmetic operations differently than Codex32. Additions and subtractions are implemented with a slider-wheel (only possible with GF(P)); Multiplications and "divisions" are done with volvelles. There is indeed a risk of using the slider-wheel in the wrong direction, and this is mitigated by 2-of-N not using additions at all. - An experienced user can compute a 12-words checksum in 4mins, and verify its correctness in 3 mins. Checksumming 24-word is quite doable, but then the difficulty comes with the shares derivation part that takes close to an hour and feels really tedious (again, for 24 words). For reference, an experienced user can secret-split a 12-words sentence in 45 minutes. A 24-words sentence will more than double that due to getting tired and losing focus. - The 2-of-(N<=26) case is handled with a variant of Shamir's algorithm that can be fully implemented in a single wheel. I'm about to post a presentation that will go into more details about that. For (K>=3)-of-M cases there's indeed a recovery wheel, plus a volvelle that does translation+fusion on the same side (see: https://beta.penlock.io/kofm-wheels.html). Best regards, 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/GqYxqTBUgHl6yq1UAaOc2O9Ea4-5yKnM-jGZzGaKC19c-k3KcUN_Bo2e7XPYUrNaX3NMJC0tCMudgSl0_l1BCRUz4DIYBR1ecL2ifopzs98%3D%40proton.me. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 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 0 siblings, 1 reply; 11+ messages in thread From: Andrew Poelstra @ 2024-05-14 13:42 UTC (permalink / raw) To: Rama Gan; +Cc: bitcoindev [-- Attachment #1: Type: text/plain, Size: 3814 bytes --] On Tue, May 14, 2024 at 12:03:45PM +0000, Rama Gan wrote: > Hello Andrew, > > Thank you for sharing your thoughts. > > - Penlock implements arithmetic operations differently than Codex32. Additions > and subtractions are implemented with a slider-wheel (only possible with > GF(P)); Multiplications and "divisions" are done with volvelles. There is > indeed a risk of using the slider-wheel in the wrong direction, and this is > mitigated by 2-of-N not using additions at all. > 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. > - An experienced user can compute a 12-words checksum in 4mins, and verify its > correctness in 3 mins. Checksumming 24-word is quite doable, but then the > difficulty comes with the shares derivation part that takes close to an hour > and feels really tedious (again, for 24 words). For reference, an > experienced user can secret-split a 12-words sentence in 45 minutes. A > 24-words sentence will more than double that due to getting tired and losing > focus. > The checksumming numbers are impressive but a little surprising -- in codex32, "translation" is a process of similar complexity on fewer characters and it takes me 5 minutes or so. Perhaps the difference is that you can use a slide wheel with a natural ordering, while we are using a slide chart? At some point I will work through your process and see how it feels. For what it's worth, codex32 quickchecks can be done in ~5 minutes as well. Though of course they are much less powerful than your checksum. 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. > - The 2-of-(N<=26) case is handled with a variant of Shamir's algorithm that > can be fully implemented in a single wheel. I'm about to post a presentation > that will go into more details about that. For (K>=3)-of-M cases there's > indeed a recovery wheel, plus a volvelle that does translation+fusion on the > same side (see: https://beta.penlock.io/kofm-wheels.html). 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. 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. (The reason for this is not so simple, and described in the codex32 math companion [1] ... but possibly if you believe it's true you can just "brute force" it without understanding why by just progressively constructing a wheel, doing various recoveries and filling in blank spaces by cross-referencing against your existing volvelle.) [1] https://secretcodex32.com/docs/2023-08-23--math.pdf -- 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/ZkNqVZFNBNTq7mAL%40camus. [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 488 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 2024-05-14 13:42 ` Andrew Poelstra @ 2024-05-16 7:43 ` 'Rama Gan' via Bitcoin Development Mailing List 2024-05-16 13:27 ` Andrew Poelstra 0 siblings, 1 reply; 11+ messages in thread From: 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-16 7:43 UTC (permalink / raw) To: Andrew Poelstra; +Cc: bitcoindev 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 2024-05-16 7:43 ` 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-16 13:27 ` Andrew Poelstra 2024-05-16 17:24 ` Andrew Poelstra 0 siblings, 1 reply; 11+ messages in thread From: Andrew Poelstra @ 2024-05-16 13:27 UTC (permalink / raw) To: Rama Gan; +Cc: bitcoindev [-- Attachment #1: Type: text/plain, Size: 4422 bytes --] 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. [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 488 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 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 0 siblings, 1 reply; 11+ messages in thread From: Andrew Poelstra @ 2024-05-16 17:24 UTC (permalink / raw) To: Rama Gan; +Cc: bitcoindev [-- Attachment #1: Type: text/plain, Size: 1937 bytes --] On Thu, May 16, 2024 at 01:27:55PM +0000, Andrew Poelstra wrote: > > > > [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). > Ah, I am incorrect. You can put the recovery windows on a slide wheel but it needs to use a different ordering than the one used for addition. So you would need a second wheel and possibly some relabelling of recovery windows. I don't see why this is ... it seems that the recovery windows, being differences of characters, should follow exactly the same pattern as addition (possibly in the opposite direction). So worth investigating. But assuming that it isn't possible and would require you introduce another wheel, it's probably not worth the extra "simplicity". After all, you only need to look up the windows once per share (so volvelle ergonomics are not so important) and you only need to cut out as many windows as you have shares (so setup/construction time is not bad). -- 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/ZkZBSriGn96GDLg-%40camus. [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 488 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 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 0 siblings, 1 reply; 11+ messages in thread From: 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-24 10:39 UTC (permalink / raw) To: Andrew Poelstra; +Cc: bitcoindev > Ah, I am incorrect. You can put the recovery windows on a slide wheel > but it needs to use a different ordering than the one used for addition. > So you would need a second wheel and possibly some relabelling of > recovery windows. > > I don't see why this is ... it seems that the recovery windows, being > differences of characters, should follow exactly the same pattern as > addition (possibly in the opposite direction). So worth investigating. No, no, you were right, it can be done. If you want to find the difference between A[2] and D[5], you can place the pointer on A, find D on the outer ring and the corresponding inner-ring character will be B[3]. Then, it is possible to write the numerical values under the first 14 characters as you suggested before. (We only care about the _shortest_ distance.) I chose to use a window because it's less "verbose". I didn't want to clutter the wheel with information that you'd use only once per recovery. (Using the window is in fact more compact.) About a header, the problem is that the fast 2-of-M algorithm won't preserve constant values across shares as Codex32 does. In Penlock, the header information is simply printed/written on the share instead of being encoded. The best I can do is to tweak both algorithm so that you can derive the secret and share's index correctly, by using "-[28]" as the secret's index. (But the secret is not a point on the line, and the share at X=28 would have a different value, so that might be more confusing than anything) -- 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/EfekwtxUZKN_4z53hjqo7lXhcMDaRHlIC-EOWNjcpL_cJgeYPa1-_1g0b6PxLZPEL0oj7YAXEWK7yg7WiEHH2FkIk7WHIFGwjMB1zoxYb6M%3D%40proton.me. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 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 0 siblings, 1 reply; 11+ messages in thread From: Andrew Poelstra @ 2024-05-24 14:14 UTC (permalink / raw) To: Rama Gan, g; +Cc: bitcoindev [-- Attachment #1: Type: text/plain, Size: 930 bytes --] On Fri, May 24, 2024 at 10:39:57AM +0000, Rama Gan wrote: > > About a header, the problem is that the fast 2-of-M algorithm won't preserve > constant values across shares as Codex32 does. > Are you sure? It seems that if two shares have the same value in a given position, the line through them should be constant, meaning that every other share will have the same constant value. -- 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/ZlCg2C4kZSGUN3Qx%40camus. [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 488 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 2024-05-24 14:14 ` Andrew Poelstra @ 2024-05-24 15:02 ` 'Rama Gan' via Bitcoin Development Mailing List 0 siblings, 0 replies; 11+ messages in thread From: 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-24 15:02 UTC (permalink / raw) To: Andrew Poelstra; +Cc: bitcoindev > Are you sure? It seems that if two shares have the same value in a given > position, the line through them should be constant, meaning that every > other share will have the same constant value. For the 2-of-M split, the secret is encoded as the difference between two consecutive shares instead of being a point at a given index. If both the secret and share A have a header `HEAD`, then share B will start with `====` (zeros) and share C will be the additive inverse of `HEAD`. The secret is the "slope" of the line; for the shares headers to be constant, the solution would be to fill the corresponding spots with zeros on the secret. So yes it _is_ possible, but then the 2-of-M and the K-of-M cases will behave differently which could be a source of confusion. I guess it is the cons of going for a composite scheme. -- 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/x8ORFhCMjZL-ViYGSXl9ek_bfU231h6sOnG97aMj6tOT3cmKKRDS8PJsfFbvfRrzGTbZLuHzSOCwmc7mGwBSxBHGAfLUyydX-OZNPYHvfrQ%3D%40proton.me. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 2024-05-12 18:04 [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases 'Rama Gan' via Bitcoin Development Mailing List 2024-05-13 13:40 ` Andrew Poelstra @ 2024-05-14 12:43 ` 'Rama Gan' via Bitcoin Development Mailing List 1 sibling, 0 replies; 11+ messages in thread From: 'Rama Gan' via Bitcoin Development Mailing List @ 2024-05-14 12:43 UTC (permalink / raw) To: bitcoindev In this message I'm going to briefly describe the cryptographic components of Penlock. I won't cover Shamir Secret Sharing here, as it is a well-known algorithm. Note that A. Poelstra and R. O'Connor previously explained its implementation on paper-computer, as well as other shenanigans, in codex32's mathematical companion: https://secretcodex32.com/docs/2023-08-23--math.pdf. ## Overview Penlock uses a composite secret splitting algorithm: 2-of-M splitting is implemented with a "paper-friendly" algorithm, whilst for (K>2)-of-M it falls back to Shamir Secret Sharing. In both cases, GF(29) is used (i.e.: all arithmetic operations are modulo 29). Using GF(Prime) allows for optimizations in the paper implementation that were not possible with fields in the form GF(2^N). ## Character Set Penlock uses a character set composed of the 26 Latin characters and the symbols `-`, `=` and `+`. Each character represents a corresponding integer, that I will write between square brackets in this document; for example: =[0], +[1], A[2], Z[27], -[28]. ## 2-of-M Splitting The concept behind the 2-of-M algorithm is relatively simple: it encodes a secret as the difference between two consecutive shares. For example, let's split "B[3]" into 3 shares: 1. Pick a random character for Share A: say G[8] 2. Derive Share B by subtracting the secret from Share A: G[8] - B[3] = D[5] 3. Derive Share C by subtracting the secret from Share B: D[5] - B[3] = A[2] We get: ShareA = G[8], ShareB = D[5], ShareC = A[2] Note that each of the shares taken separately is merely a random number and doesn't contain any information about the secret. The secret can be recovered by computing the difference between two shares, divided by the distance between these shares. For example, let's recover the previous secret from shares A and C: ``` Secret = (ShareA - ShareC) / distance(ShareA, ShareC) = (G[8] - A[2]) / 2 = E[6] / 2 = B[3] ``` In this example we did split only one character, but a complete phrase will be split similarly by splitting its characters one after another. Cryptographers might recognize that algorithm as a variation of Shamir Secret Sharing. To summarize, Shamir's 2-of-M encodes the secret at a specific x of `f(x) = ax + b`, while Penlock's 2-of-M encodes it as the `a` in `f(x) = -ax + b` (Share A being `b`). ## Checksum Additionally, Penlock uses a simple checksum that guarantees error-free results despite potential manipulation errors. For any given piece of data, the checksum will be composed of the differences between each two consecutive characters. For example: ``` Data : C[04] O[16] I[10] N[15] Checksum: Q[18] K[12] V[23] D[05] Because : O[16] - C[04] = K[12] I[10] - O[16] = V[23] (-6 % 29) N[15] - I[10] = D[05] C[04] - N[15] = Q[18] (-11 % 29) ``` This checksum has been specifically designed for Penlock needs. It is great at detecting and locating errors, but unless bech32 it is bad at repairing missing data. This trade-off seems acceptable because secret splitting already provides data redundancy (i.e.: if one share gets damaged, it is possible to fix it using the two other shares). ## Implementation The arithmetic operations used for 2-of-M splitting and checksumming are implemented within a single wheel that can be printed from https://beta.penlock.io/2ofm-wheel.html. The outer rings of the wheel implement the addition and the subtraction, and the spiral in the middle implements the division. A step-by-step guide for computing the checksum shown above, but with the wheel, can be found in the example of "Generating the Checksums" at https://beta.penlock.io/2of3-guide.html. -- 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/9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM%3D%40proton.me. ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2024-05-24 15:08 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2024-05-12 18:04 [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases '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 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
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox