posts/merkle-tree/

[utterances-bot]

Implementing a Merkle tree in Python :: trebaud

Unless you’ve been living under a rock for the past few years you have probably heard of Bitcoin, the decentralized, peer-to-peer, public, trustless, cash system protocol. Regardless of whether or not you think bitcoin’s current valuation is in a bubble or worse that it’s a Ponzi scheme, it’s undeniable that the protocol solves a real and old problem in distributed computing, a.k.a the Byzantine’s General Problem. One of the underlying data structures ensuring the immutability of the blockchain is the Merkle tree.

https://trebaud.github.io/posts/merkle-tree/

[paul-oprea]

Out of curiosity, did you test with more than 4 values? To notice the infinite recursion bug you've got in your code?

[Div16s]

This base case is missing:

if there is only one node

    if len(nodes) == 1:
        return nodes[0]

[trebaud]

Hey guys thank you for testing! Indeed there's an implementation error with my code , sorry about that 😅

It will only work with a 2^x number of elements (except for 3 elements because of the clause that checked for odd numbers and added an extra element, making it a 2^2=4 elements array). At 5 values it will start failing...

To fix it we could indeed check for the len(nodes) ==1 base case, the created Node in that case could just point its left and right child to the single leaf:

        if len(nodes) == 1:
            return Node(nodes[0], nodes[0], Node.doubleHash(nodes[0].value))

The initial clause checking for odd number of elements would become obsolete. I will make the changes!

[brianw0924]

your implementation can't verify if the transaction is in the tree

[soccerplayer09]

@brianw0924 Can you provide little bit of detail?

[brianw0924]

Your node only have left and right pointers, how could you build the proof path from leaves?