BitMEX Research 제공
출처: https://blog.bitmex.com/quantum-safe-lamport-signatures/
초록 : 본 논문에서는 1979년에 발명된 해시 함수 기반 양자 안전 디지털 서명 체계인 램포트 서명을 소개합니다. 이 기법을 통해 양자 안전 서명이 어떻게 매우 간단하여 복잡성이나 새로운 수학 계산을 필요로 하지 않는지 설명합니다. 비트코인이 양자 안전 서명 체계를 채택한다면 이러한 해시 기반 서명이 우리가 취해야 할 방향이 될 수 있다고 주장합니다. 양자 컴퓨팅이 비트코인에 즉각적인 위협이 될 것이라고 단정 지을 만한 확실한 근거는 없습니다(당분간은 아닙니다). 하지만 양자 컴퓨팅의 인식된 위협을 완화하는 첫 번째 단계는 사용자에게 비트코인을 안전하게 사용할 수 있는 방법을 제공하는 것이라고 생각합니다. 이러한 옵션이 제공되면 일반 사용자의 채택은 자연스럽게 다음 단계로 이어질 것입니다.
- 레슬리 램포트, 미국의 수학자이자 컴퓨터 과학자 -
개요
최근 "비트코인의 양자 컴퓨팅 위협 노출"이 이슈 화두였습니다. 최근 샌프란시스코 프레시디오 비트코인에서 이 문제를 주제로 한 컨퍼런스가 열렸습니다. 저희는 사람들이 최대한 합리적으로 행동해야 한다고 생각합니다. 저희는 양자 컴퓨팅을 이해하지 못하고, 양자 컴퓨팅 하드웨어에서 아직 인상적인 결과를 보지 못했기 때문에 우려할 필요는 거의 없어 보입니다. 하지만 저희의 아이디어가 일부 사람들에게는 위협적으로 느껴질 수 있다는 것도 알고 있습니다. 양자 컴퓨팅은 (이론적으로) 매우 빠르게 발전할 수 있기 때문입니다. 일반적인 우려는 비트코인이 새롭고 복잡하며 리스크 포스트 양자 암호화 디지털 서명 체계로 업그레이드해야 할 수도 있다는 것입니다. HAWK , SQI , Falcon , CRYSTALS 등 유행처럼 들리는 여러 체계에 대한 내용을 읽어보실 수 있습니다. 이러한 새로운 체계는 자체적인 리스크 안고 있을 수도 있습니다. 만약 우리가 잘못된 것을 선택한다면 어떨까요? 2023년에는 새로운 포스트 양자 암호화 체계인 " SIKE 알고리즘 "이 기존의 비양자 컴퓨팅에 의해 무력화되었다는 보고가 있었습니다. 게다가 양자 컴퓨팅이 너무나 빠르게 발전해서 거의 아무도 이해하지 못한다면, 이러한 체계가 정말 안전하다고 확신할 수 있는 사람이 누구겠는가?
하지만 비트코인이 양자 이후 디지털 서명 체계로 업그레이드된다면 복잡하고 리스크 신기술은 필요 없게 될 것입니다. 비트코인의 디지털 서명 체계인 타원 곡선 디지털 서명 알고리즘(ECDSA)은 빠른 소인수분해를 위해 쇼어 알고리즘을 사용하기 때문에 잠재적으로 양자 취약성을 가지고 있습니다. 그러나 해시 함수는 양자 컴퓨팅에 대해 매우 안전합니다. SHA256과 같은 해시 함수의 취약점은 그로버 알고리즘 에 의해 보안성이 2차적으로 저하된다는 것입니다. 즉, 256비트의 보안 대신 128비트만 사용하게 됩니다. 이는 대체로 용인되는 것으로 보이며, 필요한 경우 충분히 긴 출력값을 가진 해시 함수를 사용할 수 있습니다.
실제로 해시 함수에만 의존하는 서명 체계가 있습니다. 예를 들어, 1979년에 발명된 램포트 서명은 비트코인에서 사용하는 타원 곡선 기반 체계보다 훨씬 간단합니다. 게다가 해시 함수에만 의존하기 때문에 양자 안전합니다. 따라서 비트코인에 양자 안전 서명 체계를 도입한다면 복잡한 새로운 수학에 의존할 필요가 없습니다. 대신 해시 함수 기반 체계를 선택하면 됩니다. 그러면 비트코인은 작업 증명 채굴 과 서명을 포함한 모든 작업에 해시 함수를 사용할 수 있어 비트코인을 더욱 간소화할 수 있습니다. 이 글의 나머지 부분에서는 램포트 서명의 개념과 작동 방식을 살펴보겠습니다.
램포트 서명은 어떻게 작동하나요?
다음 예에서는 Lamport 서명이 SHA256 해시 알고리즘을 사용한다고 가정하지만, 작동 원리에 영향을 미치지 않고 거의 모든 해시 함수를 사용할 수 있습니다. Lamport 서명에서 개인 키는 ECDSA 서명처럼 단일 256비트 난수가 아닙니다. 대신, 각각 256개의 256비트 난수를 포함하는 두 개의 난수 집합으로 구성됩니다. 이 예에서는 이 두 집합을 "집합 A"와 "집합 B"라고 합니다. 따라서 Lamport 서명에서 개인 키는 2 * 256 * 256 = 131072 bits = 16.3 KB 입니다. 이 512개의 256비트 난수는 각각 해시되고, 결과 해시는 해당 공개 키가 되어 공개 키의 크기는 16.3 KB 됩니다. 비트코인 주소는 공개 키를 구성하는 모든 문자열을 연결한 SHA256 해시일 수 있습니다. 다음 다이어그램은 개인 키와 공개 키 간의 대응 관계를 보여줍니다.
메시지에 서명할 때 첫 번째 단계는 SHA256을 사용하여 메시지를 해싱하고 출력(해시 값)을 이진수로 변환하는 것입니다. 이 이진수의 각 자릿수는 서명에 포함되는 개인 키를 결정합니다. A 집합은 0, B 집합은 1입니다. 해시 값의 첫 번째 비트는 개인 키의 첫 번째 난수에 해당하고, 두 번째 비트는 두 번째 난수에 해당하며, 나머지도 마찬가지입니다. 따라서 서명은 개인 키의 50%를 무작위로 선택하여 생성됩니다.
이 메시지를 검증하기 위해 검증자는 메시지를 해시하고 해시 값의 이진 표현의 각 비트를 사용하여 검증에 사용할 공개 키를 결정하기만 하면 됩니다. 그런 다음 검증자는 서명의 각 숫자를 해시하여 해당 공개 키와 일치하는지 확인합니다. 두 숫자가 정확히 일치하면 서명은 유효합니다. 서명자는 모든 개인 키를 알아야 하며, 해시 함수는 무작위이므로 서명할 메시지를 알기 전까지는 서명에 필요한 집합 A 또는 집합 B의 어떤 부분이 필요한지 예측할 수 없습니다. 따라서 이 방식이 안전한 이유를 쉽게 알 수 있습니다. 검증 과정은 계산적으로 간단합니다.
일회용의
램포트 서명의 주요 약점은 공개/개인 키 쌍을 한 번만 사용할 수 있다는 것입니다. 트랜잭션이 서명되어 블록체인 온체인 게시되면 개인 키의 50%가 노출됩니다. 동일한 공개 키가 다시 사용되면 남은 개인 키의 50%가 추가로 노출됩니다. 통계적으로 이는 전체 개인 키의 75%가 노출된다는 것을 의미합니다. 개인 키를 재사용하는 횟수가 많을수록 보안성이 크게 저하되는 것을 쉽게 알 수 있습니다. 즉, 개인 정보 보호 측면에서는 좋지만, 주소를 재사용하지 못할 수 있다는 단점도 있습니다.
- 사람들은 주소를 재사용하는 데 익숙합니다.
- 누군가가 이미 사용된 주소로 자금을 보내면 어떻게 되나요?
- RBF를 어떻게 구현할까요? 추가 입력을 추가하고 이 추가 입력에만 서명하는 방식으로 구현할 수 있지만, 이 경우 UTXO 선택 문제가 발생합니다.
유연한 수학이 없다
또 다른 단점은 ECDSA와 같은 유연한 수학적 기법을 사용할 수 없다는 것입니다. 예를 들어, BIP-32 결정적 계층형 지갑은 ECDS 기능을 활용하여 "xpub(확장 공개 키)"를 사용할 수 있도록 합니다. 이는 해시 함수만 사용하는 시스템에서는 불가능합니다.
용량
또 다른 주요 문제는 램포트의 공개 키와 서명의 엄청난 크기입니다. 공개 키는 16KB, 서명은 8KB로 총 24KB입니다. 비트코인 블록은 수십 개의 거래만 포함할 수 있는 반면, 오늘날의 블록은 수천 개의 거래를 포함할 수 있습니다. 그러나 모든 양자 안전 솔루션은 이 문제를 어느 정도 공유하는 것으로 보입니다.
스핑크스+
방금 데모 목적으로 기존 램포트 서명 체계를 분석하여 해시 함수에만 의존하는 서명 체계가 어떻게 작동하고 양자 안전할 수 있는지 보여주었습니다. 비트코인에 해시 기반 서명 체계를 통합한다면 훨씬 더 진보된 옵션이 있습니다. 1982년, 윈터니츠는 램포트 체계의 변형을 발표했습니다. 윈터니츠의 체계는 메시지 해시를 절반으로 나누고 이 두 숫자를 개인 키의 다른 부분에 매핑하여 더 많은 해싱 라운드를 필요로 했습니다. 2011년에는 더 새로운 변형인 XMSS 가 등장했고, 2015년에는 해시 기반 서명 체계의 또 다른 변형인 SPHINCS가 도입되었습니다.
SPHINCS+는 훨씬 작은 서명을 허용하며, 개인 키는 여러 번 재사용될 수 있습니다. 이러한 방식은 모두 머클 트리 구조를 사용하며, 최상위에 "전역 공개 키"가 위치하여 일반적으로 서명 크기가 32바이트에 불과합니다. 비트코인이 포스트 양자 서명 방식을 채택한다면, 머클 트리를 사용하는 이러한 해시 함수 서명 방식을 사용할 수 있습니다. 비트코인은 이미 머클 트리를 광범위하게 사용하고 있기 때문에 서명에도 매우 편리합니다.
라이트닝 랩스(Lightning Labs)의 공동 창립자인 올라올루와 오순토쿤(Olaoluwa Osuntokun)은 최근 샌프란시스코에서 열린 양자 보안 컨퍼런스(Quantum Security Conference)에서 SPHINCS+ 서명을 발표했습니다. 그는 이 프레젠테이션에서 SPHINCS+ 사용 시 직면하는 장단점과 우선순위에 따라 원하는 기능을 구현하는 방법을 설명했습니다. 조정 가능한 매개변수에는 서명 생성 해싱 비용, 서명 검증 해싱 비용, 안전한 재사용 횟수, 그리고 서명 크기가 포함됩니다. 올라올루와는 이러한 조정을 통해 궁극적으로 서명 크기를 2KB로 줄일 수 있을 것이라고 언급했는데, 이는 합리적인 것으로 보입니다. 물론 이는 현재 온체인 서명 크기(약 70바이트)보다 훨씬 큰 크기입니다.
출처: https://x.com/PresidioBitcoin/status/1945877820657508650
결론적으로
ECDSA가 직면한 양자 위협에 대해 깊이 이해하지는 못하지만, 이를 추구할 만한 설득력 있는 이유는 없다고 생각합니다. 비트코인에 사용되는 ECDSA 방식은 수십 년 동안 안전할 가능성이 높으므로, 양자 컴퓨터의 성능에 대한 더 구체적인 입증이 나올 때까지 기다리는 것이 합리적인 결정일 수 있습니다. 하지만 비트코인을 어떻게 양자 안전하게 만들 수 있을지 고려해 보는 것은 가치가 있을 수 있습니다. 첫 번째 단계는 해시 기반 서명 방식을 사용하여 비트코인을 안전하게 사용할 수 있는 방법을 만드는 것입니다. 취약한 자금을 동결 계획을 논의하는 것은 양자 안전한 지출 방식이 개발되고 널리 사용되기 전까지는 큰 의미가 없다고 생각합니다. 양자 안전한 지출 방식이 개발되고 널리 채택될 때에만 이 논의에 참여할 가치가 있을 것입니다.
물론 해시 기반 서명 체계를 추가하려면 상당한 작업이 필요합니다. 서명 크기가 상당히 크고, 그에 따라 거래 수수료도 상당히 높은데, 이러한 양자 안전 서명 체계가 어떻게 채택될 수 있을까요? 블록 가중치 할인과 블록 크기 제한으로 완전히 새로운 방식을 도입해야 할까요? 아니면 거래/UTXO 수 대신 가치로 채택률을 측정할 수도 있습니다. 아마도 이러한 양자 안전 체계는 ETF 제공업체나 비트코인 리저브처럼 거래가 거의 발생하지 않는 수천 개의 비트코인을 보유한 기관들이 먼저 도입할 것입니다. 이러한 기관들에게는 추가 거래 수수료 부담이 미미할 것입니다. 개별 사용자는 2KB 서명이 필요한 양자 안전 출력에 저축을 저장하고, 일일 지출은 양자 취약 출력에 사용할 수 있습니다. 이러한 일일 지출은 주소 재사용을 방지하기 위해 P2WPKH 출력을 사용함으로써 비교적 안전하게 보호될 수 있습니다. P2WPKH는 또한 해시 함수를 양자 방지 수단으로 사용하므로, 사용자는 거래가 확인되지 않은 동안만 리스크 에 노출됩니다.
양자 안전 서명 체계가 널리 채택되면 양자 리스크 완화를 위한 다음 단계에 대한 논의가 훨씬 수월해질 것입니다. 저희는 양자 안전 상환 옵션이 존재하게 되면 궁극적으로 합리적인 사용자들이 앞으로 나아갈 방향을 제시할 것이라고 생각합니다. 만약 양자 안전 출력을 선호한다면 괜찮습니다. 그건 그들의 선택입니다. 만약 채택이 진정으로 널리 확산된다면, 자금 동결, 블록 가중치 제한 변경, BIP-39 시드 워드와 같은 양자 안전 복구 체계, 그리고 사람들이 필요하다고 생각하는 다른 모든 조치들과 같은 논란의 여지가 있는 다른 조치들을 논의할 수 있을 것입니다. 결정은 코인 보유자들이 하게 두겠습니다.
(위에)
