블록체인 합의 알고리즘의 correctness

블록체인 기술의 핵심이 합의 알고리즘이다 보니 전산 전공자가 아닌 분들도 PoW나 PoS, BFT 같은 합의 알고리즘에 대해 엔지니어들 못지 않은 지식을 자랑하는 걸 많이 볼 수 있습니다. 그리고 신규 블록체인 플랫폼이 저마다의 합의 알고리즘을 하나씩 내놓으면서 유행처럼 많은 합의 알고리즘을 쏟아져 나오고 있습니다.

여러 대의 노드가 트랜잭션의 내용과 순서를 합의하는 방법이야 얼마든지 많으니 수많은 합의 알고리즘이 나오는 것도 이상한 일은 아닙니다. 하지만 합의 알고리즘이 아무리 그럴싸 해도 다음 두 가지 속성을 만족시키지 않으면 아무 소용이 없습니다.

  • Safety: 나쁜 일이 일어나지 않음
  • Liveness: 좋은 일은 언젠가는 일어남

합의 알고리즘이 safe하지 않으면 블록에 포크가 발생하게 되고, 합의 알고리즘이 live하지 않으면 합의를 영원히 못하고 교착 상태에 빠질 수 있습니다.

따라서 합의 알고리즘을 검토하고 공부하실 때 가장 중요하게 보셔야 할 항목은 safety와 liveness에 대한 formal proof입니다. 두 속성을 수학적으로 증명하지 못한 합의 알고리즘은 사실상 이런 식으로 하면 합의가 될 것 같다는 직관 그 이상도 이하도 아닙니다.

한 예로, Raft 합의 알고리즘을 BFT로 수정한 Tangaroa라는 합의 알고리즘이 있습니다. 스탠포드 대학원생 2명이 분산 컴퓨팅 수업 들으면서 과제 보고서로 제출한 합의 알고리즘인데, 어떤 이유인지 유망한 BFT 합의 알고리즘으로 둔갑하여 Kadena Juno나 ScalableBFT 같은 블록체인 프로젝트에도 적용이 되었습니다. 그런데 이 합의 알고리즘은 safety, liveness 두 가지 다 문제가 있습니다.

분산 컴퓨팅은 수많은 가능성을 고려해서 모든 문제를 다 대비해야 하고, 그럴려면 수학적인 증명이 필수입니다. 누가 세상에 없던 고성능 합의 알고리즘을 만들었다고 주장한다면 safety/liveness에 대한 formal proof 먼저 확인하시기 바랍니다.

코드체인 데브 미팅 후기

어제 세 번째 코드체인 데브 미팅이 있었다. 코드체인 데브 미팅은 일주일에 한 번 오픈소스 코드체인 프로젝트에 기여하는 개발자들이 모여 개발 논의, 코드 리뷰, 기술 발표 등을 진행하는 정례 행사이다. 이번 미팅에는 코드체인팀 8명, 외부 기여자 4명 총 12명이 참석하였다.

오늘 처음 참석한 SKT  송지영님이 간단히 소개를 하고, 곧 바로 기술 발표를 시작했다. 이번 발표는 내가 했고 주제는 Schnorr 서명이었다. Schnorr 서명은 ECDSA에 비해 알고리즘이 간단하고 서명 및 검증이 효율적이라 차세대 서명 알고리즘으로 주목받고 있다. Decred 프로젝트가 이미 Schnorr 서명을 사용하고 있고 비트코인도 도입을 검토하고 있다. 코드체인도 Schnorr 서명 검토를 위한 준비 작업을 진행 중이고 앞으로 계속 안정성을 테스트해 볼 예정이다. Schnorr 서명의 특성이 궁금하신 분은 이전 글을 참고.

4

30분 정도 발표를 마치고 즐거운 저녁 식사 시간. 첫 미팅 피자, 두 번째 미팅 치킨에 이어 오늘의 메뉴는 햄버거다. 개발자들의 식성을 고려해 패스트푸드 위주로 준비하였으나 건강을 해치는 것 같아 다음 주부터는 샌드위치, 샐러드로 전환할까 고민 중이다. 식사 시간에는 간단히 서로의 안부도 묻고, 블록체인 기술에 대한 논의도 이루어졌다. (먹는다고 바빠서 밥 먹는 사진은 못 찍었다.)

