Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Kaz Wesley
I don't see how set reconciliation alone would be practical for condensed block exchange -- if the keys are txids it'd require a round trip to request the missing tx; if we could somehow get the What's the Difference approach to effectively operate on full transactions instead, the log(keysize)

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Gregory Maxwell
On Thu, Jul 31, 2014 at 1:47 PM, Kaz Wesley kezi...@gmail.com wrote: trip to request the missing tx; if we could somehow get the What's the Difference approach to effectively operate on full transactions instead I explain how to do this on the network block coding page. Given that you know

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Kaz Wesley
the need to have transmitted the transaction list [..] first 32 bits per transaction is at least double the communication overhead of the simple approach, and only offers a bound on the probability of needing a round trip. On Thu, Jul 31, 2014 at 2:29 PM, Gregory Maxwell gmaxw...@gmail.com

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Gregory Maxwell
On Thu, Jul 31, 2014 at 2:41 PM, Kaz Wesley kezi...@gmail.com wrote: the need to have transmitted the transaction list [..] first 32 bits per transaction is at least double the communication overhead of the simple approach, and only offers a bound on the probability of needing a round trip.

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Kaz Wesley
the FEC still lets you fill in the missing transactions without knowing in advance all that will be missing. I don't see why we need to solve that problem, since the protocol already involves exchanging the information necessary to determine (with some false positives) what a peer is missing,

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Gregory Maxwell
On Thu, Jul 31, 2014 at 3:27 PM, Kaz Wesley kezi...@gmail.com wrote: the FEC still lets you fill in the missing transactions without knowing in advance all that will be missing. I don't see why we need to solve that problem, since the protocol already involves exchanging the information

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-31 Thread Kaz Wesley
On Thu, Jul 31, 2014 at 4:18 PM, Gregory Maxwell gmaxw...@gmail.com wrote: On Thu, Jul 31, 2014 at 3:27 PM, Kaz Wesley kezi...@gmail.com wrote: the FEC still lets you fill in the missing transactions without knowing in advance all that will be missing. I don't see why we need to solve that

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-19 Thread Gregory Maxwell
On Fri, Jul 18, 2014 at 8:06 PM, Emin Gün Sirer el33th4...@gmail.com wrote: Most things I've seen working in this space are attempting to minimize the data transfered. At least for the miner-interested case the round complexity is much more important because a single RTT is enough to

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-19 Thread Wladimir
On Fri, Jul 18, 2014 at 4:53 PM, Gavin Andresen gavinandre...@gmail.com wrote: Two more half-baked thoughts: We should be able to assume that the majority of transaction data (except for coinbase) has already been propagated. As Jeff said, incentivizing nodes to propagate transactions is a

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Jeff Garzik
On Thu, Jul 17, 2014 at 6:46 PM, Gavin Andresen gavinandre...@gmail.com wrote: I'd encourage you to code up a prototype first (or at the same time), in whatever programming language / networking library you're most familiar with. +1 Maybe not even using the existing p2p protocol; there could

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Gavin Andresen
Two more half-baked thoughts: We should be able to assume that the majority of transaction data (except for coinbase) has already been propagated. As Jeff said, incentivizing nodes to propagate transactions is a very good thing (the signature cache already gives a small incentive to miners to

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Jeff Garzik
On Fri, Jul 18, 2014 at 10:53 AM, Gavin Andresen gavinandre...@gmail.com wrote: But if there was some agreed-upon canonical ordering, then it should theoretically be possible to take shortcuts in the what order. You'd start with setof(transactions I think everybody knows about) Select some

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Kaz Wesley
Peers exchanging mempool priority policies is great; that accomplishes the flexibility in what txes to remember that I was going for with the forget-filters, but much more neatly, with less overhead and some side benefits. Here's what I'm picturing now: - exchange priority policies in peer

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Jeff Garzik
On a flood-fill network, you don't want to create a storm of I already have this replies. On Fri, Jul 18, 2014 at 1:39 PM, Kaz Wesley kezi...@gmail.com wrote: Peers exchanging mempool priority policies is great; that accomplishes the flexibility in what txes to remember that I was going for

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Emin Gün Sirer
I thought I'd chime in and point out some research results that might help. Even if they don't, there is a cool underlying technique that some of you might find interesting. The problem being tackled here is very similar to set reconciliation, where peer A thinks that the set of transactions that

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-18 Thread Gregory Maxwell
On Fri, Jul 18, 2014 at 5:54 PM, Emin Gün Sirer el33th4...@gmail.com wrote: The problem being tackled here is very similar to set reconciliation, where peer A thinks that the set of transactions that should be in the block is S_A, Most things I've seen working in this space are attempting to

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-17 Thread Gavin Andresen
A couple of half-baked thoughts: On Thu, Jul 17, 2014 at 5:35 PM, Kaz Wesley kezi...@gmail.com wrote: If there's support for this proposal, I can begin working on the specific implementation details, such as the bloom filters, message format, and capability advertisment, and draft a BIP once

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-17 Thread Kaz Wesley
I'm moving this design document to a gist so that I can integrate changes as they come up: https://gist.github.com/kazcw/43c97d3924326beca87d One thing that I think is an important improvement over my initial idea is that the bloom filters don't need to be kept around and built up, they can just

Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire

2014-07-17 Thread Gregory Maxwell
On Thu, Jul 17, 2014 at 2:35 PM, Kaz Wesley kezi...@gmail.com wrote: A node should be able to forget invs it has seen without invalidating what peers know about its known txes. To allow for this, a node assembles a bloom filter of Another option would be to just guarantee to keep at least the