양자컴퓨터란?

양자컴퓨터는 연산 체계 자체가 기존의 컴퓨터와 전혀 다른 방식으로 작동하는 컴퓨터입니다. 기존의 방식은 비트로 0, 1로만 표현되며 비트는 둘 중 하나만 가질 수 있습니다. 반면 양자컴퓨터은 0, 1, 그리고 0과 1의 조합을 동시에 나타내고 저장할 수 있는 양자 비트(quantum bits), -이를 줄여서 큐비트(qubits)라고도 말함- 를 이용하여 데이터를 처리합니다. 이러한 두 상태의 중첩이 가능해짐에 따라 양자 컴퓨터는 바이너리 비트를 이용하여 모든 정보를 0 아니면 1로만 저장할 수 있는 전통적인 컴퓨터보다 훨씬 더 데이터 처리의 속도를 가속화 할 수 있습니다. 즉, 양자컴퓨터는 양자 컴퓨터는 모든 가능한 상태가 중첩되어 얽혀있는 상태 -이를 양자 결집 상태(quantum-coherent state) 라 칭함- 를 이용합니다. 이를 더 설명하자면 양자 상태는 여러 가지 고유값을 가지는 서로 다른 고유 상태가 중첩되어 존재하는데 양자역학적으로 측정 혹은 섭동 행위는 중첩되어 존재하는 양자 상태를 붕괴시켜 허용된 고유상태 중 특정한 하나로 확정되도록 합니다. 여기서 고유 상태 중 어떤 상태로 확정될지는 아무도 알 수 없고 확률적으로 추정만 가능합니다. (어려워)  이러한 어려운 내용을 요약하면 양자는 간단하게 자연현상은 확률의 지배를 받으며측정 혹은 섭동 행위 자체가 상태에 영향을 미칩니다.

용어

  • 양자 중첩 (quantum superposition) : 어떤 입자가 에너지 또는 위치와 관련하여 가질 수 있는 모든 가능한 상태들로 동시에 존재하는 양자역학적 특성.
  • 양자 얽힘 (quantum entanglement) : 둘 이상의 양자 상태를 밀접하게 연관시켜 서로 엮어 놓은 상태. 얽힘 상태의 양자들은 서로 분리된 물리계에서도 어느 한쪽의 상태가 결정되면 다른 쪽 상태도 그 결과에 따라 필연적으로 결정되는 현상을 보임

위 설명에선 나오진 않았지만 자주 등장하는 단어입니다.

양자 컴퓨터의 작동원리

물리학 전공이 아니여서 아주 간단하게만 설명하고 넘어갑니다.

위에서 설명했지만 큐비트로 정보를 처리하기 위해서는 모든 것이 상호의존적인 중첩 상태에 있어야 합니다. 이러한 상태를 가리켜 양자 결집 상태(quantum-coherent state)라고도 하는데, 큐비트가 서로 결집되어 뒤얽혀 있는 상태를 가리킵니다. 이 상태에서는 하나의 큐비트에 변화를 주면 이것이 나머지 큐비트에게도 영향을 미치게 됩니다. 큐비트는 아주 연약하기 때문에 약간의 온도 변화, 소음, 파동, 그리고 움직임만으로도 물리학자들이 결잃음(decoherence)이라 부르는 상태가 될 수 있습니다. 결잃음이란 에너지가 새어 나가 계산에 실패하는 상태를 가리킵니다. 오늘날 큐비트들은 결잃음이 발생하기 전까지 양자 상태를 고작 100 마이크로초 동안만 유지할 수 있다고 IBM 연구원들은 설명하고 있습니다

위의 결잃음 상태를 보는 것과 같이 양자 컴퓨터는 아주 극단적입니다. 쿨링에는 약 0.015 켈빈도의 온도가 필요한데, 이는 항성간 우주의 온도보다 180배나 더 차가워야 함을 의미한다고 합니다. 또한 이들은 지구의 자기장보다 50배 약한 강도로 보도돼야 하고 대기 중의 압력보다 100억 배 더 압력이 약한 고진공 상태에 두어야 하며, 저진동 표면에 위치시켜야 합니다.


이렇게 양자를 유지하는 것이 어려운 것 처럼 임의의 양자 상태를 복사하는 것은 불가능 합니다. 이러한 양자의 속성을 사용하면 보안에 있어 절대적으로 해킹할 수 없는 암호체계를 만들 수 있습니다. 또한 해킹하고자 하는 행동이 양자의 정보상태를 망가뜨리기 때문에 금방 알아챌 수도 있습니다.

얼마나 빠를까?

양자 컴퓨팅의 우수성은 특히 오늘날 가장 빠른 슈퍼 컴퓨터 보다도 훨씬 빠르게 데이터를 처리할 수 있다는 점에서 주목받고 있습니다. 일반적으로 50큐비트에서 이러한 속도가 가능해진다고 알려져 있지만 큐비트 수가 증가할수록 양자 결집 상태를 유지하는 것이 어려워진다는 문제가 있습니다. 

양자 컴퓨터와 현존하는 암호화 알고리즘

소인수분해 문제 이외에도 수많은 암호 알고리즘이 바탕을 두고 있는 이산로그 문제 역시 양자컴퓨터로 해결할 수 있습니다. 따라서 양자컴퓨터가 본격적으로 실용화되면 현재까지 개발된 대부분의 암호 알고리즘이 쓸모 없어지게 됩니다. 하지만 양자컴퓨터가 모든 암호를 풀 수 있는건 아닙니다. 현재 모든 암호는 NP문제입니다. 양자컴퓨터가 NP-완전 문제(NP-complete)를 다항 시간(P)에 풀 수 있다는 잘못된 인식이 널리 퍼져 있으나 확실하게 증명된 내용은 없습니다(풀리면 7대 난제 해결). 그리고 컴퓨터가 진화했던 만큼 더 안전한 알고리즘을 만들면 되기 때문에 기존과는 차원이 다른 보안 알고리즘을 사용할 가능성이 남아있습니다. 게다가 현재 제안된 알고리즘들 중 격자 기반(lattice based) 암호계는 아직 양자컴퓨터로 해결할 알고리즘은 없습니다. 그 외에도 AES와 같은 블록 암호들 역시 아직 양자컴퓨터로 깨뜨릴 알고리즘이 나오지 않았으므로 현재로서는 '양자컴퓨터가 급격히 실용화되더라도' 안전하다고 볼 수 있습니다.

