Validate Bitcoin Transactions
HardPremium
Blockchains like Bitcoin use the UTXO (Unspent Transaction Outputs) model to track ownership of coins. In this model, each transaction consumes UTXOs as inputs and creates new UTXOs as outputs. However, there can be invalid transactions where:
- The
senderdoes not own the UTXO they're trying to spend. - The same UTXO has already been used as input in another transaction.
You're given the following tables:
transactionstable:transaction_id(unique identifier for each transaction)sender(address of the person initiating the transaction)timestamp(time when the transaction was created)
transaction_inputstable:input_id(unique identifier for each input within a transaction)transaction_id(foreign key referencing transactions)utxo_id(foreign key indicating which UTXO is being consumed by this input)
utxotable:utxo_id(unique identifier for the UTXO)address(owner of the UTXO)amount(amount of cryptocurrency represented by the UTXO)
Given these tables, write a SQL query to identify transactions that are potentially invalid based on the above conditions. Your output should have the following column: InvalidTransactionId.
- Using a CTE to Identify Non-owners:
- First, we used a CTE named
InvalidSendersto connect thetransactions,transaction_inputs, andutxotables. This allowed us to compare thesenderin thetransactionstable with theaddress(owner) in theutxotable. - By filtering out the entries where the sender doesn't match the UTXO owner, we identified the transactions where the sender isn't the actual owner of the UTXO they're trying to spend.
- First, we used a CTE named
- Spotting Double-spends with Aggregation:
- We're using the
ROW_NUMBER()window function to assign a number to each transaction that uses a particular UTXO, sorted by the timestamp. - Transactions with a row number greater than 1 for a particular UTXO are considered invalid, as they are attempts to double-spend after the first valid transaction.
- We're using the
- Combining the Results with UNION:
- To fetch the final list of invalid transaction IDs, we combined the results from both CTEs using a
UNION. This ensured that we captured all transactions that either involved a sender who wasn’t the UTXO's rightful owner or involved a UTXO that was used in multiple transactions.
- To fetch the final list of invalid transaction IDs, we combined the results from both CTEs using a
-- Using Common Table Expressions (CTEs) for clarity
WITH InvalidSenders AS (
SELECT t.transaction_id
FROM transactions t
JOIN transaction_inputs ti ON t.transaction_id = ti.transaction_id
JOIN utxo u ON ti.utxo_id = u.utxo_id
WHERE t.sender <> u.address
),
DoubleSpends AS (
SELECT ti.transaction_id, ti.utxo_id, ROW_NUMBER() OVER(PARTITION BY ti.utxo_id ORDER BY t.timestamp) AS rn
FROM transaction_inputs ti
JOIN transactions t ON t.transaction_id = ti.transaction_id
)
SELECT transaction_id AS InvalidTransactionId
FROM InvalidSenders
UNION
-- Filter out only those that are not the first transaction based on timestamp
SELECT transaction_id AS InvalidTransactionId
FROM DoubleSpends
WHERE rn > 1;
WITH CTE AS ( SELECT *, ROW_NUMBER()OVER(PARTITION BY utxo_id ORDER BY transaction_id) AS trx_rk FROM transactions JOIN transaction_inputs USING (transaction_id) JOIN utxo USING (utxo_id) ) SELECT transaction_id AS InvalidTransactionId FROM CTE WHERE sender!=address OR trx_rk > 1