13 ms·

Sqids – Generate short unique IDs from numbers

• koromak 3y ago
  I'd love a short ID standard of some kind. There are so many situations where I just want a quick, ephemeral ID. Doesn't need to be cryptographically secure, collisions are expected. It would be nice to have something to import from the standard library in most languages.
• deleted 3y ago
  [deleted]
• dfc 3y ago
  It's weird under "Get Started" they have links to 40 different languages. You can only get started with 15 of the 40 languages listed, the other 25 are skeleton repos asking for people to start the repo to indicate interest.
  • hooverd 3y ago
    Maybe a slam dunk first FOSS contribution?
    • ctoth 3y ago
      This seems like a perfect use case for an LLM :)
  • LeFever 3y ago
    It’s kinda clever. The people most likely to look at this project are also likely ideal candidates for implementing the library in a new language (Developer, FOSS enthusiast, interested in the project, need the library in a language they’re familiar with that isn’t implemented yet). Also, the language pills differentiate between those that have been implemented (color logo, dark text, bold) and those that aren’t (grayscale).
    • 4kimov 3y ago
      Good points. Those pages also contain links to old implementations (Hashids), because a lot of projects still use those and want to be able to find them.
    • alas44 3y ago
      Also can help track which languages people click on, probably a good proxy of where there would be the need to develop a lib
  • vyrotek 3y ago
    The approach definitely works. Some time ago I saw .NET listed but discovered it wasn't complete. I was eager to replace an existing Hashids implementation so I made some comments, shared a starter-snippet, and then someone was excited enough to complete in just a few days. It was great to see how quick the community stepped in. Maybe there was a bit of Cunningham's Law in effect with my contribution, ha. https://github.com/sqids/sqids-dotnet/issues/2#issuecomment-1661485906 https://github.com/sqids/sqids-dotnet/issues/2#issuecomment-...
• deleted 3y ago
  [deleted]
