Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Clear up confusion by introducing definitions in hbbft #347

Open
mbr opened this issue Nov 19, 2018 · 13 comments
Open

Clear up confusion by introducing definitions in hbbft #347

mbr opened this issue Nov 19, 2018 · 13 comments

Comments

@mbr
Copy link
Contributor

mbr commented Nov 19, 2018

There has been a bit of confusion between observers, nodes, validators and some other terminology, especially since it is not 100% clearly defined. Our main issues occur on the boundary between algorithms and network transport, also the "abuse" of the term "observer" has been an issue.

This is an attempt to define these terms clearly. Any suggestions/improvements are welcome, also we need a place to stick these (ideally, the hbbft docs?).

Finally, these should be checked for compatibility with other PoA projects.

(see end for up-to-date version)

## Transport layer

The transport layer routes messages sent by nodes. Every transport network message has a destination, which is either a single node ID or All. Messages destined to All are sent to any known node by the sender, this resolution happens at the latest possible time when the message is sent.

* Node: Any instance of the program running, capable of receiving and sending messages. Every node is known to the transport network by an ID. Nodes may send and receive messages.

* Peer: A node in the transport network that is not the current one.

* Observer: A node that never sends messages. For this reason, it never influences the network (and is technically "invisible" to upper algorithm layers), but affects performance.

* Transport network: An fully interconnected network of nodes.

## Algorithm layer:

Any algorithm network runs on top of a transport network.

* Participant: A node that actively runs an algorithm. It sends and receives messages.

* Auditor: An observer that runs an instance of an algorithm passively, e.g. to verify its output. It has no influence on the network.

* Network: A complete graph of participants connected through a transport network.

* Network size: A network's number of participants.

* Faulty participant: A malicious or malfunctioning ("byzantine") participant.

## Specific to DHB

Every node ever actively involved in DHB is a participant. However, any participant can be in one of two states:

* Candidate: A participant seeking to be included in a future set of validators.

* Validator: An "incumbent", active validator that actively signs blocks.

The network sizes of DHB must not be confused with the network size of a contained Honey Badger instance inside DHB, as the size of DHB includes candidates.

@mbr
Copy link
Contributor Author

mbr commented Nov 19, 2018

My remaining two gripes with this are that "faulty node" is no longer a meaningful term and "faulty participant" does not have the same ring to it.

@mbr mbr self-assigned this Nov 19, 2018
@c0gent
Copy link
Contributor

c0gent commented Nov 19, 2018

I think this is a step in the right direction. I really like the 'Auditor' term. I think we should probably continue to call a 'Participant' a 'Validator' though, in the interest of minimal disruption. You could then rename the DHB-Validator to 'Incumbent' (a term to be used in documentation, etc., not a type rename in code).

@vkomenda
Copy link
Contributor

I like these definitions. But I still have a few points for discussion. Please feel free to disagree. There are a few things that catch the attention in your scheme of definitions.

Do you view a participant as a node in a distributed algorithm? I'm inclined to keep the term node since it is used in papers that define distributed algorithms we implemented. Renaming nodes as "participants" contradicts the established terminology. Maybe call them "algorithm nodes" in general? Possibly noting that we call those just "nodes" for short? Renaming nodes as "participants" runs outside the established terminology.

I'd rather come up with a new name for constructs that we added to the theoretical algorithms to allow them to change their run-time parameters, at the level of algorithms. I'd say that instead we need a term to call peers in the sender queue. If "nodes" is taken by the algorithms then maybe "members"?

@andogro
Copy link
Contributor

andogro commented Nov 20, 2018

Thanks for initiating - it helps clarify a lot! I can include as a glossary in the docs/wiki.

Wondering if this simplification makes sense?

Any algorithm network runs on top of a transport network. Nodes in the algorithm network can either be active or passive.

Active Nodes: Nodes in the network actively running an algorithm. They send and receive messages.

  • Validator: An active node that signs blocks.
  • Candidate: An active node seeking to become a validator (DHB only).
  • Faulty: An active node that is faulty, malicious or malfunctioning.

Passive Nodes: Observer nodes that receive messages but have no influence on network functionality.

  • Auditor A passive node that runs an instance of an algorithm but does not send messages, useful for verifying output.

I’m not a huge fan of auditor because it suggests participation (and taxes) to me. Does witness, watcher, or listener do anything for you (or possibly defining observer terminology at the algorithm layer and using another term at the transport layer)? I can live with auditor but will need to adjust my attitude accordingly..

I believe Validators would be the same in this case for both HB and DHB - is that true? Not sure if Incumbent nodes need to be identified for testing or some other purpose?

@afck
Copy link
Collaborator

afck commented Nov 20, 2018

Also note the usage of the words "staker", "validator" and "observer" in the new contracts.

@afck
Copy link
Collaborator

afck commented Nov 21, 2018

This is the current nomenclature in the new contracts:

  • observer is the address which received at least one stake (observer can be validator if it is chosen randomly at the beginning of new staking epoch);
  • pool is the same as observer (its another name);
  • staker is the address which makes a stake for some observer (or a few observers). Staker puts his stake in the pool of observer (pool of stakes for this observer).

