클레이튼 블록 Tx 순서 원리

이쓰레드의 연장입니다. 쓰레드가 엑티브하지않아 다시올립니다.

특정 주소의 Tx가 반복해서 블록의 1번째에 담기고 있습니다.

Tx이 블록에 담기는게 랜덤으로 알고있는데 코드적으로 아니라면 알려주시면 감사하겠습니다!

주기적으로 컨트랙트를 바꾸고 있고,

현재는 이 주소로 Tx를 날립니다.

0xfd0fb722 메서드를 사용하는 Tx들을보면 거의 대부분 블록에서 1번째에 담깁니다.

이전 쓰레드에서 프론트러닝 이야기가 간간히 나오는데, 프론트러닝이 중요한게아니라

어떻게 블록의 1번째 Tx 슬롯을 매번 차지할 수 있는가? 입니다.

랜덤으로 알고있던 Block Tx ordering이 FCFS로 바뀐적이 있나요?

2 Likes

정정합니다 0x2468c5a8 메서드도 추가합니다

1 Like
  1. 블록안의 tx 순서가 랜덤이 아니라 특수한 상황(ex: 체인 개발자도 몰랐던 코드 허점)에서의 순서 특정
  2. GC가 연관된 어뷰징(ex: 오픈소스니 순서 소팅하는 부분만 특정 계정은 tx에 무조건 1위로 설정하도록 수정 후 컴파일 하는 등)
  3. 공개하지 않았지만 FIFO방식으로 변경된 버전이 적용

세 케이스 중 하나로 추측되는데요,
체인 신뢰성에 큰 훼손이 있을 수 있는 이슈인만큼 정확한 원인 파악해서 공유 부탁드립니다.

저도 세케이스 정도로 추측하고있습니다.

3가지 경우 특히 2번이면 신뢰성에 큰 문제가있을걸로 생각하는데 포럼쪽에서는 심각하게 안받아들이는지

분석이나 관련 답변이없네요…

다른쪽에 제보해서 알아봐야할듯합니다

말씀주신 분류 중에서는 1번이라 생각됩니다.
Klaytn에서 블록에 tx가 담기는 순서를 랜덤이라 표현하는데, 정확히 말하자면 "우선순위를 보장해주는 로직이 없다"입니다. 즉, 랜덤을 보장해주기 위한 로직이 적용되어 있지 않기에 개발언어인 golang의 특성이나 노드 자원 상태에 따라 조금 더 우선수위를 확보할 수 있는 방안이 존재할 수 있습니다. 실제로 최근 Cypress 블록에 담기는 트랜잭션들을 보면 이러한 특성을 실험히는 듯한 트랜잭션들을 종종 볼 수 있습니다.

가장 우려하시는 부분은 2번 사항 같은데, 이 부분은 가능성이 아주 낮다고 생각하고 있습니다. 데이터를 확인하시면 아시겠지만 특정 Miner에서만 말씀주신 현상이 발생하는 것이 아닙니다. 따라서, 해당 tx 사용자가 GC 전체과 담합하지 않는한 GC가 연관된 어뷰징이 생각하기 어렵습니다. 게다가, 해당 사용자는 단 하나의 tx만 보낸는 것이 아니라 우선순위를 확보하기 위한 여러 tx를 한 블록에 담기도 합니다. 따라서 정확적으로도 GC 담합의 가능성을 말하기는 이르다 생각됩니다. 아시겠지만, GC가 어뷰징을 했다는 것을 파악하는 것보다 GC가 어뷰징을 하지 않는다는 것을 증명하기는 아주 어렵습니다. 이 부분을 의심하고 GC들에게 어떠한 방식의 증명을 요구하기 위해서는 좀 더 탄탄한 데이터가 필요할거 같습니다.

FIFO 방식은 현재 Klaytn dev branch에 일부 개발되어 있으며, 한달 이내로 출시 예정인 v1.8.3에 정식으로 적용될 것 입니다. 이 방식이 적용된다면 각 CN이 가장 먼저 받은 트랜잭션을 우선적으로 블록에 넣게 될 것입니다. 또한, 동적 gas price 정책도 차후 버전에서 논의되고 있는데, 이 기능이 적용된다면 이 또한 트랜잭션 순서에 영향을 줄 것 같습니다.

2 Likes

Klaytn은 메인넷 런칭시점부터 항상 오픈소스로 개발되고 있습니다.
블록에 담긴 Tx우선순위와 관련된 코드는 Klaytn Github Repository 가셔서 txpool과 worker 패키지쪽에서 직접 확인하실 수 있습니다.

조금 걱정되는부분은, 조금 더 우선순위라고 하기엔 거의 매번 1번으로 담기는게 우려되긴했습니다.

로직상 map에서 account대로 tx를 뽑아오는데,

Golang에서 map key iteration은 순서를 보장할 수 없다. 랜덤성을 띈다고 이야기하고있습니다

reference1 : Go maps in action - The Go Programming Language
reference2 : Go 1 Release Notes - The Go Programming Language

어뷰징이 아니라면 해당 사용자가 Goalng 에서 랜덤 selection과 klaytn 코드 사이의 결함을 발견했다고 보는건가요?

실제로 최근 Cypress 블록에 담기는 트랜잭션들을 보면 이러한 특성을 실험히는 듯한 트랜잭션들을 종종 볼 수 있습니다.

이부분을 공유해주시면 좀더 분석하는데 도움이 될 듯 합니다.

게다가, 해당 사용자는 단 하나의 tx만 보낸는 것이 아니라 우선순위를 확보하기 위한 여러 tx를 한 블록에 담기도 합니다.

이부분은 대부분 1~2 Tx를 보내는걸로 분석되고있기는 합니다.

네 해당코드는 팔로업 하고 있고 그부분을 보고 당연히 랜덤일 수 밖에없다고 생각해서 쓰레드를 열긴 했습니다

Golang에서 이야기하는 순서를 보장할 수 없기에 랜덤성을 띈다라는 표현은 랜덤을 구현하였다와는 Randomness 정도의 측면에서는 아주 다른 이야기입니다. 100번 중에 한번만 달라도 순서를 보장할 수 없기에 랜덤성을 띈다라고 표현할 수 있습니다. 이 부분에 대해서 높은 Randomness가 항상 보장된다고 생각하는건 어려울거 같습니다.

우선 이를 결함이라 파악하려면 Klaytn의 설계 목적에 블록에 담기는 트랜잭션을 랜덤으로 넣는 것이 있거나 저희가 사용한 golang 라이브러리가 Randomness를 보장하려는 의도가 있어야할거 같습니다. 결함이라기 보단 의도하지 않은 부분을 활용할 수 있는 방안을 찾아다고 생각됩니다.

Cypress에서 최근 블록을 조회하시다보면 한 블록안에 “0x1111” 로 시작하는 Sender와 "0x7777"로 시작하는 Sender의 트랜잭션들을 넣는 모습 등을 보실 수 있습니다. 지금 제가 블록번호를 가지고 있진 않은데, 최근 (Gas 가격 상승 이후) 블록들을 살펴보시면 이런 패턴들을 보실 수 있을 것입니다.

1 Like

맞습니다, 이야기해주신 것처럼 순서 보장불가로 랜덤성을 띈다와, 랜덤을 구현했다는 당연히 다른이야기입니다.

그러나 순서 보장 불가가 Native Map에 키가 추가되면 Key iteration이 섞이면서 발생하는데, Golang 에서 그게 컨트롤 가능한 영역이 아닌걸로 알고 있어서 의문을 제기한거였구요.
(제가 랜덤을 이야기한 부분은 어느 라이브러리가아니라 기본 Golang SDK인 native Map에서의 순서보장 불가능을 말한 것 이었습니다)

랜덤 인데 왜 매번 1등인지가 아니라 순서 보장이 불가능한 Map iteration에 특수 Key만 매번 1번이 가능한 영역인가? 라는 질문이라고 보면 적합할 듯 합니다.

Fee delegation Type Tx에 결함이 있어서 GasPrice를 높게 설정가능한가? 등 여러 케이스를 고려해봤지만, 불가능하고 결국 마지막 Block generation worker부분에서 transaction을 뽑아올때 Golang Map Iteration에서 순서보장 불가능. 으로 도달하더라구요. 그렇다면 2번 을 떠올릴 수 밖에 없게되구요.
( 여담으로 다른 아비트라지하는 봇이 Fee delegate로 따라해보는 것 같더라구요, 그러나 위에 언급된 공격자가 항상 1번을 차지하긴 하더라구요 )

따라서 2번이 아니라면, 팀 내에서 1번에 해당하는 부분을 파악하고있는지가 궁금했습니다.

추가로 0x111~ 0x777 Tx는 역시 본적있습니다만, 해당 시도라기보다는 아비트라지 기회블록에서 한번씩 발생하더군요. 당연히 다른 Tx와 함께 순서가 섞여있었고 매번 위 공격자 Tx가 1번이라 특이점은 없었습니다

@Aidan 관련해서 Go map iteration에서 start offset 이 랜덤이긴 하네요. 시작점만 랜덤이라 Key iteration전체가 섞이진 않지만 시작포인트는 랜덤으로 잡히는걸로 보입니다.

아래는 관련 테스트해본 코드입니다.


package main

import (
	"container/heap"
	"fmt"
	"math/big"

	"github.com/klaytn/klaytn/blockchain/types"
	"github.com/klaytn/klaytn/common"
)

func main() {

	m := make(map[common.Address]types.Transactions)

	testlist := []string{
		"0x3ca69faf2882bdfcea7f2d3231ce4ce37e6a91cc",
		"0xf280dcff4d17d5ca776789b1162920780193e6b3",
		"0xaab71f01cb214be4edc037a793c47391f88b8cc7",
		"0xd37c65ec7395cdfec5cc6d1435fae5bcfafe9de0",
		"0x55dab9feede9725333a9703b8f4d60dcf6ebf6d4",
	}
	for i, s := range testlist {
		txs := make(types.Transactions, 0)
		values := map[types.TxValueKeyType]interface{}{
			types.TxValueKeyNonce:    uint64(0),
			types.TxValueKeyGasPrice: big.NewInt(750000000000),
			types.TxValueKeyGasLimit: uint64(4000000),
			types.TxValueKeyTo:       common.HexToAddress("0x3ca69faf2882bdfcea7f2d3231ce4ce37e6a91cc"),
			types.TxValueKeyFeePayer: common.HexToAddress("0x3ca69faf2882bdfcea7f2d3231ce4ce37e6a91cc"),
			types.TxValueKeyAmount:   common.Big0,
			types.TxValueKeyFrom:     common.HexToAddress(s),
			types.TxValueKeyData:     []byte{},
		}
		if i == 0 {
			values[types.TxValueKeyGasPrice] = big.NewInt(750000000001)
		}
		tx, err := types.NewTransactionWithMap(types.TxTypeFeeDelegatedSmartContractExecution, values)
		if err != nil {
			panic(err)
		}

		txs = append(txs, tx)
		m[common.HexToAddress(s)] = txs
	}

	heads := make(types.TxByPrice, 0, len(m))
	for acc, accTxs := range m {
		heads = append(heads, accTxs[0])
		m[acc] = accTxs[1:]
	}
	heap.Init(&heads)
	for i := 0; i < 5; i++ {
		from, _ := heads[0].From()
		fmt.Printf("%s\n", from.Hex())
		heap.Pop(&heads)
	}
}

Worker의 Selection 로직을 비슷하게 실험해보았는데 위와같이 GasPrice가 다른 Tx가 존재하지 않는 한 나머지들은 Random하게 순서가 Selection 됩니다.

그러나 txpool에 add할때 gas price관련해서 validate하는곳에서 예외 부분이 보이지 않기는 합니다…

따라서,

  • GasPrice를 높게 설정한 Tx가 통과되는 경우
  • 특정 Tx를 1st order로 Accept해주는 경우

둘중하나로 생각됩니다.

테스트해본 결과, map의 0번 인덱스에 가까울수록 처음으로 iteration될 확률이 높습니다. 참고로 올려주신 map iterator초기화 코드에 보면, fastrand()함수를 이용하고 있는데요 코드를 보시면 알 수 있듯이 현재 나의 tx가 가진 인덱스를 알기도 힘들뿐 아니라 안다고 하여도 map의 키값인 address를 적절하게 조절하여 시작 인덱스로 만든다는 것은 더욱 어려워 보입니다.

