원문 제목：《Building Cicada: Private on-chain voting using time-lock puzzles》

저자：Michael Zhu，a16z

편집：Lynn，MarsBit

모든 의미 있는 방식으로 작동하는 투표 시스템은 완전성과 투명성에 의존합니다. 표면적으로 볼 때, 이는 블록체인이 이러한 시스템을 구축하는 이상적인 플랫폼이 되게 합니다------실제로 많은 분산 조직이 집단 의도를 표현하기 위해 무허가 투표를 채택했습니다. 이는 종종 막대한 재산을 휘두르거나 주요 프로토콜 매개변수를 조정하는 상황에서 이루어집니다. 그러나 체인 상 투표에도 단점이 있으며, 개인 정보 보호가 아직 탐색되지 않고 개발되지 않았습니다. 이는 Web3 투표 시스템에 불리합니다------현재 사용 중인 대부분의 체인 상 투표 프로토콜에서 투표용지와 투표 결과는 완전히 공개됩니다. 개인 정보 보호가 없다면, 투표 결과는 쉽게 조작될 수 있으며 유권자 동기 부여가 잘못될 수 있어 비민주적인 결과를 초래할 수 있습니다.

이것이 우리가 Cicada를 발표하는 이유입니다: 시간 잠금 퍼즐과 제로 지식 증명을 활용하여 개인 체인 상 투표를 구현하는 새로운 오픈 소스 Solidity 라이브러리입니다. 기존 시스템과 비교할 때, Cicada는 새로운 개인 정보 보호 속성을 가지고 있으며, 신뢰 가정을 최소화하고 이더리움 메인넷에서 사용할 수 있을 만큼 효율적입니다.

이 글에서는 투표 개인 정보 보호의 현황을 조사하고 Cicada가 어떻게 작동하는지에 대한 높은 수준의 설명을 제공합니다(정식 증명은 곧 공개될 예정입니다). 또한 개발자들이 GitHub 저장소를 확인하도록 권장합니다------Cicada는 다양한 투표 계획과 기능을 지원하기 위해 여러 방식으로 조정 및 확장될 수 있으며, 우리는 커뮤니티와 협력하여 이러한 가능성을 탐색하고자 합니다.

개인 투표에 대한 간략한 조사

어떤 투표 시스템(체인 상 또는 기타)에서도 고려해야 할 여러 다른 수준의 개인 정보 보호가 있습니다. 개별 투표용지의 공개, 진행 중인 집계 및 유권자 신원은 유권자의 동기 부여에 다양한 방식으로 영향을 미칩니다. 어떤 개인 정보 보호 속성이 필요한지는 투표의 맥락에 따라 다릅니다. 암호학 및 사회 과학 문헌에서 자주 등장하는 몇 가지는 다음과 같습니다:

