원저자:소울 머신; 이 기사에 대한 지원 비디오:https://v.qq.com/x/page/f07704nx4iq.html
첫 번째 레벨 제목
캐스퍼 FFG 알고리즘 흐름
이미지 설명
PoW 프로세스
위 사진의 노란색 채굴자들은 갑자기 계산량을 늘려 나쁜 짓을 하기 시작했습니다 오래된 블록에서 시작하여 새로운 체인이 분기되어 그 위에서 계속 채굴되었습니다 길이가 왼쪽을 초과하면 새 체인이 끊어집니다 .오래된 체인이 성공적으로 교체될 수 있으면 이전의 오래된 블록이 취소되고 내부의 모든 트랜잭션을 덮어쓰고 다시 씁니다.
현재 PoW를 기반으로 Casper FFG는 PoS 투표 프로세스 계층을 추가하여 Finality를 더욱 향상시키고 이전 블록을 취소하는 것은 이론적으로 불가능합니다. Casper FFG는 비침습적 알고리즘으로 기존의 이더리움 PoW 알고리즘을 변경하지 않고 이 PoW 레이어에 BFT 방식의 PoS를 추가한 것입니다. 보존. 이를 바탕으로 100개의 블록이 채굴될 때마다 PoS 검증 노드는 마지막 블록에 투표하게 되며, 2/3 통과 후 마지막 블록을 체크포인트(checkpoint)라고 합니다.완료된 체크포인트는 실행 취소할 수 없습니다.요약하면 PoW 블록 생성 메커니즘은 유지되고 동시에 PoS는 100 블록마다 투표하여 이더리움의 보안(안전성 또는 최종성)을 더욱 강화합니다.
투표 메시지의 필드는 다음과 같습니다.
위 표에서 보듯이 각 투표 메시지는 5개의 필드를 포함하며, s는 소스 체크포인트의 블록 해시, t는 타겟 체크포인트의 블록 해시, h(s)는 s의 블록 높이, h(t)는 다음을 나타냅니다. t의 블록 높이, S는 서명을 나타냅니다.이 5개 필드 중 h(s), t, h(t)의 3개만이 실제로 핵심입니다.
Casper FFG의 투표 메시지는 두 단계를 교묘하게 한 단계로 결합합니다.본질적으로 pBFT 및 Tendermint의 두 단계 투표(pre-prepare->prepare, pre-vote->pre-commit)와 동일합니다.
아래 그림은 투표에 두 단계가 필요한 이유를 설명합니다.
동시에 Casper FFG의 투표 메시지는 Tendermint의 잠금 메커니즘과 유사한 효과가 있습니다.
다음은 Casper FFG 알고리즘에서 흔히 볼 수 있는 여러 용어의 정의입니다.
한 조각supermajority link, a→b로 작성하면 투표 메시지의 2/3 이상이 체크포인트 a에서 시작하여 체크포인트 b를 가리키면 a와 b 사이에 압도적 다수 링크가 있음을 의미합니다. 압도적 다수 링크는 여러 체크포인트에 걸쳐 있을 수 있습니다. 즉, h(b)>h(a)+1이 적합합니다.
두 개의 체크포인트 a와 b가 서로갈등, 이는 a와 b가 서로 다른 분기에 있음을 의미합니다. 즉, a와 b는 동일한 경로에 있지 않습니다.
체크포인트 c는justified체크포인트는 다음 조건 중 하나를 충족해야 합니다, (1) 제네시스 블록이거나 (2) 이를 가리키는 압도적 다수 링크가 있습니다.
체크포인트 c는finalized체크포인트, 정당화될 필요가 있고 그것에서 비롯된 절대다수 링크가 있습니다. c→c', 그리고 c'는 그것의 것입니다.직계 자식즉, c'의 높이는 c의 높이에 1을 더한 값입니다.
예를 들어 다음 그림과 같이
첫 번째 레벨 제목
페널티 조건(SlashCondition)
Validator가 다음 두 가지 조건 중 하나라도 위반하면 처벌을 받고 모든 예치금이 몰수됩니다.
1. No double vote: t1==t2. 같은 높이에 있는 두 개의 다른 블록에 투표하는 것은 불가능합니다. 이것은 상대적으로 이해하기 쉬운데, 동일한 높이에서 두 개의 다른 블록에 투표하는 것은 Nothingat Stake의 전형적인 투기 행위이며, 이에 대해 처벌을 받게 됩니다.
2. No surround vote.t2 < t1 < s1 < s2 . 예를 들어, 유효성 검사기는 먼저 몇 블록 후에 s1 -> t1에 투표하고 계속해서 s2 -> t2에 투표합니다. t2< t1,s1 -> t1에 먼저 투표를 했기 때문에 문제가 되는 이전 투표의 대상 블록보다 낮습니다. 간격이 s1->t1보다 작고 s1->t1로 완전히 덮이면 이 투표는 이전 투표를 잊은 것처럼 s2와 t2 사이의 블록에 반복적으로 동의합니다. 이러한 망각 행위도 처벌됩니다.
아래 그림은 Nodouble 투표 위반의 예를 보여줍니다.
PoW 채굴 중에는 포크가 같은 높이에서 발생하는 것이 일반적입니다. 이때 4개의 검증자 노드 중 두 개의 포크에 동시에 투표한 2개의 악성 노드가 있어 2개의 새로운 블록이 정당성을 갖게 됩니다. 파기되며, 신고한 사람은 포상금(발견수수료)을 받게 됩니다.
아래 그림은 No 둘러싸기 투표 위반의 예를 보여줍니다.
어느 시점에서 A->B 및 A->C라는 두 개의 절대다수 링크가 있으므로 A가 최종화되고 B와 C 모두 정당화된 블록입니다. 이 경우 검증 노드의 1/3 이상이 동시에 B와 C에 투표한 것을 의미하며, 이는 합법적이며 노더블 투표 규칙이나 nosurround 투표 규칙을 위반하지 않습니다.
첫 번째 레벨 제목
안전 증명 및 그럴듯한 생동감
이 섹션에서는 Casper FFG의 Safety(Finality)와 Liveness를 증명합니다.
먼저 Casper FFG는 accountable safety와 그럴듯한 liveness를 주장합니다.accountable이란 검증자 노드가 상당한 양의 예치금을 지불해야 한다는 것을 의미합니다.예치금으로 초기 신뢰가 있고 신뢰할 수 있습니다(accountable).
Plausible liveness는 실제로 새로운 것이 아닙니다.비트코인의 liveness와 정확히 동일합니다.네트워크가 분할(파티션)될 때 전체 시스템이 여전히 새로운 트랜잭션을 작성하고 블록을 생성할 수 있음을 의미합니다.
자세한 증명은 아래에서 시작됩니다.
책임 있는 안전: 충돌하는 두 개의 체크포인트(checkpoint), am과 bn은 확정(finalized)할 수 없습니다.
입증하다:반증 방법을 사용하여 am과 bn이 서로 충돌하고(즉, 동일한 분기가 아닌 두 분기에서) 종료가 완료되고 각각 정당한 하위 블록 am+1이 있다고 가정합니다. 그리고 bn+1.
높이 m과 n이 같으면 두 체크포인트에 동시에 투표하는 검증 노드의 1/3이 있어야 합니다. 이 노드는 이중 투표 금지 규칙을 위반하고 모든 예금이 파괴되어 1/3을 잃게 됩니다. 확인 노드, am 및 bn을 완료할 수 없습니다.
높이 m과 n이 같지 않으면 n > m(n< m은 동일한 과정을 증명함), 제네시스 블록에서 bn까지의 경로는 제네시스→b1→b2→...→bi→bj→...→bn이고, bi는 높이가 다음보다 작거나 같은 첫 번째 블록입니다. am, 즉 i≤m, bj는 높이가 am+1보다 크거나 같은 첫 번째 블록, 즉 j≥m+1입니다. 다음은 다음을 증명합니다.
i==m이면 검증 노드의 1/3이 이중 투표 금지 규칙을 위반하고 처벌을 받게 되어 am과 bn이 확정되지 않습니다.
j==m+1이면 위와 동일;
만약 내가
요약하자면, am과 bn은 어떤 상황에서도 완결이 불가능하고 증명이 완전합니다.
Plausible Liveness: 검증자 노드의 2/3 이상이 정당한 블록을 시작점으로 투표하는 한 항상 새로운 최종 블록이 생성될 수 있습니다.
간단히 말해서, 정당한 블록을 시작점으로 삼고 그보다 높은 노드에 투표할 수 있습니다.예를 들어 높이 m에 하나, 높이 n에 하나(시작점 포함 , 3개의 블록이 한 줄에 있어야 함) nodoublevote 및 nosurround 투표 규칙을 위반하지 않고 둘 중 하나 또는 둘 다에 투표할 수 있습니다. 즉, 여러 블록을 건너뛰고 더 높은 블록을 직접 캐스팅할 수 있습니다. 다음으로 정당화된 블록은 am 또는 bn이거나 둘 다일 수 있습니다(둘 다 2/3 이상의 투표를 얻음, 이때 둘 모두에 투표한 노드의 1/3 이상이 있어야 함).
네트워크가 분리되더라도 PoW는 양쪽에서 계속 블록을 생성할 수 있지만 이때 Validators 노드는 더 이상 어느 체크포인트에서든 2/3 투표에 도달할 수 없습니다. 계속 성장할 수 있습니다. 네트워크가 반으로 쪼개져도 여전히 작동할 수 있습니다.(Tendermint는 네트워크가 쪼개지면 무한정 대기할 수 밖에 없습니다.) 이런 강인한 생명력은 개연성의 또 다른 의미가 될 수 있습니다.
Casper FFG는 Plausible liveness에서 추론할 수 있습니다.ForkChoice 규칙: 항상 가장 높은 정당한 체크포인트 위에 있는 가장 긴 체인을 선택합니다.즉 가장 높은 정당한 블록을 먼저 찾은 다음 이 블록에서 시작하여 가장 긴 체인을 선택하는 것입니다. PoW 알고리즘에서 가장 긴 체인을 단순히 선택하는 것과 비교할 때 전제 조건이 하나 더 있습니다.
예를 들어, 아래와 같이 표시됩니다.
위의 그림에서 완성된 가장 높은 것부터 두 개의 정당한 체크 포인트를 가리키는 두 개의 절대다수 링크가 있습니다. 이때 네트워크는 특정 순간에 분할됩니다. 예를 들어 해저 광 케이블이 끊어져 둘. 이때 양측의 PoW는 계속해서 정상적으로 블록을 생성하게 되지만, 각 체크포인트가 투표할 때 새 체크포인트에 100% 동의하더라도 검증자 노드가 절반만 가지고 있기 때문에 기껏해야 절반의 투표만 받을 수 있습니다. , 2/3를 초과할 수 없습니다. 따라서 네트워크가 분할된 후에도 PoW는 체인을 계속 확장하지만 모든 새로운 블록을 마무리하고 정당화할 수는 없습니다.
첫 번째 레벨 제목
동적 유효성 검사기 세트
첫 번째 레벨 제목
스택 공격에 아무것도 없음
순수한 PoS 블록과 투표는 컴퓨팅 파워를 필요로 하지 않으며 비용도 없습니다(PoW에서는 짧은 체인에서 채굴하면 채굴해도 보상이 없고 컴퓨팅 파워가 낭비되어 비용이 발생합니다) ) 때문에 블록체인 포크 시 검증자 노드는 어떤 브랜치가 맞는지 알 수 없으므로 보상을 받기 위해서는 각 브랜치에 투표하는 것이 가장 좋은 전략입니다. PoS는 이러한 행위를 처벌하기 위해 일반적으로 검증 노드가 투표 전에 보증금을 지불하도록 요구하며, 누군가가 각 지점에서 투기하는 것으로 밝혀지면 보증금을 몰수합니다.
첫 번째 레벨 제목
장거리 공격
장거리 공격은 다음 세 가지 상황을 말합니다.
순수 PoS의 경우 순수 PoS에서 블록을 생성하는 데 드는 비용이 없기 때문에 실제 체인보다 긴 분기 체인을 쉽게 생성할 수 있습니다.
PoW의 경우 악의적인 노드가 컴퓨팅 파워의 51% 이상을 가지고 있다고 가정하면 실제 체인보다 긴 포크 체인을 만들 수도 있습니다. PoW 블록 생산에 비용이 있기 때문에 이런 상황은 비교적 드물며, 이렇게 큰 컴퓨팅 파워로 정직하게 채굴하고 더 많은 보상을 얻는 것이 좋습니다. 그러나 악의적인 노드가 오래 전에 이익에 의해 엄청난 양의 트랜잭션이 있었다면 악의적인 노드도 다시 포크하고 돈을 이중으로 지출할 동기가 있습니다. 장거리 공격.
세 번째 경우는 PoS와 PoW에 해당하는 경우로, 새로운 풀노드가 그냥 온라인 상태가 되면 우연히 여러 악성 노드와 연결되어 블록 동기화가 시작된다 체인은 여전히 길다 이때 정직한 풀노드가 있더라도 나중에 연결되면 전체 노드에서 보낸 체인이 더 짧아지고 새 노드에서 거부됩니다. 부끄럽군요.
첫 번째와 세 번째 경우 문제는 본질적으로 동일하며 더 긴 체인을 받았을 때 그것이 참인지 거짓인지 어떻게 판단합니까? 이 게시물의 VitalikProof of Stake: How I Learned toLove Weak Subjectivity 해결책을 설명하면서 우리는 여전히 외부 세계로부터 약간의 지식과 신뢰, 이른바 약한 주관성을 도입해야 합니다.V 하나님은 이런 약한 신뢰가 달성하기 쉽다고 믿으므로 안전을 약화시키지 않습니다. 블록체인. 새 노드가 온라인 상태가 되면 외부 세계에서 다음 지식을 얻고 신뢰해야 합니다.
1. 프로토콜 정의 이것은 다루기 쉽고 블록체인의 프로토콜은 코드에 존재합니다. 새 노드가 실행하는 코드 버전은 기본적으로 코드를 신뢰한다는 의미입니다.
2. 최신 유효 블록. 이 블록은 너무 오래되어서는 안 되며 마지막 N 내에 있어야 합니다. N은 충분히 신선하기만 하면 미리 정의할 수 있습니다.
2의 경우 문제가 큽니다. 새로운 전체 노드가 온라인 상태가 되면 최신 유효 블록을 어디에서 얻을 수 있습니까? 여기에 추가 신뢰 지식을 도입해야 합니다. 예를 들어 CasperFFG의 경우 새 노드가 온라인 상태가 되면 예치금을 지불한 전체 노드만 신뢰해야 하며 여러 노드를 연결하여 최신 최종 블록을 얻는 것이 가장 좋습니다. 가장 최근에 확정된 블록을 받으면 안심하고 동기화를 시작할 수 있으며, 악의적인 노드로부터 더 긴 체인을 수신하더라도 동일한 높이에서 악의적인 노드의 블록의 해시 값이 달라야 하기 때문에 동기화를 시작할 수 있습니다. 가짜 사슬임에 틀림없으니 이 사슬은 버려라.
요컨대, 장거리 공격에 대처하기 위해서는 이러한 공격을 방지하기 위해 외부 세계의 약간의 지식에 의존할 필요가 있습니다.
첫 번째 레벨 제목
대규모 충돌 사례(Castastrophic Crashes)
검증 노드의 1/3 이상이 동시에 충돌하거나, 네트워크에 문제가 발생하여 오프라인 상태가 되거나, 네트워크가 분리되는 경우, 이때 투표 시 2/3 이상의 표를 모으는 것이 불가능합니다. 시간, 즉 지금부터 새로운 절대다수 링크를 생성할 수 없습니다. 즉, 새로운 블록을 완료할 수 없습니다.
이 논문에서는 다음과 같은 방법을 소개합니다. Inactivity leak 비결은 두 개의 하위 네트워크가 독립적으로 작동하도록 만들고 계속해서 독립적으로 투표하고 새 블록을 마무리하는 것입니다.
요약하다
요약하다
Casper FFG 알고리즘은 2개의 페널티 조건(슬래시 조건), 포크 선택 규칙(포크 선택 규칙) 및 동적 검증 노드 집합의 세 부분으로 구성됩니다. Casper FFG는 모든 PoW 알고리즘에 적용 가능하여 PoW 알고리즘의 보안을 향상시킵니다.
Casper FFG의 블록 생성 메커니즘은 PoW(PoW 기반 블록 제안 메커니즘)이며, 향후 블록 생성 메커니즘은 순수한 PoS인 PoS로 대체될 것입니다.
네트워크 통신의 복잡도는 PoW 단계에서는 O(n), BFT 투표 단계에서는 O(n2)입니다. 일반적으로 자본금 임계값 때문에 전체 네트워크 노드에 비해 검증 노드의 수가 적기 때문에 O(n2)라고 해도 n이 작기 때문에 여전히 통신량이 상대적으로 적습니다.
최대 내결함성(fault tolerance)과 관련하여 PoW 단계에서는 악의적인 노드의 컴퓨팅 파워가 50% 미만으로 허용될 수 있으며, BFT 투표 단계에서는 악의적인 노드가 요구하는 자금의 양이 1/3 미만입니다. 간단하고 대략적인 요약에서 최대 내결함성은 1/3로 간주될 수 있습니다.
네트워크 가정은 PoW 단계에서는 동기식, BFT 투표 단계에서는 비동기식으로 일반적으로 네트워크 가정은 동기식입니다.
Finality는 PoW 단계에서 Probabilistic하고 BFT 투표 후에 Deterministic이 되며 일반적으로 Deterministic이 됩니다.
참조
참조
Casper the Friendly Finality Gadget
EthereumPoS: Casper FFG In Depth - YouTube
Ethereum PoS Overview: Casper FFG
Casper FFG with one message type,and simpler fork choice rule
Ethereum Casper 101
A Simplified Look at Ethereum’sCasper
Consensus Compare: Casper vs.Tendermint - Medium
Proof of Stake: How I Learned toLove Weak Subjectivity
