paint-brush
Building A Blockchain in Rust & Substrate: [A Step-by-Step Guide for Developers]by@nicolezhu
19,086 reads
19,086 reads

Building A Blockchain in Rust & Substrate: [A Step-by-Step Guide for Developers]

by NicoleZhuJune 17th, 2020
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Building a Bitcoin-like blockchain in Rust & Substrate: [A Step-by-Step Guide for Developers] "A Step by-step Guide" is a self-guided tutorial on how to build a gas-less, Bitcoin-style blockchain from scratch. You'll learn that a blockchain is a lot more powerful than just smart contracts. We'll learn how to implement the UTXO ledger model, Bitcoin’s accounting mechanism, and how to change the network transaction pool logic. We’ll use this time now for a crash course how Bitcoin works and explore this developer SDK that we're using.

Companies Mentioned

Mention Thumbnail
Mention Thumbnail

Coins Mentioned

Mention Thumbnail
Mention Thumbnail
featured image - Building A Blockchain in Rust & Substrate: [A Step-by-Step Guide for Developers]
NicoleZhu HackerNoon profile picture

A beginner-friendly tutorial on how to build hardcore blockchain infrastructure in Substrate, an open source framework.

In this self-guided tutorial, you’ll build a gas-less, Bitcoin-like blockchain from scratch. You'll learn that a blockchain is a lot more powerful than just smart contracts.

Feel free to repurpose any of this content to host your own workshops!

What you will learn: 

  • Implement the UTXO ledger model, Bitcoin’s accounting mechanism
  • Change the network transaction pool logic
  • Configure a genesis block & write some tests
  • Deploy your chain & interact with the live node using a web client

Requirements:

  • NO blockchain & Rust knowledge needed
  • Basic programming experience
  • Estimated time: 3 hours

For a more detailed walkthrough where I thoroughly explain why we’re doing each step, and where we take time to discuss Rust traits, check out this video tutorial accompaniment: 

Let’s get started!

Installation

1. Get the latest stable version of Rust & WebAssembly tools. In your terminal, run the commands:

# On Windows, download and run rustup-init.exe from https://rustup.rs instead

# On Macs:
curl https://sh.rustup.rs -sSf | sh
rustup update nightly
rustup target add wasm32-unknown-unknown —toolchain nightly
rustup update stable
cargo install —git https://github.com/alexcrichton/wasm-gc

If you counter any issues or use a different OS , check out this detailed setup guide.

2. In a new terminal, also clone your copy of this tutorial's boilerplate code: 

git clone https://github.com/substrate-developer-hub/utxo-workshop.git
git fetch origin workshop:workshop
git checkout workshop
# [Optional] Once step 1 installations are completed
# Run the following commands to shorten future build time
cd /project_base_directory
cargo test -p utxo-runtime

This repo also contains an updated & complete Bitcoin implementation in the

master
branch (as a cheat), so make sure you check out the
workshop
branch to start from scratch!

Depending on your CPU, 1st-time Rust installations can take up to 10-20 minutes.

Let’s use this time now for a crash course how Bitcoin works, as well as explore this developer SDK that we're using!

Quick Primer on the UTXO ledger model

If you own a bank account, you’re already familiar with the “accounts based” ledger model. This is where your bank account has a total balance that gets credited or debited per transaction. 

Bitcoin offers a fundamentally different ledger model called UTXO, or Unspent Transaction Outputs. 

UTXO works like travellers checks in that: 

  1. Whoever physically has the check can spend the money. In other words, the spending permission is tied to the money, not an account number. 
  2. You can’t rip up a check and spend its parts. You have to spend the entire check, and receive any change in a new check. 

In the following example, Bob has a UTXO worth $50. He wants to give Alice $0.5, so he destroys his $50 UTXOs, and creates two new UTXOs of values $0.5 (for Alice) and $49.5 (as change). 

Image source: https://freedomnode.com/

Cryptography is the underlying mechanism that allows only Bob, and not anyone else, to spend his UTXOs. 

This information is stored in one of each UTXO’s 3 fields:

  1. A reference hash of where the UTXO exists, sort of like an address pointer in a database
  2. The monetary value of the UTXO, e.g. $50
  3. The public key of its “owner”

The public key corresponds with a secret “private key”, that only the owner would have. So to spend the UTXO, the owner has to cryptographically "sign over" a transaction with his corresponding private key. The signature can be later checked against the "public key" to verify its validity.

For example, when Alice spends her UTXO, it would look like this: 

She creates a new transaction (gray background), supplies her UTXO as input to be spent, and in the

sigscript
field, Alice provides her signature.

