Nick Szabo  🔑

@Datavetaren @Nightwolf42 Provably secure Bitcoin would require true broadcast: O(n^2). We don't know how secure lesser messaging is.

@NickSzabo4 @Nightwolf42 The clients I've looked at maintains a fixed set of open connections. So live graph consists of C*N edges.

@Datavetaren @NickSzabo4 @Nightwolf42 Every full node still needs to see all transactions.

@mmeijeri @NickSzabo4 @Nightwolf42 Yes and these tx flow on the edges of a graph where the number of edges is O(n) or O(n log n) if C=log n.

@Datavetaren @NickSzabo4 @Nightwolf42 And each of these needs to transfer O(n) txs.

@mmeijeri @NickSzabo4 @Nightwolf42 O(n*m) if m num of tx. But n and m are independent. Also, we're talking about bandwidth between nodes.

@mmeijeri @NickSzabo4 @Nightwolf42 Or at least m is not a linear function of n. Number of tx is related to number of users. Perhaps m=log n.

@Datavetaren @mmeijeri @Nightwolf42 But no rigorous argument has ever been made that Bitcoin is still secure when m=logn rather than n.