Linear님의 정보보호 공부 블로그

https://www.youtube.com/watch?v=nd9W5TStxNo

위 링크로 들어가면 해당 강의를 보실 수 있습니다. 

본문 내용은 위의 강의를 들으면서 저 스스로 정리한 공부 노트입니다.

4. Attack Scenarios

○ 결국 Cumulative Weight로 신뢰를 평가하기 때문에 공격자는 기존 네트워크 보다 빠른 속도로 'Cumulative Weight'를 축적하고자 함

1. 공격자가 판매자에게 물건 값을 지불하는 거래를 발행한다. 이 때 판매자는 이 거래의 Cumulative Weight가 일정 값 이상에 도달하면 물건을 공격자에게 전달한다.

2. 공격자는 Double-spending 거래를 발행한다.

3. 공격자는 자신의 Computing power를 이용하여 이중 지불된 거래를 승인하는 많은 개수의 작은 거래를 생성한다. (이 때 원래 정직한 거래는 승인하지 않는다. 두 거래 사이에 Conflict가 생기기 때문에)

4. 많은 수의 작은 거래 대신에 Weight가 매우 큰 거래를 발행하는 방법도 가능(Site 자체의 Weight가 무거움, 이것 때문에 상한 Weight를 둔다.)

5. 공격자는 이중 지불된 거래를 포함하는 Subtangle이 원거래의 Subtangle보다 빠르게 Cumulative Weight를 축적하여 원거래를 포함하는 Subtangle이 버려지기를 원함.

○ In the "ideal" situation of this mathematical model, this attack always succeeds 

// 여기선 Weight가 모두 1로 동일하다는 가정을 사용하지 않고 Weight는 3^n으로 생각한다.

// Exponential Distribution : Nonce를 찾기 시작한 시점과 Nonce를 찾은 시점의 간격이 Exponential Distribution을 따른다고 가정한다. 10시간이 될수도 있고 100시간이 될수도 있는데 일반적으로 이렇게 Parameter가 주어지면 일반적으로 이것의 역수가 된다. 비트코인으 POW도 Computing Power가 클수록 Nonce를 빨리찾는 것과 비슷한 개념이다. Tip 발생 횟수는 Poisson이고 간격이 Exponential을 따른다. 여기서는 가 컴퓨팅 파워를 의미하기 때문에 거래의 Weight를 작게 만들수록, 컴퓨팅 파워가 클수록 W는 줄어든다.

- 판매자의 원거래의 Cumulative Weight이 에 도달하면 거래를 수행하며, 이 때 도달하는 시간은 

- : 정당한 노드로부터 단위시간 당 발행되는 거래 개수

- : 일반적인 거래의 평균적인 weight

- 안에, 첫 번째 공격이 성공할 확률, => 결국 3^n0의 Weight를 가지는 Tip을 생성하는데 까지의 걸리는 시간이 t0보다 작기를 원함

----------------------------------------------------------------------------------------------------------------------------------------------------

<수학적 풀이>

가 되는데 이를 가지고 대입하면 다음과 같다.

----------------------------------------------------------------------------------------------------------------------------------------------------

- 첫 번째 공격이 실패하더라도, 원거래가 포함된 가지의 총 weight이 이중 거래의 weight인 보다 작기를 바라며 확률이 존재,

// t0 이후에 어떤 특정한 시점에서 원거래보다 큰 Weight의 거래를 만들면 된다.

○ The situation where the maximum own weight is capped at a value of 1,

// 따라서 Weight의 제한을 두지 않으면 공격의 위험이 있기 때문에 Weight를 최대 1로 가정한다. 

- 공격자는 이중 거래를 승인하는 많은 수의 nonsense 거래를 발행할 것

// 이 때에는 원거래보다 더 많은 Tip들을 붙이면 Cumulative Weight가 더 커지기 때문에 공격이 된다.

- 이parameter 를 가지는 exponential 변수일 때, 는 parameter 1을 가지는 exponential 변수이며 

에 대해 다음을 만족,

// t0까지 원거래의 Cumulative Weight (w0) 보다 이중거래의 계산속도가 더 빠르다고 가정을 한다.

- 이중거래가 시간 에서 원거래보다 큰 Cumulative weight 를 가질 확률은

// w0개의 Gk의 합은 w0개의 거래를 발행하는 것 까지의 걸리는 시간 (weight가 1이기 때문), m은 생각하지 않아도 된다고 설명해주신다. 각 거래를 만드는 시간 이 변수 G1, G2 ... 이 되는데 이 시간을 전부 합쳐야 한다. (Attacker가 1명이라고 가정하는 듯)

