Topic: Function to determine if your UTXOs will allow for this specific transaction (Read 125 times)

I used the wrong term. It should be combinations, and that makes it 2^N, which is better than N!. But as you stated, optimizations are possible.

BTW, this is a variation of the Knapsack Problem.

This code does what you're asking for:

https://github.com/bitcoin/bitcoin/blob/master/src/wallet/coinselection.cpp#L21

(Actually, somewhat more-- not only does it bound the fee over-payment, but it finds solutions that pay at least a given feerate-- though it could be run with a feerate of 0 to give more of what you're asking for)

Bitcoin core will produce changeless outputs when it can... and it can pretty often for wallets with many inputs.


That would work but has factorial complexity, which is actually a problem on practical wallet sizes. More efficient is possible.

You'll probably want to determine the size of the transaction first[1]. Since there is only one output, size with respect to that is fixed, though can vary dependent on the kind of unlocking script you have. Eg. P2PKH outputs are bigger than P2WPKH output by 3 byte. The GitHub code that you should be able to find gives you the size of the various kinds of inputs (including the signature) and outputs.

-> Create the variables for the inputs and outputs to calculate the size.

Afterwhich, you can relate it to the fees that you're going to pay. The fee rates you're going to decide on will determine the kinds of outputs that you're able to use. By limiting the total fees below 1000 sat, deduce the range of acceptable transaction size based on your desired fee rates*. Next, run through the permutations combinations of the inputs (and a fixed output), determine one that'll result in 0.03BTC as the output after deducting the estimated fees. Note that the signature size can vary slightly so I'll leave a few satoshi for the fees to compensate for the margin of error.

*Strictly speaking, due to how vague the question is, you can choose a huge range of fees (at least 1sat/vbyte) or just use whatever is left after deducting 0.03BTC to be used as the fees. Since the question doesn't state whether the transaction has to be standard, just include a range of 0-1000 sat as the fees and permutate the value of the inputs.  

[1] https://jlopp.github.io/bitcoin-transaction-size-calculator/

Edited: Same mistake as above

There are no optimization requirements and no fee requirements beyond a max of 1000 sats. The answer is fairly trivial: enumerate the permutations combinations of the outputs until you find a match.

Edit: Oops. Wrong term.

I have been thinking about this problem given by a friend, any insights on getting started with this would be great,
I am a beginner in Python  but know JavaScript/PHP at a advanced level:

You are given a bunch of Bitcoin UTXOs of varying amounts that you are able to spend from your Bitcoin wallet. They are given to you sorted by amount. You want to pay someone 0.03 BTC with a fee of less than 1000 sats AND not generate any change. Write a function to determine if your UTXOs will allow for this specific transaction. Remember, you may use more than 1 input.



Thanks.