Quote from: laurentmt on August 10, 2015, 06:03:45 PM

@Peter R: Having followed the discussion on this thread, I must say that I'm quite impressed by the work done for this paper. Bravo !
I still have to read the end of the paper but I've got a question related to the impossibility of an unhealthy fee market (chapter 7).
According to you, what would be the consequences of a new propagation mechanism like IBLT (see https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2) ?

Great question.

There's two cases to consider: (1) how an IBLT propagation mechanism will affect spam costs for an attacker, and (2) how it will affect the health of the fee market in general.

1. IBLT will make spam proportionally more costly for an attacker, since the propagation efficiency of IBLT relies on partially synchronized mempools. There's more on this here.

2. The paper viewed the IBLT scheme as a way to compress block solutions by some factor γ, where γ represents the coding gain. In this regard, it is similar to the compression already achieved by the Corallo Relay Network, only with a higher coding gain. Assuming that block solutions are propagated across physical channels, and that the quantity of pure information communicated per solution is proportional to the amount of information contained within the block, then the communication time will always grow asymptotically like O(Q) as per the Shannon-Hartley theorem, and the fee market will be healthy. In other words, as long as the block solutions contain information in the sense defined by Shannon (also called the Shannon Entropy) about the transactions they contain, then bigger blocks will contain more of it and, by the Shannon-Hartley Carrying Capacity Theorem, the communication speed has a fundamental lower bound governed by the laws of physics.

So to answer your question, my view is that IBLT would not affect the health of the fee market (but it would reduce the average fee per transaction).

This discussion relates to my main point of contention with Greg Maxwell. In email correspondence, he suggested that it would be possible to have infinite coding gain for block solutions announcement. (I.e., he suggested that block solutions can truly be communicated in an amount of time that does not depend, even asymptotically, on the amount of transactions included in the block. He said this is possible if what went into a block was already agreed upon far ahead of time [so that zero information needed to be communicated when the block was solved]). I think the onus is on him to rigorously show:

(a) Under what assumptions/requirements such a communication scheme is physically possible.

(b) That such a configuration is not equivalent to a single entity¹ controlling >50% of the hash power.

(c) That the network moving into such a configuration is plausible.

Nevertheless, I've agreed with him to discuss this point of contention when I make the other corrections to my paper.

¹For example, if--in order to achieve such a configuration with infinite coding gain--miners can no longer choose how to structure their blocks according to their own volition, then I would classify those miners as slaves rather than as peers, and the network as already centralized.