Create seemingly random IDs from Big Integer Sequence in PostgreSQL
Published: 2021-08-20 01:53:07

Here is a combination of cool code snippets I've received on StackOverflow over the years, to generate seemingly random IDs out of an incremental integer. You can use this to normalize your PostgreSQL BigInteger ID on a record table, so it doesn't appear, well, incremental. It is not for some security purpose, just for making the ID not *feel* like it's incremental.

First, we want to generate a random list of bytes. We then take that list of bytes and create a second list, mapping the output (array value) to the input (index). This essentially creates a two-way mapping function, but a random one. Then we do this as many times as we want, so each table has a different randomness feeling when generating the IDs. Here is that code.

```js
import fs from 'fs'

const json = [
  [],
  []
]

let i = 0
let a = []
while (i < 256) {
  a[i] = i
  i++
}

i = 0
while (i < 256) {
  json[0][i] = shuffle(a.concat())
  i++
}

json[0].forEach(a => {
  let o = new Array(256)
  a.forEach((x, i) => {
    o[x] = i
  })
  json[1].push(o)
})

fs.writeFileSync('seeds/id-generator.json', JSON.stringify(json))

function shuffle(array) {
  for (var i = array.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  return array
}
```

We then want to create a mapping from a BigInteger from PostgreSQL (or anywhere), and a custom ID string, and back.

Here is the code:

```js
import ID_SEED from './seeds/id-generator.json'

const CODE = `abcdefghzyxwvust`

function toPublic(id, salt) {
  const byteArray = bnToBuf(id)
  const eightArray = new Array(8)
  byteArray.forEach((x, i) => eightArray[i] = x)
  const n = 8 - byteArray.length
  let i = 0
  while (i < n) {
    eightArray[i] = 0
    i++
  }
  let j = 0
  while (i < 8) {
    eightArray[i] = byteArray[j]
    j++
    i++
  }

  let string = eightArray
    .map((x, i) => ID_SEED[0][salt + i][x])

  string = string
    .map((x, i) => {
      let v = toStringRadix(x, CODE).padStart(4, toStringRadix(0, CODE))
      return v
    })
    .join('')
  return string
}

function toPrivate(string, salt) {
  let byteArray = chunkSubstr(string, 4)
    .map(x => parseIntRadix(x, CODE))
    .map((x, i) => ID_SEED[1][salt + i][x])
  return bufToBn(byteArray).toString()
}

function bnToBuf(bn) {
  let hex = BigInt(bn).toString(16)
  if (hex.length % 2) {
    hex = '0' + hex
  }

  const len = hex.length / 2
  const u8 = new Uint8Array(len)

  let i = 0
  let j = 0
  while (i < len) {
    u8[i] = parseInt(hex.slice(j, j+2), 16)
    i += 1
    j += 2
  }

  return u8
}

function bufToBn(buf) {
  const hex = []
  const u8 = Uint8Array.from(buf)

  u8.forEach(function (i) {
    let h = i.toString(16)
    if (h.length % 2) {
      h = '0' + h
    }
    hex.push(h)
  })

  return BigInt('0x' + hex.join(''))
}

function parseIntRadix(value, code) {
  return [...value].reduce((r, a) => r * code.length + code.indexOf(a), 0)
}

function toStringRadix(value, code) {
  var digit
  var radix = code.length
  var result = ''

  do {
    digit = value % radix
    result = code[digit] + result
    value = Math.floor(value / radix)
  } while (value)

  return result
}

function chunkSubstr(str, size) {
  const numChunks = Math.ceil(str.length / size)
  const chunks = new Array(numChunks)

  for (let i = 0, o = 0; i < numChunks; ++i, o += size) {
    chunks[i] = str.substr(o, size)
  }

  return chunks
}

export default {
  toPrivate,
  toPublic,
}
```

First, we have to define the "code" we want to use for the ID string. We make it using an "alphabet" of a multiple-of-8 characters, so we chose 16 characters. There is this great function using radix math to convert an integer to a string using a code, and back. It works with any number of characters, but we choose multiple of 8 so it maps to bytes in a reversible way.

```js
console.log(toStringRadix(72, CODE)) // => ez
console.log(toStringRadix(102, CODE)) // => gg
```

It is reversible too:

```js
console.log(parseIntRadix('ez', CODE)) // => 72
console.log(parseIntRadix('gg', CODE)) // => 102
```

So that's a pretty nifty function.

Then the next thing to do is convert the bigint string from the database to our custom ID format. That is what `toPublic` does. It also takes a "salt", an offset for the random array to use in generating the string.

```
console.log(toPublic(72, 0)) // => aaaaaatsaabbaayxaahyaafvaacaaavc
console.log(toPublic(102, 0)) // => aaaaaatsaabbaayxaahyaafvaacaaasx
```

Now, given an ID like this (which we may get as a parameter from the URL path), you can convert it back.

```
console.log(toPrivate('aaaaaatsaabbaayxaahyaafvaacaaavc', 0)) // => 72
console.log(toPrivate('aaaaaatsaabbaayxaahyaafvaacaaasx', 0)) // => 102
```

That's about it! Code is messy, but hey. Not spending the time refactoring it just yet!