# 피아트-샤미르 휴리스틱 (Fiat-Shamir Heuristic)

피아트-샤미르 휴리스틱(Fiat-Shamir Heuristic)은 대화형 증명에서 검증자가 보내는 무작위 도전값(challenge)을 지금까지 주고받은 내용의 해시로 대체해, 증명자가 혼자서 만들 수 있는 비대화형 증명으로 바꾸는 기법입니다. 1986년 아모스 피아트(Amos Fiat)와 아디 샤미르(Adi Shamir)가 제안했으며, 슈노르 서명과 대부분의 현대 영지식 증명(SNARK, STARK, 불릿프루프)이 이 변환을 사용합니다.

## 자세히 알아보기

전형적인 시그마 프로토콜은 세 단계입니다. ① 증명자가 커밋먼트(commitment) R을 보냅니다. ② 검증자가 무작위 도전값 e를 보냅니다. ③ 증명자가 응답 s를 보냅니다. 증명자가 e를 미리 알 수 없기 때문에 속일 수 없습니다. 피아트-샤미르 변환은 ②를 e = H(공개 정보 ‖ R)로 바꿉니다. 해시 출력은 예측할 수 없으므로 검증자가 무작위로 뽑은 것과 같은 효과를 내고, 이제 증명자는 (R, s)만 공개하면 누구나 검증할 수 있습니다. 여기에 메시지 m을 해시에 넣으면 e = H(R ‖ P ‖ m)인 슈노르 서명이 됩니다.

이름에 '휴리스틱'이 붙은 이유는 안전성이 해시 함수를 이상적인 무작위 함수로 보는 랜덤 오라클 모델에서만 증명되기 때문입니다. 실제 해시로 바꿨을 때 일반적으로 안전하다는 보장은 없으며, 이론적으로는 반례도 존재합니다. 그러나 표준 해시와 올바른 구현을 쓰면 실무에서 매우 안정적으로 쓰여 왔습니다.

가장 흔한 실수는 해시 입력에 필요한 정보를 빠뜨리는 '약한 피아트-샤미르'입니다. 증명하려는 명제(공개 입력)나 이전 메시지를 해시에 넣지 않으면 공격자가 도전값을 먼저 보고 맞춤 명제를 만들어 가짜 증명을 위조할 수 있습니다. 2022년 보안 기업 Trail of Bits는 이런 유형의 취약점(Frozen Heart)이 PlonK, 불릿프루프 등 여러 증명 시스템 구현에 있었다고 공개했습니다. 대책은 모든 공개 입력과 대화 내용을 도메인 구분과 함께 해시하는 '트랜스크립트'를 쓰는 것입니다.

## 블록체인·암호화폐에서는

Bitcoin의 BIP-340 슈노르 서명, Ed25519, zk 롤업의 증명, Monero의 불릿프루프와 링 서명이 모두 피아트-샤미르 변환으로 비대화형이 된 결과물입니다. 블록체인에서는 증명자와 검증자가 실시간으로 대화할 수 없으므로, 이 변환이 없으면 온체인에서 검증 가능한 영지식 증명 자체가 어렵습니다.

## 쉽게 말하면

시험관이 무작위로 내던 질문을, 답안 앞부분을 넣으면 질문이 튀어나오는 '봉인된 질문 기계'로 대신하는 것입니다. 기계의 결과는 미리 알 수 없으니 시험관 없이도 공정한 시험이 됩니다.

---
출처: https://achivx.kr/glossary/fiat-shamir-heuristic-%ED%94%BC%EC%95%84%ED%8A%B8-%EC%83%A4%EB%AF%B8%EB%A5%B4-%ED%9C%B4%EB%A6%AC%EC%8A%A4%ED%8B%B1/ · ACHIVX 용어 사전 · 수정일 2026-10-20