180116 블록체인 공부 IOTA란 무엇인가? 를 보고 (4)

블록체인/IOTA

180116 블록체인 공부 IOTA란 무엇인가? 를 보고 (4)

KimLinear 2018. 1. 16. 21:30

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들을 선택할 확률이 줄어든다는 것을 보이면 된다.

// 위의 그림에서 lazy tips 부분을 예로 들면 Main tangle안에 있는 Transaction은 lazy과 또다른 Main tangle안의 Transaction에 의해 Approve가 되었을 것이다. 따라서 이 lazy tip이 Approve한 Main tangle안에 있는 Transaction의 Cumulative Weight는 결국 Main tangle 안에 Transaction들에 의해 결정되고 lazy tip의 Cumulative weight는 0이기 때문에 Cumulative weight의 차이가 크다. 따라서 lazy tip으로 진행할 확률은 줄어든다.

// Parasite chain의 경우에는 Attacker의 Computing Power가 전체 Main tangle의 Computing Power보다 작다고 가정하여서 Parasite Chain에서 Main tangle을 Approve한 부분을 놓고 보았을 때 Main tangle안의 Transaction에서 Parasite Chain의 Transaction의 Cumulative Weight는 결국 Attacker가 생성한 Transaction에 의해서밖에 Approve받지 못하므로 Main tangle의 Cumulative Weight와는 차이가 크다. 따라서 Parasite chain으로 진행할 확률이 줄어들게 된다.

// 하지만 IoT 환경에서 Full node를 전부 파악하고 이 Tip Selection Algorithm을 계산하는 것은 무리가 있다. 따라서 이 계산을 매번 할 수가 있을까라는 생각을 하게 된다. 이에 대한 정보는 해당 영상을 보면 light한 node는 Tip selection을 사용하지 않고 특정 node에 이 알고리즘 수행을 위임하여 Tip이 생성될 때마다 이 Tip Selection Algorithm을 매번 수행한다고 한다. 따라서 특정 node에 대한 신뢰문제가 발생한다고 한다.

○ 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으로 인한 차이가 크게 없음