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.

https://www.youtube.com/watch?v=k8a6tX53YPs&t=433s

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.

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.

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.

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.

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.

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.

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.

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)

Who is in the project team and what are their roles?

Compiler & Programming Language Research

Philip DiSarro

Philip is a Computer Science Graduate School Student specializing in Compiler Development & Programming Language Theory. He was one of the first developers to formally verify smart contracts in Cardano using Agda. Philip was the lead architect of many features (both live and upcoming) on WingRiders DEX. Philip has also made significant contributions to the Cardano developer ecosystem. As a co-chair of the IOHK developer experience working group he worked to identify and resolve pain points that DApp developers experience in Cardano, and had an integral role in getting Lucid & Plutus Simple Model included in the Plutus Pioneer Program. He is a blockchain consultant & educational lecturer for Emurgo. Many know him as the primary instructor for the Cardano Solutions Architect course.

Philip is currently the lead smart contract developer at Ikigai Technologies, a consultant and lecturer for Emurgo and a founder of Anastasia Labs.

His previous experience includes:

WingRiders - Lead Smart Contract Developer

Agora - open-source contributor

Plutarch - Liqwid-Extra - open-source contributor

Plaid - FinTech Software Engineer

Philip is responsible for creating the design pattern documentation, implementing the Plutarch wrapper library, and maintaining them to reflect advancements in the developer ecosystem such as new efficiency tricks or design patterns.

Functional Programming & TypeScript SDKs

Jonathan Rodriguez

Jonathan is a highly skilled smart contract developer specializing in Cardano, a blockchain technology that he is deeply passionate about.

His passion in smart contract development drives him to constantly polish his technical knowledge. In the pursuit of that knowledge he obtained the following certifications: Cardano Solution Architect, Cardano Developer Professional, and Associate Certificate.

With an extensive background in Haskell development, which is a critical language for Cardano, he possesses a thorough understanding of functional programming concepts.

His expertise extends to various aspects of the Cardano ecosystem, including the Cardano Toolchain, Transaction Structure, Plutus Smart Contracts, Native Tokens, DApp Connector, and other essential components.

Jonathan is well-versed in conducting use case analysis and tokenomics, as well as interfacing with decentralized storage, server APIs, and integrating databases.

He is knowledgeable in establishing robust CI/CD (Continuous Integration/Continuous Deployment) flows and integrating them into development processes. Additionally, he is skilled in conducting thorough unit testing to ensure the reliability and security of his smart contract solutions.

Jonathan is responsible for contributing to the documentation, implementing the Aiken wrapper library, and maintaining them to remain up-to-date with advancements in the developer ecosystem.

Smart-Contract Developer & Blockchain Specialist

Micah Kendall is a proficient blockchain developer specializing in contract development on the Cardano blockchain using the Aiken language. With a strong background in smart contract development and blockchain technologies, Micah is passionate about creating reliable and efficient solutions on the Cardano platform. He further has backgrounds in Haskell development and functional programming.

Through his experience developing the Lenfi and Yamfore smart contract systems, Micah has demonstrated an understanding of the Cardano ecosystem, and expertise in smart contract development. He has knowledge writing efficient contracts and successfully implementing complex contract logic on the Cardano blockchain.

Micah will be joining the design and development, writing Aiken implementations, and contributing to the Typescript SDK.

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.