Changeset View
Changeset View
Standalone View
Standalone View
src/avalanche_impl.h
- This file was added.
// Copyright (c) 2018 The Bitcoin developers | |||||
// Distributed under the MIT software license, see the accompanying | |||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | |||||
#ifndef BITCOIN_AVALANCHE_IMPL_H | |||||
#define BITCOIN_AVALANCHE_IMPL_H | |||||
#include <cstdint> | |||||
namespace { | |||||
/** | |||||
* Finalization score. | |||||
*/ | |||||
static int AVALANCHE_FINALIZATION_SCORE = 128; | |||||
schancel: Doesn't this imply that you need 64 yes votes in a row to finalize? This seems quite high. | |||||
schancelUnsubmitted Not Done Inline ActionsShould there be a comment about what the byzantine threshold is for this finalization score given how the VoteRecord is hardcoded? schancel: Should there be a comment about what the byzantine threshold is for this finalization score… | |||||
/** | |||||
* Vote history. | |||||
*/ | |||||
struct VoteRecord { | |||||
private: | |||||
// Historical record of votes. | |||||
uint16_t votes; | |||||
schancelUnsubmitted Not Done Inline ActionsDo these need to be atomic variables? schancel: Do these need to be atomic variables? | |||||
deadalnixAuthorUnsubmitted Done Inline ActionsNo. This is in a rwcollection. deadalnix: No. This is in a rwcollection. | |||||
// confidence's LSB bit is the result. Higher bits are actual confidence | |||||
// score. | |||||
uint16_t confidence; | |||||
/** | |||||
* Return the number of it set in an integer value. | |||||
* TODO: There are compiler intrinsics to do that, but we'd need to get them | |||||
* detected so this will do for now. | |||||
*/ | |||||
static uint32_t countBits(uint32_t value) { | |||||
uint32_t count = 0; | |||||
while (value) { | |||||
// If the value is non zero, then at least one bit is set. | |||||
count++; | |||||
// Clear the rightmost bit set. | |||||
value &= (value - 1); | |||||
} | |||||
return count; | |||||
} | |||||
public: | |||||
VoteRecord() : votes(0xaaaa), confidence(0) {} | |||||
bool isValid() const { return confidence & 0x01; } | |||||
uint16_t getConfidence() const { return confidence >> 1; } | |||||
bool hasFinalized() const { | |||||
return getConfidence() > AVALANCHE_FINALIZATION_SCORE; | |||||
} | |||||
bool registerVote(bool vote) { | |||||
votes = (votes << 1) | vote; | |||||
auto bits = countBits(votes & 0xff); | |||||
bool yes = bits > 6; | |||||
bool no = bits < 2; | |||||
if (!yes && !no) { | |||||
// The vote is inconclusive. | |||||
return false; | |||||
} | |||||
if (isValid() == yes) { | |||||
// If the vote is in agreement with our internal status, increase | |||||
// confidence. | |||||
confidence += 2; | |||||
schancelUnsubmitted Not Done Inline ActionsShould this be? confidence = ((confidence & 0xfffe) << 1) | 2; schancel: Should this be?
```
confidence = ((confidence & 0xfffe) << 1) | 2;
```
| |||||
deadalnixAuthorUnsubmitted Done Inline ActionsNo. I'm not sure what this is even supposed to do. deadalnix: No. I'm not sure what this is even supposed to do. | |||||
} else { | |||||
// The vote did not agree with our interal state, in that case, | |||||
// reset confidence. | |||||
confidence = yes; | |||||
} | |||||
return true; | |||||
} | |||||
}; | |||||
} | |||||
#endif // BITCOIN_AVALANCHE_IMPL_H |
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?