UTXO Optimizer and Scheduler

[IMPACT] Please describe your proposed solution.

Cardano’s usage of the UTXO model is arguably its greatest benefit over the plethora of other chains that exist. The UTXO model provides greater security and once you wrap your brain around it, the development of smart contracts is greatly augmented by it. However, UTXOs can be tricky to work with for larger transactions, moreso if non-Ada assets are involved.

Suppose your wallet contains a large number of UTXOs each having different combinations of Ada and non-Ada assets. If you would like to transfer several assets contained in different UTXOs to different output addresses, this transaction could be tricky to structure. Particularly if you are using the CLI interface to do so, which many developers are.

The workaround many use is to run all the transactions sequentially using some kind of queuing mechanism, that executes transactions sequentially. This is an adequate workaround in most cases, but as Cardano grows, the concurrency of UTXOs can become a powerful tool to maximize the efficiency of transactions. The parallel nature of the UTXOs themselves can be leveraged to improve the scalability of the network.

The way to solve and maximize the efficiency would be to devise an algorithm that can schedule transactions given the current UTXO state, predict the future UTXO state, and use that to schedule subsequent transactions. Because of the deterministic nature of Cardano transactions, it is possible to structure transactions during one time period, to optimize for transactions that need to be run in the future. This also means that we can predict the future state of a wallet, if we know what the structure of the transactions are on our planning horizon.

This algorithm would compute the optimal schedule of transactions and UTXO consumptions to use per time period. So instead of running several sequential transactions, you could then use the optimal schedule to get the same done, with fewer transactions. Additionally, a smart algorithm would be able to structure these transactions in light of network parameter constraints to maximise the computational ability of each transaction and subsequently the network nodes that compute it. That way transactions maximize the usage of the potential power of Cardano transactions.

This algorithm would naturally improve the developer experience for projects that run high volumes of complex transactions (Dexes, marketplaces, games et cetera), it would reduce the burden to operate queuing infrastructure and it would subsequently reduce the volume of small transactions on the network, maximizing the computation efficiency of the network and reducing the transaction volume load.

This problem of concurrency has been solved in many different ways in the field of industrial engineering because similar problems occur in logistics and manufacturing. Most notably, the fields of Operations Research and Scheduling Theory contain a number of methods to approach these kinds of problems. Just off the top of my head, this problem could be approached using linear programming, or finite-horizon markov decision processing, or even graph traversal and optimal path algorithms.

I propose creating a math model that solves this problem using some of the aforementioned methods, and a subsequent Javascript/Python script that developers could use to structure their transactions that implements this math model. I propose taking on this challenge as part of an independent study that will count towards my post-grad degree. My degree is a Master of Science with a major in Industrial Engineering, at Wichita State University, in Wichita, Kansas, USA. The outcome of this research would count towards the final semester of my degree, with my graduation being in December of 2022.

Cardano’s success can also be attributed in part to its slow and methodical research-driven approach to solving problems. My goal is to produce a research worthy of being published at the end of this study. Ideally, I would like to see it published in a journal or conference proceedings however that decision can only be made once all the work has been completed and it would be ignorant of me to promise that during a proposal.

Cardano is also a blockchain of the people and the last thing it needs, is to have research conducted that is locked behind corporate paywalls. Wichita State University has a student-owned IP policy, which means that the ownership of this research resides with the student and is not closed behind an institutional paywall. As a member of the Cardano community, I will make this research and the codebase accessible under an MIT license.

There are many discussions that can be had about how blockchain technology can be used to reform the world of education. I believe community based funding platforms such as Catalyst could prove to be incredibly powerful ways to do so particularly as a bridging mechanism to on-board a very traditional system into the next era of technological innovation. Students can get access to very specific funding that is scoped and preconditioned well in advance and audited by a community of people with a shared governance interest that is not motivated by profit only.

Beyond solving an actual problem in Cardano, my hope is that this project could serve as inspiration for future students to make a contribution to Cardano through academic research, and use Project Catalyst as a way to help them along. In that way this would serve both as a solution to an existing problem, and a prototype for solutions to future problems.

