Я пытаюсь реализовать доказательство согласованности дерева Merkle, но я застрял в понимании алгоритма
Я пытаюсь реализовать алгоритм согласованности дерева Merkle с этой документа:
Тем не менее, я как бы застрял на проверке согласованности, потому что всегда выполняю бесконечный цикл при выполнении части ConsProofSub.
Пример:
Новое дерево имеет 8старое дерево имеет 7 листья.
Проходя через предыдущую функцию, я получаю m = 7, листья моего нового дерева как вектор E а также true как b,
Функция проходит через рекурсивный поток кода, пока мы не достигнем этой ситуации:
E теперь имеет 2 элементы, так n = 2,
m = 1, из-за предыдущих вычитаний в рекурсивном вызове для m < k, так же как b = false,
Мы не падаем в m = n && b = false если как m а также n не равны
k в настоящее время рассчитывается как, опять же, 2потому что потолок корректирует получающийся 1/2 от log2(n)/2 в 1,
Мы падаем в m <= k случай, и еще раз, мы рекурсивно вызываем функцию с точно такими же параметрами. Теперь мы находимся в бесконечном цикле.
Тем не менее, я не могу понять, что я делаю неправильно. Я чувствую себя как потолок в k расчет это проблема. Это в основном делает невозможным выйти из цикла, потому что k казалось бы, всегда будет выше, чем m после нескольких итераций.
Любой совет / намек на мою ошибку здесь?
РЕДАКТИРОВАТЬ: Интересно то, что алгоритм, кажется, отлично работает, когда n нечетное число. Кажется, что он не работает даже для четных чисел. Я только что попробовал это с новым деревом из 7 листьев, и оно работает как шарм, предоставляя правильные узлы, необходимые для подтверждения согласованности.
Тем не менее, я все еще не могу понять, какие изменения нужно будет сделать, чтобы он работал с четными числами.
1 ответ
Кажется, в книге есть ошибка. Случай, когда m = n а также b = true должен быть обработан отдельно. Немного более подробное описание алгоритма можно найти в RFC 6962.
Вот как вы можете это исправить:
