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

Design and implement quorum balancing #240

Closed
6 tasks done
bpalaggi opened this issue Aug 23, 2019 · 13 comments · Fixed by #663
Closed
6 tasks done

Design and implement quorum balancing #240

bpalaggi opened this issue Aug 23, 2019 · 13 comments · Fixed by #663
Assignees
Labels
C.Blockchain Story-Points:13 type-feature
Milestone

Comments

@bpalaggi
Copy link

bpalaggi commented Aug 23, 2019

As a developer, I need to know what algorithm to follow for quorum assignment in order for the protocol to prevent censorship while being open.

Description

We can consider two degenerate cases for quorum balancing:

  • When there is a single quorum with all nodes in it, safety is maximized, but so is communication overhead;
  • When each node live in their own quorum, safety does not exists but there is no communication: a less degenerate version would be having a ring where every node belongs to two quorums, each with another node (or: two two nodes quorums).

The goal of quorum balancing is to produce a network graph with optimal safety & overhead. Note that the nodes that are quorum intersections are likely to be higher-staking nodes, as they have more to lose.

Example of rules:

  • There is no quorum with < 3 nodes;
  • There is no quorum with > 7 nodes;
  • A quorum economic value must be >= 350,000 BOA;
  • The top X (X=5?) stakers are placed in different quorums and used as 'seed';

Definition of done:

  • A new validator is assigned a quorum immediately;
  • Quorums get regularly shuffled (how often?);
  • There is a sufficient (how much?) quorum intersection;
  • Validators are distributed among quorums in an unpredictable manner;
  • Validators are distributed among quorums in a fairly balanced way;
  • Quorum distribution only depends on globally available state;

Tentative approach:

  • Come up with a simple algorithm based on the example rules posted above;
  • Build test case for working and non-working (byzantine) validators;
  • Compute the economic penalty (low & high bounds) => If node A cheats, home much does it cost ? Is it aligned with the power this node has in the system ?;
  • Optimize
  • Repeat
@Geod24 Geod24 added this to the 2. Validator milestone Sep 4, 2019
@Geod24 Geod24 added the type-feature label Sep 4, 2019
@Geod24 Geod24 changed the title Quorum balancing Design and implement quorum balancing Sep 5, 2019
@Geod24 Geod24 added the status-blocked label Sep 5, 2019
@Geod24
Copy link
Contributor

Geod24 commented Sep 5, 2019

Depends on #209

@bpalaggi bpalaggi added this to To do in Sprint #8 (2019-10-29 to 2019-11-12) via automation Oct 29, 2019
@MichaelKim20 MichaelKim20 moved this from To do to In progress (Max 4) in Sprint #8 (2019-10-29 to 2019-11-12) Nov 1, 2019
@bpalaggi bpalaggi added this to To do in Sprint #9 (2020-01-07 to 2020-01-20) via automation Jan 7, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #8 (2019-10-29 to 2019-11-12) Jan 7, 2020
@Geod24 Geod24 moved this from To do to Blocked (Max 1) in Sprint #9 (2020-01-07 to 2020-01-20) Jan 7, 2020
@Geod24 Geod24 removed the status-blocked label Jan 21, 2020
@bpalaggi bpalaggi moved this from Blocked (Max 1) to In progress (Max 5) in Sprint #9 (2020-01-07 to 2020-01-20) Jan 21, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #9 (2020-01-07 to 2020-01-20) Jan 21, 2020
@AndrejMitrovic AndrejMitrovic self-assigned this Jan 21, 2020
@AndrejMitrovic AndrejMitrovic added this to To do in Sprint #10 (2020-01-21 to 2020-02-10) via automation Jan 21, 2020
@AndrejMitrovic
Copy link
Contributor

AndrejMitrovic commented Jan 21, 2020

- [ ] Validators are distributed among quorums in an unpredictable manner;

I think this sentence is not entirely correct. It should be predictable given another number X, which itself is unpredictable (and based on the preimage). So the algorithm to select the quorum is predictable, but its inputs are not predictable.

@AndrejMitrovic
Copy link
Contributor

AndrejMitrovic commented Jan 21, 2020

Quorums get regularly shuffled (how often?);

According to the yellow paper: Quorum balancing events happens once every 6 rounds.. So, every hour.

@AndrejMitrovic
Copy link
Contributor

AndrejMitrovic commented Jan 21, 2020

I would actually add that past performance of a validator should be taken into account when assigning quorums. For example:

The top X (X=5?) stakers are placed in different quorums and used as 'seed';

This could be gamed by a new player that spins up 5 new nodes and stakes more than the next 5 highest staked nodes. If we could incorporate the number N, where N is the number of times a node's public key participated in a finalized (accepted) vote for a block, then we could take into account the past performance of a node too. It should be a sort of "weight" to the algorithm.

