Blockchain Ethereum Assignment Solution : Merkle Patricia tree, radix tree, ETHASH

Q1. In Ethereum public network, as of now how many addresses are there and what is the size of Merkle Patricia tree. If required download the main network block from any source and check the size.

 

Ans: In Ethereum, public network, 92582970 addresses as of 1st April 2020. are there. And the size of Merkle Patricia tree is 29492 bytes.

 

Q2. Like Ethereum, find the number of addresses used till now in Bitcoin.

 

Ans. The number of addresses used 615,463,205, as of 20th February 2020.

 

Q3. At present time, a node with 2GB GPU can act as a miner of Ethereum main network or not. 

Ans. No. at least 3 GB of RAM or it won’t be able to properly mine Ethereum. This is due to the growing DAG file (directed acyclic graph) used in the Ethereum Proof of Work hashing process.

 

Q4. Analyze and differentiate the Patricia tree and Radix tree?

Ans. Patricia tree is also a type of trie tree and it was first described in 1968 by Donald R. Morrison. This is similar to Radix Tree with radix equals to 2 and has an innovative concept to store n items in the n nodes. It is very compact that if a node is only one child for a parent then it gets merged with a parent. The way it is used in cryptocurrency especially in Ethereum is with the Merkle tree concept to ensure the integrity of the leaf node data. A radix tree is a compressed version of a trie. In a trie, on each edge you write a single letter, while in a PATRICIA tree (or radix tree) you store whole words. Now, assume you have the words hello, hat and have. To store them in a trie, it would look like:

   e – l – l – o

  /

h – a – t

      \

       v – e

And you need nine nodes. I have placed the letters in the nodes, but in fact they label the edges.In a radix tree, you will have:

           *

           /

        (ello)

         /

* – h – * -(a) – * – (t) – *

                 \

                 (ve)

                   \

                    *

and you need only five nodes. In the picture above nodes are the asterisks. So, overall, a radix tree takes less memory, but it is harder to implement. Otherwise, the use case of both is pretty much the same.

Blockchain Ethereum Assignment Solution

                                                      Fig-Radix tree

Blockchain Ethereum Assignment Solution

                                                     Fig- Patricia tree

 

Q5. How the size of DAG in ethereum ETHASH grows when the height of the DAG remains the same?

Ans. DAG file changes every epoch. One epoch is 30 000 blocks. The size of the data set DAG is decided using block number and other initial parameters. The size will vary based on the block height.

But the question says about when the height of the DAG remains the same how the size of DAG in ethereum ETHASH grows. So from the formula,

Size = DATASET BYTES INIT + DATASET BYTES GROWTH * block number/ EPOCH LENGTH

So we increase the value of the initial parameters DATASET BYTES INIT, DATASET BYTES GROWTH then the size of DAG in ethereum ETHASH grows.

 

LAB WORKS:

Q1.     Write the structure of Merkle Patricia tree.

 

Ans.

In the Bitcoin network, the Merkle tree is used to summarize all transactions in a block and to generate a digital fingerprint of the entire transaction set.

 

Structure of Merkle Patricia tree

In the Merkle Patricia tree(MPT), the tree nodes can be divided into the following four categories:

(1) empty nodes

(2) branch nodes

(3) leaf nodes

(4) expansion nodes

whose hollow nodes are used to represent empty strings.

The branch node

branch node is used to represent all non-leaf nodes in the MPT tree that have more than one child node. The definition is as follows:

type fullNode struct {

Children [17] node // Actual trie node data to encode / decode (needs custom encoder

flags nodeFlag

}

// nodeFlag contains caching-related metadata about a node.

type nodeFlag struct {

hash hashNode // cached hash of the node (may be nil)

gen uint16 // cache generation counter

dirty bool // if the node has changes that must be written to the database

}

In addition, each branch node will have an attached field nodeFlag, which records some auxiliary data:

(1) node hash: If the field is not empty, then when the node needs to hash calculation, you can skip the calculation process directly using the result (when the node is dirty, this field is blank) calculated last time;

(2) the dirty flag: when a node is modified, the flag is set to 1;

