합의 알고리즘

합의 알고리즘은 블록체인과 같은 p2p 시스템에서 각 노드간 정보 도달의 시간차이가 있을 때 참가자들의 하나의 결과에 대한 합의를 얻기 위한 알고리즘입니다. 블록체인에서는 생성된 블록의 정당성을 검토하고 그 불록을 전체 블록체인에 반영하기 위해서 합의 알고리즘을 사용합니다.

작업 증명(PoW, Proof of Work)

PoW는 풀기 어려운 문제를 가장 빨리 해결한 사람에게 블록을 생성할 수 있는 권한을 주고 그 보상으로 코인을 제공하는 방식입니다. 비트코인의 경우는 무작위로 생성된 난수를 맞추는 문제를 제공하고 있으며, 약 10분 정도에 풀리도록 난이도 조절을 하고 있습니다. 난이도 조절은 이전 문제를 푸는데 걸리는 시간을 참고하여 너무 빨리 푼 경우는 난수의 자릿수를 늘리고, 너무 오래 걸린 경우는 난수의 자릿수를 줄이는 식으로 조절합니다.

또한 각 노드들의 데이터 전송 시간 차이로 인해 체인이 분기되는 경우가 발생할 수 있으며, 그런 경우 몇 번의 블록을 더 생성한 다음 가장 긴 체인을 올바른 것으로 판단하고 있습니다. 이 경우 짧은 체인에 있던 블록의 내용은 없던 일이 되기 때문에 계좌의 잔액이 바뀌거나 거래 자체가 없어지는 경우도 발생할 수 있습니다. 비트코인에서는 이런 경우를 방지하기 위해 거래가 확정되더라도 6블럭 정도를 추가로 기다리지 않으면 다음 거래를 할 수 없도록 제한을 두는 등의 방법을 적용하고 있으며, 이를 결제 완전성(Settlement Finality) 또는 파이널리티 불확실성(Finality Uncertainty)이라고 부릅니다. 파이널리티 불확실성은 금융 시스템에 도입되기 어려운 이유 중 하나가 되고 있습니다.

PoW는 다수결로 결정을 내리는 알고리즘이기 때문에 ‘51% 문제’가 발생할 수 있습니다. 블록체인은 해시 코드들의 체인이기 때문에 기존 내역을 변경하는 것은 상당히 어렵고, 특히 비트코인의 경우 모드 노드가 풀 가동시 약 10분에 하나의 해시값을 찾을 수 있을 정도이기 때문에 기존 내역을 변경하는 것은 불가능에 가깝습니다. 하지만, 51% 공격의 문제는 새로 생성하는 블록을 공격하는 점에 있습니다. 51퍼센트 공격을 하는 구체적인 방법은 다음과 같습니다.

• 해시 파워의 절반 이상을 가진 노드가 마이닝을 통해 해시값을 찾더라도 이웃 노드들에게 전파를 하지 않음
• 그리고 그 다음 블록을 계속해서 생성(과반수 이상의 해시 파워를 갖고 있기 때문에 다른 마이너들보다 긴 블록체인을 만들 수 있는 가능성이 높습니다.)
• 비트코인에서는 체인 분기시 짧은 체인은 파기하며, 가장 긴 체인을 올바른 체인으로 선정하기 때문에 해커들의 체인이 올바른 체인이 될 가능성이 높음

또한 PoW는 반복적인 연산을 계속해서 특정 값을 찾아내기 때문에 불필요한 연산을 많이 하게 되며 그로 인한 리소스 낭비(대표적으로 전기비)가 심하다는 단점이 있습니다. 또한 성능적인 제한도 있어 실시간성이 필요한 업무에는 적합하지 않습니다.

PoW는 모든 노드들이 트랜잭션 실행 결과를 검토해야 하기 때문에 각 노드들은 모든 블록 정보를 보유해야 합니다. 2016년 12월 기준으로 비트코인의 전체 블록들의 용량은 약 90기가 이상이었고 꾸준히 증가하고 있습니다. 향후에도 블록을 쌓을 때마다 용량이 증가해야 하고 1 블록의 용량 제한이 풀리거나 합의 시간이 단축되는 경우에는 전체 용량 증가 속도도 더 증가할 가능성이 있습니다.

