임포스터를 뽑은 적이 없었습니다 — 역할 배정을 검증 가능하게 만들다

AI 요약

오픈소스 Among Us 클론은 플레이어 ID를 비교해 가장 큰 ID를 가진 클라이언트가 임포스터 역할을 맡았습니다. 서버가 역할을 배정하거나 기록을 검증하지 않았고, 플레이어가 ID를 알면 임포스터를 미리 알아낼 수 있었습니다. 개발팀은 기존 게임을 새로 만들거나 화면·네트워크 메시지를 바꾸지 않고, 역할 배정과 게임 기록을 검증하는 Shadow Protocol을 덧붙였습니다.

역할 배정을 먼저 커밋합니다

게임 시작 때 브리지가 역할을 섞고, 각 역할을 좌석 번호와 게임 시드에 묶어 커밋먼트(commitment)를 만듭니다. 여기에 32바이트 난수 솔트를 더해 역할을 감춥니다. 역할 정보가 플레이어에게 전달되기 전에 커밋먼트를 원장에 올립니다. 좌석 번호를 포함해 다른 사람에게 역할 증명을 옮기지 못하게 하고, 게임 시드를 넣어 과거 경기의 공개 값을 재사용하지 못하게 합니다. 솔트는 가능한 역할을 대입해 커밋먼트를 추측하는 공격을 막습니다.

처치 검증 회로는 역할·좌석·솔트를 비공개 증인으로 받습니다. 증인이 해당 좌석의 커밋먼트를 다시 열고 역할이 SABOTEUR인지 확인한 뒤, 희생자가 유효한 좌석이며 살아 있고 자기 자신은 아닌지 검사합니다. 공개되는 값은 희생자 좌석뿐입니다. 검증자는 처치자가 실제 임포스터인지 확인하지만, 처치자의 좌석은 알지 못합니다. 다른 역할의 플레이어가 임포스터라고 주장하면 자신의 커밋먼트를 열지 못해 거부됩니다.

투표와 퇴장 기록도 검증합니다

투표에는 솔트, 회의 라운드, 'vote' 문자열을 해시한 널리파이어(nullifier)를 씁니다. 같은 사람이 같은 회의에서 다시 투표하면 같은 값이 나와 중복 투표로 거부됩니다. 회의 라운드가 바뀌면 값도 바뀌므로 다음 회의에서는 다시 투표할 수 있습니다. 솔트가 비공개인 동안에는 널리파이어만으로 투표자를 추적하지 못합니다.

퇴장 때는 플레이어가 공개한 역할과 솔트가 경기 시작 때 만든 커밋먼트를 여는지 확인합니다. 경기 종료 뒤에는 모든 좌석의 커밋먼트를 열어 제삼자가 기록을 다시 계산할 수 있습니다. 개발팀은 초기 역할 배정, 처치, 투표, 퇴장, 승자 결정, 경기 감사의 여섯 이벤트만 구현 범위로 정했습니다. 게임 화면과 네트워크 페이로드는 건드리지 않았고, 기존 코드에 표시한 패치는 15곳이며 새 Python 파일 하나가 이벤트를 TypeScript 브리지로 전달합니다.

게임 루프를 막지 않고, 역할 비밀은 숨기지 않습니다

증명 처리는 몇 초가 걸릴 수 있어 게임 프레임 안에서 기다리지 않도록 했습니다. 대부분의 체인 호출은 백그라운드 큐에서 비동기로 처리하며, 프레임을 멈추지 않도록 시간 제한과 재시도 대기 상한을 둡니다. 예외는 역할 배정입니다. 커밋먼트가 원장에 기록되기 전에는 임포스터를 두지 않고, 별도 스레드에서 배정을 진행합니다. 조용히 기존의 취약한 방식으로 돌아가는 대체 경로는 없습니다.

다만 서버는 여전히 역할과 솔트를 봅니다. 이 버전은 비밀을 서버로부터 감추지 않고, 서버가 역할 증명이나 경기 기록을 위조하지 못하게 하는 설계입니다. 데모도 Midnight 테스트넷에서 실행하지 않았습니다. 기본 mock 모드는 브리지 프로세스 안의 원장을 사용하며, Compact 계약과 같은 규칙을 검사하지만 실제 영지식 증명은 만들지 않습니다. 테스트넷 연결에는 지갑 생성과 계약 호출 구현이 남아 있습니다. 브리지가 솔트를 모두 보유하므로 투표를 대신 제출할 가능성도 있고, LAN 통신은 기존 게임의 pickle을 그대로 씁니다.

셔플 편향과 검증 결과

개발팀은 고정 시드와 5인 로비로 15단계 실행을 재현하고, 비임포스터의 처치, 역할 사칭, 중복 투표, 잘못된 퇴장 역할, 사칭 승리를 시험했습니다. 거부 메시지는 모두 mock 원장에서 나왔습니다. 100,000개 시드로 셔플을 반복한 결과 임포스터가 각 좌석에 배정된 비율은 19.85~20.16%였습니다. 256개 바이트 값을 5로 나눈 나머지를 그대로 쓰면 편향이 생기므로, 나눗셈이 고르게 떨어지지 않는 값 255를 버립니다. 이를 제거하면 특정 좌석의 배정 비율이 20.31%까지 올라갑니다.

프로젝트는 MLH 해커톤 게임 부문에서 우승했으며, 팀은 4명입니다. 글은 역할을 플레이어 지갑에 맡기고 브리지가 비밀을 보지 못하게 하는 웹 클라이언트와, 누구도 배정을 단독으로 알지 못하는 mental-poker 방식의 배정을 다음 단계로 제시합니다. 카드 덱이나 배틀로열 전리품 표처럼 비공개 배정이 있는 기존 게임에도, 경기 전에 커밋하고 나중에 검증하는 계층을 붙이는 구상을 설명합니다.

dev.to 반응

• @soumyadeepdey — @heyitsjem @jess @ben, 또 블로그로 돌아왔습니다. 이번 글도 마음에 들었으면 좋겠습니다!
  • @soumyadeepdey — 밈도 더 있어요.

원문: dev.to / 번역·요약: Trawling