(3) birth mark: When the node is first loaded into memory (or modified), will be given a count value as a birth mark, the logo will be used as a basis for the removal of the node, remove the memory “too old The

leaf node & extension node

leaf node is similar to the definition of the extended node, as follows:

type shortNode struct {

key [] byte

Val node

flags nodeFlag

}

where the key field is:

key: for storing node belonging to the key range;

Val: used to store the contents of the node;

Read More: How Monte Carlo Markov Chain is used in IOTA to Select tip

Q2. Implement the hash pointer using the Go language.

 

Ans.

package main

import (

"crypto/sha1"

"fmt"

   )

type Node struct{

data string

hash[] byte

next *Node

last bool

}

func get_sha_hash(x *Node)  []byte {

sh := sha1.New()

sh.Write([]byte(x.data))

sh.Write(x.hash)

bs := sh.Sum(nil)

return bs    

}

func display(x *Node){

fmt.Printf("data = %s  ",x.data);

fmt.Printf("hash of data = %x\n",x.hash);    

if(x.last){    

}else{

     display(x.next);

}

}


func main() {

var node Node

var t1 *Node  

var i int

    
node.data = "Genesis Block"

//node.hash = get_sha_hash(&node)

node.last = true

t1 = &node

var size int

size = 0

fmt.Printf("Enter no of Block \n");

fmt.Scanln(&size)

fmt.Printf("Enter data \n");

for i = 0; i < size -1; i++ {

     temp := &Node{}

     var tstr string

     fmt.Scanln(&tstr)

     temp.data = tstr//

     temp.last = true

     temp.hash = get_sha_hash(t1)

     t1.last = false

     t1.next = temp

     t1 = t1.next  

}    

  display(&node)

   

}

Blockchain Ethereum Assignment Solution

Q3. Write an Ethereum smart contract for simple Election voting and find the number of gas needed. This can be tested in Truffle or other test networks.

 

Ans.

 

pragma solidity 0.5.16;

contract Election {

  struct Candidate {

uint id;

string name;

uint voteCount;

  }

  mapping(address => bool) public voters;

  mapping(uint => Candidate) public candidates;

  uint public candidatesCount;

  event votedEvent (

uint indexed _candidateId

  );

  constructor() public {

addCandidate("Candidate 1");

addCandidate("Candidate 2");

  }

  function addCandidate (string memory _name) private {

candidatesCount ++;

candidates[candidatesCount] = Candidate(candidatesCount, _name, 0);

  }

function vote (uint _candidateId) public {

require(!voters[msg.sender]);

require(_candidateId > 0 && _candidateId <= candidatesCount);

voters[msg.sender] = true;

candidates[_candidateId].voteCount ++;

emit votedEvent(_candidateId);

  }

}

In this  Election voting smart contract the number of gas needed is 66244 per vote.

 

 Ethereum Assignment Solution

Blockchain Ethereum Assignment Solution

 

12 thoughts on “Blockchain Ethereum Assignment Solution : Merkle Patricia tree, radix tree, ETHASH”

  1. Good day! I know this is somewhat off topic but I was wondering which blog platform are you using for this website?

    I’m getting fed up of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform.

    I would be great if you could point me in the direction of a good
    platform.

  2. I used to be suggested this web site through my cousin.
    I’m not positive whether this put up is written by him as
    no one else know such special approximately my problem.
    You are amazing! Thank you!

  3. Its such as you read my mind! You appear to understand so much approximately this,
    such as you wrote the ebook in it or something.
    I think that you just could do with a few percent to pressure the
    message house a little bit, but instead of that, this is fantastic blog.
    An excellent read. I will certainly be back.

    Also visit my web-site: Breeze Tech Reviews

  4. I’m not that much of a online reader to be honest but your blogs
    really nice, keep it up! I’ll go ahead and bookmark your
    site to come back in the future. Cheers

  5. Hello there, I discovered your web site by the
    use of Google whilst looking for a comparable subject, your site got here up,
    it seems great. I have bookmarked it in my google bookmarks.

    Also visit my homepage … Vita Silk Lux

Leave a Reply

Your email address will not be published. Required fields are marked *