1
$\begingroup$

Consider two sets:

The "big set" contains all integers between $0$ and $2^{160}$ exactly once.

The "small set" contains all integers between $0$ and $2^{32}$ exactly once.

Given that the number of members in the "big set" is greater than those in the "small set", there can't be an injective function $f(n_b) = n_s$ mapping any input being a member of the "big set" $n_b$ to an output that's a member of the "small set" $n_s$. If that function $f$ existed, it'd be the questions' answer.

For practical reasons, we assume that there can however still be a construction/algorithm with a practical function $f_p$ where the results of all inputs into $f_p(n_b)$ are a member of the "small set" and each $n_b$ points to a distinct $n_s$.

For a lack of understanding about cryptographic concepts, I'll call this property "collision-aware". E.g. to implement this construction, assuming a storage capacity of the size of $2^{256}$ (256-bit unsigned integer), is there a function $f_p$ or an algorithm that for any $n_b$ either returns a "collision" ("collision-aware") or a distinct member of $n_s$?

Improve this question
$\endgroup$
12
  • $\begingroup$ Is very unclear to me what you're looking for. How does what you're describing in your second paragraph differ from an injective function? $\endgroup$
    – Maeher
    Jun 25, 2021 at 13:04
  • 1
    $\begingroup$ Without any additional requirements the function defined as "If $x\leq2^{32}$, return $x$, else return $\bot$." seems to satisfy your requirements from the question. But I'm sure that you have additional requirements that you for some reason refuse to specify. $\endgroup$
    – Maeher
    Jun 25, 2021 at 13:25
  • 1
    $\begingroup$ What about a truncated hash? In our use case, that works up to and including #101 with less than 1 chance in 850 thousand of the contrary. $\endgroup$
    – fgrieu ♦
    Jun 25, 2021 at 14:58
  • 1
    $\begingroup$ Next obviously wrong attempt to find out what you're really looking for: Assign indices sequentially. Maintain a 33-bit counter n initialized at zero. Everytime you see an input, if $n<2^{32}$ return n and increment the state. If $n=2^{32}$ return $\bot$. $\endgroup$
    – Maeher
    Jun 25, 2021 at 17:54
  • 2
    $\begingroup$ You could try using a truncated hash and maintaining an approximate set membership datastructure (e.g. a Bloom filter) of the used up indices. But it's likely that that will end up being too large. $\endgroup$
    – Maeher
    Jun 25, 2021 at 21:47

2 Answers 2

Reset to default
2
$\begingroup$

What about:- $$ n_s = \mathcal{H}(n_b) \& (2^{32} - 1) $$ where $n_b \in N_b$, etc? $\mathcal{H}$ can be a hash function of your choosing. Since this is a crypto site, I suggest SHA-256. $\&$ means bitwise AND, but could be replaced with right or left shifts of the appropriate number of bits (128 in SHA-256's case). Too slow perhaps(?)

Cryptographic hash functions are surjective, meaning their outputs occasionally collide. That rate of collisions will greatly increase if you truncate $\mathcal{H}$ to 32 bits. Even more so will the effect of the pigeon hole principle. So you'll have set $N_b$ filling up with uniformly distributed numbers, giving $n_b \to n_s$ from domain to codomain.

I don't know about Ethereum, but 160 looks suspiciously like the output of SHA-1. If so, just truncate the account/address to 32 bits as it's already uniformly distributed.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ "Cryptographic hash functions are surjective" - I don't think so. Surjective means that for every possible hash value, there exists some message that generates it. You can't prove that a cryptographic hash function has no "blind spots". $\endgroup$
    – Nayuki
    Jun 25, 2021 at 21:15
  • $\begingroup$ Hey @paul-uszak. I've commented in my original answer why I believe truncating is not the optimal solution. Wrt to uint160 and SHA-1: In Ethereum an account is derived from an ECDSA public key, then hashed using Keccak-256 to a 32bytes output and then - surprisingly - truncated using only the last 20 bytes. Finally it's prefixed with 0x. See more: ethereum.stackexchange.com/a/3619/47031 $\endgroup$
    – user10030
    Jun 25, 2021 at 21:28
  • $\begingroup$ @user10030 So you have your answer :-) Truncate to four bytes and there you have it, as in my post scriptum. $\endgroup$
    – Paul Uszak
    Jun 26, 2021 at 2:49
  • $\begingroup$ While I appreciate the existence of your solution, I believe it's not what I'll ultimately need. In case I truncate to 4 bytes, I start giving my users an incentive to mine for $n_b$s that result in the same $n_s$. Sure, for addresses $n_b$ that only hold a low amount of monetary value this may not be a real problem or an economically sound attack: But I'd like to generally avoid this type of problem. There either cannot be collisions or there can be collisions and I'm immediately aware of them as I can look back at all other hashing operation inputs and outputs. $\endgroup$
    – user10030
    Jul 2, 2021 at 10:26
  • $\begingroup$ @user10030 Absolutely there will be collisions due to the pigeon hole principle. At a best rate of $2^{-32}$ per account. Then it will increase asymptomatically towards 1 as the codomain fills up. $\endgroup$
    – Paul Uszak
    Jul 2, 2021 at 16:37
1
$\begingroup$

If I understand the requirements, what you are asking for is not a "function" according to the normal definition. It sounds like you want some $f$ that given a sequence of inputs ${x_i}$ will return either a deterministic value $y_i$ or an error symbol if it has already returned $y_i$. But suppose $x_k$ is the first input to return an error. What should happen if you call $f$ with the sequence starting from $x_k$? I think you would want it to not return an error, so the value of $f(x_k)$ is not well-defined.

The way to resolve that mathematically is to change the definition of $f$ to accept a sequence. But practically, what that probably means is having your system record all the inputs that is has been called with. And you'll find that if you do that, you might as well just return $0, ..., n-1$ for the first distinct inputs, and errors for everything following.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, practically being "collision-aware" would probably mean having to pass a sequence to $f$. Actually, passing in a sequence would be no problem as long as it wouldn't lead to an increase in storage for each new hashing operation. I'm wondering if there's e.g. a way where the previously passed value could be factorized or compressed such that they won't take up much storage and where it'd become practical to always pass all past values and a new one to make the function "collision-aware", as in "it's returning an error symbol if it encounters an output for more than the first time". $\endgroup$
    – user10030
    Jul 2, 2021 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.