비트코인 이기적 채굴과 Dyck 단어: 조합적 증명

목차

1. 서론

이기적 채굴(Selfish Mining, SM)은 비트코인에서 블록을 은닉하는 전략으로, 프로토콜 난이도 조정 메커니즘의 결함을 이용합니다. 공개된 가장 긴 체인을 항상 확장하는 정직한 채굴자와 달리, 이기적 채굴자는 새로 채굴된 블록을 은닉하여 비밀 포크를 생성하고, 수익을 극대화하기 위해 전략적으로 이를 공개합니다. 이러한 전략을 평가하는 핵심 지표는장기 표면 해시율 $\tilde{q}$입니다. 이는 시간이 지남에 따라 공식 블록체인에서 공격자가 기여한 블록의 비율을 나타냅니다.

기존 분석은 복잡한 마르코프 체인 또는 마팅게일 기법에 의존했습니다. 본 논문은 다이크 단어와 카탈란 수를 사용한간결한 조합론적 증명을 제안하여, 유도 과정을 더 이해하기 쉽고 우아하게 만듭니다.

2. 공격 주기와 Dyck 단어

하나의 공격 주기는 각 블록이 이기적 채굴자(S) 또는 정직한 채굴자(H)에 의해 채굴되는 일련의 사건으로 모델링될 수 있습니다.

2.1. 시퀀스 표현

예시: 시퀀스 SSSHSHH 는 이기적 채굴자가 세 개의 블록을 채굴한 후, 정직한 채굴자가 하나를 채굴하고, 이어서 이기적 채굴자가 하나를 채굴한 다음, 마지막으로 정직한 채굴자가 두 개를 채굴함을 나타냅니다. 이기적 채굴자의 리드가 줄어들 때 주기가 종료되며, 이는 그들이 자신의 포크를 공개하도록 유도합니다.

2.2. L의 분포

$L$을 각 공격 주기에 공식 블록체인에 추가되는 블록의 수라고 하자.

정리 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, 그리고 $n \geq 3$에 대해,

증명 개요: $n \geq 3$에 대해, 사건 ${L=n}$은 SS 로 시작하고 H 로 끝나는 수열에 대응하며, 중간 부분은 S→"(" 및 H→")" 매핑 후 길이가 $2(n-2)$인Dyck 단어를 형성한다.(균형 잡힌 괄호 문자열). 카탈란 수 $C_{n-2}$는 이러한 다이크 단어를 세는 데 사용됩니다.

3. 핵심 수학적 결과

3.1. L의 기대값

추론 2.3: $E[L] = 1 + \frac{p^2 q}{p - q}$.

이는 카탈란 수의 알려진 생성 함수 관계에서 비롯됩니다.

3.2. 표면 연산력 공식

$Z$를 공격자가 각 주기에 공식 체인에 추가하는 블록 수라고 하자. 장기 표면 해시율은 $\tilde{q} = E[Z] / E[L]$이다.

정리 2.4: 比特币的表面算力为： $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ 其中 $p$ 是诚实矿工的算力，$q$ 是攻击者的算力（$p+q=1$, $q<1/2$），$\gamma$ 是在分叉期间在攻击者区块上挖矿的诚实矿工比例。

4. 기술 분석과 프레임워크

4.1. 수학적 프레임워크

핵심 혁신은 공격 시퀀스를Dyck 경로(균형 잡힌 괄호 문자열)에 매핑한 데 있습니다. 이를 통해 이기적 채굴이 성숙한 조합 수학과 연결되어, 이전에 확률 과정이 필요했던 확률 계산이 단순화됩니다.

핵심 공식: $n\geq3$에 대해, 확률 $P[L=n]$은 카탈란 수 $C_{n-2}$에 비례하며, 확률 가중치 $p$와 $q$로 스케일링됩니다: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. 분석 프레임워크 예시

L=4 사례 분석:

1. 시퀀스는 반드시 SS 로 시작하고 H 로 끝나야 한다.
2. 중간 두 위치는 길이 2의 Dyck 단어를 형성해야 하나? 잠시만, 자세히 보자: L=4의 경우, n=4이므로 n-2=2이다. 우리는 중간 부분이 길이 2*(2)=4 문자인 Dyck 단어가 필요한가? 정리는 n≥3일 때, P[L=n]이 w = SS X1...X_{2(n-2)} H 형태의 시퀀스에 대응한다고 명시한다. 여기서 X 부분은 길이 2(n-2)의 Dyck 단어를 형성한다. n=4일 때, 길이는 2*(4-2)=4이다. 따라서 중간 부분은 Dyck 단어를 형성하는 4개의 문자를 가진다. 예시: SS(SHSH)H? 매핑 S→(, H→). 중간 부분 "SHSH"는 "()()"가 되며, 이는 Dyck 단어이다. 확률 가중치는 p^{#S} q^{#H} = p^3 q^3? w=SS S H S H H에서 S와 H를 계산해 보자: S는 4번 나타나는가? 실제로: SS S H S H H: 위치: S,S,S,H,S,H,H. 즉, S 4개, H 3개이다. 따라서 p^4 q^3이다. 공식은 p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4를 제시한다. 차이가 있다. PDF에서는 "w에서 문자 'S'(또는 'H')의 수는 n(또는 n-1)이다. 따라서, 우리는 P[L=n] = p^{n-1} q^n C_{n-2}"를 얻는다고 한다. n=4의 경우, 즉 p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4이다. 이는 공식과 일치한다. 따라서 예시 시퀀스 SS S H S H H는 S 4개, H 3개, 즉 p^4 q^3을 가지며 p^3 q^4가 아니다. 그러므로 Dyck 단어 조건 하에서, SS S H S H H는 L=4의 유효한 시퀀스가 아닌가? 균형이 맞지 않을 수 있다. 매핑해 보자: S→(, H→). SS S H S H H는 ((( ) ( ) )가 된다. 이는 불균형이다(열린 괄호 3개, 닫힌 괄호 2개). 따라서, 실제로 유효한 시퀀스는 S의 총수가 n이고 H의 총수가 n-1이며, 중간 부분이 Dyck 단어인 것들이다. Dyck 조건은 균형을 강제하여 특정한 계수로 이어진다. 따라서, 이 프레임워크는 유효한 공격 경로를 우아하게 포착한다.

이 프레임워크는 마르코프 체인 시뮬레이션 없이도 체계적인 열거와 확률 계산을 가능하게 한다.

5. 결과 및 영향

推导出的 $\tilde{q}_B$ 公式量化了自私挖矿的盈利阈值。例如，当 $\gamma=0$ 时，攻击者需要 $q > \approx 0.25$ 才能盈利，低于朴素的 $q>0.5$ 假设。这突显了一个关键协议漏洞。

차트 설명: 不同 $\gamma$ 值下 $\tilde{q}_B$ 与 $q$ 的关系图将显示：1) 当 $q$ 高于某个阈值时，$\tilde{q}_B > q$，表明有利可图。2) 更高的 $\gamma$（攻击者连接性更好）会降低盈利阈值并增加表面算力收益。

6. 업계 애널리스트 관점

핵심 통찰: 본 논문의 우아함은 복잡한 상태 기반 공격을 명확한 조합 모델로 단순화했다는 점에 있습니다. 이는 이기적 채굴의 수익성이 단순한 원시 해시율뿐만 아니라, 공격 시퀀스와 표준 조합 객체(Dyck 단어) 사이의구조적 결합이것은 단순한 수학적 기교가 아닙니다. 이는 비트코인 프로토콜의 취약점이 본질적으로형식 언어 문제——그 안전성은 블록 경쟁에서 특정 문자열 패턴의 확률 분포에 달려 있습니다.

논리적 흐름: 저자는 먼저 공격 주기를 문자열(S/H 시퀀스)로 프레이밍합니다. 핵심 단계는 성공적인 공격(공격자의 모든 블록이 수용됨)이 본질적으로 특정 시작/종결 기호로 둘러싸인 Dyck 단어에 해당하는 문자열이라는 점을 인식하는 것입니다. 이를 통해 그들은 마르코프 체인의 평형 방정식을 풀 필요 없이, 카탈란 조합론의 강력한 도구를 직접 활용하여 계수와 확률 생성을 수행할 수 있었습니다. 최종 공식은 L의 기대값(카탈란 생성 함수를 통해)과 Z의 기대값(L=1,2 등의 경계 사례를 고려)을 연결하여 유도되었습니다.

