📅 Original date posted:2023-02-23
🗒️ Summary of this message: Generators for degree 2 BCH codes are smooth and factor into quadratic and linear components, allowing for partial verification of codex32 strings.
📝 Original message:After some consultation, I now see that generators for all degree 2 BCH
codes, such as ours, are smooth and factor into quadratic and linear
components.
Anyhow the upshot of all this is that you can perform a "quickcheck"
verification of the codex32 strings for whatever size of verification you
want to do, 1 character, 2 characters, 3 characters, upto the full 13
characters. Each of these partial verifications will have BCH properties.
A 1 character quickchecksum will guarantee to detect any 1 character
error. A 3 character quickchecksum will guarantee to detect any 2
character error, etc. There remains a 1 in 32^n chance of failing to
detect larger numbers of errors where n is the size of your quickcheck.
To illustrate, let's consider a quickcheck of size 2. This can detect any
1 character error and will only have a 1/1024 chance of failing to detect
other random errors. Let's take the second test vector as our example: "
MS12NAMEA320ZYXWVUTSRQPNMLKJHGFEDCAXRPP870HKKQRM"
You start in a specified initial state with a pair of bech32 characters.
For MS1 strings and a size 2 quickcheck it would be the pair of Bech32
characters 'AS'.
Next we "add" the first character after the prefix, which is '2' by using
the addition volvelle or lookup table. "Adding" '2' to 'S' yields '6' and
our state becomes 'A6'.
Next we have to look up 'A6' in a lookup table. This table is too big to
fit in the margin of this email, so I will have to omit it. But it would
have an entry mapping 'A6' -> 'QM'. Our state becomes 'QM'
>From this point we have an even number of remaining characters in the input
string and we can work 2 characters at a time. We "add" the next two data
characters from our string, which are 'NA'. Again, using the volvelle or
lookup table we get that adding 'N' to 'Q' yields 'N', and adding 'A' to
'M' yields 'X'. So our state is now 'NX'
Next we look up 'NX' in this table I haven't given you and we will find an
entry mapping 'NX' -> 'DX', making 'DX' our new state.
We keep repeating this process alternating between adding pairs of
characters and using this unstated lookup table all the way until the end
where we will reach a final state which will be 'H9'.
If you follow this procedure with any string (upto 400 bit master seeds)
you will always end up in the state 'H9'.
A specialized worksheet would help guide the process making the process
easier to follow.
This process is somewhat close to Peter Todd's suggestion of using a lookup
table on "words", which in this case would be pairs of bech32 characters,
and adding values together. The catch is that the addition is done with
Bech32 addition rather than calculator addition, which I accept is a
moderately large catch.
Anyhow, the point is that you can do this sort of partial verification by
hand to whatever degree you like, if you are in a rush and are willing to
accept larger chances of failing to catch random errors.
On Wed, Feb 22, 2023 at 2:01 PM Russell O'Connor <roconnor at blockstream.com>
wrote:
> 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 at 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 at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230222/8bca8605/attachment-0001.html>;
Russell O'Connor [ARCHIVE] /
npub1dw…8plrw
2023-06-07 23:19:45
in reply to nevent1q…k8uy
Author Public Key
npub1dw88wd5gqsqn6ufxhf9h03uk8087l7gfzdtez5csjlt6pupu4pwsj8plrwPublished at
2023-06-07 23:19:45Event JSON
{
"id": "c1caf085bdb23149bad18bc4c4ae8c471a1dbde73e4d1321f8faa86e3db3c40e",
"pubkey": "6b8e77368804013d7126ba4b77c7963bcfeff909135791531097d7a0f03ca85d",
"created_at": 1686179985,
"kind": 1,
"tags": [
[
"e",
"a3a3f4bb7a4f76a4dd4ffb9bad737c4cf2aefb0496fa4b312d6d5bf1fd8cde22",
"",
"root"
],
[
"e",
"23da8c9d37edc6ab7dc13d66f2ed9ad88b00d09ff08660abb0eb6dbea5cb9cad",
"",
"reply"
],
[
"p",
"6b8e77368804013d7126ba4b77c7963bcfeff909135791531097d7a0f03ca85d"
]
],
"content": "📅 Original date posted:2023-02-23\n🗒️ Summary of this message: Generators for degree 2 BCH codes are smooth and factor into quadratic and linear components, allowing for partial verification of codex32 strings.\n📝 Original message:After some consultation, I now see that generators for all degree 2 BCH\ncodes, such as ours, are smooth and factor into quadratic and linear\ncomponents.\n\nAnyhow the upshot of all this is that you can perform a \"quickcheck\"\nverification of the codex32 strings for whatever size of verification you\nwant to do, 1 character, 2 characters, 3 characters, upto the full 13\ncharacters. Each of these partial verifications will have BCH properties.\nA 1 character quickchecksum will guarantee to detect any 1 character\nerror. A 3 character quickchecksum will guarantee to detect any 2\ncharacter error, etc. There remains a 1 in 32^n chance of failing to\ndetect larger numbers of errors where n is the size of your quickcheck.\n\nTo illustrate, let's consider a quickcheck of size 2. This can detect any\n1 character error and will only have a 1/1024 chance of failing to detect\nother random errors. Let's take the second test vector as our example: \"\nMS12NAMEA320ZYXWVUTSRQPNMLKJHGFEDCAXRPP870HKKQRM\"\n\nYou start in a specified initial state with a pair of bech32 characters.\nFor MS1 strings and a size 2 quickcheck it would be the pair of Bech32\ncharacters 'AS'.\n\nNext we \"add\" the first character after the prefix, which is '2' by using\nthe addition volvelle or lookup table. \"Adding\" '2' to 'S' yields '6' and\nour state becomes 'A6'.\n\nNext we have to look up 'A6' in a lookup table. This table is too big to\nfit in the margin of this email, so I will have to omit it. But it would\nhave an entry mapping 'A6' -\u003e 'QM'. Our state becomes 'QM'\n\n\u003eFrom this point we have an even number of remaining characters in the input\nstring and we can work 2 characters at a time. We \"add\" the next two data\ncharacters from our string, which are 'NA'. Again, using the volvelle or\nlookup table we get that adding 'N' to 'Q' yields 'N', and adding 'A' to\n'M' yields 'X'. So our state is now 'NX'\n\nNext we look up 'NX' in this table I haven't given you and we will find an\nentry mapping 'NX' -\u003e 'DX', making 'DX' our new state.\n\nWe keep repeating this process alternating between adding pairs of\ncharacters and using this unstated lookup table all the way until the end\nwhere we will reach a final state which will be 'H9'.\n\nIf you follow this procedure with any string (upto 400 bit master seeds)\nyou will always end up in the state 'H9'.\n\nA specialized worksheet would help guide the process making the process\neasier to follow.\n\n\nThis process is somewhat close to Peter Todd's suggestion of using a lookup\ntable on \"words\", which in this case would be pairs of bech32 characters,\nand adding values together. The catch is that the addition is done with\nBech32 addition rather than calculator addition, which I accept is a\nmoderately large catch.\n\nAnyhow, the point is that you can do this sort of partial verification by\nhand to whatever degree you like, if you are in a rush and are willing to\naccept larger chances of failing to catch random errors.\n\n\nOn Wed, Feb 22, 2023 at 2:01 PM Russell O'Connor \u003croconnor at blockstream.com\u003e\nwrote:\n\n\u003e After some poking around at the math, I do see that the 13 character\n\u003e generator (for regular sized shares) is reasonably \"smooth\", having roots\n\u003e at T{11}, S{16}, and C{24}.\n\u003e\n\u003e This means we could build a \"quick check\" worksheet to evaluate the string\n\u003e modulo (x - T) to verify a 5 bit checksum, whose operation would be similar\n\u003e to the existing checksum worksheet in structure but significantly less work.\n\u003e\n\u003e Perhaps 5 bits is too short, and it is more reasonable working modulo (x -\n\u003e T)*(x - S) to get a 10 bit checksum. A worksheet for a 15 bit checksum is\n\u003e also an option, and possibly others well depending on the size of the other\n\u003e factors. I think this process is would be about as simple as any other\n\u003e comparable hand operated checksum over the bech32 alphabet would be.\n\u003e\n\u003e I haven't looked into the smoothness of the long generator for seeds that\n\u003e are greater than 400 bits. If it isn't smooth and smoother options are\n\u003e available, perhaps it should be changed.\n\u003e\n\u003e On Wed, Feb 22, 2023 at 11:29 AM Peter Todd via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\u003e On Sun, Feb 19, 2023 at 10:12:51PM +0000, Andrew Poelstra via bitcoin-dev\n\u003e\u003e wrote:\n\u003e\u003e \u003e \u003e What really did catch my attention, but which was kind of buried in\n\u003e\u003e the\n\u003e\u003e \u003e \u003e project documentation, is the ability to verify the integrity of each\n\u003e\u003e \u003e \u003e share independently without using a computer. For example, if I\n\u003e\u003e store a\n\u003e\u003e \u003e \u003e share with some relative who lives thousands of kilometers away, I'll\n\u003e\u003e be\n\u003e\u003e \u003e \u003e able to take that share out of its tamper-evident bag on my annual\n\u003e\u003e \u003e \u003e holiday visit, verify that I can still read it accurately by\n\u003e\u003e validating\n\u003e\u003e \u003e \u003e its checksum, and put it into a new bag for another year. For this\n\u003e\u003e \u003e \u003e procedure, I don't need to bring copies of any of my other shares,\n\u003e\u003e \u003e \u003e allowing them (and my seed) to stay safe.\n\u003e\u003e \u003e \u003e\n\u003e\u003e \u003e\n\u003e\u003e \u003e This is good feedback. I strongly agree that this is the big selling\n\u003e\u003e \u003e point for this -- that you can vet shares/seeds which *aren't* being\n\u003e\u003e \u003e actively used, without exposing them to the sorts of threats associated\n\u003e\u003e \u003e with active use.\n\u003e\u003e \u003e\n\u003e\u003e \u003e We should make this more prominent in the BIP motivation.\n\u003e\u003e\n\u003e\u003e I don't think that use-case is a good selling point. The checksum that\n\u003e\u003e Codex32\n\u003e\u003e uses is much more complex than necessary if you are simply verifying a\n\u003e\u003e share by\n\u003e\u003e itself.\n\u003e\u003e\n\u003e\u003e A *much* simpler approach would be to use a simple mod N = 0 checksum,\n\u003e\u003e either\n\u003e\u003e by creating the seed such that each share passes, or by just storing an\n\u003e\u003e additional word/symbol with the seed in such a way that sum(words) mod N\n\u003e\u003e = 0\n\u003e\u003e passes. This approach is not only possible to compute by hand with a\n\u003e\u003e word/symbol-\u003enumber lookup table, and pen and paper or a calculator. It's\n\u003e\u003e so\n\u003e\u003e simple they could probably *remember* how to do it themselves.\n\u003e\u003e\n\u003e\u003e\n\u003e\u003e Secondly, if all shares have mod N checksums, it may be sufficient for\n\u003e\u003e everyone\n\u003e\u003e to write down the checksums of the *other* shares, to verify they are the\n\u003e\u003e correct ones and a different (otherwise correct) share hasn't\n\u003e\u003e accidentally been\n\u003e\u003e substituted.\n\u003e\u003e\n\u003e\u003e Indeed, with some brute forcing and small checksums, I'd expect it to be\n\u003e\u003e mathematically possible to generate Shamir's secret sharing shards such\n\u003e\u003e that\n\u003e\u003e every shard can share the *same* checksum. In which case the share\n\u003e\u003e verification\n\u003e\u003e procedure would be to simply ask every share holder to verify the checksum\n\u003e\u003e manually using the mod N procedure, and then verify that each share\n\u003e\u003e holder has\n\u003e\u003e the same checksum. This would be less error prone in terms of leaking\n\u003e\u003e information accidentally if the checksum was obviously *not* part of the\n\u003e\u003e share:\n\u003e\u003e eg by encoding the share with words, and the checksum with a number.\n\u003e\u003e\n\u003e\u003e Obviously, small checksums aren't fool proof. But we're probably better\n\u003e\u003e off\n\u003e\u003e creating a relatively easy procedure with a 1-in-1000 chance of an error\n\u003e\u003e going\n\u003e\u003e undetected than a complex procedure that people don't actually do at all.\n\u003e\u003e\n\u003e\u003e --\n\u003e\u003e https://petertodd.org 'peter'[:-1]@petertodd.org\n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230222/8bca8605/attachment-0001.html\u003e",
"sig": "cdd4a1ef73aabc5ce785bd0bd0620669c990d032d893d4137fb6c62e73a6bd1f684e56ace8d62317dd9cfc69b1f1d8e6ae3ffb943be75a846b124ae44bdbdc21"
}