出块流程

为平行链尽可能平均地分配validator group；
collator生成一个平行链区块，和该区块的PoV一起组成collation/candidate；
collator将candidate通过Collator Protocol传递给group内的validator（1 to 1，非广播）；
group内的validators通过Candidate Backing对candidate进行验证和共识。collation通过共识后状态变更为”backable”；
中继链出块人将backable candidate打包上链，此时candidate状态为”pending availability”，此时不会更新parachain的head；
在后续的中继链区块中，validators会通过Availability Distribution子系统使得candidate变为available（所有validators的2/3以上持有candidate的PoV）；
中继链出块人将available的candidate打包上链，此时更新parachain的head，并对candidate中包含的消息（主要是跨链消息）进行处理；
类似于finalize，对candidate也有Approval Process的过程，来对candidate进行二次检查，如果有validator报告检查不通过，那么触发所有validators对该candidate进行重新验证。

中继链

启动

中继链启动时，启动overseer，包含一些子系统：candidate_backing，candidate_selection，statement_distribution，availability_distribution等,route_message为子系统进行AllMessages消息中继，发送到指定的子系统。中继链forward_events将中继链主系统的消息传递给overseer。
中继链节点与overseer交互由事件触发，主要的事件是块导入，块终结，send_msg。Event::BlockImported和Event::BlockFinalized会更改active_leaves，send_msg主要用来初始化collation_generation子系统，激活CollatorProtocol，向provisioner请求候选区块。
- OverseerHandler{events_tx} 外部发送事件，overseer.events_rx接收外部消息。
- 子系统持有OverseerSubsystemContext 与overseer 交互
- 子系统A，B交互，A发送AllMessages::B，overseer转换为Fromoverseer::Communication{B}发送给B。

请求候选区块

CollatorProtocol::validator_side：

接受到来自collator的Declare，将collator的信息（peer_id, collatorId）保存到State.known_collators。collatorId是collator的公钥。
接受到来自collator的AdvertiseCollation，触发notify_candidate_selection：通知CandidateSelectionSubsystem。
CandidateSelectionSubsystem handle_collation:
- 检查para_id是否是该validator负责的，如果不是，forward_invalidity_note -> report_collator 降低collator的信誉。
- get_collation发送CollatorProtocolMessage::FetchCollation，触发fetch_collation，等待回应：
  - request_collation发送CollatorProtocolMessage::RequestCollation(relay_parent, para_id)，向known_collators请求collation。
  - 收到collator发来的protocol_v1::CollatorProtocolMessage::Collation，触发received_collation：取消仍然正在进行的request_collation（第一次选择了Collation的地方，先到先得，还没准备好发送的collator被排除），唤醒requests_in_progress（如果超时，惩罚collator），回复请求一个元组(candidate_receipt, pov)唤醒get_collation，存储collation。如果是过时的collation，会降低collator的声誉。
- second_candidate：发送CandidateBackingMessage::Second(relay_parent,candidate_receipt,pov) 给 candidate backing子系统；

验证、支持候选区块

candidate backing子系统 process_msg处理 CandidateBackingMessage::Second。

检查para_id是否是self.assignment；
检查是否second（支持）过其他candidate；
检查是否对该candidate已经有issued_statements；

validate_and_second

检查candidate中的collator是否为schdule计划中的，如果无效，惩罚collator；

background_validate_and_make_available：将candidate加入awaiting_validation，启动异步任务validate_and_make_available：

从params获取到PoV（Second消息中携带了PoV）；
request_candidate_validation发送CandidateValidationMessage::ValidateFromChainState，candidate validation子系统spawn_validate_from_chain_state
- find_assumed_validation_data检查candidate的PersistedValidationData是否与中继链上一致，这里也检查了parent_head；
- spawn_validate_exhaustive -> validate_candidate_exhaustive，
  - perform_basic_checks基础检查：pov大小是否超过max_pov_size，candidate.descriptor.pov_hash与pov.hash是否一致，check_collator_signature；
  - validate -> wasm_executor::validate_candidate -> pool.validate_candidate -> validate_candidate_custom -> ValidationHost::validate_candidate: start_worker通过process::Command::new子命令创建子进程执行run_worker，父子进程通过共享内存进行通信
    - run_worker -> validate_candidate_internal
      - 调用validation_code中的validate_block(ValidationParams)： E::execute_block(block)执行区块，然后读取变更后的存储组装成ValidationResult（数据结构与CandidateCommitments一致）
  - 检查ValidationResult.head_data.hash() == descriptor.para_head ?
  - 将ValidationResult组装成CandidateCommitments，返回验证结果(CandidateCommitments, persisted_validation_data)
