Please describe your proposed solution.

Before describing the solution, it's important to describe the problem with more details, since the details help understand why it is reasonable to believe that it is possible to optimize the synchronization time by 10x, which is quite an ambitious target.

Out of the author's experience in building and optimizing distributed-computing systems, a reasonable software-optimization target is to make the software performant enough, so that hardware is a bottleneck. Typically, such hardware bottlenecks are network bandwidth, CPU utilization, or the bandwidth of the storage system.

Does Daedalus utilize available hardware resources well?

When thinking about this proposal, I’ve taken a deeper look at Daedalus and Cardano Node to see how far the software is from fully utilizing these three major resources. Based on my calculations, it is very far (more than 10x) away from any of those limits. Here are my calculations:

1. Network. The Cardano Ledger consumes around 60GB of storage at the moment. That’s uncompressed. Ignoring the compression for now, a user with a 250 MBits/sec (~30MBytes/sec) Internet connection should download 60GB in about half an hour (60GB / 30MB/sec ~ 2000 seconds or 33 minutes). So, more than 10x quicker that the 12-24 hours that a full sync takes right now.
2. CPU. Cardano uses Blake2b (<https://www.blake2.net/>) hash function, which can verify up to 1GB of data per second per one CPU. Given a modern 8-core system, that gives 8GB/sec of hashing power. At the rate of 8GB/sec, 60GB ledger can be processed in 7.5 seconds! Next, Cardano uses fast and secure Ed25519 elliptic-curve public-key cryptography, which can verify 30'000 signatures pers second per CPU. On an 8-core system that's 240'000 singnatures per second. Assuming that each cardano block requires to verify 100 signatures, 350 epocs, and 21600 blocks per epoch, the whole blockchain should be verified quicker than in an hour: (350 epochs x 21600 blocks per epoch x 100 signatures per block / 240000 verifications per second) = 3150 seconds. So, again 10x quicker than the current time.
3. Storage. A modern PCIe SSD can read and write at least at the rate of 1GB/sec, and the newest models approach 7GB/sec. Even taking the slower rate of 1GB/sec, the whole ledger can be read in 60 seconds. Here a 10000x difference between the 12-24 hours needed by Daedalus, so storage is definitely not the bottleneck here.

After making the above calculations, three quick technical experiments were conducted to further verify that there are practical ways to improve the situation. The experiments are described in the end of this section.

The improvement plan

The above calculations and the results of the experiments suggest that the primary focus of the optimizations shall be:

1. improvements in the network utilization during synchronization.
2. improvements in the code responsible for reconstruction of the wallet history.

In addition, since just having better algorithms is not enough to improve the user experience, those algorithms shall be integrated into the software available to the general public.

Therefore, the plan is the following:

1. Prepare a method for a more efficient delivery of historical blockchain data over network to a new Daedalus setup. At the moment, the simplest possible solutions seems to be a variant of a BitTorrent protocol to ensure that the network capacity scales well with the number of clients and is inline with the overall approach of decentralization.
2. Prepare an algorithm for a quicker reconstruction of wallet history from an on-disk blockchain. Here, at least two approaches are attractive: indexing and better utilization of multi-core CPUs. Indexing will allow Daedalus to scan only those blockchain blocks that are likely (or definitely) to have transactions affecting a given wallet (there are a number of robust solutions from the database space, such as B-Tree indexes, hash-tables, etc.). For the multi-core utilization, the search for blocks relevant to the history of a given wallet can be done in parallel to reduce the wait time for the user.
3. Create a Daedalus launcher/wrapper desktop apps for Windows and Mac OS, and command-line utils for Linux, allowing the general public to benefit from the quick syncs while the algorithms are reviewed by the IOHK for inclusion into the mainstream code of Daedalus and Cardano Node themselves. These apps will guarantee that at least a quicker transfer of blockchain over network is available to end users. If it is possible to pre-initialize the wallet data for Daedalus by a wrapper app is something I still need to research.
4. Create the necessary network infrastructure (geographically distributed servers with high network bandwidth; regularly created snapshots of blockchain for distribution) to ensure that client apps can download blockchain quickly even in cases where there are insufficient number of peers in for high-speed peer-to-peer download.
5. Look into how best to utilize compression algorithms during network transfer and on-disk storage of blockchain data. Algorithms, such as LZ4 which provides an extremely high decompression speed (1000+MBytes/sec per one core) are of interest, ensuring that there are remaining CPU resources available to other tasks.
6. Work with IOHK through the creation of GitHub Issues and Pull Requests to support them in the process of integration of the new algorithms into the mainstream code of Daedalus and Cardano Node projects.

This plan is tentative since during deeper investigations alternative solutions can be discovered. The goal of this plan is to show that there are specific and feasible actions that can be taken to improve the situation.

Technical/Algorithmic Details

• To improve the network utilization the current plan (subject to change if deeper research highlights a better alternative) is to
• utilize a BitTorrent-like protocol, which means that during the Turbo-Sync process, the client computer will be a part of a peer-to-peer download network and not only download the latest blockchain data but share it with other clients.
• use all relevant peer-to-peer extensions, such as support for trackerless protocol, peer-to-peer exchange of nodes on the network, etc.
• use the classic prioritize the rarest block sharing policy.
• To improve the performance of wallet-history reconstruction
• a simple but low-risk method - utilize multi-core CPUs:
• the necessary first step to reconstruct a wallet's history is to identify blockchain blocks that contain transactions with sending or receiving addresses (a wallet can have many) derived from the wallet's private key. Let's call this step identification of the relevant blocks.
• even though the identification of the relevant blocks is necessary to fully reconstruct a wallet's history, the good news is that for most of the wallets only a small fraction of blocks (less than 1%) contains related transactions.
• the simplest possible way to reduce the run time is to simply use all available cores to run the public-key cryptography operations verifying if a given address is derived from the wallet of interest. So, this is the plan minimum.
• once the relevant blocks are identified, we can use exactly the same reconstruction process as is used right now, but requiring it to do much less than 1% of its original blocks - since most don't have transactions in many blocks of the blockchain.
• An alternative approach:
• most popular Cardano wallets generate a stake key at the same time as the payment key, and the good news that the stake key does not change and can be extracted directly from any payment address used in a transaction.
• the idea is then to create an index (a special data structure) for each block allowing to quickly check if there were transactions in the block from a wallet described by a given stake key.
• this index can be precomputed and shared along with the blockchain data distributed over the Turbo Sync method.
• having the index, Daedalus can reduce the complexity of the verification by more than 100x (the % of blocks that contain transactions referencing a given wallet is in most cases less than 1/100th) by only looking into blocks which are suggested by the index.

Experiment 1 - quick transfer of blockchain history

The following experiment was conducted to prove that the on-disk blockchain can be transferred at speeds fully utilizing the available network capacity:

1. create a new virtual machine (I've used Linux) and install a fresh copy of Daedalus.
2. launch Daedalus to let it create its local file system storage (under Linux its under $HOME/.local/share/Daedalus/mainnet).
3. stop Daedalus after several minutes of run-time.
4. take another computer which has Daedalus installed and fully synchronized. In this case a Windows computer was used
5. Take a local blockchain copy from "%APPDATA%\Daedalus Mainnet\chain\blockhain" and ""%APPDATA%/Daedalus Mainnet/chain/ledger" and put the files into an archive. That's about 60GB uncompressed, and 20GB when compressed.
6. Upload the archive onto a server with a high-speed connection (1GBit/sec).
7. Download the archive to the Linux virtual machine. Of course, this download was able to fully utilize the network.
8. Unpack the files into $HOME/.local/share/Daedalus/mainnet/chain/blockchain and $HOME/.local/share/Daedalus/mainnet/chain/ledger.
9. Start Daedalus inside the virtual machine and measure the time till it reports that it is fully synced.

In my case, the start time including sync to 100% on such a pre-initialized setup took just 5 minutes. So, this experiment proves the following points:

1. It's easy to transfer the historical state of the blockchain at the full network speed.
2. The on-disk format used by Daedalus and Cardano Node is compatible between different Operating Systems - Linux and Windows in this case.

Experiment 2 - wallet-history reconstruction with a synchronized blockchain data

For many users, the next step after having Daedalus installed and synced is either to create a new wallet or to recover a previously created one. So, I've done the following:

1. Took the same virtual machine with Daedalus synced to 100%.
2. Recovered the wallet that I previously created.
3. Measured the time till Daedalus reports that the full history of the wallet is ready.

In my case, this took 6 hours! This is with a fully synchronized ledger data already stored on the local disk!

This experiment proves the following point:

1. Even if the network is not the bottleneck anymore, the algorithm for wallet-history reconstruction still takes tremendous amounts of time.
2. The time it takes is 1000x more than what the local storage system needs to read the data from disk, suggesting a major potential for algorithmic optimization.

Experiment 3 - extracting stake keys from wallet payment addresses

One of the questions that I really wanted to answer is if there is a way for the Daedalus to only analyze those blocks in the blockchain which have transactions relevant for a given wallet. If that is possible, this can easily allow speedups of 100x and more simply because most wallets have less than a hundred of transactions in their history, while the whole blockchain creates 21600 blocks every epoch (every 5 days). One of the ways to do so is to create a new data-structure allowing to quickly check if a given block has data relevant to a given wallet. Normally, this is hard to do since each wallet can have many payment addresses, but in practice most Cardano wallets generate not only a payment address but also a stake key and that key does not change and can be extracted from the payment address and then used to verify if a given payment address is likely to be related to a given wallet. To test this hypothesis, I've done the following

1. Took Edmurgo's Cardano Serialization lib: https://github.com/Emurgo/cardano-serialization-lib
2. Written a very simple script (a copy below) to see if it is easy to extract stake key from multiple payment address of the same wallet generated by Daedalus and Yoroi.
3. Checked if the script will return the same stake key for any payment address related to several wallets in my possession.

The result was that yes - all payment addresses from the same wallet have the same extracted stake key, which potentially can be used to create a quick-search index to find blocks that contain transactions related to a given wallet.

The script for Node.JS (assumes that the imported package is installed with npm first).

> import * as CardanoWasm from '@emurgo/cardano-serialization-lib-nodejs';

> const addresses = [ &lt;a list of Cardano addresses starting with addr> ];

> for (const addrStr of addresses) {

> let addr = CardanoWasm.Address.from_bech32(addrStr);

> let stakeCred = CardanoWasm.BaseAddress.from_address(addr).stake_cred();

> console.log(addrStr, '=>', 'stake:', Buffer.from(stakeCred.to_keyhash().to_bytes().buffer).toString("hex"));

> }

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

Daedalus Wallet is one of the most popular Dapps in the Cardano ecosystem. This proposal aims to dramatically (10x) improve the user experience for first-time Cardano users - the experience of setting up a decentralized wallet and occasionally checking the balance and making transactions. Improving this experience is likely to be visible to most people in the Cardano ecosystem and those who just explore Cardano. Thus, this proposal is likely to be a major booster of the number of active users of Cardano and their engagement with the ecosystem.

This proposal directly supports the following KPIs of the Dapps, Products, and Integrations challenge:

• it increases the usage of the truly decentralized Cardano wallet, Daedalus, instead of the centralized light wallets, such as Yoroi.
• it increases the adoption of Cardano - the number of people who regularly interact with Cardano blockchain, since the primary decentralized wallet is easier to use.
• it increases the number of transactions performed, since it's more convenient to occasionally use the wallet.
• it increases the quality of a major existing product - Daedalus Wallet.
• it increases the usage of a major existing product - Daedalus Wallet.

In addition, since one of the key underlying components that will be improved - blockchain-history synchronization - is used by Cardano Stake Pool operators as well, this proposal can improve the overall network stability of Cardano ecosystem by providing stake pool operators with tools for a faster disaster recovery (setting up a new node after an unrecoverable server crash). This is because the first step in setting up a stake pool node is exactly the same synchronization of the ledger.

Last but not least, the research of how best to utilize compression algorithms can unlock a way for creating a decentralized mobile wallet - a mobile app consuming 70GB is probably unrealistic for many users, but an app that requires just 20GB or 30GB can be much more feasible. Again, keeping a mobile-wallet app always running in background just to ensure that it is synced is unrealistic - that will drain the phone's battery very quickly, but having a quicker resync, requiring just 5-10 minutes after a month of inactivity, makes using a fully-decentralized mobile wallet much more realistic.

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

The biggest risks behind this proposal are:

• Finding an algorithm capable of fully saturating the client’s network while transferring the blockchain data. Even though, it is possible there could be challenges with the integration of the new algorithm. The major algorithms themselves are battle-tested by the internet community over the last 20 years. For example, the BitTorrent protocol is available for more than 20 years and is capable of transferring data at the full bandwidth of the user’s network channel. So, in my opinion, the risk of failure here is low.
• Finding an algorithm for wallet-history reconstruction that is more efficient or better utilizes multi-core CPUs of modern laptops and computers. This is a more serious risk since there can be no compromises with regards to the quality of the verification. At the same time, methods such as indexes (yes like at the end of a book - a special structure allowing to quicker find relevant information) are actively used in the field of databases with great success. Even if indexing is a no-go, searching for the blocks that contain transactions of a given wallet with multiple processes in parallel can still be a solution that can reduce that wait time for end users.
• Ensuring a seamless integration of the found algorithms into Daedalus and Cardano Node projects. Out of the author’s experience as a funded proposer, the IOHK teams are busy, so it’s not realistic to expect a quick integration of complex solutions. To address this risk, this proposal does two things:
• Provides a standalone Daedalus Turbo App, which will work as a launcher for the Daedalus and ensures that Daedalus won’t have to sync the whole blockchain itself.
• Reserves sufficient resources for adjustments, new iterations, and bugfixes to ensure that the developed algorithms can be realistically integrated into the mainstream code.

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

Months 1-4

• Investigation of the networking bottlenecks in Cardano Node code.
• Experiments with proof-of-concept solutions to fully utilize the network, primarily looking at BitTorrent-like protocols, such as BitTorrent and BitTorrent streaming.
• Deliverable: a proof-of-concept sync tool capable to fully saturate the network bandwidth of up to 250 MBits/second.

Months 5-8

• Prepare wrapper apps for Windows and Mac OS and command-line utilities for Linux which will make the quick download of the blockchain data available to the general public.
• Experiment with various compression methods to further optimize network-transfer speed and potentially the use of on-disk storage.
• Deliverable: initial versions of Daedalus Turbo Apps are available for Windows and Mac OS.
• Deliverable: an initial version of command-line tools for Linux is available for download.

Months 9-12

• Investigate the code responsible for wallet-history reconstruction in Daedalus and Cardano Node.
• Investigate options for application of indexing algorithms to accelerate wallet-history reconstruction.
• Investigate options to better utilize multiple-core CPUs for quicker wallet-history reconstruction.
• Deliverable: A proof-of-concept implementation of a quicker wallet-history-reconstruction algorithm.
• Optional deliverable: if technically meaningful, integrate the algorithms into the wrapper apps.

Months 13-24

• Investigate how best to integrate the proof of concepts into Daedalus and Cardano Node.
• Prepare code and documentation to support IOHK in the integration of the new algorithms into Daedalus and Cardano Node.
• Work iteratively with GitHub maintainers of Cardano Node and Daedalus to integrate the algorithms into the projects.
• Fix potential bugs
• Further optimize the performance of the algorithms where possible.
• Deliverable: GitHub issues with specific requests and proposals.
• Deliverable: GitHub pull requests for cases where implementation is straightforward to help the IOHK team to quicker integrate the improvements.

Technological Notes

• The wrapper apps will be written with Electron and Node.JS - the same technological stack as is used by Daedalus itself to simplify future integration into the mainstream code and increase the potential of code reuse.
• The command line utilities for Linux will be written with for Node.JS to maximize the code reuse between all three client applications: Windows App, Mac OS App, and Linux CLI.
• For the network utilization, libtorrent (a robust C++ library for BitTorrent protocol) will likely be used.
• The algorithms for a quicker wallet-history-reconstruction are likely to be written in C or C++ to optimize for hardware performance and to make them available in different programming languages/environments, such as Haskell and Node.JS.
• To make the new algorithms available in the Haskell runtime used by Cardano Node, the "Foreign Function Interface" (FFI) of Haskell will be used.
• To make the new algorithms available within Node.JS environment, the "Native Addons" interface of Node.JS will be used.

N.B: At the moment of writing this proposal, the author is working on a 6-month project funded in Fund7. By the time the results of Fund9 are available, the active work on that project will be completed. So, that project work does not create risks with regards to the feasibility of this proposal.

Please provide a detailed budget breakdown.

This is a unique project, so it makes more sense to present primary cost-drivers instead of the bottom-up cost estimates since bottom-up estimates are very likely to be wrong but cost-drivers are likely to stay the same.

Here are the primary cost drivers:

• Research & Development - 40%
• an algorithm maximizing the network utilization during synchronization
• an algorithm unlocking utilization of multiple cores during wallet-history reconstruction
• an algorithm to pre-index blockchain to allow excluding irrelevant blocks when reconstructing a wallet's history.
• a standalone launcher app for Daedalus for Windows and Mac OS allowing to benefit from quicker syncs while the algorithms are integrated into mainstream projects of IOHK: Daedalus and Cardano Node.
• a set of command-line utilities for Linux for Stake-Pool operators allowing to use the quicker sync while waiting for the integration into the mainstream repositories
• reserve for additional iterations, bug fixes and support activities necessary to integrate the algorithms into the mainstream projects run by IOHK: Daedalus and Cardano Node.
• Quality Assurance and Testing of Distributed Systems - 10%
• renting cloud hardware for massive-scale tests - 1000s of nodes globally to verify the final versions of the peer-to-peer sync code. Costs are $1+ per hour per 1 node, so just one test with 1000 servers for one hour costs already $1k. Such tests can be needed weekly as new versions of the code are ready.
• ADA bonuses for users who would agree to run Daedalus Turbo launcher app and CLI tools during early testing stages of the solution.
• Taxes, Financial Expenses and Fees - 50%
• The author is based in Germany and based on the experience as a funded proposer in Fund7 a major reserve for tax payments and pre-payments (in Germany the financial authority can request to prepay taxes during the year) is necessary.
• ADA/USD fluctuations between the time Catalyst funds are disbursed and the actual exchange into fiat happens are major in practice: sadly ADA can fluctuate up to 5-10% within a single 24-hour period, and the exchange rate calculated by Catalyst for payments may not be actual at the time of the actual trade at an exchange. Over the last 6 months, the ADA/USD was mostly decreasing, creating a major financial expense for funded proposers.
• Crypto exchange spreads and trading fees ADA to USDT/BUSD + USDT/BUSD to EUR
• Bank fees.

The Research & Development part of the costs is driven by the rates of the following experts:

• during the first 12-months:
• Principal engineer - distributed-computing systems and algorithms.
• Senior engineer - Node.JS & Electron.
• Senior systems and networks administrator.
• during the second 12-months of the project:
• Senior engineer - Haskell & Cardano blockchain.
• Principal engineer - distributed-computing systems and algorithms.

The above areas of technical expertise are in high demand, leading to the following cost structure:

• The budget for the first 12 months of R&D: 350k EUR
• The budget for the second 12 months of R&D: 250k EUR.
• The budget for testing and quality assurance: 60k EUR.

That's 660k EUR in total, including taxes and additional financial expenses related to funding being provided in ADA.

This project is budgeted in Euro, and since it's a 24-month project, it's necessary to take into account EUR/USD rate fluctuations. The EUR/USD exchange rate over last 5 years was fluctuating in the range of 1.25 to 1.05 EUR per USD. So, the average rate of 1.15 was used to derive the USD funds requested.

The requested budget in USD is $759000 = 660k EUR * 1.15 (EUR/USD).

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

The author of the proposal has almost 20 yeas of experience of building high-performance distributed-computing systems, such as search engines, analytical big-data-processing systems, and scalable applications of machine learning. In addition, the author has broad experience in Cardano ecosystem: a funded proposer in Fund7, a Plutus Pioneer, an Atala PRISM Pioneer.

The author runs a boutique digitalization agency located in Berlin, Germany. We believe that the best technical solutions are created when the whole team both deeply understands the problem at hand and the technology used to solve it. To achieve that, we work only on a few select projects at a time and only on projects that can be implemented with a team size of less than 10 participants. These restrictions ensure that we have the capacity to communicate all the necessary information within the team to ensure that everyone understands the the whole project very well.

The author keeps a number of running contracts with freelance experts (designers, front-end and back-end developers, quality assurance experts, data scientists, system administrators, etc.). The contracts guarantee the freelancers a certain minimum number of services purchased and the freelancers guarantee that they can be added to projects on a short notice. The specific experts who will participate in this proposal will be determined once the funding is confirmed, but the author will be personally responsible for research and development of the algorithms and project management.

More about the author can be found on LinkedIn: https://www.linkedin.com/in/alexsierkov/

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

No. This proposal is organized as a single fundable item to ensure that the promised impact - 10x quicker synchronization will become available to Cardano users without any contingencies on future funding rounds. The reason behind this decision is that most of the budget will be spent on figuring out optimal algorithms and software-integration points, which are activities not particularly visible to end users. If the project were split into several parts, a situation could arise where most of the budget is spent and progress is made but the impact is not delivered to the users. Since this is an expensive project, the decision was made to focus on ensuring the delivery of the impact to end users if it is funded.

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

This project is about reducing the Daedalus’s sync time, so all metrics are centered around that objective and key factors that influence it:

• The sync time:
• The time it takes to sync Daedalus from scratch on a modern hardware: an 8-core laptop with a 250 MBits/sec Internet connection.
• The time it takes to resync after one month of inactivity on a modern hardware: an 8-core laptop with a 250 MBits/sec Internet connection.
• Client network utilization during active synchronization:
• network throughput: MBits/sec
• peak/average % of the available bandwidth used.
• Client CPU utilization during active synchronization:
• processing throughput: MBytes/sec per CPU core.
• peak/average % of CPU utilization across all cores.
• Daedalus start up time - the time from the icon is clicked till the time the balance of a newly created wallet is shown.
• With no data pre-synced.
• With data up to the last epoch pre-synced.
• With data up to the last hour pre-synced.

In addition, since the project relies on the integration of the developed algorithms into the mainstream projects managed by IOHK: Daedalus and Cardano Node, the following metrics can be used to measure the integration process:

• The number of GitHub issues created and solved.
• The number of GitHub pull requests created and merged.

To verify the end result of the integration (that end users actually benefit from the new software):

• the monthly number of unique IP addresses that participate in the Turbo Sync protocol.

Last but not least to deliver the impact to the users while waiting for the full integration of the mainstream projects temporary apps will be built, so it’s good to measure their adoption:

• The number of downloads of the Daedalus Turbo launchers for Windows and Mac OS.
• The number of downloads of the Linux CLI tools for Stake-Pool operators.

Periodic progress and KPI updates will be published to:

• project's website - will be created in the case the proposal is funded; a link will be added as comment to this proposal for the visibility and provided in the monthly progress reports to the Catalyst team.
• project's github repository - will be created in the case the proposal is funded; a link will be added as comment to this proposal for the visibility and provided in the monthly progress reports to the Catalyst team.

What does success for this project look like?

Stage 1:

• Launcher apps for Windows and Mac OS that using Turbo Sync protocol to synchronize the blockchain's history before launching Daedalus are available for general public.
• A set of command-line utilities for Linux leveraging the Turbo Sync protocol to quicker create a Cardano Node from scratch are available to the general public.
• The time it takes to download a full copy of blockchain's history is 60 minutes or less with a network connection of 250 MBits/second or better.
• The time it takes to download up to a month of blockchain's history is 5 minutes or less with a network connection of 250 MBits/second or better.

Stage 2:

• The new algorithms for quicker download and quicker wallet-history reconstruction are integrated into Daedalus and Cardano Node and are available as a setting.
• The setting can be enabled during the installation and in the respective settings interface or configuration file.
• With Turbo Sync enabled, the time it takes to download a full copy of blockchain's history and to reconstruct the wallet's history is 60 minutes or less with a network connection of 250 MBits/second or better and a CPU with 8 or more cores.
• With Turbo Sync enabled, the time it takes to download up to a month of blockchain's history and to reconstruct the wallet's history during that month is 5 minutes or less with a network connection of 250 MBits/second or better and a CPU with 8 or more cores.

Stage 3:

• Turbo Sync is enabled by default in Daedalus and Cardano Node.

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

This is an entirely new proposal.