Rusty Chains: A Basic Blockchain Implementation Written in Pure Rust

What is inside the story?

In this article, I will take you a bit along my journey into blockchain. The next project at my work will be fueled by blockchain technology. Since I had (have) no real idea about that topic apart from some general high level ideas, I started to grind for information on the topic and finally decided that the best way to overcome the level of just repeating buzzwords and to get an actual level of understanding is to get the hands dirty: Implementing the thing from scratch.

Not everything which would be needed to deploy your own public blockchain, but a working part of the base technology which already resembles a fully functional (local) blockchain. We will use the rather new programming language Rust to do so. Since the language does not have a huge user base like Java, C++ or Python, that module will be very detailed in the implementation part by not only showcasing the code but explaining its ideas and syntax.

There is a lot to cover. When following up, you will have a natural understanding of blockchains by creating an extensible blockchain prototype and learn some usable basics in Rust. Who knows what that might be good for in the future? But don’t worry, I will try to guide you step by step through the whole thing instead of just dropping code snippets.

Prerequisites

Fast Track 🏃

• Repository:
• Github homepage:
• Code documentation (cargo doc): In  
• Code Description: Chapter “Implementation PART I”
• Using the module / showcase: Chapter “Usage example”

Fundamentals

What is a Blockchain? 

First things first: let us talk a little bit about the blockchain itself (no really: first get yourself a coffee or tea ☕ we have work to do). If we want to talk about blockchains, we first should talk about Distributed Ledgers. You have probably heard this term in the same breath as blockchain.

Maybe you have come around the peer-to-peer filesharing protocol BitTorrent[2]. This protocol enables filesharing in a decentralized manner. Normally, when downloading a file from somewhere over the internet, you will send a request to a specific server which stores the whole file and transmits the data to your device. This is classical client server architecture. BitTorrent however will share a single file across multiple actors / peers at the same time. If you download a file from the Torrent network, you effectively will download it from multiple sources and eventually becoming a source yourself by participating in the network.

Distributed ledgers share some common characteristics. The data (i.e., the ledger) - which generally is not just a simple file but rather a kind of database or really whatever you want it to be - is distributed across multiple actors / peers. There is no single authority in charge for keeping, modifying or distributing that ledger. Rather, all the connected peers keep a copy of the very same ledger.

How authentication is managed? What about network latency? That’s a lot of complicated tech to cover. All those questions need some form of consensus which all participating peers agree on. Consensus is a rather long topic on its own. There are different types of consensus algorithms suiting different use cases[3] all having their own advantages and disadvantages.

In this article we will implement a sort of a Proof of Work variant, which is used in known public blockchains like Ethereum (might switch to Proof of Stake in future versions) or Bitcoin. We will come back on that in Chapter II of the writeup.

Having that said, what is the connection between distributed ledgers and blockchains? To be honest: Taxonomy wise — it’s not that simple[4]:

The term blockchain is an ill-defined buzzword

The blockchain itself is just a special kind of ledger

It is a special kind of ledger which remembers all states-transitions it ever went through. Imagine having a regular database, where every change / transaction you commit will be recorded such that the final state of the database can always be obtained by executing all the recorded transactions in order. The final state in the context of blockchains is referred as World State.

Since this state does not contain the whole history of transactions, it is typically much smaller than the actual blockchain. However, it is not strictly necessary to store the world state since it always could be retrieved by replaying all transactions. This chain of ordered transactions is secured in a way that it is impossible to change any intermediate transaction (previous chain parts) without breaking the whole thing apart. This is often referred as immutable state.

But why is it that people talk about blockchains when they are talking about concrete realizations like Bitcoin or Ethereum? Well, the blockchain itself is a part of all of them. I would rather refer to them as Blockchain Frameworks and Blockchain Ecosystems. 

The common understanding of blockchain actually refers to blockchain frameworks and blockchain ecosystems

Marketing decided that this is the same, but keep in mind: it really isn’t. Blockchain Frameworks and Ecosystems typically offer a lot of technology and software, mostly together with a couple of of additional components offering different sets of features, possibly also with an existing user base / network. There are a lot of blockchain frameworks in the wild, which may or may not be compatible to another.

