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.

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

Grant: SubSMT #2104

Merged
merged 7 commits into from
Dec 1, 2023
Merged

Grant: SubSMT #2104

merged 7 commits into from
Dec 1, 2023

Conversation

YanOctavian
Copy link
Contributor

@YanOctavian YanOctavian commented Nov 12, 2023

Project Abstract

On-chain resources are precious, and more and more teams, especially L2,
need to put data and calculations off-chain, and Merkel trees are used more frequently.
Sparse Merkle trees are widely used in blockchains, and have been used hundreds of thousands of times in the Ethereum community.
Polkadot uses the rust language as its development language, and the implementation of sparse Merkel trees currently lacks a unified solution.
Especially in substrate and ink, if there is an implementation template for sparse Merkle trees,
it will greatly save the community's development time and avoid repeated development.
This project will do just that.

Grant level

  • Level 1: Up to $10,000, 2 approvals
  • Level 2: Up to $30,000, 3 approvals
  • Level 3: Unlimited, 5 approvals (for >$100k: Web3 Foundation Council approval)

Application Checklist

  • The application template has been copied and aptly renamed (project_name.md).
  • I have read the application guidelines.
  • Payment details have been provided (bank details via email or Polkadot (USDC & USDT) address in the application).
  • The software delivered for this grant will be released under an open-source license specified in the application.
  • The initial PR contains only one commit (squash and force-push if needed).
  • The grant will only be announced once the first milestone has been accepted (see the announcement guidelines).
  • I prefer the discussion of this application to take place in a private Element/Matrix channel. My username is: @_______:matrix.org (change the homeserver if you use a different one)

Copy link
Contributor

github-actions bot commented Nov 12, 2023

CLA Assistant Lite bot All contributors have signed the CLA ✍️ ✅

@YanOctavian
Copy link
Contributor Author

YanOctavian commented Nov 12, 2023

I have read and hereby sign the Contributor License Agreement.

@semuelle
Copy link
Member

recheck

@YanOctavian
Copy link
Contributor Author

CLA Assistant Lite bot All contributors have signed the CLA ✍️ ✅

I have read and hereby sign the Contributor License Agreement.

@YanOctavian
Copy link
Contributor Author

recheck

Done, thank you!

@semuelle semuelle self-assigned this Nov 14, 2023
Copy link
Member

@semuelle semuelle left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for the application, @YanOctavian. I will try and get some feedback on this from DevRel. I will also share it with the rest of the committee. In the meantime, could you provide a registered address, either in the application or via email?

@semuelle semuelle added the ready for review The project is ready to be reviewed by the committee members. label Nov 14, 2023
@YanOctavian
Copy link
Contributor Author

Thanks for the application, @YanOctavian. I will try and get some feedback on this from DevRel. I will also share it with the rest of the committee. In the meantime, could you provide a registered address, either in the application or via email?

Excellent! I have added my address to the application.

@YanOctavian
Copy link
Contributor Author

Thanks for the application, @YanOctavian. I will try and get some feedback on this from DevRel. I will also share it with the rest of the committee. In the meantime, could you provide a registered address, either in the application or via email?

Excellent! I have added my address to the application.

@semuelle Sorry to bother you, the application has been basically supplemented and updated. We would like to know what you think of this project so that we can further develop it. We are very honored to be able to provide products and ideas for the polkadot ecosystem. Looking forward to getting your replies and suggestions.

Copy link
Collaborator

@Noc2 Noc2 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@YanOctavian
Copy link
Contributor Author

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@Noc2 thank you for your reply. Yes, we have implemented Sparse Merkle Trees in our own project. Off-chain storage technology has become quite common, and many teams have this requirement. In our project, we use Sparse Merkle Trees due to their characteristic of having a completely binary path, which is particularly friendly to zero-knowledge proof circuits. As you know, off-chain computation and storage are often combined with zero-knowledge proofs.

While using Rust in our team, we found that development in this area was lacking. Either the existing verification methods were not user-friendly, or they consumed too much gas. We spent over a month working on code writing and testing in this area, hoping to provide our final technical solution to the Polkadot ecosystem to simplify development. Moreover, in the Ethereum ecosystem, we discovered a large number of examples using Sparse Merkle Trees. All of this indicates that the Sparse Merkle Tree solution is widely adopted.

Given that the Polkadot ecosystem has the highest technical activity and the fastest-growing developer community, there are undoubtedly many potential teams using such technology. We aim to contribute to making development simpler in this ecosystem.

