Awarded: - Bounty #31 - Merkle Patricia Tree - Motoko - $6,000

Merkle Patricia Tree - Motoko - #31

Current Status: Discussion

  • Discussion (01/09/2023)
  • Ratification: (01/09/2023)
  • Open for application: (01/09/2023)
  • Assigned
  • In Review
  • Closed

Official Link

Bounty Details

  • Bounty Amount: $6,000 USD
  • Bounty Acceleration: For each 1 ICP sent to 596b5cdecdae9a8ba967d3bdc448d829f353c40c40a284b5f51a6ca283249e02, will add .25 ICP to this issue and .75 ICP to fund other initiatives.
  • Project Type: Team
  • Opened: 01/09/2023
  • Time Commitment: Weeks
  • Project Type: Library
  • Experience Type: Intermediate - Motoko; Intermediate - Crypto;


As we make progress to further integrating EVM based blockchains with motoko, we need more EVM based tools. While Bounty #29 seeks a short term solution, this bounty seeks to implement the fundamental libraries needed to build and verify transactions and data on motoko canisters without having to make an async call to a utility canister.

To execute this bounty you need to implement a Merkle Patricia Tree in motoko. See Merkle Patricia Trie | This library should be stable in nature and use a functional design such that it is not necessary to use pre/post upgrade to stabilize data.

See GitHub - ZhenyaUsenko/motoko-hash-map: Stable hash maps for Motoko for a stable pattern methodology.

See GitHub - ethereumjs/merkle-patricia-tree: Project is in active development and has been moved to the EthereumJS VM monorepo. for a JS implementation. The tests in this project should be repeated in the motoko library.

You should also offer an optional data pathway to use the stable btree library at GitHub - sardariuss/MotokoStableBTree: if the user needs access to a larger set of memory.

The library should be set up to work with vessel and MOPS.

Completing this bounty will give the developer the chance to tackle Bounty 31 - EVM Transactions - Motoko, and eventually, Bounty 27a - No Key Wallet Motoko

This bounty gives the opportunity to:

  • learn motoko
  • learn about evms and Merkle Patricia Trees
  • learn about witnesses

To apply for this bounty you should:

  • Include links to previous work writing tutorials and any other open-source contributions(ie. your github).
  • Include a brief overview of how you will complete the task. This can include things like which dependencies you will use, how you will make it self-contained, the sacrifices you would have to make to achieve that, or how you will make it simple. Anything that can convince us you are taking a thoughtful and expert approach to this design.
  • Give an estimated timeline on completing the task.
  • Post your application text to the Bounty Thread

Selection Process

The developer’s advisors will propose a vote to award the bounty and the Developer Advisors will vote.

Bounty Completion

Please keep your ongoing code in a public repository(fork or branch is ok). Please provide regular (at least weekly) updates. Code commits count as updates if you link to your branch/fork from the bounty thread. We just need to be able to see that you are making progress.

The balance of the bounty will be paid out at completion.

Once you have finished, please alert the dev forum thread that you have completed work and where we can find that work. We will review and award the bounty reward if the terms have been met. If there is any coordination work(like a pull request) or additional documentation needed we will inform you of what is needed before we can award the reward.

Bounty Abandonment and Re-awarding

If you cease work on the bounty for a prolonged(at the Developer Advisory Board’s discretion) or if the quality of work degrades to the point that we think someone else should be working on the bounty we may re-award it. We will be transparent about this and try to work with you to push through and complete the project, but sometimes, it may be necessary to move on or to augment your contribution with another resource which would result in a split bounty.


The bounty was generously funded by the DFINITY Foundation. If you would like to turbocharge this bounty you can seed additional donations of ICP to 596b5cdecdae9a8ba967d3bdc448d829f353c40c40a284b5f51a6ca283249e02. ICDevs will match the bounty $40:1 ICP for the first 75 ICP out of the DFINITY grant and then 0.25:1. All donations will be tax deductible for US Citizens and Corporations. If you send a donation and need a donation receipt, please email the hash of your donation transaction, physical address, and name to More information about how you can contribute can be found at our donations page.

FYI: General Bounty Process


The draft bounty is posted to the DFINITY developer’s forum for discussion

Ratification: (01/09/2023)