Next to the already mentioned Ethereum and Bitcoin, there are prominent representatives like Hyperledger Fabric, Hyperledger Besu, Substrate, Quora or Corda just to name a view; all having different features and use cases / audiences[5].

What we need blockchains for? (Use Cases)

This question is not so easy to answer and might also be somewhat opinionated. Blockchain Frameworks can be categorized into at least two different flavors: public blockchains and private blockchains. Those are not fundamentally different, but their components and use cases differ.

Public blockchains are basically accessible by anyone. People can join and participate if they speak the same language, i.e., following the same protocols (having the same consensus). Therefore, there exists a multitude of clients for specific blockchains.

Ethereum has more than 10 active projects listed[6] which are implemented in all sorts of programming languages including in Rust (Parity Ethereum).

They are unique and steady. Changes are not opaque anymore. And here is the important takeaway: there is no need for any participant to trust in anybody. Everyone is watching. It is almost impossible to manipulate the system since it doesn’t depend only on a single actor.

That also means, you cannot DDoS[7] the network. Those attack vectors just disappear. Security comes by design.

What might smart and creative people come up with using blockchain tech in the future?

Private Blockchains are basically not different from public blockchains. They use the same technology but come with additional features, which are not common in public chains. Private blockchains are not meant to be joined by anyone but a regulated audience. Those could be different organizations which are sharing some joint workflows, possessions or values.

To enable a collaboration like that, frameworks also needs features like authentication, authorization, permissioning (user roles), rights management, deployment, networking, monitoring and so forth. But why should anyone want to deal with such complicated technology just to share a chain of transactions and data between some limited companies?

Well, the audience seems way smaller. Remember the shared state which all the participants store and the consensus which the participants agree on? There is no central authority which you just have to trust. No one can just manipulate data. There are no two valid realities existing at a time. Also, since every party stores at least one copy of the ledger, there is no risk on loosing access to the data. If you share some interest with someone else but you cannot absolutely trust on the integrity of the company, private blockchains may have you covered.

Implementing The Blockchain - PART I

This section will start on implementing the blockchain itself. We will define the project layout including the basic data structures which constitute the blockchain. Those will serve as a skeleton for all the implementations that are necessary later. Please note that I am by no means a Rust (or blockchain) expert. In fact, this is my first Rust project.

The structure of the project

We will go with a very simple folder structure, which basically consists of only three files. A main file (main.rs) which will contain the code that will invoke the blockchain and does some sample operations to demonstrate the functionality. Another file which will be inside a subdirectory will contain our actual blockchain data structures and implementations.

The last file will be the cargo.toml file which will hold the external dependencies of the project together with some project meta data. The structure will be as follows:

/rchain
 |-- src
 |---- rchain
 |------ mod.rs
 |-- main.rs
 |-- cargo.toml

The cargo.toml comes with only one dependency at the moment which will be a hashing-library (Blake2 [10]) and looks like that:

[package]
name = "rchain_v1"
version = "0.1.0"
authors = ["Richard Vogel <[email protected]>"]
edition = "2018"
 
# See more keys and their definitions at //doc.rust-lang.org/cargo/reference/manifest.html
 
[dependencies]
blake2 = "*"

The first time you run cargo build within the directory to build the project and create executables, cargo will download and compile the dependencies for your architecture. That is a great step from complicated dependency management in C(++): it is similar to what pip for Python is doing. At the time of writing there are over 44,000 so called crates in the index[11].

The

rchain

__init__.py

The Blockchain module

Let’s go into the details of the implementation itself. We start with a UML class diagram to illustrate how everything falls together within the module (although Rust doesn’t have explicit classes). Refer to this graphic to this place when you feel you got lost in all the details.

Some details are a bit simplified or omitted in order to keep the diagram reasonable. We will walk through each of the components step by step. The code itself will be heavily commented and documented. Please read the code snippets which I provide here (also read the code in the repository to get the full picture), even if you do not understand every small detail of the syntax.

Rust can be a bit hard on newcomers, especially if you come from a high-level language like JavaScript or Python. I will explain some of the more peculiar Rusty syntax within the article. If you have little to no coding experience and just want to know how blockchains work: still read the code comments!

