Sync/serve protocols

[iddo]

Here’s the sync/serve protocols under the assumption that we want all honest nodes to have all the syntactically-valid ballots (except when there’s a malfeasance proof that entails discarding of dishonest ballots) and all the unified content blocks (UCBs).

Note that sync’ing should be different in case we decide to invalidate this assumption (in favor of aggressive pruning), but that might be significantly less conservative.

Serve protocol:

• Purpose: newcomer node fetching all the data of layers that she never reached yet.
• The newcomer node requests “serve(start_layer=x, end_layer=y)” from her neighbor(s), and the honest neighbor sends all the syntactically-valid ballots and contextually-valid UCBs of layers x…y as data stream.
• Note that the honest neighbor will have rules regarding how to throttle these “serve” requests, specifically:
  ** not allowing more than N serve requests simultaneously
  ** not allowing repeated serve requests from the same neighbor (determined according to the neighbor’s IP address)
  ** using less bandwidth and lower priority for “serve” requests, relative to other communication.
• The default honest newcomer may request multiple neighbors to serve her the data concurrently, for example serve(start=1, end=1000) request sent to neighbor Alice and serve(start=1001, end=2000) request sent to neighbor Bob and serve(start=2001, end=3000) request sent to neighbor Carol, etc.

Sync reconciliation protocol for the contextually-valid mesh:

• Note: The UCB of layer J has the list of rewarded ballots (i.e., the ballots of layer J that voted on layer J-1 and the earlier layers) with multiplicities.
  ** For example the list can be “Alice:2, Bob:1, Carol:4” meaning that Alice had 2 rewarded ballots, Bob had 1 rewarded ballot, and Carol had 4 rewarded ballots.
  ** The honest smesher needs to verify that she indeed has all of these rewarded ballots (in the above example the ballot of multiplicity=2 of Alice and the ballot of multiplicity=1 of Bob and the ballot of multiplicity=4 of Carol), otherwise she requests from neighbors (or else via gossip) the missing rewarded ballots, and as long as these rewarded ballots are unavailable she considers the UCB to be invalid and votes against it (voting still in favor is a less conservative approach).
• We have at most one contextually valid UCB per layer.
• Every honest node maintains the cumulative hash-chain of the contextually valid UCBs.
• The two neighbors perform binary search to find the first layer J that they disagree on.
  ** When the disagreed-upon layer is discovered, the neighbor Alice send her UCB to neighbor Bob, then Bob computes the symmetric difference (according to his own layer) and sends back to Alice his UCB along with the rewarded ballots that Alice is missing, and then Alice sends him the rewarded ballots that he’s missing (according to the listed rewards in his UCB).
  ** The neighbors Alice and Bob continue consecutively with layer J+1, then layer J+2, then layer J+3, and so on, performing the same symmetric difference protocol. If the symmetric differences starting from layer J are large (in other words, the intersection is almost empty) then both of them switch to “serve” mode.

Sync reconciliation protocol for the contextually-invalid mesh:

• For non-rewarded ballots, each honest node sorts them according to local timestamps (so the ballot that was received most recently will be the last in the sorting, even if it’s a ballot of an old layer), but also maintains their hash-chain according to lexicographical ordering.
• In the first sync round the neighbor Alice will send to the neighbor Bob her latest batch (according to ber local timestamp ordering) of non-rewarded blocks (the default batch size is a protocol parameter, it can be e.g. 100). Then Bob computes the symmetric difference (with his own latest batch) and sends the result back to Alice.
• If Alice and Bob still don’t agree on the lexicographical hash-chain value (in particular if the entire batch was already known to the other neighbor) then Alice will send her previous batch, and so on (for example, the last batch contains non-rewarded ballots 1 to 100 that were receiving during the first three months after genesis, the one-before-last batch contains non-rewarded ballots 101 to 200 were received during the next two months after that, etc.)
• If after several rounds (i.e., batches) Bob never sent any non-rewarded ballots that Alice didn’t already have, then Alice will switch to “serve” mode, and in the end ask Bob to send the ballots that she is missing (the same is also true vice versa, i.e., Bob will switch to serve mode if Alice didn’t send ballots that he didn’t already have).

Sync’ing of contextually-invalid UCBs:

• The default behavior of the honest node is not to sync her contextually-invalid UCBs at all, but also not to prune each contextually-invalid UCB for as long as she has honest ballots that voted for it (if all the ballots that voted for the UCB were discarded and replaced with malfeasance proofs, then the contextually invalid UCB should be discard too).
• Note that the honest node Alice may store ballots that vote for a hash of UCB for which Alice doesn’t have the preimage.

[countvonzero]

@iddo

Note that sync’ing should be different in case we decide to invalidate this assumption (in favor of aggressive pruning), but that might be significantly less conservative.

don’t understand the meaning of this.

@iddo

The default honest newcomer may request multiple neighbors to serve her the data concurrently, for example serve(start=1, end=1000) request sent to neighbor Alice and serve(start=1001, end=2000) request sent to neighbor Bob and serve(start=2001, end=3000) request sent to neighbor Carol, etc.

our data validation in current implementation is recursive. doing these in parallel will most likely cause memory blowup.

@iddo

** For example the list can be “Alice:2, Bob:1, Carol:4” meaning that Alice had 2 rewarded ballots, Bob had 1 rewarded ballot, and Carol had 4 rewarded ballots.

currently each party will just have 1 rewarded ballot in any given block. the single ballot will record the eligibility count for that layer.

@iddo

If after several rounds (i.e., batches) Bob never sent any non-rewarded ballots that Alice didn’t already have, then Alice will switch to “serve” mode, and in the end ask Bob to send the ballots that she is missing (the same is also true vice versa, i.e., Bob will switch to serve mode if Alice didn’t send ballots that he didn’t already have).

but does node switch back to serve node just because one neighbor is behaving dishonestly? why not drop this peer instead?

@iddo

The default behavior of the honest node is not to sync her contextually-invalid UCBs at all, but also not to prune each contextually-invalid UCB for as long as she has honest ballots that voted for it (if all the ballots that voted for the UCB were discarded and replaced with malfeasance proofs, then the contextually invalid UCB should be discard too).

should this be part of the sync protocol? to me this is more like pruning protocol.
the only reason a node would have contextually invalid block is if it had generated it (according to hare output) locally and later found that the network voted for a different block.

[iddo]

@countvonzero

don’t understand the meaning of this.

These sync/serve protocols are under the simple/natural assumption that we want honest nodes to have the same data. If we are pruning “contextually invalid” data (such as non-rewarded ballots) then obviously we don’t need to sync such data. Such pruning is far from trivial and quite possibly it’s a bad idea, and if we assess these sync/serve protocols to be pleasant enough then the need for pruning reduces.

@countvonzero

our data validation in current implementation is recursive. doing these in parallel will most likely cause memory blowup.

There can be sophisticated variants (e.g. header first sync followed by backward sync), but simplest in the above example is that if there are say 1 millions layers in total and the newcomer asks Alice for serve(start=1, end=1000) and serve(start=3001, end=4000) and erve(start=6001, end=7000) and so on, and asks Bob for serve(start=1001, end=2000) serve(start=4001, end=5000) and serve(start=7001, end=8000) and so on, and asks Carol for serve(start=2001, end=3000) and serve(start=5001, end=6000) and serve(start=8001, end=9000) and so on, and the newcomer won’t validate the layer data immediately upon receiving it, but rather merge the streams from Alice,Bob,Carol continuously as they arrive, and validate sequentially from the start until the latest consecutive layer (then wait until more consecutive layers arrive before continuing to validate).

@countvonzero

currently each party will just have 1 rewarded ballot in any given block. the single ballot will record the eligibility count for that layer.

I think that we’re saying the same thing here.
The next point about “needs to verify that she indeed has all of these rewarded ballots” is the important part, are we doing this?

@countvonzero

but does node switch back to serve node just because one neighbor is behaving dishonestly? why not drop this peer instead?

For example, it might be that Alice has a lot of data but Bob was isolated and he has little data, even though both of them are honest.

Anyway, the important thing is that we will have an implementation of the “serve” protocol, and an implementation of the “sync” protocol, and then we can specify the exact rules that decide whether the neighbor is considered dishonest (and should be dropped/blacklisted) or still considered to be honest (and then we switch from “sync” to “serve”).

@countvonzero

should this be part of the sync protocol? to me this is more like pruning protocol.
the only reason a node would have contextually invalid block is if it had generated it (according to hare output) locally and later found that the network voted for a different block.

If say the adversary creates a ballot that votes for an unknown UCB that the adversary created, then the honest miner needs to receive this adversarial UCB before considering this adversarial ballot to be data that can potentially affect the contextually valid mesh. So if this adversarial UCB is sent then by default it should be received and kept, because the ballot might not be adversarial but rather an honest ballot that’s sent after netsplit. To avoid DoS, as mentioned we should discard UCBs if all ballots that vote for them were discarded and replaced with malfeasance proofs.

[countvonzero]

@iddo

** The honest smesher needs to verify that she indeed has all of these rewarded ballots (in the above example the ballot of multiplicity=2 of Alice and the ballot of multiplicity=1 of Bob and the ballot of multiplicity=4 of Carol), otherwise she requests from neighbors (or else via gossip) the missing rewarded ballots, and as long as these rewarded ballots are unavailable she considers the UCB to be invalid and votes against it (voting still in favor is a less conservative approach).

currently UCB has a list of transactions and rewards. only ATX id and weight are in the rewards, and we don’t verify that the rewarded ballots actually exist locally.

even tho the only time we would sync a UCB from neighbor is when it becomes contextually valid, we can still potentially miss rewarded ballots in this case.

if we failed to sync any transactions in the UCB, then we will not store this UCB locally (and therefore would not vote for it).

[iddo]

@countvonzero

if we failed to sync any transactions in the UCB, then we will not store this UCB locally (and therefore would not vote for it).

The same should be done regarding the rewarded ballots of the UCB (the weight of the reward should be the same value as the multiplicity of the ballot).

So if Alice has reward with weight 2 and Bob has reward with weight 5 then the honest node needs to have the ballot of Alice that’s voting for the previous layer with multiplicity 2 and the ballot of Bob for the previous layer with multiplicity 5, otherwise the honest node shouldn’t vote for this UCB.

And again, this is under the assumption that we want all honest node to sync all the relevant data so that they will be consistent with each other (if we opt for the aggresive approach then we might want to vote in favor of UCB whose rewarded ballots are missing, but we might want to do it only in some scenarios, or likely never, so we should implementing the fully correct behavior now).