ZK 시크릿 산타 프로토콜

avatar
Ethereum Research
12-01
이 기사는 기계로 번역되었습니다
원문 표시

안녕하세요, 이더리움 연구자 여러분! 겨울이 다가오면서 이 흥미로운 프로토콜을 포럼에도 공유하기로 했습니다. 올해 초, 저희는 이더리움에 (진정한) 시크릿 산타를 구현하여 플레이어의 프라이버시와 게임의 정확성을 유지하는 방법에 대한 연구 논문을 작성했습니다. ZKSS 프로토콜에 대한 여러분의 생각이 궁금합니다!

arXiv 에 있는 해당 논문에 대한 링크는 다음과 같습니다.

추상적인

본 논문은 영지식증명(ZKP)을 활용하여 선물 발송자/수신자 관계를 구축하는 동시에 발송자의 기밀성을 유지하는 3단계 시크릿 산타 알고리즘을 제안합니다. 이 알고리즘은 순열적 분산을 유지하며, 중앙 기관 없이도 성공적으로 작동합니다. 설명된 접근 방식은 거래 중계자와의 통합을 통해 솔리디티(Solidity)에서 구현될 수 있습니다.

1. 서론

크리스마스가 되면 누구나 시크릿 산타 게임을 즐깁니다. 하지만 온라인에서 게임을 플레이하려면 극복해야 할 몇 가지 어려움이 있습니다.

첫째, 이더리움 블록체인의 개방성으로 인해 비공개적으로 연산을 수행할 수 없습니다. 시크릿 산타 참여자의 신원(주소)을 은폐하기 위해 ZKP(영지식증명)와 함께 거래 중계기가 사용됩니다.

두 번째로, 체인상에는 (진정한) 무작위성의 원천이 없으므로 선물을 보내는 사람/받는 사람 쌍의 선택은 Secret Santa 참가자에게 아웃소싱되고 ZKP를 통해 검증되므로 아무도 스스로 선택하지 않도록 보장합니다.

셋째, "이중 투표" 문제는 널리퍼(블라인더) 개념을 통해 해결됩니다. 프로토콜은 플레이어의 기밀성을 침해하지 않으면서 참여 여부를 검증할 수 있습니다.

2. 프로토콜 설명

ZK 시크릿 산타(ZKSS) 프로토콜은 게임 참가자 전원의 참여가 필요한 3단계의 비동료 상호 작용 프로세스입니다.

이 알고리즘의 핵심은 실행 정확성을 보장하고 사용자 기밀성을 유지하기 위해 여러 암호화 기본 요소를 사용한다는 것입니다. \mathbb{F}_p F p 를 소수 p p 에 대한 유한체라 하고,

\mathsf{해시}(m) \;\rightarrow\; h \;\in\; \mathbb{ F } _p 해시 ( m ) → 시간 ∈ F 피

임의의 메시지 m m을 입력으로 받아 필드 요소 h h 를 반환하는 암호화 해시 함수를 나타냅니다.

증명 관계는 다음과 같이 정의됩니다.

\mathcal{R} = \{(w, x) \in \mathcal{W} \times \mathcal{X} \;:\; \phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)\}, R = { ( w , x ) ∈ W × X : ϕ 1 ( w , x ) , ϕ 2 ( w , x ) , … , ϕ m ( w , x ) } ,

여기서 w w 는 증인 데이터, x x 는 공개 데이터, \{\phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)\} { ϕ 1 ( w , x ) , ϕ 2 ( w , x ) , … , ϕ m ( w , x ) } 는 동시에 증명해야 하는 관계 집합입니다.

함수 \mathsf{ecrecover} e cre c o v e r [ 1 ]은 ECDSA 서명 \mathsf{sig} s i g 와 서명 된 해시 h h 를 기반 으로 사용자 의 \mathsf{address} 주소를 복구하는 데 사용됩니다.

마지막으로, 루트 값으로 이어지는 노드 값들의 목록인 머클 증명 p_i \in \mathbb{F}_p^{(n)} p i ∈ F ( n ) p 를 고려합니다. 원소 x x 에 대한 머클 증명은 다음과 같이 검증할 수 있습니다.

\mathsf{merkleVerify}(x, p_i , root ) \ ; \ rightarrow \ ; \ mathsf { bool } .merkleVerifyy ( x , p_i , root ) → 볼 .​​​

2.1. 설정

사전 설정을 위해서는 모든 ZKSS 참여자가 스마트 계약에 자신의 주소를 공개적으로 등록해야 합니다. 설정은 한 번만 수행하면 되므로, 참여자 설정을 여러 게임에서 재사용할 수 있습니다.

설정은 공개 프로세스이므로 주요 참여자가 선택되어 모든 플레이어를 대신하여 안전하게 단일 거래에 등록할 수 있습니다.

알고리즘 1: 설정

입력:

  • 공공의:
    • 주소 - ZKSS 참여자 Ethereum 주소

설치 과정:

  1. 주요 참여자는 스마트 계약에서 등록 기능을 호출하여 모든 참여자의 주소를 제공합니다.
  2. 이 계약은 참여자의 Sparse Merkle Tree(SMT)에 주소 를 해당 index = hash ( address ) index = hash ( address ) 형태 로 저장 합니다 .

참여자 SMT[2]는 ZKSS 전체에서 참여자가 초기 참여자 집합에 속하는지 확인하는 데 사용됩니다.

2.2. 서명 약속

첫 번째 단계인 서명 커밋(signature commitment )은 ZKSS 참여자가 결정론적으로 도출된 ECDSA 서명을 사용하도록 제한하는 데 필요합니다. 이 단계의 근거는 ecdsa 비결정론 보안 섹션을 참조하십시오.

알고리즘 2: 서명 커밋

입력:

  • 공공의:
    • H H – 사용자의 ECDSA 서명 해시 ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | 이벤트 ID ) , 여기서 \ mathsf {address} 주소 는 사용자 의 Ethereum 주소 이고 , \mathsf{eventId} 이벤트 ID 는 ( \ mathsf { contract\ address}\ ||\ \ mathsf { nonce } 계약 ) 입니다 . 주소​​​​​​ | | n o n c e ), 그리고 || | | 는 연결 연산입니다.

약속 과정:

  1. 참가자는 메시지 M M = ( \mathsf{address}\ ||\ \mathsf{eventId} a d r e s s 에 서명합니다. | | e v e n t I d )를 실행하고 서명 해시를 계산합니다.
  2. 참여자는 해시를 매개변수로 하여 스마트 계약에서 커밋 함수를 호출합니다.
  3. 계약은 제공된 해시를 해당 \mathsf{index} 인덱스 = H H 의 서명 약정 SMT에 저장합니다.

또한, 서명 약정 단계에서 스마트 계약은 \mathsf{msg.sender} ms g . sender 가 초기 ZKSS 참여자 집합 에 속하는지 확인해야 합니다.

2.3. 선물 발송자 결정

두 번째 단계는 발신자 결정 이라고 하며, 모든 ZKSS 참여자가 익명으로 무작위성 r r을 선물 발신자 배열에 추가해야 합니다.

알고리즘 3: 선물 보내는 사람 결정

입력:

  • 사적인:

    • \mathsf{sig} s i g – 사용자의 ECDSA 서명 ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | 이벤트 ID )​​​​
    • \mathsf { address } 주소 – 사용자 주소
    • p_p p p – 사용자 주소 포함에 대한 Merkle 증명
    • p_c p c – 사용자 서명 커밋 포함을 위한 Merkle 증명

  • 공공의:

    • r r – 사용자의 고유한 무작위성
    • \mathsf{eventId} 이벤트 ID – ZKSS 게임 의 고유 ID
    • \mathsf{root_p} r o o t p – 참가자 SMT 루트
    • \mathsf{root_c} r o o t c – 서명 커밋 SMT 루트
    • \mathsf{null_s} n u l l s – 무작위성의 이중 등록을 방지하기 위한 사용자의 nullifier

증명:

관계에 대한 증명 \pi_e π e를 생성합니다.

\mathcal{R}_{e} = \{\mathsf{서명}, \mathsf{주소}, p_p, p_c, r, \mathsf{이벤트 ID}, \mathsf{루트_p}, \mathsf{루트_c}, \mathsf{null_s}: \\\mathsf{null_s} \leftarrow \mathsf{해시}(\mathsf{서명.s}), \\\mathsf{주소} \leftarrow \mathsf{이전 복구}(\mathsf{서명}, (\mathsf{주소}\ ||\ \mathsf{이벤트 ID})), \\\mathsf{merkleVerify}(\mathsf{주소}, p_p, \mathsf{루트_p}) \rightarrow \mathsf{참}, \\\mathsf{merkleVerify}(\mathsf{hash}(\mathsf{sig}), p_c , \ mathsf { root_c } ) \ rightarrow \ mathsf { true } , \\ r = r * r \ } R e = { sig , 주소 , p p , p c , r , 이벤트 ID , root p , root_c , null s : 널 ← 해시 ( 시그마 . 시 )​​​ ​​​​​​​주소 ← 복구 ( 서명 , ( 주소 ​​​​​​​​​​ ​​​​​ ​​​​​​​ | | 이벤트 ID ) ) ,​​​​​ merkle V e r i f y ( 주소 , p p , root p ) → 참 ,​​​​​ ​​​​​​​​​​​​merkle V e r i f y ( hash ( sig ) , pc , root c ) → tru e ,​​​​ ​​​​​​​​​​​​r = r ∗ r }

증명 \pi_e π e는 계약에 의해 검증됩니다. 만약 증명이 정확하고 \mathsf{null_s} n u l l s가 사용된 무효화 함수 목록에 포함되지 않으면, 사용자는 릴레이를 통해 무작위성을 배열에 포함합니다. 무작위성과 무효화 함수는 쌍으로 접근 가능해야 합니다.

관계 \mathcal{R}_{e} R e 의 마지막 연산 r = r * r r = r ∗ r은 프로토콜의 건전성을 보장하기 위해 r r 값을 "고정"하는 추가 제약 조건을 생성합니다.

r r 은 모든 참여자에 의해 고유하게 생성되어야 하며 공개적으로 공개되어야 합니다. 그러나 r r 과 참여자 간의 관계는 중계자가 거래 를 전송 하는 ZKP ( 영 지식 증명 ) 에 숨겨져 있습니다.

플레이어는 무작위성 r r 을 위해 2048비트 RSA 공개 키를 사용하는 것이 좋습니다. 즉, ZKSS 참여자는 고유하게 RSA 개인 키(기억해야 함)를 생성하고, \mathsf{exp} e exp p = 65537이 주어졌을 때 해당 공개 키를 공개합니다.

공개된 RSA 공개 키는 알고리즘의 세 번째 단계에서 선물 수신자의 배송 주소를 암호화하는 데 사용되므로 해당 선물 발송자만 해당 주소를 읽을 수 있습니다.

2.4. 선물 수령자 공개

세 번째 단계인 수신자 공개(receiver disclosure )는 ZKSS 알고리즘의 마지막 단계입니다. 이 단계를 마치면 시크릿 산타 배포가 완료되고 선물 발송자는 수신자에게 선물을 보내기 시작할 수 있습니다.

수신자 공개 단계는 중계자 없이도 수행될 수 있으며, 수신자 신원( msg.sender ms g . s e n d e r ) 이 관계 없이 공개됩니다.

알고리즘 4: 선물 수신자 공개

입력:

  • 사적인:

    • \mathsf{sig} s i g – 사용자의 ECDSA 서명 ( \mathsf{address}\ ||\ \mathsf{eventId } a d r e s s | | 이벤트 ID )​​​​

  • 공공의:

    • \mathsf { address } 주소 – 사용자 주소
    • \mathsf{eventId} 이벤트 ID – ZKSS 게임 의 고유 ID(계약 주소 || | | nonce)
    • \mathsf{null_s} n u l l s – 발신자의 nullifier