빠르게 식사를 마친 후 다시 모여 외부 기여자 중 한 분인 이동준님이 작성하신 Stratum 프로토콜제안을 함께 검토하였다. Stratum은 코드체인 노드와 마이너가 효율적으로 통신할 수 있도록 TCP 상에 JSON RPC를 정의한 네트웍 프로토콜이다. 비트코인, 이더리움 마이닝 풀 등에서도 Stratum 프로토콜을 사용하고 있으나 표준 명세가 없이 마이닝 풀마다 제각각 조금씩 다른 프로토콜을 정의해서 사용하고 있다.

코드체인도 최근 Cuckoo Cycle 기반의 PoW 합의 알고리즘을 지원하기 시작했기 때문에 코드체인 노드와 마이너 사이의 효율적인 통신 채널이 필요했다. 마침 이동준님이 해당 작업에 지원하여 프로토콜 제안을 해주셨고 이후 구현까지 진행하기로 하셨다.  코드체인을 오픈소스 한 이후 벌써 13개 이상의 PR를 주셨을 만큼 열정적으로 참여해주고 계신 이동준님에게 이 자리를 통해 감사의 말씀을 드린다.

설계 리뷰 이후에는 각자 삼삼오오 흩어져서 개발 논의 및 코드 리뷰를 진행하였다. 해외 오픈소스 프로젝트와 달리 코어 개발팀과 직접 만나 코드 리뷰를 진행할 수 있다는 사실은 코드체인 프로젝트의 가장 큰 장점이라 하겠다. 미리 PR을 올려놓고 미팅에 참석해서 리뷰를 진행할 수도 있고, 미팅에 와서 버그를 할당 받은 후에 그 자리에서 논의하고 바로 PR 및 코드 리뷰까지 진행하는 것도 가능하다.

2

코드체인 프로젝트에 PR을 하나라도 제출하신 분은 코드체인 데브 미팅에 참석 가능하다. 블록체인 코어 개발자가 되는 정도(正道)는 직접 코어를 개발해 보는 것이고 이미 코어 개발 경험이 있는 팀과 같이 하면 더욱 빠르게 성장할 수 있다. 아직 블록체인 기술에 익숙치 않다고 걱정할 필요는 없다. 코드체인은 초심자들도 쉽게 프로젝트에 참여할 수 있도록 비교적 쉽게 수정할 수 있는 간단한 이슈를 Good first issue 로 모아서 제공하고 있다. Good first issue를 하나 골라 커밋을 만들고 PR만 보내면 그 후로는 코드체인 개발팀이 친절히 도와준다.

블록체인 코어 기술을 개발하겠다는 팀은 많지만 소스코드를 공개하지 않으면 어떤 프로젝트를 하는지 알 방법이 없다. 코드를 공개했어도 개발활동을 오픈하지 않으면 외부 개발자들이 참여할 방법이 없다. 코드체인은 코드체인팀 뿐만 아니라 많은 외부 개발자들이 참여하는 진정한 의미의 오픈소스 프로젝트로 만들고 싶다. 개발자분들의 많은 참여 부탁드린다.

블록체인 기술에 대한 오해: 작업 증명과 보상

비트코인, 이더리움이 PoW (작업 증명) 방식으로 블록을 생성하고 블록 생성 보상을 준다는 사실은 널리 알려져있다.  그럼 네트워크 참여자가 네트워크에 도움이 되는 행위를 하면 네트워크에서 발행한 토큰으로 보상해 준다는 아이디어도 가능하지 않을까? 생각보다 쉽지 않다.

우선 아무 작업이나 작업 증명에 사용할 수 있는 게 아니다. 비트코인의 경우 SHA256 해시 함수를 작업 증명에 사용하고 있는데, 타겟을 만족시키는 논스 값을 찾을 때는 상당한 계산이 필요하지만 이미 찾은 논스 값이 맞는지 검증에 필요한 계산은 아주 간단하다. 바꿔 말해, 마이너 입장에서 실제로 많은 계산을 하지 않고서 논스 값을 찾을 수 있는 방법이 없고 검증 노드 입장에서는 간단한 계산 한 번으로 작업 증명을 검증할 수 있기 때문에 이러한 방식은 작업 증명에 적합하다.

