# Map many crytocurrency token IDs (2^512) into a single set of tokens IDs (2^256)

Let we have a finite (small compared to 2256) set $$T$$ of 257-bit numbers.

Need a function $$f: T \to 2^{256}$$ such that it's almost of zero probability that $$f(n)=f(m)$$ for two different numbers $$n,m\in T$$.

Computation of $$f^{-1}$$ must be constant (at worst logarithmic) on the size of $$T$$.

Computation of $$f$$ must also be easy (not exponential, ideally constant time).

The function $$f$$ should "extend" easily when we add one new element to $$T$$.

How? Is this possible at all?

I need this to map two (in the future three) different kinds of crytocurrency token IDs into a set of tokens IDs.

Update: I realized I need to be able to do this even if 257 is replaced by 512 in the question. Well to be able to pack not 512 but just 256+160 = 316 numbers would be enough. It can be done by storing every new element of 𝑇 (it's initially empty) into the storage mapping its consecutive number $$f(T)$$ to the element of 𝑇, but I'd prefer to do it without any persistent storage (that is not storing anything between invocations of $$f$$ and when adding a new element to $$T$$).

• I realized I need to be able to do this even if 257 is replaced by 512 in the question. Well to be able to pack not 512 but just 256+160 = 316 numbers would be enough. It can be done by storing every new element of $T$ (it's initially empty) into the storage mapping its consecutive number to the element of $T$, but I'd prefer to do it without any persistent storage! Dec 25 '20 at 12:16
• Any function from $\{0,1\}^{512}\to\{0,1\}^{256}$ that's easy to compute in both directions for all inputs $t$ in arbitrary subset $T$ of $\{0,1\}^{512}$ will need about $256\,|T|$ bits of storage.
– fgrieu
Dec 25 '20 at 12:20
• @fgrieu Can I see a proof? Dec 25 '20 at 12:21
• Entropy argument: we can store set $T$ as the definition of function $f$ and the set $f(T)$. That gives a minimum size for the definition of $f$. We can approach that minimum with an explicit construction.
– fgrieu
Dec 25 '20 at 13:35