Isabelle/STARK: A Formalization of zk-STARK in Isabelle/HOL
이 논문은 실행 가능한 증명자 및 검증자 모델, 최약전제(weakest-precondition) 미분법을 갖춘 확률적 상태 모나드, 그리고 명시적인 확률 경계와 함께 제로 실패(zero-failure) 정직한 완전성 및 건전성에 대한 형식적으로 검증된 정리들을 특징으로 하는, STARK 스타일의 투명한 증명 프로토콜에 대한 Isabelle/HOL 형식화를 제시한다.
원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기
당신이 거대한 금고의 비밀번호를 알고 있다는 것을 증명하려고 한다고 상상해 보세요. 하지만 비밀번호를 직접 말하지도 않고, 상대방이 당신이 입력하는 것을 기다리느라 몇 시간씩 허비하게 만들지도 않으면서 말이죠. 이것이 바로 암호학(cryptography)의 세계입니다. 이 특정 분야에서 우리는 STARK라고 불리는 일종의 디지털 증명을 살펴보고 있습니다. STARK를 하나의 "마법 영수증"이라고 생각해 보세요. 만약 당신이 복잡한 컴퓨터 프로그램을 실행한다면, STARK는 "나는 이 프로그램을 올바르게 실행했으며, 여기 그 결과가 있다"라고 말해주는 작고 위조 불가능한 쪽지와 같습니다. 이 과정에서 프로그램이 어떻게 작동했는지에 대한 지저분한 세부 사항은 밝히지 않습니다.
이 영수증들이 어떻게 작동하는지 이해하려면 세 가지 간단한 것을 알아야 합니다. 첫째, 컴퓨터는 종종 문제를 다항식(대수학에서 기억할 법한 구불구불한 선들)을 이용한 수학 퍼즐로 변환합니다. 둘째, 수학이 맞는지 확인하기 위해 모든 숫자를 하나하나 검사하는 대신, 국 전체가 짠지 확인하기 위해 국 한 숟가락을 맛보는 것처럼 몇 개의 무작위 샘플을 추출합니다. 셋째, 누군가 당신이 맛을 본 후에 국의 상태를 바꾸지 못하게 하기 위해, 우리는 거대한 데이터 더미에 대한 디지털 지문과 같은 **머클 트리(Merkle tree)**를 사용합니다. 데이터 더미 속의 쌀알 하나라도 바뀌면 지문이 완전히 바뀌어 버립니다.
이 분야의 핵심 질문은 이것입니다: "우리가 이 마법 영수증이 조작 불가능하다는 것을 절대적으로 확신할 수 있는가?" 오랫동안 사람들은 STARK에 대한 규칙을 써 내려왔지만, 규칙을 쓰는 것과 그것이 실제로 작동함을 증명하는 것은 다릅니다. 바로 여기서 **형식 검증(formal verification)**이 등장합니다. 이는 수학적 증명을 매우 엄격한 '로봇 변호사'에게 입력하여, 논리적 단계에 구멍이 있는지, "아마도"라는 모호함이 있는지, 혹은 숨겨진 속임수가 있는지 하나하나 체크하게 하는 것과 같습니다. 이것이 바로 **"Isabelle/STARK: A Formalization of zk-STARK in Isabelle/HOL"**라는 논문이 하는 일입니다.
저자인 디에고 마름솔러(Diego Marmsoler)는 복잡한 STARK 프로토콜을 컴퓨터가 이해하고 100% 확실하게 검증할 수 있는 언어로 번역했습니다. 그는 단순히 어떻게 작동해야 하는지에 대한 이야기를 쓴 것이 아니라, Isabelle/HOL이라는 도구 안에서 실제로 작동하는 모델을 구축했습니다. 이 도구는 답변이 정당화될 때까지 모든 단계를 요구하는 매우 엄격한 수학 선생님 역할을 합니다.
그가 발견한 내용은 다음과 같습니다. 첫째, 그는 시스템의 실행 가능한 버전을 구축했습니다. 그는 컴퓨터에서 실제로 실행할 수 있는 디지털 "증명자(Prover, 영수증을 만드는 쪽)"와 "검증자(Verifier, 영수증을 확인하는 쪽)"를 만들었습니다. 그는 증명자가 정직하게 규칙을 따른다면, 검증자가 항상 그 증명을 수락한다는 것을 증명했습니다. 정직한 증명자가 실패할 확률은 제로입니다. 이는 레시피를 완벽하게 따르면 케이크가 반드시 부풀어 오른다는 것을 증 proving하는 것과 같습니다.
둘째, 가장 중요한 점은 이것입니다. 만약 누군가 부정직하게 행동하려 한다면 어떻게 될까요? 그들은 가짜 영수증을 검증자에게 통과시키려는 교활한 "공격자(Adversary)"의 시나리오를 만들었습니다. 이 논문은 공격자가 속임수를 쓸 확률이 0은 아니지만, 수학적으로 극도로 미미하다는 것을 증명합니다. 그들은 단순히 "희박하다"라고 말한 것이 아니라, 공격자가 성공할 확률이 정확히 얼마나 작은지를 계산하는 구체적인 공식을 작성했습니다. 이 공식은 올바른 무작위 숫자를 맞추거나, 디지털 지문의 결함을 찾아내거나, 수학 방정식을 조작하는 등 공격자가 부정직하게 행동할 수 있는 모든 다양한 경로를 합산하여, 성공 확률이 매우 작은 수치 내에 묶여 있음을 보여줍니다.
또한 이 논문은 몇 가지 "쉬운" 증명 방식들을 명시적으로 배제합니다. 당신은 이렇게 생각할 수도 있습니다. "데이터 전체를 그냥 훑어보면 가짜인지 알 수 있지 않을까?" 저자는 아니오라고 답합니다. 현실 세계에서 검증자는 오직 몇 군데의 무작위 지점만을 봅니다(이것이 "맛 테스트"입니다). 이 논문은 검증자가 전체 그림을 본다고 가정해서는 안 된다는 것을 증명합니다. 대신, 검증자가 아주 작은 부분만을 보더라도 증명이 작동해야 함을 입증합니다. 또한 단순히 수학이 작동한다고 가정하는 방식을 거부하고, 증명을 아주 작고 관리 가능한 층위로 나누어 "지문" 로직과 "무작위 샘플링" 로직을 각각 별도로 체크한 뒤, 이들이 어떻게 결합되는지를 보여주었습니다.
이 작업의 가장 멋진 부분 중 하나는, 그들이 단순히 이론적인 무한의 세계를 위해 증명한 것이 아니라는 점입니다. 그들은 매우 작은 수학 세계(숫자가 5개뿐인, 마치 5까지 가는 시계와 같은 필드)를 사용하여 아주 작은 작동 예시를 구축했습니다. 그들은 이 작은 시계 위에서 정직한 증명자와 검증자를 실행했고, 그것들이 성공하는 것을 지켜보았습니다. 이는 그들의 코드가 단순한 이론이 아니라 실제로 실행된다는 것을 보여줍니다.
그렇다면 결론은 무엇일까요? 이 논문은 새로운 유형의 STARK를 발명했거나 시스템을 더 빠르게 만들었다고 주장하는 것이 아닙니다. 대신, 그것은 수학의 문을 잠갔다고 주장합니다. 그것은 STARK 프로토콜이 건전하다는 기계 검증된 보증을 제공합니다. 규칙을 따르면 영수증을 얻게 됩니다. 규칙을 깨려고 시도한다면, 수학은 당신이 성공할 가능성이 거의 없다고 말하며, 컴퓨터는 그 논리의 모든 단계를 확인했습니다. 이는 복잡한 암호학적 약속을 검증된 사실로 바꾸어 놓으며, 단순히 사람이 "내 생각엔 맞는 것 같아"라고 말하는 것이 아니라, 로봇 변호사가 숙제를 검사하는 것과 같은 수준의 신뢰를 부여합니다.
연구 분야의 논문에 파묻히고 계신가요?
연구 키워드에 맞는 최신 논문의 일일 다이제스트를 받아보세요 — 기술 요약 포함, 당신의 언어로.