[IMPACT] Please describe how your proposed solution will address the Challenge that you have submitted it in.

This proposal will improve the efficiency of large and complex transactions, most of which are usually generated using the CLI, a developer tool. This tool would make projects more efficient, reduce the burden for developers to create queuing systems, and allow for the current abilities of Cardano to be maximized.

Besides these immediately tangible ways this proposal will address the challenge, I also believe that this project could become a template or prototype for future researchers to become on-boarded into the world of blockchain and specifically Cardano. There is a massive number of extremely talented individuals out there pursuing post-graduate studies, many of whose contributions will end up being shelved after submission because of the way the traditional academic system works. This proposal will serve as a proof that it is possible to solve difficult real-world problems, through targeted academic research, whilst meeting the requirements for the traditional education system.

[IMPACT] What are the main risks that could prevent you from delivering the project successfully and please explain how you will mitigate each risk?

Many of the risks that could occur, even if they occur, will be dealt with before funding is even received or fully realized. Because of the timeline of delivery to meet degree requirements, a lot of the work will be done well before funding is received, possibly even completed. Also, to preserve the privacy of my faculty advisor, their name will not be mentioned in this proposal. Here are some of the risk I can foresee and how I would address them: 

1. The scope of the project is too small to conform to the requirements for the degree
2. This will be addressed by submitting a scope document to my faculty advisor at WSU, which will be approved first. 
3. The research to develop the math model takes much longer than expected
4. This project will be initialized with an in-depth literature study that will have been completed or in its later stages, by the time the first batch of funding will be received. This literature study should provide enough detail to adequately gauge and scope the true extent of the problem. Scope creep or research delays are very difficult to pre-empt so they will be evaluated with my faculty advisor as they present themselves and relevant mitigation steps for each will be put in place.
5. The coding takes longer than expected
6. The coding will be produced after the math model has been created. One workaround in this situation would be to publish the math model first and then follow up with the coding implementation.
7. I become a bad student and I don’t deliver the deliverables
8. This research will be guided by three faculty member check-ins. This research will be conducted during the last semester of my studies, with my main thesis research already having been completed. There is very little incentive for me to fail this close to graduation.
9. I cannot manage juggling my various responsibilities
10. I have been doing the work + study juggling for 2.5 years, with exemplary results. I am confident I have more than enough time management in place to manage my commitments everywhere. Additionally, this independent research replaces the requirements for an in-person course I would have otherwise had to attend and have worked into my timeline.
11. Research sniping
12. As much as I would like to believe in a perfect world, the reality is, that doesn't exist. There are certain actors in the world of academia that actively engage in research sniping in an attempt to steal the contributions of others and claim ownership of the IP before the original authors have a chance to do so. To reduce the risk of this happening, I will provide my Catalyst co-ordinator with the check-in information and progress reports of where my study is, however the final full version will only be made public once the risk for research sniping has been largely mitigated.

[FEASIBILITY] Please provide a detailed plan, including timeline and key milestones for delivering your proposal.

27 September - Delivery of Literature Review, Thesis, and Problem Statement

2 November - Delivery of math model, relevant simulation/coding, and preliminary results

8 December - Completed paper and code base. The hope is that this deliverable will be sufficient for publication in a Journal/Conference (open-access)

[FEASIBILITY] Please provide a detailed budget breakdown.

I will not attempt to make a profit out of this, I will use the Catalyst funding to cover my tuition cost for this independent study. These fees are published publicly at the following link: https://www.wichita.edu/services/tuitionfees/index.php

This independent study will count towards 3 credit hours hence the multiplication by 3 where the rates are given per credit hour.

Tuition - $756.38 * 3 Credit Hours = $2269.14

Campus Infrastructure Fees - $19 * 3 = $57

Technology Fee - $1 *3 = $3

Transportation Fee - $0.75 * 3 = $2.25

Student Support Services Fee = $667.41

Engineering Program Fee = $160.29

Pretax Total (to be paid to the university) = $3159.09

Total Requested (adjusted for 22% tax) = $3,854.09