@mbr
Copy link
Contributor Author

mbr commented Dec 4, 2018

Here's the latest discussion result (missing some context from the video):

Transport

Transport Network -> Network
Node -> (Active Node)
Observer -> Passive Node

Consensus Protocol

DistAlgorithm -> ConsensusProtocol
Quorum := The 1/3 stuff
Committee := Participants that count toward quorum
Optional: Participant -> Member of a committee

Optional: Validator -> Member of a committee
Optional: Witness := Passive node that runs the algorithm

"Layer 3"

Honey Badger:
Validator := Participant

Broadcast:
Proposer := One of the participants

Dynmic Honey Badger:
Candidate := "Hopeful" (active node) for the next committee
Validator := Participant

@andogro
Copy link
Contributor

andogro commented Dec 4, 2018

Thanks Marc, I appreciate the bottom up approach. If we keep Quorum, we will want to clarify that the requirements fluctuate depending on the Layer 3 protocol. If this introduces more confusion than it solves, and doesn't have any precedent in the literature (as Committee does?), then it may be simpler to leave as Committee size despite the length. A brief look around turns up lots on Quorum, which is the jpmorgan blockchain :(. Mentioning these items in case anyone else has thoughts on the subject. For conciseness, I think quorum is good, for clarity, I think size is more clear. Either should work. Other than that, we would keep Participant in the Consensus Protocol layer and stress that there are different types of participants in Layer 3.

@mbr
Copy link
Contributor Author

mbr commented Dec 5, 2018

Regarding quorum, it's not not the size, but the portion of the size that matters? @afck: Can you comment on quorum and usage/occurence frequency?

I am not 100% set on the definition though, because it's more common to state that 3f < N, instead of a quorum q = N-f => f = N-q => 3(N-q) < N => q = 2/3*N+1.

@afck
Copy link
Collaborator

afck commented Dec 5, 2018

I don't think we should define "quorum" at all; it's not an hbbft-specific term and doesn't even have one fixed meaning in any particular algorithm. There are plenty of instances where we do something like voting, on all layers of the stack, and I'd call the amount of required votes a "quorum", that's at least one reading of the dictionary definition. But we might as well just avoid the term and talk about "majority", "supermajority" or "threshold".

I guess in our code, a quorum is often f + 1, but sometimes also N - f or 2 f + 1.

@mbr
Copy link
Contributor Author

mbr commented Dec 5, 2018

The issue I have with "majority" is that cases like f + 1 often are not a majority =). Threshold is better, but do we run into confusion because it's closely associated with threshold_crypto?

@afck
Copy link
Collaborator

afck commented Dec 5, 2018

I'd say threshold cryptography is just one example of an algorithm that involves a threshold? I don't consider it a different meaning that would introduce ambiguity here.
Anyway, I'm not even sure where we have that problem in the documentation. In many places we just write something like "wait for f + 1 messages…", "once there are at least N - f…", etc., without using any of those terms.

@mbr
Copy link
Contributor Author

mbr commented Dec 5, 2018

I hope this will be the final version then:


Definitions

Network Layer

The transport layer routes messages sent by nodes. Every transport network message has a destination, which is either a single node ID or All. Messages destined to All are sent to any known node by the sender, this resolution happens at the latest possible time when the message is sent.

  • Active node: A node that can send and receive messages.
  • Passive node: A node that cannot send messages, but will receive all messages an active node would receive in its place.

Consensus Protocol Layer

A consensus protocol is a distributed algorithm that runs on top of a network.

  • Faulty/Byzantine node: A node that may not execute the algorithm correctly.
  • Committee: An algorithm-dependent subset of the active nodes.
  • Participant: A node that is part of the committee.
  • Threshold: An algorithm-dependent threshold for the maximum allowed number of faulty nodes in the committee.

Algorithm-specific layer

The third layer is different for every algorithm and may introduce new terms. Lower-layer terms should be reused though, to reduce vocabulary inflation. Some examples:

Honey Badger, Dynamic Honey Badger

  • Validator: Synonym for participant
  • Candidate: An active node that is not a part of the committee.

Broadcast

  • Proposer: The active node that initiates the broadcasting process.

Optional terms

Optional terms are not necessary to describe things, but are in common use:

  • Peer: From a single node's viewpoint, any other node is a peer.
  • Observer: This term will be retired, as it has too many conflicting meanings all-around at the moment.
  • Witness: A passive node that runs an algorithm (potentially to verify it is running correctly) (formerly called an auditor).

Changes to be made:

  • Rename the DistAlgorithm trait to ConsensusProtocol (Rename DistAlgorithm to ConsensusProtocol. #377)
  • Rename methods in library source to be in line with new wording (there should be few of these)
  • Rename methods and attributes of the test network to match the new definitions
  • Insert these definitions into the docs
  • Update documentation with these changes

@mbr mbr removed their assignment Dec 31, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants