다음에 올 것을 만들어가는 기술에 대한 심층 기사.

Lean으로 리만 가설 검증하기: 엔지니어를 위한 교훈

1,700만 줄짜리 Lean 증명이 여러 독립 검사기를 통과했습니다. 증명 보조기가 현업 엔지니어에게 주는 교훈을 정리했습니다.

교회처럼 맞물린 빛나는 기하학 블록들로 지은 대성당, 거대한 기계 검증 증명을 연상시킨다.
증명이 너무 커서 다 읽을 수 없더라도, 이음새만 점검하면 구조는 살펴볼 수 있습니다.

최근 나온 가장 대담한 소프트웨어 엔지니어링 성과는 프레임워크, 데이터베이스, AI 에이전트가 아닙니다. 바로 증명입니다. Levent Alpöge가 리만 가설에 대한 Lean 검증을 약 1,700만 줄 규모의 라이브러리로 공개했고, 하루도 지나지 않아 분산된 자원봉사자들이 이를 컴파일하고, 최종 정리를 Mathlib의 표준 명제와 대조하고, 내보낸 증명을 여러 독립 커널로 다시 검사했습니다. 그중 두 개는 거짓 증명을 받아들이지 않는다는 점을 기계적으로 검증한 논증을 갖고 있습니다.

제 주장은 다소 튀는 얘기입니다. 먼저 주장을 펼친 뒤 일부는 물러서겠습니다. 이번 일은 이 10년간 프로그래밍 언어 분야에서 가장 중요한 사건이고, 정수론과는 거의 상관이 없습니다. 리만 가설은 사실 부차적입니다. 핵심은 연구 수준의 규모에서 실제로 작동하는 사례가 생겼다는 점입니다. 소프트웨어 엔지니어들이 계속 주변만 맴돌며 제대로 다루지 못한 질문, 즉 사람이 도저히 검토할 수 없을 만큼 거대하면서도 낯선 사람들이 자기 평판을 걸고 믿을 만큼 엄밀하게 검증된 산출물은 어떻게 만드는가에 대한 답이 나온 것입니다.

1,700만 줄짜리 Lean 검증이 실제로 의미하는 것

Lean은 Nicolaas de Bruijn이 1960년대 후반 Automath와 함께 정리한 아이디어를 바탕으로 합니다. Automath는 수학을 기계가 검사할 수 있는 형태로 표현하려던 초기 시스템 중 하나입니다. 이 아이디어는 지금 '드 브라윈 기준'으로 불립니다. 증명 보조기는 증명 객체를 만들어야 하고, 이 객체는 작고 독립적인 검사 프로그램이 단독으로 검증할 수 있어야 한다는 것입니다. 시스템에서 똑똑하고 복잡한 부분, 즉 엘라보레이터, 전술(tactic) 엔진, 사람이 쓴 증명 스크립트를 형식적 객체로 바꾸는 자동화는 명시적으로 신뢰하지 않습니다. 이들은 컴파일러이며, 모든 컴파일러처럼 버그가 있을 수 있다고 봅니다. 신뢰는 커널에 있습니다. 커널은 완전히 전개된 증명 항이 논리의 규칙을 만족하는지 타입 검사하는 작은 프로그램입니다.

이 구조 덕분에 1,700만 줄짜리 산출물도 의미를 가집니다. 이 증명을 읽은 사람은 없습니다. 읽을 수도 없습니다. 주요 운영체제 컴포넌트 수준의 규모이고, 대부분 기계가 생성하고 기계에 맞춰진 코드입니다. 그래도 검증 워크플로는 이것을 잘 만든 빌드 시스템이 컴파일된 바이너리를 다루듯 취급합니다. 수십 명이 라이브러리를 각자 컴파일해서 똑같은 원본 증명 내보내기 파일을 바이트 단위로 동일하게 재현했습니다. 밀폐되고 결정적인 빌드가 내용 주소 지정이 가능한 산출물을 만들어낸 셈이고, 흥미로운 부분은 여기서 시작됩니다. 검사기가 소비하는 것은 소스가 아니라 바로 이 산출물이기 때문입니다.

읽을 수 없는 증명이라도 신뢰할 수 있는 증명일 수 있습니다. 일반적인 코드 리뷰를 뒤집는 이 역전이 이야기의 핵심입니다.

