//! We want to make the simplest possible blockchain to begin with. Just a hash-linked data
//! structure. We learned from the lecture that it is actually the headers that are hash linked, so
//! let's start with that.
use crate::hash;
// We will use Rust's built-in hashing where the output type is u64. I'll make an alias
// so the code is slightly more readable.
type Hash = u64;
/// The most basic blockchain header possible. We learned its basic structure from lecture.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Header {
parent: Hash,
height: u64,
// We know from the lecture that we will probably need these, but we don't need them yet.
extrinsics_root: (),
state_root: (),
consensus_digest: (),
}
// Here are the methods for creating a new header and verifying headers.
// It is your job to write them.
impl Header {
/// Returns a new valid genesis header.
fn genesis() -> Self {
return Self {
height: 0,
parent: Hash::default(),
state_root: (),
extrinsics_root: (),
consensus_digest: (),
};
}
/// Create and return a valid child header.
fn child(&self) -> Self {
return Self {
height: self.height + 1,
parent: hash(self),
state_root: (),
extrinsics_root: (),
consensus_digest: (),
};
}
/// Verify that all the given headers form a valid chain from this header to the tip.
/// An "entire" chain can be verified by calling this method on a genesis header.
/// This method may assume that the block on which it is called is valid, but it
/// must verify all of the blocks in the slice;
fn verify_sub_chain(&self, chain: &[Header]) -> bool {
let mut curr_hash = hash(self);
let mut is_verified: bool = true;
let mut chain_iter = chain.iter();
let mut curr_height = self.height;
while let Some(header) = chain_iter.next() {
if header.height - curr_height != 1 {
return false;
}
is_verified &= header.parent == curr_hash;
curr_hash = hash(header);
curr_height = header.height;
}
is_verified
}
}
// And finally a few functions to use the code we just
/// Build and return a valid chain with exactly five blocks including the genesis block.
fn build_valid_chain_length_5() -> Vec<Header> {
let g = Header::genesis();
let mut curr_header = g.clone();
let mut chain = vec![curr_header.clone()];
for _ in 0..4 {
chain.push(curr_header.child());
curr_header = curr_header.child();
}
return chain;
}
/// Build and return a chain with at least three headers.
/// The chain should start with a proper genesis header,
/// but the entire chain should NOT be valid.
fn build_an_invalid_chain() -> Vec<Header> {
let g = Header::genesis();
let curr_header = g.clone();
let mut chain = vec![curr_header.clone()];
for _ in 0..2 {
chain.push(curr_header.child());
}
return chain;
}
// To run these tests: `cargo test bc_1
#[test]
fn bc_1_genesis_block_height() {
let g = Header::genesis();
assert!(g.height == 0);
}
#[test]
fn bc_1_genesis_block_parent() {
let g = Header::genesis();
assert!(g.parent == 0);
}
#[test]
fn bc_1_child_block_height() {
let g = Header::genesis();
let b1 = g.child();
assert!(b1.height == 1);
}
#[test]
fn bc_1_child_block_parent() {
let g = Header::genesis();
let b1 = g.child();
assert!(b1.parent == hash(&g));
}
#[test]
fn bc_1_verify_genesis_only() {
let g = Header::genesis();
assert!(g.verify_sub_chain(&[]));
}
#[test]
fn bc_1_verify_three_blocks() {
let g = Header::genesis();
let b1 = g.child();
let b2 = b1.child();
assert!(g.verify_sub_chain(&[b1, b2]));
}
#[test]
fn bc_1_cant_verify_invalid_height() {
// This and following tests use the student's own verify function so as
// not to give away the solution to writing that function.
let g = Header::genesis();
let mut b1 = g.child();
b1.height = 10;
assert!(!g.verify_sub_chain(&[b1]))
}
#[test]
fn bc_1_cant_verify_invalid_parent() {
// This test chooses to use the student's own verify function so as
// not to give away the solution to writing that function.
let g = Header::genesis();
let mut b1 = g.child();
b1.parent = 10;
assert!(!g.verify_sub_chain(&[b1]))
}
#[test]
fn bc_1_verify_chain_length_five() {
// This test chooses to use the student's own verify function.
// This should be relatively safe given that we have already tested that function.
let chain = build_valid_chain_length_5();
assert!(chain[0].verify_sub_chain(&chain[1..]))
}
#[test]
fn bc_1_invalid_chain_is_really_invalid() {
// This test chooses to use the student's own verify function.
// This should be relatively safe given that we have already tested that function.
let invalid_chain = build_an_invalid_chain();
assert!(!invalid_chain[0].verify_sub_chain(&invalid_chain[1..]))
}
p2_extrinsic_state
//! Now that we have a functioning hash-linked data structure, we can use it to actually
//! track some state. Here we will start to explore the idea of extrinsics and state by
//! slightly abusing the header's extrinsics_root and state_root fields. As the names imply,
//! these are typically used for Merkle roots of large data sets. But in our case we will use
//! these fields to directly contain a single extrinsic per block, and a single piece of state.
//!
//! In the coming parts of this tutorial, we will expand this to be more real-world like and
//! use some real batching.
use crate::hash;
// We will use Rust's built-in hashing where the output type is u64. I'll make an alias
// so the code is slightly more readable.
type Hash = u64;
/// The header is now expanded to contain an extrinsic and a state. Note that we are not
/// using roots yet, but rather directly embedding some minimal extrinsic and state info
/// into the header.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Header {
parent: Hash,
height: u64,
extrinsic: u64,
state: u64,
// Still no consensus. That's the next part.
consensus_digest: (),
}
// Here are the methods for creating new header and verifying headers.
// It is your job to write them.
impl Header {
/// Returns a new valid genesis header.
fn genesis() -> Self {
return Self {
height: 0,
parent: Hash::default(),
state: Hash::default(),
extrinsic: Hash::default(),
consensus_digest: (),
};
}
/// Create and return a valid child header.
///
/// This blockchain will work as an adder. That means that the state starts at zero,
/// and at each block we add the extrinsic to the state.
fn child(&self, extrinsic: u64) -> Self {
return Self {
height: self.height + 1,
parent: hash(self),
state: self.state + extrinsic,
extrinsic,
consensus_digest: (),
};
}
/// Verify that all the given headers form a valid chain from this header to the tip.
///
/// In addition to the consecutive heights and linked hashes, we now need to consider our state.
///
/// So in order for a block to verify, we must have the above explained relationship between the
/// extrinsic, the previous state, and the current state.
fn verify_sub_chain(&self, chain: &[Header]) -> bool {
let mut curr_header = self;
let mut is_verified: bool = true;
let mut chain_iter = chain.iter();
let mut curr_height = self.height;
while let Some(header) = chain_iter.next() {
if header.height - curr_height != 1 {
return false;
}
is_verified &= header.parent == hash(curr_header)
&& header.state == curr_header.state + header.extrinsic;
curr_header = header;
curr_height = header.height;
}
is_verified
}
}
// And finally a few functions to use the code we just
/// Build and return a valid chain with the given number of blocks.
fn build_valid_chain(n: u64) -> Vec<Header> {
let g = Header::genesis();
let mut curr_header = g.clone();
let mut chain = vec![curr_header.clone()];
for extrinsic in 0..(n - 1) {
chain.push(curr_header.child(extrinsic));
curr_header = curr_header.child(extrinsic);
}
return chain;
}
/// Build and return a chain with at least three headers.
/// The chain should start with a proper genesis header,
/// but the entire chain should NOT be valid.
///
/// As we saw in the last unit, this is trivial when we construct arbitrary blocks.
/// However, from outside this crate, it is not so trivial. Our interface for creating
/// new blocks, `genesis()` and `child()`, makes it impossible to create arbitrary blocks.
///
/// For this function, ONLY USE the the `genesis()` and `child()` methods to create blocks.
/// The exercise is still possible.
fn build_an_invalid_chain() -> Vec<Header> {
todo!("Exercise 5")
}
/// Build and return two header chains.
/// Both chains should individually be valid.
/// They should have the same genesis header.
/// They should not be the exact same chain.
///
/// Here is an example of two such chains:
/// /-- 3 -- 4
/// G -- 1 -- 2
/// \-- 3'-- 4'
///
/// Side question: What is the fewest number of headers you could create to achieve this goal.
fn build_forked_chain() -> (Vec<Header>, Vec<Header>) {
let chain = build_valid_chain(3);
let shared_header = chain.last().unwrap();
let mut forked_chain_a = chain.clone();
let mut curr_forked_header = shared_header.clone();
for extrinsic in 3..=4 {
forked_chain_a.push(curr_forked_header.child(extrinsic));
curr_forked_header = curr_forked_header.child(extrinsic);
}
let mut forked_chain_b = chain.clone();
let mut curr_forked_header = shared_header.clone();
for extrinsic in 13..=14 {
forked_chain_b.push(curr_forked_header.child(extrinsic));
curr_forked_header = curr_forked_header.child(extrinsic);
}
return (forked_chain_a, forked_chain_b);
// Exercise 7: After you have completed this task, look at how its test is written below.
// There is a critical thinking question for you there.
}
// To run these tests: `cargo test bc_2`
#[test]
fn bc_2_genesis_block_height() {
let g = Header::genesis();
assert!(g.height == 0);
}
#[test]
fn bc_2_genesis_block_parent() {
let g = Header::genesis();
assert!(g.parent == 0);
}
#[test]
fn bc_2_genesis_block_extrinsic() {
// Typically genesis blocks do not have any extrinsics.
// In Substrate they never do. So our convention is to have the extrinsic be 0.
let g = Header::genesis();
assert!(g.extrinsic == 0);
}
#[test]
fn bc_2_genesis_block_state() {
let g = Header::genesis();
assert!(g.state == 0);
}
#[test]
fn bc_2_child_block_height() {
let g = Header::genesis();
let b1 = g.child(0);
assert!(b1.height == 1);
}
#[test]
fn bc_2_child_block_parent() {
let g = Header::genesis();
let b1 = g.child(0);
assert!(b1.parent == hash(&g));
}
#[test]
fn bc_2_child_block_extrinsic() {
let g = Header::genesis();
let b1 = g.child(7);
assert_eq!(b1.extrinsic, 7);
}
#[test]
fn bc_2_child_block_state() {
let g = Header::genesis();
let b1 = g.child(7);
assert_eq!(b1.state, 7);
}
#[test]
fn bc_2_verify_genesis_only() {
let g = Header::genesis();
assert!(g.verify_sub_chain(&[]));
}
#[test]
fn bc_2_verify_three_blocks() {
let g = Header::genesis();
let b1 = g.child(5);
let b2 = b1.child(6);
assert_eq!(b2.state, 11);
assert!(g.verify_sub_chain(&[b1, b2]));
}
#[test]
fn bc_2_cant_verify_invalid_parent() {
let g = Header::genesis();
let mut b1 = g.child(5);
b1.parent = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_2_cant_verify_invalid_number() {
let g = Header::genesis();
let mut b1 = g.child(5);
b1.height = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_2_cant_verify_invalid_state() {
let g = Header::genesis();
let mut b1 = g.child(5);
b1.state = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_2_verify_forked_chain() {
let g = Header::genesis();
let (c1, c2) = build_forked_chain();
// Both chains have the same valid genesis block
assert_eq!(g, c1[0]);
assert_eq!(g, c2[0]);
// Both chains are individually valid
assert!(g.verify_sub_chain(&c1[1..]));
assert!(g.verify_sub_chain(&c2[1..]));
// The two chains are not identical
// Question for students: I've only compared the last blocks here.
// Is that enough? Is it possible that the two chains have the same final block,
// but differ somewhere else?
assert_ne!(c1.last(), c2.last());
}
p3_consensus.rs
//! We now have a hash-linked header chain that accepts simple extrinsics and tracks simple state.
//! Now we will explore consensus. We are not looking at finality or fork choice here. Rather,
//! we are adding validity rules. There are two common types of validity rules and we will explore
//! both.
//! 1. Rules to throttle authoring. In this case we will use a simple PoW.
//! 2. Arbitrary / Political rules. Here we will implement two alternate validity rules
use crate::hash;
use rand::Rng;
// We will use Rust's built-in hashing where the output type is u64. I'll make an alias
// so the code is slightly more readable.
type Hash = u64;
/// In this lesson we are introducing proof of work onto our blocks. We need a hash threshold.
/// You may change this as you see fit, and I encourage you to experiment. Probably best to start
/// high so we aren't wasting time mining. I'll start with 1 in 100 blocks being valid.
const THRESHOLD: u64 = u64::max_value() / 100;
/// In this lesson we introduce the concept of a contentious hard fork. The fork will happen at
/// this block height.
const FORK_HEIGHT: u64 = 2;
/// The header is now expanded to contain a consensus digest.
/// For Proof of Work, the consensus digest is basically just a nonce which gets the block
/// hash below a certain threshold. Although we could call the field `nonce` we will leave
/// the more general `digest` term. For PoA we would have a cryptographic signature in this field.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Header {
parent: Hash,
height: u64,
extrinsic: u64,
state: u64,
consensus_digest: u64,
}
// Here are the methods for creating new header and verifying headers.
// It is your job to write them.
impl Header {
fn generate_nonce(&self) -> u64 {
let mut rng = rand::thread_rng();
return rng.gen::<u32>() as u64;
}
/// Returns a new valid genesis header.
fn genesis() -> Self {
return Self {
height: 0,
parent: Hash::default(),
state: 0,
extrinsic: 0,
consensus_digest: 0,
};
}
/// Create and return a valid child header.
fn child(&self, extrinsic: u64) -> Self {
let mut valid_header: Header = Self {
height: self.height + 1,
parent: hash(self),
state: self.state + extrinsic,
extrinsic,
consensus_digest: Hash::default(),
};
loop {
let nonce = self.generate_nonce();
valid_header.consensus_digest = nonce;
if hash(&valid_header) < THRESHOLD {
return valid_header;
}
}
}
fn is_header_verified(prev_header: &Header, header: &Header) -> bool {
if header.height.saturating_sub(prev_header.height) != 1 {
return false;
}
let valid_hash = header.parent == hash(prev_header);
let valid_extrinsic = header.state == prev_header.state + header.extrinsic;
let valid_consensus_digest = hash(header) < THRESHOLD;
return valid_hash && valid_extrinsic && valid_consensus_digest;
}
/// Verify that all the given headers form a valid chain from this header to the tip.
///
/// In addition to all the rules we had before, we now need to check that the block hash
/// is below a specific threshold.
fn verify_sub_chain(&self, chain: &[Header]) -> bool {
let mut prev_header = self;
let mut chain_iter = chain.iter();
while let Some(header) = chain_iter.next() {
if !Header::is_header_verified(prev_header, header) {
return false;
}
prev_header = header;
}
return true;
}
// After the blockchain ran for a while, a political rift formed in the community.
// (See the constant FORK_HEIGHT) which is set to 2 by default.
// Most community members have become obsessed over the state of the blockchain.
// On the one side, people believe that only blocks with even states should be valid.
// On the other side, people believe in only blocks with odd states.
/// verify that the given headers form a valid chain.
/// In this case "valid" means that the STATE MUST BE EVEN.
fn verify_sub_chain_even(&self, chain: &[Header]) -> bool {
let mut prev_header = self;
let mut chain_iter = chain.iter();
while let Some(header) = chain_iter.next() {
if header.height > FORK_HEIGHT && header.state % 2 != 0 {
return false;
}
if !Header::is_header_verified(prev_header, header) {
return false;
}
prev_header = header;
}
return true;
}
/// verify that the given headers form a valid chain.
/// In this case "valid" means that the STATE MUST BE ODD.
fn verify_sub_chain_odd(&self, chain: &[Header]) -> bool {
let mut prev_header = self;
let mut chain_iter = chain.iter();
while let Some(header) = chain_iter.next() {
if header.height > FORK_HEIGHT && header.state % 2 != 1 {
return false;
}
if !Header::is_header_verified(prev_header, header) {
return false;
}
prev_header = header;
}
return true;
}
}
/// Build and return two different chains with a common prefix.
/// They should have the same genesis header.
///
/// Both chains should be valid according to the original validity rules.
/// The first chain should be valid only according to the even rules.
/// The second chain should be valid only according to the odd rules.
///
/// Return your solutions as three vectors:
/// 1. The common prefix including genesis
/// 2. The even suffix (non-overlapping with the common prefix)
/// 3. The odd suffix (non-overlapping with the common prefix)
///
/// Here is an example of two such chains:
/// /-- 3 -- 4
/// G -- 1 -- 2
/// \-- 3'-- 4'
fn build_contentious_forked_chain() -> (Vec<Header>, Vec<Header>, Vec<Header>) {
let g = Header::genesis(); // state = 0
let b1 = g.child(5); // state = 5
let b2 = b1.child(6); // state = 11
let chain = vec![b1, b2];
let forked_header = chain.last().unwrap();
let forked_even_header_a = forked_header.child(3); // state = 14
let forked_even_header_b = forked_even_header_a.child(2); // state = 16
let forked_odd_chain_a = forked_header.child(4); // state = 15
let forked_odd_chain_b = forked_odd_chain_a.child(2); // state = 17
return (
chain.clone(),
vec![forked_even_header_a, forked_even_header_b],
vec![forked_odd_chain_a, forked_odd_chain_b]);
}
// To run these tests: `cargo test bc_3`
#[test]
fn bc_3_genesis_block_height() {
let g = Header::genesis();
assert!(g.height == 0);
}
#[test]
fn bc_3_genesis_block_parent() {
let g = Header::genesis();
assert!(g.parent == 0);
}
#[test]
fn bc_3_genesis_block_extrinsic() {
// Typically genesis blocks do not have any extrinsics.
// In Substrate they never do. So our convention is to have the extrinsic be 0.
let g = Header::genesis();
assert!(g.extrinsic == 0);
}
#[test]
fn bc_3_genesis_block_state() {
let g = Header::genesis();
assert!(g.state == 0);
}
#[test]
fn bc_3_genesis_consensus_digest() {
// We could require that the genesis block have a valid proof of work as well.
// But instead I've chosen the simpler path of defining the nonce = 0 in genesis.
let g = Header::genesis();
assert!(g.consensus_digest == 0);
}
#[test]
fn bc_3_child_block_height() {
let g = Header::genesis();
let b1 = g.child(0);
assert!(b1.height == 1);
}
#[test]
fn bc_3_child_block_parent() {
let g = Header::genesis();
let b1 = g.child(0);
assert!(b1.parent == hash(&g));
}
#[test]
fn bc_3_child_block_extrinsic() {
let g = Header::genesis();
let b1 = g.child(7);
assert_eq!(b1.extrinsic, 7);
}
#[test]
fn bc_3_child_block_state() {
let g = Header::genesis();
let b1 = g.child(7);
assert_eq!(b1.state, 7);
}
#[test]
fn bc_3_child_block_consensus_digest() {
let g = Header::genesis();
let b1 = g.child(7);
assert!(hash(&b1) < THRESHOLD);
}
#[test]
fn bc_3_verify_genesis_only() {
let g = Header::genesis();
assert!(g.verify_sub_chain(&[]));
}
#[test]
fn bc_3_verify_three_blocks() {
let g = Header::genesis();
let b1 = g.child(5);
let b2 = b1.child(6);
assert_eq!(b2.state, 11);
assert!(g.verify_sub_chain(&[b1, b2]));
}
#[test]
fn bc_3_cant_verify_invalid_parent() {
let g = Header::genesis();
let mut b1 = g.child(5);
b1.parent = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_3_cant_verify_invalid_number() {
let g = Header::genesis();
let mut b1 = g.child(5);
b1.height = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_3_cant_verify_invalid_state() {
let g = Header::genesis();
let mut b1 = g.child(5);
b1.state = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_3_cant_verify_invalid_pow() {
let g = Header::genesis();
let mut b1 = g.child(5);
// It is possible that this test will pass with a false positive because
// the PoW difficulty is relatively low.
b1.consensus_digest = 10;
assert!(!g.verify_sub_chain(&[b1]));
}
#[test]
fn bc_3_even_chain_valid() {
let g = Header::genesis(); // 0
let b1 = g.child(2); // 2
let b2 = b1.child(1); // 3
// It' all about the states, not the extrinsics. So once the state is even
// we need to keep it that way. So add evens
let b3 = b2.child(1); // 4
let b4 = b3.child(2); // 6
assert!(g.verify_sub_chain_even(&[b1, b2, b3, b4]));
}
#[test]
fn bc_3_even_chain_invalid_first_block_after_fork() {
let g = Header::genesis(); // 0
let b1 = g.child(2); // 2
let b2 = b1.child(1); // 3
let b3 = b2.child(2); // 5 - invalid
let b4 = b3.child(1); // 6
assert!(!g.verify_sub_chain_even(&[b1, b2, b3, b4]));
}
#[test]
fn bc_3_even_chain_invalid_second_block_after_fork() {
let g = Header::genesis(); // 0
let b1 = g.child(2); // 2
let b2 = b1.child(1); // 3
let b3 = b2.child(1); // 4
let b4 = b3.child(1); // 5 - invalid
assert!(!g.verify_sub_chain_even(&[b1, b2, b3, b4]));
}
#[test]
fn bc_3_odd_chain_valid() {
let g = Header::genesis(); // 0
let b1 = g.child(2); // 2
let b2 = b1.child(1); // 3
// It' all about the states, not the extrinsics. So once the state is odd
// we need to keep it that way. So add evens
let b3 = b2.child(2); // 5
let b4 = b3.child(2); // 7
assert!(g.verify_sub_chain_odd(&[b1, b2, b3, b4]));
}
#[test]
fn bc_3_odd_chain_invalid_first_block_after_fork() {
let g = Header::genesis(); // 0
let b1 = g.child(2); // 2
let b2 = b1.child(1); // 3
let b3 = b2.child(1); // 4 - invalid
let b4 = b3.child(1); // 5
assert!(!g.verify_sub_chain_odd(&[b1, b2, b3, b4]));
}
#[test]
fn bc_3_odd_chain_invalid_second_block_after_fork() {
let g = Header::genesis(); // 0
let b1 = g.child(2); // 2
let b2 = b1.child(1); // 3
let b3 = b2.child(2); // 5
let b4 = b3.child(1); // 6 - invalid
assert!(!g.verify_sub_chain_odd(&[b1, b2, b3, b4]));
}
#[test]
fn bc_3_verify_forked_chain() {
let (prefix, even, odd) = build_contentious_forked_chain();
let g = &prefix[0];
let full_even_chain = [&prefix[1..], &even].concat();
let full_odd_chain = [&prefix[1..], &odd].concat();
// Both chains are individually valid according to the original rules.
assert!(g.verify_sub_chain(&full_even_chain[..]));
assert!(g.verify_sub_chain(&full_odd_chain[..]));
// Only the even chain is valid according to the even rules
assert!(g.verify_sub_chain_even(&full_even_chain[..]));
assert!(!g.verify_sub_chain_even(&full_odd_chain[..]));
// Only the odd chain is valid according to the odd rules
assert!(!g.verify_sub_chain_odd(&full_even_chain[..]));
assert!(g.verify_sub_chain_odd(&full_odd_chain[..]));
}
p4_batched_extrinsic.rs
//! Until now, each block has contained just a single extrinsic. Really we would prefer to batch
//! them. Now, we stop relying solely on headers, and instead, create complete blocks.
use crate::hash;
type Hash = u64;
/// The header no longer contains an extrinsic directly. Rather a vector of extrinsics will be
/// stored in the block body. We are still storing the state in the header for now. This will change
/// in an upcoming lesson as well.
#[derive(Default, Clone, Debug, PartialEq, Eq, Hash)]
pub struct Header {
parent: Hash,
height: u64,
// We now switch from storing an extrinsic directly, to storing an extrinsic root.
// This is basically a concise cryptographic commitment to the complete list of extrinsics.
// For example, a hash or a Merkle root.
extrinsics_root: Hash,
state: u64,
pub consensus_digest: u64,
}
// Methods for creating and verifying headers.
//
// With the extrinsics no longer stored in the header, we can no longer do
// "on-chain" execution with just headers. That means that this code actually
// gets simpler in many ways. All the old execution logic, plus some new batching
// logic moves to the block level now.
impl Header {
/// Returns a new valid genesis header.
pub fn genesis() -> Self {
return Self {
height: 0,
parent: Hash::default(),
state: 0,
consensus_digest: 0,
extrinsics_root: Hash::default(),
};
}
/// Create and return a valid child header.
/// Without the extrinsics themselves, we cannot calculate the final state
/// so that information is passed in.
pub fn child(&self, extrinsics_root: Hash, state: u64) -> Self {
return Self {
state,
extrinsics_root,
height: self.height + 1,
parent: hash(self),
consensus_digest: 0,
};
}
/// Verify a single child header.
///
/// This is a slightly different interface from the previous units. Rather
/// than verify an entire sub-chain, this function checks a single header.
/// This is useful because checking the header can now be thought of as a
/// subtask of checking an entire block. So it doesn't make sense to check
/// the entire header chain at once if the chain may be invalid at the second block.
fn verify_child(&self, child: &Header) -> bool {
if child.height.saturating_sub(self.height) != 1 {
return false;
}
let valid_hash = child.parent == hash(self);
let valid_extrinsic = child.state == self.state;
return valid_hash && valid_extrinsic;
}
/// Verify that all the given headers form a valid chain from this header to the tip.
///
/// We can now trivially write the old verification function in terms of the new one.
/// Extra street cred if you can write it
/// - with a loop
/// - with head recursion
/// - with tail recursion
fn verify_sub_chain(&self, chain: &[Header]) -> bool {
let mut chain_iter = chain.iter();
let get_child_header = chain_iter.next();
return match get_child_header {
Some(header) => {
self.verify_child(header) && header.verify_sub_chain(chain_iter.as_slice())
},
None => true,
};
}
}
/// A complete Block is a header and the extrinsics.
#[derive(Default, Clone, Debug, PartialEq, Eq, Hash)]
pub struct Block {
pub(crate) header: Header,
pub(crate) body: Vec<u64>,
}
// Methods for creating and verifying blocks.
//
// These methods are analogous to the methods on the headers. All of the
// transaction execution logic is now handled at the block level because
// the transactions are no longer available at the Header level.
impl Block {
fn execute_extrinsics(extrinsics: &Vec<u64>) -> u64 {
let mut state = 0;
for extrinsic in extrinsics.iter() {
state += extrinsic;
}
return state;
}
/// Returns a new valid genesis block. By convention this block has no extrinsics.
pub fn genesis() -> Self {
return Self { header: Header::genesis(), body: vec![] };
}
/// Create and return a valid child block.
/// The extrinsics are batched now, so we need to execute each of them.
pub fn child(&self, extrinsics: Vec<u64>) -> Self {
return Self {
header: self.header.child(
hash(&extrinsics),
self.header.state + Block::execute_extrinsics(&extrinsics),
),
body: extrinsics,
};
}
/// Verify that all the given blocks form a valid chain from this block to the tip.
///
/// We need to verify the headers as well as execute all transactions and check the final state.
pub fn verify_sub_chain(&self, chain: &[Block]) -> bool {
let mut chain_iter = chain.iter();
let get_child_block = chain_iter.next();
return match get_child_block {
Some(block) => {
// state value of the current block + state value of the child block = final state in block header
Block::execute_extrinsics(&self.body) + Block::execute_extrinsics(&block.body)
== block.header.state
&& hash(&block.body) == block.header.extrinsics_root
&& block.verify_sub_chain(chain_iter.as_slice())
},
None => true,
};
}
}
/// Create an invalid child block of the given block. Although the child block is invalid,
/// the header should be valid.
///
/// Now that extrinsics are separate from headers, the logic for checking headers does
/// not include actual transaction execution. That means it is possible for a header to be
/// valid, but the block containing that header to be invalid.
///
/// Notice that you do not need the entire parent block to do this. You only need the header.
fn build_invalid_child_block_with_valid_header(parent: &Header) -> Block {
let child_header = parent.child(hash(&vec![1, 2, 3]), 0);
let child_block = Block { header: child_header, body: vec![] };
return child_block;
}
#[test]
fn bc_4_genesis_header() {
let g = Header::genesis();
assert_eq!(g.height, 0);
assert_eq!(g.parent, 0);
assert_eq!(g.extrinsics_root, 0);
assert_eq!(g.state, 0);
}
#[test]
fn bc_4_genesis_block() {
let gh = Header::genesis();
let gb = Block::genesis();
assert_eq!(gb.header, gh);
assert!(gb.body.is_empty());
}
#[test]
fn bc_4_child_block_empty() {
let b0 = Block::genesis();
let b1 = b0.child(vec![]);
assert_eq!(b1.header.height, 1);
assert_eq!(b1.header.parent, hash(&b0.header));
assert_eq!(b1, Block { header: b1.header.clone(), body: vec![] });
}
#[test]
fn bc_4_child_block() {
let b0 = Block::genesis();
let b1 = b0.child(vec![1, 2, 3, 4, 5]);
assert_eq!(b1.header.height, 1);
assert_eq!(b1.header.parent, hash(&b0.header));
assert_eq!(b1, Block { header: b1.header.clone(), body: vec![1, 2, 3, 4, 5] });
}
#[test]
fn bc_4_child_header() {
let g = Header::genesis();
let h1 = g.child(hash(&[1, 2, 3]), 6);
assert_eq!(h1.height, 1);
assert_eq!(h1.parent, hash(&g));
assert_eq!(h1.extrinsics_root, hash(&[1, 2, 3]));
assert_eq!(h1.state, 6);
let h2 = h1.child(hash(&[10, 20]), 36);
assert_eq!(h2.height, 2);
assert_eq!(h2.parent, hash(&h1));
assert_eq!(h2.extrinsics_root, hash(&[10, 20]));
assert_eq!(h2.state, 36);
}
#[test]
fn bc_4_verify_three_blocks() {
let g = Block::genesis();
let b1 = g.child(vec![1]);
let b2 = b1.child(vec![2]);
let chain = vec![g.clone(), b1, b2];
assert!(g.verify_sub_chain(&chain[1..]));
}
#[test]
fn bc_4_invalid_header_does_not_check() {
let g = Header::genesis();
let h1 = Header { parent: 0, height: 100, extrinsics_root: 0, state: 100, consensus_digest: 0 };
assert!(!g.verify_child(&h1));
}
#[test]
fn bc_4_invalid_block_state_does_not_check() {
let b0 = Block::genesis();
let mut b1 = b0.child(vec![1, 2, 3]);
b1.body = vec![];
assert!(!b0.verify_sub_chain(&[b1]));
}
#[test]
fn bc_4_block_with_invalid_header_does_not_check() {
let b0 = Block::genesis();
let mut b1 = b0.child(vec![1, 2, 3]);
b1.header = Header::genesis();
assert!(!b0.verify_sub_chain(&[b1]));
}
#[test]
fn bc_4_student_invalid_block_really_is_invalid() {
let gb = Block::genesis();
let gh = &gb.header;
let b1 = build_invalid_child_block_with_valid_header(gh);
let h1 = &b1.header;
// Make sure that the header is valid according to header rules.
assert!(gh.verify_child(h1));
// Make sure that the block is not valid when executed.
assert!(!gb.verify_sub_chain(&[b1]));
}
p5_fork_choice.rs
//! Forks in the blockchain represent alternative histories of the system.
//! When forks arise in the blockchain, users need a way to decide which chain
//! they will consider best, for now. This is known as a "fork choice rule".
//! There are several meaningful notions of "best", so we introduce a trait
//! that allows multiple implementations.
//!
//! Since we have nothing to add to the Block or Header data structures in this lesson,
//! we will import them from the previous lesson.
use rand::Rng;
use super::p4_batched_extrinsics::{Block, Header};
use crate::hash;
const THRESHOLD: u64 = u64::max_value() / 100;
/// Judge which blockchain is "best" when there are multiple candidates. There are several
/// meaningful notions of "best" which is why this is a trait instead of just a
/// method.
pub trait ForkChoice {
/// Compare two chains, and return the "best" one.
///
/// The chains are not assumed to start from the same genesis block, or even a
/// genesis block at all. This makes it possible to compare entirely disjoint
/// histories. It also makes it possible to compare _only_ the divergent part
/// of sibling chains back to the last common ancestor.
///
/// The chains are assumed to be valid, so it is up to the caller to check
/// validity first if they are unsure.
fn first_chain_is_better(chain_1: &[Header], chain_2: &[Header]) -> bool;
/// Compare many chains and return the best one.
///
/// It is always possible to compare several chains if you are able to compare
/// two chains. Therefore this method has a provided implementation. However,
/// it may be much more performant to write a fork-choice-specific implementation.
fn best_chain<'a>(candidate_chains: &[&'a [Header]]) -> &'a [Header] {
todo!("Exercise 1")
}
}
/// The "best" chain is simply the longest chain.
pub struct LongestChainRule;
impl ForkChoice for LongestChainRule {
fn first_chain_is_better(chain_1: &[Header], chain_2: &[Header]) -> bool {
return chain_1.len() > chain_2.len();
}
fn best_chain<'a>(candidate_chains: &[&'a [Header]]) -> &'a [Header] {
// Remember, this method is provided. You _can_ solve the exercise by
// simply deleting this block. It is up to you to decide whether this fork
// choice warrants a custom implementation.
let mut chain_iter = candidate_chains.iter();
let mut best = chain_iter.next().unwrap();
while let Some(next_chain) = chain_iter.next() {
if best.len() < next_chain.len() {
best = next_chain;
}
}
return best;
}
}
/// The best chain is the one with the most accumulated work.
///
/// In Proof of Work chains, each block contains a certain amount of "work".
/// Roughly speaking, the lower a block's hash is, the more work it contains,
/// because finding a block with a low hash requires, on average, trying more
/// nonces. Modeling the amount of work required to achieve a particular hash
/// is out of scope for this exercise, so we will use the not-really-right-but
/// conceptually-good-enough formula `work = THRESHOLD - block_hash`
pub struct HeaviestChainRule;
fn generate_nonce() -> u64 {
let mut rng = rand::thread_rng();
return rng.gen::<u32>() as u64;
}
fn mine_consensus_digest(header: &mut Header, threshold: u64) {
let mut valid_header = header.clone();
loop {
let nonce = generate_nonce();
valid_header.consensus_digest = nonce;
if hash(&valid_header) < threshold {
header.consensus_digest = nonce;
break;
}
}
}
/// Mutates a block (and its embedded header) to contain more PoW difficulty.
/// This will be useful for exploring the heaviest chain rule. The expected
/// usage is that you create a block using the normal `Block.child()` method
/// and then pass the block to this helper for additional mining.
fn mine_extra_hard(block: &mut Block, threshold: u64) {
mine_consensus_digest(&mut block.header, threshold);
}
impl HeaviestChainRule {
fn get_total_work(chain: &[Header]) -> i64 {
let mut total_work: i64 = 0;
chain.iter().for_each(|header| {
total_work = total_work.saturating_add(THRESHOLD as i64 - hash(header) as i64);
});
return total_work;
}
}
impl ForkChoice for HeaviestChainRule {
fn first_chain_is_better(chain_1: &[Header], chain_2: &[Header]) -> bool {
return HeaviestChainRule::get_total_work(chain_1)
> HeaviestChainRule::get_total_work(chain_2);
}
fn best_chain<'a>(candidate_chains: &[&'a [Header]]) -> &'a [Header] {
// Remember, this method is provided.
let mut chain_iter = candidate_chains.iter();
let mut best = chain_iter.next().unwrap();
while let Some(next_chain) = chain_iter.next() {
if HeaviestChainRule::get_total_work(best)
< HeaviestChainRule::get_total_work(next_chain)
{
best = next_chain;
}
}
return best;
}
}
/// The best chain is the one with the most blocks that have even hashes.
///
/// This exact rule is a bit contrived, but it does model a family of fork choice rules
/// that are useful in the real world. We just can't code them here because we haven't
/// implemented Proof of Authority yet. Consider the following real world examples
/// that have very similar implementations.
///
/// 1. Secondary authors. In each round there is one author who is supposed to author. If that
/// author fails to create a block, there is a secondary author who may do so. The best chain is
/// the one with the most primary-authored blocks.
///
/// 2. Interleaved Pow/PoA. In each round there is one author who is allowed to author. Anyone else
/// is allowed to mine a PoW-style block. The best chain is the one with the most PoA blocks, and
/// ties are broken by the most accumulated work.
pub struct MostBlocksWithEvenHash;
impl MostBlocksWithEvenHash {
pub fn count_even_hash(chain: &[Header]) -> usize {
let mut block_count = 0;
chain.iter().for_each(|block| {
let block_hash = hash(block);
if block_hash % 2 == 0 {
block_count += 1;
}
});
return block_count;
}
}
impl ForkChoice for MostBlocksWithEvenHash {
fn first_chain_is_better(chain_1: &[Header], chain_2: &[Header]) -> bool {
return MostBlocksWithEvenHash::count_even_hash(chain_1)
> MostBlocksWithEvenHash::count_even_hash(chain_2);
}
fn best_chain<'a>(candidate_chains: &[&'a [Header]]) -> &'a [Header] {
// Remember, this method is provided.
let mut chain_iter = candidate_chains.iter();
let mut best = chain_iter.next().unwrap();
while let Some(next_chain) = chain_iter.next() {
if MostBlocksWithEvenHash::count_even_hash(best)
< MostBlocksWithEvenHash::count_even_hash(next_chain)
{
best = next_chain;
}
}
return best;
}
}
// This lesson has omitted one popular fork choice rule:
// GHOST - Greedy Heaviest Observed SubTree
//
// I've omitted GHOST from here because it requires information about blocks that
// are _not_ in the chain to decide which chain is best. Therefore it does't work
// well with this relatively simple trait definition. We will return to the GHOST
// rule later when we have written a full blockchain client
//
// The GHOST rule was first published in 2013 by Yonatan Sompolinsky and Aviv Zohar.
// Learn more at https://eprint.iacr.org/2013/881.pdf
//
/// Build and return two different chains with a common prefix.
/// They should have the same genesis header. Both chains should be valid.
/// The first chain should be longer (have more blocks), but the second
/// chain should have more accumulated work.
///
/// Return your solutions as three vectors:
/// 1. The common prefix including genesis
/// 2. The suffix chain which is longer (non-overlapping with the common prefix)
/// 3. The suffix chain with more work (non-overlapping with the common prefix)
fn create_fork_one_side_longer_other_side_heavier() -> (Vec<Header>, Vec<Header>, Vec<Header>) {
let g = Header::genesis();
let b1 = g.child(hash(&vec![1]), 2);
let b2 = b1.child(hash(&vec![2]), 3);
let prefix_chain = vec![b1, b2];
// 1. The common prefix including genesis
let forked_header = prefix_chain.last().unwrap();
// 2. The suffix chain which is longer (non-overlapping with the common prefix)
let mut longest_chain_ha = forked_header.child(hash(&vec![1, 2]), 3);
mine_consensus_digest(&mut longest_chain_ha, u64::max_value() / 2);
let mut longest_chain_hb = longest_chain_ha.child(hash(&vec![3, 4]), 10);
mine_consensus_digest(&mut longest_chain_hb, u64::max_value() / 5);
let mut longest_chain_hc = longest_chain_hb.child(hash(&vec![7]), 17);
mine_consensus_digest(&mut longest_chain_hc, u64::max_value() / 3);
let mut longest_chain_hd = longest_chain_hc.child(hash(&vec![4, 5]), 26);
mine_consensus_digest(&mut longest_chain_hd, u64::max_value() / 4);
let mut more_work_chain_ha = forked_header.child(hash(&vec![5, 6]), 11);
mine_consensus_digest(&mut more_work_chain_ha, u64::max_value() / 200); // 1 valid block / 200 blocks
let mut more_work_chain_hb = more_work_chain_ha.child(hash(&vec![1, 2]), 14);
mine_consensus_digest(&mut more_work_chain_hb, u64::max_value() / 250); // 1 valid block / 250 blocks
return (
prefix_chain.clone(),
vec![longest_chain_ha, longest_chain_hb, longest_chain_hc, longest_chain_hd],
vec![more_work_chain_ha, more_work_chain_hb],
);
}
#[test]
fn bc_5_longest_chain() {
let g = Header::genesis();
let h_a1 = g.child(hash(&[1]), 1);
let h_a2 = h_a1.child(hash(&[2]), 2);
let chain_1 = &[g.clone(), h_a1, h_a2];
let h_b1 = g.child(hash(&[3]), 3);
let chain_2 = &[g, h_b1];
assert!(LongestChainRule::first_chain_is_better(chain_1, chain_2));
assert_eq!(LongestChainRule::best_chain(&[chain_1, chain_2]), chain_1);
}
#[test]
fn bc_5_mine_to_custom_difficulty() {
let g = Block::genesis();
let mut b1 = g.child(vec![1, 2, 3]);
// We want the custom threshold to be high enough that we don't take forever mining
// but low enough that it is unlikely we accidentally meet it with the normal
// block creation function
let custom_threshold = u64::max_value() / 1000;
mine_extra_hard(&mut b1, custom_threshold);
assert!(hash(&b1.header) < custom_threshold);
}
#[test]
fn bc_5_heaviest_chain() {
let g = Header::genesis();
let mut i = 0;
let h_a1 = loop {
let header = g.child(hash(&[i]), i);
// Extrinsics root hash must be higher than threshold (less work done)
if hash(&header) > THRESHOLD {
break header;
}
i += 1;
};
let chain_1 = &[g.clone(), h_a1];
let h_b1 = loop {
let header = g.child(hash(&[i]), i);
// Extrinsics root hash must be lower than threshold (more work done)
if hash(&header) < THRESHOLD {
break header;
}
i += 1;
};
let chain_2 = &[g, h_b1];
assert!(HeaviestChainRule::first_chain_is_better(chain_2, chain_1));
assert_eq!(HeaviestChainRule::best_chain(&[chain_1, chain_2]), chain_2);
}
#[test]
fn bc_5_most_even_blocks() {
let g = Header::genesis();
let mut h_a1 = g.child(2, 0);
for i in 0..u64::max_value() {
h_a1 = g.child(2, i);
if hash(&h_a1) % 2 == 0 {
break;
}
}
let mut h_a2 = g.child(2, 0);
for i in 0..u64::max_value() {
h_a2 = h_a1.child(2, i);
if hash(&h_a2) % 2 == 0 {
break;
}
}
let chain_1 = &[g.clone(), h_a1, h_a2];
let mut h_b1 = g.child(2, 0);
for i in 0..u64::max_value() {
h_b1 = g.child(2, i);
if hash(&h_b1) % 2 != 0 {
break;
}
}
let mut h_b2 = g.child(2, 0);
for i in 0..u64::max_value() {
h_b2 = h_b1.child(2, i);
if hash(&h_b2) % 2 != 0 {
break;
}
}
let chain_2 = &[g, h_b1, h_b2];
assert!(MostBlocksWithEvenHash::first_chain_is_better(chain_1, chain_2));
assert_eq!(MostBlocksWithEvenHash::best_chain(&[chain_1, chain_2]), chain_1);
}
#[test]
fn bc_5_longest_vs_heaviest() {
let (_, longest_chain, pow_chain) = create_fork_one_side_longer_other_side_heavier();
assert!(LongestChainRule::first_chain_is_better(&longest_chain, &pow_chain));
assert_eq!(LongestChainRule::best_chain(&[&longest_chain, &pow_chain]), &longest_chain);
let (_, longest_chain, pow_chain) = create_fork_one_side_longer_other_side_heavier();
assert!(HeaviestChainRule::first_chain_is_better(&pow_chain, &longest_chain));
assert_eq!(HeaviestChainRule::best_chain(&[&longest_chain, &pow_chain]), &pow_chain);
}
p6_rich_state.rs
//! In this lesson we expand our simple notion of state, and show how the state is typically not
//! stored in the header, Or indeed anywhere in the block at all.
//!
//! To facilitate this exercise, consider that we want our blockchain to store not only the sum of
//! the extrinsics, but also the product. You can also imagine many other calculations the chain may
//! want to track (min, max, median, mean, etc).
//!
//! As the state data gets large, it is no longer reasonable to store it in the blocks. But if the
//! state isn't in the blocks, then how can we perform the state-related validation checks we
//! previously performed? We use a state root to cryptographically link our heder to a complete
//! state.
//!
//! This notion of state may sound familiar from our previous work on state machines. Indeed this
//! naming coincidence foreshadows a key abstraction that we will make in a coming chapter.
type Hash = u64;
use crate::hash;
/// In this section we will use sum and product together to be our state. While this is only a
/// doubling of state size remember that in real world blockchains, the state is often really really
/// large.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct State {
sum: u64,
product: u64,
}
/// The header no longer contains the state directly, but rather, it contains a hash of
/// the complete state. This hash will allow block verifiers to cryptographically confirm
/// that they got the same state as the author without having a complete copy of the
/// author's state
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Header {
parent: Hash,
height: u64,
extrinsics_root: Hash,
/// Stores a cryptographic commitment, like a Merkle root or a hash to the complete
/// post state.
state_root: Hash,
consensus_digest: u64,
}
// Methods for creating and verifying headers.
//
// We already moved the execution logic to the block level in the last section.
// So this code is similar to last time. One key addition we are making is that
// genesis blocks can have an initial state, or "genesis state" other than the
// default. So we need to commit the initial state root to the genesis header here.
impl Header {
/// Returns a new valid genesis header.
fn genesis(genesis_state_root: Hash) -> Self {
return Self {
height: 0,
parent: Hash::default(),
state_root: genesis_state_root,
consensus_digest: 0,
extrinsics_root: Hash::default(),
};
}
/// Create and return a valid child header.
///
/// The state root is passed in similarly to how the complete state
/// was in the previous section.
fn child(&self, extrinsics_root: Hash, state_root: Hash) -> Self {
return Self {
height: self.height + 1,
parent: hash(self),
state_root,
consensus_digest: 0,
extrinsics_root,
};
}
/// Verify a single child header.
fn verify_child(&self, child: &Header) -> bool {
child.height.saturating_sub(self.height) == 1 && child.parent == hash(self)
}
/// Verify that all the given headers form a valid chain from this header to the tip.
fn verify_sub_chain(&self, chain: &[Header]) -> bool {
let get_next_header = chain.iter().next();
return get_next_header.is_some()
&& self.verify_child(get_next_header.unwrap())
&& get_next_header.unwrap().verify_sub_chain(chain);
}
}
/// A complete Block is a header and the extrinsics.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Block {
pub(crate) header: Header,
pub(crate) body: Vec<u64>,
}
/// Methods for creating and verifying blocks.
///
/// We no longer have access to a state simply by having access to a block.
/// Therefore, we need a pre-state explicitly passed for these block methods.
/// In a real blockchain network, the client is typically responsible for
/// storing some likely-to-be-needed states and have them ready for use in
/// such operations.
///
/// These methods also differ from last time because you will need to
/// calculate state roots to pass to the header-level methods.
impl Block {
/// Returns a new valid genesis block. By convention this block has no extrinsics.
pub fn genesis(genesis_state: &State) -> Self {
Block { header: Header::genesis(hash(genesis_state)), body: vec![] }
}
/// Create and return a valid child block.
pub fn child(&self, pre_state: &State, extrinsics: Vec<u64>) -> Self {
let state = Block::execute_extrinsics(&mut pre_state.clone(), &extrinsics);
Block { header: self.header.child(hash(&extrinsics), hash(&state)), body: extrinsics }
}
fn execute_extrinsics(pre_state: &mut State, extrinsics: &Vec<u64>) -> State {
for extrinsic in extrinsics.iter() {
pre_state.sum += extrinsic;
pre_state.product *= extrinsic;
}
return pre_state.clone();
}
/// Verify that all the given blocks form a valid chain from this block to the tip.
///
/// This time we need to validate the initial block itself by confirming that we
/// have been given a valid pre-state. And we still need to verify the headers,
/// execute all transactions, and check the final state.
pub fn verify_sub_chain(&self, pre_state: &State, chain: &[Block]) -> bool {
let mut chain_iter = chain.iter();
let get_child_block = chain_iter.next();
let state = Block::execute_extrinsics(&mut pre_state.clone(), &self.body);
// validate the initial block itself by confirming that we have been give a valid pre-state
return hash(&state) == self.header.state_root
&& match get_child_block {
Some(block) => {
self.header.verify_child(&block.header)
// validate that the block extrinsics stored in body match with the header extrinsic root
&& hash(&block.body) == block.header.extrinsics_root
&& block.verify_sub_chain(&state, chain_iter.as_slice())
},
None => true,
};
}
}
/// Create an invalid child block of the given block. The returned block should have an
/// incorrect state root. Although the child block is invalid, the header should be valid.
///
/// As we saw in the previous section, the logic for checking headers can no longer
/// not include actual transaction execution, making it possible for invalid blocks
/// to still contain valid headers. There are now two ways to accomplish this.
/// 1. Block includes wrong extrinsics that do not match extrinsics root in header (from last time)
/// 2. Block contains invalid state root that does not match the correct post state (new this time)
///
/// As before, you do not need the entire parent block to do this. You only need the header.
/// You do, however, now need a pre-state as you have throughout much of this section.
fn build_invalid_child_block_with_valid_header(parent: &Header, pre_state: &State) -> Block {
let extrinsics = vec![1, 2, 3];
Block {
header: parent.child(
hash(&extrinsics),
hash(&Block::execute_extrinsics(&mut pre_state.clone(), &vec![1])),
),
body: extrinsics,
}
}
#[test]
fn bc_6_genesis_header() {
let state = State { sum: 6, product: 9 };
let g = Header::genesis(hash(&state));
assert_eq!(g.height, 0);
assert_eq!(g.parent, 0);
assert_eq!(g.extrinsics_root, 0);
assert_eq!(g.state_root, hash(&state));
}
#[test]
fn bc_6_genesis_block() {
let state = State { sum: 6, product: 9 };
let gh = Header::genesis(hash(&state));
let gb = Block::genesis(&state);
assert_eq!(gb.header, gh);
assert!(gb.body.is_empty());
}
#[test]
fn bc_6_child_block_empty() {
let state = State { sum: 6, product: 9 };
let b0 = Block::genesis(&state);
let b1 = b0.child(&state, vec![]);
assert_eq!(b1.header.height, 1);
assert_eq!(b1.header.parent, hash(&b0.header));
assert_eq!(b1, Block { header: b1.header.clone(), body: vec![] });
}
#[test]
fn bc_6_child_block() {
let state = State { sum: 6, product: 9 };
let b0 = Block::genesis(&state);
let b1 = b0.child(&state, vec![1, 2, 3, 4, 5]);
assert_eq!(b1.header.height, 1);
assert_eq!(b1.header.parent, hash(&b0.header));
assert_eq!(b1, Block { header: b1.header.clone(), body: vec![1, 2, 3, 4, 5] });
}
#[test]
fn bc_6_child_header() {
let state_0 = State { sum: 6, product: 9 };
let g = Header::genesis(hash(&state_0));
let mut extrinsics = vec![1, 2, 3];
let mut state_1 = state_0;
for extrinsic in extrinsics.iter() {
state_1.sum += extrinsic;
state_1.product *= extrinsic;
}
let h1 = g.child(hash(&extrinsics), hash(&state_1));
assert_eq!(h1.height, 1);
assert_eq!(h1.parent, hash(&g));
assert_eq!(h1.extrinsics_root, hash(&extrinsics));
assert_eq!(h1.state_root, hash(&state_1));
extrinsics = vec![10, 20];
let mut state_2 = state_1;
for extrinsic in extrinsics.iter() {
state_2.sum += extrinsic;
state_2.product *= extrinsic;
}
let h2 = h1.child(hash(&extrinsics), hash(&state_2));
assert_eq!(h2.height, 2);
assert_eq!(h2.parent, hash(&h1));
assert_eq!(h2.extrinsics_root, hash(&extrinsics));
assert_eq!(h2.state_root, hash(&state_2));
}
#[test]
fn bc_6_verify_three_blocks() {
let state_1 = State { sum: 6, product: 9 };
let g = Block::genesis(&state_1);
let b1 = g.child(&state_1, vec![1]);
let state_2 = State { sum: 7, product: 9 };
let b2 = b1.child(&state_2, vec![2]);
let chain = vec![g.clone(), b1, b2];
assert!(g.verify_sub_chain(&state_1, &chain[1..]));
}
#[test]
fn bc_6_invalid_header_doesnt_check() {
let state = State { sum: 6, product: 9 };
let g = Header::genesis(hash(&state));
let h1 = Header {
parent: 0,
height: 100,
extrinsics_root: 0,
state_root: hash(&(State { sum: 0, product: 0 })),
consensus_digest: 0,
};
assert!(!g.verify_child(&h1));
}
#[test]
fn bc_6_invalid_block_state_doesnt_check() {
let state = State { sum: 6, product: 9 };
let b0 = Block::genesis(&state);
let mut b1 = b0.child(&state, vec![1, 2, 3]);
b1.body = vec![];
assert!(!b0.verify_sub_chain(&state, &[b1]));
}
#[test]
fn bc_6_block_with_invalid_header_doesnt_check() {
let state = State { sum: 6, product: 9 };
let b0 = Block::genesis(&state);
let mut b1 = b0.child(&state, vec![1, 2, 3]);
b1.header = Header::genesis(hash(&state));
assert!(!b0.verify_sub_chain(&state, &[b1]));
}
#[test]
fn bc_6_student_invalid_block_really_is_invalid() {
let state = State { sum: 6, product: 9 };
let gb = Block::genesis(&state);
let gh = &gb.header;
let b1 = build_invalid_child_block_with_valid_header(gh, &state);
let h1 = &b1.header;
// Make sure that the header is valid according to header rules.
assert!(gh.verify_child(h1));
// Make sure that the block is not valid when executed.
assert!(!gb.verify_sub_chain(&state, &[b1]));
}
Please read this information first before working on this issue
Before committing to the tasks in the community, please skim through the guidelines below to grasp the overall idea of how the community works first. It does not take long but I believe it will give you a big picture of the vision and culture of TheLowLevelers.
Description
p1_header_chain.rs
p2_extrinsic_state
p3_consensus.rs
p4_batched_extrinsic.rs
p5_fork_choice.rs
p6_rich_state.rs
Please read this information first before working on this issue
Before committing to the tasks in the community, please skim through the guidelines below to grasp the overall idea of how the community works first. It does not take long but I believe it will give you a big picture of the vision and culture of TheLowLevelers.