+++ date = '2023-09-23T03:00:03+07:00' draft = false title = 'A Simple Proof of XOR Uniqueness' author = ["Jose Sitanggang"] tags = ['computer-science', 'math', 'proof', 'bit-manipulation'] math = true description = "When computers are too slow to prove the correctness, mathematics rides to the rescue. That's why we need math -- even computers could use a little math magic!" +++
I have a simple algorithm to conceal an auto-increment ID within a globally unique identifier such as UUIDv4, which involves XOR. The motivation behind this algorithm is to eliminate the predictability of the auto-increment ID when it's exposed in a URL1.
I can use UUID directly, but indexing UUIDs in MySQL has a significant performance impact2. UUID is necessary for security, while the auto-increment ID is essential for performance. This algorithm combines the best of both worlds. The basic idea is to generate a new ID, called ShadowID, derived from both the UUID and the auto-increment. The requirement is that the ShadowID must be reversible to retrieve the auto-increment and the UUID if we know the algorithm and the secret number that used to generate the ShadowID.This reversibility is essential for utilizing the auto-increment ID for database queries and the UUID as a security token.
Since the ShadowID is used for identification, it must be unique.
As a software engineer, to determine whether applying XOR breaks the uniqueness of the ShadowID, I wrote a simple program. Everything worked well for integers with fewer than 16 bits. However, for 32-bit integers, I found myself waiting too long for the results, and for int64, I ran out of memory. It was quite disappointing.
Fortunately, I studied mathematics during my undergraduate computer science studies, so I decided to revisit my math textbook and came up with ideas to use math proofs instead. To put it in perspective, a set with
Before we dive into the proof, let's formalize the problem statement.
For any chosen positive integer
There are many ways to prove this statement. In this article, I will use the proof by contradiction.
Let's assume that there are two integers,
We will prove that this assumption leads to a contradiction, which means that we would find
Proof by contradiction
Based on the assumption, the left and right sides are equal, so applying XOR to both sides will also be the same4. Also, XOR is associative4. Therefore:
Applying XOR to an integer with itself equals
Performing the same operation on the left-hand side, we obtain:
As a result, we have found that
We've proven that applying XOR to an integer with any possible value of