Linear님의 정보보호 공부 블로그

1 Abstract

인증은 모든 형태의 원격 통신에 필수적입니다. 인증의 부재는 중간자 공격 (man-in-the-middle attack)의 문을 열어 주며, 핵심 순간에 수행된다면 전체 상호 작용을 파괴 할 수 있습니다. 현재 인터넷 인증 방식에는 인증 기관 및 신뢰 웹이 포함됩니다. 이러한 접근법은 모두 중요한 단점이 있습니다. 전자는 신뢰할 수있는 제 3 자에게 의존하여 중앙 실패 지점을 도입하고, 후자는 진입 장벽이 높습니다. Certcoin은 대체, 공개 및 분산 인증 방식을 제안합니다. Certcoin의 핵심 아이디어는 도메인 및 관련 공개 키의 공개 원장을 유지하는 것입니다. Certcoin 구성표와 스마트 폰과 같이 제한된 저장 용량을 갖춘 장치에서 Certcoin을보다 쉽게 사용할 수 있도록 여러 가지 최적화 방법을 설명합니다. 우리의 최적화는 암호화 누적 기 및 분산 해시 테이블과 같은 도구를 사용합니다.

2 Existing Approaches to Authentication

1976 년에 공개 키 암호가 출현하기 전에는 대부분의 보안 메시지 전송이 이전에 일부 비밀 키 K를 공유 한 두 당사자 모두에게 의존하는 대칭 암호화 프로토콜을 사용하여 수행되었습니다. 공격자가 비밀 키를 추측 할 가능성은 매우 낮기 때문에 이 구조에서 인증은 간단합니다. K로 암호화 된 모든 개별 메시지는 인증 된 사용자로 간주됩니다. 그러나 통신하기 전에 키를 교환하는 것은 많은 수의 엔티티가 네트워크에 자유롭게 가입하고 탈퇴 할 수 있어야하며 네트워크상의 다른 엔티티와 안전하게 통신 할 수 있어야하는 인터넷과 같은 동적 환경에서는 비실용적입니다. 엔티티들의 수가 증가함에 따라 각 쌍의 엔티티가 자신의 공유 키를 빠르게 설정하는 것은 실행 불가능하게된다 [11].

공개 키 암호화는이 확장 성 문제를 해결합니다. ; 그러나 인증은 훨씬 간단합니다. 전통적인 공개 키 시스템에서 사용자는 메시지 수신자의 공개 키를 검색하고 해당 키로 암호화 한 다음 자체 서명 키로 메시지에 서명합니다. 그러면 수신자는 메시지를 해독 할 수있는 유일한 사람입니다. 그 사람은 비밀 암호 해독 키를 가진 유일한 소유자이기 때문입니다. 이 설정은 사전 키 협약의 필요성을 없애 주지만, 모든 엔티티가 이제 암호화를 생성 할 수 있기 때문에 발신자를 인증해야하는 문제가 발생합니다. 그는 디지털 서명을 기반으로 보낸 사람의 공개 키를 확인할 수 있지만 보낸 사람의 신원을 결정하기 위해 공개 키만 사용할 수는 없습니다 [21].

PKI (Public Key Infrastructure) 개념은 메시지 보낸 사람의 신원을 확인해야하는 필요성에서 비롯되었습니다. PKI는 일반적으로 각 개체의 공개 키를 증명하는 인증서를 발급합니다. 또한 PKI는 비밀 키가 유실되었거나 관련 개인이 악의적 인 것으로 간주 될 때 공개 키가 손상된 경우 인증서를 해지 할 수 있습니다. 현재 가장 일반적으로 사용되는 두 가지 접근 방식은 중앙 집중식의 신뢰할 수있는 제 3 자 인증 기관 (CA)과 종종 피플 - 피어 인증의 분산 네트워크 (Phil Zimmerman의 작성자 인 Phil Zimmerman PGP)

2.1 인증 기관

일반적으로 인증 기관 (CA)은 일반적으로보다 일반적인 선택으로 사용자 네트워크에 대한 디지털 인증서를 제공하고 관리하는 신뢰할 수있는 제 3 자 역할을합니다. 이를 수행하기 위해 CA에는 사용자 신원을 확인하고 Distinguish Name (DN, 예 : Google 또는 Facebook)을 할당하고 DN과 함께 공개 키를 기록하는 일종의 등록 프로세스가 있어야합니다. 이러한 레코드에는 데이터 암호화 또는 서명 확인 여부와 상관없이 키 용도에 대한 표시뿐만 아니라 만료 날짜가 포함됩니다. CA는 두 가지 목적을 수행합니다. 즉, 사용자가 특정 공개 키를 보유하고 사용자에 해당하는 공개 키의 조회를 용이하게하는지 확인하는 것을 용이하게합니다. 검증은 각 사용자에게 발급 된 인증서를 통해 수행됩니다. 그 인증서는 CA가 서명 한 "사용자 x가 공개 키 PK를 보유하고있는"형식의 진술입니다. 조회는 모든 사용자가 다른 개인의 공개 키를 요청하도록 허용하여 수행됩니다. 그런 다음 요청자는 해당 개인과 지식에 대한 지식이 없음을 증명함으로써 개인이 해당 비밀 키를 보유하고 있는지 확인할 수 있습니다. CA는 신뢰할 수있는 사람이 인증서를 신뢰해야하기 때문에 궁극적으로 네트워크 신뢰 에이전트 역할을합니다 [16].

이러한 레코드에는 데이터 암호화 또는 서명 확인 여부와 상관없이 키 용도에 대한 표시뿐만 아니라 만료 날짜가 포함됩니다. CA는 두 가지 목적을 수행합니다. 즉, 사용자가 특정 공개 키를 보유하고 사용자에게 해당하는 공개 키의 조회를 용이하게하는지 확인하는 것을 용이하게합니다. 검증은 각 사용자에게 발급 된 인증서를 통해 수행됩니다. 그 인증서는 CA가 서명 한 "사용자 x가 공개 키 PK를 보유하고있는"형식의 진술입니다. 조회는 모든 사용자가 다른 개인의 공개 키를 요청하도록 허용하여 수행됩니다. 그런 다음 요청자는 해당 개인과 지식에 대한 지식이 없음을 증명함으로써 개인이 해당 비밀 키를 보유하고 있는지 확인할 수 있습니다. CA는 신뢰할 수있는 사람이 인증서를 신뢰해야하기 때문에 궁극적으로 네트워크 신뢰 에이전트 역할을합니다 [16].

많은 엔티티는 비밀 키가 유실 된 경우 안전하게 비밀 키를 백업하고자 할 수 있습니다. 이를 수행하는 프로세스를 키 복구라고하며 오늘날의 많은 CA가 제공하는 기능입니다. 해독 키가 손실되면 민감한 데이터 또는 중요한 데이터가 영구적으로 손실 될 수 있습니다. 다른 한편, 서명 키의 손실은 상대적으로 중요하지 않습니다. 이전에 서명 된 메시지는 여전히 공개 키로 검증 될 수 있으며 (취소되지 않았다고 가정) 사용자는 서명을 계속하기 위해 새 키 쌍을 간단히 얻을 수 있습니다. 또한 CA와 서명 키를 백업하면 CA가 키 소유자로 가장 할 수 있습니다. 따라서 CA가 서명 키가 아닌 암호 해독 키를 백업하는 것이 가장 적합합니다 [13]. 따라서 모든 사용자는 두 기능에 동일한 키 쌍을 사용하는 대신 두 개의 키 쌍 (암호화 및 서명)을 생성해야합니다.

최근에는 너무 많은 신뢰가 CA에 배치되고 있음을 보여주는 수많은 사건이있었습니다. CA는 해킹 당했고 (예 : DigiNotar 사건), 고객 (예 : TrustWave 사건)에 하위 루트 인증서를 발행하여 고객이 자체적으로 인증서를 발급 할 수있게했습니다.

이러한 사고를 방지하기위한 한 가지 방법은 CA의 작업에 투명성을 도입하는 것입니다. Google CertiPate 투명성 프로젝트 [3]는 정확하게 이것을 시도합니다. 그들은 세계적으로 독립된 서버를 숫자 (예 : ≤ 1000)에 대한 공용 추가 전용 로그를 유지할 것을 제안합니다. 이러한 각 로그 서버는 별도의 CA에 의해 실행될 수 있습니다. 그런 다음이 로그는 다른 공개적으로 실행되는 서버에 의해 의심스러운 인증서가 있는지 모니터하고 모든 사람이 실행할 수있는 경량의 감사 소프트웨어로 일관된 동작을 감사합니다. 이렇게하면 도메인의 소유자가 자신의 도메인에 대해 발급 된 모든 인증서를 볼 수있게되어 모든 잘못된 인증서를 발견 할 수 있습니다.