I am confident that I can meet the requirements for my post-grad studies and produce some valuable research for the Cardano community, that is why my aim is not to seek funding beyond that which is required for my tuition for this study only.

[FEASIBILITY] Please provide details of the people who will work on the project.

Bio: Benjamin Beer – Ben’s formal education is in Computer and Electronic Engineering with a focus on both hardware and software-based programming and system design. His Master's degree specialty focus is on the creation of industrial blockchain systems for application in the world of supply chain. He was on the NWU Solar Car racing team in South Africa as an engineer to create a web-based Race Strategy Optimization System that provides near real-time feedback in a race scenario by collating and processing large amounts of telemetric and geodesic data. As part of his post-graduate thesis, he focused on the incorporation of blockchains, specifically smart contracts, into the supply chain. This research involved significant work on Ethereum with Solidity, before being introduced to Cardano. 

Linkedin: https://www.linkedin.com/in/benjamin-beer/

Twitter: @bigbenbeer

Overview of relevant experience (both academic and work):

1. Undergraduate degree in Computer and Electronic Engineering (academic experience on the computer science and math side)
2. 18 Months of blockchain-specific graduate-level research looking at the industrial usage of smart contracts and supply chain (In the process of being published however I am not able to share anymore until the research is accepted)
3. 18 Months of Optimization mathematics coursework with exemplary results (4-point GPA scale)
4. Spring 2021: Operations Research I - (4 GPA)
5. Spring 2021: Modeling and Analysis of Manufacturing Systems (Math optimization of production lines) - (4 GPA)
6. Fall 2021: Operations research II - A (4 GPA)
7. Spring 2022: Stochastic Modeling and Analysis - B+ (3.3 GPA)
8. Spring 2022: Game Theory and Mechanism Design - A- (3.7 GPA)
9. CTO of Revelar, with 13 successfully funded proposals, many of which I authored, 1 I’ve closed out personally, 3 I’m very close to closing out, and another 2 I will be done with by the time this work starts. 
10. A year’s worth of hands-on experience with Cardano, its CLI, and the underlying UTXO technology
11. 18 months of experience working with a Solar Car racing team on the creation of a cloud-based, mathematical race strategy optimization platform.
12. 8 Years of programming experience is many different languages (Javascript and Python included)

This project will also have an assigned faculty advisor at my college, however to preserve their privacy, I will not include them on the proposal directly.

[FEASIBILITY] If you are funded, will you return to Catalyst in a later round for further funding? Please explain why / why not.

If there is scope to develop this project, or expand on the code base then definitely I will return.

[FEASIBILITY] Are you or any member of your team working on any other proposals in this Fund9?

[FEASIBILITY] Are you or your team working on any other proposals from previous Funds?

[AUDITABILITY] Please describe what you will measure to track your project's progress, and how will you measure these?

In addition to check-in meetings and reports, the following auditing metrics will be used.

The code base will be shared in a public GitHub repository at the following link: https://github.com/bigbenbeer/Plethora.The final coding tool will be called Plethora because there are a plethora of UTXOs to manage (it sounds pretty cool too). 

I will post the graded documents if allowed on the same Github as they become available. 

If there is enough scope, the final paper will be published in an Open-Access Journal/Conference paper. If I do not seek to publish through a formal academic means, I will publish a whitepaper instead using the same public Github repository. 

I will gauge interest using the feedback I receive through Github pull requests and questions. If there is enough feedback, I would submit a proposal for Fund 10 to expand on the research/codebase.

[AUDITABILITY] What does success for this project look like?

The production of both a publication-worthy paper, and a code tool developers can use to schedule transactions to maximize UTXO efficiency.

Also, I hope to help inspire other academics to become more actively involved in Cardano research even while they are studying and this proposal if funded would provide a prototype for how this can be realized. Education is something I am passionate about and I have quite literally moved 14000 miles away from my home to do so. What greater way to make a valuable contribution to humanity, than to use Project Catalyst to improve Cardano, the blockchain of the people, and in the process inspire others.

[AUDITABILITY] Please provide information on whether this proposal is a continuation of a previously funded project in Catalyst or an entirely new one.

Entirely new proposal