Nullorm

블록체인 가상화폐를 대표하는 비트코인은 채굴, 검증 등 모든 수학적 과정 안에 이 SHA-256이라는 알고리즘이 등장하는 것으로 보인다. 

사실 해시알고리즘까지 알아야하나? 싶긴 하지만 그래도 일단 코인수학&암호학 이라는 카테고리를 만든 김에 첫 번째 수학적 내용으로 적절해보이긴 해서 공부해보았다.

1. SHA-256?

SHA-256은 메시지, 파일 암호화 또는 무결성검증 등에 널리 사용되는 일방향 암호화 해싱 알고리즘이다. 

대상 데이터를 256-bit 길이의 hash값으로 변환하는 역할을 한다. 

해시 알고리즘의 가장 큰 특징은 암호화 대상 데이터(평문)의 값이 아주 조금만 달라져도 결과값(암호문)이 크게 달라지는 것이다.

한번 예시와 함께 살펴보자.

2. 예시 (python)

import hashlib

data1 = "helloWorld"
res1 = hashlib.sha256(data1.encode()).hexdigest()
data2 = "hellWorld"
res2 = hashlib.sha256(data2.encode()).hexdigest()

print("res1:", res1)
print("res2:", res2)

비슷한 두 data를 SHA-256으로 암호화했는데, 너무나도 다른 결과값이 출력되었다.

res1: 11d4ddc357e0822968dbfd226b6e1c2aac018d076a54da4f65e1dc8180684ac3
res2: 83c111ea0677450e0293e71274de14f832a2a0293192a8bff29fee2fb7a86ed4

이를 통해 hash함수의 특징인 일명 '눈사태 효과'를 확인할 수 있었다.

3. SHA-256의 특징

• 우선 SHA-256은 블록체인에서 가장 많이 채택하여 사용되고 있다.
• 단방향성: 평문을 암호화했을 때, 다시 평문으로 복호화할 수 없다. 평문은 임의의 길이의 메시지이며, 이를 암호화하면 256-bit의 축약된 메시지로 출력된다. 데이터의 수정/변경을 검사하는 데 사용할 수는 있지만 인증은 불가능하다. 인증을 위해서는 메시지 인증 코드(MAC)과 디지털 서명(전자서명)이 요구된다.
• 안전성: 이전버전인 SHA-1의 경우, 해시 충돌이 발견된 사례가 있기 때문에, 이와 크게 다르지 않은 256의 경우에도 안전성이 완벽하다고 하기는 어려울 것이다. 하지만, 양자컴퓨터와 같은 초성능 컴퓨터가 발명되기 전까지는 뚫기 어려울 것으로 보고 있다.
• 블록체인에서는 SHA-256의 취약점이 발견되는 일이 있다고 하더라도, 하드포크와 같은 알고리즘 개선 기법을 이용하면 이러한 문제를 해결할 수 있다.

4. SHA-256의 구조

사실 SHA-256의 구조라기보다는 해시함수 암호화 과정의 구조라고 할 수도 있을 것 같다.

1. 전처리

전처리 단계에서는, 메시지를 512bit 블록으로 처리하는 과정을 거친다. 우선 메시지는 메시지 길이를 나타내는 64비트 값으로 끝나도록 패딩되고, 최종적으로 길이가 512비트의 배수가 된다.

2. 초기 해시 값 구성

SHA-256은 초기 해시 값으로 시작하는데, 이 값은 8개의 32bit word로 구성되어있다. 

3. 메시지 스케줄링

각 512비트 메시지 블록은 64개의 32bit 워드로 확장된다. (진짜 '확장'임) 이렇게 메시지 스케줄 배열이 만들어지고, 초기 16개의 워드는 메시지 블록에서 직접 가져온 것이며, 나머지 48개는 특정 연산을 거쳐서 만들어진 것이다.

4. 압축함수 실행

초기 해시값과 메시지 스케줄 배열을 사용해서 SHA-256 알고리즘은 64라운드의 압축함수를 실행함(64라운드는 좀 많네..) 각 라운드에서는 주요 두 가지 연산을 실행하게 된다. 확장된 메시지와 라운드 상수를 포함하는 모듈라 덧셈, 그리고 논리 함수가 수행된다고 한다. 그 결과, 8개의 해시값이 업데이트 된다.

이 부분을 자세히 다뤄보고싶긴 하지만,,, 뭔가 해시함수에는 흥미가 안생긴달까... 나중에 좀 수학적으로 재밌는것들 위주로 깊게 파고들어가보겠다..!! ㅎ

5. 최종 해시값 생성

모든 메시지 블록이 처리되면, 마지막 블록의 압축 결과는 이전블록의 결과와 함쳐져 최종 해시값을 형성한다.최종 값은 8개의 32bit word로 구성되어, 총 256bit 크기의 해시 값을 결과로 얻게 되는 것이다.

이렇게 대략적으로 SHA-256해시에 대해 좀 알아보았다.

다음부터는 암호 프로토콜과 같은 내용이나, 공개키 암호 시스템 등에 대해서도 알아보도록 하자.

지난번 포스팅에서 다뤘었다. 

대체 PoW가 무엇인가!!! 작업증명이 그래서 뭔데!!!

자. 지금부터 한번 시작해보도록 하자. 라는 말을 쓰는 지금 시점에서, 나는 작업증명이 뭔지 모른다.

따라서, 이 글을 읽는 사람들에게 누구보다 모르는 사람의 관점에서 잘 설명할 수 있지 않을까? (라는 희망.)

1. 서론

블록체인 네트워크에서 비트코인은 블록체인에 새로운 블록을 추가하는 방식으로 조폐(화폐를 제조) 및 송금을 한다.

작업증명은 이 조폐 및 송금에서 사용되는 트랜잭션(Transaction: 거래)시에 이를 거래하는 방법이다. 

나카모토 사토시의 비트코인 백서에는 이런 말이 있었다(비트코인 백서 서론)

필요한 것은 신뢰 대신 암호학적 증명(cryptographic proof)에 기반해, 거래 의사가 있는 두 당사자가 신뢰받는 제삼 자를 찾지 않고 서로 직접 거래하게 하는 전자 결제 시스템이다.

즉, 거래를 중개하는 중개 플랫폼(은행 등)을 신뢰해야만 개인 간의 거래가 가능했던 이전의 방식이 아닌, 암호학적 증명에 기반하겠다는 말이다. 이는 곧, 사람, 시스템을 신뢰하는 데에는 어떻게든 오류가 생길 수 있으니, 절대적인 수학을 믿겠다는 말로 들린다. 

2008년 글로벌 금융위기 사태 직후, 금융위기 조사위원회(FCIC)는 525페이지 분량의 보고서에 이런 말이 있다.

"당시의 위기는 인간의 행동과 무대책의 결광지, 천재지변이나 컴퓨터 모델 문제가 아니다. 셰익스피어를 인용하자면 잘못은 저 별들이 아니라 우리에게 있다." 즉, 2009년의 나카모토 사토시는 인간에 의해 만들어진 금융시스템을 신뢰하기보다는, 보다 믿을 수 있는 수학적(암호학적 증명) 방법에 기댔다고 볼 수 있겠다.

그렇다면, PoW는 대체 뭘까?

 1. PoW(Proof of Work: 작업증명)

비트코인의 전체적인 구조를 살펴보자.

자, 시장이 처음 생기면 일단 어떻게 해야하는가?

1. 화폐를 만든다(찍는다)

2. 화폐를 시장에 공급한다.

3. 시장 구성원들이 화폐와 재화를 거래하며 화폐를 거래한다.

전체적으로 보면 이러한 구조가 될 것이다. 그런데, 각각의 단계를 어떠한 주체가 담당하는지 살펴보자.

1. 중앙은행에서 화폐를 발행한다.

2. 은행이 시장에 화폐를 공급한다.

3. 구성원들이 화폐를 거래한다(전자화폐의 경우, 이중지불문제와 보안을 위해 은행의 중개가 필요)

결국, 모든 과정에서 은행은 필수불가결의 요소이다.

하지만, 비트코인은 무엇인가?

바로 은행이 존재하지 않는, 은행을 신뢰하지 않는, 수학을 믿는 전자화폐이다. 이러한 과정들에서, 은행을 대신할 수 있는 요소로 등장하는 것이 바로 PoW, 작업증명이다.

작업증명이 비트코인에서 어떠한 기능을 하는지 가볍게 일단 한번 보자.

1. 채굴자는 화폐를 발행하고 이를 시장에 공급한다.(물론 바로 공급을 하지 않을 수 있겠지만.. 이들도 돈을 벌어야지)

