Lightweight Verifiable Computation with Constant-Size Proofs for Sequential State Transitions

디지털 세상에서 많은 시스템은 현재의 상태가 이전에 일어난 일에 전적으로 의존하는 일련의 사건 체인에 기반하여 작동합니다. 공장을 모니터링하는 센서 네트워크, 거래를 기록하는 금융 장부, 또는 환자의 건강을 추적하는 데이터 스트림을 생각해 보십시오. 각 사례에서 기계는 이전 상태를 가져와 새로운 정보를 적용하고, 신선한 결과를 만들어냅니다. 문제는 작업을 수행하는 기계를 신뢰할 수 없을 때 발생합니다. 만약 서버가 시퀀스의 다음 단계를 계산한다면, 멀리 떨어진 관찰자가 그 계산이 올바르게 수행되었는지, 서버가 오래된 데이터를 재사용하지 않았는지, 혹은 단순히 그럴듯해 보이지만 실제로는 틀린 결과를 지어낸 것은 아닌지 어떻게 확신할 수 있을까요? 최종 숫자 하나만을 확인하는 것으로는 충분하지 않습니다. 그 숫자에 도달하기까지의 전체 이력을 검증해야 합니다. 전통적으로 긴 계산 체인을 검증하는 것은 처음부터 모든 단계를 다시 수행하는 것을 의미했으며, 이는 체인이 길어질수록 과정이 더 느려지고 비용이 많이 드는 문제가 되었습니다.

연구자 정희원과 이현범은 단계별로 진화하는 시스템을 위한 이 특정 문제를 해결하는 새로운 방법을 개발했습니다. 연구 논문에 발표된 이들의 연구는 매번 전체 역사를 다시 계산하게 하지 않고도 이러한 순차적 업데이트를 검증하는 방법을 소개합니다. 모든 새로운 단계를 완전히 새로운 퍼즐로 취급하는 대신, 이들의 시스템은 정당성의 증명을 점진적으로 업데이트할 수 있도록 허용합니다. 여행자가 국경을 넘는 장면을 상상해 보십시오. 매번 새로운 나라에 들어갈 때마다 여행의 시작부터 모든 여권 도장을 확인하는 대신, 국경 요원은 가장 최근의 도장만을 확인하고 그것이 이전 것에 적법하게 추가되었는지만 검증하면 됩니다. 연구진은 복잡한 컴퓨터 계산에 대해 이것이 가능하도록 하는 수학적 프레임워크를 설계하여, 얼마나 많은 단계가 지나갔더라도 증명이 작게 유지되고 검증은 빠르게 이루어지도록 했습니다.

그들 발견의 핵심은 이러한 순차적 작업에 특화되어 설계된 새로운 수학적 구조군입니다. 검증 가능한 컴퓨팅(verifiable computing)의 세계에는 단일 계산이 올바르게 수행되었음을 증명할 수 있는 기존 도구들이 있지만, 계산이 많은 작은 단계들의 긴 체인인 경우에는 어려움을 겪습니다. 한 가지 흔한 접근 방식은 새로운 단계가 추가될 때마다 컴퓨터가 전체 역사를 다시 증명하도록 요구하는데, 이는 큰 부담이 됩니다. 또 다른 접근 방식은 '폴딩(folding)'이라 불리는 기술을 사용하여 단계들을 결합하지만, 이는 종종 매우 큰 증명 파일을 생성하여 검증 속도를 늦춥니다. 정희원과 이현범은 그 중간 경로를 찾아냈습니다. 그들은 새로운 단계에 대한 증명이 이전 단계의 증명에 소량의 새로운 정보를 단순히 더함으로써 구축되도록 설계했습니다. 이는 작업을 수행하는 컴퓨터가 처음부터 다시 시작할 필요가 없으며, 작업을 확인하는 사람 또한 전체 역사를 다시 볼 필요가 없음을 의미합니다.

연구팀은 다중 센서 데이터 융합, 벡터에 대한 특정 수학적 연산 수행, 보안 시스템에 사용되는 암호화 체인 실행 등 다양한 현실적인 시나리오에서 이 방법을 테스트했습니다. 그들은 이 시스템이 자원이 제한된 환경에서 어떻게 작동하는지 확인하기 위해 에지 디바이스의 게이트웨이로 자주 사용되는 저렴하고 작은 컴퓨터인 라즈베리 파이 5(Raspberry Pi 5)에서 테스트를 진행했습니다. 결과는 놀라웠습니다. 그들의 방법은 증명 크기가 단 160바이트에 불과했는데, 이는 선도적인 대안 방법이 요구하는 11,500~12,500바이트와 비교했을 때 매우 작은 수치입니다. 또한 증명을 검증하는 데 걸린 시간도 매우 빨라 11.6밀리초에서 28.9밀리초 사이였습니다. 반면 대안 방법은 단 하나의 증명을 검증하는 데 거의 250밀리초가 걸렸습니다. 증명을 생성하는 측면에서도, 그들의 시스템은 긴 체인의 처음부터 다시 증명하는 전통적인 방식보다, 특히 단계의 수가 많아질수록 훨씬 더 빨랐습니다.