2.2 Web of Trust

실제로 사용되는 두 번째 주요 PKI는 PGP Trust of Web (WoT)입니다. 이 시스템에서는 인증이 완전히 분산되어 있습니다. 사용자는 자신의 공개 키에 서명함으로써 신뢰할 수있는 다른 사람들을 지정할 수 있습니다. 그렇게함으로써 사용자는 자신의 공개 키와 신뢰할 수있는 것으로 간주되는 엔티티의 디지털 서명을 포함하는 인증서를 누적합니다. 그런 다음 인증서는 자신이 신뢰하는 사람의 서명이 포함되어 있는지 확인할 수있는 경우 당사자가 신뢰할 수 있습니다 [21].

이 시스템은 중앙 집중식 장애 지점을 없애기 때문에 분산 된 성격을 활용합니다. 그러나 신원 또는 원격 사용자가 네트워크에 가입하는 것은 일반적으로 신원을 확인하고 공개 키를 처음 서명 한 사람과 만나는 것이 일반적이므로 만나야합니다. 또한 CA와 달리 WoT는 키 복구를 처리 할 방법이 없습니다. 사용자는 개인 키가 분실되거나 손상된 경우 자신의 인증서를 철회하도록 임명 된 다른 사용자를 자신의 "지정된 취소 자"로 선택하는 것으로 제한됩니다. 이러한 변화에도 불구하고, Trust of Web은 상당한 수정없이 거의 25 년 동안 성공적으로 운영되었습니다.

2.3 Certcoin: the Best of Both Worlds

투명한 인증 기관과 웹 신뢰의 장점을 통합 한 시스템 인 Certcoin을 소개합니다. Google CertiPate 투명성 프로젝트와 마찬가지로 Certcoin은 완전히 공개되고 감사가 가능합니다. WoT와 마찬가지로 Certcoin은 분산되어 있으며 단일 실패 지점이 없습니다. 우리는 3 절에서 Certcoin 프로토콜의 세부 사항을 제공합니다.

3 The Fundamental Certcoin Protocol(기본 Certcoin 프로토콜)

Bitcoin을 기반으로 한 새로운 분산 형 공개 키 인프라를 제안합니다. 주어진 신원 또는 도메인에 해당하는 공개 키를 신뢰할 수 있고 영구적으로 게시하는 기능은 인증 방법이 간단합니다. Bitcoin과 다른 cryptocurrencies는 정확히 같은 게시판을 구현합니다.

우리는 Namecoin [2] 위에 프로젝트를 분기하고 CertCoin 트랜잭션이 블록 체인에 제대로 구축되도록 병합 된 마이닝 프로토콜을 활용하여 Certcoin을 구축 할 것을 제안합니다. Namecoin은 .bit 주소에 대한 분산 DNS로 작동하도록 설계된 cryptocurrency입니다. 도메인 등록 및 업데이트를 지원하는 세 가지 유형의 트랜잭션 (이름 신규, 이름 갱신 및 이름 갱신)이 있습니다. 새로운 이름은 일반적으로 Namecoin이 0.01 단위 인 반면 나머지는 무료입니다.

3.1 Registering a Domain with Certcoin(Certcoin으로 도메인 등록)

"온라인" 비밀 키는 웹 사이트를 호스팅하는 서버와주고받는 메시지를 인증하는 데 사용됩니다. 이 비밀 키는 Certcoin에서 웹 사이트를 인증하는 데 사용되는 기본 키이기도합니다. 인증의 일부로 해당 키 지식에 대한 증거가 필요할 것입니다.

"오프라인" 비밀 키는 인터넷에 연결된 장치에 저장된 결과 온라인 키가 직면하게 될 보안 위협과 동일한 보안 위협에 취약하지 않은 안전한 장소에 저장됩니다. 이 기본 키는 보안 위반이나 키 손상의 경우 새 키를 서명하거나 취소하는 데 주로 사용됩니다. 이에 대해서는 4.2 절에서 더 자세히 설명 할 것이다.

도메인에 대해 새 키를 만들면 같은 유형의 이전 키로 서명됩니다. 이렇게하면 언제든지 도메인에 등록 된 두 유효한 키를 일련의 서명 된 문을 통해 도메인에 등록 된 처음 두 키 쌍으로 추적 할 수 있습니다.

3.2 Updating a Public Key Corresponding to a Domain(도메인에 해당하는 공개 키 업데이트)

도메인 d에 해당하는 공개 키 pkold를 새로운 공개 키 pknew (동일한 온라인 / offline 형식)로 변경하는 것은 게시로 수행됩니다. 

우리 게시판으로 이동합니다. 여기서 σ는 보안 디지털 서명 알고리즘입니다. 우리는 여기에서 디지털 서명을 활용하여 새로운 공개 키가 이전 공용 키에 해당하는 비밀 키 보유자 만 게시 할 수 있도록합니다. 이 업데이트 트랜잭션은 서명이 pkold로 검증 된 경우에만 처리됩니다.

3.3 Verifying / Looking Up a Public Key(공개 키 확인 / 검색)

공개 또는 온라인 유형의 공개 키 pk가 도메인 d에 해당하는지 확인하는 것은 블록 체인을 탐색하고 다음을 확인하는 것입니다.

• 도메인 d가 정확히 한 번 등록되었습니다.

• d에 해당하는 공개 키에 대한 후속 업데이트의 모든 서명은 d의 이전 공개 키로 검증합니다.

• 마지막 업데이트로 pk가 d에 해당하는 공개 키가되고

• 도메인 d의 소유자라고 주장하는 사용자는 a zero-knowledge proof of knowledge를 사용하여 pk에 해당하는 비밀 키 sk를 알고 있습니다.

도메인 d에 해당하는 공개 키 pk (offline 또는 online 유형 중 하나)를 찾으려면 블록 체인을 탐색하고 다음을 수행해야합니다.

• 도메인 d가 정확히 한 번 등록되었는지 확인합니다.

• d에 해당하는 공개 키에 대한 후속 업데이트의 모든 서명이 이전 공개 키로 검증되었는지 확인합니다.

• d에 해당하는 공개 키에 대한 최종 업데이트를 찾고 업데이트가 발생한 공개 키 pk를 저장합니다.

• 도메인 d의 소유자라고 주장하는 사용자가 지식 지식이없는 지식을 사용하여 pk에 해당하는 비밀 키 sk를 알고 있는지 확인합니다. 제로 지식 지식 지식이 유효한 경우, pk를 리턴하십시오. 그렇지 않으면 ⊥를 돌려 준다.

4 Key Recovery and Revocation(키 복구 및 해지)

완전 기능 인증 시스템은 키 해지 및 복구를위한 일부 기능을 제공해야합니다. 특정 비밀 키가 손상되거나 도난 당하거나 단순히 만료 될 수 있습니다.이 경우 키 소유자는 이전 키를 폐기하고 새 키를 가져와야합니다. 마찬가지로 암호는 잊어 버릴 수 있으며 특정 복구 방법이 필요할 수 있습니다. 전통적인 인증 기관 시스템에서는 이러한 목적 중 하나를 달성하기 위해 단순히 고객 지원 부서에 전화 할 수 있습니다. 그러나 분산화 된 시스템에서는 처음부터 기계에 폐기 및 복구 메커니즘을 구축해야합니다.

4.1 Key Recovery(키 복구)

사용자가 도메인에 대한 비밀 / 공개 키 쌍을 생성하면 Certcoin은 비밀 키가 최소한 3 개의 신뢰할 수있는 "친구"사이에서 공유되는 복구 시스템(e.g. using the Shamir secret sharing paradigm [22])을 설정해야하며 재구성을 위해 최소 2 개의 임계 값이 필요합니다. 또한 향상된 보안을 위해 각 신뢰할 수있는 친구는 다른 사람의 신원을 알지 않아야합니다. 실제로는 다른 사람을 신뢰하기를 원하지 않는 사용자는 "친구"를 자신이 만든 여러 가지 Certcoin 계정으로 지정하여 이러한 보안 목표를 달성 할 수 있습니다. Bitcoin 지갑 관리 플랫폼 인 Armory [12]에서도 이와 비슷한 기술을 사용합니다. 여기서 Armory [12]는 지갑의 열쇠가 비밀리에 복구가 가능하도록 공유합니다.

4.2 Key Revocation(키 폐지)

