이 그림은 비트코인의 동작을 한 페이지에 정리한 모습을 나타낸다.맨 왼쪽에는 블록체인이 존재한다.제네시스 블록 (높이가 0인 블록) 부터 그 위로 하나씩 블록을 차곡 차곡 쌓으면서 블록 체인이 형성된다.비트코인을 사용한 거래가 발생하여 그에 대한 트랜잭션이 발생하면, 채굴자는 그 트랜잭션을 모아서 블록으로 만들고, 작업 증명에 성공하면 채굴된 블록을 발표한다.만약 이 블록이 다수의 사용자에 의해 받아들여지면 그 블록에 포함된 트랜잭션들은 다수에 의해 인정받는 유효한 트랜잭션이 된다.  비트코인의 트랜잭션은 위와 같이 생겼다.먼저 트랜잭션에는 input, output 부분이 있고, input 에는 비트코인이 빠져나갈 위치가 들어간다.(정확히는 나의 계좌의 최종 잔고를 나타내는 트랜잭션들이 들어간다.)out..

비트코인은 '통신 프로토콜' 이다.사카시 나카모토는 비트코인을 위해 컨센서스, 채굴, 비트코인 생성 방법, 트랜잭션과 같은 내용들을 프로토콜로 만들어 두었고, 비트코인 코어와 같은 소프트웨어가 프로토콜을 실제로 구현한 것과 같다.지금은 비록 사카시 나카모토는 빠졌지만 '비트코인 코어' 는 여전히 권위있는 프로그램이다.그래서 새로운 아이디어가 등장하면 먼저 코어 프로그램에 적용을 하고, 이후에 다른 버전 소프트웨어에도 적용된다. 비트코인 코어와 같은 프로그램을 다운받아서 실행하면, 코인이 생성이 되고, 이 코인을 하나의 어카운트에서 다른 어카운트로 보낼 수 있다.그리고 이 보내는 행위를 '트랜잭션' 이라고 한다.각각의 트랜잭션은 '블록' 에 기록이 되고, 이 블록들이 순서에 따라 연결된 것을 '블록체인' ..

암호학(Cryptology)은 비밀 통신과 관련된 과학 분야를 말한다.암호학은 크게 Cryptography 와 Cryptanalysis 로 분류된다.Cryptography는 암호를 만드는 것과 관련된 분야, Cryptanalysis 는 암호를 깨는 것과 관련된 분야이다.위 3개 개념을 통틀어서 Crypto 라고 부르기도 한다. 물론 암호학을 공부하는 사람은 이 두 분야를 모두 공부해야 한다.자신이 만든 암호화 알고리즘이 얼마나 공격에 강력한지 입증하려면 공격 수단에 대한 이해도 필요하기 때문이다. 암호학 분야가 달성하려는 목표는 4가지가 있다. 1. Confidentiality (기밀성)A가 B에게 메세지를 보낼 때, B 이외에는 아무도 이 메세지의 내용을 알 수 없도록 만드는 것현대에는 Symmetri..

Regular Language 의 특성 판별 어떤 regular language 에 임의의 문자열을 넣었을 때, 그 문장이 L에 포함되는지 안되는지 결정할 수 있는 알고리즘이 존재한다. 너무나도 당연한 말이다.왜냐하면 regular language 는 DFA를 통해 나타낼 수 있고, 이 기계에 문자열 w를 넣으면 이 문장이 L 에 속하는지 판별할 수 있기 때문이다. DFA는 곧 판별 알고리즘을 나타내는 것과 같으며, 이런 알고리즘을 가리켜 membership algorithm 이라고 한다.  standard representation 으로 나타낸 regular language 에 대해서, 이 언어 집합이 공집합, 유한집합, 무한집합 중 어떤 것에 해당하는지 판별하는 알고리즘이 존재한다. 1. 공집합 여부..

regular language는 수학적으로 문장의 집합이다.regular language는 DFA, NFA로 나타낼 수도, Regular expression 으로 나타낼 수도, Regular Grammar로도 나타낼 수 있다. 그렇다면 우리가 수학적으로 다룰 수 있는 언어는 레귤러 랭귀지가 전부일까?또한 레귤러 랭귀지에 대한 특정 연산에 대해서 닫힌 (closure) 연산이 존재할까? 어떤 연산이 닫혀있다는 것은 피연산자와 연산 후 결과의 집합이 같은 것을 말한다.예를 들어 두 정수를 더하면 그 결과 역시 정수이므로 정수는 덧셈에 대해 닫혀있다고 할 수 있다. 이번 글에서는 Regular Language 에 대해 Closure Properties 에 집중해서 정리해본다. 기본 연산에 대해  위 정리는 ..

