coplit

power

문제 요약

• 거듭제곱을 구하는 문제다. 문제에 로그시간내에 풀어라고 명시되어 있다.

내 접근

• 일반적인 반복문을 활용해서 상수시간으로 풀려고 했다. 콘솔에서는 제대로 작동했지만 실제 테스트에서는 에러가 났다. 메모리 초과로 예상된다.
• 문제에서 주어진 조건과 주의사항을 꼼곰히 파악해야한다. 출제자는 그냥 주의사항을 써 놓은 것이 아니다.

정답

• 로그시간으로 풀려면 이분탐색과 재귀의 컨셉을 활용해서 풀어야 한다.
• power(num, N) = power(num, N/2) * power(num, N/2) * (N % 2 === 1 ? num : 1) 이라는 점화식이 도출되고, 이를 바탕으로 풀이하면 된다.

quick sort

• 불안정정렬, 제자리정렬, 비교 정렬, 분할정복 알고리즘
  상수로그시간, 분할, 정렬
• 피벗 선택의 적절성만 보장된다면 상수로그시간에 정렬
• 이미 정렬된 최악의 경우 지수시간에 수행됨
• 평균적으로 상수로그시간에 수행이 보장된다.

문제 요약

• 그 유명한 퀵 정렬을 구현하는 문제다.

내 접근

• 왼쪽 오른쪽 두 포인터를 활용해서 정렬하고, 포인터가 교차될 때 정렬을 멈춘다는 컨셉이었는데 기억이 안나서 다른 자료를 참고했다.

학습한 내용

• 유틸리티 함수로 파티션 함수를 따로 정의해서 활용한다. 파티션 함수는 정해진 피벗을 기준으로 왼쪽 오른쪽 포인터가 교차될때까지 값을 이동시키는 역할을 수행한다.
• 한번 정해진 피벗을 기준으로 파티션이 수행되면 피벗을 제외한 값을 대상으로 퀵 정렬을 재귀적으로 수행하면 된다.

정답

• c 스타일로 partition 함수를 활용해서 구현하는 방법과
• python, js의 편리한 내장기능을 활용해서 구현하는 방법이 있다.
  • 나눗셈시 parseInt() 해주는거 잊지 말자.

다짐

• 소프트웨어 엔지니어라면 퀵정렬, 합병정렬, 버블정렬 삽입정렬, 선택정렬, 힙 정렬, 이진탐색, BFS, DFS는 자다가 일어나서도 구현 할 수 있어야 한다고 생각한다. 반복해서 학습하고 노력하자. (우선순위를 정해서 구현해본다.)

블록체인 Introduction -2

Introduction

블록체인이란

분산데이터베이스

• 네트워크를 통해 관리되는 분산DB, 데이터를 네트워크에 연결된 여러 컴퓨터에 보관

잠재력

• 제 3자 없이 무결성 보장
• 차세대 일반목적기술로 탈중앙화, 수평적 비즈니스의 기반 기술

블록체인 소개

공개 범위에 따른 블록체인

퍼블릭 블록체인

• 누구나 트랜잭션을 읽고 쓸 수 있음.
• 공개 네트워크에 참여한 모든 노드들에 의해 검증되어 신뢰도가 높지만 속도가 느림.

프라이빗 블록체인

• 단일 서비스 제공자의 허가를 받아야만 네트워크에 참여 가능
• 기업에서 주로 활용하여 엔터프라이즈 블록체인이라고도 함
• 하이퍼레저는 대표적인 프라이빗 블록체인 프레임워크

컨소시엄 블록체인

• 같은 목적을 가진 여러 기관이 하나의 컨소시엄을 구성하여 네트워크를 구성. 프라이빗 블록체인과 달리 거버넌스가 특정 기관들의 그룹에 의해 구성됨
• 다수 참여자의 투명하고 수평적인 협의를 제 3자의 개입없이 가능하게 했음
• 하이퍼레저 패브릭이 대표적인 컨소시엄 블록체인

블록체인 구분 기준

• 

분산원장기술 (DLT)

• 거래 기록의 원장을 분산화된 네트워크에서 기록 및 관리 하는 것
• 중앙집중원장의 단점을 보완하기 위해 탄생

중앙집중원장의 단점 : 시간과 비용 문제

• 제 3자의 관리 수수료 부과, 웨스턴유니온 등.
• 중개자(미들맨)를 거침으로써 프로세스 전반에 걸쳐 시간과 비용이 증가, 증권예탁결제의 3일 거래 방식.

중앙집중원장의 단점 : 보안 문제

• single point of failure : 인터파크 해킹, 카카오톡

분산원장기술의 장점

