a16z: Cicada가 온체인 투표를 위해 타임록 퍼즐과 ZK 증명을 활용하는 방법
원저자:Michael Zhu
원본 편집: Lynn, MarsBit
원저자:원본 편집: Lynn, MarsBit의미 있는 방식으로 작동하는 모든 투표 시스템은 무결성과 투명성에 의존합니다. 표면적으로 이것은 블록체인을 이러한 시스템을 구축하기 위한 이상적인 플랫폼으로 만듭니다. 실제로 많은 분산 조직이 채택했습니다.허가 없이 투표종종 상당한 부를 휘두르거나 주요 프로토콜 매개 변수를 조정하면서 집단적 의도를 표현합니다. 그러나 온체인 투표에는 단점도 있습니다.
프라이버시는 미개척 및 미개척 상태로 남아 있습니다.
, Web3 투표 시스템에는 좋지 않습니다. 오늘날 사용되는 대부분의 온체인 투표 프로토콜에서 투표 및 투표 결과는 완전히 공개됩니다. 프라이버시가 없으면 투표 결과가 쉽게 조작되고 유권자 인센티브가 잘못 조정되어 잠재적으로 비민주적인 결과를 초래할 수 있습니다.이것이 우리가 타임록 퍼즐과 영지식 증명을 활용하여 비공개 온체인 투표를 가능하게 하는 새로운 오픈 소스 Solidity 라이브러리인 Cicada를 출시하는 이유입니다. 기존 시스템과 비교하여 Cicada는 새로운 프라이버시 속성을 가지고 있으며 신뢰 가정을 최소화하고 이더리움 메인넷에서 사용하기에 충분히 효율적입니다.이 게시물에서는 투표 개인 정보 보호 상태를 조사하고 Cicada가 작동하는 방식에 대한 높은 수준의 설명을 제공합니다(정식 증명이 곧 제공될 예정임). 또한 개발자가 다음을 검토하도록 권장합니다.
GitHub 저장소
- Cicada는 다양한 투표 체계와 기능을 지원하기 위해 다양한 방식으로 조정 및 확장될 수 있으며 커뮤니티와 협력하여 이러한 가능성을 모색할 수 있기를 바랍니다.
개인 투표에 대한 간략한 조사모든 투표 시스템(온체인 또는 기타)에는 고려해야 할 다양한 수준의 프라이버시가 있습니다. 개별 투표용지, 누적 집계, 유권자 신원 공개는 모두 다양한 방식으로 유권자 동기에 영향을 미칩니다. 어떤 프라이버시 속성이 필요한지는 투표의 맥락에 따라 다릅니다. 암호학 및 사회 과학 문헌에 자주 등장하는 몇 가지:투표용지 프라이버시: 비밀 투표용지, "
호주 투표
”는 개별 유권자의 선호도를 보존하고 뇌물 수수 및 강압을 완화하기 위한 방법으로 실제 투표 시스템용으로 개발되었습니다(온체인 설정에서는 투표 프라이버시보다 더 강력한 속성이 필요할 수 있습니다. "). 투표 프라이버시는 또한 사회적 바람직성 편향을 완화할 수 있습니다. 누군가는 다른 사람들이 자신의 선택에 대해 어떻게 생각하는지에 따라 투표해야 한다는 압력이 적습니다.
유권자 익명성: 많은 실제 투표 시스템에서 귀하의 투표는 공개되지 않지만 귀하가 투표했다는 사실은 공개되는 경우가 많습니다. 이것은 유권자 사기를 방지하는 데 중요합니다. 유권자 기록을 게시하면 사람들이 다른 사람이 자신의 이름으로 투표했는지 확인할 수 있기 때문입니다. 그러나 온체인에서는 암호화 프리미티브를 사용하여 익명성을 유지하면서 유권자 사기를 방지할 수 있습니다.지적영수증 없음: 개별 유권자는 제3자에게 어떻게 투표했는지 증명하기 위해 투표용지의 "영수증"을 제공하며, 그렇지 않으면 티켓 판매로 이어질 수 있습니다. 밀접하게 관련되어 있지만 더 강력한 속성은 누군가가 유권자에게 특정 방식으로 투표하도록 강요하는 것을 방지하는 강제 저항입니다. 이러한 속성은 스마트 계약 시장을 통해 의결권을 유동화할 수 있는 분산 환경에서 특히 매력적입니다. 불행하게도 구현하기도 어렵습니다. 사실 Juels et al.
지적
, 신뢰할 수 있는 하드웨어가 없는 무허가 환경에서는 불가능합니다.
Cicada는 진행 중인 투표 수 개인 정보 보호에 중점을 두지만 (나중에 논의하는 것처럼) 유권자 익명성과 투표 개인 정보 보호를 달성하기 위해 영지식 그룹 구성원 증명과 결합할 수 있습니다.
Cicada 소개: 동형 타임록 문제에서 프라이버시를 계산하는 투표Rivest, Shamir, Wagner, 1996 진행 중인 투표 집계의 프라이버시를 달성하기 위해 Cicada는 (우리가 아는 한) 이전에 온체인에서 사용된 적이 없는 암호화 프리미티브를 활용합니다.
먼저 타임락 퍼즐(Malavolta Thyagarajan, 2019 )는 미리 정해진 시간이 경과한 후에야 드러날 수 있는 비밀을 캡슐화한 암호 퍼즐, 더 구체적으로는 일부 비병렬 계산을 반복적으로 수행하여 해독할 수 있는 퍼즐입니다. Timelocked 퍼즐은 통계 실행에서 개인 정보를 보호하기 위해 투표와 관련하여 유용합니다. 사용자는 자신의 투표를 timelocked 퍼즐로 제출하여 투표 프로세스 중에 비밀로 유지되지만 투표 후에 공개될 수 있습니다. 대부분의 다른 비공개 투표 구조와 달리 통계 기관(종이 또는 디지털 투표 용지를 집계하는 선거 요원과 같은), 임계값 암호화(여러 신뢰할 수 있는 당사자가 메시지를 해독하기 위해 협력해야 함) 또는 기타 신뢰할 수 있는 당사자에 의존하지 않고 통계적 프라이버시가 작동할 수 있습니다. 투표 후 결과가 공개되도록 누구나 타임록 퍼즐을 풀 수 있습니다.
둘째, 동형 타임록 퍼즐(
)는 비밀 키, 복호화 퍼즐 또는 백도어 사용에 대한 지식으로 암호화된 값에 대한 일부 계산이 가능하다는 추가 속성을 가지고 있습니다. 특히, 선형 동형 타임록 퍼즐을 사용하면 퍼즐을 함께 결합하여 원래 퍼즐의 비밀 값 합계를 캡슐화하는 새로운 퍼즐을 생성할 수 있습니다.
논문의 저자가 지적했듯이 선형 동형 타임록 퍼즐은 비공개 투표에 특히 적합한 프리미티브입니다. 투표는 퍼즐로 인코딩될 수 있으며 동형적으로 결합되어 인코딩된 최종 계산 퍼즐을 얻을 수 있습니다. 즉, 각 투표에 대해 고유한 퍼즐을 풀지 않고 최종 결과를 밝히는 데 단 한 번의 계산만 필요합니다.
새로운 구조: 효율성과 장단점
투표 제도가 온체인에서 실용적이 되려면 고려해야 할 몇 가지 문제가 있습니다. 첫째, 공격자는 잘못 인코딩된 투표를 함으로써 투표 조작을 시도할 수 있습니다. 예를 들어, 우리는 각 투표용지에 대한 타임록 퍼즐을 부울 값으로 인코딩하기를 원할 수 있습니다: 투표 중인 제안에 대해 "1", 반대에 대해 "0". 열렬한 제안 지지자는 효과적인 투표권을 확장하기 위해 "100"과 같은 코드를 시도할 수 있습니다.
유권자가 투표 자체와 함께 투표의 유효성에 대한 영지식 증명을 제출하도록 함으로써 이 공격을 방지할 수 있습니다. 그러나 영지식 증명은 계산 비용이 많이 듭니다. 유권자 참여 비용을 가능한 한 낮게 유지하려면 증명이 (1) 클라이언트 측에서 효율적으로 계산 가능하고 (2) 온체인에서 효율적으로 검증 가능해야 합니다.
증명을 가능한 한 효율적으로 만들기 위해 일반적인 증명 시스템이 아닌 특정 대수 관계를 위해 설계된 영지식 증명인 맞춤형 시그마 프로토콜을 사용합니다. 이로 인해 증명 시간이 매우 빨라집니다. Python에서 투표 유효성 증명을 생성하는 데 기성 노트북에서 14ms가 걸립니다.
시그마 프로토콜의 유효성 검사기는 개념적으로 단순하지만 상당히 많은 수의 모듈식 지수가 필요합니다. Malavolta 및 Thyagarajan의 선형 동형 체계는 Paillier 암호화를 사용하므로 이러한 지수는 일부 RSA 모듈로 N에 대해 모듈로 N^2를 수행합니다. 합리적인 크기의 N의 경우 지수화는 대부분의 EVM 체인에서 매우 비쌉니다(수백만 가스). 비용을 줄이기 위해 Cicada는 Exponential ElGamal을 사용합니다. Exponential ElGamal은 여전히 가산 동형을 제공하지만 더 작은 계수(N^2 대신 N)에서 작동합니다.
ElGamal 사용의 한 가지 단점은 카운트를 해독하는 마지막 단계에서 개별 로그를 무차별 대입해야 한다는 것입니다(이는 오프체인에서 수행되며 효과적으로 온체인에서 검증됨). 따라서 예상되는 최종 투표 수가 상당히 적은 경우에만 작동합니다(예: 2^32 미만 또는 약 430만 표). 원래 Paillier 기반 체계에서는 크기에 관계없이 카운트를 효율적으로 해독할 수 있습니다.
RSA 모듈러스 N을 선택하는 것 또한 장단점이 있습니다. 우리의 구현은 가스 효율성을 위해 1024비트 계수를 사용합니다. 이것은 지금까지 공개적으로 팩터링된 가장 큰 RSA 계수(829비트)보다 훨씬 높지만 RSA 암호화 또는 서명을 위해 일반적으로 권장되는 크기인 2048비트보다 낮습니다. 그러나 우리의 애플리케이션은 장기적인 보안을 요구하지 않습니다. 일단 선거가 끝나면 미래에 N이 고려될 위험이 없습니다. 타임록이 만료된 후 개표와 투표가 공개된다고 가정하면 상대적으로 작은 계수를 사용하는 것이 합리적입니다. (이 또한 분해 알고리즘이 개선되면 향후에 쉽게 업데이트할 수 있습니다.)
익명성 및 유권자 자격
위에서 언급한 바와 같이 Cicada는 투표 중 투표 수를 비공개로 유지하는 시간 잠금 퍼즐 속성인 실행 수 프라이버시를 제공합니다. 그러나 각 개별 투표용지는 동일한 공개 매개변수로 암호화된 타임록 퍼즐이기도 합니다. 이는 필요한 계산을 수행하여 카운트를 해독할 수 있는 것처럼 각 투표도 해독할 수 있음을 의미합니다. 즉, Cicada는 투표 중에만 투표용지 프라이버시를 보장합니다. 호기심 많은 관찰자가 특정 유권자의 투표용지를 해독하려는 경우 그렇게 할 수 있습니다. 개별 투표지를 해독하는 것은 최종 집계를 해독하는 것만큼 비용이 많이 들기 때문에 순진하게도 n명의 유권자가 있는 투표지를 완전히 해독하려면 O(n) 작업이 필요합니다. 그러나 이러한 모든 투표는 최종 집계를 해독하는 데 걸리는 벽시계 시간과 동일한 양의 벽시계 시간을 사용하여 병렬로 해독할 수 있습니다(기계가 충분하다고 가정).일부 투표에서는 이것이 바람직하지 않을 수 있습니다. 투표 집계 프라이버시를 일시적으로 운영하는 것에 만족하지만 투표 프라이버시를 무기한으로 원할 수도 있습니다. 이를 달성하기 위해 우리는 Cicada를 익명의 투표자 자격 프로토콜과 결합할 수 있으며 그룹 멤버십의 영지식 증명으로 인스턴스화됩니다. 그렇게 하면 투표용지가 기밀 해제되더라도 누군가 그런 식으로 투표했다는 사실만 드러날 뿐이며 우리는 이미 개표를 통해 이를 알고 있습니다.여기여기그리고여기그리고
여기
제안).
통계적 권위
Cicada를 설계할 때 첫 번째 우선 순위 중 하나는 통계 기관의 필요성을 피하는 것이었습니다. 많은 사설 투표 구조는 투표를 받고 집계하기 위해 반신뢰 통계 기관(또는 안전한 다자간 계산을 통해 조정된 위임된 위원회)을 필요로 합니다. 블록체인 맥락에서 이는 이러한 체계가 스마트 계약만으로는 실행될 수 없으며 일부 사람의 개입과 신뢰가 필요함을 의미합니다.
대부분의 구조에서 집계 당국은 무결성(투표 수를 조작할 수 없음)에 대해 신뢰할 수 없지만 활성에 대해 신뢰할 수 있습니다. 오프라인 상태인 경우 최종 결과를 계산할 수 없으므로 투표가 무기한 지연됩니다. 일부 구조에서는 프라이버시를 유지하도록 신뢰하기도 합니다. 즉, 각 개인이 투표하는 방법을 알고 있지만 이 정보를 공개하지 않고 투표 결과를 게시할 것으로 예상됩니다.
통계 기관은 많은 실제 시나리오에서 합리적인(그리고 필요한) 가정이지만 신뢰를 최소화하고 검열 저항을 보장하는 것이 목표인 블록체인 환경에서는 이상적이지 않습니다.
Cicada는 온체인 투표 프라이버시 분야의 여러 방향 중 하나를 탐색하고 다른 그룹에서 수행하는 많은 연구를 보완합니다. 위에서 언급했듯이 Cicada는 세마포어, ZK 저장 증명 및 속도 제한 무효화기와 같은 익명 그룹 구성원 기술과 밀접한 관련이 있습니다. Cicada는 유권자의 가스 부담을 줄이기 위해 Nouns Vortex 팀이 제안한 낙관적 증명 검사기를 통합할 수도 있습니다.
