ㅍㅍㅅㅅ

51% 공격에 대한 수학적 정리

여러분도 51% 공격(51% Attack)에 대한 이야기를 들어본 적 있을 것이다. 이에 대한 것은 여러 글에서 언급된 적이 많다. 51% 관련 글들을 보면 다음과 같다.

• 블록체인 51% 공격 주의보
• 블록체인 2.0 | 51% 공격은 기능인가 취약점인가?
• PoW를 위기에 빠뜨린 ‘51% 공격’

51% 공격(혹은 취약점)이라 함은 채굴이 가능한 노드 중 과반 이상이 공격 노드(혹은 장부조작을 하고자 하는 노드)인 경우 장부의 조작을 합법적으로 할 수 있다는 것이다. 즉 누군가가 채굴 노드의 과반 이상을 통제해 합법적으로 장부를 조작하는 공격을 뜻한다.

「비트코인 백서」에 나오는 수학 공식 이야기한다더니 갑작스럽게 51% 공격에 대한 이야기로 시작해서 조금 당황했을지 모르겠다. 아시다시피 「비트코인 백서」에는 51% 공격과 직접 연결된 내용은 없다. 또 하나, 「비트코인 백서」를 자세히 설명한 자료가 많기는 하지만 유독 한 부분에 대한 설명을 찾기가 어려운데, 그건 바로 PoW에서 등장하는 수학 공식에 대한 설명 부분이다. 그리고 여기에 처음 등장하는 수식이 있다.

「비트코인 백서」의 내용을 살펴보자

1. q_0는 공격자(attacker) 노드가 현재 장부를 완료한 시점에서 그다음 장부를 합법적으로 조작(더 정확하게 말하자면, 다음 장부를 합법적으로 수정하는 것을 의미)할 수 있는 가능성(확률)을 의미한다.
2. p_0는 합법적인 노드가 현재 장부(0)를 완료한 시점에서 다음 장부(0+1)에 합법적으로 수정(혹은 기입)할 가능성을 의미한다.
3. 다음노드(0+1)의 입장에서는 정확한(혹은 정직한) 장부로 완료가 되거나, 공격자에 의해 거짓된 장부로 완료되거나 둘 중 하나가 된다(즉 그 중간은 없다). 이를 수학적으로 표현하면, p_0 = 1-q_0
4. 만약 현재 장부가 아닌 h만큼 과거에서 다음 장부(0+1)를 조작되어 완료될 할 가능성은 q_h가 된다.
5. 만약 공격(혹은 추월)을 해야 할 장부가 그다음 장부(0+1)에서 꽤 떨어져 있다면(h가 상대적으로 큰 수), 다음 장부가 공격(혹은 조작)당할 가능성은 0(zero)에 수렴한다 (h가 무한대).
6. q_h는 공격자가 h개의 장부만큼 떨어진 시점에서 그다음 장부(0+1)를 조작할 가능성(확률)을 의미한다.

7. h개만큼의 과거(혹은 뒤 쳐진 장부)에서 다음장부(0+1)가 정상적인 장부로 완료 될 가능성은 p_h=1-q_h
8. 현재 장부를 완료한 시점에서 공격자 노드(q_0)와 정상 노드(p_0)의 비율은 채굴 가능한 노드들 중에서 정상 노드와 공격자 노드의 비율과 동일 하다. 예를 들어 100개의 채굴 노드가 있다고 했을 때 65개가 정상적인 노드라면 p_0=0.65, q_0=0.35가 된다.
9. 51% 공격에서 "51%"는 바로, p_0<=q_0인 경우를 의미한다.
10. 하지만 (위의 수식 상으로) 더 엄밀하게 말하면 51%가 아니라, 50(+)%를 의미한다. 즉 50%보다 조금만 더 높아도 소위 말하는 "51% 공격"을 당한다.
11. 실제로 51% 공격을 당할 가능성은, 공격 노드가 과반이 되지 않더라도 존재한다(수식의 두 번째 조건).
12. 실제 다음 장부가 조작될 가능성은 현재 (초기)상태(0)의 정상 노드와 공격 노드의 비율을 의미할 뿐만 아니라, 만들어질 다음 장부(0+1)까지의 거리 (h)에 의해 결정된다.

계속 수학 공식 이야기를 하자

앞에서는 첫 번째 공식에 대해서 이야기했다. 이제 2~4의 수학 공식을 이야기하려고 한다. 우선 공식들을 설명하기 전에 우선 알아야 할 것이 있는데, 정리하자면 다음과 같다.