• 인증과 증명의 효율성
• 시스템의 안정성
• 보안성과 투명성
• 중개자 없는 거래주체간 직접 거래 가능

트랜잭션

• 트랜잭션이란 DB의 상태를 변화시키는 논리적 기능을 수행하기 위해 구성된 일련의 작업의 모음
• 블록체인에서 트랜잭션은 체인의 상태를 변화시키는 역할 수행

블록의 구조

• 블록 = 헤더(메타데이터) + 체인(트랜잭션 리스트)
• 블록체인과 트랜잭션의 구조

비트코인과 이더리움의 트랜잭션 구조 차이

비트코인 트랜잭션 구조

• 이해하지 않고 넘어감
• 다른 자료를 통해 학습해 보기로 함

이더리움 트랜잭션 구조

• 비트코인과 가장 큰 차이는 Nonce가 있다는 것
• 이중지불 문제를 해결하기 위해 이더리움에서 등장한 방식
• 논스는 해당 주소에 종속적인 트랜잭션 순서이다. 트랜잭션시마다 Nonce++된다. 하지만 계정에 저장되는 것이 아니라 네트워크 상에서 동적으로 계산 된다.
• 논스는 순차적으로 수행되고 이전 논스가 5일때 논스값이 7인 트랜잭션은 멤풀에서 논스6인 트랜잭션이 처리될때까지 기다렸다가 함께 처리된다.
• 동일 논스에 여러 트랜잭션이 발생한 경우 최대 가스피를 지불한 트랜잭션을 유효한 트랜잭션으로 처리한다.

이해하지 못한 부분

• 모든 트랜잭션은 일회성이므로 하나의 상태만 변화시킬 수 있다.
• 이중지불 문제를 해결하기 위해 비트코인은 UTXO(미사용 트랜잭션 출력값)을 활용하고, 이더리움은 어카운트 기반으로 특정 논스를 오직 한번만 사용하게 하는 카운터로 활용한다.
• 질문들

1. UTXO는 전체 네트워크의 컨텍스트에서 관리되는 변수인가?
2. UTXO는 컴퓨터의 한계로 인해 최댓값이 존재하는가?
3. UTXO의 최댓값에 도달하면 네트워크는 새로운 트랜잭션을 블록에 추가하지 못하나?(이중 지불 문제가 해결되지 않으므로)
4. 결과적으로 비트코인이 다 채굴되면 비트코인 네트워크는 쓸모없어 지는가?

ACID

• Atomicity : Commit || Rollback
• Consistency : DB 전체의 구조적 무결성
• Isolation : No interaction with other TX
• Durability : Saved for good when committed

블록체인의 구성요소

합의알고리즘

합의알고리즘이 뭐야?

• 분산시스템에서 다수의 참여자들이 동일한 의사결정을 하기위해 사용하는 알고리즘

왜 필요해?

• 분산시스템에서 모든 노드들이 정직하게 작동하는 것을 기대할 수 없음.
• 악의적인 노드들의 트롤링이 발생해도 올바른 트랜잭션을 담은 유효한 블록을 생성하기 위해서

작업증명

블록 생성 권한

• 블록생성 시간동안 가장 많은 해시파워를 제공한 노드가 블록을 생성할 수 있음.
• 구체적으로 채굴자들은 논스(Nonce)라는 임의의 값을 맞추기 위해 컴퓨팅파워를 사용하며 논스를 찾은 노드가 블럭생성의 권한을 갖는다.
• 브랜치가 생긴 경우 경쟁에서 이긴 가장 긴 블록체인이 최종적인 브랜치로 채택됨(이해 못함)

장, 단점

• 장점 : 강력한 보안성, 서비스 남용 방지
• 단점 : 전력 소모 과다, 해시파워 유지 필요, 마이닝풀의 권력 비대화

지분증명

블록생성 권한

• 지분을 많이 가지고 있는 노드에게 블록생성 권한 부여
• 채굴자는 이자와 같은 방식으로 채굴에 대한 보상을 받을 수 있음

장, 단점

• 장점 : 해시파워 많이 필요하지 않음, 블록 생산자의 탈중앙화, 덤핑 방지됨
• 단점 : 보안성에 대한 검증 불충분, 고래들의 권력 비대화

위임 지분 증명

• POW, POS 부터 자세히 알고 난 후에 공부할게~

블록생성 권한

장, 단점

지갑

지갑이란?

• 개인키를 보관하는 소프트웨어
• 채굴과 노드에서 노드가 바로 지갑
• 데스크탑, 모바일, 하드웨어, 웹 지갑 등이 있음

지갑의 구조

