September 2018 - Blockchain Guide for Everyone

Tangle: Weighted Random walk

In the previous article, I have introduced the concept of tips selection using unweighted random walk (URW) algorithm. However, URW has its weakness that could crash the IOTA ecosystem. Fortunately, there is a better tips selection method known as the weighted random walk(WRW). In this article, I shall introduce the concept of WRW with the help of some illustrations.

The Lazy Tips

The main issue of using the URW algorithm is the occurrence of lazy tips. Lazy tips are tips that choose to approve some old transactions rather than actively looking to approve new transactions. We label them lazy tips because they could not be bothered to update the latest state of the IOTA Tangle network. Instead, they choose to broadcast its transactions based on old data. Let’s examine the following diagram.

With reference to the diagram above, transaction 17 and transaction 18 are lazy tips as they only approved some old transactions, as shown clearly in the diagram. If we employ the unweighted random walk selection method, these two tips have equal chances to get approved as other tips. Their behaviors would not even be penalized by the IOTA system. If there are too many lazy tips exist in the system, the Tangle will become stagnated or simply failed, as illustrated in the diagram below.

In the diagram above, we notice that the transactions 30 to 38 chose to approve very old transactions, leaving transactions 25 to 29 unapproved, or became orphans. In such situation, the Tangle structure will just stop propagating and eventually crumbles.

Weighted Random Walk

How should we overcome the ‘Lazy Tips’ phenomenon? We might impose a rule that requires all incoming transactions to approve the recent transactions. However, this coercive way is against the principles of decentralization and democracy, the core essence of decentralized ledger technologies. Therefore, IOTA opted for the persuasion method. It implements a built-in incentives system that rewards the participants to approve the recent transactions. The method is called the weighted random walk(WRW).

Weighted random walk uses the bias strategy to select the path towards a particular tip. The bias strategy involves choosing a path that has the highest approved transactions over the path that has very few approved transactions. Here we introduce a term called cumulative weight to denote the number of approvers of the transactions. It means that the higher the number of approvers, the higher the cumulative weight and vice versa. The approvers could both be direct or indirect approvers. Let’s examine the following diagram.

In order to approve tip number 13, the walker needs to walk to transaction number 5. However, transaction 5 only has a cumulative weight of 1, therefore the walker will not continue on this path. Instead, it will look for the path that has the highest cumulative weight. In our example, transaction 3 has a weight of 6, therefore the walker will choose this path and eventually reach transaction 14 and approve it.

The Parameter Alpha

However, even the weighted random walk method has its own weakness. If we insist that every approval of the transactions must follow the rule strictly, we will do away with randomness completely and many tips will be left unapproved. The Tangle system will end up having many unapproved transactions, or orphans. *I introduced my own word orphan which may not be accurate in accordance with the IOTA white paper. You can read the IOTA white paper here.

To overcome the issues, IOTA introduced a parameter α to control the ‘weight’ of the weighted random walk. If α =0, it becomes unweighted random walk and creates the issue of approving too many lazy tips. On the other hand, if we set the value of α too high, it will end up as a super weighted random walk which will leave many orphans in the Tangle.

Therefore, it is important to find a good balance between approving too many lazy tips and not leaving too many orphaned tips behind. To sum up, finding an ideal value for α is important to maintain the coherence of the Tangle ecosystem championed by IOTA.

Tips Selection in Tangle

We have learned about the basic concepts of Tangle in the previous article. Now. let’s examine how tips are selected. We shall also discuss transaction rates and the concept of random walk.

In IOTA tangle, transactions do not occur uniformly but rather randomly. At a certain period, there may be m transactions while in another period there may be only n transactions, where m>n or m<n. The transaction rate can be determined by a mathematical process known as Poisson Point Process. The Poisson Point Process model is used to analyze random events, such as the arrival of customers at a store, phone calls at a call center or occurrence of earthquakes, distributed in time

The transaction rate may be calculated based on the simplified Poisson Point Process formula as follows:

N=λt

Where N is the number of transactions and t is the time unit. λ is a constant. For example, if we set λ =5, and time unit =10 (the unit could be in milliseconds or seconds etc), the number of transactions occurring in a 10-unit time interval is 5×10=50.

Setting a suitable value of λ is crucial to maintaining the coherence of the Tangle structure. if we set the value of λ to be very small, let’s say 0.1 and the number of transactions remains at 50, the time interval will be 50 ÷ 0.1=500. In this case, it means that transactions will come in so slowly that it will form a chain instead of a Tangle, such that only one single tip could be approved at any given time, instead of approving two previous transactions. The scenario is illustrated in the diagram below:

On the other hand, what will happen if we set the value of λ too high? For example, if λ =10000 and N=50, the time interval t is 0.0005. It means that transactions will be occurring so fast that the only tip they can view is the genesis node, as illustrated in the diagram below:

In both cases, the Tangle structure will crumble.

Unweighted Random walk Algorithm

The tips selection algorithm we have discussed so far is a random selection process. This kind of selection process might not be suitable for the real use case. Therefore, we need to choose a more advanced tip selection algorithms. One of the algorithms is known as the unweighted random walk.

What is it? In programming, a walker is a variable used to move through an array or other data structure, often heading towards a fixed value and stepping through elements in an array. In Tangle, we can program a walker on the genesis transaction, and make it walks towards the tips.

On each step, it walks to one of the transactions which directly approves the one we are currently on. It chooses which transaction to walk to with equal probability, therefore it is called unweighted random walk. You can visualise the process from the animated diagram below:

Please watch the video below to understand more about the Tangle system.

Video Adapted from IOTA.ORG

Introducing IOTA

The Machine Economy

From the connected mobile devices, wearable devices to Smart homes, the Internet of Things is beginning to permeate every aspect of our lives. The adoption of IoT technologies is fostering a new economy nurtured by these technologies. As this kind of economy is powered by the machine to machine (M2M) communication, it is also known as the machine economy.

According to IOTA foundation, the number of connected devices is estimated to reach 75 billion by 2025. Internet of Things (IoT) includes tiny sensors on roads, bridges, railway tracks, mobile phones, smart washing machines , smart drones, wearable electronics like smartwatches and more. The amount of data being produced and consumed by all these devices is becoming astronomical.

Over the next five years, it is predicted that the global IP traffic on the IoT network will increase five-fold by 2021, monthly IP traffic is expected to reach 31 Gigabytes per capita. However, for the same period, broadband speeds are expected only to double and the global data pipelines will experience congestion. By then, it will not be possible for all these devices to stay connected 24/7 to the centralized cloud silos for all the data they will generate.

Recently, the emergence ‘Fog’ and ‘Mist’ computing emerged might provide a solution to the aforementioned issue. However, how to distribute resources efficiently across the IoT ecosystem remains a huge challenge in this new Machine Economy. Therefore, IOTA was conceptualized with the mission to tackle the congestion issue. By implementing zero fee transactions, these devices can share the technological resources in real-time locally in a distributed network. In this way, it can avoid the centralized points of failure, eliminating the resource infrastructure bottleneck.

The Vision of IOTA

The vision of IOTA is to enable all connected devices through verification of truth and transactional settlements, which incentivize devices to make available its properties and data in real time. In addition, the IOTA cryptocurrency was developed to enable Machine-2-Machine (M2M) transaction, thus creates the machine economy powered by IoT.

The main objective of IOTA is to serve the machine economy by enabling zero fee M2M payments. IOTA has established itself as the leader in IoT fintech landscape by providing efficient, secure, lightweight, real-time microtransactions without fees. It is open-source and engineered specifically for the Internet of Things. Its real-time microtransactions using the IOTA cryptocurrency has created an ecosystem that is ready and flexible for scale.

The Tangle

IOTA technology is similar to the blockchain technology but it is not blockchain-based. In fact, it utilizes a kind of distributed ledger technology minus the blocks. IOTA is a permissionless distributed ledger that utilizes a cutting-edge technology, known as Tangle. The Tangle is a new data structure based on a Directed Acyclic Graph(DAG). As opposed to the blockchain, it has no blocks, no chain and also no Miners. This unique new architecture enables IOTA works differently compared to Blockchains and other Distributed Ledger Technologies.

The Core Principles

IOTA uses a DAG instead of a blockchain to store its ledger. The main objective is to solve the scalability issue. As we all know, a blockchain has an inherent transaction rate limit, due to the conflict between block sizes and block issuances rates. If blocks are issued too frequently, or are too large, forks will occur often. When a fork happens, several new blocks are added to the chain simultaneously, and the network needs to decide between them, thus slow down the validation process.

In a DAG, forks can still occur but unlike in a blockchain, a fork is not final. In the DAG system, diverging branches can still be merged back together, as long as they are consistent with each other. The transaction rate is therefore bounded only by the latency between the nodes. A DAG favors availability over consistency.

The Tangle Structure

The Tangle is a Directed Acyclic Graph (DAG). In computer science, a directed graph is a collection of vertices (squares), which are connected to each other by edges (arrows). In the IOTA Tangle data structure, the vertices represent transactions, and the edges represent approvals. It retains the blockchain features that include distributed ledger, immutability, and secure transactions, but it does not utilize the blocks.

The Tangle structure is shown in the following figure.

With reference to the figure below, If there is an edge(arrow)
directed node (vertex) 100 to node 99, it means that node 100 approves the transaction at node 99. When a node issues a new transaction, it must choose 2 previous ones to approve, thereby adding 2 new edges(arrows) to the graph. Notice that each node must be connected to two previous nodes.

The first transaction in the Tangle is referred to as the genesis. All the IOTA tokens were created in the genesis, and no new ones will ever be created. All transactions in the tangle reference the genesis directly or indirectly.

Transactions with no approvers are called tips. In the figure above, node 100 is a tip because no one approves its transaction yet. All the nodes must choose tips to approve, rather than older transactions, because this helps move the network consensus forwards. The method for choosing which two tips one should approve is one of the key innovations of IOTA.

Tokenization Explained

What is Tokenization?

Tokenization has become a buzzword today due to its adoption in the payment industry and blockchain. However, Its usage is not limited to the aforementioned industries. It can be applied to many other industries such as healthcare, stock trading, gaming and more.

The primary purpose of tokenization is to ensure data security. It is used for handling sensitive data such as payment, medical record, personal ID and more.

According to Wikipedia,

“Tokenization, when applied to data security, is the process of substituting a sensitive data element with a non-sensitive equivalent, referred to as a token, that has no extrinsic or exploitable meaning or value. The token is a reference (i.e. identifier) that maps back to the sensitive data through a tokenization system. The mapping from original data to a token uses methods which render tokens infeasible to reverse in the absence of the tokenization system, for example using tokens created from random numbers.

The tokenization system must be secured and validated using security best practices applicable to sensitive data protection, secure storage, audit, authentication and authorization. The tokenization system provides data processing applications with the authority and interfaces to request tokens, or detokenize back to sensitive data.”

In short, Tokenization is the process of substituting sensitive data with non-sensitive identification symbols known as tokens. Tokenization retains all the essential information of the data without compromising its security.

A Short History

According to Wikipedia, the concept of tokenization has existed since the invention of the currency system centuries ago. It was adopted as a means to reduce risk in handling financial instruments by replacing them with surrogate equivalents.

In addition, coin tokens have a long history of use replacing the financial instrument of minted coins and banknotes. In more recent history, tokens are used in mass rapid transit payment, casino chips and more. The adoption of the above systems is to replace physical currency and cash for reducing risks such as theft.

In the digital world, tokenization techniques have been used since the 1970s. They were meant to isolate real data elements from exposure to other data systems(Wikipedia, 2018). In databases, surrogate key values have been used since 1976 to isolate data associated with the internal mechanisms of databases and their external equivalents for a variety of uses in data processing.

More recently, these concepts have been extended to consider this isolation tactic to provide a security mechanism for the purposes of data protection. For example, in the payment card industry, tokenization is one means of protecting sensitive cardholder data in order to comply with industry standards and government regulations.

Definition in Blockchain

In blockchain, tokenization is a method that converts rights to an asset into a digital token. Thus, we can take an asset, tokenize it and create its digital representation that lives on Blockchain. Blockchain guarantees that the ownership information is immutable. The tokens created in this way is also known as crypto tokens.

For example, you can tokenize an asset such as a book that you authored. The book is kept somewhere while the book token is uploaded to the blockchain network. The book crypto token is a representation of the book ownership. You can specify how many tokens need to be transferred to your crypto wallet before you can transfer the book ownership to a buyer by means of a smart contract.

One of the actual use cases is https://stamp.io , a platform where you can store your tokenized documents on the block and certify it, as shown in the following figure:

Cryptokitties is a brilliant example of the crypto token that allows users to acquire an adorable collectible by transferring some cryptocurrencies to the owner. The owner will then transfer the digital collectible to the buyer. The transaction occurs automatically via the smart contract.

Another use case is we can create a crypto token that represents some customer loyalty points on a blockchain. This type of token is also known as utility token. It can be used to manage customers’ reward schemes for the retail chains. Other examples include the crypto token that gives entitlement to the token holder to view certain hours of video streaming on a video-sharing blockchain. A house owner can sell his house by transferring the tokenized house deed to the buyer. Last but not least, a crypto token may even represent another cryptocurrency.

Fungible Tokens vs Non-Fungible Tokens

We often come across the terms fungible Tokens and non-fungible tokens in the blockchain. What are they? The following table explains what are they and how they differ.

Fungible Tokens	Non-fungible Tokens
Interchangeable A fungible token can be exchanged with any other fungible token of the same type. It is like exchanging a dollar bill with another dollar bill and the value is still the same.	Non-Interchangeable A non-fungible token cannot be exchanged with another non-fungible token of the same type. It is like your passport or ID, they cannot be exchanged.
Uniform Each fungible token is identical to all other fungible tokens of the same type. For example, your one-dollar bill is the same as John’s one-dollar bill.	Unique Each token is unique and different from all other tokens of the same type. For example, your bank account is not the same as John’s bank account
Divisible A fungible token can be divided into smaller units and the total value is still the same. For example, you can divide a dollar bill into two 50 cents or five 20 cents and the total value is still the same.	Non-divisible The non-fungible token cannot be divided into smaller units. The basic unit is one token and one token only. For example, your driving license.
ERC-20 Standard The Ethereum Standard is used for issuance tokens to be used as cryptocurrencies.	ERC-721 Standard The Ethereum Standard is used for the issuance of unique, non-fungible tokens. The most well-known case is CryptoKitties, which is a virtual collectibles marketplace where each kitty is unique.

Non-fungible tokens can be used in KYC (Know Your Customer) procedures, for academic degrees and other educational certificates, collectibles, badges, voting & elections, loyalty programs, in-game items, copyright, supply chain tracking, medical data, software licenses, warranties, and more.