소프트웨어 개발자라면 이 역전을 잠시 곱씹어 볼 만합니다. 우리의 기본 품질 보증 수단은 사람이 diff를 열어 찡그리며 들여다보는 것입니다. 이 방식은 리뷰어 한 명이 일주일에 수천 줄 정도를 볼 때까지는 괜찮지만, 그 이상이 되면 찡그리는 행위가 형식적인 연극이 되어 버립니다. Lean 커뮤니티의 답은 신뢰를 스택 아래로 내리는 것입니다. 작은 커널을 신뢰하고, 그 커널을 독립적으로 재구현한 다양한 구현을 신뢰하며, 그 위에 있는 수백만 줄은 읽어야 할 산문이 아니라 검사해야 할 데이터로 취급합니다. 이건 수학 트릭이 아니라 엔지니어링의 입장입니다.

명제 문제: 올바른 정리를 증명하기

커뮤니티가 가장 먼저 확인한 것은 증명이 아니라 명제였습니다. 외부인들이 늘 과소평가하는 부분이고, 형식화 프로젝트가 조용히 실패하는 지점이기도 합니다. 증명 보조기는 여러분이 의도한 바가 무엇인지 신경 쓰지 않고, 잘못된 것을 완벽한 엄밀성으로 증명하도록 얼마든지 허용합니다. 고전적인 장난감 예시는 검증된 정렬 루틴인데, 명세에는 출력이 정렬되어 있다고 쓰고 입력의 순열이라는 조건은 빠뜨린 경우입니다. 빈 리스트는 완벽하게 정렬되어 있고, 증명도 통과합니다. 그런데 함수는 쓰레기입니다.

그래서 이 작업의 인증은 쉽게 지나칠 수 있는 사실에 기대고 있습니다. RiemannHypothesis 명제는 이미 Mathlib에 있었고, 해석적 수론과 Lean의 인코딩 관례를 모두 아는 사람들이 그 명제를 검토했습니다. 영점이 어디에 놓일 수 있는지, 자명한 영점이 어떻게 제외되는지, 함수가 애초에 어디서 정의되는지 같은 것들입니다. 이후 커뮤니티는 Mathlib만 임포트하는, 이 명제만 따로 분리한 파일을 추가했고, comparator와 con-leche --compare라는 두 개의 독립 도구로 Alpöge의 라이브러리가 증명하는 정리가 정확히 그 명제라는 것을 확인했습니다. 가까운 근사치도 아니고, 가설이 슬쩍 빠진 정의상의 유사품도 아닙니다. 제가 전에도 명세와 구현 사이의 간극에 버그가 숨어 있다고 주장한 적이 있는데, 형식 수학에서는 그 진실이 블로그 글에 그치지 않고 전용 도구가 붙은 체크리스트 항목이 됩니다.

업계 기준으로 보면 이 규율은 꽤 특이합니다. 여러분의 시스템이 하는 일이 계약서의 내용과 같은지 증명하는 것만이 목적인 전용 도구를 만든 팀을 마지막으로 본 적이 언제인가요? 우리는 계약을 샘플링하는 테스트를 작성하고, 계약을 어렴풋이 가리키는 타입 시그니처를 씁니다. Lean 커뮤니티는 그것을 식별하는 비교기를 만들었습니다. 이 일에서 한 가지만 가져간다면 이것을 가져가세요. 기계가 여러분의 증명을 검사했다고 기뻐하기 전에, 기계가 여러분의 주장을 검사하고 있는지부터 확인하세요.

돋보기 아래 거의 똑같이 생긴 두 개의 황동 열쇠, 하나는 열쇠 구멍에 맞고 다른 하나는 미묘하게 어긋나 있다.
거의 맞는 명제의 증명은 이빨 하나가 어긋난 열쇠와 같습니다. 인상적이지만 쓸모는 없습니다.

커널 신뢰와 검사기 생태계

Lean의 공식 커널은 작지만, '작다'는 것만으로 보안 논증이 되지는 않습니다. 오히려 재구현을 해보라는 초대장에 가깝습니다. 이 검증은 그 초대에 강하게 응했습니다. 내보낸 증명은 Lean 커널만이 아니라 con-leche, con-ron, 그리고 서로 다른 프로그래밍 언어로 작성된 여러 서드파티 검사기가 같은 비활성 내보내기 파일을 읽어 검사했습니다. 여기서 비활성이라는 단어가 중요합니다. 검사기는 증명 소스의 코드를 절대 실행하지 않으므로, 1,700만 줄 어딘가에 숨은 악성 코드 조각이 있더라도 그것이 작동할 런타임이 없습니다. 문서를 검토하는 것과 첨부 파일을 실행하는 것의 차이입니다.

