Хэш-календарь
Хэш -календарь — это структура данных, которая используется для измерения течения времени путем добавления хеш-значений в базу данных, доступную только для добавления, с одним хеш-значением за прошедшую секунду. Его можно рассматривать как особый вид дерева Меркла или хеш-дерева , обладающего свойством, что в любой момент времени дерево содержит листовой узел каждую секунду с 01.01.1970 00:00:00 UTC.
Листья нумеруются слева направо, начиная с нуля, а новые листья всегда добавляются справа. Периодически публикуя корень хеш-дерева, можно использовать хэш-календарь в качестве основы схемы цифровой временной метки на основе хеш-связывания .
История [ править ]
Конструкция хеш-календаря была изобретена эстонскими криптографами Ахто Булдасом и Мартом Саарепера на основе их исследований свойств безопасности криптографических хеш-функций и цифровых временных меток на основе хеш-связывания. [1] Целью их разработки было устранить необходимость в доверенной третьей стороне, т. е. чтобы время метки времени можно было проверить независимо от эмитента метки времени. [2]
Построение хэш-календаря [ править ]
Существуют различные алгоритмы, которые можно использовать для построения хэш-календаря и извлечения соответствующей хэш-цепочки в секунду. Проще всего представить, что календарь строится в два этапа. На первом этапе листья собираются в полные бинарные деревья, начиная слева и делая каждое дерево как можно большим.
На втором этапе несколько несвязанных деревьев превращаются в одно дерево путем слияния корней исходных деревьев, но на этот раз начиная справа и добавляя по мере необходимости новые родительские узлы (красные узлы).
Затем хэш-цепочки можно извлечь, как и из любого хеш-дерева. Поскольку хеш-календарь построен детерминированным образом, форму дерева на любой момент можно восстановить, зная только количество конечных узлов в дереве в этот момент, что на одну больше, чем количество секунд с 1970-01-го года. 01 00:00:00 UTC в этот момент. Следовательно, зная время создания календарного дерева и извлеченную из него хеш-цепочку, можно вычислить значение времени, соответствующее каждому конечному узлу.
Распределенный хеш-календарь [ править ]
Распределенный хеш-календарь — это распределенная сеть узлов хэш-календаря. Чтобы обеспечить службу высокой доступности, можно иметь несколько календарей в разных физических местах, каждый из которых взаимодействует друг с другом, чтобы гарантировать, что каждый календарь содержит идентичные значения хеш-функции. Обеспечение согласованности календарей — это форма византийской отказоустойчивости.
Справа показан кластер календаря из 5 узлов, где каждый узел взаимодействует с каждым другим узлом в кластере и нет единой точки отказа. Хотя каждый узел имеет часы, они используются не для установки времени напрямую, а в качестве метронома, чтобы гарантировать, что узлы «бьются» одновременно.
Приложения [ править ]
Кластер хэш-календаря из пяти узлов является компонентом инфраструктуры бесключевой подписи (KSI), где каждый лист хеш-календаря представляет собой совокупное хэш-значение глобально распределенного хеш-дерева.
См. также [ править ]
- Криптографические хэш-функции
- Связанная временная метка
- Хэш-список
- Хэш-таблица
- Дерево Меркла
- Доказуемо безопасная криптографическая хэш-функция
Ссылки [ править ]
- ^ Система и способ создания цифрового сертификата, патент 8 312 528.
- ^ «Обучающая серия по хэш-функциям | Guardtime» . Архивировано из оригинала 16 февраля 2013 г. Проверено 7 января 2013 г.
Внешние ссылки [ править ]
- Патент на дерево Меркла 4,309,569 – объясняет как структуру хеш-дерева, так и его использование для обработки множества одноразовых подписей.
- Эффективное использование деревьев Меркла — объяснение первоначальной цели деревьев Меркла в лабораториях RSA : обработка множества одноразовых подписей Лэмпорта.
- https://web.archive.org/web/20110625054822/http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html
