Anastasia Labs - The Trifecta of Data Structures: Merkle Trees, Tries, and Linked Lists for Cutting-Edge Contracts

[GENERAL] Name and surname of main applicant

[GENERAL] Email address of main applicant

Additional applicants

Philip Disarro

Mladen Lm

Micah Kendall

[GENERAL] Please specify how many months you expect your project to last (from 2-12 months)

[GENERAL] Please indicate if your proposal has been auto-translated into English from another language.

[GENERAL] Does your project have any dependencies on other organizations, technical or otherwise?

[GENERAL] If YES, please describe what the dependency is and why you believe it is essential for your project’s delivery. If NO, please write “No dependencies.” .

No dependencies

[GENERAL] Will your project’s output/s be fully open source?

[GENERAL] If NO, please describe which outputs are not going to be open source. If YES, please write “Project will be fully open source.”

Project will be fully open source.

[METADATA] Category of Proposal

[IMPACT] Please describe your proposed solution.

In the Cardano community, there is a noticeable absence of shared design patterns and limited availability of practical examples and educational resources for scaling solutions using these patterns.

On-chain data is constrained by the ledger rules and transaction size limitations due to the nature of the blockchain. The ledger serves as a reliable proof of events rather than a full-fledged database or computation layer.

Utilizing specific data structures like Merkle trees, linked lists, and tries can provide efficient solutions within these constraints.

Merkle trees are valuable in proving the presence of arbitrary data within the tree structure. By carrying only the root hash in the script, an efficient and space-saving proof can be generated, ensuring data integrity and validity.

Linked list structures leverage the EUTXO model to enhancing scalability and throughput significantly. By linking multiple UTXOs together through a series of minting policies and validators, it can improve the user experience interacting with smart contract concurrently.

https://github.com/Plutonomicon/plutonomicon/blob/main/assoc.md

Tries or Stick Breaking Set are particularly useful in facilitating mutable data storage in scripts by leveraging the sharing of common prefixes. This approach optimizes storage efficiency and enables more extensive data manipulation within the constrained on-chain environment.

https://github.com/Plutonomicon/plutonomicon/blob/main/stick-breaking-set.md

We believe Cardano deserves a proper solution developed by experienced developers who care about the community to build the bridge between the pond -> the island -> the ocean.

[IMPACT] How does your proposed solution address the challenge and what benefits will this bring to the Cardano ecosystem?

The most important impact we're aiming is to help other developers to learn about these design patterns and build impactful applications, and also we want encourage the community to use them.

We believe these tools will be used by many of the developers already in Cardano and it will also alleviate the burden of understanding the EUTXO scalability solutions for new developers.

These design patterns can be utilized in various scenarios, as follows:

Merkle trees

Can be utilized in conjunction with minting policies for NFT platforms. By employing Merkle trees, users can be granted permission to mint NFTs only if they can provide a verifiable proof of their presence within the tree. This integration with minting policies ensures that users are validated against the Merkle tree before the NFT minting process takes place. Once the user's presence is confirmed, the minting policy can proceed with minting the NFT.

Linked lists

Can be leveraged in smart contract applications where the order of inputs is not crucial, and multiple users can interact with the contracts simultaneously. For example, consider a decentralized voting system where users can cast their votes concurrently. A linked list data structure can be employed to store and manage the votes efficiently. Each user's vote can be represented as a node in the linked list, containing relevant information such as the user's address and their chosen candidate.

Tries or Stick Breaking Set

One possible smart contract application for tries is a decentralized name registry. The trie data structure can be used to store the registered names and their associated data efficiently. Each name can be represented as a key within the trie, and its corresponding metadata can be stored as the value associated with that key.

Real Use

Micah will be utilising the work done here as part of Lenfi's governance solutions.

[IMPACT] How do you intend to measure the success of your project?

GitHub Stars:

Monitor the number of stars on the GitHub repository as an indicator of community interest and adoption.

Forks:

Track the number of forks of the repository, indicating the interest to explore the project.

Pull Requests and Contributions:

Monitor the number of pull requests received from users and developers, indicating active community collaboration.

Feedback and Discussions:

Monitor the number of feedbacks, discussions, and questions on the project's GitHub repository.

[IMPACT] Please describe your plans to share the outputs and results of your project?