@AndrejMitrovic AndrejMitrovic added the Story-Points:8 label Jan 22, 2020
@AndrejMitrovic AndrejMitrovic moved this from To do to In progress (Max 5) in Sprint #10 (2020-01-21 to 2020-02-10) Jan 22, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #10 (2020-01-21 to 2020-02-10) Feb 11, 2020
@bpalaggi bpalaggi added this to To do in Sprint #11 (2020-02-11 to 2020-02-24) via automation Feb 11, 2020
@bpalaggi bpalaggi moved this from To do to In progress (Max 5) in Sprint #11 (2020-02-11 to 2020-02-24) Feb 11, 2020
@AndrejMitrovic
Copy link
Contributor

AndrejMitrovic commented Feb 12, 2020

Some research notes:

This post describes the new quorum config in Stellar, and also has a general overview of how quorums in Stellar work: https://medium.com/stellar-developers-blog/why-quorums-matter-and-how-stellar-approaches-them-547336c1275

The two PRs implementing semi-automatic quorum configuration and an "intersection-checker"
stellar/stellar-core#2125
stellar/stellar-core#2127

Here's a paper linked to from the blog post: https://arxiv.org/pdf/1902.06493.pdf. From the paper:

The Disjoint Quorums Problem answers the question whether a given instance of Federated
Byzantine Agreement System contains two quorums that have no nodes
in common. We show that this problem is NP-complete.


In our case we wouldn't mark any nodes as belong to an "organization" and the "quality" of the nodes would not be hardcoded, but instead we would just use the amount of stake as the marker of quality. After all, if a node misbehaves then it will get slashed, and its staked amount becomes lower (and therefore the "quality" of the node drops).

The blog post describes a commit we're not using yet (https://github.com/stellar/stellar-core/releases/tag/v11.2.0) which was released in June 28th 2019. We're using a commit from May 20th 2019.

It might be possible to reuse / adapt these Stellar routines (Config::generateQuorumSet / Config::generateQuorumSetHelper), if they don't depend on any Stellar-specific state. But we do have to take into account the random value and the quorum re-shuffling too.


Edit: Another useful article: https://www.stellar.org/developers-blog/intuitive-stellar-consensus-protocol

@bpalaggi bpalaggi added this to To do in Sprint #12 (2020-02-25 to 2020-03-9) via automation Feb 25, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #11 (2020-02-11 to 2020-02-24) Feb 25, 2020
@bpalaggi bpalaggi moved this from To do to In progress (Max 5) in Sprint #12 (2020-02-25 to 2020-03-9) Feb 25, 2020
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 14, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 14, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 14, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 14, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 14, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 14, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 16, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 16, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 16, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 16, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 16, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 28, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Apr 28, 2020
The generator uses a provided source of randomness
to shuffle the nodes into different quorums.

The source of randomness should be derived from
the revealed preimages of the validators.

Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
@bpalaggi bpalaggi added this to To do in Sprint #16 (2020-05-05 to 2020-05-18) via automation May 6, 2020
@bpalaggi bpalaggi moved this from To do to In progress (Max 5) in Sprint #16 (2020-05-05 to 2020-05-18) May 6, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #15 (2020-04-07 to 2020-05-04) May 6, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #16 (2020-05-05 to 2020-05-18) May 19, 2020
@bpalaggi bpalaggi added this to To do in Sprint #19 (2020-06-16 to 2020-06-22) via automation Jun 16, 2020
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Jun 16, 2020
Nodes which have a higher staken amount have a
higher chance of being included in each node's
quorum set.

Part of: bosagora#240
AndrejMitrovic added a commit to AndrejMitrovic/agora that referenced this issue Jun 18, 2020
Nodes which have a higher stake compared
to the rest of the network will have a
higher chance of being included in other
node's quorum sets.

Part of: bosagora#240
@bpalaggi bpalaggi moved this from To do to In progress in Sprint #19 (2020-06-16 to 2020-06-22) Jun 22, 2020
@Geod24 Geod24 added the C.Blockchain label Jul 5, 2020
@AndrejMitrovic
Copy link
Contributor

AndrejMitrovic commented Jul 27, 2020

Currently the only part that is not fully implemented is:

  • Quorums get regularly shuffled (how often?);

Right now the quorums only get reshuffled when the validator set changes (new enrollment, expired enrollment). But we may want to shuffle quorums regularly, for example every N blocks (N would be defined by the protocol).

However I think this will require more preimage support. In our unittests we have tests such as:

  • Set validation cycle to 20
  • Generate genesis
  • Create 19 blocks
  • Start the nodes

The nodes won't have any preimages on startup except the commitment in the enrollment in the genesis block. If we set the "periodic shuffle" N parameter to 10, then on boot-up the nodes would generate the quorums for block height 0 and then on block height 10. But it's not possible to test this right now because the preimages are missing for height 10, so this would lead to an assertion failure.

@Geod24 Geod24 closed this as completed Jul 28, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C.Blockchain Story-Points:13 type-feature
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants