On the timestamps in the tangle 번역

On the timestamps in the tangle

Serguei Popov∗

August 6, 2017

Description of the problem and proposed algorithms(문제 및 제안 알고리즘에 대한 설명)

다음에서 우리는 고정 된 순간의 Tangle [1]을 고려한다; 즉, Tangle의 상태는 고정되어 있으므로 간단히 T로 나타냅니다. 일부 표기법 : x가 Tangle의 사이트 (트랜잭션)이면 A(x)는 x에 의해 승인 된 두 트랜잭션 집합을 나타냅니다.  우리는 만약 xj 모든 j = 1, ..., k에 대해 xj  ∈ A(xj−1)에서 x = x0, x1, ... , xk = y 일련의 사이트가 있는 경우 x는 y를 참조(간접적으로 승인)한다라고 말한다. x와 관련하여 "과거"와 "미래"에 대해 이렇게 쓰도록하겠습니다.

다시 말하면, 상기는 Tangle에 부분 순서 구조를 도입합니다. 또한 우리는 참조하거나 참조하지 않는 트랜잭션 집합을 Ind (x) = T / (P (x) ∪F (x))로 나타냅니다. (약어 사용됨). x ∈ Ind (x)를 정의하면된다.

다음으로 각 트랜잭션 x에 대해 타임 스탬프 t (x)가 있다고 가정합니다. 즉, 원칙적으로, t (x)는 트랜잭션이 Tangle에 부착 된 시간에 대응한다. 모든 x ∈ T에 대해 A (x) = {y1, y2} 인 t(x)> t (y1,2)가 필요하다. 즉, 트랜잭션은 "미래의" Timestamp 인 다른 트랜잭션을 승인 할 수 없습니다. 우리의 상정 된 가정은 대다수 (합리적인 의미에서) 대다수의 트랜잭션이 신뢰할 수있는 시계를 장착 한 정직한 노드에 의해 발행 된 것입니다. 

이제 타임 스탬프 t (x)를 가진 트랜잭션 x (전형적으로, 이미 Tangle의 "깊은 내부"입니다.) 를 생각해보십시오. 문제는 그것이 정직하고 악의적인 노드(또는, 어쩌면 정직한 노드에서 어떤 이유에 의해 시계가 오작동해서 발생할 수도 있습니다.)에 의해 발행되었는지 알지 못한다는 것입니다. 그러므로 t(x)가 x가 Tangle에 부착 된 실시간(심지어 대략적인) Tx인지 확실하지 않습니다. 우리의 목표는 Tx에 대한 신뢰 구간 [ax, bx]를 구성하는 것이다. 즉, 이벤트 Tx ∈ [ax, bx]가 높은 확률로 발생하도록 (확정적인) ax ≤ bx를 원한다.

다음에서는 이러한 구간을 구성하기위한 두 가지 절차를 고려합니다.

Procedure 1. β ∈ (0, 1/2)를 고정한 다음, 데이터 수집을 고려한다 (사실, 다중 집합)

(t (y) : y ∈ Ind (x)).    (1)

그런 다음 ax와 bx를 상기 데이터 수집의 β-와 (1-β) - 분계선으로 정의하십시오.  β = 0 (즉, 위의 데이터 수집에서 ax와 bx를 최소값과 최대 값으로 취하는 것)이 좋은 아이디어가 아닌 이유를 설명해야합니다. 그 이유는 악의적인 개체가 ax를 0(과거의 다른 거래를 승인하는 새로운 거래를 발행하고 작은 t- 값을 가짐)으로, bx(x를 참조하지 않고 매우 큰 t- 값을 갖는 새로운 트랜잭션을 발행함으로써)를 무한하게하여 절차를 망칠 수 있기 때문입니다. β가 0에서 멀어지면 "분열"거래가 중단됩니다.

원칙적으로 β를 증가시킴으로써 위에서 설명한 악성 행동에 대한 방어력을 강화합니다. 반면에 β가 1/2에 "too close" 하다면 결과는 "too random"할 것이다(x가 정직한 노드에 의해 발행 된 경우 라 할지라도, β가 1/2에 가까울 때, t (x) 자체가 신뢰 구간으로 갈 수 없다는 것을 관찰 할 수있다)). 현재로서는 β의 "최적"값이 무엇인지는 불분명합니다. 실제로, 네트워크에서 악의적 인 노드의 비율과 이러한 분석을 수행하는 방법에 대한 가정을 만들어야합니다. 어쨌든, 경험적으로 [0.2,0.3]의 β 값이 효과가있을 것입니다. 

위의 절차의 단점으로, 각 x에 대해 개별적으로 계산을 수행해야한다는 점에 유의하십시오 (일반적으로 x != y 일 때 Ind(x) != Ind(y)를 관찰하십시오). 이것은 Tangle이 매우 큰 경우를 대비하여 계산상의 차이를 야기 할 수 있습니다.  On the other hand, the outcome of the procedure is deterministic, provided of course that the nodes use the same β and see the same state of the tangle. 

이제는 계산이 더 쉽고 동시에 많은 트랜잭션에서 작동하는 또 다른 절차를 설명하겠습니다. 반면에, random1 결과를 생성합니다. 

Procedure 2. Tangle의 깊숙한 곳에서 시작하여 [1]의 4.1 절에 설명 된 Random Walk를 실행하고 x가 참조하는 마지막 트랜잭션의 타임 스탬프가되도록 ax를 취하고, bx는 x를 참조하는 첫 번째 트랜잭션의 타임 스탬프가됩니다. 

악의적인 노드가 고정된 트랜잭션의 타임 스탬프를 위조하려고 시도하면, 이 트랜잭션은 Random Walk에 의해 선택되지 않을 것임을 관찰하십시오. 실제로, 악의적인 노드가 "과거로 부터의" 타임 스탬프를 두는 경우(즉, t (x)는 x가 발행 된 실제 시간보다 훨씬 크다), 이는 [1]의 섹션 4.1의 "Lazy Tip" 사례에 해당합니다. 그러한 거래는 오랜 시간 동안 누군가에 의해 참조되지 않을 것이고, 다시 Random Walk가 결국 그것을 통과하지 않을 것입니다.

Conclusion

Tangle은 트랜잭션의 정확한 시간 순서를 설정하기에 부적합한(사실, 일반적으로 불가능한) 부분 순서 구조만 있는 그래프입니다. 모든 트랜잭션에 타임 스탬프가 있어도 이 모든 타임 스탬프가 정확하다는 것을 확신 할 수 없습니다(거래가 나타나는 실제 시간에 대해 네트워크를 속이는 일부 악의적인 노드 및/또는 잘못된 시계가 있는 일부 노드가 있을 수 있습니다). 그럼에도 불구하고 합당한 정확도로 타임 스탬프의 신뢰 간격을 결정할 수 있습니다. 위의 텍스트에서 우리는이를 수행하기위한 두 가지 알고리즘을 설명했습니다; 첫 번째 것은 계산적으로 더 복잡하지만 결정론적(deterministic) 결과를 산출합니다 (동일한 β를 사용하고 Tangle의 동일한 상태를 보는 두 개의 노드는 동일한 신뢰 구간을 얻을 것이다). 다른 알고리즘은 더 간단하고 동시에 여러 트랜잭션에 대한 타임 스탬프의 신뢰 간격을 결정하지만 임의의 결과를 생성합니다 (랜덤 워크가 실제로 선택한 경로에 따라 다름).

References

[1] S. Popov (2015) The tangle. https://iota.org/IOTA Whitepaper.pdf