[Blockchian] 블록체인과 튜링 완전, 그리고 비트코인

스마트 컨트랙트와 상태 기계의 관계에 대해서 간략하게 언급했었다. 그리고 이더리움이 튜링 완전(Turing Completeness)을 추구하고 있다는 것도 소개했다. 그렇다면 튜링 완전이 무엇을 의미하는지, 블록체인에서 튜링 완전이 왜 중요한지, 그리고 어떻게 구현했는지 한 번 살펴보자.

먼저 튜링 완전은 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력으로 문제를 풀 수 있는 것이다. 따라서 튜링 머신이 풀 수 있는 문제는 그 프로그래밍 언어나 추상 머신도 해결할 수 있는 것이다. 이번에는 튜링 머신이라는 새로운 개념이 등장했다.

튜링완전언어(모든 수학문제를 풀어낼 수 있는 알고리즘을 만들어낼 수 있는 컴퓨터 언어) + 무한한 저장공간 = 모든 계산 가능한 문제를 계산해내는 기계 = 튜링기계(인간의 뇌)

우리는 블록체인과 튜링 완전과의 관련성을 소개하기 전에, 이 문구를 이해하는 것을 목표로 하자.

튜링 머신

이미테이션 게임이라는 영화를 보았다면, 나치 독일의 암호기인 에니그마를 해독하는 과정에서 이러한 거대한 기계를 본 적이 있을 것이다. 이것도 튜링 머신의 일종이다. 이론적으로 표현하면 다음과 같다.

오, 정말 친숙치 않게 생겼다. 이론은 항상 그런거니까, 너무 겁먹지 말고 튜링 머신의 구성 요소를 차근차근 알아보자.

• 테이프(Tape) : 테이프는 일정한 크기의 셀로 나뉘어 있는 종이 테이프이다. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다.
• 헤드(R/W head) : 헤드는 종이 테이프의 특정 한 셀을 읽고 쓰는 것이 가능하며 이동이 가능하다.
• 제어 유닛(Finite control) : 제어 유닛은 테이프의 현재 셀에 기록된 심볼에 대해, 내장된 그래프에 따라서 어떻게 읽고 쓸지, 그리고 이동할지를 결정한다. 그와 동시에 현재 튜링 머신의 상태를 기록한다.
• 행동표(Action table) : 행동표는 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다. 제어 유닛에서의 내장된 그래프라고 생각하면 된다.

혹시나 내장된 그래프, 행동표에 궁금할까봐 조심스레 사진을 가지고 왔다. 튜링 머신은 입력이 주어지면 밑 사진의 그래프에 따라서 계속 동작하거나 동작을 멈춘다.

튜링완전언어

튜링 머신을 살펴보면서, 제어 유닛은 주어진 입력과 내장된 그래프에 따라서 행동을 결정한다고 했다. 즉 주어진 문제와 내장된 해결 방법에 따라서 행동한다. 튜링 완전 언어는 내장된 해결 방법이 어떠한 문제든 해결할 수 있는 것을 의미한다. 그래서 위에서 '모든 수학문제를 풀어낼 수 있는 알고리즘을 만들어낼 수 있는 컴퓨터 언어'라고 소개한 것이다.

그런데 튜링완전언어에 대한 설명 중에는 컴퓨터 언어라는 표현이 있다. 컴퓨터 언어 중에서도 특히 다음 조건을 충족시키는 것을 의미한다.

1. 문제에 대한 해결과정(프로세스)를 충분히 분할할 수 있을 만큼 작은 단위를 사용해야 한다.
2. 조건문과 반복문이 있어야 한다.

궁극적인 모델은 인간의 뇌

튜링머신의 궁극적인 목표는 인간의 뇌를 기계로 구현하는 것이다. 그럼 우리가 평소에 하는 행동을 생각해보면서, 이 행동을 하기 위해서는 기계가 어떠한 것을 필요로 하는지 알아보자.

우리는 졸리면 냅다 침대에 누워서 자곤 한다. 굳이 침대가 아니더라도 의자에서 자기, 책상에 엎드려 자기, 대충 아무데서나 드러눕고 자기 등 무엇이든 상관 없다. 그저 피곤하니까, 자고 싶으니까 바로 잔다. 하지만 기계의 입장에서도 이렇게 간단할까?

세분화

'졸려서 침대에 누워 잔다.'는 다음과 같은 단계로 세분화되었다.

1. 뇌는 졸린 상태이므로 하품을 하도록 한다.
2. 우리는 하품을 한다.
3. 우리는 침대를 본다.
4. 침대에 누워서 자면 되겠다는 생각을 한다.
5. 침대에 눕는다.
6. 침대에서 잔다.
7. 잠에서 깬다.

기계의 입장에서는 이렇게 세분화하여야 그나마 이해하기 좋을 것이다. 한편 우리는 잠에서 깼을 때, 아직 피곤하다면 더 잠을 잘 수도 있다. 이럴 때, 위와 같이 세분화하면 중간 과정을 옮겨와 활용할 수 있게 된다.

