튜링 머신에서 블록체인으로: 언어로 보여지는 세계

튜링 머신에서 블록체인으로: 언어로 보여지는 세계

백엔드 엔지니어를 하면서 분산 환경에 대해 자연스럽게 관심을 갖게 되었다. 그러다보니 어느새 블록체인을 탐구하기 시작하였고 현재는 블록체인 스터디를 하고있다. 블록체인 기술은 분산된 수많은 노드들이 다 같이 합의를 이뤄 거래에 대한 데이터 일관성을 지켜나가는 개념적으로 거대한 하나의 시스템이다. 그리고 이러한 시스템을 신뢰하는 사람들이 모여서 하나의 생태계를 이뤄나간다. 기존에 국가 정부, 중앙된 기관을 신뢰하며 믿고 맡기던 일을 이제는 컴퓨터가 하는 것이다. 컴퓨터란 무엇일까? 쭈욱 들어가다보면... 컴퓨터 과학에 나오는 흔한 서사가 있다. 바로 [힐베르트 - 괴델 - 튜링] 이야기이다. 튜링이 고안해낸 튜링머신은 지금 우리가 사용하는 컴퓨터 원천 설계도이자, 블록체인, AI 기술을 탄생하게 한 주역이다. 이 이야기를 시작으로 블록체인 기술을 겉핥기 해보았다. 이번 내용은 언어 중심으로 구성하였고 분산 시스템, 합의 등 이외의 주제들은 복잡성을 줄이고자 제외하였다. 힐베르트 이야기부터 시작한다.

 

1. 튜링 머신이란 무엇인가?

수학계의 꿈, 힐베르트 프로그램

당시 학계에서 이름을 떨친 수학자 힐베르트는 1928년 세계수학자대회에서 공식적으로 '힐베르트 프로그램'을 만들자고 전세계 수학자들에게 제안하였다. "수학의 모든 명제가 단 한 세트의 기본적인 공리들로부터 기계적으로 추론될 수 있다면, 수학을 완전성과 무모순성에 기초한 학문으로 체계를 형식화할 수 있다."는 것이 그의 주장이었다.^[각주:1]

• 완전성: 주어진 공리 세트를 사용하여 모든 참된 수학적 명제를 증명할 수 있어야 함
• 일관성: 주어진 공리 세트를로부터 모순되는 명제를 도출할 수 없어야 함
• 결정론성: 주어진 명제가 참인지 거짓인지 결정할 수 있는 절차가 있어야 함

힐베르트 수학자

 

참고로 20세기 초에는 러셀, 비트켄슈타인과 같은 학자들도 활발히 활동한 시기이기도 하다. 이때 당시 유명한 역설은 러셀의 이발사 역설(1901)이 있다. 러셀은 거짓말쟁이 역설 ('나는 지금 거짓말을 하고 있다.' 그리고 '이 문장은 거짓이다.')을 집합 이론의 관점에서 체계적으로 정리하였다.^[각주:2]

• 마을에서 단 한 명의 이발사(남성)는 스스로 수염을 깎지 않는 모든 사람의 수염을 면도하고 그 이외의 사람의 수염은 깎지 않는다고 가정한다.
• 여기서 문제는 "이발사는 자신의 수염을 면도하는가?"이다.

결국 이 말은 자기모순적인데, 그 이유는 정확히 참 또는 거짓으로 증명할 수 없기 때문이다. 

• 만약 다른 사람이 이발사의 수염을 깎아준다고 하면, 이 이발사는 '스스로 깎지 않는' 사람에 속하므로, 위 문장에 따르면 자신의 수염을 깎아야 한다.
• 그러나 만약 수염을 직접 깎는다고 하면, '스스로 깎는' 사람에 속하므로, 위 문장에 따르면 자신의 수염을 깎을 수 없다.

 

힐베르트는 수학에서 사용하는 형식 언어를 사람들이 사용하는 자연 언어와는 달리 러셀이 언급한 모순이 존재하지 않는 완전한 언어로 자리매김하고 싶어했다. 어떻게 증명할까 고민해봤더니... 완전한 수학의 형식 언어로 짜여진 기본 공리들을 입력으로 나오면 다양한 추론을 통해 모든 수학 명제를 증명하고 새로운 이론을 만들 수 있는 만능 프로그램을 만들면 되는 것이 아닌가?

자연 언어: 사람들이 일상생활에서 사용하는 언어 (복잡, 모호함, 맥락에 따라 의미 변함)
형식 언어: 수학, 언어학, 컴퓨터 과학에 논리적으로 쓰이는 용어 (엄격한 체계와 규칙, 모호성 없음, 일관성과 완전성을 추구)

 

괴델의 불완전성 정리, 결정할 수 없는 문제에 대하여

