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

«Хеш-дерево» — это концепция, аналогичная хэш-дереву Меркла/тигровому дереву, используемому Amazon Glacier для проверки целостности данных в подмножествах заданного потока данных.

Чтобы получать хэши дерева от Amazon Glacier при извлечении данных, указанный диапазон байтов должен быть «выровнен по хэшу дерева».

Концепция "выровненного хэша дерева" описана здесь.< /а>

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

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

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

  • Если P — нечетное число, существует только один возможный диапазон, выровненный по хэшу дерева, то есть [P, P + 1 МБ).
  • If P is an even number and k is the maximum number, where P can be written as 2k * X, then there are at most k tree-hash aligned ranges that start with P. X is an integer greater than 0. The tree-hash aligned ranges fall in the following categories:
    • For each i, where (0 <= i <= k) and where P + 2i < N, then [P, Q + 2i) is a tree-hash aligned range.
    • P = 0 — это особый случай, когда A = 2[lgN]*0

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

Тестовые примеры:

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

algorithm amazon-glacier data-structures binary-tree
person seb    schedule 04.06.2016    source источник
comment
Выравнивание по мегабайтам требуется. P и Q кратны одному МБ (таким образом, P – целочисленное смещение от начала файла в МиБ). Невозможно быть выровненным по дереву, а не по мегабайтам; набор всех возможных блоков, выровненных по древовидному хэшу, является подмножеством всех возможных блоков, выровненных по мегабайтам, с очевидным исключением, которое позволяет блоку быть выровненным по мегабайтам с конечной точкой за фактическим концом файла и при этом оставаться древовидным. выравнен по хешу.   -  person Michael - sqlbot    schedule 04.06.2016
comment
@ Майкл-sqlbot Ты прав. Я отредактировал вопрос.   -  person seb    schedule 04.06.2016

Ответы (1)


arrow_upward
1
arrow_downward

Вот базовая реализация функции 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 Alignment с учетом здесь, но не инструкции по его идентификации.

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

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

    [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. #P7# #P8#
    #P9#
    #P10# #P11#
    #P12#
    #P13#
person Patrick Trentin    schedule 10.06.2016
comment
Извините за запутанные тестовые примеры. [4,5) в основном эквивалентно [(1024*1024*4, (1024*1024*5)-1]. Но я думаю, что вы в значительной степени прибили его. - person seb; 10.06.2016