중간 과정 활용

이렇게 피곤할 때는 침대에 다시 누워 더 잠을 자게끔 할 수 있다. 더불어 매일 밤마다, 혹은 피곤할 때마다 이러한 행동을 반복하도록 할 수도 있다.

반복

이제 자는 것이 아니라, 누워서 스마트폰으로 유튜브를 보고 싶을 때가 있다. 이럴 때는 피곤하다는 것을 느끼거나, 잠자는 중간 과정을 바꿔서 응용하면 된다.

응용

이렇게 일상적인 행동을 기계로 옮기기 위한 과정들을 간략하게나마 알아봤다. 우리가 행동하는 원리랑 똑같기 때문에, 앞서 튜링완전언어에서 두 가지 조건을 충족시키는 것이 중요한 이유이다.

튜링완전언어로 분류되지 않는 것

1. Markdown
2. HTML
3. CSS
4. Script
   ...

튜링완전언어의 두 가지 조건을 만족하지 않는다면, 프로그래밍 언어로 분류되지 않는다. 그래서 Markdown, HTML, CSS 등은 프로그래밍 언어로 분류되지 않는다. 이런 언어는 Markup language라고 해서 따로 분류되어 있다. 특이하게도 HTML + CSS의 조합은 튜링완전언어의 두 가지 조건을 만족하기 때문에, 프로그래밍 언어로 분류되곤 한다.

블록체인과 튜링완전 간 관련성을 알아보기 전에, 튜링머신과 튜링완전언어에 대해 살펴보았다. 우리가 이해하려고 했던 문구에는 무한한 저장공간도 있었는데, 사실 무한한 저장공간은 현실세계에서 만들 수 없다. 대신 유한한 저장공간이더라도, 지속적으로 저장공간을 늘려가는 대책 방안을 마련할 수 있다. 이러한 경우에는 느슨한 튜링완전(Loose Turing Completeness)이라고 일컫는다. 이제는 정말로 블록체인을 만나러 가보자.

Script

"이더리움은 왜냐하면 비트코인 시스템의 튜링 불완정성이라는 한계를 극복하고자 나온 시스템이기 때문이다."라고 언급한 적이 있었다. 그럼 비트코인은 왜 튜링 불안정하고, 이것이 어떤 문제가 되는지부터 시작해보자. 비트코인에서 사용하는 언어는 Script이다. 그런데 이 언어는 if 조건문만을 지원하고, 반복문을 지원하지 않는다. DDoS 공격을 원천적으로 막고자 했기 때문이다.

무한 반복과 거래 증명

반복문을 쓰다보면, 가끔씩 반복문이 종료되지 않고 무한 반복하는 경우가 있다. 반복문에 종료 조건이 아예 없거나, 있더라도 종료 조건을 만날 수가 없을 때 이런 문제가 발생한다. 즉 문제를 해결할 때까지 반복을 계속하지만, 문제를 해결하는 것이 굉장히 오래 걸리거나 해결할 수 없는 상태이다. 어떤 언어가 튜링완전언어이고 반복문을 사용할 수 있게 된다면, 자연스럽게 생길 수 있는 문제이다.

블록체인은 분산 시스템이기에, 각 블록체인 노드는 트랜잭션 메시지에 대해서 다른 노드와 비교하며 전체 네트워크의 거래 내용을 실시간으로 동기화한다. 이러한 거래 증명 과정에서 무한 반복문이 발생한다면, 네트워크에 참여하고 있는 노드들의 컴퓨팅 파워를 잡아먹기 시작할 것이다. 블록체인 네트워크 내 컴퓨팅 파워를 모두 차지하면, 네트워크는 마비될 것이다. 특히 프로그램 카운터를 하나씩 증가시키면서 무한 연산을 한다면, 결국에는 CPU 자원을 모두 차지해 네트워크는 아무 연산도 수행하지 못 할 것이다.

DDoS 공격

위와 같은 현상을 DDoS 공격이라고 한다. Script에서 반복문 기능이 제외된것은 DDoS 공격을 원천 방어하기 위해서이다. 그렇다면 블록체인 시스템에서 DDoS 공격이 얼마나 위험하길래, 반복문 기능까지 제외하면서 방지하려고 한걸까?

블록체인은 탈중앙화 분산 시스템을 추구하므로, 메시지가 정상적인 것인지 악의적인 것인지는 전적으로 해당 노드의 판단에 맡긴다. 하지만 메시지를 판별하는 것이 모호하기 때문에, 노드가 악의적인 메시지를 실제로 발견하기 매우 어렵다.

한편 채굴자는 고액의 수수료를 받기 위해서, 높은 수수료 거래를 우선적으로 실행한다. 왜냐하면 보통 채굴 과정에서 트랜잭션 수수료의 합과 암호화폐를 보상으로 받기 때문이다. 그리고 이들은 채굴을 하기 위해서 1000만원 가량하는 ASIC이라는 채굴 전용 기계를 도입하고, 한 국가의 전력 소비량을 넘을 정도의 전기를 사용하는 등 많은 투자를 한다. 그렇다보니 비싼 수수료를 제시한 거래를 우선으로 처리하려는 것은 당연하다. 그럼 일반적인 수수료를 갖는 거래는 채굴자의 우선 순위에서 밀려나므로, 점점 블록에서 배제된다. 결과적으로는 정상적인 거래이지만, 수수료가 비싸지 않다는 이유로 거래를 거부당한다.