이와 같이 PoW는 많은 단점들을 갖고 있는 합의 알고리즘이기 때문에 그 한계가 명확하며, 새로운 대안을 찾는 시도가 계속되고 있습니다.

지분 증명(PoS, Proof of Stake)

PoS는 PoW의 단점을 극복하기 위해서 나온 대안 중 하나이며, 블록을 생성할 수 있는 확률을 각 노드가 갖고 있는 토큰의 지분에 비례하도록 하는 알고리즘입니다. 합의에 필요한 리소스가 PoW에 비해 비약적으로 적으며, 속도 문제도 훨씬 개선이 된 알고리즘입니다. 하지만 PoS도 다음과 같은 문제점들을 갖고 있습니다.

PoS는 지분이 많을 수록 더 유리해지는 방식이므로, 각 노드들이 토큰을 수집하기만 하고 사용하지 않으려는 경향이 나타날 수 있습니다. 그래서 사용하지 않는 오래된 토큰에 대해서는 지분 평가를 떨어뜨리는 ‘Proof of Stake Velocity’라는 방식이 제안되고 있습니다.

또한 필요한 리소스 코스트가 너무 저렴하여 ‘아무 것도 수행하지 않는 문제(Nothing at Stake)’가 발생할 수 있습니다. 만약 체인이 분기되는 상황이 발생하게 되면, 각 노드들은 양쪽 체인 모두에서 같은 양의 지분을 갖고 있게 됩니다. 즉, 양쪽 분기 모두 대등한 체인이 되기 때문에 굳이 누군가 나서서 사태를 수습할 이유가 없습니다. 또한 양쪽 체인에 베팅이 가능하기 때문에 체인 분기를 고의로 노리고 계속 시도할 수 있다는 단점도 있습니다.

그리고 블록체인의 첫 번째 블록에 해당하는 제네시스 블록 시점에서 지분이 100%에 달하기 때문에 시스템을 개시한 사람은 몇 번이고 전체 블록을 다시 만들어낼 수 있다는 치명적인 문제가 있습니다. 그 외의 각 노드들도 지분만 갖고 있으면 그 시점부터 다시 시작하는 것이 가능하기 때문에 PoS만으로는 위변조를 막을 수 없습니다. 블록을 생성하는 코스트가 너무 낮기 때문에 이전 블록들로 거슬러 올라가서 현재까지의 모든 체인을 위변조할 가능성도 있습니다.

PBFT(Practical Byzantine Fault Tolerance)

PoW나 PoS와 마찬가지로 비잔틴 문제 해결로부터 시작되었지만, PoW나 PoS와는 달리 결제 완결성과 성능 문제를 해결한 합의 알고리즘입니다. 다만 모든 참가자를 알아야 하기 때문에 퍼블릭 블록체인에서 적용하기는 어렵습니다. 하이퍼레저(Hyperledger)나 Eris 등의 프라이빗 블록체인에서는 PBFT 알고리즘을 많이 채택하고 있습니다.

PBFT는 모든 노드를 알고 있어야 합니다. 노드 중 하나가 리더(Primary)가 되며, 자신을 포함해서 모든 노드들에게 요청을 보냅니다. 그리고 그 요청에 대한 응답을 집계한 다음 다수결을 이용해 블록을 확정합니다. PoW나 PoS와는 달리 의사 결정을 먼저 한 다음 블록을 생성하기 때문에 블록체인의 분기가 발생하지 않습니다. 따라서 결제 완결성을 지원하며, PoW처럼 해답을 찾기 위한 반복적인 연산 과정이 없기 때문에 필요한 리소스 코스트가 낮으며 훨씬 더 좋은 성능으로 동작합니다.