@YanOctavian
Copy link
Contributor Author

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@Noc2 thank you for your reply. Yes, we have implemented Sparse Merkle Trees in our own project. Off-chain storage technology has become quite common, and many teams have this requirement. In our project, we use Sparse Merkle Trees due to their characteristic of having a completely binary path, which is particularly friendly to zero-knowledge proof circuits. As you know, off-chain computation and storage are often combined with zero-knowledge proofs.

While using Rust in our team, we found that development in this area was lacking. Either the existing verification methods were not user-friendly, or they consumed too much gas. We spent over a month working on code writing and testing in this area, hoping to provide our final technical solution to the Polkadot ecosystem to simplify development. Moreover, in the Ethereum ecosystem, we discovered a large number of examples using Sparse Merkle Trees. All of this indicates that the Sparse Merkle Tree solution is widely adopted.

Given that the Polkadot ecosystem has the highest technical activity and the fastest-growing developer community, there are undoubtedly many potential teams using such technology. We aim to contribute to making development simpler in this ecosystem.

https://github.com/Orbiter-Finance/OB_Submitter/blob/main/crates/off-chain-state/src/lib.rs This is the interface of our off-chain part, and the code of the upstream library has also been made necessary Change. Of course, if it is compatible with substrate, there is still similar work to be done. This is just an example used in Ethereum smart contracts. We now hope to be compatible with both ecologies at the same time

@YanOctavian
Copy link
Contributor Author

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@Noc2 thank you for your reply. Yes, we have implemented Sparse Merkle Trees in our own project. Off-chain storage technology has become quite common, and many teams have this requirement. In our project, we use Sparse Merkle Trees due to their characteristic of having a completely binary path, which is particularly friendly to zero-knowledge proof circuits. As you know, off-chain computation and storage are often combined with zero-knowledge proofs.
While using Rust in our team, we found that development in this area was lacking. Either the existing verification methods were not user-friendly, or they consumed too much gas. We spent over a month working on code writing and testing in this area, hoping to provide our final technical solution to the Polkadot ecosystem to simplify development. Moreover, in the Ethereum ecosystem, we discovered a large number of examples using Sparse Merkle Trees. All of this indicates that the Sparse Merkle Tree solution is widely adopted.
Given that the Polkadot ecosystem has the highest technical activity and the fastest-growing developer community, there are undoubtedly many potential teams using such technology. We aim to contribute to making development simpler in this ecosystem.

https://github.com/Orbiter-Finance/OB_Submitter/blob/main/crates/off-chain-state/src/lib.rs This is the interface of our off-chain part, and the code of the upstream library has also been made necessary Change. Of course, if it is compatible with substrate, there is still similar work to be done. This is just an example used in Ethereum smart contracts. We now hope to be compatible with both ecologies at the same time

https://github.com/nervosnetwork/sparse-merkle-tree/blob/master/src/merkle_proof.rs#L537Such similar verification methods are difficult to use in smart contracts. We currently use verification ideas that save gas and are easier for developers to understand.

@YanOctavian
Copy link
Contributor Author

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@Noc2 thank you for your reply. Yes, we have implemented Sparse Merkle Trees in our own project. Off-chain storage technology has become quite common, and many teams have this requirement. In our project, we use Sparse Merkle Trees due to their characteristic of having a completely binary path, which is particularly friendly to zero-knowledge proof circuits. As you know, off-chain computation and storage are often combined with zero-knowledge proofs.
While using Rust in our team, we found that development in this area was lacking. Either the existing verification methods were not user-friendly, or they consumed too much gas. We spent over a month working on code writing and testing in this area, hoping to provide our final technical solution to the Polkadot ecosystem to simplify development. Moreover, in the Ethereum ecosystem, we discovered a large number of examples using Sparse Merkle Trees. All of this indicates that the Sparse Merkle Tree solution is widely adopted.
Given that the Polkadot ecosystem has the highest technical activity and the fastest-growing developer community, there are undoubtedly many potential teams using such technology. We aim to contribute to making development simpler in this ecosystem.

https://github.com/Orbiter-Finance/OB_Submitter/blob/main/crates/off-chain-state/src/lib.rs This is the interface of our off-chain part, and the code of the upstream library has also been made necessary Change. Of course, if it is compatible with substrate, there is still similar work to be done. This is just an example used in Ethereum smart contracts. We now hope to be compatible with both ecologies at the same time

https://github.com/nervosnetwork/sparse-merkle-tree/blob/master/src/merkle_proof.rs#L537Such similar verification methods are difficult to use in smart contracts. We currently use verification ideas that save gas and are easier for developers to understand.

