libra共識算法分析
- 2020 年 3 月 13 日
- 筆記
- 核心算法說明
- 基於chained實現，整體上是當前輪推動下一輪共識繼續下去, 如此來持續運轉下去, 數據有效性證明基於(QC)實現
- leader廣播proposal消息{round, qc, propsal}
- replica收到proposal後本地計算後發送投票信息到下一個leader
- 下一個leader負責聚合(qc_aggrate)後再通過proposal消息廣播出來進入下一輪
- 活性證明, 數據有效性基於(TC)實現
- 每個節點一旦進入一輪新的共識就會開始計時, 一旦超時就廣播timeout_vote消息
- 其他節點收到後本地放到pending_vote隊列中, 然後開始本地等待其他節點的timeout_vote投票來名聚合, 一旦簽名聚合成功, 則進入下一輪, 並計算相應輪次的leader, 給該leader發起投票，如此將重新起搏整條鏈的共識
- 關於輪次
- 每個節點的輪次是嚴格遞增的，只有收到有效數據才會增加輪次，增加輪次的規則就是看(QC和TC)兩者的高度誰高，誰高那就使用誰的輪次，因為TC/QC都是有法律效應的
- 基於chained實現，整體上是當前輪推動下一輪共識繼續下去, 如此來持續運轉下去, 數據有效性證明基於(QC)實現
活性證明【降維到傳統pbft廣播實現】
libra活性證明基於tc(timeoutcetificate)來實現，在每輪啟動時(收到proposal處理時)本地設置一個定時器，該定時器觸發後直接廣播timeoutvote_msg到所有節點，每個節點自己本地聚合生成相應的timeoutcetificate，一旦聚合完成就會round+1，然後投遞vote信息到round + 1的leader，這樣round + 1的leader又可以驅動起來。為了對齊時間，間隔時間會隨着本地timeout次數的增加而變長，每次以1.5的n個指數被遞增。直到收到新的leader發出來的proposal為止。
1.觸發:
本地設置timeout時間process_local_timeout在timeout時廣播timeout_vote
// 處理本地超時事件
pub async fn process_local_timeout(&mut self, round: Round) {
// 根據當前輪次信息和base_ms設置超時, 一旦超時則拋出timeout事件, 然後又觸發到proces_local_timeout
// 注意：這裡不會引起輪次增加
pacemaker.process_local_timeout(round)
// 根據情況廣播timeout_vote
let timeout_vote_msg = VoteMsg::new(timeout_vote, self.gen_sync_info());
// 廣播,每個節點都廣播出來
self.network.broadcast_vote(timeout_vote_msg).await
}
2.投票處理
收到timeoutvotemsg，收到的節點自己聚合
// 處理投票業務
pub async fn process_vote(&mut self, vote_msg: VoteMsg) {
if !vote_msg.vote().is_timeout() {
// …非超時投票處理
} else {
// 添加投票信息
self.add_vote(vote_msg.vote();
}
}
// 統計投票信息
async fn add_vote(&mut self, vote: &Vote) -> anyhow::Result<()> {
// Add the vote and check whether it completes a new QC or a TC
let res = self.pending_votes.insert_vote(vote, &self.validators);
match res {
VoteReceptionResult::NewQuorumCertificate(qc) => {
// ..
// 聚合qc簽名
self.new_qc_aggregated(qc, vote.author()).await
}
// 覺tc簽名
VoteReceptionResult::NewTimeoutCertificate(tc) => self.new_tc_aggregated(tc).await,
}
}
// tc聚合處理
async fn new_tc_aggregated(&mut self, tc: Arc<TimeoutCertificate>) -> anyhow::Result<()> {
// 證書處理
self.process_certificates(
self.block_store.highest_quorum_cert().as_ref(),
Some(tc.as_ref()),
)
}
3.certificate處理
接收certificate後進行處理
async fn process_certificates(
&mut self,
qc: &QuorumCert,
tc: Option<&TimeoutCertificate>,
) -> anyhow::Result<()> {
// pacemaker處理證明, 觸發輪次切換
if let Some(new_round_event) = self.pacemaker.process_certificates(
Some(qc.certified_block().round()),
tc_round,
highest_committed_proposal_round,
) {
// 切換輪次, 如果是leader則廣播proposal, 如果不是leader則等着
self.process_new_round_event(new_round_event).await;
}
}
// 處理certificate的時候明確new-round，pacemaker更新本地round
pub fn process_certificates(
&mut self,
hqc_round: Option<Round>,
htc_round: Option<Round>,
highest_committed_round: Option<Round>,
) -> Option<NewRoundEvent> {
// 明確計算出新的輪次後才會更新輪次
let new_round = std::cmp::max(qc_round, tc_round) + 1;
if new_round > self.current_round {
// Start a new round.
self.current_round = new_round;
// 新輪次重置超時
let timeout = self.setup_timeout();
let new_round_reason = if qc_round >= tc_round {
NewRoundReason::QCReady
} else {
NewRoundReason::Timeout
};
let new_round_event = NewRoundEvent {
round: self.current_round,
reason: new_round_reason,
timeout,
};
debug!(“Starting new round: {}”, new_round_event);
return Some(new_round_event);
}
}
4.切換輪次
async fn process_new_round_event(&mut self, new_round_event: NewRoundEvent) {
// 基於roating leader選擇算法選擇leader
// backup什麼事情都不做
if self
.proposer_election
.is_valid_proposer(self.proposal_generator.author(), new_round_event.round)
.is_none()
{
return;
} else {
// leader廣播new proposals
let proposal_msg = match self.generate_proposal(new_round_event).await {
// …
};
network.broadcast_proposal(proposal_msg).await;
}
}
5.參與新的共識
