On Nov 16, 2016 8:03 PM, Nikita Popov <nikita....@gmail.com> wrote: > > On Tue, Nov 15, 2016 at 6:32 PM, Dmitry Stogov <dmi...@zend.com> wrote: >> >> On Nov 15, 2016 18:50, Nikita Popov <nikita....@gmail.com> wrote: >> > >> > On Tue, Nov 15, 2016 at 4:19 PM, Dmitry Stogov <dmi...@zend.com> wrote: >> >> >> >> New patch, attached to bug report, should fix both problems. >> >> >> >> I'm going to commit it tomorrow, if no objections. >> >> >> >> >> >> Thanks. Dmitry. >> > >> > For the new validate_root patch, wouldn't we still end up with inode >> > collisions caused by the hash function? It looks like for inodes > 2^16 >> > collisions should be "common". >> > >> > Nikita >> >> >> It's not a problem to add inode check, but I think we don't need it. >> >> >> Let S1 and S2 strings, R1 and R2 root_hashes and F a hash function. >> >> You propose the following comparison for collision checks >> >> >> F(S1) ^ R1 == F(S2) ^ R2 && R1 == R2 && S1 == S2 >> >> >> R1 == R2 seems useless. The existing condition: >> >> >> F(S1) ^ R1 == F(S2) ^ R2 && S1 == S2 >> >> >> fails if S1 != S2 independently on R1 and R2. >> >> If S1 and S2 are the same, than F(S1) equal to F(S2) and consequently, to >> satisfy the whole condition, R1 should be equal to R2 >> >> >> Am I wrong? > > To clarify: My concern is not with the way the hash is compared, but that the > root hash itself could have collisions. That is, you have two root inodes I1 > and I2 and two root hashes R1 = H(I1), R2 = H(I2). In that case it may be > that R1 == R2, but I1 != I2. At least that's the way I understood the patch > -- it doesn't looks like there is anything explicitly preventing this.
I see. Actually, for 64-bit systems it's better to eliminate bits permutation at all, but for 32-bit we can't avoid possible collisions, even if we include high bits into hash. The good thing, that inodes above 2^32 may make sense only on filesystems above 16TB with 4096 block sise (may be I'm wrong). do you have any ideas? Thanks. Dmitry. > > Nikita
