바이너리서치와 블록체인: EstimateGas

Binary Search

목차

1.블록체인 기반 앱에서 트랜잭션 수행에 필요한 가스 측정은 어떻게 할까?

2.Binary search란?

3. Binary Search 알고리즘 코드

4. Binary Search 알고리즘 적용

5. 블록체인에서의 Binary Search 알고리즘 (EstimateGas)

6. 마치며

1. 블록체인 기반 앱에서 트랜잭션 수행에 필요한 가스 측정은 어떻게 할까?

블록체인 기반 앱을 개발하다보면, A 트랜잭션을 수행하는데 들어가는 가스량에 대해서 설정해주어야 하는 경우가 있다. 가장 좋은 시나리오는 해당 함수가 어느 정도의 가스 리밋이 필요한지에 대해서 미리 알고 있고, 해당 값을 넣어주어 바로 transaction을 보내는게 가장 효율적인 시나리오이지만, 그렇지 않은 경우는 트랜잭션을 보내기 전에 얼마만큼의 가스가 들지에 대해서 측정을 해야 한다.

이러한 가스 측정은 어떻게 할까? 블록체인에는 estimateGas 라는 함수가 존재한다. estimateGas를 호출하게 되면 해당 예비 트랜잭션을 블록체인을 구성하는 노드가 받아서 가스를 측정한다. 이러한 가스를 측정하는 EstimateGas의 내부 알고리즘은 생각보다 간단하다. EstimateGas의 내부 알고리즘은 Binary Search 알고리즘이 적용되어 있는데, 이 Binary Search란 매우 쉽게 접할 수 있는 알고리즘으로, 보통 알고리즘을 공부하게되면 초반부에 접할 수 있다.

2. Binary search란?

Binary search란 간단히 말해서, 스무고개와 비슷한 방법이다. 예를 들어, 친구가 1 ~ 1000의 숫자 중 본인이 어떤 숫자를 생각하고 있는지 단 10번의 질문을 통해서 맞추면 나에게 100만원을 주고, 못 맞추면 내가 친구에게 200만원을 주는 게임을 하자고 친구가 제안했다고 가정해보자.

이 게임 해야될까? 하지 말아야 될까?

일단, 1 ~ 1000은 범위가 꽤 크다. 학창시절, 자물쇠의 비밀번호를 잊어버렸을 때 1 ~ 999까지 하나씩 돌려가면서 찾던 경험에 비추어보면 쉽지 않은 문제라고 생각된다.

하지만 우리에게는 10번의 질문을 할 수 있는 기회가 있다.

..그렇다고 한들 뭐가 달라질까?

Binary search 알고리즘을 알고 있다면 달라진다! 이 알고리즘을 이용하면 친구가 제안한 게임은 무조건 내가 이기는 게임이 된다.

먼저 내가 친구에게 할 질문의 목록은 다음과 같다.

1. “너가 생각하는 숫자가 500 보다 커?”

- 응

2. “너가 생각하는 숫자가 750 보다 커?”

- 응

3. “너가 생각하는 숫자가 875 보다 커?”

- 아니

4. “너가 생각하는 숫자가 812 보다 커?”

- 응

5. “너가 생각하는 숫자가 843보다 커?”

- 아니

6. “너가 생각하는 숫자가 827보다 커?”

- 아니

7. “너가 생각하는 숫자가 819보다 커?”

- 응

8. “너가 생각하는 숫자가 823보다 커?”

- 응

9. “너가 생각하는 숫자가 825보다 커?”

- 응

10. “너가 생각하는 숫자가 826보다 커?”

- 아니

너가 생각하는 숫자는 826이구나?

- 응 맞아..

3. Binary Search 알고리즘 코드

위에서 말했던 질문을 코드로 작성하면 다음과 같다.

while (low + 1 < high) {

mid = (low + high) / 2

if (mid < solution) {

low = mid

} else {

high = mid

}

}

예상했듯이, 바이너리서치는 전체적인 탐색범위를 계속해서 좁혀나가면서 정답을 찾아내는 알고리즘이다.

탐색범위를 좁히는 것은 최소값과 최대값에 대해서 계속해서 수정해나가면서 이루어진다.

위의 코드에서 low가 정답범위의 최소값, high가 최대값이고, mid는 최소값과 최대값을 더한 값의 절반이다. 마지막으로 solution은 친구의 숫자, 즉 정답이 되는 숫자이다.

친구가 1 ~ 1000 범위에 정답이 있다고 했으니 초기의 low는 1이고, high는 1000이 된다.

이를 토대로 위에 작성된 코드를 따라가보자.

while (low + 1 < high)

이 코드의 의미는, “최소값에 1을 더한 값이 최대값보다 작다면 아래의 코드를 수행하라”이다. 문장이 좀 수학문제 지문같아서 모호하게 느껴져도 곧 이해될 것이다.

mid = (low + high) / 2

이 코드의 의미는, 최소값과 최대값의 절반에 해당하는 값을 mid라는 값으로 한다라는 의미이다.

low는 1이고 high는 1000이니까, 여기서 mid는 500이 된다.

if (mid < solution) {

low = mid

}

본격적으로 질문을 시작하는 문장이다. 아까 mid값으로 해준 500보다 solution(정답)이 큰지 묻는다.

만약 500보다 정답이 크다면 low 값을 500으로 해준다.

else {

high = mid

}

만약 solution(정답)보다 mid가 크지 않다면, high 값을 500으로 해준다.

이 코드를 실제로 위에서 했던 질문에 적용해보면서 따라가보자.

