UTXO wallet DB Management

In the realm of blockchain technology, UTXO (Unspent Transaction Output)-based wallets play a crucial role in managing and facilitating transactions on networks such as Bitcoin. Efficient database management lies at the core of these wallets, ensuring smooth operation, optimal performance, and robust security. In this article, we delve into the intricacies of database management for UTXO-based wallets, exploring key concepts, challenges, and best practices.

Understanding UTXO-Based Wallets: UTXO-based wallets operate on the principle of managing a set of unspent transaction outputs. Each UTXO represents a certain amount of cryptocurrency or NFT associated with a specific output of a transaction. Wallets maintain a database that tracks these UTXOs, enabling users to perform transactions by selecting appropriate outputs and creating new ones as needed.

Key Database Management Considerations:

1. UTXO Set Management: The heart of a UTXO-based wallet's database management lies in efficiently managing the UTXO set. This involves operations such as adding new UTXOs when receiving funds, updating existing UTXOs when spending funds, and removing spent UTXOs to maintain an accurate and up-to-date set.
2. Transaction Building and Coin Selection: Wallets must implement robust algorithms for coin selection when building transactions. These algorithms optimize factors such as minimizing transaction fees, avoiding dust outputs, and maintaining user privacy. Efficient coin selection is crucial for optimal transaction throughput and cost-effectiveness.
3. Address Indexing: Wallet databases often include mechanisms for indexing addresses associated with UTXOs. Address indexing facilitates operations such as balance calculation, transaction history retrieval, and address reuse prevention. Proper indexing enhances query performance and improves user experience.
4. Security and Consistency: Database management in UTXO-based wallets prioritizes security and data consistency. Measures such as transaction atomicity, database backups, and encryption are essential for safeguarding user funds and preventing data corruption or loss.

There are some key differences in how wallets for UTXO-based blockchains (like Bitcoin) and account-based blockchains (like Ethereum) handle building and maintaining their internal databases. Here's a breakdown:

UTXO-Based Blockchains:

• Wallet Database: Instead of storing a single balance, the wallet tracks Unspent Transaction Outputs (UTXOs). These UTXOs represent individual units of cryptocurrency received through past transactions that haven't been spent yet.
• Building the Database: When you receive cryptocurrency, a new UTXO with the corresponding amount is added to your wallet's database.
• Maintaining the Database: Spending cryptocurrency involves selecting specific UTXOs that add up to the amount you want to send. These UTXOs are then marked as "spent" and removed from your wallet's database. New UTXOs representing the remaining balance and any change are created and added.

Analogy: Imagine your wallet is like a physical wallet containing cash bills. Each UTXO is like a unique bill (e.g., a $10 bill). Transactions involve selecting specific bills to pay and receiving new bills as change.

Account-Based Blockchains:

• Wallet Database: The wallet stores your account balance, similar to a traditional bank account.
• Building the Database: When you receive cryptocurrency, the wallet updates your account balance by adding the received amount.
• Maintaining the Database: Spending cryptocurrency involves sending a transaction with the desired amount. The wallet doesn't directly manipulate the UTXOs on the blockchain; it just broadcasts the transaction for the network to process. The network then updates the account balance on the blockchain itself.

Analogy: Imagine your wallet is like a bank account. You see your total balance, and transactions directly modify that balance.

Now I will explain the db management of Tuxedo blockchain .

FYI Tuxedo is UTXO based blockchain built on top of substrate framework.

Link for Tuxedo: Tuxedo: Write UTXO-based Substrate Runtimes

DB management in Tuxedo CLI-Rust wallet: Tuxedo/wallet/src/sync.rs

Design for syncing a local database with a blockchain network.?The code manages UTXO (Unspent Transaction Outputs) and maintains consistency with the blockchain.?It includes database initialization, block synchronization, transaction handling, and UTXO management functions.

There are 8 tables in the database.

You can have many tables 2 for each UTXO.1 for spent and another for unspent.