• 공개키(주소)와 개인키(암호)로 구성되어 있음
• 공개키는 해당 지갑으로 암호화폐를 전송하는 주소로 활용됨.
• 비밀키는 본인 이외에 절대 공개되면 안됨.

어카운트

비트코인과 이더리움

비트코인 코어

• C++로 구현됨
• 풀 노드를 돌리기 위해서는 100GB 가량의 데이터 다운로드 필요함

이더리움 클라이언트

• 분산 네트워크이므로 클라이언트만 존재함
• Geth : 고랭으로 개발된 공식 이더리움 클라이언트
• Parity : 러스트로 구현된 써드파티 클라이언트

거버넌스를 통한 플랫폼의 발전

• 이것도 나중에 공부..

재윤TV- 블록체인의 원리

비트코인의 원리

비트코인 논문에서 다룬 핵심 쟁점들

1. 신원인증 없는 거래
2. 이중지불 문제 해결
3. 이중지불 문제 해결을 위한 합의 알고리즘

트랜잭션

• 일반적으로 데이터의 상태를 바꾸는 논리적 단위
• 비트코인에서는 자산의 상태를 변화시키는 단위

제 3자에 의한 신원인증 불필요

공개키 암호화

• 비트코인에서는 타원곡선 알고리즘으로 공개키 암호화 구현

1. 비밀키로 원본데이터를 암호화
2. 공개키로 암호화된 서명을 검증가능
3. 검증 결과에 따라 원본데이터의 진위판별 가능

암호학적 해시 함수

• 임의의 데이터를 일정길이의 문자열로 바꾸는 단방향 함수
• 입력값으로 출력값을 찾기는 쉽지만 역방향으로 찾기는 현실적으로 불가능
• 입력값을 조금만 바꿔도 전혀 다른 값을 출력(avalanche effect)하므로 추론하기도 어렵다. 부르트 포스말고는 방법이 없음
• 같은 입력값은 deterministeic으로 항상 같은 출력값을 출력하므로 검증이 용이하다.

해시함수를 활용한 전자서명의 절차

1. 트랜잭션을 해시함수에 넣어 해시화 한다.h1

2. 해시값을 비밀키로 암호화하여 전자서명을 생성한다.
   

3. 트랜잭션의 원본과 전자서명을 함께 송신한다.

4. 수신노드는 수신한 트랜잭션의 원본을 동일한 해시함수로 해싱하여 h2을 얻는다.

5. 수신노도는 전자서명을 비밀키로 복호화하여 송신자가 보낸 h3을 얻는다.

6. 수신자는 h2와 h3(실제로는 h1과 같다)을 비교한다.

7. 비교 결과 참이면, 수신자는 트랜잭션에 해당하는 비밀키를 가진 정당한 송신자로부터 생성된 트랜잭션임을 확인 가능하다.

이중지불문제

이중지불문제란?

• 정당한 권리를 가진 한 사람이 모순되는 두 가지의 트랜잭션을 동시에 발생시키는 경우 이중지물문제 발생
• 100원을 가진 A가 B와 C에 동시에 각각 100원을 보내는 트랜잭션을 제출했을때 어떤 트랜잭션이 유효한지 판별해야 하고, 모든 피어들이 같은 결론을 가져야 함.
• 분산네트워크에서 이러한 문제를 해결하는 알고리즘을 합의 알고리즘이라 함.
• 이중지불문제는 비잔틴 장군 문제로 치환가능함

비잔틴 장군 문제

• 분산시스템에서 이중지불문제를 해결하기 위해 레슬리 램포트의 논문에서 언급된 문제
• 분산시스템에서 정직한 참여자들이 합의에 도달하기 위한 조건에 대한 논의

1. 배신자의 수가 전체의 1/3 미만이고 (n > 3t)
2. 모든 메시지가 동기적으로 올바른 채널을 통해 전달될 경우
3. 합의에 도달 할 수 있다

• 이것이 BFT 알고리즘
• 노드 수가 정해져있고, 돌아가면서 블럭을 생성한다.

BFT 알고리즘의 문제점

• 배신자의 수와 전체 노드의 수에 따라 합의에 필요한 메시지의 수가 으로 증가pow(n, t) 하므로 통신비용이 너무 비쌈
• 과반 이상의 노드가 시스템에서 이탈하면 합의를 도출할 수 없음
• 신규 참여자가 네트워크에 진입하면 부하가 기하급수적으로 증가함
• 따라서 전통적인 PBFT 알고리즘으로 개방형 네트워크를 만들 수 없다.
• 그래서 비트코인이 원하는 개방형 시스템을 만들기 위해 새로운 합의 알고리즘인 POW가 탄생

합의 알고리즘

블록