그러나 이로부터 3년 뒤에 힐베르트의 꿈은 젊은 수학자에 의해 깨지고 말았다. 젊은 수학자 쿠르트 괴델이 '불완전성 정리'^[각주:3]를 발표한 뒤다. 해당 논문이 발표되고 나서 학회는 발칵 뒤집혀졌다. 당시 명성을 떨치던 힐베르트의 주장에 대한 반론을 제기했던 것이 하나의 이유이고, 그가 접근한 방식이 당시 탄생하지 얼마되지 않았던 '메타수학'에 대한 활용을 깔끔하게 해낸 것이 그 다음 이유이다. 

 

 

발표한 다음 이론들을 보면 수학과 같이 온전한 공리 체계를 가진 어떠한 체계에서도 해당 공리 체계 내에서 증명되지 않는 참인 수학적 진술이 존재함을 증명했다.

• 제 1불완전성 정리: 어떠한 공리 체계에서도 참이지만 증명할 수 없는 명제가 존재한다.
• 제 2불완전성 정라: 어떠한 공리 체계에서도 일관성(무모순성)을 증명하기 위해서 해당 체계 내에서는 증명할 수 없다. 

 

괴델은 이를 증명하기 위해서 '괴델수'라는 개념을 고안해냈다. 메타수학은 수학에 대한 수학을 뜻하며, '1+1=2'라는 수학 명제가 있을 때 이러한 수학 명제를 ''1+1=2'라는 명제는 참이다'와 같이 수학을 다른 차원의 시선에서 연구하는 분야이다. 수학과 메타 수학은 서로 다른 차원에 속해있다. 수학이 A차원, 메타 수학을 B차원이라고 한다면, A 차원에 존재하는 수학적 명제를 B 차원에 존재하는 메타 수학적 명제를 통해 증명하게 되면 다양한 모순들이 발생한다. 당연한 것이 이들은 다른 공리 체계로 만들어진 다른 차원에 존재하는 개념들을 가지고 왔기 때문이다. 점프라는 개념을 z축이 없는 개미의 2차원 세상에 대입하여 문제를 해결해나가는 방법 자체가 모순이듯이 말이다. 그런데 괴델은 '괴델 수'를 사용하여 메타 수학의 명제를 수학이라는 차원으로 끌고왔다. 이 부분이 당시 많은 사람들이 놀랐던 점이기도 하다. 해당 정리 내용을 간략하게 살펴보면 다음과 같다.^[각주:4] 

 

제 1 불완전성 정리

P: ∼(∃x)Dem(x,Sub(y,a,y))

 

P의 명제를 풀이하면, 'x가 존재하지 않는다'이다. (x는 Sub(y,a,y)의 증명을 말한다) Sub(y,a,y)를 해석해보면 y라는 명제에서 a를 미지수 y로 대체하면 대응되는 괴델수이다. 결국, Sub(y,a,y)는 y를 뜻하고 이는 증명 불가능하다는 명제이다. 이제 여기에 괴델수를 부여하여 메타수학 차원에서 수학의 차원으로 가져와 보자. P에 괴델수 n을 부여해보면 다음과 같다.

 

Q:  ∼(∃x)Dem(x,Sub(n,a,n))

 

해당 명제는 'Sub(n, a, n)을 가진 명제는 증명할 수 없다'라는 의미를 가진다. 잠깐 Sub(n,a,n)는 무엇인가? 괴델수 n에 부합하는 명제에서 a에 부합하는 대상 y를 n으로 바꾸었다. Q는 명제 P: 'y는 증명 불가능하다'에서 대상 y를 n으로 바꾼 명제이다. 즉, Q = Sub(n,a,n)으로 자기 자신을 가리킨다. 따라서, Q는 Q 자기 자신에 대한 명제에 증명에 해당하는 x는 존재하지 않는다는 결론이 된다.

 

이 글은 쓴 시점 필자의 사고 구조로 해당 정리를 완전하게 받아들였다고는 장담하지는 못한다. 그냥 '메타수학 명제를 괴델수를 사용하여 수학 명제로 가져왔고, 수학적 공리 체계 위에서 자기 참조 모순을 지니지 않으면서(어디에도 명제 p나 q가 자기 자신을 언급하지 않는다) Q 명제와 같이 참이지만 증명 불가능한 명제가 존재한다'라고 이해하고 넘어갔다. 여기서 힐베르트 프로그램의 꿈 중 하나인 완전성은 부정되었다.

 

제 2 불완전성 정리

두 번째 정리는 제 1 불완전성 정리에서 증명한 명제 Q를 가지고와서 귀류법으로 '공리계가 무모순임을 공리계 내에서 증명 불가능하다'를 증명했다. 

• 힐베르트 프로그램 조건: '공리계가 무모순임을 공리계 내에서 증명 가능해야 한다'
• 가정: '명제 Q는 무모순적임을 증명 가능하다' (명제 Q: 참이지만 증명 불가능하다)
  • Q가 참일 경우, Q는 증명 불가능하다. 그러나 가정과 모순이므로, Q는 거짓이 된다.
  • 그러면 Q가 거짓일 경우, Q는 증명 가능해진다. 그러나 Q는 제 1불완전성 정리에서 증명 불가능함을 증명했다. 따라서 해당 주장은 모순이므로, Q는 참이다.

