checksum/fonction de hachage avec propriété réversible

Question

Je cherche un hashcode spécifique ayant les propriétés suivantes. Je ne connais pas de tels hashcodes et je ne sais pas s'il est possible de faire une telle chose. Je voulais juste le mettre dehors et voir ce que les gens disent.

J'ai deux bases de données (terme vaguement utilisé - ne pense pas à SQL ou quoi que ce soit de ce genre), un maître et une sauvegarde. Il est nécessaire de synchroniser les deux bases de données et de détecter si les bases de données ne sont pas synchronisées. Au lieu de vérifier toutes les données, il serait préférable de conserver un code qui peut être vérifié. Mais les deux bases de données ne partagent pas nécessairement toutes les modifications. Étant donné que les modifications du maître à la sauvegarde sont groupées, il est possible que certaines modifications du maître à sauvegarder soient réduites.

ie: disons que l'état actuel de la base de données comporte les éléments A-> X, B-> Y et C-> Z. Maintenant B est modifié tel que B-> Y1 puis plus tard B-> Y2. Le seul changement qui sera envoyé du maître à la sauvegarde est B-> Y2. L'intermédiaire B-> Y1 est ignoré.

Maintenant, au lieu de boucler tous les éléments de chaque base de données pour vérifier qu'ils correspondent, nous préférons conserver un code de hachage en cours des éléments dans les deux emplacements, puis juste comparer cela. Le hashcode aurait à calculer quelque chose comme:

supposant hashcode précédent de Hm0:
hashcode HM1 = f (Hm0, A-> X, B-> Y, C> Z)

lorsque des changements de B maintenant:
hashcode HM2 = f (HM1, B-> Y1)
puis
hashcode hm3 = f (HM2, B-> Y2)

donc maître aura hashcode de h3. Maintenant la sauvegarde ne recevra pas la modification B-> Y2, donc si elle calcule un code de hachage en cours, ce sera comme ceci:

hashcode hb1 = f (hb0, A-> X, B-> Y, C- > Z)
hashcode HB2 = f (HB1, B-> Y2)

maintenant, nous voulons HB2 et hm3 pour correspondre, comme l'état actuel des bases de données sont les mêmes. Mais la plupart (sinon tous) hashcodes ne fonctionnent pas de cette façon. Donc, ce que nous voudrions alors, c'est que nous voulions "enlever" la contribution de B-> Y du hachage d'abord, puis "ajouter" la contribution de B-> Y1, puis enlever la contribution de B-> Y1 et ajoutez la contribution de B-> Y2 dans le code de hachage. Nous voulons donc quelque chose comme ceci:

Deux fonctions, f, g: f modifient le hashcode existant en ajoutant la contribution d'un nouvel élément, tandis que g modifie le hashcode existant en supprimant la contribution d'un élément.

Le maître:
HM1 = f (Hm0, A-> X, B-> Y, C> Z)

lorsque B se modifie à B-> Y1:
hm2 = g (HM1, B-> Y)
hm3 = f (hm2, B-> Y1)

lorsque B sont modifiés à B-> Y2:
HM4 = g (hm3, B-> Y1)
HM5 = f (hm4, B-> Y2)

hm5 est le nouveau hashcode f ou l'état actuel de la base de données (A-> X, B-> Y2, C-> Z)

sur la protection:
HB1 = f (HB0, A-> X, B-> Y, C- > Z)

lorsque B se modifie à B-> Y2:
hb2 = g (HB1, B-> Y)
HB3 = f (HB2, B-> Y2)

maintenant HM5 et hb3 devrait correspondre, car l'état actuel des deux bases de données est le même. Donc: Y a-t-il de tels algorithmes f et g? J'espère avoir clarifié la question ... Merci.

Answer 1

Il suffit d'ajouter et de soustraire vos codes. Avec h (x) étant n'importe quelle fonction de hachage:

hm2 = hm1 + h(B->Y) 
hm3 = hm2 + h(B->Y1) 
hm4 = hm3 - h(B->Y1) 
hm5 = hm4 + h(B->Y2) 

hb2 = hb1 + h(B->Y) 
hb3 = hb1 + h(B->Y2) 

hm5 et hb3 sont égaux.

Notez qu'il n'est pas nécessaire d'ajouter ou de soustraire. Toute opération réversible fonctionnera (théoriquement, multiplier/diviser peut aussi fonctionner, mais il pourrait y avoir plus de problèmes de débordement et d'ambiguïté sur ce qui se passe autour de 0).

Answer 2

Hmm. Je ne suis pas sûr d'une fonction de hachage qui fait exactement ce que vous demandez. Mais il semble qu'une structure similaire à la façon dont Git stocke ses révisions pourrait faire ce dont vous avez besoin (ce qui a été inspiré par la façon dont Monotone a stocké ses révisions). Git calcule la somme SHA-1 de chacun des fichiers du référentiel. Ceux-ci sont utilisés comme identifiants de blob. Il a ensuite un arbre, qui mappe les noms de fichiers aux ID blob (et autres sous-arbres, pour les sous-répertoires). L'identifiant d'un arbre est sa somme SHA-1. (Bien que ce ne soit pas pertinent pour votre utilisation, je ne crois pas, les arbres sont ensuite référencés par des révisions, qui incluent des choses comme l'auteur, la date et une ou plusieurs révisions parentes). Cela signifie que vous n'avez pas besoin de recalculer la somme SHA-1 pour chaque blob lorsque vous en mettez à jour un; il suffit de recalculer le SHA-1 pour le blob qui change et de recalculer le SHA-1 pour l'arbre.

Vous pouvez faire de même avec vos données. Calculez le hachage de chacun de vos objets et placez tous vos mappages clé-> hachage (valeur) dans un seul fichier, et calculez le hachage de celui-ci. Si le fichier contenant key-> hash (value) est trop grand pour que vous vouliez le re-hacher à chaque fois, vous pouvez le diviser en sections, et avoir une clé -> hash (section), où chaque section a une clé. > Hash (valeur). Un niveau de branchement devrait généralement être suffisant pour la plupart des cas, mais vous pouvez en construire une structure arborescente si vous en avez vraiment besoin.