Hi, I'm working on a new blockchain proposal right now. My understanding is that gossip is more fault-resistant and topology independent. While spanning tree is faster, it is more fragile as it critically depends on the root node. If the root fails, the entire broadcast tree must be recreated. Is it possible to use tree communication in a peer-to-peer network like Bitcoin?
Possible, but not secure. As you noticed, a minimum spanning tree produces graph that is full of points of failure-- almost any dishonest node would cause significant breakage.
For transaction relay I believe I have
previously described a class of gossip protocols that should be within a small constant factor of asymptotically optimal without reducing the reliability much below the current setup.
For block relay where the objective is to minimize latency at basically all costs, the
state of the art technique uses network coding to achieve latency close to the physical limits-- in the Fibre protocol the source(s) of a block do not send the block data directly. Instead they send error correction code data to their peers who also share this error correction data to their peers. If the block has size M a node need only receive any M of it it before they can recover the whole block. The process is largely insensitive to link or node outages or delays, and very little redundant data is received. (The actual process is somewhat more complex because it also utilizes the nodes mempools which end up providing most of the block data without every having to transmit it at all.).
(The promiscuous cross forwarding and potential multi-source combining of Fibre depends on all the participants in a single fibre network trusting each other... or otherwise they can trash the recovery.-- this isn't much of problem because fibre is really only needed to get blocks around the world and there can be multiple separate fibre networks)
