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

Simple Directed Acyclic Graph (IOTA-like) implementation in Python 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 hashlibimport randomimport stringimport timefrom 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 = Nonedef 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_graphOut[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. Now we going to move some funds, but in order to do so we need to add extra function to our Block class: def add_value_tx(self, sender, receiver, amount, signature): self.value_tx = {'sender': sender, 'receiver': receiver, 'amount': amount, 'signature': signature } This will add non-zero transaction status to a block object: # prepare block usual wayvalue_block = Block(*find_tips()) # add value transition in blockvalue_block.add_value_tx('iota_satoshi', 'iota_foundation_address', 50, 'calligraphic_signature_of_satoshi_himself') Obviously calligraphic_signature_of_satoshi_himself is cryptographic signature of the public-key/address iota_satoshi. Now we need to handle a logic for value transactions that will modify tangle_ledger: def check_value_tx(value_tx): if value_tx['sender'] in tangle_ledger: if value_tx['amount'] <= tangle_ledger[value_tx['sender']]: # if signature is valid too res = True return res def move_money(sender, receiver, amount): tangle_ledger[sender] -= amount if receiver in tangle_ledger: tangle_ledger[receiver] += amount else: tangle_ledger[receiver] = amount First one checks if sender address even exists and have enough money to be spend. Second one moves funds from sender to receiver adding the later if not exist on the ledger. (One can still send negative amount and throw someone in dept 😱 ) All that remains to modify add_tx() : def add_tx(block: Block): if block.branch in tangle_graph and block.trunk in tangle_graph: if block.value_tx: if check_value_tx(block.value_tx): move_money(block.value_tx['sender'], block.value_tx['receiver'], block.value_tx['amount']) tangle_graph[block.get_hash()] = [block.branch, block.trunk] tangle_data[block.get_hash()] = block.data_payload else: tangle_graph[block.get_hash()] = [block.branch, block.trunk] tangle_data[block.get_hash()] = block.data_payload Now we can add a block with a value-transaction add_tx(value_block) and the Tangle will look like: tangle_graph{'2b503d9c90eec329b96b89cde4dc54efa826b0df': ['genesis_trunk','580e464bd9cef52e4af07508171ce84369b258d5'], '37379d02f49e9dc57a6e08ff33e218a12c39f9de': ['genesis_branch','e0d5787db72c7a0bea6d9621f73bd4b21f47546f'], '580e464bd9cef52e4af07508171ce84369b258d5':['37379d02f49e9dc57a6e08ff33e218a12c39f9de','genesis_trunk'], 'c33f585243abac2f59494eb092a600d3fe97423a': ['genesis_branch', '580e464bd9cef52e4af07508171ce84369b258d5'], 'e0d5787db72c7a0bea6d9621f73bd4b21f47546f': ['genesis_trunk','genesis_branch'], 'genesis_branch': [], 'genesis_trunk': []} tangle_ledger{'iota_foundation_address': 50, 'iota_satoshi': 50} tangle_data{'2b503d9c90eec329b96b89cde4dc54efa826b0df': 'yxgcs', '37379d02f49e9dc57a6e08ff33e218a12c39f9de': '1lyf8', '580e464bd9cef52e4af07508171ce84369b258d5': '1y4vu', 'e0d5787db72c7a0bea6d9621f73bd4b21f47546f': 'nct8w', 'c33f585243abac2f59494eb092a600d3fe97423a': {'data_payload': 'ps697', 'value_payload': {('sender', 'iota_satoshi'), ('receiver', 'iota_foundation_address'), ('amount', 50), ('signature', 'calligraphic_signature_of_satoshi_himself')}} This is simplest DAG implementation and of course it lack of consensus, keys encryption, validation and network topology, but it should give a reader the intuitive understanding how IOTA works. Gist pages with the full code can be found here. You can reach me on IOTA Discord at stkubr#1936 or on Twitter @KubrakStan. If you like my work and want me to continue expanding this tutorial into a second part, adding nodes consensus, Flask webserver and etc. please feel free to donate some Iotas on address: EHNQJBGFAIUTJKPMSUCSDMIH9XTHANMJBVEZLFYURUXJUARTGKG9KDBHTCZHDKZZOGT9ENQEMHPOSLHPWXAELUPSDX Thank you for your attention :)