저자: 니콜라스 베스코보
BitVM 프레임 임의의 오프체인 연산에 대한 낙관적 검증을 비트코인 네트워크에 도입하여 zk 롤업이나 사이드체인 브리지와 같은 더욱 복잡한 연산을 가능하게 하도록 설계되었습니다. BitVM은 낙관적 검증을 지원하는 메커니즘을 도입함으로써 비트코인의 유연성을 향상시킵니다. 반면 BitVMX는 다른 기술을 사용하여 특정 연산에 대한 검증을 더욱 빠르고 효율적으로 수행함으로써 더 나은 결과를 얻습니다. 여기서 "낙관적 검증" 이란 연산이 유효하지 않다는 것이 증명되지 않는 한 유효하다고 가정하는 검증 방식을 의미합니다.
이러한 시스템의 보안을 보장하기 위해 BitVM과 BitVMX는 램포트(Lamport) 및 윈터니츠(Winternitz) 서명을 사용합니다. 이러한 암호화 방식은 전체 프로세스의 "상태 유지"를 보장하는 데 핵심적인 역할을 합니다. BitVM과 BitVMX는 이러한 서명 체계를 통해 다양한 공격에 대한 강력한 보안을 제공하고 모든 작업이 정확하게 실행되도록 보장합니다.
이 문서에서는 "램포트 서명"과 "윈터니츠 서명"이 무엇인지, 후자가 전자의 개념을 어떻게 확장했는지, 그리고 BitVM에서 어떻게 사용되는지 설명합니다. 또한 이러한 서명이 BitVM 및 BitVMX에 상태 유지 기능을 제공하여 특정 변수가 한 번 설정되면 이후 스크립트에서 수정하거나 재사용할 수 없도록 하는 방법을 설명합니다.
램포트와 빈터니츠 서명 이해하기
전자서명 체계는 전자 메시지(또는 문서)의 진위와 무결성을 검증하는 데 사용되는 수학적 방법입니다. 간단히 말하자면 다음과 같습니다.
- 램포트 서명은 일회성 전자 약정 (기본적으로 해시 함수 기반)을 사용하여 위조 불가능한 서명을 제공합니다.
- 반면, 윈터니츠 서명은 암호학적 보안을 달성하기 위해 단방향 함수를 여러 번 반복 (종종 체인 형태로) 사용합니다.
1970년대 후반 레슬리 램포트가 제안한 램포트 서명은 해시 함수 기반 전자 서명 방식입니다. 암호화 해시 함수의 단방향 속성을 활용하여 보안을 강화합니다. 램포트 서명은 단순성과 양자 컴퓨팅 공격에 대한 저항력으로 잘 알려져 있습니다. 서명 과정은 미리 대량 의 키 쌍을 생성한 후 이를 사용하여 서명하는 방식으로 진행됩니다. 하지만 서명 크기가 매우 커서 적용 분야에 제약이 있을 수 있습니다.
랄프 머클과 로버트 윈터니츠가 각각 독립적으로 제안한 윈터니츠 서명은 해시 함수 기반의 또 다른 유형의 디지털 서명입니다. 램포트 서명과 유사한 보안 수준을 제공하면서도 효율성이 더 높습니다. 램포트 서명과 비교했을 때, 윈터니츠 서명은 체인 구조를 활용하여 서명 크기를 줄이고 실용성을 높였습니다. 사용자가 윈터니츠 매개변수를 조정할 수 있도록 함으로써, 계산 속도와 서명 크기 사이의 균형을 맞출 수 있으며, 본질적으로 램포트 서명 방식을 일반화한 것입니다.
램포트 서명: 형식적 관점
이 장에서는 램포트 서명의 생성, 사용 및 검증 과정을 단계별로 설명합니다. 키 생성 과정, 메시지 서명 및 서명 검증의 기술적 측면을 살펴봅니다. 마지막으로 관련 보안 고려 사항과 취약점에 대해 논의합니다.
키 생성
서명해야 하는 메시지의 각 비트 i에 대해, 각각 $S_{i, 0}$과 $S_{i, 1}$로 표시되는 두 개의 임의 문자열(비트 시퀀스)을 생성합니다. 메시지 길이가 n비트인 경우, i의 값은 0부터 $n-1$까지의 범위를 갖습니다.
개인 키는 이러한 임의의 문자열 쌍 $(S_{i, 0}, S_{i, 1})$로 구성됩니다(여기서 $i = 0, 1, …, n-1$).
개인 키의 각 문자열 쌍 $(S_{i, 0}, S_{i, 1})$에 대해 이 문자열의 해시를 계산하고 쌍으로 유지합니다: $(H(S_{i, 0}), H(S_{i, 1}))$.
공개 키는 이러한 해시 쌍 $(H(S_{i, 0}), H(S_{i, 1}))$로 구성됩니다(여기서 $i = 0, 1, …, n-1$).
서명 메시지
서명할 메시지 m을 이진 형식, 즉 $m = m_0m_1…m_{n-1}$로 변환합니다. 여기서 각 $m_i$는 비트(0 또는 1의 값)입니다.
메시지의 각 비트 $m_i$에 대해 서명에는 해당 개인 키 $S_{i, m_i}$가 포함됩니다.
궁극적으로 서명은 n개의 요소로 이루어진 시퀀스입니다: (S_{0, m_0}, S_{1, m_1},...,S_{{n-1}, m_{n-1}}) .
서명을 확인하세요
메시지 m과 그 서명 (S_{0, m_0}, S_{1, m_1},...,S_{{n-1}, m_{n-1}}) 이 주어졌습니다.
메시지 m을 이진 형식으로 변환합니다: $m = m_0m_1…m_{n-1}$.
각 비트 $m_i$에 대해 서명의 해당 요소의 해시 값 $H(S_{i, m_i})$을 계산합니다.
계산된 각 해시 값 $H(S_{i, m_i})$이 공개 키의 해당 요소($H(S_{i,0})$ 또는 $H(S_{i, 1})$)와 일치하는지 확인합니다.
안전 고려 사항
- 일회용 : 램포트 서명 방식은 각 키 쌍이 하나의 메시지에만 서명하는 데 사용될 때만 안전합니다. 동일한 키 쌍을 사용하여 여러 메시지에 서명하면 개인 키의 일부가 노출되어 보안이 손상됩니다.
- 해시 함수 : 램포트 서명 방식의 보안은 사용되는 암호화 해시 함수의 강도에 달려 있습니다. 해시 함수는 역상 공격, 제2 역상 공격 및 충돌 공격에 대한 저항력을 가져야 합니다.
왜 "일회용 서명"이라고 부르는 걸까요?
램포트 서명 방식은 동일한 공개 키를 사용하여 여러 메시지에 서명할 경우 보안이 급격히 떨어지기 때문에 "일회용 서명"으로 알려져 있습니다. 서명하는 메시지가 추가될 때마다 개인 키에 대한 정보가 더 많이 노출되어 공격자가 서명을 위조하기가 더 쉬워지기 때문입니다.
공격자는 서명 하나만 관찰해도 공개 키에 있는 모든 해시 값 쌍 중 하나의 해시 값의 역상을 알 수 있습니다. 하지만 서명 두 개를 알면 절반의 해시 값 쌍의 역상 두 개와 나머지 절반의 역상 하나를 알 수 있습니다. 서명 세 개를 알면 4분의 3의 해시 값 쌍의 역상 두 개를 알 수 있고, 이런 식으로 서명이 하나씩 늘어날수록 보안 수준이 점차 낮아집니다. 즉, 동일한 공개 키의 보안성은 서명이 하나씩 추가될 때마다 실질적으로 절반 반감 것입니다.
(역자 주: 저자는 앞 단락에서 비트가 무작위로 분포된다는 가정을 사용했습니다.)
예를 들어, 공개 키가 2차 역상 공격에 대해 256비트의 보안을 제공하고 충돌 공격에 대해 128비트의 보안을 제공하도록 설계된 경우, 세 번 서명된 후에는 실질적인 공격이 가능해집니다. 네 번 서명된 후에는 메시지와 서명을 연결하는 것이 매우 쉬워집니다. 이러한 취약점은 공격자가 알려진 해시값(및 그 역상)을 사용하여 원하는 메시지에 대한 새로운 유효한 서명을 생성할 수 있기 때문에 발생합니다. 특히 메시지에 어느 정도 유연성이 있는 경우 이러한 공격이 더욱 효과적입니다.
램포트 시그니처 취약점은 두 번 이상 사용될 때 발생합니다.
램포트 서명을 사용하여 동일한 공개키로 반복적으로 서명할 때 발생하는 주요 취약점은 공격자가 이전에 관찰된 서명에서 얻은 정보를 이용하여 임의의 메시지에 대한 서명을 위조할 수 있다는 점입니다. 공격자가 동일한 공개키를 사용하여 여러 메시지에 대해 생성된 서명을 알고 있다고 가정해 보겠습니다. 이 경우 공격자는 알려진 서명들을 조합하여 새롭고 유효한 서명을 만들어낼 수 있습니다.
예를 들어, 길이가 16비트인 메시지를 생각해 보겠습니다.
서명된 메시지는 m1 = 0001111101110001 및 m2 = 0111110000111111입니다. 공격자는 위 두 메시지의 서명에서 대응하는 부분을 조합하여 새로운 메시지 m * = 0101111000110101에 대한 서명을 위조할 수 있습니다. m1 과 m2 의 대응하는 비트를 사용하여 구성된 모든 m * 는 유효한 서명을 위조할 수 있습니다. 즉, 이러한 비트에 대응하는 해시 값의 역상을 사용하여 간단하게 서명을 구성할 수 있습니다.
메시지가 서명되기 전에 해시되는 경우(즉, 서명이 메시지 자체가 아니라 해시 값인 경우), 공격은 더 복잡해지지만 여전히 가능합니다. 공격자는 이전에 서명된 메시지들의 해시 값과 충분히 많은 동일한 부분을 공유하는 메시지 m * 의 해시 값을 찾아야 합니다. 관찰 가능한 서명이 추가될 때마다 공격에 필요한 해시 함수 평가 횟수가 줄어들어 위조가 더 쉬워집니다.
기본적으로 램포트 서명 방식을 사용할 때는 보안 유지를 위해 각 공개 키는 한 번만 사용해야 합니다. 하나의 공개 키를 여러 메시지 서명에 재사용하면 공격자가 새로운 서명을 위조하는 데 필요한 정보를 얻을 수 있게 되어 궁극적으로 이 암호화 시스템의 무결성을 손상시킬 수 있습니다.
윈터니츠의 특징: 이론적 관점
앞서 논의했듯이, 윈터니츠 일회용 서명(WOTS)은 램포트 서명을 개선한 것으로, 서명과 공개 키의 크기를 크게 줄였습니다. 하지만 공짜는 없습니다. 이러한 개선에는 서명을 생성하고 검증하는 데 더 많은 노력이 필요하다는 대가가 따릅니다. 이 장에서는 윈터니츠 서명에 대한 공식적인 정의와 작동 방식을 설명합니다.
매개변수 및 시작
- W: 윈터리츠 파라미터는 양의 정수이며, 한 번에 처리할 수 있는 비트 수를 결정합니다.
- n: 해시 출력의 길이(비트 단위).
- l: 메시지 다이제스트의 세그먼트 수는 $l = \lceil n/W \rceil$로 계산됩니다. 여기서 $\lceil \rceil$는 주어진 숫자보다 크거나 같은 가장 작은 정수를 취함을 의미합니다.
- l': 체크섬의 길이로, $l' = \lceil (\log_2(l * (2^W - 1)))/W \rceil$로 계산됩니다.
- L: 서명의 전체 길이, L = l + l'.
키 생성
길이 n의 임의 비트 문자열 $S_i$ L개를 생성합니다. 여기서 $i = 0, 1, …, L-1입니다.
개인 키는 다음과 같은 임의의 비트 문자열로 구성됩니다: $S = (S_0, S_1, …, S_{L-1})$.
각 개인 키 조각 $S_i$에 대해 해시 함수 $2^W$를 연속적으로 적용합니다: $P_i = H^{2^W}(S_i)$.
공개 키는 다음 해시 결과로 구성됩니다: $P = (P_0, P_1, …, P_{L-1})$
서명 메시지
서명할 메시지 m을 W비트 길이의 l개 조각으로 나눕니다: $m = (m_0, m_1, …, m_{l-1})$.
체크섬 C를 계산합니다: $C = \sum_{i=0}^{l-1}(2^W - 1 - m_i)$.
체크섬 C를 길이 W비트의 l'개 조각으로 변환합니다: $C = (c_0, c_1, …, c_{l'-1})$. 일반적으로 첫 번째 요소가 체크섬으로 사용됩니다: $C = (c_0)$.
다이제스트의 각 조각 $m_i$와 체크섬 $c_i$에 대해, 해당 개인 키 조각 $m_i$번을 해싱하여 서명 $\sigma_i$를 생성합니다. $\sigma_i = H^{m_i}(S_i)$, 여기서 $i = 0, 1, …, l-1$입니다.
마찬가지로 체크섬 부분의 경우: $\sigma_{l+j} = H^{c_j}(S_{l+j})$, 여기서 $j = 0, 1, …, l'-1$입니다.
완전한 서명은 다음 조각들의 조합입니다: $\sigma = (\sigma_0, \sigma_1, …, \sigma_{L-1})$.
서명을 확인하세요
메시지 m과 그 서명 $\sigma = (\sigma_0, \sigma_1, …, \sigma_{L-1})$이 주어졌습니다.
메시지 m을 l개의 부분으로 나눕니다: $m = (m_0, m_1, …, m_{l-1})$.
체크섬 C를 계산하고 이를 l'개 부분으로 나눕니다: $C = (c_0, c_1, …, c_{l'-1})$.
각 서명 조각 $\sigma_i$에 대해 해시 함수 $2^W - 1 - m_i$번을 적용하여 공개 키 조각을 도출하려고 합니다.
$$
P_i : \widehat{P_i} = H^{2^W - 1 - m_i}(\sigma_1) , \qquad i = 0, 1, …, l -1
$$
마찬가지로 체크섬 부분에 대해서도 다음과 같습니다.
$$
\widehat{P_{l+j}} = H^{2^W - 1 - c_{j}}(\sigma_{l+j}) , \qquad j = 0, 1, …, l' -1
$$
파생된 공개 키 $(\widehat{P_0}, \widehat{P_1},…, \widehat{P_{L-1}})$가 공개 키 $P = (P_0, P_1, …, P_{L-1})$와 일치하면 유효한 서명입니다.
안전 고려 사항
- 매개변수 선택 : W 값의 선택은 서명 크기와 계산 효율성 간의 균형에 영향을 미칩니다. W 값이 클수록 서명 크기는 작아지지만 서명 및 검증에 필요한 계산 부담은 증가합니다.
- 일회용 : 램포트 서명과 마찬가지로 빈터니츠 서명도 일회용으로만 사용해야 합니다. 동일한 키 쌍을 재사용하여 여러 메시지에 서명하면 개인 키에 대한 정보가 노출되어 보안이 손상될 수 있습니다.
아래 그림은 W=2, l=5일 때 윈더리츠 체인(개인키에서 공개키를 유도하는 과정)의 순서를 보여줍니다. 각 화살표는 해시 작업 검색을 나타냅니다. (역자 주: 원문의 오류가 수정되었습니다.)
체크섬이 필요한 이유는 무엇인가요?
기술적인 관점에서 볼 때, 윈터니츠 서명 체계에서 체크섬은 보안을 유지하고 서명 과정의 무결성을 보장하는 데 필수적입니다.
윈터니츠 서명 방식은 메시지를 여러 조각으로 나누고, 각 조각의 값에 따라 해당 개인 키 조각을 특정 횟수만큼 해싱하는 방식으로 작동합니다. 그러나 이 과정에는 취약점이 있습니다. 공격자가 해시 체인의 값들로 구성된 서명을 알고 있다면, 해시 체인의 후속 요소들을 이용하여 유효한 서명을 재구성할 수 있습니다. 해시 체인의 요소 하나만 노출시켜도 공격자는 모든 후속 해시 값(주어진 값에 대한 동일한 개인 키 조각의 서명)을 계산할 수 있기 때문에, 서명의 무결성을 훼손할 수 있습니다.
이러한 리스크 완화하기 위해 체크섬은 매우 중요합니다. 체크섬은 메시지에 대한 모든 수정 사항이 체크섬에도 일관되게 반영되도록 보장합니다. 이는 개인 키 없이는 계산적으로 불가능한 작업입니다. 해시 체인의 후속 값을 사용하려면 서명 체크섬의 해시 체인에서 이전 값을 알아야 하는데, 개인 키 없이는 불가능하기 때문입니다. 체크섬은 추가적인 검증 계층 역할을 하여, 역상 생성 능력이 없는 공격자가 개인 키 없이 다른 메시지에 대한 유효한 서명을 생성하는 것을 방지합니다.
(역자 주: 여기서의 논리는 해시 체인이 단방향이기 때문에 체크섬을 고려하지 않고 WOTS 서명을 아는 것만으로는 공격자가 더 큰 $m_i$ 값에 대해서만 서명을 위조할 수 있다는 것입니다. 즉, 해시 체인의 뒷부분 값을 사용해야 합니다. 그러나 앞서 언급한 체크섬 $C = \sum_{i=0}^{l-1}(2^W - 1 - m_i)$를 사용하면 $m_i$가 클수록 C 값은 작아집니다. 이러한 C 값을 가진 서명을 만들려면 개인 키 해시 체인의 앞부분 값을 사용해야 합니다. 알려진 서명에서 이를 유도하려면 해시 연산을 역으로 수행해야 하는데, 이는 계산적으로 불가능합니다. 따라서 개인 키 없이는 서명을 생성하는 것이 불가능합니다.)
또한 체크섬은 서명 과정의 무결성을 보장합니다. 이는 서명 과정에서 비트가 누락되거나 대체되지 않았는지 확인하는 최종 검사입니다. 이를 통해 메시지 전체가 고려되었고 서명에 정확하게 표현되었음을 보장합니다.
또한 체크섬은 서명의 전반적인 무결성을 검증합니다. 즉, 올바른 횟수의 해시 반복이 적용되었는지 확인하여 서명이 정확하고 안전한지 보장합니다.
체크섬이 없으면 이 방식은 공격에 매우 취약합니다. 공격자는 메시지 조각을 쉽게 바꿔치기하여 개인 키 없이도 유효한 서명을 생성할 수 있습니다. 또한 체크섬이 없으면 불완전한 검증이 이루어져, 바꿔치기되거나 잘린 메시지가 서명된 것으로 간주될 수 있습니다.
BitVM과 BitVMX: 램포트와 윈터니츠의 특징이 뚜렷하게 드러나는 분야.
앞서 언급했듯이 BitVM과 BitVMX는 비트코인 네트워크에 임의의 오프체인 연산에 대한 낙관적 검증을 제공하도록 설계된 프레임 입니다. 두 프레임워크 모두 램포트 서명 또는 윈터니츠 서명을 사용하여 강력한 데이터 커밋먼트를 생성할 수 있습니다. 여기서 커밋먼트란 특정 데이터가 존재했고, 안전하게 기록되었으며, 특정 시점에 서명되었다는 암호학적 보증을 의미합니다. 이러한 커밋먼트는 향후 검증자의 이의 제기에 활용될 수 있습니다. 이러한 서명을 사용함으로써 각 커밋먼트는 검증 가능하고 변조 방지 기능을 갖추게 됩니다.
검증자가 운영자의 의견에 동의하면 별도의 조치가 필요하지 않으며 운영은 정상적으로 진행됩니다. 그러나 검증자가 운영자의 의견에 동의하지 않는 경우, 양측이 이러한 약정에 공개적으로 서명했으므로, 양측은 서로의 정보를 이용하여 상대방이 사기를 시도하거나 잘못된 운영을 수행하고 있음을 입증할 수 있습니다.
BitVM의 핵심 혁신은 여러 트랜잭션에 걸쳐 상태를 유지하고 참조할 수 있는 기능입니다. 이는 매 단계마다 일회용 서명을 사용하여 상태를 확정함으로써 가능합니다. BitVM은 램포트 서명을 활용하여 모든 상태 전환이 안전하게 확정되고 후속 작업에서 안정적으로 참조될 수 있도록 보장합니다.
결론적으로
램포트 서명과 윈터니츠 서명은 BitVM 및 BitVMX 프로토콜에 사용하기에 적합한 여러 가지 바람직한 특성을 지니고 있습니다. 이러한 서명을 해당 프로토콜에 통합하면 비트코인의 스크립팅 기능이 크게 향상되어 효율적이고 안전한 상태 저장 작업이 가능해집니다. 데이터 커밋먼트에 이러한 서명을 사용하면 네트워크가 보안과 성능을 유지하면서 더욱 복잡한 트랜잭션을 처리할 수 있습니다. 이러한 암호화 기술은 비트코인의 미래에 매우 중요하며, 신뢰 최소화 사이드체인 브리지 및 낙관적으로 검증된 영지식 증명과 같은 더욱 발전되고 안전한 탈중앙화 애플리케이션의 발전을 위한 기반을 마련합니다.
(위에)