특히 두 개의 주력 검사기는 따로 언급할 가치가 있습니다. con-leche와 con-ron은 각각 집합론에 상대적인 형식적 증명을 함께 제공하는데, 이 증명은 두 검사기가 거짓 증명을 받아들일 수 없다는 것을 보여 줍니다. 이는 흔한 무한 회귀를 끊어 줍니다. Lean 커널에도 이론상 건전성 버그가 있을 수 있으니 다른 커널로 확인하고, 그 커널에도 버그가 있을 수 있다고 말할 수 있겠지요. 하지만 검사기의 정당성 논증 자체가 다른 기반 위에서 기계적으로 검증되어 있다면, 공격 표면은 '여러 구현, 여러 언어, 여러 기반 시스템을 동시에 통과하는 버그'로 줄어듭니다. 불가능하지는 않지만, 계획에 넣고 대비할 종류의 일은 아닙니다. 제가 Rust의 borrow checker조차 건전성 구멍을 배포한 적이 있다고 쓴 적이 있어서, '커널을 믿으면 된다'는 말을 가볍게 하지 않습니다. 답은 신뢰할 수 있는 단일 컴포넌트에 있었던 적이 없습니다. 다양한 검사기 집단과 공유되고 이식 가능한 증명 형식이 답입니다. 수십 년간 항공전자 분야가 실천해 온 N버전 프로그래밍을 드디어 진리 자체에 적용한 셈입니다.