Note: Alice is "signing over" the details of the entire transaction. This has the benefit of locking in the transaction output details, to prevent network level tampering. Later on, the blockchain will verify that Alice did indeed authorise all of the details of this entire transaction.

We’ll cover the security implications in greater detail in Part 2, when you secure your blockchain against malicious attacks.

Quick Primer on Substrate Framework

You're using an open-source blockchain framework called Substrate. Substrate is Rust based and compiles to a binary instruction format called WebAssembly (WAsm).

Out of the box, you get core blockchain components like a distributed database, a peer-to-peer networking layer, and various consensus mechanisms we can choose from.

In this tutorial, we’ll get very familiar with the transaction queue and runtime module layers

Let's start coding!

Part 1: Build the logic layer of the blockchain

1. In terminal, do a quick Rust compiler check to ensure everything downloaded correctly:

cargo check -p utxo-runtime
# Don’t worry if this takes a while, just let it run!
# You should see a few warnings but no breaking errors

2. Open up the project in your favourite Rust compatible IDE. I recommend IntelliJ or VSCode for their Rust syntax highlighting.

3. Open the

Runtime
subdirectory, which houses the blockchain runtime. Then, open up
utxo.rs
file, which is where you’ll build most of your Bitcoin UTXO logic.

You’ll see a typical Substrate starter template, with inline comments that explain how to use the SDK. Further down, you should also see where you can write unit tests. 

4. Right after dependency import lines, create the data structures needed to represent UTXOs and a UTXO transaction.

/// Single transaction to be dispatched
#[cfg_attr(feature = "std", derive(Serialize, Deserialize))]
#[derive(PartialEq, Eq, PartialOrd, Ord, Default, Clone, Encode, Decode, Hash, Debug)]
pub struct Transaction {
    /// UTXOs to be used as inputs for current transaction
    pub inputs: Vec<TransactionInput>,
    
    /// UTXOs to be created as a result of current transaction dispatch
    pub outputs: Vec<TransactionOutput>,
}

/// Single transaction input that refers to one UTXO
#[cfg_attr(feature = "std", derive(Serialize, Deserialize))]
#[derive(PartialEq, Eq, PartialOrd, Ord, Default, Clone, Encode, Decode, Hash, Debug)]
pub struct TransactionInput {
    /// Reference to an UTXO to be spent
    pub outpoint: H256,
    
    /// Proof that transaction owner is authorized to spend referred UTXO & 
    /// that the entire transaction is untampered
    pub sigscript: H512,
}

/// Single transaction output to create upon transaction dispatch
#[cfg_attr(feature = "std", derive(Serialize, Deserialize))]
#[derive(PartialEq, Eq, PartialOrd, Ord, Default, Clone, Encode, Decode, Hash, Debug)]
pub struct TransactionOutput {
    /// Value associated with this output
    pub value: Value,

    /// Public key associated with this output. In order to spend this output
	/// owner must provide a proof by hashing the whole `Transaction` and
	/// signing it with a corresponding private key.
    pub pubkey: H256,
}

For a more detailed walkthrough & line-by-line explanation of the above, check out this video accompaniment

5. Designate what gets stored on the blockchain chain-state. This is done inside a Rust macro called

decl_storage
. You'll be storing a hashmap of 256bit pointers to UTXOs as the key, and the UTXO struct itself as the value. Implement the following: 

decl_storage! {
    trait Store for Module<T: Trait> as Utxo {
        /// All valid unspent transaction outputs are stored in this map.
        /// Initial set of UTXO is populated from the list stored in genesis.
        UtxoStore build(|config: &GenesisConfig| {
            config.genesis_utxos
                .iter()
                .cloned()
                .map(|u| (BlakeTwo256::hash_of(&u), u))
                .collect::<Vec<_>>()
        }): map H256 => Option<TransactionOutput>;

        /// Total reward value to be redistributed among authorities.
        /// It is accumulated from transactions during block execution
        /// and then dispersed to validators on block finalization.
        pub RewardTotal get(reward_total): Value;
    }

    add_extra_genesis {
        config(genesis_utxos): Vec<TransactionOutput>;
    }
}

Notice, in addition to configuring storage, we also configured how* this storage will be populated at the genesis block. At block 0, you will be able to seed your blockchain with an existing vector of UTXOs to spend!

6. Create the transaction signatures that will allow users of your Bitcoin blockchain to spend UTXOs. Let's implement the

spend
function:

// External functions: callable by the end user
decl_module! {
    pub struct Module<T: Trait> for enum Call where origin: T::Origin {
        fn deposit_event() = default;

        /// Dispatch a single transaction and update UTXO set accordingly
        pub fn spend(_origin, transaction: Transaction) -> DispatchResult {
                                    // TransactionValidity{}
            let transaction_validity = Self::validate_transaction(&transaction)?;
            
            Self::update_storage(&transaction, transaction_validity.priority as u128)?;

            Self::deposit_event(Event::TransactionSuccess(transaction));

            Ok(())
        }
}

Note, we'll be implementing a few helper functions for this spend transaction logic shortly.

7. Blockchains can also emit events whenever there are on-chain transactions. Set up your blockchain to recognize a

TransactionSuccess
event type.

decl_event!(
    pub enum Event {
        /// Transaction was executed successfully
        TransactionSuccess(Transaction),
    }
);

Note, in step 2, you are already emitting this event after every successful spend transaction.

For a more line-by-line explanation of the above, check out this video accompaniment

Part 2: Secure the chain against malicious attacks

In Part 1, we scaffolded the basic building of UTXOs. In this section, we’ll get into the cryptographic security of our chain and implement UTXO transaction logic.

In fact, there are many vulnerabilities that the Bitcoin blockchain defends against.

  • Inputs and outputs are not empty
  • Each input exists and is used exactly once
  • Each output is defined exactly once and has nonzero value
  • Total output value must not exceed total input value
  • New outputs do not collide with existing ones
  • Replay attacks are not possible
  • Provided input signatures are valid
  • The input UTXO is indeed signed by the owner
  • Transactions are tamperproof 

1. Let's now implement the

validate_transaction
function to ensure these security checks. 

// "Internal" functions, callable by code.
impl<T: Trait> Module<T> {
    pub fn validate_transaction(transaction: &Transaction) -> Result<ValidTransaction, &'static str> {
        // Check basic requirements
        ensure!(!transaction.inputs.is_empty(), "no inputs");
        ensure!(!transaction.outputs.is_empty(), "no outputs");

        {
            let input_set: BTreeMap<_, ()> =transaction.inputs.iter().map(|input| (input, ())).collect();
            ensure!(input_set.len() == transaction.inputs.len(), "each input must only be used once");
        }
        {
            let output_set: BTreeMap<_, ()> = transaction.outputs.iter().map(|output| (output, ())).collect();
            ensure!(output_set.len() == transaction.outputs.len(), "each output must be defined only once");
        }

        let mut total_input: Value = 0;
        let mut total_output: Value = 0;
        let mut output_index: u64 = 0;
        let simple_transaction = Self::get_simple_transaction(transaction);

        // Variables sent to transaction pool
        let mut missing_utxos = Vec::new();
        let mut new_utxos = Vec::new();
        let mut reward = 0;

        // Check that inputs are valid
        for input in transaction.inputs.iter() {
            if let Some(input_utxo) = <UtxoStore>::get(&input.outpoint) {
                ensure!(sp_io::crypto::sr25519_verify(
                    &Signature::from_raw(*input.sigscript.as_fixed_bytes()),
                    &simple_transaction,
                    &Public::from_h256(input_utxo.pubkey)
                ), "signature must be valid" );
                total_input = total_input.checked_add(input_utxo.value).ok_or("input value overflow")?;
            } else {
                missing_utxos.push(input.outpoint.clone().as_fixed_bytes().to_vec());
            }
        }

        // Check that outputs are valid
        for output in transaction.outputs.iter() {
            ensure!(output.value > 0, "output value must be nonzero");
            let hash = BlakeTwo256::hash_of(&(&transaction.encode(), output_index));
            output_index = output_index.checked_add(1).ok_or("output index overflow")?;
            ensure!(!<UtxoStore>::exists(hash), "output already exists");
            total_output = total_output.checked_add(output.value).ok_or("output value overflow")?;
            new_utxos.push(hash.as_fixed_bytes().to_vec());
        }
        
        // If no race condition, check the math
        if missing_utxos.is_empty() {
            ensure!( total_input >= total_output, "output value must not exceed input value");
            reward = total_input.checked_sub(total_output).ok_or("reward underflow")?;
        }

        // Returns transaction details
        Ok(ValidTransaction {
            requires: missing_utxos,
            provides: new_utxos,
            priority: reward as u64,
            longevity: TransactionLongevity::max_value(),
            propagate: true,
        })
    }
}

Oof that's a lot. To get a line by line explanation of what's going on, check out part 2 of the video accompaniment.

2. In part 1, we assumed the use of a few internal helper functions. Namely the step where we actually update the blockchain storage, when our transactions are validated. In the same

impl<T: Trait> Module<T>
scope, do the following:

/// Update storage to reflect changes made by transaction
    /// Where each utxo key is a hash of the entire transaction and its order in the TransactionOutputs vector
    fn update_storage(transaction: &Transaction, reward: Value) -> DispatchResult {
        // Calculate new reward total
        let new_total = <RewardTotal>::get()
            .checked_add(reward)
            .ok_or("Reward overflow")?;
        <RewardTotal>::put(new_total);

        // Removing spent UTXOs
        for input in &transaction.inputs {
            <UtxoStore>::remove(input.outpoint);
        }

        let mut index: u64 = 0;
        for output in &transaction.outputs {
            let hash = BlakeTwo256::hash_of(&(&transaction.encode(), index));
            index = index.checked_add(1).ok_or("output index overflow")?;
            <UtxoStore>::insert(hash, output);
        }

        Ok(())
    }

As well as

get_simple_transaction
:

    // Strips a transaction of its Signature fields by replacing value with ZERO-initialized fixed hash.
    pub fn get_simple_transaction(transaction: &Transaction) -> Vec<u8> {//&'a [u8] {
        let mut trx = transaction.clone();
        for input in trx.inputs.iter_mut() {
            input.sigscript = H512::zero();
        }

        trx.encode()
    }

Part 3: Test your code

In this short part, you'll learn how to construct a blockchain testing environment, build some initial state prior to each test, as well as use some handy helper functions that are available for testing in Substrate/Rust. 

1. Construct your test environment:

// This function basically just builds a genesis storage key/value store according to our desired mockup.
    // We start each test by giving Alice 100 utxo to start with.
    fn new_test_ext() -> sp_io::TestExternalities {
    
        let keystore = KeyStore::new(); // a key storage to store new key pairs during testing
        let alice_pub_key = keystore.write().sr25519_generate_new(SR25519, Some(ALICE_PHRASE)).unwrap();

        let mut t = system::GenesisConfig::default()
            .build_storage::<Test>()
            .unwrap();

        t.top.extend(
            GenesisConfig {
                genesis_utxos: vec![
                    TransactionOutput {
                        value: 100,
                        pubkey: H256::from(alice_pub_key),
                    }
                ],
                ..Default::default()
            }
            .build_storage()
            .unwrap()
            .top,
        );
        
        // Print the values to get GENESIS_UTXO
        let mut ext = sp_io::TestExternalities::from(t);
        ext.register_extension(KeystoreExt(keystore));
        ext
    }

This function builds a genesis storage key/value store according to the code we wrote back in step 1 during

decl_storage
. We simply start each test by giving Alice a UTXO of value 100 to start spending.

2. Write a simple unit test, testing a simple transaction

    #[test]
    fn test_simple_transaction() {
        new_test_ext().execute_with(|| {
            let alice_pub_key = sp_io::crypto::sr25519_public_keys(SR25519)[0];

            // Alice wants to send herself a new utxo of value 50.
            let mut transaction = Transaction {
                inputs: vec![TransactionInput {
                    outpoint: H256::from(GENESIS_UTXO),
                    sigscript: H512::zero(),
                }],
                outputs: vec![TransactionOutput {
                    value: 50,
                    pubkey: H256::from(alice_pub_key),
                }],
            };
            
            let alice_signature = sp_io::crypto::sr25519_sign(SR25519, &alice_pub_key, &transaction.encode()).unwrap();
            transaction.inputs[0].sigscript = H512::from(alice_signature);
            let new_utxo_hash = BlakeTwo256::hash_of(&(&transaction.encode(), 0 as u64)); 
            
            assert_ok!(Utxo::spend(Origin::signed(0), transaction));
            assert!(!UtxoStore::exists(H256::from(GENESIS_UTXO)));
            assert!(UtxoStore::exists(new_utxo_hash));
            assert_eq!(50, UtxoStore::get(new_utxo_hash).unwrap().value);
        });
    }

3. Don't forget the handy constants!

    // need to manually import this crate since its no include by default
    use hex_literal::hex;

    const ALICE_PHRASE: &str = "news slush supreme milk chapter athlete soap sausage put clutch what kitten";
    const GENESIS_UTXO: [u8; 32] = hex!("79eabcbd5ef6e958c6a7851b36da07691c19bda1835a08f875aa286911800999");
    

4. Run your test in the console with

cargo test -p utxo-runtime

And your test should pass, meaning your basic UTXO blockchain is done!

Stuck at this point? Check out this repo for what your current implementation might look like.

Part 4: Configure transaction pool logic

In this section, you’ll change how your network prioritizes incoming transactions & handles an annoying UTXO race condition that Bitcoin experiences. Specifically, you'll learn how to change the blockchain transaction queueing logic without much code.

