kombinieren SHA1 Hashes, um einen neuen Hash zu generieren

Question

Mit einer (möglicherweise großen) Liste von eindeutige Textzeilen (stringifizierte JSON-Daten) Ich muss einen eindeutigen Hash für das gesamte Textdokument berechnen. Häufig werden neue Zeilen an das Dokument angehängt und gelegentlich werden einige Zeilen daraus gelöscht, was zu einem völlig neuen Hash für das Dokument führt.

Das ultimative Ziel ist es, identische Dokumente nur mit dem Hash zu identifizieren.

Natürlich das SHA1-Hash für das gesamte Dokument nach jeder Änderung der Berechnung würde ich die gewünschten eindeutigen Hash, sondern wäre auch rechnerisch teuer - vor allem in einer Situation, in der nur ~ 40 Bytes angehängt werden, um ein 5 Megabyte-Dokument und alle diese Daten müssten erneut die SHA1-Berechnung durchlaufen.

Also, ich bin auf der Suche nach einer Lösung, die es mir erlaubt, die Zeit zu reduzieren, die es dauert, den neuen Hash zu berechnen.

Eine Zusammenfassung der Problemeigenschaften/Anforderungen:

• jede Linie garantiert
• die Reihenfolge der Linien einzigartig sein muss nicht unbedingt müssen (noch besser aus, wenn es nicht der Fall ist)
• die Länge einer einzelnen Zeile ist in der Regel klein, aber das ganze Dokument groß sein könnte
• kann der Algorithmus für beigefügten Daten optimiert werden (dh delet ing Daten könnten sogar einen Neustart von Grund auf in einem solchen Fall erforderlich)

Meine aktuelle Idee ist, die SHA1 (oder was auch immer) Hash für jede einzelne Zeile einzeln und dann XOR die Hashes zusammen zu berechnen. Das sollte alle Anforderungen erfüllen. Für neue Linien berechne ich einfach den SHA1 dieser Linie und XOR es mit der bereits bekannten Summe.

Allerdings bin ich in Zweifel, weil ...

• Ich bin nicht sicher, ob die XOR-verknüpft Hash immer noch stark genug sein würde, um genau ein Dokument zu identifizieren (dh. Ist es eine deutlich höhere Wahrscheinlichkeit, unerwünschte Kollisionen?)
• Berechnung vieler SHA1-Hashes von kurzen Linien könnten rechnerisch teuer von seinem eigenen (zumindest während der Initialisierung)

Wer seine etwas Licht in diese Fragen vergießen?

Alternativ ist es vielleicht allgemein mit SHA1 (oder einem ähnlichen Hash) möglich, schnell einen neuen Hash für angehängte Daten zu generieren (old hash + appended data = new hash)?

Answer 1

können Sie inkrementelle Aktualisierungen durchführen zu Gleichstrom-Berechnung:

var crypto = require('crypto'); 

var shasum = crypto.createHash('sha1'); 
shasum.update("Hello, "); 
shasum.update("World!"); 
console.log(shasum.digest('hex')); 

shasum = crypto.createHash('sha1'); 
shasum.update("Hello, World!") 
console.log(shasum.digest('hex')); 

Answer 2

Es gibt Probleme mit jede Datei einzeln Hashing.

Wenn zwei identische Zeilen hinzugefügt werden, ändert sich der kombinierte Xor nicht.

Sie könnten besser die einzelnen Zeilen Hashing hashing.

Verwenden Sie vielleicht eine Merkle Tree.