// 원거래가 더 먼저 w0까지 도달해야 하기 때문에 다음과 같이 확률을 계산한다.

- 시간 에서 이중거래가 원거래보다 큰 Cumulative weight를 가질 확률은

// 위의 식에서 t0보다 이후의 시간인 t가 되었을 때 w0보다 lambda t 만큼의 Weight가 더 증가하기 때문에 다음과 같은 식이 나온다.

- :  adaptation period의 cumulative weight의 성장 속도는 보다 느리다 라는 가정을 한다. (당연한 가정)

- 즉, 이중 지불 공격이 성공할 확률은

- 일때 확률의 상한은 0.29 이며, 일 때, 확률의 상한은 0.00001135 이다.

- 즉, 시스템의 안전을 위해서는 이어야 하며, 차이가 크게 유지될수록 이중 지불 공격이 성공할 확률이 낮아진다. 그렇기 때문에 추가적인 안전장치를 필요로 함

- Conflict 문제 해결을 위한 알고리즘 제안: "tip selection algorithm"

○ A Parasite Chain Attack

// 기생하는 체인을 만드는 것. 붉은 색으로 찍혀있는 부분이 Double-spending이다. 발행을 하고 Cumulative weight를 쌇기 위해 Tip들을 이어서 붙임 중간의 Tip들은 main tangle을 참조하면 안된다. 참조하면 Conflict가 일어나기 때문이다. 어느정도 Weight가 쌓이면 한번에 여기있는 팁들보다 더 많은 팁들을 발행한다. 이렇게 되면 Random하게 팁을 선택할 때 이 Parasite Chain의 Tip이 선택될 확률이 증가하기 때문에 이 Parasite Chain이 Main tangle이 된다.

○ A New Tip Selection Algorithm

- Main tangle이 Attacker 보다 Cumulative weight의 증가속도가 빠르다는 사실을 이용하여 Tip selection을 위한 MCMC Algorithm 제안

1. [W, 2W] 사이의 모든 sites를 고려
// Tip Selection Algorithm을 위해서는 Full Node를 알아야 한다.

2. N개의 독립적인 particle에 대해 tip을 향해서 Independent discrete-time random walks를 수행

3. 너무 빠른 속도로 tip에 도달하는 경우 lazy tip일 가능성이 존재하므로 제외하고, tip에 도달하는 첫 2개의 tip을 승인

4. Transition Probability: 는 x의 Cumulative weight을 의미하며, y가 x를 승인하는 경우 transition probability는 다음과 같이 정의함

// Independent discrete-time random walks를 수행할 때 둘의 Cumulative Weight의 차이가 더 작은쪽에 더 큰 확률을 준다. 아래의 그림을 보면 13에서 시작해서 10으로도 갈 수 있고 11로도 갈 수 있지만 11이 Cumulative Weight의 차이가 더 작기 때문에 11로 진행한다. 이를 위의 식으로 정의한다. 위의 식에서 값에 의해 얼만큼 확률을 더 크게 줄 것인지 조절할 수 있다. N개의 particle에 대해 모두 이 Independent discrete-time random walks를 수행한다. 이 후 처음으로 1등으로 도달한 tip을 정당한 tip으로 간주한다. 하지만 lazy tip같은 경우 바로 갈 수 있기 때문에 너무 빨리 도착한 것은 제외한다.

// 이 알고리즘이 good tip을 잘 선택한다는 것을 보이기 위해선 lazy tip이나 bad tip들을 선택할 확률이 줄어든다는 것을 보이면 된다. 

<Independent discrete-time random walks를 수행하는 예>

○ Why the nodes would follow this algorithm.

// 많은 node들이 Reference 방식을 따른다고 하면 결국 이 Selfish node도 Reference 방식을 따르는 것이 좋다. 간단히 말해서 Tip Selection Algorithm은 결국 Tip 선택하는 것에 lazy tip쪽은 확률이 작고 good tip쪽은 확률이 크고 Parasite chain쪽은 확률이 작은 Distribution을 만드는 것이다.

- A past snapshot of the tangle

- Defines a probability distribution on the set of tips

- Generating too much competition between selfish nodes for subsequent approval

- To verify the same "bad" tips would remain small

○ Inherently different from other decentralized constructs, such as Bitcoin

