Как получить разумный CRC CRC

Question

У меня есть древовидная структура, где каждый узел знает свой CRC. Какой разумный способ вычислить CRC для каждого поддерева, что даст мне хорошее значение для всего поддерева к этому моменту? Другими словами, значение, определяющее, была ли изменена какая-либо часть поддерева.

Моя текущая мысль - просто взять каждый дочерний узел CRC, преобразовать его в строку/байт [], объединить все узлы вместе и взять CRC этого байта []. Но я не уверен, что это может привести к легким столкновениям, поскольку я подозреваю, что это удаляет довольно много информации.

(я смотрел на crc32_combine, но это кажется неуместным, потому что у меня нет каких-либо длины. Я мог бы использовать нулевую длину, но это будет лучше или хуже?)

Работа в C#, но я предположим, это действительно язык агностик.

EDIT: Закончен с использованием этой техники. Будет переключиться на более длинные хэши, если столкновения, похоже, будут проблемой. Хотя мне не нужен порядок листьев, чтобы быть важным, я не использую xor на всякий случай, если это произойдет позже.

Answer 1

В идеале вы бы объединить ЗПК узлов для вычисления CRC из суб-дерева, используя что-то вроде crc32_combine(). Результат будет таким же, как вычисление CRC по всем узлам в любом каноническом порядке, который вы определили. Это только проверит порядок, но не структуру дерева. Другая структура с тем же порядком даст тот же CRC. Это будет справедливо независимо от того, как вы комбинируете CRC, если не включить дополнительную информацию о древовидной структуре.

Для использования crc32_combine() требуется длина данных для каждого из комбинированных CRC (кроме первого). Это, по-видимому, не сохраняется и недоступно в этом случае. Вместо этого вы можете сделать поток байтов CRC в каноническом порядке и взять CRC этого потока. (Вам нужно будет решить, должны ли CRC быть сохранены в потоке байтов большими или маленькими, а затем придерживаться вашего соглашения.)

Использование криптографических подписей, таких как SHA1 или MD5, не является необходимым, если вы не являетесь по какой-то причине беспокоился, что коварный человек вмешивается в ваши расчетные контрольные значения и пытается обмануть вас, думая, что содержимое дерева не изменилось, когда они есть. (Коварный человек уже может делать это на уровне узлов в любом случае, поскольку CRC легко подделываются.) В противном случае такие подписи просто теряют время процессора. Если вы просто хотите более длинный хеш, более 32 бит, чтобы уменьшить вероятность столкновений, вы можете использовать быструю хеш-функцию, такую ​​как одна из CityHash family.

Answer 2

Я бы использовал, по крайней мере, SHA1 для ваших контрольных сумм, поскольку столкновений не так уж и редко для MD5, и ваша идея о объединении CRC кажется твердой, хотя лично я бы XOR хэши вместе, чтобы сэкономить на RAM и CPU.

Answer 3

используйте что-то предназначенное для этого, например, SHA-2. Вы можете уйти с CRC32 в зависимости от ваших конкретных требований. Существует аналогичный вопрос размещен здесь с большим количеством обсуждения:

Can CRC32 be used as a hash function?