- runtime_api_request发送RuntimeApiRequest::CheckValidationOutputs，Runtime api子系统调用inclusion模块的check_validation_outputs_for_runtime_api，主要是检查CandidateCommitments是否满足接受标准：数据大小，消息数量。
检查commitments_hash是否与ValidationResuld的一致；
make_pov_available：生成纠删码，验证erasure_root。store_available_data：发送AvailabilityStoreMessage::StoreAvailableData(CandidateReceipt.hash, self.ValidatorIndex, n_validators, AvailableData, tx)，av store存储可用数据available_data和整个纠删码。

发送ValidatedCandidateCommand::Second(candidate, commitments, pov)

validate

// 主要是persisted_validation_data的数据
pub struct ValidationParams {
	/// Previous head-data.
	pub parent_head: HeadData,  // persisted_validation_data.parent_head
	/// The collation body.
	pub block_data: BlockData,  // pov.block_data
	/// The current relay-chain block number.
	pub relay_chain_height: RelayChainBlockNumber,
	/// The relay-chain block's storage root.
	pub relay_storage_root: Hash,
	/// The MQC head for the DMQ.
	///
	/// The DMQ MQC head will be used by the validation function to authorize the downward messages
	/// passed by the collator.
	pub dmq_mqc_head: Hash,
	/// The list of MQC heads for the inbound HRMP channels paired with the sender para ids. This
	/// vector is sorted ascending by the para id and doesn't contain multiple entries with the same
	/// sender.
	pub hrmp_mqc_heads: Vec<(Id, Hash)>,
}

pub struct ValidationResult {
	/// New head data that should be included in the relay chain state.
	pub head_data: HeadData,
	/// An update to the validation code that should be scheduled in the relay chain.
	pub new_validation_code: Option<ValidationCode>,
	/// Upward messages send by the Parachain.
	pub upward_messages: Vec<UpwardMessage>,
	/// Outbound horizontal messages sent by the parachain.
	pub horizontal_messages: Vec<OutboundHrmpMessage<Id>>,
	/// Number of downward messages that were processed by the Parachain.
	///
	/// It is expected that the Parachain processes them from first to last.
	pub processed_downward_messages: u32,
	/// The mark which specifies the block number up to which all inbound HRMP messages are processed.
	pub hrmp_watermark: RelayChainBlockNumber,
}

AvailableData

pub struct AvailableData {
	/// The Proof-of-Validation of the candidate.
	pub pov: std::sync::Arc<PoV>,
	/// The persisted validation data needed for secondary checks.
	pub validation_data: PersistedValidationData,
}

对候选区块共识

