It’s no secret that I’ve been in a real groove with Rust and Rust-based domain specific languages lately. For ETH Denver this year, I had the pleasure of extensively using the Sway programming language to create a decentralized bounty board. Sway is a rust-based DSL for smart contracts using the Fuel Virtual Machine runtime. Despite some wide architectural differences between the EVM and FVM, such as having a UTXO based model, most of the expressions I find myself accustomed to were readily accessible in the standard library (like msg.sender, block.timestamp, msg.value, etc). Fortunately, I felt right at home for a lot of this hackathon while using Sway, despite it being new to me.

The first step of this algorithm is to take the leaf node and search its key against the mapping to retrieve its neighbor

Every tree begins as a vector of Leafs. Each of these Leafs are hashed to form leaf nodes, the first layer of the tree.

Data structures such as Merkle Trees are critical to how blockchains store data, save space, and otherwise bolster read times in large data sets.

“Ethereum is a deterministic but practically unbounded state machine, consisting of a globally accessible singleton state and a virtual machine that applies changes to that state.” (ME 39). A state machine, formally, is “nothing more than a binary relation on a set”, where elements of the set are known as states; however, it may best be understood as an “abstract model of step-by-step processes” (MCS 167). On Ethereum specifically, state is one giant data structure known as a hexary Patricia Markle Trie and all of this information is stored on-chain using the root hash of the data structure. The EVM defines what transactions are valid state transitions, the formal specifications can be found in appendix H of the yellow paper. Valid transactions on the Ethereum blockchain are what contain changes therein to the one and only canonical state of the blockchain. What is very important to note, however, is that a single transaction can be of arbitrary and unbounded complexity given that it fits within a block. With a set of valid states, we can then express the transition of state as q ----> r, where q is the initial state and r is the new, valid state. Lastly, there is no going “in-between” q and r, failure to execute a transaction will cause it to revert back to q. With unbounded transaction complexity using smart contracts and cross-contract calls, some patterns lead to reentrant calls and can drain smart contracts of their funds in the worst cases.

Nakamoto consensus is notorious for being one of the lowest throughput consensus mechanisms a blockchain might implement on paper. Of course, implementing Nakamoto consensus isn’t for no reason: the highly battle tested nature of proof-of-work (PoW) algorithms makes it the most secure candidate on the list. The problem is clear: how does a blockchain maintain the security inherent in PoW while increasing throughput? In 2015, Joseph Poon and Thaddeus Dryja proposed a revolutionary solution and concept in response to the scalability trilemma: an off-chain protocol running on a network of nodes that settles transactions instantly. Impressively, this elegant solution also maintains the trustless and decentralized nature of the Bitcoin and Litecoin blockchains without any compromise on the integrity of the blockchain’s design or principles.