Обзор
Merkletree широко используется в технологии биткойнов. Эта статья направлена на то, чтобы реализовать простой Merkletree через код и вычислять Treeroot of Merkle Tree.
Merkle Tree - это структура данных, которая проверяет любой тип данных, хранящихся, обработанных и передаваемых между компьютерами.
В настоящее время основная цель дерева Меркл состоит в том, чтобы гарантировать, что блоки данных, полученные из сети сверстников, не повреждены и не изменяются, и проверить, что другие сетки сверстников не лгут, чтобы отправлять фальшивые блоки данных.
Пример приложения Merkle Tree
Биткойн
Гита
Мазон Динамо
Гассандра
Приложения в биткойнах
Каждый блок в биткойнах содержит подпись сбора всех транзакций. Эта подпись реализована с использованием Merkle Tree. Дерево Меркл используется для биткойна, чтобы суммировать все транзакции в блоке, генерировать общий цифровой отпечаток всего набора транзакций и обеспечить очень эффективный процесс, чтобы проверить, включена ли транзакция в блок.
Очень важное использование деревьев Меркл состоит в том, чтобы проверить, содержит ли блок указанную транзакцию. Деревья Меркл построены путем рекурсивно хэширующих пар узлов, пока не появится только один хэш.
Реализация кода дерева Меркл
Узел хеш -дерева называется корнем Меркл. Дерево Меркл может проверить, включен ли какой -либо элемент данных в дерево, используя временную сложность log2 (n):
Пакет Test; Import java.security.messagedigest; import java.util.arraylist; import java.util.list; public class merkletrees {// Список транзакций <string> txlist; // Merkle Root String Root; / ** * Constructor * @param txlist Список транзакций транзакций */ public merkletrees (list <string> txlist) {this.txlist = txlist; root = ""; } /*** Выполнить merkle_tree и установить 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 (TeplxList); while (newtxlist.size ()! = 1) {newtxlist = getNewtxlist (newtxlist); } this.root = newtxlist.get (0); } /*** Список хэша возврата узла. * @param tepsptxlist * @return */ private list <string> getNewtxlist (list <string> tepplexlist) {list <string> newtxlist = new arraylist <string> (); int index = 0; while (index <temptxlist.size ()) {// Left String Left = TemptXlist.get (index); index ++; // правая строка right = ""; if (index! = temptxlist.size ()) {right = temptxlist.get (index); } // sha2 jex value string sha2hexvalue = getsha2Hexvalue (слева + справа); newtxlist.add (sha2hexvalue); index ++; } вернуть newtxlist; } / ** * return hex string * @param str * @return * / public String getsha2Hexvalue (String str) {byte [] cipher_byte; try {messagegest 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)); } вернуть sb.toString (); } catch (Exception e) {e.printstackTrace (); } возвращаться ""; } / ** * Получить root * @return * / public String getRoot () {return this.root; }}Подготовка данных
Мы помещаем данные транзакции в список:
List <string> temptxlist = new ArrayList <string> (); TemptXlist.Add ("a"); TemptXlist.Add ("b"); TemptXlist.Add ("c"); TemptxList.Add ("d"); TemptXlist.Add ("e");Процесс реализации
Подготовьте данные о транзакциях для расчета значения хэша каждой данные и постепенно сформировать левые и правые узлы дерева, чтобы выполнить цикл, чтобы узнать, что в конце остается только один данные.
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); index ++; // правая строка right = ""; if (index! = temptxlist.size ()) {right = temptxlist.get (index); } // sha2 jex value string sha2hexvalue = getsha2Hexvalue (слева + справа); newtxlist.add (sha2hexvalue); index ++; }тест
Пакет Test; 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 merkletrees = new Merkletrees (Temptxlist); merkletrees.merkle_tree (); System.out.println ("root:" + merkletrees.getroot ()); }}Результаты исполнения
Эта статья реализует простую Merkletree из формы простого бинарного дерева и рассчитывает TreeRoot, но на самом деле Merkletree не является консервативным, а бинарное дерево также может быть многодушными деревьями.
90% этой статьи основана на переводе, оригинальный адрес
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.