악의적인 사용을 하려고 해도 과반수 획득을 해야 하며, 누구나 노드로 참여할 수 있는게 아니라 허가된 노드만 참여하기 때문에 과반수 획득이 쉽지 않습니다. 또한 리더가 악의적인 행동을 했다고 판단이 되면 다수결을 통해 리더를 교체할 수도 있기 때문에 매우 강력한 보안을 갖고 있습니다.

하지만, 모든 노드를 알고 있어야 하고 전원의 의사 소통이 필요하기 때문에 노드가 증가할 수록 성능은 감소합니다. PoW나 PoS는 수천 개의 노드를 운영할 수 있지만 PBFT는 수십 개의 노드가 한계입니다.

Sieve

Sieve는 IBM에서 고안한 PBFT를 확장한 알고리즘입니다. 하이퍼레저에도 채택되어 있었으나 2016년 7월 대상에서 제외되었습니다.

실행 결과 전송과 집계 결과 전송으로 흐름을 나눈 것이 특징이며 합의를 형성하기 전 단계에서 실행 결과를 검토해 결과가 다른 경우 취소(Abort) 시킵니다. 각 노드들의 실행 결과가 다른 것을 초기에 탐지하고 싶을 때 유용한 알고리즘입니다. 집계 결과 전송에는 PBFT를 사용하는 경우가 많습니다.

Paxos

가장 유명한 합의 알고리즘 중 하나입니다. 단순하지만 합의 형성에 특화되어 있어 실제로 구현하기에는 어려움이 많습니다.

Paxos의 특징은 과반수의 동의를 얻었다면 그 동의 내용이 나중에라도 변경되는 일이 없다는 점입니다. 리더에 의해 합의 형성을 수행하지만 비잔틴 장애 허용 모델은 아니기 때문에 리더가 악의적인 행동을 하거나 멤버가 거짓으로 신고한 경우 정상적인 동작을 하지 않기 때문에 악의를 가진 참가자가 존재할 수 있는 환경에서는 적합하지 않은 알고리즘입니다.

HTTP에 대한 이해

HTTP는 월드 와이드 웹(World Wide Web)에 대한 어플리케이션 레벨의 통신 프로토콜입니다. 텍스트 기반으로 되어 있지만 강력합니다.

HTTP는 FTP나 Telnet처럼 연결 지향 프로토콜(Connection-Oriented Protocol)이 아닌, 상태가 없는 프로토콜입니다. 동일 서버에 대해 요청을 여러 번 했을 때, 각 요청들은 이전 요청들에 대한 기록을 전혀 알 수 없습니다. 연결 지향성 프로토콜의 경우는 끊임없이 서로간의 메세지를 체크하기 위해 연결을 계속 유지시켜야 하지만, HTTP는 그렇지 않습니다.

HTTP는 원래 HTML만 전송하도록 설계되었습니다. HTTP 0.9 버전에서는 GET 메소드만 지원했습니다.

HTTP Request

HTTP는 요청(Request)과 응답(Response) 프로토콜입니다. HTTP 요청은 다음과 같은 구성으로 이루어져 있습니다.

1. 요청
2. 빈 라인 또는 요청 헤더
3. 빈 라인
4. 메시지 본문

예를 들면 다음과 같은 형태로 이루어져 있습니다.

GET /blog/categories/ HTTP/1.1
HOST: snowdeer.github.io
User-Agent: Mozilla/5.0
(Empty Line)

위 예제에서 첫 번째 라인이 요청 메소드이며, 그 다음은 URI(Uniform Resource Identifier)입니다. 그리고 마지막으로 HTTP 버전을 명시합니다.

두 번째 라인과 세 번째 라인은 요청 헤더입니다. 마지막 라인의 경우 비어있는데 메시지 본문이 없더라도 반드시 포함되어야 합니다.

HTML 지원 메소드

GET 메소드는 HTTP의 기본적인 요청입니다. POST의 경우 HTML 2.0부터 지원하기 시작했습니다. HTML은 GET과 POST 이 외의 메소드는 별도로 지원하지 않습니다. HTML 5의 초안에서 PUT과 DELETE 메소드를 추가로 지원하기로 했었으나 마지막에는 지원하지 않기로 결정했습니다.