• 모든 블록체인에서 하나의 합의의 단위는 블록이다.
• 블록안의 모든 트랜잭션들은 유효한 수행이 보장된 트랜잭션들이다. (이중지불 문제가 발생하지 않는 트랜잭션들)
• 비트코인에서 생성되는 DAG상 가장 마지막에 있는 트랜잭션(UTXO)들의 집합이 블록 상태를 의미한다.

UTXO

• unspent transaction output : 새로운 블록 생성에 사용되지 않았으므로 Unspent 아닌가? -> 맞음
• 블록은 전역적인 맥락에서 선형적으로 생성된다.
• 각 블록은 이전 블록을 참조하는 맥락에서 순서가 정해져 있다.
• 특정 시점의 블록상태는 UTXO의 집합이다. 새로운 블럭의 생성은 UTXO의 집합을 소비하여 새로운 UTXO를 만든다.
• 비트코인은 최신상태를 따로 저장하지 않으므로 UTXO의 집합을 탐색하여야만 최신 원장의 상태를 알 수 있다.

트랜잭션과 블록의 전파(propagation)

특정 노드에서 신규 생성된 블록을 전체 네트워크의 피어에 나눠주는 행위

가십 프로토콜(gossip protocol)

• P2P 네트워크에서 각 노드가 이웃 노드에게 데이터를 전파하는 방법
• 대역폭의 낭비를 줄이면서도 데이터를 빠르고 안정적으로 전파 가능
• 효율성을 일부 희생해서 안정성을 높임. 실제로 유의미하게 비효율적이진 않음
• 따라서 비트코인을 비롯한 많은 블록체인이 가십 프로토콜을 사용함

블록의 전파 도중에 새로운 블럭이 생성된다면?

• 신규 블럭생성 속도가 블록의 전파시간보다 빠르다면, 전체가 동기화되어있지 않은 상태에서 신규 블럭이 생성됨.
• 이 때는 race condition이 발생하여 전체 네트워크를 동기화 할 수 없는 문제 발생.
• 90% 이상 동기화 이후에 신규 블럭이 생성되어야 race condition을 방지할 수 있음

Cheat resistant timer

• 의도적으로 블록생성속도를 네트워크보다 늦추는 타이머
• 타이머가 expire 되어야 신규블록을 생성할 수 있다.
• 타이머 시간은 무작위로 생성되지만 알고리즘에 의해 생성범위를 조정할 수 있어야 한다.

POW

랜덤타이머를 만드는 방법이 POW

• 블록생성시 컴퓨팅파워를 소비하게 만듦
• 특정 값(nonce)을 찾은 노드가 블록을 sealing할 수 있고, sealing된 블록이 유효한 블록으로서 네트워크상에 전파 가능하다.
• 논스를 찾는 작업은 확률적이므로 많은 시행을 한 사람이 올바른 논스값을 찾을 확률이 높다.

논스와 리딩제로

while True:
	해시값 = SHA256(상수 + 논스)
    if leadingZero(해시값) == definedLeadingZeroVal:
    	break
return

해쉬값이 특정 조건 (리딩제로의 개수)가 되도록 논스를 계속 조정해야됨

비트코인에서의 POW

• 

1. 트랜잭션을 sha256으로 해싱한 결과를 헤더에 머클루트해시로 넣는다.
2. 헤더에는 이전 블록의 해시값이 포함되어 있으므로 블록체인은 순서를 유지할 수 있다.
3. 물론 이전 블록의 해시값은 리딩제로 조건을 만족하는 해시값
4. 이제 헤더의 모든 정보를 sha256으로 해싱해서 리딩제로 조건을 만족하기만 하면 된다.
5. 리딩제로 조건을 만족할 때 까지 계속 nonce값을 바꿔가면서 부르트 포스로 대입한다.
6. 리딩제로 조건을 만족하는 nonce를 찾으면 해당 블록은 seal되어 네트워크상에 전파되고 채굴자는 보상으로 코인을 얻는다.
7. 새로운 블록생성을 전파 받은 노드들은 자신이 만들던 블록을 폐기하고, 새롭게 신규 블록 뒤에서부터 블록생성 작업을 진행한다.

• 그런데 랜덤타이머니까 아주 낮은 확률로 블록이 두개 동시에 생성되기도 하고, 이 문제를 해결할 필요가 있다.

체인 선택 규칙

• 비트코인은 longest chain rule을 추가하여 합의 알고리즘을 완성한다.
• 가장 긴 체인을 canonical chain이라 하며, canonical chain이 바뀌는 과정을 reorg라 한다.

비트코인 보안(이해 못함)

알아야 하는 키워드만 정리하고 넘어가는걸로...

• reorg
• 51% attack
• singleton global state
• finalizing tx
• interval and block size trade off