3 ms·

Bitcoin Mining is NP-hard (2014)

deleted 9y ago
[deleted]
tromp 9y ago
Many miners require a minimum fee-per-byte for including a transaction in their memory pool of transactions awaiting inclusion in a block. So they would for instance ignore a transaction of B bytes if its fee is less than B * 100 satoshi (at 10^-8 BTC, the smallest unit of account). Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears (still leaving the NP-hard conflict resolution problem).
- TD-Linux 9y ago
  The conflict resolution problem was traditionally solved just by taking the first seen valid transaction and disregarding any subsequent conflicting transactions. That of course is not necessarily profit maximizing, so current implementations generally allow replacing the transaction as long as it pays an incrementally higher fee than the one it's replacing (the increment usually being the same as the minimum fee you mentioned). Non-mining nodes have to implement a similar policy, as it's also used for preventing DoS on the P2P network.
- Retric 9y ago
  Considering how centralized Bitcoin has become minors are incentivized to raise the threshold for inclusion in a block even if they make less per block in the short term artificial scarcity can become extremely valuable in the mid term.
- nullc 9y ago
  > Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available: https://people.xiph.org/~greg/temp/fee_avail4.png https://people.xiph.org/~greg/temp/fee_avail4.png which is important for long term stability: https://medium.com/@bergealex4/bitcoin-is-unstable-without-the-block-size-size-limit-70db07070a54 https://medium.com/@bergealex4/bitcoin-is-unstable-without-t... > and the knapsack problem disappears Just cutting off low fee TX is a worse result than even the most approximate knapsack solver you could use. :) (Take transactions in order of fee per unit-limit, skip ones that won't fit, until you're full or you've skipped too many times sequentially-- which is what we do... with a too many threshold of a few thousand IIRC) The reason for the floor is primarily to avoid wasting resources trying to verify transactions which are never going to confirm. The floor rate used in the network today is 1e-8 BTC per byte, though it automatically goes up if the backlog of transactions gets large (over about 150MB of transactions). That limiting works by nodes keeping 150MB of transactions and if they gain more they drop the lowest feerate transaction and set their minimum to that value. The minimum then decays back to 1e-8 BTC/byte at a speed which depends on how much below the limit the node is... [ these parameters don't need to be completely consistent in the network, nodes will tell their peers what fee levels they're willing to process] > NP-hard conflict resolution problem That is ignored in Bitcoin implementations today because double spends are rare, interesting ones are extra rare with complex dependency graphs, and there is a social good to behaving in simple an explicable ways.
nullc 9y ago
> The current default Bitcoin implementation makes no effort to solve or even really approximately this problem I think this was somewhat out of date even when it was written. :( When I've sampled it before the solver in Bitcoin reliably produces results which are very close to the best results that an external MILP solver produces... and since a year and a half ago it even considers dependencies in that analysis. The knapsack part of the problem is not that impacting because a block is composed of thousands of transactions, which are mostly very small compared to the block size... and for the lower fee transaction the slope of the fees per unit for the available options is not very high. Basically, so long as you get the high fee transactions it usually doesn't much matter if you fail to eek the last few bytes out of a block.
- Ar-Curunir 9y ago
  I'm sure you know this, but NP-hardness results only matter for worst-case instances. Even if Bitcoin's algorithm is roughly close to optimal on real-world instances, it doesn't mean somebody won't be able to generate a series of transactions that cause the algorithm to exhibit worst-case behaviour. Also, the NP-hardness results would apply even if the Bitcoin algorithm is updated.
  - replies_to_all 9y ago
    Nullc is CTO of a company trying to take control over Bitcoin development by pushing an update they call "SegWitness". Nullc's gamble is that if they can get their code into Bitcoin their company, Blockstream, will be able to sell their "expertise". Honestly, at this point, they are just a marketing company with a single product they are desperate to push at any cost. If nullc does not seem to "understand" something, that is often why, he has incentive to see the system fail to upgrade on its own, selling their segwitness as the "solution" to a non-existent problem. Granted, it is hard to see IPO like profits working on an "open-source" project.
    - indolering 9y ago
      Can we please leave the cryptocurrency drama out of this? Every time a cryptocurrency post is submitted to HN the discussions get overtaken by political bickering.
replies_to_all 9y ago
> That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available... Are you insane, Sir? Right now (Thursday) people are waiting 6+ hours for a TX and are forced to use TX accelerators just to get a TX through [1]. Average cost per TX is over $2.00 right now [2], BECAUSE of the backlog. Nullc, you are a jackass with a financial incentive to see Bitcoin fail to scale on-chain. I should hope no one here would fall for your pathetic attempt to skew the real issues of raising the block size. Please troll elsewhere, Sir. [1] https://www.reddit.com/r/btc/comments/66l192/transaction_stuck_for_already_6_damned_hours/ https://www.reddit.com/r/btc/comments/66l192/transaction_stu... [2] https://supload.com/H1oAvdIRe https://supload.com/H1oAvdIRe
- nullc 9y ago
  > Average cost per TX is over $2.00 right now [2] Thanks for demonstrating that you're probably not even a Bitcoin user at all. (The median transaction size is 226 bytes, -- and so you're using a figure per kB-- so equal to 4.5 txn.) (doubly ironic to see you complain about segwit in one breath and transaction fees in the next) > people are waiting 6+ hours for a TX and are forced You can choose how long you'd like to wait in exchange for more or less fees-- this how the system works, no one is forced to do anything. > with a financial incentive to see Bitcoin fail I have large incentives to see Bitcoin be successful-- but can you articulate any way that I can profit from failure? I'm here writing to you with a well known identity, upfront about what I work on and what I think is important. If you're angry that other people won't rewrite Bitcoin's rules to suit whatever agenda you have-- that sounds like a personal problem. It certainly isn't my problem.
