Merkle wortel en boom van Bitcoin – Hoe te bouwen?

Volgen en delen nu!

Wanneer u meer te weten komt over versleutelde valuta's, vindt u de term Merkle wortel respectievelijk de Merkle tree. Het is in Bitcoin gebruikt als elementaire functie om blokken te bouwen. Weten hoe de Merkle tree te bouwen is essentieel om software te ontwikkelen die nodig is om blokken te bouwen, zoals een pool-of mining software.

Vingerafdrukken – veilige gegevensintegriteit:

Een vingerafdruk of in deze context eerder Hash is het resultaat van een functie en een reeks bytes. Het resultaat van dezelfde functie en een gelijke volgorde van bytes in dezelfde volgorde zal altijd hetzelfde zijn, alleen de kleinste verandering keert terug met zeer grote goed een complete andere hash.

Gebruik van hashes:

Er zijn drie grote gebruik van hashes:

  • Omdat het niet mogelijk is om een dergelijke hash terug te berekenen naar de invoer byte-reeks, worden systemen met gebruikersverificatie opgeslagen als gebruikelijk alleen de hash in plaats van een gewoon wachtwoord voor meer beveiliging. Het systeem vergelijken op verificatie alleen de opgeslagen hash met de hash van de invoer van het wachtwoord.
  • Hashes worden gebruikt voor zeer eenvoudige gegevens vergelijkende. Op veel websites wordt een bestands-hash weergegeven op Download pagina's. U hoeft alleen maar de hash van uw gedownloade bestand te berekenen en ze te vergelijken met de hash op de website om bijna absoluut zeker te zijn, u hebt het juiste bestand gedownload, omdat slechts één bit verandering waarschijnlijk een andere hash zou produceren.
  • De hash van een reeks bytes is met uitzondering van het berekenen van deze niet voorspelbare, versleutelde valuta's gebruiken hashes als uitdaging voor regulering.

Wat is een Merkle wortel?

Een Merkle wortel, vernoemd naar Ralph Merkle die ze patenteerde, is een hash, berekend op basis van een geordende opeenvolging van hashes. Bitcoin slaat een Merkle wortel op in de byte sequenties genaamd Block, dit veld heet ook Merkle root. Ze worden berekend door een virtuele constructie, genaamd Merkle tree.

Wat is een Merkle boom?

De naam Merkle tree komt van binaire bomen zoals gerichte grafieken, waarbij elk element behalve de meeste top heeft een pretendent en maximaal twee opvolgers. Het bovenste element wordt het hoofdknooppunt genoemd, dus de Merkle-wortel is slechts het hoofdknooppunt van een Merkle-boom. De structuur wordt alleen gebouwd om het hoofdknooppunt te krijgen en daarna te worden weggegooid.

Hoe bouw je een Merkle boom? – Stap voor stap:

Volg gewoon deze eenvoudige stappen om een Merkle-boom uit een reeks hash te berekenen:

  1. In gevallen begint u met slechts één hash, deze is al de Merkle wortel.
  2. Neem de hashes besteld in groepjes van twee. Als u een oneven aantal hashes hebt, bevat de laatste groep het laatste element twee keer.
  3. Concatenate the hashes in little endian byte order, hence the least significant bit of the first hash is the least significant bit of the concatenation.
  4. Hash the concatenation and store the result in last-in-last-out order, the result of the first two hashes is the first element of the next row.
  5. Continue the previous three steps, until you have the single top root node.

This image describes the virtual Merkle Tree of the three hashes A, B and C in Bitcoin using the algorithm SHA-256 twice:

How to build a merkle tree

Purpose of the Merkle Root in Bitcoin:

The Merkle Root in the Bitcoin block header field with the same name is calculated from the hashes of the transactions of this block.

Ensuring data integrity:

The only connection between a Block header and the transactions is the stored Merkle Root. Nevertheless, the data integrity is ensured, a change of a transaction would change the transaction hash, this would change the Merkle Tree and this the hash of the block header.

Faster block header hashing:

The hashing time of a block header doesn’t depend on the transaction count stored in this block. That is for fair mining very important. The Merkle Tree needs just to get recalculated, each time the transactions change, but this is very fast, even compared with finding a block with the lowest possible difficulty. It would be otherwise a competition between the speed of generating and testing block headers and transaction count.