We're planning to share information about the project on a biweekly basis on every social media platform managed by Anastasia labs. Once the project is completely done we're planning to have a twitter space for Q&A.

We have a lot of expectation about this project because we do believe it can offer a great opportunity to continue pushing for excellence within the dev community, and also onboard new people.

[CAPABILITY/ FEASIBILITY] What is your capability to deliver your project with high levels of trust and accountability?

We commit to sharing the latest status of our project on a biweekly basis through comprehensive reports that cover various aspects, including financial updates, progress milestones, and key achievements.

At Anastasia Labs we value transparency and so we invite the community to actively participate in auditing our progress. We welcome scrutiny and encourage the community to assess our work to build trust and confidence.

[CAPABILITY/ FEASIBILITY] What are the main goals for the project and how will you validate if your approach is feasible?

At Anastasia Labs, our goals for implementing the Merkle tree, Trie, and Linked List are as follows:

Generic & production ready:

We aim to implement the aforementioned onchain data structures in Aiken and Plutarch, to facilitate production level efficiency by adopting best industry practices and optimization techniques. The solutions will be as generic as possible to support the widest number of use-cases.

Ensuring Robustness through Testing:

We are aiming to employ unit tests.

Open sourcing

The development of every data structure will be entirely open sourced.

[CAPABILITY/ FEASIBILITY] Please provide a detailed breakdown of your project’s milestones and each of the main tasks or activities to reach the milestone plus the expected timeline for the delivery.

Phase 1 - Design & Develop Patterns (Aiken & Plutarch)

Key Points:

• Implement Merkle Tree
• Implement Trie
• Implement Linked List

Timeline:

2 months

Acceptance Criteria:

Completion of all design patterns tagged with a release version

Phase 2 - Thorough Testing (Aiken & Plutarch)

Key Points:

• Implement Test Merkle Tree
• Implement Test Test Trie
• Implement Test Test Linked List

Timeline:

2 months

Acceptance Criteria:

All design patterns pass unit testing.

Phase 3 - Write comprehensive documentation

Key Points:

• Documentation for Merkle Tree
• Documentation for Trie
• Documentation for Linked List

Timeline:

2 months

Acceptance Criteria:

All design patterns are properly documented.

[CAPABILITY/ FEASIBILITY] Please describe the deliverables, outputs and intended outcomes of each milestone.

Phase 1 - Design & Develop Patterns (Aiken & Plutarch)

Each design pattern (Merkle Tree, Trie, Linked List) will have a tagged version, enabling the community to track progress, updates, and improvements.

Phase 2 - Thorough Testing (Aiken & Plutarch)

Each design pattern (Merkle Tree, Trie, Linked List) will have its own Continuous Integration and Continuous Deployment (CI/CD) pipeline, enabling the community to easily check the project's correctness.

Phase 3 - Write comprehensive documentation

Each design pattern will have a dedicated example section with a comprehensive documentation, showcasing practical examples.

[RESOURCES & VALUE FOR MONEY] Please provide a detailed budget breakdown of the proposed work and resources.

Phase 1 - Design & Develop Patterns (Aiken & Plutarch):

Development Resources:

3 Software Developers

• Implement Test Merkle Tree
• Implement Test Test Trie
• Implement Test Test Linked List

105166 ADA (estimated cost for the duration of 2 months)

Phase 2 - Thorough Testing (Aiken & Plutarch):

Testing Resources:

2 QA/Test Engineers:

$30,000 (estimated cost for the duration of 2 months)

105166 ADA

Phase 3 - Write Comprehensive Documentation:

2 Technical Writers for the duration of 1 month

28042 ADA (estimated cost for the duration of 2 months)

[RESOURCES & VALUE FOR MONEY] How does the cost of the project represent value for money for the Cardano ecosystem?

At Anastasia Labs, we understand that highly skilled software developers come with a cost, and their expertise can demand high hourly rates. We firmly believe that the cost of our project represents significant value for the Cardano ecosystem.

We want to empower developers within the community to leverage these patterns, improve their own projects, and contribute to the overall growth and success of Cardano.

[IMPORTANT NOTE] The Applicant agreed to Fund10 rules and also that data in the Submission Form and other data provided by the project team during the course of the project will be publicly available.