합의 (컴퓨터 과학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 계산 모델
4. 합의 문제의 동치성
5. 합의 문제의 해결 가능성
6. 합의 프로토콜 예시
- 6.1. 무허가 합의 프로토콜
7. 합의 수 (Consensus Number)
8. 한국의 관점 및 더불어민주당의 입장
참조

1. 개요

합의 문제는 분산 컴퓨팅 시스템에서 여러 프로세스 또는 에이전트가 단일 데이터 값에 동의해야 하는 근본적인 문제이다. 장애 허용 프로토콜은 유한성, 무결성, 일치성의 속성을 가지며, 실행 시간과 메시지 복잡도에 따라 성능이 평가된다. Paxos, Multi-Paxos, Raft와 같은 프로토콜은 단일 값 또는 다중 값 합의를 위해 사용되며, 비잔틴 장애와 같은 다양한 장애 상황을 고려해야 한다. FLP 불가능성 결과에 따라 완전 비동기 시스템에서는 충돌 실패를 허용하는 합의 해결책이 존재하지 않지만, 무작위 알고리즘을 통해 이를 회피할 수 있다. 또한 비트코인과 같은 무허가 합의 프로토콜은 작업 증명, 지분 증명 등의 방식을 사용하여 시빌 공격을 방어한다. 공유 메모리 시스템에서는 동시 객체의 합의 숫자를 통해 합의의 가능성을 판단하며, 이를 통해 헐리히의 동기화 객체 계층을 형성한다.

더 읽어볼만한 페이지

분산 컴퓨팅 문제 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다.
분산 컴퓨팅 문제 - 비잔티움 장애 허용
비잔틴 장애 허용(BFT)은 분산 컴퓨팅 시스템에서 일부 구성 요소가 오류나 악의적인 행위를 하더라도 시스템 전체가 정상적으로 작동하도록 보장하는 속성으로, 비잔틴 장애에 대한 대응책으로 합의 알고리즘을 통해 신뢰성을 확보하며, 블록체인, 항공, 군사, 암호화폐 등 다양한 분야에서 활용된다.
장애 허용 컴퓨터 시스템 - 컴퓨터 클러스터
컴퓨터 클러스터는 여러 대의 상용 컴퓨터를 고속 네트워크로 연결하여 고성능 컴퓨팅 시스템을 구축하는 방식으로, 슈퍼컴퓨터를 포함한 다양한 분야에서 높은 가용성과 확장성을 제공하며, 클러스터 미들웨어를 통해 시스템 관리, 부하 분산, 통신 방식, 데이터 공유 등을 지원하고 노드 장애 관리를 위한 펜싱 기술을 활용한다.
장애 허용 컴퓨터 시스템 - 트랜잭션 처리
트랜잭션 처리는 데이터베이스 시스템에서 데이터의 일관성과 무결성을 보장하기 위한 기술이며, ACID 속성을 통해 데이터 정확성을 유지하고 롤백, 데드락 처리 등의 기술을 활용한다.

합의 (컴퓨터 과학)
정보 공학
정의
분야	컴퓨터 과학, 분산 컴퓨팅
목적	분산 시스템에서 신뢰할 수 있는 합의 도출
관련 문제	비잔틴 장군 문제 합의 문제
주요 특징
속성	합의: 모든 정상적인 프로세스가 동일한 값에 동의함 무결성: 합의된 값은 프로세스에 의해 제안된 값 중 하나여야 함 종료: 모든 정상적인 프로세스는 결국 결정을 내림
합의 알고리즘
종류	Paxos Raft PBFT 작업 증명(PoW) 지분 증명(PoS)
활용
적용 분야	블록체인 분산 데이터베이스 클라우드 컴퓨팅
참고 자료
관련 논문	Reaching Agreement in the Presence of Faults (Leslie Lamport, Marshall Pease, Robert Shostak, 1980)

2. 정의

'''합의 문제 (Consensus Problem)'''는 분산 컴퓨팅 및 다중 에이전트 시스템에서 여러 프로세스(또는 에이전트)가 단일 데이터 값에 대해 동의해야 하는 근본적인 문제이다. 그러나 일부 프로세스는 고장나거나 신뢰할 수 없게 될 수 있으므로, 합의 프로토콜은 장애 허용이거나 복원력이 있어야 한다.

장애를 허용하는 합의 프로토콜은 일반적으로 다음과 같은 속성을 갖는다.^[43]

'''유한성 (Termination)''': 결과적으로 모든 정상적인 프로세스들은 어떤 값을 정한다.
'''무결성 (Integrity)''': 만약 모든 정상적인 프로세스들이 같은 값 v를 제안했었다면, 정상적인 프로세스들은 반드시 값을 v로 정해야 한다. 이 속성은 '''유효성 (Validity)'''으로도 알려져 있다.^[44]
'''일치성 (Agreement)''': 모든 정상 프로세스들은 반드시 값이 일치한다.

무결성에 대한 정의는 적용 방법에 따라서 적절하게 변형될 수 있다. 예를 들어, 일부 정상 프로세스가 제안했던 값과 동일한 값으로 결정하는 더 약한 무결성은 모든 정상 프로세스들의 제안 값을 필요로 하지 않는다.

t개 이하의 실패에서 n개의 프로세스들 간의 합의를 정확하게 보장하는 프로토콜을 '''t-복원성(t-resilient)''' 프로토콜이라 부른다.

합의 프로토콜의 성능의 핵심 요소는 다음과 같다. 대문자 O 표기법으로 나타낸다.

'''실행 시간(running time)''': 메시지 교환 라운드 수를 나타내는 함수이다.
'''메시지 복잡도(message complexity)''': 프로토콜에 의해 생성된 메시지 트래픽 수를 나타내는 함수이다.

그 밖에도 메모리 사용량이나 메시지 크기 등이 성능 요인으로 포함된다.

합의를 생성하는 한 가지 방법은 모든 프로세스(에이전트)가 다수결 값에 동의하는 것이다. 그러나 하나 이상의 결함이 있는 프로세스가 결과 출력을 왜곡하여 합의에 도달하지 못하거나 잘못된 합의에 도달할 수 있다.

2. 1. 합의 프로토콜의 기본 속성

합의 프로토콜은 여러 프로세스들이 하나의 값에 대해 일치하도록 하는 알고리즘으로, 장애 허용 및 복원력을 갖춰야 한다. 장애를 허용하는 합의 프로토콜은 다음과 같은 속성을 갖는다.^[43]

유한성 (Termination): 모든 정상적인 프로세스들은 결국 어떤 값을 결정한다.
무결성 (Integrity): 모든 정상적인 프로세스들이 동일한 값 v를 제안했다면, 정상적인 프로세스들은 반드시 v로 값을 결정해야 한다. 이 속성은 유효성 (Validity)이라고도 불린다.^[44]
일치성 (Agreement): 모든 정상 프로세스들은 반드시 같은 값에 동의해야 한다.

t개 이하의 실패에서 n개의 프로세스들 간의 합의를 정확하게 보장하는 프로토콜을 t-복원성(t-resilient) 프로토콜이라고 부른다.

합의 프로토콜의 성능은 다음 두 가지 요소로 평가한다.

실행 시간(running time): 메시지 교환 라운드 수를 나타내는 함수로, 대문자 O 표기법으로 나타낸다.
메시지 복잡도(message complexity): 프로토콜에 의해 생성된 메시지 트래픽 수를 나타내는 함수이다.

이 외에도 메모리 사용량이나 메시지 크기 등이 성능 요인으로 고려된다.

Paxos는 가장 전통적인 단일 값 합의 프로토콜로, 협력 노드는 정수와 같은 단일 값에 동의한다. 이진 합의는 입력과 출력 도메인을 단일 이진 숫자 {0,1}로 제한하는 단일 값 합의 문제의 특별한 경우이다. Multi-Paxos 및 Raft와 같은 다중 값 합의 프로토콜은 일련의 값에 동의하여 점진적으로 증가하는 기록을 형성한다.

부분 동기 시스템에서 n개의 프로세스가 있을 때, 각 프로세스는 개인 값을 선택하고, 라운드 방식으로 서로 통신하여 합의 벡터를 생성한다.^[7] 이 과정에서 다음 요구 사항이 충족되어야 한다.

# 올바른 프로세스가 특정 값을 전송하면, 모든 올바른 프로세스는 해당 값을 받거나 아무것도 받지 않아야 한다(무결성 속성).

# 한 라운드에서 올바른 프로세스가 전송한 모든 메시지는 같은 라운드에서 모든 올바른 프로세스에게 수신되어야 한다(일관성 속성).

이러한 문제의 변형은 한 유형의 모델에서 문제에 대한 해결책이 다른 유형의 모델에서 다른 문제에 대한 해결책이 될 수 있다는 점에서 동일하다. 예를 들어, 동기식 인증된 메시지 전달 모델에서 약한 비잔틴 장군 문제에 대한 해결책은 약한 상호 작용 일관성에 대한 해결책으로 이어질 수 있다.^[8] 상호 작용 일관성 알고리즘은 각 프로세스가 해당 합의 벡터에서 다수결 값을 합의 값으로 선택함으로써 합의 문제를 해결할 수 있다.^[9]

2. 2. 추가 고려 사항

프로세스가 겪을 수 있는 장애에는 두 가지 유형이 있는데, 하나는 충돌 장애이고 다른 하나는 비잔틴 장애이다. 충돌 장애는 프로세스가 갑자기 중단되고 재개되지 않을 때 발생한다. 비잔틴 장애는 어떠한 조건도 부과되지 않는 장애이다. 예를 들어, 적대자의 악의적인 행동의 결과로 발생할 수 있다. 비잔틴 장애를 경험하는 프로세스는 다른 프로세스에 모순되거나 상충되는 데이터를 보낼 수 있거나, 대기 상태로 있다가 오랜 지연 후에 활동을 재개할 수도 있다. 두 가지 유형의 장애 중에서 비잔틴 장애가 훨씬 더 파괴적이다.

따라서 비잔틴 장애를 허용하는 합의 프로토콜은 발생할 수 있는 모든 가능한 오류에 탄력적이어야 한다.

비잔틴 장애를 허용하는 합의의 더 강력한 버전은 무결성 제약을 강화하여 제공된다.
무결성: 만약 올바른 프로세스가

v

를 결정하면,

v

는 어떤 올바른 프로세스에 의해 제안되었음에 틀림없다.

2. 3. 성능 요소

3. 계산 모델

다양한 계산 모델이 "합의 문제"를 정의할 수 있다. 일부 모델은 완전 연결 그래프를 다루는 반면, 다른 모델은 링과 트리를 다룬다. 일부 모델에서는 메시지 인증이 허용되지만, 다른 모델에서는 프로세스가 완전히 익명으로 처리된다. 프로세스가 공유 메모리의 객체에 접근하여 통신하는 공유 메모리 모델 역시 중요한 연구 분야이다.^[4]

합의 문제는 비동기 또는 동기 시스템의 경우를 고려할 수 있다. 실제 통신은 본질적으로 비동기적인 경우가 많지만, 동기 시스템을 모델링하는 것이 더 실용적이고 종종 더 쉬운데,^[4] 비동기 시스템이 동기 시스템보다 자연스럽게 더 많은 문제를 포함하기 때문이다.^[4]

동기 시스템에서는 모든 통신이 ''라운드''로 진행된다고 가정한다. 한 라운드에서 프로세스는 필요한 모든 메시지를 보낼 수 있으며 다른 프로세스에서 오는 모든 메시지를 수신할 수 있다. 이러한 방식으로 한 라운드의 메시지는 동일한 라운드 내에서 전송된 모든 메시지에 영향을 미칠 수 없다.^[4]

4. 합의 문제의 동치성

0부터 $n-1$ 까지 번호가 매겨진 $n$ 개의 프로세스 모음이 서로 메시지를 보내 통신한다. 프로세스 $0$ 은 모든 프로세스에 값 $v$ 를 전송해야 한다. 프로세스 $0$ 이 올바른 경우, 모든 올바른 프로세스는 $v$ 를 수신해야 한다. 또한, 두 개의 올바른 프로세스는 동일한 값을 수신해야 한다. 이 문제는 장군의 문제로도 알려져 있다.

5. 합의 문제의 해결 가능성

완전 비동기 메시지 전달 분산 시스템에서, 적어도 하나의 프로세스가 '충돌 실패'를 겪을 수 있는 경우, 결정적 알고리즘으로는 합의를 달성하는 것이 불가능하다는 '''FLP 불가능성 결과'''가 1985년에 증명되었다.^[5] 이 결과는 최악의 스케줄링 시나리오에서 도출된 것으로, 일반적인 상황에서는 발생할 가능성이 낮다.^[4]

비동기 모델에서 통신 링크 손실과 같은 일부 형태의 실패는 동기식 합의 프로토콜로 처리할 수 있다. 예를 들어, 통신 링크의 손실은 비잔틴 실패를 겪은 프로세스로 모델링할 수 있다. 무작위 합의 알고리즘은 최악의 스케줄링 시나리오에서도 높은 확률로 안전성과 활성성을 모두 달성하여 FLP 불가능성 결과를 회피한다.^[6]

$t$ 개의 결함이 있고, $n$ 개의 프로세스가 있는 경우, $\tfrac{t}{n} < \tfrac{1}{3}$ 이면 비잔틴 장군 문제를 해결하는 t-복원 익명 동기 프로토콜이 존재한다.^[10]^[11] 또한, $f$ 개의 비잔틴 프로세스를 포함하여 $n$ 개의 프로세서가 있는 시스템에서, ''구두 메시지 모델''에서는 $n \leq 3f$ 에 대한 합의 문제를 해결하는 알고리즘이 존재하지 않는다.^[12] ''서면 메시지 모델''에서는 $n=f+1$ 을 허용하는 프로토콜이 존재한다.^[2]

완전 비동기 시스템에서는 하나 이상의 충돌 실패를 허용하는 합의 해결책이 없다.^[5] 이 결과는 마이클 J. 피셔(Michael J. Fischer), 낸시 린치(Nancy Lynch), 마이크 페터슨(Mike Paterson)의 이름을 따 FLP 불가능성 증명이라고 불리며, 이들은 이 연구로 Dijkstra Prize를 수상했다. FLP 결과는 공정성 가정에서도 검증되었다.^[13] 그러나 FLP는 합의에 도달할 수 없다는 것이 아니라, 모델 가정 하에서 어떤 알고리즘도 항상 유한 시간 내에 합의에 도달할 수 없다는 것을 의미하며, 실제로는 발생할 가능성이 매우 낮다.

6. 합의 프로토콜 예시

비잔틴 장애를 허용하는 다항 시간 이진 합의 프로토콜의 예로는 Garay와 Berman이 제안한 Phase King 알고리즘이 있다.^[14] 이 알고리즘은 ''n''개의 프로세스와 최대 ''f''개의 장애가 있는 동기식 메시지 전달 모델에서 합의 문제를 해결하며, ''n'' > 4''f''인 경우에 작동한다. Phase King 알고리즘에서는 각 ''f'' + 1개의 단계가 있으며, 각 단계에는 2라운드가 있다. 각 프로세스는 선호하는 출력(초기에는 프로세스 자체의 입력 값과 동일)을 추적한다. 각 단계의 첫 번째 라운드에서 각 프로세스는 자신의 선호 값을 다른 모든 프로세스에 브로드캐스트한다. 그런 다음 모든 프로세스에서 값을 수신하고, 다수 값과 그 개수를 결정한다. 단계의 두 번째 라운드에서 현재 단계 번호와 일치하는 ID를 가진 프로세스가 해당 단계의 왕으로 지정된다. 왕은 첫 번째 라운드에서 관찰한 다수 값을 브로드캐스트하고, 동점자 역할을 한다. 그런 다음 각 프로세스는 다음과 같이 선호하는 값을 업데이트한다. 첫 번째 라운드에서 프로세스가 관찰한 다수 값의 개수가 ''n''/2 + ''f''보다 크면, 프로세스는 선호하는 값을 해당 다수 값으로 변경한다. 그렇지 않으면 단계 왕의 값을 사용한다. ''f'' + 1단계가 끝나면 프로세스는 선호하는 값을 출력한다.

구글은 분산 록 관리자 라이브러리인 Chubby를 구현했다.^[15] Chubby는 장애 발생 시에도 높은 가용성을 확보하기 위해 복제된 데이터베이스에 저장된 작은 파일에 록 정보를 유지한다. 데이터베이스는 Paxos 합의 알고리즘을 기반으로 하는 내결함성 로그 계층을 기반으로 구현된다. 이 체계에서 Chubby 클라이언트는 복제된 로그에 액세스/업데이트(즉, 파일 읽기/쓰기)하기 위해 Paxos ''마스터''와 통신한다.^[16]

비트코인은 P2P 네트워크에서 합의를 유지하기 위해 작업 증명을 사용하였다.

많은 실시간 전략 온라인 대인 대전 게임은 게임 내 플레이어 간의 게임 상태를 관리하기 위해 수정된 록스텝 프로토콜을 합의 프로토콜로 사용한다. 각 게임 액션은 총 게임 상태의 해시와 함께 게임 내 다른 모든 플레이어에게 브로드캐스트되는 게임 상태 델타를 생성한다. 각 플레이어는 델타를 자체 게임 상태에 적용하고 게임 상태 해시를 비교하여 변경 사항을 검증한다. 해시가 일치하지 않으면 투표가 이루어지고, 게임 상태가 소수인 플레이어는 게임에서 연결 해제 및 제거된다(동기화 손실이라고 함).

Leslie Lamport의 Paxos 합의 알고리즘과, Raft와 같은 그 변형은 널리 배포된 분산 컴퓨팅 및 클라우드 컴퓨팅 시스템에서 널리 사용된다. 이러한 알고리즘은 일반적으로 동기식이며 진행을 위해 선출된 리더에 의존하며, 비잔틴 장애가 아닌 충돌만 허용한다.

또 다른 잘 알려진 접근 방식은 MSR 유형 알고리즘이라고 하며, 이는 컴퓨터 과학에서 제어 이론에 이르기까지 널리 사용되어 왔다.^[17]^[18]^[19]

소스	동기화	인증	임계값	라운드 수	비고
Pease-Shostak-Lamport ^[10]	동기식	구두	$n > 3f$	$f+1$	총 통신 $O(n^f)$
Pease-Shostak-Lamport ^[10]	동기식	서면	$n > f+1$	$f+1$	총 통신 $O(n^f)$
Ben-Or ^[20]	비동기식	구두	$n > 5f$	$O(2^n)$ (예상)	예상 $f < \sqrt{n}$ 일 때 $O(1)$ 라운드
Dolev et al.^[21]	동기식	구두	$n > 3f$	$2f+3$	총 통신 $O(f^3 \log f)$
Dolev-Strong ^[2]	동기식	서면	$n > f+1$	$f+1$	총 통신 $O(n^2)$
Dolev-Strong ^[2]	동기식	서면	$n > f+1$	$f+2$	총 통신 $O(nf)$
Feldman-Micali ^[22]	동기식	구두	$n > 3f$	$O(1)$ (예상)
Katz-Koo ^[23]	동기식	서면	$n > 2f$	$O(1)$ (예상)	공개 키 기반 구조 (PKI) 필요
PBFT ^[24]	비동기식 (안전성) 동기식 (생존성)	구두	$n > 3f$
HoneyBadger ^[25]	비동기식	구두	$n > 3f$	$O(\log n)$ (예상)	트랜잭션당 통신 $O(n)$ - 공개 키 암호화 필요
Abraham et al.^[26]	동기식	서면	$n > 2f$	$8$
Byzantine Agreement Made Trivial ^[27]^[28]	동기식	서명	$n > 3f$	$9$ (예상)	디지털 서명 필요

== 무허가 합의 프로토콜 ==

무허가 합의 프로토콜은 네트워크에 있는 누구든지 사전 허가 없이 동적으로 참여할 수 있도록 허용하지만, 시빌 공격 위협을 완화하기 위해 다른 형태의 인위적인 비용 또는 진입 장벽을 부과한다. 비트코인은 작업 증명과 난이도 조정 기능을 사용하여 최초의 무허가 합의 프로토콜을 도입했는데, 참여자들이 암호화 해시 함수 퍼즐을 풀기 위해 경쟁하고, 투자한 계산 노력에 비례하여 확률적으로 블록을 커밋하고 관련 보상을 받을 권리를 얻는다. 이 방식의 높은 에너지 비용에 부분적으로 동기를 부여받아, 이후의 무허가 합의 프로토콜은 지분 증명, 공간 증명, 권한 증명과 같은 시빌 공격 방어를 위한 다른 대체 참여 규칙을 제안하거나 채택했다.

비트코인은 허가 없이 열린 P2P 네트워크에서 합의를 달성하기 위해 작업 증명, 난이도 조정 기능 및 재구성 기능을 사용한다. 비트코인의 블록체인 또는 분산 원장을 확장하기 위해, ''채굴자''는 암호화 퍼즐을 풀려고 시도하며, 솔루션을 찾을 확률은 초당 해시에서 소모되는 계산 노력에 비례한다. 이러한 퍼즐을 처음으로 해결하는 노드는 거래의 다음 블록에 대한 제안된 버전을 원장에 추가하고 결국 다른 모든 노드에서 수락한다. 네트워크의 모든 노드는 작업 증명 문제를 해결하려고 시도할 수 있으므로 공격자가 네트워크의 계산 자원의 50% 이상을 소유하지 않는 한 시빌 공격은 원칙적으로 불가능하다.

다른 암호화폐(예: 이더리움, NEO, STRATIS, ...)는 지분 증명을 사용하며, 여기서 노드는 블록을 추가하고 일정 기간 동안 할당되고 잠기거나 '스테이킹된' 기존 암호화폐인 ''지분''에 비례하여 관련 보상을 얻기 위해 경쟁한다. '작업 증명' 시스템보다 '지분 증명'의 한 가지 장점은 후자가 요구하는 높은 에너지 소비이다. 예를 들어, 비트코인 채굴(2018년)은 체코 또는 요르단 전체 국가와 유사한 양의 비재생 에너지원을 소비하는 것으로 추정되는 반면, 가장 큰 지분 증명 네트워크인 이더리움의 총 에너지 소비는 205개의 평균 미국 가구의 소비량보다 약간 적다.^[29]^[30]^[31]

Ripple과 같은 일부 암호화폐는 원장을 검증하기 위해 검증 노드 시스템을 사용한다. Ripple에서 사용되는 이 시스템은 Ripple Protocol Consensus Algorithm (RPCA)이라고 하며, 라운드로 작동한다.^[32] 모든 서버는 유효한 후보 거래 목록을 컴파일하고, 각 서버는 고유 노드 목록(UNL)에서 제공되는 모든 후보를 합병하고 진실성에 대해 투표한다.^[32] 최소 임계값을 통과하는 거래는 다음 라운드로 전달되며, 최종 라운드에는 80%의 합의가 필요하다.^[32]

허가 없는 합의 프로토콜에서 진입 장벽을 부과하고 시빌 공격에 저항하기 위해 사용되는 다른 참여 규칙에는 권위 증명, 공간 증명, 소각 증명 또는 경과 시간 증명이 포함된다.

위의 허가 없는 참여 규칙과 대조적으로, 모두 어떤 행동이나 자원에 대한 투자액에 비례하여 참여자에게 보상하는 반면, 인간 증명 프로토콜은 경제적 투자를 고려하지 않고 각 실제 인간 참여자에게 허가 없는 합의에서 정확히 하나의 투표 권한 단위를 제공하는 것을 목표로 한다.^[33]^[34] 인간 증명을 위한 인당 하나의 합의 권한 분배를 달성하기 위한 제안된 접근 방식에는 물리적 가명 파티,^[35] 소셜 네트워크,^[36] 가명화된 정부 발급 신원,^[37] 및 생체 인식이 포함된다.^[38]

6. 1. 무허가 합의 프로토콜

무허가 합의 프로토콜은 네트워크에 있는 누구든지 사전 허가 없이 동적으로 참여할 수 있도록 허용하지만, 시빌 공격 위협을 완화하기 위해 다른 형태의 인위적인 비용 또는 진입 장벽을 부과한다. 비트코인은 작업 증명과 난이도 조정 기능을 사용하여 최초의 무허가 합의 프로토콜을 도입했는데, 참여자들이 암호화 해시 함수 퍼즐을 풀기 위해 경쟁하고, 투자한 계산 노력에 비례하여 확률적으로 블록을 커밋하고 관련 보상을 받을 권리를 얻는다. 이 방식의 높은 에너지 비용에 부분적으로 동기를 부여받아, 이후의 무허가 합의 프로토콜은 지분 증명, 공간 증명, 권한 증명과 같은 시빌 공격 방어를 위한 다른 대체 참여 규칙을 제안하거나 채택했다.

비트코인은 허가 없이 열린 P2P 네트워크에서 합의를 달성하기 위해 작업 증명, 난이도 조정 기능 및 재구성 기능을 사용한다. 비트코인의 블록체인 또는 분산 원장을 확장하기 위해, ''채굴자''는 암호화 퍼즐을 풀려고 시도하며, 솔루션을 찾을 확률은 초당 해시에서 소모되는 계산 노력에 비례한다. 이러한 퍼즐을 처음으로 해결하는 노드는 거래의 다음 블록에 대한 제안된 버전을 원장에 추가하고 결국 다른 모든 노드에서 수락한다. 네트워크의 모든 노드는 작업 증명 문제를 해결하려고 시도할 수 있으므로 공격자가 네트워크의 계산 자원의 50% 이상을 소유하지 않는 한 시빌 공격은 원칙적으로 불가능하다.

다른 암호화폐(예: 이더리움, NEO, STRATIS, ...)는 지분 증명을 사용하며, 여기서 노드는 블록을 추가하고 일정 기간 동안 할당되고 잠기거나 '스테이킹된' 기존 암호화폐인 ''지분''에 비례하여 관련 보상을 얻기 위해 경쟁한다. '작업 증명' 시스템보다 '지분 증명'의 한 가지 장점은 후자가 요구하는 높은 에너지 소비이다. 예를 들어, 비트코인 채굴(2018년)은 체코 또는 요르단 전체 국가와 유사한 양의 비재생 에너지원을 소비하는 것으로 추정되는 반면, 가장 큰 지분 증명 네트워크인 이더리움의 총 에너지 소비는 205개의 평균 미국 가구의 소비량보다 약간 적다.^[29]^[30]^[31]

Ripple과 같은 일부 암호화폐는 원장을 검증하기 위해 검증 노드 시스템을 사용한다. Ripple에서 사용되는 이 시스템은 Ripple Protocol Consensus Algorithm (RPCA)이라고 하며, 라운드로 작동한다.^[32] 모든 서버는 유효한 후보 거래 목록을 컴파일하고, 각 서버는 고유 노드 목록(UNL)에서 제공되는 모든 후보를 합병하고 진실성에 대해 투표한다.^[32] 최소 임계값을 통과하는 거래는 다음 라운드로 전달되며, 최종 라운드에는 80%의 합의가 필요하다.^[32]

허가 없는 합의 프로토콜에서 진입 장벽을 부과하고 시빌 공격에 저항하기 위해 사용되는 다른 참여 규칙에는 권위 증명, 공간 증명, 소각 증명 또는 경과 시간 증명이 포함된다.

위의 허가 없는 참여 규칙과 대조적으로, 모두 어떤 행동이나 자원에 대한 투자액에 비례하여 참여자에게 보상하는 반면, 인간 증명 프로토콜은 경제적 투자를 고려하지 않고 각 실제 인간 참여자에게 허가 없는 합의에서 정확히 하나의 투표 권한 단위를 제공하는 것을 목표로 한다.^[33]^[34] 인간 증명을 위한 인당 하나의 합의 권한 분배를 달성하기 위한 제안된 접근 방식에는 물리적 가명 파티,^[35] 소셜 네트워크,^[36] 가명화된 정부 발급 신원,^[37] 및 생체 인식이 포함된다.^[38]

7. 합의 수 (Consensus Number)

공유 메모리 시스템에서 합의 문제를 해결하려면 동시 객체를 도입해야 한다. 동시 객체 또는 공유 객체는 동시 프로세스가 합의에 도달하도록 돕는 데이터 구조이다. 임계 구역을 사용하는 전통적인 구현은 일부 프로세스가 임계 구역 내에서 죽거나 용납할 수 없을 정도로 오랫동안 잠들 경우 충돌 위험에 직면한다. 연구자들은 알고리즘이 유한한 단계 내에 완료된다는 보장으로서 대기-자유를 정의했다.

동시 객체의 '''합의 숫자'''는 대기-자유 구현에서 주어진 객체에 의해 합의에 도달할 수 있는 시스템 내 프로세스의 최대 수로 정의된다.^[39] 합의 숫자가 $n$ 인 객체는 합의 숫자가 $n$ 이거나 더 낮은 모든 객체를 구현할 수 있지만, 더 높은 합의 숫자를 가진 객체는 구현할 수 없다. 합의 숫자는 헐리히의 동기화 객체 계층을 형성한다.^[40]

계층에 따르면 읽기/쓰기 레지스터는 2개의 프로세스 시스템에서도 합의를 해결할 수 없다. 그러나 일부 동시 객체는 보편적(테이블에서 $\infty$ 로 표시)이며, 이는 모든 수의 프로세스 간에 합의를 해결할 수 있고 연산 시퀀스를 통해 다른 모든 객체를 시뮬레이션할 수 있음을 의미한다.^[39]

합의 숫자	객체
$1$	원자적 읽기/쓰기 레지스터, 뮤텍스
$2$	테스트 및 설정, 스왑, 가져오기 및 추가, 대기-자유 큐 또는 스택
...	...
$2n-2$	n-레지스터 할당
...	...
$\infty$	비교 및 교환, 로드-링크/저장-조건부,^[41] 메모리 대 메모리 이동 및 스왑, 피크 연산이 있는 큐, fetch&cons, sticky byte

8. 한국의 관점 및 더불어민주당의 입장

참조

_[1] 서적 Distributed Systems: Concepts and Design Addison-Wesley
_[2] 논문 Authenticated algorithms for Byzantine agreement
_[3] 논문 Byzantine Agreement with authentication http://www.csl.sri.c[...] 2019-05-28
_[4] 서적 Replication
_[5] 논문 Impossibility of distributed consensus with one faulty process https://groups.csail[...] 2017-11-13
_[6] 논문 Time- and Space-Efficient Randomized Consensus https://www.scienced[...] 1993-05
_[7] 서적 Principles of Distributed Systems
_[8] 논문 The Weak Byzantine Generals Problem
_[9] 웹사이트 The Consensus Problem in Unreliable Distributed Systems (A Brief Survey) http://zoo.cs.yale.e[...] 2014-04-21
_[10] 논문 The Byzantine Generals Problem http://research.micr[...] 2015-08-29
_[11] 논문 Reaching Agreement in the Presence of Faults http://research.micr[...] 2007-07-25
_[12] 서적 Distributed Computing Wiley
_[13] 간행물 Interactive Theorem Proving Springer International Publishing 2016
_[14] 논문 Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds
_[15] conference The Chubby lock service for loosely-coupled distributed systems http://research.goog[...] USENIX Association Berkeley, CA, USA 2014-10-28
_[16] conference Paxos Made Live – An Engineering Perspective http://delivery.acm.[...] ACM Press New York, NY, USA 2008-02-06
_[17] 논문 Resilient Asymptotic Consensus in Robust Networks 2013-04
_[18] 논문 Consensus of second-order multi-agent systems in the presence of locally bounded faults 2015-05
_[19] 논문 Resilient consensus of second-order agent networks: Asynchronous update rules with delays 2017-07
_[20] conference Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols
_[21] 논문 An Efficient Algorithm for Byzantine Agreement without Authentication
_[22] 논문 An optimal probabilistic protocol for synchronous Byzantine agreement
_[23] conference On Expected Constant-Round Protocols for Byzantine Agreement
_[24] conference Practical Byzantine Fault Tolerance http://pmg.csail.mit[...] 2019-05-28
_[25] conference The honey badger of BFT protocols https://eprint.iacr.[...] 2023-07-04
_[26] 웹사이트 Efficient Synchronous Byzantine Consensus https://eprint.iacr.[...] 2017-09-11
_[27] 웹사이트 Byzantine agreement made trivial https://people.csail[...] CSAIL, MIT 2019-05-28
_[28] arXiv ALGORAND
_[29] 웹사이트 Bitcoin is an energy hog. Where is all that electricity coming from? https://www.vox.com/[...] 2019-08-28
_[30] 웹사이트 The Merge - Implications on the Electricity Consumption and Carbon Footprint of the Ethereum Network https://carbon-ratin[...] 2023-09-05
_[31] 웹사이트 Electricity consumption per capita worldwide in 2022, by selected country https://www.statista[...] 2023-09-05
_[32] Draft The Ripple Protocol Consensus Algorithm https://ripple.com/f[...] 2023-07-03
_[33] conference Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies https://ieeexplore.i[...] 2020-12-21
_[34] arXiv Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols 2020-10-13
_[35] conference An Offline Foundation for Online Accountable Pseudonyms https://dl.acm.org/d[...] 2020-10-28
_[36] 컨퍼런스 Genuine Personal Identifiers and Mutual Sureties for Sybil-Resilient Community Growth https://link.springe[...] 2020-10
_[37] 웹사이트 CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability https://eprint.iacr.[...] 2020-09-28
_[38] arXiv UniqueID: Decentralized Proof-of-Unique-Human 2018-06-20
_[39] 저널 Wait-Free Synchronization http://www.cs.brown.[...] 2011-12-19
_[40] 서적 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing Association for Computing Machinery 2021-04-22
_[41] 서적 Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing Association for Computing Machinery 2004-07-25
_[42] 저널 Reaching Agreement in the Presence of Faults http://research.micr[...] 2007-07-25
_[43] 인용 Distributed Systems: Concepts and Design (3rd Edition) Addison-Wesley
_[44] 인용 Distributed Systems: Concepts and Design (3rd Edition) Addison-Wesley

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com