sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
worstadmin has joined #bitcoin-wizards
thrmo_ has quit [Quit: Waiting for .007]
so has joined #bitcoin-wizards
opdenkamp has quit [Ping timeout: 260 seconds]
AaronvanW has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 245 seconds]
keymone has quit [Ping timeout: 252 seconds]
opdenkamp has joined #bitcoin-wizards
michaelsdunn1 has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
dougsland has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
keymone has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 252 seconds]
Belkaar has quit [Ping timeout: 240 seconds]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
grubles has quit [Quit: Leaving]
Murchone has quit [Quit: Snoozing.]
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 244 seconds]
_tin has quit [Ping timeout: 252 seconds]
RubenSomsen has joined #bitcoin-wizards
nuncanada has quit [Ping timeout: 252 seconds]
roconnor_ has quit [Quit: Konversation terminated!]
roconnor_ has joined #bitcoin-wizards
roconnor_ has quit [Client Quit]
roconnor has joined #bitcoin-wizards
_tin has joined #bitcoin-wizards
treyzania has quit [Quit: ZNC 1.6.6 - http://znc.in]
treyzania has joined #bitcoin-wizards
_tin has quit [Ping timeout: 240 seconds]
Krellan has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 252 seconds]
rmwb has joined #bitcoin-wizards
dougsland has quit [Ping timeout: 240 seconds]
rmwb has quit [Ping timeout: 240 seconds]
morcos has quit [Remote host closed the connection]
morcos has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 252 seconds]
intcat has quit [Remote host closed the connection]
intcat has joined #bitcoin-wizards
rh0nj has quit [Remote host closed the connection]
rh0nj has joined #bitcoin-wizards
worstadmin has quit [Quit: Connection closed for inactivity]
bitconner has quit [Ping timeout: 252 seconds]
bitconner has joined #bitcoin-wizards
bitconner has quit [Ping timeout: 252 seconds]
rmwb has joined #bitcoin-wizards
tromp_ has joined #bitcoin-wizards
tromp has quit [Ping timeout: 260 seconds]
rmwb has quit [Ping timeout: 252 seconds]
echonaut has quit [Remote host closed the connection]
echonaut11 has joined #bitcoin-wizards
setpill has joined #bitcoin-wizards
phwalkr has joined #bitcoin-wizards
bitconner has joined #bitcoin-wizards
bitconner has quit [Ping timeout: 252 seconds]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 252 seconds]
Nebraskka_ has quit [Quit: Good day, my fellow citizens!~]
Nebraskka has joined #bitcoin-wizards
waxwing| has left #bitcoin-wizards ["Leaving"]
bitconner has joined #bitcoin-wizards
shesek has quit [Ping timeout: 245 seconds]
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
TheoStorm has quit [Remote host closed the connection]
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
phwalkr has quit [Ping timeout: 252 seconds]
AaronvanW has joined #bitcoin-wizards
phwalkr has joined #bitcoin-wizards
bitconner has quit [Ping timeout: 252 seconds]
rmwb has joined #bitcoin-wizards
phwalkr has quit [Ping timeout: 240 seconds]
thrmo has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
phwalkr has joined #bitcoin-wizards
phwalkr has quit [Ping timeout: 240 seconds]
rmwb has quit [Ping timeout: 245 seconds]
Guyver2 has joined #bitcoin-wizards
shesek has quit [Ping timeout: 252 seconds]
enemabandit has joined #bitcoin-wizards
dougsland has joined #bitcoin-wizards
intcat has quit [Remote host closed the connection]
dougsland has quit [Ping timeout: 245 seconds]
intcat has joined #bitcoin-wizards
thrmo_ has joined #bitcoin-wizards
thrmo has quit [Remote host closed the connection]
sdaftuar_ is now known as sdaftuar
sdaftuar has quit [Changing host]
sdaftuar has joined #bitcoin-wizards
sipa has quit [Remote host closed the connection]
sipa has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
thrmo_ has quit [Remote host closed the connection]
thrmo_ has joined #bitcoin-wizards
bitconner has joined #bitcoin-wizards
bitconner has quit [Ping timeout: 264 seconds]
CheckDavid has joined #bitcoin-wizards
thrmo_ is now known as thrmo
SopaXorzTaker has joined #bitcoin-wizards
<Varunram>
"Fraud Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities": https://arxiv.org/pdf/1809.09044.pdf?
rmwb has joined #bitcoin-wizards
phwalkr has joined #bitcoin-wizards
nuncanada has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 272 seconds]
victorSN has quit [Read error: Connection reset by peer]
rockhouse has quit [Read error: Connection reset by peer]
victorSN has joined #bitcoin-wizards
rockhouse has joined #bitcoin-wizards
bitconner has joined #bitcoin-wizards
bitconner has quit [Ping timeout: 250 seconds]
Nebraskka has quit [Quit: Good day, my fellow citizens!~]
Nebraskka has joined #bitcoin-wizards
Nebraskka has quit [Quit: Good day, my fellow citizens!~]
Nebraskka has joined #bitcoin-wizards
phwalkr has quit [Ping timeout: 244 seconds]
dougsland has joined #bitcoin-wizards
Giszmo1 has joined #bitcoin-wizards
phwalkr has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 260 seconds]
Giszmo1 has quit [Ping timeout: 252 seconds]
michaelsdunn1 has joined #bitcoin-wizards
sfhi has joined #bitcoin-wizards
Giszmo has joined #bitcoin-wizards
<gmaxwell>
wow I think it's really unfortunately that they failed to credit the origin of the sampling based anti-censorship-- which I had previously explained directly to one of the authors, even the term fraud proof is one I intoduced, yet the paper seems to make no mention of any of the bitcoin discussion on the subject.
<gmaxwell>
maybe the eth huffers will market it to the point of it sounding interesting to others, finally.
Chris_Stewart_5 has quit [Ping timeout: 252 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
<gmaxwell>
Particularly sad in that I've explained the sampling approach specifically in response to their past publication on 'fraud proofs' that failed to acknoweldge other work in this space.
<gmaxwell>
"This is also sad because unawareness of other work means that they weren't aware that the community actually has an interesting and powerful improvment to fraud censorship" ... "The improvement we have is this, a party offering a block to the network can be required to code it using a locally decodable rateless error correcting code" ... "Now, when people fetch, they pick random parts to fetch,
<gmaxwell>
and check those parts.. but if the sever transmits more than the total block size in aggregate, the other nodes can colaborate to recover any censored parts"
<RubenSomsen>
Does the process described in the paper actually manage to make fraud proofs viable? My comprehension reached its limit when the paper started talking about fraud proofs for the validity of extended data...
Murch has joined #bitcoin-wizards
<gmaxwell>
I don't think it makes it any more viable than they were in 2015: The coding based anticensorship isn't that strong an improvement: you end up having to send a lot of data to only get a moderately high confidence that the block is actually recoverable.
<gmaxwell>
if its viable depends on if you consider the resulting parameters useful.
p0nziph0ne has quit [Ping timeout: 244 seconds]
<RubenSomsen>
I see, I have no idea how much data it is, but it seemed problematic to me that light clients need to fetch more data just to make sure the extended data is in order
waxwing has joined #bitcoin-wizards
SopaXorzTaker has quit [Quit: Leaving]
rmwb has joined #bitcoin-wizards
p0nziph0ne has joined #bitcoin-wizards
_tin has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 252 seconds]
bitconner has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
bitconner has quit [Ping timeout: 252 seconds]
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 264 seconds]
enemabandit has quit [Ping timeout: 245 seconds]
<musalbas>
gmaxwell, we do mention some of the bitcoin discussions in the related work section. the paper however is a preprint and thus comments are welcome. thanks for your feedback, and pointers to related discussions. i will see if i can cite lines of irc chat logs in the bibliography; i was not aware of them.
<musalbas>
>you end up having to send a lot of data to only get a moderately high confidence that the block is actually recoverable.
<musalbas>
In section 5.6 and 6, we discuss the amount of data that needs to be sent, and the confidence that you have
<musalbas>
"Figure 6 shows how this probability varies with s samples for k = 32 and k = 256; each light client samples at least one unavailable share with about 60% probability after 3 samplings (i.e., after querying respectively 0.07% of the block shares for k = 32 and 0.001% of the block shares for k = 256), and with more than 99% probability after 15 samplings (i.e., after querying respectively 0.4% of the block shares for k = 16 and 0.005% of
<musalbas>
the block shares for k = 256). Figure 7 shows that light clients would have to download about 3.6 KB of shares to be able to detect incomplete blocks with more than 99% probability for k = 32, and about 57 bytes of shares for k = 256."
<musalbas>
Some may consider 99% to be too low -- if you want 99.99% you need 30 samples
<gmaxwell>
That sounds right.
<musalbas>
(you can also increase the probability significantly by reducing the message/error-bits ratio; but then you need more light clients in the network to do the sampling.)
<gmaxwell>
One concept we'd talked about before was having a designated source, e.g. a partcular origin that guarentees to make the data available. If your sampling fails, you tell friends about it (rate limited by coin ownership or POW) and they can attempt the same same sampling. The result was that the dishonest origin could never serve more than O(blocksize) worth of data to all clients before having
<gmaxwell>
to stop serving entirely, or have the bad data be detectable. But that particular guarentee required, AFAICT, a designated origin.
<gmaxwell>
musalbas: I think it's important to distinguish the confidence you get from your sampling alone, vs the confidence a network of honest nodes get assuming you aren't partitioned from it. The latter is obviously a lot more powerful, but it requires a stronger assumption that you're able to communicate with these honest peers.
<gmaxwell>
any kind of fraud proof idea needs _some_ anti-partitioning assumption, but it's better if its the weakest assuption we can get.
<musalbas>
gmaxwell, indeed - we assume that light clients are connected to at least one honest node; and each honest node is connected to at least one other honest node
<gmaxwell>
musalbas: the argument there seems to be without the erasure coding. We had suggested designated source (e.g. the miner) with erasure coding, as an extra step so that instead of a probablistic fault, either the block could be recovered or everyone doesn't accept that block.
<gmaxwell>
musalbas: re: "we assume that light clients are connected to at least one honest node" I'm referring to things like the statement in your must recent link "you need ~1140 light clients to make up for overlap" -- that there needs to be some large number of lite clients which you are honestly connected to, to achieve a given probablity.
<musalbas>
gmaxwell, what prevents me from Sybil attacking the network to tell everyone that all the samples are unavailable, but when they check them they actually are available, thus forcing people to download the whole block for no reason?
shesek has quit [Ping timeout: 246 seconds]
<musalbas>
gmaxwell, re: overlap, that's correct - Table 1 in the paper analyses how many light clients you need for this overlap for various block sizes and sample sizes.
<musalbas>
oh, you mean you think you have to be connected yourself to all those 1140 light clients?
<musalbas>
not necessarily - those light clients can gossip shares to all the full nodes that they are connected to if the full nodes ask for them, and those full nodes can further gossip the shares with each other
<musalbas>
(hence the assumption of the honest full nodes of the network not being partitioned)
<gmaxwell>
musalbas: in that model, because the requests are rate limited (by pos or pow). Sorry if I've sent us on a tangent: I wasn't saying we thought it was an acceptable tradeoff, quite the opposite. We also encountered the really strong anti-partitioning assumption, and the best we could do to improve it was designated source, but it wasn't attractive because you could dos attack it.
<gmaxwell>
musalbas: by honestly connected, I mean that there must be a graph of node connections with a connected component of all honest nodes containing them.
<musalbas>
why do you think anti-partitioning is an overly strong assumption?
<musalbas>
re: rate limiting, that seems antithetical to the security of the scheme - you want as many as light clients as possible to sample for requests ideally so that they can all get some assurance
<nsh>
(rate limiting is essential because resource exhaustion is one of the many things that enable partitioning attacks, which are the scourge of distributed systems in adversarial settings generally)
<nsh>
minimising assumptions about network topology is standard best practice
<musalbas>
nsh: that doesn't seem to be a problem specific to fraud proofs then; might want to rate limit how much light clients can ask for transactions from full nodes etc
<gmaxwell>
To be clear: any kind of fraud proof requires SOME kind of anti-partitioning assumption, so I'm not saying all anti-partitioning is too strong. E.g. the basic assumption needed is that there is a connected honest graph between you and some honest full node. But partitioning attacks are real and easy. Especially in a decenteralized network: See, e.g. the lit on eclipse attacks. For all systems
<gmaxwell>
your ISP has the ability to pretty freely control who you connect to, etc.
* nsh
nods
<treyzania>
^ that's why having multiple ISPs is nice
<musalbas>
that is the assumption that we make (i.e. your node isn't under an eclipse attack, which even full nodes rely on this assumption)
<gmaxwell>
so what nsh was saying, minimizing assumptions and making the assumptions that exist super clear is important. I haven't read the entire paper carefully enough to know if you did that yet, sorry! :) at least glacing at your graphs and such it wasn't clear to me what percentage detections depended on what assumptions about connections to how many honest nodes.
<gmaxwell>
musalbas: EEEEE.. be really careful with "which even full nodes rely on this assumption". To the extent thats true, a full node will NEVER accept a rules violation.
<musalbas>
yes, but i mean the full node could be on the wrong chain
<musalbas>
if under an eclipse attack
<gmaxwell>
Yes, but that changes the costs and incentives, potentially dramatically.
<musalbas>
yeah. so if you eclipse attack a light client under this model, they wouldn't be able to receive fraud proofs ofc
<musalbas>
the assumption we make is basically that all nodes aren't under an eclipse attack
<musalbas>
or the 'honest' nodes aren't, that is
<musalbas>
(ofc some of them will be; and they can't benefit from fraud proofs)
<gmaxwell>
Right, and so assuming an attacker can mine an invalid block and eclipse attack users, what is the probablity of them tricking any one of many targets which they are also able temporarily partition from some of the honest network?
<gmaxwell>
Really where we failed to advance the idea was just that... if an attacker just served up to the pooint they would have gotten caught, they'd be able to satisify a large number of clients before anyone could tell there was fraud. Far fewer than without the erasure coding, but still probably enough to hit every interesting victim with pretty high probablity.
<musalbas>
if by 'temporarily partition' you mean you're partitioning entire subgraphs of the network, rather than individual nodes, then that would depend on how many light clients there are in the network and if there are enough of them to sample all the chunks
<musalbas>
how many light clients there are in the partitioned network*
<gmaxwell>
Yes. a point on terminology, when you say that a node isn't eclipsed to me 'eclipse attack' means that it connects entirely to attacker nodes. But what you actually require is stronger than 'not eclipsed' you require that it be connected to a subgraph of honest nodes of at least some sufficient size.
<musalbas>
gmaxwell, ah, so you should also check out section 5.4; we also describe a potential but optional 'enhanced network model' that gives improved guarantees: basically you send the sample requests through a mix net, and assuming that the requests are received in a uniformly random manner, then the adversary cannot fool the first 1129 clients; they have to fool all or none
<musalbas>
(it doesn't really have to be a mix net; you can just introduce an implicit delay on the client-side)
<gmaxwell>
That sounds interesting!
AaronvanW has joined #bitcoin-wizards
<musalbas>
(hmm actually you need to need a mix net, or onion routing at least, so that the requests are anonymous)
<gmaxwell>
I think there were three things the limited out excitement about error-coded-sampled-anti-withholding: (1) it had really strong anti-partitioning assumptions (stronger than 'you are honestly connected to one honest node'), (2) that a trickle attacker could still fool a very large number of hosts (even though they'd have to stop after that number, rather than it being unbounded like the uncoded
<gmaxwell>
case), (3) actually implementing it far enough to get concrete numbers was a lot of work for unclear benefits.
<gmaxwell>
You clearly solved (3). :) sounds like you might have an improvement for (2).
AaronvanW has quit [Ping timeout: 246 seconds]
<gmaxwell>
re correlating peers, I just assumed that the code was rateless. (uh, the great things you can do when not actually talking in terms of a concrete construction)
<musalbas>
the main performance bottleneck we found was doing the Reed-Solomon encoding; however using libs that take advantage of SIMD instruction set, we were able to get in the in milliseconds, but it could be even lower by using FFT-based encoders
<gmaxwell>
musalbas: re: FFT, https://github.com/catid/leopard/ uses the 'additive fft' to get state of the art performance even for very small problems.
<musalbas>
yeah, i was trying to create a Go wrapper for that library to use in our implementation which is in Go (https://github.com/musalbas/rsmt2d)
<musalbas>
but didn't finish
<gmaxwell>
I assume you don't have to deal with errors, only erasures, because the miner commits to the shares, and if any set of shares is inconsistent that just means the block is invalid.
<musalbas>
yeah that's right; if the any shares are inconsistent, they don't match the merkle root for that row/column
<musalbas>
in which case a fraud proof of that will be generated
<musalbas>
(section 5.5)
<gmaxwell>
(I only ask just because it means you don't need to use a code where error decoding is computationally tractable, but you were using one where it is)
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
<musalbas>
yeah, we could probably generalise it a bit more and say we don't have to use Reed-Solomon coding but any similar code
<musalbas>
that supports erasures
<gmaxwell>
You don't need an MDS code either.
dougsland has quit [Ping timeout: 240 seconds]
<gmaxwell>
It only matters because RS codes have traditionally been far from the state of the art in erasure code computational performance on actual hardware, because field arith is slow. ( leopard maybe signaling a bit of a counter example for a useful code size, but thats somewhat dicy )
belcher has joined #bitcoin-wizards
<gmaxwell>
in any case, not actually important.
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
_tin has quit [Ping timeout: 272 seconds]
bitconner has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
phwalkr has quit [Remote host closed the connection]
phwalkr has joined #bitcoin-wizards
<gmaxwell>
musalbas: ah your fix for (2) can just be stated as if the users anonymously interleave their sampling, then it isn't likely that the attacker could satisify many users without giving themselves away. This works better if there are more samples. If there are only a few samples per user, there could still be decent odds that some fraction get satisfied.
enemabandit has joined #bitcoin-wizards
phwalkr has quit [Ping timeout: 240 seconds]
_tin has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 245 seconds]
intcat has quit [Remote host closed the connection]
intcat has joined #bitcoin-wizards
thrmo has quit [Quit: Waiting for .007]
setpill has quit [Quit: o/]
bitconner has quit [Ping timeout: 260 seconds]
rmwb has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
bitconner has joined #bitcoin-wizards
ruby32 has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
bitconner has quit [Ping timeout: 245 seconds]
AaronvanW has quit [Ping timeout: 245 seconds]
sfhi has quit [Ping timeout: 245 seconds]
enemabandit has quit [Quit: Lost terminal]
bitconner has joined #bitcoin-wizards
shesek has quit [Ping timeout: 252 seconds]
phwalkr has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
shesek has quit [Ping timeout: 260 seconds]
TheoStorm has joined #bitcoin-wizards
ruby32 has quit [Remote host closed the connection]
ruby32 has joined #bitcoin-wizards
RubenSomsen has quit [Quit: Connection closed for inactivity]
shesek has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
shesek has quit [Changing host]
ghost43_ has joined #bitcoin-wizards
ghost43 has quit [Ping timeout: 256 seconds]
shesek has quit [Ping timeout: 245 seconds]
rmwb has joined #bitcoin-wizards
ghost43_ has quit [Remote host closed the connection]
ghost43 has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 260 seconds]
intcat has quit [Ping timeout: 256 seconds]
Giszmo has quit [Ping timeout: 252 seconds]
michaels_ has joined #bitcoin-wizards
morcos has quit [Remote host closed the connection]
morcos has joined #bitcoin-wizards
michaelsdunn1 has quit [Ping timeout: 252 seconds]
Giszmo has joined #bitcoin-wizards
rh0nj has quit [Remote host closed the connection]
rh0nj has joined #bitcoin-wizards
ruby32 has quit [Ping timeout: 240 seconds]
ruby32 has joined #bitcoin-wizards
phwalkr has quit [Remote host closed the connection]
phwalkr has joined #bitcoin-wizards
phwalkr has quit [Remote host closed the connection]
phwalkr has joined #bitcoin-wizards
phwalkr_ has joined #bitcoin-wizards
phwalkr has quit [Read error: Connection reset by peer]
phwalkr_ has quit [Remote host closed the connection]
TheoStorm has quit [Quit: Leaving]
AaronvanW has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 260 seconds]
ruby32 has quit [Ping timeout: 240 seconds]
shinohai has quit [Remote host closed the connection]
thrmo has joined #bitcoin-wizards
shesek has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
michaels_ has quit [Remote host closed the connection]
ruby32 has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
Murch has quit [Quit: Snoozing.]
Murch has joined #bitcoin-wizards
ruby32 has quit [Ping timeout: 250 seconds]
kristofferR has joined #bitcoin-wizards
ruby32 has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 260 seconds]
tromp_ has quit [Remote host closed the connection]