오늘자 매일경제에 실린 사막 한복판서도 버퍼링 없다…유튜브 위협하는 블록체인TV 기사는작업 증명을 잘못 이해하고 있는 대표적인 예다. 이 프로젝트의 아이디어는 간단하다.  P2P로 트위치와 같은 스트리밍 서비스를 제공할 예정인데, 컴퓨팅 파워와 네트웍 대역폭을 제공한 유저들에게는 토큰 보상을 제공한다.

문제는 유저가 실제로 컴퓨팅 파워와 네트웍 대역폭을 제공했는지 검증하기가 쉽지 않다는 점이다. 비트코인, 이더리움이 엄청난 양의 컴퓨팅 파워를 쓸모도 없는 해시 계산 따위에 낭비하고 있는 이유는 이러한 방식이 작업 증명에 효율적이기 때문이다. 어떤 노드가 동영상 인코딩, 디코딩이 컴퓨팅 파워를 사용했다는 사실을 제 3자에게 어떻게 증명할 수 있는가? 어떤 노드가 다른 노드에게 실제로 유용한 콘텐츠를 제공했다는 사실을 어떻게 검증할 수 있는가? 이러한 질문에 제대로 된 답변을 내놓지 못하면 이 서비스는 기술적 불가능하다.

다른 유저가 인증을 해주는 방법도 생각해 볼 수 있지만, 익명성을 보장하는 P2P 네트워크의 특성상 시빌 공격(Sybil Attack)에 취약하다. 한 유저가 여러 개의 계정을 생성해서 서로 보상을 주기 시작하면 네트워크에 아무런 유용한 일을 하지 않고서도 토큰을 보상으로 받을 수 있는 문제가 생기기 때문이다. 이를 해결하기 위해 중앙화된 인증 수단을 도입하는 순간 더 이상 분산 네트워크라고 부를 수 없게 된다.

블로그 글을 열심히 쓰면 보상을 주거나, 게임을 열심히 하면 보상을 주는 시스템도 모두 같은 이유로 어뷰징에 취약하다. 흔히 블록체인 기술을 어뷰징 혹은 핵을 방지하는 기술로 설명하는 경우가 많은데 사실 블록체인은 어뷰징에 무척 취약하고 어뷰징을 막기 위해 많은 고민을 해야만 하는 기술이다. 어떤 행위를 보상하는 이코노미를 설계하기 전에 그 행위를 객관적으로 검증할 수 있는지 먼저 확인해야 한다.

Schnorr 서명

비트코인, 이더리움 모두 서명 알고리즘으로 ECDSA(Elliptic Curve Digital Signature Algorithm)을 사용하고 있다.  ECDSA는 전통적인 DSA에 비해 키/서명 크기가 작기 때문에 많은 블록체인에서 서명 알고리즘으로 채택하고 있다.

하지만 최근 비트코인은  ECDSA를 Schnorr 서명으로 대체하려는 논의를 진행 중이다. Schnorr 서명은 ECDSA에 비해 다음과 같은 장점이 있다.

1. n-of-n threshold signature를 효율적으로 지원함

여러 개의 Schnorr 서명은 하나의 서명으로 합쳐질 수 있다. ECDSA는 n-of-n multisig를 지원하기 위해 n개의 공개 키와 n개의 서명 데이터가 필요하지만, Schnorr 서명은 1개의 공개 키와 1개의 서명 데이터로 n-of-n multisig를 지원할 수 있다.

2. ECDSA에 비해 서명 데이터의 크기가 작음

DER 인코딩된 ECDSA 서명이 71-72 바이트를 차지하는 것과 달리 Schnorr 서명은 64바이트의 고정된 크기를 가진다. 서명 데이터의 크기가 줄었기 때문에 네트워크 전송 및 디스크에 저장해야 할 데이터의 크기 역시 줄어든다.

3. signature malleability 문제가 존재하지 않음을 증명

malleability 문제가 있는 ECDSA와 달리 Schnorr 서명은 malleability가 없다는 사실이 증명되었다.

Schnorr 기반의 multi signature scheme의 자세한 내용은 MuSig, a multi-signature scheme based on Schnorr signatures을 참고하기 바란다.

 

최근 코드체인도 Schnorr 서명 도입을 위한 준비를 시작했다.

아이콘의 비상식적인 행보

