비트코인 서명 묶음 검증, 128비트 계수로 줄여도 안전할까
비트코인 거래를 확인할 때 컴퓨터는 거래가 정당한 권한을 가진 사람의 승인을 받았는지 살핀다. 이때 쓰이는 전자서명이 많아지면 서명을 하나씩 검증하는 일도 그만큼 늘어난다. 여러 서명을 한데 묶어 확인하는 배치 검증은 그 계산의 일부를 함께 처리해 시간을 줄이려는 방법이다.
그런데 묶어서 확인하려면 각 서명에 곱할 계수가 필요하다. 2026년 11월 2일 비트코인 기술 토론 게시판 Delving Bitcoin에 올라온 글은 서명 규칙인 BIP340의 배치 검증 계수를 256비트에서 128비트로 줄이는 제안을 다뤘다. 게시글 작성자에 따르면 관련 암호 라이브러리인 libsecp256k1에서 배치 검증이 최대 약 9% 빨라진다.
속도만 보면 반가운 소식이다. 하지만 계수의 가능한 값이 줄면 잘못된 서명을 놓칠 가능성도 달라질 수 있다. 그렇다면 숫자를 절반으로 줄여도 괜찮다는 말은 무슨 뜻일까? 게시글의 답은 조건부다. 작성자는 계수를 실제처럼 배치 데이터에서 결정적으로 만드는 두 방식에 대해, 공격자의 시도 횟수를 포함한 오류 확률의 경계를 형식적으로 증명했다고 설명한다. 그 결론은 해시를 이상화한 수학 모델과 입력을 표현하는 방식이 맞아야 적용된다.
왜 서명을 섞을 때 계수가 필요할까
전자서명 검증은 서명과 메시지, 공개키가 일정한 수학적 관계를 만족하는지 확인하는 일이다. 개별 검증에서는 서명마다 그 관계가 맞는지 따로 확인한다. 배치 검증에서는 여러 검증 관계에 계수를 곱해 하나의 큰 관계로 합친 다음 함께 검사한다.
이때 단순히 모든 관계를 더하기만 하면 문제가 생길 수 있다. 한 서명에서 생긴 오류가 다른 서명의 오류와 반대 방향이라면 합친 결과에서는 서로 지워질 수 있기 때문이다. 개별적으로는 틀린 항목들이 묶음에서는 맞는 것처럼 보이는 셈이다.
계수는 이런 상쇄를 어렵게 만든다. 각 오류에 별도의 계수가 적용되므로, 공격자가 오류를 정해 놓았을 때 그것들이 정확히 상쇄되는 계수가 나올 가능성을 제한할 수 있다. 계수들이 반드시 서로 다른 값을 가져야 한다는 뜻은 아니다. 게시글에서 다루는 안전성, 즉 건전성은 바로 이 문제를 뜻한다. 잘못된 서명이 들어 있는 묶음이 검증을 통과할 가능성이 얼마나 제한되는가 하는 것이다.
계수의 비트 수는 가능한 값의 범위를 정한다. 128비트 계수라면 기본적으로 가능한 값이 2의 128제곱 가지다. 이 수가 크다고 해서 설명이 끝나는 것은 아니다. 공격자가 계수를 모른 채 묶음을 한 번만 내는지, 계수 생성 결과를 미리 확인하면서 여러 묶음을 시험할 수 있는지에 따라 판단해야 할 확률이 달라진다.
또한 게시글의 속도 수치는 특정 라이브러리의 배치 검증에 대한 설명이다. 최대 약 9%라는 수치를 비트코인 노드 전체의 처리 속도나 다른 라이브러리의 개선 폭으로 읽어서는 안 된다. 확보된 게시글 발췌에는 그 최대치를 얻은 장치나 세부 측정 조건도 제시되지 않는다. 이 글은 제안과 작성자의 증명 설명을 다루며, 제안이 채택됐다고 말하는 것은 아니다.
매번 제비를 뽑는 것이 아니라면
계수의 역할을 처음 배울 때는 각 계수를 서로 독립적으로, 가능한 값 중에서 균등하게 뽑는다고 생각하기 쉽다. 이런 이상적인 조건에서는 다른 계수들이 정해졌을 때, 잘못된 서명의 오류를 나머지 오류와 정확히 상쇄할 계수는 많아야 하나다. 따라서 계수가 b비트라면 해당 조건에서 잘못된 묶음이 통과할 확률은 2의 b제곱분의 1로 제한된다.
하지만 게시글이 주목한 실제 생성 방식은 검증할 때마다 별도로 제비를 뽑는 방식이 아니다. 배치의 데이터에 해시 함수를 적용해 계수를 결정적으로 만든다. 해시 함수는 입력 데이터를 일정한 형태의 값으로 바꾸는 함수다. 같은 입력을 넣으면 같은 결과가 나오므로, 공격자도 후보 배치를 만들고 어떤 계수가 나오는지 시험할 수 있다.
이 차이가 안전성 논의의 출발점이다. 계수를 무작위 값처럼 취급하는 설명만으로는 부족하다. 공격자가 계수 생성 방법을 알고 후보 입력을 골라볼 때도 오류 가능성이 충분히 낮은지 살펴봐야 한다.
게시글은 두 가지 생성 방식을 다룬다. 하나는 BIP340 문서에서처럼 배치 전체를 해시해 계수를 얻는 방식이다. 다른 하나는 앞에서부터 항목을 누적하며, 각 위치까지의 내용을 해시해 계수를 만드는 방식이다. 후자에서는 공격자가 앞쪽 항목에서 나온 계수를 보고 나중 항목을 고르는 상황까지 생각해야 한다. 작성자는 이런 선택을 허용하는 설정에서도 두 방식의 건전성을 Lean 4로 증명했다고 밝힌다.
확률에 붙은 q는 무엇을 뜻하나
작성자가 제시한 경계는 계수를 만드는 해시를 랜덤 오라클로 모델링한다. 이는 새로운 입력마다 독립적이고 균등한 무작위 출력을 돌려주되, 같은 입력에는 같은 출력을 돌려주는 이상적인 함수를 상정하는 방법이다. 현실의 해시 함수가 문자 그대로 이런 기계라는 뜻이 아니라, 그 모델 안에서 무엇을 보장할 수 있는지 따지는 것이다.
이 모델에서 b는 계수 해시의 출력 비트 수이고, q는 공격자가 오라클에 질의한 횟수다. 게시글에 따르면 배치 전체에서 계수를 만드는 방식과 앞의 항목을 누적하는 방식 모두, 잘못된 배치가 통과할 확률의 상한은 다음과 같다.
(q+1) / 2^b
계수가 128비트라면 분모는 2^128이다. 배치 전체를 해시하는 방식에 대해서는 게시글이 배치 크기에 관계없이 이 경계를 제시한다. 중요한 것은 분자다. 공격자가 많은 후보를 시험할수록 원하는 계수를 찾아낼 기회가 늘어나므로 q를 빼고 숫자 128만 보고 판단할 수 없다. 분자의 1은 게시글 설명에서 검증자 자신의 질의에 해당하는 몫이다.
이 식은 주어진 모델과 가정 아래에서 제시된 상한이다. 공격자가 어떤 현실 환경에서든 반드시 이 확률로 성공한다는 예측도, 성공 확률이 0이라는 보장도 아니다. 또 게시글은 서명 검증에 쓰이는 다른 해시인 챌린지 해시는 임의의 함수로 두었다고 설명한다. 따라서 이 결과를 ‘모든 해시 함수와 모든 서명 시스템이 안전하다’는 주장으로 바꿀 수는 없다.
반복해서 운이 좋은 묶음을 찾는 공격
왜 시도 횟수가 중요한지 보여주기 위해 게시글 작성자는 ‘그라인딩’ 예를 든다. 그라인딩은 후보를 조금씩 바꾸어 해시를 계속 계산하면서 원하는 결과가 나올 때까지 찾는 방법이다. 여기서는 유효한 서명 하나를 바탕으로, 한쪽에는 오류를 더하고 다른 쪽에는 대응하는 오류를 빼 두 개의 잘못된 서명을 만든다.
이 두 오류는 특정 계수에서 정확히 상쇄된다. 게시글의 구성에서는 두 번째 계수가 1이면 잘못된 두 서명이 담긴 배치가 통과한다. 공격자는 오류의 크기를 바꾸며 새 배치 후보를 만들고, 그때마다 계수를 계산해 자신에게 유리한 값이 나오는지 살핀다. 개별 서명을 정상으로 바꾸는 것이 아니라, 묶어 검사할 때 오류가 가려지는 입력을 찾는 것이다.
게시글은 이 예에서 두 생성 방식 모두에 대해 q번 시도했을 때 성공할 확률을 1-(1-2^-b)^q로 제시한다. 적절한 범위에서는 이를 대략 q/2^b로 볼 수 있다. 이는 앞의 상한과 비교했을 때, 반복 시도에 따른 위험 증가가 단지 증명을 느슨하게 해서 생긴 숫자가 아니라 실제로 구성한 공격 예에서도 나타난다는 뜻이다. 다만 이 예가 현실의 모든 공격을 대표한다는 뜻은 아니다.
128비트 계수에 관해 작성자가 든 예는 약 2^64번 해시를 시도하면 성공 확률이 약 2^-64라는 것이다. 2^64는 약 1,844경 번에 이르는 매우 큰 횟수다. 여기서 특히 조심할 점은, 그만큼 시도하면 성공한다는 말이 아니라 그만큼 시도해도 성공 확률이 약 2^-64라는 말이라는 점이다. 게시글의 계산은 공격 비용을 무시하지도 않고, 성공 가능성을 0이라고 부르지도 않는다.
컴퓨터로 증명했다는 말의 범위
게시글 작성자는 두 계수 생성 방식의 건전성을 Lean 4와 수학 라이브러리 Mathlib 등을 이용해 증명했다고 설명한다. Lean은 사람이 수학적 주장과 증명 단계를 컴퓨터가 확인할 수 있는 형식으로 작성하도록 돕는 도구다. 게시글은 사용한 곡선과 관련 수학적 성질, Lean 커널의 검사도 신뢰 기반으로 제시한다. 또 작성한 모델을 BIP340 테스트 벡터와 대조했다고 밝힌다.
형식 증명의 장점은 복잡한 논증에서 사람이 단계 하나를 무심코 건너뛰거나 필요한 조건을 빠뜨리는 위험을 줄이는 데 있다. 특히 누적 생성 방식에서는 앞 계수를 보고 뒤 항목을 선택할 수 있으므로, 계수들이 처음부터 서로 독립적이라고 단순 가정하는 설명만으로는 충분하지 않다. 게시글의 증명은 마지막으로 잘못된 서명까지의 앞부분을 따로 살피고, 새로운 해시 응답이 잘못된 묶음을 완성할 수 있는 경우를 제한하는 방식으로 이 문제를 다룬다고 한다.
그렇지만 컴퓨터가 확인하는 것은 어디까지나 작성된 모델과 그 안의 논증이다. 테스트 벡터와의 대조도 모델과 구현이 모든 가능한 입력에서 완전히 같다는 증명으로 자동 변환되지는 않는다. 확보된 자료는 게시글 작성자의 설명이지, 별도 감사 결과나 모든 실제 구현에 대한 검증 보고서가 아니다. 따라서 형식 증명은 강력한 근거이지만, 모델이 실제로 배치 데이터를 어떻게 구성하는지까지 제대로 반영하는지는 따로 중요한 질문으로 남는다.
메시지를 어디서 끊어 읽는지도 중요하다
그 질문이 구체적으로 드러나는 곳이 입력 인코딩이다. 게시글의 증명은 서로 다른 배치가 서로 다른 해시 입력을 만든다고 가정한다. 그래야 배치를 바꾼 공격자의 새로운 시도를 해시 함수에 대한 별도의 입력으로 다루는 논증이 성립한다.
문제는 길이가 제각각인 메시지를 길이 표시 없이 이어 붙일 때다. 예를 들어 메시지 두 개가 각각 ‘AB’와 ‘C’인 경우와 ‘A’와 ‘BC’인 경우를 생각해 보자. 경계 표시 없이 이어 붙이면 둘 다 ‘ABC’다. 메시지 사이에서 한 글자를 옮겨 서로 다른 배치를 만들었는데도, 해시에 들어가는 연결 결과는 같을 수 있다. 해시 함수의 성능 문제가 아니라, 함수가 입력받기 전에 두 구성이 같은 문자열로 표현되는 문제다.
작성자는 BIP340 문서의 시드 입력과 글에서 다룬 누적 방식 모두에 이런 주의점이 있다고 지적한다. 따라서 임의 길이 메시지를 그대로 이어 붙이는 경우에는 게시글의 확률 경계가 그 증명만으로 따라오지 않는다. 그렇다고 이것이 곧바로 실제 공격이 성공했다는 뜻도 아니다. 정확히 말하면, 제시된 증명의 전제가 충족되는지 다시 살펴야 한다는 뜻이다.
게시글은 비트코인에서 서명되는 메시지가 32바이트 길이의 서명 해시, 즉 sighash인 경우에는 이 문제가 영향을 주지 않는다고 설명한다. 길이가 고정돼 있으면 메시지 경계를 같은 방식으로 정할 수 있기 때문이다. 임의 길이 메시지까지 다루려면 각 메시지 앞에 길이를 해시 입력에 포함하는 방법도 제안한다. 이 차이는 같은 ‘BIP340 서명’이라는 이름만 보고 서로 다른 사용 환경에 결론을 옮기면 안 되는 이유다.
결국 128비트 계수가 안전하다는 말의 의미는 ‘절반으로 줄여도 아무 일 없다’가 아니다. 게시글이 제시한 두 생성 방식에서는, 해시를 랜덤 오라클로 보는 모델과 배치 인코딩 조건 아래 공격자의 q번 질의를 포함한 확률 경계가 나온다는 뜻이다. libsecp256k1 배치 검증에서 제시된 최대 약 9%의 속도 이점도 그 조건과 나란히 놓고 읽어야 한다. 속도 개선의 숫자와 안전성의 숫자를 비교하기 전에, 누가 입력을 고르고 얼마나 시험할 수 있으며 그 입력이 무엇을 뜻하는지부터 확인해야 하는 이유다.