그렇다면 만약 비정상적으로 높은 수수료를 제시하는 거래를 무한히 만들 수 있다면, 채굴자는 이 거래를 계속해서 받아들이려 할 것이다. 실제로는 이 거래는 비정상적인 메시지였을 뿐이기에, 정상적인 거래는 처리되지 않을 것이다. 어느 한 노드가 비정상적인 거래를 받아들였다면, 다른 노드들도 이 거래 내용을 비교하며 실시간으로 동기화 해야 한다. 무한히 생성되는 비정상적인 거래로 각 노드의 컴퓨팅 자원이 낭비되기 시작하고, 블록체인 네트워크 전체가 마비되기 시작한다.

이러한 형태의 공격을 DDoS 공격이라고 한다. 블록체인 네트워크가 마비되면 채굴자한테도 피해가 간다. 그래서 채굴자는 비정상적인 거래에 대한 우선순위를 조정해 대응한다. 한편 이러한 공격은 보통 악성코드에 감염된 노드에 의해서 수행된다고 알려져있다. 악성코드를 없애거나, 감염된 노드가 치료될 때까지 네트워크에서 제외하는 등으로 문제를 해결할 수 있을 것이다. 그런데 이러한 해결 방법은 악성코드에 감염된 노드가 무엇인지, 어디까지 퍼졌는지 찾아내는 것이 선행되어야 하기 때문에 대응하기가 어렵다.

응용의 희생

앞서 튜링완전언어를 살펴보면서, 응용에 대해서도 알아봤다. 비트코인은 이러한 응용이 제한적이기 때문에, 현재 볼 수 있는 화려한 스마트 컨트랙트 블록체인을 만들 수 없다. 그 이유는 Script에서 반복문의 부재, 그리고 UTXO(Unspent Transaction Outputs)의 제한된 상태표현 문제점 때문이다. 중요한 것은 다음 문장이다.

UTXO는 블록체인에 기록된 "소비되지 않은 출력값"을 통해 거래의 유효성을 검사하여 코인의 존재 여부를 확인한다. - UTXO, 해시넷

즉 출력값이 사용되었거나, 사용되지 않았다는 2가지 상태만을 표현할 수 있다. 하지만 사람의 행동은 2가지 상태만으로 표현하기에는 너무나도 부족하다. 스마트 컨트랙트를 만들 수 없다는 것은 아니지만, 이걸 가지고 어플리케이션을 만드려면 엄청난 고생이 필요할 것이다. 더불어 반복문도 없이 진행한다면 고생길이 눈에 보인다.

Script에 대한 깊은 이해를 하고 싶다면, 새로운 Smart Contract 프로그래밍 언어 만들기 — VM(0) 글을 참고하자. 원리를 이해하는 데 많은 도움이 될 것이라고 생각한다.

다음은 이더리움

지금까지 작성한 포스팅 중에 가장 긴 포스팅이 되었다. 스마트 컨트랙트와 상태 기계부터 출발해, 튜링 완전의 중요성에 대해서 살펴보았다. 그리고 비트코인으 튜링 완전을 포기했던 이유와 그로 인해 희생해야 했던 것들이 무엇인지 알아봤다. 글의 흐름상 비트코인에 대해서 부정적으로만 이야기했다. 하지만 UTXO와 Script만의 장점이 있기 때문에, 비트코인은 가치를 저장하는 암호화폐로 인정받고 있는 것이다. 언젠가 이에 대해서도 다뤄볼 예정이다. 지금은 일단 이더리움으로 넘어가보자.

Reference

이더리움 개론 + 튜링완전, https://brunch.co.kr/@ashhan/10
튜링머신, http://www.aistudy.co.kr/linguistics/turing_linz.htm
블록체인 기록 보관 방식의 차이점: 비트코인(UTXO) vs. 이더리움(계좌/잔고), https://xangle.io/research/6253b47e2d003e735a45c494
이더리움 백서 톺아보기 - 2편, https://m.upbitcare.com/academy/education/coin/253
[블록체인 리포트] 블록체인을 이용한 보안 강화부터 위협까지, https://www.techm.kr/news/articleView.html?idxno=5109
블록체인 네트워크 보안 위협 탐지 기술 동향 분석, https://koreascience.kr/article/JAKO202119060130545.kr&sa=U
[밑바닥비트코인] 7. 스크립트, https://humankind.tistory.com/47?category=943346
새로운 Smart Contract 프로그래밍 언어 만들기 — VM(0), https://medium.com/de-labtory/%EC%83%88%EB%A1%9C%EC%9A%B4-smart-contract-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EC%96%B8%EC%96%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0-vm-0-c6441e52423