TigerCow.Door


이전글

#1_블록체인 무엇인가::소프트웨어 시스템 아키텍처

#2_블록체인 무엇인가::분산 P2P 시스템

#3_블록체인 무엇인가::블록체인의 과제

#4_블록체인 무엇인가::소유권의 본질



안녕하세요. 문범우입니다.

이번 포스팅에서는 분산 P2P 시스템의 무결성 침해와 관련된 가장 중요한 사례 중 하나인 이중사용(Double Spending)문제에 대해서 알아보겠습니다.


1. 이중사용(Double Spending)


이중사용은 쉽게 말해서 동일한 재화, 물건에 대해 두번 사용한다는 것 입니다.

보다 쉽게 이해하기 위해 부동산을 판매하는 상황으로 가정해보겠습니다.


A가 B에게 집을 팔았습니다.

이로 인해서 집에 대한 소유권은 A에서 B로 이전 되었음이 P2P 시스템의 어느 원장에 기록되었습니다. 그럼 우리가 이전에 학습한 바와 같이 원장을 관리하는 피어가 즉시 다른 피어에게 이러한 사실을 알립니다. 그리고 그 피어는 또 다른 피어에게 사실을 알립니다.

하지만, 이때 A가 아직 사실을 받지 못한 원장에 접근해서 집에 대한 소유권 이전을 A에서 C로 이전되었음이라고 기록했습니다. 마침 해당 원장을 관리하는 피어는 다른 사실에 대해 들은바가 없으므로 해당 기록을 받아들이게 됩니다.


즉, A가 B에게 집을 판 사실이 모든 피어에게 전달되기 전, 다른 피어에게 접근해 동일한 집을 판매하는 행위가 이중사용입니다.



2. 이중사용의 3가지 의미


이전에 알아본 블록체인도 다양한 의미를 가지고 있듯이 이중사용도 크게 3가지의 의미를 지니고 있습니다.


1. 디지털 재화를 복사해 발생하는 문제

실제로 컴퓨터의 데이터를 복사하는데는 별다른 제약이 존재하지 않습니다. 바로 이런 특성을 이용해서 동일한 디지털 재화를 반복해서 복사함으로써 지불하는데 사용할 수 있습니다.

이는 실물 화폐를 복사하는 범죄와 동일한 것 입니다.


2. 원장의 분산 P2P 시스템에서 발생하는 이중사용 문제

이는 위에서 알아본 예시에 대한 관점입니다. 모든 피어들이 정보를 전달받기까지 시간이 걸리는 문제로 인해 일부 피어가 서로 상이한 정보를 갖게 되는 것 입니다.

모든 피어가 동시에 최신정보를 얻지 못한다면, 최신 정보를 획득한 누군가에 의해서 정보가 악용될 가능성이 있습니다.


3. 순수 분산 P2P 시스템의 무결성이 침해된 이중사용 문제

이중사용 문제를 좀 더 추상화해서 크게 본다면, 분산 P2P 시스템 내의 데이터의 일관성을 유지하는 문제로 생각해볼 수 있습니다. 즉, 데이터의 일관성은 시스템 무결성의 한 측면이므로 이중 사용 문제는 결국 시스템의 무결성이 침해된 사례로 볼 수 있습니다.



3. 이중사용 문제를 해결하는 방법


1. 디지털 재화를 복사해 발생하는 문제 해결

사실상 디지털 재화나 화폐를 복사해 한 번 이상 사용하는 문제는 소유권의 본질과 관련이 있습니다. 즉, 특정 재화나 화폐의 소유권이 누구에게 있는지에 대한 관리가 필요한 것 입니다. 이렇게 특정 데이터와 그 소유자를 매핑하는 수단이 필요하는데 이러한 것은 올바르게 작동되는 원장으로써 해결될 수 있습니다.


2. 원장의 분산 P2P 시스템에서 발생한 이중사용 해결

사실상 이러한 문제에 대한 해결은 블록체인 구조로 가능합니다.

우리가 지난 포스팅에서 블록체인과 원장의 P2P 시스템 간의 관계를 알아보았던 것과 같이, 현재 다양한 포스팅에서 사용되고 있는 블록체인이란 용어 자체가 원장의 분산 P2P 시스템의 이중사용 문제를 없애주는 해결책인 셈 입니다.


3. 분산 P2P 시스템의 무결성이 침해된 이중사용 해결

무결성의 내용과 의미는 분산 P2P 시스템의 용도가 무엇인지에 따라서 결정됩니다. 즉, 간단한 파일 공유 시스템의 경우에는 디지털 화폐의 소유권을 비교하는 것과는 다른 측면의 무결성이 고려될 수 있습니다.

결국 분산 P2P 시스템의 응용분야에 따라 블록체인이 아닌 다른 기술이나 데이터 구조 혹은 다른 알고리즘이 무결성을 확보하고 유지하기에 더 적합할 수 있습니다.



이렇게 이중 사용 문제에 대해서 알아보았습니다.

다음 포스팅에서는 블록체인이 어떻게 무결성을 확보하고 유지하는지에 대해서 알아보도록 하겠습니다.




블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


안녕하세요. 문범우입니다.

오랜만에 파이썬 관련 내용을 포스팅하게 되었습니다.

최근 자바 언어에 대해 다시 공부하면서 멀티 쓰레딩 개념을 학습중인데, 파이썬에서 해당 내용을 다뤄보지 않은 것 같아 간략하게나마 공부하고 이를 정리해보았습니다.


즉, 이번 글에서는 파이썬에서의 멀티 프로세싱, 멀티 쓰레딩에 대해서 알아보도록 하겠습니다.



글에 앞서서, 멀티 프로세싱, 멀티 쓰레딩 등, 동시성 프로그래밍에 대한 개념적인 내용은 아래 글을 참고하시면 되겠습니다.

https://doorbw.tistory.com/26


먼저 전체적인 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from functools import partial 
from threading import Thread
import multiprocessing
import time
 
def singleCount(cnt,name):
    for i in range(1,10000001):
        cnt += 1
        if(i%2500000 == 0):
            print(name,":",i)
 
lists = ['1','2','3','4']
# single process start
cnt = 0
print(" # # SINGLE PROCESSING # # ")
start_time = time.time()
for each in lists:
    singleCount(cnt,each)
print("SINGLE PROCESSING TIME : %s\n" %(time.time()-start_time))
 
# multi process start
cnt = 0
print(" # # MULTI PROCESSING # # ")
start_time = time.time()
pool = multiprocessing.Pool(processes=4)
func = partial(singleCount, cnt)
pool.map(func, lists)
pool.close()
pool.join()
print("MULTI PROCESSING TIME : %s\n" %(time.time()-start_time))
 
#multi threading start
cnt = 0
print(" # # MULTI THREADING # # ")
start_time = time.time()
th1 = Thread(target=singleCount, args=(cnt,"1"))
th1.start()
th1.join()
th2 = Thread(target=singleCount, args=(cnt,"2"))
th2.start()
th2.join()
th3 = Thread(target=singleCount, args=(cnt,"3"))
th3.start()
th3.join()
th4 = Thread(target=singleCount, args=(cnt,"4"))
th4.start()
th4.join()
print("MULTI THREADING TIME : %s\n" %(time.time()-start_time))
 
cs


코드에서는 싱글 프로세싱, 멀티 프로세싱, 멀티 쓰레딩 총 3개의 로직이 구현되어 있으며 이에 대한 결과는 아래와 같습니다.


* 싱글 프로세싱


* 멀티 프로세싱


* 멀티 쓰레딩


위의 결과를 보시면 사실상 싱글 프로세싱과 멀티 쓰레딩의 시간차이는 크게 없고, 멀티 프로세싱에서만 시간 효율이 존재함을 알 수 있습니다.


파이썬에서는 GIL(Global Interpreter Lock)이라는 동작때문에 사실상 여러개의 스레드가 동일한 자원에 대해 접근하지 못합니다.

즉, 우리가 기대한 것과 달리 하나의 스레드가 종료함에 따라 다른 스레드가 진행되는 것이죠. 이러한 GIL때문에 오히려 멀티 쓰레딩이 싱글 쓰레딩보다 I/O작업이 많아 짐에 따라 시간소요가 커질 수 있기도 합니다.

이에 대해 보다 자세한 내용은 아래 링크에서 확인하실 수 있습니다.

https://medium.com/@mjhans83/python-gil-f940eac0bef9


그리고, 멀티 프로세싱은 개념적으로 공부한 것과 같이 다수의 프로세스를 띄워 작업을 처리하기 때문에 당연히 싱글 프로세싱보다 처리 시간이 단축되는 것을 볼 수 있습니다.



오랜만에 다시금 동시성 프로그래밍 개념들에 대해 공부하다보니 또 헷갈리는 내용들과 질문들이 생기게 되었습니다..

위의 글에서 설명이 부족한 이유는 아마 아직 해결되지 못한 궁금증과 질문들 때문일겁니다.. 따로 위에는 적어두지 않았지만 추후에 보다 깊이 이해하게 된다면 한번더 제대로 정리하고 싶어지네요 :-(


잘못된 점이나 궁금하신 점들 언제든지 연락주시면 저도 많이 부족하지만 같이 이야기해보면서 답을 찾아나가면 좋을 것 같습니다 :)

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

 

안녕하세요. 문범우입니다.

최근 파이썬을 활용할 일이 많이 없었는데, 엊그제 문득 필요한게 생각나서 후다닥 파이썬으로 만들어보았습니다.


뭐라고 이름을 지어야할지 모르겠는데..

많은 분들도 만들어서 사용하시기도 하는 것으로 알고 있습니다.

제가 자주 보는 커뮤니티에서의 특정 게시판 상위 n개에 대해서 크롤링하여 링크를 포함한 헤드라인만 정해진 시각에 제 메일로 보내는 프로그램입니다.


저는 OKKY라는 커뮤니티에서 스터디, 뉴스, 행사에 관련된 3개 게시판에 대해 상위 5개 또는 3개의 글을 정해진 시각(오전, 점심, 오후)에 메일로 보내도록 하였습니다.


메일 내용을 더 꾸밀 수도 있겠지만..

일단은 심플하게 아래와 같이 메일이 전송됩니다 :)




실제로 이렇게 해두고 나니, 정해진 시각에 한번쯤 더 쳐다보게 되고 요새 바빠서 다양한 행사에 대해 관심가지지 못하고 있는데 이를 보완할 수 있을 것 같다는 생각이 듭니다.


관련 코드는 github에 올려두어 아래 링크에서 확인해보실 수 있습니다.


https://github.com/doorBW/event_crawl


코드에서도 확인하실 수 있으며, 사용된 내용들은 크게


1. requests와 bs4를 이용한 웹 크롤링

2. SMTP 서버를 통한 메일 보내기

3. crontab 활용하여 일정시간에 쉘스크립트 실행시키기


입니다. 각각에 대해서는 구글에 검색해보시면 다양한 자료를 찾아보실 수 있으니 추가적인 설명은 접어두도록 하겠습니다.


코드가 깔끔할지는 모르겠으나, 필요하신분들 참고하셔도 될 것 같습니다.

추가적으로 궁금한 점등의 문의사항은 언제든 댓글이나 카톡, 이메일로 연락주세요 :)

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

지난 포스팅에서 시간복잡도, 공간복잡도 등에 대해서 알아보며 Big-O 표기법에 대해서 살펴보았습니다.

이번에는 실제로 특정 코드나 알고리즘을 대상으로 그 시간복잡도를 분석해보는 실습을 진행해보도록 하겠습니다.


아래에서 다루게 될 예제들은 ''코딩인터뷰 완전 분석"(게일라크만맥도웰 지음, 이창현 옮김)_인사이트출판 서적에서 일부 참고 및 발췌하였습니다.



 > N에 대한 정확한 사용


우리는 이전 포스팅에서도 그러했듯이 Big-O 표기법으로 나타낼때에 흔히 O(N), O(log N) 과 같이 나타냅니다. 그런데 이때 N에 대해 정확하게 이해하지 못하였다면 추후 잘못된 분석을 할 수 있습니다.

아래와 같은 상황을 생각해보겠습니다.


여러개의 문자열로 구성된 배열이 있습니다. 

이때 각각의 문자열에 대해 먼저 정렬을 하고 이후 전체 문자열을 사전순으로 다시 정렬하는 알고리즘이 있습니다.

이러한 알고리즘의 수행시간은 어떻게 될까요?


간단히 생각해보면, 각 문자열을 정렬하는데 O(N*logN)의 시간이 소요되므로 모든 문자열에 대해서는 O(N*N*logN)이 소요될 것입니다. 그리고 전체 문자열들에 대해 사전순으로 정렬해야 하므로 O(N*logN) 이 추가됩니다.

즉, 해당 알고리즘의 수행시간은 O(N*N*logN + N*logN) = O(N*N*logN) 이라고 생각할 수 있습니다.


하지만 이는 완벽하게 틀린 분석입니다.

어디서 부터 잘못됐는지 아시겠나요?

바로 N에 대한 정확하지 않은 사용입니다.

위의 분석에서는 문자열의 길이와 문자열의 개수 모두 N으로 중복해서 사용하였습니다. 이는 아예 다른 시간복잡도를 가져오게 되는 큰 실수입니다.


제대로된 분석을 위해서는 다음과 같이 변수를 정의하고 진행합니다.


- 가장 길이가 긴 문자열의 길이를 s라고 하자.

- 배열의 길이를 a라고 하자.


이렇게 된다면, 각 문자열을 정렬하는데 O(s * log s) 가 소요되며 모든 문자열에 대해서 생각해 보면, O(a * s * log s) 가 소요됩니다.

그리고 문자열 비교시, 두개를 서로 비교할 때 O(s) 만큼 시간이 소요되고 이것을 총 O(a * log a) 번해야 하므로 O(a * s * log a) 만큼의 시간이 소요 됩니다.

따라서 전체 시간 복잡도는, O(a * s * (log a + log s)) 입니다.




> 재귀 호출 패턴 분석


아래는 균형 이진 탐색 트리에서 모든 노드의 값을 더하는 간단한 코드입니다. 수행시간을 한번 분석해보죠.


