Descripción general
Merkletree es ampliamente utilizado en la tecnología Bitcoin. Este artículo tiene como objetivo implementar un Merkletree simple a través del código y calcular el Treeroot of Merkle Tree.
Merkle Tree es una estructura de datos que verifica cualquier tipo de datos almacenados, procesados y transmitidos entre computadoras.
Actualmente, el objetivo principal del árbol de Merkle es garantizar que los bloques de datos recibidos de la red pares no estén dañados ni cambiados, y verificar que otras redes de pares no mienten para enviar bloques de datos falsos.
Ejemplo de la aplicación Merkle Tree
Bitcoin
Gita
Dinamo de Mazon
Gassandra
Aplicaciones en Bitcoin
Cada bloque en Bitcoin contiene una firma de recolección de todas las transacciones. Esta firma se implementa utilizando Merkle Tree. El árbol de Merkle se usa para Bitcoin para resumir todas las transacciones en el bloque, generar una huella digital general de todo el conjunto de transacciones y proporcionar un proceso muy efectivo para verificar si la transacción está incluida en el bloque.
Un uso muy importante de los árboles de Merkle es verificar si el bloque contiene una transacción especificada. Los árboles de Merkle están construidos por pares de nodos de hash recursivamente hasta que solo hay un hash.
Implementación del código de árbol de Merkle
El nodo del árbol hash se llama raíz de Merkle. El árbol de Merkle puede verificar si algún elemento de datos está incluido en el árbol utilizando la complejidad de tiempo de log2 (n):
Prueba de paquete; import java.security.messageGest; import java.util.arrayList; import java.util.list; public class Merkletrees {// Lista de transacciones Lista <String> txList; // raíz de cadena de raíz merkle; / ** * constructor * @param txList Lista de transacciones de la lista de transacciones */ public Merkletres (list <String> txList) {this.txList = txList; root = ""; } /*** Ejecutar merkle_tree y establecer root. */ 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); } /*** Return Node Hash List. * @param TemptXList * @return */ private list <String> getNewtxList (list <String> TemptXList) {list <String> newtxList = new ArrayList <String> (); int index = 0; while (index <temptXlist.size ()) {// Left String Left = TemptXList.get (index); índice ++; // Cadena derecha derecha = ""; if (index! = TemptXList.size ()) {right = temptXlist.get (index); } // SHA2 Hex Value String Sha2HexValue = getSha2HexValue (izquierda + derecha); newtxlist.add (sha2HexValue); índice ++; } return newtxlist; } / ** * return hex string * @param str * @return * / public string getSha2HexValue (String str) {byte [] cipher_byte; Pruebe {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 (); } devolver ""; } / ** * Get root * @return * / public string getroot () {return this.root; }}Preparación de datos
Ponemos los datos de la transacción en la lista:
List <String> TemptXList = New ArrayList <String> (); TemptXList.Add ("A"); TemptXList.add ("B"); TemptXList.add ("C"); TemptXlist.add ("D"); TemptXlist.add ("e");Proceso de implementación
Prepare los datos de la transacción para calcular el valor hash de cada datos, y forme gradualmente los nodos izquierdo y derecho del árbol para ejecutar el bucle para saber que solo quedan un datos al final
Lista privada <String> getNewtXList (list <string> temptXlist) {list <string> newtxList = new ArrayList <String> (); int index = 0; while (index <temptXlist.size ()) {// Left String Left = TemptXList.get (index); índice ++; // Cadena derecha derecha = ""; if (index! = TemptXList.size ()) {right = temptXlist.get (index); } // SHA2 Hex Value String Sha2HexValue = getSha2HexValue (izquierda + derecha); newtxlist.add (sha2HexValue); índice ++; }prueba
prueba de paquete; 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 merkletres = new Merkletrees (TemptXlist); merkletres.merkle_tree (); System.out.println ("root:" + merkletres.getroot ()); }}Resultados de la ejecución
Este artículo implementa un simple Merkletree a partir de la forma de un árbol binario simple y calcula Treeroot, pero de hecho, Merkletree no es conservador y los árboles binarios también pueden ser árboles multifork.
El 90% de este artículo se basa en la traducción, dirección original
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.