The developer advisor’s board will propose a bounty be ratified and a vote will take place to ratify the bounty. Until a bounty is ratified by the Dev it hasn’t been officially adopted. Please take this into consideration if you are considering starting early.

Open for application

Developers can submit applications to the Dev Forum post. The council will consider these as they come in and propose a vote to award the bounty to one of the applicants. If you would like to apply anonymously you can send an email to austin at icdevs dot org or sending a PM on the dev forum.


A developer is currently working on this bounty, you are free to contribute, but any splitting of the award will need to be discussed with the currently assigned developer.

In Review

The Dev Council is reviewing the submission


The award has been given and the bounty is closed.

Other Bounties

Since @relaxed04 just finished the RLP implementation and SHA3 is also available, I think it is possible to start working on this one.

I would be interested in implementing this one. Previously I have been working on a Motoko code-formatter in Rust (deprecated) and recently finished the Motoko Bootcamp in the Top 3 (my Bootcamp-Project on Github).

My plan is to start by setting up the environment for unit testing, read up on the Ethereum implementation, and then provide an estimated timeline.

Awesome! Super excited to get this going!

I will submit it to the dev board.

@icme, @aiv, @quint, @mparikh, @cryptoschindler please vote :slight_smile:

1 Like

Also interested in working on this one. Was waiting to wrap up the SHA3, and PRNG work for Timo before proposing an implementation plan here but it looks like things might be moving forward. Happy to work as a team or help out too.

We certainly love to see developers working together if you and @f0i can work it out.

What do you say @f0i ? No hard feelings if you want to go solo.

Hey @ray-react0r. In general, I’m open to sharing the work. Currently, I don’t see a clean way to split the tasks but if you have a suggestion we can discuss it. I’ll send you a DM.

Hi @skilesare ,

@f0i and I chatted about the project and we’re not seeing straightforward ways to split up the work (yet). However, we see you have Project Type marked as Team. Do the ICDevs see a good way to split up the work or was this more of a size of work decision?

That said, we’re definitely still open to working together. To make any decisions easier on our end, could the governance group pick an assignee for the sake of a team lead? Then we can decide how best to include the other.

I wanted to update you on the project. Since we were unable to split the work, I’ve moved ahead and started working on it.
I created a Github repository for this project which contains some initial test cases for the Trie’s put and get functions, along with some helper functions.

My focus is on completing and testing the Trie functions first, followed by hashing/encoding, and finally implementing the proof/verify system.

Similar to f0i, I’ve started as well. I’ve got some simple tests, most of the necessary data structures, a find function, and a trivial case for put. Initially, I wanted to emulate the Motoko-base Trie interface but found the generic K became cumbersome and likely unnecessary. Will post the repo when things stabilize a little more.


You’re welcome to work on the bounty, but is assigned to fi0 at the moment. There are a couple of other ETH-focused bounties if you want to take a stab at one of those. I think the EVM Witness prover might need the output of this, but you could get the basics in place and then just plug in the witness resolver at the end.

Sounds good. Thanks for the update. @f0i, as discussed, happy to help.

I wanted to quickly update you on the progress I’ve made. I’ve successfully implemented functions to add data, calculate hashes, generate inclusion proofs, and verify them. Currently, I’m working on resolving some issues related to exclusion proofs.

So far, I’ve repeated about two-thirds of the trie tests from the ethereumjs repository, and the remaining tests will be covered soon.

Additionally, I plan to optimize the performance of the system by minimizing the number of slow array operations and storing data as Blobs instead of [Nat8]s.

1 Like

The implementation is now mostly completed. I added the package to mops and added some documentation with examples to the

The Trie module currently exposes some internal functions and types to be accessible by the tests. I might move them to another module to cleanup the interface. Also I’m planing to run some more performance tests and optimizations. I started by generating some flamegraphs, which so far shows that nearly all of the time is spend with Keccak hashing. So I don’t expect to get huge performance improvements, but there are some smaller issues that can be improved.


Version 1.0.0 of my project has been published on mops, and I have also provided some examples in the README file on GitHub. I believe that my implementation meets the bounty’s requirements and I’m looking forward to some feedback.

For your convenience, I’ve included the links to the project below:

1 Like