30년 전 합체크 이론, 영지식증명 핵심으로 돌아왔다

30여 년 전 현실 응용과 거리가 멀다고 여겨졌던 합체크 프로토콜이 현대 영지식증명 기술의 핵심 도구로 다시 조명되고 있다. 블록체인에서 계산 결과를 짧은 증명으로 검증해야 하는 수요가 커지면서 대화형 증명 이론의 쓰임이 넓어졌다는 평가다.

안드리센호로위츠 크립토는 8월 12일 공개한 퍼스트 프린시플스(First Principles)에서 노엄 니산(Noam Nisan) 히브리대 교수, 팀 러프가든(Tim Roughgarden) 안드리센호로위츠 크립토 리서치 총괄, 저스틴 탈러(Justin Thaler) 안드리센호로위츠 리서치 파트너의 대담을 공개했다. 니산 교수는 괴델상 수상자로, 1990년대 초 대화형 증명과 계산복잡도 연구에 참여했다.

대담의 중심은 합체크 프로토콜이었다. 이 기법은 검증자가 거대한 계산 전체를 직접 다시 계산하지 않고도 증명자가 제시한 계산 결과가 맞는지 확률적으로 확인하도록 돕는다. 블록체인에서는 거래, 상태 전이, 프로그램 실행 결과를 짧은 증명으로 압축해 검증하는 영지식증명 설계와 맞닿아 있다.

합체크 프로토콜은 다항식과 무작위성을 활용해 대화형 증명의 범위를 넓힌 연구 흐름에서 나왔다. 이후 IP=PSPACE 논의와 검증 가능한 계산 연구의 배경이 됐고, 현대 블록체인 인프라에서는 빠른 증명 생성과 효율적인 검증을 위한 기술 요소로 다뤄진다.

안드리센호로위츠가 주목한 대목은 쓸모없어 보이던 이론이 실제 인프라로 이동한 경로다. 니산 교수는 당시 이런 아이디어가 실용 기술이 될 것으로 예상하지 못했다. 그러나 블록체인은 제3자의 계산을 다시 믿는 대신 검증해야 하는 환경을 만들었고, 짧고 빠른 증명의 필요성이 커졌다.

스나크(SNARK)는 ‘간결한 비대화형 지식 논증’을 뜻한다. 증명자는 계산을 수행했다는 증거를 만들고, 검증자는 원 계산을 반복하지 않고 이를 확인한다. 영지식 속성이 결합되면 입력값을 드러내지 않고도 계산의 정당성을 보일 수 있다.

다만 모든 스나크가 같은 방식으로 설계되는 것은 아니다. 합체크는 빠른 증명자 구현을 위한 한 축으로 다뤄진다. 탈러 파트너는 합체크가 실용적인 스나크를 만들기 위한 도구로 거의 최적에 가까울 수 있다고 봤다.

이번 대담은 니산 교수의 연구 궤적도 함께 다뤘다. 그는 복잡도 이론에서 인터넷 인센티브 문제로 관심을 옮겼고, 이는 알고리즘 게임이론 분야로 이어졌다. 안드리센호로위츠는 이 흐름이 이후 블록체인 수수료, 토큰 경제, 프로토콜 설계 논의와도 연결된다고 설명했다.

국내 독자에게도 이 주제는 단순한 학술사가 아니다. 국내 거래소, 지갑, 디앱 이용자가 체감하는 속도와 비용, 프라이버시 기능 뒤에는 검증 계산의 성능 문제가 놓여 있다. 합체크 프로토콜은 그 문제를 풀기 위한 여러 도구 중 하나로 다시 평가받고 있다.