알고리즘

알고리즘(algorithm)이란 어떤 문제를 해결하기 위해 정해진 규칙이나 절차를 말한다. 알고리듬(algorithm) 또는 산법(算法)이라고도 한다. 컴퓨터 알고리즘은 입력된 자료를 바탕으로 원하는 출력을 유도하는 규칙들의 집합이다. 알고리즘은 프로그램 개발의 기초가 된다.

명칭

알고리즘은 9세기 페르시아의 수학자인 무하마드 알콰리즈미(Muhammad al-Kwarizmi)의 이름을 라틴어화한 알고리즈무스(algorismus)에서 따온 말이다.

'알고리즘'은 '알고리듬'으로 표기하기도 하는데, 둘 다 허용되는 표기법이다. 양자의 사용빈도를 조사해 보면, 알고리즘이라는 표기가 알고리듬이라는 표기에 비해 압도적으로 많이 사용되고 있다. 예를 들어 구글 검색 결과를 보면, 2018년 기준으로 알고리즘이 약 590만개이고, 알고리듬이 약 21만개로서 약 30배 정도 차이가 난다.

알고리듬으로 표기하는 것은 영어식 표기이다. 영어로 algorithm의 발음 기호는 [ӕlgərɪðəm]이며 ð는 this [ðɪs]의 ð 발음이다. 따라서 이 단어는 영어식으로 '앨거리듬'으로 표기하거나 좀 더 한국식 발음으로 표기하면 '알고리듬'으로 표기할 수 있다. 영어에서 algorithm을 알고리즘으로 읽는 건 this를 "지스"로 읽는 것과 마찬가지의 잘못이다. rhythm [rɪðəm]을 '리즘'이 아닌 '리듬'으로 표기하는 것과 마찬가지로 algorithm은 알고리듬으로 표기해야 한다는 주장이다. 한편 algorism이라는 "아라비아 숫자식 기수법"이라는 뜻을 가진 유사한 단어가 있는데, 이 단어의 발음기호는 [ǽlɡərìzm]이므로 오히려 이 단어를 앨거리즘이나 알고리즘이라고 읽어야 한다는 의견이다.

위 주장에 대해 반론도 존재한다. 알고리즘이라는 말은 영어가 아니라 원래 페르시아어인데, "알콰리즘 + 이 = 알콰리즈미"(al-Kwarizmi)이므로, '리듬'이 아니라 '리즘'이 맞다는 의견이다. 이 말이 서양으로 건너온 라틴어에서도 "알고리즘 + 우스 = 알고리즈무스"(algorismus)로 표기되므로, '리듬'이 아니라 '리즘'에 가깝다. 따라서 한국어로는 최대한 원어에 가깝게 '알고리즘'으로 표시하는 것이 맞다는 의견이다. 어쨌든 실제 생활에서는 알고리즘이라는 표기가 알고리듬이라는 표기에 비해 약 30배 정도 압도적으로 많이 사용되고 있다.

종류

암호 알고리즘

암호 알고리즘이란 문서나 데이터의 내용을 다른 사람이 알지 못하게 하거나 혹은 본인 인증을 위해 사용하는 알고리즘을 말한다. DES, AES, ARIA, SEED 등의 대칭키 암호 알고리즘과 RSA, 타원곡선암호 등 공개키 암호 알고리즘이 있다.

• 대칭키 암호 알고리즘

• DES :
• AES :
• ARIA :
• SEED :

• 비대칭키 암호 알고리즘

• RSA :
• 타원곡선암호 :

합의 알고리즘