// 그 분포값을 알 경우 왼쪽의 큰 Tip들이 Distribution의 값이 크다고 하면 Selfish한 노드들이 본인이 Approve될 확률을 높이기 위해 이 Tip들을 무조건적으로 선택한다면 또 다른 Selfish한 노드들이 이 Tip을 무조건적으로 또 선택하면 이 Selfish한 노드들 끼리 경쟁이 발생해서 뒤에 들어올 node들에게 Approve될 확률이 줄어들기 때문에 이 Selfish한 노드들도 결국 Random하게 Reference를 따라 Select하는 것이 낫다.

○ Splitting Attack

// Sub tangle이 2개가 되기를 바라는 것, 이 2개를 계속 유지하면서 Double-spending attack을 시도하는 공격이다.

- 2개의 branch가 동시에 자라도록 유도하여 각 branch에서 double-spending attack을 시도하는 것이 가능

- "Sharp-threshold": Too hard to maintain the balance between the two branches

// 이 경우에 막기위한 방법이 Sharp-threshold이다.

-- 예를 들어, 한 쪽 branch는 총 weight가 537이고 다른 한 쪽은 528인 경우, 각 branch를 선택할 확률이 1/2 이지만 만약 1/2보다 큰 확률로 537 weight의 branch를 선택하도록 하여 공격자가 두 branch간의 균형을 유지하지 못하도록 한다.

// 이전 식에서를 조절하면 확률을 크게주는 것이 가능하다. 이 경우 Attacker들이 균형을 맞춰주려고 한다면 굉장히 많은 Computing power를 사용해야 한다.

-- MCMC algorithm에 rapidly decaying function을 사용한다.

- Network Synchronization issue

-- 한 번에 많은 수의 거래 발행할 수 있는 노드가 존재하면 공격자가 균형을 유지하는데 어려움

-- 최근 발행된 거래의 confirmation 신뢰도가 낮으므로, branch가 더 이상 자라지 않고, 정직한 노드는 분기 이전의 거래를 confirmation하는 방법으로 방어가 가능함

- MCMC depending on both 

-- Tip의 Cumulative weight에 의해 결정함으로써 더 작은 branch로 확장 되는 것을 방지함

5. Resistance to quantum computations

○ Quantum computation에 의해서 hashing power의 향상

- Bitcoin의 경우, 기존 컴퓨터 사용시 hash값을 찾기 위해 평균적으로 개의 nonce를 체크해야 했다면 Quantum computation을 

사용하면 개만 체크하면 됨

- Hashing power 향상에 따른 난이도 조절이 요구됨

○ "Large weight" attack에 효율성 부여

- Weight의 상한선을 주기 때문에 hashing power는 에서 로 향상됨

- 거래를 발행하기 위한 전체 사용 시간 중에 hashing 과정이 차지하는 비율이 높지 않기 때문에 quantum computation으로 인한 차이가 크게 없음

https://www.youtube.com/watch?v=nd9W5TStxNo

위 링크로 들어가면 해당 강의를 보실 수 있습니다. 

본문 내용은 위의 강의를 들으면서 저 스스로 정리한 공부 노트입니다.

3. 시스템의 안정성

○ 시스템의 안정성을 tip의 개수로 평가

- 승인되지 않은 거래가 증가하면 시스템의 불안정을 야기

○ L(t)는 시간 t에서 시스템 내에 존재하는 총 tip의 개수를 의미하며 Stable 한 상태이길 원한다.

- Positive recurrent assumption:

어떤 시점을 잡아도 그 때의 tip의 개수는 몇개가 될 확률이 각각 존재한다.

○ 확률적 분석을 위해 몇 가지 가정을 추가한다.

- The process of incoming transactions can be modeled by a Poisson process with the rate parameter .

 (가장 중요한 가정, 새롭게 발생되는 프로세스를 Poisson Process로 가정한다. 단위시간당 발생하는 사건의 횟수의 평균 값을 라 한다. 단위시간당 개의 거래가 평균적으로 발생한다고 가정)

- All devices has approximately the same computing power. (Weight =1로 가정한 것과 연관)

- Transaction이 't' 에 발행되면 't + h' 이후에 tangle에서 관측 가능 (평균적으로 거래 발생시간 t보다 h시간 이후에 관측이 됨)

- Tip의 개수는 roughly stationary in time(시간에 대해서 Tip의 개수는 대략 고정되어 있다)

- 가정의 현실성 여부 논의 가능

○  다음과 같은 가정들을 받아들일 때, 그럼 안정적인 시스템의 'Stable' 한 tip의 개수는 몇 개?

- 임의의 2개의 tip을 선택하는 경우, 

- 임의의 k개의 tip을 선택하는

---------------------------------------------------------------------------------------------------------------------------------------------------------

<수학적 풀이>

○ hidden tip