• 투표용지 개인 정보 보호: 비밀 투표용지, 즉 "호주 투표"는 현실 세계의 투표 시스템을 위해 개발된 것으로, 개인 유권자의 선호를 유지하고 뇌물 및 강요를 완화하는 방법입니다(체인 상 설정에서는, 우리는 투표용지 개인 정보 보호보다 더 강력한 속성이 필요할 수 있습니다------아래의 "영수증 없음"을 참조하십시오). 투표용지 개인 정보 보호는 사회적 기대 편향을 완화할 수도 있습니다------즉, 다른 사람들이 자신의 선택에 대해 어떻게 생각하는지에 따라 투표하는 압력이 줄어듭니다.
• 진행 중인 집계의 개인 정보 보호: 많은 투표 시스템은 유권자가 여전히 투표 중일 때 진행 중인 집계를 숨기거나 각 옵션에 대해 얼마나 많은 투표가 이루어졌는지를 숨겨 투표율과 유권자 동기에 영향을 미치지 않도록 합니다. 우리는 현실 세계에서 이러한 경우를 보았습니다; 예를 들어, 늦게 투표하는 미국 상원의원은 일찍 투표하는 상원의원보다 더 가능성이 높습니다 그들의 정당과 일치합니다. 체인 상에서는: 토큰 가중 투표에서, 고래는 상대방이 앞서도록 하여 그들의 잘못된 안전감을 조작할 수 있습니다(일부는 어차피 이길 것이라고 가정하여 투표를 게을리할 수 있습니다), 그런 다음 마지막 순간에 자신의 투표용지를 던져 결과를 좌우할 수 있습니다.
• 유권자의 익명성: 많은 현실 세계의 투표 시스템에서, 당신의 투표는 공개되지 않지만, 당신이 투표했다는 사실은 종종 공개됩니다. 이는 유권자 사기를 방지하는 데 중요합니다. 왜냐하면 투표자의 기록을 공개하면 다른 사람들이 그들의 이름으로 투표했는지 확인할 수 있기 때문입니다. 그러나 체인 상에서는, 우리는 암호학적 원리를 사용하여 유권자 사기를 방지하면서 익명성을 유지할 수 있습니다------예를 들어, Semaphore를 통해, 당신은 제로 지식으로 당신이 아직 투표하지 않은 자격 있는 유권자임을 증명할 수 있습니다.
• 영수증 없음: 개인 유권자는 그들이 어떻게 제3자에게 투표했는지를 증명하기 위해 자신의 투표용지의 "영수증"을 제공합니다. 그렇지 않으면 매표가 발생할 수 있습니다. 밀접하게 관련된 그러나 더 강력한 속성은 강요 방지로, 이는 누군가가 유권자에게 특정 방식으로 투표하도록 강요하는 것을 방지할 수 있습니다. 이러한 속성은 분산 환경에서 특히 매력적입니다. 왜냐하면 투표권이 스마트 계약 시장을 통해 유동성을 가질 수 있기 때문입니다. 불행히도, 이러한 속성을 구현하는 것은 어렵습니다------실제로, Juels 등은 신뢰할 수 있는 하드웨어 없이 무허가 환경에서 이것이 불가능하다고 지적했습니다。

Cicada는 진행 중인 집계 개인 정보 보호에 중점을 두지만(우리가 나중에 논의할 것처럼), 이는 제로 지식 그룹 구성원 증명과 결합하여 유권자의 익명성과 투표용지 개인 정보 보호를 달성할 수 있습니다.

Cicada 소개: 동형 시간 잠금 문제에서의 집계 개인 정보 보호

진행 중인 집계의 개인 정보 보호를 달성하기 위해, Cicada는(우리가 아는 한) 이전에 체인 상에서 사용된 적이 없는 암호학적 원리를 활용합니다.

첫째, 시간 잠금 문제(Rivest, Shamir, Wagner, 1996)는 비밀을 감싸고 있으며, 특정 시간 이후에만 공개될 수 있는 암호 문제입니다------더 구체적으로 말하면, 이 문제는 반복적으로 일부 비병렬 계산을 수행하여 해독할 수 있습니다. 투표의 맥락에서 시간 잠금 문제는 진행 통계의 개인 정보 보호를 달성하는 데 유용합니다: 사용자는 그들의 투표용지를 시간 잠금 문제로 제출할 수 있으며, 이로 인해 투표 과정에서 비밀이 유지되지만 투표 후에는 공개될 수 있습니다. 다른 대부분의 개인 투표 구조와 달리, 이는 진행 통계 개인 정보 보호가 통계 기관(예: 선거 직원이 종이 또는 디지털 투표용지를 계산하는 것) 또는 임계값 암호화(여러 신뢰할 수 있는 당사자가 메시지를 해독하기 위해 협력해야 함) 또는 기타 신뢰할 수 있는 당사자에 의존할 필요가 없음을 의미합니다: 누구나 시간 잠금 문제를 해결하여 투표 후 결과가 공개되도록 할 수 있습니다.

둘째, 동형 시간 잠금 문제(Malavolta Thyagarajan, 2019)는 비밀 키를 알고 있거나 문제를 해독하거나 백도어를 사용할 경우 암호화된 값에 대한 일부 계산이 가능하다는 추가 속성을 가지고 있습니다. 특히, 선형 동형 시간 잠금 문제는 우리가 문제를 결합하여 원래 문제의 비밀 값의 합을 감싸는 새로운 문제를 생성할 수 있게 합니다.

논문의 저자들이 지적한 바와 같이, 선형 동형 시간 잠금 문제는 개인 투표에 특히 적합한 원리입니다: 투표용지는 문제로 인코딩될 수 있으며, 이들은 동형적으로 결합되어 최종 집계를 인코딩하는 문제를 생성할 수 있습니다. 이는 각 투표용지에 대해 고유한 문제를 해결하는 대신, 최종 결과를 공개하는 데 단 한 번의 계산만 필요함을 의미합니다.