Grammar 에 대해서 어떤 문법의 모든 production 이 A → xB 또는 A → x 형태로 작성된다면,이 grammar에 대해 right-linear 하다고 말한다. (A, B는 변수이고 x는 터미널이다.) 반대로 모든 production 이 A → Bx 또는 A → x 로 형태로 작성되면,이 grammar에 대해 left-linear 하다고 말한다. 이때 left-linear 또는 right-linear 한 grammar를 가리켜, Regular Grammar 라고 말한다.regular grammar는 프로덕션이 만드는 sentential form의 변수 개수가 1개 또는 0개라는 특징이 있다.  위 그림과 같은 2개의 문법을 보자.production 에 집중해서 보면,첫 번째 문법은 rig..

지난 글에서 DFA로 나타내는 언어는 regular language 이며, regular language 는 DFA로 나타낼 수 있다고 하였다.그런데 이 regular language 를 나타내는 방법 중 하나가 바로 regular expression 이었다. 따라서 위 그림과 같이, regular expression 은 DFA / NFA 로 나타낼 수 있고,반대로 DFA / NFA 가 나타내는 언어도 regular expression 을 통해 나타낼 수 있다. 이를 증명하려면, regular expression 이 나타내는 언어가 DFA가 만드는 언어의 superset 이고,반대로 DFA 가 만드는 언어가 regular expression 이 나타내는 언어의 superset 임을 보이면 된다.그러면 r..

지금까지 DFA에 대해서 정리하면서, DFA로 표현할 수 있는 언어를 regular language 라고 했었다.이때, 모든 NFA는 DFA로 변환이 가능하기 때문에 NFA로 표현할 수 있는 언어 역시 regluar language 였다.DFA로 표현가능한 언어가 regular language 라면, 거꾸로 regular language 는 DFA로 표현이 가능하다.  따라서 위 그림과 같은 관계가 성립한다.이번 글에서는 regular language를 나타내는 또 다른 방법인 regular expression 에 대해 정리해본다. regular expression 은 다음 3가지 내용으로 정의된다. 1. φ, λ, a ∈ Σ (알파벳에 포함되는 하나의 심볼) 3가지는 모두 regluar expressi..

다음 2개의 명제가 참인지 거짓인지 생각해보자. 1. DFA가 받아들이는 언어는 유일하다. (O)DFA가 받아들이는 (생성하는) 언어는 유일하다.(그리고 그 언어는 regluar 하므로, regular language 라고 할 수 있다.) 2. Regular Language 가 주어질 때, 이 언어를 만드는 DFA는 유일하다. (X)이 명제는 위 명제의 역인데, 이 명제는 틀렸다.하나의 언어를 받아들이는 (만드는) DFA는 여러개가 존재할 수 있다.같은 언어를 만들어내는데, 10개 state로 구성된 DFA를 만들 수도 있고, 20 state 로 구성된 DFA를 만들 수도 있다.따라서 이로부터 어떻게 하면 같은 언어를 만들더라도 최소한의 상태를 사용해서 만들 수 있을지 고민할 수 있다.   왼쪽의 DFA..

인덱스는 결국 레코드를 빠르게 식별하기 위해 레코드 정보인 rid 를 갖고 있는 추가적인 데이터이다.이 데이터 하나하나를 가리켜 '데이터 엔트리' 라고 부르며 이 정보드는 인덱스 파일에 저장되어 있다.인덱스 파일도 레코드를 저장하는 파일처럼 여러 인덱스 엔트리의 집합으로 구성되어 있고, '페이지' 로 구분된다. 이번에는 정렬되어 있는 데이터 엔트리 중에서 내가 찾으려는 데이터 엔트리를 빠르게 찾기 위한 방법을 정리해본다.데이터 엔트리를 빠르게 찾기 위해 데이터 엔트리를 특별한 방법으로 젖아할 수 있는데, 크게 트리 기반 인덱스와 해시 기반 인덱스로 나뉜다.이번 글에서는 먼저 트리 기반 인덱스에 대해 정리해본다. 트리 기반 인덱스트리 기반 인덱스는 특정 탐색 키 값을 트리의 노드로 갖고 있다. (이를 가리..