제곱투표를 이용한 컨퍼런스 프로포절 심사 - 전자 투표 시스템을 향하여

이드콘 발표자 심사과정

한국에서 열리는 첫번째 한국 이더리움 개발자 컨퍼런스인 이드콘 준비를 위해 많은 분들이 도와주고 계신데요, 뜻 깊은 행사인 만큼 많은 분들이 발표신청을 해주셨습니다. 예상보다 너무 많은 프로포절이 들어와서 이를 공정하게 심사하는 것도 쉽지 않은 일이었습니다.

그래서 한번에 많은 수의 프로포졀을 여러사람들이 효과적으로 심사하기 위해서, 제곱투표 (https://en.wikipedia.org/wiki/Quadratic_voting) 기법을 사용해 보았습니다.
각 심사자들이 100점 만점기준으로 각 프로포절들을 점수 매기는 방식이 아니라 (예를 들어 프로포절 A는 90점, B는 75점 등), 각 심사자는 100점을 각 프로젝당 0에서 10점씩 분배해서 할당시키는 방법입니다. 투표 규칙은 다음과 같았습니다.

제곱투표 심사규칙

  1. 심사는 2 라운드에 걸쳐서 이루어지고, 1 라운드에서 전체 세션수의 50%, 2라운드에서 50%를 결정함.

  2. 각 라운드에서 각 심사위원은 총 100점을 "반드시 선정되어야 한다고 생각하는 프로젝"에 나누어 기입한다. 단, 하나의 프로젝에 10점 이상을 초과해서 부여할 수 없음.
    예들 들어, 10개의 발표를 선정해서 10점씩 줄수도 있고, 20개의 프로젝에 5점씩, 또는 10개에 8점씩, 20개에 1점씩 등으로 마음데로 배분할 수 있다. 단 정수배분만 가능함.

  3. 각 라운드에서 각 심사위원이 부여한 점수를 그냥 합계를 내서 순위를 정하는 것이 아니라, 심사위원이 부여한 점수의 루트값을 구해서 이 루트합의 순위로 각 라운드에서 할당된 수만큼의 발표자를 선정함. (quadratic voting).

  4. 투표는 비밀투표이고, 심사 종료후 각 프로포절당 최종 루트값과 순위만 집계되어 심사위원들에게 공유됨.

자 이러한 방법으로 예를 들어 100개의 프로포절을 11명의 심사위원들이 심사를 해서 1라운드에 25개, 2라운드에서 25개, 총 50개의 프로포절을 선정해야된다고 가정해 봅시다 (실제 응모한 전체 프로포절 수는 이와 좀 다릅니다).

다음 그림은 실제 투표 결과의 일부분입니다.

이런 방식으로 라운드1, 라운드2 투표를 집계해서 제곱근합의 순위로 각각 30개와 24개의 프로포절이 최종 선정되었습니다.

제곱투표를 사용하는 가장 큰 장점은, 각각의 선택지에 대해 가중치를 두는 효과를 만들 수 있다는 것입니다. 각 심사자는 많은 프로포절이 다루는 여러가지 상이한 주제들에 대해 전부 전문적으로 잘 알기는 매우 힘듭니다. 특정한 프로포절의 주제에 대해 별 관심이 없을 수도 있고, 잘 모를 수도 있습니다. 반면 특정 주제에 대해서는 이번에 이것이 꼭 발표되어야 한다고 매우 강하게 생각할 수도 있습니다. 이런 관심도(또는 평가점수)를 모두 단순한 스케일로 평가하는 것은 각 평가자들이 각 프로포졀에 대해 가지는 중요성의 강도(intensity)를 충분히 반영하기 힘듭니다. 반면 이러한 선호도의 강렬함이 직선(linear) 함수로 표현되는 것은 너무 과도한 집중이 될 수 있기 때문에, 결과를 평가할 때는 루트값을 사용합니다. 강렬함을 표시하는 코스트의 입장에서 보면 강렬함을 증가시키 위한 코스트가 제곱으로 늘어가는데, 그래서 이런 기법을 제곱투표라고 합니다. 이러한 제곱투표는 여러 영역에 여러가지 방식으로 적용가능합니다.

리커트 스케일 vs 제곱투표(QV)

제곱투표와 일반적인 리커트 스케일(Likert scale)을 사용한 서베이의 차이를 연구해본 좋은 논문(http://www.sci.sdsu.edu/crmse/msed/papers/Quarfoot2.pdf)이 있습니다. 리커트 스케일은 흔히 볼 수 있는 선호도 조사방식인데 예를 들어 “매우찬성, 찬성, 중립, 반대, 매우 반대” 이런 식의 5개 중 하나를 선택하게 만드는 방식입니다. 다음과 같은 미국의 주요 정치 현안에 대한 찬반 의견을 제곱투표와 리커트 서베이 두가지 방식으로 진행했다고 합니다.

  1. Requirement for background checks for all gun purchasers.
  2. Elimination of the Affordable Care Act of 2010 (aka ‘Obamacare’).
  3. Raise the minimum wage from $7.25 to $10.10 over the next 3 years.
  4. Nationwide ban on abortion in nearly all circumstances.
  5. Sharp reduction of federal and state programs intended to help the poor with costs
    of food, shelter and education.
  6. Immediate deportation of any person who is found to be living in the United States
    illegally.
  7. Raise taxes on corporations and the wealthy to combat income inequality.
  8. Send large numbers of US ground troops to fight ISIS militants in Syria and Iraq.
  9. Do not allow Syrian refugees into the United States.
  10. Legally require employers generally to pay women the same salary as men receive
    for the same work.


(출처: http://www.sci.sdsu.edu/crmse/msed/papers/Quarfoot2.pdf)

위의 표는 두명의 투표자가 리커드 스케일링과 QV 방식에서 어떤 차이를 보여주었는지를 예시한 것입니다. 왼쪽 투표자의 경우 리커드 방식의 점수 부여와 QV 방식간에 큰 차이를 보여주지 않습니다. 리커드에 비해 조금 더 호불호가 분명히 보인다는 정도의 차이가 있습니다. 반면, 오른쪽 투표자의 경우는 리커드 스케일링과 QV간에 매우 큰 차이를 보여줍니다. 리커드 스케일링일 때, 거의 모든 이슈들에 대해 큰 선호도 차이를 보여주지 않았는데, QV에서는 "최저임금, 부자에 대한 증세, 남여차별 임금 반대"에 대해 매우 큰 목소리를 내고 있습니다. 다른 이슈들에게 갈 점수를 모아서 이 세가지의 이슈에 대해 중점 투표했습니다. 이 사람에게는 이 이슈들이 다른 이슈들에 비해 훨씬 더 절박한 것들이라는 것을 표현한 것이지요. 여론 형성에는 이러한 절박한 사람들의 목소리가 매우 중요한데, 일반적인 리커드 스케일의 선호도 조사에서는 이를 잘 반영하기 힘든 반면, QV는 그 강도를 좀 더 부각시켜서 반영할 수 있다는 이야기입니다.

전자투표 시스템의 딜레마

전자 투표 시스템에 대해 상당한 오랜 시간동안 많은 사람들이 연구를 하고 실험을 해왔지만, 아직도 매우 일반화되고 있지는 못합니다. 정책 결정이나 법안 통과를 위한 여론조사나, 공정한 결정이 필요한 심사위원회 투표, 법적 효력이 있는 선거 등 다양한 영역이 전자 투표 시스템이 적용될 수 있는 영역이 되겠지만, 활성화되고 있지 못하는 데에는 생각보다 투표가 요구하는 여러가지 속성들(properties)를 다 만족시키가 매우 어렵다는 이유도 있습니다(물론 정치적인 이해관계도 전자투표 시스템의 확산에 큰 걸림돌이기도 합니다).

당장 위의 이드콘 프로포절 심사과정과 결과처리를 전자투표방식으로 구현하려고 보면, 의외로 간단치 않은 문제들이 생깁니다. 그 중에서도 가장 해결하기 쉽지 않은 부분이 “비밀” 투표, 즉 투표내용의 secrecy 입니다. 투표의 종류의 따라 비밀투표가 필요한 경우도 있고, 아닌 경우도 있겠지만, 비밀투표가 필수적인 요건일 때가 많습니다.

우선 중앙화된 모델을 사용한다고 가정해 봅시다. 심사자 각각 심사결과를 자신의 프라이빗키로 인코딩해서 그 결과를 집계자에게 제출하고, 집계자는 심사자의 공개키로 그 결과를 디코딩해서 집계 공표하면 될 것입니다. 그런데 이 집계자가 정확히 집계를 했는지, 어떤 조작이 있었는지를 검증하기 위해, 별도의 조사관이 있어야 합니다. 이 과정에서 각각의 심사자는 다른 심사자의 심사 결과를 볼 수 없지만, 집계자와 조사관은 전체 내용을 다 볼 수 있기 때문에, 진정한 의미에서의 비밀성은 지켜지지 않습니다. 또한 집계자와 조사관의 담합 가능성도 여전히 남아 있습니다.

그럼 집계를 스마트 컨트랙을 사용하고, 투표의 룰을 공평하게 강제하기 위해 스마트 컨트랙을 사용한다고 가정해 봅시다. 외부의 집계자를 별도로 두지 않는다고 했을 때, 어떻게 비밀 투표를 구현할 수 있을까요?

첫번째 방법은, 각 심사자가 자신의 투표 결과를 자신의 프라이빗키로 인코딩해서 결과를 스마트컨트랙에 보내고, 투표마감 시간이 끝난후, 각자 커밋한 투표의 내용을 공개(reveal)하는 것입니다 (commit-reveal scheme). 이 방법을 쓰면, 투표마감 전까지는 투표의 내용을 알 수 없기 때문에 비밀투표의 성격을 일부 만족시킵니다. 그리고 투표내용 공개가 끝난후 나온 각 심사자의 점수가 원래 정한 규칙에 어긋남이 있었는지 여부도 스마트 컨트랙에 의해 검증이 가능합니다. 하지만 여기서 문제는 결국 개별 심사자의 투표결과가 공개된다는 점입니다. 두가지 차원의 비밀성 문제가 있는데, 하나는 투표자-투표내용간의 연결고리이고 다른 하나는 개별 투표내용 자체의 공개입니다. 이 두 문제를 해결하는 방식은 각각 다를 수 있는데, 둘 다 해결이 쉽지는 않아 보입니다.

전자 투표 시스템이 갖추어야 할 주요 속성

비밀투표 요건외에도 전자 투표 시스템이 갖추어야 할 요건들은 여러가지가 있을 수 있습니다. 일반화시키면 이런 요건들이 해당될 것 같습니다.

  • integrity - 투표 프로세스, 집계, 결과에 integrity가 보장되어야 함.
  • verifiability - 위의 integrity 를 검증할 수 있어야 함.
  • privacy - 투표자의 신원과 투표내용의 프라이버시는 보장될 수 있어야 함.
  • secrecy - 필요할 경우 투표내용의 공개없이 집계가 가능하고 이것을 검증할 수 있어야 함.
  • security - 투표 결과를 조작하거나, 공격하는 행위에 대해 적절한 보안장치가 있어야 함.
  • transparency - 투표의 전과정과 규칙들이 투명하게 공개되어 있고, 이것이 집행되는지를 확인할 수 있어야 함.
  • fairness - 참여자 모두가 동등한 권리를 부여 받고 시스템을 이용할 수 있어야 함.
  • efficiency - 이러한 시스템을 사용하는 것이 안하는 것보다 더 효율적이어야 함.
  • reliability - 시스템이 안정적으로 작동한다는 것이 보장되어야 함.

이러한 속성들을 모두 완벽하게 충족시키기는 쉽지 않고, 경우에 따라서는 일부 속성이 반드시 필요한 것이 아닌 경우도 있을 것입니다.

스마트 컨트랙, 동형암호, sMPC(secure multi party computation), ZKP

제곱투표를 어떻게 활용해 볼까하는 문제의식에서 글이 출발했는데, 일반화된 전자 투표 플랫폼의 개념으로 확장되고 말았습니다. 제곱투표도 투표의 한가지 형태라고 한다면, 일반화된 투표 플랫폼이 구현될 수 있다면 쉽게 셋업이 가능할 듯 합니다.

위에서 전자투표가 갖추어할 여러가지 속성들을 구현하려면, 최신의 암호학적 연구성과들을 수용해야만 될 것이라 봅니다.

  • 스마트 컨트랙 - 전체 투표 시스템의 정합성을 보장하고, 규칙을 강제하기 위해서는 스마트 컨트랙의 사용이 거의 필수적일 것이라 봄.
  • 동형암호(homomorphic encryption) - 투표내용을 공개하지 않은 상태로, 즉 인크립션 된 상태로 집계하기 위해서는 여러가지 방식의 동형암호 기법이 필요함.
  • secure MPC - security, privacy, secrecy, verifiability 등의 속성을 충족하기 위해 secure secret sharing 을 비롯한 여러가지 방식의 sMPC 기법이 필요
  • ZKP - sMPC의 핵심 컴포넌트로 사용될 수도 있고, 독자적인 컴포넌트가 될 수도 있음

스마트 컨트랙과 암호학에 기반한 일반화된 투표 플랫폼이 개발될 수 있다면, 그 활용영역은 매우 많을 것이고, 당장 QV 같은 새로운 형태의 평가 또는 서베이 기법들을 구현해 볼 수 있을 것입니다.

4 Likes

정말 좋은 도메인이라 생각합니다. 좀 더 기술적 첨언을 하자면…
제곱투표의 경우 곱하기와 더하기가 동시에 가능한 full homomorphic이 필요합니다. 다만 한두번의 연산만 한다면 somewhat homomorphic으로도 가능하고요. 전자는 넘 느려서 쓰기 어렵고요. 후자는 적용 가능할거 같습니다.
Secure mpc의 경우 단순 적용하면 이해 관계자가 모두 온라인 상태여야 하므로 네트웍 구성에서 좀 더 구조화가 필요할거 같아요. 또한 컨트랙이 verifiable 속성을 부여한다면 금상첨화죠.

투표하는 집단의 사이즈가 아주 작다면 모르겠지만, 일반적으로는 투표과정 자체는 non-interactive 프로세스가 되어야 할 것 같고요, 집계와 집계의 검증과정이 (1) 스마트컨트랙에 의해 계산되거나 (2) 오프체인 컴퓨테이션에서 계산되고 오픈할 결과만 온체인으로 들어오되, 이 결과에 대해 챌린지 할 수 있게 하거나 (3) 집계를 담당하는 비교적 소수의 인원간의 sMPC 로 처리하거하 해야 될 것 같습니다.
필요하면, 스마트 컨트랙을 플라즈마체인으로 내려야 될 지도 모르겠네요.