공정한 선거를 위한 블록체인 기반 전자투표 시스템 제안
Writer: 이동헌(DongHeon Lee), 최정인 (Blockchain in public sector team)
Seoul Nat’l Univ. Blockchain Academy Decipher(Medium)
Reviewed by 고주환(JooHwan Ko)
선거는 민주주의의 근간을 이루는 제도이며 그 어떤 시스템보다도 공정하고 투명해야 한다. 누군가 마음대로 투표 결과를 위조할 수 있다면 그 누구도 선거의 정당성을 인정하지 않을 것이다. 때문에 현대 국가들은 보다 정밀한 개표와 투개표 조작 방지를 위해 막대한 비용을 지불하고 있다. 가령, 2018년 대한민국 지방 선거에서는 투개표 관리를 위해 64만 명의 인력과 5113억 원의 예산이 투입되었다.
이러한 정부의 노력에도 불구하고, 사람들은 선거의 공정성을 완전히 신뢰하지 않는다. 선거가 종료될 때마다 개표조작 의혹이 심심찮게 터져나오는 것만 보아도 그렇다. 실제로 개표 과정상의 문제로 무효 처리되는 많은 표들은 이러한 의혹을 부채질한다.
IT 기술의 발전으로 전자투표 시스템이 등장하자, 정밀하고 무결한 개표에 대한 사람들의 기대가 높아지기 시작했다. 전자투표는 사람에 의한 개표를 기계에 의한 개표로 완전히 대체하기 때문에 기존의 종이투표 시스템보다 오류나 조작 가능성을 낮출 수 있기 때문이다. 그러나 아직까지 종이투표를 완전히 대체할 만한 전자투표 시스템은 등장하지 않았다. 전자투표는 해커들이 선거를 방해하거나 투표를 조작하는 등의 악의적인 공격에 취약하기 때문이다.
최근 들어, 이같은 전자투표 시스템의 보안 문제를 해결하기 위한 방법으로 블록체인이 주목받고 있다. 블록체인은 데이터 무결성을 보장할뿐 아니라, 누구나 투명하게 검증할 수 있다는 점 때문에 선거에 활용하기에 적합한 기술이라고 평가된다. 그러나 공식적인 선거는 이보다 훨씬 많은 조건이 필요하기 때문에, 실제로 선거에 활용될 수 있는 블록체인 기반의 전자투표 시스템을 개발하기 위해서는 더 많은 고민과 연구가 필요한 상황이다.
본 글의 목적은 블록체인 기술이 실제로 공정하고 투명한 선거에 활용될 수 있는 방법을 제안하는 것이다. 우선 공정한 투표 시스템 설계를 위한 필수 조건을 정리하고, 이를 바탕으로 기존 전자투표 시스템의 문제를 진단할 것이다. 최종적으로, 필수 조건을 모두 만족할 수 있는 블록체인 기반의 투표 시스템을 제안하고자 한다.
공정한 투표 시스템 설계를 위한 필수 조건
대한민국 헌법에 의하면, 선거의 기본원칙은 보통 선거, 평등 선거, 직접 선거, 비밀 선거, 그리고 자유선거이다. 전자투표 시스템이 이러한 원칙을 보장하기 위해서는 아래와 같은 조건들을 만족시켜야 한다.
공정한 선거를 보장할 수 있는 투표 시스템이라면, 투표 과정 및 개표 과정에서 시스템 상 어떠한 데이터 조작도 불가능해야 한다. 특히 이를 위해 투표 결과를 검증할 수 있어야 하는데, 구체적으로는 개별 검증성과 전체 검증성을 모두 확보해야 한다.
개별 검증성은 자신의 표가 제대로 기입되었는지 투표자가 직접 검증할 수 있는지의 여부를 의미한다. 가령 1번 후보를 선택한 투표자가 개표 DB에서 자신의 표가 1번으로 입력되었음을 확인할 수 있다면, 개별 검증성이 확보되었다고 볼 수 있다. 전체 검증성은 개표 결과가 조작되지 않았다는 것을 누구나 검증할 수 있는지의 여부를 의미한다. 가령 전체 투표 데이터가 웹상에 공개되어 누구나 투표를 셀 수 있다면 전체 검증성이 확보되었다고 볼 수 있다.
또한, 공정한 투표를 위해 투표자의 투표값이 무엇인지 당사자를 제외한 그 누구도 알 수 없어야 한다. 이는 타인이 자신의 투표값을 알아낼 수 없어야 한다는 것뿐 아니라, 자신이 타인에게 자신의 투표값을 증명할 수 없어야 한다는 것을 의미한다. 전자의 경우, 투표 순간의 물리적 독립성 또는 전자투표 시스템 보안성 확충으로 달성될 수 있다. 실질적으로 달성되기 어려운 것은 후자이다. 이를테면, 투표 검증성을 위해 고안된 투표 영수증의 경우 투표 매매에 악용될 여지가 높다. 투표 매매 및 강압에 의한 투표를 방지하기 위해, 이와 같은 완전 익명성은 시스템 설계 상황에서 반드시 고려되어야 한다.
이상의 조건들을 활용하여 기존의 전자투표 시스템을 평가하고, 보다 완전한 투표 시스템을 제안하고자 한다.
전자투표의 빛과 그림자
현재 시행되고 있는 전자투표 시스템은 투표 장소에 따라 REV 방식과 PSEV 방식으로 구분된다.
REV(Remote internet E-Voting) 방식
REV방식은 PC를 비롯한 다양한 디바이스에서 인터넷에 접속해 원격으로 투표를 하는 방식이다. 웹사이트나 SMS 등으로 이루어지는 모든 형태의 전자투표가 REV 방식에 속한다. 인터넷 상으로 투표를 진행하기 때문에, 투표 주최 측에서 투표용지 및 투표소 설치 등의 물리적 비용이 크게 절감된다. 또한, 투표자가 직접 투표장소에 가지 않아도 되기 때문에 편리하고 접근성을 향상시킬 수 있다는 이점이 있다. REV 방식은 대학 내 선거, 조합장 선거, 정당 경선, 주주총회, 지방선거 등 중소규모의 선거에 널리 활용되는 전자투표 방식이기도 하다.
그러나 REV 방식의 전자투표에서는 투표가 이루어지는 시점에 자신의 투표값을 타인에게 보여 주거나, 타인이 자신의 투표에 영향력을 행사하는 것이 얼마든지 가능해진다. 이는 곧 투표 매매나 강압에 의한 투표의 위험으로 이어진다. 즉 REV방식에서는 비밀 투표의 원칙이 파괴될 여지가 높기 때문에, 공정성이 엄밀하게 지켜져야 하는 선거에는 활용되기 힘들다.
PSEV(Poll Site E-Voting) 방식
PSEV 방식은 기존의 종이투표처럼 투표소에 가서 투표를 하는 방식이다. 다만 투표용지 대신 투표기기를 이용해서 투표값을 입력하는 방식이다. 투표가 종료되면 투표기기에 모인 데이터를 개표기기로 보내서 집계를 진행한다. 일반적으로 투표기기와 개표기기는 하이재킹(Hijacking) 및 해킹의 위험을 없애기 위해 네트워크와 분리되어 있고, 개표 시점이 되면 관리인단에 의해 서로 연결되어 투표기기의 데이터가 개표기기로 이동한다. PSEV 방식 역시 정당이나 지방 단위의 선거에서 널리 활용되고 있으며, 전 세계적으로 전자투표의 대세를 이루고 있다.
PSEV 방식의 전자투표를 활용하면 무효표의 수 및 집계에 걸리는 시간이 현저히 감소한다. 그러나 이 또한 투표의 공정성과 신뢰성 문제를 완전히 해결하지는 못한다. 익명성을 보장하기 위해 투표값에 투표자의 정보가 남지 않기 때문에, 유권자는 자신의 투표값이 집계에 정확히 반영되었는지 확인할 방법이 없다. 또한 서버가 중앙화되어 있기 때문에, 해킹 가능성 및 투표 시스템 개발업체 내부자의 부정행위 가능성이 있다. 중앙 서버가 터지는 등의 문제가 발생할 경우, 기존의 투표값이 무효화되는 가능성도 존재한다. 즉 현재의 PSEV 방식의 전자투표 시스템 상에서는 정확성, 검증성 및 완전성의 원칙들이 지켜지지 않을 수 있다.
투표 영수증
투표 영수증의 예시
PSEV 방식의 전자투표의 신뢰도를 향상하기 위한 방안으로, 투표 영수증에 관한 연구가 진행되어 왔다. 투표자가 투표값을 입력하면 투표기기가 영수증을 발급해주는데, 영수증에는 확률적 암호기법으로 출력된 코드가 찍혀있다. 투표자는 코드를 투표소 게시판에서 확인하거나 인터넷 웹사이트상의 공개 게시판에 입력하여 자신의 투표가 올바르게 집계되었는지 검증할 수 있다. 이를 통해 앞서 언급했던 원칙들, 특히 검증성을 보완할 수 있을 것이다.
그러나 투표 영수증을 도입할 경우, 타인에게 자신의 영수증을 보여 줄 수 있기 때문에 투표 매매 및 강압에 의한 투표에 이용될 여지가 있다. 오히려 기존의 투표 방식에서는 자신이 특정 후보에게 투표했다는 사실을 투표 매수자에게 증명할 길이 없기 때문에, 투표 매매 및 협박의 실효성이 적다. 하지만 투표기기를 이용해서 투표를 하도록 한 뒤 투표 영수증을 가져오라고 한다면 투표 매수가 가능하다. 투표 매수를 방지하기 위해 투표소 밖으로 영수증을 가지고 나갈 수 없게 하는 등의 방식이 제안되기도 했다. 그러나 현재로선 어떤 방식도 완벽하지는 않다.
뿐만 아니라, 이 방식에서는 투표 영수증을 활용한 검증을 완전히 신뢰할 수 없다는 문제가 존재한다. 온라인상에 공지된 투표값과 실제 개표를 할 때 사용되는 집계 데이터가 동일하다는 보장이 없기 때문이다. 즉, 기존의 투표 영수증 방식 하에서는 투표 관리자를 완전히 신뢰할 수 있다는 전제가 있어야 검증성을 보장할 수 있다.
정리하자면,
- PSEV 방식의 전자투표는 신속하고 효율적으로 집계를 할 수 있다는 장점이 있지만 아직 기술적으로 보안성이 완전하지 않다.
- 투표 영수증의 경우 검증성을 확보하는 대신 익명성이 깨질 수 있어 투표 매수의 가능성이 존재한다.
때문에 전자투표 기술이 상용화된 지금도, 대통령 선거와 같이 중요한 선거는 여전히 종이투표로 진행되고 있는 것이다.
블록체인을 통한 문제 해결 가능성
블록체인 상에 기록된 데이터는 위변조가 사실상 불가능하며 검증이 용이하다. 이러한 블록체인의 특성 때문에, 투표 시스템에 블록체인을 적용하고자 하는 많은 시도가 있었다. 본 글에서는 스마트 컨트랙트를 활용한 일반적인 블록체인 투표 시스템의 구성 요소 및 프로세스를 개략적으로 제시하고자 한다.
선거 구성 요소
일반적인 블록체인 투표 시스템의 구성 요소는 선거 관리자, 투표자, 지역 노드, 부트노드로 정의할 수 있다. 선거 관리자(Election administrators)는 선거 유형 정의 및 선거 생성, 투표지(Ballot)의 항목 구체화, 투표자 등록 역할을 수행한다. 선거 관리자 역할은 복수의 신뢰 기관에게 주어진다. 투표자(Voter)는 신원 증명 과정을 거쳐 투표를 진행하고, 자신의 투표를 검증할 수 있다.
지역 노드(District Node)는 해당 지역의 투표지에 접근할 권한을 갖게 된다. 복수의 지역 노드들이 검증하여 합의에 도달한 투표만이 실질적으로 블록체인에 올라가게 된다. 각 지역 노드는 부트노드(Bootnode)를 호스팅할 수 있다. 부트노드는 지역 노드들이 서로를 찾고 소통할 수 있게 도와주는 역할일 뿐, 블록체인 트랜잭션을 따로 저장하지 않는다.
선거 프로세스
일반적인 블록체인 투표 시스템을 활용한 선거는 투표자 등록(Voter registration), 선거 생성(Election creation), 투표(Vote transaction), 투표 집계(Tallying results), 투표 검증(Verifying vote)의 다섯 단계로 프로세스가 진행된다.
투표자 등록(Voter registration)
신원 검증이 된 투표자에 한해 공개키와 개인키가 생성된다. 우선은 신원 확인 및 검증을 위해 정부 차원의 신원 증명 서비스가 개입되는 것을 가정한다. 검증된 각 키페어마다 토큰이 주어지는데, 이는 중복 투표를 방지하기 위한 것이다.
예를 들어, 신원검증을 받은 홍길동은 토큰을 한 단위 받게 된다고 가정하자. 홍길동이 특정 후보자에게 투표를 할 경우, 후보자에게 토큰 한 단위가 전송된다. 이미 투표를 해서 토큰이 없는 키페어의 경우 투표가 되지 않기 때문에 중복 투표를 방지하게 되는 것이다.
투표 자격이 있는 투표자들의 목록은 선거 기간 중에 변경되지 않는 결정적(deterministic) 목록으로, 아래의 선거 생성 과정에 활용된다. 검증된 투표자에 한해 공개키와 개인키를 보관할 수 있도록 월렛이 생성되며, 특정 월렛이 특정 투표자와 매칭되는지 시스템이 알지 못하게 하기 위해 NIZKP(비대화 영지식증명)과 같은 방식을 활용할 수 있다.
선거 생성(Election creation)
우선 투표 관리자들이 선거 생성 컨트랙트(Election creation contract)를 실행한다. 선거 생성 컨트랙트에는 후보자 목록 및 투표 지역 목록이 명시되어 있다. 선거 생성 컨트랙트에 명시된 투표 지역 목록에 한해, 지역마다 투표지(Ballot)가 생성되어 블록체인에 배포된다. 여기서 투표지라 함은 물리적인 투표용지가 아닌, 스마트 컨트랙트로 구현된 것을 의미한다.
투표지 컨트랙트의 경우 투표 지역(Voting district)을 파라미터로 갖고, 해당 투표 지역에 소속된 후보자 목록이 명시되어 있다. 선거가 시작되면, 각 지역 노드는 해당 투표 지역을 파라미터로 가진 투표지 컨트랙트에 대한 권한을 갖게 된다.
투표(Vote transaction)
투표자가 투표를 한다는 것은, 자신의 투표 지역을 파라미터로 가진 투표지 컨트랙트를 호출하는 것을 의미한다. 앞서 언급했듯이 투표자가 투표를 하게 될 경우 토큰이 지불되며, 투표지 컨트랙트는 투표자가 소속된 지역의 지역 노드를 통해 블록체인에 접근하게 된다. 투표자의 투표에 대해 대다수의 지역 노드들이 합의를 이루게 되면, 블록체인에 투표가 올려지게 된다.
투표지 컨트랙트에 의해 투표는 블록체인 상에 트랜잭션의 형태로 저장되고, 투표자는 해당 트랜잭션의 트랜잭션 ID를 통해 자신의 투표를 검증할 수 있다. 투표 검증에 대한 부분은 투표 검증 파트에 구체적으로 서술되어 있다.
투표 트랜잭션에는 트랜잭션 ID, 트랜잭션이 담긴 블록, 헤당 트랜잭션을 전송한 투표지 컨트랙트, 투표값 등이 담기게 된다. 위의 표는 관악구에서 기호 1번을 투표한 투표자의 트랜잭션을 나타내고 있다. 이 트랜잭션에는 투표 장소와 투표값이 담길 뿐, 투표자에 대한 정보는 담기지 않는다는 것이 중요하다.
투표 집계(Tallying results)
스마트 컨트랙트로 구현된 투표지이기 때문에, 투표 집계 과정이 기존 투표 집계 과정에 비해 매우 빠르게 진행된다는 것이 블록체인 투표의 장점이다. 투표지 컨트랙트들이 지역 단위로 집계를 진행한 이후 상위 지역으로 값을 전달하는 방식으로 전체 집계가 진행된다.
투표 검증(Verifying vote)
투표를 완료한 투표자의 경우, 트랜잭션 ID를 통해 해당 투표를 검증할 수 있다. 자신이 소속된 지역의 관공서에 가서 자신의 신분을 증명한 이후, 트랜잭션 ID를 제시한다. 그러면 담당자가 지역 노드를 활성화시킨 이후 해당 트랜잭션 ID가 담긴 블록을 찾아주면, 해당 블록에 기입된 투표값을 확인함으로써 검증이 완료된다.
블록체인 기반의 투표 시스템은 위변조 가능성이 원천 차단된다는 장점이 있으며, 위와 같은 프로세스를 구현할 경우 공정한 선거를 위한 필수 조건들도 상당 부분 만족시킬 수 있다. 그러나 아래의 두 가지 이유로, 이 또한 완전한 투표 시스템이라고 보기는 힘들다.
- 전체 검증성을 달성할 수 없다.
투표자는 자신의 표가 제대로 기록되었다는 사실을 개별적으로 검증할 수 있지만, 전체 개표 결과에 대해 직접 검증할 수는 없다. 비밀 투표를 위해 투표 데이터는 관리 기관에서만 관리되기 때문이다.
2. 완전한 익명성이 달성되지 않는다.
관리기관은 투표자들의 신원과 투표값을 매칭할 수 있다. 아무리 신뢰받는 관리기관이라고 해도, 내가 누구를 뽑았는지 알 수 있는 데이터를 관리기관이 가지고 있다는 사실은 거부감을 일으키기 쉽다.
언뜻 보기에, 전체 검증성과 완전 익명성을 동시에 달성하는 것은 불가능한 것처럼 보인다. 전체 개표 데이터를 누구나 볼 수 있으면서, 나를 제외한 타인의 투표값을 절대 알 수 없어야 한다는 것을 의미하기 때문이다. 하지만 본 글에서는 전체 검증성과 완전 익명성을 달성할 수 있는 메커니즘을 제안하려고 한다. 즉, 본 글에서 제안하는 투표 시스템 상에서는,
- 누구나 개표 DB에 접근해서 자신의 투표값과 전체 개표값을 검증할 수 있다.
- 자신을 제외한 누구도 자신의 투표값을 알 수 없으며, 타인에게 자신의 투표값을 증명할 수 없다.
본 투표 시스템은 위에서 서술된 선거 구성 요소와 선거 프로세스를 기반으로, 투표 영수증에 공개키를 랜덤으로 출력하고자 한다.
투표 과정
투표는 신원인증, 투표, 그리고 영수증 발급의 세 단계로 진행된다.
0) 키페어 할당
- 투표 자격이 있는(eligible) 유권자들의 수만큼 공개키-개인키 쌍을 발급한다.
- 각 공개키 계정에는 투표 토큰이 하나씩(투표 하나당 하나씩) 지급된다.
1) 신원인증
- 투표자는 관리기관이 지정한 투표소에 방문하여 투표 관리인에게 자신의 신원을 증명한다.
- 투표자의 신원이 확인될 경우, 관리인은 투표 토큰을 보유한 공개키 — 개인키 쌍을 블록체인 DB로부터 랜덤추출하여 투표자에게 제공한다. 이때 랜덤추출은 오프체인으로 실행된다.
2) 투표
- 투표자는 투표 기기를 통해 자신이 방금 받은 공개키 주소의 토큰을 원하는 선택지의 컨트랙트로 보낸다. 투표 기기에 공개키와 개인키를 입력하는 과정은 QR코드를 활용하는 등의 방식으로 신속하게 진행되는 것을 전제한다.
3) 영수증 발급
- 투표 기기는 투표가 기록된 공개키 중에서, 각 후보에게 투표한 공개키 하나씩을 랜덤으로 추출하여 인쇄해 준다. 단, 이 중에는 투표자가 방금 투표에 사용한 공개키 주소가 반드시 포함되어 있다.
- 가령, 후보자가 세 명이라고 하자. 투표 영수증에는 1번 후보자에게 투표한 사람이 사용한 공개키, 2번 후보자에게 투표한 사람이 사용한 공개키, 3번 후보자에게 투표한 사람이 사용한 공개키가 찍혀 있다. 그리고 이 중 하나는 방금 투표를 실시한 투표자가 신원인증 이후 랜덤으로 받은 공개키인 것이다.
- 이러한 장치는 투표 매수를 방지하기 위한 것으로, 이를 통해 전체 검증성과 완전 익명성을 동시에 달성할 수 있다.
- 선거 초반에는 투표한 인원이 충분하지 않아서, 아직 표를 받지 못한 후보자가 있을 수 있다. 이를 고려하여, 본 시스템에서는 후보자들이 자신에게 스스로 투표하는 것을 전제한다. 즉, 선거가 개시된 이후 첫번째로 투표한 사람의 경우 자신이 투표에 사용한 공개키, 그리고 나머지 후보자들 각각이 투표에 사용한 공개키가 영수증에 출력될 것이다.
4) 개표 단계
- 투표가 종료된 후 각 선택지 컨트랙트에 모인 토큰의 수를 확인하는 것으로 개표를 실행한다.
- 개표 단계에서는 누구나 블록체인상에 기록된 데이터를 확인할 수 있다. 따라서, ‘투표자’는 영수증에서 자신이 투표에 사용한 공개키를 블록체인에서 찾아서 올바르게 투표가 입력되었는지 검증할 수 있으며(개별 검증성) 누구나 전체 데이터를 바탕으로 올바르게 개표가 이루어졌음을 검증할 수 있다(전체 검증성).
예시를 통해 위 과정을 구체적으로 서술하면 다음과 같다. 후보 1번, 2번이 출마한 선거를 가정하자. 아래는 투표자 최씨가 투표소에 방문한 현재 블록체인에 기록된 데이터의 일부이다. ‘투표 상태’는 각 공개키에서 토큰을 보낸 후보 번호이며, 아직 투표하지 않은 공개키는 0으로 표시된다.
- 최씨가 투표소에서 신원을 인증하자, 관리인은 투표상태가 0인 공개키 가운데 랜덤추출을 통해 공개키 IJKL과 그에 해당하는 개인키를 제공했다. 이때 관리인은 자신이 제공한 키 쌍이 무엇인지 알 수 없다.
- 최씨는 IJKL의 비밀키로 후보 1번에 토큰을 보냈고 이는 투표 기기에 의해 블록체인에 전파되었다. 최씨의 투표 이후, 투표 상태는 아래와 같이 바뀌었다.
3. 투표 기기는 다음과 같은 영수증을 출력해 줄 것이다. 최씨가 후보 1번에 투표할 때 사용한 공개키인 IJKL, 그리고 후보 2번에 투표한 공개키 중 하나인 QRST가 출력된다.
4. 투표가 모두 끝나고, 블록체인에 기록된 모든 공개키 투표값들이 다음과 같이 공개된다.
5. 최씨는 영수증에 적혀 있는 IJKL에 해당하는 투표값을 확인함으로써 자신의 투표가 올바르게 기록되었다는 사실을 확인할 수 있다. 하지만 최씨의 영수증을 본 다른 사람은 이 중 최씨가 투표에 사용한 공개키가 있다는 사실만 알 뿐, 실제로 어떤 후보에게 투표했는지는 알 수 없다.
이같은 방식에는 공개키 — 개인키 쌍의 안전한 보관을 위해 투표 관리자를 신뢰해야 한다는 한계가 존재한다. 하지만 모든 투표자는 블록체인상에 공개된 데이터를 통해 자신의 투표값을 투명하게 검증할 수 있으므로, 개인키와 공개키를 보관하는 투표 관리자가 처벌의 위험을 감수하고 투표값을 위변조하는 일은 발생하지 않을 것이다.
결론
본 글에서는 블록체인을 활용해 위변조가 불가능한 투표시스템을 구상하되, 기존의 전자투표 중 PSEV 방식이 가진 검증성과 익명성의 tradeoff 문제를 해결할 수 있는 블록체인 투표 시스템의 구성 요소 및 프로세스를 제시해보았다. 전체 검증성과 완전 익명성을 충족시키기 위해 본 글은 공개키를 랜덤 셔플하는 방식의 장치를 제안하였다.
현재까지 등장한 보안기술 가운데 블록체인은 투표의 검증성과 투명성, 그리고 보안성을 동시에 보장하는 거의 유일한 기술로 평가되고 있다. 본 글에서 제시한 방안이 아니더라도, 블록체인 기반 투표시스템이 전시행정의 수단이 아니라 기존 선거 시스템을 대체할 수 있을 만한 완전성을 갖추기 위해 앞으로 더 많은 연구가 필요할 것이다.
