해시

해시(hash, 哈希)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다. 이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다. 해시값이라고도 한다. '해쉬'가 아니라 '해시'가 올바른 표기법이다. 해시는 암호학에 있어서 매우 중요한 요소이며, 블록체인(blockchain)을 구현하기 위한 핵심 기술이다.

특징

무결성

해시는 특정한 데이터를 이를 상징하는 더 짧은 길이의 데이터로 변환하는 행위를 의미한다. 여기서 상징 데이터는 원래의 데이터가 조금만 달라져도 확연하게 달라지는 특성을 가지고 있어 무결성을 지키는 데에 많은 도움을 준다. 예를 들어 'A'라는 문자열의 해시와 'B'라는 문자열의 해시는 고작 한 알파벳이 다를뿐이지만 해시 결과값은 완전히 다른 문자열이 나오게 된다.

보안성

해시는 기본적으로 복호화가 불가능하다는 특징이 있다. 이는 당연히 입력 데이터 집합이 출력 데이터 집합을 포함하고 있으므로, 특정한 출력 데이터를 토대로 입력 데이터를 찾을수 없기 때문이다. 즉, 동일한 출력 값을 만들어낼 수 있는 입력 값의 가짓수는 수학적으로 무한개라고 볼 수 있다. 만약에 해시 결과 값에 대해서 복호화를 수행할 수 있다면, 이는 압축률이 무한인 압축 알고리즘과도 같다. 해시는 애초에 복호화를 수행할 수 없도록 설계되었으며, 실제로도 해커가 쉽게 복호화를 할 수 없다는 점에서 강한 보안성을 가진다.

비둘기집 원리

대부분의 해시 알고리즘들은 항상 고정된 길이의 결과 문자열을 반환한다는 특징을 가지고 있다. 대표적인 해시 알고리즘인 MD5로 예를 들면, 128비트로 구성된 결과값, 즉 32자리의 16진수 값을 반환한다. 이 문자열의 길이는 변하지 않는다. 한 비트 단위는 0 혹은 1이라는 두 가지 경우의 수를 가진다는 점에서 128비트는 총 $2^{128}$만큼의 경우의 수를 표현할 수 있다. 이는 약 340 간($10^{36}$)에 해당하는 매우 큰 숫자이다. 단순히 무차별 대입으로 해시 결과가 동일한 두 입력 값을 찾기 위해서는 개인용 컴퓨터로는 상당히 많은 시간을 필요로 하게 된다. 하지만 아무리 큰 숫자라고 하더라도 무한은 아니라는 점에서 특정한 두 입력 값의 결과 해시 값이 동일한 경우가 발생할 수 있다. 예를 들어 입력 값의 개수가 $2^{128}$를 넘어가게 되면 최소한 한 쌍의 입력 값은 그 결과 값이 동일할 것이다. 더 간단히 설명하자면 비둘기가 5마리일때 상자가 4개밖에 존재하지 않는다면 아무리 비둘기를 균등하게 분배해도 최소한 한 상자에는 2마리의 비둘기가 들어가게 된다. 이러한 원리를 비둘기집 원리라고 말한다. 이 원리에 따라 해시에서는 '서로 다른 입력 값의 해시 결과 값이 동일한 문제' 즉, 해시 충돌이 발생할 여지가 있다.

활용

해시는 블록체인과 IPFS 등 다양한 분야에서 활용되고 있다. 보안 분야에서도 널리 사용되는데 이는 해시 함수가 원래의 문장을 복호화할 수 없게 뭉개버린다는 장점과 원문과 해시값 사이에 선형적 관계가 없다는 특성을 지니고 있기 때문이다. 해시 함수의 결과물은 고정된 길이의 숫자이므로, 원래의 정보는 손실되는데, 이러한 특성 때문에 하나의 원 데이터는 하나의 해시값만 가지지만, 하나의 해시값을 만들어 낼 수 있는 원본 데이터는 매우 많아서, 해시값만 가지고는 아무리 용을 써도 이미 뭉개져버린 원문을 복원해해는 것은 불가능하다. 따라서 비밀번호, 전자서명, 전자투표, 전자상거래와 같은 민감한 입력의 무결성을 검증할 때 주로 사용된다. 따라서 데이터의 무결성과 직접적인 연관이 있기 때문에 어떤 해시 함수에서 해시 충돌이 일어나기 쉽다는 것은 보안 분야에서는 매우 민감한 문제에 해당한다.

해시함수

