Review of the PARSEC paper


#1

Ok, as you said, at this stage, you prefer a kind of paper review openly in this forum. So I will use this thread to give my oppinions and everyone can join. As it is the nature of a review process, things might get harsh from time to time, but they are not ment to. I put my time into it, because I thing the algorithm is good and should be pushed into the scientific space, once everything is clear.


SAFE Network Dev Update - March 7, 2019
#2

1.) Meta Elections:

In the paper:

“We can view a meta-election for node X with latest agreed block B as a function on a subset H_{X,B} of the gossip graph G, which is the set of all events that are descendants of any observer of this meta-election[…]”

If a meta_election is a function, how can a vertex in the graph “observe” such a function? Or do you mean observer of the value meta_election_{X,B}(X) \in {0,1, UnDef}? Looks like a type mismatch…

This should be the definition of meta-election, as its the first time that term appears. But the definition is CIRCULAR and hence not well formed. meta_election is a set of functions, each defined on a certain graph H_{X,B}, but to define that graph H_{X,B}, we need the definition of the term meta_election.

Moreover there is not “the” gossip graph. After each syncing events, we have a different graph, where the previous gossip graph is a subgraph. Therefore H_{X,B} “depends on time” (or on a sequence of syncs), so to speak. Or are the various meta_elections only defined between sync events? I.E. the graph is considered static?

So this paragraph should start with a propper definition of the gossip graph, i.e. a graph that changes over a sequence of syn events: G: Sync --> GRAPHS. A map from say natural numbers into the class of graphs… Something like that.

Then a propper definition of H_{X,B} has to appear. It is impossible to understand the various involved functions, if the codomain is not defined.

We need a proof that vertices in H_{X;B} that have no ancestors, are observers, otherwise some functions are not well defined.

In the definition auf the set of aux functions: Why does self_parent always exists?


#3

Is stage the adaptation of “round” in the underlying binary ABFT consensus? I mean the variable r_i in Figure 2 line (00) in the paper of Raynal et. al.


#4

You should see our slack over the last few years :smiley: Please don’t worry the dev forum is to allow succinct and deep questions in technical ways. It was created to not scare the less technical users on the main forum as the language will be more precise than wooly English that we all use normally to not offend. So no worries there. Hopefully, I will get back to this or the team will soon and help where we can. I mean this convo would be better in the dev forum, but let’s get these questions answered here first.

Thanks though, this is great to see.


#5

I see, than maybe a mod can transfer this to the dev forum? Or I will reopen there


#6

No, you’re OK, but perhaps new questions on this could be over there when these are answered first though. All good.


#7

things might get harsh from time to time

No worries here. There is no such thing as harsh in a technical discussion: there is valid concerns and there is invalid concerns. Valid concerns are welcome and invalid concerns must be addressed with a rational answer. No hurt feelings either way :slight_smile:

If a meta_election is a function, how can a vertex in the graph “observe” such a function?

I can see your confusion. When we said “any observer of this meta-election”, we didn’t mean: something that observes the meta-election. We were refering to the concept of “observer” defined in section 2.4:
An observer is a gossip-event with a certain property (specifically, “the first gossip event which strongly sees block votes created by a supermajority of nodes”)

I guess we could be more precise here by saying “any observer contained in this gossip graph”.

This should be the definition of meta-election, as its the first time that term appears.

Yes, that’s what we’re going for with the: “that is, deciding whether or not to take a single node’s opinion into account when trying to choose a single new block.”
Hopefully, it makes more sense with the previous point being cleared up.

Moreover there is not “the” gossip graph.

Since we defined a meta-election as a function that takes a gossip graph (plus a node and the latest agreed block), in the context of that function, there is indeed one and only one gossip graph.
Like you said, gossiping will evolve the graph, but then the meta-election can be recalculated with the new gossip graph (or subset thereof).

Or are the various meta_elections only defined between sync events? I.E. the graph is considered static?

Yes, that’s exactly it. We thought it was much simpler to explain the principles that way.

So this paragraph should start with a propper definition of the gossip graph

We aimed to define this in section 2.2: Data structures.
Section 2.3.1: synchronisation gives an idea of the gossip process.
Note that we are a bit succinct there as we assume that gossip is familiar from the literature. This is one point I would like to expand on if and when we write an extended version of the paper.

Then a propper definition of H_{X,B} has to appear. It is impossible to understand the various involved functions, if the codomain is not defined.

I think I addressed this already. Feel free to ask again if it’s not clear enough :wink:

We need a proof that vertices in H_{X;B} that have no ancestors, are observers, otherwise some functions are not well defined.

Actually, that is not one of our claims. It isn’t necessary and it would actually never happen in practice.
The only gossip events without ancestors are the initial events. When the graph gets constructed, some events will eventually contain block votes. As the graph evolves, at some point, these block-votes will be strongly seen, so there will be observers.
Prior to that point, the meta-election for any node would be valid and return ⊥ (neither 0 nor 1). I guess the latest agreed block B is an optional input, which is not obvious in our paper so I’m taking note of this as a place where the wording can be improved.

In the definition of the set of aux functions: Why does self_parent always exists?

In any gossip graph with more than one node, the initial event (the only event without a self_parent) may never be an observer as it may not strongly see any other event by definition and events carrying auxiliary values have to be descendants of observers by definition too.
If the graph contains a single node, a single gossip event and that event contains a vote block, you may have found an edge-case where our protocol isn’t well defined :D. In that case, the meta-election should always trivially return 1, but maybe the paper would be clearer if we stated that edge case explicitely to avoid complicating any other place that assumes a self_parent in gossip events that descend from observers :slight_smile:

Is stage the adaptation of “round” in the underlying binary ABFT consensus? I mean the variable r_i in Figure 2 line (00) in the paper of Raynal et. al.

No. That would be what we call round. It isn’t too far though. The difference is that we perform a 3 steps process for the concrete coin. At the end of each step, we reset the round to 0 as we go for a new binary agreement. The stage keeps increasing.

I hope this covered your questions. Any follow-up welcome, although like @dirvine said, maybe the dev forum would be better suited for these types of in depth discussions :smiley:


#8

Why not define events in a such way that any event has self and other ancestors? We could just use hash(emptyset) in that case. Because thats what its actually IS. The ancestor is the empty set, so lets take that hash.

The question on the proof that any vertex that is not an observer in H_{X,B} has ancestors, is just to make sure, that all of the functions are at least well defined. If you have a vertex in H_{X,B} that is not an observer, some functions call ancestor vertices. In that case, there is no ancestor, hence the function is not defined.

Sure, you can capture that in practice, but for a clean scientific paper, its really bad. If you send a paper to review and you use undefined functions in proofs, that will certainly be rejected.


#9

Do we really need the “already meta_elected” in the definition of all the functions? For example in the definition of est, we have the case “if there exists an ancestor d of e such that v = meta election(d) 6 = ⊥”… If we could proof the consensus part without this, the definition of all the functions would be much simpler, as only self ancestors do play a role. The original b-BFTC handles this differently. It looks like a shortcut that makes sense in implementation, but not in the theory.

Then these function can be written in standard recursive style, which is easy as the set of self ancestors is evidently linear ordered and we can recurse like over natural numbers. Recursion over graphs is much more complicated, since the order is not obvious…

Actually the definition of all the functions in the meta election part, look like they ware more or less copied from an implementation. Because they are “optimized” that way. If we rewritem them in classical recursive style, we could try for simplification and “decoupling” to come at least close the simplicity of the original b-BFT consensus.


#10

Great to see some effort from outside of Maidsafe and the community to improve on important stuff!


#11

Was this discussion continued on the dev forum or are the questions from a week ago still unanswered? If it was, could someone link it?


#12

Still unanswered, I’m afraid. Will come back to it, though. Just been busy :sweat_smile:


#13

Why not define events in a such way that any event has self and other ancestors? We could just use hash(emptyset) in that case. Because thats what its actually IS. The ancestor is the empty set, so lets take that hash.

To me, saying the initial events have no parent is more expressive than saying they’ve got a parent that is “the null entity”. This one is mostly a matter of taste, though so your opinion may be fixed on this but I don’t think there is a strong argument for changing our definition.

The question on the proof that any vertex that is not an observer in H_{X,B} has ancestors, is just to make sure, that all of the functions are at least well defined. If you have a vertex in H_{X,B} that is not an observer, some functions call ancestor vertices. In that case, there is no ancestor, hence the function is not defined.

I’m not sure if it’s clear to you but there are exactly N events that have no ancestors. These are the initial events by each node. Nothing more, nothing less.
An event always sees itself, and for an initial event; that’s the only event it sees.
For strongly seeing, with a single node network, the initial event strongly sees itself. In any other network, the initial event from any node strongly sees no event.
Observer and further definitions flow from there.

Sure, you can capture that in practice, but for a clean scientific paper, its really bad. If you send a paper to review and you use undefined functions in proofs, that will certainly be rejected.

We’ll make sure to make that clear in the paper. Thanks for the observation.

Do we really need the “already meta_elected” in the definition of all the functions? For example in the definition of est, we have the case “if there exists an ancestor d of e such that v = meta election(d) 6 = ⊥”… If we could proof the consensus part without this, the definition of all the functions would be much simpler, as only self ancestors do play a role. The original b-BFTC handles this differently.

This is definitely needed.

In “Byzantine Agreement, Made Trivial”; they have this statement:
A player i exits this loop by propagating (i.e., by sending to all players, including himself), at some step, either a special value 0∗ or a special value 1∗, thereby instructing all players to “pretend” they respectively receive 0 and 1 from i in all future steps.

In “Signature-Free Asynchronous Byzantine Consensus with t < n/3 and O(n^2) Messages”, they have this point:

  • The statement decide() used at line08 allows the invoking process p_i to decide but does not stop its execution. A process executes round forever. This facilitates the description and the understanding of the algorithm.

Our “already meta-elected” bits are our way of expressing the same message.

It looks like a shortcut that makes sense in implementation, but not in the theory.

I think we disagree here. To me, if something is so clear it’s obvious how to implement it, it doesn’t make it a dirty/non-pure/non-academical “shortcut for implementation”; it just makes it a clear statement. Code is just a very clear and detailed expression of theoretical ideas…

Then these function can be written in standard recursive style, which is easy as the set of self ancestors is evidently linear ordered and we can recurse like over natural numbers. Recursion over graphs is much more complicated, since the order is not obvious…

I would love to see your suggestion in more details. I feel like we’ve hit or are close to the simplest necessary wording to describe the algorithm. If you can see a way to express it in a purer, more succinct fashion, I would be genuinely interested.

Actually the definition of all the functions in the meta election part, look like they ware more or less copied from an implementation. Because they are “optimized” that way. If we rewritem them in classical recursive style, we could try for simplification and “decoupling” to come at least close the simplicity of the original b-BFT consensus.

This paper was written before the code. It was written by programmers, though so we have our way of seeing the world. As I mentionned above, I think that having the paper be clear enough that you can see a way of implementing it is more a feature than a bug: it means that every detail is clear enough that you can fully understand it. When reading some papers, I sometimes have to unpack a lot of meaning from very compact statement and that generally makes me feel like it was written this way to show off succint writing skills rather than to convey a point as clearly as possible. From the programming world, we must convey a point as simply as possible since indeed it must be simple enough that a dumb machine will be able to do something with it.

This is my personal opinion, though. I know that some readers would prefer to see it expressed in the way you describe, so if you can think of ways to compactify the definitions while remaining exactly accurate, I am really keen on discussing them and maybe we could publish both papers side-by-side or replace bits of the paper if your approach is obviously superior in some cases.

I hope this doesn’t feel too much like I’m being defensive of the way we did things for the sake of it. I’m trying to remain somewhat objective; although of course I am quite aware of my biases as a programmer.
Once again, thank you very much for taking the time of engaging in this discussion. I really appreciate your thoughts on this.


#14

To me, saying the initial events have no parent is more expressive than saying they’ve got a parent that is “the null entity”. This one is mostly a matter of taste, though so your opinion may be fixed on this but I don’t think there is a strong argument for changing our definition.

Sure it works either way. My intention is to condense your paper into a small algorithm in “standard presentation”… So its not that important. On the level of implementation you handled it in the “cause” enum. My personal taste would be different though, but that too is not important.

I’m not sure if it’s clear to you but there are exactly N events that have no ancestors. These are the initial events by each node. Nothing more, nothing less.

I’m not talking about the gossip graph, as such. I’m talking about the subgraph H_{X,B}. Since it is only a subgraph, we have situations, where a vertex in H_{X,B} has no ancestors IN H_{X,B} without being an initial event. It might in fact be trivial to show, that each of these vertices is an observer. But IMHO that needs to be said for the various functions on H_{X,B} to be well defined.

The point is, that IF there is a vertex e in H_{X,B} that has no self parent INSIDE H_{X,B} and is not an observer, then functions like aux, are not well defined. The value aux(e) is computed as aux(self_parent(e)) but self_parent(e) is not in H_{X,B}. However, note that this can easily be changed. In your implementation you used Some() (if I remember correctly), but that is specific to a certain programming style.

The statement decide() used at line08 allows the invoking process p_i to decide but does not stop its execution. A process executes round forever. This facilitates the description and the understanding of the algorithm.

We could define the decide() value in such a way, that it is only computed from aux, bv, est and so on, if self parent decide is still empty. Therefore once a decide() is not empty anymore, it doesn’t change forever. This way, once a node decides, changes in aux, bv and est have no influence on it and it is static from that point on, no matter how aux, est and bv behave in the future.

Doing it like that, takes meta_election out of a lot of other functions and makes their involved, recursive definition a lot less complicated. And opens them to a pure recursive/inductive definition on the linear ordered set of self ancestors in H_{X,B}

I would love to see your suggestion in more details. I feel like we’ve hit or are close to the simplest necessary wording to describe the algorithm. If you can see a way to express it in a purer, more succinct fashion, I would be genuinely interested.

Might be true… But still I give it a go. After all its part of me trying to understand every bit of the algorithm. Mostly to validate the proofs.

As I mentioned above, I think that having the paper be clear enough that you can see a way of implementing it is more a feature than a bug: it means that every detail is clear enough that you can fully understand it.

Not much arguing here. I think it is a matter of taste, as you said. Depends although on what you want to achieve. If for example you want to verify the proof of PARSEC with CoQ or Isabell a different style might be preferred. After all, having additional papers like “PARSEC from a mathematicians p.o.v.”, can’t be a bad thing and reflects the open nature of your project.


#15

I’m not talking about the gossip graph, as such. I’m talking about the subgraph H_{X,B}. Since it is only a subgraph, we have situations, where a vertex in H_{X,B} has no ancestors IN H_{X,B} without being an initial event.

Right. Thanks for taking the time to clarify this. I now see the exact situation you’re refering to :smile:

It might in fact be trivial to show, that each of these vertices is an observer. But IMHO that needs to be said for the various functions on H_{X,B} to be well defined.

Right. If you’re speaking about having no ancestor at all in H_{X,B}; yes, it is trivial to show as any event in a meta-election must be either an observer or a descendant of an observer. I take your point, though: let’s make that cristal clear in the paper. (BTW, I plan to raise Jira tasks for points such as this one that came up in this thread. I’ll link them in this thread once I do it)

The point is, that IF there is a vertex e in H_{X,B} that has no self parent INSIDE H_{X,B} and is not an observer, then functions like aux, are not well defined. The value aux(e) is computed as aux(self_parent(e)) but self_parent(e) is not in H_{X,B}. However, note that this can easily be changed. In your implementation you used Some() (if I remember correctly), but that is specific to a certain programming style.

OK. Now that I see where you’re coming from, this makes sense. It wouldn’t be the case though as it’s easy to prove there is no such event.

We could define the decide() value in such a way, that it is only computed from aux, bv, est and so on, if self parent decide is still empty. Therefore once a decide() is not empty anymore, it doesn’t change forever. This way, once a node decides, changes in aux, bv and est have no influence on it and it is static from that point on, no matter how aux, est and bv behave in the future.

Doing it like that, takes meta_election out of a lot of other functions and makes their involved, recursive definition a lot less complicated. And opens them to a pure recursive/inductive definition on the linear ordered set of self ancestors in H_{X,B}