- 시간 t에서는 tip처럼 보이지만 t-h이후에 다른 새로운 tip들이 Approve 하여서 t+h 이후에는 tip이 아닌 것으로 단위시간 동안 개가 생기는데만큼의 시간이 지났으므로 으로 계산한다.

○ revealed tip

     - ,진짜 tip

따라서 시간 t에서 우리가 보는 tip의 수 는

으로 계산할 수 있다.

- 이항분포

X : n번 독립시행 하였을 때 event 발생 횟수

=> 내가 원하는 이벤트가 r번 일어날 확률

이 기대값을 구하면 (n : 수행 횟수, p : 해당 이벤트가 발생할 확률)

Stable하기 위해서는 Tip을 Random하게 2번 뽑을 때 revealed tip에서 1번 고르는 쪽이 Stable 하게 할 수 있다. (Purely random 전략)따라서 

이 되어야 한다. 1이 되는 이유는 기존의 revealed tip 1개를 Approve 하고 자기 자신이 Tip으로 대체되야 하기 때문이다. 2면 revealed tip에서 2번 선택하기 때문에 Tip은 점점 줄어들게 된다. 따라서 

가 되고 따라서 

가 된다.

(이는 아직 Tip Selection과는 관련이 없다.)

---------------------------------------------------------------------------------------------------------------------------------------------------------

○ "purely random" 전략은 일반적으로 비효율적

- A "lazy" node: 특정 거래만 반복해서 승인하여 새로운 거래 승인에 공헌하지 않음

- A "malicious" entity: 악의적인 사용자가 많은 수의 tip을 생성하여 정직한 사용자의 tip이 상대적으로 선택될 확률 감소

- 이러한 상황을 다루기 위해 더 "좋은" tip을 선택하기 위한 알고리즘이 필요하다 : "tip selection algorithm"

○ Low load regime

- Tip의 개수가 적고, 자주 1개인 경우

- network latency가 낮고, device의 계산이 바른 경우

- 일반적으로 총 거래가 적을 경우 이지만, 거래가 적당한 규모로 증가하더라도 가능함

- Tip의 개수를 의도적으로 늘리고자 하는 공격자가 없다고 가정 <- Critical !! 따라서 일반적으로 다음의 High load regime 상황을 주로 고려한다.

○ High load regime

- Tip의 개수가 많음

- 총 거래량이 매우 많은 경우

- Computational delays together with network latency

Figure 3: Low load (top) and high load (bottom) regimes of incoming transaction flow. White squares represent verified sites, while gray squares represent tips.

3.1 Cumulative weight(= 거래의 신뢰도) 증가 속도 평가

○ In the Low load regime

- 새롭게 발행되는 모든 거래들에 의해 indirectly approved 되기 때문에 단위시간 당 의 속도로 Cumulative weight가 증가함

○ In the High load regime

- 발행된지 오래된 거래는 low load regime와 같으나, tangle에 최근 추가된 거래의 경우 adaptation period 휴에 low regime과 같은 의 속도에 도달하게 됨

- In the "adaptation period"

-- H(t) is the expected cumulative weight at time t

(시간 t에서 특정 거래의 cumulative weight 값)

-- K(t) is the expected number of tips that approved the transaction at time t

(시간 t에서 특정 거래를 승인해준 tip의 개수)

---------------------------------------------------------------------------------------------------------------------------------------------------------

<수학적 풀이>

H(t)의 도함수를 먼저 구한다.

Stable한 상태의 t 시점에서 총 Tip 개수는 개가 있다고 앞서 설명하였다.

이중 K(t - h)개의 tip들은 이전에 나를 Approve (Direct 또는 Indirect하게) 해준 Tip들이다. 새로운 Tip들이 이 Tip들이 

이 K(t - h)개의 Tip들을 선택해야 나의 Cumulative weight가 증가할 것이다.

따라서 2가지로 볼 수 있는데 Tip을 선택할 때 이 K(t-h)개를 선택하거나 아니면 다른 나머지를 선택하는 것이다.

이 상황에서는 확률의 여집합을 사용해야 한다.

총 개의 Tip중 Tip을 2번 선택할 때 2번 다 K(t-h)가 아닌 나머지를 선택할 확률은

이다. 이를 계산하여 정리하면 

가 된다. 따라서 아래의 함수에 새로 생기는 Tip이 나를 Approve한 Tip을 선택하는 확률값이 다음과 같이 들어가고 

개의 tip들이 새로 생겼기 때문에 아래와 같은 식을 구할 수 있다.

이고 따라서

이다.

