zk-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge)

zk-STARK(Zero-Knowledge Scalable Transparent ARgument of Knowledge)는 신뢰 설정(trusted setup) 없이 해시 함수만으로 구성하는 영지식 증명 체계입니다. 2018년 엘리 벤사손(Eli Ben-Sasson) 등이 발표했으며, '확장 가능(Scalable)'하고 '투명(Transparent)'하다는 뜻이 이름에 담겨 있습니다.

자세히 알아보기

STARK는 증명하려는 계산을 실행 기록(trace) 표로 만들고, 그 표가 규칙을 지켰다는 조건을 다항식 제약(AIR, 대수적 중간 표현)으로 바꿉니다. 그런 다음 FRI(Fast Reed-Solomon IOP of Proximity)라는 저차 다항식 검사로 '제약을 만족하는 낮은 차수의 다항식이 존재한다'는 사실을 확률적으로 증명합니다. 커밋에는 머클 트리를, 비대화형 변환에는 피아트-샤미르 휴리스틱을 사용합니다.

특징은 다음과 같습니다. ① 투명성: 비밀 난수를 버려야 하는 신뢰 설정이 없어 '유독성 폐기물(toxic waste)' 위험이 없습니다. ② 확장성: 증명 생성 시간은 계산 크기에 거의 선형이고, 검증 시간은 다중 로그 수준으로 짧습니다. ③ 양자 내성 기대: 타원곡선·페어링이 아니라 충돌 저항 해시에만 의존하므로 양자 컴퓨터에 강할 것으로 여겨집니다. 단점은 증명 크기가 수십~수백 KB로 Groth16 같은 페어링 기반 SNARK(수백 바이트)보다 훨씬 크다는 점입니다.

엄밀히 STARK는 '영지식'이 선택 사항이며, 롤업처럼 계산이 올바르다는 것(계산 무결성)만 증명하면 되는 경우 영지식 없이 쓰이기도 합니다. 실무에서는 큰 STARK 증명을 다시 작은 SNARK 증명으로 감싸 온체인 검증 비용을 줄이는 재귀 구성이 흔합니다.

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

StarkWare의 StarkEx와 Ethereum 레이어 2 네트워크 Starknet이 대표적인 STARK 기반 시스템입니다. 수천 건의 트랜잭션을 오프체인에서 실행하고 STARK 증명 하나를 Ethereum에 제출해 상태 변경의 정당성을 증명합니다. RISC Zero 같은 범용 zkVM도 STARK 계열 증명을 사용합니다. 이렇게 하면 레이어 1의 보안을 유지하면서 수수료와 처리량을 개선할 수 있습니다.

쉽게 말하면

수천 쪽짜리 계산 노트를 다 보여 주지 않고, 무작위로 몇 군데만 찔러 봐도 노트 전체가 맞다는 것을 확신시켜 주는 방법입니다. 공증인(신뢰 설정) 없이 누구나 같은 규칙으로 검증할 수 있습니다.