Efficient way to combine collection of hashes into a single hash?

Question

I have a system where each user will submit a set of data. The data will be hashed and their hash will be submitted to the server. My plan is to combine each users hash (converted to bytes XOR'd with the root hash) to generate a final hash. This is done as a means to create entropy so that the final hash can be used to generate a "random" number. It is not possible to generate a pseudo / truly random number on the system, hence the work around.

Currently, I am doing the following on the server (pseudo code) :

//hexidecimal 54673257461630679457 (large prime)

var rootHash = 0x2F6BE6DFD71F8B9A1;

submitData(var userHash){
    rootHash ^= userHash;
}

After all of the user hashes are XOR'd with the root hash, the root hash is converted into a number and then the last 10 digits of that number are used as the "random number."

Users are able to see eachother's hashes, however with a system like this, I figure even if they calculated the final number, submitting new data would change the root hash and thus change the final number generated.

I am not very experienced in this field so my question is, what are some of the cons of using a method like this, and is there a more efficient way to do this?

Answer 1

With the system as described, the last participant to submit its hash can trivially choose "the random number", knowing the initial value of rootHash and what hashes earlier participant submitted, by choosing the values of the hash s/he submits (s/he computes the XOR of these and $d+10^{10}r$ truncated to the hash width, where $d$ is the desired 10-digit value and $r$ is random; this insures "the random number" is $d$ ).

Even if what s/he submits has to be the hash of something (that's untold), finding a suitable something is feasible (that's expected to require a mere 5 thousand million hashes; or few hundred thousands if the last two submitters collude).

Replacing the XOR with a hash of the concatenation of the submissions do not help much (for example, it remains very easy for the last submitter to force "the random number" to be even).

A method truly solving this issue could be:

1. each participants draws a random $x_i$ (say, 128-bit)
2. each participant submits the hash of $h_i=H(x_i)$ to the server and/or each participant; that's called a commitment of $x_i$
3. after the above is complete each participant reveals its $x_i$
4. the server and/or each participant checks that $H(x_i)=h_i$ for all participants
5. the $x_i$ are processed just as the hashes in the question (there's no reason to initialize rootHash to an haphazard value, zero will do just as well).

This way each submitter can be convinced that whatever collusion there might exist among other participants, "the random number" is at least as unpredictable as the $x_i$ s/he submitted, if the hash is collision-resistant (implying it is wide, e.g. 256-bit). Note: if the hash was not collision-resistant, the last submitter of $x_i$ could have selected $x_i$ and $x_i'$ with equal hashes $h_i$, then knowing the $x_i$ of all other participants could decide to submit either $x_i$ or $x_i'$ so as to influence "the random number" in some controlled way.

Answer 2

Depending on your exact requirements (do you have often updates or deletes to the data?) a Merkle-Tree might help you here.