Less internet traffic for miner and pools:

Big pools needs a very strong internet connection. Since miners need to build steadily block headers, a miner needs to know the Merkle Root. The pool transfers only with the method mining.notify the hashes of the transactions to build the tree local, a transfer of all transactions would cost a lot more traffic, most transactions are bigger than the block header.

Less storage space needed:

It is possible to test a block for containing a transaction just by knowing the hashes. Lightweight Bitcoin clients use this fact to store just hashes instead of the full transactions to reduce the storage space of the global blockchain database.

Java build Merkle Root example code:

The Java class MerkleRootBuilder below implements the calculation of a Merkle Root. It expects as constructor arguments an instance of a sorted java.util.Collection (for example java.util.ArrayList), containing the hashes as little endian byte arrays and an implement of the Interface HashFunction, properly an instance of the class DoubleSha256HashFunction. The first element of the byte arrays has to be the least significant byte of the hashes, the first element of the collection (element 0 on indexed collections) should be the coinbase transaction, element 1 the second transaction of the block and so on.

The method build starts at the bottom of the tree with two Deques. One contains the hashes of the current row, the other one is the target of the results. If the source deque contain an odd count of elements, the last element is at the start of the next row uncopied added a second time. In a perfect binary tree grows the row element count exponential to the linear growing of rows, so adding the element a second times become on big element count faster than testing each element for being the last one. The arrays become never changed nor sent to outside the own class instances, so we doesn’t need to copy them. The inner loop gets the elements in pairs of two, concats them, hash them (for abstraction in two steps, it could be one step for more performance) and adds the result to the other deque. After the last two elements became handled, the source and target deques become swapped and the game start from scratch, along there is more than one hash left.

public final class MerkleRootBuilder implements Factory<byte[]> {
	private final Collection<byte[]> elements;
	private final HashFunction hashFunc;

	/**
	 * 
	 * @param elements A sorted collection of hashes, each in little endian order. (elements.get(x)[0] = the least significant byte)
	 * @param hashFunc
	 */
	public MerkleRootBuilder(final Collection<byte[]> elements,
			final HashFunction hashFunc) {
		if(elements == null) {
			throw new IllegalArgumentException("elements == null");
		} else if(elements.size() == 0) {
			throw new IllegalArgumentException("elements.size() == 0");
		} else if(hashFunc == null) {
			throw new IllegalArgumentException("hashFunc == null");
		}
		
		this.elements = new ArrayList<byte[]>(elements.size());
		this.elements.addAll(elements);
		
		// Check from field to avoid race manipulation
		for(final byte[] bs:this.elements) {
			if(bs == null) {
				throw new IllegalArgumentException("elements contains null");
			}
		}
		this.hashFunc = hashFunc;
	}
	@Override
	public byte[] build() {
		// Just one hash? We have the root already =)
		if(elements.size() == 1) {
			// Get the single element
			for(final byte[] once:elements) {
				return(once);
			}
		}
		
		Deque<byte[]> now = new LinkedList<byte[]>(elements);
		Deque<byte[]> nxt = new LinkedList<byte[]>();
				
	
		
		do {
			// If the current row of the Merkle Tree contains
			// an even element count, the last hash become
			// concatted by itself.
			// Doesn't copy it, we won't change it!
			if((now.size() & 1) != 0) {
				now.addLast(now.getLast());
			}
						
			while(now.size() > 0) {
				final byte[] h0 = now.removeFirst();
				final byte[] h1 = now.removeFirst();
				final byte[] cat = concatBytes(h0, h1);
				final byte[] hash = hashFunc.hash(cat);
				nxt.addLast(hash);
			}
			// Triangle swap of source and destination for the next
			// level.
			final Deque<byte[]> tri = now;
			now = nxt;
			nxt = tri;
		} while(now.size() > 1);
		return(now.getFirst());
	}
	/**
	 * 
	 * @param a
	 * @param b
	 * @return (a[0],a[1],a[2]...a[n-1],b[0],b[1],b[2]...)
	 */
	private byte[] concatBytes(final byte[] a, final byte[] b) {
		final int aLen = a.length;
		final int bLen = b.length;
		
		final byte[] c = Arrays.copyOf(a, aLen + bLen);
		System.arraycopy(b, 0, c, aLen, bLen);
		return(c);
	}
}
public final class DoubleSha256HashFunction implements HashFunction {
	@Override
	public byte[] hash(final byte[] in) {
		try {
			final MessageDigest d = MessageDigest.getInstance("SHA-256");
			d.update(in, 0, in.length);
			final byte[] firstTurn = d.digest();
			d.reset();
			d.update(firstTurn, 0, 32); // 256 Bit = 32 Byte
			return(d.digest());
		} catch (final NoSuchAlgorithmException e) {
			throw new RuntimeException(e);
		}
	}
}
public interface HashFunction {
	public byte[] hash(byte[] in);
}
public interface Factory<T> {
	T build();
}