• whalesalad 3y ago
  This used to have a totally different name iirc, they used to be called hashids
  • deleted 3y ago
    [deleted]
  • resoluteteeth 3y ago
    Yeah, it says that both in the page title and the logo at the upper left
  • ChrisArchitect 3y ago
    A recent Show HN: from the dev (who's also in this thread) explaining the rebrand https://news.ycombinator.com/item?id=38185437 https://news.ycombinator.com/item?id=38185437
  • unfunco 3y ago
    I've always thought it was called bijection.
• c2xlZXB5Cg1 3y ago
  Reminds me of proquints https://github.com/dsw/proquint https://github.com/dsw/proquint But 127.0.0.1 looks more "readable" to me than lusab-babad
• no_wizard 3y ago
  I like the idea, though I use nanoid with the safe letter dictionary (it excludes letters used for profanity[0]) They should use a similar dictionary approach IMO because I looked at the implementation and it’s hardcoded to look for “bad” words Otherwise looks real straightforward! I’d love to see some performance test suites for it [0]: https://github.com/sqids/sqids-javascript/blob/ebca95e11493212099627276bd418cc6fd357160/src/sqids.ts#L10C1-L10C1 https://github.com/sqids/sqids-javascript/blob/ebca95e114932... [1]: though with UUID v4 so common to generate and well optimized in most languages I wonder if these userland solutions are really better. You can always generate a UUID and re-encode with base32 or base64 with also is well optimized in most languages
  • lxgr 3y ago
    > it excludes letters used for profanity That doesn't seem possible. How would that work? > I looked at the implementation and it’s hardcoded to look for “bad” words. If you mean https://github.com/y-gagar1n/nanoid-good https://github.com/y-gagar1n/nanoid-good, that seems to be doing the same thing. In general, I'm a bit weary of solutions that "guarantee no bad words" – this is usually highly language-specific: One language's perfectly acceptable name is another language's swear word.
    • no_wizard 3y ago
      This is the implementation: https://github.com/CyberAP/nanoid-dictionary https://github.com/CyberAP/nanoid-dictionary We use it in a highly internationalized product spanning multiple languages and haven’t yet ran into a complaint or value on audit that would constitute something offense in any language per our intl content teams anyway. That isn’t to say it’s 100% (and simply enough we don’t audit every single URL) but I suspect we would have gotten at least a user heads up by now Never the less we are moving our approach to uuids that get base32 encoded for some of our use case for this. They’re easier to work for us in many scenarios
    • deleted 3y ago
      [deleted]
    • Sharlin 3y ago
• dumbo-octopus 3y ago
  Odd design decision in that if you provide your own blocklist, it overwrites their (extensive) default list instead of adding to it. And in general the algorithm is surprisingly complicated for something that could be replaced with simply base64 encoding, the given example (1,2,3) base64 encodes to a string with just one more letter than this algorithm. That said I do appreciate the semicolon-free-style. I don't typically see that in libs besides my own. https://github.com/sqids/sqids-javascript/blob/main/src/sqids.ts https://github.com/sqids/sqids-javascript/blob/main/src/sqid...
  • 8organicbits 3y ago
    The problem is their block list will change over time. If you don't override it, then your IDs won't decode right when you update. This is a huge risk. > You have to account for scenarios where a new word might be introduced to the default blocklist https://sqids.org/faq#future-blocklist https://sqids.org/faq#future-blocklist Honestly, I think they need to rethink this. Otherwise you've got different library versions for different languages each using different default blocklists, none of which are compatible.
    • wtetzner 3y ago
      > If you don't override it, then your IDs won't decode right when you update. They'll decode fine. Encoding might change.
      • 8organicbits 3y ago
        I think your right, but that violates the uniqueness guarantee. It doesnt seem like something that should change over time by default.
        • dumbo-octopus 3y ago
          There explicitly is no uniqueness guarantee. It is known that the same values can encode into many different strings, and they recommend always decoding then reencoding with a stable algorithm to achieve a "canonical" id if one is needed. https://sqids.org/faq#valid-ids https://sqids.org/faq#valid-ids
• jsf01 3y ago
  What’s the use case for passing in an array of numbers? Typically when generating an ID my input is either a single random number, a string that’s being hashed, or nothing at all.
  • 4kimov 3y ago
    [shard_number, primary_id_number, timestamp]
    • dumbo-octopus 3y ago
      But then why not just arbitrary text?
• James_K 3y ago
  I guess they haven't heard of base-64.
  • xjia 3y ago
    Or base58, e.g. https://api.rubyonrails.org/classes/SecureRandom.html#method-c-base58 https://api.rubyonrails.org/classes/SecureRandom.html#method...
  • dymk 3y ago
    That doesn't solve the same set of problems as TFA. Randomized output order for sequential input, skips IDs that include profanity.
    • James_K 3y ago
      There is no need for randomised output, and they've said themselves that you can recover the input from the output. It's literally just so that it looks like something cool and technological is happening. You can skip IDs that contain base64 profanity just by doing the reverse encoding on your block list and skipping those IDs. Or you could exclude vowels from your alphabet and do a base 54 encoding. Or you could grow up and accept that your 4 millionth ID which no one is going to read might have a naughty word in it (horror).
    • jbverschoor 3y ago
      There's no info on how this actually works. Actually I have no idea what it does in the first place.. From the FAQ: > How can I make my IDs unique? > The library accepts a custom alphabet from which it can generate IDs. Simply pre-shuffle the default alphabet that's provided. I also have no idea how to use the library.. What are the 3 numbers parameters for encode()? The actual code: https://github.com/sqids/sqids-ruby/blob/main/lib/sqids.rb https://github.com/sqids/sqids-ruby/blob/main/lib/sqids.rb I'd simply base-58 a GUID instead. At least you'll know what kind of constraints / sorting the IDs will have.
  • majkinetor 3y ago
    One of the points is also to use custom alphabet.
• deleted 3y ago
  [deleted]
• canU4 3y ago
  Sad that it is not for user ids
  • 8organicbits 3y ago
    I think that's only if you don't want to leak user count when your ID is an autoincrement. Elsewhere people mention cryptographicly remapping integers, which could work (by itself, or before passing the ID to sqids).
• packetlost 3y ago
  The name (but not function) seems really close to squuids from Datomic/Clojure.
• 3cats-in-a-coat 3y ago
  I don't get it, that's like two lines of code, why does it have a library and even a domain
  • k2xl 3y ago
    Also wondering this
  • tinco 3y ago
    [flagged]
    • tlonny 3y ago
      [flagged]
    • 3cats-in-a-coat 3y ago
      I have over 20 years of experience, I run a team, and I can code something like this in my sleep, as well as any average developer (but maybe "average" is lower than where it used to be in my day). Don't talk down to strangers on the Internet so arrogantly, you only end up embarrassing yourself. I went to check what this code does (beyond a base conversion with a custom alphabet) and I laughed my ass off. 1. Literally TWO-THIRDS of the "library" is a clumsily put together ban list of slurs. Hardcoded, in the library. This DOES NOT belong there. 2. It also contains alphabet checks like say repeated letters, which it'll run every single time it produces an ID, instead of statically checking the alphabet ahead of time, and just using it in production... or even simply selecting an URL-safe alphabet and sticking with it. 3. Despite all the checks, block lists, the default alphabet doesn't do the most elementary thing when producing alpha-numeric ids: exclude letters and digits which look similar, and so will look identical in some fonts. Nasty when you have to write an ID from say a screenshot, or a poster, or what have you. All in all, that's only borderline more utility than the infamous "leftpad" library, and it may actually be harmful in practice, because it contains a bunch of specific and/or superfluous concerns by the author, almost as if they're trying to justify why this is a library in the first place, but which will likely not align with the precise requirements of the users and their project business rules, while it excludes others (like the one I mentioned in point 3 up there). But I'm sure the kids will be impressed.
• its-summertime 3y ago
  For a similar thing, (X bytes to X bytes, no collisions) https://en.wikipedia.org/wiki/Format-preserving_encryption https://en.wikipedia.org/wiki/Format-preserving_encryption is a good page
  • jchook 3y ago
    Also see Knuth Hash and k-dimensional equidistribution.
• habitue 3y ago
  Skipping profanity seems like a liability in this design. It means in order to preserve the encoding you need to make the banned word list immutable, otherwise old sqids will decode to the wrong thing when you get them back.
  • Etheryte 3y ago
    I don't think this holds, you can enforce filtering in the encoding step, i.e. be strict about what you output, but always decode, even if the input is profanity. This means you can also be backwards compatible if you update the list etc. So in short, the old maxim of be strict about your outputs and lenient about your inputs.
    • fimdomeio 3y ago
      From their FAQ: "The best way to ensure your IDs stay consistent throughout future updates is to provide a custom blocklist, even if it is identical to the current default blocklist."
      • Etheryte 3y ago
        In that case it sounds like a shortcoming on their part. There is no fundamental reason to have that limitation. I understand it can make the implementation easier to not have it, but in my opinion being blocklist change agnostic would be a much better value offering.
      • lights0123 3y ago
        The *encoding* changes. The decoding stays consistent: > Decoding IDs will usually produce some kind of numeric output, but that doesn't necessarily mean that the ID is canonical. To check that the ID is valid, you can re-encode decoded numbers and check that the ID matches. The reason this is not done automatically is that if the default blocklist changes in the future, we don't want to automatically invalidate the ID that has been generated in the past and might now be matching a new blocklist word.
  • runlevel1 3y ago
• 8organicbits 3y ago
  The mention of one-time passcodes seems odd. Those need to be unguessable, but don't need to be unique. If you supply a suitable random source, then I suppose it works, but the "padded with junk" feature makes these look more complex than they really are. The standard choice of 4 to 8 random digits works well and it's clear what level of security they provide. Digits are easier to understand than case sensitive latin characters, especially when your native language uses a different character set.
  • pytness 3y ago
    I think you completely misunderstood the article, or you have not read it. The uniqueness from the system comes from the fact that two different numbers will never have the same id. The pad only works for things like user ids. You can also change the alphabet it uses so its not case sensitive; using this alphabet: "ABCDEFGHJKLMNPQRSTUVWXYZ0123456789" and a minimum of 8 digits, it will produce 8 digit ids all the way 4294967295 (0xffffffff).
    • hot_gril 3y ago
      This doesn't go against what the other commenter said. The understanding was correct.
• progne 3y ago
  In a Ruby app we just convert to a high base, like > 1234567890.to_s(36) => "kf12oi" That gets us most of the way there, but Sqid has a Ruby library and lets you set a much higher base, including upper case characters, and I suppose, emoji. We're going to need much bigger numbers before that space savings makes much difference. I like it, but it's hard to know when something like that is worth adding a dependency.
  • vyrotek 3y ago
    I believe a big part of the idea is for the hash to be unpredictable as well. If I figure out you're using (36) then I know the next number 1234567891 is "kf12oj". Not the case with Sqids.
    • hot_gril 3y ago
      You can easily brute-force this. Sqids also says it's not good for sensitive data.
      • 8organicbits 3y ago
        It looks like an easy brute force too, there's no compute-hard operations here. I guess you could scramble your alphabet? Otherwise Uk always comes after bM, etc.
        • posix86 3y ago
          My understanding is that you can re-order the source alphabet, and encode numbers with swapped characters. Unless you know of 36 numbers that they're exactly 1 id apart, you will always have uncertainty to what the ids actually map to.I guess given a large, large number of ids along with the order they're assigned (which might be given through the time at which they're assigned), you could create a pribabilistic statement on the actual order of the 36 characters based on the fact that most numbers increase/decrease faster the bigger they are. (this fact is e.g. used to detect fabricated bank statements - if the first digit of any number in the statement is equally likely to br 1 or 9, the numbers are randomly generated whereas if they're real, 9 is less likely than 1)
• 1-6 3y ago
  Sqids vs Squids. Missing the 'U' for unique but nevertheless a unique shortened version of the regular spelling.
• urza 3y ago
  I wanted to say that I use similar project called HashIDs, but I see that HashIDs rebranded to Sqids :)