- Dylan16807 9y ago
  The hell are you talking about? He says there's a backlog, you say there's a backlog, where's the disagreement other than your unrelated anger toward him?
- dang 9y ago
  We've banned this account for breaking the HN guidelines. Doing this will eventually get your main account banned as well, so please stop. We detached this subthread from https://news.ycombinator.com/item?id=14162653 https://news.ycombinator.com/item?id=14162653 and marked it off-topic.
2win 9y ago
Free Instant 1$Bitcoin+Gift card codes For Free [b]You are Interested: Go to https://goo.gl/k5uMPS https://goo.gl/k5uMPS Bonus:For First 1000people that will signup.They'll send to you where Earn $25Gift card codes free.
2win 9y ago
Free Instant 1$Bitcoin+Gift card codes For Free [b]You are Interested: Go to https://goo.gl/k5uMPS https://goo.gl/k5uMPS Bonus:For First 1000people that will signup.They'll send to you where Earn $25Gift card codes free.

deleted 9y ago

[deleted]

Many miners require a minimum fee-per-byte for including a transaction in their memory pool of transactions awaiting inclusion in a block. So they would for instance ignore a transaction of B bytes if its fee is less than B * 100 satoshi (at 10^-8 BTC, the smallest unit of account). Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears (still leaving the NP-hard conflict resolution problem).

TD-Linux 9y ago
The conflict resolution problem was traditionally solved just by taking the first seen valid transaction and disregarding any subsequent conflicting transactions. That of course is not necessarily profit maximizing, so current implementations generally allow replacing the transaction as long as it pays an incrementally higher fee than the one it's replacing (the increment usually being the same as the minimum fee you mentioned). Non-mining nodes have to implement a similar policy, as it's also used for preventing DoS on the P2P network.
Retric 9y ago
Considering how centralized Bitcoin has become minors are incentivized to raise the threshold for inclusion in a block even if they make less per block in the short term artificial scarcity can become extremely valuable in the mid term.
nullc 9y ago
> Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available: https://people.xiph.org/~greg/temp/fee_avail4.png https://people.xiph.org/~greg/temp/fee_avail4.png which is important for long term stability: https://medium.com/@bergealex4/bitcoin-is-unstable-without-the-block-size-size-limit-70db07070a54 https://medium.com/@bergealex4/bitcoin-is-unstable-without-t... > and the knapsack problem disappears Just cutting off low fee TX is a worse result than even the most approximate knapsack solver you could use. :) (Take transactions in order of fee per unit-limit, skip ones that won't fit, until you're full or you've skipped too many times sequentially-- which is what we do... with a too many threshold of a few thousand IIRC) The reason for the floor is primarily to avoid wasting resources trying to verify transactions which are never going to confirm. The floor rate used in the network today is 1e-8 BTC per byte, though it automatically goes up if the backlog of transactions gets large (over about 150MB of transactions). That limiting works by nodes keeping 150MB of transactions and if they gain more they drop the lowest feerate transaction and set their minimum to that value. The minimum then decays back to 1e-8 BTC/byte at a speed which depends on how much below the limit the node is... [ these parameters don't need to be completely consistent in the network, nodes will tell their peers what fee levels they're willing to process] > NP-hard conflict resolution problem That is ignored in Bitcoin implementations today because double spends are rare, interesting ones are extra rare with complex dependency graphs, and there is a social good to behaving in simple an explicable ways.

