알고리즘

알고리즘(algorism)이란 어떤 문제를 해결하기 위해 정해진 규칙이나 절차를 말한다. 알고리듬(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)로 표기되므로, '리듬'이 아니라 '리즘'에 가깝다. 따라서 한국어로는 최대한 원어에 가깝게 '알고리즘'으로 표시하는 것이 맞다는 의견이다. 또한 알고리즘의 영어 표기도 굳이 algorithm으로 하지 않고, algorism으로 하고 있으므로, 그것에 해당하는 한국어 표기는 '알고리듬'이 맞다는 의견이다. 어쨌든 실제 생활에서는 알고리즘이라는 표기가 알고리듬이라는 표기에 비해 약 30배 정도 압도적으로 많이 사용되고 있다.

종류

암호 알고리즘

---

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

대칭키 암호 알고리즘

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

공개키 암호 알고리즘

• RSA :
• 타원곡선암호 :

합의 알고리즘

---

합의 알고리즘이란 다수의 참여자들이 통일된 의사결정을 하기 위해 사용하는 알고리즘을 말한다. 작업증명(PoW), 지분증명(PoS), 위임지분증명(DPoS), 활동증명(PoA), 중요도증명(PoI), 신뢰성증명(PoB), 권위증명(PoA) 등 다양한 합의 알고리즘이 있다.

• 작업증명(PoW, Proof of Work) : 목표값 이하의 해시를 찾는 과정을 무수히 반복함으로써 해당 작업에 참여했음을 증명하는 방식의 알고리즘이다. 채굴(mining)을 통해 작업증명을 한다. 비트코인, 이더리움, 라이트코인, 비트코인캐시, 비트코인골드, 모네로, 지캐시, 시아코인, 불왁, 에이치닥 등의 암호화폐에서 작업증명 방식을 사용하고 있다.
• 균형작업증명(ePoW, equilibrium Proof of Work) : 기존 작업증명(PoW) 방식을 기반으로 하되, 한 번 채굴에 성공한 노드는 일정 기간 강제로 휴식을 취하도록 만들어 다른 노드들에게 채굴 기회를 공평하게 나누어 주는 방식의 합의 알고리즘이다. 에이치닥 코인에서 이 방식을 사용하고 있다.
• 지분증명(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 방식을 사용하고 있다.
• 활동증명(PoA, Proof of Activity) : 작업증명(PoW) 방식과 지분증명(PoS) 방식을 혼합한 알고리즘이다. 디크레드가 이 방식을 사용하고 있다.
• 지출증명 : 코인을 결코 돌아올 수 없는 지갑에 보내서 소각하면, 소각한 코인량에 비례하여 채굴 성공 가능성이 높아지는 방식이다. 슬림코인(slimcoin)이 이 방식을 사용하고 있다.
• 중요도증명(PoI, Proof of Importance) : 블록체인 네트워크에서 더 많은 지분을 가지고 더 많이 거래를 함으로써 더 많은 활동량을 보인 사람에게 더 큰 의사결정 권한을 주는 방식이다. 넴이 이 방식을 사용하고 있다.
• 신뢰성증명(PoB, Proof of Believability) : 커뮤니티에 대한 기여도를 고려하여 신뢰성이 높은 그룹을 찾아내고 이를 묶어서 증명에 사용하는 방식이다. 이오스트가 이 방식을 사용하고 있다.
• 권위증명(PoA, Proof of Authority) : 권위있는 기관에서 조건에 맞는 노드를 증명해 이들간 합의를 이루는 방식이다. 두나무 블록체인 서비스(DBS)는 권위증명(PoA) 방식을 사용한다.
• 용량증명 : 노드가 가진 데이터 스토리지 공간의 크기에 비례하여 투표 효력을 계산하는 방식이다. 용량증명의 변형된 형태가 저장증명과 공간증명(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) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반