• ComputerGuru 3y ago
  I haven’t been able to find a case for this because ids either need to be unique or they’re not going to be large. If they’re unique, I’m using uuid or ulid (uuidv7 of tomorrow) as the sortable primary key type to avoid conflicts without using the db to generate and maintain sequences. Where do you have unique ids that aren’t the primary key? I would be more interested in a retrospectively unique truncated encoding for extant ulid/uuid; ie given that we’ve passed timestamp foo, we know that (where no external data is merged) we only need a bucketed time granularity of x for the random component of the id to remain unique (for when sortability is no longer needed). Or just more generally a way to convert a ulid/uuidv7 to a shorter sequence if we are using it for external hash table lookups only and can do without the timestamp component.
  • hot_gril 3y ago
    > Where do you have unique ids that aren’t the primary key? For things that need public IDs, I always generate and store uuid4s* to avoid leaking database state or anything like that. Even uuid7 leaks creation timestamps. It's cheap and easy to map public IDs to/from PKs at the API boundaries. * possibly encoded as something nicer like base64 for APIs or URLs
  • Bytewave81 3y ago
    The idea is that you encode and decode database IDs with this. You wouldn't save them separately unless you were using it for a purpose other than shareable "identifiers" which don't leak significant amounts of database state. Imagine something like a link shortener where you want to provide a short link to users, but don't want it to just be a number.
    • hot_gril 3y ago
      These leak the state just as much. They're reversible back to integers.
    • ComputerGuru 3y ago
      My point was that this only encodes numbers and you wouldn’t use numbers as primary keys for the reasons outlined.