nullc 9y ago

> The current default Bitcoin implementation makes no effort to solve or even really approximately this problem I think this was somewhat out of date even when it was written. :( When I've sampled it before the solver in Bitcoin reliably produces results which are very close to the best results that an external MILP solver produces... and since a year and a half ago it even considers dependencies in that analysis. The knapsack part of the problem is not that impacting because a block is composed of thousands of transactions, which are mostly very small compared to the block size... and for the lower fee transaction the slope of the fees per unit for the available options is not very high. Basically, so long as you get the high fee transactions it usually doesn't much matter if you fail to eek the last few bytes out of a block.

Ar-Curunir 9y ago
I'm sure you know this, but NP-hardness results only matter for worst-case instances. Even if Bitcoin's algorithm is roughly close to optimal on real-world instances, it doesn't mean somebody won't be able to generate a series of transactions that cause the algorithm to exhibit worst-case behaviour. Also, the NP-hardness results would apply even if the Bitcoin algorithm is updated.
- replies_to_all 9y ago
  Nullc is CTO of a company trying to take control over Bitcoin development by pushing an update they call "SegWitness". Nullc's gamble is that if they can get their code into Bitcoin their company, Blockstream, will be able to sell their "expertise". Honestly, at this point, they are just a marketing company with a single product they are desperate to push at any cost. If nullc does not seem to "understand" something, that is often why, he has incentive to see the system fail to upgrade on its own, selling their segwitness as the "solution" to a non-existent problem. Granted, it is hard to see IPO like profits working on an "open-source" project.
  - indolering 9y ago
    Can we please leave the cryptocurrency drama out of this? Every time a cryptocurrency post is submitted to HN the discussions get overtaken by political bickering.

replies_to_all 9y ago

> That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available... Are you insane, Sir? Right now (Thursday) people are waiting 6+ hours for a TX and are forced to use TX accelerators just to get a TX through [1]. Average cost per TX is over $2.00 right now [2], BECAUSE of the backlog. Nullc, you are a jackass with a financial incentive to see Bitcoin fail to scale on-chain. I should hope no one here would fall for your pathetic attempt to skew the real issues of raising the block size. Please troll elsewhere, Sir. [1] https://www.reddit.com/r/btc/comments/66l192/transaction_stuck_for_already_6_damned_hours/ https://www.reddit.com/r/btc/comments/66l192/transaction_stu... [2] https://supload.com/H1oAvdIRe https://supload.com/H1oAvdIRe

nullc 9y ago
> Average cost per TX is over $2.00 right now [2] Thanks for demonstrating that you're probably not even a Bitcoin user at all. (The median transaction size is 226 bytes, -- and so you're using a figure per kB-- so equal to 4.5 txn.) (doubly ironic to see you complain about segwit in one breath and transaction fees in the next) > people are waiting 6+ hours for a TX and are forced You can choose how long you'd like to wait in exchange for more or less fees-- this how the system works, no one is forced to do anything. > with a financial incentive to see Bitcoin fail I have large incentives to see Bitcoin be successful-- but can you articulate any way that I can profit from failure? I'm here writing to you with a well known identity, upfront about what I work on and what I think is important. If you're angry that other people won't rewrite Bitcoin's rules to suit whatever agenda you have-- that sounds like a personal problem. It certainly isn't my problem.
Dylan16807 9y ago
The hell are you talking about? He says there's a backlog, you say there's a backlog, where's the disagreement other than your unrelated anger toward him?
dang 9y ago
We've banned this account for breaking the HN guidelines. Doing this will eventually get your main account banned as well, so please stop. We detached this subthread from https://news.ycombinator.com/item?id=14162653 https://news.ycombinator.com/item?id=14162653 and marked it off-topic.

2win 9y ago

Free Instant 1$Bitcoin+Gift card codes For Free [b]You are Interested: Go to https://goo.gl/k5uMPS https://goo.gl/k5uMPS Bonus:For First 1000people that will signup.They'll send to you where Earn $25Gift card codes free.

2win 9y ago