저자: 조나스 닉
출처: https://blog.blockstream.com/op_checkshrincs-a-hash-based-signature-opcode-for-post-quantum-bitcoin/
현재 비트코인에 양자 내성 서명을 통합하는 구체적인 해결책은 없습니다. 블록스트림 리서치는 지난 1년간 이 문제를 연구해 왔습니다. 이 글에서는 연구 결과를 공유하고, 최적화된 해시 함수 기반 서명이 비트코인의 양자 내성을 위한 실용적인 선택이며 조만간 적용될 수 있음을 주장합니다. 또한, 잘 정립된 암호학적 가정을 기반으로 최소 서명 크기를 갖는 양자 내성 서명 방식인 "SHRINCS"와 "SHRIMPS"를 소개하고, 예비 제안을 제시합니다.
최신 비트코인 출력 방식은 슈노르(Schnorr) 공개 키에 자금을 잠그고, 이러한 출력을 사용하려면 유효한 슈노르 서명이 필요합니다. 그러나 슈노르 서명은 양자 컴퓨터에 취약합니다. 양자 후 서명 검증을 추가하는 가장 자연스러운 방법은 탭루트(Taproot) 스크립트 트리에 양자 후 옵션을 추가하는 것입니다. 소프트 포크 업그레이드를 통해 비트코인 출력은 슈노르 공개 키와 양자 후 서명된 공개 키에 동시에 커밋될 수 있습니다. 탭루트는 실제로 사용된 스크립트의 머클 트리 경로만 공개하기 때문에 사용자는 슈노르 서명을 계속 사용하여 자금을 사용할 수 있으며(서식 크기가 작아 거래 수수료가 저렴함), 거래 비용은 거의 변하지 않습니다. 양자 후 옵션은 스크립트 트리에 조용히 대기할 수 있습니다. 충분히 강력한 양자 컴퓨터가 사용 가능해지면 사용자는 두 번째 경로, 즉 양자 후 서명을 사용하여 자금을 사용하는 방식으로 전환해야 하며, 이때 더 높은 거래 비용이 적용됩니다.
양자 업그레이드 후 실패 시나리오
양자 저항으로의 업그레이드는 여러 가지 이유로 실패할 수 있으며, 이러한 상황을 사전에 방지하는 것이 나중에 논의될 설계 선택에 영향을 미칩니다.
- 처리량이 급격히 감소했습니다 . 서명 크기가 너무 크면 블록 공간이 쉽게 부족해져 많은 사용자가 거래를 전혀 확인할 수 없게 됩니다.
- 검증 비용 . 서명 검증에 필요한 계산량이 너무 높으면 서명을 완벽하게 검증할 수 있는 노드 수가 줄어들어 네트워크의 중앙 집중화에 영향을 미칠 수 있습니다.
- 서명 비용 . 하드웨어 서명 장치 및 리소스가 제한된 장치도 합리적인 시간 내에 서명을 생성할 수 있어야 합니다.
- 암호화 방식이 뚫렸습니다 . 그 방식은 보안 가정에 의존했는데, 그 가정이 영원히 참일 수는 없었습니다.
- 아무도 그 제안을 채택하지 않았습니다 . 업그레이드 제안이 너무 복잡하거나 기존 인프라에 통합할 수 없었기 때문입니다. 당신 혼자 제안을 채택하는 것만으로는 충분하지 않습니다. 네트워크상의 다른 모든 사용자가 해킹당하면, 당신의 코인이 아무리 완벽하게 안전하더라도 경제적 가치는 없습니다.
- 구현의 복잡성 . 제안된 구현에는 버그가 있거나 공격에 취약할 수 있으며, 비트코인 합의 규칙의 고유한 특성으로 인해 사람들은 사소한 호환성 문제조차 발생시키지 않고 이 코드를 무기한으로 유지 관리해야 합니다.
이러한 함정을 피할 수 있는 제안만이 대략적인 합의를 얻을 가능성이 있다.
표준 후보자
첫 번째 후보군은 NIST(미국 국립표준기술연구소)에서 표준화한 서명 방식들입니다. 이러한 방식들은 이미 존재하며 구현체도 제공되므로, 최소한의 노력으로 비트코인 업그레이드 제안(BIP)으로 변환할 수 있습니다. 비교 기준은 Taproot 출력에 사용된 Schnorr 서명 방식입니다. 모든 거래에 Schnorr 서명을 사용한다면, 현재 평균 거래 크기를 기준으로 비트코인 네트워크는 초당 약 6.5건의 거래를 처리할 수 있습니다. 본 논문에서 사용된 모든 초당 거래량(TPS)은 거래당 평균 입력 2.27건, 출력 2.64건( transactionfee.info 에 따른 2026년 3월 30일 기준 90일 평균)을 가정하고 있으며, 비트코인 블록 크기 제한은 일정하게 유지된다고 가정합니다.
슈노르 서명은 현재 지갑 인프라가 의존하는 기능, 특히 BIP 32 비강화 키 파생 기능을 지원합니다. 또한 최근 몇 년 동안 비트코인 생태계 전반에 걸쳐 배포된 효율성 향상 기능(예: MuSig2)과 계획된 개인정보 보호 및 효율성 개선 기능(예: 임계값 서명, 비공개 결제, 입력 간 서명 집계)을 가능하게 했습니다.
- "격자" 가정에 기반한 ML-DSA 는 처리량을 초당 절반의 트랜잭션(NIST 보안 레벨 3 기준)으로 줄일 뿐만 아니라, BIP 32 비강화 키 유도를 포함한 Schnorr 서명의 모든 기능을 잃게 됩니다.
- SLH-DSA는 해시 함수를 기반으로 합니다. 이 해시 함수는 비트코인이 이미 사용하고 있는 보수적인 가정을 바탕으로 하므로 NIST 보안 등급 1을 목표로 할 수 있습니다. 그러나 처리량은 초당 0.36건으로 더욱 감소하며, 슈노르 서명의 장점도 상실될 것입니다.
이 두 가지 접근 방식 모두 즉각적인 해결책은 아니며, 네트워크 처리량을 크게 떨어뜨릴 것입니다. 블록 크기 제한을 늘리면 처리량 문제를 완화할 수 있지만, 시급하고 실용적인 양자 컴퓨팅 이후 업그레이드를 논란의 여지가 있는 블록 크기 증가와 연계하는 것은 성공할 가능성이 낮습니다. 블록 크기 제한은 별도로 논의하는 것이 가장 좋습니다.
추가 조사가 필요한 후보자
NIST에서 표준화한 솔루션은 배포가 간편하지만, 감수해야 할 단점이 많습니다. 다른 대안들은 더 나은 절충안을 제시하지만, 안정적인 배포 옵션이 되기까지는 훨씬 더 많은 연구와 시간이 필요합니다.
- Falcon^WS 는 비교적 새로운 격자 기반 서명 방식입니다. 서명 크기 면에서 상당한 개선을 보여주지만(NIST 보안 레벨 5에서 처리량은 초당 1건에 달함), 아직 상용화하기에는 미성숙한 단계입니다. 이 예시는 격자 기반 서명 방식이 궁극적으로 어떤 가능성을 제시하는지 보여주기 위해 포함되었습니다.
- Schnorr 서명 특징 집합과 일치하는 BIP 32 및 임계값 서명과 같은 격자 서명은 추가 연구가 필요한 유망한 방향입니다. 그러나 이러한 특징을 추가하면 서명 크기가 (이러한 특징을 무시하는 격자 방식과 비교하여) 상당히 증가하여 처리량이 약 1 TPS로 감소할 수 있으며, 이는 Falcon^WS보다 낮은 수준입니다. 예를 들어, 수정된 Raccoon-G 방식은 계층적 결정론적 키 유도(강화되지 않은 유도 포함)를 지원하지만 공개 키 크기는 16kB에 달하고 서명 크기는 20kB입니다.
- SQIsign은 "동형성(isogeneities)"을 기반으로 하며, 뛰어난 서명 크기와 약 3.6 TPS(보안 수준 5) 상승 처리량을 자랑합니다. 또한 동형성은 Schnorr 서명의 특성을 지원할 가능성이 있습니다. 하지만 문제는 SQIsign의 암호화 가정이 격자(lattice) 기반 암호화 가정보다 훨씬 덜 성숙되어 있다는 점입니다. 따라서 보안 침해 리스크 현실적이며 단기간에 제거하기 어려울 것으로 예상됩니다. 새로운 암호화 가정에 대한 신뢰를 구축하는 데는 상당한 시간이 걸릴 것입니다.
- 블록 수준 서명 집계는 간결한 증명(SNARK)을 사용하여 블록 내 모든 서명을 집계합니다. 보수적으로 추정하면 각 블록에 500kB의 증명이 필요하며, 이로 인해 초당 약 6.7건의 처리량이 발생합니다. 최근 BitZip 과 LeanVM이 이 방식을 제안했습니다. 하지만 누가 증명을 계산할 것인지, 채굴 중앙 집중화를 어떻게 방지할 것인지, 그리고 상당한 엔지니어링 복잡성 등 여러 가지 해결해야 할 문제가 남아 있습니다.
해시 함수 기반 서명 및 서명 할당량을 최적화합니다.
이러한 모든 후보들은 보안 가정, 효율성, 속성 및 복잡성이라는 다차원적인 상충 관계 내에 존재합니다. 해시 함수 기반 서명의 경우, 특히 두 가지 방향이 유망해 보입니다. 첫째, 상태 유지라는 새로운 차원을 추가하여 완전히 새로운 설계 공간을 열 수 있습니다. 둘째, 프로토콜 복잡성이 약간 증가하는 대신 성능이 크게 향상되는 것을 감수할 수 있습니다. 이 두 가지 접근 방식을 결합하면 해시 함수 기반 서명이 매력적인 후보가 됩니다. 새로운 암호학적 가정을 도입하지 않고도 더 높은 효율성을 제공하며, 암호화 방식은 비교적 해석하고 구현하기 쉽습니다.
"메모리 요구 사항"은 모든 해시 함수 기반 서명 방식에 내재된 개념인 " 서명 할당량 "을 활용합니다. 이 매개변수는 단일 공개 키로 새 메시지에 안전하게 서명할 수 있는 횟수를 나타냅니다. SLH-DSA에서 할당량은 2^64로 설정되어 있으며, 이는 실제 응용 분야에서 사실상 무한대에 가깝습니다. 할당량을 의도적으로 줄이면 최종 서명 크기를 줄일 수 있지만, 할당량이 소진되면 공개 키의 보안이 손상됩니다.
SLH-DSA 서명 할당량을 2^64로 설정하면 서명 크기는 약 8kB가 되어 처리량은 초당 0.36건(TPS)에 불과합니다. 할당량을 2^40(공개 키당 1조 개의 서명)으로 줄여도 현재 블록 크기에서는 할당량이 소진되지 않고 수백 년 동안 사용할 수 있습니다. 이처럼 할당량을 줄이면 서명 크기는 5.7kB로 줄어들어 처리량이 33% 증가합니다.
신
그렇다면 서명 할당량을 얼마나 줄일 수 있을까요? 비트코인 기본 계층에서는 보안 모범 사례에 따라 주소 재사용이 권장되지 않으므로 일반적인 공개 키는 서명에 몇 번만 사용됩니다. 따라서 서명 예산은 매우 낮을 수 있습니다. 이보다 더 많은 서명이 필요한 사용자를 위해 백업 옵션을 제공할 수 있습니다. 이 방식은 공개 키에 두 가지 서명 경로를 제공합니다. 하나는 할당량 내에서 작은 서명을 생성하는 간결한 경로이고, 다른 하나는 서명 횟수를 기억할 필요 없이 서명을 생성하는 항상 사용 가능한 백업 경로입니다.
간결한 경로에는 대가가 따릅니다. 서명자는 할당량을 초과하지 않도록 서명 횟수를 지속적으로 추적해야 합니다. 이 카운터가 바로 상태 이며, 이를 사용하는 방식은 상태 저장 방식입니다. 데스크톱 및 모바일 지갑과 같은 환경에서는 백업 가져오기가 일상적인 작업이기 때문에 상태 저장 방식을 지원하기 어렵습니다. 이전 백업을 다시 가져오면 의도치 않게 카운터가 이전에 사용했던 값으로 되돌아갈 수 있습니다. 이후 서명은 해당 상태를 재사용하게 되어 사용자의 자금이 위험에 처할 수 있습니다. 블록스트림 리서치 팀을 포함한 비트코인 개발자들은 비트코인 제품이 오용에 강하도록 노력해 왔습니다. 상태 저장 방식은 본질적으로 (상태 비저장 방식에 비해) 더 취약합니다. 처음 이 방향을 탐구했을 때, 우리는 흥미로운 기술이지만 실용적이지는 않다고 생각했습니다.
하지만 사용자가 실수로 서명 상태를 손상시키는 것을 방지하는 메커니즘이 있습니다. 바로 전용 서명 장치입니다. 이 장치는 초기화 후 시드 항을 생성하고 초기 상태를 설정하며, 이 상태는 해당 장치에만 저장되고 외부로 유출되지 않습니다. 이 장치는 간결한 서명을 생성합니다. 이 상태는 공개되어 있으므로 소프트웨어 지갑은 거래 전송 전에 준비된 서명이 상태를 재사용하지 않았는지 확인하는 추가 보안 검사를 수행할 수 있습니다. 서명 장치를 분실, 손상 또는 교체하는 경우 사용자는 시드 항을 새 장치로 가져올 수 있으며, 그러면 새 장치는 자동으로 상태 비저장 경로로 전환되어 더 크고 상태가 없는 서명을 생성합니다. 장치에 상태를 완벽하게 보존함으로써 사용자가 서명을 손상시킬 가능성을 완전히 제거합니다.
우리는 이렇게 만들어진 구조를 "SHRINCS"라고 명명할 것입니다. 이 구조는 두 가지 핵심 아이디어에 기반합니다.
- 공개 키는 두 가지 서명 경로와 함께 사용할 수 있습니다 . 하나는 간결하고 상태를 유지하는 경로이고, 다른 하나는 상태를 저장하지 않는 백업 경로입니다.
- 이 설계는 매우 효율적이고 간결한 경로를 사용합니다 . 자세한 내용은 이 논문의 범위를 벗어나지만, 이 구조는 기존의 해시 함수 기반 서명 방식을 직접적으로 기반으로 합니다.
처리량 비교:
- SLH-DSA : 0.36 TPS
- SLH-DSA의 서명 할당량이 2^40으로 감소했습니다. (초당 처리량 0.48건)
- SHRINCS 컴팩트 경로 (서명 크기 580바이트): 최대 3 TPS(각 서명이 컴팩트 경로를 사용한다고 가정할 경우)
SHRINCS의 리스크 프로필은 다른 양자 컴퓨팅 후보들과 크게 다릅니다. 다른 후보들은 네트워크의 모든 사용자에게 영향을 미치는 시스템적 리스크, 즉 낮은 처리량, 불확실한 암호화 가정, 취약한 합의 프로토콜 등을 안고 있습니다. 반면 SHRINCS는 개별 기기의 상태 관리라는 국소적인 리스크 에 의존합니다. 안전한 배포 가능성과 이러한 처리량 수치를 고려할 때, SHRINCS는 더 이상 흥미로운 기술이 아니라 양자 컴퓨팅에 대한 현실적인 방어 수단이 될 수 있습니다.
새우
SHRINCS 방식에서 시드 항을 새로운 장치로 가져오는 것은 상태 비저장 백업 경로를 트리거하여 서명 크기를 증가시키기 때문에 비용이 많이 듭니다. 그러나 이러한 백업 경로는 키 수명 주기 동안 자주 발생하지 않습니다. SHRINCS는 이러한 점을 활용하여 백업 장치를 위한 두 번째 소형 경로를 추가합니다. 1,000개의 서명 할당량을 사용하면 이 경로는 약 3,000바이트 크기의 서명을 생성합니다. 이는 기본 장치 서명 크기의 5배이지만 백업 경로(SLH-DSA 서명)보다는 2.5배 작습니다.
백업 경로 최적화
상태 유지를 통합하는 것은 앞서 언급한 두 가지 방향 중 하나입니다. 다른 하나는 상태 비저장 백업 경로 자체를 최적화하는 것입니다.
SLH-DSA 서명의 7,872바이트(초당 0.36건)부터 다음과 같은 최적화를 추가할 수 있습니다.
- 서명 할당량을 2^40으로 줄이면 서명 크기가 5,792바이트(초당 0.48건)로 줄어들어 약 26% 감소합니다.
- WOTS+C (블록스트림 암호학자 미하일 쿠디노프가 공동 저자로 참여)와 PORS+FP 는 SPHINCS+의 직접적이고 쉽게 사용 가능한 대안이지만, SLH-DSA 체계에서는 채택되지 않았습니다. 이를 통해 서명 크기를 5,060바이트(초당 0.54건 처리)로 줄여 성능 저하 없이 약 13%를 추가로 감소시킬 수 있습니다. 유일한 단점은 NIST 표준을 준수하지 않는다는 것입니다.
- 서명 및 키 생성 시간을 5배로 늘리면 크기가 약 11% 추가적으로 줄어들어 4,496바이트(초당 0.60건)가 됩니다.
- 바이트당 검증 시간이 Schnorr 서명의 약 1.5배까지 상승 , 이를 약 13% 더 줄여 3,896바이트(초당 0.69건)까지 낮출 수 있습니다.
이러한 모든 요소를 결합하면 상태 비저장 해시 함수 기반 서명의 크기를 SLH-DSA 서명의 절반으로 줄일 수 있습니다. 서명 또는 검증 시간이 더 오래 걸리는 대신, 서명 크기를 더욱 줄이기 위한 더욱 강력한 조치를 취할 수도 있습니다.
순진한 제안
이 제안은 두 가지 설계 원칙에 기반합니다.
첫째, (SLH-DSA 방식과 비교했을 때) 검증 시간을 늘리지 않습니다. 이는 향후 블록 크기 제한을 늘리는 것을 더욱 어렵게 만들지 않기 위함입니다. 또한 블록 수준 서명 집계가 도입될 경우 SNARK 증거 생성 과정을 크게 간소화합니다.
둘째로, "모든 용도에 하나의 서명"이라는 개념은 폐기되고, 특정 적용 시나리오에 맞는 여러 서명 방식이 도입됩니다.
- 데스크톱 및 모바일 레이어 1 지갑은 상태를 안전하게 저장할 수 없지만, 일반적으로 더 빠른 CPU를 갖추고 있습니다. 이러한 지갑은 서명 시간을 희생하는 대신 서명 크기를 줄이는 상태 비저장 서명 방식을 사용할 수 있습니다. 서명 할당량이 2^40일 때 서명 크기는 약 4,496바이트입니다. 이 할당량은 우발적으로 초과될 가능성을 훨씬 뛰어넘는 크기입니다.
- 서명 전용 장치는 상태를 안전하게 보존하도록 설계할 수 있지만, 일반적으로 프로세서 성능이 약하기 때문에 서명 비용을 높이는 것은 현실적인 전략이 아닙니다. SHRINCS와 SHRIMPS는 상태 저장 서명 방식을 사용하여 서명 크기를 줄이고 서명 속도를 높입니다. 상태 비저장 방식의 대체 경로는 2^32의 서명 할당량을 사용합니다(하드웨어 서명 장치에서 버튼을 40억 번 누르는 사람은 없을 것입니다). 기본 장치의 서명 크기는 약 580바이트이고, 대체 장치(소형)의 서명 크기는 약 3,000바이트이며, 대체 경로의 서명 크기는 약 4,336바이트입니다.
- 라이트닝 노드는 본질적으로 상태를 유지하며 더 빠른 서명 속도의 이점을 누립니다. 채널 업데이트는 전용 서명 장치의 백업 경로와 동일한 상태 비저장 방식을 사용합니다. 서명 할당량은 2^32, 즉 약 4,336바이트입니다. 약 40억 개의 서명을 처리한 노드는 새로운 공개 키로 교체할 수 있습니다. SHRINCS의 간소화된 경로(약 580바이트)를 사용하면 협력적 채널 폐쇄가 가능합니다.
그 결과, 네 가지의 독자적인 서명 변형이 결합되었습니다. 실제 처리량은 0.60~3.04 TPS에 이르며, 표준 SLH-DSA 방식의 0.36 TPS를 훨씬 능가합니다.
해결되지 않은 질문과 한계점
이 제안은 완성된 디자인이라기보다는 출발점에 가깝습니다. 또한 몇 가지 한계점과 미해결 문제가 있습니다.
- 검증 시간이 크기보다 우선합니다 . 이 제안은 검증 시간을 희생하는 대신 서명 크기를 더욱 최적화할 수 있습니다. 현재 바이트당 검증 비용은 슈노르 서명보다 6배 낮으므로 이론적으로 블록 검증 시간을 늘리지 않고도 블록 크기를 6배까지 늘릴 수 있습니다. 더 엄밀한 근거를 제시하려면 더 나은 벤치마킹이 필요합니다. (역자 주: 네트워크 대역폭 병목 현상으로 인해 이러한 극단적인 시도는 현실적으로 불가능합니다.)
- 서명 방식의 동질성 및 개인정보 보호 수준 저하 : 하나의 서명 방식만 사용하는 대신 여러 서명 방식을 조합하여 사용할 수 있도록 허용하면 이러한 서명 방식의 개인정보 보호 수준이 동시에 저하됩니다.
- 적용 범위 및 레이어 2 : 이 제안에서 다루지 않는 애플리케이션 시나리오가 있습니까? 이 제안은 레이어 2 프로토콜과 어떻게 상호 작용합니까?
- 소프트 포크 통해 도입될 수 있는 미래 의 SNARK 기반 서명 집계에 대비하여 서명 체계를 어떻게 설계해야 할까요? 이러한 점을 지금 고려해야 할까요?
- 서명 시간 : 다양한 컴퓨팅 플랫폼에서 서명에 허용 가능한 시간은 어느 정도일까요? 더 나은 서명 시간 벤치마크를 통해 서명 크기를 크게 줄일 수 있을 것입니다.
- 참조 구현 : C++ 코드인가, 아니면 형식 명세인가? 대규모 언어 모델(LLM) 시대에는 합의에 중요한 코드에 대한 형식 검증이 그 어느 때보다 실현 가능해졌습니다.
다음은 무엇인가요?
비트코인의 양자 컴퓨팅 업그레이드를 위한 설계 공간은 매우 광범위하며, 어떤 단일 서명 방식도 확실히 정답이라고 할 수는 없습니다. 그럼에도 불구하고, 최적화된 상태 저장 해시 기반 서명은 오늘날의 표준 방식보다 더 나은 절충점을 제공합니다. 이러한 방식은 향후 소프트 포크 에 의존하지 않고도 비트코인을 계속 사용할 수 있도록 해줄 가능성을 지니고 있습니다. 한편, 더 나은 격자 기반 방식, 서명 집계, 호몰로지 기반 암호화와 같은 장기적인 개선 방안에 대한 연구도 병행되어야 합니다.
다행히 배포 문제는 서명 방식 선택과 대체로 무관합니다. 새로운 해시 함수 기반 opcode는 Taproot, Taproot v2 또는 BIP 360 "Pay to Merklegen"을 통해 배포할 수 있습니다.
해시 함수 기반 서명 방식에 상태 저장 기능을 추가함으로써 얻을 수 있는 최적화 효과는 아직 충분히 연구되지 않았습니다. 상태 저장 기능이 가져올 수 있는 다른 잠재적인 최적화 효과는 무엇일까요? 신중한 엔지니어링 설계로 상태 저장 장치의 보안을 보장할 수 있을까요? 다양한 계층 2 프로토콜이 상태 저장 서명을 직접 활용할 수 있을까요?
해시 함수 기반 서명과 그 매개변수에 대해 더 자세히 알아보려면 저희 논문 " 비트코인을 위한 해시 함수 기반 서명 고려하기 "를 참조하십시오. 이 글에 나오는 숫자들은 여기에 있는 스크립트를 사용하여 도출할 수 있습니다. Simplicity 언어로 작성된 검증기인 SHRINCS의 C++ 구현체 와 초안 사양은 GitHub에서 확인할 수 있습니다. SHRINCS는 이미 프로덕션 환경에 배포 가능하며, Liquid 온체인 에서 시연을 마쳤고 , 누구나 직접 사용해 볼 수 있습니다.
(위에)