• waffle_ss 3y ago
  I wrote a Ruby gem to address this problem of hiding sequential primary keys that uses a Feistel network to effectively shuffle int64 IDs: https://github.com/abevoelker/gfc64 https://github.com/abevoelker/gfc64 So instead of /customers/1 /customers/2 You'll get something like /customers/4552956331295818987 /customers/3833777695217202560 Kinda similar idea to this library but you're encoding from an integer to another integer (i.e. it's format-preserving encryption). I like keeping the IDs as integers without having to reach for e.g. UUIDs
  • wslh 3y ago
    I recommend to review my comment where I also use a Feistel cipher [1] but the difference is that it is not limited to int64 but I can even use 8 bits. Obviously loosing security properties but working as an obfuscation method. If you use a random source with relatively few bits you should check if there are duplicates while with the Feistel cipher you are sure there isn't. [1] https://news.ycombinator.com/item?id=38418198 https://news.ycombinator.com/item?id=38418198
• chupapimunyenyo 3y ago
  Hashids seems way better than their new implementation
• Use 3y ago
  Why should you hide your user count?
  • sneak 3y ago
    The rate of change over time can be used against you; many people consider their businesses’ month-over-month growth (or lack thereof) to be private information. “$WEBSITE did 50,000 signups a month during the beginning of the pandemic, but now struggles to sign up a thousand a week” is a story.
• Schnitz 3y ago
  It would be great to have a quick primer on why this is better than what people typically homebrew, like base62 encoding a random number.
  • sneak 3y ago
    Database PKs usually aren’t random, which AFAIK is what is usually used as the number in this case.
    • hot_gril 3y ago
      Database PK really shouldn't be exposed like this. I think that's what they're getting at, though. The thing is, sequential database PK is still shorter and more readable than a Sqid.
  • 8organicbits 3y ago
    If you use a random number then you need to store it somewhere to map back to the original. Sqids is an encoding, you can decode the sqid back to the original without storage overhead. Features like the profanity filter avoid creating URL routes like /user/cuntFh. Cross language support allows interop between the encoder and decoder across microservices written in different languages.
    • antifa 3y ago
      base62 decodes back to Int32 perfectly.
• parhamn 3y ago
  Side note: there are some business insights you can get from a company using serial ids. i.e if you sign up and get user id 32588 and make another account a few days later, you can tell the growth rate of the company. And this is possible with every resource type in the application. I do wonder how much the url bar junk thing matters these days. I tend to use uulids (waiting on uuid v7 wide adoption), and they're a bit ugly, but most browsers hide most of the urls now anyway. The fact that there is a builtin time component comes in clutch sometimes (e.g. object merging rules).
  • deleted 3y ago
    [deleted]
  • pacificmint 3y ago
    > you can tell the growth rate of the company. You can even do this when you don’t know the exact interval by using probabilities. The Allies used this method to estimate German tank production in World War II by analyzing the serial numbers of captured or destroyed tanks. This is know as the German Tank Problem [1] [1] https://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem
    • lhamil64 3y ago
      It also makes it slightly easier to perform certain attacks since it's trivial to figure out other IDs.
      • ozim 3y ago
        Making non-guessable IDs for broken authorization is security by obscurity. If you have integer IDs it is also trivial to find authorization flaws on your own. Any pentester will go for it right away. If you make non guessable IDs they might skip it and go look for other stuff.
    • leobg 3y ago
      Very interesting. I’m a lawyer and using sequential IDs in a fraud case right now, to determine the number of victims. Unfortunately, so far, I only have the IDs of two victims, and those are from just within about a month, whereas the fraud has likely been going on for several years. Just simply extrapolating that growth rate isn’t going to be very accurate. Also, I suspect that the perpetrators did not start at ID 1.
• swyx 3y ago
  saving it to my list of uid implementations https://github.com/swyxio/brain/blob/master/R%20-%20Dev%20Notes/uuid%20list.md https://github.com/swyxio/brain/blob/master/R%20-%20Dev%20No...