Of course, our goal is not how to change these upstream libraries, but how to provide simpler sparse Merkle tree pallets and ink smart contracts for developers to use directly. And a corresponding off-chain backend

@YanOctavian
Copy link
Contributor Author

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@Noc2 thank you for your reply. Yes, we have implemented Sparse Merkle Trees in our own project. Off-chain storage technology has become quite common, and many teams have this requirement. In our project, we use Sparse Merkle Trees due to their characteristic of having a completely binary path, which is particularly friendly to zero-knowledge proof circuits. As you know, off-chain computation and storage are often combined with zero-knowledge proofs.
While using Rust in our team, we found that development in this area was lacking. Either the existing verification methods were not user-friendly, or they consumed too much gas. We spent over a month working on code writing and testing in this area, hoping to provide our final technical solution to the Polkadot ecosystem to simplify development. Moreover, in the Ethereum ecosystem, we discovered a large number of examples using Sparse Merkle Trees. All of this indicates that the Sparse Merkle Tree solution is widely adopted.
Given that the Polkadot ecosystem has the highest technical activity and the fastest-growing developer community, there are undoubtedly many potential teams using such technology. We aim to contribute to making development simpler in this ecosystem.

https://github.com/Orbiter-Finance/OB_Submitter/blob/main/crates/off-chain-state/src/lib.rs This is the interface of our off-chain part, and the code of the upstream library has also been made necessary Change. Of course, if it is compatible with substrate, there is still similar work to be done. This is just an example used in Ethereum smart contracts. We now hope to be compatible with both ecologies at the same time

https://github.com/nervosnetwork/sparse-merkle-tree/blob/master/src/merkle_proof.rs#L537Such similar verification methods are difficult to use in smart contracts. We currently use verification ideas that save gas and are easier for developers to understand.

Of course, our goal is not how to change these upstream libraries, but how to provide simpler sparse Merkle tree pallets and ink smart contracts for developers to use directly. And a corresponding off-chain backend

Thanks a lot for the application. I have one initial question: Why do you think there is an urgent need for sparse Merkle trees , and who is the large user base? Do you want to use it for a specific project? Do you know somebody that depends on it, etc?

@Noc2 thank you for your reply. Yes, we have implemented Sparse Merkle Trees in our own project. Off-chain storage technology has become quite common, and many teams have this requirement. In our project, we use Sparse Merkle Trees due to their characteristic of having a completely binary path, which is particularly friendly to zero-knowledge proof circuits. As you know, off-chain computation and storage are often combined with zero-knowledge proofs.
While using Rust in our team, we found that development in this area was lacking. Either the existing verification methods were not user-friendly, or they consumed too much gas. We spent over a month working on code writing and testing in this area, hoping to provide our final technical solution to the Polkadot ecosystem to simplify development. Moreover, in the Ethereum ecosystem, we discovered a large number of examples using Sparse Merkle Trees. All of this indicates that the Sparse Merkle Tree solution is widely adopted.
Given that the Polkadot ecosystem has the highest technical activity and the fastest-growing developer community, there are undoubtedly many potential teams using such technology. We aim to contribute to making development simpler in this ecosystem.

https://github.com/Orbiter-Finance/OB_Submitter/blob/main/crates/off-chain-state/src/lib.rs This is the interface of our off-chain part, and the code of the upstream library has also been made necessary Change. Of course, if it is compatible with substrate, there is still similar work to be done. This is just an example used in Ethereum smart contracts. We now hope to be compatible with both ecologies at the same time

https://github.com/nervosnetwork/sparse-merkle-tree/blob/master/src/merkle_proof.rs#L537Such similar verification methods are difficult to use in smart contracts. We currently use verification ideas that save gas and are easier for developers to understand.

Of course, our goal is not how to change these upstream libraries, but how to provide simpler sparse Merkle tree pallets and ink smart contracts for developers to use directly. And a corresponding off-chain backend

After early development and testing on Ethereum, we now have very complete pallet and ink smart contracts and backend implementation solutions, and we hope to provide such technical implementation for the Polkadot ecosystem. This is a basic development solution and a technology that can be reused by all teams using substrate and ink. To facilitate the development of others, this is our original intention in creating this project.

Copy link
Collaborator

