Дерево Хеш: как проверить, если диапазон выровнен по дереву?

Question

«Tree Hash» - это концепция, подобная дереву хребта Merkle Tree/Tiger, используемому ледником Амазонки, для проверки целостности данных подмножеств заданного потока данных.

Для получения хешей-хешей из ледника Амазонки при получении данных указанный диапазон байтов должен быть «выровнен по дереву».

The concept of "tree hash aligned" is described here.

Цитируя документации разработчика:

в диапазоне [A, B] является дерево-хэш выровнен по отношению к архиву тогда и только тогда, когда новое дерево хэш построен на [A, B], корень хэша дерева этого диапазона эквивалентен узлу в хеше дерева всего архива. [...]

Рассмотрите [P, Q), поскольку запрос диапазона для архива из N мегабайт (МБ) и P и Q кратно одному мегабайту. Обратите внимание, что фактический инклюзивный диапазон - [P MB, Q MB - 1 байт], но для простоты мы показываем его как [P, Q). С учетом этих соображений,

• Если P - нечетное число, существует только один возможный диапазон с вырезом по дереву, т.е. [P, P + 1 MB).
• Если P - четное число, а k - максимальное число, где P может быть записано как 2k * X, то не более k выровненных по дереву диапазонов, начинающихся с P. X, является целым числом больше 0. это дерево-хэш выравненные диапазоны относятся к следующим категориям:
  • Для каждого я, где (0 < = я < = к) и где Р + 2i < Н, то [Р, Q + 2i) является деревом -высокий диапазон.
  • P = 0 является частным случаем, где А = 2 [ЛГН] * 0

Теперь вопрос: Как я могу проверить программным способом, если данный диапазон [StartByte-величина, endByte] является дерево -hash выровнен? Язык программирования не имеет значения.

Тестовые:

[0,0) => true 
[0,1) => true 
[0,2) => false 
[0,3) => true 
[1,2) => false 
[4,5) => true 

Answer 1

Здесь основная реализация is_treehash_aligned функции в Python:

import math 

def max_k(x): 
    return 1 + max_k(x/2) if x % 2 == 0 else 0 

def is_treehash_aligned(P, Q): 

    if (Q < P): 
     return False 
    elif (P % 2 == 1): 
     return Q == P 
    else: 
     ilen = Q - P + 1 # size(interval) 
     if not (((ilen & (ilen - 1)) == 0) and ilen != 0): 
      return False # size(interval) ~ not power of two 
     if P == 0: 
      return True 
     else: 
      k = max_k(P) 
      i = int(math.log(ilen, 2)) 
      return i <= k 

if (__name__ == "__main__"): 
    ranges = [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), \ 
       (4, 5), (6, 7), (2, 4), (6, 8), (5, 6), \ 
       (4, 4), (1, 1), (4194304, 5242879), \ 
       (4194304, 5242880), (4194304, 5242881)] 

    for r in ranges: 
     ret = is_treehash_aligned(*r) 
     print("[" + str(r[0]) + ", " + str(r[1]) + ") => " + str(ret)) 

Выход:

[0, 0) => True 
[0, 1) => True 
[0, 2) => False 
[0, 3) => True 
[1, 2) => False 
[4, 5) => True 
[6, 7) => True 
[2, 4) => False 
[6, 8) => False 
[5, 6) => False 
[4, 4) => True 
[1, 1) => True 
[4194304, 5242879) => True 
[4194304, 5242880) => False 
[4194304, 5242881) => False 

Обратите внимание, что:

• Я принял ваших обозначения для интервалов, а не выданные инструкции. Как следствие, можно предположить, что каждый интервал равен Мегабайт выровнен.
• Результат для тестового шкафа [4194304, 5242880) отличается от того, что вы задали в исходном вопросе, хотя я дважды проверил его, и я уверен, что он правильный.
• Если N известен, это не так в ваших тестовых случаях, тогда, когда P == 0 также необходимо принять любой диапазон s.t. Q >= floor(N), и не только те, размер которых равен мощность двух. Аналогичный аргумент можно было бы сделать для поддеревьев, для которых нет ничего на справа. Оба эти случая будут соответствовать определению из Tree-Hash Alignmenthere, но не для определения его.

---

Примечания: как вопрос, и description проблемы, как представляется, хотя и сбивает с толку.

1. тестовых примеров приведен с обозначением [A, B), где A является индексом стартового блока и B является индексом блока конечной (включено), если предположить, что весь архив состоит массив - indexed от 0-- от N размер блоков 1 MB каждый (кроме, возможно, последний). Например .:

   [0,0) => true 
   [0,1) => true 
   [0,2) => false 
   [0,3) => true 
   [1,2) => false 
   [4,5) => true 
   

   Однако инструкции предположить, что диапазоны даны с обозначениями [P MB, Q MB – 1 byte].

2. В инструкции являются в заблуждение.

   Например, здесь он говорит:

   Если P является четным числом, а к максимальное число, где P может быть записана в виде 2k * X, то там не более чем к деревьям хэш выровнен диапазоны, которые начинаются с P

   появляется сила символ быть опущены, возможно, из-за неправильного HTML кода, так как предложение должно быть «крупнейший k ул P = (2^k)*X».

   Другой пример:

   Для каждого я, где (0 < = я < = к) и где Р + 2i < Н, то [Р, Q + 2i) представляет собой дерево-хэш выравнивается ассортимент.

   Предположим, например, что Q = P + 1, i > 0 и k > 0.Затем интервал [P, Q + 2^i) имеет размер = Q + 2^i - P = P + 1 + 2^i - P = 2^i + 1 > 1. Однако по конструкции не существует такого tree-hash выровненный диапазон с нечетным размером больше одного. Предложение должно быть: «[...], затем [P, P + 2^i) - это выровненный по дереву диапазон«.