The first part will focus on the data structures itself (i.e., what purpose they serve and what data they contain). The second part will focus on some of the more important implementations (i.e., functions and methods). The third part will finally demonstrate a simple usage of the

Blockchain

Data structures

Blockchain

The definition of the

Blockchain

Rust does not have a class keyword. This doesn’t mean rust is not supporting class-like project structures. We will use structs instead, which feature a lot of what classes in other languages can do

Obviously, the struct stores a list of Blocks which we will define in detail later. Also, there is a Map / Dictionary of Accounts stored, which keeps track of the current final state of the blockchain. The mapping of that map is User Id to Account. For now, the User Id is arbitrary, in the next article those keys will be used to represent the public key of the account.

Our blockchains world state is completely represented by this Map. Finally. pending_transactions will be used for bookkeeping of ready but not yet executed transactions. We will not make use of this for now. This is a preparation for the next article.

The first thing you may notice is that I used “

///

//

Everything that is marked with

///

You may also wonder for the line

#[derive(Debug, Clone)]

Here we use Debug and Clone. Debug is a helper for pretty-printing a struct using the print!-command, which otherwise would not work as easily; Clone is used to be able to create duplicates of objects.

Note the

pub

WorldState

As mentioned earlier, the blockchain is just a special type of ledger that stores information in a special way. As seen in the

Blockchain

Traits basically define a behavior or interface which can be shared across multiple objects. This particular interface really just defines some functionality which an object should provide in order to be a WorldState. Our blockchain will implement that trait later.

You may notice some rather unusual notation when not having seen the rust language. The first thing might be the

 -> ~

Rusts types cannot be set to null

(or None if you come from Python; do not confuse that with Rusts Option::None, which is not exactly the same) and does not support Exceptions. Therefore, you see return values like Optionand Result. The Option indicates that the function might return valid data (e.g., Option<&Account>indicates that the function might return a reference (&) to some Account-instance or not).

Similarly, for indicating a function which may fail or succeed (where you might use Exceptions in other languages) you can use the Error-type. That’s a bit more involved in this example as this is written as

-> Result<(), &'static str>

Consider the two cases: a function might succeed or fail (possibly for multiple reasons, just like there are different types of Exceptions). For this reason, you will have to provide a data type for each case: the success case and the fail case. For that function we provided

()

&’static str

The

()

void

&’static str

The

’

static

’

For now: this specific lifetime specifier just means that we want to return a pointer to a string which is baked into the binary (thus the value is static indicating the lifetime of the whole program, i.e., that value never dies). The last thing to note here is that

Result

Option

We will see soon that Rust Enumerations can carry variable data within their variants, which also enables this exact use case. Due to the frequent usage, those Enums are globally available in every module per default.

Typically, a block does not include only one action to be performed, therefore transactions member stores a vector of all the actions it includes. The hash will store a normalized representation of the whole block (including all transactions) inside.

For generating such a hash, there is a hash function needed. You might have heard of MD5 or SHA-hashes. Those get some arbitrary long input data and produce an (almost) unique and handy output while preserving some cryptographic properties[14].

We will make use of that property when implementing adding the Proof of Work in the next article.

