Skip to content
1        10        20        30        40        50        60        70        80        901//! A deliberately small, educational proof-of-work blockchain.23use std::error::Error;4use std::fmt;56use sha2::{Digest, Sha256};78/// SHA-256 digest stored by every block.9pub type Hash = [u8; 32];1011/// One simple, structurally validated transfer.12#[derive(Clone, Debug, Eq, PartialEq)]13pub struct Transaction {14    pub sender: String,15    pub recipient: String,16    pub amount: u64,17}1819impl Transaction {20    /// Create a transaction. The chain checks its fields when a block is mined21    /// and whenever the chain is validated.22    #[must_use]23    pub fn new(sender: impl Into<String>, recipient: impl Into<String>, amount: u64) -> Self {24        Self {25            sender: sender.into(),26            recipient: recipient.into(),27            amount,28        }29    }3031    fn is_valid(&self) -> bool {32        !self.sender.trim().is_empty() && !self.recipient.trim().is_empty() && self.amount > 033    }34}3536/// A mined block, including its link to the preceding block.37#[derive(Clone, Debug, Eq, PartialEq)]38pub struct Block {39    pub index: u64,40    pub previous_hash: Hash,41    pub transactions: Vec<Transaction>,42    pub nonce: u64,43    pub hash: Hash,44}4546impl Block {47    /// Return the block's digest as 64 lowercase hexadecimal characters.48    #[must_use]49    pub fn hash_hex(&self) -> String {50        hash_hex(&self.hash)51    }5253    fn calculate_hash(&self) -> Hash {54        let mut hasher = Sha256::new();55        hasher.update(b"pow-chain:block:v1");56        update_field(&mut hasher, &self.index.to_be_bytes());57        update_field(&mut hasher, &self.previous_hash);58        update_field(&mut hasher, &self.nonce.to_be_bytes());59        update_field(60            &mut hasher,61            &self.transactions.len().to_string().into_bytes(),62        );6364        for transaction in &self.transactions {65            update_field(&mut hasher, transaction.sender.as_bytes());66            update_field(&mut hasher, transaction.recipient.as_bytes());67            update_field(&mut hasher, &transaction.amount.to_be_bytes());68        }6970        hasher.finalize().into()71    }7273    fn mine(74        index: u64,75        previous_hash: Hash,76        transactions: Vec<Transaction>,77        difficulty: u8,78    ) -> (Self, u64) {79        let mut block = Self {80            index,81            previous_hash,82            transactions,83            nonce: 0,84            hash: [0; 32],85        };8687        loop {88            block.hash = block.calculate_hash();89            if meets_difficulty(&block.hash, difficulty) {90                let attempts = block.nonce + 1;91                return (block, attempts);92            }93            block.nonce = block.nonce.checked_add(1).expect("nonce space exhausted");94        }95    }96}9798/// A chain of hash-linked, proof-of-work blocks.99#[derive(Clone, Debug)]100pub struct Blockchain {101    difficulty: u8,102    blocks: Vec<Block>,103}104105/// Summary of the work performed while appending a block.106#[derive(Clone, Debug, Eq, PartialEq)]107pub struct MiningSummary {108    pub block_index: u64,109    pub nonce: u64,110    pub hash: Hash,111    /// Number of hashes evaluated, including the successful one.112    pub attempts: u64,113}114115/// Errors returned when constructing, mining, or validating a chain.116#[derive(Clone, Debug, Eq, PartialEq)]117pub enum ChainError {118    InvalidDifficulty(u8),119    InvalidTransaction {120        block_index: u64,121        transaction_index: usize,122    },123    EmptyChain,124    InvalidIndex {125        expected: u64,126        actual: u64,127    },128    InvalidPreviousHash {129        block_index: u64,130    },131    InvalidBlockHash {132        block_index: u64,133    },134    InsufficientDifficulty {135        block_index: u64,136    },137}138139impl fmt::Display for ChainError {140    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {141        match self {142            Self::InvalidDifficulty(difficulty) => {143                write!(formatter, "difficulty {difficulty} is outside 0..=64")144            }145            Self::InvalidTransaction {146                block_index,147                transaction_index,148            } => write!(149                formatter,150                "block {block_index} has an invalid transaction at position {transaction_index}"151            ),152            Self::EmptyChain => formatter.write_str("chain has no genesis block"),153            Self::InvalidIndex { expected, actual } => {154                write!(formatter, "expected block index {expected}, got {actual}")155            }156            Self::InvalidPreviousHash { block_index } => {157                write!(158                    formatter,159                    "block {block_index} does not link to its predecessor"160                )161            }162            Self::InvalidBlockHash { block_index } => {163                write!(164                    formatter,165                    "block {block_index} has an incorrect stored hash"166                )167            }168            Self::InsufficientDifficulty { block_index } => write!(169                formatter,170                "block {block_index} does not meet the configured difficulty"171            ),172        }173    }174}175176impl Error for ChainError {}177178impl Blockchain {179    /// Create a chain and mine its genesis block at the requested difficulty.180    /// Difficulty counts leading zero hexadecimal digits (0 through 64).181    ///182    /// # Errors183    ///184    /// Returns [`ChainError::InvalidDifficulty`] when the difficulty exceeds 64.185    pub fn new(difficulty: u8) -> Result<Self, ChainError> {186        if difficulty > 64 {187            return Err(ChainError::InvalidDifficulty(difficulty));188        }189190        let (genesis, _) = Block::mine(191            0,192            [0; 32],193            vec![Transaction::new("network", "genesis", 1)],194            difficulty,195        );196        Ok(Self {197            difficulty,198            blocks: vec![genesis],199        })200    }201202    /// The number of leading zero hexadecimal digits required in each hash.203    #[must_use]204    pub const fn difficulty(&self) -> u8 {205        self.difficulty206    }207208    /// Return the chain's blocks in order, from genesis to tip.209    #[must_use]210    pub fn blocks(&self) -> &[Block] {211        &self.blocks212    }213214    /// Mine and append a block after checking its transactions.215    ///216    /// # Errors217    ///218    /// Returns [`ChainError::InvalidTransaction`] if any transaction has an219    /// empty party name or a zero amount.220    ///221    /// # Panics222    ///223    /// Panics only if the in-memory chain exceeds `u64::MAX` blocks or all224    /// `u64` nonce values are exhausted without finding proof-of-work.225    pub fn mine_block(226        &mut self,227        transactions: Vec<Transaction>,228    ) -> Result<MiningSummary, ChainError> {229        let next_index = u64::try_from(self.blocks.len()).expect("block count exceeds u64");230        validate_transactions(next_index, &transactions)?;231232        let previous_hash = self.blocks.last().expect("genesis block exists").hash;233        let (block, attempts) =234            Block::mine(next_index, previous_hash, transactions, self.difficulty);235        let summary = MiningSummary {236            block_index: block.index,237            nonce: block.nonce,238            hash: block.hash,239            attempts,240        };241        self.blocks.push(block);242        Ok(summary)243    }244245    /// Check transaction structure, sequential indices, hash links, stored246    /// digests, and proof-of-work for every block.247    ///248    /// # Errors249    ///250    /// Returns the first structural, link, hash, transaction, or proof-of-work251    /// error found in the chain.252    ///253    /// # Panics254    ///255    /// Panics only if the in-memory chain exceeds `u64::MAX` blocks.256    pub fn validate(&self) -> Result<(), ChainError> {257        if self.blocks.is_empty() {258            return Err(ChainError::EmptyChain);259        }260261        for (position, block) in self.blocks.iter().enumerate() {262            let expected_index = u64::try_from(position).expect("block count exceeds u64");263            if block.index != expected_index {264                return Err(ChainError::InvalidIndex {265                    expected: expected_index,266                    actual: block.index,267                });268            }269            validate_transactions(block.index, &block.transactions)?;270271            let expected_previous_hash = if position == 0 {272                [0; 32]273            } else {274                self.blocks[position - 1].hash275            };276            if block.previous_hash != expected_previous_hash {277                return Err(ChainError::InvalidPreviousHash {278                    block_index: block.index,279                });280            }281            if block.hash != block.calculate_hash() {282                return Err(ChainError::InvalidBlockHash {283                    block_index: block.index,284                });285            }286            if !meets_difficulty(&block.hash, self.difficulty) {287                return Err(ChainError::InsufficientDifficulty {288                    block_index: block.index,289                });290            }291        }292        Ok(())293    }294}295296fn validate_transactions(index: u64, transactions: &[Transaction]) -> Result<(), ChainError> {297    for (transaction_index, transaction) in transactions.iter().enumerate() {298        if !transaction.is_valid() {299            return Err(ChainError::InvalidTransaction {300                block_index: index,301                transaction_index,302            });303        }304    }305    Ok(())306}307308fn update_field(hasher: &mut Sha256, bytes: &[u8]) {309    // A decimal byte length and delimiter make each variable-sized field310    // unambiguous without relying on a platform-dependent integer width.311    hasher.update(bytes.len().to_string().as_bytes());312    hasher.update(b":");313    hasher.update(bytes);314}315316fn meets_difficulty(hash: &Hash, difficulty: u8) -> bool {317    let whole_zero_bytes = usize::from(difficulty / 2);318    hash[..whole_zero_bytes].iter().all(|byte| *byte == 0)319        && (difficulty.is_multiple_of(2) || hash[whole_zero_bytes] < 0x10)320}321322/// Render a hash as lowercase hexadecimal.323#[must_use]324pub fn hash_hex(hash: &Hash) -> String {325    const HEX: &[u8; 16] = b"0123456789abcdef";326    let mut rendered = String::with_capacity(hash.len() * 2);327    for byte in hash {328        rendered.push(char::from(HEX[usize::from(byte >> 4)]));329        rendered.push(char::from(HEX[usize::from(byte & 0x0f)]));330    }331    rendered332}333334#[cfg(test)]335mod tests {336    use super::{Blockchain, ChainError, Hash, Transaction, hash_hex};337338    #[test]339    fn hash_hex_is_deterministic() {340        let known: Hash = [0xab; 32];341        assert_eq!(hash_hex(&known), "ab".repeat(32));342    }343344    #[test]345    fn block_hash_and_mining_are_deterministic_at_zero_difficulty() {346        let mut first = Blockchain::new(0).expect("valid difficulty");347        let mut second = Blockchain::new(0).expect("valid difficulty");348        let transaction = vec![Transaction::new("alice", "bob", 7)];349350        let first_summary = first351            .mine_block(transaction.clone())352            .expect("valid transaction");353        let second_summary = second.mine_block(transaction).expect("valid transaction");354355        assert_eq!(first_summary.hash, second_summary.hash);356        assert_eq!(357            hash_hex(&first_summary.hash),358            "25f281f9693fd587f4cad1bc91c7344fb2c6b9960cb2be122cda2c08d6f027ca"359        );360        assert_eq!(first_summary.nonce, 0);361        assert_eq!(first_summary.attempts, 1);362        assert_eq!(first.blocks()[1].hash, first.blocks()[1].calculate_hash());363        assert_eq!(first.validate(), Ok(()));364    }365366    #[test]367    fn rejects_invalid_difficulty_and_transactions() {368        assert_eq!(369            Blockchain::new(65).err(),370            Some(ChainError::InvalidDifficulty(65))371        );372373        let mut chain = Blockchain::new(0).expect("valid difficulty");374        let error = chain375            .mine_block(vec![Transaction::new("alice", " ", 7)])376            .expect_err("blank recipient must fail");377        assert_eq!(378            error,379            ChainError::InvalidTransaction {380                block_index: 1,381                transaction_index: 0,382            }383        );384        assert_eq!(chain.blocks().len(), 1);385    }386387    #[test]388    fn validates_links_hashes_and_configured_difficulty() {389        let mut chain = Blockchain::new(1).expect("valid difficulty");390        chain391            .mine_block(vec![Transaction::new("alice", "bob", 3)])392            .expect("mine a block");393        chain.validate().expect("mined chain is valid");394395        let mut tampered = chain.clone();396        tampered.blocks[1].transactions[0].amount += 1;397        assert_eq!(398            tampered.validate(),399            Err(ChainError::InvalidBlockHash { block_index: 1 })400        );401402        let mut broken_link = chain.clone();403        broken_link.blocks[1].previous_hash = [0; 32];404        broken_link.blocks[1].hash = broken_link.blocks[1].calculate_hash();405        assert_eq!(406            broken_link.validate(),407            Err(ChainError::InvalidPreviousHash { block_index: 1 })408        );409    }410411    #[test]412    fn rejects_a_rehashed_block_without_sufficient_work() {413        let mut chain = Blockchain::new(1).expect("valid difficulty");414        chain415            .mine_block(vec![Transaction::new("alice", "bob", 3)])416            .expect("mine a block");417418        let block = &mut chain.blocks[1];419        while super::meets_difficulty(&block.hash, chain.difficulty) {420            block.nonce += 1;421            block.hash = block.calculate_hash();422        }423424        assert_eq!(425            chain.validate(),426            Err(ChainError::InsufficientDifficulty { block_index: 1 })427        );428    }429}