HTTP Response

HTTP Response는 서버가 클라이언트에게 전달하는 메시지이며 다음과 같은 구성으로 이루어져 있습니다.

1. 응답 상태
2. 0개 혹은 그 이상의 응답 헤더
3. 빈 라인
4. 메시지 본문

HTTP 응답 상태는 다음과 같이 5 종류로 이루어져 있습니다.

• 1xx : 서버가 요청을 받아 이미 처리중임
• 2xx : 요청을 성공적으로 수행했음. 보통 200 OK로 리턴
• 3xx : 리다이렉션(Redirection)
• 4xx : 페이지를 찾을 수 없는 경우 발생. 보통 404 Not Found로 리턴
• 5xx : 서버에 문제 발생했음을 의미

HTTP/2

HTTP/2는 속도에 중점을 두고 있으며 SPDY/2에 기반하고 있습니다. HTTP/1.x는 텍스트 기반의 프로토콜이었으나 HTTP/2는 바이너리(Binary) 프로토콜입니다. HTTP/1.x에 비해 디버깅이 어려운 단점은 있습니다.

단일 요청을 수행했던 HTTP/1.x와 달리 HTTP/2는 완전 다중화(Fully multiplexed)로 되어 있습니다. 같은 시간대 여러 연결을 허용하고 다중 요청과 다중 응답을 해줄 수 있습니다. 또한 HTTP/2는 헤더를 압축해서 과부화를 줄이며, 서버측에서 클라이언트로 푸시(Push) 응답을 보내는 것도 허용합니다.

블록체인 분류

블록체인은 크게 3가지 형태로 분류할 수 있습니다. 누구라도 자유롭게 노드 참여가 가능한 퍼블릭 블록체인(Public Blockchain), 허가된 노드들만 참여가 가능한 프라이빗 블록체인(Private Blockchain), 여러 기관들이 컨소시움을 이루어서 블록체인 네트워크를 같이 운영하는 컨소시엄 블록체인(Consortium Blockchain)으로 나눌 수 있습니다. 하지만, 프라이빗 블록체인과 컨소시움 블록체인은 그 성격이 유사하기 때문에 보통 블록체인을 나눌 때는 퍼블릭 블록체인과 프라이빗 블록체인으로 나눕니다.

퍼블릭 블록체인

퍼블릭 블록체인은 누구나 노드 참여가 가능하기 때문에, 악의가 있는 참가자를 가려내거나 대처해야 하는 아주 큰 이슈가 존재합니다. 이는 블록체인이 등장하기 이전부터 비잔틴 장군 문제(Byzantine Generals’ Problem)라는 난제로 유명했었고, 크게 다음과 같은 문제가 걸림돌이었습니다.

• p2p 시스템에서는 각 노드간 정보 도달에 시간 차이가 존재한다. 또는 도달하지 못하는 경우도 발생할 수 있다.
• 악의가 있는 노드에 의해 잘못된 정보가 전달 될 수 있다.

블록체인도 비잔틴 장군 문제를 고스란히 갖고 있고, 비트코인에서는 작업 증명(PoW, Proof of Work)이라는 합의 알고리즘을 도입하여 이 문제를 해결했습니다. 물론 PoW가 비잔틴 장군 문제의 유일한 해결책은 아니기 때문에 PoW 이외의 합의 알고리즘(예를 들면 PoS 등)을 채택하고 있는 블록체인 기술들도 늘어나고 있는 추세입니다.

PoW나 PoS 등의 합의 알고리즘은 추가 포스팅을 통해 설명을 하도록 하겠습니다.

암튼, 퍼블릭 블록체인은 노드 참여가 자유롭다는 점 때문에 성능이나 PoW 도입으로 인한 다양한 단점들을 많이 갖고 있습니다. PoW의 단점들도 추가 포스팅으로 같이 설명하도록 하겠습니다.