Q가 참이면 거짓이되고, Q가 거짓이면 참이된다. 이것으로 가정한 명제는 모순되는 명제이므로, '공리계가 무모순임을 공리계 내에서 증명 가능하다'는 거짓이 된다. 따라서, 공리계가 무모순임을 공리계 내에서 증명할 수 없다. 

 

이렇게 괴델은 해당 공리 체계 내에서 증명되지 않는 참인 수학적 진술이 존재한다는 것을 증명했다. 또한, 그런 시스템은 자체 일관성을 증명할 수 없다는 것도 보여주었다. 여기서 얻을 수 있는 것은 추론 규칙을 아무리 잘 만들어도 그 법칙들만으로는 모든 참인 명제들을 절대 길어올릴 수 없다는 것이다. 놓친 사실까지 길어올리도록 매번 기계를 확장한다해도, 또 기계가 길어올리지 못하는 사실이 존재한다는 것이다. 마치 힐베르트의 프로그램은 모래사장의 모든 모래를 주먹으로 쥐려는 행동과 같다.

 

컴퓨터의 아버지, 앨런 튜링

그때 당시 수학과를 수석으로 졸업한 앨런 튜링은 1935년 맥스 뉴먼 교수의 '괴델 불완전성 정리'에 대한 강의를 듣게 된다. 그리고 튜링은 자신만의 방식으로 문제를 재해석하여 1936년 '계산 가능한 수에 대하여, 결정문제에 대한 활용을 중심으로' 논문을 발표한다. 

 

 

증명을 살펴보기 전에 개인적으로 와닿았던 부분은 괴델과 달리 힐베르트 프로그램은 만들 수 없다로 끝나지 않고, 튜링은 '가능한' 부분을 찾고자 했다는 것이다. 현재 많은 업적을 인정받아 영국 50파운드(한국으로 치면 5만원권)에 새겨진 앨런 튜링은 'Those who can imagine anything, can create the impossible. 무엇이든 상상할 수 있는 사람은 무엇이든 만들어 낼 수 있다.'라는 말을 남긴 적이 있다고 하는데(출처는 명확하지 않다), 해당 논문이나 콜로서스와 같은 업적으로 보면 충분히 납득이 가는 부분이다.

 

컴퓨터의 원천 설계도, 튜링 머신

튜링은 해당 논문에서 '계산 가능한 수'에 대한 개념을 정의하고 튜링 머신을 소개한다. 머신의 구성은 간단하다.

• 정사각형으로 칸을 매긴 무한한 테이프(메모리)
• 테이프를 읽고 쓰는 기계(CPU)
• 상태 기록기
• 행동표

튜링 머신

 

해당 머신은 계산 가능한 수에 한하여 다양한 문제를 풀 수 있게 디자인되었다. 가볍게는 x, y를 입력하면 x+y를 출력하는 머신, 그리고 뺄셈을 해주는 머신 그리고 곱셈, 나눗셈을 해주는 머신을 만들어 볼 수 있다. 

간단한 기능을 하는 튜링 머신

 

 

그리고 각자의 역할을 머신들을 한 곳에 모아둔 머신을 설계하면 이는 지금의 계산기라고 불리는 머신이 된다. 

 

현재 스마트폰에 담긴 앱들 또한 이러한 튜링 머신의 개념에서 발전되어 동작하는 단순 머신들의 집합이다. 예시로, 머신을 통해 실시간으로 상품 재고가 변하고 소비자들은 이러한 상품을 다양하게 살 수 있는 기능을 가진 소프트웨어의 모습은 다음과 같다.^[각주:5]

 

Reveal2021 - 쿠팡의 대규모 트래픽을 다루는 백앤드 전략

 

 

정지 문제, 프로그램이 무한히 작동하는지 판별할 수 있을까?

이렇게 튜링 머신을 소개하고 나서 튜링 또한 힐베르트 프로그램은 존재할 수 없음을 증명해냈다. 

• 힐베트르 프로그램 조건:  '주어진 명제가 참인진 거짓인지 결정할 수 있어야 한다'
• 가정: 모든 머신을 시뮬레이션할 수 있는 튜링 머신이 존재한다면(힐베르트 프로그램이 존재한다면), 튜링은 정지할 것인지 아니면 무한히 계속 작동할 것인지에 대한 판별할 수 있는 머신 또한 존재해야 한다. 

 

튜링은 이를 증명하기 위해가 자기 참조 기계를 만들었다.

1. 특정 입력값을 넣으면 해당 머신이 멈출 것인지에 대해 결정론적 결과(0 또는 1)를 도출하는 머신이 무한히 존재한다.
2. 그리고 이러한 입력값을 받은 다음에 그에 대해 반대되는 값을 도출하는 머신 또한 존재한다.
3. 그러면 그 반대를 출력하는 머신을 다시 1번의 머신에 넣으면 어떻게 될까? 

 