새로운 구조: 효율성과 균형

투표 계획을 체인 상에서 실용적으로 만들기 위해서는 몇 가지 문제를 고려해야 합니다. 첫째, 공격자는 잘못된 인코딩된 투표용지를 제출하여 투표를 조작하려고 할 수 있습니다. 예를 들어, 우리는 각 투표용지의 시간 잠금 문제가 부울 값으로 인코딩되기를 원할 수 있습니다: "1"은 투표된 제안을 지지함을 나타내고, "0"은 반대를 나타냅니다. 열정적인 제안 지지자는 예를 들어 "100"으로 인코딩하여 그들의 유효 투표권을 확대하려고 할 수 있습니다.

우리는 유권자가 투표용지를 제출할 때 유효성에 대한 제로 지식 증명을 함께 제출하도록 하여 이러한 공격을 방지할 수 있습니다. 그러나 제로 지식 증명의 계산 비용은 매우 높습니다------유권자의 참여 비용을 가능한 한 낮추기 위해, 증명은 (1) 클라이언트에서 효율적으로 계산 가능하고 (2) 체인 상에서 효율적으로 검증 가능한 것이어야 합니다.

증명을 가능한 한 효율적으로 만들기 위해, 우리는 특정 대수 관계를 위해 설계된 제로 지식 증명인 맞춤형 시그마 프로토콜을 사용했습니다. 이는 증명자의 시간이 매우 빠르다는 것을 의미합니다: Python으로 투표용지 유효성 증명을 생성하는 데, 일반 노트북에서 14ms가 소요됩니다.

이 시그마 프로토콜의 검증자는 개념적으로 매우 간단하지만, 상당한 양의 큰 모듈 거듭제곱이 필요합니다. Malavolta와 Thyagarajan의 선형 동형 계획은 Paillier 암호화를 사용하므로, 이러한 거듭제곱은 특정 RSA 모듈 N에 대해 N\^2로 수행됩니다. 합리적인 크기의 N에 대해, 대부분의 EVM 체인에서 거듭제곱은 매우 비쌉니다(수백만 가스). 비용을 줄이기 위해, Cicada는 지수 ElGamal을 사용합니다------지수 ElGamal은 여전히 가산 동형성을 제공하지만 더 작은 모듈(N 대신 N\^2)에서 작동합니다.

ElGamal을 사용하는 한 가지 단점은 해독 카운트의 마지막 단계가 이산 로그를 무차별 대입으로 풀어야 한다는 것입니다(참고: 이는 체인 외부에서 수행되며 체인 상에서 유효하게 검증됩니다). 따라서 이는 예상되는 최종 투표 수가 상당히 작은 경우(예: 2\^32 미만, 즉 약 430만 표)에서만 적용됩니다. 초기 Paillier 기반 계획에서는 크기에 관계없이 카운트를 효율적으로 해독할 수 있었습니다.

RSA 모듈 N을 선택하는 것도 균형을 포함합니다. 우리의 구현은 가스 효율성을 높이기 위해 1024비트 모듈을 사용합니다. 이는 역사상 공개적으로 분해된 최대 RSA 모듈(829 비트)보다 훨씬 높지만, RSA 암호화 또는 서명에 대해 일반적으로 권장되는 크기인 2048비트보다 낮습니다. 그러나 우리의 응용 프로그램은 장기적인 보안성을 필요로 하지 않습니다: 선거가 끝난 후, 미래에 N을 고려하는 데 위험이 없습니다. 카운트와 투표용지가 시간 잠금 기간이 만료된 후 공개된다고 가정하므로, 상대적으로 작은 모듈을 사용하는 것은 합리적입니다. (분해 알고리즘이 개선되면, 이는 미래에 쉽게 업데이트될 수 있습니다.)

익명성과 유권자 자격