퍼블릭 블록체인은 많은 노드들의 참여가 보장될수록 보안성이 강력해지기 때문에 참여한 노드들에게 보상을 줘야 하는 p2p 경제 원칙을 따르고 있습니다. (p2p 경제 원칙의 대표적인 사례로 비트토렌트같은 경우는 파일 공유를 하면 다운로드 속도를 보상으로 제공합니다.) 따라서 그 보상을 코인으로 제공하는 경우가 대다수이기 때문에 내부 화폐가 필요하다고 볼 수 있습니다.

퍼블릭 블록체인은 알고리즘 변경이나 버그 수정, 엔진 업그레이드 등이 상당히 어렵습니다. 만약 수정을 하게 될 경우 최악의 경우에는 하드포크(Hard-fork)가 발생하게 되어 새로운 체인이 만들어지는 경우도 발생할 수 있습니다.

프라이빗 블록체인

프라이빗 블록체인은 허가된 노드들만 네트워크에 참여가 가능합니다. 이를 관리하는 멤버쉽 서비스가 따로 존재하며 특정 기업에서 프라이빗 블록체인 기반으로 서비스를 제공하면, 해당 블록체인의 노드들은 서비스를 제공하는 기업에서 전부 구동시킬 가능성이 높습니다. (참고로 해당 기업의 서비스에 회원 가입이나 로그인이 자유롭다고 해서 해당 서비스가 퍼블릭 블록체인인 것은 아닙니다. 서비스의 회원이 아닌 ‘노드(Node)’로서 참여가 자유로울 때 퍼블릭 블록체인이 되는 것입니다.)

프라이빗 블록체인은 이미 신뢰할 수 있는 노드들만 참여가 가능하기 때문에, 악의가 있는 참가자를 가려내는 것보다는 성능이나 결제 완료성(Settlement Finality)이 훨씬 중요합니다. 그래서 성능과 결제 완료성 문제를 해결한 합의 알고리즘인 PBFT(Practical Byzantine Fault Tolerance)를 주로 사용합니다.

PBFT는 다수결로 의사를 결정하고, 그 다음에 블록을 생성하기 때문에 체인의 분기가 발생하지 않습니다. 그래서 결제 완료성이 보장되며, PoW와 같이 정답을 찾을 때까지 반복적인 연산을 하지 않기 때문에 훨씬 고성능으로 동작할 수 있습니다.

네트워크에 참여한 모든 노드들은 특정 기업에서 자체적으로 운영하는 노드일 가능성이 높기 때문에 퍼블릭 블록체인과 같은 보상 시스템이 필요없습니다. 즉, 내부 화폐가 없더라도 잘 동작할 수 있습니다.

또한 모든 노드들을 특정 기업에서 컨트롤할 수 있기 때문에 코드 수정이나 엔진 업그레이드 등이 퍼블릭 블록체인에 비해 훨씬 더 쉽습니다.

비트코인, 이더리움, 하이퍼레저 비교

퍼블릭 블록체인과 프라이빗 블록체인의 설명에 앞서 먼저 퍼블릭 블록체인(Public Blockchain)의 대표적인 기술인 비트코인(Bitcoin Core)과 이더리움(Ethereum), 그리고 프라이빗 블록체인(Private Blockchain)의 대표적인 기술인 하이퍼레저(Hyperledger)의 특징을 간단히 살펴보도록 하겠습니다.

위에서 ‘결제 완료성(Settlement Finality)’은 결제가 완료될 때까지의 불확실성을 의미합니다. 비트코인이나 이더리움의 경우 합의 알고리즘을 PoW(Proof of Work) 방식을 이용하는데, PoW 방식은 체인이 분기되었을 때 가장 긴 체인을 올바른 체인으로 선택합니다. 체인 분기가 아주 잦은 건 아니지만 종종 발생하는 편이기 때문에 비트코인의 경우 거래가 확정되더라도 6블럭 정도를 추가로 기다리지 않으면 확실한 결과를 얻을 수가 없습니다.

Keras를 이용한 이진 데이터(Binary Data) 분류하기 예제 코드

데이터셋은 아래의 코드를 이용해서 랜덤으로 생성합니다.

import numpy as np

x_train = np.random.random((1000, 12))
y_train = np.random.randint(2, size=(1000, 1))

x_test = np.random.random((100, 12))
y_test = np.random.randint(2, size=(100, 1))

import matplotlib.pyplot as plt

plot_x = x_train[:, 0]
plot_y = x_train[:, 1]
plot_color = y_train.reshape(1000, )

plt.scatter(plot_x, plot_y, c=plot_color)
plt.show()

사실 위 데이터는 완전 무작위로 생성한 값이기 때문에 특정 패턴이 없습니다. 그래서 머신 러닝에서 활용하기에 그리 좋은 케이스는 아닙니다. 하지만 이런 무작위 데이터는 아주 쉽게 만들 수 있기 때문에 연습용으로 활용하거나, 실제 데이터 분석을 하기 전 프로토타입 구현용으로는 괜찮은 것 같습니다.

퍼셉트론 신경망 예제

import numpy as np
from keras.models import Sequential
from keras.layers import Dense

x_train = np.random.random((1000, 12))
y_train = np.random.randint(2, size=(1000, 1))

x_test = np.random.random((100, 12))
y_test = np.random.randint(2, size=(100, 1))

model = Sequential()
model.add(Dense(1, input_dim=12, activation='sigmoid'))

model.compile(optimizer='rmsprop', loss='binary_crossentropy',
              metrics=['accuracy'])

hist = model.fit(x_train, y_train, epochs=100, batch_size=30)

import matplotlib.pyplot as plt

fig, loss_ax = plt.subplots()

acc_ax = loss_ax.twinx()
loss_ax.set_ylim([0.0, 1.0])
acc_ax.set_ylim([0.0, 1.0])

loss_ax.plot(hist.history['loss'], 'y', label='train loss')
acc_ax.plot(hist.history['acc'], 'b', label='train acc')

loss_ax.set_xlabel('epoch')
loss_ax.set_ylabel('loss')
acc_ax.set_ylabel('accuracy')

loss_ax.legend(loc='upper left')
acc_ax.legend(loc='lower left')

plt.show()

loss_and_metrics = model.evaluate(x_test, y_test, batch_size=30)
print('loss_and_metric: {}'.format(loss_and_metrics))

실행 결과는 다음과 같습니다.

다층 퍼셉트론 신경망 예제

import numpy as np
from keras.models import Sequential
from keras.layers import Dense

x_train = np.random.random((1000, 12))
y_train = np.random.randint(2, size=(1000, 1))

x_test = np.random.random((100, 12))
y_test = np.random.randint(2, size=(100, 1))

model = Sequential()
model.add(Dense(64, input_dim=12, activation='relu'))
model.add(Dense(1, activation='sigmoid'))

model.compile(optimizer='rmsprop', loss='binary_crossentropy',
              metrics=['accuracy'])

hist = model.fit(x_train, y_train, epochs=100, batch_size=30)

import matplotlib.pyplot as plt

fig, loss_ax = plt.subplots()

acc_ax = loss_ax.twinx()
loss_ax.set_ylim([0.0, 1.0])
acc_ax.set_ylim([0.0, 1.0])

loss_ax.plot(hist.history['loss'], 'y', label='train loss')
acc_ax.plot(hist.history['acc'], 'b', label='train acc')

loss_ax.set_xlabel('epoch')
loss_ax.set_ylabel('loss')
acc_ax.set_ylabel('accuracy')

loss_ax.legend(loc='upper left')
acc_ax.legend(loc='lower left')

plt.show()

loss_and_metrics = model.evaluate(x_test, y_test, batch_size=30)
print('loss_and_metric: {}'.format(loss_and_metrics))

실행 결과는 다음과 같습니다.

사실 데이터셋이 완전 무작위이이 때문에 많은 결론을 도출할 수는 없지만, 여기서 알 수 있는 것은 다층 신경망이 단층 신경망보다는 학습 속도가 훨씬 더 빠르다는 것을 알 수 있습니다.