해당 증명의 전제로 튜링 머신 하나는 자연수 하나에 대응한다는 것이다. 튜링 머신은 자연수의 무한대보다 클 수 없다.^[각주:6] 표로 나타내면 아래와 같다. 해당 표는 세상에 존재하는 모든 튜링 머신과 그 머신에 입력을 넣으면 출력하는 결과를 나타낸다. 온전한 공리 체계를 가진 시스템 내부라고 보면 된다. 그러나, Mn의 머신은 해당 시스템에 속해있지 않는다. 결국 괴델의 제 2 불완전성 정리와 같은 결론으로 아무리 Mn이라는 머신을 주어담으려고 해도 해당 시스템 내에서는 주어담을 수 없다는 것이다. 

 

결론은 힐베르트 프로그램이 가정한 완전하고 일관된 수학적 체계는 불가능함을 나타낸다. 모든 수학적 명제를 결정할 수 있는 범용적인 기계는 존재하지 않는다. 만약 정지 판별 문제를 할 수 있는 머신이 존재했다면 이더리움 Gas의 개념이 존재하지 않았을 것이라고 가볍게 생각해볼 수 있다. 이를 통해 '계산 가능성'에 대한 연구가 활발히 진행된다. 

 

2. 튜링 머신에서 블록체인 세계로: 언어 중심

'컴퓨터과학이 여는 세계'라는 책을 통해서 컴퓨터 과학의 기초를 다시 다지게 되었고 해당 글을 쓰는데에도 큰 도움을 받은 책이다. 해당 책에서 어느 챕터 소개글에 이러한 글이 있다.

모든 도구를 다루는 방법이 함께 하는데, 인류가 발명한 대개의 도구는 물리적인 도구였고 다루려면 물리적인 근육이 필요하였다. 하지만, 컴퓨터는 마음의 도구이고 그 도구를 다루는 방법은 지혜와 언어로 짜여진 소프트웨어이다. 

알고리즘: 도구가 일하는 방법 
언어: 도구가 표현하는 방법 

 컴퓨터 과학이 여는 세계 中

 

소프트웨어의 본질은 알고리즘과 언어에 있다. 이러한 작은 소프트웨어들이 쌓이고 합치고 서로 교류하며 탄생하는 것이 우리가 흔히 접하는 웹, 디지털 세계인 것이다. 알고리즘은 접어두고 언어를 중심으로 글을 계속 이어나가고자 한다. 

 

현대 프로그래밍 언어는?

언어는 알고리즘으로 기계적인 방법을 적고 이를 튜링 머신이 실행하게 한다. 다음은 'hello world'를 출력하는 간단한 golang 언어로 만든 머신이다. 직관적으로 봐도 package, func, main, print 등 기계보다는 사람이 읽을 수 있는 언어임을 알 수 있다. 정보 이론을 탄생시킨 클로드 섀넌에 의해 현대 CPU 프로세서는 0과 1 시퀀스로 되어있는 바이너리 입력 데이터를 읽고 결과를 출력하도록 디자인되어 있다. 그러면 고수준 프로그래밍 언어에서 어떻게 0과 1로만 이루어진 데이터로 변환할 수 있을까?

• 고수준 프로그래밍 언어: 사람 친화적인 언어
• 저수준 프로그래밍 언어: 기계 친화적인 언어

 

 

컴파일러, 프로그래밍 언어를 번역하는 기계

현실에서도 다른 언어를 사용하는 두 사람이 원활하게 소통을 하기 위해서는 통역사가 필요하다. 컴퓨터 세계에서도 마찬가지이다. 그리고 통역사 역할을 하는 기계를 컴파일러라고 한다. 간단한 동작 방식은 다음과 같다. 사람 친화적인 언어인 Source 코드를 컴파일러에게 전달하면 어휘 분석 → 구문 분석 → 의미 분석 → 코드 생성 단계를 거쳐 기계가 읽을 수 있는 Object 코드를 생성한다. 개발자들은 자신이 쓰는 언어가 어떻게 실행되는지 직접 만들어보기도 한다.

• rust로 만든 interpreter
• python code 500 line으로 만든 C compiler

컴파일러 동작 구조

 

"if x is ture then y else z"라는 문법을 사용할 수 있는 프로그래밍 언어가 있고 해당 문장을 컴파일해보자.

 

어휘 분석기 Lexer

코드가 컴파일러에게 전달되면 첫 번째로 하는 일이 해당 프로그래밍 언어의 어휘를 분석하는 것이다.

 

"if, then, else는 조건문이고, x, y, z는 변수이고, ..."

어휘 분석기 Lexer

 

예시를 들면 이렇다.

KIND        STRING
-----------------------
if          Kind::if
x           {x value}
is          Kind::equal
true        Kind::True
then        Kind::Then
y           {y value}
else        Kind::Else
z           {z value}
#EndOfToken

 

 

구문 분석기 Parser