증명:

관계에 대한 증명 \pi_c π c를 생성합니다.

\mathcal{R}_{c} = \{\mathsf{sig}, \mathsf{주소}, \mathsf{이벤트 ID}, \mathsf{null_s}: \\\mathsf{null_r} \leftarrow \mathsf{해시}(\mathsf{sig.s}), \\\mathsf{주소} \leftarrow \mathsf{ecrecover}(\mathsf{sig}, (\mathsf{주소}\ ||\ \mathsf{이벤트 ID}) ) , \\\ mathsf { null_r } \ neq \ mathsf { null_s } \ } R c = { sig , 주소 , 이벤트 ID , null s : n u l l r ← 해시 ( s i g . s ) ,​​​주소 ← 복구 ( 서명 , ( 주소 ​​​​​​​​​​ ​​​​​ ​​​​​​​ | | 이벤트 ID ) ) ,​​​​​ n u l l r ≠ n u l l s }

증명 \pi_c π c 는 계약에 의해 검증됩니다. 검증이 성공하고 \mathsf{null_r} n u l l r 이 선택된 \mathsf{null_s} n u l l s 와 같지 않으면, 수신자의 \mathsf{address} 주소 가 해당 발신자 의 난수 ( RSA 공개 키)에 할당됩니다.

무효화자의 불평등은 이전 단계에서 수신자의 위치가 공개되지 않도록 비공개적으로 검증되어야 합니다.

수신자 공개의 고유성을 강제하기 위해 스마트 계약 은 ( 공개적 으로 ) 고유 한 msg.senders 메시지 발신자 목록 을 유지 관리하고 이들이 초기 ZKSS 참여자 세트에 속하는지 확인해야 합니다.

여러 수신자가 동시에 같은 발신자를 선택하는 충돌이 발생하는 경우, 거래 중 하나는 되돌려져야 하고, 버려진 수신자는 다시 자신을 공개하려고 시도해야 합니다.

ZKP와 함께, 선물 수신자는 선물을 받을 암호화된 (실제) 주소를 제공할 수 있습니다. 암호화는 이전에 제공된 발신자의 RSA 공개 키를 사용하여 수행됩니다.

ZKSS 프로토콜을 구현하면 ZKP 검증 체계에 RSA 암호화 정확성 검사가 추가될 수 있습니다.

3. 보안

3.1. ECDSA 비결정론

서명 커밋 단계가 없으면 ZKSS 프로토콜을 공격하여 게임에 서비스 거부(DoS) 공격을 가할 수 있습니다. 부정직한 참여자는 비결정적 ECDSA 서명을 생성하고 무효화 방지 기능을 우회하여 모든 발신자의 슬롯을 점유할 수 있습니다.

따라서 EdDSA 서명을 사용하는 ZKSS 프로토콜의 대안 버전이 제안될 수 있습니다. 이러한 결정론적 특성 덕분에 서명 커밋 단계를 건너뛰고, 서명 커밋 SMT를 제거하고, 무효화 함수를 \mathsf{hash}(\mathsf{sig}) h a s h ( s i g ) 로 직접 생성할 수 있으며, \mathsf{hash}(\mathsf{sig.s}) h a s h ( s i g . s ) 로 생성할 수 있습니다 .

3.2. 수신기 프론트러닝

프로토콜의 수신기 공개 단계에서 사소한 프런트러닝 공격이 발생할 가능성이 있습니다.

부정직한 선물 발송자는 수신자보다 앞서 거래 메모리 풀을 모니터링하여(같은 발송자를 선택함으로써) 수신자가 다음 공개 시도에서 부정직한 발송자를 선택할 가능성을 높일 수 있습니다.

