Thank you for this. arxid is my first published package and my first open-source project, so a detailed critique is worth a lot more to me than silence would have been, and I'd rather hear it now than after someone deployed it. You said critiquing can be fun; getting critiqued this thoroughly turned out to be useful in a way I didn't expect.
I went and measured everything you raised. Most of it held up, some of it was worse than you said, and one of my own follow-up guesses turned out wrong. The result is shipping as spec v2.
The threat model. You asked the direct question and the answer is no: it is not computationally infeasible to recover an id without the key. The repo said a lot about what arxid isn't and never once stated what it defends against. There's now a threat model section that says plainly what it stops (URL-walking, row counts, growth rates), what it doesn't (forgery, anyone with the key, anything your authz layer should have caught), and the limits with numbers.
On rounds, you were right, and I took the paper's actual recommendation. I built the distinguisher. Fixing one Feistel half and varying the other, the statistic Lout XOR Lin collides at roughly twice the rate of a random permutation. I validated the methodology against an actual Fisher-Yates permutation first (ratio 0.989, as theory says). At the real 40-bit width, 4 rounds separates at ~2^13 chosen queries and reaches ratio 1.85 by 2^16. The structure is gone by 5 rounds. But you pointed at Patarin, and Patarin's recommendation is at least 6 rounds for a pseudorandom permutation, so rather than argue that 5 was enough, v2 ships 6. The extra round over the measured threshold is lost in the noise of the base62 step (below), so there was no reason not to take the recommendation. That's what picking the count by measuring avalanche instead of resistance to attacks had cost me, and the worst-pair column in my own published table (0.1117 at 4 rounds vs 0.0039 at 5) was already saying so. The signal was in my README and I didn't act on it.
Your consecutive-codes point was the sharpest thing in your post, and it's worse than you argued. You said guaranteeing it would spill information. Correct, an ideal permutation produces adjacent pairs about twice per full domain, so guaranteeing zero is itself a distinguisher. But when I measured, v1 didn't produce too few. It produced them hundreds to thousands of times more often than chance. Consecutive ids landing on adjacent codes leaks exactly the ordering the library exists to hide. Concrete counterexample in shipped 0.1.0, identical in the Rust and TypeScript ports: under key 0x652BFD48C7ED0458, ids 48326508 and 48326509 encode to 5kusgvr and 5kusgvs. That claim was asserted in three READMEs and pinned by three test files that passed only because they happened to sample points where it held. All removed. Zero occurrences at 6 rounds.
The one you got at sideways is real and neither of us named it. "Ciphertext fed directly to the cipher", determinism is inherent to stateless reversible FPE, that part is the product. But underneath it is that arxid has no tweak. FF1/FF3-1 have one for exactly this reason. /orders/5kusgvr and /users/5kusgvr were the same id under one app-wide key, and that was undocumented. Now documented, with a per-resource-type key as the mitigation.
Also fixed: the key schedule. You flagged it as homemade, and the key equals not-key property, discovered after the fact and then frozen as "not a defect", was the evidence you were pointing at. The cause was folding the key halves with XOR, which cancels under complement. Changed to a wrapping add; full 2^64 key space back, and u64::MAX is now a meaningful test vector instead of a duplicate of key 0.
Where I'd push back a little. On ergonomics, keeping a sequential PK and deriving the public code is the design goal, not an accident, the id is an internal identifier, not a secret. But you're right about the coupling, and it turned out to matter more than either of us said: the distinguisher above is unreachable from the encode side, because it needs thousands of ids sharing their low 20 bits and a deployment with ids under a million has at most one per class. From the decode side it's free, the attacker picks the codes, and all 2^20 codes with a fixed high half are valid strings, so I measured that direction all the way to the 2^20 wall. The only thing it also needs is the application revealing the decoded id. So your "it's easy to leak this ID inadvertently" objection is precisely what converts a theoretical attack into a reachable one. Fair hit, and now in the docs as "do not echo internal ids back".
And you're right that random ids or UUIDs are the proper answer when ids need to be confidential. There's now a "use something else" table: random/UUIDv7 for confidentiality, FF1 or FF3-1 (NIST SP 800-38G) for real format-preserving encryption, HMAC in a lookup column for unforgeable public ids. Saying that out loud costs the project nothing.
Smaller ones, all conceded: hardcoded key in the docs that people would copy (worst practical item on your list, it was in four files, gone); no version in the key; endianness for key storage (from_key_bytes / fromKeyBytes, big-endian); repeated "frozen" boilerplate. On property-based testing you were right and I overstated my fix in an earlier draft: proptest is in the Rust suite, but the TypeScript port only had fixed-sample structural tests, so adding real property tests there is on me. What did land now is a CI job that generates 200k randomized rows from the Rust reference each run and checks the TypeScript port against them, differential fuzzing across the ports, which the repo had none of.
What the extra rounds cost, since it's the obvious objection. On the bare permutation each ARX round costs on the order of ~1.5 ns, so two extra rounds is about +3 ns, real, but on a number no one ships. On the path an app actually pays, permutation plus the base62 String, it vanishes: the allocation dominates and its own jitter is several ns, larger than the round cost. One run of my own benchmark clocked the 5-round encode as faster than the 4-round one, which is impossible and is the whole point, on that path the round count is below the noise floor. I had to interleave every arm in one process to see even that much; timing one count in one session and another later gives noise several times larger than the effect, which is the trap the old benchmark table fell into. So I've stopped quoting the benchmarks to three significant figures, the section now tells you to measure on your own hardware, and the round count I used to defend on performance grounds was never buying me anything measurable where it mattered.
The spec is no longer described as frozen. v1 shipped frozen before anyone had looked at it, that was the actual mistake, upstream of every technical one. You called it as the first issue in your post and it was the right call. v2 is the current version, not the final one, and the contributing guide now asks for a measurement rather than an argument when someone wants to propose v3. Every experiment above lives in examples/ so nobody has to take my word for any of it.
Thank you. This was worth more than the release was.
I've written a lot below but I do get the feeling this crate is more of a 'I made something for fun' thing. This makes most of the concerns below not really important but I do want to raise them for fun on my end too, since critiquing can be fun.