No it wasn't-- maybe on that site, but only due to it filtering things.

Because of ongoing low level spam attacks any long running 0.12 node has had a 300MB mempool (which is the limit) for months now.   There are about 800 MBytes of unconfirmed valid transactions that I'm aware of... 

None of this is especially interesting: one should always assume that the number of transactions at a fee of 0 is effectively infinite.

The spammers moved to paying more than 1e-8 BTC per byte; which is still much lower than most ordinary transactions; but high enough to move the needle on tradeblock... this lets people spin a bunch of FUD.  Meanwhile for most people transactions continue to function like normal: a total non-event.

This was asked, and answered in another recent thread: https://bitcointalk.org/index.php?topic=1378112.msg14031820#msg14031820

Great point! Thought also precludes gaining a product of pairings speedup (though as I mentioned, efficient fraud proofs would preclude that).  Products in the transfer group (which is going to be 3kilobit or so), are not ultrafast either, so that is not totally negligible.  It would also mean that the 3kbit intermediate elements would need to be cached, instead of just a set.  Memory usage for our signature caches is already a consideration.

My thinking there is also somewhat influenced by my thinking in terms of the benefit from privacy or anti-reorg, transactions need to be not broadcast in advance to some degree. But you're absolutely right that caching is not totally lost.

Oh come now.  TPTB made a totally offtopic post-- had nothing to do with Bitcoin at all, and only anything to do with the thread in question is that the rust language was mentioned in the thread and TPTB made a one sentence comment that he previously had complaints about rust but didn't remember them-- and it got moved to another subforum; where.. in fact, I wrote a polite reply to his commentary on audio codecs.

TPTB's response was to go on a campaign of insults and allegations; spreading conspiracy theories and such; instead of just looking in his post history to see that the post was still there.  His immediate recourse to attacks creates a hostile environment. Most thoughtful people have better things to do than to deal with that, myself included.  If you'd like to continue to share a forum with "the best software developers of our industry"-- then you should step up and ask people like TPTB to relax on the attacks, not shake your head with him in agreement when someone else doesn't completely lie down and take a pile of abuse.

The paper is trying to be "conservative" in how limited they believe capacity increases from re-parameterization can come... meaning they're leaping for the largest possible increases, without regard to many considerations... e.g. how far before the existing system will certainly go off the rails.  They use this approach so they can then argue that even that much isn't enough-- a conclusion I strongly agree with.

That doesn't mean that those parameters are actually workable, however.

In terms of the interblock time, decreases have dramatic effects once you consider an adversarial setting-- honest miners end up diluted working on many forks more often, while a high hashpower attacker stays focused.  Decreased interblock times also increase the pressure to consolidate mining to a few (or one pools) by making it more profitable to do so. Many of the tools to increase reliability of shorter interblock times, like GHOST, increase other problems like selfish mining that crop up once you are considering rational actors (instead of just honest/altruistic ones).

If you chart out a simulation of how long a user has to wait for (e.g. 99.9999%) confidence that their transaction won't be reversed, as a function of the expected interblock time you end up with a chart that looks like this(ignore the scaling):


(flip vertically for 'wait time goes up').  The scaling of this depends on factors like network hashpower distribution and latencies which are hard to measure and which change. The key take away is the derivative: if the time is somewhat longer than optimal for the network-reality, it has a fairly small effect on time-until-security ... but if it's shorter than optimal it rapidly destroys security.  This is why it's important to be relatively conservative with the interblock interval.

Please try to get that code corrected. Lots of people copy and paste, and the pasted code can live for a long time.

No, it is assuming the user will make exactly one seek. Otherwise, it would assume caching.  The expected accesses given are what you would get for a user that makes only a single seek.

This is also not a free choice. In existing formats with optional indexes _no_ commonly used software is able to correctly seek when the "optional" index is not present. Many have no support for that case at all at all, and what has support in theory doesn't work due to inadequate testing. Doing so would also increase the overhead for the format by 20% or so (as in if the overhead for a file was 100k, it ends up being 120k). As mentioned, accurate indexes are not small-- and many things compromise by just not providing accurate indexes; which then leaves applications linearly scanning or not permitting sample accurate seeking.

