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
Noldorin has quit [Ping timeout: 255 seconds]
Guyver2 has quit [Read error: Connection reset by peer]
deusexbeer has quit [Quit: Konversation terminated!]
priidu has quit [Ping timeout: 240 seconds]
jtimon has quit [Ping timeout: 260 seconds]
rmwb has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
dabura667 has joined #bitcoin-wizards
chjj has quit [Ping timeout: 255 seconds]
itsme has joined #bitcoin-wizards
DougieBot5000 has quit [Quit: Leaving]
jtimon has quit [Remote host closed the connection]
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
coinsmurf has quit [Ping timeout: 240 seconds]
MaxSan has quit [Quit: Leaving.]
rmwb has joined #bitcoin-wizards
coinsmurf has joined #bitcoin-wizards
DigiByteDev has joined #bitcoin-wizards
coinsmurf has quit [Ping timeout: 268 seconds]
mn3monic has joined #bitcoin-wizards
mn3monic has joined #bitcoin-wizards
mn3monic has quit [Changing host]
bedeho has joined #bitcoin-wizards
[7] has quit [Disconnected by services]
TheSeven has joined #bitcoin-wizards
DigiByteDev has quit [Quit: DigiByteDev]
Dyaheon has quit [Ping timeout: 255 seconds]
afk11 has quit [Ping timeout: 248 seconds]
Dyaheon has joined #bitcoin-wizards
afk11 has joined #bitcoin-wizards
matozoid has joined #bitcoin-wizards
mn3monic has quit [Excess Flood]
mn3monic has joined #bitcoin-wizards
<runeks>
sipa: that makes sense, since the further we get into a chain, the larger the UTXO set, so I would assume that the lookup/update operations become increasingly expensive. Is this the primary performance bottleneck of UTXO DB management -- that the UTXO set grows, and thus the duration of the operations on it? Or is it just because it's updated sequentially, i.e. one transaction at a time is "folded" into the UTXO set?
<sipa>
larger utxo set = slower operations on it
<sipa>
we heavily cache the active parts of the set in memore, but for optimal speed you need several GB cache already
<sipa>
there are some proposals that remove or reduce the load of utxo management from full nodes
<sipa>
and replace them with wallet generated proofs of unspentness
<sipa>
for example petertodd's txo mmr, or bram cohen's bitfield
<runeks>
I'm wondering if we could gain a speedup in this area if we used a temporary data structure for the UTXO set which allows negative balances, meaning that if an input redeems an output not in the UTXO set, it's added to this temporary UTXO set with a negative balance. Then we chop up the chain in <num_cores> pieces, have each core produce a temporary UTXO set of this nature, and finish off by merging these temporary UTXO
<runeks>
sets, which should end up with all the negative balances being cancelled out by a positive one (or the chain is invalid).
<sipa>
you can't validate a script without looking up the output
<sipa>
but perhaps the whole thing could be delayed
<runeks>
sipa: everything we can't validate right now would be deferred until we merge temporary UTXO sets
<sipa>
that sounds like ot could theoretically give some improvement
<sipa>
but not so much... you can get the same effect by using a db engine that supports multiple asynchronous queries
<sipa>
the idea of removing the concern of utxo sets from full nodes sounds far more appealing to mr
coinsmurf has joined #bitcoin-wizards
<runeks>
I'll have to read up on that
matozoid has quit [Ping timeout: 268 seconds]
<runeks>
Would that require a change in the protocol?
<sipa>
yes
<sipa>
proofs need to be sent along with transactions
<sipa>
and blocks
<runeks>
Ok, I see. I guess I'm mostly interested in speed-ups not requiring protocol changes.
matozoid has joined #bitcoin-wizards
<sipa>
haha, those are certainly less invasive
<sipa>
but the potential impact is also much smaller
<sipa>
protocol change here btw does not mean consensus change
Giszmo has quit [Quit: Leaving.]
<runeks>
I guess the speedup would depend on how many cores you have available. Although, the temporary UTXO sets, which would need to be merged, would keep increasing in size, until you have a merge operation with roughly two halves of the UTXO set. So here, too, performance degrades as we get closer to a final UTXO set.
<runeks>
So are we walking a change to the P2P protocol only?
<runeks>
*talking
<sipa>
yes
<sipa>
an invasive one, though
<sipa>
and a change to wallet software, eventually
<runeks>
Oh ok. That's much less of a problem.
<sipa>
and they come with big tradeoffs
str4d has joined #bitcoin-wizards
<sipa>
transactions (on P2P) would become significantly bigger
<runeks>
Hmm, I see. That's unfortunate. As far as I can see, the broadcast-all-to-all nature of the P2P network is Bitcoin's primary bottleneck.
<sipa>
bandwidth usage is really not that high
ryan-c has quit [Quit: quitting]
<sipa>
a non-serving bitcoin full node just needs a few kb/s
<sipa>
(after IBD)
<runeks>
I mean, if 1KB/s of transaction data needs to be spread out between 10,000 nodes, that's 10MB/s for
<runeks>
all nodes cumulatively.
<sipa>
yeah
rmwb has quit [Remote host closed the connection]
<runeks>
Also, with regards to "you can get the same effect by using a db engine that supports multiple asynchronous queries", as far as I can see, this isn't possible unless each entry in the UTXO set has a monotonically increasing counter (e.g. <32_bit_block_num+32_bit_tx_num_in_block>), such that an output can only cancel out an input if it appears in an earlier tx (an output can only cancel out a negative-balance entry in
<runeks>
the UTXO set if the output's counter is less than that of the negative-balance UTXO entry).
<sipa>
instead of merging the sets, you just issue an asynchronous query in a single set
<sipa>
and continue prcocessing when it comes back
<sipa>
that should be just as fast, with lower latency
<sipa>
the advantage of merging sets is that it's linear in time
<sipa>
but the disadvantage is that most of the time you're not using your hardware at all
<runeks>
sipa: but queries need to be handled in-order, such that only an output that was added earlier can be cancelled out by an input
<sipa>
yes?
<sipa>
the spend only happen after the send
<runeks>
sipa: How can we make sure queries are handled in-order unless each UTXO entry contains a counter?
<sipa>
i don't understand
<sipa>
the blockchai is the order
<sipa>
spending a utxo before it is created is illegal
<runeks>
Right, but the supposed speedup is from parallelizing UTXO operations. And then we lose the ordering.
<sipa>
do a quick pass for finding utxos spent within the block itself
<sipa>
anything else should also be created by an earlier block
<sipa>
also, parallellizing utxo sets is not that hard
<sipa>
just keep 256 parallel caches based on the first 8 bits of the txid
<sipa>
the likelyhood of needing to modify two of them concurrently is low
<sipa>
even when proxessing on multiple threads
ryan-c has joined #bitcoin-wizards
* sipa
zzz
Ylbam has joined #bitcoin-wizards
<runeks>
You can't modify the UTXO set in parallel unless each entry in it describes when the entry in question appeared in the blockchain.
<runeks>
It's the same with all parallel databases, I believe: each operation needs a counter/timestamp such that only an "update(x) *after* create(x)" works, as opposed to "create(x) after update(x)".
<runeks>
I believe most parallel DBs use a monotonically increasing counter, while a DB like Google Spanner uses an absolute timestamp from an atomic clock which is synchronized between all nodes. For Bitcoin this counter could be a 64 bit word, where the most significant 32 bits is the block count, and least significant 32 bits is tx_number_within_block.
bitbit has quit [Ping timeout: 260 seconds]
<runeks>
Using a strategy like this we can, essentially, separate each tx from its containing block, and fold them in parallel into the UTXO set, since the counter (for each tx) now makes sure that only earlier outputs can be redeemed by later inputs, and not the other way around.
<sipa>
well, i'm still talking about a model where you fully process one block before moiving on to the next
<sipa>
and utxos are incredibly easy structures
<sipa>
they're created once, typically looked up once or twice, and deleted
phayd has joined #bitcoin-wizards
<sipa>
there's no sequencing of operations needed apart from making sure the spend hapoens after the creation
<sipa>
the in-memory cache in bitcoin core takes advantage of that: utxos that are created and spent before a disk flush happens are just deleted and never hit disk at all
thrmo has joined #bitcoin-wizards
<sipa>
and parallellizing is not hard with parallel caches
<sipa>
just not implememted
<sipa>
oh... you really need to make sure a block is valid as soon as possible in steady state
<sipa>
otherwise you can't processing new mempool txn, which is essential for mini g
<sipa>
in IBD some parallel processing with higher throughput but worse latency may make sense
<runeks>
To be clear, I'm only talking about IBD, where we have a huge, sequential list of transactions that need to be processed in-order. But it may not make sense, performance-wise, unless we have much more than 4-8 cores. So that would entail either waiting for many-core CPUs, or needing the ability to schedule it onto multiple VMs.
chjj has quit [Ping timeout: 260 seconds]
matozoid_ has quit [Read error: Connection reset by peer]
matozoid has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 260 seconds]
matozoid has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
chaosdav has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
CubicEarth has joined #bitcoin-wizards
chjj has quit [Ping timeout: 240 seconds]
AaronvanW has quit [Ping timeout: 246 seconds]
Aaronvan_ is now known as AaronvanW
CubicEarth has quit []
chjj has joined #bitcoin-wizards
dabura667 has quit [Remote host closed the connection]
jcluck has joined #bitcoin-wizards
cluckj has quit [Ping timeout: 240 seconds]
brand0 has quit [Ping timeout: 246 seconds]
irc_bot has quit [Ping timeout: 240 seconds]
matozoid has joined #bitcoin-wizards
brand0 has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 240 seconds]
Dyaheon has joined #bitcoin-wizards
chjj has quit [Ping timeout: 240 seconds]
rmwb has quit [Ping timeout: 246 seconds]
chjj has joined #bitcoin-wizards
matozoid has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
matozoid has joined #bitcoin-wizards
augoeides[m] has quit [Ping timeout: 264 seconds]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
augoeides[m] has joined #bitcoin-wizards
sdaftuar_ is now known as sdaftuar
sdaftuar has quit [Changing host]
sdaftuar has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
rmwb has joined #bitcoin-wizards
matozoid has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
Guyver2 has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
matozoid has joined #bitcoin-wizards
matozoid has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
matozoid has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 255 seconds]
Aaronvan_ has joined #bitcoin-wizards
pro has quit [Quit: Leaving]
AaronvanW has quit [Ping timeout: 246 seconds]
Aaronvan_ has quit [Ping timeout: 240 seconds]
rmwb has joined #bitcoin-wizards
DrNo has quit [Ping timeout: 268 seconds]
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
DrNo has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 260 seconds]
_whitelogger has joined #bitcoin-wizards
matozoid has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
rmwb has quit [Ping timeout: 258 seconds]
deusexbeer has quit [Quit: Konversation terminated!]
Chris_Stewart_5 has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 255 seconds]
Dyaheon has joined #bitcoin-wizards
Aaronvan_ has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
pro has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 240 seconds]
MaxSan has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
str4d has quit [Quit: Leaving]
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
Aaronvan_ is now known as AaronvanW_
AaronvanW_ has quit [Remote host closed the connection]
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 240 seconds]
rmwb has quit [Ping timeout: 255 seconds]
Aaronvan_ is now known as AaronvanW
marcoagner has quit [Ping timeout: 255 seconds]
mn3monic has joined #bitcoin-wizards
marcoagner has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
bedeho has joined #bitcoin-wizards
marcoagner has quit [Ping timeout: 240 seconds]
bedeho has quit [Ping timeout: 240 seconds]
marcoagner has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
chjj has quit [Ping timeout: 240 seconds]
rmwb has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
chjj has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
abpa has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
JackH has quit [Ping timeout: 258 seconds]
kmels has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
bitbit has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 240 seconds]
Dyaheon has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
paveljanik has joined #bitcoin-wizards
paveljanik has joined #bitcoin-wizards
paveljanik has quit [Changing host]
chjj has quit [Ping timeout: 255 seconds]
MaxSan has quit [Quit: Leaving.]
bitbit has quit [Ping timeout: 260 seconds]
chjj has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
MaxSan has joined #bitcoin-wizards
PaulCape_ has quit [Quit: .]
PaulCapestany has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 240 seconds]
DougieBot5000_ has joined #bitcoin-wizards
vicenteH` has joined #bitcoin-wizards
MaxSan has quit [Ping timeout: 240 seconds]
Muis_ has joined #bitcoin-wizards
robmyers_ has joined #bitcoin-wizards
marcoagner has quit [Ping timeout: 240 seconds]
ibrightly_ has joined #bitcoin-wizards
bitjedi_ has joined #bitcoin-wizards
marcoagner has joined #bitcoin-wizards
davec_ has joined #bitcoin-wizards
thom_ has joined #bitcoin-wizards
swoup- has joined #bitcoin-wizards
thrasher`` has joined #bitcoin-wizards
Yogh_ has joined #bitcoin-wizards
yongu_ has joined #bitcoin-wizards
BlueMatt_ has joined #bitcoin-wizards
DougieBot5000 has quit [*.net *.split]
Yogh has quit [*.net *.split]
qpm has quit [*.net *.split]
nanotube has quit [*.net *.split]
thom has quit [*.net *.split]
ibrightly has quit [*.net *.split]
bitjedi has quit [*.net *.split]
thrasher` has quit [*.net *.split]
Muis has quit [*.net *.split]
herzmeister[m] has quit [*.net *.split]
harding has quit [*.net *.split]
mol has quit [*.net *.split]
davec has quit [*.net *.split]
schmidty has quit [*.net *.split]
vicenteH has quit [*.net *.split]
ensign has quit [*.net *.split]
robmyers has quit [*.net *.split]
baffo32 has quit [*.net *.split]
mryandao has quit [*.net *.split]
renlord has quit [*.net *.split]
swoup has quit [*.net *.split]
yongu has quit [*.net *.split]
leonidaz0r has quit [*.net *.split]
BlueMatt has quit [*.net *.split]
Muis_ is now known as Muis
bitjedi_ is now known as bitjedi
ibrightly_ is now known as ibrightly
mryandao- has joined #bitcoin-wizards
robmyers_ is now known as robmyers
renlord has joined #bitcoin-wizards
mol has joined #bitcoin-wizards
nanotube has joined #bitcoin-wizards
harding has joined #bitcoin-wizards
leonidaz0r has joined #bitcoin-wizards
BlueMatt_ is now known as BlueMatt
BlueMatt has joined #bitcoin-wizards
BlueMatt has quit [Changing host]
herzmeister[m] has joined #bitcoin-wizards
mn3monic has joined #bitcoin-wizards
mn3monic has joined #bitcoin-wizards
mn3monic has quit [Changing host]
ensign has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 240 seconds]
MaxSan has joined #bitcoin-wizards
baffo32 has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
crossing-styx has joined #bitcoin-wizards
mn3monic has joined #bitcoin-wizards
bedeho has quit [Remote host closed the connection]
jcluck is now known as cluckj
mn3monic has quit [Ping timeout: 268 seconds]
mn3monic has joined #bitcoin-wizards
airbreather has quit [Ping timeout: 240 seconds]
bedeho has joined #bitcoin-wizards
deusexbeer has joined #bitcoin-wizards
brianhoffman has quit [Ping timeout: 246 seconds]
Dyaheon has quit [Ping timeout: 240 seconds]
brianhoffman has joined #bitcoin-wizards
Dyaheon has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
chjj has quit [Ping timeout: 246 seconds]
chjj has joined #bitcoin-wizards
priidu has quit [Ping timeout: 268 seconds]
priidu has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 258 seconds]
smk has joined #bitcoin-wizards
coinsmurf has quit []
bedeho has quit [Remote host closed the connection]
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 255 seconds]
Giszmo has joined #bitcoin-wizards
bjorn[m] has quit [*.net *.split]
yoleaux has quit [*.net *.split]
teslax has quit [*.net *.split]
execute has quit [*.net *.split]
aem has quit [*.net *.split]
luke-jr has quit [*.net *.split]
stiell has quit [*.net *.split]
aj has quit [*.net *.split]
jeremyrubin has quit [*.net *.split]
nephyrin has quit [*.net *.split]
jcorgan has quit [*.net *.split]
rasengan has quit [*.net *.split]
luke-jr has joined #bitcoin-wizards
jeremyru1in has joined #bitcoin-wizards
aj has joined #bitcoin-wizards
nephyrin has joined #bitcoin-wizards
rasengan has joined #bitcoin-wizards
stiell has joined #bitcoin-wizards
aem has joined #bitcoin-wizards
Guest31352 has joined #bitcoin-wizards
smk has quit [Ping timeout: 260 seconds]
jcorgan has joined #bitcoin-wizards
bjorn[m] has joined #bitcoin-wizards
yoleaux has joined #bitcoin-wizards
Dyaheon has quit [Ping timeout: 240 seconds]
Dyaheon has joined #bitcoin-wizards
yoleaux has quit [*.net *.split]
yoleaux has joined #bitcoin-wizards
Aaronvan_ has quit [Ping timeout: 240 seconds]
Chris_Stewart_5 has quit [Ping timeout: 246 seconds]
AaronvanW has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
str4d has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
marcoagner has quit [Ping timeout: 260 seconds]
bedeho has quit [Ping timeout: 258 seconds]
crossing-styx has quit [Ping timeout: 240 seconds]
Guyver2 has quit [Quit: :)]
rmwb has quit [Ping timeout: 240 seconds]
marcoagner has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
crossing-styx has joined #bitcoin-wizards
kmels has quit [Ping timeout: 255 seconds]
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 258 seconds]
crossing-styx has quit [Ping timeout: 240 seconds]