Хеш календар

Хеш календар јесте структура података која се користи за мерење протоком времена додавањем хеш вредности у базу података на коју се само додају подаци са једном хеш вредношћу по протеклој секунди. Може се посматрати као специјална врста Мерклијевог или хеш стабла, са особином да у сваком датом моменту, стабло садржи лист за сваку секунду од 01.01.1970. 00:00:00 UTC.

Хеш стабло са 8 чворова и хеш календар после 7 секунди

Хеш стабло са 8 чворова и хеш календар после 7 секунди.

Хеш календар после 31 секунду

Хеш календар после 31 секунду састоји се од 5 развојених хеш стабала.

Чворови су нумерисани слева надесно почевши од нуле и сваки нови лист се увек додаје здесна. Периодичним публиковањем корена хеш стабла могуће је користити хеш календар као основу за дигиталну временску схему засновану на хеш-линковању.

Историјат

Конструктор хеш календара је осмишљен од стране естонских криптографичара Ахто Булдаса и Март Саарепера и заснован је на њиховом истраживању на сигурносним својствима криптографских функција за сажимање и дигиталној временској схеми засновној на хеш-линковању. Њихов дизајн циљ је био уклањање зависности од трећом страном односно да би време временске схеме требало да буде верификовано независно од издаваоца временске схеме.

Конструкција хеш календара

Постоје различити алгоритми који могу да се користе за изградњу хеш календара и извлачења релевантног хеш ланца по секунди. Најлакше је замислити изградњу календара у две фазе. У првој фази, листови се сакупљају у комплетно бинарно стабло, почевши слева, правивши свако стабло што је веће могуће.

Редак хеш календар са 11₁₀ = 1011₂ листова

У другој фази, више неповезаних стабала се спајањем корена иницијалних стабала претварају се у једно стабло, али овог пута почевши здесна, додајући нови родитељски чвор уколико је то потребно (црвени чворови).

Компактан хеш календар са 11₁₀ = 1011₂ листова.

Хеш ланац може бити извучен из било ког хеш стабла. С обзиром да је хеш календар изграђен на детерминистички начин, облик стабла се сваког момента може реконструисати знајући само број листова у стаблу у том моменту, што је један више него број секунди почевши од 01.01.1970. 00:00:00 UTC до тог момента. Дакле, задајући време када је стабло календара креирано, као и хеш ланца извученог из нјега, временска вредност која одговара сваком листу може бити израчуната.

Дистрибуирани хеш календар

Дистрибуирани хеш календар је дистрибуирана мрежа чворова хеш календара. Да би се осигурала висока доступност сервира, могуће је имати више календара на различитим физичким локацијама који сви комуницирају међусобно да би обезбедили да сваки календар садржи идентичне хеш вредности. Обезбеђивање да календари остану у складу је форма Бизантиновог прага толеранције.

Испод је приказана група календара од 5 чворова где сваки чвор комуницира са сваким другим чвором у групи што доводи до непостојања грешке. Иако сваки чвор има часовник, часовник се не користи за подешавање времена директно, већ као метроном да би обезбедило "куцање" чворова у исто време.

Апликације

Група календара од пет чворова је компонента Keyless Signature Infrastructure (KSI), где сваки лист у хеш календару представља агрегатну хеш вредност глобално дистрибуираног хеш стабла.

Види још

• Криптографске хеш функције
• Дигитална временска схема заснована на хеш-линковању
• Хеш листа
• Хеш табела
• Меркли стабло

Спољашње везе

• Merkle tree patent 4,309,569 – Објашњава структуру хеш стабла као и његово коришћење приликом руковођења вишеструких једновременских потписа.
• Efficient Use of Merkle Trees – RSA лабораторије објашњава оригиналну намену Меркли стабала: руковођење вишеструких Лампорт једновременских потписа.
• https://web.archive.org/web/20110625054822/http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html