Bitcoin Forum
April 25, 2024, 08:16:53 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Function to determine if your UTXOs will allow for this specific transaction  (Read 94 times)
decent1984 (OP)
Newbie
*
Offline Offline

Activity: 6
Merit: 3


View Profile
July 06, 2021, 04:40:56 AM
Merited by HCP (2), Pmalek (1)
 #1

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.
1714033013
Hero Member
*
Offline Offline

Posts: 1714033013

View Profile Personal Message (Offline)

Ignore
1714033013
Reply with quote  #2

1714033013
Report to moderator
1714033013
Hero Member
*
Offline Offline

Posts: 1714033013

View Profile Personal Message (Offline)

Ignore
1714033013
Reply with quote  #2

1714033013
Report to moderator
1714033013
Hero Member
*
Offline Offline

Posts: 1714033013

View Profile Personal Message (Offline)

Ignore
1714033013
Reply with quote  #2

1714033013
Report to moderator
According to NIST and ECRYPT II, the cryptographic algorithms used in Bitcoin are expected to be strong until at least 2030. (After that, it will not be too difficult to transition to different algorithms.)
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1714033013
Hero Member
*
Offline Offline

Posts: 1714033013

View Profile Personal Message (Offline)

Ignore
1714033013
Reply with quote  #2

1714033013
Report to moderator
1714033013
Hero Member
*
Offline Offline

Posts: 1714033013

View Profile Personal Message (Offline)

Ignore
1714033013
Reply with quote  #2

1714033013
Report to moderator
1714033013
Hero Member
*
Offline Offline

Posts: 1714033013

View Profile Personal Message (Offline)

Ignore
1714033013
Reply with quote  #2

1714033013
Report to moderator
odolvlobo
Legendary
*
Offline Offline

Activity: 4298
Merit: 3208



View Profile
July 06, 2021, 04:56:07 AM
Last edit: July 06, 2021, 08:03:12 AM by odolvlobo
 #2

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.

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
ranochigo
Legendary
*
Offline Offline

Activity: 2954
Merit: 4163


View Profile
July 06, 2021, 05:01:29 AM
Last edit: July 06, 2021, 03:01:26 PM by ranochigo
 #3

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.  Tongue

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

Edited: Same mistake as above

.
.HUGE.
▄██████████▄▄
▄█████████████████▄
▄█████████████████████▄
▄███████████████████████▄
▄█████████████████████████▄
███████▌██▌▐██▐██▐████▄███
████▐██▐████▌██▌██▌██▌██
█████▀███▀███▀▐██▐██▐█████

▀█████████████████████████▀

▀███████████████████████▀

▀█████████████████████▀

▀█████████████████▀

▀██████████▀▀
█▀▀▀▀











█▄▄▄▄
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
.
CASINSPORTSBOOK
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀▀█











▄▄▄▄█
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8382



View Profile WWW
July 06, 2021, 05:05:52 AM
Merited by pooya87 (3), ABCbits (2), hosseinimr93 (1)
 #4

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.

The answer is fairly trivial: enumerate the permutations of all the outputs until you find a match.

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

Activity: 4298
Merit: 3208



View Profile
July 06, 2021, 08:07:41 AM
 #5

The answer is fairly trivial: enumerate the permutations of all the outputs until you find a match.
That would work but has factorial complexity, which is actually a problem on practical wallet sizes. More efficient is possible.

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

BTW, this is a variation of the Knapsack Problem.

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!