Consider the following race condition, where Alice sends Bob her UTXO A, creating a new UTXO B belonging to Bob.

What’s happening behind the scenes is that Alice's transaction starts propagating across the nodes in the network:

Immediately, Bob decides to spend this UTXO B, creating a UTXO C.

Thus his transaction starts to propagate across the network to nodes that haven’t heard from Alice yet! This can be common, due to regular network latency and other real world constraints.

Nodes that heard from Bob but not from Alice yet, will reject his transaction since UTXO B doesn’t yet exist in their blockchain state. But Bob’s transaction IS valid, so this error due to this race condition is not ideal.

Ideally, we can queue up valid transactions a network pool and wait until prerequisite conditions are satisfied.

1. Luckily Substrate enables a single API call for you to change transaction ordering logic. Configure the

runtime_api::TaggedTransactionQueue
trait as follows:

    impl sp_transaction_pool::runtime_api::TaggedTransactionQueue<Block> for Runtime {
        fn validate_transaction(tx: <Block as BlockT>::Extrinsic) -> TransactionValidity {            
            // Extrinsics representing UTXO transaction need some special handling
            if let Some(&utxo::Call::spend(ref transaction)) = IsSubType::<utxo::Module<Runtime>, Runtime>::is_sub_type(&tx.function) {
                match <utxo::Module<Runtime>>::validate_transaction(&transaction) {
                    // Transaction verification failed
                    Err(e) => {
                        sp_runtime::print(e);
                        return Err(TransactionValidityError::Invalid(InvalidTransaction::Custom(1)));
                    }
                    // Race condition, or Transaction is good to go
                    Ok(tv) => { return Ok(tv); }
                }                
            }

            // Fall back to default logic for non UTXO::execute extrinsics
            Executive::validate_transaction(tx)
        }
    }

Effectively, we're telling the transaction queue to wait for the hash of a required UTXO to exist, before processing a new transaction that spends this UTXO. The transaction pool will hold on to race-UTXOs until this condition is satisfied for a certain period of time.

For a detailed explanation of what's happening, check out part 4 of the video accompaniment.

Part 5: Final touches & deploy!

In this final section we’re ready to configure our blockchain deployment specifications, designate what gets included in genesis block, and deploy!

1. Step into the

src
subdirectory now, and find the
chain_spec.rs
file. 

2. In

testnet_genesis
function, append the following configuration to set-up your testnet with seed data / UTXOs.

// Dev mode genesis setup
fn testnet_genesis(
    initial_authorities: Vec<(AuraId, GrandpaId)>,
    root_key: AccountId,
    endowed_accounts: Vec<AccountId>,
    endowed_utxos: Vec<sr25519::Public>,
    _enable_println: bool) -> GenesisConfig 
{
    GenesisConfig {
      system: Some(SystemConfig {
        code: WASM_BINARY.to_vec(),
        changes_trie_config: Default::default(),
      }),
      ...
      utxo: Some(utxo::GenesisConfig {
        genesis_utxos: endowed_utxos
                      .iter()
                      .map(|x|
                        utxo::TransactionOutput {
                          value: 100 as utxo::Value,
                          pubkey: H256::from_slice(x.as_slice()),
                      })
                      .collect()
      }),
    }
}

3. In

fn load
, make sure to also include the genesis set of public keys that should own these UTXOs.

// Genesis set of pubkeys that own UTXOs
                vec![
                    get_from_seed::<sr25519::Public>("Alice"),
                    get_from_seed::<sr25519::Public>("Bob"),
                ],

4. In your terminal, compile and build a release of your blockchain in developer mode:

# Initialize your Wasm Build environment:
./scripts/init.sh

# Build Wasm and native code:
cargo build --release

5. Start your node and your blockchain will start producing blocks:

./target/release/utxo-workshop --dev

# If you already modified state, run this to purge the chain
./target/release/utxo-workshop purge-chain --dev

For a more detailed walkthrough & line-by-line explanation of the above, check out this final part of the video accompaniment. 

Congratulations! You’ve now built and deployed a Bitcoin-like blockchain from scratch.

Quick UI Demo

In this tutorial, you learned how to change the underlying ledger model and built a Bitcoin chain on Substrate. In fact, you can implement any fundamental token model on your chain. You can change how your network prioritizes various transactions i.e. manipulate the networking layer without much code. You can even change validator economics structures by using leftover values to reward your validators. You can easily configure your genesis block.

Hopefully this tutorial convinced you to give building blockchain infrastructures a try and to check out Substrate!

Questions?

  • Ping us on Riot chat: https://riot.im/app/#/room/#substrate-technical:matrix.org
  • DM me on Twitter: https://twitter.com/nczhu