[fastx] How to facilitate Bulk Sync between authorities, authorities and full replicas

[gdanezis]

Authorities need re-assurance at some point they have ingested all updates from other authorities up to a point. Similarly, full replicas (ie. nodes that try to replicate all state, but do not validate yet) also need to track the full state of the system, and to do so need to know they have received all updates from authorities up to a point. This design task is about designing this mechanism.

[gdanezis]

@huitseeker has written on some ingredients we can use to solve this, here: https://docs.google.com/document/d/1LXVNqhHSbY499G-seenTYCPRHXormZLK9BXzMSmG7L4/edit?usp=sharing

Key readings:

• Eppstein, David, Michael T. Goodrich, Frank Uyeda, and George Varghese. "What's the difference? Efficient set reconciliation without prior context." ACM SIGCOMM Computer Communication Review 41, no. 4 (2011): 218-229.
• Ozisik, A. Pinar, Gavin Andresen, George Bissias, Amir Houmansadr, and Brian Levine. "Graphene: A new protocol for block propagation using set reconciliation." In Data Privacy Management, Cryptocurrencies and Blockchain Technology, pp. 420-428. Springer, Cham, 2017.

[gdanezis]

Here are my current thoughts on Sync design:
https://docs.google.com/document/d/10SpQluu2Rpc9loUBbxyaCfXqCtkB-FwIZuucnDF_DSQ/edit?usp=sharing
@sblackshear , @huitseeker any comments welcome.

[huitseeker]

The core of the argument against the way you're implementing the push-pull gossip (and then using it to argue that the byzantine authorities never flood anybody else) is that:

• if, as an authority, I only communicate with a small, slowly-evolving constant set of peers, then I'm vulnerable to eclipse attacks. The same issue, seen at scale, would show that Byzantine authorities are able to implement a min-cut of the peerage graph to split the network into two connected components, breaking BFT assumptions.
• hence there must be out-of-peerage communications. The entire causality chain of that stream of communication cannot be strictly initiated by the recipient (though they can finish it in a "pull"), because the recipient may not be aware (through the silencing method above) there is something to "pull" in the first place.
• hence as a honest authority I must accept out-of-peerage messages pushed to me from random other authorities: the intent is that another honest (but out-of-peerage) sender authority must be able to make me aware of a new interesting message to pull. That "awareness" push does not have to be the message itself, it can just be a pointer to it. The rest of the message can be pulled afterwards. The overall message propagation pattern looks like a Levy flight.
• the only way I can "control" these initial awareness out-of-peerage messages can be sorted in two broad groups:
  • a priori, on the form (e.g. messages which size is limited by a constant, which admission is conditioned on fair resource allocation across senders...)
  • a posteriori, on the semantics : a new message is only re-transmitted further (through the peerage graph) if I, as the initial recipient authority, can vouch for its validity (e.g. it's not a duplicate, has not yet been seen by all my peers, etc ...)
• hence there must be enough data transmitted for me, as an authority, to check the message is not a duplicate. In our case, the only thing that I, as an authority, can compare to my own knowledge, is the transaction hashes that are claimed to be in this new message.
• to summarize, I must, as an honest authority:
  • be open to receive a claim to an interesting payload (e.g. a block containing new transactions)
  • from out-of-peerage authorities
  • and I must dereference this claim at least up to knowing which transactions it purports to contain (through hashes).

QED: honest authorities must be open to receive, up to fairness, a stream of transaction hashes claimed to be newly produced by any other authority, including Byzantine ones. Those messages must be received as long as they are fairly received (i.e. a byzantine authority does not produce more data than any other would) and be of a size at least equal to that amount of transaction hashes produced by the median honest authority over the same period of time.

If an honest authority produces V TPS, and the corresponding stream of transactions hashes are a V/n data stream, then honest authorities must therefore be open to receiving V/n bytes per second from a Byzantine authority, without constraining those hashes to match valid or new transactions. As a consequence, considering there are f Byzantine authorities, the amount of ingress that the honest node must accept is V(f/n), which should be sufficient to cause a significant amount of slowdown when f is concretely large (average TPS: 512 bytes, average has: 32 bytes, ratio n = 16).

[huitseeker]

There's quite a bit more on IBLT-based solutions, notably:

• ballpark estimates of bandwidth https://mysten-labs.slack.com/archives/C02KZT2LL78/p1640734762102600?thread_ts=1640724805.098300&cid=C02KZT2LL78
• a multi-way sync protocol that works well with gossip.
  Just jotting those down here to not lose track of either.

[gdanezis]

Here I discuss one more ingredient we can use for end of epoch or state commitment sync, to get a agreed checkpoint with most of the work done asynchronously and a tiny bit synchronously: https://docs.google.com/presentation/d/1TSs1FPC9INZMpipP1vP2dK7XMmOXtHk5CLWFKO6s7p8/edit?usp=sharing

[huitseeker]

Here's a new design that aims at producing a checkpoint as well, but hints at limited amounts of state synchronization along the way:
https://docs.google.com/document/d/17KjGGLl8L8MSkJ0RBS5au-jR4Jp475BFi_1-rJCS6mk/edit?usp=sharing

[huitseeker]

In a neighboring PR, @gdanezis was asking:

I am still unsure how a facility for a (say byzantine) node to commit to its sequence, and to allow clients to ask [for stuff] can lead to any kind of DoS or resource exhaustion.

It's not about the pull-based logic

The notion of "asking once you've seen the commitments", like any pull-based logic, is not a subject of concern. In fact, it's very likely that the commitments themselves, if they point me to finite-size payloads of data that each carry authentication, make me safe in asking for unseen data productively. Concretely, once I ask the server using a hash it signed over, it had better deliver me the correct and valid payload, or I'll have the cryptographic assets to reveal it as Byzantine.

The issue is that upstream of that, commitments without throughput limits in themselves are a "damned if you do, damned if you don't" logic: if as a node I don't subscribe to enough commitment streams, I'm likely to be unable to succeed in syncing with the network, and if I do subscribe to Byzantine authorities, I'm likely to be bogged down into improductive resource consumption (through the commitments alone) until I can determine for sure that the commitment data I'm receiving from a subscribee is not valuable.

Replay attacks

The problem is that determining the value of commitment data itself (without committing to further resource consumption) is very hard, and quickly becomes a cat-and-mouse game of how much ingress throughput a subscribee can steal from the subscriber without revealing it's Byzantine. That's because there's not much I can do with commitments except read them and see if I already have something for them, by which time the damage is done. The typical attack here is not a DDoS, it's a replay attack, where the replay is information that's 💯 valid but known by the Byzantine node to not make the client node progress.

In itself, this commitment replay attack is an amplification of the resource consumption of the sync process, and because it occurs at the expense of non-sync activities of the node (e.g. ingesting new transactions), it becomes a global throughput limit on the whole system.

One simple heuristic for clamping down on these shenanigans is to say that for a given unit of time, a client must know if there are interesting new elements to download anywhere in the system after having seen an amount of commitments of size s per server such that (3f+1) s is well below the ingress limits of the node.

It's of course a heuristic: I'm not saying it's impossible to have a protocol that works without a hard global cap on the throughput of commitments. For example, the cap could be adaptative and be readjusted periodically depending on load, just as the difficulty is for PoW blockchains. It just gets complicated quickly, and needs to account for f actors serving a commitment replay attack at the highest throughput they can get away with.

Absolutely zero structure on batch production (no max batch size, no batch frequency), though, is an additional risk because it lets any Byzantine node do whatever they want with this, and lets the subscribers only have network-based QoS as a defense (evenly divide throughput dedicated to commitment download among subscribees). Network-based QoS possible, but it's not easy to implement, and the implementations are not efficient on the most common network infrastructures today.

How to fit things into a constant?

I don't have the full story, but one thing that helps is this:

If a node has recently seen a batch of transactions, a lot of them are probably referring to transactions in the same batch, depending on each other.
e.g. if I have seen (TX1) and (TX2, which depends on TX1) within the same batch, I don't need to commit to TX1 within the batch. If I commit to TX2 alone, a honest node that has neither TX1 nor TX2 will ask me for it, check TX2 is valid, and come back with an ask for TX1 (through causal pointers).

How likely is that to occur within the same batch? The Utreexo paper, Figure 2 makes me think this is a pretty frequent case for Bitcoin at least.

The question I'm asking myself is: can we structure the presentation of commitments so that we transmit commitments to useful data more sparsely?

[gdanezis]

I got a few more resources from Martin kleppmann:

Martin Kleppmann martin.kleppmann@cl.cam.ac.uk
Thu 24/02/2022 11:18
Hi George,

That sounds good! On the problem of exchanging differences between sets with lots of overlap, there has been some interesting work on BFT set reconciliation algorithms:
https://arxiv.org/abs/1905.10518
https://github.com/sipa/minisketch

If you're willing to organise the elements of the set into a hash graph, you can also use a graph reconciliation algorithm, which I've worked on:
https://martin.kleppmann.com/2020/12/02/bloom-filter-hash-graph-sync.html
https://arxiv.org/abs/2012.00472

Best wishes,
Martin

[huitseeker]

I'm very familiar with Erlay, and have worked on extending + fuzzing rust bindings for minisketch. They're a nice constant-factor improvement on IBLTs that works along the same principles (this is what I was mentioning @asonnino), which we already integrated in our thinking.

I'm also very familiar with the hash graph Martin is suggesting (@gdanezis I believe I mentioned it before I joined - you then shared you had attended Martin's presentation in-person in 2019), but it works by re-constituting causal broadcast from scratch, and has a prohibitive communication complexity cost.