위에서 언급한 바와 같이, Cicada는 진행 집계 개인 정보 보호를 제공합니다------시간 잠금 문제 속성이 투표 기간 동안 집계의 비밀을 유지합니다. 그러나 각 개별 투표용지도 동일한 공개 매개변수 하에 암호화된 시간 잠금 문제입니다. 이는 카운트를 해독할 수 있는 것처럼(필요한 계산을 수행하여) 각 투표용지도 해독할 수 있음을 의미합니다. 다시 말해, Cicada는 투표 기간 동안만 투표용지 개인 정보 보호를 보장합니다------호기심 많은 관찰자가 특정 유권자의 투표용지를 해독하고자 한다면, 그렇게 할 수 있습니다. 특정 개인 투표용지를 해독하는 것은 최종 집계를 해독하는 것만큼 비쌉니다. 따라서 n명의 유권자가 있는 경우, 완전히 해독하는 데 O(n)의 작업이 필요합니다. 그러나 모든 이러한 투표용지는 병렬로 해독될 수 있습니다(충분한 기계가 있다고 가정할 때), 소요되는 시계 시간은 최종 집계를 해독하는 데 필요한 시간과 동일합니다.

일부 투표용지의 경우, 이는 바람직하지 않을 수 있습니다. 우리는 진행 중인 집계 개인 정보 보호에 만족하지만, 무기한 투표 개인 정보 보호를 원할 수 있습니다. 이를 달성하기 위해, 우리는 Cicada를 익명 유권자 자격 프로토콜과 결합하여 제로 지식 그룹 구성원 증명을 통해 인스턴스화할 수 있습니다. 이렇게 하면 투표용지가 해독되더라도, 그것이 드러내는 것은 단지 누군가가 이런 방식으로 투표했다는 것뿐입니다------우리는 이미 집계에서 이를 알고 있습니다.

우리의 저장소에는 Semaphore를 사용하여 유권자 익명을 위한 예제 계약이 포함되어 있습니다. 그러나 Cicada 계약 자체는 유권자 자격을 결정하거나 실행하는 방법에 대한 어떤 가정도 하지 않습니다. 특히, Semaphore를 Semacaulk 또는 ZK 상태 증명(예: 여기 및 여기에서 제안된 것)으로 대체할 수 있습니다.

통계 기관

우리가 Cicada를 설계할 때 가장 중요한 목표 중 하나는 통계 기관의 필요성을 피하는 것이었습니다: 많은 개인 투표 구조는 반신뢰할 수 있는 통계 기관(또는 안전한 다자간 계산을 통해 조정되는 권한 위원회)이 투표용지를 수신하고 집계해야 합니다. 블록체인 환경에서는 이러한 계획이 스마트 계약만으로 실행될 수 없으며, 일부 인적 개입과 신뢰가 필요합니다.

대부분의 구조에서, 집계 기관은 완전성 측면에서 신뢰할 수 없지만(그들은 투표용지 수를 조작할 수 없습니다), 활성 측면에서는 신뢰할 수 있습니다------그들이 오프라인 상태일 경우, 최종 결과를 계산할 수 없으므로 투표 결과를 무기한 지연시킬 수 있습니다. 일부 구조에서는 그들이 개인 정보 보호를 유지하는 것도 신뢰받습니다------즉, 그들은 모든 사람이 어떻게 투표했는지 알고 있지만, 이 정보를 공개하지 않을 것으로 예상됩니다.

많은 현실 세계의 시나리오에서 통계 기관은 합리적(그리고 필요)인 가정이지만, 블록체인 환경에서는 이상적이지 않으며, 우리의 목표는 신뢰를 최소화하고 검열 저항을 보장하는 것입니다.

Cicada는 체인 상 투표 개인 정보 보호 분야의 여러 방향을 탐색하며, 다른 팀이 진행 중인 대부분의 연구를 보완합니다. 위에서 언급한 바와 같이, Cicada는 신호량, ZK 저장 증명 및 속도 제한 무효화기와 같은 익명 그룹 구성원 기술과 밀접하게 관련되어 있습니다. Cicada는 또한 Nouns Vortex 팀이 제안한 낙관적 증명 검사기와 통합하여 유권자의 가스 부담을 줄일 수 있습니다.

Cicada를 다양한 투표 계획(예: 토큰 가중 투표, 이차 투표)을 지원하도록 조정할 기회도 있습니다------더 복잡한 계획은 이더리움 메인넷에서 계산 비용이 너무 높을 수 있지만, L2에서는 실용적일 수 있습니다. 이를 염두에 두고, 우리는 Cicada를 다음 단계로 가져가는 데 기여, 포크 및 제안을 환영합니다.