ICON은 작년 성공적인  ICO를 밑거름으로 고속 성장하고 있는 유명한 블록체인 프로젝트이다. 이더리움과 마찬가지로 스마트 컨트랙을 통해 다양한 DApp을 서비스할 수 있는 체인이며, 서로 다른 여러 체인을 연동하는 인터체인 프로젝트이기도 하다.

자타가 공인하는 국내 최고의 블록체인 기술 기업이지만, 마케팅과 사업 제휴 능력에 비해 의외로 기술력을 보여준 것이 없고 기술 개발과 관련된 그간의 행보도 무척이나 비상식적이다.

 

1. 스크린샷으로만 존재하는 메인넷 런칭 소식

아이콘은 2018 1 24 Hello ICON World 블로그를 통해 메인넷 런칭 소식을 알렸다. 하지만 공개된 건 제네시스 블록 스크린샷 한 장 뿐 메인넷의 주소도 블록 익스플로러로 공개하지 않았다.

 

2. 소스 코드 비공개

1월에 이미 메인넷을 런칭했다고 하는데 아직도 소스 코드는 공개하지 않고 있다. ICO를 위해 공개한 프로토타입 수준의 loopchain 소스 코드 6개월 넘게 업데이트 없이 방치되고 있다.

icon.support FAQ 소스 코드를 공개하지 않는 이유를 다음과 같이 밝히고 있다.

We are developing on Gitlab for internal uses. It is because currently ICON is being used by actual institutions, and opening the related sources is concerned to their intellectual property rights. We need some time to sort this part out from the rest and make it open sourced and update to github. We will soon open our technical development community and start to develop on the basis of github completely.

ICON을 이미 사용하고 있는 곳의 지적재산권 때문에 소스 코드를 공개하지 못하고 있다는 해명인데, 해명 자체도 석연치 않지만 이 해명이 사실이라고 해도 공개 블록체인으로 펀딩 받은 프로젝트의 지적재산권을 온전히 소유하지 못하고 있다는 건 심각한 문제이다.

 

3. 수준 이하의 개발력과 실망스러운 대응

6 18일 이더리움 위에 발행된 아이콘 ERC20 스마트 컨트랙에서 어이 없는 실수가 발견되었다. 개발자가 코딩 실수로 아이콘 관리자에게만 허용되어야 하는 전체 거래 중지 및 재개 기능이 모두에게 허용된 것이다.

일단 1월에 메인넷을 런칭했는데 6 18일까지도 이더리움 상에서 토큰 거래가 이루어지고 있었다는 사실 자체가 이상하다. 스마트 컨트랙 실행은 커녕 토큰 거래도 못 하는 메인넷을 6개월 가까이 운영하면서 뭘 한 걸까?

스마트 컨트랙에서 발견된 버그는 단순한 코딩 실수로 개발자가 테스트 한 번만 해봤어도 발견할 수 있었다. 어이 없는 실수지만 버그 없는 소프트웨어란 없고 다행히 금전적인 손실을 초래하는 버그도 아니니 불행 중 다행이라 하겠다.

하지만 더루프 김종협 대표의 최근 인터뷰 해명은 무척 실망스럽다.

김 대표는프로그래밍에서 코드에 오류가 있는지 검사를 할 때 일반적으로는 CI(지속적 통합)유틸리티 툴을 사용해 지속적·자동적으로 검사가 하게 되는데, 중앙화 된 서버에서 개발이 이뤄지지 않는 블록체인에는 이 같은 자동화 검사의 개념이 없다때문에 개발자가 일일이 검사를 진행해야 하는데 이 같은 과정에서 사고가 발생할 수 있다고 설명했다. 그는 이어이처럼 CI 개념이 도입되지 않고 있다는 것은 블록체인 기술의 단점이라고 말했다.

아이콘 스마트 컨트랙 버그는 CI 없어도 개발자가 딱 한 번이라도 테스트해봤으면 바로 알 수 있는 단순한 버그다. 그런데 김 대표는 이걸 블록체인 특성상 어쩔 수 없는 문제인 것처럼 해명하고 있다.

그리고 일부 언론은 이 버그가 아이콘 구현의 버그인 것처럼 보도하고 있는데, 아이콘 메인넷에서 발생한 버그가 아니라 이더리움 위에 구현된 아이콘 ERC20 토큰에서 발생한 버그다.

 

