백준 17115번: Kudeki Chain

백준에는 가끔 경이로운 문제들이 있다.

재능이 많은 사람들이 그 재능을 발산할 곳을 찾다 못해 백준 문제에 그 정수를 담아놓는 듯한 기분이다.

구데기컵의 이 문제도 그러하다. 본격적인 채굴 문제...

문제의 기본적인 원리는 비트코인의 그것을 이용한다.

비트코인에 조금이나마 관심이 있는 사람이라면 비트코인이 hash를 쓴다는 것 정도는 알고있을 것이다. 하지만 사실 hash를 직접 써 볼 기회가 그리 많지는 않다. 이 문제는 그런 의미에서 요즘 각광받는 블록체인 기술의 맛보기라도 볼 수 있다는 점에서도 아주 좋은 문제이다.

배경 지식을 아주 간단하게만 설명하면, 비트코인은 블록 전체를 sha-256이라는 해시 알고리즘을 통해 hash를 돌려서 hash값이 특정 숫자 이하가 나오도록 하며,

블록에는 거래정보 / 직전 블럭 해시 / 변조 부분 등이 담긴다. 채굴을 할 때는 보통 변조 부분을 한 비트씩 바꾸며 계속 hash값를 계산한다.

변조 부분 사이즈가 그리 크지 않아서, 저 부분 외에도 많은 곳들을 바꾸어야 하지만 일단 넘어가자.

흥미로운 것은 git도 유사한 구조를 사용한다는 것이다. 어쩌면 비트코인의 원조 격일지도...

git은 sha-256 대신 sha-1이라는 알고리즘을 사용한다.

아무 git repository에나 들어가서, 다음과 같이 입력해보자.

> git cat-file commit HEAD

그러면 다음과 같은 출력이 뜰 것이다.

tree ~~

parent ~~

author 아무개 <아이디> 시간 +0900

committer 아무개 <아이디> 시간 +0900

메시지

자세히 찾아보지는 않았지만, tree는 파일들을 통해 구한 hash 값인 것 같다.

아마 모든 파일을 commit할 때마다 hash를 계산하지는 않을 것이고, 변경된 파일들만 계산하고 hash값들끼리 또 hash를 돌리거나 그런 식으로 작동하지 않을까 생각한다. 확실한 것은 파일만 똑같다면, 언제 commit을 하던지 간에 이 값은 동일하다.

parent는 직전 commit의 hash값이다.

author과 committer는 생략.

메시지 부분은 commit 할 때 -m 뒤에 적어둔 부분이다.

또, 

> git cat-file commit HEAD | wc -c

를 입력하면 다음과 같은 출력이 뜬다.

commit 숫자

여기 나온 숫자는 아까 위의 출력의 총 길이이다. 맨 마지막 '\n'을 포함하는 길이인 것 같다.

commit의 hash값은, commit 숫자 + '\0 + tree~메시지를 hash를 돌린 값이다.

이제 우리가 할 일은, 이 hash값이 0000... 으로 시작하도록 만드는 일이다. 바꿀 수 있는 부분은 메시지 부분이기 때문에 메시지를 계속 바꾸어가며 무작정 hash를 돌리기만 하면 된다.

많은 방법이 있지만, 파일이 고정되어 있으므로 시간, 메시지만 바꾸어가며 hash를 돌리면 편하다.

현재의 timestamp에서 20초 정도를 더한 다음, 메시지 조합을 바꾸며 원하는 hash값을 찾은 뒤,

찾았을 경우 그 시간이 될 때까지 기다리다가 그 메시지로 commit을 해주면 된다.

동시에 여러 thread를 이용해서 돌리면 더 빠른 성능을 낼 수 있다.

아래는 코드이다.

#include <iostream>
#include <string>
#include <ctime>
#include <pthread.h>
#include <unistd.h>
#include "sha1.h"
using namespace std;

const int thread_num = 8;
int difficulty = 7;
bool find = 0;
int ans_time;
string message;