2. 구성원들이 화폐를 거래한다.

해당 두 과정이 위의 세 과정을 압축했다고 볼 수 있다. 작업증명(PoW)는 이 두 과정 모두에서 작동한다.

우선, 조폐(1번)의 과정에서는, 화폐 발행인(채굴자)에게 일(채굴)을 했다는 것을 증명하도록 하여 화폐를 발행한다.

중앙집권화되지 않은 탈중앙화된 블록체인의 조폐 과정에서는 처음 만들어진 알고리즘 이외에는 누가 얼마의 화폐를 받을 지 결정할 수 있는 중앙 권력이 없기 때문에 모든 참여자들이 자동으로 동의할 수 있는 방법이 필요하다.

그렇다면, 채굴자는 어떤 문제를, 어떤 해시함수를 계산한다는 것일까? 간단하게 그림으로 한 번 알아보자.

비트코인의 작업증명 방식을 간단하게 그림으로 나타내보았다.

우선, 작업증명은 SHA-256과 같은 해시연산을 거쳐 이루어지는데, 

과정은 이러하다.

Hash(이전 블록의 해시값 || 생성할 블록의 트랜잭션 data || 임의의 Random한 Nonce) < 목표값

을 달성할 경우, 작업증명에 성공했다고 보는 것이다.

이와 관련하여 백서에서는 어떻게 이야기하는지 살펴보자.

우리는 타임스탬프 네트워크용으로 블록의 해시에 주어진 0 비트들을 모두 발견할 때까지 블록 안에 임시값을 증가시키는(incrementing a nonce) 것으로 작업증명을 구현했다.

이 말이 위에서 한 말과 같은 말로 받아들이면 될 것이다.

이게 대체 뭔 과정이길래 이정도만으로도 작업증명이 된다는 것일까?

답은 바로 Hash함수의 일방향적 특성에 있다.

수학적(암호학적)으로, 해시(Hash)함수는 일방향함수이기 때문에, 이를 역산하는 것이 무차별 대입(Brute Force)이외에는 방법이 없다는 점에 착안하여, 모든 채굴자가 해시함수를 계산해 가장 먼저 계산한 사람이 새로 발행되는 비트코인을 받아가는 구조이다.

또한 작업증명(PoW)는, 다수결의 체인의 대표성을 결정하는 문제도 해결한다. 만약, 1 IP당, 1표에 기반한 다수결로 검증을 진행하게 된다면, 한번에 수많은 IP를 할당할 수 있는 누군가(악의적인 공격자)에 의해 해당 네트워크 전체가 장악될 수 있다. 위에서 소개한 다수결은 기본적으로 CPU당 1표이다. 다수결의 결과는 가장 많은 자원이 사용된 작업증명들의 가장 긴 체인이 된다(즉, Hash Rate가 가장 높은 체인이 가장 긴 체인이 된다.) 정직한 노드들에 의해 다수의 CPU파워가 통제된다면, 가장 정직한 체인이 가장 빠르게 늘어나 다른 경쟁 체인들을 압도할 것이다.

또한, 과거 블록을 수정하려면 공격자는 해당 과거 블록의 값에 대한 작업증명을 재수행해야하고, ( Hash(해당 블록의 이전 블록 해시 값 + 변경하고자 하는 데이터 + Nonce) 를 다시 해야함.) 또한, 해당 블록 이후의 모든 타임스탬프의 블록에 대하여 모든 연산을 재수행해야 하는 문제가 생긴다. 또한, 이러한 작업을 가장 정직한 노드들의 작업 속도를 따라잡아야 그것이 가장 무결한 노드라는 것을 인정받을 수 있다. 

따라서, 비트코인은 그 구조상 블록의 수가 늘어날수록 블록의 위/변조가능성은 거의 0에 수렴하게 된다는 것을 알 수 있다.

또한, 실제로 발생한 문제이기도 하지만, 채굴자들은 자원을 아끼기 위해 기존 CPU의 수만배 파워를 내는 채굴기를 개발해내었다. 이러한 상황에서 채굴의 난이도는 상대적으로 쉬워질 수 밖에 없기 떄문에, 초기 알고리즘은 채굴의 난이도 (위 그림에서는 목표 값)를 시간당 평균 블록 수에 따른 평균 목표값을 조정하여 결정하도록 하였다.