전통적인 공개 키 인프라에서 인증서는 특정 연령대에 만료되거나 인증서 폐기 목록 (CRL) [10]에 추가되거나 온라인 인증서 상태 프로토콜 (OCSP) [14]을 통해 폐기됩니다. 

Certcoin은 lifetime 가치를 창출 할 수 있습니다. 각 공개 키는 관련 타임 스탬프를 가지며 공개 키가 Lifetime 보다 이전에 생성 된 경우 연령만으로 거부해야합니다. 공용 키는 전통적인 PKI와 마찬가지로 이유 코드(reason code)를 사용하여 수동으로 해지 할 수 있습니다. 원인 코드는 "지정되지 않음", "키 손상", "CA 손상", "변경된 상태", "대체 된 상태"또는 "작동 중지"중 하나 일 수 있습니다. 

항상 각 도메인에는 두 개의 연결된 비밀 키가 있습니다. 하나는 online 이고 다른 하나는 offline 인 것입니다. 서로 다른 State의 타협은 서로 다른 방식으로 대응 될 수 있습니다. Google은 공격자가 키에 액세스하고 공격자가 키를 도용하는 (즉, 도메인 소유자가 멀리있는 키에 액세스하는) 경우를 구분합니다.

• 공격자가 하나의 비밀 키만 액세스 할 수 있는 경우 : 실제 도메인 소유자는 여전히 자신의 비밀 키 모두에 액세스 할 수 있으며 두 키를 사용하여 작성한 하나의 키와 서명하려고 시도한 다른 키를 폐기하는 상태의 서명에 서명 할 수 있습니다. 그런 다음 도메인 소유자가 현재 두 키 쌍을 사용하여 손상된 키를 업데이트합니다. 마지막으로, 두 가지 이전 보안 키는 손상된 키의 모든 향후 작업을 무효로하는 문에 서명하는 데 사용됩니다. 이렇게 하면 실제 도메인 소유자는 다시 두 개의 비협조적인 키의 유일한 소유자가되며 공격자는 무효화 된 키에만 액세스 할 수 있습니다. 이 모든 진술은 블록 체인에 트랜잭션으로 게시되며 공개적으로 검증 할 수 있습니다. 블록이 많은 문이 하나의 블록에 나타날 수 있기 때문에 동일한 블록에서 해지 된 키 (자매 키로 서명되지 않은 키)로 서명 된 모든 새 키는 블록 내의 타임 스탬프에 관계없이 자동으로 무효화됩니다. 이렇게하면 공격자가 이전 키를 취소 할 때 바로 제어 할 수있는 새 키에 침입 할 수 없게됩니다.

• 공격자가 온라인 비밀 키를 도용 한 경우 : 도메인 소유자가 온라인 비밀 키에 대한 모든 액세스 권한을 잃고 공격자가 도메인 소유자가 키 복구 시스템을 통해 키를 복구하지 못하도록 관리합니다. 모든 비밀 키는 온라인 비밀 키에 의해 생성 된 모든 서명에 대해 거부권을 행사하기 때문에 모두 손실되지 않습니다. 도메인 소유자는 offline 비밀 키를 사용하여 손상된 온라인 키로 서명 된 모든 키를 무효로하는 명령문에 서명하고 손상된 키 자체를 해지 할 수 있습니다. 다음으로, 도메인 소유자는 새로운 온라인 비밀 키를 생성하기 위해 offline 비밀 키를 사용할 수 있습니다. 그런 다음 저장 공간을 확보하기 위해 비밀 키를 반환한다. 

• 공격자가 온라인 및 오프라인 키 모두에 액세스 할 수있는 경우 : 도메인 소유자는 여전히 두 키에 액세스 할 수 있습니다. 두 사람은 실제 도메인 소유자와의 상대를 구별 할 수있는 방법이 없으므로 두 키를 모두 사용하여이 키로 서명 된 현재 및 미래의 진술을 모두 무효화하는 성명서에 서명 할 수 있습니다.

• 공격자가 두 비밀 키를 훔친 경우 : 도메인 소유자가 더 이상 자신의 키에 액세스 할 수 없으며 Certcoin 프로토콜 내에서 그러한 상황을 처리 할 방법이 없습니다.

위에서 설명한 방식으로 비밀 키 손상을 해결하려면 먼저 손상을 발견해야합니다.

5 Cutting Down on Storage: Accumulators for Key Verification(저장 공간 절약 : 키 확인 용 축압기)

Certcoin을 배치하는 데있어서 한 가지 중요한 문제는 모든 Certcoin 사용자가 전체 블록 체인을 저장해야하는 것입니다. Bitcoin 블록 체인은 현재 16GB이며, 월 약 1GB의 속도로 증가하고있는 것으로 보입니다 [1]. Certcoin을 순진하게 구현하려면 검증을 수행하는 모든 장치 또는 엔터티에 대용량 저장 용량이 필요합니다. 그러나 이것이 항상 가능한 것은 아닙니다. 예를 들어 스마트 폰의 브라우저에는 사용 가능한 많은 저장 공간이 없을 수도 있습니다.

등록 된 도메인 및 키의 현재 상태 (즉, 도메인에서 현재 키까지의 맵) 만 유지하면 조금 더 나아질 수 있습니다. 여전히 등록 된 도메인 수에는 선형적인 저장 공간이 필요하지만 전체 블록 체인을 순회하는 것과는 달리 검사 당 일정한 시간 만 필요합니다. 또한 Bitcoin 프로토콜 [20]을 사용하여 추가 블록을 검증 할 수 있도록 블록 체인의 마지막 몇 블록을 저장해야합니다. 나머지 블록은 포함 된 공개 키 업데이트를 확인한 후 내용이 저장 상태를 업데이트하는 데 사용 된 후에 폐기됩니다. 그러나 등록 된 도메인 수가 선형화 된 저장 공간은 여전히 비현실적입니다. 스마트 폰의 브라우저는이를 지원할 수 없습니다.

우리는 Certcoin 저장 요구 사항을 낮추기 위해 Accumulator [15]의 사용을 제안합니다. Accumulator는 세트의 구성원을 테스트하는 데 사용되는 디지털 객체입니다. Accumulator 는 형식 (d, pk) 또는 형식 (d, pk, exp)의 튜플을 저장합니다. 여기서 d는 도메인이고, pk는 공개 키이고, exp는 선택적 만료 날짜입니다. 그런 다음 Accumulator 는 pk가 d에 등록되었는지 여부를 결정하는 데 사용될 수 있습니다. 대응하는 비밀 키 sk의 지식은 여전히 zero-knowledge proof 을 통해 증명 될 필요가있다. 이 절에서는 암호화 Accumulator를 설명하고 Certcoin에서 이 암호화 Accumulator를 사용하는 방법에 대해 설명합니다.

5.1 Cryptographic Accumulator Definitions(암호 누산기 정의)

디지털 서명에 대한 분산 형 대안으로서 암호화 Accumulator의 사용은 Benaloh와 de Mare에 의해 1994 년에 처음 기술되었다. Accumulator는 일련의 요소를 일정한 크기로 표현한 것입니다. Accumulator에 요소를 추가하면 증인이 생성되어 해당 요소가 추가되었음을 입증하는 데 사용할 수 있습니다. 보다 공식적으로, Accumulator 스키마는 4 개의 다항식 시간 알고리즘으로 구성됩니다.

• Gen (1^k) → a 

보안 매개 변수 k가 주어진 경우 빈 Accumulator의 초기 값과 추가 매개 변수를 생성합니다.