We will generate and store that very hash of the block within each transaction. If someone would change just anything in the block, those hashes would not match anymore, which easily can be checked by just hashing again. And here comes the glue of the blockchain: Blocks (except the first one) will also store the hash of their previous block (here:

prev_hash

So, if someone tampers with the blockchain, that person would not only invalidate that very same block but also would invalidate all pointers to previous hashes in the upcoming blocks. The whole blockchain will fall apart. 

Normally, adding blocks to a distributed blockchain is computationally intensive and / or needs authorization. Again, we will see why when adding the Proof of Work in part II to our blockchain. For now, let’s just say, that this is practically infeasible in real scenarios unless quantum computers might change that.

The last variable, the nonce (number used once) will be (miss-)used later too for the proof of work. We come back to the

nonce

Transaction

This finishes the description of the block itself. Please make sure you understand the topic of hashes, and how they are used to tie the blocks together, since it is the integral component of the blockchains’ tamper-resistance.

Transaction

The Transaction structure represents some request to the blockchain which on execution will lead to a change of the WorldState (a state transition) and looks as follows:

Every transaction must be linked to an existing user at a specific time, whom will be stored in the

from

created_at

The

record

TransactionData

The

signature

from

We already have seen the

nonce

Although it is not completely implemented, I marked the code position where you would have to add some code in order to enforce that rule. But why should anybody care for this at all? Using a nonce will help preventing at least three problems: networks problems, user errors and malicious intends. All due to one single number.

The basic thought is as follows: when not accepting a nonce twice, a request which will be transmitted more than once to the system will be rejected. This fixes (i) faulty network stacks, which for some reason transmit a network package twice, (ii) users or faulty user interfaces which for whatever reason accidentally transmit the same message multiple times (you don’t want to send the very same payment accidentally twice), and (iii) some attacker might capture the request as is and — without any change — may submit it again.

This attack can also make you spend your hard-earned coins multiple times, too. The attack (which is not unique to distributed blockchains) is known as replay attack for obvious reasons. If we would not have a nonce, even a signed message cannot prevent replay attacks.

TransactionData

The

TransactionData

You may have noticed that this time, we are not defining a

struct

enum

CreateUserAccount

ChangeStoreValue TransferTokens

CreateTokens

Somewhat specific to Rust is that every variant may hold additional variable data. The

CreateUserAccount

Those arguments can also be named for better clarity (as in

TransferTokens {to: String, amount: u128}

Account and AccountType

An account of our blockchain hold

tokens

store

ChangeStoreValue

TransactionData

This transaction is meant to write arbitrary values into the user account and store it into the store. We could use it for example to store different kind of digital values (e.g., purchases of digital music) or physical values (e.g., owned properties) or just any other information we like into the account.

The remaining member

acc_type

TransactionData

Different accounts can be used as the base building block for realizing your own realization of permissioning. Maybe you want only specific accounts to be able to submit specific requests? Or only some accounts have permissions to add or verify blocks, create tokens or hold business logic (like smart contracts or chain code)? Here is the starting point for those implementations.

This finishes the declarations of the data structures. If you made it until here: you have covered almost anything which is needed to understand the nuts and bolts of this blockchain, well done 😊. The rest will be needy greedy details. But that is what you came for, right?

Structure Implementations

While the last section was very detailed and covered almost every line of code, this section will only focus on the important parts of the implementations. However, if you don’t come here to learn some Rust: most of the details here are actually treated already informatively in the sections before. You may just skim read that section.

Account 👤

Structure implementations start with the

impl

new

__init__()

In fact, naming the function

new

new

You may have noticed the return type

Self

cls

@classmethod

store

HashMap

new

HashMap

Append a block to the blockchain ➕

The functionality to add a block to the blockchain is a core ingredient. Here you will have to enforce all policies a block has to comply with in order to be accepted. Due to the function is very lengthy and doing multiple things the code will be snippet and explained in pieces.

This snippet defines the function

append_block

Result

&mut self

mut

This is similar to the (implicit)

this

self

genesis

Note that even if Rust is a strongly typed language you don’t always have to provide the data type explicitly. In this case the compiler infers that we are defining a Boolean variable (bool). In modern C++ and C# you would use the

auto-

var

where

verify_own_hash()

This code snippet checks first if the hash is set and if it is set it will verify if its valid by comparing it to the correct hash. This is done by calling 

.is_some()

hash: Option<String>

.is_some()

Knowing this fact, we can safely use 

.unwrap()

.as_ref()

.eq

.calculate_hash()

If

verify_own_hash()

false

Err

.into()

“Some String”

&str

String

.into()

Next, we check if the block is meant to be appended to the current last block. We do this by checking if prev_hash stores the actual the hash of the last block in the blockchain:

Even though both

prev_hash

hash

Option<String>

==

true

Option

Now, we check if the block contains transactions. This is just a policy we enforce, you might remove it if you want to support empty blocks.

There is nothing new to that code. Let’s move on to something more involved: verifying each transaction in the block. We want the transactions to be authentic (not tampered with) and we want them to be valid, i.e., the execution of the transaction must be possible. We do not want a transaction to spent tokens, which the account does not supply. Because a block contains multiple transactions, we will need some kind of rollback-functionality.

Otherwise, if a transaction is executed correctly and later transaction is not (forcing us to reject the block) we might end up with an inconsistence World State. That’s something we do not want. Since I don’t want to implement some complicated rollback algorithm, we just clone the whole state even though it really is not the best idea, since this could eat very much memory if the state is big:

Remember the

#[derive(Clone)]

Firstly, we iterate over all the blocks' transactions this is done by a

for

index, transaction)

block.transactions.iter().enumerate()

enumerate()

Basically, 

.iter()

.enumerate()

Inside the loop we try to execute each transaction by calling

transaction.execute()

execute

-> Result

if let Err(err) 

Err

err

If the transaction executes correctly (i.e., if it returns the Results’ an

Ok

old_state

format!

(

"{} World"

.format("Hello")

Well, if everything went fine, we just append the block and indicate everything went fine by returning the

Ok

In Part II of this series, we will come back to this function when adding Proof of Work and authentication (signatures).

Hashing 🝖

This is the place where we make use of the external crate Blake2. After creating an instance of Blake2 (

hasher

&self

.update()

u8

Yes: we actually hash the hashes of the transactions. Since the block itself also contains some data which is unique to the block, we will have to take those into account also when creating the whole block’s hash. We do this by just formatting the relevant information (previous hash and nonce) to a string and feeding it to the update function. This is somewhat lazy.

To tell the hasher we are done adding data and start the hashing, we use its

finalize()

[u8]

The transactions'

calculate_hash()

Verify the blockchain 🗹

To check if the blockchain that is presented to you is valid (i.e., no one tampered with), we need to basically do the same checks (making sure the blocks are not tampered and correctly connected) as when adding the block to the blockchain, while just omitting some different messages. Refer to the Block’s function

check_validity()

Executing a transaction ▶

Normally, the execution of a transaction comes with some change in the world state. Specifically, for this implementation this actually is a change in the

accounts

Blockchain

trait

WorldState

Our

Blockchain

Here we define the implementation of trait

WorldState

Blockchain

get_user_ids()

Because we did not come around that kind of syntax for now, let me explain this expression. The 

.keys()

accounts

or id in …

But instead we make use of functional programming paradigms here. If you coded in R or Python or JavaScript you probably came around the

map()

Here, the inline function

|s| s.clone()

s

&String

.collect()

Vec<String>

Now having that settled, we can now come to the actual implementation of the

execute()

This looks a bit weird if you’re not used to template parameters. The interesting part might be the

<T: WorldState>

execute

execute

trait

WorldState

You basically declare a new type and set the constraint that this very type should implement the

WorldState

T

world_state: &mut Blockchain

This backend could easily be a PostreSQL or MySQL handler. The actions we perform are for the most parts not specific to blockchains.

Having this covered, lets take a look in the implementation of the

execute

Before each execution we check if the user who wants to execute it really exists. Here we use the

trait

get_account_by_id()

fn get_account_by_id(&self, id: &String) -> Option<&Account>

account

Again, we destructure that

Option

f let

The statement match

&self.record

TransactionData

TransactionData

WorldState

If we fail to do so for any reason, we will return an

Err

Some of it does for me still. However, the great error messages spilled out by the compiler are often quite helpful in spotting the problems. If you write code, its sometimes even fun to fix them and make the compiler happy (I fixed like a hundred of them while writing this little piece of code…).

Usage example

1. Initializing a valid blockchain adding some transactions (adding users, transferring tokens)
2. Tampering with a transaction and detecting it
3. Smarter tampering with a transaction, still detecting it

The contents of the following file are found in the main.rs file. If you read the implementations above, this code will be fairly simple to understand.

We start by declaring our module (

rchain

Like in C(++) or Java, a Rust program have a standard entry point declared by a function named

main()

Now we create a genesis block and define the users we want to create:

After doing so we loop over the

initial_users

The last lines add all the transactions to the genesis block. The value 0 in the transaction’s constructor should be the nonce. However, since we do not enforce this nonce at the blockchain right now we just fill it with a dummy zero.

It will be a good starting point for your own coding adventures to implement the policy to enforce of a correct nonce.

The

{:#?}

{:?}

You should see the line Genesis block successfully added: Ok(()) in your terminal, after which the blockchain output starts. Notice the printout of the “accounts” which should contain alice and bob both having 100,000,000 tokens.

Now we add another block containing an action to transfer one token from alice to bob. The blockchain will again be printed. You should notice the changes in the balance of the accounts.

The last line should report a valid blockchain as Blockchain valid: Ok(()).

Now that everything seems fine, the first attack will start. Bob was not satisfied with this one coin Alice transferred. So, he decides to directly change the transaction in the blockchain.

We first clone our working blockchain to have a new one to operate on which has the same state. Then we get ourselves a mutable reference to the second transaction in the first block using

bc_attack_1.blocks[1].transactions[0].borrow_mut()

TransactionData

This is the

TransferTokens

&mut

 ref mut amount

The binding syntax

{to: _, ...}

to

Now we set the value at the memory position where amount refers to, to 100, which is Bob’s desired amount of coins, using

*amount=100

Which should print: Is the Blockchain still valid? Err(“Stored hash for Block #2 does not match calculated hash (Code: 665234234)”,)

→ The blockchain is invalid.

While Bob failed, Alice also wants to try her luck. Since she didn’t want to steal coins from Bob, she changed the

CreateTokens

Also, she noticed Bob’s mistake and didn’t want to run into the same trap, so she decided to also update the manipulated blocks hash. The basic attack looks conceptually the same as Bob’s attack.

Is the Blockchain still valid? Err("Block #1 is not connected to previous block (Hashes do not match. Should be `ÜQ\u{14}²Jüø9É7x;\u{86}æÇÐ\u{8d}À¤þMy<\u{19}óí\u{5}Qoó;ÞNc\u{12}u×1qÕ@Öáø\u{87}áHÿÞ²Àpª£\u{4}·\u{1e}íµ«Þû±¬` but is ``óç\u{93},\nbÿÁ=\u{9b}º\u{98}&¼-8$Ö~ü}òB)F°yXÙ#ãL\u{84}dÜcû/\u{9a}½I\u{16}É\u{98}¥çC;ðJè\u{9c}ý\u{9f}\u{9a}/¼\u{1}þ<òÕû`)",)

 → The blockchain broke again 🎉🥳

Conclusions and outlook

The upcoming Part II will add the following functionality:

• Sign transactions using public/private keys to make them tamper proof
• Add a transaction queue to the blockchain which holds requested transactions that are not yet executed (candidates for blocks)
• Add Proof of Work to secure the blockchain against tampering and uncontrollable growth
• Some more project structuring
• Unit testing in Rust

I hope you had a nice time reading through this rather big document. Feel free to go on in implementing some of the missing functionality and add your own ideas. There are some

@TODO

I am happy to hear any suggestions for improvements. If there is something that can be done better or easier, if there is something you’d like to add, if you see mistakes or if you need some more explanation somewhere: feel free to write me any suggestions. Just drop me a message. I hope to see you in Part II.

References 📚

• [1] Official Rust installation instructions
   
• [2] Wikipedia Article on BitTorrent
  //en.wikipedia.org/wiki/BitTorrent
• [3] Shijie Zhang, Jong-Hyouk Lee: Analysis of the main consensus protocols of blockchain
  
• [4] Adrianne Jeffries: Blockchain is meaningless, 2018
  
• [5] Leewayhertz, Top blockchain platforms of 2020
  
• [6] Github page on Ethereum related projects
  
• [7] Wikipedia page on DDoS attacks
  
• [8] Medium Article on lang registry using blockchain
  
• [10] Documentation of the Blake2 crate
  
• [11] Package index for Rust
  
• [12] Wikipedia Article on Unit Types
  en.wikipedia.org/wiki/Unit_type
• [13] Wikipedia Article on Garbage Collection
  
• [14] Tutotrialspoint, Cryptography Tutorial: Cryptography Hash functions,
  
• [15] Wikipedia Article on function composition