Simple Directed Acyclic Graph (IOTA-like) implementation in Python

The full article was originally published by Coinmonks on Medium. Read the full article here.

For those whom just the blockchain is not enough.

About the same time a year ago I had my “leap of faith” in crypto world. I read tens of whitepapers, thousands Reddit posts, visited numerous meetups until I have discovered IOTA and joined the crypto-rage. As a dry residue now there is a knowledge that I’d like to share with the audience. Inspired by the accessibility and easiness of such blockchain tutorials like this or this and the lack of similar tutorials for Directed Acyclic Graphs (DAG), I thought to contribute as well. So here is a simple implementation of IOTA-like Distributed Ledger Technology – the Tangle! Gist pages with the full code can be found here.

Let’s start with adding the libraries we will need:

import hashlib
import random
import string
import time
from collections import OrderedDict

Then we’re going the represent Tangle as three separate dictionaries:

tangle_graph = {'genesis_branch': [],
                'genesis_trunk': []}

tangle_data = {}

tangle_ledger = {‘iota_satoshi’: 100}

tangle_graph will represent the graph data structure — each dictionary key is a transaction and each value is a list of two other transactions referenced by key, so-called: branch and trunk. We initiate Tangle with some genesis branch and trunk. tangle_data contains transaction to data payload map and tangle_ledger is a map of public keys to values. In actual IOTA implementation these data structures are not separated and are the Tangle, but for the visibility of the tutorial we keep it like that.

Here for the sake of simplicity we will not use any asymmetric cryptographic encryption like RSA or quantum-resistant Winternitz signatures, just keep in mind that ‘iota_satoshi’ is a public key or an address and whoever has a corresponding private key would be able to spent from this address.

Then we need a hashing function, let’s take simple SHA1:

def calc_hash(msg):
    hasher = hashlib.sha1(msg.encode())
    return hasher.hexdigest()

Now we introduce a basic block — Block class (pun intended):

class Block:
    def __init__(self, branch, trunk):
        self.branch = branch
        self.trunk = trunk
        self.timestamp = time.time()
        self.data_payload = get_random_string()
        self.value_tx = None

def get_hash(self):
return calc_hash(str(OrderedDict(self.__dict__)))

Block contains branch and trunk legs, timestamp and some data. Here get_random_string() just supplies block’s data_payload with random string.

Further we define function that adds blocks to Tangle:

def add_tx(block: Block):
  if block.branch in tangle_graph and block.trunk in tangle_graph:
      tangle_graph[block.get_hash()]=[block.branch,block.trunk]
      tangle_data[block.get_hash()] = block.data_payload

Basically the function checks if block’s branch and trunk legs exist in the ledger and if true, adds new transaction to Tangle.

Now we need some algorithm that selects transactions out existing ones in Tangle to be branch and trunk for the new one:

def find_tips():
    return tuple(random.sample(set(tangle_graph.keys()), 2))

This is the simplest uniform random tips selection algorithm – it just selects two different random transactions out of all transactions. In reality things are much more sophisticated.

And this is it! With one class and three functions we can run the Tangle — let’s run add_tx(Block(*find_tips())) :

tangle_graph
Out[24]: 
{'e0d5787db72c7a0bea6d9621f73bd4b21f47546f': 
['genesis_trunk','genesis_branch'],
 'genesis_branch': [],
 'genesis_trunk': []}

We just added transaction ‘e0d5787db72c7a0bea6d9621f73bd4b21f47546f’ that references ‘genesis_trunk’ and ‘genesis_branch’. Let’s add more by running add_tx(Block(*find_tips())) few more times!

{'2b503d9c90eec329b96b89cde4dc54efa826b0df': 
['genesis_trunk','580e464bd9cef52e4af07508171ce84369b258d5'],
 '37379d02f49e9dc57a6e08ff33e218a12c39f9de': 
['genesis_branch','e0d5787db72c7a0bea6d9621f73bd4b21f47546f'],
 '580e464bd9cef52e4af07508171ce84369b258d5':['37379d02f49e9dc57a6e08ff33e218a12c39f9de','genesis_trunk'],
 'e0d5787db72c7a0bea6d9621f73bd4b21f47546f':
 ['genesis_trunk','genesis_branch'],
 'genesis_branch': [],
 'genesis_trunk': []}

As you can see Tangle grows and newer transactions starting to randomly reference older transactions. As for tangle_data it looks as following:

{'2b503d9c90eec329b96b89cde4dc54efa826b0df': 'yxgcs',
 '37379d02f49e9dc57a6e08ff33e218a12c39f9de': '1lyf8',
 '580e464bd9cef52e4af07508171ce84369b258d5': '1y4vu',
 'e0d5787db72c7a0bea6d9621f73bd4b21f47546f': 'nct8w'}

Just some random data as intended.

Read the full Article

The full article was originally published by Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.

You might also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. AcceptRead More