2023-06-28
4145
양자컴퓨터 시대에도 비트코인은 안전할까요?
이 질문은, '유의미한 시간 안에 임의의 SHA256 충돌을 일으킬 수 있는가?'와 관련됩니다.(참조: 해시함수란 무엇인가요?)
SHA256은 임의의 입력값을 받아 고정된 256비트의 숫자로 출력해주는 해시함수이며, 보통 출력값은 16진수 64자리로 표현합니다. SHA256은 기본적으로 충돌이 없다고 가정하지만, 디지털 데이터의 종류는 무한한 반면 SHA256 출력은 256비트로 제한되어 있기 때문에, 서로 다른 2^256개의 입력을 초과하는 또 다른 입력이 주어지면 비둘기집의 원리에 의해 반드시 충돌이 발생합니다. 다시 말해서, 빠르게 2^256번의 연산을 할 수 있는 엄청난 성능의 컴퓨터가 존재한다면, 임의의 SHA256 해시값의 충돌을 쉽게 찾을 수 있다는 것입니다. 그렇다면 2^256은 얼마나 큰 수일까요? 편의를 위해 2^256 = 10^77정도로 근사해 계산해보겠습니다.
현재 비트코인 네트워크의 해시레이트는 평균 350 EH/s 입니다. 이는 초당 3.5 * 10^20번, 연간 10^28번의 SHA256 연산을 수행한다는 의미입니다. 이 속도라면, 비트코인 네트워크는 향후 10^49년 안에는 반드시 SHA256 해시충돌을 찾게 됩니다. 그러면 10^49년은 얼마나 긴 시간입니까? 우주의 나이가 '겨우' 1.38 * 10^10년 정도로 추산된다는 점을 생각하면, 현재의 컴퓨팅 기술로는 SHA256 충돌을 찾는 것이 사실상 불가능합니다.
그렇다면 양자컴퓨터의 경우는 어떠합니까?
보통 사람들이 양자컴퓨터에 대해 갖는 이미지는 '엄청나게 빠른 컴퓨터'입니다. 그러나 이는 정확한 이해가 아닙니다. 양자컴퓨터는 다항 시간안에 소인수 분해를 할 수 있는 쇼어 알고리즘과 같이, 특수한 양자 알고리즘을 적용하여 효율적으로 풀 수 있는 일부 문제들에 강한 특수한 컴퓨터입니다. 그런 문제들 중에는, 소인수분해를 사용하는 공개 키 암호체계인 RSA나, 비트코인이 공개키 <-> 개인키를 구현하는데 사용하는 ECDSA(타원곡선암호)의 해독과 같은 것들이 있습니다. 그러나 여전히 양자컴퓨터로 임의의 SHA256 해시충돌을 찾는 효율적인 방법은 알려져 있지 않습니다. 그로버 알고리즘 등이 존재하지만, 이는 단순히 사용된 암호체계의 자릿수를 늘리는 것만으로도 간단하게 대처가 가능합니다.
뿐만 아니라, 비트코인의 주소가 도출되는 과정을 살펴보면 단순히 개인키에 ECDSA를 적용해 도출한 공개키 자체가 비트코인 주소가 되는 것이 아니라, 그 이후에도 SHA256과 RIPEMD160을 통해 두 차례 더 해시를 합니다. 따라서, SHA256과 RIPEMD160의 해시충돌을 임의로 빠르게 찾을 수 있는 방법이 없다면 비트코인의 공개주소를 보고 개인키를 알아내는 것은 불가능합니다.
결론적으로, 빠르게 양자컴퓨터가 발전하여 가시적으로 위협이 될 수준이 된다면 이는 RSA, ECDSA 등을 광범위하게 사용중인 전세계 군사/경제/금융계에는 큰 피해를 끼칠 것이나 여전히 비트코인은 가장 빠르게 대처하고 나쁜 사태를 예방할 것입니다.
심지어 SHA256에 대한 일반적 충돌을 찾아내는 방법이 나온다고 하더라도, 사토시가 이미 2010년에 제안한 것처럼 비트코인 네트워크도 이에 발맞추어 양자내성을 가진 서명방식의 새로운 주소체계를 따르는 프로토콜로 업그레이드를 하면 됩니다. 이 경우 특정 이익집단의 주도로 이루어지는 포크가 아니며 취약한 기존 체인에 남아서 모든 자금을 잃기만을 기다리고 있을 동기가 없기 때문에 체인이 갈라지지 않을 것입니다.
2020년에 나온 한 논문[6]을 보면, 유저가 양자 내성을 지닌 디지털 서명을 따르는 주소로 자금을 이동할 수 있도록 하는 프로토콜이 제안된 바 있으며, 이를 구현할 시 소프트포크만으로 충분히 문제가 해결될 것으로 보입니다.
그러나 이것은 아직 일어나지 않은 미래의 일에 대한 사고 실험이며, 우리 생애 중 이런 일이 일어날지 조차 알 수 없으므로, 현실적으로 벌써 걱정할 문제라고 보기는 어렵습니다.
요약하면 다음과 같습니다.
- SHA256은 매우 뛰어난 성능의 양자컴퓨터가 나온다고 해도 안전할 것이다.
- RSA, ECDSA 등은 쇼어 알고리즘을 실용적으로 구현할 수 있는 양자컴퓨터가 나오면 위험해질 수 있다. 그러나 비트코인의 주소는 ECDSA 적용 이후에도 SHA256 / RIPEMD160 을 통한 두 번의 해시함수를 더 적용해 도출되므로, SHA256의 임의충돌을 만들어낼 수 있는 방법이 발견되기 전까지는 안전할 것이다.
- 설사 그런 방법이 발견된다 하더라도, 양자 내성을 지닌 디지털 서명 방식을 따르는 주소 체계를 따르는 포크를 적용하면 된다.
참고:
1. Will quantum computing break SHA-256 encryption?
2. Quantum Computers Break Encryption in China But Far From Cracking Bitcoin
3. 사토시가 사라지기 전, 그가 남긴 기록들 - 1분 비트코인
4. SHA-256 충돌은 왜 발견되지 않았을까?
5. @atomicBTC - 양자컴퓨터가 나오면 비트코인은 끝일까?
6. 양자 내성에 대한 커밋, 더 나은 방어: 빠른 양자 컴퓨팅 공격에 대한 비트코인의 속도와 위험을 구성할 수 있는 방어
4