Aperçu
Merkletree est largement utilisé dans la technologie Bitcoin. Cet article vise à implémenter un simple Merkletree via le code et à calculer le Treerooot of Merkle Tree.
L'arbre Merkle est une structure de données qui vérifie tout type de données stockées, traitées et transmises entre les ordinateurs.
Actuellement, l'objectif principal de l'arbre Merkle est de s'assurer que les blocs de données reçus du réseau de pairs ne sont pas endommagés et inchangés, et de vérifier que d'autres réseaux de pairs ne mentent pas pour envoyer de faux blocs de données.
Exemple d'application de l'arbre Merkle
Bitcoin
Gita
La dynamo de Mazon
Gassandra
Applications en Bitcoin
Chaque bloc de Bitcoin contient une signature de collecte de toutes les transactions. Cette signature est implémentée à l'aide de l'arbre Merkle. L'arbre Merkle est utilisé pour le bitcoin pour résumer toutes les transactions dans le bloc, générer une empreinte digitale numérique globale de l'ensemble des transactions et fournir un processus très efficace pour vérifier si la transaction est incluse dans le bloc.
Une utilisation très importante des arbres Merkle consiste à vérifier si le bloc contient une transaction spécifiée. Les arbres Merkle sont construits en hachant récursivement des paires de nœuds jusqu'à ce qu'il n'y ait qu'un seul hachage.
Implémentation du code d'arbre Merkle
Le nœud de l'arbre de hachage est appelé la racine Merkle. L'arbre Merkle peut vérifier si un élément de données est inclus dans l'arborescence en utilisant la complexité temporelle de log2 (n):
Test de package; Importer java.security.MessagediGest; import java.util.arraylist; import java.util.list; classe publique MerkletRees {// Liste des transactions <string> txlist; // Merkle Root String Root; / ** * Constructeur * @param txlist des transactions Liste de transaction * / MerkleTrees public (list <string> txList) {this.txlist = txlist; root = ""; } / ** * Exécuter Merkle_tree et définir la racine. * / public void merkle_tree () {list <string> temptxlist = new ArrayList <string> (); for (int i = 0; i <this.txlist.size (); i ++) {temptxList.add (this.txlist.get (i)); } List <string> newtxlist = getNewTxList (TemptxList); while (newtxList.size ()! = 1) {newtxList = getNewTxList (newtxList); } this.root = newtxlist.get (0); } / ** * Liste de hachage de nœud de retour. * @param tentxlist * @return * / list private <string> getNewTxList (list <string> temptxList) {list <string> newtxlist = new ArrayList <string> (); int index = 0; while (index <TemPtxList.size ()) {// String gauche gauche = TemptxList.get (index); index ++; // String droit droit = ""; if (index! = temptxList.size ()) {droite = temptxList.get (index); } // Sha2 Hex Value String sha2hexValue = getSha2HExValue (gauche + droit); newtxlist.add (sha2hexvalue); index ++; } return newtxList; } / ** * RETOUR HEX String * @param str * @return * / public String getSha2hexValue (String str) {Byte [] cipher_byte; essayez {messagediGest md = messagediGest.getInstance ("sha-256"); md.update (str.getBytes ()); cipher_byte = md.digest (); StringBuilder sb = new StringBuilder (2 * cipher_byte.length); for (byte b: cipher_byte) {sb.append (string.format ("% 02x", b & 0xff)); } return sb.toString (); } catch (exception e) {e.printStackTrace (); } retour ""; } / ** * Get root * @return * / public String getroot () {return this.root; }}Préparation des données
Nous mettons les données de transaction dans la liste:
List <string> temptxlist = new ArrayList <string> (); temptxList.add ("a"); temptxList.add ("b"); TemptxList.add ("C"); TemptxList.add ("D"); TemptxList.Add ("E");Processus de mise en œuvre
Préparez les données de transaction pour calculer la valeur de hachage de chaque données et former progressivement les nœuds gauche et droit de l'arbre pour exécuter la boucle pour savoir qu'une seule données est laissée à la fin
Liste privée <string> getNewTxList (list <string> temptxList) {list <string> newtxlist = new ArrayList <string> (); int index = 0; while (index <TemPtxList.size ()) {// String gauche gauche = TemptxList.get (index); index ++; // String droit droit = ""; if (index! = temptxList.size ()) {droite = temptxList.get (index); } // Sha2 Hex Value String sha2hexValue = getSha2HExValue (gauche + droit); newtxlist.add (sha2hexvalue); index ++; }test
Test de package; import java.util.arraylist; import java.util.list; public class app {public static void main (string [] args) {list <string> temptxlist = new ArrayList <string> (); TemptxList.add ("A"); TemptxList.add ("B"); TemptxList.add ("C"); TemptxList.add ("D"); TemptxList.add ("E"); MerkleTrees merklerees = new MerkleTrees (TemptxList); MerkleTrees.merkle_tree (); System.out.println ("root:" + merkletrees.getroot ()); }}Résultats de l'exécution
Cet article met en œuvre un simple merkletree à partir de la forme d'un simple arbre binaire et calcule Treerooot, mais en fait, Merkletree n'est pas conservateur et l'arbre binaire peut également être des arbres multi-fourchettes.
90% de cet article est basé sur la traduction, adresse originale
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.