해시 캘린더

Hash calendar

해시 캘린더는 경과초당 1개의 해시 값을 갖는 추가 전용 데이터베이스에 해시 값을 추가하여 시간의 흐름을 측정하는 데 사용되는 데이터 구조다.그것은 특별한 종류의 머클이나 해시 트리로 생각할 수 있는데, 그 속성은 1970-01-01-01 00:00 UTC 이후 1초마다 트리에 리프 노드가 포함되어 있다는 것이다.

8 리프 노드와 7초 후 해시 캘린더가 있는 해시 트리
31초 후 일정 해시

잎은 0부터 시작해서 왼쪽에서 오른쪽으로 번호가 매겨지고 항상 오른쪽에 새로운 잎이 추가된다.해시 트리의 루트를 정기적으로 게시함으로써 해시 링크 기반 디지털 타임스탬프 구성의 기초로 해시 캘린더를 사용할 수 있다.

역사

해시 캘린더 구성은 에스토니아 암호학자 아흐토 불다스와 마트 사레페라가 암호 해시함수의 보안 속성과 해시링크 기반 디지털 타임스탬프에 관한 연구를 바탕으로 발명했다.[1]이들의 설계 목표는 신뢰할 수 있는 제3자의 필요성(즉, 타임스탬프의 시간은 타임스탬프의 발행자와 독립적으로 검증 가능해야 함)을 제거하는 것이었다.[2]

해시 캘린더 구성

해시 캘린더를 구축하고 초당 관련 해시 체인을 추출하는 데 사용할 수 있는 알고리즘은 서로 다르다.가장 쉬운 것은 달력이 두 단계로 만들어지는 것을 상상하는 것이다.1단계에서는 잎을 완전한 이진수로 모아 왼쪽부터 시작하여 각 나무를 최대한 크게 만든다.

1110 = 10112 리프가 있는 희소 해시 캘린더

2단계에서는 초기 트리의 뿌리를 병합해 여러 개의 비연결 트리를 하나의 트리로 만들지만 이번에는 오른쪽부터 시작해 필요에 따라 새로운 상위 노드(빨간 노드)를 추가한다.

1110 = 10112 리프가 있는 컴팩트 해시 캘린더.

그런 다음 해시 체인은 어떤 해시 트리에서도 추출할 수 있다.해시 캘린더는 결정론적인 방식으로 구축되기 때문에 그 순간 트리의 리프 노드 수만 알면 언제든지 트리 모양을 재구성할 수 있는데, 이는 1970-01-01-01 00:00:00 UTC에서 그 순간까지의 초 수보다 1초 더 많은 것이다.따라서 캘린더 트리가 생성된 시간과 그 트리에서 추출된 해시 체인을 고려할 때 각 리프 노드에 해당하는 시간 값을 계산할 수 있다.

분산 해시 캘린더

분산 해시 캘린더는 해시 캘린더 노드의 분산 네트워크다.고가용성 서비스를 보장하기 위해 서로 통신하는 여러 물리적 위치에 여러 개의 캘린더를 둘 수 있어 각 캘린더에 동일한 해시 값이 포함되어 있는지 확인할 수 있다.달력이 일치하도록 보장하는 것은 비잔틴의 내결함성의 한 형태다.

오른쪽에는 각 노드가 클러스터의 다른 모든 노드와 통신하고 단일 장애 지점이 없는 5 노드 달력 클러스터가 표시된다.각 노드에는 시계가 있지만 시계는 시간을 직접 설정하는 데 사용되는 것이 아니라 노드가 동시에 "박동"하도록 하기 위한 메트로놈으로 사용된다.

적용들

5개 노드 해시 캘린더 클러스터는 KSI(Keyless Signature Infrastructure)의 구성요소로서, 해시 캘린더의 각 리프는 글로벌 분산 해시 트리의 집계 해시 값이 된다.

참고 항목

참조

  1. ^ 디지털 인증서 특허 8,312,528 생성 시스템 및 방법
  2. ^ "Archived copy". Archived from the original on 2013-02-16. Retrieved 2013-01-07.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)

외부 링크