P - NP 문제

  • P: 시간만 있으면 풀 수 있는 문제. O(n)과 같이 현실적으로 풀 수 있는 알고리즘의 복잡도
  • NP: 알고리즘의 복잡도가 너무 비현실적인 문제. 기하급수적으로 복잡도가 증가

NP 문제

그래프가 주어졌을 때 그래프의 모든 점을 정확하게 한번씩만 지나는 경로가 존재하는가?

위와 같은 문제가 주어졌을 때(=해밀턴 경로 문제) 이 문제에 대해 어떤 경로를 입력으로 준다면, 컴퓨터는 이게 정답인지 아닌지 알려줄 수 있습니다. NP문제로 돌아가서, 비결정론적 튜링머신이 주어진 입력이 정답인지 아닌지 계산하는데 다항시간(P)이 걸린다고 하면 NP문제라고 합니다. 다시 말하면, 컴퓨터로 다항 시간에 풀어낼 수 없는 문제들을 NP 문제라고 칭합니다.

NP-난해 (NP-hard) 문제

위에 나오진 않지만 NP-완전문제를 설명하기 전, 간단히 소개합니다. 적어도 NP문제 보다 어렵고 모든 NP 문제를 다항 시간 내에 어떤 문제 A로 환원(reduction)할 수 있다면, 그 A 문제를 NP-난해(NP-hard) 문제라고 합니다.

환원(reduction)이란?

문제 A: 주어진 n개의 숫자를 크기 순서로 정렬하는 문제
문제 B: 주어진 n개 숫자의 중간값을 계산하는 문제

어떤 사람이 문제 A를 풀 수 있다면 당연히 B도 쉽게 풀 수 있습니다. A를 푼 다음 가운데 수만 뽑아내면 문제 B가 풀리기 때문입니다. 이와 같은 것을 문제 B를 문제 A로 환원(reduction)시킬 수 있다고 표현합니다.

NP-완전 (NP-complete) 문제 

NP난해 문제에 포함되며, NP문제에도 포함된다면 이를 NP-완전(NP-complete) 문제라고 합니다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게되므로 NP 문제들 중에서는 가장 핵심이 되는 문제입니다. 위에서 예를든 해밀턴 경로 문제도 대표적인 NP-완전 문제들 중 하나입니다.

만약 NP=P 가 옳은지 그른지 증명을 할 수 있다면 여러 교과서에 실릴 수 있습니다.

격자 기반 암호

격자 암호화(lattice cryptography)로 불리는 차세대 양자암호화 방식이 현재 개발이 되었는데 이는 현존하는 컴퓨터나 양자 컴퓨터 조차도 해독할 수 없다고 합니다. 격자는 점으로 만들어진 무한 그리드를 나타내는데 격자 암호화 기술 방식을 사용하면 해커들에게 민감한 데이터를 노출시키지 않고도 파일을 작업하거나 암호화 할 수 있습니다. 격자암호화 기술은 정보를 숨기기 위해 고차원 기하 구조를 사용하는데 키가 없으면 양자 컴퓨터로도 풀 수 없는 문제를 생성해 냅니다. 

출처: IBM

따라서 양자컴퓨터가 실용화되고 그 때까지 격자 기반 알고리즘을 양자컴퓨터로 해결할 알고리즘이 개발되지 않는다면, 격자 기반 알고리즘이 공개키 암호계의 대세를 차지하게 될 가능성도 있습니다.


'블록체인' 카테고리의 다른 글

이더리움이란?  (0) 2018.07.28
비트코인 - UTXO란?  (0) 2018.07.24
양자컴퓨터란?  (0) 2018.07.23
블록체인 타임스탬프  (0) 2018.07.18
51% 공격(Attack)이란?  (0) 2018.07.17
작업증명 (Proof-of-Work : PoW) 알고리즘이란?  (0) 2018.07.11

블록체인에 해당하는 개념은 “타임 스탬프 서버”라는 부분에 설명되어 있습니다. 이로 인해 블록체인과 타임스탬프는 상당히 큰 연관성이 있어 보인다는 것을 알 수 있습니다.

그렇다면, “타임 스탬프” 개념에 대해서 다시 생각해 봅시다. 일반적인 타임스탬프(Timestamp)라고 하면 “2018-04-05 13:00:00”등의 형식으로 표현되는 날짜와 시간이 적힌 문자열이라고 생각하게 됩니다. 실제 생활에서는 독자가 여행을 가기 위해 KTX 티켓을 예매하기 위해 시간을 선택하면 그것을 누가 언제 몇시 몇분에 탑승을 위한 계약 내용에 날짜와 같이 저장되는 것이 타임스탬프의 한 종류라고 봐도 됩니다. 타임스탬프의 역할은 어떤 이슈가 일어난 날짜와 시간을 기록하여 사실 존재를 증명하는 전후 관계를 보장하는 것입니다.

현실세계의 타임스탬프

아래 그림과 같이 지역별 시차를 제외하면 표준시간, 현지시간 등의 표준화를 통해 모든 사물, 사람들이 시간축을 공유합니다.

모든 사람은 같은 시간축을 공유

컴퓨터의 타임스탬프