• Add (a, y) → (a', w) 

누산기 a의 현재 상태와 y 가산 값을 취하고 해당 증인 w뿐만 아니라 Accumulator a'의 새로운 상태를 반환합니다.

• WitAdd (w, y) → w' 

증인 w의 현재 상태와 새로운 값 y를 Accumulator에 가산하여 갱신 된 증인 w'을 반환한다.

• Ver (a, y, w) → {0,1}

Accumulator a의 현재 상태, a의 멤버가 확인되는 값 y 및 y가 a에 있는 것의 증인 w 그리고 y가 a에있는 것처럼 보이는 경우 1을 반환하고 그렇지 않으면 0을 반환합니다.

Accumulator는 다음과 같은 속성이있는 경우 안전합니다.

• Correctness(정확성) : 값 y가 일치하는 것의 최신 증인은 항상 최신 Accumulator에서 y의 멤버 자격을 확인하는 데 사용할 수 있습니다. 좀 더 공식적으로, 모든 유효한 값 y와 유효한 값 [y1, ..., yl1], [y1, ..., yl2]의 추가 집합

• Soundness(건전성) : y 멤버십에 대한 검증이 성공하는 방식으로 Accumulator에 추가되지 않은 값 y에 대한 증인 w를 제작하는 것은 어렵습니다. 보다 공식적으로,  oracles a에서 Add 및 WitAdd 블랙 박스 액세스가있는 어떠한 확률적인 polynomial-time 공격자 A에 대해

여기서 y는 Add를 호출하지 않은 A의 요소이고, a는 공격자가 Add에 대한 모든 호출을 한 후에 Accumulator의 상태이며, negl은 보안 매개 변수에서 무시할 수있는 함수입니다.

Accumulator에서 추가 속성이 필요할 수 있습니다.

• Compactness : Accumulator의 바람직한 특성은 얼마나 많은 항목이 추가 되더라도 작게 유지된다는 것입니다. Accumulator는 크기가 일정하면 (즉, 포함하는 요소의 수에 관계없이) 작다. 일부 Accumulator는 포함하는 요소의 수와 로그 적으로 증가합니다.

• Dynamism : 2002 년 Jan Camenisch와 Anna Lysyanskaya [9]는 삭제 알고리즘 Del과 증인 업데이트 알고리즘 WitDel을 사용하여 Accumulator에서 요소 삭제를 지원하는 동적 Accumulator의 개념을 도입했습니다.

• 보편성 (Universality) : 2007 년 Jiangtao Li, Ninghui Li와 Rui Xue [18]는 보편적 인 Accumulator의 개념을 소개했다. 보편적 인 Accumulator는 멤버쉽 증명 이외에 비회원 증명을 지원하는 Accumulator이다.

• Strength: • 장점 : 2008 년 Philippe Camacho, Alejandro Hevia, Marcos Kiwi 및 Roberto Opazo [7]는 Accumulator 관리자를 신뢰할 만한 것으로 간주하지 않는 강력한 Accumulator 개념을 소개하였다. 강한 Accumulator는 5.2.1 절에 설명 된 RSA Accumulator에서와 같이 Accumulator 생성 또는 유지 관리에 트랩 도어 정보를 사용할 수 없습니다. 

5.2 Cryptographic Accumulator Constructions(암호화 Accumulator 구조)

RSA 구성, Bilinear Map 구성 및 Merkle Hash Tree 구성을 포함하여 여러 가지 알려진 Accumulator 구조가 있습니다. Bilinear Map 구조의 속성은 RSA 구조의 속성과 비슷하므로이 백서에서는 이에 대해 자세히 설명하지 않습니다. 또한 우리는 이러한 Accumulator 이외에 블룸 필터 (Bloom Filter)는 증인을 활용하지 않기 때문에 기술적으로 암호화 Accumulator가 아니지만 효율적인 멤버십 테스트에도 사용할 수 있어 고려한다. 그림 1의 표에는 이러한 모든 구성의 일부 속성이 요약되어 있습니다.

5.2.1 The RSA Accumulator(RSA 누산기)

Benaloh와 de Mare [5]는 해쉬 함수 h : X × Y → X 인 준 환원 해쉬 함수로부터 Accumulator를 구성 할 것을 제안했다. 모든 x ∈ X와 y1, y2 ∈ Y에 대해

순서는이 해시 함수의 적용에 중요하지 않으므로 h(x, {y1, y2, ..., yn}) 를 h(h(...h( h(x ,y1), y2)...), yn).로 표시한다.

Accumulator는 고정 된 x로 시작하여 값 yi가 h에 반복적으로 적용되어 집합에 추가 될 수 있습니다. h가 단방향 함수일 경우 집합의 yi 값은 h(w, yi) = a 의 검사에 의해 주어진 증인 w = h(x, {yj} j != i)에서 Accumulator에 테스트 될 수 있다. 이것은 분명하다: 값 yi가 합법적으로 a에 추가되었다면 유효한 w = h (x, {yj} j != i)가 유지되었을 것이다. 이것은 또한 h는 단방향이기 때문에, 값 w와 yi는 주어진 a만을 얻는 것이 어렵다.

Zn* 의 거듭 제곱은 단방향 및 준 가변 (quasi-commutative)이며 다음과 같이 암호화 Accumulator를 구성하는 데 사용할 수 있습니다.

v를 충돌 방지 해시 함수(collision-resistant hash function)라고합시다.

v를 사용하는 것은 y = yi yj에 대한 명백한 증인 제조 공격(obvious witness fabrication attack)을 방지하기 위해 필요하며, 여기서 yi 및 yj는 Accumulator에 합법적으로 추가됩니다.

이 구성은 n의 인수 분해가 적에게 알려지지 않은 경우에만 안전합니다. 즉, n의 인수 분해는 trap door입니다. 그러나 이 trap door는 Accumulator를 사용하지 않고 Accumulator를 만드는 데만 필요합니다. Add, WitAdd 및 Ver 알고리즘은 모두 n의 인수 분해를 모른 채 수행 될 수 있습니다. 따라서 Gen가 trap door 정보를 사용하기 때문에 RSA Accumulator가 강력한 Accumulator가 아닌 반면 안전한 방식으로 Gen를 수행하고 (아마도 다중 사용자 계산을 통해) Accumulator에 결과 Accumulator를 제공함으로써 강력한 Accumulator manager를 만들 수 있습니다.

Jan Camenisch와 Anna Lysyanskaya [9]는 RSA 누산기를 동적으로 만드는 방법을 제시한다. 다음과 같이 삭제 알고리즘 Del 및 추가 미러링 모니터 업데이트 알고리즘 WitDel을 설명합니다.

Del과 WitDel은 Gen과 마찬가지로  trap door에 대한 지식이 필요합니다.

5.2.2 The Merkle Hash Tree Accumulator

Jiangtao Li, Ninghui Li와 Rui Xue [18]는 Merkle Hash Trees의 건축과 유사한 방식으로 Accumulator를 건설 할 것을 제안했다. 그들의 논문에서 제시된 구성은 보편적으로 설계 되었기 때문에 더 복잡하고 다소 효과적입니다. 보편성이 Certcoin Accumulator의 매우 중요한 자산이라고 생각하지 않기 때문에 비공식적으로 Merkle 해시 트리 구조의 약간 더 단순한 버전을 제시합니다.

h가 충돌 방지 해시 함수라 하자. 트리 깊이 i (i는 1부터 log(n) 까지의 집합의 원소)와 거의 같은 수준에서 이 Accumulator는 log (n) 평형 Merkle Hash Tree 뿌리의 목록을 유지하며,  여기서 n은 Accumulator의 요소 수이다.

a = [r1, ..., rlog (n)]이라 하자. 

6 Cutting Down on Storage: Distributed Hash Tables for Key Lookup(저장소 축소 : 키 조회를 위한 분산 해시 테이블)

암호화 Accumulator는 대용량 저장 오버 헤드를 발생시키지 않고 공개 키를 검증하는 문제를 해결합니다. 이제는 비슷한 제한이있는 공개 키를 가져 오는 문제로 넘어갑니다. Certcoin의 디자인은 인증과 배포를 명확하게 구분합니다. 도메인 구매 및 공개 키는 블록 체인에 저장되어 공개적으로 확인할 수있는 자격 증명 소스를 생성합니다. 불행히도 블록 체인은 본질적으로 키 - 값 검색을 지원하지 않으므로 동적 쿼리를 원활하게 수행 할 수 없습니다. 기존의 CA는 일반적으로 자체 인증 키 서버 역할을하므로 네트워크가 다른 사용자의 공개 키를 검색하도록 쿼리할 수 있습니다. 실용적인 PKI가되기 위해서는 CertCoin이 선택한 ID에 대한 공개 키를 효율적으로 검색하기위한 자체 인터페이스도 제공해야합니다. 이를 달성하기 위해 우리의 솔루션은 인증 된 DHT를 사용하여 구입 한 도메인 모음에 의해 유지 관리되는 탄력적이고 분산 된 키 서버를 만드는 방법을 제안합니다. 따라서 Certcoin의 배포 메커니즘은 자체 유지 키 전달 서비스를 만들기 위해 Kademlia DHT [19]의 고유 한 속성 중 일부를 사용합니다.

표준 형식에서 Kademlia는 인증되지 않아 중독, 라우팅 및 Sybil 공격에 취약합니다. 그러나 아래에서는 Certcoin의 블록 체인에 저장된 인증 데이터를 활용하여 각각 예방 방법을 설명합니다. 물론 우리는 도메인을 구입했는지 여부에 상관없이 모든 당사자가 Certcoin의 공개 키에 액세스 할 수 있기를 원합니다. 따라서 키 조회 요청을 인증하지 않기로 선택합니다. 이러한 요청의 읽기 전용 특성으로 인해 외부 공격자가 이 RPC를 악용하여 키 - 값 쌍을 변경할 수 없습니다. 따라서이 절의 나머지 부분에서는이 작업을 인증 문제에서 제외합니다.

6.1 Design of the Kademlia Distributed Hash Table(Kademlia 분산 해시 테이블 설계) // https://github.com/pRivAte12/kademila-kor

Kademlia가 제공하는 많은 바람직한 특성은 라우팅 테이블을 업데이트하기 위해 최소의 통신 오버 헤드를 발생시키는 대칭 라우팅 프로토콜의 결과입니다. Kademlia가 제공하는 많은 바람직한 특성은 라우팅 테이블을 업데이트하기 위해 최소의 통신 오버 헤드를 발생시키는 대칭 라우팅 프로토콜의 결과입니다. 이 프로토콜은 네트워크를 통해 전송 된 모든 패킷이 실행 가능한 노드 및 라우트의 상태에 대한 유용한 정보를 포함하도록 설계되었습니다. 따라서 Kademlia는 다른 노드에서 지속적으로 통신하고 사용자로부터 질의하여 장애를 자동으로 라우팅합니다. 따라서 Kademlia는 다른 노드에서 지속적으로 통신하고 사용자로부터 질의하여 장애를 자동으로 라우팅합니다.

또한 Kademlia는 라우팅 테이블에서 가장 오래된 활성 노드를 유지하려고 시도하여 노드 장애가 가동 시간과 반비례한다는 사실을 활용하여 가장 신뢰할 수있는 노드에 대한 경로가 위에 설명 된대로 네트워크의 다른 라우팅 테이블로 전파되도록 합니다 . 그런 다음 계속 증가하는 다른 라우팅 테이블에서 그 존재가 유지되는 방법으로 DHT의 노드가 온라인 상태를 유지하는 것이 가장 좋습니다. DHT의 응답 시간은 대상에 도달하는 데 필요한 숫자 홉에 따라 달라 지므로 신뢰할 수없는 노드는 공개 키에 액세스하려는 클라이언트에 대해 쿼리 응답을 느리게합니다. 이는 6.2.3에서 더 자세히 논의 된 Kademlia의 핵심 검색 프로토콜에 대한 Certcoin의 수정에 의해 시행됩니다.

모든 노드는 가능한 경로마다 k 개의 가능한 라우팅 값을 유지합니다. 이들 노드들 각각 사이에서 엔트리가 반복되지 않는다고 가정하면, 노드가 키에 도달 할 수 없다는 확률은 (2^-k)^k = 2^-k^2이다. 이것은 발신자의 테이블에있는 모든 k 노드가 임의의 노드로 들어오는 메시지나 나가는 메시지없이 자신의 라우팅 테이블에서 k 개의 실패를 갖도록 요구합니다. 그러나 중복은 확실히 발생해야하지만 네트워크의 라우팅 테이블이 본질적으로 가장 안정적인 노드를 저장한다는 사실에 의해 설정됩니다. 앞서 언급했듯이 라우팅 테이블은 보내거나받은 모든 메시지로 업데이트됩니다. 결과적으로 공격자가 구멍을 만들어야하는 평균 시간 간격이 비례하여 줄어들 기 때문에 더 많은 요청이 이루어짐에 따라 네트워크가 더욱 안전하게됩니다.

또한 Kademlia의 라우팅 프로토콜은 액세스 빈도에 따라 값을 분산하는 캐싱 메커니즘을 사용하도록 수정 될 수 있습니다. 네트워크의 많은 부분이 값을 복제 할 것이므로 더 많은 인기 키를 공격자가 목표로 삼기가 더 어려워 질 것입니다. 이를 달성하기 위해 필요한 추가 공간은 최소한이며 노드는 캐시 된 값을 계속 전파하는 노드가 많아짐에 따라 소스로 직접 트래픽이 감소하는 것을 볼 수 있기 때문에 노드가 참여할 수 있습니다.

6.2 Kademlia for Certcoin(Certcoin을위한 Kademlia)

6.2.1 Authenticated RPCs(인증 된 RPC)

앞서 언급했듯이 인증되지 않은 DHT는 중독 및 라우팅 공격에 취약합니다. 다행스럽게도 노드가 Kademila의 RPC에 서명하도록 요구함으로써 쉽게 보호 할 수 있습니다. 우리는 노드 u에서 시작된 표준 메시지 M을 다음과 같이 Certcoin의 DHT에 적합한 인증 메시지 MAuth로 변환하는 방법부터 설명합니다.

PKu 및 WitnessPKu를 포함하면 수신자는 누적기를 사용하여 보낸 사람의 진 본성을 즉시 확인할 수 있습니다. 노드가 인증되지 않은 메시지를 라우팅을 업데이트하는 데 사용해서는 안되며, 이는 중독 공격을 유도하기 때문입니다. 따라서 노드가 특정 키에 대해 DHT 외부에서 인증되지 않은 쿼리를 수신하면 노드는 재귀 적이며 인증 된 키 검색 시퀀스를 시작하지만 해당 라우팅 테이블을 업데이트하기 위해 메시지를 무시합니다. 물론 대상 경로까지의 노드는 검증 된 RPC를 사용하여 테이블을 업데이트해야합니다

6.2.2 Node ID Assignment(노드 ID 할당)

더 많은 압박은 잘 알려진 시빌 공격에 대해 방어이다. 공격자는 대개 ID 공간의 특정 영역을 타겟팅 할 수있는 다수의 ID를 만들 수 있습니다. 인증 기관의 존재 여부를 결정할 수있는 응용 프로그램에서는 일반적으로 등록 프로세스를 통해 개체와 ID의 일대일 매핑을 보장함으로써 해결됩니다. CA의 교체가 Certcoin의 궁극적 인 목표이기 때문에 이것이 유효한 해결책이 아니라는 것은 분명합니다. 다행스럽게도 Certcoin과 블록 체인의 통합은 이미 등록 서비스를 제공합니다. 그런 다음 DHT는 H (도메인 이름, 공개 키 서명, 블록 타임 스탬프)에 해당하는 노드 ID를 만듭니다. 여기서 H는 단방향이며 충돌 방지입니다.

임의의 사용자가 작성한 쿼리에 대한 DHT의 응답을 보여주는 Certcoin의 대체 키(alternate key) 검색 프로토콜의 예입니다.

6.2.3 Key Retrieval(키 검색)

노드가 단순히 자신을 제거하고 네트워크의 나머지 부분에 키를 배포하지 못하게하려면 키 조회에 응답하는 모든 노드가 그 키와 연관된 호스트 이름의 하트 비트 메시지(물론 배열 경계 검사 포함)에 대한 응답을 수신 할 수있을 때만 응답해야합니다. 노드는 이를 수행하지 않으면 엔티티가 떠나도록 허용하고 나머지 노드에 응답 요청의 부담을가하므로이 확인을 수행 할 인센티브를 갖습니다. 또한 서버는 하트 비트 메시지에 응답해야하며, 그렇지 않으면 사용자는 해당 사이트의 공개 키를 검색 할 수 없습니다.

DHT 외부로 전달되는 쿼리 응답을 다른 인증 된 RPC와 똑같이 구성해야하므로 키 조회 절차의 보안을 강화할 수 있습니다. 이를 통해 누구나 부정확 한 응답을 게시함으로써 악의적 인 노드를보고 할 수 있습니다. 노드가이를 인식하게되면, 라우팅 테이블에서 노드 끝 노드를 즉시 제거해야합니다. 또한 호스트 이름과 연관된 값을 저장하는 모든 노드는 상기 키에 대한 요청을 존중하지 않아야합니다.

DHT 외부로 전달되는 쿼리 응답을 다른 인증 된 RPC와 똑같이 구성해야하므로 키 조회 절차의 보안을 더욱 강화할 수 있습니다. 이를 통해 누구나 부정확 한 응답을 게시함으로써 악의적 인 노드를보고 할 수 있습니다. 노드가 이를 인식하게되면, 라우팅 테이블에서 상한 노드를 즉시 제거해야합니다. 또한 호스트 이름과 연관된 값을 저장하는 모든 노드는 상기 키에 대한 요청을 존중하지 않아야합니다.

7 Conclusion

결론적으로, 우리는 Certcoin이 인증서 기관과 PGP Trusts of Web을 대신 할 수있는 실행 가능한 PKI라고 믿습니다. 우리의 구성은 내재 된 내결함성, 중복성 및 투명성을 비롯하여 완전히 분산 된 아키텍처에서 이익을 얻습니다. 그럼에도 불구하고 Certcoin은 인증서 생성, 해지, 연결 및 복구를 포함하여 완전한 기능을 갖춘 인증 기관의 예상 기능을 지원합니다. 도메인 구매 및 전송은 간단한 Bitcoin 트랜잭션으로 수행되어 Miner들에게 incentivize를 지급합니다. Certcoin은 암호화 어큐뮬레이터를 사용하여 도메인 인증을위한 일정한 크기의 저장소를 유지 관리합니다.이 저장소는 최근 인터넷 사용 추세에 따라 더욱 중요 해지고 있습니다. 마지막으로, 우리의 설계는 CertCoin을 성능에 민감한 응용 프로그램에보다 실용적으로 만들어주는 효율적인 키 검색을 제공하는 자체 유지, 신뢰할 수있는 키 배포 메커니즘의 필요성을 해결합니다. 또한 Certcoin은 신뢰할 수있는 제 3 자의 필요성 및 제한된 접근성과 같은 현재 PKI에 내재 된 많은 문제를 해결합니다.

우리는 미래에 Certcoin을 구현하여 우리의 결과를 경험적으로 발견하고 그 실행 가능성을 입증 할 수있는 추가 최적화를 모색 할 계획입니다.

비트코인과 스크립트 언어 강의를 보고 개인적으로 공부하기 위해 정리한 내용입니다.

해당 강의는 아래의 링크에서 보실 수 있습니다.

https://www.youtube.com/watch?v=kejG9xQCKDI

비트코인의 거래란?

복식기입법(Double-Entry Bookkeeping)으로서의 거래

항상 Input과 Output이 있고 총 Input 값의 합은 항상 총 Output값의 합보다 커야한다. 두 값의 차이는 채굴자에게 부여되는 수수료이다.

거래의 체인

UTXO 기반 거래에 대한 설명...

거래 데이터

version

vin = Input값들에 대한 Array

vout = Output값들에 대한 Array

거래의 출력값

비트코인 블록체인의 기본단위, 불가분(indivisible), 블록체인에 기록, 정당성 인정

비트코인 full-node는 모든 UTXO를 Tracking함

"value" : 비트코인의 양

"ScriptPubKey"(locking script) : 출력값을 사용할 수 있는 조건을 명시한 스크립트(i.e. 암호학적 퍼즐 cryptographic puzzle), 누가 쓸수있느냐에 대한 조건을 명시하고 있다. 일반적으로 수신자의 Private Key로 풀수 있다.

모든 거래는 UTXO set을 변화시킴 (state transition)

"비트코인을 받는다" = "자신의 키로 통제 가능한 UTXO가 블록체인에 기록된다."

나의 잔고(balance) = 수많은 블록에 포함된 수많은 거래들에 흩어져 있는 내가 사용할 수 있는 UTXO들의 합

거래 입력값

- "txid" : 사용할 UTXO를 포함하는 거래의 아이디, 모든 Transaction은 이전의 Transaction ID를 Reference를 한다.

- "vout"(Output index) : 사용할 UTXO의 index, 이전 Transaction ID를 보고 이전의 Transaction에서 몇번째 Output인지 나타냄

- "scriptSig"(Unlocking Script): UTXO를 사용하기 위한 조건을 충족하는 스크립트, 이전의 Locking Script와는 반대의 개념 (e.g. 전자서명)

- "sequence"

- 거래 입력값에는 UTXO에 대한 reference만이 존재 -> UTXO의 value와 locking script에 대한 정보가 없다.

- 거래의 검증, 수수료

거래 수수료

- 거래 수수료 (transaction fee) = 입력값의 합 - 출력값의 합

- 거래 수수료는 1. 채굴자에 대한 보상, 2. 스팸 공격으로부터 네트워크를 방어하기 위한 수단으로 사용

- 거래 수수료는 거래금액이 아닌 거래의 크기(kB)에 비례 (e.g. 240 satoshi/byte)

- 시장원리에 따라 거래 수수료가 정해짐

- 초기에는 공간이 널널하였기 때문에 constant fee였지만 -> 거래가 많아지고 활성화 되면서 dynamic fee로 바뀜 (third party fee estimation service or built-in fee estimation algorithm, 자신의 거래에 대한 적정한 수수료 예측 알고리즘)

스크립트 언어

- 포스(Forth, 1960년대 개발된 나온 low level에 script언어)와 같은 스택기반(Stack-based)의 스크립트 언어 사용

- UTXO의 locking script(내가 이 script를 푸는 사람에게 권한을 준다.)와 입력값의 unlocking script(내가 script를 풀었으니 권한을 획득할 수 있다.) 모두 스크립트 언어로 작성

- 튜링 불완전 (no loops, 루프를 돌릴 수 없다. or complex flex control)

- stateless verification

Unlocking script + locking script

Unlocking script : 2 (열쇠)

locking script: : 3 OP_ADD 5 OP_EQUAL (자물쇠, 어떤 숫자에 3을 더했더니 5와 같아지는 숫자)

verification: 2 3 OP_ADD 5 OP_EQUAL 

이 검증 작업을 풀면 아래와 같다.

위와같이 스택으로 verification이 검증된다.

실제 Unlocking Script와 Locking Script의 구조는 다음과 같다.

Unlocking Script는 주로 "scriptSig" 라고 많이 부르는데 주로 signature와 Public Key로 구성되어 있다. Locking Script는 "scriptPubKey" 라고 주로 한다. 

이것을 Execution Pointer에 의해 실행되는 모습을 나타내면 다음과 같다.

거래 만들기

- 지갑이 특정 거래에 맞춰 입력, 출력값들을 선택하여 거래(transaction)를 build함 (오프라인에서도 가능)

- 지갑은 특정 주소가 사용 가능한 모든 출력값 (output)을 계속해서 추적 (track)  (내 잔고를 계속해서 업데이트)

- Full-node client를 돌리는 지갑의 경우 블록체인에 기록된 모든 UTXO들을 저장 -> 거래 입력값 선택 및 신규 거래의 검증이 빠름

- "lightweight" client의 경우 API를 통해 full-node로부터 필요 정보를 수신 (SPV, simple payment verification)

- 특정 주소의 UTXO set에서 거래금액에 맞는 적절한 입력값의 조합을 찾아냄

- 출력값은 스크립트(script)의 형태로 성성, 해당 스크립트에 대한 solution을 제시하여야 해당 출력값의 금액을 사용 가능(e.g 특정 출력값은 Bob의 public address에 대응하는 key를 제시한 경우에만 사용 가능)

- 수수료(transaction fee)의 설정 (i.e. 수수료 = 입력값의 합 - 출력값의 합)

거래를 블록체인에 추가하기

- 완성된 거래(transaction)을 비트코인의 P2P 네트워크에 전송

- 비트코인 노드: 비트코인의 프로토콜을 사용하여 비트코인 네트워크에 참가하는 시스템

- 비트코인 노드는 다수의 다른 노드들과 연결되어 있으며 새로운 정당한(valid) 거래를 수신하는 즉시 연결된 다른 노드들에게 해당 거래를 전파 (i.e. gossip network, flooding)

- 해당 거래가 채굴자(miner)에게 전파되어 (mining)되면 블록체인에 추가됨.

- confirm은 내 거래가 블록체인에 추가되면 1 confirm이고 뒤에 블록이 생기면 2 confirm 계속 증가... 6 confirmation은 6 confirm이 되면 double spending으로부터 안전하다는 공식 

리플에 대해 공부를 해보려고 하는데 Blockchainers에서 강의한 내용을 참고하여 정리를 해보도록 한다.

( https://www.youtube.com/watch?v=KEdqYNp5jnU 에서 해당 강의 영상을 보실 수 있습니다.)

4. 리플 합의 알고리즘과 단점

분산 결제 시스템이 가지는 문제: 비잔틴 장군 문제

○ 비잔틴 장군 문제란?

비잔틴 제국 장군들의 딜레마는 1982년 레슬리 램포트 등 3명의 컴퓨터 공학자들이 마이크로소프트 의뢰를 받아 수행한 연구의 논문 발표를 통해 처음으로 정식화 되었다. 비잔틴 제국 장군들이 봉착한 딜레마는 실제 역사적 사건이 아니라 분산 컴퓨팅에서 발생할 수 있는 신뢰와 합의의 문제를 함축한 우화다.

내용은 다음과 같다. 

1. 비잔틴 군대의 여러 사단이 적군의 도시 바깥에 진을 치고 있다.

2. 각 사단은 장군이 통솔하고 있다.

3. 장군들은 오로지 전령을 통해서만 서로 연락할 수 있다. 적군을 관측한 다음, 그들은 공동의 행동계획에 결정해야 한다.

4. 그렇지만, 장군들 가운데에는 배신자가 섞여 있을 수도 있고, 그들은 다른 장군들이 협의에 이르지 못하게 하려 한다.

5. 배신자는 규칙을 충실히 따르는 충직한 지휘관들과 달리 규칙에 얽매이지 않고 마음대로 행동할 수 있다.

Q. 이 때 배신자의 존재에도 불구하고 지휘관들이 동일한 공격 계획을 세우기 위해선 충직한 지휘관이 얼마 있어야 하며, 이 지휘관들이 어떤 규칙을 따라 교신해야 하는지에 대한 문제가 비잔티움 장군 문제다.

처음엔 누가 배신자(중복 사용)인지 모른 채 노드들은 채굴에 나선다. 그러나 다수의 노드가 참여한 블록에서 먼저 채굴이 이뤄지고 결국 배신자인 중복으로 사용된 거래는 자동 폐기된다.  과반수의 충성스럽고 정직한 장군들이 협업(채굴)하면 거짓 정보는 자연스럽게 소멸하는 셈이다.

부정한 세력이 비트코인 네트워크에 참여하는 전체 컴퓨터의 51%를 제어한다면 거짓 정보를 만들 수 있다. 그러나 비트코인 네트워크의 아주 초기 단계에서나 가능할지 몰라도 네트워크가 커지면 커질수록 어렵게 된다. 사토시 나카모토도 논문에서 “이런 상황을 예상할 수는 있지만, 부정한 세력이 그렇게 할만한 유인이 없다”고 밝히고 있다.

○ 비잔틴 장군 문제에 대한 해결 분야 3가지

1. 정확성(Correctness)

- 거래가 정상인지 비정상인지 판별하는 작업으로써 과거에는 기관간 신뢰와 암호화 서명을 통해서 특정 기관에서 한 서명이란 것을 증명하였다.

2. 동의(Agreement)

- 탈중앙화 회계 시스템은 단일 글로벌 사실에 동의할 수 있는가?

- 정확성과 동의는 다른 문제이다. 이에 대한 대표적인 문제가 이중 지불 문제이다. A가 같은 화폐를 B와 C에게 보낼 때 이 거래는 정확성 측면에서 본다면 정상적인 거래이다. 하지만 동의 측면에서 이 두 거래를 모두 동의하면 안되는 문제이다.

3. 실용성(Utility)

- 속도(빠른 네트워크 속도(latency)로 Data를 전송하고 수신), 정확성과 합의에 참여하기 위한 연산능력(채굴에 얼마나 많은 사람들이 참여할 수 있는지) 또는 네트워크를 원활히 사용하기 위해 사용자가(end user) 갖춰야 하는 기술력(낮은 사양에서도 정상적으로 사용할 수 있는지)을 말한다.

리플 프로토콜의 개별 요소

- 합의 (Consensus) = 정확성 + 동의 + 실용성 :  이 3가지가 갖추어져야 합의로 인정된다.

- 서버 (Server): 클라이언트 : 클라이언트 소프트웨어가 아닌 서버 소프트웨어를 실행하는 주체, 합의에 참여

- 원장 (ledger): 합의 과정을 거친 거래로 지속적으로 업데이트 되는 네트워크에 기록된다. 

- Last-Closed Ledger: 합의 과정을 거친 최신원장; 네트워크의 현 상태를 나타내며 다시 바뀌지 않는다.(리플의 특징으로 이더리움의 State와 비슷한 개념으로 생각할 수 있다.)

- Open Ledger: 노드의 현 운영상태 (각 노드마다 Open Ledger를 유지한다); 특정 서버 사용자의 결제는 그 서버 Open Ledger에 적용은 되나 합의 절차 전 까지 거래는 Final하지 않고 합의가 이루어지는 시점에 Open Ledger -> Last-closed Ledger 가 된다.

- Unique Node List(UNL): 각 서버 S는 UNL을 가지고 잇고 UNL은 S가 합의를 할 때 Query하여 합의가 가능한지 합의를 같이하는 S가 신뢰하는 서버들이다. 합의를 도출하기 위해 S의 UNL만 고려되며(네트워크의 모든 노드 X); UNL은 S가 네트워크 안에서 공모하지 않을 것이라고 신뢰하는 집합이다.(S는 UNL각 멤버를 신뢰할 필요는 없다. 여러 멤버들이 모여있는 멤버 집합을 신뢰하는 것이다.)

- Proposer: 합의 절차에 포함되기 위해 모든 서버는 거래를 전파할 수 있으며 새 합의 라운드가 시작되면 모든 서버는 유효한 거래를 포함하기 위해 노력한다. 하지만 S는 합의 과정에서 S의 UNL에 포함된 서버의 Proposal만 고려한다.

기존 합의 알고리즘 ( %는 잘못을 해도 괜찮은 노드의 비율, 비트코인의 경우 51%가 잘못하면 문제가 발생한다.)

- BFT: 33%; 디지털 서명을 요구하지는 않음

- FaB Paxos: 20%

- Attiya, Doyev, Gill: 25%

- BFT-CUP: 33%

리플 합의 알고리즘 (RPCA: Ripple Protocol Consensus Algorithm)

- Byzantine failure이 있더라도 ledger-close에 합의 도달할 수 있다. (모든 거래가 거부되는 합의도 포함한다.)

 UNL에 한 서버가 계속 스팸 Transaction을 발행할 경우 다른 서버들이 해당 서버를 무시하자고 하는 합의도 포함한다.

- 네트워크 각 노드는 그 노드의 UNL의 Probpsal에만 투표를 하지만 (노드별 UNL은 다르다.) UNL membership이 달라도 합의 도달

-> 때문에 fork가 일어나지 않는다. (노드가 2개 이상의 집합으로 나눠지고 각각 합의하고 각 노드 집합의 노드들이 서로 다른 2개 last-closed ledger을 목격하는 것을 fork라고 한다.) 

- 노드 실패율이 20% 이하이면 합의가 가능하다.

RPCA의 1라운드(합의에 도달하기 위하여 진행되는 과정으로 계속해서 라운드가 반복된다.)

1. 각 서버는 이번 합의 라운드가 전에 목격했으나 적용되지 않은 유효한 Tx을 '후보집합'으로 공개한다. 각 서버마다 목격했던 Tx들을 이 거래들을 후보로 추천하고자 공개를 한다.

2. 각 서버는 자신의 UNL에 있는 모든 서버들의 후보집합을 모아서 그 후보집합에 있는 Tx의 유효성에 대한 투표를 진행한다.

3. 최소한의 'yes' 투표(최소한의 기준은 각 round마다 설정이 된다.)를 받은 Tx는 다음 라운드로 진행한다. 받지 못한 Tx는 영구 제외되거나 다음 원장의 합의 과정이 시작될 때 후보로 포함된다.

4. 1,2,3번 과정이 반복되어 계속 진행되다가 UNL상의 서버들의 최소 80%가 Tx에 대해 동의를 한다면 원장에 기록되고 이는 최신 Last-closed ledger가 된다.

정확성(Correctness)

- UNL에서 20% 미만이 Bad하다면 정확하다. 즉, 80%이상이 정상적인 노드일 경우 정확하다.

- UNL은 대부분 신뢰할 수 있는 것이기 때문에 크게 문제가 되지 않고 전체적으로 보면 '공모하는 카르텔'이 문제가 된다. (UNL에서 서버 10개중에 3개가 조작하고자 공모하는 경우)

- 하지만, 이에 따른 Ripple에서 얘기하는 대책은 UNL은 임의적이 아니라 20% 미만으로 유지할 수 있도록 선별한다는 것이다. 즉, 익명이 아니여서 암호학으로 식별할 수 있기에 다양한 대륙, 국가, 산업, 이념 등에서 신뢰할 수 있는 노드 UNL만 선별하면 20%보다 훨씬 적은 확률이 가능하다고 한다. 즉 Ripple은 이론적인 해결책이 아닌 현실적인 해결책으로 접근하였다.

위의 그림은 Ripple Whitepaper에 있는 그림을 가져온 것이다.

옆에 Pc들은 공모할 사람들의 percentage를 나타낸다. X축은 UNL의 크기로 UNL이 몇개가 있는지를 나타낸다. Y축은 카르텔이 합의에 도달하는 가능성, 즉 Fork에 성공할 가능성에 대한 확률을 나타낸다

공모할 사람들이 0.05 퍼센트일 경우(Pc = 0.05), 노란선을 보게되면 Fork에 성공할 가능성은 거의 0%에 가깝게 된다.

표에서 공모할 사람들이 가장 많은 20 퍼센트인 경우(Pc = 0.20), 파란색 선을 보게되면 UNL Size가 10에서는 약 35%이고 UNL Size가 증가할 수록 확률은 증가한다. 하지만 결정적으로 50%의 확률을 넘지 못한다. 50%의 확률이 넘어야 합의에 도달할 수 있기 때문에 안전하다고 주장한다.

동의(Agreement)

- 정직하고 Error-free한 노드들(Non-faulty)이 UNL과 상관없이 동일한 거래집합에 대해 합의를 볼 수 있다.

- 만약 UNL 멤버쉽에 다른 제한이 없고 악의적인 UNL들의 수가 전체 UNL의 20%라면 fork는 가능하다.

- 파벌이 덜 하다면 즉, 각 서버들의 UNL의 교집합이 적다면, 모든 노드 UNL topography가 더 복잡하기 때문에 fork는 더 힘들어진다.

- 동의는 노드 교차점 크기와 연관이 있고 Non-faulty 노드 교차점과는 연관이 없다. 아래에 그림에 설명이 나와있다.

그림을 보면 왼쪽 위의 육각형의 UNL clique(파벌) 부분을 보면 각 노드는 5명을 신뢰하고 있다. 이 육각형에서 한 노드를 보면 붉은색의 다른 UNL clique와 연결되어 있다. 즉, 해당 노드는 다른 UNL Clique에 있는 노드까지 포함하여 총 6개의 UNL을 가지고 있다. 이렇게 다른 UNL Clique와 연결되어 있는 노드를 교차점이라고 한다. 

교차하는 노드가 Faulty한지 Non-Faulty한지는 중요하지 않고 교차하는 노드의 수가 많은지가 중요하다고 한다.

실용성(Utility)

- 정확성과 동의가 보장 된다면 네트워크 속도만 보장이 됐을 때 Convergence는 보장된다. 노드 반응시간을 모니터 하고 특정 시간보다 반응이 느린 노드는 모든 UNL에서 제외된다.

- 모든 노드의 초기 UNL이 조건(각각의 노드들은 처음부터 UNL을 가지고 시작한다.)을 충족하다가 특정 Node가 반응이 느리거나 없어 제외된다면 새로운 UNL로 정확성과 동의가 충족 되어야 한다.

- "A latency bound heuristic is enforced on all nodes in the Ripple Network to guarantee that the consensus algorithm will converge"

- 노드가 악의적인 행동을 한다면 네트워크에서 제외(악의적인 행동의 예: 매 거래마다 'no' 투표, 합의에 의해 검증되지 않는 거래를 지속적으로 제안)

- 기본적으로 큐레이션된 UNL을 모든 유저에게 제공해서 공모하는 확률을 낮춘다. 순진한 유저도 합의 알고리즘에 참여 가능

- 포크를 예방하기 위해 네트워크 분열 탐지 알고리즘 사용. 노드는 UNL에 활성화된 멤버 수를 모니터 하고 만약 수가 급격하게 정해진 수치 이하로 떨어진다면 포크가 발생했을 가능성이 크다. 이런 경우 노드는 Tx를 처리하거나 투표는 안해도 참여하고 있다는 것을 'partial validation'으로 표시

- RPCA는 합의 라운드에 적용되지 않고 합의 최소 기준점이 최대 80%까지 증가하는데에 적용. 수 라운드를 통해 네트워크 거래률을 저하하는 노드 탐지가 가능하다. 이런 불량 노드는 첫 몇 라운드는 괜찮지만 합의 기준점이 증가함에 따라 제외된다. 80%에 해당되는 Tx는 의외로 몇개 없어 느린 노드도 합의를 볼 수 있을 수 있음.

- 블록 생성시간은 수 초이다.

문제점 및 지적(리플의 문제점을 다룬 논문과 비트코인 core개발자가 Ripple의 코드 및 구조를 보고 문제점 지적한 내용이 주로 있음)

- SCP 이전 Stellar 대 RPCA

- Validator UNL 교집합이 최대 UNL 교집합 40%가 (과거 20%)되어야지 Fork가 없음

- 리플 기술 문서는 따로 '블록체인'을 언급 하지 않음; '블록의 체인' - 왜 각 블록이 특별한가? 

- 서명된 메시지 자체는 임의적으로 만들면 되기에 신뢰대상이 되지 않음. 리플의 신뢰는 UNL과 서명된 메시지가 일치하기 때문이다. 리플은 reorg가 없을 것이라고 가정하는 듯 하다. reorg 위험이 없다면 이는 중앙화 시스템이 아닌가?

- 리플 현재 UNL 교차점은 100%이지만 자원하는 사람이 없다. (UNL 8개에서 더 이상 증가하지 않는다. Validator역할에 대해 보상도 없으며 법적 책임을 가져야 하기 때문에 아무도 하려고 하지 않는다. )

- 비트코인: 경제적 합의. 허가없이 경제적 유인 때문에 채굴자가 된다.

- 리플: 경제적 유인 없음. Validator이라는 이유로 UNL에 자동 포함 되지 않고 UNL에 포함이 되기 위해 리플에 문의를 하고 허가를 받아야 함. Validator는 각종 법적 책임을 쳐야함(태만에 의한 소송, 금융 범죄 방조) 

- 만약 리플에 포크가 발생한다면 이중 지불 및 금전적 피해가 발생할 것이며 진 체인은 기록 일부 또는 모든 기록을 포기해야 함 - 리플 소프트웨어는 이게 불가능 하다고 가정. 만약 발생한다면 바로 소송

- UNL 기록이 100% 교차하는 것이 교차 하지 않는 것에 비해 유리. 그럼 누가 왜 100+ 개의 고유 노드나 UNL을 사용할까? 

결론은 사용하지 않는다.

- KYC/ AML (리플은 거의 실명제)

- 리플은 모든 validator는 원장을 가지고 있어야 한다 - 확장성 문제

- 만약 거래기록을 가지고 있기에 법적 책임을 져야 한다면 은행이 왜 서로를 위해 Validator가 될까? 

- 중앙화 시스템이 가지고 있는 문제 및 공격 vector

- XRP는 스팸 공격 대비해 존재하나 스팸 공격은 악의가 없다는 식으로 진행 될 수 있다. 리플회사가 이와 같은 경우 XRP를 팔지 않을 경제적 유인은 없다. 스팸공격에도 결국 XRP가 필요하고 공격시 XRP를 태우기 때문에 결국 XRP의 가격이 올라가기 때문이다.

질문

- 이론 vs 실천, 시행착오의 역할, Open source VS Closed source

-> 이론상에서 좋은것이 반드시 실천에서 승리하는 것은 아니다. 실패 후에 잘될 수 있기 때문에 시행착오를 거치면서 강화될 때 Open Source가 좋은지 Closed source가 좋은지.(비트코인은 Open source, 리플은 Closed source)

- 중앙화 - 분산화 - 탈중앙화?

-> 리플은 조직 자체는 중앙화에 가깝다.

- 가치 이전 VS 자산이전

-> 비트코인은 실제로 BTC가 옮겨지지만 XRP는 가치를 이전하기 위한 수수료 같은 개념 

- 리플의 첫 의도 및 방향성과 현재 의도 및 방향성

-> 개인에게 가치이전할 수 있는 방향성을 주려고 하였으나 방향성이 바뀌어서 은행에서 사용하는 방향으로 변경되었다.

- 역사적 시선으로 XRP 바라보기(사기체인)

-> 역사적으로 개발자들이 ICO를 진행하면서 모든 코인을 풀지 않고 숨겨두었다가 ICO후 가격이 오르면 팔아서 이익을 챙기는 일이 많았는데 때문에 리플은 XRP를 내세우지 않았다.

- 규제와 Bitcoin-neutrality

-> Bitcoin-neutrality(비트코인 중립성): 비트코인은 화폐라고 정의하면 다른 용도로 사용하는 비트코인에 다른 사용 방법들은 제외가 된다. (Internet-neutrality: 인터넷은 메일을 위한 시스템이라고 정의하면 인터넷은 발전하지 못했다.)

- 블록체인의 정의