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
v20100 has joined #bitcoin-wizards
<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...
<surae>
and i don't quite follow how your argument isn't a criticism of pools
<surae>
i think one good criticism of the idea is this
<gmaxwell>
surae: I gave that example too.
<gmaxwell>
"Or alternatively, you and sipa could collude by sharing your solutions and I will mine none of them."
<gmaxwell>
surae: bitcoin pools don't have this property.
<gmaxwell>
Bitcoin mining is progress free (at least on a single block basis)
<surae>
ah, i thought you were referring to collusion by this accumulated hashing concept
<sipa>
surae: in Bitcoin, a majority hashrate can collude
<gmaxwell>
Yes, via agrregate proof of work. But that isn't what bitcoin pools do.
<sipa>
but in a world where PoW has progress, the _highest_ hashrate can always win, even if it is not a majority
<gmaxwell>
or the highest collusion, 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
<bsm117532>
sipa: commitments are easy to add to anything.
tromp has quit [Remote host closed the connection]
<sipa>
bsm117532: not if you still need to show all the originals in order to prove their correctness :)
<sipa>
then you're back to an O(n) proof
<bsm117532>
Commitments are easy to aggregate ;-)
<bsm117532>
But yeah I see your point
<sipa>
anyway, have a look at the "proofs of proof of work" work if you're not familiar with it
<sipa>
(see what i did there? proofs proof, work work?)
<surae>
hat tip
<sipa>
surae: bitcoin mining has 0 progress
<bsm117532>
I'm familiar ;-)
<surae>
well, it's a coin flip, success or fail
<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>
yeah, that's what i was trying to get at
<surae>
if we were to design a PoW system that has a progression instead of these discrete jumps
<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.
<bsm117532>
smaller targets = more miners = more decentalization.
<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
<surae>
point being, I agree, the notion of progress breaks PoW pretty handily
rmwb has quit [Remote host closed the connection]
* bsm117532
finally gets gmaxwell's use of "progress"
<bsm117532>
And here I thought it was just the opposite of congress.
<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>
braids as in category theory, or braids as in something else?
<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...
<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...
gmaxwell has left #bitcoin-wizards [#bitcoin-wizards]
<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
ablug has quit [Quit: Connection closed for inactivity]
sipa has left #bitcoin-wizards [#bitcoin-wizards]
DCLXVI` has joined #bitcoin-wizards
metric_ has joined #bitcoin-wizards
metric has quit [Write error: Broken pipe]
DrNo has quit [Excess Flood]
cfields has quit [Quit: No Ping reply in 180 seconds.]
DrNo has joined #bitcoin-wizards
cfields has joined #bitcoin-wizards
dclxvi has quit [Ping timeout: 260 seconds]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
Aaronvan_ has quit [Ping timeout: 240 seconds]
rmwb has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 240 seconds]
Ylbam has quit [Quit: Connection closed for inactivity]
Dyaheon has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 246 seconds]
dabura667 has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
cyphase has quit [Quit: cyphase.com]
jtremback_____ has quit [Quit: Connection closed for inactivity]
cyphase has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 245 seconds]
harrymm has quit [Ping timeout: 240 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
v20100 has quit [Ping timeout: 255 seconds]
cluckj has quit [Ping timeout: 260 seconds]
harrymm has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
PaulCapestany has quit [Ping timeout: 240 seconds]
PaulCapestany has joined #bitcoin-wizards
pro has quit [Quit: Leaving]
priidu has quit [Ping timeout: 258 seconds]
ablug has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
tromp has joined #bitcoin-wizards
RubenSomsen has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
mkarrer has quit [Ping timeout: 240 seconds]
RubenSomsen has quit [Ping timeout: 240 seconds]
rmwb has quit [Remote host closed the connection]
RubenSomsen has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
Belkaar has quit [Ping timeout: 240 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
rmwb has quit [Ping timeout: 260 seconds]
RubenSomsen has quit [Ping timeout: 240 seconds]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
alferz has joined #bitcoin-wizards
TheSeven has quit [Ping timeout: 245 seconds]
TheSeven has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
alferz has quit [Ping timeout: 268 seconds]
rmwb has joined #bitcoin-wizards
rmwb has quit [Remote host closed the connection]
superkuh has quit [Remote host closed the connection]
superkuh has joined #bitcoin-wizards
Aranjedeath has quit [Quit: Three sheets to the wind]
harrymm has quit [Remote host closed the connection]
skeuomorf has quit [Ping timeout: 255 seconds]
tromp has quit [Remote host closed the connection]
Ylbam has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
skeuomorf has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 255 seconds]
kenshi84_ has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 245 seconds]
tromp has joined #bitcoin-wizards
Giszmo has quit [Quit: Leaving.]
tromp has quit [Ping timeout: 255 seconds]
coinsmurf has quit [Read error: Connection reset by peer]
BashCo has joined #bitcoin-wizards
priidu has quit [Ping timeout: 240 seconds]
priidu has joined #bitcoin-wizards
coinsmurf has joined #bitcoin-wizards
Guest67683 has quit [Ping timeout: 255 seconds]
rusty has quit [Ping timeout: 260 seconds]
bteitelb has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
goatturner has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 240 seconds]
skeuomorf has quit [Ping timeout: 258 seconds]
priidu has quit [Read error: Connection reset by peer]
priidu has joined #bitcoin-wizards
Guest73816 has joined #bitcoin-wizards
bteitelb has quit [Ping timeout: 260 seconds]
jannes has joined #bitcoin-wizards
thrmo has joined #bitcoin-wizards
mkarrer has joined #bitcoin-wizards
d9b4bef9 has quit [Remote host closed the connection]
d9b4bef9 has joined #bitcoin-wizards
vicenteH has joined #bitcoin-wizards
thrmo_ has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 272 seconds]
josephpoon has quit [Ping timeout: 258 seconds]
josephpoon has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
goatturneer has joined #bitcoin-wizards
ablug has quit [Quit: Connection closed for inactivity]
goatturner has quit [Ping timeout: 240 seconds]
Guyver2 has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
<stevenroose>
Did doge fork of Bitcoin before checklocktimeverify existed?
<stevenroose>
srry for off-topic
tromp has quit [Ping timeout: 240 seconds]
dabura667 has quit [Remote host closed the connection]
Aaronvan_ is now known as AaronvanW
btcdrak has quit [Quit: Connection closed for inactivity]
swoup has joined #bitcoin-wizards
swoup has quit [Changing host]
swoup has joined #bitcoin-wizards
btcdrak has joined #bitcoin-wizards
beatrootfarmer has joined #bitcoin-wizards
BashCo has quit [Ping timeout: 240 seconds]
goatturneer has quit [Ping timeout: 240 seconds]
NewLiberty has quit [Ping timeout: 246 seconds]
BashCo has joined #bitcoin-wizards
goatturneer has joined #bitcoin-wizards
beatrootfarmer has quit [Ping timeout: 255 seconds]
beatrootfarmer has joined #bitcoin-wizards
Noldorin has quit [Ping timeout: 260 seconds]
goatturneer has quit [Ping timeout: 240 seconds]
<bsm117532>
stevenroose: yes
<stevenroose>
bsm117532, so I guess they don't have it?
<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.
<bsm117532>
I worked on Doge a little bit, I know for sure they forked before CSV...
goatturneer has joined #bitcoin-wizards
<bsm117532>
Last commit to their repo is in 2015 and that's before CSV.
<bsm117532>
Why?
goatturner has joined #bitcoin-wizards
beatrootfarmer has quit [Ping timeout: 245 seconds]
beatrootfarmer has joined #bitcoin-wizards
priidu has quit [Ping timeout: 260 seconds]
goatturneer has quit [Ping timeout: 255 seconds]
v20100 has joined #bitcoin-wizards
goatturner has quit [Ping timeout: 255 seconds]
priidu has joined #bitcoin-wizards
blackwraith has joined #bitcoin-wizards
priidu has quit [Ping timeout: 240 seconds]
goatturneer has joined #bitcoin-wizards
RubenSomsen has joined #bitcoin-wizards
beatrootfarmer has quit [Ping timeout: 255 seconds]
beatrootfarmer has joined #bitcoin-wizards
goatturner has joined #bitcoin-wizards
goatturneer has quit [Ping timeout: 260 seconds]
beatrootfarmer has quit [Ping timeout: 272 seconds]
tromp has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 240 seconds]
AaronvanW has joined #bitcoin-wizards
airbreather has quit [Quit: Leaving]
airbreather has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
Alina-malina has quit [Excess Flood]
Alina-malina has joined #bitcoin-wizards
Alina-malina has quit [Changing host]
Alina-malina has joined #bitcoin-wizards
blackwraith has quit [Ping timeout: 240 seconds]
btcdrak has quit [Quit: Connection closed for inactivity]
str4d has quit [Ping timeout: 268 seconds]
jtimon has joined #bitcoin-wizards
goatturneer has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
beatrootfarmer has joined #bitcoin-wizards
goatturner has quit [Ping timeout: 272 seconds]
goatturneer has quit [Ping timeout: 255 seconds]
laurentmt has quit [Client Quit]
btcdrak has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
goatturneer has joined #bitcoin-wizards
beatrootfarmer has quit [Ping timeout: 255 seconds]
beatrootfarmer has joined #bitcoin-wizards
goatturneer has quit [Ping timeout: 260 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
boing has quit [Remote host closed the connection]
Giszmo has joined #bitcoin-wizards
<Taek42>
Picking which transctions to put in a block to get optimal revenue is an NP-hard problem
<Taek42>
but, you can write a linear time algorithm to get a bound on how far you are from the optimal situation
<bsm117532>
Uh...why? Just grab the subset with highest fees.
Taek42 is now known as Taek
<Taek>
bsm117532: it's the knapsack problem
<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>
because then you get to have more sets included overall
<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>
it's another centralization pressure on mining
<bsm117532>
It may be NP hard, but definitely tractable with modern hardware.
<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
<bsm117532>
That's small fish for optimization algorithms.
<Taek>
does bitcoin core do optimal transaction selection?
<Taek>
also, would there be a DoS you could set up if the wallet was programmed to do optimal selection?
<bsm117532>
Sure but that DoS can only be executed by submitting valid transactions.
<bsm117532>
A large pile of low-fee transactions would do it.
laurentmt has joined #bitcoin-wizards
Aranjedeath has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 260 seconds]
Dyaheon has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
thrmo_ is now known as thrmo
kmels has joined #bitcoin-wizards
jannes has quit [Quit: Leaving]
goatturneer has joined #bitcoin-wizards
beatrootfarmer has quit [Ping timeout: 258 seconds]
Lamby_ has joined #bitcoin-wizards
Lamby_ has left #bitcoin-wizards [#bitcoin-wizards]
v20100 has quit [Ping timeout: 255 seconds]
abpa has joined #bitcoin-wizards
beatrootfarmer has joined #bitcoin-wizards
goatturner has joined #bitcoin-wizards
goatturneer has quit [Ping timeout: 272 seconds]
<jnewbery>
transaction selection is also hard because it's nonlinear and multi-dimensional
beatrootfarmer has quit [Ping timeout: 255 seconds]
<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)
BashCo has quit [Ping timeout: 260 seconds]
<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...
boing has joined #bitcoin-wizards
boing has quit [Ping timeout: 260 seconds]
Belkaar has quit [Read error: Connection reset by peer]
BashCo has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
boing has joined #bitcoin-wizards
chjj has quit [Ping timeout: 240 seconds]
RubenSomsen has quit [Ping timeout: 255 seconds]
NewLiberty has quit [Ping timeout: 245 seconds]
chjj has joined #bitcoin-wizards
Noldorin has quit [Ping timeout: 255 seconds]
RubenSomsen has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
bteitelb has joined #bitcoin-wizards
smk has joined #bitcoin-wizards
vicenteH has quit [Ping timeout: 240 seconds]
laurentmt has joined #bitcoin-wizards
boing has quit []
Chris_Stewart_5 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 255 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
smk has quit [Ping timeout: 260 seconds]
smak has joined #bitcoin-wizards
RubenSomsen has quit [Ping timeout: 240 seconds]
kmels has quit [Ping timeout: 240 seconds]
smak is now known as smk
Dyaheon has quit [Ping timeout: 255 seconds]
Dyaheon has joined #bitcoin-wizards
kmels has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 255 seconds]
smk has quit [Ping timeout: 260 seconds]
<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)
<jnewbery>
Taek: exactly
<instagibbs>
Taek, standardness checks would likely make it not a concern, but it matters for consensus still
priidu has joined #bitcoin-wizards
Guyver2 has quit [Quit: :)]
PaulCapestany has quit [Quit: .]
PaulCapestany has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 255 seconds]
talmai has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 255 seconds]
talmai has quit [Quit: mining]
talmai has joined #bitcoin-wizards
blackwraith has joined #bitcoin-wizards
priidu has quit [Ping timeout: 245 seconds]
Chris_Stewart_5 has quit [Ping timeout: 255 seconds]
v20100 has joined #bitcoin-wizards
talmai has quit [Quit: mining]
blackwraith has quit [Ping timeout: 255 seconds]
jtimon has joined #bitcoin-wizards
Zaghie has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
talmai has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
Zaghie has quit [Quit: Zaghie]
Zaghie has joined #bitcoin-wizards
talmai has quit [Quit: mining]
skeuomorf has joined #bitcoin-wizards
kmels has quit [Ping timeout: 245 seconds]
talmai has joined #bitcoin-wizards
talmai has quit [Quit: mining]
harrymm has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 240 seconds]
altoz has quit [Remote host closed the connection]
altoz has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
jrayhawk_ has joined #bitcoin-wizards
Zaghie has quit [Quit: see ya next time]
Meeh has quit [Excess Flood]
kaalia has quit [Excess Flood]
Lightsword_ has joined #bitcoin-wizards
Lightsword has quit [Excess Flood]
jrayhawk has quit [Remote host closed the connection]
kaalia has joined #bitcoin-wizards
Meeh has joined #bitcoin-wizards
Lightsword_ is now known as Lightsword
tromp has quit [Remote host closed the connection]