void* thread_main(void* arg) {
	int tid = (long long)arg;
	int start = (tid * 26) / thread_num;
	int end = ((tid + 1) * 26) / thread_num;

	string s = "commit 218";
	s += '\0';
	s += "tree f1f930091088706edcb2a47e6f7bf3934f1be7d3\nparent 000000000000e437f6dc150daaf0e0e3daa07b3c\nauthor JeonggyunKim <dgistjg@gmail.com> 1234567890 +0900\ncommitter JeonggyunKim <dgistjg@gmail.com> 1234567890 +0900\n\n@@@@@\n";

	while (1) {
		time_t timestamp = time(0);
		timestamp += 30;


		int temp = timestamp;
		for (int i = 0; i < 10; ++i) {
			s[154 - i] = temp % 10 + '0';
			s[214 - i] = temp % 10 + '0';
			temp /= 10;
		}

		for (char a = 'a' + start; a < 'a' + end; ++a) {
			s[223] = a;
			for (char b = 'a'; b <= 'z'; ++b) {
				s[224] = b;
				for (char c = 'a'; c <= 'z'; ++c) {
					s[225] = c;
					for (char d = 'a'; d <= 'z'; ++d) {
						s[226] = d;
						for (char e = 'a'; e <= 'z'; ++e) {
							s[227] = e;
							string t = sha1(s);
							
							int cnt = 0;
							int ind = 0;
							while (t[ind++] == '0') cnt++;
							if (cnt >= difficulty) {
								::find = 1;
								ans_time = timestamp;
								message = s.substr(223, 5);
								cout << "find: " << timestamp << ' ' << message << '\n';
								cout << "hash: " << t << '\n';
							}
							if (::find) return NULL;
						}
					}
				}
			}
		}
	}
}


int main(int argc, char *argv[]) {
	int start = time(0);
	if (argc == 2) difficulty = atoi(argv[1]);

	pthread_t tid[thread_num];
	for (int i = 0; i < thread_num; ++i) {
		pthread_create(&tid[i], NULL, thread_main, (void*)i);
	}
	for (int i = 0; i < thread_num; ++i) {
		pthread_join(tid[i], NULL);
	}

	cout << "find after " << time(0) - start << "second...\n";
	while (time(0) != ans_time);
	execlp("git", "git", "commit", "-m", message.c_str(), NULL);
}

sha1은 잘 구현된 것들이 있는데, 가져다가 사용했다.

혹시 python을 사용할 사람이 있다면 다음과 같이 사용하면 된다.

import hashlib
a = b'123'
result = hashlib.sha1(a).hexdigest()

bytearray를 사용한다는 점에 유의하자.

나는 뭔가 cpp이 빠를 것 같아서 http://www.zedwood.com/article/cpp-sha1-function 것을 사용했다.

(그런데 생각만큼 빠르지는 않더라. 이상한 걸 막 갖다써서 그런가..)

#include <ctime>
time_t now = time(NULL);

위 코드를 사용하면 현재 timestamp를 얻을 수 있다.

혹시 commit이 잘 안 될까봐, 메시지는 a~z까지만 사용하였고 5글자를 사용하였다.

정답을 찾으면 현재 시간에서 정답 시간이 될 때까지 wait을 해준뒤, exec 함수로 git commit을 실행해주면 된다.

나는 wait이 약간 불안해서 그냥 while문을 돌렸다.

일단 7개의 0을 목표로 돌려보았다.

372초 간 돌아간 뒤, hash값을 찾아내고 commit을 실행하였다.

해당 commit의 hash값을 알아내는 방법은 상기하였듯, commit 숫자 + '\0 + tree~메시지를 hash 돌리면 된다.

리눅스에서는 기본적으로 hash의 계산을 지원한다.

예를 들어

> printf "123" | sha1sum

이라고 입력하면 123에 대한 sha-1 해시값을 출력해준다.

셸에 다음과 같이 입력하자.

> (printf "commit %s\0" $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD) | sha1sum

참고로 위에서 설명한 것과 똑같은 과정을 진행하는 것이다.

계산 결과 올바른 값을 얻었음을 알 수 있다.

노트북에서 8개 thread로 돌렸더니, 1초에 80만 개 정도 체크를 할 수 있는 것 같다.

실제로 372초간 돌렸더니 맞는 값을 찾아냈다. 16^7 / 800000 = 335니까, 얼추 계산이 맞는 것 같다.

현재 문제를 맞춘 사람은 12명. 그렇다면 이번에 문제를 풀려면 0이 13개 연속으로 붙어야 한다.

내 노트북 하나로 돌린다면 얼마의 시간이 걸릴까? 평균적으로 4284년이 걸린다.

GPU를 쓰거나, 조금 더 좋은 라이브러리를 쓰거나, 코드를 최적화하면 시간이 많이 줄어들 수는 있을 것 같지만 어림도 없어 보인다.

또 ASIC은 해시를 계산하는 데 GPU보다 10만 배 정도의 성능을 낸다고 한다. sha-256 ASIC이야 많이 있지만 sha-1도 ASIC이 있는지는 잘 모르겠다.

0 9개 정도만 되어도 비벼볼 만 했을텐데.. 꼭 풀고 싶은 문제였지만 빠르게 접었다.

내 예상으로 한 명 정도는 문제를 더 풀 것 같다. 그 이상은 어림없을 듯.