39 ms·

Yeah - I was going to say the same thing. Hashing would be the way to go if you're going for runtime and efficiency. You select the elements in an ordered manne

Yeah - I was going to say the same thing. Hashing would be the way to go if you're going for runtime and efficiency. You select the elements in an ordered manner though so that makes it n*log(n) and then produce a hash value for each table (or each row in the table) -- I'm trying to think if there is a better way of doing it in less time right now but I'm not seeing it yet. You could do this in O(n) or even constant time but it adds a bit of complexity to the solution I think.

Someone 3y ago
If you hash each row in isolation and XOR the hashes of all rows, you don’t need the ordering. I also think XOR-ing doesn’t lose you ‘resolving power’ for this problem, compared to hashing the hashes or hashing everything in one go.
- photon_lines 3y ago
  Ahhh nice - yup that's one solution and really elegant as well. Great suggestion :)
- sibrahim 3y ago
  XOR is not a great choice here. Consider that 2 copies of a row give the same result as 0 (or 4, 6, etc). And even without multiple copies of rows, you can force any hash you'd like by observing what happens when you insert more random rows and finding a subcollection that flips exactly the bits you want. What you probably want to look at is homomorphic hashing. This is usually implemented by hashing each row to an element of an appropriate abelian group and then using the group operation to combine them. With suitable choice of group, this hash can have cryptographic strength. Some interesting choices here are lattices (LtHash), elliptic curves (ECMH), multiplicative groups (MuHash).
  - Someone 3y ago
    > XOR is not a great choice here. Consider that 2 copies of a row give the same result as 0 (or 4, 6, etc). That indeed is a major flaw. You have to use another commutative operation that doesn’t destroy entropy. Addition seems a good choice to me. > And even without multiple copies of rows, you can force any hash you'd like I don’t see how that matters for this problem.
    - sibrahim 3y ago
      It depends on whether you are doing something security critical with the result. Maybe you have a trusted table hash but only a user-supplied version of the table. Before you use that data for security sensitive queries, you should verify it hasn't been modified. Basically, if you ever have to contend with a malicious adversary, things are more interesting as usual. If not, addition is likely fine (though 2^k copies of a row now leave the k lowest bits unchanged).

Someone 3y ago

If you hash each row in isolation and XOR the hashes of all rows, you don’t need the ordering. I also think XOR-ing doesn’t lose you ‘resolving power’ for this problem, compared to hashing the hashes or hashing everything in one go.

photon_lines 3y ago
Ahhh nice - yup that's one solution and really elegant as well. Great suggestion :)
sibrahim 3y ago
XOR is not a great choice here. Consider that 2 copies of a row give the same result as 0 (or 4, 6, etc). And even without multiple copies of rows, you can force any hash you'd like by observing what happens when you insert more random rows and finding a subcollection that flips exactly the bits you want. What you probably want to look at is homomorphic hashing. This is usually implemented by hashing each row to an element of an appropriate abelian group and then using the group operation to combine them. With suitable choice of group, this hash can have cryptographic strength. Some interesting choices here are lattices (LtHash), elliptic curves (ECMH), multiplicative groups (MuHash).
- Someone 3y ago
  > XOR is not a great choice here. Consider that 2 copies of a row give the same result as 0 (or 4, 6, etc). That indeed is a major flaw. You have to use another commutative operation that doesn’t destroy entropy. Addition seems a good choice to me. > And even without multiple copies of rows, you can force any hash you'd like I don’t see how that matters for this problem.
  - sibrahim 3y ago
    It depends on whether you are doing something security critical with the result. Maybe you have a trusted table hash but only a user-supplied version of the table. Before you use that data for security sensitive queries, you should verify it hasn't been modified. Basically, if you ever have to contend with a malicious adversary, things are more interesting as usual. If not, addition is likely fine (though 2^k copies of a row now leave the k lowest bits unchanged).