Сколько листьев узлы есть в дереве Merkle, который имеет общие узлы N?
Может кто-нибудь помочь мне с этим? Предположим, что дерево Merkle осуществляется так же, как это для Bitcoin сделок.
Любая помощь очень ценится
|
|
||||||
7 января 2014, 9:16:43 AM
|
# 1 |
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Взлом Биткоин адресов.
500 Биткоинов взломаны в "мозговом кошельке" с паролем "bitcoin is awesome" Адрес кошелька: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE Приватный ключ: 5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e подробнее... Всем кто хочет заработать Биткоины без вложений - рекомендую сайт http://bitcoin-zarabotat.ru |
|
|
|
Как заработать Биткоины?
Без вложений. Не майнинг.
|
7 января 2014, 9:31:23 AM
|
# 2 |
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Получил 1806 Биткоинов
Реальная история. Примеры:
6 4 5 1 2 3 {3} Всего узлы = 6 узлы Листовые = 3 7 5 6 1 2 3 4 Всего узлы = 7 узлы листьев 4 = 11 -10 6 7 8 {8} 1 2 3 4 5 {5} Всего узлы = 11 узлы Leaf = 5 15 13 14 9 10 11 12 1 2 3 4 5 6 7 8 Всего узлы = 15 узлы Листовые = 8 |
|
|
|
|
7 января 2014, 10:11:17 AM
|
# 3 |
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Если дерево завершено (. IE 1/2/4/8/16 / ... листовые узлы), то формула:
Лист Count = (N + 1) / 2 |
|
|
|
|
7 января 2014, 12:56:40 PM
|
# 4 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Я уверен, что это элегантный способ сделать это, но я потратил слишком много времени, и я могу управлять в коде (грязный). Только в случае, если кто-то на этот вызов, вот некоторые дополнительные данные:
Лист Вершины, Всего Вершины 1,1 2,3 3,6 4,7 5,11 6,12 7,14 8,15 9,20 10,21 11,23 12,24 13,27 14,28 15,30 16,31 17,37 18,38 19,40 20,41 21,44 22,45 23,47 24,48 25,52 26,53 27,55 28,56 29,59 30,60 31,62 32,63 33,70 ... 63126 64127 65135 66136 67138 |
|
|
|
|
7 января 2014, 4:57:18 PM
|
# 5 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Подойдя ближе. Это получает общее количество узлов из подсчета листьев (напротив того, что я пытаюсь сделать)
Код: INT GetNodeCount (интермедиат leafCount) { INT nodeCount = 1; для (INT I = leafCount; я > 1; я = (I + 1) >> 1) nodeCount + = я; вернуться nodeCount; } |
|
|
|
|
9 января 2014, 5:57:21 AM
|
# 6 |
|
Сообщения: 406
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Я уверен, что это элегантный способ сделать это, но я потратил слишком много времени, и я могу управлять в коде (грязный). Только в случае, если кто-то на этот вызов, вот некоторые дополнительные данные: Лист Вершины, Всего Вершины 1,1 2,3 3,6 4,7 5,11 6,12 7,14 8,15 9,20 10,21 11,23 12,24 13,27 14,28 15,30 16,31 17,37 18,38 19,40 20,41 21,44 22,45 23,47 24,48 25,52 26,53 27,55 28,56 29,59 30,60 31,62 32,63 33,70 ... 63126 64127 65135 66136 67138 Является ли это биекция? Эквивалентный есть только один способ нарисовать дерево с к общим узлам? |
|
|
|
|
27 сентября 2014, 12:03:49 PM
|
# 7 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
AKAIK это в основном 1-к-1 (он же биекция). Я решил все эти проблемы, и я буду публиковать статью в ближайшее время на Merkle деревьев, включая бинарного Merkle синтаксического дерева, используемого в Cryptonite.
|
|
|
|
|
28 сентября 2014, 10:25:17 AM
|
# 8 |
|
Сообщения: 464
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Вы ищете точное число? Если приближение хорошо, это просто половина. Мы можем доказать это следующим образом:
Merkle дерево представляет собой бинарное дерево, которое является по существу прямым турниром ликвидации. Когда два хешей объединяются, один хэш производится. Так что если вы начинаете с N листьев и держать на сочетающих узлов, каждый раз, когда вы уменьшаете число на 1. Для того, чтобы добраться до одного узла, поэтому мы имеем сделать N-1 комбинации и общее количество узлов, то примерно 2н. Это справедливо, независимо, где вы объедините узлы в дереве. Тем не менее, Мерка дерево также добавляет узлы, когда существует нечетное число узлов в заданном уровне. Вы имеете в большинстве log_2 (N) дополнительные узлы добавляют, т.е. уровень один за ваше дерево. Таким образом, число между 2N и 2N + log2 (N). По мере роста Н, этот термин журнал negligeable. Постараюсь найти точную формулу. |
|
|
|
|
28 сентября 2014, 10:54:14 AM
|
# 9 |
|
Сообщения: 2016
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Если я не ошибаюсь, чтобы найти общее число узлов N из листьев узлов М, у вас есть
N = 2M + число не-конечные 0 'в двоичном представлении M в. С единственным исключением является М является степенью 2, в этом случае N = 2М-1. Например, если М = 66, то двоичное разложение 1000010. Это 1 задней ноль и 4, не отставая 0, так что вы имеете N = 2M + 4 = 136. Для того, чтобы сделать наоборот, вы могли бы просто начать с N / 2 и посчитайте вниз (если степень 2). |
|
|
|
|
2 октября 2014, 11:23:59 AM
|
# 10 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Если я не ошибаюсь, чтобы найти общее число узлов N из листьев узлов М, у вас есть N = 2M + число не-конечные 0 'в двоичном представлении M в. С единственным исключением является М является степенью 2, в этом случае N = 2М-1. Например, если М = 66, то двоичное разложение 1000010. Это 1 задней ноль и 4, не отставая 0, так что вы имеете N = 2M + 4 = 136. Для того, чтобы сделать наоборот, вы могли бы просто начать с N / 2 и посчитайте вниз (если степень 2). Это очень здорово спасибо. Я все еще думаю об этом могли бы вы объяснить немного больше о подсчете вниз? Я имею в виду, мы знаем, N, поэтому, начиная с N / 2 мы храним не вычитанием 1 из N до чего? N = 2M + NNTZ (число не-конечные нули) М = (N - NNTZ) / 2 Просто не получить его жаль. Я работал с ним в гораздо более сложным образом, используя то, что я называю серии вальса (Ссылка WolframAlpha) Граф в основном представляет собой бинарное дерево. Если вы сквош графика сверху вниз это эффективный способ хранения узлов линейно для структуры чтения / записи. А затем, чтобы получить линейный индекс вальса любого узла: C # Код: общественности статической ULONG ToWaltzIndex (интермедиат уровень, ULONG смещение) { возврата (смещение * (1u << (Уровень + 1))) + (1u << 1-й уровень; } И, чтобы получить количество листьев: Код: /// <резюме> /// Мы знаем это: /// * Все положительные целые числа являются действительным leafCounts /// * Только определенные значения являются допустимым nodeCounts. /// * Существует 1: отображение 1 между leafCount: nodeCount /// * Когда перечислено в порядке, различие между допустимыми значениями nodeCount следует ряду вальса /// * Когда дерево завершено (так называемый symetric), то: leafCount = (nodeCount + 1) / 2 /// Следовательно: /// * Разница между любым nodeCount и nodeCount полного дерева с одной и той же высотой /// должна быть сумма K элементов серии вальса. /// * nodeDiff = сумма (вальс [0], ..., вальс [K-1]) /// * Х = GetWaltzSumCount (nodeDiff) /// * leafCount = maxLeafCount - X /// общественности статической ULONG GetLeafCount (ULONG nodeCount) { // максимально допустимое кол-лист на текущей высоте ULONG maxLeafCount = Pow2Prev (nodeCount); // максимально допустимое общее количество узлов на текущей высоте ULONG maxNodeCount = (maxLeafCount * 2) - 1; // Получить разницу между текущим узлом подсчетом и подсчетом максимального узла ULONG nodeDiff = maxNodeCount - nodeCount; // если numNodes равно maxNodes тогда leafCount должна равняться maxLeafCount если (nodeDiff == 0) вернуться maxLeafCount; // Вычесть количество суммируемых вальсовых элементов (шагов), которые необходимы, чтобы равняться nodeDiff, от maxLeafCount вернуться maxLeafCount - GetWaltzSumCount (nodeDiff); } И для полноты картины. поддерживающие функции (GetWaltzSumCount): Код: /// Возвращает число элементов, которые должны быть добавлены для того, чтобы достичь целевого значения. /// /// <Имя параметра ="цель">Целевой результат для эмуляции /// <возвращается>Количество последовательных элементов, которые должны быть добавлены вместе до достижения цели общественности статической ULONG GetWaltzSumCount (ULONG мишень) { ULONG Счетчик = 0; ULONG сумма = 0; в то время как (сумма < мишень) сумма + = GetWaltzValue (++ счетчик) + 1; если (сумма > мишень) counter--; возврат счетчика; } /// <резюме> /// Значение вальса это количество раз число можно сократить вдвое, не оставляя остаток. Эти /// значение (серия) полезно для навигации и хранения бинарных древовидных структур. /// /// <Имя параметра ="номер">Положительная INT больше- общественности статической UINT GetWaltzValue (ULONG номер) { // Охватывает все неподписанные значения 64bit константный UINT maxDivisions = 64; ULONG Num = число; для (UINT = 0; я <= maxDivisions; я ++) { если ((NUM% 2) == 1) Взамен я; Num = Num / 2; } певд IndexOutOfRangeException ("Не удалось найти значение Waltz для номера: " + Номер); } |
|
|
|
|
2 октября 2014, 12:56:29 PM
|
# 11 |
|
Сообщения: 2016
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
То, что я имел в виду с подсчетом вниз:
Скажем, N = 135. Вы начинаете с 135/2 = 67. Вы попробуйте сначала М = 67, используя метод, который вы получаете N = 138, который является неправильным. Тогда вы пытаетесь M = 66, что дает N = 136. Тогда вы пытаетесь M = 65, это дает N = 135, так что правильный результат. Чтобы уточнить, я не уверен, что мой метод работает, если вы размещаете больше значения, используя реализацию, я могу проверить мой. |
|
|
|
|
2 октября 2014, 1:20:44 PM
|
# 12 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Но M неизвестно, так как вы можете сказать, что N является правильным?
Я изо всех сил думать сегодня Edit: О, я вижу. Я получаю сейчас Это большое упрощение. Я проверю, который быстрее, так как я не декрементируете столько раз с моим методом. Ваш является бесконечно более объяснимым, хотя (скорее всего, быстрее тоже). Когда (если) я заканчиваю свою статью я ссылочку вам |
|
|
|
|
2 октября 2014, 1:31:37 PM
|
# 13 |
|
Сообщения: 2016
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Но M неизвестно, так как вы можете сказать, что N является правильным? Спасибо Но нам еще нужно проверить метод работы NNTZ.Я изо всех сил думать сегодня Edit: О, я вижу. Я получаю сейчас Это большое упрощение. Я проверю, который быстрее, так как я не декрементируете столько раз с моим методом. Ваш является бесконечно более объяснимым, хотя. Когда (если) я заканчиваю свою статью я ссылочку вам |
|
|
|
|
2 октября 2014, 1:45:11 PM
|
# 14 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Это довольно прямо вперед, чтобы вычислить N из M так (Bitcoin делает это), так что не должно быть проблемой.
Метод Биткойн (приблизительно): Код: INT GetNodeCount (интермедиат leafCount) { INT nodeCount = 1; для (INT I = leafCount; я > 1; я = (I + 1) >> 1) nodeCount + = я; вернуться nodeCount; } |
|
|
|
|
2 октября 2014, 2:19:02 PM
|
# 15 |
|
Сообщения: 464
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Если количество листьев является степенью 2, то общее число узлов равно 2n - 1.
Если это не так, есть дополнительные узлы, введенные для заполнения отверстий. Пусть т число этих дополнительных узлов. Общее число узлов становится 2n -1 + т. При п записываются в двоичной форме, деление на два эквивалентно битовый сдвиг вправо. Пока последняя цифра является 0, число четное. Поэтому все нули являются уровни, которые даже и не ввести новые узлы. Когда мы достигаем 1, добавляется дополнительный узел. Она осуществляется на следующий уровень. Пример: 101. Без дополнительных узлов, мы имеем 1 в корне. 10 на втором уровне и 101 на третьем. но дополнительный узел сделал 3-го уровня 110. И второй уровень теперь 11. Это опять странно, так что дополнительный узел еще раз добавил. И это становится 100. Мы можем видеть, что процесс добавления узлов продолжается для каждого 0, которое появляется после того, как первый 1. Поскольку перенос сделал число нечетным. Когда мы достигаем 1. Перенос оказывается, что в 0 и нести 1 дальше. Поэтому 1 не оказывает никакого влияния количества дополнительных узлов. В заключение отметим, что количество дополнительных узлов 1 + число нулей, которые находятся слева от первого 1, что является не самым значащим битом. Конечный результат 2n + число нулей, не являющихся хвостовых. Кредиты идут к Меням для формулы. |
|
|
|
|
2 октября 2014, 2:39:48 PM
|
# 16 |
|
Сообщений: 71
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Если количество листьев является степенью 2, то общее число узлов равно 2n - 1. Если это не так, есть дополнительные узлы, введенные для заполнения отверстий. Пусть т число этих дополнительных узлов. Общее число узлов становится 2n -1 + т. При п записываются в двоичной форме, деление на два эквивалентно битовый сдвиг вправо. Пока последняя цифра является 0, число четное. Поэтому все нули являются уровни, которые даже и не ввести новые узлы. Когда мы достигаем 1, добавляется дополнительный узел. Она осуществляется на следующий уровень. Пример: 101. Без дополнительных узлов, мы имеем 1 в корне. 10 на втором уровне и 101 на третьем. но дополнительный узел сделал 3-го уровня 110. И второй уровень теперь 11. Это опять странно, так что дополнительный узел еще раз добавил. И это становится 100. Мы можем видеть, что процесс добавления узлов продолжается для каждого 0, которое появляется после того, как первый 1. Поскольку перенос сделал число нечетным. Когда мы достигаем 1. Перенос оказывается, что в 0 и нести 1 дальше. Поэтому 1 не оказывает никакого влияния количества дополнительных узлов. В заключение отметим, что количество дополнительных узлов 1 + число нулей, которые находятся слева от первого 1, что является не самым значащим битом. Конечный результат 2n + число нулей, не являющихся хвостовых. Кредиты идут к Меням для формулы. Спасибо, что является отличным объяснением того, как она работает. Если вы не возражаете, я хотел бы использовать его (или, возможно, отредактированную версию) в своей статье с кредитом вам. Статья о бинарных Merkle деревьев в целом, включая способ для хранения / извлечения их в порядке вставки, а также сбалансированный дизайн Merkle Trie (кредит CATIA / Cryptonite). Он будет опубликован открыто (если я надеюсь, обойти его окончания). |
|
|
|
|
2 октября 2014, 2:54:28 PM
|
# 17 |
|
Сообщения: 464
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Конечно, без проблем. благодаря
|
|
|
|
|
3 октября 2014, 4:09:27 PM
|
# 18 |
|
Сообщения: 111
цитировать ответ |
Re: Merkle Деревья - Сколько листьев узлов в дереве с общими узлами N?
Примеры: 6 4 5 1 2 3 {3} Всего узлы = 6 узлы Листовые = 3 7 5 6 1 2 3 4 Всего узлы = 7 узлы листьев 4 = 11 -10 6 7 8 {8} 1 2 3 4 5 {5} Всего узлы = 11 узлы Leaf = 5 15 13 14 9 10 11 12 1 2 3 4 5 6 7 8 Всего узлы = 15 узлы Листовые = 8 Будет ли возможность оптимизировать таким образом, что эти деревья построены? Это, кажется, не совсем правильно хэшировании конечных узлов листа с собой, когда вы сталкиваетесь с нечетными номерами. Как насчет этого: Для каждого 1 в двоичном представлении числа элементов в наборе (количество листовых узлов) вы построить полный Merkle дерево. (Если имеются нечетное число, то конечное дерево будет просто один элемент). Тогда хэш корень наименьшего дерева с корнем второй по размеру. Hash результат этого с корнем третьей наименьшему и т.д., пока не будет достигнут корень самого большого дерева, и это ваш блок хэш. В качестве примера, чтобы представить набор 5 конечных узлов, представленных в двоичной системе на 101 я бы построить два дерева (на самом деле конечный я не дерево, но только один элемент) Так это будет выглядеть следующим образом. H1234.5 H12.34 H1.2 H3.4 1 2 3 4 5 Только 4 хешей по сравнению с 6 выше. Таким образом, для числа 7 (111) мы строим три дерева (один единственный элемент) H1234.567 H12.34 H56.7 H1.2 H3.4 H5.6 1 2 3 4 5 6 7 Один хэш меньше. Я на самом деле не исследовали эту идею, но на первый взгляд, кажется более эффективным в ряде хэшей, а в некоторых случаях более эффективным для проверки элементов. Однако это также кажется слишком простым, так что не так с ним? |
|
|
|
Как заработать Биткоины?
Bitcoin Wallet * Portefeuille Bitcoin * Monedero Bitcoin * Carteira Bitcoin * Portafoglio Bitcoin * Bitcoin Cüzdan * 比特币钱包
bitcoin-zarabotat.ru
Почта для связи: bitcoin-zarabotat.ru@yandex.ru
3HmAQ9FkRFk6HZGuwExYxL62y7C1B9MwPW
Bitcoin Wallet * Portefeuille Bitcoin * Monedero Bitcoin * Carteira Bitcoin * Portafoglio Bitcoin * Bitcoin Cüzdan * 比特币钱包
bitcoin-zarabotat.ru
Почта для связи: bitcoin-zarabotat.ru@yandex.ru
3HmAQ9FkRFk6HZGuwExYxL62y7C1B9MwPW
Регистрация для новых участников, на данный момент не доступна. Просим извинения за временные неудобства.