컴퓨터 세계에서는 현실세계의 시간과 반드시 동기화되는 것은 아니기 때문에(각각의 환경이 참조하는 시간이 다르기 때문), 여러 환경에 따라 다른 시각을 보일 수 있습니다. 여기서 지불한 사실이 언제 일어났는지에 대한 합의를 하지 못하면, 사실 증명이 어렵게 됩니다. 이런 경우, 타임스탬프를 악의적으로 쉽게 변경할 수 있어 어려움이 생기게 됩니다. 예를 들어 게임에서 이벤트를 할 경우, 특정 시간에 한정 아이템을 받을 수 있는 조건이 발생하거나 특정 시간대에서만 얻을 수 있는 혜택이 제공될 때, 사용자가 기기의 시간대를 변경해서 미리 이벤트 정보를 확인하고 부정 플레이를 할 수 있게 됩니다. 

모든 사람이 컴퓨터에 설정된 시간, 즉 모두 다른 시간축을 가짐

중앙집권적 타임스탬프

인터넷 서비스는 불특정 다수의 사람들에게 서비스하는데 있어서 어느 한 곳에 중심을 두고 그 중심점의 시간을 기준으로 서비스 무결성을 유지하고 있습니다. 보통 타임서버에 접근하여 시간 동기화를 하여 모든 서버가 동일한 시간축을 가지도록 사용하고 있습니다. 이 경우 타임서버가 해킹당한다면 시간축이 틀어질 수 있는 단점이 있습니다. 여기서 비트코인은 “아무도 간섭없이 사용할 수 있는 송금 구조를 만들자”것과 “누구도 마음대로 중지시킬 수 없다”라는 구조를 실현하기 위해서는 중앙집권적 구조가 아닌 중심부가 없는 P2P형태의 구조를 생각하게 되었습니다.

타임서버와 동기화하여 각 서버의 시간축을 동일하게 유지

비중앙집권적 타임스탬프

P2P 시스템에서 중심부 시간에 의존하지 않은 상태로 타임스탬프를 필요로 하는 데이터를 처리하기 위해 새로운 타임스탬프 방법이 필요해졌습니다. 다시 말해, 타임스탬프가 필요한 서비스를 P2P로 실현하기 위해 중심부 시간에 동기하는 방법으로는 한계가 존재하여 블록체인 타임스탬프 개념이 나왔습니다. 블록체인이 획기적으로 보이는 이유는 시간을 되돌릴 수 없다는 것과 1개의 시간축을 모두가 공유하고, 그 시간축에서 전화 관계를 정의할 수 있는 물리적인 시간 특징을 암호화학에 기초한 데이터구조를 사용하여 다시 구현한 것입니다.

P2P네트워크에서 모든 사람이 볼 수 있는 시간 = 블록체인 타임스탬프

해시체인 타임스탬프

물리적 시간의 동기화가 확인하기 어려운 분산시스템에서 모든 참가자가 하나의 시간축을 공유하려면 어떤 사건이 일어난 절대적인 시간을 엄격하게 요구하는 것이 아니라, 전후 관계가 존재하는 2개의 사건에 대해 그 순서를 특정할 수 있는 상대적 시간으로 시간축을 정의하는 방법이 있습니다. 즉, 사건1과 사건2가 발생했을 때 사건1과 사건2가 일어난 정확한 시간을 몰라도, '사건1이 사건2 다음에 일어났다' 라는 상대적인 전후 관계만을 취급한다는 것입니다. 이 개념은 분산시스템의 논리적 타임스탬프라고 말합니다.

블록체인은 암호화 해시함수를 사용하여 데이터가 존재하기 전에 다른 데이터가 존재했다는 전후 관계를 논리적으로 부정할 수 없는 형태로 정의하고 있습니다.

사건의 상대적인 전후 관계만 취급하는 시간축


위 그림에서 A데이터에 대해 암호화 해시함수를 이용하여 얻어진 해시값 h(A)이라고 합니다. h(A)값이 존재하는 것은 이전 A데이터가 있는 것이 논리적으로 옳다고 봅니다. 또한, B = h(A)로 h(B)를 계산하면 h(B)가 존재하기 전에 h(A)가 존재하고 있었다고 볼 수 있습니다. 이처럼 동일한 데이터에 대해 재귀적으로 암호화 해시함수를 적용하는 기술이 해시체인입니다. 이 해시체인은 일회성 비밀번호 인증 시스템 구현에 주로 사용됩니다.

확장된 해시체인

확장된 해시체인

위의 확장된 해시체인을 사용하여 모든 데이터의 존재증명과 전후 관계를 증명할 수 있습니다. 실무적인 P2P시스템에서 사용하기 위해서는 몇가지 이슈를 해결해야 합니다.

  • 여러개의 노드가 참여하는 P2P 네트워크에서 모든 노드가 항상 최신 타임스탬프를 볼 수 있는가?
  • 노드가 과거 데이터를 변조한 경우, 변주 탐지 및 변조 데이터를 거부할 수 있는가?

블록체인에서는 위 첫번째 이슈를 해결하기 위해 모든 데이터를 항상 모든 노드에서 공유하지 않고 여러 데이터를 정리한 블록단위로 공유합니다. 이 블록을 만드는데 사용되는 기술이 머클트리(Merkle tree 또는 해시트리)입니다. 또한 이 머클트리를 사용하여 두번째 이슈를 해결할 수 있습니다. 머클트리는 http://brownbears.tistory.com/372 정리되어 있으니 확인하면 됩니다.

'블록체인' 카테고리의 다른 글

비트코인 - UTXO란?  (0) 2018.07.24
양자컴퓨터란?  (0) 2018.07.23
블록체인 타임스탬프  (0) 2018.07.18
51% 공격(Attack)이란?  (0) 2018.07.17
작업증명 (Proof-of-Work : PoW) 알고리즘이란?  (0) 2018.07.11
머클트리(merkle tree)란?  (0) 2018.07.09

51% 공격(Attack)이란?