즉, 블록들이 너무 빠르게 생성된다면 채굴 난이도는 높아진다는 것이다(목표값이 낮아진다는 것이다.)

3. 마치며...

이렇게 작업증명에 대한 기본적인 개념들을 다루어보았다.

다소 수학적인 내용이 등장할 것이라고 예상했었지만, 해시함수 이외에는(이것도 별 수학적으로 접근하지는 않았지만...) 그런 내용은 없었던 것 같다.

작업증명(Proof of Work) 이외에도 지분증명(Proof of Stake)라는 개념이 존재하는데, 이는 나아아중에 다뤄보도록 하겠다.

글 읽어주셔서 감사하옵니다^^

지난번 게시물에 이어서 확장 유클리드 알고리즘을 시작해보도록 해보아요...

지난 게시물에서, 유클리드 알고리즘에 의해

GCD(a, b) = GCD(b, r) 이 성립한다는 것을 알았음.

(※  GCD : greatest common divisor : 최대공약수, a % b = r)

확장 유클리드 알고리즘은 최대공약수 gcd를 구하는 것 뿐만아니라, 정수해를 가지는 부정방정식

ax + by = c가 주어질 때, a, b의 최대공약수를 구함과 동시에 이 방정식을 만족하는 x, y를 찾아주는 알고리즘이다.

당연히 식이 하나에 두 변수가 있으므로 unique한 해를 찾는다기보다는 무수히 많은 (x, y) 쌍에  대한 규칙을 찾는 것이라고 보면 될 것이다.

코드로 구조를 살짝 표현 해볼까?

pseudo code 로 작성된 확장 유클리드 알고리즘.

r과 old_r을 각각 b와 a라고 두고(기존 항등식에서 사용하던 a,b와 같음), 나머지 변수들을 치워보면은 기존의 유클리드 알고리즘에서 사용하던 코드와 일치한다는 것을 알 수 있다.

이제, 여기에 s와 t가 추가되었는데, 이들은 초기값은 반드시 0, 1 / 1, 0으로 고정되고, 그 이후는 r. 즉, a, b와 비슷한 방식으로 처리되게 됨.

이걸 한번 시뮬레이션 해보자!

161x + 28y = 7을 계산해보자.

X_new는 이번 사이클에서 새롭게 구해지는 값을 말한다.

q는 이번 사이클에 구해지는 몫이다.

초기 세팅은 이러하다.

- q =  old_r / r

- r_new = old_r - r * q

- s_new = old_s - s * q

- t_new = old_t - t * q

old_r = a, r = b로 세팅하고(그저 초기값일 뿐이랍니다), old_s, sm old_t, t는 1, 0, 0, 1로 각각 고정시켜놓는다.

첫 스텝에서 old_r(a)을 r(b)로 나눈 몫 q = 5, r = 21이다.

이 예시에서는 a, b가 양수라서 별 상관이 없긴 하지만, 원래 확장유클리드 알고리즘은 음수에서도 작동을 해야한다. 그래서 r_new는 반드시 0 이상 abs(r) 미만의 정수가 되어야 한다(다들 아실거라고 믿고..)

예를 들어 7/(-3)을 한다고 하면 그 몫은 -2가 아니라 -3이라는 말이다. 7 - (-3 * -3)를 해야 나머지가 2. 즉, 0 이상 3 미만의 값으로 들어오기 떄문이다.

자 여기까지 왔으면, 나머지 s와 t를 구해준후

한칸씩 왼쪽으로 밀어서 두 번째 사이클을 준비해준다.

이런 작업을 r = 0이 될 떄까지 반복해주면 우리가 찾던 값이 등장하게 되는 것이다.

이러한 과정을 거친 결과 r = 0인 사이클에서, old_r = GCD인 것을 알 수 있고,

ax + by = c의 값을 구할 수 있는 것이다.

이 때,

x = old_s = -1

y = old_t = 6

c = GCD(161, 28) = 7임을 알 수 있다.

결과 : 161 * (-1) + 28 * 6 = 7

이렇게 확장 유클리드 알고리즘을 간단하게 알아보았다 ^^

s_new 와 t_new를 구하는 과정이 r_new를 구하는 과정과 같은 이유는

같은 연산을 적용해나가면서 값을 찾아주기 위함이다.

이걸 적용해볼만한 문제를 보게 된다면 아래 덧붙이도록 해보도록 노력해보도록... 해보겟슴미다.