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

원문 출처:  https://medium.com/biilabs/in-depth-explanation-of-how-iota-making-a-transaction-bcdd9713b939

이 글은 IOTA에서 Transaction이 어떻게 생성되는지에 대한 설명을 담은 원문을 한글로 번역한 것 입니다. 오역이 있을 수 있으니 원문과 비교하여 읽으면 도움이 될 것 같습니다.

In depth explanation of how IOTA making a transaction

이 게시물은 IOTA가 트랜잭션에서 번들로, 해시에서 주소로, 개인 키에서 서명 메시지로 트랜잭션을 만드는 방법을 자세히 설명합니다. 이것은 IOTA가 한 주소에서 다른 주소로 거래를 제안하는 방법을 알기 위해 필요한 전부입니다.

0. Before We Start

이 두 가지 자료를 이미 읽었는지 확인하십시오. 당신에게 IOTA 거래의 기본 견해를 제공합니다.

1. 1. Bundles — IOTA Documentations (https://iota.readme.io/v1.2.0/docs/bundles)

1. 2. Making a Transaction — IOTA Documentations (https://iota.readme.io/v1.2.0/docs/making-a-transaction)

2. Making bundle

예를 들어 봅시다. A는 동일한 시드로부터 3 개의 주소를 가지며 몇개의 value를 가집니다.

Gather all transaction we need in bundle

- index 0: AAAAAAAA, balance: 50

- index 1: BBBBBBBB, balance: 70

- index 2: CCCCCCCC, balance: 20

A가 B의 주소 DDDDDDDD로 100i를 보낼 때, IOTA는 다음과 같이 할 것입니다 :

번들로 필요한 모든 거래를 모으기

B의 주소로 Output Transaction 준비 및 Bundle에 추가

Balance와 함께 A의 주소에서 Input Transaction 준비

Meta Transaction 슬롯을 사용하여 각각의 Input Transaction을 Bundle에 추가한다. 

메타 트랜잭션 슬롯 금액은 주소 보안 수준에 따라 다르며 주소의 기본 보안 수준은 2입니다. 즉, 트랜잭션 서명을 전달하는 데 하나의 추가 트랜잭션이 필요합니다.

번들의 잔액이 여전히 양수인 경우 사용되지 않은 출력 트랜잭션을 추가하여 소비되지 않은 값(Unspent value)을 이동합니다

Bundle finalized

 번들 Balance가 0인지 체크(입력 값 = 출력 값, Kirchhoff의 회선 법칙(Kirchhoff’s circuit laws)을 recall)

Generate bundle hash

- Kerl을 사용하여 transaction 유효성 검사 항목(address, value, obsolete tag, timestamp, current index, and last index)으로 흡수한다.

- Secure bundle hash 생성 여부를 확인하고, 그렇지 않으면 obsolete tag(폐기 태그)를 증가시키고 다시 생성한다. (https://github.com/iotaledger/iota.lib.py/issues/84)

- 모든 트랜잭션에 Bundle hash 및 초기화 서명 조각을 채워넣는다 

- transaction hash, transaction tips, signature fragment and nonce가 이 단계에서 채워있지 않음을 확인하고 bundle hash만 결정됩니다.

Bundle signing

- seed를 통해 키 생성기(key generator) 가져 오기

- 트랜잭션을 반복하고 만약 트랜잭션이 Output transaction이면 이 transaction을 signing하려고 시도할 것이다(만약 필요하면 meta transaction으로). 

- 주소 index 및 security level으로 키 생성을 통해 Address private key를 얻는다.

- address private key와 bundle hash를 사용하여 signature fragment(서명 조각)을 생성하고 트랜잭션의 signature fragment 부분을 채 운다.

- 만약 security level이 2인 경우 2개의 transaction에 사인을 해야 한다. (output transaction과 다음 meta transaction인 경우 1개)

이 단계가 끝나면, bundle hash 및 transaction signature를 역순으로 (마지막 index부터 0 index 까지) transaction trytes들의 리스트를 얻는다.

3. Get two tips for trunk and branch

이 글에서 나는 MCMC 알고리즘을 다루지 않을 것이며, 이것을 블랙 박스라고 생각한다. getTransactionsToApprove를 통해 IRI로부터 두 가지 팁을 얻을 수있다.

4. Proof of Work

마지막 단계에서는 번들의 각 트랜잭션에 trunk, branch 및 nonce (여기에서 작업 증명!)를 채워야한다.

번들 설명서에 언급된 바와 같이, 번들은 Tangle 안의 Atomic transfer(원자적 전송) 항목이다. 즉, 하나의 bundle 안에서 같은 팁들을 가지고 있어야 한다.

그런 다음 Bundle의 모든 트랜잭션을 마지막 인덱스부터 0 인덱스까지 trunk, branch hash, time stamp을 채우기 위해 이동하고 nonce값을 찾ㄱ고 transaction hash를 생성하기 위한 PoW를 수행하고 PoW 결과의 유효성을 검사한다.

마지막 인덱스의 트랜잭션 트렁크와 분기 해시는 우리가 얻는 이전 팁이 될 것이다. 다른 트랜잭션의 트렁크는 이전 트랜잭션의 해시이고 분기 해시는 팁의 트렁크 트랜잭션이다. 

모든 것이 제대로 되었으면 모든 필드가 채워진 전체 트랜잭션 trytes를 얻을 수 있습니다!

5. PoC code for Python with PyOTA

	# -*- coding: utf-8 -*-
	# This is a POC code to generate IOTA transaction and bundle
	#
	# Note: You will need to implement getTransactionsToApprove
	#
	import iota
	import pearldiver
	SEED = 'GENERATE_YORU_SELF'
	tag = iota.Tag('TESTINGPYTHON')
	pt = iota.ProposedTransaction(
	address=iota.Address('9TPHVCFLAZTZSDUWFBLCJOZICJKKPVDMAASWJZNFFBKRDDTEOUJHR9JVGTJNI9IYNVISZVXARWJFKUZWC'),
	value=90,
	tag=tag,
	message=iota.TryteString('HELLO')
	)
	pb = iota.ProposedBundle([pt])
	# pb.add_inputs([list])
	# pb._create_input_transaction(addy)
	addy = iota.Address('INDTKDAH9GGWDAJDWQLWUKCIHSYNEFQUGVHOYWLZRYPEZIZYQHQJNDLDPCLWMMO9UAEZUWPHMWZRLWGOB')
	addy.balance = 100
	addy.key_index = 2
	addy.security_level = 2
	inputs = [
	iota.ProposedTransaction(
	address=addy,
	tag=tag,
	value=-addy.balance
	)
	]
	for input in inputs:
	pb._transactions.append(input)
	for _ in range(addy.security_level - 1):
	pb._transactions.append(iota.ProposedTransaction(
	address=addy,
	tag=tag,
	value=0
	))
	# send unspent inputs to
	unspent = iota.Address('HWFZCLVY9RPTAWC9OIOSHXSWFIYMSYSYBHZER9BYZ9KUPUJTRUOLKSGISILWFCWJO9LNZOLWRCJMVDJGD')
	pb.send_unspent_inputs_to(unspent)
	# This will get the bundle hash
	pb.finalize()
	# If the transaction need sign, it will then sign-up the transaction
	# to fill up signature fragements
	kg = iota.crypto.signing.KeyGenerator(SEED)
	# pb.sign_inputs(kg)
	i = 0
	while i < len(pb):
	txn = pb[i]
	if txn.value < 0:
	if txn.address.key_index is None or txn.address.security_level is None:
	raise ValueError
	# pb.sign_input_at(i, kg.get_key_for(txn.address))
	address_priv_key = kg.get_key_for(txn.address)
	# Fill in signature fragement
	# address_priv_key.sign_input_transactions(pb, i)
	from iota.crypto.signing import SignatureFragmentGenerator
	sfg = SignatureFragmentGenerator(address_priv_key, pb.hash)
	for j in range(address_priv_key.security_level):
	txn = pb[i + j]
	txn.signature_message_fragment = next(sfg)
	i += txn.address.security_level
	else:
	i += 1
	# Now each transaction have their signature into bundle
	# this is the end of the transaction construction.
	# We can now propose the transaction to tangle
	# At this moment, tips still not inside each transaction,
	# and each transaction hash is not yet generated
	trytes = pb.as_tryte_strings()
	# Get tips by getTransactionsToApprove
	# tips = getTransactionsToApprove()
	trunk_hash = iota.Hash('')
	branch_hash = iota.Hash('')
	# Do PoW (attach to tangle)
	prev_tx = None
	for tx_tryte in trytes:
	txn = iota.Transaction.from_tryte_string(tx_tryte)
	txn.trunk_transaction_hash = trunk_hash if prev_tx is None else prev_tx.hash
	txn.branch_transaction_hash = branch_hash if prev_tx is None else trunk_hash
	# Copy obsolete tag if tag field is empty
	if not txn.tag:
	txn.tag = txn.obsolete_tag
	# Copy timestamp
	txn.timestamp = None
	txn.timestamp_lower_bound = None
	txn.timestamp_upper_bound = None
	# Do the PoW for this transaction
	diver = pearldiver.PearlDiver()
	trits = txn.trits()
	diver.search(trits, min_weight_magniude, -1)
	# Validate PoW
	# transactionValidator.validate(txn.as_trits())

view rawIOTA_contruct_tx_bundle.py hosted with ❤ by GitHub

여기서는 IOTA가 트랜잭션을 사용하여 Bundle을 구성하는 방법과 bundle hash, transaction hash, trunk hash, branch hash 및 nonce.와 같은 트랜잭션의 중요한 부분을 채울 때에 대해 설명한다.

우리는 명확하게 알고있다 트랜잭션을 생성하는 모든 단계에서 IoT 디바이스의 핵심 부분은 본인의 Transaction에 Signing하는 부분만 신경쓰고 나머지 other output transaction, tip selection and PoW 는 해당 디바이스에서 수행될 필요가 없다.

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의 일부분 제외

IOTA란 무엇인가? - IOTA 개요 / 작동원리 / 안정성

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

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

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

The Tangle

Tangle은 IOTA의 기본구조이다. 블록체인은 아니지만 분산화된 장부(Distributed Ledger)중의 하나이다. 

확률 모형으로 이 네트워크가 언제 안전한지에 대해 공부하는 내용을 다루도록한다.

1. 개요

○ 블록체인 기반 구조에서 거래를 진행할 때 이 거래를 승인해서 블록에 등록해주는 블록을 만드는 사람들에게 fee를 줘야 하고 이 fee가 높을 수록 승인이 빠르게 진행된다.

○ 이를 Heterogeneous Nature 때문이라고 하는데 Heterogeneous Nature란, 이렇게 거래를 발행하는 사람과 거래를 승인하는 사람이 분리되어있는 환경을 말한다.

○ IOTA에는 Micropayments를 가능하게 하기 위해 이 Heterogeneous Nature를 없애 Transaction fee를 없앴다. Micropayments의 제약은 내가 거래를 발행하기 전에 먼저 거래를 승인해줘서 fee를 없애야 한다.

○ 기본적인 구조

- Direct Approved & Indirect Approved 라는 2가지 승인이 존재한다.

ex) A는 D와 B를 확인해준다. D는 Genesis를 Approve 한다. 이런것이 Direct Approve이고 A는 Genesis를 Indirect하게 Approve한다.

- 노드들의 네트워크와 거래들의 네트워크를 따로 보아야 한다. 위의 그림은 거래들의 네트워크이기 때문에 Tangle이다. 블록체인에서는 블록 안에 여러개의 거래가 들어가지만 여기서는 노드 1개에 거래 1개이다. Tangle에서는 이를 Site라고 한다.

- 꼭 그렇지는 않다고 한다. 위 영상에서 설명하시는 분이 이해한 바로는 제네시스 사이트는 발행할 때 토큰들을 발행하고 나중에는 더 이상 토큰을 발행하지 않는다. 따라서 founder의 주소를 가지고 있는 트랜잭션들을 포함한다.

- 거래들은 본인만의 Weight를 가진다. Weight는 뒤에 자세한 설명이 나올 예정이다.

○ 메인 아이디어

- 노드는 2개의 다른 거래들을 승인해주어야 한다.

- 노드는 2개의 트랜잭션이 Conflict한지 체크하고 Conflict하다면 approve하지 않는다.

- 비트코인처럼 Hash Puzzle을 풀어야 노드는 유효한 거래를 발행할 수 있다.

○ The network is asynchronous

- Conflict 한 거래가 있을 경우 누가 고아블록이 될 지 결정해야함: "tip selection algorithm" (뒤에 설명)

- Section 2. Notations

- Section 3. Stability

- - 3.1 How fast does the cumulative weight typically grow?(얼마나 빠르게 신뢰도가 향상되는가?)

- Section 4. Possible attack scenarios

- - 4.1 A parasite chain attack and new tip selection algorithm

- - 4.2 Splitting Attack

- Section 5. Resistance to quantum computations

이어서 Section 2로 진행할 예정