Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

extend key length from 64 to 160 bit in sparse merkle tree implementation #194

Closed
johannbarbie opened this issue May 23, 2019 · 17 comments
Closed

extend key length from 64 to 160 bit in sparse merkle tree implementation #194

johannbarbie opened this issue May 23, 2019 · 17 comments
Labels
bounty size-XS total effort of ~200 DAI

Comments

@johannbarbie
Copy link
Member

johannbarbie commented May 23, 2019 •
edited
Loading

Bounty

A sparse Merkle tree (SMT) is a data structure useful for storing a key/value map which works as follows. An empty SMT is simply a Merkle tree with 2^256 leaves, where every leaf is a zero value. Because every element at the second level of the tree is the same z2=hash(0, 0), and every element at the third level is the same z3=hash(z2, z2) and so forth this can be trivially computed in 256 hashes. From there, we can add or remove values by modifying values in place in the sparse Merkle tree, eg. to add the value 42 at position 3, we modify the second value the second level to v2=hash(0, 42), the first value at the third level to v3=hash(0, v2), the first value at the fourth level to v2=hash(v3, z3) (since at this point, the left subtree represents keys 0…3 and the right subtree represents keys 4…7 which are still all empty), and so forth up to the top. source

Scope

  • the given contract implements a key length of 64 bit. extend this to 160 bits, so we can use addresses as keys.
  • extend the unit tests to cover read / update / delete for all edge cases.
  • separate SparseMerkleTree contract into contract and lib.

Deliverables

  • code
  • tests

Gain for the project

Roles

bounty gardener: @johannbarbie / 10%
bounty worker: @roleengineer / 75%
bounty reviewer: @johannbarbie / 15%
@johannbarbie johannbarbie added bounty size-XS total effort of ~200 DAI labels May 23, 2019
@johannbarbie johannbarbie mentioned this issue May 23, 2019
Merged
@gitcoinbot
Copy link

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

This issue now has a funding of 150.0 DAI (150.0 USD @ $1.0/DAI) attached to it as part of the leapdao fund.

@gitcoinbot
Copy link

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

Workers have applied to start work.

These users each claimed they can complete the work by 1 week, 6 days from now.
Please review their action plans below:

1) roleengineer has applied to start work (Funders only: approve worker | reject worker).

I'm actively dive into Solidity, so think it would be good experience to me to solve this issue. I'm familiar with such data structure as binary tree, but implemented it with Python. I need one day to understand if I can do it. So, I will add a comment, and if more suitable candidates wouldn't express interest, you can approve me.

Learn more on the Gitcoin Issue Details page.

@gitcoinbot
Copy link

gitcoinbot commented May 24, 2019 •
edited
Loading

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

Work has been started.

These users each claimed they can complete the work by 2 years, 9 months ago.
Please review their action plans below:

1) roleengineer has been approved to start work.

I'm actively dive into Solidity, so think it would be good experience to me to solve this issue. I'm familiar with such data structure as binary tree, but implemented it with Python. I need one day to understand if I can do it. So, I will add a comment, and if more suitable candidates wouldn't express interest, you can approve me.

Learn more on the Gitcoin Issue Details page.

@johannbarbie
Copy link
Member Author

@roleengineer 👋
thanks for the application. if you have technical questions, reach out to me. if non-technical, contact @kohola71. don't hesitate to join our slack.

@pbteja1998
Copy link

@johannbarbie I want to work on this if this gets available in the future. Please tag me if the bounty status becomes open again.

Thanks.

@roleengineer
Copy link
Contributor

I'm ending researching stage and starting to code. I will add WIP PR within 2-3days.

@johannbarbie
Copy link
Member Author

@pbteja1998 thanks for the interest. will do. also will tag in in similar bonties

@gitcoinbot
Copy link

@roleengineer Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

  • reminder (3 days)
  • escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

@frankchen07
Copy link

hi @roleengineer - frank from gitcoin here - any progress on that WIP PR?

@gitcoinbot
Copy link

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@roleengineer due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

  • reminder (3 days)
  • escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

@roleengineer
Copy link
Contributor

Hi @frankchen07 Yes, I'll add this WIP PR today. I had unexpectable problem, my laptop broke and it's on repaire now (I wrote Johann about this situation via Slack). I took another laptop today and after setting up necessary environment, I'll make it.

@johannbarbie
Copy link
Member Author

@roleengineer any way i can help?

@johannbarbie
Copy link
Member Author

@roleengineer good job with adding additional unit tests here:
https://github.com/roleengineer/SMT_solidity_javascript/blob/master/test/sparseMerkleTree.js
to accept the contribution i would ask you to put all the code from your own repo into this PR: #201

the idea is that we can review it, and then merge into master.

@roleengineer roleengineer mentioned this issue Jun 7, 2019
Merged
@gitcoinbot
Copy link

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

Work for 150.0 DAI (150.0 USD @ $1.0/DAI) has been submitted by:

  1. @roleengineer

@johannbarbie please take a look at the submitted work:

@gitcoinbot
Copy link

⚡️ A tip worth 60.00000 DAI (60.0 USD @ $1.0/DAI) has been granted to @roleengineer for this issue from @johannbarbie. ⚡️

Nice work @roleengineer! Your tip has automatically been deposited in the ETH address we have on file.

@gitcoinbot
Copy link

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

The funding of 150.0 DAI (150.0 USD @ $1.0/DAI) attached to this issue has been approved & issued to @roleengineer.

Additional Tips for this Bounty:

  • johannbarbie tipped 60.0000 DAI worth 60.0 USD to roleengineer.

@johannbarbie
Copy link
Member Author

resolved in #201

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bounty size-XS total effort of ~200 DAI
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@johannbarbie @frankchen07 @pbteja1998 @gitcoinbot @roleengineer