어휘 분석기에 의해 기계가 읽을 수 있는 토큰의 형태로 분류가 되었다면 이를 이젠 구문 분석기에서 맥락을 파악한다. 여기서는 푸시다운 오토마타을사용하여 스택으로 추상 구문 트리(AST)를 생성한다. 

 

구문 분석기 Parser

 

오토마타 이론, 계산할 수 있는 기계의 다양한 모델

이러한 중요한 역할을 하는 컴파일러를 좀 더 들여다보면 오토마타 이론이 나온다. 오토마타 이론이란 컴파일러와 같은 기계와 같이 계산 능력을 갖춘 추상적인 기계(오토마톤)를 이용해서 풀 수 있는 문제들을 연구하는 분야이다. 이러한 오토마타는 결정론적 알고리즘과 같이 입력을 받아 일정하게 상태를 전이하며 출력을 내놓는다.

 

여기서 형식 언어와 형식 문법을 다루게 된다. 형식 언어는 위에서 힐베르트 이야기할 때도 잠깐 언급한 내용이다. 형식 언어는 수학, 언어학, 컴퓨터 과학에 논리적으로 쓰이는 용어 (엄격한 체계와 규칙, 모호성 없음, 일관성과 완전성을 추구) 을 나타낸다. 언어학자 노암 촘스키^[각주:7]는 이러한 형식 언어를 문법의 생성규칙 형태에 따라 4가지 타입으로 구분지을 수 있도록 제안했다. 

• 재귀 열거 가능 언어(Recursive-Enummerable Language): 해당 언어는 표현에 제약이 없다. 해당 언어를 인식할 수 있으면 튜링 머신이라고 한다. 무한한 테이프, 심볼, 상태, 상태표이 네 가지 도구를 통해 어떠한 프로그램이나 알고리즘 모델링할 수 있다.
• 문맥 의존 언어(Context-Sensitive Language): 문맥에 따라 뜻이 바뀌는 언어를 말한다. 이는 유한한 테이프를 가지는 선형 바운디드 튜링머신이 인식할 수 있다.
• 문맥 자유 언어(Context-Free Language): 문맥에 제약이 없는 더 단순한 문법을 가진다. 이는 PDA(푸시다운 오토마타)로 인식할 수 있다. 컴파일러의 구문 분석기도 이에 해당한다. 프로그래밍 언어를 보면 보통 {, }로 함수를 열고 닫고 하는데 스택으로 동작하는 PDA로 구문 분석을 하기 때문이다. 
• 정규 언어(Regular Language): 가장 단순한 생성규칙을 가진다. 이는 테이프(메모리)가 없는 계산 모델로, 특정 패턴을 가진 문자열을 인식하는 데 사용한다. 전화번호 패턴을 확인하는 정규 언어식과 컴파일러의 어휘 분석이 이에 해당한다.

컴파일러는 정규 언어로 어휘 분석을 하고 문맥 자유 언어인 프로그래밍 언어의 구문 분석을 PDA를 통해서 한다. 그리고 튜링 머신에서 동작하도록 디자인된 대부분 프로그램은 이 두 기계로는 정확한 해석이 불가능해서 타입 체크와 같은 의미 분석(Semantics)^[각주:8]을 추가로 해주고 있다. 

오토마타 이론과 촘스키 위계

 

현대 프로그래밍 언어는 대부분 결정론적이고 문맥 자유 언어로 디자인된다. 여기서 '재귀 열거 가능 언어를 인식할 수 있는 기계가 튜링 머신이며, 우리가 사용하는 대부분의 만능 앱들은 튜링 완전하다'라는 개념에 의문을 가졌다. 그래서 추가로 알아본 결과, 언어를 구문을 기술할 수 있는 능력과 해당 언어로 표현할 수 있는 계산의 종류나 복잡성은 별개라고 봐야함을 알게 되었다. 프로그램이 튜링 머신을 시뮬레이션 할 수 있으면 튜링 완전하다고 하는 것이다. 이러한 튜링 완전성을 지니게 되면 충분한 시간과 메모리가 주어지면 알고리즘이 있는 모든 문제를 해결할 수 있다.

튜링 완전성

 

블록체인 첫 번째 기술, 튜링 불완전한 비트코인

많은 아티클이나 블록체인을 처음 접하게 되었을 때 볼 수 있는 문장은 '비트코인은 튜링 불완전하나 이더리움은 튜링 완전하다'는 것이다. 비트코인은 튜링 불완전하도록 설계되었다. 왜냐하면 단순히 분산 원장을 관리하고 트랜잭션만 처리하는 기능이 제한된 기계이기 때문이다. 그 이상의 기능은 필요하지도 않고 만들어져서도 안된다. 그래서 당연히 의도된 설계라고 볼 수 있다. 비트코인 머신에서는 단순한 스크립트 언어가 존재한다. 

• 단순한 트랜잭션만을 처리할 수 있는 스크립트 언어는 트랜잭션의 유효성을 검증하기 위한 간단한 스택 기반의 언어이다.
• 상수, 신술 명령어, 조건문, 스택 연산 처리, 비교/논리 로직, 암호관련 명령어 등이 포함된다.