해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다. 보통 그리 복잡하지 않은 알고리즘으로 구현되기 때문에, 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모하는 특성이 있다. 그리고 해시함수(hash function)는 결정론적으로 작동하기 때문에, 원래의 데이터가 같으면 해시값도 항상 동일하며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 해시 함수도 존재한다. 이러한 특성으로 인해 다양한 목적에 맞게 설계된 해시 함수가 존재하며 자료구조, 캐시, 중복 레코드 검색, 유사 레코드 검색, 에러검출 등 다양한 분야에서 매우 유용하게 사용된다. 하지만 서로 다른 데이터가 동일한 해시값을 가질 수 있기 때문에 해시충돌이 발생할 수 있다.

해시테이블

해시 테이블(hash table)은 키와 값을 매핑해 둔 데이터 구조이다. 해시함수를 이용하여 검색하고자 하는 값을 변환하면 그 값이 저장된 위치를 즉시 알아낼 수 있다. 데이터의 양이 아무리 많아지더라도 원리적으로 해시 변환과 검색에 걸리는 시간은 항상 동일하다. 따라서 방대한 데이터에서 특정한 값을 검색할 때 해시 테이블을 사용하면 검색 시간을 획기적으로 단축할 수 있다. 해시 맵(hash map)은 기존 해시 테이블의 기능을 개선한 신 버전의 해시 테이블이다.

해싱

해싱(hashing)이란 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법을 말한다. 해싱에 사용되는 자료구조는 배열(array)과 연결 리스트(linked list)가 조합된 형태이다. 짧은 해시 키를 사용하여 항목을 찾으면, 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다.

해시의 방법

제산법

제산법은 나머지 연산자를 사용하여 테이블 주소를 계산하는 방법이다. 레코드 키 값을 수치 자료로 간주하여 어떤 양의 정수(대게 해시 테이블의 크기)로 나눈 나머지를 홈 주소로 결정하는 간단한 방법이다.

ex) 버킷주소 = 키 값 % 해시 테이블의 크기
12 = 512 % 100

제곱법

제곱법은 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용하는 방법이다. 제곱된 결과의 중간 비트는 대게 레코드의 모든 문자에 의존하므로, 레코드를 구성하는 몇 개의 문자가 같을지라도 서로 다른 레코드 키는 다른 홈 주소를 갖게 될 확률이 높다. 홈 주소를 얻기 위해 사용되는 비트 수는 테이블의 크기에 따라 달라지는데, 중간 부분의 자릿수를 n 이라 하면 각 레코드 값들이 가지는 범위인 해시 테이블의 크기는 $2^{n}$이 된다.

키 값 제곱 => 해시 테이블 크기에 따라 주소 값 산출

ex) 레코드 키 값이 K=512이고, 해시테이블 크기가 100일때 제곱법에 의한 레코드 주소는
512제곱 = 262144 =====> 중간 2자리 "21"이 최종 주소값이 됨

숫자 분석법

레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법이다.

ex) 해시 테이블의 크기 = 1000, 홈 주소: 0~999까지(3자리 필요) 레코드 키 값이 다음의 (a)와 같을 때 숫자 분석법을 이용하여 각 키들에 대한 홈 주소를 결정하시오.
 (레코드 키 값)  (각 키의 홈 주소)
012 - 452 - 0236 ==> 426
012 - 153 - 0530 ==> 150
015 - 342 - 0935 ==> 395
012 - 752 - 1032 ==> 702
012 - 852 - 0470 ==> 840
012 - 543 - 0231 ==> 512
(1) (a)에서 왼족 3자리는 거의 같으므로 제거
(2) 왼쪽 5열, 6열, 7열, 9열 역시 동일 숫자가 많이 분포하므로 무시
(3) 비교적 고른 숫자 분포를 가진 4열, 8열, 10열을 선택하여 주소로 사용

폴딩법

폴딩법은 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더하거나 배타적 논리합(XOR)을 취하여, 해시 테이블의 홈 주소로 이용하는 방법으로 두 가지 방법이 사용된다.

3	0	1	2	3	0	1	2	3	2	1	3	3	0
P1			P2			P3			P4			P5

이중폴딩 ==> P1+P2+P3+P4+P5 = 301+230+123+213+30 = 897이 홈주소가 된다.
경계폴딩 ==> P1+P2(역)+P3+P4(역)+P5 = 301+032+123+312+30 = 798이 홈주소가 된다.

기수변환법