• bufferoverflow 3y ago
  Do we really need a library for that? Shouldn't it be a simple function?
  • wlonkly 3y ago
    A library is a good place to put (even simple) functions that are shared between a lot of programs.
• dustingetz 3y ago
  anyone have a copy pasta for the widest possible alphabet (i.e. extended unicode safe chars)
• filleokus 3y ago
  > Not Good For: > User IDs - Can be decoded, revealing user count Suppose you don't want to leak the count, what's a resonable way of implementing that? You can of course have a uuid v7 / uulids or something as the primary key. Or have it as a public facing primary key, mapping back to a sequential ID PK (there might be some performance hits with larger PK's in e.g postgres? or is that just fud?) But you could also generate a public ID with something like encrypt(seq_id, secret) and then encode it with whatever alphabet and or profanity filter you'd like - right? The issue then is that all public ID's would be long (and of course dealing with a decrypt operation on all incoming requests). Don't know what's best really.
  • 8n4vidtmkvmk 3y ago
    Add an offset, multiply by a large prime number, and modulo. I don't think you can recover the original number without figuring out the prime.
    • filleokus 3y ago
      Ah, that's neat. Why is the offset necessary?
      • erhaetherth 3y ago
        Might not be, but I like to start with a big number instead of 0 or 1 to fill all the bits. For example, if your prime is 100019, then your first number in binary is 00011000011010110011 but if your max number is something like 2^53 (00100000000000000000000000000000000000000000000000000000) then you have a lot of unfilled bits. The way I have mine set up, the output ID is always exactly 9 chars. 99% of the time it's naturally 9 chars because just by probability most of the numbers will be large, but some of them come out 8 chars and then I just pad up to 9 so it's nice and consistent.
• kryptogeist 3y ago
  Damn, those squids are getting smart
• orf 3y ago
  How do you adjust or evolve the blocklist with this, without making previously generated IDs incorrect? The ID is simply incremented if it is blacklisted [1]. So the ID is fixed to the blacklist content, and adjusting it in any way invalidates certain segments of previously generated IDs? 1. https://github.com/sqids/sqids-rust/blob/9f987886bc06875d7828f843be8e154938140cb0/src/lib.rs#L215 https://github.com/sqids/sqids-rust/blob/9f987886bc06875d782...
  • ec109685 3y ago
    They address it here: https://sqids.org/faq#future-blocklist https://sqids.org/faq#future-blocklist You're right that you can't update the blocklist in a backwards compatible way.
  • Guillaume86 3y ago
    Didn't check the code but you could encode offseted hash + the offset to avoid blacklisted words and the decoder would decode any version of the hash (offseted or not).
  • timwis 3y ago
    Include a version prefix perhaps?
• revenga99 3y ago
  is there anyway to generate short unique id's from UUID's? snowflake is incredibly slow when joining UUID => UUID columns.
  • resoluteteeth 3y ago
    Isn't the thing that makes UUIDs UUIDs that they have enough bits that they are guaranteed to be unique without any synchronization? I don't think you could reduce the amount of random bits (I guess there are some non-random parts in standard UUIDs but not a significant amount) while preserving that property unless you add back some other form of synchronization to ensure that there aren't collisions which seems like it would defeat the purpose.
  • bjt 3y ago
    If you know which type of uuid you have (v1, v4, etc) then you can take a look at how many bits of randomness it has, how many total items you have, and compute the probability of a collision if you just take a subset of the bits and use that as an ID. In theory it's definitely possible. The 128 bits you get in a UUID is a LOT of randomness for an identifier. Postgres BIGINTs are just 64 bits. Instagram's sharded IDs are just 64 bits. (See below.) You can test it. If you're using uuidv4 (which is 100% random bits, minus a few for the version), you could make a new column in your table in Snowflake, populate it with the first 64 random bits of your existing uuid column, then see if you have any collisions. https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c https://instagram-engineering.com/sharding-ids-at-instagram-...
  • s4i 3y ago
    Encoding the UUID in e.g. base 64 or Crockford’s base 32 (instead of the standard hex+dashes) saves you some space.
• andrewstuart 3y ago
  What is the decimal range of these values?
• sandstrom 3y ago
  Neat library! We're using randomly generated strings for many things. IDs, password recovery tokens, etc. We've generated millions of them in our system, for various use-cases. Hundreds of thousands of people see them every day. I've never heard any complaints about a random content-id being "lR8vDick4r" (dick) or whatever. But nowadays our society is so afraid of offending anyone, that profanity filters has extended all the way to database IDs and password recovery tokens. (there are some legit cases, like randomly generated IDs for user profiles shared in public URLs, that users have to live with, but even there just make the min length 8 and you're unlikely to have any full-word profanity as the complete ID; put differently, I don't understand why they made the block list an opt-out thing)
  • doublemint2203 3y ago
    I'm actually more convinced the problem is corporate risk management to deal with the tendencies of social media to overhype issues by design, rather than a statement on society
  • hobo_mark 3y ago
    Well if you don't filter, things like this may happen: https://github.com/compiler-explorer/compiler-explorer/issues/1297 https://github.com/compiler-explorer/compiler-explorer/issue... Me and you will know it's just random characters, but if HR enters the chat...
  • 3cats-in-a-coat 3y ago
    The block list is 2/3 of the (minified) library. I found this entire choice odd. First, it's highly incomplete because you can find at least 10x more combinations spelling the same "word". And probably 10x more slurs that aren't in this block list. Second, because it's hardcoded in your source. Third, because there are more elegant solutions. Such as to pick an alphabet that can't spell readable words unless you're trying really hard to read a slur into it. Say this (no vowels or digits): bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ (length 42) The full lower+upper+digits alphabet they use is 62. Feels like you're losing a lot, but... not really. - A 128-bit id in base 62 = 22 letters. - A 128-bit id in base 42 = 24 letters. JUST TWO MORE LETTERS. And it's one more letter for 64-bit id (11 vs 12). And we can avoid this entire silliness. The problem is the author doesn't realize that logN is... logarithmic, I suppose.
• akoboldfrying 3y ago
  This looks handy. Given the retry-on-bad-word feature, I was sceptical of the no-collision claim -- but after looking at the JS source code, I'm confident it's correct. For each number encoded, one character from the alphabet is "held back" to use as a delimiter (with the particular character chosen changing as each number is processed, presumably to make the output "look more random"). The very first character output is essentially a "free choice" that selects the initial permutation of the alphabet to use. The algorithm is implemented as a function encodeNumbers() that calls toId() to encode each number, then checks for bad words and recurses with a new value of "increment" if it finds any. To prove correctness it's helpful to imagine an "in-between" function, tryEncodeNumbers(numbers, alphabet), which the outer encodeNumbers() calls in a loop to do most of its work (pseudocode): function encodeNumbers(numbers) { offset = sum(numbers) do { result = tryEncodeNumbers(numbers, permute(alphabet, offset + increment++)) } while (badWordIn(result)) return result } Here permute() is a function that permutes the characters in its first (string) argument according to its second (integer) argument in some arbitrary way. The toId(num, alphabet) function, which simply encodes a single number using "digits" taken from the characters in the alphabet parameter, is clearly injective with respect to the num parameter provided that alphabet contains no duplicate characters -- that is, if we hold some duplicate-free alphabet string fixed, every distinct value of num produces a distinct encoded string as output. (For example, toId(42, "0123456789") gives "42", and no other value of num produces this string when the alphabet remains unchanged.) tryEncodeNumbers(numbers, alphabet) first outputs a character representing alphabet (i.e., its initial alphabet -- which is its complete internal state), then joins together a bunch of these toId()-encoded numbers, with an extra character in between each that is known not to appear as a digit in the preceding number, permuting the alphabet in an alphabet-dependent but num-independent way for each encoded number output. Because the alphabet permutation is independent of the input array of numbers, this means that the alphabet used to encode the i-th number depends only on the initial alphabet and i. This means that, again holding its initial alphabet fixed, tryEncodeNumbers() is likewise injective with respect to the input array of numbers. (Suppose it were not: Then there is an initial dupe-free alphabet, and two distinct arrays of numbers, that produce the same output. Find the first position where the two arrays differ. Since the final results are identical by assumption, one of the two encoded outputs for this position must be a prefix of the other. But if the two encoded outputs are of different lengths, the shorter one must either terminate the entire string, making it shorter than the other encoded string, or be immediately followed by a character that cannot appear in the output of toId() with the alphabet used at this position, both of which contradict the assumption that the resulting strings are equal. Therefore toId() must have output identical strings for the two different numbers at this position, when given the same alphabet. But this contradicts injectivity of toId(), so this (non-injectivity of tryEncodeNumbers()) is impossible.) The final step is to see that, if encoding two inputs with the top-level encodeNumbers() function gives the same first character C, it must be because the first successful (bad-word-free) loop iteration for the first input passed the same alphabet to tryEncodeNumbers() as the first successful loop iteration for the second input. If the remainders of the two encoded strings are also equal, then by injectivity of tryEncodeNumbers() for fixed alphabet choice their input number arrays must have also been the same. Since no restrictions were placed on the two inputs, this holds for all possible input pairs -- that is, it is impossible for encodeNumbers() to produce the same encoded output string for two different inputs.
• BraverHeart 3y ago
  I see many people in this thread saying that this is a good way to hide insights from ids/numbers, I don't understand, aren't the generated values easily decoded? couldn't I just decode a couple of numbers to get that insight? What am I missing.
  • jonasdoesthings 3y ago
    The docs state: Not Good For: [...] User IDs Can be decoded, revealing user count So yeah, just using a sequential id and encoding the number with this library is not a viable idea if you want to hide your insights.
  • hot_gril 3y ago
    I noticed this too, and imo it's a design flaw that people get misled this way. Sequential inputs should yield sequential outputs, otherwise you might think it's meant to be unpredictable like SHA256.
• andix 3y ago
  Actually I'm a bit disappointed that it can't format 128 bit integers or byte arrays. That would allow formatting UUIDs. I'm not a huge fan of public facing integer IDs. There is always the risk of leaking some kind of critical information with ascending IDs. So I will probably keep Base64URL formatting my UUIDs to make them shorter for URLs, QR Codes and so on. Quick example: 20b30b32-d421-4cfb-bdbc-9a4e0475abea => MguzICHU-0y9vJpOBHWr6g It's important to keep in mind that there are different ways to convert an UUID to a byte array (little/big endian, order of segments, ..)
  • Mogzol 3y ago
    Even if it could format 128 bit integers, I don't see how that would be any better than base64-encoding them. Base64 is already pretty close to the maximum efficiency you can get for shortening UUIDs while still using URL-safe characters.
    • andix 3y ago
      To add some of the additional features Squids provide. You can also convert any smaller integer to a string with Base64.
  • stavros 3y ago
    The shortuuid library can do that: https://pypi.org/project/shortuuid/ https://pypi.org/project/shortuuid/
  • hippich 3y ago
    I actually used sqids algo for something very different where I had to encode arbitrary sized byte arrays. And with Ruby it was very simple to remove limit - I think it was matter of monkey-patching https://github.com/sqids/sqids-ruby/blob/main/lib/sqids.rb#L187 https://github.com/sqids/sqids-ruby/blob/main/lib/sqids.rb#L... to return infinity. The reason for the limit is most likely to ensure interoperability with libraries in other languages where working with bignums is much more complicated.
    • andix 3y ago
• ForHackernews 3y ago
  Oh, they finally fixed the badly named "hashids"
• wslh 3y ago
  I offered something similar here [1] and it is used by many companies including Philip Morris, and the Argentinian tax agency for the same purposes. The technique I used (I should publish it as open source) is using a Feistel cipher [2] with a key. The Feistel network could be adjusted to almost any size and the key used in every round is an expansion of a general key using a key derivation function [3] (KDF3 if I remember well). Basically it is a symmetric cipher of arbitrary size. [1] https://www.nektra.com/products/secure-coupon-code-generator/ https://www.nektra.com/products/secure-coupon-code-generator... [2] https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher [3] https://en.wikipedia.org/wiki/Key_derivation_function https://en.wikipedia.org/wiki/Key_derivation_function
  • smashed 3y ago
    I'm not a cryptographer and did not understand half the things you said except symmetric crypto. I think there are 2 problems with this approach: How do you prevent the double spend problem, for example duplicate entry tickets. You would have to mark the ticket as used in a central database anyway to prevent it What happens if the secret key material is compromised? Anyone can issue new valid numbers, etc.. Please correct me if I'm wrong.
    • wslh 3y ago
      No problem, the two answers here: 1/ You don't have duplicates because a Feistel network assures you there is no duplicates: every input has a different output with a fixed key in every round. 2/ If the secret is compromised anyone can issue valid numbers in the same way that if your secret encryption keys for encrypting your data exposes it. The idea is that the secret key material is never compromised as it is assumed in all security cases. You should custody with the right measures based on the attack vectors you have. The custody of secrets is independent of this method. Please let me know if you have more questions.
      • pixel8account 3y ago
        >The idea is that the secret key material is never compromised as it is assumed in all security cases. That's not true, we have (perfect) forward secrecy, backwards secrecy and key rotation mechanisms because we often care what happened after the key is inevitably compromised. In this case the problem makes it hard to "rotate" the keys in a meaningful way, but I'm yet to see a proof it's impossible.
• deleted 3y ago
  [deleted]
• SebRollen 3y ago
  The second example for each language sample where the generated squid ends up being “B4aajs” essentially reads as “P0ooop” to a Swedish speaker. Which is fine, they don’t propose to filter “bad” words in other languages, but kind of funny when that’s one of the highlighted examples, right next to the goal of filtering words. Goes to show how hard it is to filter profanity generally for international audiences
  • SheepSlapper 3y ago
    Could you just remove vowels and hit 99.9% of profanity in all languages? Ditto for removing their 0-9 equivalents, if you're really worried about it. Quick out of the box support for that via being able to define a custom alphabet.
    • jabagawee 3y ago
      You might still have issues with generating sequences like "XtrmlyBdWrd" that are still recognizable.
      • SheepSlapper 3y ago
        Well until we figure out a way to remove pattern matching from humans... use GUIDs if that's an issue. Removing vowels fixes "spelling almost all bad words explicitly", though I'm open to being proven wrong with fun new swears in exotic (to me) languages :) The problem of "pick any N symbols that don't make any profanity in any language across all time" isn't what this is solving, nor should it have to. Take the same concept but use whitelisted words to build the token if you're that adverse to computer generated, fill in the blank naughty words. Keep "pen" and "island", among other things, off that list ;)
    • kitten_mittens_ 3y ago
      With enough fricatives, some languages still manage. See the Serbian for Serbian, srpska https://en.wikipedia.org/wiki/Republika_Srpska https://en.wikipedia.org/wiki/Republika_Srpska.
  • 3y ago