CandidateBackingJob监听任务，handle_validated_candidate_command接受命令ValidatedCandidateCommand::Second：将candidate_hash插入self.seconded和self.issued_statements，组装Statement::Seconded(CommittedCandidateReceipt)
- sign_import_and_distribute_statement对statement共识
  - sign_statement对statement签名
  - import_statement
    - primitive_statement_to_table转换statement为SignedStatement
    - Table::import_statement
      - import_candidate：导入Statement::Candidate状态的candidate。digest = CommittedCandidateReceipt.hash()。如果Table.authority_data已经有proposal，验证digest，如果不相符，要报告Misbehavior::MultipleCandidates。Table::candidate_votes插入CandidateData。进行投票ValidityVote::Issued。
      - validity_vote
        
        requisite_votes：计算至少需要的票数，group.validators.len()/2 + 1；
        
        检查本validator是否是group内，如果不是，报告Misbehavior::UnauthorizedStatement；
        
        如果已经投票过，报告Misbehavior::ValidityDoubleVote或者Misbehavior::DoubleSign；
        
        如果是第一次投票，insert(vote)。当票数足够时（大于该group的1/2），update_includable_count更新Table::includable_count，记录parachain是否通过。返回Summary。
      - attested_candidate：仅当can_be_included为true时，才返回AttestedCandidate
      - 将summary.candidate(digest)插入CandidateBackingJob的backed集合，table_attested_to_backed将AttestedCandidate转换为BackedCandidate，send_to_provisioner将(relay_parent, CommittedCandidateReceipt) 通过封装在ProvisionableData::BackedCandidate消息中存储到provisioner_subsystem。当can_be_included为false时，不会存储到provisioner_subsystem，中继链就不会打包这个候选区块。
      - issue_new_misbehaviors报告之前出现的misbehaviors。
  - distribute_signed_statement：发送StatementDistributionMessage::Share。statement distribution子系统收到后：
    - inform_statement_listeners（collator在wait_to_announce时注册成为listener）
    - circulate_statement_and_dependents(更新后）广播statement：active_head在之前收到OverseerSignal::ActiveLeaves时创建
      - note_statement：做一些简单检查，标记statement的状态，比如如果可以接受并且是未存到active_head的，那么返回NotedStatement::Fresh。
      - 如果是NotedStatement::Fresh，circulate_statement查找其他还未拥有该statement的validators，返回peers_needing_dependents。
      - send_statements_about给peers_needing_dependents发送statements。
      - 其他validator handle_network_update 收到NetworkBridgeEvent::PeerMessage后，handle_incoming_message：
        
        如果是不需要的statement, report_peer降低peer的信誉；
        
        check_statement_signature，签名错误report_peer；
        
        检查statement是否真的存在于收到的peer data，不存在则report_peer；
        
        如果该statement不在该validator的known_candidates中，send_statements_about发送该candidate的statements给peer。所以group内的validator不一定需要直连，通过p2p网络最终也能收到其他的statement。
        
        inform_statement_listeners
        
        note_statement：如果是NotedStatement::Fresh，发送CandidateBackingMessage::Statement。
        
        CandidateBacking子系统收到后：
        
        check_statement_signature
        
        maybe_validate_and_import
        
        import_statement
        
        kick_off_validation_work：如果已经在issued_statements中则直接退出。检查group_id。如果candidate的collator与required_collator不一致，将其直接插入到issued_statements，然后返回。否则
        
        background_validate_and_make_available：此时传入的PoV为None，在validate_and_make_available中会触发request_pov_from_distribution，向所有拥有当前relay_parent的peers广播awaiting pov状态，最后发送ValidatedCandidateCommand::Attest给CandidateBackingJob。
        
        CandidateBackingJob收到Attest后，检查issued_statements，未issue的话插入其中，然后sign_import_and_distribute_statement。
      - 如果是fresh的，circulate_statement，但是忽略peers_needing_dependents。
- distribute_pov：发送PoVDistributionMessage::DistributePoV。
  - 子系统pov distribution接受DistributePoV后handle_distribute：distribute_to_awaiting把pov发给等待该relay_parent的validator（之前有request_pov_from_distribution），发送PoVDistributionMessage::SendPoV，其他validator收到后handle_incoming_pov继续distribute_to_awaiting。

CommittedCandidateReceipt

pub struct CommittedCandidateReceipt<H = Hash> {
	/// The descriptor of the candidate.
	pub descriptor: CandidateDescriptor<H>,
	/// The commitments of the candidate receipt.
	pub commitments: CandidateCommitments,
}

CandidateData

pub struct CandidateData<Ctx: Context> {
	group_id: Ctx::GroupId, // para_id
	candidate: Ctx::Candidate,  // CommittedCandidateReceipt
	validity_votes: HashMap<Ctx::AuthorityId, ValidityVote<Ctx::Signature>>,
	indicated_bad_by: Vec<Ctx::AuthorityId>, // count ValidityVote::Invalid
}

Summary

pub struct Summary<Digest, Group> {
	/// The digest of the candidate referenced.
	pub candidate: Digest,
	/// The group that the candidate is in.
	pub group_id: Group,
	/// How many validity votes are currently witnessed.
	pub validity_votes: usize,
	/// Whether this has been signalled bad by at least one participant.
	pub signalled_bad: bool,
}

AttestedCandidate

pub struct AttestedCandidate<Group, Candidate, AuthorityId, Signature> {
	/// The group ID that the candidate is in.
	pub group_id: Group,
	/// The candidate data.
	pub candidate: Candidate,
	/// Validity attestations.
	pub validity_votes: Vec<(AuthorityId, ValidityAttestation<Signature>)>,
}

BackedCandidate

pub struct BackedCandidate<H = Hash> {
	/// The candidate referred to.
	pub candidate: CommittedCandidateReceipt<H>,
	/// The validity votes themselves, expressed as signatures.
	pub validity_votes: Vec<ValidityAttestation>,
	/// The indices of the validators within the group, expressed as a bitfield.
	pub validator_indices: BitVec<bitvec::order::Lsb0, u8>,
}

可用性检查

Availability Distribution子系统:
- handle_our_view_change：将处于pending availability队列中（根据core获得，core的状态是根据链上存储计算的）的backed candidates对应的ErasureChunk广播给peers（如果拥有的话）。遍历所有validator获取chunk_index，获取对应的ErasureChunk；
- process_incoming_peer_message：发送StoreChunk给av store来保存与本validator_index对应的chunk。
- handle_peer_view_change：将所有活跃信息重新发送给该peer；
BitfieldSigning子系统：每次收到ActiveLeaves(ActiveLeavesUpdate)都会派发一个BitfieldSigningJob，延迟1.5秒后construct_availability_bitfield：
- get_availability_cores；
- get_core_availability：发送AvailabilityStoreMessage::QueryChunkAvailability(candidate, validator_index, tx)向Availability Store查询对于该validator对某个Core是否拥有availability chunk
- 遍历所有availability_cores，得到bitfield: Vec；
validator.sign对bitfield签名；
发送BitfieldDistributionMessage::DistributeBitfield(relay_parent, signed_bitfield)。
bitfield distribution收到后，handle_bitfield_distribution处理signed_bitfield：
- validator_index从签名中获取validator_index，再从ProtocolState::per_relay_parent::validator_set中得到validatorId；
- relay_message将bitfield发送ProvisionableData::Bitfield给Provisioner记录到signed_bitfields。

ErasureChunk

pub struct ErasureChunk {
	/// The erasure-encoded chunk of data belonging to the candidate block.
	pub chunk: Vec<u8>,
	/// The index of this erasure-encoded chunk of data.
	pub index: u32,
	/// Proof for this chunk's branch in the Merkle tree.
	pub proof: Vec<Vec<u8>>,
}

出块

中继链propose
- get_provisioner_data
  - overseer.wait_for_activation等待relay_parent为中继链父哈希的叶子在overseer上激活，发送ProvisionerMessage::RequestInherentData请求数据，PROPOSE_TIMEOUT(2.5秒)内需要收到数据；
- 打包进inherent_data。
Provisioner子系统启动job时，ProvisioningJob::inherent_after设置为Delay(PRE_PROPOSE_TIMEOUT) 2秒；
收到RequestInherentData消息后，等待inherent_after空闲，然后
- send_inherent_data：回应RequestInherentData请求
  - request_availability_cores
  - select_availability_bitfields：此时存储在signed_bitfields中的可能有多个bitfields。选择规则：对每个validator，选择通过可用性检查最多的bitfields；
  - select_candidates：
    - 转换availability_cores为(ScheduledCore, OccupiedCoreAssumption)
    - request_persisted_validation_data：向RuntimeApi请求；
    - 比对para_id和persisted_validation_data_hash；
    - 发送CandidateBackingMessage::GetBackedCandidates获取candidates: Vec；
    - 检查candidates的顺序是否与selected_candidates一致；
  - 返回(bitfields, candidates)。
inclusion_inherent模块中create_inherent，调用Call::inclusion(signed_bitfields, backed_candidates, parent_header)。
- 每个块只能执行一次inclusion；
- 检查parent_header；
- process_bitfields：处理bitfields，返回已经处理完置为free的core队列，对应的candidates一定已经是baked：
  - 读取PendingAvailability存储（process_candidates中会插入）
  - 根据signed_bitfields签名的validator_index更新pending_availability中的availability_votes[val_idx]为true；
  - AvailabilityBitfields::insert(validator_index, record)；
  - 检查pending_availability::availability_votes是否大于2/3的validators.len()；
  - enact_candidate:
    - T::RewardValidators::reward_backing
    - T::RewardValidators::reward_bitfields
    - schedule_code_upgrade
    - prune_dmq
    - enact_upward_messages
    - prune_hrmp
    - queue_outbound_hrmp
    - note_new_head更新平行链head；
  - pending_availability.core插入freed队列；
- <scheduler::Module<T>>::clear()；
- <scheduler::Module<T>>::schedule(freed,block_number)；
- process_candidates：处理backed的candidates，PendingAvailability::insert(para_id, CandidatePendingAvailability)，返回来自scheduled的Vec<(core_index, bakers)>；
- scheduler::Module::occupied：backed candidates将process_candidates返回的cores进行占用，然后才能进行Availability Distribution与BitfieldSigning；
- <ump::Module<T>>::process_pending_upward_messages()。

Approval Check

group内的validator可能作恶，需要二次检查（类似finalized)。随机选取一些validator来再次验证平行链区块，如果验证失败，触发escalation，要求所有的validator来验证这个平行链区块。Approval Process是可以一次最终确认多个平行链区块的。

进入中继链出块的共识流程，直到被GRANDPA确认。

Jenner's Blog

平行链节点的出块流程