@Noc2 Noc2 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for the quick reply. I have some follow-up questions:

  • Could you tell me more about your project (it's not orbiter?) that leverages Sparse Merkle trees?
  • Do I understand it correctly that you already finished the work of this grant?

@YanOctavian
Copy link
Contributor Author

YanOctavian commented Nov 27, 2023

Thanks for the quick reply. I have some follow-up questions:

  • Could you tell me more about your project (it's not orbiter?) that leverages Sparse Merkle trees?
  • Do I understand it correctly that you already finished the work of this grant?

@Noc2 Great Job! In the orbiter team, we developed the submitter project using rust. The core development of this project will be completed by me. It tracks the transfer of specific contracts on L2 and the Ethereum chain, and then stores the account amount in an off-chain sparse Merkle tree. Provide transaction proof and verification through zero-knowledge proof, and then provide Merkel root to the chain. We found that the functions of the sparse Merkel tree can be completely independent and used as development templates for the community to facilitate developer development. At present, we have only completed some functions in Ethereum, and are considering continued development of substrate and ink smart contracts that are compatible with Polkadot to support the technological development of the Polkadot community. We are also senior developers of the substrate ecosystem, have more than 3 years of development experience in the Polkadot community and fully understand the needs of the community. So this grant project was created.

@YanOctavian
Copy link
Contributor Author

Thanks for the quick reply. I have some follow-up questions:

  • Could you tell me more about your project (it's not orbiter?) that leverages Sparse Merkle trees?
  • Do I understand it correctly that you already finished the work of this grant?

@Noc2 Great Job! In the orbiter team, we developed the submitter project using rust. The core development of this project will be completed by me. It tracks the transfer of specific contracts on L2 and the Ethereum chain, and then stores the account amount in an off-chain sparse Merkle tree. Provide transaction proof and verification through zero-knowledge proof, and then provide Merkel root to the chain. We found that the functions of the sparse Merkel tree can be completely independent and used as development templates for the community to facilitate developer development. At present, we have only completed some functions in Ethereum, and are considering continued development of substrate and ink smart contracts that are compatible with Polkadot to support the technological development of the Polkadot community. We are also senior developers of the substrate ecosystem, have more than 3 years of development experience in the Polkadot community and fully understand the needs of the community. So this grant project was created.

@Noc2 https://github.com/Orbiter-Finance/papers/blob/main/yellowpaper/yellowpaper.md#off-chain-componentThis is the yellow paper of our Orbiter team, which mentions the submitter client. We are very much looking forward to you learning about it, if you are interested.

@YanOctavian
Copy link
Contributor Author

YanOctavian commented Nov 28, 2023

Thanks for the quick reply. I have some follow-up questions:

  • Could you tell me more about your project (it's not orbiter?) that leverages Sparse Merkle trees?
  • Do I understand it correctly that you already finished the work of this grant?

@Noc2 Great Job! In the orbiter team, we developed the submitter project using rust. The core development of this project will be completed by me. It tracks the transfer of specific contracts on L2 and the Ethereum chain, and then stores the account amount in an off-chain sparse Merkle tree. Provide transaction proof and verification through zero-knowledge proof, and then provide Merkel root to the chain. We found that the functions of the sparse Merkel tree can be completely independent and used as development templates for the community to facilitate developer development. At present, we have only completed some functions in Ethereum, and are considering continued development of substrate and ink smart contracts that are compatible with Polkadot to support the technological development of the Polkadot community. We are also senior developers of the substrate ecosystem, have more than 3 years of development experience in the Polkadot community and fully understand the needs of the community. So this grant project was created.

@Noc2 https://github.com/Orbiter-Finance/papers/blob/main/yellowpaper/yellowpaper.md#off-chain-componentThis is the yellow paper of our Orbiter team, which mentions the submitter client. We are very much looking forward to you learning about it, if you are interested.

We will use a lot of substrate technology in the future, such as the decentralized sequencer of cross-chain bridge, which requires the use of substrate's transaction pool and p2p. substrate is a very excellent technical framework, thank you for your work. We also hope to provide good ideas to the Polkadot community and jointly promote the community’s technology development.

@YanOctavian YanOctavian requested a review from Noc2 November 28, 2023 09:54
@octavei
Copy link
Contributor

octavei commented Mar 15, 2024

@keeganquigley
Copy link
Contributor

Hi @YanOctavian to answer your question, we don't typically support retroactive payments, and since I can't see the project since it is closed-source, it is hard to judge if it is something we'd be interested in, but since it has already been built it probably wouldn't be eligible for a grant, unfortunately. But I appreciate the update and sounds good, looking forward to the delivery.

@keeganquigley
Copy link
Contributor

Hi @YanOctavian how is the delivery coming along?

@keeganquigley
Copy link
Contributor

pinging @YanOctavian

@keeganquigley
Copy link
Contributor

Hi @YanOctavian as we haven't heard from you in a couple months, please let us know if you are still planning to submit a delivery soon for this milestone. If it is significantly delayed, we would ask for an amendment to be submitted to extend the timeline. Thanks!

@octavei
Copy link
Contributor

octavei commented May 7, 2024 via email

@keeganquigley
Copy link
Contributor

Hi @YanOctavian thanks for the update.

Sure thing, feel free to amend the original contract to extend the timeline, and then create a PR for it at https://github.com/w3f/Grants-Program

This should be approved relatively quickly since it's a simple update. Thanks!

@keeganquigley
Copy link
Contributor

Hi @YanOctavian if delivered in the next 2 - 3 weeks probably no amendment needed. But any longer than that and the above would apply. Let me know if you still plan to submit this. Thanks.

@keeganquigley
Copy link
Contributor

Hi @YanOctavian just checking if you are able to submit an amendment for this? You can extend it for 2 months if necessary and that will take off any added pressure. Thanks.

@keeganquigley
Copy link
Contributor

Hi @YanOctavian at this point I'd say let's go ahead and cancel it and you can potentially pick it back up in the future should you want to work on it. Let me know if this sounds good, otherwise we'll close it in a few days. Thanks.

@YanOctavian
Copy link
Contributor Author

Hi @YanOctavian at this point I'd say let's go ahead and cancel it and you can potentially pick it back up in the future should you want to work on it. Let me know if this sounds good, otherwise we'll close it in a few days. Thanks.

Thank you for your reply and I apologize for being so late in replying to you. I've been really burned out on some personal team stuff lately. But I still prioritize this project, please give me some time. If I can, I will temporarily stop other things and try to finish it first. I agree with the idea of ​​extending it by 2 months, which would relieve me of the extra pressure. Thank you again for your professionalism and continued follow-up with us

@YanOctavian
Copy link
Contributor Author

Hi @YanOctavian if delivered in the next 2 - 3 weeks probably no amendment needed. But any longer than that and the above would apply. Let me know if you still plan to submit this. Thanks.

In addition, I have a question. If the deadline is extended, which part needs to be updated by submitting PR?

@semuelle
Copy link
Member

If the deadline is extended, which part needs to be updated by submitting PR?

Hi @YanOctavian. Under Development Roadmap, there are declarations of total duration and milestone durations. You can simply change these to a more realistic timeframe.

@YanOctavian
Copy link
Contributor Author

If the deadline is extended, which part needs to be updated by submitting PR?

Hi @YanOctavian. Under Development Roadmap, there are declarations of total duration and milestone durations. You can simply change these to a more realistic timeframe.

#2335 , @semuelle Thank you very much for your reminder. I have submitted a new PR and changed the milestone time to a specific time range.

@keeganquigley
Copy link
Contributor

Hi @YanOctavian just checking in to see how milestone 1 is coming along.

@keeganquigley
Copy link
Contributor

Hi @YanOctavian seeing as M1 was due about a month ago under the new amendment, just seeing how progress is coming along. Thanks for any update you can provide.

@octavei
Copy link
Contributor

octavei commented Sep 23, 2024 via email

@keeganquigley
Copy link
Contributor

Hi @octavei still planning to deliver soon?

@keeganquigley
Copy link
Contributor

pinging @YanOctavian

@octavei
Copy link
Contributor

octavei commented Nov 8, 2024 via email

@keeganquigley
Copy link
Contributor

Sounds good thanks @YanOctavian if you find that the delivery will be delayed past November, please consider filing an amendment to extend the timeline. Thanks and have a great weekend :)

@keeganquigley
Copy link
Contributor

hi @YanOctavian just checking in :)

@octavei
Copy link
Contributor

octavei commented Dec 4, 2024 via email

@keeganquigley
Copy link
Contributor

@octavei any updates? If the project will be further delayed could you please consider filing an amendment to extend the timeline?

@YanOctavian
Copy link
Contributor Author

@octavei any updates? If the project will be further delayed could you please consider filing an amendment to extend the timeline?

Apologies for the late reply. I've been busy with the development of this project last month. I've already submitted and had my PR for the first milestone merged, and will submit the second milestone in the next few days. I'm not sure if any updates are needed in the application. Have a great day! @keeganquigley

@YanOctavian
Copy link
Contributor Author

w3f/Grant-Milestone-Delivery#1228

@octavei
Copy link
Contributor

octavei commented Dec 16, 2024 via email

@semuelle
Copy link
Member

@octavei, I can confirm that we have received the invoice. It should be processed fairly soon.

@octavei
Copy link
Contributor

octavei commented Dec 17, 2024 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
ready for review The project is ready to be reviewed by the committee members.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

5 participants