다만 pending에서 tx를 가져올 때, flatten()을 이용하고 있는데 이는 nonce기반으로 정렬되어 가져옵니다. 따라서 nonce가 낮다면 pending에서 처음으로 꺼내올 가능성이 높아지고 이는 block에 먼저 들어갈 확률도 높아집니다. 말씀해주신 tx들을 보면 대부분 nonce가 0~3사이인 것을 확인 할 수 있습니다.

aidan께서 말씀해 주셨듯 이후 업데이트에서는 이러한 점들을 고민하여 반영하고 있으며, 보다 공정한 트랜잭션 분배를 기대할수 있을거라 생각합니다.

`package main

import (
	"encoding/hex"
	"fmt"
	"os"
)

var addrs = []string{
	"000001f41166f8fc328b8bee979f141871f07e7e",
	"ea4fab048c46ebf29dbd48dd988599297a40d875",
	"c90211f8a76cfe2711f94531a7274f2ddd6534e6",
	"3625122aa684ffad36648d080c1c899108165857",
	"5364f88213ccf65b1aa05baee7f9358bfe3898a5",
	"349796f796a76dfe8f3670acf2cbc34430055796",
	"1c7aa22e001a6b53f2b43325140c2899f0916333",
	"100001f41166f8fc328b8bee979f141871f07e7e",
	"2b10a43e2fd40f7797c5cbb2de1d1ffa4a9dbcf8",
	"fa4fab048c46ebf29dbd48dd988599297a40d875",
	"d90211f8a76cfe2711f94531a7274f2ddd6534e6",
	"4625122aa684ffad36648d080c1c899108165857",
	"6364f88213ccf65b1aa05baee7f9358bfe3898a5",
	"449796f796a76dfe8f3670acf2cbc34430055796",
	"2c7aa22e001a6b53f2b43325140c2899f0916333",
	"449796f796a76dfe8f3670acf2cbc34430055797",
	"2c7aa22e001a6b53f2b43325140c2899f0916334",
	"1b10a43e2fd40f7797c5cbb2de1d1ffa4a9dbcf8",
	"9c7aa22e001a6b53f2b43325140c2899f0916333",
	"6b10a43e2fd40f7797c5cbb2de1d1ffa4a9dbcf2",
}

func main() {
	mTestFile, err := os.OpenFile("csv file path", os.O_APPEND|os.O_WRONLY|os.O_CREATE, os.FileMode(644))
	if err != nil {
		panic(err)
	}

	const normalize = 1000000
	for testCnt := 0; testCnt < 20; testCnt++ {
		firstCnt := make([]int, len(addrs))
		for i := 0; i < normalize; i++ {
			j := 0
			iterTest := newMap()
			for _, v := range iterTest {
				if j == 0 {
					firstCnt[v] = firstCnt[v] + 1
				}
				j++
			}
		}

		for _, n := range firstCnt {
			// fmt.Printf("%f%%\t", float32(n)/float32(cnt)*100)
			fmt.Fprintf(mTestFile, "%f%%,", float32(n)/float32(normalize)*100)
		}
		fmt.Fprintln(mTestFile, "")
	}
	fmt.Fprintln(mTestFile, "")
}

func newMap() map[[20]byte]int {
	iterTest := map[[20]byte]int{}
	i := 0
	for _, addr := range addrs {
		var decoded [20]byte
		temp, err := hex.DecodeString(addr)
		copy(decoded[:], temp[:20])
		if err != nil {
			panic(err)
		}
		iterTest[decoded] = i
		i++
	}
	return iterTest
}
`

본 코드로 테스트해본결과 golang의 map자체가 낮은 index에 편향성을 갖도록 설계된 것 같습니다.

2 Likes

먼저 flatten은 관계가 없는걸로 파악됩니다

클레이튼은 같은 from의 Tx 는 연달아 처리되도록 되어있어서 각 from별로 nonce를 정렬하여 flatten해옵니다.

따라서 pending tx map에서 from이 key, flattened txs가 value로 옵니다.

즉 iteration에 1번째 slot을 받는것은 nonce와는 무관하다고 할 수 있습니다 (address, txs 쌍 이므로 같은 키 내에서만 nonce가 상관있음)

