wumpus changed the topic of #bitcoin-wizards to: This channel is 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
PRab has quit [Quit: ChatZilla 0.9.92 [Firefox 40.0.3/20150826023504]]
zooko has joined #bitcoin-wizards
zooko__ has joined #bitcoin-wizards
zooko_ has quit [Ping timeout: 272 seconds]
DougieBot5000 has joined #bitcoin-wizards
zooko has quit [Ping timeout: 256 seconds]
zooko has joined #bitcoin-wizards
nubbins` has quit [Quit: Quit]
kmels has joined #bitcoin-wizards
zooko__ has quit [Ping timeout: 250 seconds]
fkhan has joined #bitcoin-wizards
fkhan has joined #bitcoin-wizards
prosody is now known as prosodyC
jinglebellz has joined #bitcoin-wizards
jinglebellz has quit [Remote host closed the connection]
shredder_ has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
shredder_ has quit [Ping timeout: 240 seconds]
prom3th3us has quit [Quit: prom3th3us]
prom3th3us has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Newyorkadam has quit [Quit: Newyorkadam]
bendavenport has quit [Quit: bendavenport]
c-cex-yuriy has quit [Quit: Connection closed for inactivity]
belcher has quit [Read error: Connection reset by peer]
belcher has joined #bitcoin-wizards
c0rw1n is now known as rw|zZz
rasengan has quit [Ping timeout: 250 seconds]
rasengan has joined #bitcoin-wizards
m_aider has quit [Quit: ZZZzzz…]
maider has joined #bitcoin-wizards
jinglebellz has joined #bitcoin-wizards
jinglebellz has quit [Ping timeout: 240 seconds]
freepoutine has quit [Ping timeout: 256 seconds]
freepoutine has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
shredder_ has joined #bitcoin-wizards
psztorc has quit [Quit: Page closed]
sparetire_ has quit [Quit: sparetire_]
shredder_ has quit [Ping timeout: 246 seconds]
jinglebellz has joined #bitcoin-wizards
neha has joined #bitcoin-wizards
p15 has joined #bitcoin-wizards
p15 has quit [Max SendQ exceeded]
maider has quit [Quit: ZZZzzz…]
prom3th3us has quit [Quit: prom3th3us]
shredder_ has joined #bitcoin-wizards
Luke-Jr has quit [Ping timeout: 246 seconds]
[7] has quit [Disconnected by services]
TheSeven has joined #bitcoin-wizards
shredder_ has quit [Remote host closed the connection]
maider has joined #bitcoin-wizards
orik has joined #bitcoin-wizards
prom3th3us has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
Newyorkadam has quit [Quit: Newyorkadam]
GAit has quit [Client Quit]
GAit has joined #bitcoin-wizards
snthsnth has quit [Ping timeout: 246 seconds]
GAit has quit [Quit: Leaving.]
GAit has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
Dr-G has quit [Disconnected by services]
Dr-G2 has joined #bitcoin-wizards
jinglebellz has quit [Remote host closed the connection]
PRab has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
TheSeven has quit [Disconnected by services]
[7] has joined #bitcoin-wizards
adam3us has joined #bitcoin-wizards
snthsnth has joined #bitcoin-wizards
maider has quit [Quit: ZZZzzz…]
merlincorey has quit [Ping timeout: 250 seconds]
GAit has joined #bitcoin-wizards
shredder_ has joined #bitcoin-wizards
GAit has quit [Client Quit]
GAit has joined #bitcoin-wizards
shredder_ has quit [Ping timeout: 255 seconds]
GAit has quit [Quit: Leaving.]
merlincorey has joined #bitcoin-wizards
merlincorey has quit [Changing host]
merlincorey has joined #bitcoin-wizards
Madars_ has joined #bitcoin-wizards
cluckj has quit [Ping timeout: 244 seconds]
Madars has quit [Read error: Connection reset by peer]
publius1788 has joined #bitcoin-wizards
publius1788 has quit [Client Quit]
publius1788 has joined #bitcoin-wizards
publius1788 has quit [Client Quit]
publius1788 has joined #bitcoin-wizards
smk has quit [Quit: Page closed]
Luke-Jr has joined #bitcoin-wizards
publius1788 has quit [Quit: leaving]
publius1788 has joined #bitcoin-wizards
publius1788 has quit [Client Quit]
certee7 has quit [Max SendQ exceeded]
publius1788 has joined #bitcoin-wizards
jinglebellz has joined #bitcoin-wizards
contrapumpkin has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
copumpkin has quit [Ping timeout: 240 seconds]
DougieBot5000 has quit [Ping timeout: 246 seconds]
jtimon has quit [Ping timeout: 255 seconds]
DougieBot5000 has joined #bitcoin-wizards
dEBRUYNE has joined #bitcoin-wizards
freepoutine is now known as poutine
copumpkin has joined #bitcoin-wizards
contrapumpkin has quit [Ping timeout: 240 seconds]
dEBRUYNE has quit [Ping timeout: 265 seconds]
mjerr has joined #bitcoin-wizards
jinglebe_ has joined #bitcoin-wizards
jinglebellz has quit [Read error: Connection reset by peer]
kmels has quit [Ping timeout: 246 seconds]
bramc has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 246 seconds]
hdbuck has joined #bitcoin-wizards
hdbuck has quit [Client Quit]
Dr-G2 has quit [Read error: Connection reset by peer]
<phantomcircuit>
so it appears that various block explorer things have connected to full replace by fee nodes
<phantomcircuit>
and the spam which is being fee sniped in a loop is causing them to show comically larger transaction volumes
shesek has quit [Ping timeout: 250 seconds]
Dr-G has joined #bitcoin-wizards
snthsnth has quit [Ping timeout: 240 seconds]
jinglebe_ has quit [Remote host closed the connection]
shesek has joined #bitcoin-wizards
cfields has quit [Ping timeout: 246 seconds]
cfields has joined #bitcoin-wizards
prom3th3us has quit [Quit: prom3th3us]
execut3 has joined #bitcoin-wizards
shesek has quit [Ping timeout: 246 seconds]
Dr-G has quit [Read error: Connection reset by peer]
execut3 has quit [Ping timeout: 265 seconds]
DougieBot5000 has quit [Quit: Leaving]
Dr-G has joined #bitcoin-wizards
Dr-G has joined #bitcoin-wizards
execut3 has joined #bitcoin-wizards
zooko_ has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
rubensayshi has joined #bitcoin-wizards
zooko has quit [Ping timeout: 256 seconds]
bramc has quit [Quit: This computer has gone to sleep]
Dr-G has quit [Read error: Connection reset by peer]
Dr-G has joined #bitcoin-wizards
fkhan has quit [Ping timeout: 246 seconds]
dc17523be3 has quit [Ping timeout: 250 seconds]
nullbyte has quit [Ping timeout: 260 seconds]
nullbyte has joined #bitcoin-wizards
dc17523be3 has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
publius1788 has quit [Changing host]
publius1788 has joined #bitcoin-wizards
Dr-G has quit [Read error: Connection reset by peer]
ThomasV has quit [Ping timeout: 256 seconds]
Dr-G has joined #bitcoin-wizards
fkhan has joined #bitcoin-wizards
fkhan has joined #bitcoin-wizards
Dr-G has quit [Read error: Connection reset by peer]
Dr-G has joined #bitcoin-wizards
sparetire_ has joined #bitcoin-wizards
Tiraspol has quit [Read error: Connection reset by peer]
Dr-G has quit [Read error: Connection reset by peer]
Tiraspol has joined #bitcoin-wizards
Dr-G has joined #bitcoin-wizards
hdbuck has joined #bitcoin-wizards
CoinMuncher has joined #bitcoin-wizards
hdbuck has quit [Quit: hdbuck]
dEBRUYNE has joined #bitcoin-wizards
CoinMuncher has quit [Quit: Leaving.]
CoinMuncher has joined #bitcoin-wizards
bedeho has joined #bitcoin-wizards
rw|zZz is now known as c0rw1n
jl2012 has quit [Read error: Connection reset by peer]
jl2012 has joined #bitcoin-wizards
orik has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
dEBRUYNE has quit [Ping timeout: 244 seconds]
erasmospunk has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
dEBRUYNE has joined #bitcoin-wizards
mjerr has quit [Ping timeout: 260 seconds]
dEBRUYNE has quit [Ping timeout: 265 seconds]
rubensayshi has quit [Remote host closed the connection]
shredder_ has joined #bitcoin-wizards
ttttemp has quit [Remote host closed the connection]
Yoghur114 has joined #bitcoin-wizards
erasmospunk has quit [Ping timeout: 250 seconds]
shredder_ has quit [Ping timeout: 272 seconds]
Dr-G has quit [Ping timeout: 264 seconds]
ttttemp has joined #bitcoin-wizards
dabura667 has joined #bitcoin-wizards
Dr-G has joined #bitcoin-wizards
Dr-G has joined #bitcoin-wizards
erasmospunk has joined #bitcoin-wizards
erasmosp_ has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 240 seconds]
<da2ce7>
phantomcircuit, in fact these public private key 'stress test' are nothing more than an effective bounty for the rollout of full replace by fee.
erasmospunk has quit [Ping timeout: 265 seconds]
ThomasV has joined #bitcoin-wizards
ttttemp has quit [Remote host closed the connection]
gill3s has joined #bitcoin-wizards
bedeho has quit [Ping timeout: 256 seconds]
Quanttek has joined #bitcoin-wizards
flower has quit [Quit: -]
gmaxwell has quit [Ping timeout: 272 seconds]
gmaxwell has joined #bitcoin-wizards
gmaxwell is now known as Guest69884
Dr-G has quit [Read error: Connection reset by peer]
Dr-G has joined #bitcoin-wizards
ttttemp has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
GAit has quit [Client Quit]
bedeho has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
airbreather has quit [Quit: Leaving]
airbreather has joined #bitcoin-wizards
Guest69884 has quit [Changing host]
Guest69884 has joined #bitcoin-wizards
Guest69884 is now known as gmaxwell
GAit has quit [Quit: Leaving.]
eudoxia has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 260 seconds]
adam3us has quit [Quit: Leaving.]
dabura667 has quit [Quit: Connection closed for inactivity]
jinglebellz has joined #bitcoin-wizards
bedeho has quit [Ping timeout: 265 seconds]
shredder_ has joined #bitcoin-wizards
d9b4bef9 has quit [Ping timeout: 240 seconds]
shredder_ has quit [Ping timeout: 250 seconds]
shredder_ has joined #bitcoin-wizards
d9b4bef9 has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
shredder_ has quit [Ping timeout: 240 seconds]
davispuh has joined #bitcoin-wizards
jinglebellz has quit [Remote host closed the connection]
binaryFate has joined #bitcoin-wizards
neha has joined #bitcoin-wizards
JackH has joined #bitcoin-wizards
jinglebellz has joined #bitcoin-wizards
neha has quit [Read error: Connection reset by peer]
<JackH>
Committed effort to improve the bitcoin wiki? <-- that one for certain is a big one
<Taek>
BlueMatt: we talked about making prs to bitcoin.ninja, what types of things would you be willing vs unwilling to merge?
<JackH>
well from reading the link really quick
<JackH>
I see everyone agree's
<JackH>
we all know alot and its nowhere to be found
<JackH>
I bet I am not the only one with 100's of links to things
<JackH>
well....kanzure is a good candidate of link overload
mjerr has joined #bitcoin-wizards
<Taek>
JackH: best place to start is by collecting a few of them into a specific topic, and then perhaps providing a commentary on the topic, maybe with prereqs and related info
<JackH>
what format would people be mostly interested in having? Wiki style? Website style? reddit style? something else?
mjerr has quit [Ping timeout: 240 seconds]
neha has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
<kanzure>
JackH: a wiki page with summaries of #bitcoin-wizards logs per day would be nice. maybe 3-4 sentences per day. http://gnusha.org/bitcoin-wizards/ has irc logs.
<JackH>
hmmm, yeah there is this as well
davec has joined #bitcoin-wizards
<JackH>
are you constantly adding new material kanzure?
<kanzure>
usually
davec has quit [Ping timeout: 244 seconds]
zwick has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
<JackH>
hmm, you know what, I think ill give this a go
<JackH>
stick around, I will show you when I got something that could maybe work
GAit has joined #bitcoin-wizards
davec has joined #bitcoin-wizards
PaulCape_ has joined #bitcoin-wizards
zooko__ has quit [Ping timeout: 248 seconds]
neha has joined #bitcoin-wizards
PaulCapestany has quit [Ping timeout: 240 seconds]
veleiro has joined #bitcoin-wizards
PaulCapestany has joined #bitcoin-wizards
PaulCape_ has quit [Ping timeout: 240 seconds]
maraoz has joined #bitcoin-wizards
GAit has quit [Read error: Connection reset by peer]
zooko has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
bramc has joined #bitcoin-wizards
neha has joined #bitcoin-wizards
prom3th3us has joined #bitcoin-wizards
airbreather has quit [Ping timeout: 250 seconds]
binaryFate has quit [Ping timeout: 244 seconds]
CodeShark has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
dEBRUYNE_ has joined #bitcoin-wizards
ThomasV has quit [Quit: Quitte]
dEBRUYNE has quit [Ping timeout: 246 seconds]
davec_ has joined #bitcoin-wizards
tbmit has quit [Quit: tbmit]
trippysalmon has joined #bitcoin-wizards
davec has quit [Ping timeout: 240 seconds]
tbmit has joined #bitcoin-wizards
davec has joined #bitcoin-wizards
prom3th3us has quit [Quit: prom3th3us]
davec_ has quit [Ping timeout: 272 seconds]
bramc has quit [Quit: This computer has gone to sleep]
dEBRUYNE_ has quit [Read error: Connection reset by peer]
<kanzure>
huh, "The world's first operating-system kernel with an end-to-end proof of implementation correctness and security enforcement is available as open source"
<maaku>
it's been open source for a little while, but I'm hoping being on github will get some visibility and use
<maaku>
(any hardware wallet authors here, this is what you should be using!)
<nsh>
(mathematics and computers don't work that way)
zooko_ has quit [Ping timeout: 250 seconds]
bramc has joined #bitcoin-wizards
orik has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
kmels has quit [Ping timeout: 256 seconds]
mjerr has joined #bitcoin-wizards
shredder_ has joined #bitcoin-wizards
shredder_ has quit [Remote host closed the connection]
orik has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
GAit has joined #bitcoin-wizards
<maaku>
nsh: it's the closest we can get
* nsh
nods
<nsh>
i don't deride the efforts; it's all grist to the mill. the problem is that people are magnetically drawn to absolutes, in a world where layered and layered and layered imperfect and leaky abstractions underpin any notion of proven absolute mathematical correctness and its projection over actual physical hardware
<nsh>
so the notion of mathematical verification unintentionally connotes things it wouldn't want to
<maaku>
well actually in the microcontroller case I find it plausible that you might be able to achieve real security that way
mjerr has quit [Ping timeout: 246 seconds]
<maaku>
intel microcode is almost certainly backdoored by TLAs, and undiscovered bugs exist, and the assumptions underlying the proof probably don't match perfectly the ISA...
<maaku>
but with a small, mips microcontroller there's actually a good chance you can get the hardware to work exactly as specified, and as assumed in the security proof
zooko has joined #bitcoin-wizards
prom3th3us has quit [Quit: prom3th3us]
prom3th3us has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
maaku has quit [Remote host closed the connection]
neha has joined #bitcoin-wizards
maaku has joined #bitcoin-wizards
maaku is now known as Guest87378
zooko has quit [Ping timeout: 255 seconds]
GAit has joined #bitcoin-wizards
bendavenport has quit [Quit: bendavenport]
Iriez has quit [Ping timeout: 240 seconds]
Dizzle has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
erasmosp_ has quit [Remote host closed the connection]
GAit has joined #bitcoin-wizards
GAit has quit [Client Quit]
CodeShark_ has joined #bitcoin-wizards
orik has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
neha has quit [Quit: ...sleep]
neha has joined #bitcoin-wizards
<BlueMatt>
Taek: anything that people in this channel would generally consider smart/interesting
ThomasV has joined #bitcoin-wizards
PaulCape_ has joined #bitcoin-wizards
PaulCapestany has quit [Ping timeout: 255 seconds]
bramc has quit [Quit: This computer has gone to sleep]
<BlueMatt>
also @bitcoin.ninja emails
Guest87378 is now known as maaku
<nsh>
maaku ( Guest87378 ): you could, surely, *under the abstraction assumptions* between the specified physical operation of the hardware and the microarchitecture logic through to machine code
<nsh>
and that would be a formidable achievement and make a lot of things a lot better
<nsh>
but ultimate, mathematics has precious little to say about the physics, and side-channels and physical subversions exist, manifest, become understood, become applicable to undermine security assurances
<maaku>
Right, well seL4 takes us as far as verifiably correct C code (assuming compiler + physical hardware conform to C standard)
<maaku>
that's a remarkably far way along
<nsh>
indeed
PaulCape_ has quit [Max SendQ exceeded]
<nsh>
so i think a great initative would be to get a foundation for this, some open-hardware where everything can be formalized, proven, audited, right up to the compiler toolchain
<nsh>
and then demonstrate the extent to which a great many of these currently-security-apocalypse-inducing internet-of-toaster devices could be redesigned on a secure basis
PaulCapestany has joined #bitcoin-wizards
<maaku>
agreed. please go do it :)
<nsh>
but that would also require a cultural shift in the way people who make these things view networking
<nsh>
it's on the TODO list :)
orik has joined #bitcoin-wizards
kmels has joined #bitcoin-wizards
shredder_ has joined #bitcoin-wizards
Madars_ is now known as Madars
ghtdak has quit [Quit: WeeChat 1.4-dev]
ghtdak has joined #bitcoin-wizards
zooko has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
neha has joined #bitcoin-wizards
jinglebellz has joined #bitcoin-wizards
zooko has quit [Ping timeout: 260 seconds]
jinglebellz has quit [Remote host closed the connection]
tbmit has quit [Quit: tbmit]
<phantomcircuit>
runeks, are you Rune Kjær Svendsen ?
<runeks>
phantomcircuit: Yes
neha has quit [Quit: ...sleep]
<phantomcircuit>
runeks, was my email to the list about full nodes using utxo set commitments clear?
<runeks>
phantomcircuit: I just saw it now. Will read and respond.
trippysalmon has quit [Ping timeout: 250 seconds]
erasmospunk has joined #bitcoin-wizards
veleiro has quit [Read error: Connection reset by peer]
veleiro has joined #bitcoin-wizards
<TD-Linux>
maaku, yeah the verifiably correct part is pretty neat. the functionality of seL4 is ultra minimal though
ThomasV has quit [Ping timeout: 250 seconds]
<TD-Linux>
it's a way to isolate processes, but in a bitcoin wallet there's really not much to isolate, and compromising any of the parts breaks the security of the whole thing
zooko has joined #bitcoin-wizards
zooko has quit [Ping timeout: 256 seconds]
mjerr has joined #bitcoin-wizards
neha has joined #bitcoin-wizards
<runeks>
phantomcircuit: I've responded :)
thesnark has joined #bitcoin-wizards
jgarzik has quit [Read error: Connection reset by peer]
jgarzik has joined #bitcoin-wizards
snthsnth has quit [Ping timeout: 264 seconds]
mjerr has quit [Ping timeout: 264 seconds]
jgarzik has quit [Read error: Connection reset by peer]
gill3s has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<maaku>
anyone have a link to greg's original utxo commitment suggestion from way back when?
thesnark has quit [Quit: bbl]
<CodeShark_>
can't we solve this attack scenario with sum trees? :)
ThomasV has joined #bitcoin-wizards
<maaku>
TD-Linux: yes, but implement network stack, database, etc. as separate processes...
bramc has joined #bitcoin-wizards
orik has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
orik has joined #bitcoin-wizards
orik has quit [Client Quit]
jgarzik has joined #bitcoin-wizards
<CodeShark_>
committing to the utxo set alone is probably insufficient
<CodeShark_>
we need other partial checks to make this secure
<CodeShark>
bah, wrong handle - committing to the utxo set alone is probably insufficient - we need other partial checks to make this secure
<CodeShark_>
inflation isn't too expensive to check against - but signature validation generally is quite expensive
jgarzik has quit [Read error: Connection reset by peer]
jgarzik has joined #bitcoin-wizards
<maaku>
oh wait Rune == runeks? ok you do know prior work here i assume
<maaku>
runeks: I'm curious why you didn't mention using a balanced Merkle tree?
shredder_ has quit [Remote host closed the connection]
shredder_ has joined #bitcoin-wizards
jgarzik has quit [Client Quit]
<runeks>
maaku: It's entirely possible that there's a data structure that's superior to a simple UTXO set hash. As long as the added computational requirements are reasonable, a different data structure might be better. I'm really just interested in having *some* fingerprint of the UTXO set be consensus-critical.
<MRL-Relay>
[tacotime] that's quite an old idea, and a softfork if you want to put it in scriptsig
<CodeShark>
it's a frustratingly old idea
<runeks>
And I say consensus-critical because I don't think adding a feature to Bitcoin Core is sufficient. It needs to be a protocol feature in order to be useful.
<maaku>
you wouldn't want it in the scriptSig of the coinbase becuase coinbases are huge
<bramc>
So here's my idea: Instead of a single utxo root, there's a utxo root and a series of deltas off of it, each smaller than the last
<maaku>
best place to put it, if soft-fork compatible, is in the last output of the last transaction
<maaku>
bramc: I think you need to justify that complexity
<bramc>
At scheduled times the utxo root is replaced with the combination of everything which was in the utxo root plus the delta right after it, and the other things move up
<MRL-Relay>
[tacotime] maaku: wouldn't the scriptsig of the coinbase be serialized to the same position in every serialized block?
<CodeShark>
Ideally we'd have a PoW layer that is agnostic to the committed structures to give us great flexibility in designing these structures without relying on stuff like coinbase hacks...but it seems the will and political climate for it just isn't there :(
ThomasV has quit [Quit: Quitte]
<maaku>
tacotime: not the point. proof size is what should be optimized, and coinbases are huge, and path to coinbase (left branches) is on average 2x as long as path-to-last-tx (right branches)
erasmospunk has quit [Ping timeout: 240 seconds]
ASTP001 has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<maaku>
(put it at the end of the transaction for midstate compression hack)
<MRL-Relay>
[tacotime] Oh, I see.
<runeks>
CodeShark: I really wish we could get together and do a complete revision of Bitcoin. We can't keep piling hacks on top of old code on top of proof-of-concepts.
<CodeShark>
Ugh
<CodeShark>
Seriously, right?
<MRL-Relay>
[tacotime] runeks: make your own alt
<bramc>
This gets you a massive boost in performance, because the merging only has to be done quite infrequently and has a long time to do it and is a single linear pass. It's also very easy to specify, because the utxo root and deltas cover very well specified ranges of blocks
<bramc>
The SPV implementation is slightly more complicated because it has to look at deltas, but that comes with benefits as well because those aren't as deep as the full root.
<maaku>
bramc at the cost of making mining inherently stateful forever
<maaku>
delay the utxo commitment by one block so it is out of the validation loop. that's all you need imho...
<bramc>
maaku Huh? It's no different from any other proposal for having utxo roots
<maaku>
bramc: time to validate the root is on the same order of validation work that is already done.
<runeks>
CodeShark: Indeed. I think we have a choice to make. We can either choose to favor the guy who downloaded bitcoin-qt 4 years ago, ran it for a couple of hours, and make sure that if he were ever to start up bitcoin-qt again, it would just work. The other choice is to build a proper protocol, using all the knowledge we've gained in the past half a decade,
<runeks>
which can actually serve as a working payment system. This would break compatibility, yes, but it would actually be a system that we can build on top of. I don't think we can have both infinite backwards compatibility and a proper protocol.
<maaku>
furthermore, by delaying one block you don't have to do it in the tight validation loop before relay
<maaku>
so why have an incremental structure beyond that?
<bramc>
Making the utxo root be one block behind is an interesting idea
<sipa>
runeks: well bitcoin is not a monolith
<bramc>
It's in line with my overall idea that you allow utxo root work to be done in the background
<maaku>
bramc: to be honest I thought that was what you proposed to me at the workshop...
<runeks>
I mean, right now we don't even have a protocol. We have a program (Bitcoin Core).
<sipa>
runeks: significant parts can be changed, or even have multiple parallel parts
<sipa>
runeks: the consensus rules are an exception
<runeks>
sipa: I'm not following. What can be changed?
<bramc>
maaku, It's in line with 'allow the work to be done later', which is what I proposed, although I was thinking more about the bigger updates than the smaller ones
<sipa>
runeks: you won't change that by using a different design
<CodeShark>
unfortunately github is not ideal for commenting on prose
<bramc>
maaku, If you're doing multiple deltas then I *think* that making a last delta just for the current block would be so computationally trivial that it might as well be done, although glomming it into a bigger delta should be put off until the next block
<maaku>
bramc: for separate reasons it is desireable for each block to have it's own delta commitment, so delaying 1 block is actually cleaner
<sipa>
runeks: bitcoin's consensus rules are descriptive, not prescriptive. we can create a document that states what the rules should be, but in the end of the day, if we find a difference between what's on paper and what the network actually runs, it's the paper that will have to change
<kanzure>
maaku: i have many links to utxo commitment proposals,
<runeks>
sipa: When a bug in Bitcoin Core appears, and we accept this bug as correct behavior (as we did with the database commit failure), Bitcoin Core becomes the protocol, and all alternative implementations become useless. This practice needs to change, in order for alternative implementations to actually be useful.
<sipa>
runeks: i think we should refactor bitcoin core's code to have the part that defines the consensus rules separately
<MRL-Relay>
[tacotime] runeks: alternative implementation adoption has always been seemingly against the collective interests of bitcoin core developers, for better or worse
<sipa>
runeks: and then don't touch it anymore unless we want the consensus rules to change
<bramc>
maaku, I think we both just said the exact same thing
<kanzure>
bramc: what sorta utxo commitment update deltas are you thinking of? there has to be some way to verify that the partial-utxo-update is valid and commit to that update i think.
<maaku>
bramc: I don't think we are in disagreement, except perhaps regarding longer window commitments
gmaxwell is now known as Guest24525
<sipa>
runeks: then anyone can create a full node implementation, as long as they can use the consensus library
<MRL-Relay>
[tacotime] runeks: there's a lot of halfbakery in core from p2p to RPC down to consensus rules, and unfortunately a lot of the latter bitcoin is stuff with.
<MRL-Relay>
[tacotime] and so everyone else is, too.
<MRL-Relay>
[tacotime] s/stuff/stuck
<runeks>
sipa: I think it's possible to define a protocol not after the C++ in Bitcoin Core, but after *intent*. We all know that the Bitcoin Core database commit failure that rejected a block was not intentional. This was clearly not a protocol feature, but a bug in Bitcoin Core. Yet the bug was accepted as correct, and the *correct* implementations (btcd, Haskoin)
<runeks>
were rejected as wrong. We may not be able to define the protocol exactly in code, but we can stop accepting unintentional behavior as correct.
<maaku>
bramc: *regarding the utility, or necessity, or benefit of longer-window commitments
<kanzure>
"Merkle mountain ranges support efficient appends and updates; when a txout is spent the tree is updated, and the updated root is what is committed in the block. Same idea as UTXO commitments, except with a merkle mountain range not only can you can do secure updates, but because it's insertion ordered you can also add new txouts without actually having any of the data in the set. (other than the tips of the trees)" from ...
<sipa>
runeks: so what do you do when the implementation differs from the intent?
<bramc>
kanzure, I'm thinking of intervals which go up by squares, starting at 8, so there's one delta of just the last block (per discussion above), followed by one from the last block which was a multiple of 8, followed by one which goes back to the last multiple of 64, followed by one for the previous 64, then one which goes back to the last multiple of 4096, etc.
<maaku>
imho we benefit from *not* doing commitments every 2016 blocks
<sipa>
runeks: you still need a hard fork to fix it
snthsnth has joined #bitcoin-wizards
<CodeShark>
we have three serious issues: 1) our current consensus structures are far from optimal for many things we'd like to do, 2) our reference implementation mixes consensus-critical stuff with everythung else, making concerns about difficulty of making changes that can be easily reviewed and tested against the current codebase trump concerns regarding fundamental structural/architectural issues, 3) we have no solid mechanism in pl
<maaku>
kanzure: thanks for the links!
<bramc>
kanzure, I *think* the merkle mountain range proposal has a different approach to rebalancing, but I'm not sure
<sipa>
runeks: adding more different consensus implementations into the mix just increases the chance for randomly ending up with disagreements
xabbix has quit [Ping timeout: 250 seconds]
<CodeShark>
3) we have no solid mechanism in place for consensus-critical changes
<runeks>
sipa: We don't need to fix hard forks. Hard forks are a disagreement in the network. Miners need to fix it, because they lose money if they don't.
<sipa>
CodeShark: 3) is called politics
<kanzure>
maaku: can you elaborate on delaying one block for utxo commitments? why does it matter that it's a commitment of the state as of the previous block and not the current block?
<CodeShark>
(2) and (3) are far more serious problems than (1)
<sipa>
runeks: miners can't fix it
<sipa>
runeks: what if two implementations are incompatible in a mutual way?
<runeks>
sipa: We should never temporarily alter the protocol rules just to solve a hard fork. This creates uncertainty, and instability.
<Taek>
kanzure: if you are committing to the current block, you have to rebuild the the commitment every time you change which set of transactions you are mining
<sipa>
the protocol rules are defined by what people run
<bramc>
The thing I'm proposing has no rebalancing ever, except for when it redoes everything from scratch. The benefit of this is that it's brainless and reliable to implement and highly efficient in terms of storage space used.
<runeks>
sipa: Unless we recognize that the protocol is faulty.
<CodeShark>
(2) is at least semi-tractable right now
<kanzure>
Taek: i don't think you have to always rebuild the entire utxo tree if you are doing the partial updates via deltas, so building it for previous/current block shouldn't matter here
sipa has left #bitcoin-wizards [#bitcoin-wizards]
<maaku>
kanzure: you've just received a full block. you've now validated its transactions. now before doing the relay you need to check the commitment -- which involves committing the changes to the utxo and rebuilding the root hash
<maaku>
you need to do that before you relay the block, because maybe the commitment is wrong
<kanzure>
right, commitment needs to be checked even if it was for the last block though
<runeks>
sipa: Two incompatible implementations means that either *one* of them is wrong or both are wrong. The wrong implementation(s) need fixing, that's all.
<CodeShark>
runeks: you either do one or three :)
<CodeShark>
Never two
zwick has quit [Quit: WeeChat 1.3]
<maaku>
right, so if on the other hand block 101 has a commitment to the utxo state after validating the previous block, #100, then the utxo tree update can happen after the block 100 is validated and relayed along
<MRL-Relay>
[tacotime] kanzure: for mmr i'm interested in seeing what insertion/delete actually costs when you have the whole exponentially rising bitcoin utxo set. it may end up prohibitively expensive, even at log(n) insertion/deletion.
<kanzure>
okay but in both cases you are still doing utxo update verification/delta work stuff.
<maaku>
right, it's just not in the receive, validate, relay loop
<CodeShark>
kanzure: is there any way I can help you in archiving good material and reorganizing it?
<bramc>
kanzure, Yeah merkle mountain ranges do stuff where they make a new tree point to a branch of an old tree. What I'm proposing doesn't do that
<kanzure>
CodeShark: writing summaries of certain broad ranges of ideas; will be giant wiki page with 20-30 different topics that are summarized with links to historical work and current work.
<bramc>
kanzure, maaku One big benefit of using deltas and merging them together is that the actual merge operation between two sorted lists is extremely efficient, so long as you don't have to do it too often.
<maaku>
tacotime: utxo growth isn't exponential in the limit
<bramc>
Like, it's much faster for the last block than the sorting operation is.
<maaku>
bramc: the disadvantage is that you have to actually store and keep around those lists :P
<kanzure>
maaku: it's still in the loop; if it's wrong, you can't relay the current block.
<CodeShark>
wonderful! I look forward to that. If you need any help writing anything let me know. We need to do better than bitcointalk and botbot links
<kanzure>
you shouldn't relay bad blocks
<kanzure>
CodeShark: yes, making up some summaries would be extremely helpful... like doing a short summary of coinjoin/coinshuffle/privacy/mixing stuff would be a good place to start.
<helo>
does utxo growth scale with exchange value "in the limit"?
<kanzure>
CodeShark: (such a summary would in theory always mention private information retrieval stuff, too)
<bramc>
maaku, They aren't very big, it's mostly the one huge list of everything back to the last multiple of 4096, everything else is tiny by comparison, and that big one is stored in a completely non-fragmented compact data structure which can be easily looked into
<maaku>
kanzure: you'll already know the commitment that should be there because you calculated it from the last block
belcher has joined #bitcoin-wizards
<kanzure>
maaku: ok, so it's still there in that block, it's just using some precomputation since the last block was received and validated.
<maaku>
so receive a block, validate it, relay it, update utxo hash, <...wait..> receive new block, validate including checking <--- prior hash, relay , etc.
<maaku>
right
<kanzure>
i mean, it's still there in that loop, but can use some cached precomputation for superfast verificatio nkthx
<bramc>
One advantage of using the squaring base of 8 is that the block size after 4096 is 16777216, which corresponds to about 300 years, so for all practical purposes it's a fixed number of deltas.
<bramc>
kanzure, Right, I'm proposing doing the same trick in the large for the utxo root as a whole
<maaku>
bramc: btw you should look at mmr's for inseration-ordered full-txout commitments
<kanzure>
man i'd really like to skip straight to "wallets carry utxos and utxo proofs, miners just make giant merkle roots and proofs for updating the authorized data structure (merkle tree of some special kind), undisclosed unknown set of transactions aren't tracked by blocks"
<maaku>
it's not obvious (to me) which is better, utxo, txo, or stxo
<maaku>
we really need competing proposals to test
<kanzure>
bramc was quite adamant about stxo being useless
<bramc>
maaku, I'm thinking a flat merkle tree of fixed depth
<kanzure>
wait i'm not allowed to say that
<CodeShark>
I still hold that fixing (2) and (3) are far more critical right now
<kanzure>
SOMEONE had good reasons for not doing stxo
<bramc>
What is stxo?
<kanzure>
spent transaction outputs
<maaku>
bramc: that requires a full node to have the full UTXO set
<CodeShark>
Fixing (1) depends on (2) and (3)
<kanzure>
"insertion-STXO proofs might be more bandwidth-friendly"
<bramc>
maaku, How can a node be 'full' if it doesn't have the full utxo set?
<maaku>
it is a very cool property of bitcoin that (with utxo, txo, or stxo commitments) that you can run a full node _without any state_ so long as proofs are provided
<bramc>
Oh, stxo is spent transaction outputs. Yeah remembering those is pointless.
<maaku>
*proofs that are less than the size of the UTXO set
<kanzure>
yes, there's a few proposals about having a storageless full-node using various utxo commitments and update proofs or something
<kanzure>
none of which are very fleshed out proposals
<maaku>
but in principle they work
<kanzure>
oops not storageless, just constant-storage-size and still fully-validating
xabbix has joined #bitcoin-wizards
xabbix has joined #bitcoin-wizards
<bramc>
I don't see how stxo is every smaller than utxo. The number of stxos is several times as much.
<maaku>
if you do something like flat merkle trees, or runeks's straight serialize the utxoset, or an infinite set of deltas, then in principle you can never get away from holding the utxo set
<bramc>
I don't understand what the counterfactual is. To answer the question of whether something is in the utxo set you need to have the utxo set.
<maaku>
bramc: imagine blocks and transactions come with proofs extracted from the merkle utxo tree
<maaku>
and that a structure is chosen such that the proof itself is the update to the tree, and that these deltas can be combined together without information in that tree, etc...
<bramc>
maaku, Oh I see. Or I mostly see. I don't follow about the proof itself being the update to the tree. That sounds like complicated data structur fu
<kanzure>
there might be a way to do that without snarks
<maaku>
bramc: it works trivially with patricia tries (one of the proposals), so that might be a place to start
<bramc>
maaku, A proof of validity of block can be included with it, but it seems more flexible for that to be included along side it in the network protocol rather than being embedded within it.
<maaku>
kanzure: snarks aren't necessary. the merklized patricia trie of utxos indexed by txid:n works for this
<kanzure>
maaku: with update proofs?
shredder_ has quit [Remote host closed the connection]
<maaku>
kanzure: snarks let you get a constant storage, constant workspace, constant time validator though, which is friggin awesome
<maaku>
better efficiencies & optimizations, simplifications of the data structure, etc. have been developed since the draft bip was last updated, just haven't had time to go back and update the document
CodeShark is now known as CodeShark__
<maaku>
mostly just tricks to reduce the number of compression rounds, make the structure easier to parse within a snark prover, etc.
CodeShark_ has quit []
<maaku>
in large the proposal is the same
CodeShark has joined #bitcoin-wizards
<kanzure>
so verification can be done without a full utxo set constructed from the blockchain?
<bramc>
You can straightforwardly do a proof of the validity of a block based off the utxo commitment in the previous block
airbreather has joined #bitcoin-wizards
<CodeShark>
I'd rather see some of these bips less focused on implementation and more focused on architecture ;)
<bramc>
The proof is larger than the block though.
<kanzure>
i believe bip1 asks for implementation details in bips
<maaku>
the verifier doesn't need a full utxo set. they just need a merkle proof of all the inputs spent in the block, whose root matches the commitment in the last block, and a delta of all the outputs added in the block
orik has joined #bitcoin-wizards
<maaku>
bramc: proof is smaller than the utxo though
<maaku>
*utxo set
shredder_ has quit [Ping timeout: 246 seconds]
<CodeShark>
I'd like to move away from a culture where everything is always specified in implementations and instead focus on other formal specification mechanisms and ways to demonstrate that a particular implementation satisfies correct behavior...but meh... :p
<bramc>
maaku, I think this property holds for all utxo commitment proposals
<kanzure>
i am also confused about what sort of attributes we're missing without snarks with this sort of proposal
<kanzure>
or which attributes we're preserving that i might be accidentally attributing to snarks already
<Taek>
CodeShark: by the time it's a bip, it's supposed to be an implementation. If you're just talking architecture it's probably not ready to be a bip. (my interpretation anyway)
<bramc>
CodeShark sometimes the most concise way to specify something is with an implementation.
<CodeShark>
I'm not opposed to also requiring implementations - don't get me wrong
<kanzure>
bramc: case in point, the amount of time to explain lightning network has been more than the time necessary to do all of the existing implementation so far
zooko has joined #bitcoin-wizards
orik has quit [Client Quit]
<maaku>
CodeShark: we would all like to do that for everything except the consensus code
<CodeShark>
I just feel like the focus is too much on how to make modifications that require the fewest changes to source code rather than modifications that better serve the platform
<maaku>
e.g. payment protocol is specified by bips 70-72. if the qt wallet differes in behavior, it is a bug and the qt wallet should be fixed
<maaku>
not so for consensus code
<kanzure>
maaku: so i think the deltas have non-constant size, and verification or proof might also be non-constant-time, and theoretically if we snarkify everything then we can get back to very-nearly-constant runtimes and memory costs. ya?
<CodeShark>
maaku: IMHO, if a particular wallet differs from BIP70-72 who cares as long as it works...and if it turns out to be a better behavior than BIP70-72, let that one be the standard :)
<maaku>
the 'storageless' part of a utxo-proof-streeming validator is the utxo storage. it has non-constant RAM requirements to validate a block
<kanzure>
(streaming?)
<maaku>
it's storage is just the last utxo commitment plus a few other misc things like block height
<CodeShark>
BIPs like 70 depend FAR more on widespread adoption to become "official" than on being a BIP
Guest24525 is now known as gmaxwell
<CodeShark>
moreover, there's room for several different competing approaches without breaking the network
<maaku>
kanzure: you could build a machine that took as input blocks prefixed with their utxo delta proofs (showing all the inputs, and paths to where the outputs need to go), and it only internally carries forward the utxo set root (+ block height, hash of last block, timestamps of last 11 blocks, current difficulty, etc.)
neha has quit [Quit: ...sleep]
<maaku>
this is the idea of a constant-storage streaming validator
<maaku>
you can even have mining nodes that behave this way: prefix transactions with their own utxo delta showing inputs and location for outputs
<maaku>
and rebase each proof using the delta of the block after it is found
<kanzure>
ah okay, then i am somewhat thinking of ways of getting rid of transactions with this scheme- which either requires at least zero knowledge proofs, or snarks, like the "zero knowledge proof of authorized utxo modification" proposal on page 46 http://diyhpl.us/~bryan/irc/bitcoin/scalingbitcoin-review.pdf
<kanzure>
ah i like the rebase terminology, is easy to grok
<maaku>
does this make sense to do? ... maybe ... not with current utxo sizes. but it would be kinda nice to not block off entirely this possibility by adopting a utxo commitment scheme that doesn't have these properties
<bramc>
maaku, Why do you want to include the proofs inline in the block chain? They can just as easily be supplied 'on the side'
<bramc>
maaku, And how could anything block off these properties? Utxo commitments by their nature make it possible to prove whether transactions are valid or not.
orik has joined #bitcoin-wizards
<kanzure>
maaku: yes it would be good to check future ideas and make sure we don't shoot ourselves in the foot, although not bend over completely backwards for somewhat-impossible-at-the-moment ideas
<maaku>
kanzure: right, snarks then removes the need for the validator to handle the proofs at all. but the miner would still need them (as input into the snark prover)
<maaku>
bramc: not inline in the block chain, they're not part of the block merkle structure. rather I was meaning that they would be part of the network protocol
<maaku>
if you broadcast a transaction or a block, it needs to come with a delta proof in this future hypothetical bitcoin p2p network
orik has quit [Client Quit]
<bramc>
maaku, I don't follow why this can't be done with any utxo commitment scheme
<CodeShark>
think git...except enforce rules regarding how files can change...and require a PoW timestamp for each commitment :)
<CodeShark>
then optimize the crap out of it
Starduster has quit []
adam3us has quit [Quit: Leaving.]
<CodeShark>
once we completely decouple the commitment structure from the transport layer, then we can talk about using ssh vs. https vs. sftp vs. blah
<CodeShark>
eventually some routable protocol, hopefully
<maaku>
bramc: it can so long as the proofs carry enough information to ensure that a rebuild of the root value of the tree can occur from the information in the proof only
<maaku>
bramc: take a 4-leaf balanced binary tree, for example, and remove the lestmost leaf
<maaku>
the other leafs "shift over" if you are doing a straight bitcoin-like merkle tree
<maaku>
and you need to know the leaf nodes in order to calculate the new structure
adam3us has joined #bitcoin-wizards
<bramc>
maaku, Oh I see now. I'll have to think about that.
<maaku>
kanzure: in particular the gist uses 28-byte hashes with the intent of combining two hashes in a single compression round
orik has joined #bitcoin-wizards
orik has quit [Client Quit]
<maaku>
turns out SHA2 padding is fucking stupid and that doesn't work, despite being the whole point of SHA224 existing as far as I can tell
<maaku>
yay standards that were never actually used for their intended purpose before becoming standards
Quanttek has quit [Remote host closed the connection]
<prom3th3us>
Pardon me if this has been asked here before, but is there a particular consensus here on sidechains? I’m reading up on them and they sound like they have some neat use cases that extend the blockchain.
<bramc>
maaku, I think I see the point about stxo commitments being more convenient now. It should be possible to do that type of tree for utxo commitments too though, it just requires a lot more care
<kanzure>
prom3th3us: useful for experimentation for risky things that might destroy bitcoin mainnet blockchain
<maaku>
bramc: well, a patricia tree does that for utxo commitments
<maaku>
(see the linked gist above)
<maaku>
but if you do go down this route of prefixed proofs, then txo / stxo may result in smaller proofs... hence the interest in them
<bramc>
maaku, I think with my proposed series of deltas approach the same constant space thing can be done but the utxo updating has to be demonstrated in an amortized way, same as how it's calculated. Does require going through the whole utxo set every 4096 blocks though.
<prom3th3us>
kanzure: Can you expand on that a bit? I haven’t heard that perspective before.
orik has joined #bitcoin-wizards
orik has quit [Client Quit]
<bramc>
maaku, The downside of a patricia tree is that it's a big mess to maintain
Guest68337 has joined #bitcoin-wizards
Starduster has joined #bitcoin-wizards
<bramc>
Come to think of it, my deltas idea could be done with patricia trees just fine
Guest68337 has quit [Client Quit]
DougieBot5000 has quit [Quit: Leaving]
adam3us has quit [Read error: Connection reset by peer]
<bramc>
Or at least something which has the property you describe, not 100% sure if my understanding of patricia trees is correct.
cholbrow has joined #bitcoin-wizards
orik has joined #bitcoin-wizards
snthsnth has quit [Ping timeout: 246 seconds]
orik has quit [Client Quit]
<CodeShark>
why is a patricia tree a big mess to maintain?
<bramc>
CodeShark if you're maintaining it incrementally it frags memory like nobody's business
<CodeShark>
can't you reallocate every once in a while to reclaim memory?
adam3us has joined #bitcoin-wizards
bsm1175321 has quit [Ping timeout: 268 seconds]
<bramc>
the effectiveness of that is heavily dependent on how much updating you're doing
Guyver2 has quit [Quit: :)]
<bramc>
I assume by 'reallocate' you mean re-sweep and consolidate
<CodeShark>
yes
kang_ has joined #bitcoin-wizards
<CodeShark>
as opposed to?
<bramc>
What I proposed involves doing the consolidating and re-sweeping at fixed times. No reason a constant size only thing couldn't keep the ongoing roots as well, although it's having to do several of them which makes things a little more complicated
<CodeShark>
good implementations that are efficient with resources are clearly nontrivial...but seem doable and seem to be something that could be well encapsulated
<bramc>
So I'm sold on patricia trees, because they make zero difference in time to do consolidations, but I'm not sure about all that walking the tree
<bramc>
the log(n) multiplier on doing everything kind of sucks
<bramc>
having to walk the tree for each transaction is a nontrivial expense
<bramc>
But we're all in agreement about having the big tree be a block behind
orik has joined #bitcoin-wizards
<CodeShark>
yeah, nothing is free..but I think the tradeoffs can be made acceptable
orik has quit [Client Quit]
c-cex-yuriy has joined #bitcoin-wizards
<CodeShark>
in any case we're trading something off - right now, we're basically sacrificing thin client security ;)
<CodeShark>
I'd be more than happy to pay someone a small amount for that log(n) overhead if it means I can validate with a high level of privacy and security from my mobile devices
<CodeShark>
right now I don't really even have that option - I basically have to run a full node
<CodeShark>
it sucks...but in principle it seems to be amenable to division of labor and economies of scale
JackH has quit [Ping timeout: 240 seconds]
zooko_ has joined #bitcoin-wizards
zooko has quit [Ping timeout: 268 seconds]
<CodeShark>
and I also think that such incentives could be offered in ways that promote decentralization
zooko has joined #bitcoin-wizards
shen_noe has joined #bitcoin-wizards
shen_noe has quit [Client Quit]
zooko_ has quit [Ping timeout: 252 seconds]
<CodeShark>
although the decentralization/economy of scale thing can be a bit of a tradeoff in some instances, perhaps
<CodeShark>
ASICs are an obvious example
zooko has quit [Ping timeout: 268 seconds]
zooko has joined #bitcoin-wizards
<bramc>
CodeShark in my proposal the log(n) to thin clients is hardly any computation because it's almost always pulled out of stuff which is kept hot
snthsnth has joined #bitcoin-wizards
<bramc>
It's a tradeoff with patricia trees which are updated every time in that the total I/O and maybe cpu is a lot less with the tradeoff that future verification-only clients have to do more work
<bramc>
Basically they have 3x the work because they're updating 3 deltas instead of a single root
Burrito has joined #bitcoin-wizards
<CodeShark>
Right - then there's the implementation difficulty for thin clients, which ideally should be low. This means either making the verification algorithms inherently simple...or publishing good libraries for it
shredder_ has joined #bitcoin-wizards
<CodeShark>
I'm actually more concerned about implementation difficulty and long-term source code maintenance than I am about log(n) or constant factor costs
<MRL-Relay>
[tacotime] implementation difficulty generally sucks
<bramc>
Verification for patricia trees is fairly brainless.
<CodeShark>
yes, so that's a big plus
<MRL-Relay>
[tacotime] because you need to create a patch structure for the tree if you're going to evaluate any blocks that are forking the mainchain
<bramc>
They're basically the same as flat fixed-depth in terms of complexity
<bramc>
tacotime, I'm perfectly happy to dump complexity of fixed-size storage onto later implementers, because that's an inherently complicated thing to do
<MRL-Relay>
[tacotime] in terms of the actual tree structure and algorithms defining it, yes, that's well characterized already
<bramc>
Having to do it multiple times won't substantially change its complexity from doing it once
<CodeShark>
right - the other important thing to consider is that as long as in theory there are significant optimizations in the implementation and there are incentives for people to look for optimizing them, these things will tend to occur as needed
<CodeShark>
we don't need to dictate top down how everything is implemented
shredder_ has quit [Ping timeout: 250 seconds]
<bramc>
If the utxo commitment is based on deltas then the checkpoints of them need to be set in advance
<CodeShark>
if we start to reach a scalability wall with a log(n) factor it means either the network is being attacked...or the network is succeeding :)
<CodeShark>
and if the incentives are there people will look for further optimizations
<bramc>
Doing an update of a delta has the appealing property that you can run a brainless linear scan instead of walking the tree per transaction. If the update is large enough it can be vastly faster even in the asymptotic, on top of being brainless to implement
kmels has quit [Ping timeout: 246 seconds]
<MRL-Relay>
[tacotime] if the delta is long enough in the past (hours), you probably don't have to worry about reorganizations at all
<MRL-Relay>
[tacotime] if you're using delta to refer to committing to past utxo roots
<MRL-Relay>
[tacotime] (or whole set hashes, whatever)
<CodeShark>
you set a cutoff for the committed delta to be 100 blocks in the past or something
<CodeShark>
and maintain a delta for all recent activity, right
<CodeShark>
?
<MRL-Relay>
[tacotime] oh, i see
<MRL-Relay>
[tacotime] well, i think the first step would just be the including the utxo set from a past perspective then
<MRL-Relay>
[tacotime] worry about hashes of the deltas (updates to it) later
<MRL-Relay>
[tacotime] and by that i mean, other people can implement that later if they thinks it's useful, if i'm following the logic here correctly
Starduster has quit []
<CodeShark>
I'm still not totally clear on why consolidating in batch is more efficient than doing it continuously
<MRL-Relay>
[tacotime] doing that is a lot less of a commitment (har) in terms of implementing a new consensus rule than say, rolling utxo sets per block or this scheme with deltas
DougieBot5000 has joined #bitcoin-wizards
<CodeShark>
I sorta do get why...but I have to think about this a little more
<MRL-Relay>
[tacotime] but other than that i don't see an advantage
eudoxia has joined #bitcoin-wizards
jgarzik has joined #bitcoin-wizards
zooko has quit [Ping timeout: 255 seconds]
memymo has joined #bitcoin-wizards
shredder_ has joined #bitcoin-wizards
zooko has joined #bitcoin-wizards
orik has joined #bitcoin-wizards
maraoz has quit [Ping timeout: 256 seconds]
Dizzle has quit [Ping timeout: 260 seconds]
<bramc>
sorry was afk. The idea with deltas is that there are deltas of size 8 blocks, which get consolidated into deltas of size 64 blocks, which get consolidated into deltas of size 4096 blocks
<bramc>
It's faster to do an operation on a delta because it's a linear pass merging two sorted sets, which can be done extremely quickly.
<bramc>
This particularly matters on a device which has to hold the utxo set on disk
<bramc>
The downside, of course, is that you need to do a whole linear pass. The crossover is when the size of the update is 1/log(n) times some constant factor. The constant factor is rather favorable to the batch operation though because of the highly localized memory accesses.
<bramc>
codeshark, did that make sense?
neha has joined #bitcoin-wizards
<CodeShark>
I think so
<CodeShark>
so you're sacrificing short-term prunability for local memory operations?
maraoz has joined #bitcoin-wizards
shredder_ has quit [Remote host closed the connection]
<bramc>
That's part of the tradeoff. You're keeping more stuff around (not a lot more data, but organized in a way which under *some* usage requires bandwidth, in others less) and you're getting performance which is less operations if the updates are big enough but more operations if the number of updates is small.
eudoxia has quit [Quit: Leaving]
<bramc>
Come to think of it, you can always do better on the batch operation, because you can share the walking down work across the whole batch
<bramc>
You don't *have* to do a linear pass, it's just the most brainless approach.
<CodeShark>
ah!
<CodeShark>
of course...in batch you only need to traverse each branch once!
dEBRUYNE_ has quit [Ping timeout: 246 seconds]
<maaku>
and you don't have to recalculate the inner node hashes between updates
<CodeShark>
yep
<maaku>
i don't dispute that it is an efficiency gain to commit less frequently than every block
<maaku>
but i don't think it is worth it
<maaku>
however, I don't see the need to have larger deltas
<maaku>
if you are committing every 8 blocks, the 64 or 4096 block deltas seem pointless to me
<bramc>
maaku, The idea is to make the brainless linear approach be fairly efficient
<bramc>
Because it's amortized over a longer time period
<maaku>
bramc: but if you are committing every 8th block, then it's not amortized at all. you're doing updates every 8th block, and then every 64th block you do those updates again
<bramc>
The batching is done at each level - you aren't updating the whole tree every 8th block, you're only batching up the last 8 things every 8th, and the 8ths are batched until you hit the 64th, and the 64ths are batched until you hit 4096
zooko_ has joined #bitcoin-wizards
<bramc>
So you're always merging together things of roughly similar size in your batch operations. It could be done at a factor of 2 and be a clear win in terms of computational efficiency, but that's a whole lot of deltas.
zooko has quit [Ping timeout: 240 seconds]
<maaku>
so what is the commitment in a block?
<maaku>
are you committing to the utxo root hash? only committing every 8th block?
<maaku>
kanzure bramc: acutally you may need to delay 2 blocks so you can start mining immediately too
<bramc>
You're committing to a list of things (possibly merkleized as well for efficiency, but let's say it's a list): A root of everything at the last utxo which was a multiple of 4096, a root of the delta from that at the last multiple of 64, a root of the delta from that at the last multiple of 8, a root of the delta from that to the last one
<bramc>
I think I have an off by one in a few places there to allow things to get calculated after the fact, but that's the general idea.
<bramc>
I woke up too early this morning to get the fenceposts correct.
shredder_ has joined #bitcoin-wizards
orik has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<CodeShark>
what does the brainless linear approach really buy you? don't you have to do more complex tree operations at some point anyhow?
shredder_ has quit [Remote host closed the connection]
<CodeShark>
I understand why you want to merge trees of equal size in batch - not entirely clear why the linear approach simplifies implementation as a whole
jinglebellz has joined #bitcoin-wizards
memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<bramc>
No more complex operations necessary - A patricia tree can be hashed left to right no problem.
kmels has joined #bitcoin-wizards
<bramc>
So there's no memory management to speak of, it's just running straight through
bliljerk_ has quit [Read error: Connection reset by peer]
jinglebellz has quit [Remote host closed the connection]
bramc has quit [Quit: This computer has gone to sleep]