1. 백서에서는 포아손 분포(Poission Distribution)를 이야기하지만 사실상 포아손 프로세스(Poission Process)를 의미한다.
2. 분포와 프로세스의 가장 큰 차이점은 시계열성(Time Series)의 여부다.
3. 분포는 단순한 확률이지만 프로세스는 확률모델(Stochastic Process)이다.
4. 물론 수식 상으로 포아손 확률과 포아손 프로세스는 한 끗 차이다.
5. 현재 장부가 공식적으로 확정된 시점부터 그다음 장부가 확정될 때까지 새로 만들어지는 장부의 확정을 기준으로 가능성(확률)을 계산하기 때문이다.
6. 프로세스를 단순한 분포로 다룰 수 있는 이유는 시계열의 모델(Stochastic Model)이라고 하더라도, 확률의 계산은 “한순간”을 다루기 때문이다.
7. 이러한 “한순간”을 시간순으로 엮으면 시계열, 혹은 Stochastic Process가 된다.
8. 우리가 최종적으로 분석하고자 하는 것은 “공격자가 그다음 장부를 조작된 채로 만들어질 가능성(확률)의 기댓값(Expected Value)”이다.
9. 블록체인 백서에서 다루는 장부생성에 관한 모델은 도박이론(Gambler’s Ruin Problem)을 기반으로 하지만 구하는 값은 공격자가 성공할 확률(즉 정상 노드가 실패할 할 확률)을 다룬다.
10. 참고로 도박이론에서는 도박꾼이 돈을 벌 확률 확률(즉 블록체인에서 정상적인 노드의 장부가 확정될 확률)을 다룬다.

블록체인과 확률모델

다시 백서의 내용을 보자.

11. 우리가 원하는 분석을 하기 위해서 기본적으로 정상 노드(honest nodes)가 다음 장부가 확정되기 전까지 새로 만들어진 블록(혹은 장부)의 수는 항상 정해져 있고, 알고 있다고 가정한다 (h가 정해짐).
12. 이후 공격자에 대한 확률적 분석은 이 전제를 기반으로 한다.
13. 반면 공격자 노드에 의해 평균적으로 만들어지는 장부(블록)의 수는 정상 노드와 공격자 노드에 따라 결정 된다.

14. 여기서 중요한 것은 실제로 공격자가 만드는 블록의 정확한 수(X)는 알 수가 없으나 포아손 분포를 따른다.
15. 계산한 값(λ_q)은 공격자가 만드는 평균 장부의 수는 포아손 분포의 인자(factor)가 된다.

16. 공식적으로 장부가 확정된 이후, 그다음 장부가 확정될 때까지 정상 노드가 만들어지는 장부의 수가 h이고, 같은 주기동안 공격자가 만든 장부의 수를 s라고 하면, 공격자가 그다음 (확정될) 장부를 조작하기 위해 추월해야 할 장부의 수는 h-s가 된다.
17. 그리고 h-s만큼 떨어진 공격자의 장부로 그다음 장부를 조작할 가능성(확률)이 3식이다.
18. 여기에 공격자 노드(attackers)와 정상 노드(honest nodes)의 비율(q_0, p_0)을 알고 있다면, 공격자 노드의 그다음 장부 조작의 가능성(확률)이 바로 3식이다(3식 첫 번째).
19. 만약, 한 주기 동안 만들어내는 공격자의 장부의 수가 정상 노드가 만들어내는 장부의 수보다 큰 경우(X>h) 그다음 만들어지는 장부는 무조건 조작된 장부, 즉 공격자에 의해 만들어진 장부다(3식 두 번째).
20. 공격자가 만드는 장부의 숫자는 X고 random variable이다. s 또한 공격자가 만드는 장부의 숫자이다. 이 두 인자(X, s)는 같기도 하고, 다르기도 하다. 이에 대한 정확한 차이를 알고 있다면, 당신은 확률론에 대해 상당한 내공을 가지고 있다는 의미이다.

21. 블록체인의 분석은 정상 노드로부터 만들어진 장부의 숫자는 정해진 것(h; deterministic)으로 가정하고, 공격자가 만든 장부의 숫자는 불확실한 것(X; random)으로 가정한다.

22. 이 수식은 사실 수식 3과 "정확하게" 동일한 수식이다.