scriptPubKey: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
scriptSig: <sig> <pubKey>

 

이러한 비트코인 스크립트 언어는 다음과 같이 실행된다. 결정론적으로 모든 실행이 True, False로 귀결된다. 

 

언어 문법 생성 규칙으로 분류된 촘스키 위계를 들고와서 대입해보자. 일반적으로 프로그래밍 언어를 구문 분석하는 데 사용하는 PDA(푸시다운 오타마타)와는 구조적으로는 큰 차이가 없다. 그러나 계산 능력에서는 루프나 복잡한 제어 구조를 제공하지 않는 이러한 비트코인 스크립트 스택 머신은 PDA보다 더 제약적이다. 그래서 다음과 같은 위치에 있다고 볼 수 있다.

비트코인 스크립트 스택 머신

 

블록체인 2.0, 튜링 완전한 이더리움

이더리움^[각주:9]은 블록체인 2.0으로 불리며, 비트코인이 지닌 한계를 극복하기 위하여 만든 튜링 완전한 기계이다. EVM(Ethereum Virtual Machine)에서 Solidity와 같은 언어로 작성된 스마트 컨트랙트를 실행한다. 모양새는 Javascript와 유사한 Solidity는 Java와 비슷하게 EVM이라는 가상 머신에서 실행될 수 있도록 디자인된 컴파일 언어이다. EVM에서 동작하는 스마트 컨트랙트 언어는 다음과 같이 실행된다.

• solidity smart contract → solc로 컴파일 → ABI, bytecode → evm으로 실행 → 각 아키텍처에 맞게 실행(x86, arm, …)

 

큰 그림으로 보면 다음과 같다. 스마트 컨트랙트를 작성하고 컴파일하여 온체인상에 저장한다. 노드에 저장된 컴파일된 파일을 트랜잭션을 실행하는 데에 사용한다. 그리고 이러한 트랜잭션을 실행되면 go-ethereum와 같은 코드로 구동된 이더리움 노드에 있는 EVM을 통해 실행한다. 

evm에서 스마트 컨트랙트가 동작하는 과정

 

이더리움 가상 머신 EVM, 하나의 언어로 다양한 기계

VM은 하드웨어 가상화, 소프트웨어 가상화로 구분할 수 있다. 이는 '가상 머신 VM: 가상 메모리, 메모리 관리 기법, Hypervisor'라는 글에서 한 번 다룬 적이 있는 내용이다. EVM은 후자에 속하며, JVM과 마찬가지로 (EVM 바이트코드로 컴파일될 수 있는) 한 번 작성된 코드는 어떤 이더리움 노드에서도 실행될 수 있다는 장점을 가지고 있다. 

 

VM

 

EVM^[각주:10]은 튜링 완전한 스택 기반 머신으로 스마트 컨트랙트를 실행한다. 그러나 이를 자세히 보면 굉장히 제약적인 머신이라는 것을 알 수 있다. 정말 비트코인이 불완전한 튜링 머신에 대한 한계에서 조심스레 튜링 완전하게끔 한 발자국 이동한 것처럼 보인다. 특징을 살펴보자.

• 튜링 완전하다. (무한 반복, 다양한 조건문 등 실행 가능)
• 인터프리터로 실행되며, Javascript처럼 단일 스레드로 동작한다.
• Program Counter, Stack, Memory, Gas, Storage, ROM(Read-Only Memory) 로 구성되어있다.
• Heap의 개념이 존재하지 않는다. (예측 불가능성 낮춤)

EVM 구조

 

싱글 스레드 동작에 Heap이 존재하지 않는다. Stack은 이삿짐 상자처럼 가장 위에 쌓인 데이터부터 하나씩 꺼낼 수 있지만, Heap은 책장처럼 원하는 데이터에 쉽게 접근이 가능하기 때문에 동적 메모리 접근법을 사용할 때 쓰이는 디자인이다. EVM은 메모리를 보호하기 위해 일부로 이러한 기능들을 제약한 것으로 보인다.

 

Solana의 스마트 컨트랙트, Rust

그러면 여기서 잠깐 Solana의 SVM과 Rust를 살펴보자. 우선 Rust 언어에는 메모리 소유권에 대한 개념이 존재한다. 기존 C, C++과 같은 언어는 메모리 할당/해제를 개발자가 직접해주어야 했는데, 그러다보니 휴먼 에러가 나기 쉽상이었다. 그래서 Rust는 이를 컴파일 단계에서 제약하는 방식으로 디자인되었다. 다음 코드에는 vec이라는 객체가 하나 존재한다.

1. ownership()함수가 실행되면서 스택이 생기고 vec의 데이터를 힙에 저장한다. vec의 소유권은 ownership()함수에게 있다.
2. take(vec) 함수가 실행되면서 vec의 메모리 소유권은 take() 스택으로 넘어가게 된다. ownership()에서는 더 이상 vec 객체를 사용할 수 없다.
3. take(vec)함수가 종료되면 vec은 return되지 않으므로 더 이상 사용되지 않는 데이터라고 판단되어 메모리가 해제된다.