Uhm. This would definitely not be sufficient:
From the definition of “decide() at line 08…”, a decided value must never change in the future. This is necessary but not sufficient.
From the other paper (Byzantine Agreement Made Trivial), (quoting again so you don’t have to scroll up)

A player i exits this loop by propagating (i.e., by sending to all players, including himself), at some step, either a special value 0∗ or a special value 1∗, thereby instructing all players to “pretend” they respectively receive 0 and 1 from i in all future steps.

This means that all values (estimates, binary values, auxiliary values) must match the decided value in any stage after a decision is taken.
At least some of this (estimates) is definitely necessary for the proofs. The point is that if a node already decided, they will now be helping other nodes reach the correct decision as fast as possible.

For instance, say Alice decides that Bob’s say in the meta-election should be considered (her decided value for Bob is true). When Carol sees this, if she is still in the process of reaching consensus, she must consider Alice’s estimate for Bob to be true in any subsequent stage of the decision process. For the estimates, it is necessary to prove Lemma 3.5 which is a key point to prove Termination. Now you mention it, it may be that forcing the binary values and auxiliary values is only an optimisation (I am not managing to convince myself right now that it is necessary for our proofs, although I would want to give it deeper thoughts and discuss it with my team if I was going to remove these 2 lines from the paper). If it is indeed unnecessary, it could shave 2 lines from the paper; but I would still implement it as currently described as it would possibly speed up consensus, so no need to discard information that we can rely on :wink:

If you can see a way to express it in a purer, more succinct fashion, I would be genuinely interested.

Might be true… But still I give it a go. After all its part of me trying to understand every bit of the algorithm. Mostly to validate the proofs.

Please do! Can’t wait to see what you come up with :tada:

Not much arguing here. I think it is a matter of taste, as you said. Depends although on what you want to achieve. If for example you want to verify the proof of PARSEC with CoQ or Isabell a different style might be preferred.

The CoQ or Isabel thing is an extremely valid point I hadn’t considered, actually :smile:

After all, having additional papers like “PARSEC from a mathematicians p.o.v.”, can’t be a bad thing and reflects the open nature of your project.

Couldn’t agree more :smile:.

I’ve said it already but I’ll say it again: I can really appreciate the time you’re taking to give thoughtful feedback on the paper and the implementation. A massive thank you for this work from me and my entire team :smile:


#16

Makes at least two of us :slight_smile: . Thanks, @Andre_Gerome this is a very valid suggestion and as you say if you/we can condense the math and subsequently the code then this makes a lot of sense and I am sure would give any reviewer some comfort.


#17

Wow, amazing deep thought/analysis going on in here! Keep it up, love to see this developing – I wish I had the brains to be more than a cheerleader!


#19

That was dramatically over my head. HOWEVER, I want to thank @Andre_Gerome for taking the time time to review the parsec paper and furthermore to discuss it with @pierrechevalier83 and @dirvine. There’s a proverb that I love that came to mind when I read this: as iron sharpens iron, so one person sharpens another.


#20

Hey there. Apologies for being away for some time. I’m still working on the review of PARSEC, though.

And I have a concern regarding stability under forking as described in the following situation:

The terms “seen” and “strongly seen” are defined w.r.t. to forking events. User Alice is said to introduce a fork into the MerkleDAG (The gossip graph), if she creates two events A and B that both have the same self parent C.

Now suppose PARSEC is running for some time and n Events have been written into the data structure of consensused blocks already. So the meta votes process for these events is finished and cleaned up.

Now what happens if Alice creates a fork with a new event, that references to one of these old event, where order was already reached over? Doesn’t it mean, that all work from that old event on has to be recomputed?

Hopefully this is clear. The picture in my mind is that of a very large gossip graph, where things only happen at the top and the bottom is long satlled, but suddenly someone creates a fork, referencing to one of these old events at the bottom.

In Swirlds Hashgraph a virtual vote is only send (virtually) from event x to event w, if w is a descendent of x AND w can strongly see x. In PARSEC the vote is send if w can see x, i.e if w is a descendent of x. I think this might couse the previously mentioned trouble. Not?


#21

This fork case is not one of the detected malicious behaviour?