하지만 이 공격은 한 번만 작동합니다(수신자는 발신자를 한 번만 선택할 수 있음). 그리고 부정직한 발신자가 이미 선택된 경우에는 불가능합니다.

4. 정확성

ZKSS의 핵심 요소는 두 번째 단계와 세 번째 단계를 분리하는 것입니다. 두 번째 단계에서는 거래 중계자가 사용되므로 세 번째 단계의 참여자는 어떤 무작위성이 어떤 참여자에게 속하는지 판단할 수 없습니다. 또한, 참여자는 무작위성을 한 번만 적용할 수 있으며, 이는 nullifers 논리에 의해 강제됩니다. 또한, ZKP를 사용함으로써 어떤 참여자도 프로토콜을 조작하여 자신에게 선물을 보내거나 특정 발신자를 선택할 수 없도록 보장합니다.

이러한 개념을 설명하기 위해 다음의 시크릿 산타 비유를 생각해 보겠습니다. n 명의 참가자가 함께 모이는 모습을 상상해 보세요(알고리즘 1 참조).

각 참가자는 자신의 무작위성이 담긴 종이를 모자 안에 안전하게 넣습니다. 모든 참가자는 각자의 메모를 비밀리에 추가하며, 프로토콜의 릴레이어에 해당하는 "전송" 메커니즘(알고리즘 3 참조)을 제외하고는 어느 쪽지가 누구의 것인지 아무도 알 수 없습니다. 릴레이어의 익명성을 보장하기 위해 다양한 기술, VPN 등이 사용될 수 있지만, 이 논문의 범위를 넘어섭니다.

마지막으로, 각 참가자는 모자에서 정확히 한 장의 지폐를 뽑습니다. 그리고 (ZKP가 보장하는) "마법"에 의해, 참가자는 자신의 지폐를 다시 꺼낼 수 없습니다(알고리즘 4 참조). 난수가 적힌 지폐가 공개되면, 특정 숫자와 연관된 해당 참가자는 지폐를 꺼낸 사람에게 선물을 보냅니다.

게다가 선택한 무작위성이 RSA 공개 키인 경우, 수신자는 RSA 암호화를 통해 산타에게 배송 주소를 안전하게 전송할 수 있습니다.

요약하자면, 프로토콜의 정확성에 대한 주요 가정은 다음과 같습니다.

  • 각 선물 발송자는 자신과 프로토콜의 두 번째 단계에서 사용된 무작위성을 공개하지 않습니다.
  • ECDSA 서명은 RFC 6979 [3]에 따라 구성되어야 합니다. 곡선의 아래쪽 절반에서만 서명이 허용됩니다.
  • \mathsf{eventId} 이벤트 ID 는 모든 ZKSS 게임 마다 고유합니다.
  • 프로토콜의 건전성은 기본 ZK 증명 시스템의 건전성에서 파생됩니다.
  • 참가자가 암호화된 페이로드를 제공하는 경우, 암호화된 데이터의 정확성을 보장할 책임이 있습니다.

참고문헌

  1. [Woo24] Gavin Wood. 이더리움: 안전한 분산형 일반화 거래 원장. https://
  2. ethereum.github.io/yellowpaper/paper.pdf . 버전 f3553dd. 접속일: 2025년 1월 8일. 2024년.
    [ide24] iden3. 희소 머클 트리. https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf .
    접속일: 2025-01-08. 2024.
  3. [Por13] Thomas Pornin. 디지털 서명 알고리즘(DSA)과 타원형의 결정론적 사용
    곡선 디지털 서명 알고리즘(ECDSA). RFC 6979. 2013년 8월. doi: 10.17487/RFC6979.
    url: RFC 6979에 대한 정보 » RFC 편집기 .

섹터:
프라이버시
레이어2
영지식증명
출처
면책조항: 상기 내용은 작자의 개인적인 의견입니다. 따라서 이는 Followin의 입장과 무관하며 Followin과 관련된 어떠한 투자 제안도 구성하지 않습니다.
라이크
즐겨찾기에 추가
코멘트
관련 콘텐츠