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
jae_ has quit [Remote host closed the connection]
ruby32 has quit [Quit: ruby32]
Emcy_ has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 250 seconds]
user7779_ has joined #bitcoin-wizards
user7779078 has quit [Ping timeout: 276 seconds]
c0rw1n is now known as c0rw|zZz
jtrag has joined #bitcoin-wizards
FranzKafka has joined #bitcoin-wizards
bramc has joined #bitcoin-wizards
alferz has joined #bitcoin-wizards
<bramc>
amiller, Not sure what you man, I'm trying to read the paper and am a bit lost in the weeds
<amiller>
bramc, hi, wait which do you want to talk about, proof of space or the cuckoo thing :)
<bramc>
amiller, looking through the channel logs, I'm confused what the reference to cuckoo is
<bramc>
amiller, I don't understand what he's claiming about cuckoo
alferz has joined #bitcoin-wizards
<bramc>
It seems implausible that such a trivial handwavy thing could bust cuckoo, given the amount of analysis it's had. All he's saying is 'oh, do a parallel sort'
Tiraspol has quit [Ping timeout: 246 seconds]
<amiller>
also, who cares about time-memory tradeoff the point is work-memory tradeoff
<bramc>
Since cuckoo is looking for cycles rather than collisions that seems basically inapplicable
Tiraspol has joined #bitcoin-wizards
Tiraspol has quit [Changing host]
Tiraspol has joined #bitcoin-wizards
<bramc>
Right, you can always do it faster if you're willing to tolerate exponential blowup in power consumption
<bramc>
Although cuckoo is reasonably resistant to that as well.
<amiller>
im not sure how to improve any intuition of it
jae_ has quit [Ping timeout: 265 seconds]
<amiller>
i wish i had an intuitive grasp for what super concentrators and expanders looks like
<bramc>
amiller, Even a straight answer to what the structure of the verifies is would be helpful. Is it a bunch of ancestors of a root revealed?
<amiller>
i think it can just be a bunch of leaves
<amiller>
and the branches to the root
<amiller>
i think it helps to understand a couple of strawman schemes
<amiller>
one they mention explicitly is where you have 100GB of actual random data
<amiller>
you have to fetch that data from a source
<bramc>
Yeah I figured out random data on my own. They say there are time space tradeoffs
<amiller>
to satisfy a large number of small random queries, you'd have to be storing a large fraction of that space
<amiller>
okay so another approach is to do several rounds of these all-or-nothing transforms
<amiller>
where you fill up the 100GB, then apply some function that accesses every byte and gives you a new 100GB, and then do this several times
<amiller>
but now you'd have to prove it's done correctly somehow
<amiller>
as a strawman, you could compute a merkle tree of the final 100GB, and a once-and-for-all snark proof that shows its coonstructed correctly
jae_ has joined #bitcoin-wizards
<amiller>
then the challenge can be answered efficiently and you don't need a lot of communication, but the setup computation is infeasible
<bramc>
I get the merkle root of random data one. The problem there is you don't have to store all the leaves, you can recompute the last few hops of them in parallel
<amiller>
well, that requires accessing a lot of memory
<bramc>
I'm thinking there's a challenge which specifies the path backwards from the root which must be revealed, so it's only logarithmic lookups
<amiller>
you will have to reveal entire paths to the root
<amiller>
i think a sequence is, a) build a confusing dag, b) build a merkle tree on top of the dag (the combined tree is still a dag) c) reveal paths from the merkle root to randomly chosen nodes in the original dag
<bramc>
Right, that seems to be the general structure
<bramc>
But what the form of the dag is and why is mysterious to me
<amiller>
i think its just alternating layers of superconcentrators, bipartite expanders, and Erdos depth robust graphs
<amiller>
(i have no idea what any of those are)
bendavenport has quit [Quit: bendavenport]
<amiller>
well its not the Erdos depth robust graphs its Erdos dense-long-path graphs.
<amiller>
the most unintuitive part to me is that with such small samples, that you have a guarantee the graph is constructed mostly correctly
<bramc>
All the examples I work through myself there are trivial cpu-space tradeoffs
<bramc>
Although this does seem to indicate why I was able to improve on proofs of time: the dense long paths construction is about requiring memory, not time, which isn't what you want for a pure proof of sequential work
hazirafel has quit [Quit: ChatZilla 0.9.91.1 [Firefox 38.0.1/20150513174244]]
<bramc>
Of course that means that my clever tricks really, really don't apply to this problem
<amiller>
bramc, the best proof of time puzzle uses a different family of graphs
<bramc>
amiller, I figured out a neat improvement on the best proof of time puzzles (unpublished)
CodeShark_ has quit [Ping timeout: 264 seconds]
CodeShark has quit [Ping timeout: 246 seconds]
<amiller>
bramc, ok im curious about that and how it compares to this 2011/553 thing, especially since they don't have any concrete parameters or implementaiton
<bramc>
amiller, Mine is a lot prettier and simpler. I think I even implemented it already
<amiller>
i want to make a little wacky-dags library that has these superconcentrators, expanders, deep and long
<amiller>
bramc ok how does it work
<bramc>
Unfortunately it isn't canonical, so the really dumb approach is better for a proof of time in a cryptocurrency
<amiller>
ah
<amiller>
i think this one has a single canonical correct one
<amiller>
but it doesn't rule out that you can cheat a small number of them, and alter the resulting hash
<bramc>
Right, you can cheat with a miniscule number of the steps and your chances of being busted are practically nothing and someone will have to redo all the work from scratch to find out
<bramc>
So, the trick is that there's a merkle root of the things which were calculated in strict sequential order
<amiller>
ok
<amiller>
so, first i builld a big hash chain sequentially, then i build a merkle root over that
<amiller>
then what, select random leaves of the tree / elements of the chain to reveal?
belcher has quit [Quit: Leaving]
<bramc>
And the way you calculate each of the leaves is by calculating as much of the merkle tree as you can so far, then hashing together those branch roots to make the new leaf
<bramc>
Then yes, you use the root as a seed to determine which leaves to reveal. The beauty of this construction is that the branch roots revealed on the way to the leaf are exactly the things which need to be hashed together to form the leaf, so it all can be verified together.
<amiller>
i don't see how that rules out malicious strategies that 'cheat' on a small number of links, optimized to allow the computing the 'good' links with parallelism
<bramc>
I don't have a simple explanation of why this seems to work but it does. The construction sort of collapses in on itself.
<bramc>
If you try to attack it the attacks all seem to subtly not work, basically boiling down to skipping only a constant fraction and grinding, which you can of course do.
<bramc>
That's the other reason for preferring the dumb approach
rht__ has joined #bitcoin-wizards
<bramc>
Maybe the more sophisticated constructions are more resistant to those sorts of attacks for deep reasons which I don't understand.
<bramc>
Basically if you skip out on half and have N challenges then you need to run 2^N grinding to pull off a fake proof of sequential work
<bramc>
I *think* that the other constructions have the same property, but I'm not 100% sure.
<amiller>
the point isn't to skip half the nodes, but to lie about a very small number of links... you'll compute nearly the same amount of total work, but you can take advantage of the bogus links to do it in parallel
<bramc>
Oh that seems to be covered. If you try to cheat that way you'll get busted by the branch roots being wrong
<bramc>
It feels like there's something subtle to the whole thing which I have some trouble giving a good intuition for.
<amiller>
yeah, me too
hodI is now known as bosma
<amiller>
i think the approach taken by the academics is try to optimize for building graphs from esoteric parts (they have a big toolbox of parts to draw from) that can easily be proven to have the right property
<amiller>
the other approach is to build graphs with simple intuitive structure, that seems to solve the problem by preventing any deviations
<amiller>
so one possibility is that our solutions are also correct, just simpler to intuit but harder to prove... the academic ones are correct and easier to prove, harder to intuit why it solves the problem at all
<bramc>
Yes I believe that's correct
<bramc>
I'm off to the bitcoin-dev meeting now, laters
<midnightmagic>
bramc: I wasn't expecting your talk to go the way it did. Thanks for letting me know it exists. Just as a tangent, a significant fraction of the electricity used in building the historical block chain has been hydroelectric with a zero carbon-emissions footprint.
<bramc>
midnightmagic, Some devs were telling me that the recent stuff in china seems to mostly be hydro, which is good, although that's also offsetting other potential uses of that same power
<bramc>
Not all that awful though since it's in an awkward out of the way place where it's hard to use the power well. It still sucks, but it's better
<midnightmagic>
bramc: New hydro projects are significant carbon footprints. The old ones like in BC, Canada can claim *modern* zero-emissions.
<midnightmagic>
woops, sorry, I didn't realize you were on your way out. Apologies, I'll stop bugging you. :)
bramc has quit [Quit: This computer has gone to sleep]
sy5error has quit [Remote host closed the connection]
FranzKafka has quit []
drwin has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
c-cex-yuriy has joined #bitcoin-wizards
rubensayshi has joined #bitcoin-wizards
bendavenport has quit [Quit: bendavenport]
sparetire_ has quit [Quit: sparetire_]
rustyn has quit []
orperelman has joined #bitcoin-wizards
ThomasV has quit [Quit: Quitte]
Mably has joined #bitcoin-wizards
user7779078 has joined #bitcoin-wizards
kisspunch has joined #bitcoin-wizards
kisspunch has left #bitcoin-wizards [#bitcoin-wizards]
AaronvanW has quit [Remote host closed the connection]
user7779078 has quit [Ping timeout: 264 seconds]
paveljanik has quit [Quit: Leaving]
AaronvanW has joined #bitcoin-wizards
TheLast has joined #bitcoin-wizards
<TheLast>
why are you allowed to send transactions without any fee?
p15x_ has joined #bitcoin-wizards
p15x has quit [Ping timeout: 265 seconds]
erasmospunk has joined #bitcoin-wizards
<Adlai>
fees are a DDoS resistence mechanism. mining is [currently] subsidized by inflation.
FranzKafka has joined #bitcoin-wizards
<TheLast>
exactly, so why does the network allow you to send transactions without paying any fee?
<TheLast>
should these not be blocked entirely to prevent spam attacks
<TheLast>
like the one we're currently seeing
<Adlai>
"spam" is fiction. there is a price for priority insertion to the ledger, and it adapts based on the queue size and how much others are willing to pay.
<gmaxwell>
TheLast: those attackers are paying fees. very tiny fees, but normally transactions pay very tiny fees.
Madars has quit [Ping timeout: 252 seconds]
erasmospunk has quit [Ping timeout: 252 seconds]
FranzKafka has quit []
Madars has joined #bitcoin-wizards
Tenhi has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
TheLast has left #bitcoin-wizards [#bitcoin-wizards]
<TheLast>
gmaxwell: do you think these spam attacks are bad for Bitcoin?
<gmaxwell>
TheLast: I don't think most people notice them at all, due to reasonably prioritization policies in some miners most txn go though without much delay.
CodeShark_ has joined #bitcoin-wizards
<gmaxwell>
AFAICT it's some promotion stunt to raise attention for some scammy website or something, who knows, who cares.
<stonecoldpat>
TheLast: considering these spam attacks and network forks, the price of bitcoin remains unaffected (has in fact gone up) - so most users dont really care
dEBRUYNE has joined #bitcoin-wizards
wallet42 has quit [Quit: Leaving.]
erasmospunk has joined #bitcoin-wizards
<CodeShark_>
stonecoldpat: I don't think most users aren't even really aware. Did anyone even cover these things in the popular press?
<gmaxwell>
CodeShark_: if the attacks mattered people would be aware of them without coverage!
<CodeShark_>
*are
rht__ has quit [Quit: Connection closed for inactivity]
<CodeShark_>
gmaxwell: did you compile that dropped tx list?
<gmaxwell>
CodeShark_: still reindexing; :( lost a couple hours away from power, it'll be done in the morning.
<gmaxwell>
speaking of that, goodnight
<CodeShark_>
goodnight
<stonecoldpat>
night, and CodeShark_: I dont think there is anything in popular press which is probably a good thing (boring news)
<CodeShark>
well, at least some people surely noticed some unusually deep reorgs
user7779078 has joined #bitcoin-wizards
TheLast has quit [Quit: Leaving.]
AaronvanW has quit [Ping timeout: 246 seconds]
user7779078 has quit [Ping timeout: 264 seconds]
orperelman has quit [Ping timeout: 246 seconds]
orperelman has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
metamarc has quit [Read error: Connection reset by peer]
metamarc has joined #bitcoin-wizards
waxwing has quit [Read error: Connection reset by peer]
JackH has joined #bitcoin-wizards
<JackH>
is the only available Bitcoin core version 10? unless I compile myself? For ubuntu
<JackH>
only = latest
<CodeShark>
try #bitcoin
waxwing has joined #bitcoin-wizards
Starduster_ has joined #bitcoin-wizards
Starduster has quit [Ping timeout: 256 seconds]
ThomasV has quit [Ping timeout: 255 seconds]
paveljanik has joined #bitcoin-wizards
Starduster_ is now known as Starduster
orperelman has quit [Ping timeout: 246 seconds]
Quanttek has joined #bitcoin-wizards
Oizopower has joined #bitcoin-wizards
p15x has joined #bitcoin-wizards
p15x_ has quit [Ping timeout: 252 seconds]
c0rw|zZz is now known as c0rw1n
user7779078 has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
user7779078 has quit [Ping timeout: 252 seconds]
priidu has quit [Ping timeout: 250 seconds]
c-cex-yuriy has quit [Quit: Connection closed for inactivity]
p15x has quit [Max SendQ exceeded]
p15x has joined #bitcoin-wizards
arubi_ has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
chmod755 has joined #bitcoin-wizards
bi_fa_fu_ has joined #bitcoin-wizards
bi_fa_fu has joined #bitcoin-wizards
moa has quit [Quit: Leaving.]
ThomasV has quit [Quit: Quitte]
bi_fa_fu_ has quit []
justanotheruser has quit [Ping timeout: 265 seconds]
<bramc>
zooko, Password hashing schemes aren't proof of work schemes
kerneloops has quit [Quit: I rage quit!]
<bramc>
Password hashing is supposed to be expensive to verify. Proof of work is supposed to be cheap to verify.
kerneloops has joined #bitcoin-wizards
<zooko>
bramc: that's what that link is about.
samson_ has joined #bitcoin-wizards
Giszmo has joined #bitcoin-wizards
starsoccer has quit [Read error: Connection reset by peer]
starsoccer has joined #bitcoin-wizards
<gmaxwell>
zooko: bleh. I think that whole discussion is OT for PHC. A point you may be missing there is that an ideal consensus POW function is progress free-- progress gives advantages to centeralized attackers; so thats an extra consideration around a single run of the algorithim taking a long time.
starsoccer is now known as Guest27290
gielbier has joined #bitcoin-wizards
Guest27290 has quit [Changing host]
Guest27290 has joined #bitcoin-wizards
Guest27290 is now known as starsoccer
starsoccer is now known as Starsoccer
<zooko>
gmaxwell: yeah, that's a very good point.
gielbier has quit [Ping timeout: 248 seconds]
jae_ has joined #bitcoin-wizards
<pigeons>
what is an advantage of "memory hardness"?
<zooko>
Posted a further extension of the talking-to-myself-off-topic thread on PHC…
<bramc>
pigeons, Memory is more commodity than CPU. A memory hard problem might be more resistant to custom chips outperforming commodity ones
<bramc>
Whether that's a real benefit is a different discussion
gielbier has joined #bitcoin-wizards
<nsh>
the main advantage is advancing the state of understanding of the hardness of making things hard
<pigeons>
yeah i think i saw some info on "outperforming" being arguable considering energy use
<gmaxwell>
kanzure: you're like a whole day late on that. :)
<Eliel>
practically speaking, there's no reason for any single person to validate any block twice. For my own use, given that I had a secure way to generate signatures with a personal high security key, I could just trust any block that's been signed with it.
<kanzure>
gmaxwell: a new low for me... alas.
bendavenport has quit [Quit: bendavenport]
se3000 has quit [Quit: se3000]
bramc has quit [Quit: This computer has gone to sleep]
<fluffypony>
kanzure: if it's zero knowledge then how can anyone know it, duh
<fluffypony>
also have we spoken about how HackingTeam's dump includes a BTC wallet swiper...
zefiris has quit [Quit: Page closed]
<kanzure>
no, although i think everyone saw it
<gmaxwell>
I'd pinged someone to fetch the arcive to look for bitcoin stuff.
bendavenport has joined #bitcoin-wizards
<kanzure>
actually, do we have a link to the swiper