Differential D2040

[avalanche] Create a structure to accumulate avalanche votes
ClosedPublic
Actions

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

Details

Reviewers

schancel
Fabien

Group Reviewers

Restricted Project

Commits

rSTAGING280fa002fa7d: [avalanche] Create a structure to accumulate avalanche votes
rABC280fa002fa7d: [avalanche] Create a structure to accumulate avalanche votes

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 3911
Build 5894: Bitcoin ABC Buildbot (legacy)
Build 5893: arc lint + arc unit

Event Timeline

deadalnix created this revision.Nov 11 2018, 01:08

Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 11 2018, 01:08

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)

Off by one error.

schancel added a subscriber: schancel.Nov 11 2018, 02:13

schancel added inline comments.

src/avalanche_impl.h
14 ↗	(On Diff #5736)	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 ↗	(On Diff #5736)	Should there be a comment about what the byzantine threshold is for this finalization score given how the VoteRecord is hardcoded?
22 ↗	(On Diff #5736)	Do these need to be atomic variables?
70 ↗	(On Diff #5736)	Should this be? confidence = ((confidence & 0xfffe) << 1) \| 2;
src/test/avalanche_tests.cpp
49 ↗	(On Diff #5736)	Normally, after this point we would stop polling though? Right?