• hot_gril 3y ago
  I think the "unique IDs" part of the title throws people off and brings security to mind. "The main use of Sqids is purely visual" is what you need to know. It's not necessarily for IDs, it's just a user-friendly way to encode/decode numbers.
  • paulddraper 3y ago
    Exactly. An alphanumeric encoding for integers.
    • mlhpdx 3y ago
      An argument could be made for calling it “compression of the string encoding”. Since HTTP is string oriented, that makes some sense as an optimization of sorts, perhaps.
      • hot_gril 3y ago
        It doesn't seem compressed, in fact the output of this is less compressible than the input. It's made for human interface.
  • hot_gril 3y ago
    Also, why is it non-sequential? That suggests it's unpredictable, but it's not. Just realized that was the thing bothering me about this.
• s4i 3y ago
  If the original numeric ID can be figured out from the sqid string, then what’s the point of the conversion?
  • nnf 3y ago
    The original numeric ID(s) can only be decoded if you know the original alphabet that was used for encoding.
    • hot_gril 3y ago
      I wouldn't bank on that information not getting out. It may even be easy to reverse-engineer. Sqid says not to use it this way.
  • hot_gril 3y ago
    The point is to make a long number more human-friendly. But I don't get why these are non-sequential then.
    • s4i 3y ago
      Unless we are talking about very long numbers, surely the numbers are easier for people to deal with, say over the phone, etc?
      • hot_gril 3y ago
        I was going to say it's for very long numbers, but I tried an example, and 123645634 becomes ARsz1pHw789c7ESzhy. The output is actually longer, and more complicated. Looks like it uses a hash. I was expecting it to just convert the base except with something to skip profanity, which would give you something much shorter going base 10 to base ~36. Tbh I don't see why it's like this.