이 연구의 가장 중요한 측면 중 하나는 이 시스템이 무엇을 요구하지 않는가 하는 점입니다. 연구진은 긴 계산 체인을 처리하는 일반적인 방법이지만 계산 비용이 많이 들고 느린 것으로 알려진 '재귀적 증명 합성(recursive proof composition)' 기술을 사용하는 것을 명시적으로 피했습니다. 이러한 복잡성을 우회함으로써, 그들은 가볍고 효율적인 시스템을 달성했습니다. 다만, 이 시스템에는 특정 경계가 있습니다. 이 시스템은 시작하기 전에 결정되어야 하는 '바운드(bound)'라고 불리는 고정된 단계 수를 위해 설계되었습니다. 즉, 이 시스템은 무한히 계속되는 데이터 스트림보다는 특정 모니터링 기간이나 감사 기간과 같이 정의된 운영 기간에 가장 적합합니다. 또한 연구진은 이 시스템이 처리되는 데이터를 숨기지는 않으며, 오직 데이터가 규칙에 따라 올바르게 처리되었는지만을 증명한다는 점을 언급했습니다.

이 연구의 함의는 매우 큽니다. 더 많은 장치와 서비스가 신뢰할 수 없는 환경에서 작동함에 따라, 과도한 계산 비용 없이 데이터 무결성을 검증하는 능력은 매우 중요해졌습니다. 이 새로운 방법은 작은 저전력 장치가 자신의 작업에 대한 증명을 생성하고, 원격 검증자가 그 사이의 작업량에 관계없이 거의 즉각적으로 그 증명을 확인할 수 있는 시나리오를 가능하게 합니다. 연구진은 이 접근 방식이 단순한 이론적 개선이 아니라, 일상적인 하드웨어에서도 효율적으로 실행될 수 있는 실용적인 것임을 입증했습니다. 증명 크기를 일정하게 유지하고 검증 시간을 짧게 유지함으로써, 그들은 시간이 지남에 따라 진화하는 디지털 시스템을 더 견고하고 효율적으로 신뢰할 수 있는 길을 열었습니다.

실험에서 팀은 두 가지 주요 접근 방식과 그들의 방법을 비교했습니다. 하나는 매 단계마다 전체 역사를 다시 증명하는 표준 방식이었고, 다른 하나는 폴딩에 기반한 최신 방식이었습니다. 표준 방식과 비교했을 때, 그들의 접근 방식은 긴 시퀀스의 마지막 단계에서 증명을 생성하는 속도가 최대 2.7배 더 빨랐습니다. 폴딩 방식과 비교했을 때는 증명 크기가 약 72~78배 더 작았고, 검증 속도는 거의 20배 더 빨랐습니다. 이러한 수치들은 실시간 센서 모니터링이나 보안 장부와 같이 속도와 데이터 크기가 매우 중요한 응용 분야에서 이 새로운 방법이 뚜렷한 이점을 제공함을 시사합니다. 연구진은 매우 짧은 시퀀스나 무제한의 무한한 계산 체인이 필요한 응용 분야에서는 다른 방법이 여전히 선호될 수 있음을 인정했습니다. 하지만 특정되고 흔한 사례인 유한한 순차적 상태 전이(bounded, sequential state transitions)에 대해서는, 그들이 가볍고 검증 가능한 솔루션을 제공했다는 점을 분명히 했습니다.

또한 이 연구는 이러한 시스템에서 신뢰 앵커(trust anchors)의 중요성을 강조합니다. 검증이 유효하려면 검증자는 초기 상태에 대한 신뢰할 수 있는 기록으로부터 시작해야 합니다. 만약 이 시작점이 훼손된다면, 전체 신뢰 체인이 깨질 수 있습니다. 연구진은 이 한계점을 명확히 하며, 시스템이 초기 상태가 정당하다는 것을 가정하고 검증자가 마지막으로 수락된 상태에 대한 안전한 기록을 유지한다고 언급했습니다. 이는 신뢰할 수 있는 기관이나 보안 로그가 초기 앵커를 제공할 수 있는 많은 실제 배포 환경에서 합리적인 가정입니다. 이러한 요구 사항을 공식화하고 그 안에서 작동하는 시스템을 구축함으로써, 연구진은 사물인터넷(IoT)에서 금융 감사에 이르는 다양한 분야에 실질적으로 적용 가능한 도구를 만들어냈습니다.

궁극적으로 이 연구는 복잡하고 진화하는 디지털 프로세스를 검증하는 방식에 대한 사고의 전환을 나타냅니다. 이는 검증이 무겁고 반복적인 작업이어야 한다는 생각에서 벗어나, 검증을 가볍고 점진적인 단계로 만드는 모델로 나아가는 것입니다. 연구진은 성능이나 확장성을 희생하지 않고도 높은 수준의 보안과 무결성을 유지하는 것이 가능하다는 것을 보여주었습니다. 세상이 점점 더 신뢰할 수 없는 환경에서 작동하는 자동화된 시스템에 의존함에 따라, 이와 같은 방법은 디지털 세계의 상태가 정확하고 신뢰할 수 있는 상태로 유지되도록 보장하는 데 필수적일 것입니다. 이 연구 결과는 단순한 이론적 호기심이 아니라, 검증 가능한 컴퓨팅을 일상적인 기술의 실질적인 현실로 만들기 위한 구체적인 진전입니다.