기수변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다. 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소 값이 테이블의 크기를 초과할 때는 주소 값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다.

ex) 해시 테이블의 크기 = 100000
십진수로 입력된 키 값(B2538) 10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오.
$(1*16^{5})+(3*16^{4})+(2*16^{3})+(5*16^{2})+(4*16^{1})+(8*16^{0})$ 
 $=1048576+196608+8192+1280+64+8=(1254728)_{10}$
홈 주소 = 4728(레코드의 주소값에서 해시 테이블이 허용하는 하위 4자리를 선택한다)

무작위방법

난수 발생 프로그램을 이용하여 난수를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로, 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위 값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용한다.

해시계산사이트

해시값을 자동으로 계산해서 알려주는 사이트로 깃허브의 온라인툴즈가 있다. 온라인툴즈(Online Tools)는 알려진 거의 모든 해시함수를 사용하여, 실시간으로 해시값을 계산해 주는 깃허브의 웹페이지이다.

참고자료

• 나동빈, 〈블록체인의 기본, 해시란 무엇인가?〉, 《bitweb》, 2018-02-12
• 나무위키 - https://namu.wiki/w/%ED%95%B4%EC%8B%9C
• 비트웹 편집국장, 〈블록체인의 기본, 해시란 무엇인가?〉, 《비트웹》, 2018-02-12
• 디센터유니버시티 보스코인, 〈(디센터 용어사전③)해시함수, 해킹이 가능한 듯 불가능…무량대수만큼 시도해야〉, 《서울경제》, 2018-08-17
• Online Tools - [1]

같이 보기

• 블록체인
• IPFS

이 해시 문서는 블록체인 기술에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