물론, 좀 더 유연하게 소유권을 빌려주는 borrowing 방식도 존재한다.

Rust 소유권

 

Solana는 스마트 컨트랙트 언어를 실행하는 SealevelVM이라고 불리는 SVM이 있고 해당 머신은 멀티 스레딩 구조로 동작한다. 그래서 여러 트랜잭션을 동시에 처리하여 높은 TPS 성능을 보여주고, 메모리 안전성에 대한 걱정은 Rust와 같은 언어를 스마트 컨트랙트 언어로 채택하면서 보완한 듯 하다. 

EVM vs SVM

 

EVM은 비트코인 스크립트 머신에 튜링 완전함에 발만 담군 형태로 확장성에 대해서는 꽤나 제약적인 구조를 지니고 있다. 이러한 한계때문에 Ethereum 2.0에서 Layer2 솔루션, 샤딩 등 확장성을 위해 부단히 노력하고 있는 것으로 보인다.

 

웹 어셈블리 WASM, 다양한 언어로 다양한 기계

Ethereum의 공동 설립자이자 Polkadot 및 Kusama의 창시자인 GavinWood는 2021 Consensus에서 다음과 같은 언급한 바가 있다. 'WebAssembly Is the Future of Smart Contracts, but ‘Legacy’ EVM Is Right Now'^[각주:11] EVM은 레거시 기술이라 같이 가야하지만 웹 어셈블리가 미래다라고 주장할 만큼 매력있어 보이는 웹어셈블리란 무엇일까? 이전에 'WebAssembly(WASM)와 WASI: 웹 브라우저 및 서버사이드 기술'에서 다룬 적이 있다. Javascript의 웹 성능 개선의 한계 곡선에 다다르는 시점에 C++, Rust와 같이 더 빠르게 실행할 수 있는 언어로 웹을 실행하자는 목표를 가지고 웹 어셈블리가 탄생하였다.^[각주:12]

• 고급 언어(C++, Rust) → IR: clang과 같은 LLVM(Low Level Virtual Machine) 프론트엔드 컴파일러를 사용하여 LLVM 중간 표현(IR)으로 변환한다. LLVM의 IR에 있으면 LLVM이 이를 이해하므로 LLVM은 일부 최적화를 수행할 수 있다. 
• IR → Wasm: 이제 LLVM의 IR에서 LLVM 백엔드 컴파일러를 통해 WebAssembly로 변환해주면 된다.

WASM

 

그런데 EVM도 Wasm처럼 'EVM 호환성'이라고 불리면서 EVM에서 동작할 수 있는 스마트 컨트랙트 언어가 무수히 많다. EVM이 읽을 수 있는 바이트코드로 컴파일할 수 있다면 EVM과 호환된다고 말한다. Avalanche, Binance Smart Chain, Polygon, Solana 등 많은 체인이 EVM 호환성을 제공하여 새로운 체인임에도 진입 장벽을 낮출 수 있었다.^[각주:13] 그렇다면 '웹 어셈블리랑 차이가 없는 게 아닌가?'라는 생각이 들 수도 있지만 다양한 언어로 다양한 기계(x86, arm, ...)에서 실행할 수 있다는 것은 장점 중 하나일 뿐이다. 웹 어셈블리 언어로 실행하면 가질 수 있는 장점은 다음과 같다.

• 리소스 효율성 및 속도 우수함 - Wasm 응용 프로그램은 최소한의 메모리 공간과 CPU 요구 사항으로 실행되도록 만들 수 있다. 그리고 네이티브와 같은 속도를 제공할 수 있다. VM 부팅 또는 컨테이너 시작과 달리 콜드 스타트가 없다.
• 보안 뛰어남 - Wasm 런타임은 기본적으로 샌드박스 처리되며 메모리에 안전하게 액세스할 수 있다. 기능 기반 모델은 Wasm 애플리케이션이 명시적으로 허용된 항목에만 액세스할 수 있도록 한다. 더 나은 공급망 보안이 있다.
  • 대부분의 언어는 런타임에서 함수는 주소를 가진다. 메모리를 바이트 배열 형태로 보면 함수 코드가 제대로 구별되지 않기 때문에 안전하지 않다.
  • Wasm은 프로그램 메모리를 안전한 영역에 캡슐화하기 때문에 프로그램을 실행하는 호스트에 영향을 미치거나 보안을 손상시킬 수 있는 코드를 허용하지 않는다.
• 휴대성이 좋음 - 여러 주요 런타임에서 대부분의 CPU(x86, ARM, RISC-V)와 Linux, Windows, macOS 및 비 Posix를 포함한 대부분의 OS를 지원한다.
• 이식성 좋음 - 40개 이상의 언어를 Wasm으로 컴파일할 수 있으며 현대적이고 지속적으로 개선되는 툴체인을 사용한다. 컴파일러는 LLVM 백엔드를 활용해 LLVM 중간 표현(IR)으로 컴파일하여 Wasm 프로그램을 생성할 수 있다.

 