장점과 부족:
장점: 증명이 매우 간결하고 이해하기 쉽습니다. 이는 이기적 채굴 수익 공식의 신비를 벗겨냅니다. Dyck 단어와의 연관성은 형식 언어 이론을 사용하여 다른 블록체인 공격(예: 균형 공격, 이클립스 공격)을 분석하는 새로운 방법에 영감을 줄 수 있습니다. 이는 학제 간 접근법(암호학 + 조합론)의 가치를 강화합니다.
부족한 점: 이 모델은 정적이고 지속적이며 일정한 연산 능력 q를 가진 공격자를 가정합니다. 동적 적응, 채굴자의 진입/퇴장, 또는 다수의 이기적 채굴자(잠재적 과점 문제)의 영향을 포착하지 못합니다. $\gamma$ 매개변수는 지나치게 단순화되었습니다; 현실 세계의 네트워크 토폴로지와 전파 지연은 더욱 복잡합니다. 후속 연구(예: Gervais et al., Financial Crypto 2016의 "Optimal Selfish Mining Strategies in Bitcoin")에서 지적했듯이, 원래의 이기적 채굴 전략이 항상 최적은 아닙니다; 더 적응적인 전략이 존재합니다. 본 논문의 기여는 기초적인 것이지, 완전한 것은 아닙니다.

실행 가능한 통찰:

1. 프로토콜 설계자를 위해: 근본 원인은 '선견' 규칙과 느린 블록 전파에 있습니다. Gervais의 '신선도 우선' 또는 Decker와 Wattenhofer의 '컴팩트 블록 릴레이'(Bitcoin Core에 이미 배포됨)와 같은 솔루션은 $\gamma$와 전파 차이를 줄이는 것을 목표로 합니다. 본 논문의 공식은 이러한 수정 사항을 테스트할 수 있는 정량적 지표를 제공합니다.
2. 채굴 풀을 위해: 임계값 계산($q$ ~0.25)은 경계선입니다. 이 규모에 근접한 채굴 풀은 심사 대상이 되어야 합니다. 분산화는 이념적일 뿐만 아니라; $\tilde{q}$ 공식에서의 보안 매개변수이기도 합니다.
3. 분석가를 위해: Dyck 단어 매핑은 강력한 템플릿입니다. 참가자의 행동이 정규 문맥 자유 언어 등 형식 언어 클래스로 분석 가능한 시퀀스를 생성하는 다른 합의 메커니즘을 찾아보십시오. 명확한 투표 시퀀스를 갖는 지분 증명 시스템은 유사한 분석에 적합할 수 있습니다.

요점: 블록체인 보안은 점차 암호학자뿐만 아니라 응용 수학자와 언어학자의 영역이 되어가고 있습니다. 본 논문은 이러한 변화의 전형적인 예입니다.

7. 미래 적용 및 방향

1. 공격 모델 확장: Dyck 단어 프레임워크는 다음을 분석하도록 조정될 수 있습니다.고집 채굴或꼬리 채굴등변형체, 여기서 공격자의 배포 전략이 다릅니다.

2. 기타 합의 프로토콜: 지분 증명(예: 이더리움의 Casper)이나 방향성 비순환 그래프 기반 프로토콜(예: IOTA, Avalanche)에 유사한 조합 방법을 적용하면, 보류 공격에 대한 복원력에 대한 새로운 통찰력을 얻을 수 있을 것입니다.

3. 자동화된 보안 검증: 합의 프로토콜의 규칙을 형식 문법으로 자동 변환하고, 여기서 발견된 Dyck 구조와 유사한 "수익성 있는 공격 문법"이 존재하는지 확인하는 도구를 개발할 수 있습니다.

4. 네트워크 동역학 통합: 향후 연구에서는 단순한 $\gamma$ 매개변수를 넘어서, 보다 현실적인 네트워크 모델(예: 전염병 모델을 사용한 블록 전파)을 조합 확률 가중치에 통합할 수 있습니다.

8. 참고문헌

1. Eyal, I., & Sirer, E. G. (2014). Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (pp. 436-454). Springer.
2. Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
3. Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.
4. Grunspan, C., & Pérez-Marco, R. (2018). On profitability of selfish mining. arXiv preprint arXiv:1805.08281.
5. Gervais, A., Karame, G. O., Wüst, K., Glykantzis, V., Ritzdorf, H., & Capkun, S. (2016). On the security and performance of proof of work blockchains. In 2016 ACM SIGSAC 컴퓨터 및 통신 보안 컨퍼런스 논문집 (pp. 3-16).
6. Bitcoin Wiki. Difficulty. https://en.bitcoin.it/wiki/Difficulty.
7. Decker, C., & Wattenhofer, R. (2013). Information propagation in the Bitcoin network. In IEEE P2P 2013 논문집 (pp. 1-10). IEEE.