• darigo 3y ago
  Makes me think of something totally different, which is how Urbit converts randomly generated numerical IDs into sorta memorable names. For example, the number 5,702,400 becomes ~sorreg-namtyv. And 1,742,733,824 becomes ~master-morzod. I enjoy the quirkiness of the names.
• notfed 3y ago
  I appreciate that the author clearly states that security, i.e., output can't be reversed back to the input, is a non-requirement. We can't criticize the author too much for that either, because, as a rule, "random-looking id generator" algorithms will always be either not secure, or not short, or not collision-free. Or they'll be a key-value database. A secure "random-looking id generator" is called a block cipher. Block ciphers with less than 128 bits of output are widely considered insecure: this corresponds to about 22 base64 characters. Going further, you probably do want to use a secure algorithm. History is full of people thinking "we don't need this to be secure, it's not used for security-sensitive things" and later regretting it. Some case studies at [1]. [1] https://www.schneier.com/blog/archives/2016/04/security_risks_11.html https://www.schneier.com/blog/archives/2016/04/security_risk... .
  • geek_at 3y ago
    > i.e., output can't be reversed back to the input But in the "Not good for" section it states the opposite: "[not good for] User IDs can be decoded, revealing user count" so it can be reversed?
    • residentcoder 3y ago
      Added parenthesis to make what your parent commentor is saying clearer: >I appreciate that the author clearly states that security, (i.e., output can't be reversed back to the input), is a non-requirement.
  • pixel8account 3y ago
    It's good to consider this but... Plenty of sites expose user ID as a regular integer. In some cases you might want to avoid this (leaking user count to competitors etc), but I have never heard about anyone calling this a vulnerability.
    • woofcat 3y ago
      I hear this all the time. Every 3PPT report I see is cranky if you have userid=2345 as you can enumerate it. Personally I think it's stupid but this is a tempting solution.
• mfbx9da4 3y ago
  Was hoping for more of a high level technical explanation of how it differs from alternatives in the FAQ
• Alifatisk 3y ago
  On a side note, "Sqids ... is an open-source library that lets you generate YouTube-looking IDs from numbers.", "The main use of Sqids is purely visual." If the purpose of it is to give a friendlier url / id, who not use something like friendly_id instead? (http://norman.github.io/friendly_id http://norman.github.io/friendly_id). The url is readable and searchable through the history. I would much rather prefer people using "www.website.com/channel/video/a-dog-walking" instead of "www.website.com/channel/video/3cXv8c".
  • chrismorgan 3y ago
    These are called slugs <https://en.wikipedia.org/wiki/Clean_URL#Slug https://en.wikipedia.org/wiki/Clean_URL#Slug>. If you’re willing to commit to a persistent slug, please do: they are nicer. But for many applications, e.g. most user-generated content, you can’t be confident they won’t change. There’s a reason for the general advice to not use data as a primary key in databases, but to use a separate ID.
• zie 3y ago
  What we did 20yrs ago was generate random numbers and then ensure the # wasn't already used. We do this only for employee ID #'s and it works fine for us. It's definitely not ideal though.