ICON은 작년 ICO를 통해 충분한 자금도 확보했고 최근 대대적인 충원을 통해 개발력도 확충했을 거라고 본다국내 블록체인 산업의 신뢰 확보를 위해서라도 더 이상의 비상식적인 행보를 멈추고 제대로 개발해서 소스 코드도 공개하고 메인넷도 확보하길 진심으로 기원한다. 화이팅이다.

BFT 합의 알고리즘

Tendermint, Casper the Finality Gadget, BFT+dPoS 등 많은 합의 알고리즘이 BFT 기반의 합의 방식을 사용하고 있습니다. BFT는 분산 컴퓨팅 분야에서 많은 연구가 되었고 safety나 liveness를 수학적으로 보장할 수 있기 때문에, 앞으로 더 많은 합의 알고리즘이 BFT를 차용하여 성능이나 확인 시간을 개선하는 용도로 사용할 것으로 보입니다.

BFT 방식의 합의 알고리즘을 실용적인 수준으로 쓸 수 있도록 개선한 PBFT(Practical Byzantine Fault Tolerance) 논문이 1999년에 나왔는데, 당시는 블록체인이 없었기 때문에 블록이 아닌 개별 연산(operation)의 순서를 보장하는 용도로 사용이 되었고 논문에서는 BFT한 NFS(Network File System)를 구현하였습니다.

이후에 나온 Tendermint 합의 알고리즘은 BFT를 블록체인에 맞게 다음과 같이 수정/보완하였습니다.

  1. 리더를 하나로 고정하지 않고 매 라운드마다 교체
  2. 노드를 동적으로 더하거나 뺄 수 있는 기능 추가
  3. Point-to-point 통신 대신 gossip 프로토콜 사용

특히, 리더를 라운드마다 교체하도록 한 부분이 중요한데 리더가 비잔틴일 경우 새로운 리더를 선출하기 위해 필요한 리더 선출 알고리즘을 단순화할 수 있고, 하나의 리더가 자신에게 유리한 트랜잭션만 선택적으로 블록에 포함시키는 행위를 방지할 수도 있습니다.

관련 내용에 관심 있으신 분은 Tendermint과 PBFT 비교 글을 참고하시기 바랍니다.

해시 충돌

비트코인을 비롯한 거의 모든 블록체인 시스템은 해시 함수의 collision을 찾기가 어렵다는 사실을 전제하고 있습니다. 비트코인은 SHA256, 이더리움은 Keccak 해시 함수를 사용하고 있는데, 만약 이들 해시 함수에 collision이 발견되면 비트코인이나 이더리움의 안정성을 담보할 수 없게 됩니다.

비트코인 스크립트 언어를 이용하면 hash collision을 찾았을 때 자동으로 상금(bounty)를 지급하는 스크립트를 작성할 수도 있습니다. 2013년 Peter Todd가 실제로 이러한 바운티 프로그램을 제안하였고, SHA1, SHA256, RIPEMD160과 같은 해시 함수 뿐만 아니라RIPEMD160(SHA256()), SHA256(SHA256())와 같은 더블 해시에도 바운티를 걸었습니다.

자세한 내용은 아래 링크에서 볼 수 있습니다.

https://bitcointalk.org/index.php?topic=293382.0

일례로, SHA1에 대한 스크립트는 다음과 같습니다.

scriptPubKey: OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
scriptSig: <preimage1> <preimage2>

두 개 의 서로 다른 메시지를 넣어서 각각 SHA1 해시를 구한 다음 비교했을 때 같은 값이 나오면 SHA1 해시에 collision이 발생한 것이고, lock script가 풀리게 됩니다.

그리고 2017년 2월에 실제로 누군가가 SHA1 바운티를 풀어서2.48 비트코인을 상금으로 가져갔습니다!

https://blockchain.info/address/37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP

다행히 비트코인은 SHA1이 아닌 SHA256 해시 함수를 사용하고 있기 때문에 SHA1 해시가 풀린 사건이 비트코인에 직접적으로 영향을 미치지는 않습니다. 다만, 이 사건은 해시 함수의 안정성이 얼마나 중요한지를 잘 보여주고 있습니다. 관련 내용은 아래 레딧 링크에서 보실 수 있습니다.