mimblewimble team mailing list archive

[Myrtle Warren <MoaningMyrtle@xxxxxxxxxxxxxx>]

What does a node do in the presence of multiple forks who disagree at the horizon, but which have different total difficulties? How long after a node has made a decision on the real chain can this be modified?

In the presence of multiple forks a node backtracks, in the extreme case leading to what you suggest: the full header history.

It seems we're settling closer to a system where bootstrapping nodes, regardless of their "mode", are able to fall back on a chain of valid PoW from genesis. I prefer this, especially starting out- cleverness can always be introduced later, but rarely can it be removed from a live system.

If forging of the horizon state involves multiple weeks worth of work at a rate that exceeds the majority hashpower of the network in order to degrade bootstrapping to the classic case, it seems like the incentive to do so has largely been eliminated.


- We're discussing the "limited history" mode right now, there's still a full node mode. I did ask in my first email whether we should have full nodes also do cut-through.


What becomes increasingly tricky to reason about is that we now have a 2x2 matrix of capabilities. On one axis, we have full vs partial header verification; on the other, we have full vs partial UTXO history (whether to perform cut-through). Nodes of the set (partial, partial) have extremely limited utility bootstrapping other nodes as they do not present byzantine fault-tolerance (they become incapable of proving their validity past a certain point) and cannot fork past the cut-through horizon on their own, nor can they assist other nodes in doing so. Nodes of the (full [headers], partial [utxo]) capability set can prove work but again cannot provide history assistance for forking. Nodes of the (full, full) capability set can provide both forking and bootstrapping support to other nodes. (I'm not sure the (partial, full) case makes any sense so I'm leaving it out here).

This matrix has significant sybil attack ramifications; for each attack vector, one must reason about the subset of [honest] nodes that are able to provide the service in question; that might be the number of (full, *) nodes for the bootstrapping case, but might be only the (full, full) subset for the long fork recovery case.

Terminology aside, I think it's fairly important that:

- The majority of the network has the ability to help nodes bootstrap, to avoid wildly different sybil attack surfaces for bootstrapping nodes as they come online;

- The majority of the network is able to reap the benefits of mimblewimble, notably reduced resource and storage consumption and enhanced privacy.


Given the complexity of the 2x2 grid and its repercussions for thinking of the defensibility of grin, perhaps it makes sense to leave the partial headers sync as a potential future improvement. It seems that its security model depends on a relatively mature coin of sufficient active and sustained hashpower to resist short-term rewriting of history.

Regarding cut-through of the UTXO set on full nodes (basically doing away with the (full, full) configuration), I'm torn. Given 2), it seems logical to build towards a significant population of pruning nodes. However, doing so does have some repercussions on the ability of nodes to recover from forks. If the vast majority of the network obeys an internal cut-through horizon, even if that horizon is extremely conservative, the network will have difficulty forking past this horizon- you are forced to rely on a small portion of full, history-maintaining nodes to help inform you of the fork. If you make it a rule that nodes should not fork past the most conservative horizon, you've introduced a de-facto checkpoint: a new node bootstrapping might have a different answer about the current chain than a node at steady-state, if the most-worked chain involved a fork from before this conservative horizon.

I tend to err on the side of practicality personally, so my preference would probably be to accept that a valid, extremely long fork (on the order of 6 months or more) would represent severe economic issues beyond just the engineering challenges of handling a long fork. I would also err on the side of not including explicit checkpoints in the code, as IMHO that raises questions about the role of developers (given that a different checkpoint could force new nodes on a lesser-worked chain). I think you can arrive at a fairly reasonable solution that is extremely conservative with its first cut-through horizon and uses some system of leveled compaction in order to cut through progressively larger chunks of blocks as blocks are buried further in history.

--MW