저장증명

저장증명(PoS; Proof of Storage)이란 증명자(prover)가 자신의 하드디스크 여유 공간에 데이터를 저장하고, 검증자(verifier)가 그것을 승인 또는 거절하는 방식으로 작동하는 합의 알고리즘이다. 이런 점에서 저장증명은 공간증명(Proof of Space)이라고도 한다. 저장증명은 용량증명 합의 알고리즘과 유사하다.

개요

저장증명은 두 가지 단계로 구성된 프로토콜이다. 초기화 단계에서 증명자 A는 데이터의 크기가 N인 데이터 D를 자신의 하드디스크에 저장하고, 검증자 B는 아주 작은 조각의 정보만 가지고 있게 된다. 이후 증명 실행 단계에서 검증자 B는 해당 데이터에 대해 승인 또는 거절할 수 있다. 검증자 B가 해당 데이터에 대해 승인하는 경우, 그 대가로 암호화폐가 보상으로 지급된다.

저장증명 합의 알고리즘을 채택한 암호화폐에는 유토큰(YOU token)이 있다.

등장배경

클라우드 컴퓨팅 응용 프로그램들은 저장증명 프로토콜, 즉 클라이언트가 저장해달라고 요청한 파일을 서버가 실제로 저장했음을 증명하는 데 쓰이는 프로토콜 안에서 해시 함수를 사용해왔다.

2007년 라마크리슈나 콜타(Ramakrishna Kotla)와 로렌초 알비시(Lorenzo Alvisi), 마이크 달린(Mike Dahlin)이 “SafeStore : A Durable and Practical Storage”라는 논문을 통해 어떤 파일 M의 저장 사실을 증명하는 다음과 같은 저장증명 프로토콜을 제안했다.

1. 클라이언트는 어떤 난수 값 C를 선택한다. 이 값을 시도(challenge)라고 부른다.
2. 서버는 그에 대한 응답(response)으로 Hash(M∥C)를 계산해서 클라이언트에게 보낸다.
3. 클라이언트도 Hash(M∥C)를 계산해서 그것이 서버가 보낸 응답값과 일치하는지 확인한다.

논문의 핵심은, 서버가 M을 모르는 상태에서 Hash(M∥C)를 추측할 수는 없으므로, 서버가 M을 온전하게 저장하지도 않고 마치 저장한 척 클라이언트를 속일 수 없다는 것이다. 그러나 여기에는 함정이 있다. 현실적으로 해시는 입력을 블록 단위로 처리하면서 각 블록 사이의 중간 연쇄 값을 계산하는 반복 해시 함수일 것이다. 예를 들어 해시가 SHA-256이고, M이 512비트라고 하면 서버는 클라이언트를 속일 수 있다. 어떻게 그럴까? 서버는 M의 첫 512비트 블록 M₁과 SHA-256의 초기치 H₀을 이용해서 연쇄값 H₁=Compress(H₀, M₁)을 계산한다. 그런 다음에는 그 H₁을 메모리에 저장하고, M 자체는 폐기해 버린다. 그러면 서버는 더 이상 M을 저장한 상태가 아니다.

클라이언트가 무작위 시도값 C를 보내면 서버는 C를 적절히 채워서 완전한 블록을 만든 후 Compress(H₁, C)를 계산하고, 그것을 Hash(M∥C)의 결과로서 클라이언트에게 보낸다. 클라이언트는 이를 믿을 수밖에 없다. 서버가 보낸 것이 실제로 Hash(M∥C)의 정확한 값이기 때문이다. 따라서 클라이언트는 서버가 자신의 파일을 잘 저장하고 있따고 믿게 된다. 그러나 앞에서 언급했듯이 서버는 파일을 이미 폐기해 버렸을 수 있다. 이 요령은 SHA-1과 SHA-2뿐만 아니라 SHA-3과 BLAKF2에도 통한다. 해결책은 간단하다. Hash(M∥C)가 아니라 Hash(C∥M)을 맞추어 보도록 프로토콜을 수정하면 된다.

참고자료

• Keda Che, "Universal Labs White Paper V.1.3 (Draft)", 2018-05-25

같이 보기

• 합의 알고리즘
• 용량증명
• 유토큰

이 저장증명 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반