Merkle Root examples:

Here are some examples to test your software and play with. The hex strings are little endian, but convert it back to real bytes before hashing.

Example 0:

Input:


 

Output:

<error>

 

Example 1:

Input:

982051fd1e4ba744bbbe680e1fee14677ba1a3c3540bf7b1cdb606e857233e0e

(Bron: Block #1)

Output:

982051fd1e4ba744bbbe680e1fee14677ba1a3c3540bf7b1cdb606e857233e0e

 

Example 2:

Input:

252bf9d75c4f481ebb6278d708257d1f12beb6dd30301d26c623f789b2ba6fc0
e2d32adb5f8ca820731dff234a84e78ec30bce4ec69dbd562d0b2b8266bf4e5a

(Bron: Block #80000)

Output:

190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f

 

Tree:

 

 

Example 3:

Input:

c6f2ba9c82a506b634cea1047e0993c0d7205f08561262cc4a5e69cdbd659cf8
4f21bb697bf3d5293fc6e137440855358b86f2b599d90ede09edaec6f9be1818
0d02210b9177cfc8193b95254473ff7bd986ed1179c276d12bad5bdba2403ad4

(Bron: Block #99960)

Output:

f94b61259c7e9af3455b277275800d0d6a58b929eedf9e0153a6ef2278a5d534

 

Tree:

 

Example 4:

Input:

876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148c
c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff
c46e239ab7d28e2c019b6d66ad8fae98a56ef1f21aeecb94d1b1718186f05963
1d0cb83721529a062d9675b98d6e5c587e4a770fc84ed00abc5a5de04568a6e9

(Bron: Block #100000)

Output:

6657a9252aacd5c0b2940996ecff952228c3067cc38d4885efb5a4ac4247e9f3

 

Tree:

 

Example 5:

Input:

3658837f39d3c6e170726ebccde47edaf5340ac830991ea7b3aaffee453f5ddc
48cc12597887c93dc161f82d8b0adf4166cc169c7be8b1cf78bfbf29448bd90e
eaaee2b601061be3fd3a547c8bbdab5658fdcd0fb633de09b06059be17da0881
d968b21afa85d6fab016c39176604fed99487f98975dc295b2139bf28fa4ffec
e7f42d1556feef839d84257262435be1417baa4048a39594990e1dedef797fb5
66d7577163c932b4f9690ca6a80b6e4eb001f0a2fa9023df5595602aae96ed8d

(Bron: Block #99974)

Output:

cce3697d67c0fe334b1c0040be1368c5ffb2c563f2486fbbe28ecf0c47662027

 

Tree:

(Click/Tip to enlarge)

Plaats uw reactie hier

Uw e-mailadres wordt niet gepubliceerd. Verplichte velden zijn gemarkeerd *

Gratis Demo!

Toetreden tot het Calloway Crypto systeem nu,
om een gratis demo-account:

Join the Calloway Crypto Soft now!

Lees nu de hele beoordeling!

Hebt u aanvullende vragen of struikelen, stuur een email naar direct naar earnmoneytodayblog@gmail.com of gebruik de simpele Contact Formulier.

 

verdienen-money.today succesvolle uitdaging: 1041/2000 succesvolle handelaar. Test nu Calloway Crypto systeem of andere geverifieerde handelssystemen kostenloos en stuur ons hoe succesvol je bent en hoeveel winst je gemaakt, en kan wat wij voor u kunnen doen.

52%

Laatste succesvolle handelaar:
Antje B.
Worden de volgende!