51% 공격은 작업증명 (PoW) 알고리즘에서 나오는 용어입니다. 비트코인은 작업증명(PoW)을 사용해서 연산을 통해 일종의 문제를 가장 빨리 푼 노드에게 블록을 추가시킬수 있는 권한을 줍니다. 이때 나머지 노드들은 해당 블록이 유효한 거래인지 승인을 하게 됩니다. 절반 이상의 승인을 거치면 유효한 거래로 확인하고 블록을 블록체인에 연결, 모든 노드에게 전파하게 됩니다. 그런데 블록체인 전체 연산량의 50%이상을 보유한 채굴자는 압도적인 채굴량을 바탕으로 전체 네트워크를 마음대로 결정할 수 있게되며 51%공격을 감행할 수 있습니다. 

  • A: 비트코인 네트워크 전체 해시 파워 중 51% 이상을 가진 채굴자 및 거래자
  • B: 일반 거래자

A가 B에게 악의적인 생각을 가지고 BTC를 판매하려고 가정합니다. A는 B에게 50BTC를 송금하고 송금한 거래 기록의 트랜잭션이 실제 블록에 담기어, 블록체인에 연결이 됩니다. B는 자신의 거래 내역이 블록체인에 연결되었기 때문에 A에게 돈을 주게 됩니다. 여기까지의 과정은 아래와 같이 볼 수 있습니다.


돈을 받은 A는 B에게 지불한 기록을 삭제하고 새로운 블록을 생성합니다. A는 해시파워가 전체의 51% 이상을 가지고 있기 때문에 빠르게 이어질 블록까지 생성해나갑니다.



A는 연산력이 다른 채굴자에 비해 훨씬 높기 때문에 A가 만든 블록은 인정을 받아 블록체인에 연결이 이어집니다. B에게 송금한 진짜 기록의 블록연결고리는 더 짧은 길이가 되어 가짜가 됩니다.(고아 블록, 스테일 블록) 이와 같이 진행되면 A는 BTC를 송금한 기록이 사라지게 되고 B에게 돈을 받은셈입니다.


51% 공격이란 전체 네트워크의 자원을 독보적으로 많이 가지고 있는 사용자, 혹은 그룹으로 인하여 발생할 수 있는 문제입니다. 이 문제는 이론적으로 가능하나 경제적으로는 불가능한 상황이 존재합니다. 만약 51% 이상의 해시파워를 보유했다면 이와같이 거래를 조작할 수 있게 되는 사실을 스테일 블록이 발생하는 과정을 통해 파악할 수 있습니다. 이 과정을 지켜보는 사용자들은 비트코인 거래를 신뢰할 수 없다고 생각되어 마구잡이로 파는 패닉셀이 발생할 수 밖에 없습니다. 51%이상의 해시파워를 지닌 채굴자는 해시파워를 유지하기위해 그만큼 어마어마한 유지비를 감당해야 되는데 비트코인 가격이 똥값이 되면 가장 먼저 타격을 입게 됩니다.

'블록체인' 카테고리의 다른 글

양자컴퓨터란?  (0) 2018.07.23
블록체인 타임스탬프  (0) 2018.07.18
51% 공격(Attack)이란?  (0) 2018.07.17
작업증명 (Proof-of-Work : PoW) 알고리즘이란?  (0) 2018.07.11
머클트리(merkle tree)란?  (0) 2018.07.09
블록체인 기술 정의  (0) 2018.07.08

작업증명(Proof-of-Work) 방식의 합의 알고리즘은 비트코인에서 사용되는 합의 알고리즘으로써 어떤 트랜잭션이 발생했을 경우 해당 트랜잭션이 유효한 트랜잭션인지에 대한 합의 방법 및 새로운 블록이 진짜인지, 가짜인지에 대한 검증을 수행합니다. 작업 증명 방식(PoW)을 이해하기 위해서는 우선 마이닝 과정에 대한 개념정리가 필요합니다.

마이닝(채굴)이란?

마이닝(채굴)이란 임의의 nonce 값을 대입하여 블록 해시 결과 값을 생성하고, 생성된 결과 값이 제시된 Target 보다 작은 블록 해시를 찾는 과정입니다 (자세한 내용은 아래에서 설명). 해시함수의 특징때문에 어떤 nonce 값을 대입해야 제시된 Target 보다 작은 블록해시 정보를 찾을 수 있을지는 알 수 없습니다.

즉 올바른 결과 값을 찾기 위해서는 nonce의 값을 0부터 1씩 증가 시키면서 제시된 Target 보다 작은 결과 값이 나올때까지 무한 반복 작업을 수행해야 합니다. 이러한 수학문제를 풀이하는 과정을 1초에 몇번이나 수행할 수 있는지에 대한 수치 정보를 해시파워라고 표현하며, 해시파워가 높은 마이너일수록 더 많은 문제를 풀어낼 수 있으며 더 많은 문제를 풀어낼 수 있는 채굴자가 새로운 블록을 찾을 확률이 더 높습니다. 해시 파워가 높은 채굴자일수록 더 많은 일을 수행했다는 의미이며, 더 많은 일을 할 경우 확률적으로 더 많은 보상을 받게 됩니다. 그렇기 때문에 PoW를 정의할때 더 많은 일을 한 채굴자에게 더 많은 보상이 주어지는 방식이라고 표현합니다.


블록 데이터 해시 연결을 위해 블록에는 블록 헤더 데이터를 해시 함수로 계산한 블록 해시가 들어가고 이를 통해 해시 연결성을 검증해 블록체인 데이터가 중간에 위변조가 되지 않았음을 확인합니다.

작업증명(PoW)은 왜 필요할까?

