3 ms·

If you want pseudo-random counters for something that are guaranteed to not have collisions, consider using a "linear feedback shift register". LFSRs allow you

If you want pseudo-random counters for something that are guaranteed to not have collisions, consider using a "linear feedback shift register". LFSRs allow you to choose the number of bits in your id, and "complete" LFSRs use a starting seed [+] value that guarantee they will exhaust the entire bit space before repeating. They are very cool. In distributed environments, you can assign different seeds to individual nodes, include the seed in the id, and guarantee no collisions across your entire network. [+]: edit: sorry, I meant "taps". It's been a minute since I got to do something new with an LFSR. LFSR output is determined by "taps" & "seed" & algorithm. Galois LFSR is an easy algorithm to implement. There are publicly available references and datasets for full-cycle LFSR taps for different bit sizes. I have a php implementation at https://github.com/robsheldon/asinius-lfsr https://github.com/robsheldon/asinius-lfsr, but the code is absurdly simple and trivial to translate into any other language. Some references and further notes are included.

ithkuil 4y ago
From TFA: > We knew that we wanted to avoid using integer IDs so that we wouldn’t reveal the count of records in all our table In order to attain that property the seed must be kept secret, right? A secret that cannot be rotated is hard to work with.
- thaumaturgy 4y ago
  The seed for an LFSR is just the starting value for its cycle; it can be any value in the cycle, and it's public anyway in that you can think of each output of an LFSR as the "seed" for the next output. But in the case of the "taps", yes, you would want to treat those as a secret if you didn't want someone to predict the next value in the cycle. An LFSR by itself might not be a complete solution for IDs for public consumption, but it does neatly solve the need for pseudo-random non-colliding IDs. Whereas NanoIDs are able to generate values with a ~1% probability of collision over some time period, LFSRs can generate values with a 0% probability of collision over their entire bit space. (And they're composable!) It looks like NanoIDs are entirely random values reduced to a specific alphabet (https://github.com/ai/nanoid/blob/main/index.js https://github.com/ai/nanoid/blob/main/index.js) -- which is approximately similar to: tr -dc _A-Z-a-z-0-9 < /dev/urandom | tr -d '/+oO0lLiI1\n\r' | head -c $num_chars ...but with a really nice collision estimation tool attached. So if you want randomness in your IDs and you still also want to guarantee 0 collisions, then you can always just append a randomly-generated value to the output of the LFSR, and then feed that into whatever widget you want to use to convert it into a public ID, if you think it's necessary. But the edge case of collision prevention at really large scales has always seemed to me to be much harder to solve than the edge case of ID enumeration giving up anything valuable (in a well-designed application).
- philsnow 4y ago
  Most implementations of generating non-sequential(-appearing) IDs have the property that they generate keys uniformly at random in a different keyspace. An attacker that can gather a large number of IDs can get an arbitrarily-good guess at the number of IDs you've generated. If the attacker can only check whether certain keys exist, they can just pick a 2^N-sized range of your keyspace, look up whether all those keys exist, and extrapolate from that an increasingly good (with higher N) guess of how many IDs you've generated.

ithkuil 4y ago

From TFA: > We knew that we wanted to avoid using integer IDs so that we wouldn’t reveal the count of records in all our table In order to attain that property the seed must be kept secret, right? A secret that cannot be rotated is hard to work with.

thaumaturgy 4y ago
The seed for an LFSR is just the starting value for its cycle; it can be any value in the cycle, and it's public anyway in that you can think of each output of an LFSR as the "seed" for the next output. But in the case of the "taps", yes, you would want to treat those as a secret if you didn't want someone to predict the next value in the cycle. An LFSR by itself might not be a complete solution for IDs for public consumption, but it does neatly solve the need for pseudo-random non-colliding IDs. Whereas NanoIDs are able to generate values with a ~1% probability of collision over some time period, LFSRs can generate values with a 0% probability of collision over their entire bit space. (And they're composable!) It looks like NanoIDs are entirely random values reduced to a specific alphabet (https://github.com/ai/nanoid/blob/main/index.js https://github.com/ai/nanoid/blob/main/index.js) -- which is approximately similar to: tr -dc _A-Z-a-z-0-9 < /dev/urandom | tr -d '/+oO0lLiI1\n\r' | head -c $num_chars ...but with a really nice collision estimation tool attached. So if you want randomness in your IDs and you still also want to guarantee 0 collisions, then you can always just append a randomly-generated value to the output of the LFSR, and then feed that into whatever widget you want to use to convert it into a public ID, if you think it's necessary. But the edge case of collision prevention at really large scales has always seemed to me to be much harder to solve than the edge case of ID enumeration giving up anything valuable (in a well-designed application).
philsnow 4y ago
Most implementations of generating non-sequential(-appearing) IDs have the property that they generate keys uniformly at random in a different keyspace. An attacker that can gather a large number of IDs can get an arbitrarily-good guess at the number of IDs you've generated. If the attacker can only check whether certain keys exist, they can just pick a 2^N-sized range of your keyspace, look up whether all those keys exist, and extrapolate from that an increasingly good (with higher N) guess of how many IDs you've generated.