What use case is excluded? Moreover-- what error is there in having a streaming container that is actually good at streaming? People can use other containers if they need other properties.  (Though ironically, the best supported non-streaming container that is widely used with Opus-- MKV-- which has 'optional' indexes, on average requires transferring more data to seek a single time than Opus in Ogg does; due to the need to transfer the whole index to seek only once). The height of flexibility is acceptance that not every goal can be optimally satisfied in a single design.

At the end of the day there are always trade-offs. The design of Ogg makes seekable streaming encoding possible, in alternatives with indexes that isn't possible at all. As a result the seeking is less efficient but with a good implementation only _slightly_-- e.g. if you seek 0 to 3 or so times, it'll still transfer less data than an format with an index. Many people are surprised at how efficient it is because they don't realize how much better secant/brent's method of root-finding is over bisection. I think the trade-off is a very good one, but if for some reason it doesn't work for your applications you're free to use another container. MKV support for Opus is well specified.  Someone caring about different things than you do does not make them bad or stupid, I hope you realize that, especially when their preference hardly hurts yours. I kinda feel like you're missing out on an opportunity to be amazed at how efficient root finding can be and learn something new and surprising to you.

I have no clue what you're going on about here. I responded politely to your message here-- are you referring to my non-amusement to your wall of insults, allegations, and personal attacks that you cross-posted to several threads; when you couldn't find your own post when it had been moved to offtopic?   I apologize if my abrasive response makes you feel threatened enough to need to expound on your best racist theories; but I have had several of our best posters in the past tell me they stopped using Bitcoin Talk because of harassment by you in particular, and its certainly a situation I've felt myself. You may not intend to troll; but your radical jumps into insults and attacks combined with your persistence and the stream of consciousness diving into incoherent technobabble arguments which you sometimes present is effectively indistinguishable from trolling. I and others have expended a lot of time trying to encourage better behavior under your now-banned past identities, without success. All that is left is to say that if you are unable to behave yourself and not act like a troll, you will be banned. Otherwise you won't be. The choice is yours.
 

Your post wasn't deleted. It was entirely off-topic (going on about an audio format, in a thread about a cryptographic protocol.. had nothing to do with Bitcoin) and ended up getting moved to the off-topic subforum: https://bitcointalk.org/index.php?topic=1378533.0 .  I even responded to it.

The only private message you've sent me is, quoted in its incoherent entirety,


But I guess I should be glad you've exposed yourself as a shameful liar. Again.

I designed the protocol used here in _2011_, Sean has been working on this implementation since last November-- even the git history goes back to Dec 4th... These sorts of things are not accomplished in days. You owe Sean and the members of the forum a retraction.

You've been banned from the technical sub-forum in the past under your prior identities. If you don't want to be again, please get some control over your behavior.

The container is very efficiently seek-able over the network, in fact. But your implementation must be sufficiently intelligent.

Here are some benchmarks from the opusfile library, On a 25 hour long variable bitrate audio recording performing 1000 jumps to exact sample positions with no caching:

Total seek operations: 1873 (1.873 per exact seek, 4 maximum).