블록체인 : 블록체인 기술 □■⊕, 합의 알고리즘, 암호 알고리즘, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 블록체인 기술 Bech32 • BTP • DRC-20 • EIP • IPFS • KRC-20 • NFT 마켓플레이스 • P2P • P2PKH • P2SH • PFP • PUF • SPV • TPS • TRC-20 • UTXO • 가나슈 • 가명성 • 가스 • 가십 • 가십 프로토콜 • 개념증명(PoC) • 검증가능지연함수(VDF) • 게스 • 고스트 프로토콜 • 공공예산 • 대체가능토큰 • 대체불가토큰(NFT) • 도지더리움 브릿지 • 디지털 자산 • 디지털 희소성 • 라운드 • 라운드 로빈 • 라이트하우스 • 랜덤 • 레그테크 • 레이든 • 리카르디안 계약 • 린스타트업 • 마스터키 • 마스트 • 메인넷 • 멜팅 • 믹싱 • 민팅 • 밈블윔블 • 반감기 • 베타넷 • 변경불가성 • 브릿지 • 블록체인 생태계 • 블록체인인공지능 • 블록체인 클라우드 서비스(BaaS) • 블룸필터 • 비블록체인 • 비앱 • 비콘체인 • 비트코인코어 • 빤통경제 • 수정 고스트 프로토콜 • 스냅샷 • 스마트 계약 • 스마트 브리지 • 스웜프로토콜 • 스크립트퍼브키 • 스테이킹 • 스텔스 주소 • 스핀오프코인 • 슬래싱 • 시크릿 컨트랙트 • 심플 컨트랙트 • 아토믹스왑 • 암호경제(크립토 이코노미) • 앵커링 • 언스테이킹 • 에어드랍 • 에폭 • 오프체인 오더락 • 오피리턴 • 옵코드 • 원토큰 문제 • 웨이 • 위스퍼 프로토콜 • 위임 • 유니스왑 • 유동성 • 이더리움 가상머신(EVM) • 이더리움 클라이언트 • 이중지불 • 익명성 • 인증된 익명 아이디 • 인터레저 프로토콜(ILP) • 자산화 • 잠금 스크립트 • 최소기능제품(MVP) • 컨소시엄 블록체인 • 컬러드코인 • 코인셔플 • 코인소각 • 코인에이지 • 코인조인 • 코인토싱 • 크립토노트 • 키스토어 • 타임락 • 테스트넷 • 토다 • 토큰 이코노미 • 토큰화 • 튜링완전 • 튜링불완전 • 트랜잭션 아이디(TxID) • 트러스트 컨트랙트 • 트루빗 • 트릴레마 • 파워 • 파티셔닝 • 퍼블릭 블록체인 • 페널티 • 프라이버시 • 프라이빗 블록체인 • 플랫폼 • 플러딩 • 피어 • 피투피(P2P) • 하이브리드 블록체인 • 합의 • 해시락 • 해시타임락(HTLC) • 해제 스크립트 • 확장성 해시 레인보우 테이블 • 매핑 • 머클경로 • 머클루트 • 머클트리 • 분산해시테이블(DHT) • 블록해시 • 스큐드 머클트리 • 온라인툴즈 • 이전블록해시 • 카뎀리아 • 해시 • 해시레이트 • 해시맵 • 해시충돌 • 해시테이블 • 해시파워 • 해시함수 • 해싱 블록 고아블록 • 그래핀 • 논스 • 마이크로블록 • 베이킹 • 북키퍼 • 브랜치블록 • 브로드캐스팅 • 블록 • 블록높이 • 블록바디 • 블록생성자 • 블록정보 • 블록타임 • 블록헤더 • 비츠 • 세그윗 • 엉클블록 • 완결성 • 제네시스블록 • 타임스탬프 • 프룻 • 프룻체인 체인 더블체인 • 라이트닝 네트워크 • 라이트닝 루프 • 루트체인 • 루프체인 • 메인체인 • 방향성 비순환 그래프(DAG) • 베리파이어블 프루닝 • 블록격자 • 블록체인 • 사용자 활성화 소프트포크(UASF) • 사용자 활성화 하드포크(UAHF) • 사이드체인 • 서브체인 • 소프트포크 • 오페라체인 • 오프체인 • 온체인 • 인터체인 • 차일드체인 • 체인 • 탱글 • 테스트체인 • 토카막 네트워크 • 포크 • 포크체인 • 퓨어체인 • 프로덕트체인 • 프루닝 • 프리포크 • 플라즈마 알고리즘 • 플라즈마캐시 • 플래시 계층 • 하드포크 • 해시그래프 • 홀로체인 노드 검증인(밸리데이터) • 기본노드 • 노드 • 라이트노드 • 랜덤노드 • 마스터노드 • 베이킹노드 • 보조노드 • 보증노드 • 슈퍼노드(슈퍼대표, 대표노드) • 슬롯 • 슬롯리더 • 엔드포인트노드(레인저노드) • 의회 네트워크 • 작업노드 • 종단노드 • 종자노드(시드노드) • 중계노드 • 지갑노드 • 채굴노드(마이닝노드) • 쿼럼 • 풀노드 • 합의노드 샤딩 네트워크 샤딩 • 데이터베이스 샤딩 • 동적샤딩 • 샤드 • 샤딩 • 스테이트 샤딩 • 알고리즘 샤딩 • 적응형 상태 샤딩 • 체인샤딩 • 트랜잭션 샤딩 채굴 병합채굴 • 사전채굴 • 에이식(ASIC) • 에이식부스트 • 에이식 저항 • 일드파밍 • 채굴 • 채굴 난이도 • 채굴량 • 탄소감축채굴 • 페어런치 탈중앙화 TVL • 거버넌스 • 다오(DAO) • 다이코(DAICO) • 닥(DAC) • 닥스(DAX) • 덱스(DEX) • 디앱(DApp) • 디지오(DGO) • 디튜브 • 디파이(DeFi) • 분산경제 • 분산원장(DLT) • 분산 클라우드 • 씨파이(C-Fi) • 오프체인 거버넌스 • 온체인 거버넌스 • 원장 • 준중앙화 • 중앙화 • 탈중앙화 • 탈중앙화 TPS • 탈중앙화 조직(DO) • 탈중앙화 지수(DQ) 분산아이디 DIDs • IETF • ToIP • 검증가능한 자격증명 • 검증인 • 디지털아이덴티티재단 • 발급자 • 보유자 • 분산아이디(DID) • 분산아이디 기관 • 분산아이디 인증(DID Auth) • 아이온 • 자기주권 • 자기주권신원 • 최소화된 자격증명 데이터 • 탈중앙화 키관리시스템 • 통합해석기 오라클 상호인증 블록체인 • 오라클 • 오라클 머신 • 오라클 문제 • 오라클 서비스 • 중간자 BIP BIP • BIP9 • BIP16 • BIP32 • BIP39 • BIP43 • BIP44 • BIP47 • BIP49 • BIP63 • BIP70 • BIP84 • BIP141 • BIP148 ERC ERC • ERC-20 • ERC-165 • ERC-223 • ERC-621 • ERC-721 • ERC-777 • ERC-827 • ERC-884 • ERC-998 • ERC-1155 • ERC-1404 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반