웹 생태계 개선을 위해 디자인된 웹 어셈블리 기술은 WASI와 함께 서버 사이드까지 영역을 확장하고 있고 블록체인에서도 이에 대한 활용과 인기는 뜨거워 보인다. 위에서 인터뷰한 Gavin Wood가 설립한 Polkadot의 Substrate를 비롯해 Cosmos에는 cosmwasm등 많이 보이기 때문이다. 

 

마무리

언어와 이를 실행하는 머신(VM, Wasm)은 해당 체인 생태계 확장에 큰 역할을 한다. 첫 번째 이유는 개발자들이 각각 선호하는 언어도 있고 잘 활용할 수 있는 언어가 제한되기 때문이다. 이는 인력적인 부분에서도 크게 고려해야할 부분이다. Sei v2와 같이 많은 체인들이 EVM 호환을 제공하는 움직임을 보이는 것은 좋은 전략으로 보여진다. 두 번째로는 머신 자체의 능력이다. 위에서 EVM을 공부해봐서 알다시피 굉장히 제약적인 부분이 많다. 떄문에 머신 자체의 확장보다는  layer2, 샤딩으로 확장을 노리고 있다. 이러한 EVM 단점을 보고 솔라나는 백엔드, AI에서도 크게 주목받는 Rust 언어를 스마트 컨트랙트 언어를 사용하고 동시성을 제공하는 SVM을 설계한 재밌는 사례도 있다. 본문에서 다루진 않았지만 Rust와 유사한 SUI Move 언어 또한 소유권 유형 덕분에 독립적은 트랜잭션으로 병렬 처리를 가능케 하였다. 트랜잭션을 온체인에 하는 것을 넘어서 비트코인 라이트닝 네트워크, 카르다노의 하이드라, 이더리움의 롤업(최근 부테린이 zk 출현 이후로 UTXO + plasma를 다시 보고 있는 것 같긴함)등 layer2 확장 전략을 보면 결국 각 머신이 어떻게 설계되어있느냐에 따라서 달라지는 것을 볼 수 있다. 

 

부제 '언어로 바라보는 세계'는 비트켄슈타인의 전기를 참고하여 지었다. 언어와 세상을 일대일 대응으로 생각하고 세상은 단지 언어로 표현된 실체일 뿐이라는 것이다. 물론 비트켄슈타인 후기에는 세상은 언어와 일대일 대응이 아닌 더 복잡한 세상임을 인정하면서 자신의 전기의 일부 내용을 부정한다. 그러나 나는 블록체인 세계는 비트켄슈타인의 전기에 대한 논리를 적용해도 된다고 생각한다. 이 세계에서는 문맥 자유 언어인 프로그래밍 언어를 사용하고 이를 번역하여 VM이 읽을 수 있는 바이트코드 또는 웹 어셈블리 언어가 그들 세상을 표현하는 언어이고 개발자들이 만들어진 공리 세트에 의해서만 세상을 표현할 수 있기 때문이다. 컴퓨터 세상의 한계는 명확하다. 그리고 명확한 한계를 통해 많은 사람들에게 신뢰를 얻고 다양한 Dapp이 탄생된다. 21세기인 지금 정말 재밌고 흥미로운 세상이 펼쳐지고 있다.

 

2024년 1월 업데이트) 최근 AI와 양자 컴퓨팅 그리고 의식에 대해 직접 탐구해보면서 3차원 관점을 벗어난 양자역학과 결합된 컴퓨터의 세상의 한계는 명확하지 않을 수 있다고 생각한다. 이는 나중에 상세히 정리해 볼 예정이다. 

 

Resources

1. Hilbert’s Program, Stanford Encyclopedia of Philosophy [본문으로]
2. 위키백과, 거짓말쟁이 역설 [본문으로]
3. On formally undecidable propositions of Principia Mathematica and related systems. I. (German) Zbl 0002.00101 [본문으로]
4. [난제] 괴델의 불완전성 정리, 이상엽 Math [본문으로]
5. Reveal2021 - 쿠팡의 대규모 트래픽을 다루는 백앤드 전략 [본문으로]
6. SNUON_컴퓨터과학이 여는 세계_2.4 튜링 기계의 급소: 튜링기계 하나는 자연수 하나_이광근 [본문으로]
7. 위키백과, 노암 촘스키 [본문으로]
8. Sematic Analytics [본문으로]
9. Ethereum, a secure decentralised generalised transaction ledger berlin version [본문으로]
10. Ethereum Virtual Machine, EVM [본문으로]
11. Polkadot’s Gavin Wood: WebAssembly Is the Future of Smart Contracts, but ‘Legacy’ EVM Is Right Now [본문으로]
12. What makes WebAssembly fast?, Lin Clark, Mozila [본문으로]
13. The Benefits of EVM Compatibility, What is EVM? Ethereum Virtual Machine [본문으로]