import Mathlib
-- The statement, maintained and vetted in Mathlib, that the
-- new library proves. Anybody can inspect what the words mean.
#check RiemannHypothesis
-- A trivial kernel-checked proof. The kernel reduces 2 + 2 to 4
-- and accepts rfl; no tactic code runs at check time.
theorem two_add_two : 2 + 2 = 4 := rfl
-- Ask the kernel what this proof's trust base actually is:
#print axioms two_add_two
-- reports that the proof depends on no axioms at all
-- Had someone snuck in `sorry` (Lean's escape hatch) or a custom
-- axiom, this is where it shows up: as `sorryAx` or worse, in
-- the dependency list of the final theorem.

마지막 메커니즘은 대부분의 시스템에 없는 감사 추적입니다. #print axioms는 사후에 커널에게 이 증명이 실제로 어떤 가정에 기대고 있는지 묻습니다. Lean의 모든 편법, 즉 sorry, 사용자가 선언한 공리, 잘못 사용된 unsafe는 이 목록에 흔적을 남깁니다. 여러분의 빌드도 '무엇을 가정했는가?'라는 질문에 같은 정밀도로 답할 수 있다고 상상해 보세요. 이 서비스는 시계가 단조 증가한다고 가정하고, 저 서비스는 TLS 1.3을 가정하고, 이 큐는 최소 한 번 전달을 보장한다고 가정하는 식입니다. 우리 시스템 대부분은 바로 이런 가정들을 안고 있지만, 요청을 받았을 때 그것을 나열할 수 있는 시스템은 거의 없습니다.

Mathlib 규모의 의존성 관리

커뮤니티 성명서의 한 문장은 순수한 의존성 관리의 시 같습니다. 코드베이스는 Mathlib에만 직접 의존한다. 벤더링된 포크도, 표준 라이브러리의 비공개 브랜치도, 트리 밖에 보류된 패치도 없습니다. 1,700만 줄짜리 연구 수학 코드가 하나의, 공유되고, 지속적으로 통합되는 상류 위에 놓여 있습니다. 이것이 가능한 이유는 Mathlib이 패키지 저장소라기보다 CI를 갖춘 표준 기구처럼 움직이기 때문입니다. 엄격한 리뷰, 기여자들이 매번 전체를 다시 빌드하지 않도록 하는 공유 캐시, 그리고 정의를 상류에 올리는 것이 커뮤니티에 베푸는 호의가 아니라 기본값인 문화가 있습니다.

그리고 명제를 먼저, 증명을 나중에 하는 순서는 엔지니어링 팀이 거꾸로 하는 부분입니다. 리만 가설의 정의는 증명이 도착하기 전에 공유 라이브러리에 병합되고, 검토되고, 단단해졌습니다. 1,700만 줄짜리 페이로드가 들어왔을 때 그것이 무엇을 주장하는지에 대한 논쟁은 없었습니다. 그 주장은 이미 인프라였기 때문입니다. 대부분의 대형 코드베이스가 거대한 기여를 흡수하는 방식과 비교해 보세요. 인터페이스는 기여 자체가 정하고, 리뷰는 시간에 쫓기며 진행되고, 계약이 어긋났다는 것을 누군가 알아차릴 즈음에는 다른 세 팀이 그 어긋난 버전에 의존하고 있습니다. Mathlib의 규율, 즉 어휘를 공개적으로 표준화한 뒤 그 위에 작업을 쌓게 하는 방식은 건강한 플랫폼 팀이 내부 API에 대해 하는 일과 정확히 같습니다. 차이라면 그들은 실제로 그렇게 한다는 점입니다.

거대한 자동화 창고에서 로봇 팔들이 밀랍으로 봉인된 똑같은 상자들을 컨베이어 벨트 위로 옮기고 있다.
하나의 공유 상류, 모든 소비자가 동일한 산출물을 다시 빌드합니다. 공공재로서의 의존성 관리입니다.

역발상 주장이 무너지는 지점

이제 물러서는 부분입니다. 이 주장은 솔직하게 스트레스 테스트를 받을 가치가 있습니다. 독립 검사기들은 수사적으로 보이는 것만큼 독립적이지 않습니다. 이들은 메타이론을 공유하고, 여러 검사기가 설계 계보를 공유하며, 검사기 작성자들은 서로 이야기를 나눕니다. 프로그래밍 언어가 다르다고 논리가 다른 것은 아닙니다. 미끄러진 전례도 있습니다. 콜라츠 추측에 대한 조작된 반박이 이런 독립 검사기 중 하나를 통과했고, 누군가 잡아내기 전까지 그랬습니다. 신뢰도 논증을 정직하게 말하면, 한 신중한 관찰자가 말한 것처럼 이 증명이 틀리려면 단일 버그가 검사기의 내부 일관성 증명과 이 특정 증명 양쪽에 동시에 영향을 주어야 하고, 그것도 모든 구현에서 그래야 합니다. 극히 드문 일입니다. 하지만 '극히 드문 일'은 확률이고, 커뮤니티 성명서는 '완전한 확신'이라고 말합니다. 그것은 확률이 아니라 사회학입니다.

발표된 네 가지 기준이 언급하지 않는 인간적인 하중 벽도 있습니다. 전해지는 바에 따르면 이 증명은 Alpöge가 방향을 잡는 가운데 AI의 도움을 많이 받아 만들어졌습니다. 문제를 분해하고, 막다른 길을 알아보고, 어떤 보조정리가 틀린 냄새가 나는지 알아채는 일이었습니다. 이 인간의 전문성은 실제 인식론적 작업을 하고 있는데, 작성된 인증서는 그것에 전혀 기대지 않는다는 점이 저를 불편하게 합니다. 제가 전에 LLM의 추측 생성과 기계적 증명 검사의 분리를 다룬 적이 있는데, 이번 사례는 그 분리가 최고 수준의 판돈에서 드러난 경우입니다. 기계가 전례 없는 규모로 제안하고, 기계가 전례 없는 규모로 검사했으며, 드물게 등장한 사람 한 명이 그 접점에 앉아 전체를 이해 가능하게 만들었습니다. 공식 이야기에서 그 사람을 지워 버리면 이야기는 더 깔끔해지지만, 덜 진실해집니다.

기계 검증 소프트웨어를 위한 엔지니어링 교훈

  • 신뢰 컴퓨팅 기반(TCB)은 작고 지루하게 유지하세요. 반드시 신뢰해야 하는 모든 줄은 부채이고, 단지 검사만 하는 모든 줄은 데이터입니다.
  • 살아 있는 프로세스에서 예상치 못한 일이 실행될 수 있는 대신, 비활성의 이식 가능한 형식으로 내보내세요. 검증은 문서 위에서 돌아가야 하며, 예기치 않은 일을 일으킬 수 있는 실시간 프로세스 위에서 돌아가면 안 됩니다.
  • 논증만이 아니라 주장을 검증하세요. 비교기를 만드세요. 증명을 축하하기 전에 산출물이 계약과 일치하는지 증명하세요.
  • 검사기를 진짜로 다양화하세요. 언어가 다르면 도움이 되고, 기반 시스템이 다르면 더 도움이 됩니다. 서로 숙제를 베낀 두 개보다 일관성 증명을 갖춘 검사기 하나가 낫습니다.
  • 빌드를 재현 가능하게 하고 산출물을 내용 주소 지정이 가능하게 만드세요. '수십 명이 같은 내보내기 파일을 재현했다'는 말은 모든 릴리스 파이프라인이 지향해야 할 문장입니다.
  • 큰 기여가 들어오기 전에 공유 어휘를 상류에서 표준화하세요. 정의가 먼저이고, 영웅적 행위는 그다음입니다.
  • 가정을 기계적으로 나열하세요. 시스템이 '무엇에 의존하는가?'에 답할 수 없다면, 여러분이 무엇을 배포했는지 모르는 것입니다.

이 목록 밑에 있는 생각은 하나입니다. 테스트는 공간을 샘플링하고, 증명은 공간을 소진합니다. 그리고 그 사이의 흥미로운 영역, 즉 속성 기반 테스트, 모델 검사, 심볼릭 실행은 업계가 첫 번째 진영에서 두 번째 진영을 향해 천천히, 마지못해 기어가는 영역입니다. 여러분의 CRUD 앱을 형식화하라고 요구하는 사람은 없습니다. 하지만 '반드시 기계 검증되어야 하는 것'의 경계는 계속 움직이고 있습니다. 암호 원시 함수, 합의 프로토콜, 스마트 컨트랙트, 비행 소프트웨어, 커널 eBPF 검증기가 그렇습니다. 이 각각의 커뮤니티는 대개 값비싼 사고 직후에 '우리가 이걸 Lean 방식으로 해야 한다'는 순간을 겪었습니다. 리만 검증은 도구, 문화, 검사기 생태계가 진짜로 거대한 무언가의 무게를 감당할 수 있다는 증명입니다. 핑계 찬장은 텅 비었습니다.

백 년간의 시도

언어를 다루는 사람으로서, 이것을 아주 오래된 내기의 결실로 보지 않을 수 없습니다. 힐베르트는 1900년에 리만 가설을 자신의 목록에 올렸습니다. de Bruijn은 1967년에 Automath를 시작했습니다. Robin Milner는 1970년대에 증명 전술을 작성하기 위한 메타언어로 ML을 만들었고, OCaml과 Haskell을 거쳐 Rust의 타입 시스템으로 이어지는 ML 계열 전체가 기계 검증 증명을 위한 도구에서 파생되었습니다. 1990년대의 QED 선언은 왜 수학 전체가 아직 형식화되지 않았는지 물었지만 대부분 어깨만 으쓱하는 답을 얻었습니다. 그 뒤 사색 정리가 Coq에서 증명되었고, 이어 Feit–Thompson 정리가, 그다음 Liquid Tensor Experiment가 현대 연구 수학이 고전뿐 아니라 커널과의 접촉도 버틸 수 있다는 것을 보여 주었습니다. 이 각각은 누군가에게 쇼로 불렸습니다. 그리고 각각은 커뮤니티를 훈련시키고, 다음 것이 올라설 라이브러리를 단단하게 만들었습니다.

그래서 제가 처음에 한 주장은 맞을까요? 부분적으로 맞습니다. 수학자들은 정리를 얻었고, 아침이 되자 이미 더 나은 질문을 하고 있었습니다. 증명이 무엇을 가르쳐 주는가? 이것은 1,700만 줄의 검사된 코드가 자동으로 해 주지 않는 일입니다. 엔지니어들은 더 드문 것을 얻었습니다. 최대 수준의 검토를 거쳐 검증된 청사진, 즉 어떤 사람도 읽기 어려울 만큼 큰 산출물을 구성하고 그것에 공동체의 이름을 걸 수 있게 하는 설계도입니다. 다음번에 설계 리뷰에서 누군가 실제 검증은 확장되지 않는다고 말하면, 어떤 빌드 로그를 보여 줘야 할지 정확히 알게 될 것입니다.