So an average of less than two operations, and in the worst case 4-- meaning even with a 100ms RTT a worse case seek will not cause a noticeable delay. (and obviously, if it cached, it would be much better.) (In other words, these figures involve absolutely no caching or shared state between the 1000 trials, they're completely and totally independent... if your application only ever did a single seeking operation it would perform an expected 1.873 random reads to do it).

This test is part of the opusfile tests directory, you can perform it yourself on your own files. Even if you constructed a malicious file that looked nothing like actual VBR audio the worst it can do is bisection-- so log() operations-- (I believe the method we use can formally be proven to never perform more than 2x the number of probes as plain bisection on any input no matter how crazy).  It turns out that over large timescales VBR isn't very variable, the variations average out and once your search space is small enough that they don't you've already pretty much landed at the solution.

And this requires no indexes which require the file be written in multiple passes or that it only be seekable when it's "finished"-- a live stream is seekable while it's being recorded. You can truncate or even extract a chunk of the middle of a stream with basically no more complexity that range requests (and putting the header at the front, if you're extracting from the middle), and the resulting output is perfectly seek-able too. Corruption to the file will not break its seek-ability (except, perhaps, for specifically malicious corruption that also fixes up a checksum). And it does this with <1% overhead.

I think the seeking performance, given a good seeking implementation, is pretty good, and it's often more efficient than other less flexible containers even when they have indexes-- because to keep their indexes reasonably sized they're not high resolution-- and getting them requires seeking to the end or a rewrite of the file. To the extent that an average near 2 is less good than 1 might be with a perfect index, that is a cost for the streaming functionality, and I think a reasonable one.

I didn't design the container, but if I did-- I might have only added an additional back-reference or two at each page; I wouldn't change how seeking works.

Tim hasn't really had anything to do with Rust-- I had some infinitesimally small influence on the language (lobbied successfully for overflow of ordinary signed types to be defined as an error). Rust has some nice properties for cryptocurrency infrastructure: in particular it has no overhead, deterministic operation, with high levels of safety enforced at compile time. These things matter for decentralized cryptocurrency, since speed is also a security consideration.

Linked near the bottom of the article now. The client is a mixture of rust and C++.

Sure it could, but there are other ways to do atomic swaps that are likely much more efficient.

Its on mainnet _now_. The transactions today were done on mainnet. Nothing new was needed in Bitcoin for this.

I am happy to announce the first successful Zero-Knowledge Contingent Payment (ZKCP) on the Bitcoin network.

ZKCP is a transaction protocol that allows a buyer to purchase information from a seller using Bitcoin in a manner which is private, scalable, secure, and which doesn’t require trusting anyone: the expected information is transferred if and only if the payment is made. The buyer and seller do not need to trust each other or depend on arbitration by a third party.

Imagine a movie-style “briefcase swap” (one party with a briefcase full of cash, another containing secret documents), but without the potential scenario of one of the cases being filled with shredded newspaper and the resulting exciting chase scene.

An example application would be the owners of a particular make of e-book reader cooperating to purchase the DRM master keys from a failing manufacturer, so that they could load their own documents on their readers after the vendor’s servers go offline. This type of sale is inherently irreversible, potentially crosses multiple jurisdictions, and involves parties whose financial stability is uncertain–meaning that both parties either take a great deal of risk or have to make difficult arrangement. Using a ZKCP avoids the significant transactional costs involved in a sale which can otherwise easily go wrong.

In today’s transaction I purchased a solution to a 16x16 Sudoku puzzle for 0.10 BTC from Sean Bowe, a member of the Zcash team, as part of a demonstration performed live at Financial Cryptography 2016 in Barbados. I played my part in the transaction remotely from California.

The transfer involved two transactions:

    8e5df5f792ac4e98cca87f10aba7947337684a5a0a7333ab897fb9c9d616ba9e
    200554139d1e3fe6e499f6ffb0b6e01e706eb8c897293a7f6a26d25e39623fae

Almost all of the engineering work behind this ZKCP implementation was done by Sean Bowe, with support from Pieter Wuille, myself, and Madars Virza.


Read more, including technical details and links to the software at https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/

Yea, I spoke to jl2012-- it's interesting how a bit of ignorance can be brilliance: He was previously unaware of the linear cancellation that was keeping this from working, so he just assumed it would work, when others had previously discarded the idea.  I still can't figure out why he wasn't jumping up and down excited to do it-- it's a nice improvement with little downside.

Right. Unfortunately, Bitcoinj sends unsolicited transactions. The developers of BTCD have been complaining about that for a while, and I'd like to stop supporting unsolicited txn... but while the behavior is common we didn't want to add misbehavior for it.


I have data from the confirmation test run,

        RX packets 169821144  bytes 83997523200 (78.2 GiB)
        RX errors 0  dropped 5  overruns 0  frame 0
        TX packets 269163479  bytes 293982867649 (273.7 GiB)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0
        RX packets 171751847  bytes 84478658144 (78.6 GiB)
        RX errors 0  dropped 5  overruns 0  frame 0
        TX packets 271892507  bytes 296796582415 (276.4 GiB)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0
and
        RX packets 175622574  bytes 85220192328 (79.3 GiB)
        RX errors 0  dropped 5  overruns 0  frame 0
        TX packets 277631356  bytes 303320529705 (282.4 GiB)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0
        RX packets 175824690  bytes 85283702303 (79.4 GiB)
        RX errors 0  dropped 5  overruns 0  frame 0
        TX packets 277920978  bytes 303653216190 (282.7 GiB)
        TX errors 0  dropped 0 overruns 0  carrier 0  collisions 0

These were 6 hour runs, with the node pre-primed for an hour before the ran began.

As tiernolan points out, the results aren't surprising-- if you go look in my reddit comments you'll see I computed similar figures for this from first principles before measuring.


Took me a bit to find it: https://github.com/bitcoinclassic/bitcoinclassic/pull/16  I'm not trying to stir drama, I was earnestly surprised as jtoomim commented extensively there.

You are!

Imagine if the network were wired such that if a message was relayed along connection 0 on each peer it would form a Hamiltonian cycle and reach every node in the network. Thus, each peer would receive and send each transaction exactly once. This shows the bound cannot be transactions*peers.

Now, this is obviously pretty fragile-- and our network doesn't form a nice complete cycle.  So if you want to check if your peers actually has all the transactions you have, does that reintroduce transactions*peers(*ratio of txid to tx size) traffic?  No.  Set reconciliation lets you communicate a set difference with size proportional to the difference, see my EL5 description of a computationally efficient set reconciliation scheme:  https://www.reddit.com/r/btc/comments/43iup7/mike_hearn_implemented_a_test_version_of_thin/czirz2p

The difference is, hopefully, almost zero size-- so the communication is small even if the number of transactions are large.

Yes, it is.  Technically it sends an INV (a message with TXids) not the whole transaction, though this is only a constant factor improvement.

Uh. Bitcoin has done this since the very early days. The batching was temporarily somewhat hobbled between 0.10 and 0.12 (especially when you had any abusive frequently pinging peers attached), but is now fully functional again and it now manages to batch many transactions per INV pretty effectively. Turn on net message debugging and you'll see the many INVs that are much larger than the minimum. The average batching size (ignoring the trickle cut-through) is about 5 seconds long-- and usually gets about 10 transactions per INV. My measurements were with these fixes in effect; I expect the blocksonly savings would have been higher otherwise.


2016-02-26 05:47:08 sending: inv (1261 bytes) peer=33900
2016-02-26 05:47:08 sending: inv (109 bytes) peer=32460
2016-02-26 05:47:08 sending: inv (37 bytes) peer=34501
2016-02-26 05:47:08 sending: inv (217 bytes) peer=33897
2016-02-26 05:47:08 sending: inv (145 bytes) peer=41863
2016-02-26 05:47:08 sending: inv (37 bytes) peer=35725
2016-02-26 05:47:08 sending: inv (73 bytes) peer=20567
2016-02-26 05:47:08 sending: inv (289 bytes) peer=44703
2016-02-26 05:47:08 sending: inv (73 bytes) peer=13408
2016-02-26 05:47:09 sending: inv (649 bytes) peer=41279
2016-02-26 05:47:09 sending: inv (145 bytes) peer=42612
2016-02-26 05:47:09 sending: inv (325 bytes) peer=34525
2016-02-26 05:47:09 sending: inv (181 bytes) peer=41174
2016-02-26 05:47:09 sending: inv (469 bytes) peer=41460
2016-02-26 05:47:10 sending: inv (973 bytes) peer=133
2016-02-26 05:47:10 sending: inv (361 bytes) peer=20541


Twiddling here doesn't change the asymptotic efficiency though; which is what my post is about.

[I'm also somewhat surprised that you were unaware of this; one of the patches "classic" was talking about patching out was the one restoring the batching... due to a transaction deanonymization service (or troll) claiming it interfered with their operations.]

[I split the thread, because we were getting away from talking about the compact aggregated signatures; into things which don't change the network behavior]

Something we must fight against if we want Bitcoin to retain it's utility in the future. No one uses a system of money with fungibility and privacy as bad as a bitcoin that has lost it's properties.

We do not store the blockchain in a database in Bitcoin Core.

txindex=1 is not very compatible with scalablity; you end up with an ever-growing index. It makes some operations faster, but at a considerable cost.

In Bitcoin core reindex spends a fair amount of time rehashing things to check data integrity, because later it is assumed to be true. It could easily be made very fast-- but at the cost of additional indexes. Right now the marginal cost of a full node wallet that supports arbritary key import is about 65GB and rapidly growing. (Pruned vs non-pruned plus txindex).

The "bad software" wasn't referring to local optimizations by any means.  What I mean is that someone who doesn't like privacy can release a wallet which forces its users to always reuse addresses and then justify it with "reuse is more efficient because things use the indexes"-- but even this would only apply if they were used 'on the wire'; if they're purely local, they're purely local.   The txindex in Bitcoin Core works internally with compact indexes in a similar way, in fact.

I'm super supportive of purely local optimizations.

If it's purely local, you could probably always number that way, so long as you had code to fix up the numbering during reorg.

There is an additional test harness built from BitcoinJ that simulates a bitcoin network and puts the node through its paces. It's called blocktester. Look at the travis ci configuration in Bitcoin core to get an idea of the tests that are automatically run on it.

Standard warnings about the near impossibility of writing new code which is consensus compatible with other code apply-- if you don't find some new surprising behavior in the network that we don't have tests for, you're almost certainly not testing hard enough to have a chance at it.

We care a lot about performance in the adversarial setting. It is very cheap to compute 64-bit collisions. So a trouble maker could cheaply break that scheme, causing it to always fall back... there are ways around that. ... or even better improvement possible, I can tell you how to reduce the "ID" overhead to _zero_ for at least the first time that ID is sent:  (and if the set reconciliation was perfectly efficient, there really only would be a 'first' time)

Instead of using transaction hashes as identifiers, pass the transaction through a cryptographic permutation (e.g. a large block blockcipher). and then use the initial N bits as the "ID"; when sending the txn, send in encoded form and don't send that part.  Now the bandwidth used sending ID's at least counts towards sending the transactions. (I describe this on the network block coding article from a while back)

If one really must use IDs smaller than 160 bits, the ID could be seeded by random value agreed between peers (best for security) to prevent collisions, but it would break multiparty reconstruction, so a recent block hash could be used instead (boo, still has collisions; but harder to compute).

Personally I don't think the small constant factor savings from smaller IDs is worth the software complexity, especially the introduction of infrequently tested error conditions... the big gain here comes from getting rid of the quadratic behavior.  If that is successful the bandwidth should be dominated by the size of the actual transactions themselves, and so even big improvements in the rest wouldn't matter much.

But then you can place misbehaving nodes in the minimum cut of those graphs (or DOS the nodes in those positions)-- that is part of what I meant by efficient gossip being in some conflict with attack resistance.


Random walks in random graphs tend to fill pretty efficiently, even with low fan-out.  I believe that simple trickling behavior combined with set reconciliation to escape cycles kills the quadratic behavior and can do so without introducing any new vulnerabilities or major slowdowns.

Yes. They would frustrate traffic analysis at least if 'constant size getdata' were also implemented-- assuming other mempool leaks were closed. (like the mempool p2p message), and if the traffic were encrypted (e.g. over tor or other encrypted transport) or if content were not visible to the attacker (e.g. for pretextual compliance with the law).

Well everything I described there is completely compatible with all scripthash types; so no real need to limit flexibility. Assuming the sighash code is separate and reused, it shouldn't increase implementation complexity.

That could be done-- but there is no need to do so normatively.  E.g. Peers could agree to transmit data using these compressed indexes, while still hashing the original values. This has the advantage of having the IDs not change out from under already authored transactions, and making sure that offline devices don't need access to (or to trust) external index providers.

This would undermine the privacy/fungibility properties of bitcoin as a whole to incentivize parties to reuse addresses. Bitcoin's privacy strongly depends on non-reuse, and additional pressure against it for the benefit of saving  on the order 12 bytes per txout doesn't sound like a win-- especially as it would be used to justify bad software, bad businesses practices, and bad public policy that force users to reuse.  Access to those indexes would have to be handled quite carefully since if you paid the wrong one the funds would be stolen.

Thanks for your thoughts!

Bitcoin Core 0.12 introduced a new blocksonly setting.  When set to blocksonly a node behaves normally but sends and receives no lose transactions; instead it handles only complete blocks. There are many applications for nodes where only confirmed transactions are interesting, and a node which still verifies and forwards blocks still contributes to network health-- less, perhaps, than one that relays transactions: but it also consumes fewer resources to begin with. An additional downside they don't get the latency advantages of signature caching since every transaction they see is totally new to them-- this isn't something miners should use.

How much less bandwidth does blocksonly use in practice?  I recently measured this using two techniques: Once by instrumenting a node to measure bandwidth used for blocks vs all other traffic, and again by repeatedly running in both modes for a day and monitoring the hosts total network usage; both modes gave effectively the same result.

How much is the savings?  Blocksonly reduced the node's bandwidth usage by 88%.

A significant implication of this is that any scheme for bandwidth reduction which works by using already relayed transactions to reduce the size of transmitted blocks can _AT MOST_ reduce the overall bandwidth usage by 12%-- assuming that differential compression achieved an "infinity-fold" improvement. (An example of Amdahl's law)

Why does relay use so much bandwidth?  The fundamental reason for this is because relay in the Bitcoin Protocol is linear in the number of transactions and the number of peers. (E.g. bandwidth is a function of Transactions * Peers).  The protocol uses an 'efficient' INV scheme --- but this scheme only reduces the bandwidth by a constant factor:  For every transaction a 36 byte long INV is sent (or received) from _every_ peer, and the full transaction is only sent once. Since the INV is a significant fraction of the transaction size (e.g. 36 bytes vs 300) this means that every 10 or so peers uses just as much bandwidth as sending the full transaction every time would take.

For the subset of nodes where blocksonly meets their needs it's available now and gives pretty much the greatest possible bandwidth savings. Full stop. For blocks the INV process is much more efficient because the ratio of INV size to a megabyte block is so large. But what can we do for all the other cases?

In the literature there are schemes for quite efficient gossip but there seems to be a trade-off between efficiency and attack robustness (for example, you could arrange nodes in a minimum spanning tree rooted at some super node(s) which would be optimal for repeated bandwidth but insanely unreliable and vulnerable to attacks). Even the simple INV scheme is vulnerable to attack: peers can delay transactions by INVing but then sending the data only after a long delay.  With ephemeral anonymous peers, attack resistance is very important to us-- but fortunately we don't need to achieve optimal efficiency.

One possible scheme I've been discussing (and working on) for a while is mempool reconciliation. My work here was originally motivated by the desire to avoid relay costs for transactions which are just going to be quickly replace or fall below the relay threshold, but this can also be applied to drastically reduce relay costs.

The idea is this, at random intervals a node will ask one of it's peers for a sketch of the top X MBytes of it's mempool. In it's request it could also signal that it's interested only in transactions whos ancestor feerate is over some minimum threshold, along with information about the size and feerate of its own mempool.  The returned sketch is an IBLT (see this reddit post for an EL5 explanation that I created for IBLT) of some size estimated by the sender based on the information sent by the requester.  Unlike the efficient block transmission IBLT proposals, this IBLT only transmits transaction IDs-- which will avoid the fragmentation overhead needed in sending whole transactions.

The requester then attempts to reconstruct the IDs using the content of it's own mempool.  If it is unable to reconstruct all of the IDs, it requests from another random peer with a different seed.

When the node has multiple IBLTs it can use the partial solutions from each of them to help solve the other ones.

As it learns new txids that it was previously unaware of it then fetches them via getdata. When it completes a reconstruction it can INV any missing transactions towards the peers that didn't have them.

(To avoid IBLT batching delays slowing transaction propagation too much, two peers can be elected to receive INVs for every transaction immediately; similar to the existing trickle-for-privacy scheme).

Most of the academic literature on IBLTs is concerned about parameter selections that minimize the asymptotic overhead (size of IBLT vs set difference) for perfect reconstruction of the set.  These parameters, however, result in quite high probabilities for complete failure.  In our case, being able to recover some of a set is fine both because mempools don't need to be completely consistent, and requests to other peers will help recover the missing entries.

A similar pattern happened (for the same reason) in the invention of fountain codes-- (one can approximately think of a IBLT as the dual of a fountain code). To achieve better odds of reconstruction, the order of nodes in the graph (isomorphic to the number of hash buckets in IBLT) should be randomly selected from a special distribution, instead of a constant. The effect is that the mixture of node orders reduces the probability that a decode gets stuck, because it is more likely that there will be be some entries that have the optimal density.  For IBLT this can be done by using the hash of the set member to pick the number of buckets for that set just like it is used to pick which buckets are used.

But right now I'm not aware of any research on what these optimal order distributions would look like for IBLTs given assumptions around capacity ratios... so I think there is a fair amount of basic science that needs to be worked out in order to really nail down a good design.  I've been trying to work on making more progress here for a couple months, but the toxic environment makes the grind a little difficult. I thought I would checkpoint my thinking here in the hope that someone would have some more thoughts to contribute.

In any case, this scheme would avoid the quadratic-like behavior of relay bandwidth. It would let nodes trade latency off vs relay overhead, and it would allow for a graceful way of handling the highest priority transactions first. -- transactions a dozen or more blocks deep in the mempool are not going to get mined any time soon, so if they have lower relay latency from reconciling them less frequently that is no great harm. I believe it could do so without substantial increases in vulnerability to attack. The same software infrastructure could also be used for bandwidth minimized block transfer for nodes that do have mempools (otherwise blocksonly gives optimal bandwidth gains), though latency minimization is much better accomplished via techniques like Matt's efficient block relay protocol-- since the most important thing to minimize latency is to minimize roundtrips.

Back in 2013 an Anonymous Author wrote a brief paper on using BLS signatures to achieve a kind of non-interactive coinjoin.  I jumped on it right away, pointing out that it also could have useful anti-censorship properties. (Edit: Paper link is down, a copy is available from Andrew Poelstra.)

The core property it depends on is that fact that for a BLS signature one can take a collection of {message, pubkey, signature} tuples and merge their signatures: {[message1, message2, ...], [pubkey1, pubkey2, ...], signature}, in a way which is infeasible to unmerge them without knowing the components, and still be able to verify the result. Via a clever trick that involves signing per input and per output, the authorship of inputs and outputs can be unlinked. I have a sidechain implementation of this that I've been working on-- like coinjoin generally it composes well with CT, but I'm unsure of what to do about the performance (more below).

Another application of these aggregatable signatures which has come up from time to time in #bitcoin-wizards is using them to reduce blocksize  ("2013-09-13 21:38 < gmaxwell> sipa: I'm mildly excited about this pairing crypto aggregate signature idea. Not because of the anonymity stuff, but because it makes scalable relay fees viable. and can also reduce transaction sizes in the non-anonymous case"), since you'd save the sizes of the free standing signatures. Aggregate BLS signatures could even be made compatible with 'efficient' fraud proofs, though the cost of doing probably makes it not a win. (You would do a merkel sum tree over the interior computation, which aggregates the partial signatures as products in a 3kbit field; which would make it possible to show a block had an invalid aggregate signature with a compact proof).

The main downside of this are two fold-- the BLS signatures involve Pairing Cryptography-- less mature security assumptions than plain ECC signatures, and more importantly they're slow to verify: On hardware that can verify 70,000 secp256k1 signatures per second (or 140,000/s with batched Schnorr) they could only process about 8,000 BLS signature per second, with state of the art parameter selection and software.  So, while bandwidth would be reduced, the capacity of most nodes wouldn't be increased much because they'd be bottlenecked on signatures.  (And, right now, signature validation is extensively cached in Bitcoin-- and the aggregation would move validation back on the critical path).

[I've had some conversations about Dan Boneh about using multi-exponentiation like optimizations in computing the required product of parings here-- but it's likely that the performance improvement that this would get would only be on the order of 2x.]

Adam Back was asking me about this again today and I pointed him to the prior discussions regarding the performance limits.  Then he suggested just using Schnorr multi-signature instead of the BLS signatures. The idea is that if you have inputs with pubkeys P and P2  you can combine them and to form a P+P2 pubkey and sign with that to prove authorization with both keys.  When this had previously been discussed the fact that someone malicious could set their P2 to P3-P and then sign the aggregate with just P3 seemed to kill it.

But actually a few months ago Pieter Wuille solved this as a side effect of his key tree multi-signature work,  He suggested instead that to combine P and P2, you use P*H(P) + P2*H(P2); this doesn't inhibit signing, but it makes it impossible to create a pubkey as a linear combination of other pre-existing pubkeys. Pieter has an implementation of this as part of the Libsecp256k1 multi-signature work: https://github.com/bitcoin/secp256k1/pull/322

So the way we could use this to improve scalability in Bitcoin would be to add a OP_GROUPCHECKSIGVERIFY (and perhaps a multi-version of it) as part of a new segwit script typecode that takes as input sighash flags and a pubkey.  The script operation would push a the pubkey onto a transaction scoped 'signature stack'  and the sighash-masked transaction hash onto a transaction scoped hash stack.

After all inputs are processed the pubkeys on the stack would be combined to a new Pubkey as P = P1*H(H(all_Pn) || P1) + P2*H(H(all_Pn) || P2) + ..., and a root message hash computed-- then an additional group signature witness at the end of the transaction would contain a signature of the root with P.

Verification speed would be similar to individual inputs with batch schnorr (the multiplication with H() can be folded into the multi-exp in verification), so this is more of a space savings than a speedup; but the size of the transaction would be reduced by 41% asymptotically-- without any new security assumptions or performance hit. The main limit is that a transaction must have many inputs to fully realize that benefit.

Unlike other past shared signature proposals based on exploiting pubkey reuse, there is no advantage in this design in reusing public keys; so it also doesn't create a new privacy moral hazard for the network.

Critically, multiple distinct users could cooperate to securely produce a single large transaction with a two round protocol which may make it reasonable to get _many_ inputs in a single transaction-- but unlike the BLS signatures they must interact in order to merge their signatures.  Effectively this would be a CoinJoin, with a big space (and thus fee) savings for the CoinJoin users.

Even without combining multiple users this approach would make it much more economical for a single user to sweep up txout dust which would be an important improvement on its own. For block 400083 if all transactions used this (but with no increase in CoinJoin, or even behavioral changes to prefer sendmany over chains of transactions which we would expect if this actually existed; and also ignoring multisig use, which would further improve this figure) I compute this would reduce the size of the block by 172050 bytes out of 897956 or a 19% reduction which is substantial fraction of the asymptotic result. [Edit: A scan of 2016 recent blocks with accurate counting for multisig, shows the actual reduction for existing usage patterns would be 30%]

In effect this could achieve at least half the asymptotic gain while having no negative performance impact (10x-17x better performance than BLS) and no new strong cryptographic security assumptions. To me it seems like a no brainer improvement that Bitcoin is almost sure to eventually adopt once implemented.