https://www.open-mesh.org/https://www.open-mesh.org/favicon.ico?16699090422018-05-10T12:42:20ZOpen Meshbatman-adv - Bug #356: TT: XOR'ing CRC results unsafehttps://www.open-mesh.org/issues/356?journal_id=14242018-05-10T12:42:20ZAntonio Quartulli
<ul></ul>after searching online, it seems that a widely strategy to compute a hash of a set (=unordered collection of elements) consists in:
<ul>
<li>compute the hash of each elements</li>
<li>sort the computed hashes lexicographically</li>
<li>concatenate the hashes in a "non-ambiguous" way to form a new string</li>
<li>hash the resulting string.</li>
</ul>
<p>The hash obtained after the last step is the signature/hash of the set.</p>
<p>Unfortunately this cannot be done on-the-fly while traversing the TT table, but requires to store all the hashes of the various elements first.</p>
<p>There seems to be a paper describing how to compute the hash of a set with constant memory<sup><a href="#fn1">1</a></sup>, but I am not sure there is an implementation available to take inspiration from.</p>
<p>[1]https://people.csail.mit.edu/devadas/pubs/mhashes.pdf</p>