IOTA 블로그의 The Tangle: an illustrated introduction Part 3: Cumulative weights and weighted random walks의 번역본입니다.

Part 1: Tangle에 대한 소개
Part 2: 트랜잭션 레이트, 처리 지연 시간, 랜덤 진행

나머지 글들도 차례차례 진행할 예정입니다.

Tangle: 그림과 함께 하는 소개

Part 3: 누적 가중치와 가중치 있는 랜덤 진행

지난주에 우리는 가중치 없는 랜덤 진행에 대해 배웠고, 오늘 우리는 조금 더 고급의 그 사촌에 대해 배울 겁니다: 가중치 있는 랜덤 진행

학습 의욕을 갖고 시작해봅시다. 우리의 팁 선택 알고리듬이 하길 바라는 것 중 하나는 느려터진(lazy) 팁을 피하는 것입니다. 느려터진 팁은 최근 것보다는 오래된 트랜잭션들을 승인하는 팁입니다. 이는 tangle을 가장 최신 상태로 만드는 것에 신경쓰지 않고, 오래된 자료에 의존해서 그 트랜잭션들을 브로드캐스트만 하기때문에 느려 터졌습니다. 이는 새로운 트랜잭션들이 확정되지 못할 때까지 네트워크에 도움을 주지 않습니다.

위의 예에서 트랜잭션 14는 매우 오래된 트랜잭션들을 승인하는 느려터진 팁입니다. 우리가 유니폼 랜덤 팁 선택 알고리듬을 사용하면 트랜잭션 14는 그냥 다른 것들처럼 승인하게 되어 모두 처벌받지 않고 있게 됩니다. 가중치 없는 진행을 사용하면 이 좋지 않은 동작은 심지어 권장됩니다. 적어도 이 특정 예제에서는요.

이 문제를 어떻게 해결할 수 있을까요? 우리가 할 수 있는 한가지는 참여자들에게 최근 트랜잭션만 승인하도록 강제하는 겁니다만, 분권화(decentralization)라는 아이디어에 위배될 겁니다. 트랜잭션들은 원하는 누구든 승인할 수 있습니다. 우리는 또한 각 트랜잭션이 들어올 때 정확히 알리는 신뢰성 있는 방법을 갖지 못하므로 룰 같은 걸 강제할 수 없습니다. 우리의 해결책은 우리의 시스템을 그런 동작에 반하는 빌트인된 인센티브를 구성해서 느려터진 팁이 누구도 승인하지 못 할만하게 하는 겁니다.

우리의 전략은 우리의 랜덤 진행에 편차(bias)를 주어서 느려터진 팁을 고르는 것을 더 적게 하는 겁니다. 우리는 누적 가중치(cumulative weight)라는 용어로 트랜잭션이 얼마나 중요한지를 나타낼 겁니다. 가벼운(light) 것보다는 무거운(heavy) 트랜잭션을 더 향해 걷도록 할 겁니다. 누적 가중치의 정의는 매우 간단합니다: 우리는 한 트랜잭션이 얼마나 많은 승인자를 가지는지를 세어서 하나를 더합니다. 우리는 직접 승인자와 간접 승인자 모두를 셉니다. 아래의 예에서 트랜잭션 3은 4개의 트랜잭션을 승인했기 때문에 (직접적으로 5; 간접적으로 7, 8, 그리고 10) 5의 누적 가중치를 갖습니다.

왜 이것이 작동할까요? 다른 느려터진 팁 상황을 봅시다. 아래 예에서 트랜잭션 16은 느려터진 팁입니다. 16이 승인되려면 랜덤 진행자는 트랜잭션 7에 닿아야만 하고, 트랜잭션 9를 피해 트랜잭션 16을 골라야 합니다. 그러나 이 상황은 트랜잭션 16이 1의 누적 가중치를 갖고, 트랜잭션 9가 누적 가중치 7을 갖기 때문에 벌어지지 않습니다! 이는 느려터진 동작을 피하는 효과적인 방법입니다.

이 시점에서 우리는 이렇게 물을 수 있습니다: 모두 랜덤성이 필요한가? 우리는 각 교차점에서 가장 무거운(the heaviest) 트랜잭션을 고르는, 확률이 관여하지 않는 특별 가중치의 랜덤 진행(super-weighted random walk)을 만들 수 있습니다. 그럼 이렇게 될 겁니다:

특별 가중치 진행: 우리는 언제나 가장 무거운 트랜잭션을 향해 간다.

회색 사각형들은 승인자가 없는 팁입니다. 다이어그램의 오른쪽 끝에 있는 팁들은 보통 팁들인데 반해, 시간축에 회색 사각형이 너무 많이 퍼져 있어 보이는 것은 문제입니다. 이들 팁들은 left behind하고 절대 승인되지 않는 트랜잭션들입니다. 이게 우리의 진행에 편차를 너무 많이 주었을 때의 단점입니다: 특정 시점에 우리가 가장 무거운 트랜잭션들만 고르도록 구성하면 높은 비율의 팁들이 절대 승인되지 않을 겁니다. 우리는 승인된 트랜잭션의 중앙 복도와, 측면 상의 잊혀진 팁들로 남겨질겁니다.

우리는 주어진 교차로에서 어떤 특정 승인자를 향해 어떻게 걸을만 하게 할 지를 정의할 방법이 필요합니다. 우리가 더 무거운 트랜잭션으로 어떤 편차를 주는 한, 그리고 얼마나 이 편차를 강하게 할 지를 정하는 파라미터를
가지는 한 우리가 고르는 딱 맞는 수식은 중요하지 않습니다. 이것은 트랜잭션의 누적 가중치가 얼마나 중요한지를 설정하는 우리의 새로운 파라미터 α를 소개합니다. 그 정확한 정의는 백서에서 찾을 수 있고, 원하신다면 이후에 이에 대해 더 자세한 사항에 대한 포스팅을 할 수도 있습니다.

가중치 있는 랜덤 진행: 각 파란색 트랜잭션은 그 누적 가중치와 다음 스텝의 진행에서 선택될 확률을 보여준다.

우리가 α를 0으로 설정하면, 우리는 가중치 없는 진행으로 돌아가게 됩니다. 우리가 α를 매우 높게 설정하면, 우리는 특별 가중치의 진행을 얻습니다. 그 사이에서 우리는 느려터진 동작을 응징하고 너무 많은 팁을 남기지 않는 것 사이의 좋은 균형을 찾을 수 있습니다. IOTA에서 α의 이상적인 값을 결정하는 것은 중요한 연구 주제입니다.

랜덤 진행의 각 스텝의 확률을 결정하기 위한 규칙을 설정하는 방법은 마르코프 체인 몬테 카를로(Markov Chain Monte Carlo) 테크닉 또는 MCMC라고 부릅니다. 마르코프 체인에서 각 스텝은 이전 것과는 상관없고 미리 결정된 룰을 따릅니다.

항상 그랬던 것처럼, 우리는 이 새로운 아이디어를 보여주기 위한 시뮬레이션이 있습니다. 우리는 α와 λ의 값들을 바꾸면서 여러분이 만들 수 있는 여러 종류의 tangle을
돌려보기를 권합니다. 다음주에 우리는 트랜잭션 A가 트랜잭션 B를 승인한다고 하는 것과 한 트랜잭션이 확인된 것으로 보일 때를 정하는 것이 어떤 의미를 가지는지에 대해 더 자세한 사항으로 들어갈 겁니다.

Part 1: Tangle에 대한 소개
Part 2: 트랜잭션 레이트, 처리 지연 시간, 랜덤 진행
Part 4: 승인자, 잔고, 이중 지불