1. BlockHashes? -? Key(block_number:u32) => Value(block_hash:H256)
2. Blocks? -? Key(block_hash:H256) => Value(block:Block)
3. UnspentOutputs? -? Key(output_ref) => Value((owner_pubkey, amount)
4. TSpentOutputs? -? ?Key(output_ref) => Value((owner_pubkey, amount)
5. UnspentKitty? -? ?Key(output_ref) => Value((owner_pubkey, KittyData)
6. SpentKitty? -? ?Key(output_ref) => Value((owner_pubkey, KittyData)
7. UnspentTradableKitty? -? ?Key(output_ref) => Value((owner_pubkey, TradableKittyData)
8. SpentTradableKitty? -? ?Key(output_ref) => Value((owner_pubkey, TradableKittyData)

UTXO-based wallet DB building is mainly 4 steps :

1. Extract the block-hash?from the block height (height = 0 means genesis block) and store it in the DB
2. Get the block based on the block-hash(block-hash obtained in the previous step) and store it in the DB
3. Extract the transactions from the block and store it in the DB?
4. Extract the UTXO of interest from the transactions and store it in the db.

Detailed steps:

Step 1: Read Node's Genesis Block Step 1.1: Retrieve Node's Genesis Block Hash

1. Make an RPC call to the blockchain node to get the genesis block hash.
2. Use the RPC method chain_getBlockHash with the height parameter set to 0. //Ex: RPC call => "hash =client.request("chain_getBlockHash", height)" // height = 0
3. Store the obtained genesis block hash for further use.

Step 1.2: Retrieve Node's Genesis Block

1. Make an RPC call to the blockchain node to get the full genesis block.
2. Use the RPC method chain_getBlock with the obtained genesis block hash. //Ex; RPC call => "block = client.request("chain_getBlock", hash);"
3. Store the obtained genesis block for further use.

Step 2: Open the Database

1. Initialize the database connection Step 2.2: Check Database Populated Status
2. Query the database to retrieve its current height.
3. If the height is greater than 0, the database is already populated; proceed to additional checks.
4. If the height is 0, the database is not populated; proceed with initialization.

Step 2.3: Verify Genesis Block Matching (If Database Populated)

1. If the database is populated, retrieve the genesis block hash from the database for height 0.
2. Compare the obtained genesis hash with the expected genesis hash.
3. If they match, continue with database operations.
4. If they do not match, abort the database opening.

Step 2.4: Initialize Database with Genesis Block (If Database Not Populated)

1. If the database is not populated (height is 0), insert the expected genesis block hash into the BlockHashes table.
2. Insert the expected genesis block into the Blocks table.

The next big step is : Synchronizing Local Database with Node in UTXO-Based Blockchain:

Below is a step-by-step explanation of the process of synchronizing a local database with the database of a running node in a UTXO-based blockchain.

Synchronize() Function Overview The synchronize function is responsible for ensuring that the local database of a wallet stays in sync with the running node's blockchain. It follows a two-step process: checking for reorganizations of blocks(re-orgs) and then synchronizing forward with the node.

FYI "re-org," occurs when there is a change in the blockchain's structure due to a divergence in the consensus of the network. This can happen when two different blocks are proposed at the same block height, leading to a temporary fork in the blockchain.

Step 1: Check for Reorganizations :

1. Initialization:

• Obtain the current height of the local database (db) and set it as the starting point.
• Retrieve the block hash at the current height from both the local database and the node.
• Initialize variables for the loop.

1. Reorganization Check Loop:

• Loop backward from the current best height to the genesis block(height = height -1).
• Check if the local wallet hash matches the node hash at each height.
• If not, unapply the highest block in the local database and continue checking the ancestor blocks.
• Decrease the height by one i.e "height = height-1" and then again loop i.e step a.
• When a match is found, proceed to the next step.

Step2: Synchronize Forward with Node

1. Prepare for Forward Sync:

• Orphaned blocks have been discarded, so prepare variables for forward syncing.
• Orphaned blocks are blocks that were initially part of the blockchain but have been discarded or abandoned due to a reorganization in the blockchain.
• Orphaned blocks occur when there is a temporary fork in the blockchain, and some blocks are left without a valid continuation in the main chain.

1. Forward Sync Loop:

• Loop forward from the common ancestor's height.
• Retrieve the hash of the next block from the node.
• Fetch the entire block from the node using node_get_block RPC call.
• Apply the block to the local database using apply_block function --. I will explain the this func later.
• Continue until there are no more blocks to sync.

Step 3. How apply_block Function works: The apply_block function is responsible for applying a block to the local database.

1. Write/Store the block hash to the block_hashes table in the local database.=> Note this block hash table meant for storing the block hashes.
2. Write/Store the entire block to the blocks table in the local database. => Note this block table is meant for storing the blocks.
3. Iterate through each transaction in the block and apply them using apply_transaction() function.Let me explain in the next steps

Note: Transactions are also called extrinsic.

Step 4: How apply_transaction() works : The apply_transaction function is responsible for applying a single transaction to the local database.

1. Insert New UTXOs

• Transaction Hash Calculation: Calculate the hash of the transaction using BlakeTwo256.
• Iterate Through Outputs: a. Iterate through each output in the transaction. b. Filter outputs based on a provided filter function. c. Match UTXO Type and Apply: i. Match each output's type using output.payload.type_id. ii. Apply specific logic for each UTXO type. . If it's a Coin UTXO, call money realted apply_transaction() func. . If it's a Timestamp UTXO, call crate::timestamp apply_transaction() func. . If it's a Kitty UTXO, call kitty related apply_transaction() func. . If it's a TradableKitty UTXO, call tradable kitty related apply_transaction() func.

1. Spend All Inputs: Means consuming all the inputs which were earlier stored in the local db.

• Iterate Through Inputs: Iterate through each input in the transaction.
• Mark Inputs as Spent: a. Call spend_output function to mark each input as spent. b. Move the record from the unspent table to the spent table.

Specific UTXO Implementations based on piece :

Step 1: Coin UTXO Implementation - apply_transaction in Money module. Responsibility: Store new Coin UTXOs in the global unspent outputs table. Details:

1. Extract the amount and output reference from the Coin UTXO.
2. Match the verifier type to Sr25519Signature and store the Coin UTXO in the global unspent outputs table.
3. Here 'Sr25519Signature' should be same as owner of the wallet.

Step 2: Kitty UTXO Implementation - apply_transaction in Kitty module. Responsibility: Store new Kitty UTXOs in the local database. Details :

1. Extract the KittyData from the Kitty UTXO.
2. Match the verifier type to Sr25519Signature and store the Kitty UTXO in the local database.
3. Here 'Sr25519Signature' should be the same as the owner of the wallet.

Similarly, we should do it for other UTXOs also such as TradableKitty, Timestamp,etc.

Spending UTXO Implementation

This means using a previously unspent output in a transaction. When an output is spent, it means that it is used as an input in a new transaction, and the funds/entity associated with that output are transferred to a new recipient or set of recipients.

Unspent Transaction Outputs (UTXOs):

1. In a UTXO-based blockchain, each transaction produces one or more outputs that represent the newly created funds.
2. These outputs are initially considered unspent until they are used as inputs in a subsequent transaction.

Spending UTXO:

1. When a user initiates a new transaction, they reference one or more UTXOs as inputs.
2. These inputs are considered spent in the new transaction, and their values are transferred to new outputs.

Step1: spend_output() Mark an existing output as spent by moving it from the unspent table to the spent table.

Details of implementation:

1. Open the unspent and spent trees in the local database.
2. Remove the UTXO record from the unspent table. -> Indicating that it is no longer available for future transactions.
3. Insert the UTXO record into the spent table. -> For maintaining a historical record of spent UTXOs.

This step is necessary for the following purposes:

1. Tracking spent UTXOs is crucial for preventing double-spending, where the same funds are used in more than one transaction.
2. It allows the blockchain to maintain a clear history of transaction outputs and helps verify the validity of new transactions.

unapply_highest_block

The process of unapply_highest_block is part of handling a reorganization (re-org) scenario in the blockchain. In case there has been a re-org, meaning a change in the blockchain's history, this function is responsible for rolling back the local database to the previous state.

unapply_highest_block Function :

Step 1: Retrieve Information

1. Database Initialization:
2. Determine Best Height:
3. Retrieve Block Hash: Remove the block hash record at the best height from the wallet_block_hashes_tree table
4. Retrieve Block: Remove the block record using the obtained hash from the wallet_blocks_tree table.

Step 2: Unapply Transactions

1. Loop Through Transactions: Iterate through the transactions in reverse order from the block's extrinsics.
2. Unapply Transaction: For each transaction, call the unapply_transaction function to undo its effects in the local database.

Step 3: Result Return Unapplied Block: Return the unapplied block, which represents the state before the re-org.

unapply_transaction Function Overview The unapply_transaction function is responsible for undoing the effects of a transaction in the local database. This involves removing the outputs added by the transaction and marking the inputs as unspent.

1. Transaction Hash Calculation: Calculate the hash of the transaction. 2. Undo Outputs:

1. Iterate through the outputs of the transaction in reverse order.
2. For each output, call the appropriate function to undo the storage of that type of UTXO.

• For example, for Coin UTXOs, call unapply_transaction() for money(),kitty() and tradableKitty().

3. Undo Inputs:

1. Iterate through the inputs of the transaction.
2. Mark each input as unspent by calling the unspend_output function.

Specific UTXO Undo Implementations We need to implement the specific UTXO undo implementation.

1. Coin UTXO Undo Implementation - unapply_transaction() Responsibility: Undo the storage of Coin UTXOs in the global unspent outputs table.
2. Kitty UTXO Undo Implementation - unapply_transaction() Responsibility: Undo the storage of Kitty UTXOs in the local database.

Unspending UTXO Implementation - unspend_output() Responsibility: Mark an existing output as unspent by moving it from the spent table back to the unspent table.

Overall this is for the recovery or rollback process of db.

Let's see some important terms :

Re-Org

What is "re-org," occurs when there is a change in the blockchain's structure due to a divergence in the consensus of the network.

This can happen when two different blocks are proposed at the same block height, leading to a temporary fork in the blockchain.

Here's how reorganizations typically occur:

Forking Point:

At a particular block height, multiple nodes in the network may simultaneously propose different blocks as the next valid block.

Temporary Fork:

The network temporarily forks into two branches, each extending from the same block height.

Competing Blocks:

Miners or validators may be working on different blocks, and both blocks are considered valid by different portions of the network.

Consensus Resolution:

The network needs to reach a consensus to determine which block will be added to the blockchain, resolving the fork.

Reorganization:

The branch with less accumulated proof-of-work or stake is typically discarded, and the other branch becomes the main chain. The discarded blocks in the alternate branch are considered orphaned.

In the context of the provided Rust code and the synchronization process, the reorganization check involves comparing the block hashes between the local wallet's database and the blockchain node's database. The synchronization algorithm loops backward from the current best height, checking whether the wallet and node agree on the best block. If there is a divergence (i.e., the wallet's hash doesn't match the node's hash at a certain height), it indicates a reorganization.

During a reorganization, the synchronization process rolls back blocks in the local wallet's database until a common ancestor block is found. This ensures that the local database aligns with the blockchain maintained by the node. Once a common ancestor is identified, the synchronization process then proceeds to sync forward from that point to catch up with the node's blockchain.

Orphaned blocks

Orphaned blocks are blocks that were initially part of the blockchain but have been discarded or abandoned due to a reorganization in the blockchain.

Orphaned blocks occur when there is a temporary fork in the blockchain, and some blocks are left without a valid continuation in the main chain.

Here's how orphaned blocks typically occur:

Consensus Resolution:

The network needs to reach a consensus to determine which block will be added to the blockchain, resolving the fork.

Orphaned Blocks:

The branch with less accumulated proof-of-work or stake is typically discarded, and the blocks in that branch become orphaned. These orphaned blocks are no longer part of the main chain.

Orphaned blocks are a natural part of blockchain systems, and they represent a divergence in the consensus of the network. When a reorganization occurs, blocks that were once considered part of the blockchain are no longer part of the main chain. This situation is handled by nodes during the synchronization process, where they may need to roll back to a common ancestor block and then sync forward from that point to align with the newly established main chain.