Subnostr

I also don’t see the benefit of having the MSB as 1: you can pad the serialized result anyway

because the division operation won't yield the first x groups of MSB zeroes, it operates from right to left

it could be the msb or the 11th msb, but with all zeroes in the first 1 or 2 11 bit parts of the number the division doesn't see them, you go to zero and then you have 23 or 22 or 21 11 bit values

just try modifying the implementation to skip the check and assume 33rd byte is all zero, and see what happens when first X of the 11 bit fields are also zero

the way you are proposing forces you to copy 32 byte segments on each operation to another position whereas the division lets you do it as 5 64 bit right shifts copying the overflow into the 11 bit field array

24 right shifts on 5 64 bit words versus 24 copy-and-shift operations, plus you have to have a lookup table to decide the shift at each point because they only coincide at 88 bit boundaries

11 and 8 is nasty, and 64 bit processor will optimize if you just use division and multiplication with powers of 2

i used to think it would be like you but go look it up, power of two in integer division and multiplication is optimized into bitshifts and bitshifts are funneled down in a second decision step to use the multiply/divide circuit

oh yeah, this is probably a big part of the reason why btcec is so much slower than libsecp256k1 too, because the secp256k1 library does it via 64 bit word multiplication and division operations, catching the result in the overflow register

Reply to this note

Please Login to reply.

Discussion

semisol 1y ago

why can’t you separately store the length of the integer with zeroes included?

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

you can implement it how you like

is there a practical reason why putting a sentinel in the MSB is a problem for your implementation?

semisol 1y ago

not really, but it could be viewed as odd by most implementors and feels kind of pointless

I would also recommend XORing the other 7 bits by a constant, to ensure that it can never match BIP39 seeds

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

if you don't have a bit turned on in the first 11 bits, you can't use a "is it zero" test to terminate the div/mod operation encoding it...

this is an operation that is going to be done on a computer, not on an embedded chip, it's less complex logic than running an iteration counter, in terms of C code it's one of the `for` clauses empty, because you only need the test in the middle, and don't need a counter

you have to do a test in the for loop anyway so being able to omit the counter is an optimization of complexity

i don't see what the point of this XOR operation means, 99.9999% of valid encodings are going to not satisfy the invariant of the check bytes of a BIP-39 master key mnemonic, how many bytes is the check? 24? 32? that's a lot of bits that are not gonna be right for a genuine random 32 byte key, more likely fail parity than not

also, isn't the BIP-39 check on the right side?

it's beyond an edge case, because it's also a user error on top of an infinitesimally small probability that a random key has a valid check

semisol 1y ago

oh, right

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

yes, that was why i put it in there, simplicity

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

also i checked, the check bytes of BIP-39 are a byte on the right hand side

firstly, if your hardware supports this, it can rule out any string that puts a 0 on the MSB on the left as being nostr key

secondly, the bip-39 check on the LSB is highly unlikely to match up, it is a 0.5% chance of a valid bip-39 key being imputed from a nostr secret key mnemonic, probably you can cut that in half even since the MSB has to be a 1

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

i checked the BIP-39 code and i played with an implementation and it does not preserve your bits

i see it says 256 bit entropy and 8 bits of check, and i presume this is right-handed encoding

yes, we could flip this around so the check is on the right side but then you simply don't have the option of doing this decoding as a series of deterministic shift-and-check operations (division, if you like), your idea rules this way of doing it out

your issues with the ordering of the encoding having a conflict with BIP-39 seems a bit silly because how would you confuse the two, and even if you did, so what, you threw away your bitcoin key and kept your nostr key? or vice versa? why would you do that?

if it is a hardware device, as if you are gonna have two, one with a bitcoin key and one with a far less valuable nostr key not be distinghuished somehow, i mean, come on, this is again user error