180115 블록체인 공부 IOTA란 무엇인가? 를 보고 (3)
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
- 
따라서 시간 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 되기 때문에 단위시간 당
○ 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이 나를 Approve한 Tip을 선택하는 확률값이 다음과 같이 들어가고
이고 따라서
이다.
하지만 고려하지 않은 경우가 Revealed tip과 Hidden tip을 고려하지 않았다. 이중에 반은 Revealed tip이고 반은 Hidden tip이다.
따라서 다음과 같은 상황을 고려해야 한다.
1. 나를 Approve해준 Tip이 줄어드는 상황 ( K(t)가 줄어듬 )
이 경우는 Revealed Tip만 2개 선택한 경우이다. 유효한 Tip을 2개 지우면서 Tip이 1개 생기기 때문이다.
전체 Tip의 개수는
이 경우의 확률은 다음과 같이 표현할 수 있다.
2. 팁이 1개 늘어나는 상황
이 경우는 Hidden tip만 2개 고르는 상황 또는 Hidden을 1개 선택하고 나를 Approve하지 않는 나머지 Tip들 중 1개를 선택하는 경우이다.
따라서 이 확률은 다음과 같이 표현할 수 있다.
여기서 뒤에 2를 곱해서 더 해준 것은 순서를 고려해서 무엇을 먼저 선택하는지 
따라서 단위 시간동안의 팁의 개수의 Expectation은 다음과 같이 계산할 수 있다.
여기서 또 하나의 가정을 한다.
이 가정은 타당하다. 전체 Tip의 개수를
따라서
이고 2개씩 Approve할 때 
가 되는데 이 식을 보면 자기 자신을 미분 하였는데 자기 자신이 다시 나왔다. 이런 함수를 Exponential 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를 보면서 공부를 할 예정이다.