Re: [bitcoin-dev] Codex32
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
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@lists.linuxfoundation.org> wrote:
>
>> On Sun, Feb 19, 2023 at 10:12:51PM +, 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
Re: [bitcoin-dev] Codex32
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@lists.linuxfoundation.org> wrote:
> On Sun, Feb 19, 2023 at 10:12:51PM +, 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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Codex32
On Sun, Feb 19, 2023 at 3:13 PM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>Codex32 allows the individual to periodically perform their
>recollection on paper in a private room without electronics and use
>nothing but a pen and some loookup tables (or a paper device) to
>verify that they recalled the string correctly (and its checksum can
>help with correcting up to several errors, although you might need a
>computer for error location and correction assistance).
>
While perhaps not entirely impossible, doing error correction by hand is
far more difficult than just the error detection process.
Fortunately, error correction can be aided by a computer needing very
little trust.
When doing hand computation of the checksum, there is an error if the final
"residue" is different from the value given in the codex32 spec.
After double checking your hand computation by redoing it, if you still get
the same incorrect residue, there is an error in your share data somewhere.
What you can do is plug in the residue that you did compute into a
computer, and have it produce an error correction string.
You can then, by hand, add this error correction string to your share to
get a corrected share.
If it were the case that all types of character errors were equally likely
(as in during an error any character is equally likely to be transformed
into any other character), then the computer would gain zero information
about your actual share data. Of course, it is not in fact the case that
all transcription errors are equally likely, and so the computer can learn
a little bit about your share. The fewer errors that are made, the less
data it can recover. If you only have one character in error, then 5 bits
is the most data it can recover, and that is assuming that it can somehow
infer your error perfectly from the delta of the error correction, which
isn't actually going to be the case.
Of course, a single share from a split secret has no information about your
master seed (the master seed is hidden in the correlation between different
shares). So learning partial information about one share isn't going to be
enough by itself to even begin compromising your master key.
This all still needs to be written up in more detail, but I figured I would
give a preview here.
- Hierarchy: Codex32 does not natively provide support for nested
>whereas SLIP39 does. E.g., in SLIP39, you can require 2-of-3 for
>{me, family, friends} where me is 2-of-3 {fire_safe, bank_safe,
>buried_in_woods}, family is 1-of-3 {alice, bob, carol}, and friends
>are 2-of-5 {d, e, f, g, h}. I assume you can do the same with Codex32
>by using the share for one level as the secret for the next level,
>although this is not described in the protocol.
>
There was a design for a second level share scheme floating around
somewhere. I'll have to dig it up. As I recall this is made slightly more
complicated by needing to incorporate share metadata (i.e. the share index)
when doing a second split, but it seemed doable at the time.
> - Versioning: Codex32's metadata can store version information for
>wallets that use implicit BIP32 paths (e.g. BIP44/49/84/86), although
>this would cut into the space available for users to set their own
>metadata and it is not specified in the draft BIP. SLIP39 also
>doesn't specify anything about implicit path versioning and, AFAICT,
>doesn't have any room to store such metadata without reducing seed
>entropy.
>
Personally, I don't consider the derivation path / descriptor data as that
sensitive, and I would recommend making wide backups of that data.
It certainly would make sense to store descriptor data alongside wherever
you keep your shares, and more places beyond that.
On the other hand, if you are trying to keep your shares innocuous somehow,
perhaps you won't be able to keep the descriptor data alongside your shares.
When I first saw the post about this, it was unclear to me that it was a
> serious project, but I've become increasingly interested as I researched
> it. I'm not personally that interested in generating entropy from dice
> or encoding shares by hand---it's already imperative that I acquire a
> trustworthy computer and load it with trustworthy software in order to
> use my seed securely, so I might as well have it generate my seeds and
> my
> recovery codes for me.
>
I do think hardware wallets are great, and overall provide a lot of
practical protection. What is notable is that once the secrets are loaded
onto a hardware wallet, as long as that wallet remains isolated, it cannot
leak any secrets.
Of course, a wallet needs to interact with the Bitcoin protocol and P2P
network, at least indirectly, in order to function, so we must break that
isolation. However, if we can limit the communication capabilities of a
hardware wallet, even a malicious wallet shouldn't be able to leak the
Re: [bitcoin-dev] Testing censorship resistance of bitcoin p2p network
On Sat, Feb 18, 2023 at 01:28:38AM +, Andrew Poelstra wrote: > On Sat, Feb 18, 2023 at 02:03:15AM +0200, Peter Todd wrote: > > On February 18, 2023 1:35:34 AM GMT+02:00, Andrew Poelstra via bitcoin-dev > > >You could try statically analyze `` to determine whether the > > >IF branch could ever be taken. For example there is no path through > > >the "inscription script" that would result in all the crap being dropped > > >by the end of the script, violating the CLEANSTACK rule. > > > > > >This sort of filtering, assuming it could be reliably and efficiently > > >done, would at least force inscription scripts to be "plausible", and > > >would greatly increase their space cost by e.g. requiring OP_DROP to be > > >added somewhere hundreds of times. > > > > "greatly increase their space cost"? > > > > Tell me, what is the actual % increase to adding OP_DROPs like you propose? > > > > By standardness rules (where you can have up to 80-byte pushes), a > little over 1%. By consensus (520-byte pushes) less than 0.2%. > > Perhaps "greatly increase" is a stretch :) but if the fee market is > functioning and we're talking about large amounts of data, it's not > trivial either. I would definitely call ~1% trivial. Fees vary more by that on an hour to hour basis. Anyway, it goes to show that protocols relying on data embedded in Bitcoin transactions would do well to have flexible encoding rules, eg by considering all PUSHDATA's with certain characteristics to be data, so that encoders can be adapted on the fly if there are any censorship issues. It's also useful if the rules allow data to be encoded in UTXO outputs, so that censorship of witness data always risks people switching to filling up the UTXO set. A kind of Mutually Assured Destruction threat in a way. FWIW, OpenTimestamps was deliberately designed to have this property. So don't mess with it. :D -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Codex32
On Sun, Feb 19, 2023 at 10:12:51PM +, 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 signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