• 작업증명(PoW, Proof of Work) : 목표값 이하의 해시를 찾는 과정을 무수히 반복함으로써 해당 작업에 참여했음을 증명하는 방식의 알고리즘이다. 채굴(mining)을 통해 작업증명을 한다. 비트코인, 이더리움, 라이트코인, 비트코인캐시, 비트코인골드, 모네로, 지캐시, 시아코인, 불웍, 에이치닥 등의 암호화폐에서 작업증명 방식을 사용하고 있다.
• 균형작업증명(ePoW, equilibrium Proof of Work) : 기존 작업증명(PoW) 방식을 기반으로 하되, 한 번 채굴에 성공한 노드는 일정 기간 강제로 휴식을 취하도록 만들어 다른 노드들에게 채굴 기회를 공평하게 나누어 주는 방식의 합의 알고리즘이다. 에이치닥 코인에서 이 방식을 사용하고 있다.
• 지연작업증명(DPoW, Delayed Proof of Work) : 자체 블록체인 이외에 추가로 기존 비트코인의 블록체인도 함께 사용함으로써 위변조가 더욱 어렵게 만드는 합의 알고리즘이다. 슈퍼넷(Supernet)이 설계하였으며, 익명성을 보장하는 프라이버시 코인인 코모도(Komodo)가 지연작업증명 방식을 사용하고 있다.
• 이중작업증명(DPoW, Dual Proof of Work) : 에이식(ASIC) 채굴기를 허용하는 1차 채굴과 에이식 채굴기를 허용하지 않는 2차 채굴을 혼합하여 진행하는 작업증명(PoW) 방식을 말한다. 그린코인(GRIN coin)이 이 방식을 사용한다.
• 지분증명(PoS, Proof of Stake) : 해당 암호화폐를 보유하고 있는 지분율에 비례하여 의사결정 권한을 주는 방식이다. 주주총회에서 주식 지분율에 비례하여 의사결정 권한을 가지는 것과 유사하다. 채굴 과정이 필요 없다. 큐텀, 피어코인 등의 암호화폐가 지분증명 방식을 사용하고 있다. 스트라티스는 처음에 작업증명 방식을 사용했으나 지분증명 방식으로 변경했다. 이더리움도 현재 작업증명 방식을 벗어나 지분증명 방식으로 변경할 예정이다.
• 우로보로스 지분증명(OPoS, Ouroboros Proof of Stake) : 기존 지분증명 방식의 문제점인 그라인딩 공격(Grinding Attack)을 방어하기 위해 코인토싱(coin tossing) 프로토콜을 사용하여 만든 합의 알고리즘이다. 카르다노가 이 방식을 사용하고 있다.
• 리스지분증명(LPoS, Leased Proof of Stake) : 자신이 소유한 암호화폐를 다른 사람에게 리스(lease)로 임대해 주고 그 대가로 보상을 받는 방식이다. 웨이브즈가 이 방식을 사용하고 있다.
• 위임지분증명(DPoS, Delegated Proof of Stake) : 암호화폐 소유자들이 각자의 지분율에 비례하여 투표권을 행사하여 자신의 대표자를 선정하고, 이 대표자들끼리 합의하여 의사결정을 내리는 방식이다. 국민의 대표로 의원을 뽑아 의회를 구성하는 대의 민주주의 제도와 유사하다. 이오스, 스팀, 리스크, 엘프, 라이즈, 아크, 비트셰어, 시프트, 보스코인 등이 위임지분증명 방식을 채택하고 있다.
• 이중위임지분증명(DDPoS, Dual Delegated Proof of Stake) : 기존의 위임지분증명(DPoS) 방식을 사용하면서, 알고리즘에 따라 실시간으로 교체되는 임의의 노드인 시그마노드(sigma node)를 추가하여 검증하도록 함으로써 대표자들 간의 담합에 의한 블록체인 데이터 조작 가능성을 예방한 합의 알고리즘이다. 곽진영이 창시한 시그마체인이 DDPoS 방식을 사용하고 있다.
• 하이퍼 위임지분증명(Hyper-DPoS) : 기존의 위임지분증명(DPoS) 방식을 기반으로 하되, 일정한 시간 안에 빠르게 반응하고 응답할 수 있는 노드(node)만을 선택하여 합의 과정에 참여시키는 합의 알고리즘이다. 하이퍼 디포스라고도 한다. 모파스가 이 방식을 사용하고 있다.
• 포뮬레이션증명(PoF, Proof of Formulation) : 포뮬레이션 보상 순서를 바탕으로 채굴자를 선택하는 합의 알고리즘이다. 플레타(Fleta)가 기존의 위임지분증명(DPoS)을 일부분 변형하여 만들었다.
• 포크능력증명(PoF, Proof of Forkability) : 정해진 수의 선출된 검증자들이 투표를 통해 3분의 2 이상 찬성으로 의사결정을 하는 합의 알고리즘이다. 기존의 비잔틴 장애 허용(BFT)과 위임지분증명(DPoS) 합의 알고리즘의 장점을 결합하여, 애스톤(Aston)을 만든 ㈜엑스블록시스템즈가 개발했다.
• 지분작업증명(PoSW, Proof of Stake and Work) : 작업증명(PoW) 방식과 지분증명(PoS) 방식을 혼합한 하이브리드 방식의 합의 알고리즘이다. 디크레드, 애터니티, 하이퍼캐시, 해피코인, 쿼크체인 등이 이 방식을 사용하고 있다.
• 트레이딩증명(PoT, Proof of Trading) : 암호화폐 거래소에서 사용자가 거래한 양에 비례하여 거래소 수수료 수익의 일부를 거래자에게 되돌려주는 트레이딩 마이닝에서 사용하는 합의 알고리즘이다. 코인제스트의 코즈 등이 있다.
• 소각증명(PoB, Proof of Burn) : 코인을 결코 돌아올 수 없는 지갑에 보내서 소각하면, 소각한 코인량에 비례하여 채굴 성공 가능성이 높아지는 방식이다. 지출증명이라고도 한다. 슬림코인(slimcoin)이 이 방식을 사용하고 있다.
• 두뇌증명(PoB; Proof of Brain) : 암호화폐의 발행을 채굴자나 지분 소유자에게 맡기지 않고, 지적 두뇌 활동을 통해 콘텐츠를 생산하는 사용자와 해당 서비스를 이용하는 참여자들에게 맡기는 합의 알고리즘이다. 스팀(Steem)이 이 방식을 사용하고 있다.
• 중요도증명(PoI, Proof of Importance) : 블록체인 네트워크에서 더 많은 지분을 가지고 더 많이 거래를 함으로써 더 많은 활동량을 보인 사람에게 더 큰 의사결정 권한을 주는 방식이다. 넴이 이 방식을 사용하고 있다.
• 신뢰성증명(PoB, Proof of Believability) : 커뮤니티에 대한 기여도를 고려하여 신뢰성이 높은 그룹을 찾아내고 이를 묶어서 증명에 사용하는 방식이다. 이오스트가 이 방식을 사용하고 있다.
• 흐름증명(PoF, Proof of Flow) : 더 많은 사용자 트래픽을 가져온 기여자에게 더 큰 보상을 해주는 합의 알고리즘이다. 중국의 요요우(YoYow)가 만들었다.
• 권위증명(PoA, Proof of Authority) : 권위있는 기관에서 조건에 맞는 노드를 증명해 이들간 합의를 이루는 방식이다. 두나무 블록체인 서비스(DBS)는 권위증명(PoA) 방식을 사용한다.
• 저장증명(PoS; Proof of Storage) : 증명자(prover)가 자신의 하드디스크 여유 공간에 데이터를 저장하고, 검증자(verifier)가 그것을 승인 또는 거절하는 방식으로 작동하는 합의 알고리즘이다. 공간증명(Proof of Space)이라고도 한다. 유토큰(YOU token)이 저장증명 방식을 사용하고 있다.
• 용량증명 : 블록체인 노드가 가진 데이터 스토리지 공간의 크기에 비례하여 투표 효력을 계산하는 방식이다. 용량증명의 변형된 형태가 저장증명(Proof of Storage) 또는 공간증명(Proof of Space)이다. 버스트코인(Burstcoin)이 용량증명 방식을 사용하고 있다.
• 경과시간증명(PoET, Proof of Elapsed Time) : 미국 인텔이 개발한 합의 알고리즘이다. 한국의 이든체인(EdenChain)이 이 방식을 사용하고 있다.
• 프랙티컬 비잔틴 장애 허용(PBFT, Practical Byzantine Fault Tolerance) : 네오, 질리카, 하이퍼레저, R3, ICT, 텐더민트 등에서 사용하는 방식이다.