이러한 작업증명 알고리즘의 필요성은 네트워크의 모든 노드가 동시에 블록을 만들 수 없게 하는 것 입니다. 작업증명을 통과해야만 블록을 생성할 수 있고, 이를 위해서는 엄청난 에너지가 소모됩니다. 그리고 작업증명 알고리즘은 Difiiculty 조절 알고리즘을 이용하여 10분당 1~2개의 블록이 생성된다는 것을 보장합니다.

네트워크의 노드들은 다음 블록을 생성하기 위해 A와 B 중 하나의 블록을 선택하여 블록을 생성합니다. 다음 블록을 생성하는 노드는 A와 B중 하나의 블록에 연결한 블록을 생성합니다. 또 다시 A를 선택한 노드와 B를 선택한 노드가 동시에 블록을 생성할 확률은 굉장히 낮겠죠. 나카모토 사토시는 확률 증명을 통해 블록 6개가 대립되는 블록이 계속 생성될 확률은 0에 가깝다는 것을 보였습니다.

작업증명 합의 알고리즘은 일시적으로 합의가 깨질 수 있으나 확률적으로 마지막엔 하나의 블록체인을 합의하게 되는 합의의 알고리즘 입니다. 작업증명 알고리즘은 기존 합의 알고리즘이 적은 수의 노드와 대다수는 올바른 행동을 한다는 가정(보통 3f+1 이상이 올바른 일을 해야 정상 운영, f는 잘못된 노드의 수)을 통해 작동하는 알고리즘인 것과 달리 글로벌한 규모의 완전히 오픈된 네트워크에서 운영할 수 있는 알고리즘 입니다.

장점

  • 최소 가격대 형성이 확실하게 정해져 있음
  • 강력한 보안성
  • 서비스 남용을 쉽게 방지

단점

  • 채굴난이도가 높아지면서 연산에 필요한 고사양 장비가 많이 필요하고, 과도한 전력소모로 인한 에너지 낭비가 커짐
  • 채굴난이도가 높아지면서 개인 채굴자는 채굴을 할 수 없는 수준까지 옴
  • 지속적으로 해시파워를 유지해야함
  • 채굴하는 업자끼리의 단합 문제

블록 구하는 방법

위에서는 마이닝(채굴)이 뭔지와 작업증명이 왜 필요한지를 설명했습니다. 지금부터는 블록을 어떻게 구할지와 작업증명의 성공 여부를 확인하는 방법을 설명하겠습니다. 

https://www.blockchain.com/에 들어가면 현재 채굴이 된 블록을 조회할 수 있습니다. 아래의 예시는 125552번째 블록을 채굴한다고 가정하여 125552를 검색해 정보를 확인합니다. (https://www.blockchain.com/btc/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d - 125552를 검색한 결과 URL)



위의 주소로 들어가 정보를 살펴보면 타임 스탬프, Bits, 해시 난수, 이전 차단, Merkle Root 정보를 확인할 수 있습니다. 앞서 설명한 블록 해시를 구하는 공식에는 6가지 요소가 필요하나 여기에는 버전 정보가 누락되어 있습니다. 그리고 타임 스탬프 정보 또한 우리가 보기 편한 형식으로 변형되어 있습니다. 실제로 블록해시를 구하기 위해 JSON 형태로 데이터를 획득해야 합니다. (https://blockchain.info/block-height/125552?format=json)

위 URL처럼 정보를 구성하여 요청하면 125552번째 블록 정보를 JSON 형태로 제공받을 수 있습니다. 참고로 위의 URL의 /125552? 이 부분에 숫자 부분이 블록 높이 정보입니다. 다른 블록을 확인하고자 할때는 원하는 블록 높이 값을 입력하여 호출하면 됩니다.


여기서 필요한 값은 ver, prev_block, mrkl_root, time, bits, nonce 입니다. 위 정보로 확인하면 nonce가 2504433986 일 때, 해시함수의 결과값이 00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d으로 작업증명이 성공한 것을 알 수 있습니다.

블록해시 구하는법

아래에서는 파이썬 3.+ 버전으로 작성하여 연습을 해봅니다.

import hashlib
import struct


little_endian = lambda value: struct.pack('<L', value).hex()
reverse_order_pair = lambda value: ''.join([value[i - 2:i] for i in range(len(value), 0, -2)])

# 125552번째 블록 정보
# 아래의 정보로 결과가 00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d 나오면 성공
block_info = {
    'hash': '00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d',
    'ver': 1,
    'prev_block': '00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81',
    'mrkl_root': '2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3',
    'time': 1305998791,
    'bits': 440711666,
    'fee': 1000000,
    'nonce': 2504433986,
    }

convert_block_info = {}

# 1. 버전, 타임, bits, nonce 정보를 리틀 엔디안 형태로 변형.
convert_block_info['ver'] = little_endian(block_info['ver'])
convert_block_info['time'] = little_endian(block_info['time'])
convert_block_info['bits'] = little_endian(block_info['bits'])
convert_block_info['nonce'] = little_endian(block_info['nonce'])

# 2. 이전 블록 해시, 머클루트 결과 값을 모두 반대 순서로 변형
convert_block_info['prev_block'] = reverse_order_pair(block_info['prev_block'])
convert_block_info['mrkl_root'] = reverse_order_pair(block_info['mrkl_root'])

# 3. 블록 헤더 정보를 모두 합산(순서가 꼭 맞아야합니다.)
header_hex = convert_block_info['ver'] + convert_block_info['prev_block'] + convert_block_info['mrkl_root'] + convert_block_info['time'] + convert_block_info['bits'] + convert_block_info['nonce']

# 4. 바이너리 형태로 변형
header_bin = bytes.fromhex(header_hex)

# 5. SHA 256으로 변환한 결과를 다시 SHA 256 으로 변환(2번진행)
hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()

# 6. hash 결과를 뒤집은 다음  16진수로 변경
result_header_hex = hash[::-1].hex()

# result : 00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d
# 성공

위의 코드를 실행하면 현재 블록의 해시 값이 나온 것을 확인할 수 있습니다. 

실제로의 채굴은 nonce를 0부터 1씩 증가시키면서 Target 값과 비교하여 작거나 같을 때까지 반복실행합니다. 

(왜 값을 Little Endian으로 변형하고 16진수 값을 뒤집고 하는지 이유는...)

정리

  1. ver, time, bits, nonce는 Little Endian 형태로 변형
  2. prev_hash, mrkl_root는 결과 값을 모두 반대 순서로 변경 (16진수 이므로 2개씩 묶어서 반대로 변경)
  3. 헤더 정보들을 모두 합산(문자열 값을 이어붙임. 이때 순서가 변경되면 안됨)
  4. 합산한 헤더 정보를 바이너리 형태로 변경
  5. SHA256 형태로 변경한 결과를 다시 SHA256으로 변형
  6. 5번에서 나온 결과를 전부 뒤집은 다음 16진수로 변경

작업증명 성공 여부의 기준은 어떻게?

작업증명의 성공 여부 뿐만 아니라 작업난이도도 bits로 결정이 됩니다. 

작업증명 값 도출 방법

nonce로 작업증명을 성공하기 위해선 bits가 제시하는 숫자와 같거나 적으면 성공입니다. 그런데 bits에서는 지수와 가수를 이용하여 표현되고 있어 조금 복잡합니다. 예를 들어, 수학에서 큰 수나 작은 수를 표현할 때, 0.1234*10^5이나 0.1234*10^(-5)과 같이 표현합니다. 이를 더 친숙하게 표현하자면 처음 예를 든 수는 12,340이고 마지막 수는 0.000001234 입니다. 이때, 0.1234를 가수, 5나 -5를 지수라 표현합니다. 위에서 Little Endian으로 구한 bits는 ffff001d지만 Big Endian으로 바꿔서 1d00ffff로 계산해야합니다. Endian으로 계산한 수는 16진수 이므로 2자리씩 끊어서 이해해야 하므로 1d, 00, ff, ff로 파악해야 합니다. 여기서 bits는 첫 수인 1d를 지수로 보고 00ffff는 가수로 봐야 합니다. 즉, 1d는 진수, 00ffff는 가수로 봅니다. (가수의 경우, 앞에 소수점 0. 이 생략되어 있으므로 0.00ffff 라는 의미입니다.)

여기서 bits가 제시하는 숫자의 계산법은 00.00ffff*256^1d 입니다. 만약 지수가 01이였다면 256^1로 소수점이 우측으로 한칸 움직인 00.ffff가 됩니다. (* 여기서 주의할 점은 16진수이므로 16당 1칸이라 생각하면됩니다.)


다시 위 구하고자 하는 bits로 돌아오면 [00].[00][ff][ff]*256^1d 즉 [00].[00][ff][ff]*256^29 이므로 (1d를 https://ko.calcuworld.com/%EC%88%98%ED%95%99/16%EC%A7%84%EB%B2%95-%EA%B3%84%EC%82%B0%EA%B8%B0/ 에 넣어 10진수로 변환하면 29의 값이 나옵니다.) 우측으로 소수점을 29칸 옮기라는 소리입니다. 다시말해서 [ff][ff] 뒤에 [00]을 26번 작성하면 됩니다. 여기서 끝을 내면 28개로 이루어지기 때문에 도출한 28개의 값 앞에 [00]을 4개 더 붙인 [00][00][00][00][ff][ff][00][00]…[00] (32bytes) - (글자 수로는 64자)가 나오게 됩니다. 

결과적으로 bits가 제시한 숫자는 000000ff0000...00 (32bytes) - (글자 수로는 64자)입니다. nonce를 변경해가며 위 에서 나온 해시결과값이 이 값보다 작거나 같아야 작업증명이 성공하게 됩니다.

작업 난이도

블록 해쉬가 특정 숫자보다 낮게 나올 때의 nonce값을 찾아내는 것이 작업 증명이라고 위에서 설명을 했습니다. 앞에서 블록 해쉬는 32바이트의 숫자라고 했는데, 이를 가지고 설명하려면 너무 복잡하기 때문에 부호가 없는 1바이트로 가정합니다. 그러면 해시함수의 결과값은 0~255 사이의 결과가 나오게 됩니다. 만약 블록해시가 128보다 작아야 된다고 하면 128보다 작은 블록해시 결과값이 나올 확률은 128/256 이므로 50%의 확률입니다.

다시 블록해시 결과값이 64보다 작아야 한다고 하면 64/256이므로 25%의 확률로 nonce를 구할 수 있습니다. 여기서 예시를 든 128, 64라는 값이 bits입니다. 

보상은?

보상은 새로 발행되는 비트코인과 해당 블록에 포함되는 거래의 거래 수수료의 합입니다. 비트코인의 새로운 발행은, 채굴자가 블록을 처음 구성할 때 채굴자의 지갑으로 일정량의 비트코인이 입금되는 거래를 그 블록의 첫 거래(generation transaction)로 추가하는 방식으로 이루어집니다. 새로 발행되는 비트코인은 최초에 50BTC에서 시작해서 블록 체인에 21만개의 블록이 추가될 때마다 절반으로 줄어듭니다. 거래 수수료는 각 거래 당사자끼리 자율적으로 정할 수 있고, 거래가 블록에 추가되는 우선 순위를 결정하는데 거래 수수료가 입력값으로 사용되기도 합니다. 즉 보상은 nonce값을 찾아내고, 그 결과 새로운 블록을 블록 체인에 추가해서, 해당 블록에 포함된 모든 거래를 유효한 거래로 확정시켜준 대가라고 할 수 있습니다.

요약

  • PoW는 비트코인의 합의 알고리즘이 대표 케이스
  • 데이터의 위변조 방지


머클트리란?

머클트리(Merkle Tree) 혹은 '해시트리(Hash Tree)'라는 구조는 Ralph Merkle이라는 사람이 1979년에 만들어 낸 개념입니다. 다른 트리 알고리즘과는 다르게 머클트리의 목적은 빠른 검색이 아니라 데이터의 간편하고 확실한 인증을 위해 사용합니다. 머클트리의 최상위 부모노드(혹은 루트)는 머클루트라 부르며 블록체인의 원소역할을 수행하는 블록에서 저장된 트랜잭션들의 해시트리라 볼 수 있습니다.

머클트리는 데이터의 간편하고 확실한 인증을 위해서 SHA-256 암호화 기술(해시함수)를 사용하고 있습니다. 자세한 내용은 아래 머클트리 그림과 같이 설명하겠습니다.

SHA-256 암호화 (해시함수)란?

SHA-256은 암호화 기술로서 복호화가 되지 않는 단방향 암호화 기술입니다. 암호화된 결과는 16진수로 어떠한 수를 암호화 하더라고 결과의 크기는 64자입니다. 

http://www.convertstring.com/ko/Hash/SHA256 해당 사이트에 들어가 abcd 라는 값을 SHA256 암호화 하면 88D4266FD4E6338D13B845FCF289579D209C897823B9217DA3E161936F031589 라는 값이 나오게 됩니다.


만약 abcd가 아닌 aacd라는 값을 SHA256으로 암호화 하면 전혀 다른 값이 나오게 됩니다. 



이와 같이 입력된 값이 1개라도 다를 경우, 결과는 전혀 유추할 수 없습니다. 또한 입력할 글자의 수에 상관없이 결과의 크기는 64자입니다.

머클트리 구조


위 그림에서는 해시함수 64자를 전부 입력하기 힘들어 길이가 4인 값으로 대체했습니다. (원래는 4자가 아닌 64자입니다.)


블록체인에서는 먼저 각 트랜잭션(이하 TX1, TX2, ..., TXn)들을 SHA-256으로 암호화해 64자의 해시결과를 만들어 냅니다. 다음 각 인접한 노드들을 합한 다음, 다시 SHA-256으로 암호화해 해시결과를 만들어 냅니다. 이러한 과정을 단 1개의 해시가 나올때까지 반복합니다.

한마디로 수많은 거래내용들을 해시함수를 통해 압축하고 인접한 노드끼리 더한다음 다시 압축 과 같은 과정을 반복해 나갑니다. 모든 결과 값은 이전 출력들을 해시함수를 거쳤기 때문에 입력이 하나라도 달라지면 최종결과인 머클루트가 달라지게 됩니다.

이러한 특성으로 블록에서 거래변조가 일어났는지를 확인할 수 있으며, 거래내용이 아무리 길어도 해시함수를 거친 결과는 64자이므로 블록의 용량을 획기적으로 줄일 수 있게 됩니다.

머클트리를 사용한 검증법

지금부터 비트코인을 예를 들어 검증하는 방법을 설명하겠습니다. 머클트리 검증에 앞서 풀 노드와 라이트 노드라는 개념이 나오는데 풀노드는 제네시스 블록부터 지금까지의 블록 즉, 블록체인 전체를 가지고 유지하는 노드입니다. 라이트 노드는 블록체인 전체가 아닌 몇몇 블록만 가지고 있으며 풀노드에게서 필요한 정보를 받아서 유지하는 노드입니다.

만약 아래의 그림과 같이 라이트 노드에서 가장 마지막 값인 1e3a 해시값과 머클루트인 af3d 해시값만 가지고 있다고 가정하고 1e3a라는 거래내역이 진짜인지 확인을 어떻게 할까요?



방법은 풀노드로 부터 검은 네모박스인 43bc, 143c, 89fe의 정보를 받아 해시 함수에 차례대로 넣어 계산을 진행합니다. 아래의 그림과 같이 검은 네모박스를 알게되면 인접한 노드끼리 더한 뒤 해쉬를 통해 상대값을 알게되어 머클트리를 진행해 나갈 수 있게 됩니다. 이와 같은 경로를 머클경로라 합니다.

만약 검은 네모박스가 아닌 파란 네모박스를 알게 된다면 해시경로를 진행해 나갈 수 없어 머클루트가 진짜인지 알 수 없게 됩니다. 이러한 과정을 통해 도출된 결과가 머클루트인 af3d의 값과 동일하지 않다면 1e3a 해시값은 거짓거래로 판명이 납니다.



요약

  • 머클트리는 SHA-256 암호화 (해시함수)를 사용
  • 머클트리를 이용하면 빠르게 데이터 검증을 할 수 있고 트리 저장 용량도 줄일 수 있음
  • 머클트리는 라이트 노드에서 거래를 검증하기 위해 사용됨


블록체인(Blockchain)

블록체인은 최초의 블록(Genesis Block)부터 시작해서 바로 앞의 블록에 대한 링크를 가지고 있는 링크드 리스트인 자료구조입니다. 다시말해 블록과 블록을 체인으로 이어준 형태입니다. 블록체인에서 사용되는 블록은 일정 시간마다 생성이 됩니다. (비트코인의 경우 10분에 한 번씩 생성)

즉 여러 건의 거래내역을 하나의 블록으로 묶어 기존에 생성된 블록에 체인처럼 계속적으로 연결한 구조를 의미합니다. 블록의 집합체인 블록체인은 여러 노드에 걸쳐 분산되어 저장 및 관리되며 모든 거래 정보를 포함하는 거대한 분산 장부 또는 공통장부(원장: Ledger)관리 기술이라 할 수 있습니다.

블록(Block)

블록이란 블록체인의 원소 개념으로 다수의 거래정보의 묶음을 의미합니다. 블록은 Height라고 불리고 있습니다. 블록체인을 길게 이어진 수평선으로 보는 것이 아니라 한 칸 한 칸 쌓아나가 탑의 형태로 구성된다고 생각하여 Height라는 말을 쓴다고 합니다. 하지만 이 Height는 정확한 블록의 이름이 아닙니다. 블록의 정확한 이름은 TXID라 불리는 블록의 해시값입니다. 이 블록의 해시값은 블록의 헤더 정보를 모두 합산한 후 SHA256으로 변환된 값입니다.

블록 구성요소

블록은 블록 헤더와 거래 정보, 기타 정보로 구성됩니다. 여기서 거래 정보와 기타 정보는 블록 바디라 볼 수 있습니다. 거래 정보는 입출금과 관련한 여러가지 정보를 가지고 있고 기타 정보는 블록 내에 있는 정보 중에서 블록 헤더와 거래 정보에 해당하지 않는 정보를 말하며, 블록 해쉬 계산에 사용되지 않습니다.

블록 구조

블록해시 (Block Hash)

블록 해시는 블록의 식별자 역할을 합니다. 블록 해시는 블록의 헤더 정보인 버전, 이전 블록 해시, 머클 루트, 타임, bits, 논스 정보를 모두 더한 후 SHA256으로 2번 변환한 결과 값입니다. 블록해시여서 블록 전체의 해시값으로 생각될 수 있지만, 블록 헤더를 해시한 값입니다.

블록 헤더 (block header)

블록 헤더는 versionpreviousblockhashmerklehashtimebitsnonce 6개의 정보로 구성되어 있습니다.

  • version: 소프트웨어/프로토콜 버전

  • previousblockhash: 블록 체인에서 바로 앞에 위치하는 블록의 블록 해쉬

  • merklehash: 개별 거래 정보의 거래 해쉬를 2진 트리 형태로 구성할 때, 트리 루트에 위치하는 해쉬값

  • time: 블록이 생성된 시간

  • bits: 난이도 조절용 수치

  • nonce: 최초 0에서 시작하여 조건을 만족하는 해쉬값을 찾아낼때까지의 1씩 증가하는 계산 회수

버전 (version)

해당 블록의 버전입니다. 현재 이 블록 헤더를 만든 비트코인 프로그램의 버전 정보입니다.

이전블록해시 (previousblockhash)

이전 블록 해시 정보는 이전 블록의 주소 값을 가리키는 요소입니다. 각 블록의 헤더 정보에는 이전 블록의 해시값을 갖고 있기 때문에 아래의 그림과 같이 블록끼리 연결될 수 있습니다.


머클해시 (merkle root)

머클해시는 블록의 바디 부분에 저장된 트랜잭션(거래 정보)들의 해시 트리입니다. 각 트랜잭션과 가까운 노드끼리 쌍을 지어 해시 값을 구하고 최종적으로 구해진 해시 값이 머클해시 값입니다. 머클해시 값을 통해 단일 블록 내에 존재하는 트랜잭션의 무결성을 검증할 수 있으며 머클해시 값을 이용하여 블록의 해시 값을 생성하였기 때문에 블록해시의 무결성도 함께 검증할 수 있습니다. 쉽게 말해 해당 블록이 유효한지에 대한 무결성을 검증하기 위한 요소가 머클해시입니다.

아래의 그림은 머클해시와 블록해시를 구하는 과정을 나타낸 그림입니다.


완료된 거래정보의 변경이 사실상 불가능한 이유

거래 정보의 해시값은 해당 거래가 포함된 블록의 머클해시 계산에 입력값으로 사용되고, 머클해시는 블록 해쉬의 계산에 입력값으로 사용됩니다. 블록 해시는 다음 블록(A라 하면)의 previousblockhash 값으로 저장되며, previousblockhash은 A 블록의 블록 헤더 정보로서, A 블록의 블록 해쉬를 계산하는데 입력값으로 사용됩니다. 따라서, 거래 정보가 변경되면 merklehash가 변경되고, merklehash가 변경되면 블록 해쉬가 변경되고, 블록 해쉬의 변경은 다음 블록의 블록 해쉬 변경으로 연쇄적으로 이어지게 됩니다. 그리고 블록 해쉬는 작업 증명(PoW)의 해답(nonce값)을 찾아내야 구할 수 있으므로, 거래 정보를 변경한 블록부터 그 이후의 모든 블록을 순서대로 다시 채굴해야 합니다.

예를 들어, 블록 하나를 채굴하는데 평균 10분이 소요되고,  현재 총 블록 수가 약 40만 블록이라고 할때, 최초의 원조 블록인 Genesis 블록에 포함된 거래를 변경하면 약 400만 분, 약 7.6년의 시간이 소요됩니다. 만약 거래를 변경한다 해도 새로운 블록들이 평균 10분 마다 하나 씩 계속 생성되므로 예상 소요시간은 계속적으로 늘어나기 때문에 이를 모두 뒤집는 것은 사실 상 불가능합니다. 즉, 완료된 거래 정보를 변경하려면, 변경하려는 거래 정보가 포함된 블록부터 그 이후의 모든 블록을 순서대로 다시 채굴해야 하는데, 이는 많은 시간이 소요되고, 그 동안 다른 노드들에 의해 블록이 계속 추가되므로, 완료된 거래 정보의 변경은 현실적으로 사실상 불가능합니다.

타임 (time)

해당 블록의 대략적인 생성시간을 의미합니다. 타임 스탬프는 유닉스 기준일 자로 표시되며 1970년 1월 1일 자정부터 경과한 시간을 초 단위로 계산한 값입니다.

bits

bits는 난이도 해시 목표 값을 의미하는 지표입니다.

nonce

블록을 만드는 과정에서 해시 값을 구할 때 필요한 재료 역할을 수행합니다. 

요약

  • 블록체인은 블록과 블록을 연결한 구조
  • 블록체인에서 블록은 여러 건의 거래내역을 가지고 있음
  • 블록의 구성요소는 헤더와 바디로 나뉘어져 있음


+ Random Posts