Page MenuHomePhabricator

[avalanche] Create a structure to accumulate avalanche votes
ClosedPublic

Authored by deadalnix on Nov 11 2018, 01:08.

Details

Summary

This is slightly different from what is described in the avalanche paper as it uses a rolling quorum instead of rounds, which means we need to use significantly higher confidence parameter, as it increases much faster.

The vote is considered inconclusive if more than one respondant disagrees with the quorum of 8.

Confidence required for finalization is 128.

Test Plan

Added test cases.

Diff Detail

Repository
rABC Bitcoin ABC
Branch
avaimpl
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 3832
Build 5737: Bitcoin ABC Buildbot (legacy)
Build 5736: arc lint + arc unit

Event Timeline

deadalnix changed the visibility from "Public (No Login Required)" to "Restricted Project (Project)".Nov 11 2018, 01:09
deadalnix edited the test plan for this revision. (Show Details)
schancel added inline comments.
src/avalanche_impl.h
14

Doesn't this imply that you need 64 yes votes in a row to finalize? This seems quite high.

When I had read the avalanche paper I was under the impression you sample ~8 random peers, count the votes, increase or decrease the confidence. Repeat this sampling X number of times.

This VoteRecord seems to be implemented to support polling a single random peer over X number of ms and eventually solidifying the vote after 64 positive quorums of 15 votes in a row. However, the quorums are taken as the most recent vote, and the 14 preceding?

14

Should there be a comment about what the byzantine threshold is for this finalization score given how the VoteRecord is hardcoded?

22

Do these need to be atomic variables?

70

Should this be?

confidence = ((confidence & 0xfffe) << 1) | 2;
src/test/avalanche_tests.cpp
49

Normally, after this point we would stop polling though? Right?

This revision is now accepted and ready to land.Nov 11 2018, 03:10
jasonbcox added inline comments.
src/test/avalanche_tests.cpp
13 ↗(On Diff #5737)

Calling third param state is confusing. Should be isStateValid

deadalnix added inline comments.
src/avalanche_impl.h
22

No. This is in a rwcollection.

70

No. I'm not sure what this is even supposed to do.

Fabien added a subscriber: Fabien.
Fabien added inline comments.
src/avalanche_impl.h
29 ↗(On Diff #5737)

it => bit

72 ↗(On Diff #5737)

interal => internal

This revision was automatically updated to reflect the committed changes.
deadalnix changed the visibility from "Restricted Project (Project)" to "All Users".Nov 21 2018, 12:18
deadalnix changed the visibility from "All Users" to "Public (No Login Required)".