참고로 올려주신 map iterator초기화 코드에 보면, fastrand()함수를 이용하고 있는데요 코드를 보시면 알 수 있듯이 현재 나의 tx가 가진 인덱스를 알기도 힘들뿐 아니라 안다고 하여도 map의 키값인 address를 적절하게 조절하여 시작 인덱스로 만든다는 것은 더욱 어려워 보입니다.

맞습니다 그래서 조절이 불가능할걸로 생각되서

  • GasPrice를 높게 설정한 Tx가 통과되는 경우
  • 특정 Tx를 1st order로 Accept해주는 경우

둘중하나로 생각됩니다.

라고 결론 내었던 것 입니다. 맵중에서는 컨트롤이 불가능하고, 마지막에 TxPriceSorting할때 수정하는 방법밖에 없어보여서요.


남겨주신 테스트의

map의 0번 인덱스에 가까울수록 처음 iteration될 확률이 높습니다.

라고 남겨주셨는데 0번 인덱스라하면 처음 값을 set한 key를 말하는걸까요? 아니면 hash map 의 0번 index bucket을 말씀하시는걸까요?

편항된걸로 보이긴하나 지금 저 해당주소의 확률을 설명하기에는 조금 부족해보이긴 했습니다… 체크 수가 부족하긴 하지만 90%이상의 1번 slot을 차지하네요.

테스트 결과를 보고싶었지만 올리기위해서 조금 수정하신걸로보여 바로 결과를 보기 힘들어 일단 내일 코드를 한번봐볼게요! 테스트 감사합니다!

@jack_jin @Aidan

여러방면으로 계속 분석해보고 있긴하지만,

0xde0e… 0x2559… 로 가는 Tx는 서로 마구 섞여있는 방면, 0x8d9c… 로 가는 이득을 취하는 Tx 2개는 정확히 1,2번을 차지하네요

이런케이스가 대부분인데 클레이튼팀내에서 적극적으로 상황파악해주셨으면 하는 바람이 있습니다

map iteration random의 편향성 이런걸 감안하더라도 말도안되는 확률을 연속적으로 보여주는거로 보입니다

예제로 한 블록만 올리긴했지만, 위와같은 블록이 다수 존재하네요

컨트랙트 : 0x8d9c2d788145472fd8e80c018f599964edaf3898

최근 트잭 몇개 순서대로 보니 싹다 모두 1등이네요.

블록넘버 (순위/해당 블록의 트잭 전체 개수)
88128895 (1/16)
88128894 (1/9)
88128819 (1/24)
88128817 (1/110)
88128718 (1/20)
88128716 (1/92)
88128576 (1/3)
88128571 (1/7)

블록넘버 찾아볼 필요 없고https://scope.klaytn.com/account/0x8d9c2d788145472fd8e80c018f599964edaf3898?tabId=txList

컨트랙트로 트잭쏜거 블록 보면 대부분 빠짐없이 1등으로 실행되고 있습니다. 꼭 원인 파악이 되면 좋겠습니다.

@user22 관심있게 보던 내용인데 업데이트 내용이있나요?? 조용하네용

재단에서는 무시해도 상관 없다고 판단 한건지…?
문제 주소 maker는 다시 다른 컨트랙트를 생성 이번에는 KUSDT 시세차익 이득을 취하고 있네요.

@HSP 제가 분석할 수 있는 선에서는 이게 한계인 것 같습니다.

아무리생각해도 Go map iteration에서 앞순위를 차지할 방법은 없으며,

블록 생성시 Tx selection 할 때 Go map iteration을 이용하는 것 외에는 저는 잘 모르겠더라구요

재단차원에서 GC들이 운영하는 CN 또는 CN을 관리해주는 대행업체가 있다면 그쪽을 한번 조사해주시면 좋을 것 같습니다. ( 바이너리가 plain한 checksum이 나오는지 or 수정된 흔적이 있는지 )

혹은,

제가 놓치는 코드부분이 이있는지 다른분들의 지식을 기다리고있습니다…

단순 0index에 우연히 1번째 slot을 차지한다는건 확률적으로 말이 안된다고생각합니다

@najhna 관련해서 재단측 생각이라도 들려주면 좋긴하겠네요

해당 사용자 주소 변경됐네요

fyi. @assomonia @najhna @Aidan @jack_jin