하지만 고려하지 않은 경우가 Revealed tip과 Hidden tip을 고려하지 않았다. 이중에 반은 Revealed tip이고 반은 Hidden tip이다.

따라서 다음과 같은 상황을 고려해야 한다.

1. 나를 Approve해준 Tip이 줄어드는 상황 ( K(t)가 줄어듬 )

이 경우는 Revealed Tip만 2개 선택한 경우이다. 유효한 Tip을 2개 지우면서 Tip이 1개 생기기 때문이다. 

전체 Tip의 개수는 이고 이중에 나를 Approve해준 K(t-h)개를 선택하는데 이 K(t-h)개의 절반이 Revealed Tip이기 때문에 

이 경우의 확률은 다음과 같이 표현할 수 있다.

2. 팁이 1개 늘어나는 상황

이 경우는 Hidden tip만 2개 고르는 상황 또는 Hidden을 1개 선택하고 나를 Approve하지 않는 나머지 Tip들 중 1개를 선택하는 경우이다.

따라서 이 확률은 다음과 같이 표현할 수 있다.

여기서 뒤에 2를 곱해서 더 해준 것은 순서를 고려해서 무엇을 먼저 선택하는지  을 계산해준 것 때문이다.  

따라서 단위 시간동안의 팁의 개수의 Expectation은 다음과 같이 계산할 수 있다.

여기서 또 하나의 가정을 한다.

이 가정은 타당하다. 전체 Tip의 개수를 로 보았을 때 Adaptation Period이기 때문에 아직 나 자신은 Tip과 매우 가까이 있기 때문이다.

따라서 

이고 2개씩 Approve할 때 이기 때문에

가 되는데 이 식을 보면 자기 자신을 미분 하였는데 자기 자신이 다시 나왔다. 이런 함수를 Exponential Function이라 하는데 따라서

로 쓸 수 있다. 이제 적분상수 C를 찾아야 한다. 이 식을 미분하면

이고 따라서 C에 대해 전개하면

이고 

를 만족하는 함수를 LambertW-function 이라 하는데 따라서 결국 C는

가 된다. 그래서 이 식을 대입하면 다음과 같이 K(t)를 구할 수 있다.

또한  K(t-h)가 매우 작다고 가정하였기 때문에 다음과 같이 전개할 수 있다.

또 결국 미분했을때 Exponential 함수이기 때문에 H(t)는 Exponential 함수가 된다. 따라서 최종적으로

가 된다.

---------------------------------------------------------------------------------------------------------------------------------------------------------

-- 즉, cumulative weight는 "adaptation period"에서 기하급수적으로 증가하며 그 후에는 기울기가 인 선형함수 형태로 증가한다.

결국 Low load regime일 때는 Cumulative Weight가 Linear하게 증가한다.  High load regime일 때는 Tip에 가까운 Adaptation Period일 경우에는 Exponential 하게 증가하다가 이 Adaptation period가 끝나면 Linear하게 증가한다. (위와 같은 가정이 있을 경우) 

Adaptation Period는 비트코인의 6 confirmation 처럼 어느정도 시간이 있어야 안정화가 된다.

다음에는 몇가지 Attack Scenario를 보면서 공부를 할 예정이다.

2. 관련 용어 정의

○ 네트워크의 안정성 및 거래의 유효성을 표현하기 위한 용어 정의

- 거래의 weight는 노드가 거래를 발행하기 위하여 투자한 일의 총 량에 비례한다 :  으로 정의

-- Spam 같은 것 불가능 하도록, 엄청 짧은 시간에 특정 Weight 이상의 거래를 많이 생산하는 것은 불가능 (비트코인처럼 Hash puzzle을 풀어야 함)

- Cumulative Weight : 거래의 Weight + 이 거래를 승인한 모든 거래의 Weight의 합

- Tips : 아직 한 번도 승인되지 않은 거래

- Score : 거래의 Weight + 이 거래가 승인한 모든 거래의 Weight의 합

위 그림에서 X라는 새로운 transaction이 생겼을 때 A와 C 2개의 Tip을 Approve해주고 Tip이 됨 X의 Weight가 3이기 때문에 A와 C의 Cumulative Weight는 3씩 증가하였다.

- Height: genesis 까지 제일 긴 path

-- G has height 1 & D has height 3

- Depth: 임의의 tip까지 가장 긴 path

-- G has depth 4 & D has depth 2

○ Cumulative weight: 거래의 유효성을 나타내는 대표적인 척도

○ 각 거래의 weight가 모두 1 이라고 가정함

- Section 4의 일부분 제외