(정답은 위에서 본 질문과 같이 826으로 한다.)

4. Binary Search 알고리즘 적용

(위에서 했던 10번의 질문을 코드를 따라가보면서 수행해본다면?)

while (low + 1 < high)

“low + 1 < high 면 다음의 코드를 수행해라.”

1 ~ 1000의 숫자범위였으니, low는 1이고 high는 1000이다.

1 + 1이 1000 보다 작은가? ( 1 + 1 < 1000 ) 그렇다.

따라서 다음 스텝을 수행한다.

mid = (low + high) / 2

“low + high의 절반을 mid의 값으로 해라.”

mid의 값은 (1 + 1000) / 2 = 500이된다. (정확히는 500.5이지만 소수점은 버린다.)

if (mid < solution) {

low = mid

}

“mid의 값이 solution(정답)보다 작다면 low의 값을 mid의 값으로 바꾼다.”

mid의 값은 500이고, 친구가 500보다 크다고 했으니, low = mid 코드를 수행한다.

따라서 이제부터 low의 값은 1이 아니라 500이 된다.

1회차의 질문을 통해서 최소값이 500이고 최대값이 1000임을 알았다.

수확: 500 < 정답 <= 1000

이제 2회차 질문부터는 위와 같은 과정을 좀 간략하게 표현해보겠다.

2회차 질문

while (500 + 1 < 1000) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (500 + 1000) / 2

if (mid < solution) : 750 < 826 OK

low = mid : low = 750

수확: 750(최소) < 정답 <= 1000(최대)

3회차 질문

while (750 + 1 < 1000) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (750 + 1000) / 2

if (mid < solution) : 875 < 826 NO

high = mid : high = 875

수확: 750(최소) < 정답 <= 875(최대)

4회차 질문

while (750 + 1 < 875) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (750 + 875) / 2

if (mid < solution) : 812 < 826 YES

low = mid : low = 812

수확: 812(최소) < 정답 <= 875(최대)

5회차 질문

while (812 + 1 < 875) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (812 + 875) / 2

if (mid < solution) : 843 < 826 NO

high = mid : high = 843

수확: 812(최소) < 정답 <= 843(최대)

6회차 질문

while (812 + 1 < 843) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (812 + 843) / 2

if (mid < solution) : 827 < 826 NO

high = mid : high = 827

수확: 812(최소) < 정답 <= 827(최대)

7회차 질문

while (812 + 1 < 827) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (812 + 827) / 2

if (mid < solution) : 819 < 826 YES

low = mid : low = 819

수확: 819(최소) < 정답 <= 827(최대)

8회차 질문

while (819 + 1 < 827) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (819 + 827) / 2

if (mid < solution) : 823 < 826 YES

low = mid : low = 823

수확: 823(최소) < 정답 <= 827(최대)

9회차 질문

while (823 + 1 < 827) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (823 + 827) / 2

if (mid < solution) : 825 < 826 YES

low = mid : low = 825

수확: 825(최소) < 정답 <= 827(최대)

10회차 질문

while (825 + 1 < 827) : OK 다음으로 진행

mid = (low + high) / 2 : mid = (825 + 827) / 2

if (mid < solution) : 826 < 826 NO

high = mid : high = 826

수확: 825(최소) < 정답 <= 826(최대)

정답: 826

5. 블록체인에서의 Binary Search 알고리즘 (EstimateGas)

위의 함수는 estimateGas라는 이름의 함수로, 어떤 트랜잭션을 보내기 전에 얼마만큼의 가스량이 필요한지에 대해서 측정해주는 함수이다. 바로 이 “측정”이 바이너리서치 알고리즘을 통해서 이루어진다.

첨부한 그림의 전체의 코드에 대해서 이해할 필요는 없고, 드래그해서 하이라이트 된 부분이 바이너리서치 알고리즘인 것에 대해서만 알면 된다.

앞에서 말했듯 바이너리서치 알고리즘은 low값과 high값을 통해서 범위를 좁혀나가면서 정답을 찾아내는 알고리즘이다. 따라서 low값과 high값이 초기에 설정되어야 하는데,

초기의 low 값은 20999 라는 값으로 설정되고(21000–1), high 값은 블록 가스리밋으로 설정된다.

다음으로, 드래그 된 부분의 executable 이란 함수는 주어진 mid 값으로 이 트랜잭션을 수행할 수 있는지에 대해서 판단해주는 함수로, 우리가 위에서 친구에게 질문을 했던 것과 같은 의미라고 보면된다. 질문 대상이 친구에서 블록체인 노드로 바뀌고, 질문 내용이 “트랜잭션 수행할 수 있는 가스량이 mid 값보다 크니?” 라고 바뀌었을 뿐이다.

EstimateGas 함수는 low 20999와 high (이더리움 블록체인의 경우 약 8000000) 값을 기준으로 바이너리서치 알고리즘을 이용해서, 계속해서 트랜잭션 수행을 시뮬레이션 해보면서 최적의 값을 측정해낸다.

6. 마치며

블록체인 쪽 코드를 살펴보다가 너무나 익숙한 코드가 있어서 놀랐는데, 그 코드가 바로 EstimateGas 였다. 학부시절 자료구조~알고리즘 수업에서 가장 초기에 접하는 알고리즘이고, 다른 알고리즘들에 비해 간단해서 기억하고 있었다. 이것을 블록체인 쪽에서 보게되니 참 반가운 것 같다. :)

(참고로 그림에 올린 저 코드는 이더리움의 go-ethereum/internal/ethapi/api.go 경로에 있는 EstimateGas 함수이다.)