1
2
3
4
5
6
int sum(Node node){
    if(node == null){
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}
cs



1. 재귀호출 패턴분석


위의 코드가 단지 이진 트리라는 이유로, 또는 재귀호출이라는 이유로 시간복잡도에 로그가 들어간다고 생각하면 안됩니다. 

실제로 재귀 함수에 분기가 여러개 존재한다면 수행 시간은 일반적으로 O(분기^깊이)가 됩니다. 즉, 두 개의 분기만 존재하는 재귀함수라면 일반적으로 O(2^깊이)의 시간복잡도를 가지게 됩니다.


그렇다면 깊이는 어떻게 될까요? 위의 코드에서 나온 트리는 균형 이진 탐색 트리입니다. 즉, 총 N개의 노드가 있다면 깊이는 대략적으로 log N 의 값을 가지게 됩니다.

그럼 수식에 따라 시간복잡도는 O(2^(log_2 N))이 되는 것을 알 수 있습니다.

하지만 조금 더 살펴보도록 합시다.

결과에 나온 log_2 N 는 과연 무엇을 의미할까요?

2^(log_2 N) = P 라고 생각해본다면, 양변에 로그를 취해

log_2 2^(log_2 N) = log_2 P 가 됩니다. 그러면 로그의 특징에 따라서,

log_2 N * log_2 2 = log_2 P

log_2 N = log_2 P

N = P

가 됩니다.

따라서 총 시간복잡도는 O(N) 이 됩니다.



2. 코드가 무엇을 의미하는가


위에서는 재귀 호출 패턴 분석을 통해 시간복잡도를 분석해보았습니다.

하지만 조금 더 직관적인 방법으로는, 코드가 무엇을 하는지를 살펴보면 알 수 있습니다.

위의 코드는 트리의 각 노드를 한 번씩 방문한 뒤 각 노드에서 상수 시간에 해당하는 일을 하게 됩니다. 즉, 수행시간은 노드의 개수와 선형관계에 있음을 알 수 있고, 이에 따라 N개의 노드가 있을때 알고리즘의 시간복잡도는 O(N)임을 알 수 있습니다.




> 순열(permutation)의 개수를 구하는 코드


아래의 코드는 입력된 문자열로 나타낼 수 있는 순열의 개수를 구하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
void permutation(String str){
    permutation(str, "")
}
 
void permutation(String str, String prefix){
    if(str.length() == 0){
        System.out.println(prefix);
    }else {
        for(int i=0; i<str.length(); i++){
            String rem = str.substring(0,i) + str.substring(i+1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}
cs


코드를 보면 꽤 까다로울 수 있습니다.

이에 대한 시간복잡도 분석을 먼저 스스로 해보시고 보시는 것도 추천드립니다 :)


먼저 위의 코드를 분석하기 위해 permutation 함수가 얼마나 호출되는지, 각 호출마다 걸리는 시간이 얼마나 걸리는지를 나누어 생각하면 쉽게 분석할 수 있습니다.


1. 순열이 완성되는 시점에서의 permutation 함수 호출

순열이 완성되는 시점에서는 코드의 7번째 라인이 실행되는 것인데, 이 또한 permutation 함수가 호출되었기 때문에 입니다. 따라서 특정 문자열에 대한 순열의 개수만큼, permutation 함수가 호출될 것이며 이 값은 n! 입니다.


2. 순열 생성이 완성되기 전에 permutation 함수 호출

동시에 9~12번째 코드라인이 얼마나 호출되어 반복되는지를 살펴보아야 합니다.

트리구조로 생각한다면 1번에서 알아본 n! 는 결국 리프노드의 개수입니다.

그리고 루트에서 리프노드까지의 거리는 n일 것이며, 이를 통해 트리의 총 노드는 절대로 n*n! 을 넘지 못합니다.


3. 한 번의 permutation 호출에서의 소요 시간

한번의 호출이 있었을 때 연산 시간이 얼마나 걸리는지를 파악합니다.

7번째 줄에서는 문자열 전체를 출력하기 때문에 O(N) 시간이 걸리며, 10번째 줄에서 시행되는 substring 함수 또한 O(N) 시간이 걸리게 됩니다.

( 단순 함수 호출이기에 O(1)로 생각하실 수 있으나 java 업데이트 후 해당 함수가 O(N)의 소요시간을 갖게 되었습니다. )


이렇게 1,2,3으로 나누어 분석한 결과 permutation 함수의 총 시간 복잡도는 O(N * N * N!) 임을 알 수 있습니다.




> 피보나치 수 1


아래의 코드는 N번째 피보나치 수(Fibonacci number)를 구하는 코드입니다.


1
2
3
4
5
int fib(int n){
    if (n <= 0return 0;
    else if (n == 1return 1;
    return fib(n-1+ fib(n-2);
}
cs


이는 위에서 우리가 알아보았던 재귀 호출 패턴 분석을 이용하면 O(2^N) 의 시간복잡도를 가지게 됩니다.


하지만 이를 좀 더 세밀하게 분석해보면 약 O(1.6^N)의 시간복잡도가 나오게 됩니다. 구체적으로 다루지는 않겠지만, 우리가 재귀 호출에 대해서 트리구조로 그려볼 때, 호출 스택의 밑바닥에서 가끔식 한번의 호출만 필요한 경우 등이 그 이유일 것입니다.




> 피보나치 수 2


이번에도 위와 같은 동작을 하는, 피보나치 수와 관련된 코드이지만 이번에는 이전에 계산된 결과 값을 정수 배열에 저장하고 이를 이용하는 방식의 알고리즘 입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
void allFib(int n){
    int[] memo = new int[n+1];
    for (int i=0; i<n; i++){
        System.out.println(i+": "+fib(i,memo));
    }
}
 
int fib(int n, int[] memo){
    if (n <= 0return 0;
    else if (n == 1return 1;
    else if (memo[n] > 0return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}
cs


위의 코드에 대해 임의의 n 값으로 실제 호출 스택을 그려본다면 fib(i)를 호출할 때마다 fib(n-1)과 fib(n-2)의 계산이 이미 끝나 있고 이를 단순히 배열에서 가져오는 연산을 진행하는 것을 알 수 있습니다.

즉, 이러한 과정은 상수시간 안에 동작하고 상수 시간의 동작을 총 N번 반복하기 때문에 해당 알고리즘의 시간복잡도는 O(N)을 가지게 됩니다.


이러한 방법은 메모이제이션(Memoization) 이라고 불리는 방법으로써, 지수 시간이 걸리는 재귀 알고리즘을 최적화할 때 쓰는 흔한 방법 중 하나 입니다.

비슷한 방법 중 하나로는 동적계획법(Dynamic Programming) 이 있습니다.


물론 메모이제이션과 동적계획법이 아예 같은 개념인 것도 아니고, 아예 다른 개념인 것도 아닙니다.

필요하다면 추후 다루게 되겠지만 간단하게 살펴보면, 메모이제이션은 결과를 구하고 이를 할용하면서 문제를 해결하는 것이고, 동적계획법은 큰 문제에 대해 작은 부분으로 나누어 작은 것부터 해결해 나가는 것 입니다.



이렇게 지난 포스팅에서 알아본 시간복잡도에 대한 개념에 이어 여러가지 예제들을 함께 살펴보았습니다.

해당 예제들을 통해 실수 할 수 있는 부분들을 캐치하여 추후 자신이 분석하고자 하는 알고리즘에 대해 보다 정확한 분석이 이루어 져야 합니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

최근 Java로 알고리즘 스터디를 시작하게 되었습니다.

단순히 문제풀이 보다는 이론적인 내용들을 살펴보며 관련된 문제를 푸는 방식으로, 기초부터 다시 살펴보려합니다.

이번에는 직접적인 알고리즘 내용에 앞서, 알고리즘 분석 즉 시간복잡도와 공간복잡도에 대해 이야기를 먼저 진행해보겠습니다.



> 왜 알아야 하는가?


Big-O 표기법은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다.

이를 통해 자신이 작성한 알고리즘이 이전보다 빨라졌는지 느려졌는지 판단하는데 도움이 될 것이다.

물론 이 외에 다른 개발자들과 특정 알고리즘에 대해 이야기하거나 효율성 판단등에 의해서 Big-O 표기법을 통해 보다 원활하게 의사소통을 진행할 수 있다.


실제로 Big-O 표기법 이외에 다른 표기법도 있으나 이에 대해서는 혼동을 피하기 위해 제일 마지막에서 언급하겠다.


또한 Big-O 표기법에 대해 이해하는 방식이 조금씩 상이할 수 있지만 그 정의를 정확하게 이해한다면 문제되지 않을 것이다.



> Big-O 표기법의 정의


Big-O 표기법은 사전적으로, 시간(또는 공간)의 상한을 이야기한다.

즉, 시간복잡도와 공간복잡도의 상한에 대해서 이야기하는 것이다.

(주로 시간복잡도를 다루게 될 것이므로 시간을 대표로 설명하겠다.)


정의대로 이야기한다면 시간복잡도에 대해서 이야기할 어떤 것의 최악의 경우(가장 느렸을 경우)에 대한 시간을 이야기 하는 것이다.

즉, 평균적으로 10시간이 걸리는 업무가 있지만 특정 상황에 따라 20시간이 걸린다고 생각해보자. 이때 그 업무에 대한 시간의 상한은 20시간이다. 아무리 오래 걸려도 20시간이면 되기때문이다.

이때 이야기 하는 '아무리 오래 걸려도' 라는 키워드가 결국 Big-O이다.


그럼 이러한 의문이 들 수 있다.


"그럼 그 업무는 아무리 오래 걸려도 100시간 안에 할 수 있으니, 시간의 상한이 100시간이라고 해도 맞는건가요?"


그렇다. 정의에 따라서는 전혀 틀린말이 아니고 수학적으로도 옳은 표기이다.

하지만, 대체로는 그렇게 이야기하지 않는다.


Big-O가 대략적으로 어떤걸 의미하고자 하는지 이해가 갔다면 조금 더 수식적으로 살펴보자.


이를 위해서 위에서 언급한 예시를 조금 더 구체화 해보자.

특정 업무에 대해서 처리할 문서가 n개라고 가정하자.


이때 만약 A라는 사람은 정직하게 일해서 문서당 소요시간이 1시간이다.

근데 B라는 사람은 아직 경력이 부족해서 문서당 소요시간이 2시간이다.

슬프게도 C라는 사람은 호기심이 많아 문서개수에 대해 제곱시간이 소요된다.

놀랍게도 D라는 사람은 자동화 툴을 만들어 놓아서 문서개수에 상관없이 10시간이 소요된다.


이러한 사람들에 대해 각각 Big-O로 소요시간을 나타내보자.


A는 O(N)이다.

문서 1개당 소요시간이 1시간이므로 문서가 늘어나면 소요시간도 선형적으로 늘어난다.


B는 O(2N)이다.

A와 비슷하게 선형적으로 늘어나지만 그 값이 2배일 뿐이다.


C는 O(N^2)이다.

A와 B에 비해 호기심이 많은 C는 문서당 제곱시간이 소요된다고 하였기에 위와 같이 표기된다.


D는 O(10)이다.

자동화 툴을 만들어 놓은 D는 문서 개수와 상관없이 무조건 10시간이 소요된다.


Big-O표기는 위와 같이 표기하는 것이다.

하지만 아직 한가지가 남았다. Big-O 에서는 작은 것들은 신경쓰지 않는다.


정말 간단하게 이야기한다면 Big-O 표기법은, 제일 영향력있는 놈만 신경쓰겠다는 이야기다.

실제로 알고리즘에 큰 영향을 주는 것만 고려하겠다는 이야기인 것이다.


이것은 특정 수식에서 최고차항을 제외한 나머지를 무시한다는 의미이기도 하며, 최고차항에 대한 상수배 또한 무시하겠다는 것이다.


최고차항에 대한 상수배를 무시하겠다는 것은

즉, Big-O 정의에 따르면, O(N)과 O(2N)은 모두 동일하게 O(N)으로 표기된다.

그렇다면, O(10)은 어떻게 표기될까?

상수 시간이므로 O(1) 로 표기된다.


그리고 최고차항을 제외한 나머지를 무시하겠다는 것은,

O(N^2 + 10N + 3) 으로 표시된 값이 있을때 이를 O(N^2)과 같이 표기하겠다는 것이다.



위와 같이 알아본 Big-O 표기법은 초기에 언급한 것과 같이 단순히 시간복잡도를 분석하는데만 사용되지 않는다. 시간 또는 공간 모두 분석하는데 사용되며 공간에 대해 분석하는 것을 공간복잡도라고 이야기한다.


공간복잡도에 대해서 추가적인 설명을 하자면 다음과 같다.


> 공간복잡도

재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.

하지만 함수를 단지 n번 호출했다고 해서 무조건 O(n) 공간을 사용하는 것은 아니다.



Big-O 표기법에서 주로 사용되는 표현들에 대한 대소비교를 해본다면 다음과 같다.(시간복잡도, 공간복잡도 순서)


O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)


그럼 마지막으로, 처음에 이야기했던 Big-O 이외의 표기법들에 대해 간단히 알아보자.


+ Big-Omega

빅 오메가라고 부르는 표기법은 시간에 대한 등가 또는 하한의 개념을 나타낸다.

즉 모든 process는 Ω(1)로 표기할 수 있다. 결국 오메가로 표기되는 알고리즘은 Ω 수행시간보다 빠를 수 없다.


+ Big theta

빅 세타라고 부르는 표기법은 Big-O와 Big-Omega 모두를 이야기한다.

즉, 특정 알고리즘의 시간복잡도가 O(N) 이면서 Ω(N) 이라면 이는 θ(N)이라고 표기할 수 있다.




이렇게 Big-O에 대한 개념적인 내용을 정리해보았습니다.

추후 필요하다고 생각되면 특정 코드나 내용들에 대해 시간복잡도와 공간복잡도를 계산해보는 내용에 대해서도 정리해보겠습니다.



블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


이전글

#1_블록체인 무엇인가::소프트웨어 시스템 아키텍처

#2_블록체인 무엇인가::분산 P2P 시스템

#3_블록체인 무엇인가::블록체인의 과제



안녕하세요. 문범우입니다.

지난 포스팅에서는 블록체인의 과제에 대해서 알아보았습니다. 이번에는 소유권의 본질에 대해 알아보도록 하겠습니다. 즉, 내가 가진 것을 내 것이라고 어떻게 증명하는지 함께 생각해보도록 합니다.



1. 소유권?


하나의 상황을 함께 생각해보겠습니다. 회사를 가기 전에 오전에 간단히 먹기 위한 쿠키를 하나 가지고 집을 나와 출근을 하기 위해 가는 길에서 목이 말라 편의점에 들려 바나나우유를 하나 구입하려 합니다. 헌데 편의점 직원이 가방 안에 있는 쿠키를 빤히 쳐다보고 있습니다. 하필이면 편의점에 있는 쿠키와 같은 쿠키입니다. 이런 상황이라면 불행히도, 직원은 내가 쿠키를 고르고 계산하지 않거나, 훔친 것으로 생각할지도 모릅니다. 더군다나 현재 편의점에는 다른 인원도 없고, CCTV도 없습니다.

이런 상황에서 그 쿠키가 나의 것이라는 것을 어떻게 증명할 수 있을까요?


너무나 당연한 것일지 모르지만, 내가 가지고 있는 것을 내 것이라고 증명하는 일. 그것을 어떻게 해야할 지 생각해본 적이 있나요?


과연 편의점에서 내가 가지고 있는 쿠키가 나의 것이라는 것을, 내가 훔치지 않았다는 것을 어떻게 증명해야 할까요?


물론 이러한 상황에서 법정을 가게 된다 하더라도, 내가 쿠키를 훔쳤다는 것을 증명할 사람도 없으므로 절도 혐의는 풀리겠지만 그렇다고 해서 소유권이 증명된 것은 아닙니다.


만약에, 내가 이전에 쿠키를 구입한 가게의 직원이 증명해준다면 어떨까요? 분명히 소유권을 증명하는데 도움이 될 것 입니다.

그러나, 법정에서 목격자에게 까다로운 질문 즉, 당신이 판매한 쿠키가 맞는지, 그 쿠키가 구체적으로 어떤 것인지, 그 쿠키를 산 것이 내가 맞는지 확신할 수 있는지, 그리고 그 모든것을 어떻게 세부적으로 기억하는지, 혹시 내가 목격자를 매수한 것은 아닌지 등을 이야기한다면 한 명의 독립적인 목격자보다, 독립적인 다수의 목격자를 확보하는 것이야 말로 소유권을 증명하는 좋은 방법이 될 것입니다.


즉, 동일한 사실을 증언하는 독립적인 목격자가 많을수록 그 사실은 진실일 가능성이 더 높아집니다. 그리고 그것이 블록체인의 핵심 개념 중 하나입니다.



2. 소유권 입증의 3요소


위의 상황을 개념화해본다면, 소유권을 입증하는데 필요한 세가지는 다음과 같습니다.


- 소유자가 누구인가

- 소유 물건은 무엇인가

- 소유자와 물건의 매핑


결국 목격자의 증언은 이 모든 것을 포괄하고 있습니다. 과거에는 이러한 목격자의 증언이 유일한 방법이었지만 최근에는 다양한 문서와 매체로 증언이 대체되고 있습니다. 



위의 사진은 소유권을 관리하는 소프트웨어를 디자인할 때 고려하는 여러 가지 개념 간의 관계를 보여주고 있습니다.

특히, 소유권을 증명하는데 있어서는 단순히 자산과 소유자의 매핑 뿐만 아니라 식별도 해야하고, 소유권을 사용하는데 있어서는 식별 뿐 아니라, 인증과 승인의 과정도 필요합니다.


이러한 식별과 인증, 승인은 보안의 개념으로 사용되는데 이에 대해서 조금 더 자세히 이해해야 합니다.


1. 식별(Identification)

식별이란 이름 또는 다른 식별자를 사용해 '누구'라고 주장하는 것이다. 하지만 식별은 누구라고 주장된 사람과 주장한 사람이 일치하는지는 증명하지 못합니다. 즉, 식별은 단순히 '누구'라고 주장하는 것을 의미합니다.


2. 인증(Authentication)

인증의 목적은 어떤 사람이 다른 누군가를 사칭하는 것을 방지하기 위함입니다. 인증이란 당신과 당신이라고 주장한 누군가가 서로 일치하는지 증명하는 것입니다.

이때 중요한 건 주장하는 바를 증명해주는 것은 그 사람만의 고유한 무엇이어야 한다는 점입니다.


3. 승인(Authorization)

승인은 식별된 사람의 성질과 특성에 기반해 특정 자원이나 서비스에의 접근을 허가해 주는 것을 의미합니다. 승인은 성공적인 인증과 함께 인증된 특정인이 가진 특성과 권리에 대한 평가를 토대로 얻는 최종 결과입니다.



3. 원장은 소유권을 증명하기도, 이전하기도 한다.


원장은 단순히 하나의 기능을 하는 것이 아니라, 두 가지 상반된 역할을 수행합니다. 하나는 원장에서 읽은 과거 데이터를 이용하여 소유권을 증명해주는 역할이고, 다른 하나는 소유권의 이전이 발생한 경우 원장에 새로운 데이터를 생성하여 이 사실을 문서화해 두는 역할입니다.


만약 원장이 누구에게나 공개되어 있다면 소유권 증명은 훨씬 쉬워집니다. 그러나 소유권 이전은 법적등의 권리를 가진 특정인에게만 배타적으로 허가되어야 합니다. 따라서 소유권 이전의 기초에는 개인정보 보호가 필요합니다.

원장에 쓴다는 것은 소유권이 변경되었다는 의미이므로 상당히 신뢰할 수 있는 개체에게만 쓸 수 있는 권한이 주어져야 합니다.

그리고 이러한 원장은 블록체인에서도 찾아볼 수 있습니다. 블록체인은 누구나 읽을 수 있게 개방된 원장과 유사한 데이터 구조를 가지는 거대한 분산 P2P 시스템입니다.



4. 소유권 관리자, 블록체인


만약 위에서 이야기한 것과 같은 원장이 손상되거나 파괴되면 어떻게 될까요? 또는 원장을 갱신하는 담장자가 실수를 하거나 고의로 위조하면?

이러한 경우 원장은 더 이상 진실을 반영하지 않게 됩니다. 원장의 내용이 진실이라고 믿고있는 이들에게 이것은 재난과도 같은 일 입니다.


원장 하나에만 의존해 소유권을 판정하는 문제는 법정에서 여러 명의 목격자에게 증언을 듣는 것과 비슷한 방식으로 해결할 수 있습니다. 

즉, 조작될 위험이 있는 원장을 하나만 유지하는 대신 원장의 순수 분산 P2P 시스템을 이용하여 다수의 노드가 동의하는 진실을 통해서 소유권을 확인하면 되는 것이죠.


그래서 결국, 소유권 관리를 위해 사용된 개별 원장은 소유권 관련 데이터를 저장하기 위해 사용된 블록체인-데이터-구조 하나와 같습니다. 즉, 개별 원장들은 P2P 시스템의 개별 컴퓨터(노드)에 저장됩니다.

이에 따라서, 블록체인-알고리즘은 개별 노드들이 최종 판결의 기초가 되는 하나의 일관된 소유권 상태에 집단적으로 도달하게 해줍니다. 

그리고, 그 과정 중 식별, 인증, 승인, 데이터 보안을 믿을 수 있는 수단으로 만들기 위해서 암호화 기법이 필요합니다.



이렇게 이번에는 소유권에 대해 그 본질을 알아보는 시간을 가졌습니다.

다음 포스팅에서는 분산 P2P 시스템에서 무결성을 침해와 가장 관련된 문제 중 하나인 이중사용 문제에 대해서 알아보겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


이전글

#1_블록체인 무엇인가::소프트웨어 시스템 아키텍처

#2_블록체인 무엇인가::분산 P2P 시스템



안녕하세요. 문범우입니다.

지난번 포스팅을 통해 분산 P2P 시스템에 대해서 알아보고, 실제로 많은 사람들이 사용하는 토렌트 서비스를 통해서 이해해 보았습니다.

그럼 이번 포스팅에서는 이러한 분산 P2P 시스템을 왜 아직 많은 곳에서 사용하지 않는지, 그리고 그것을 블록체인이 어떻게 해결해 줄 수 있는지에 대해서 알아보며 블록체인에 대해 정의를 내려보도록 하겠습니다.


1. 순수 분산 P2P 시스템의 지속 가능성


사실 우리는 두번째 포스팅에서 순수 분산 P2P 시스템이 산업 전체를 뒤바꿀 수 있을 만큼 강력한 잠재력을 지니고 있다고 알아보았습니다. 그런데 왜 아직 많은 곳에서 사용되지 않는 것 일까요?

즉, 순수 분산 P2P 시스템이 산업 전반에 사용되기 위하여 해결해야 할 주요과제는 무엇일까요?


P2P 시스템에 대한 지속 가능성은 우리가 첫번째 포스팅에서 알아보았던 개념, 신뢰와 무결성에 달려 있습니다.

소프트웨어 시스템의 관점에서 무결성은 시스템의 안전성, 완결성, 일관성, 정확성 및 변형과 오류 없음을 의미하는 비기능적 측면이고, 신뢰란 별도의 증거나 증명 또는 조사 과정 없이도 누군가 또는 무엇인가의 신뢰성, 진실성, 능력을 믿어주는 확고한 신념을 의미합니다.


즉, 사용자들은 P2P 시스템에 대해 일단 시스템에 합류를 하고 시스템에 기여합니다. 이후 지속적인 상호작용에 대한 결과가 기대했던 바와 같으면 더 큰 신뢰가 쌓여가면서 지속적으로 시스템의 구성원으로 남게 됩니다. 이렇게 사용자들의 기대를 충족시키며 시스템에 대한 신뢰를 강화시키기 위해서는 무엇보다 시스템의 무결성이 필요합니다. 

다시 말해, 시스템에 대한 무결성이 확보되지 않는다면 시스템은 사람들에게 신뢰를 잃어갈 것이며, 결국 사용자가 떠나는 문제가 발생하게 됩니다.


그렇다면, 우리가 순수 분산 P2P 시스템의 존립과 직결된 신뢰, 무결성에 대한 중요성을 이해했다면 다음과 같은 질문을 생각해볼 수 있습니다.


"순수 분산 P2P 시스템의 무결성을 확보하고 유지할 수 있는 방법은 무엇일까?"


순수 분산 P2P 시스템의 무결성을 확보하고 유지하는 일은 여러가지 요인에 달려 있지만 가장 중요한 두가지는 다음과 같습니다.


- 전체 노드 또는 피어의 개수를 아는가?

- 각 피어의 신뢰성에 대해 어느 정도 알고 있는가?


분산 P2P 시스템 내의 전체 노드 개수와 각 노드의 신뢰성을 알고 있다면 무결성을 확보할 가능성은 더 커집니다. 최악의 환경은 시스템에 참여한 노드의 개수도 모르고 각 노드의 신뢰성도 전혀 모르는 경우입니다. 모두에게 개방된 순수 P2P 시스템을 인터넷 상에서 운영하는 경우가 바로 그 최악에 해당 하는 것이죠.



2. P2P 시스템의 무결성을 위협하는 요소


그렇다면, P2P 시스템에서 우리가 중요하다고 이야기하는 무결성을 위협하는 요소는 또 무엇이 있을까요?


1. 기술적 결함

P2P 시스템은 인터넷으로 통신하는 사용자들의 개별 컴퓨터로 구성됩니다. 그런데 컴퓨터를 비롯한 모든 전자기기는 언제든지 고장이나 오류가 발생될 수 있습니다. 즉, 모든 분산 시스템에서는 개별 컴퓨터를 비롯하여 네트워크 장비 등이 고장이나 오류가 발생했을 때에 대한 대처가 가능해야 합니다.


2. 악의적 피어

P2P 시스템에서 무결성을 위협하는 두번째 요소는 악의적인 의도를 가진 사용자입니다. 이 요소는 첫번째와 같은 기술적 원인이 아니라, 시스템을 이용해 자신 개인의 이득을 취하려는 악의가 원인입니다.

부정직하고 악의적인 피어는 P2P 시스템의 근간인 신뢰성을 공격하려 하기 때문에 가장 심각한 위협 요소 입니다. 이러한 위협으로 인해 P2P 시스템 내의 사용자들이 다른 피어를 믿지 못하게 된다면 시스템을 떠나게 되고 더 이상 계산자원에 기여하지 않게 됩니다. 결국 전체 시스템 구성원이 감소되고 이로 인해 시스템의 효용성이 저하되며 또 다른 이탈자가 반복되는 악순환이 형성될 수 있습니다.



3. 블록체인, 무결성을 확보하라.


사실 위에서 이야기 한 것과 달리 최고의 상황, 최적의 상황에서 신뢰와 무결성을 확보하여 시스템을 유지하는 것은 어렵지 않습니다. 하지만 실제로 우리가 해야되는 것은 위에서 나온 것들을 바탕으로 한 최악의 조건을 가진 분산 시스템에서 신뢰와 무결성을 확보하는 점 입니다.

그리고 바로 이것이 블록체인이 해결해야 하는 과제 입니다.

즉, 블록체인이 해결해야 되는 문제는 '개수도 알려져 있지 않고 신뢰성과 안정성도 알 수 없는' 피어들로 구성된 순수 분산 P2P 시스템의 무결성을 확보하고 유지하는 것 입니다.



4. 그래서 '블록체인' 이란?


그래서 도대체 '블록체인'이 무엇일까요?

사실 블록체인은 다양한 의미로 사용될 수 있습니다.

먼저 4가지 다른 의미에 대해서 간략하게 알아보도록 하겠습니다.


1. 데이터 구조의 명칭

컴퓨터 과학이나 소프트웨어 공학에서 말하는 데이터 구조(data structure)란, 구체적인 정보나 내용과 상관없이 데이터를 정리하는 방식을 이야기 합니다. 

데이터 구조는 간단하게, 건물 설계도의 평면도 쯤으로 생각해볼 수 있습니다. 평면도는 공간의 구체적인 용도와 상관없이 벽과 바닥 그리고 계단을 사용하여 공간을 분리되기 때문 입니다.

블록체인이 데이터 구저의 명칭으로 사용될 때에는 블록이라 불리는 단위에 모인 모든 데이터를 지칭합니다. 그리고 이 블록들은 책을 구성하는 페이지들과 유사하게 마치 체인처럼 서로 연결되어 있어서 블록체인이라는 이름이 붙었습니다.


2. 알고리즘의 명칭

소프트웨어 공학에서 알고리즘(algorithm)이란 컴퓨터가 실행해야 할 일련의 명령어들을 의미합니다. 그리고 이 명령어들은 대개 데이터 구조를 포함합니다.

블록체인이 알고리즘의 명칭으로 사용될 때에는 순수 분산 P2P 시스템에서 여러 블록체인 데이터 구조 내의 정보 내용을 민주주의 투표 방식과 비슷한 방법을 써서 서로 협상하는 일련의 명렁어를 의미하는 것 입니다.


3. 기술묶음의 명칭

블록체인이 기술 묶음의 명칭으로 사용될 때에는 블록체인 데이터 구조(blockchain-data-structure), 블록체인 알고리즘(blockchain-algorithm), 암호화 및 보안 기술의 조합을 의미하게 됩니다.

이들의 조합은 응용분야와 상관없이 순수 분산 P2P 시스템의 무결성을 확보하는데 이용될 수 있습니다.


4. 일반 응용분야를 가지는 순수 분산 P2P 시스템을 포괄하는 용어

블록체인은 블록체인 기술묶음을 활용하는 거래장부들의 순수 분산 P2P 시스템을 지칭하는 포괄적인 용어로도 사용됩니다. 

즉, 순수 분산 시스템을 구성하는 한 부분인 소프트웨어의 단위를 의미를 이야기하는 것이 아니라 순수 분산 시스템 전체를 의미합니다.


그리고 우리가 이어서 블록체인에 대한 이야기를 할 때, 위에서 알아본 4가지 의미 중 4번째인, 순수 분산 P2P 시스템 전체를 의미하는 용어로 블록체인이라는 단어를 사용합니다.


그럼, 아직 중요하게 알아볼 내용들이 많지만 임시적으로 블록체인에 대한 정의를 내려보면 다음과 같습니다.


블록체인이란 무결성을 확보하고 유지하기 위해 순서에 따라 연결된 블록들의 정보 내용을 암호화 기법과 보안기술을 이용해 협상하는 알고리즘으로 구성된 소프트웨어 요소를 활용하는 원장(거래장부)의 순수 분산 P2P 시스템을 의미한다.



5. 비트코인 기술이 블록체인의 전부는 아니다.


위에서 임시적으로 정의한 내용에서 비트코인(Bitcoin)이나 암호화폐(Cryptographic money)에 대한 어떠한 언급도 존재하지 않습니다.

사실 많은 기사나 읽을거리에서 블록체인의 목적이 디지털 화폐의 소유권을 관리하기 위한 것으로 기술하고 있는데, 이렇게 암호화폐의 소유권을 관리하는 것은 아주 중요하고 자연스러운 블록체인의 응용분야 중 하나일 뿐이며 그 자체가 블록체인의 전부는 절대 아닙니다.


블록체인은 다양한 분야에 폭넓게 응용될 수 있습니다. 그럼에도 블록체인에 따라 암호화폐, 디지털화폐 등에 대한 소유권 관리 측면이 부각되는 이유는 두가지가 있습니다.

첫번째, 이해하기도 설명하기도 가장 쉽기 때문입니다.

두번째는 경제에 가장 크게 영향을 끼치는 실 사례이기 때문입니다.


블록체인을 원장(거래장부)의 분산 P2P 시스템을 관리하는 기술묶음의 용도로 활용하게 된다면 디지털 재화의 소유권 관리나 암호화폐와 같은 특별한 분야에 사용할 수 있습니다. 그러나 우리가 알아볼 때에는 이렇게 특정 분야만 고려하지 않지만, 블록체인을 더 쉽게 이해하도록 특정 재화와 상관없이 소유권을 관리하고 명료화하는 일반적인 응용 예에 대해서만 다룰 것 입니다.



이렇게 순수 분산 P2P 시스템이 유지되기 위해 필요한 점, 그리고 그것을 위협하는 요소들에 대해서 알아보고 이어서 블록체인이라는 용어에 대해 알아보며 임시적인 정의를 내려보았습니다. 그리고 비트코인 기술이 블록체인에 대해 보다 쉽게 이해하기 쉬운 사례일 뿐임을 말씀드렸습니다.

이후 포스팅에서는 우리가 블록체인에 대해 본격적으로 이해하기 위해 먼저, 소유권이라는 본질에 대해서 알아보도록 하겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc


이전글

#1_블록체인 무엇인가::소프트웨어 시스템 아키텍처



안녕하세요. 문범우입니다.

지난 첫번째 글에서 '소프트웨어 시스템 아키텍처'에 대해서 알아보았습니다. 그 중에서도 블록체인이 도구로서 활용될 분산 시스템에 대해서 주로 알아보았습니다.

그리고 이번 포스팅에서는 분산 시스템 중에서도 특수한 형태로 나타난 '분산 P2P 시스템'에 대해서 알아보도록 하겠습니다.




1. 분산 P2P 시스템이란


피어 투 피어(peer - to - peer) 시스템은 분산 시스템의 특수한 형태입니다. P2P 시스템에서는 개별 컴퓨터(노드)로 구성되어 있으며 분산 시스템이기 때문에 중앙 노드의 조정 없이 네트워크의 모든 구성원이 서로에게 계산 자원을 제공합니다.

무엇보다 중요한 것은 네트워크 상에서 각 노드는 시스템 내에서 동등한 권리와 역할을 가집니다. 즉, 모든 노드가 자원의 공급자인 동시에 소비자가 됩니다.

쉽게 생각해보면 많은 사람들이 사용하고 있는 '토렌'를 생각해볼 수 있습니다.

토렌트또한 개방형 P2P 시스템으로써, 동일한 네트워크에 참여한 모든 노드가 소비자로서, 피어의 역할을 하게 되며 공급자로서 시드의 역할도 하게 됩니다.


추가로 보다 세부적인 내용에 대한 설명은 아래 블로그들을 참고하시면 좋을 것 같습니다. 아무래도 블록체인과 토렌트의 네트워크 방식이 동일하기 때문에 관련되어 설명하는 부분들이 많습니다. 만약 블록체인과 관련된 내용에 대해 이해하기 어렵다면 무시하시고, 토렌트에서 사용되는 P2P 네트워크에 대해서만 이런거구나 하는 느낌으로 이해하시면 좋을 것 같습니다.

토렌트를 알아보자

토렌트 개념잡기

토렌트와 블록체인


그 내용을 대략적으로 이해해본다면, P2P 네트워크 상에는 더 많은 사용자가 네트워크에 참여할수록 네트워크는 더 거대해지고 더 강력해집니다. 토렌트를 사용해보신분들도 있겠지만 많은 사람들이 다운받으려고 하는 최신 파일을 다운 받을때는 정말 빠른 속도로 다운받을 수 있죠.(물론 우리나라에서는 저작권등의 문제로 불법입니다!)

하지만 토렌트의 단점으로는 오래되거나 사람들에게 관심없는 파일의 경우에는 파일의 조각을 공급해주는 시더가 없기 때문에 다운받는 속도가 느립니다. 그리고 이것이 블록체인과 토렌트의 차이이기도 합니다. 추후에도 알아보겠지만 블록체인에서는 이러한 문제를 막기위해, 시더의 존재를 유지하기 위해 '채굴'이라는 개념이 존재합니다.



2. P2P 네트워크의 잠재력


사실 P2P 네트워크는 과거에도 존재했으며, 특정 산업에 대한 변화도 이끌어내었습니다. 대표적인 것은 바로 음악산업입니다.

요즘은 음악을 듣기 위해 CD를 사기보다 MP3 파일을 공유하는 스트리밍 서비스를 주로 이용합니다. 이런 변화는 사람들이 각자 가지고 있는 음악 파일을 서로 공유할 수 있는 소프트웨어의 등장으로 가능해졌습니다. 그리고 그것의 시작은 냅스터(Napster) 서비스 이었으며 냅스터의 공동 창업자 숀 패닝(Shawn Fanning)은 다음과 같은 말을 하였습니다.

"이 시스템의 어떤 점이 그렇게 흥미로운가 하면, 바로 동료들과 상호작용한다는 점이다. 길거리 사람들 그 누구와도 서로 정보를 주고받을 수 있다."


음악산업은 과거에 다음과 같이 작동하였습니다. 먼저 음악가와 스튜디오가 계약을 맺습니다. 계약이 성사된 후에, 스튜디오는 음악가의 노래를 녹음하고 CD와 테이프와 같은 다양한 매체에 담아서 이를 판매하였습니다. 즉, 스튜디오는 결국 음악가와 음악을 듣고자하는 소비자 사이에서 중개자 역할을 수행하였습니다.

이렇게 스튜디오가 중개자 역할을 할 수 있었던 이유는 음반 제작, 마케팅, 판매채널등에 대한 전문적인 지식을 보유하였기 때문입니다. 그러나 2000년 이후에 스튜디오 환경은 급격히 변화되었습니다.

음악의 디지털화, 저렴한 녹음시설 및 개인 PC의 보급, 인터넷의 등장은 사실상 음악 스튜디오가 사람들에게 필요없게 된 배경입니다. 이전에 스튜디오가 주로 하던 음반 제작, 마케팅, 판매채널에 대한 전문적인 지식의 장벽이 낮아짐에 따라 작곡가나 소비자 스스로가 해결할 수 있게 되었기 때문이죠.

즉, 냅스터는 중개자로서의 음악 스튜디오를 대체하는데 주된 역할을 수행한 것입니다.

냅스터의 등장으로 음악을 듣고자 하는 소비자들은 CD를 구입하지 않아도 최신 인기곡을 들을 수 있게 되었고, 다양한 사람들과 음악 파일을 공유할 수 있게 되었습니다. 스튜디오 산업에는 큰 타격을 입히게 되었지만 결국적으로 음악 소비자들은 이전에 경험하지 못한 폭넓은 음악 세계를 접하게 되었습니다.


이와 같이 P2P 네트워크는 거의 모든 산업을 뒤흔들 잠재력을 가지고 있습니다.

최소한 무형의 상품이나 디지털화 된 상품 또는 서비스를 중개하는 역할을 주업으로 하는 산업은 거의 모두 P2P로 대체될 가능성이 높은 것이죠. 그리고 우리 주변에 이런 종류의 산업중 가장 크게 다가오는 것은 금융업입니다.


은행계좌나 신용카드, 직불카드에 들어있는 것은 결국 무형의 비트와 바이트, 즉 디지털 정보입니다. 즉 이 세상의 대부분의 돈과 자산은 무형의 비트와 바이트 형태로 금융회사의 중앙 정보 기술 시스템에 저장되어 있습니다.

은행을 비롯한 금융계의 많은 회사들은 돈과 재산을 나타내는 비트와 바이트를 생산하고 소비하는 사람들 사이를 단순히 이어주는 중개자 역할을 주로 수행합니다. 우리가 돈을 빌리고, 빌려주는 등의 행위는 사실 중개자가 무형의 상품을 시스템 속에서 대상자에게 전달함으로 이루어집니다. 실질적으로 이용하는 우리는 느끼지 못하지만 간단한 거래하나에도 많은 중개자가 관여하게 됩니다.

'블록체인 무엇인가?'의 책에서 이야기하기로는 국가간의 은행 자금이체의 과정에서는 5개의 중개기관이 관여하게 되며 각 처리단계마다 일정 시간이 소요되며 해당 비용을 청구하게 됩니다. 하지만 P2P 거래에서는 동일한 행위가 훨씬 간단하며 시간과 비용도 거의 들지 않습니다.


즉, 중앙 통제 시스템과 비교하여 P2P 시스템이 가진 장점으로는, 중개자를 통해 간접적으로 상호작용하지 않고 거래 당사자끼리 직접 상호작용한다는 점이며 그 과정속에서 처리 시간과 비용이 현저하게 줄어든다는 점 입니다.



3. P2P 시스템과 블록체인의 연관성


그래서, 이렇게 좋은 P2P 시스템과 우리가 알고자하는 블록체인은 정말 무슨 연관이 있는 것 일까요?

다시한번 P2P 시스템에 대해 결론을 내려보면서 블록체인과의 연관성을 알아보겠습니다.


1. P2P 시스템의 정의

P2P 시스템은 여러 노드(개별 컴퓨터)로 구성된 분산 소프트웨어 시스템으로, 한 노드의 자원(계산 능력, 저장 공간, 정보 배분 등)을 다른 노드들이 직접적으로 사용할 수 있다는 특징을 가집니다. 따라서 모든 사용자의 컴퓨터는 자원의 공급자인 동시에 소비자가 됩니다.


2. P2P 시스템의 아키텍처

P2P 시스템은 구조 자체가 분산 컴퓨터 시스템으로 되어 있습니다. 하지만 여전히 중앙 통제 요소를 가지는 P2P 시스템도 존재합니다. 중앙 통제 P2P 시스템은 중앙 노드를 이용하여 노드 간 상호작용을 중재하고, 피어 노드가 제공하는 서비스 목록들을 유지 관리하고 노드를 검색하며 식별합니다. 이러한 중앙 통제 P2P 시스템의 대표적인 예는 위에서 이야기한 냅스터입니다. 냅스터는 중앙 데이터베이스에 접속한 모든 노드와 각 노드가 보유한 노래 정보를 저장하고 있습니다.

반면 순수 분산 P2P 시스템에는 중앙에서 통제하거나 조정하는 어떠한 요소도 없습니다. 따라서 시스템의 모든 노드는 동일한 과제를 수행하며, 자원과 서비스의 생산자인 동시에 소비자 역할을 수행합니다.


3. P2P 시스템과 블록체인의 연관성

결론부터 이야기하면, 블록체인은 분산 시스템에서 무결성을 확보하고 유지하는 도구입니다. 즉 순수 분산 P2P 시스템은 무결성의 확보와 유지를 위해 블록체인을 도구로서 활용합니다.


즉, 사람들은 전체 산업을 통째로 뒤바꿀 수 있는 장점을 가진 순수 분산 P2P 시스템이 블록체인을 활용하여 무결성을 확보하고 유지할 수 있다는 점 때문에 블록체인에 대해 열광합니다. 그러나 엄밀히 이야기하면 사람들을 정말로 흥분시킨 요소는 '탈중개화'입니다. 즉, 블록체인은 단지 탈중개화를 위한 도구일 뿐입니다.


다시 한번 정리한다면, 사람들이 블록체인에 열광하는 이유는 탈중개화를 통해 전체 산업 생태계를 변화시킬 잠재력을 지닌 순수 분산 P2P시스템이 무결성의 확보와 유지를 위한 도구로 블록체인을 사용할 수 있기 때문입니다.



이렇게 해서 분산 P2P 시스템에 대해서 알아보았습니다.

다음 포스팅에서는 본격적으로 블록체인에 대해서 포커싱을 두며 '왜 우리에게 블록체인이 필요한가', 즉 블록체인이 해결해야 하는 문제점들과 그 문제점을 해결하는 것이 왜 중요한지등을 알아보며 이야기를 해보겠습니다.

추가적으로 궁금하거나 의문이 드는 점, 잘못된 내용들에 대한 피드백은 언제든지 댓글이나 메일, 카톡을 통해서 말씀해주시면 감사하겠습니다.



블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc



안녕하세요. 문범우입니다.

앞으로 몇회에 걸쳐서 블록체인에 대한 기초적인 내용을 정리해보려 합니다.

단순히 자료를 수집해서 정리해보기에는 아직 제 스스로도 개념적으로 부족한 부분들이 많아서, 다니엘 드레셔 지음, 이병욱 옮김의 '블록체인 무엇인가?' 라는 책을 기반으로 하려 합니다.


정리의 순서가 책의 순서와 비슷할 것이며, 책을 보면서 좀 더 궁금한 내용 같은 부분은 온라인을 통해 공부해가며 추가하여 정리하려 합니다.


궁금하거나 건의사항이 있으신 분은 언제든지 댓글 또는 이메일, 카톡을 통해서 연락주시면 감사하겠습니다.


블록체인을 위한 기초


이번 글에서는 블록체인을 이해하기 위한 기초로써, 소프트웨어 아키텍처에 대해 알아보면서 블록체인이 달성하고자 하는 것에 대해서 함께 알아보도록 하겠습니다.


1. 소프트웨어 아키텍처


소프트웨어 아키텍처를 알아보기 이전에 시스템 자체를 개념적으로 분리하기 위해 사용되는 구분 기준이 있습니다. 크게 두가지로 나뉘어지는데 다음과 같습니다.


1. 응용계층 - 구현계층

2. 기능적 측면 - 비기능적 측면


먼저 응용계층과 구현계층에 대해서 알아봅니다.

사용자의 요구사항과 시스템의 기술 구조를 구분하여 생각해보면 이 둘을 나누어 생각할 수 있습니다.

즉, 응용계층은 사용자의 요구사항, 사용자의 필요와 연관됩니다.

반면에 구현계층은 이러한 요구사항을 실현하는 것 입니다. 즉 구현계층의 구성요소는 본질적으로 기술적이며, 목적 달성을 위한 수단으로 생각될 수 있습니다.


두번째로 기능적 측면과, 비기능적 측면에 대해서 알아보겠습니다.

먼저 기능적 측면은 '시스템이 무엇을 하는가'로 구분되며 비기능적 측면은 '그 무엇을 어떤 식으로 하는가'로 구분됩니다. 

해당 부분이 헷갈릴 수 있기 때문에 핸드폰을 예로 들어 생각해본다면, 기능적 측면으로는 음악 청취, 사진 촬영, 사진의 개별 픽셀 조작 등이 있으며 비기능적 측면으로는 멋진 UI, 실행속도가 빠른 소프트웨어, 사용자 데이터 보호와 저장능력 등이 있습니다. 또한 비기능적 측면에서 중요시 되는 것은 보안과 무결성입니다. 여기서 무결성은 시스템이 의도한 대로 작동하는 것을 의미합니다. 무결성은 보안과 정확성을 포함한 개념이기도 합니다.


이렇게 두가지로 나누어 본 개념들을 함께 고려하여 핸드폰을 예시로 생각해본다면 다음 표와 같습니다.


 

 기능적 측면

 비기능적 측면

 응용 계층

 사진 촬영

 전화 걸기

 이메일 보내기

 인터넷 검색

 문자 메시지 보내기

 보기 좋은 UI

 사용 편의성

 빠른 메시지 전송

 구현 계층

 사용자 데이터 저장

 가장 가까운 모바일 커넥터에 연결

 디지털 카메라의 픽셀에 접근

 효율적인 데이터 저장

 에너지 절약

 무결성 관리

 개인정보 보호


이렇게 응용계층과 구현계층, 기능적 측면과 비기능적 측면으로 핸드폰이라는 시스템을 분리하여 생각해보았습니다.

이중에서 구현 계층의 비기능적 측면인 무결성 관리에 대해서 한번 더 알아보겠습니다.


무결성이란 모든 소프트웨어 시스템이 가지는 중요한 비기능적 측면으로 주로 다음과 같은 세가지 구성요소로 이루어집니다.


데이터 무결성: 시스템에서 사용하고 유지 관리하는 데이터는 완전하고 정확하며 모순이 없다.

작동 무결성: 시스템은 의도한 대로 작동하며 논리적 오류가 없다.

보안: 시스템은 허가받은 사용자에게만 데이터 및 기능에 대한 접근 권한을 부여할 수 있다.


실제로 많은 소프트웨어 이용자들은 무결성이라는 개념을 당연시하게 여깁니다. 그들이 사용하는 소프트웨어들이 다행히 무결성을 잘 지키고 있기 때문입니다. 하지만 실제로 이러한 무결성을 개념을 잘 지키기 위해서 개발자들에 대한 노력은 매우 크게 필요합니다. 만약 핸드폰에서 카카오톡을 실행시켰는데 인터넷 어플이 실행된다던지의 시스템 오류가 발생하면 안될테니까요.



2. 시스템 아키텍처


이렇게 해서 소프트웨어 아키텍처를 개념적으로 분리해서 나누어보았습니다.

이번에는 소프트웨어 아키텍처를 구현하는 다양한 방법 중에서 필수적으로 결정해야 하는 시스템 아키텍처에 대해서 알아보겠습니다.

여기서 시스템 아키텍처란, 구성요소를 구조화하고 구성요소 간 관계를 설정하는 방식을 의미합니다.

소프트웨어 시스템에 주로 사용되는 아키텍처는 크게 두가지로, 중앙 통제(Centralized) 방식과 분산(Distributed) 방식이 존재합니다.



위의 사진에서 좌측이 중앙 통제 시스템이며 우측이 분산 시스템입니다.

사진에서 확인할 수 있듯이 중앙 통제 시스템에서는 중앙의 하나의 노드(컴퓨터)가 모든 노드와 연결되어 있습니다. 반면에 분산형에서는 그렇지 않고 모든 노드가 서로 연결되어 있습니다.


이후에 보다 자세히 설명드리겠지만 실제로 현재 사회에서의 대부분의 시스템은 중앙 통제 시스템이지만, 블록체인은 분산 시스템을 가능하게 합니다.

그럼 블록체인에 앞서서, 분산 시스템 자체에 대한 장단점을 살펴보도록 하겠습니다.



3. 분산 시스템


먼저 분산 시스템의 장점에 대해서 알아보겠습니다.


1. 계산 능력이 더 뛰어나다.

분산 시스템에서의 계산 능력(Computing power)은 서로 연결된 모든 노드(컴퓨터)의 계산 능력이 합쳐져 발현됩니다. 즉, 분산 시스템에서는 대부분 단일 컴퓨터보다 강력한 계산 능력을 가질 수 있게 됩니다.


2. 비용이 절감된다.

분산 시스템에서는 여러 대의 컴퓨터로 구성되기 때문에 초기 비용은 개별 컴퓨터보다 더 많이 들 수 있습니다. 하지만 슈퍼 컴퓨터 하나에 대해 유지 보수하는 비용과 비교했을 때는 분산 시스템의 비용이 더 절감됩니다.

또한 분산 시스템에서는 개별 컴퓨터가 교체될 때 전체 시스템에 큰 영향을 끼치지 않는 점까지 고려하면 더욱 그렇습니다.


3. 더 안정적이다.

위에서 짧게 이야기 했듯이 분산 시스템에서는 개별 노드(컴퓨터)가 교체될때 전체적인 시스템의 안정성에 영향을 미치지 않습니다. 하나의 구성요소가 없거나 오류가 발생되면 다른 요소가 그 일을 대신하게 되기 때문입니다.


4. 자연스럽게 확장된다.

분산 시스템에서는 더 많은 노드(컴퓨터)를 자연스럽게 확장시킬 수 있습니다. 초기부터 그러한 것을 고려되어 설계 및 운영되기 때문에 추가적인 계산 능력을 필요로 하는 등의 상황에서 추가적인 노드를 자연스럽게 추가할 수 있습니다.



이번에는 분산 시스템의 단점에 대해서 알아보도록 하겠습니다.


1. 조정 오버헤드가 발생한다.

분산 시스템에서는 구성요소들을 조정하는 중앙요소가 없습니다. 따라서 각각의 모든 요소가 스스로 조정을 해야하는데 모두가 동등한 지위를 가지고 있기 때문에 이것이 쉽지 않고 모든 요소가 조정을 하는 작업을 필요로 하기 때문에 자원이 소모되며 그로 인해 조정 오버헤드(Coordination overhead)가 발생됩니다.


2. 통신 오버헤드가 발생한다.

조정을 위해서는 서로의 통신이 필요합니다. 따라서 분산 시스템 내 모든 요소들은 서로 통신을 주고 받습니다. 이로 인해 계산 능력의 일부가 통신 프로토콜 지원과 메시지의 송수신 및 처리에 소모됩니다. 결과적으로 통신 오버헤드(Communication overhead)가 발생합니다.


3. 네트워크 의존도가 높다.

위에서 이야기 했듯이 분산 시스템에서는 모든 요소들이 통신을 하게 되며, 그 통신은 네트워크를 통하게 됩니다. 그러나 거의 모든 네트워크에는 자체적인 결함과 장애 가능성이 내재될 수 밖에 없으며 이것은 결국 분산 시스템에서의 통신과 조정에 영향을 미치게 됩니다. 그렇다고 해서 네트워크를 사용하지 않으면 통신과 조정, 노드 간 협력도 불가하기 때문에 네트워크 의존도가 높습니다.


4. 프로그램이 복잡해집니다.

앞에서 이야기 하였듯이 분산 시스템에서는 노드간 조정과 통신이 이루어집니다. 또한 네트워크적인 문제도 발생될 수 있기 때문에 이 모든 것을 해결하기 위해서 소프트웨어가 복잡해 집니다.


5. 보안에 신경써야 한다.

네트워크를 통해 자원 및 정보를 주고받게 되면 악의를 가진 개체가 접근하는 보안 문제를 고려해야 합니다. 그러므로 모든 분산 시스템은 보안에 있어 철저히 대비해야 합니다.


물론 이렇게 알아본 분산 시스템의 장점과 단점을 모은 혼합시스템도 존재합니다.

실질적인 블록체인 응용을 배우기 위해서는 이 부분을 꼭 이해해야 합니다. 혼합시스템은 크게 두가지로 존재합니다.

분산 시스템 내의 중앙 통제와 중앙 통제 시스템 내의 분산 시스템입니다.



좌측과 같은 시스템은 얼핏 보기에 모든 구성요소들이 분산 시스템을 이루는 것처럼 보이지만 사실 모든 원이 중앙의 큰 원에 직접 연결되어 있습니다. 즉 겉보기에는 분산시스템이지만 사실 중앙 통제 시스템입니다.

우측 사진은 이와 상반된 시스템을 보여줍니다.


이러한 혼합시스템에 대해서 고려하는 것은 매우 중요합니다. 이 때, 실제로 하나의 시스템이 분산 시스템인지를 파악하려면 전체 시스템을 동시에 종료할 수 있는 단일 구성요소, 즉 스위치가 있는지 살펴보면 됩니다.



이제 우리가 블록체인을 공부하기에 앞서 이러한 시스템을 왜 살펴보았는지 다시 생각해보아야 합니다.


실제로 중앙 통제 시스템과 분산 시스템은 단순히 하나의 목적을 위한 도구, 수단일 뿐 입니다. 두가지 시스템 모두 장단점이 있기에 더욱 그러합니다.

하지만 그 차이점 중에서, 앞에서 우리가 중요하게 다룬 '무결성'이라는 것에 대해서 두가지 시스템은 매우 다르게 접근합니다. 그리고 이 부분 때문에 블록체인이 중요해집니다.


블록체인은 분산 시스템이 무결성을 확보하게 해주는 도구입니다. 따라서 구현계층의 비기능적 측면을 성취하게 해주는 도구로 볼 수 있습니다.



이렇게 블록체인에 앞서, 소프트웨어 시스템에 대해 기본적인 개념을 살펴보았습니다. 다음 포스팅에서는 분산 시스템에서도 특수한 형태로 등장한 P2P 시스템에 대해서 알아보며 공부해보도록 하겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번에 소개해드릴 알고리즘 문제는, 2017년 카카오톡 블라인드테스트 1차 코딩시험에서 나왔던 문제중 난이도가 제일 낮다는 소개된 '비밀지도' 문제입니다.


해당 문제는 프로그래머스를 통해, 아래 주소에서 만나보실 수 있습니다.

https://programmers.co.kr/learn/courses/30/lessons/17681?language=python3


난이도가 가장 낮다고 소개된 만큼, 문제자체도 간단하고 풀이도 어렵지 않습니다.

따라서 해당 문제는 추가적인 설명대신 코드만 첨부해드리도록 하겠습니다.

추가적으로 궁금한 사항이 있으시면 언제든지 댓글 및 카카오톡이나 이메일을 통해서 연락주시면 바로 답변드리도록 하겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def solution(n, arr1, arr2):
    answer = []
    decode_arr1 = []
    decode_arr2 = []
    tmp_str = ''
    tmp_answer = ''
    for i in arr1:
        tmp_str = str(bin(i))[2:]
        while(len(tmp_str) < n):
            tmp_str = '0'+tmp_str
        tmp_str = tmp_str.replace('0',' ')
        tmp_str = tmp_str.replace('1','#')
        decode_arr1.append(tmp_str)
    for i in arr2:
        tmp_str = str(bin(i))[2:]
        while(len(tmp_str) < n):
            tmp_str = '0'+tmp_str
        tmp_str = tmp_str.replace('0',' ')
        tmp_str = tmp_str.replace('1','#')
        decode_arr2.append(tmp_str)
    
    for i in range(n):
        for j in range(n):
            if (decode_arr1[i][j] == '#'or (decode_arr2[i][j] == '#'):
                tmp_answer += '#'
            else:
                tmp_answer += ' '
        answer.append(tmp_answer)
        tmp_answer = ''
    return answer
cs


블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc