Java Fragen zum MerkleTree und MessageDigest

[Slight]

Hallo,

ich muss einen MerkleTree implementieren der balanciert und k-när ist. k wird auf 5! beschränkt.

1. Ich möchte also die Datenblöcke hashen und den Blättern des Baums zuordnen, soweit ich das richtig verstanden habe.
Folgenden Code habe ich gefunden, welcher allerdings einen Binärbaum verwendet:
(https://github.com/richpl/merkletree/blob/master/src/merkletree/MerkleTree.java)

	private byte[] digest(Leaf leaf)
	{
		final List<byte[]> dataBlock = leaf.getDataBlock();
		
		// Create a hash of this data block using the 
		// specified algorithm
		final int numBlocks = dataBlock.size();
		for (int index=0; index<numBlocks-1; index++)
		{
			md.update(dataBlock.get(index));
		}
		// Complete the digest with the final block
		digest = md.digest(dataBlock.get(numBlocks-1));
		
		return (digest);
	}

Ich verstehe hier nicht wirklich den Unterschied von md.update und md.digest, ich habe das jetzt so verstanden dass "digest = md.digest(dataBlock.get(numBlocks-1));" nur das letzte byte Array hasht, aber das macht ja irgendwie keinen Sinn.
Auf dieser Seite: https://docs.oracle.com/javase/7/docs/api/java/security/MessageDigest.html habe ich es jetzt so verstanden, dass md.digest() den Hash produziert, und md.update das aktuelle Array in md legt um es dann zu hashen. Aber dann müsste diese Zeile doch auch innerhalb der Schleife liegen?

Ich würde mich freuen, wenn mich da jemand genauer aufklärt.

Außerdem wird hier (https://github.com/richpl/merkletree/blob/master/src/merkletree/MerkleTree.java) ganz oben die Logik des Binären Merkle-Trees erklärt: Ein Merkle-Tree besteht aus 2 Kindern und einer Hash Repräsentation der Kinder. Ich glaube für meine Aufgabenstellung brauche ich im Merkle-Tree selbst nur die Hash-Repräsentation. Diese Kinder sind entweder Blätter (in denen die Datenblöcke gespeichert werden) oder selbst Merkle-Trees.
Ich bin kurz davor das zu verstehen, aber blicke leider doch noch nicht ganz durch und kann es dementsprechend auch nicht richtig auf den k-nären Merkle-Tree übertragen. Ich hätte es erst so implementiert, dass es eine Klasse Merkle-Tree gibt die Nodes enthält und eine Klasse Nodes, welche dann z.B. die Variablen "List<Node> childs" und "Node Parent" und "List<byte[]> dataBlock", ich glaube das wird aber viel komplizierter als die oben erwähnte Idee.
Kann mir das vielleicht jemand erklären und hätte eine Idee, wie man das auf einen k-nären Baum übertragen kann? Gibt es dann vielleicht statt "MerkleTree leftMerkleTree" "MerkleTree rightMerkleTree" eine Liste die MerkleTrees beinhaltet?


Liebe Grüße und danke schon mal im voraus!

 

[fhtagn]

for (byte[] data : dataBlock) {
	md.update(data);
}
digest = md.digest();

So ist es vielleicht anschaulicher: update fügt zu hashende Daten hinzu, digest liefert den resultierenden Hash. Im Originalcode läuft die Schleife nur bis zum vorletzten Block und fügt den letzten Block außerhalb der Schleife hinzu, warum auch immer.

Ergänzung (18. Juni 2016)

Zum Thema Merkle-Tree. MMn sollte ein Blatt nur einen einzelnen Datenblock und den Hash für diesen speichern, denn man möchte ja die Integrität von einzelnen Datenblöcken prüfen können und nicht nur von, sagen wir, 5er Gruppen.

So könnte die Datenstruktur aussehen:

public class MerkleTree {
	private MerkleTree parent;
	private final List<MerkleTree> children;
	private final byte[] dataBlock;
	private final byte[] hash;   // dataBlock-Hash oder Hash der children-Hashes

	public MerkleTree(byte[] dataBlock) {}          // Leaf
	public MerkleTree(List<MerkleTree> children) {} // Subtree
}

Was noch fehlt, ist der Code, der den balancierten Baum aufbaut:
1. für jeden Block ein MerkleTree-Leaf anlegen. Das ist die unterste Ebene im Baum.
2. für jeweils 5 MerkleTrees ein MerkleTree-Parent anlegen. Parents ergeben die nächste Ebene.
3. Schritt 2 solange wiederholen, bis es auf oberster Ebene nur noch ein MerkleTree-Root gibt.

 

[Slight]

Vielen, vielen Dank für die Antwort, jetzt verstehe ich die Sache schon besser. Ein Merkle-Tree kann aber den Grad 5!=120 haben.

Der parent wird also erstellt, indem ein neues MerkleTree-Objekt angelegt wird, welches die Hashes der Blätter nochmal hasht und dieses parent wird dann bis zu 120 childs zugeordnet, hab ich das richtig verstanden?
Ich dachte erst, ich müsse eine neue Methode implementieren, die dann das gesamte Hash-byte-Array hasht und nicht die einzelnen Hashes die es enthält. Also dass es immer nur einen Wert für den Hash und kein Array gibt.

Ich habe nun versucht es so zu lösen, wie du es beschrieben hast:
https://www.dropbox.com/sh/z4hex6b95qkpkry/AABt9OoM7EiE27Mwx-672XDea?dl=0

Ich bekomme aber noch eine NullPointerException, obwohl ich glaube, alles initialisiert und gefüllt zu haben. Ich finde den Fehler aber einfach nicht, da ich jetzt auch in den Code eine Ausgabe geschrieben habe, die mir eigentlich auch die Daten, die angeblich nicht initialisiert sind, ausgibt. Und am Ende steht die NullPointerException.

Liebe Grüße

 

[fhtagn]

Ja, der Hash eines Vaterknotens sind die Hashes der Kindknoten nochmal gehasht.
Die NPE sehe ich nicht, müsste eigentlich einfach im Stacktrace zu sehen sein.
In den Konstruktoren stimmt etwas mit parent nicht. Auch sollten dataBlock, children und hash final sein, da man diese Werte später nicht mehr ändern kann, ohne dass der gesamte Baum neu berechnet werden muss.

public MerkleTree(byte[] dataBlock) {
    this.children = null;
    this.dataBlock = dataBlock;
    this.hash = this.md.digest(dataBlock);
}
 
public MerkleTree(List<MerkleTree> children) {
    this.children = children;
    this.dataBlock = null;
 
    for (MerkleTree child : this.children) {
        children.parent = this;
    }

    for (MerkleTree child : this.children) {
        this.md.update(child.hash);
    }
    this.hash = this.md.digest();
}

 

[Slight]

Ah okay, vielen Dank, jetzt hab ich es verstanden