체인 알고리즘

체인 알고리즘이란 다수의 거래기록을 암호화하여 위변조를 방지하고 탈중앙 분산 저장 방식으로 데이터를 관리하는 알고리즘이다. 블록체인 알고리즘과 그 대안으로 나온 라이트닝 네트워크, 플라즈마, 플라즈마캐시, 사이드체인, 더블체인, 인터체인, 탱글, 해시그래프 등이 있다.

• 블록체인(blockchain) : 다수의 거래 기록을 묶어 블록을 구성하고, 해시를 이용하여 여러 블록을 체인처럼 연결한 뒤, 다수의 사람들이 복사하여 분산 저장하는 알고리즘이다. 비트코인의 창시자인 사토시 나카모토가 처음 개발했다.
• 라이트닝 네트워크(lightning network) : 기존 블록체인의 느린 속도를 해결하고 번개처럼 빠른 속도를 구현하기 위해, 개별 거래를 별도의 채널에서 처리한 후 그 결과만 블록체인에 기록하는 방식으로 작동하는 알고리즘이다.
• 플라즈마(plasma) : 모든 거래내역을 메인체인에서 처리하는 블록체인과 달리, 메인체인(또는 루트체인)에 나뭇가지처럼 이어진 차일드체인에서 사전에 수집된 정보들을 처리한 후 결과만 루트체인에 전달함으로써 처리 속도를 향상시킨 알고리즘이다. 비탈릭 부테린과 조셉 푼이 공동 개발했다.
• 플라즈마캐시(plasma cash) : 모든 사용자가 모든 거래내역을 복사하여 관리하던 기존의 블록체인이나 플라즈마 알고리즘과 달리, 개별 사용자가 관심을 가진 특정 코인이 포함된 블록만 추적함으로써 처리 속도를 향상시킨 알고리즘이다. 이더리움을 창시한 비탈릭 부테린과 댄 로빈슨, 칼 플로어쉬 등이 공동 개발하고 있다.
• 사이드체인(sidechain) : 플랫폼 코인에 해당하는 이더리움, 넴, 엘프 등의 메인체인 옆에 나란히 붙어서 작동하는 체인을 말한다. 사이드체인만의 독립된 노드를 구성하지 않고, 기존 메인체인의 노드에 사이드체인의 노드가 추가되는 방식으로 작동한다.
• 더블체인(double chain) : 퍼블릭 블록체인과 프라이빗 블록체인을 연결한 체인이다. 예를 들어, 보안이 중요한 가정용 사물인터넷(IoT) 기기는 프라이빗 블록체인을 이용하고, 자동화된 결제를 위해 퍼블릭 블록체인에 연결하는 방식이다. ㈜더블체인의 전삼구 대표가 제안한 개념이다.
• 인터체인(interchain) : 다른 블록체인들을 서로 연결하기 위한 체인이다. 인터체인을 사용하면 A라는 암호화폐로만 구매할 수 있는 제품이나 서비스를 인터체인으로 연결된 B라는 다른 암호화폐로도 구매할 수 있다. 인터체인 방식의 암호화폐는 한국의 ㈜아이콘루프가 개발한 아이콘 등이 있다.
• 퓨어체인(purechain) : 물리적 복제방지기술인 PUF(퍼프)를 이용하여 데이터의 위변조를 방지하고 거래 당사자 간의 합의만으로도 거래를 확정지을 수 있는 기술이다. 기존 블록체인의 문제점을 하드웨어적으로 해결하려는 시도이다.
• 탱글(tangle) : 기존 블록체인의 한계를 극복하고자 블록 자체를 없애고, 새로 발생한 거래가 이전에 발생한 2개의 거래를 확인해 주는 방식으로 작동하는 알고리즘이다. 사물인터넷(IoT) 시대의 M2M 코인인 아이오타(IOTA)에 사용된 알고리즘이다.
• 해시그래프(hashgraph) : 기존 블록체인의 한계를 극복하고자 연결리스트 방식이 아니라, 하나의 노드가 다른 불특정 노드에게 가십(gossip)을 전달하는 방식으로 작동하는 알고리즘이다. 기존 블록체인의 장점인 위변조 방지 기능과 탈중앙 의사결정구조를 유지하면서도, 1초에 수십만 건 이상의 트랜잭션을 처리할 수 있다. 리몬 베어드(Leemon Baird)가 개발했다.

참고자료

• 〈알고리즘〉, 《위키백과》

같이 보기

• 암호 알고리즘
• 합의 알고리즘
• 체인 알고리즘
• 블록체인
• 탱글
• 해시그래프
• 암호화폐

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반