13:19 UTC

< June 2017 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

- Console
- #amber
- #apicula
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #buildbot
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #lowempire
- #maemo-leste
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- ##moved_to_libera
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #openwrt-devel
- #panfrost
- ##panfrost-offtopic
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #river
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #stellar
- #stellar-dev
- ##stm32-rs
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #videocore
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja

<surae>
@gmaxwell Your 10,000 hash example: there is a third option, where you have 40h/s, and sipa and bsm117532 have 30 h/s, where sipa and bsm start a pool...

<gmaxwell>
"Or alternatively, you and sipa could collude by sharing your solutions and I will mine none of them."

<sipa>
but in a world where PoW has progress, the ___highest___ hashrate can always win, even if it is not a majority

<surae>
so, if you can make a continuous amount of progress, like a slider bar, i can see where you are going with that, and if the progress is discrete or atomic, you may as well be back to the usual block system

<sipa>
bsm117532: not if you still need to show all the originals in order to prove their correctness :)

<sipa>
surae: the amount of work you've done before has no effect on how long it will take you to create the next block

<surae>
then the smallest discrete jump would be miner's new "target," like blocks would normally be, but rewards would occur every few successes instead of after a single success.

<surae>
like halving, if you changed PoW to require two hashes that both satisfy a size requirement, you're still just flipping coins until a prescribed number of successes and then getting a reward

<bsm117532>
Well it seems I may get some time to work on braids again...and may be on the hunt for a PoW algorithm that makes sense for it...

<surae>
gmaxwell & sipa: the more precisely that hashrate determines the next block winner, the more often the largest miner wins, if hashrate ***completely*** determines the next block winner with no randomness, then largest miner always wins...

<bsm117532>
braids as in organizing blocks into a directed acyclic graph (blocks can have multiple parents) instead of a chain. https://scalingbitcoin.org/hongkong2015/presentations/DAY2/2_breaking_the_chain_1_mcelrath.pdf

<surae>
otoh, the less that hashrate determines next block winner, the more that smaller miners have a chance...

<surae>
and hey, guess what, the exponential distribution has maximal entropy, so we want blocks to arrive in a poisson process, and not only that but a large number of coin flips is well-approximated as a poisson process...

<bsm117532>
More simulation and analysis: https://www.reddit.com/r/btc/comments/4su1gf/braiding_the_blockchain_32_min_qa_we_cant_remove/

<surae>
which makes bitcoin's PoW impossible to improve, switching out hash functions or something silly like that can, at best, only improve how closely we can approximate the true block arrival rate as Poisson

<bsm117532>
I'd have to go look at their codebase...but CSV activated about 1y ago, and almost no altcoins have kept up with the furious pace of development of bitcoin core.

<Taek42>
but, you can write a linear time algorithm to get a bound on how far you are from the optimal situation

<Taek>
if you grab the subsets with the highest fees, you end up with this unused extra space at the end because the next fee-dense subset may not fit

<Taek>
so it may be in your best interest to drop a larger, more fee-dense transaction set in order to grab some smaller less fee dense transaction sets

<Taek>
the bound of course is the amount of space you have left at the end, multiplied by the density of most-dense set that doesn't fit

<Taek>
if you add a consensus rule (soft-fork) banning dependent sets above a certain size from being included on-chain, then you know there is a consensus-bound on how suboptimal one can be with a linear time algorithm

<Taek>
if the max size were 50,000 bytes, you know that the linear time algorithm is going to be within 5% at worst of the optimal algorithm

<Taek>
this means miners who can afford to do fancy/expensive solving will get at most a 5% advantage

<Taek>
today, they could get a much bigger advantage if there are lots of very large transaction sets with varying fee densities

<bsm117532>
Well it's an optimization problem with a constraint. That is NP-hard generally. But why bring that up?

<Taek>
I was thinking about miners that might deploy lots of hardware simply dedicated to picking the optimal set of transactions

<Taek>
the mempool can have tens of thousands of transactions. I guess I don't actually know how intractable or tractible it might be, but I was just assuming that it was intractible at that scale

<Taek>
also, would there be a DoS you could set up if the wallet was programmed to do optimal selection?

<jnewbery>
nonlinear because a block can contain transactions and their parents => the validity of a transaction in a block depends on which other transactions are included in that block

<jnewbery>
multi-dimensional because there are two constraints: block size (1MB) and block sigops (20000)

<surae>
for a CPU-only mining coin, I imagine transaction selection is a complete waste of time. each CPU cycle spent on optimizing selections is not spent on hashes, so it's very likely a miner's strategy would be maximized by just bundling the first selection of transactions they see... but with an ASIC or a GPU doing the mining, different story...

<Taek>
jnewbery: is the number of sigops low enough that it's a practical constraint? Or for any realistic set are you going to be well under the sigops limit?

<Taek>
I guess when thinking in terms of maliciously constructed transactions, you do need to consider the sigops limt

<jnewbery>
Taek: I believe it's not usually an issue. But it does mean that the transaction selection algorithm can't just maximize for fee/byte (otherwise someone could construct transactions that would cause miners to mine invalid blocks)