andytoshi changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | This channel is logged. | For logs and more information, visit https://bitcoin.ninja
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
laptop has quit [Ping timeout: 246 seconds]
ddustin has quit [Remote host closed the connection]
willcl_ark has quit [Ping timeout: 240 seconds]
willcl_ark has joined #bitcoin-wizards
TheoStorm has quit [Quit: Leaving]
rusty has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
jonatack_ has joined #bitcoin-wizards
thrasher` has quit [Ping timeout: 240 seconds]
jonatack has quit [Ping timeout: 260 seconds]
thrasher` has joined #bitcoin-wizards
justan0theruser has joined #bitcoin-wizards
TheoStorm has quit [Quit: Leaving]
TheoStorm has joined #bitcoin-wizards
chjj has quit [Quit: WeeChat 2.2]
kenshi84_ has joined #bitcoin-wizards
chjj has joined #bitcoin-wizards
kenshi84 has quit [Ping timeout: 265 seconds]
sr_gi has quit [Read error: Connection reset by peer]
sr_gi has joined #bitcoin-wizards
jadi has joined #bitcoin-wizards
jadi has quit [Ping timeout: 240 seconds]
tomkap1 has quit [Remote host closed the connection]
chaosagent has joined #bitcoin-wizards
belcher_ has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
belcher has quit [Ping timeout: 260 seconds]
justan0theruser has quit [Ping timeout: 240 seconds]
TheoStorm has quit [Quit: Leaving]
AaronvanW has joined #bitcoin-wizards
troygiorshev has quit [Ping timeout: 256 seconds]
ghost43 has quit [Remote host closed the connection]
Kiminuo has quit [Read error: Connection reset by peer]
chaosagent has quit [Remote host closed the connection]
AaronvanW has quit [Ping timeout: 260 seconds]
rusty has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
Stephnix has joined #bitcoin-wizards
rusty has quit [Quit: Leaving.]
rusty has joined #bitcoin-wizards
shesek has quit [Remote host closed the connection]
AaronvanW has quit [Ping timeout: 256 seconds]
reallll has joined #bitcoin-wizards
belcher_ has quit [Ping timeout: 260 seconds]
Kiminuo has joined #bitcoin-wizards
rusty has quit [Ping timeout: 256 seconds]
AaronvanW has joined #bitcoin-wizards
jadi has quit [Read error: Connection reset by peer]
jadi has joined #bitcoin-wizards
sr_gi has quit [Read error: Connection reset by peer]
sr_gi has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 264 seconds]
shesek` has joined #bitcoin-wizards
reallll is now known as belcher
son0p has joined #bitcoin-wizards
jonatack_ has joined #bitcoin-wizards
jonatack_ has quit [Quit: jonatack_]
jonatack has joined #bitcoin-wizards
shesek` is now known as shesek
shesek has quit [Changing host]
shesek has joined #bitcoin-wizards
son0p has quit [Quit: Lost terminal]
son0p has joined #bitcoin-wizards
CryptoDavid has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
bitdex has quit [Quit: = ""]
AaronvanW has quit []
AaronvanW has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
harrigan has quit [Ping timeout: 246 seconds]
harrigan has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
Kiminuo has quit [Quit: Leaving]
vcorem has quit [Quit: Leaving]
son0p has quit [Quit: Lost terminal]
yanmaani has quit [Ping timeout: 268 seconds]
TheoStorm has quit [Quit: Leaving]
yanmaani has joined #bitcoin-wizards
jadi has quit [Ping timeout: 265 seconds]
jadi has joined #bitcoin-wizards
jeremyrubin has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
ddustin_ has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 240 seconds]
ddustin_ has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
someone235 has joined #bitcoin-wizards
rewhget has joined #bitcoin-wizards
rewhget has quit [Client Quit]
jeremyrubin has quit [Ping timeout: 240 seconds]
jeremyrubin has joined #bitcoin-wizards
Stephnix has quit [Remote host closed the connection]
brg444_ has joined #bitcoin-wizards
brg444_ has quit []
brg444 has joined #bitcoin-wizards
brg444 has quit [Client Quit]
brg444_ has joined #bitcoin-wizards
brg444_ has quit [Client Quit]
brg444 has joined #bitcoin-wizards
FrontSevens has joined #bitcoin-wizards
ghost43_ has quit [Quit: Leaving]
ghost43 has joined #bitcoin-wizards
jadi has quit [Ping timeout: 246 seconds]
jadi has joined #bitcoin-wizards
proofofkeags has joined #bitcoin-wizards
jeremyrubin has quit [Quit: Konversation terminated!]
Iriez has quit [Remote host closed the connection]
son0p has joined #bitcoin-wizards
fluffypony has quit [Disconnected by services]
Guest87054 has joined #bitcoin-wizards
Guest87054 has quit [Quit: peace out, A town]
TheoStorm has joined #bitcoin-wizards
Iriez has joined #bitcoin-wizards
son0p has quit [Quit: leaving]
<gleb>
I was recently thinking about the IBD dos issue, where someone can feed us with low-work really-long which we'd take forever to download/verify. I think that's why we have checkpoints right? And the approach is still suboptimal
<gleb>
I'm sorry if I'm misunderstanding something and unintentionally spreading fud about checkpoints...
<sipa>
well blocks wouldn't be downloaded until you provide the victim with a valid headers chain whose combined cumulative work exceeds the main chain's
<gleb>
sipa: still, headers should be downloaded?
<sipa>
which won't happen until there is actual a hashrate majority cooperating with the attacker
<sipa>
in which case we have bigger problems
<gleb>
I remember suhas tried to do something smart, reverse load or something.
<sipa>
(or really, then they're not an attacker anyway)
<gleb>
I was wondering if this could be done with a snark instead?
<sipa>
gleb: yes, that's possible, but that's what checkpoints exist for
<sipa>
they'd need to branch off past the last checkpoint
<gleb>
A source-of-blocks provides a compact proof that their chain is "legit" whatever that means
rusty has joined #bitcoin-wizards
<gleb>
That would allow removing checkpoints and maybe making it more robust.
<pinheadmz>
gleb like, offer the highest header first so you can see how much work it has?
<sipa>
which is a long time ago, but still means a very nontrivial Pow cost for the attacker per block, due to the difficulty that existed at the time
<pinheadmz>
then load headers in reverse until it connects if that value is high enouch
<sipa>
pinheadmz: you can't tell from a header how much work the entire chain has
<pinheadmz>
ah, only the bits target for that one single header
<sipa>
yes, but you can't really make assumptions about the difficulty at any particular point in the future
<pinheadmz>
so you can imagine difficulty going way up and then way down and having a header with an easy target, even though it is the most work chain
<sipa>
except using the max-4x-drop-per-2016-blocks rule
<gleb>
sipa: won't a snark be better approach than checkpoints? Of course they have to be properly designed :)
<pinheadmz>
the paper has a "headers with checkpoints variant" -- It would cost around $1,433,924 USD in mining hardware and electricity to produce 315GB of payload header data in 450 hours with ability to add
<pinheadmz>
additional data at a rate of 315GB per hour for $104 USD
son0p has joined #bitcoin-wizards
<sipa>
gleb: long term checkpoints are pretty unsatisfying, but i also don't think there is a real problem today
<gleb>
sipa: yeah sure, I was just thinking of experimenting with zkp and that felt like a might-be-useful problem to solve.
<gleb>
Optional plugin for bitcoin core which does zkp instead of checkpoints
<gleb>
Okay, I guess if someone ever worked on it, you'd probably know and let me know :)
<sipa>
yeah, i think it's an interesting problem
<sipa>
but wouldn't headers-validity of an entire chain be an enormous amount of work to construct a snark for?
<sipa>
100000s of SHA256s
<pinheadmz>
if you use a zkSNARK would oyu have to implement the bitcoin diff adjust algorithm ?
DeanWeen has quit [Remote host closed the connection]
<pinheadmz>
ha sipa yeah
<sipa>
that's trivial i think compared with SHA256 :p
<pinheadmz>
right everytime i try to learn about snarks my brain melts around the "write the program in logic gates" etc
<pinheadmz>
like, at that point dosnt it reuire so much human auditing of *that* code that the snarks isnt worth it?
<pinheadmz>
(for omplex problems)
<sipa>
a very quick guesstimate makes me think you'd need over 10 billion multiplication gates in the proof
<sipa>
as it's a long repetition of the exact same operation
CryptoDavid has quit [Quit: Connection closed for inactivity]
<gleb>
Good to know, thank you for the feedback. I'll think about it now.
<sipa>
pinheadmz: that only needs a few hash operations
<sipa>
pinheadmz: in a snark, if you compute multiple hashes, you need to multiply the gate counts
<pinheadmz>
sipa you dont have to implement ECDSA and bip32 ?
<pinheadmz>
ok i see, keep hash count low, maintain sanity
<sipa>
if you use a proof system with a compatible group order, you wouldn't need to implement EC multiplication inside the circuit
<pinheadmz>
ahhh oh kay interesting
<sipa>
(you can't use snarks then of course, because no pairing-friendly group with the secp256k1 order is known)
rusty has quit [Ping timeout: 240 seconds]
DeanGuss has joined #bitcoin-wizards
<andytoshi>
gleb: if you are thinking of doing a stark of blockheaders that would be amazing!!
sdaftuar has joined #bitcoin-wizards
<sipa>
starks also don't have strong security assumptions afaik
<andytoshi>
i think it's definitely feasible. i don't have a good intuition for concrete numbers. if you had to use a machine with 500gb of RAM for 2 weeks to produce the proof it wouldn't shock me (and we can get you such a machine :P)
<sipa>
and for the application of proving header validity, their large proofs aren't really a problem
<sipa>
andytoshi: i don't think it's interesting if it can't be basically done on the fly by normal nodes
<andytoshi>
sipa: you mean, the security assumptions are "safe"
<andytoshi>
i always get strong/weak backward :)
<andytoshi>
sipa: well it might be ok if the first 650000 blocks take forever
<andytoshi>
and then nodes are just adding a few (dozen) at a time afterward
<sipa>
andytoshi: i mean, if you're only going to do it once, we can just use a checkpoint at that height instead :p
<andytoshi>
sipa: you can extend existing starks, is my point. at the very least by doing a recursive stark
<andytoshi>
but there are also papers about somehow inherently making them extensible
<andytoshi>
if you have some pre-stark data to work with
<sipa>
andytoshi: and doing a few dozen is not interesting either; headers are 80 bytes... if the proof is bigger than the headers we don't really gain anything
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
<sipa>
you probably need to be able to construct for 1000s of headers at once at least
<sipa>
hmm, recursive starks may be useful
<sdaftuar>
i'm a little late to this conversation but just tried to catch up on the logs. it seemed to me that once we have p2p logic that solved this problem, we would never need to use it, because there would be no incentive to do this attack.
<andytoshi>
oh, yeah, i hadn't considered that you could non-recursively stark up 50000 blocks at once (say) and that'd still be valuable
<sdaftuar>
so i think that creates some sort of bound on how much effort to go to, to design a solution
<gleb>
sdaftuar: I know this is a weird question, but do you think the p2p approach is easy enough?
<andytoshi>
sdaftuar: i can imagine the starks being useful beyond an anti-DoS mechanism
<sipa>
andytoshi: hmm if a stark is feasible for just proving one header's chainwork recursively in function of a proof of the previous block... that might be practical if one step of the proof is relatively cheap to construct
<sdaftuar>
andytoshi: ah then that probably makes more sense than the kind of p2p logic i was envisioning, which was definitely not useful beyond the thing i tried to write it for :)
<sipa>
because then you have an O(1) incrementally computable thing, that any node could keep updated, and provide to any other node that asks for it
<andytoshi>
lol, well, i'm missng context about how this would integrate into the p2p layer :) i just came here to shill starks' computational feasibility
<sdaftuar>
gleb: i managed to write code that i *believe* works, even without a p2p protocol extension (i opened, and hten closed a pull request with the logic, so people could look at it if they cared).
<sdaftuar>
gleb: it would be easier with a p2p protocol extension that enabled reverse headers fetching
<sipa>
"what is you best chain's tip work, and prove to me that a chain with that much work actually exists" - "here ya go"
<sdaftuar>
that seems nice!
<gleb>
andytoshi: what do you think are other applications of headers stark?
<gleb>
I can only shamefully think of some wrapped bitcoin whatever...
<andytoshi>
gleb: well, if i give you a stark that a header is the tip of the best-work chain, then when i give you the actual headers you only need to check that they form a chain
<sipa>
sdaftuar: with a stark this would still be in the 10s of kilobytes (or 100s?) of proof data... but not 10s of MB
<andytoshi>
you don't need to check nBits, check the PoW etc
<gleb>
may be useful for light clients?
<andytoshi>
yes
<andytoshi>
and you can do better..
<sipa>
a recursive snark (not really up to date how far those are along...) would do the same with a tiny amount of data
<sdaftuar>
andytoshi: so the stark somehow encodes the bitcoin headers consensus rules, is the idea? what about timestamp?
<gleb>
And actually, when I receive a payment, it's really a payer should *prove* the transaction is in the heaviest (heavy enough) chain
<andytoshi>
i can provide a stark that (a) a blockheader is the tip of a best-work chain, and (b) all its blocks are committed to in a merkle tree whose root i provide (which also commits to height and other stuff you might care about)
<andytoshi>
and now you have a way to quickly check individual blocks without downloading the whole chain
<sipa>
andytoshi: hmmm!
<sipa>
do you need a stark for that?
<andytoshi>
sdaftuar: yeah, i'm thinking specifically about the difficulty/PoW rules
<sdaftuar>
there's also the pesky 2 hour rule
<sipa>
you could envision an interactive protocol where you first commit to a merkle sum tree of blockheader chainwork, and i make a few random queries in that tree
<andytoshi>
true sdaftuar ... like everything consensus-wise it'd spiral out and be hard to capture. but i think it's feasible to do. (unlike, say, trying to caputer all the Script rules)
<andytoshi>
sipa: well, the hard part is that you want to verify that the challenge blockheaders are actually in the chain
<sipa>
andytoshi: so you ask to reveal a few random pairs of subsequent headers, and see the later one refers to the previous one?
<andytoshi>
and if you want to do that without needing O(height) many blockheaders, you need some stark-like thing
<andytoshi>
sipa: hmmmmmm
<sipa>
this feels related to flyclient
<andytoshi>
that's pretty clever
<andytoshi>
yeah i could believe this could work
<sipa>
you can bias your queries in function of chainwork too
<sipa>
if you interactive descend through the tree
<sipa>
(or fiat-shamir it...)
<andytoshi>
just revealing random pairs i think isn't enough, if you lie about a single connection you can create a pretty destructive false proof and you might not get caught
<andytoshi>
biasing in terms of chainwork would help
<gleb>
Thank you, I didn't expect us having so good discussion here.
<gleb>
I'll probably take a closer look in a week or two, and will post here if I have any results.
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
son0p has quit [Quit: Lost terminal]
tromp has quit [Ping timeout: 260 seconds]
<phantomcircuit>
sipa, yeah i guess walking backwards would let you apply some kind of sanity check by asking many peers for their tip but also what if the chain with the most work has a recent run of lower difficulty blocks
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 256 seconds]
justan0theruser has quit [Ping timeout: 240 seconds]