1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
use std::cell::Cell;
use crate::snowman::snowball::{self, binary};
use avalanche_types::ids::{bag::Bag, bits, Id};
/// Represents a binary node with either no child, or a single child.
/// It handles the voting on a range of identical, virtuous, snowball instances.
/// ref. "avalanchego/snow/consensus/snowball/tree.go#binaryNode"
#[derive(Clone, Debug)]
pub struct Node {
/// Parameters inherited from the tree.
pub parameters: crate::Parameters,
/// Runs snowball logic.
pub snowball: binary::Snowball,
/// The choices preferred at every branch in their sub-tree.
pub preferences: Cell<[Id; 2]>,
/// The index in the Id of the choice that this node is deciding on.
/// Will be in the range [0, 256)
pub bit: Cell<i64>,
/// Used as an optimization to prevent needless tree traversals.
/// It is the continuation of shouldReset in the Tree struct.
pub should_reset: Cell<[bool; 2]>,
/// The child is the potentially none, node that votes on the next bits
/// in the decision.
pub child0: Option<Box<snowball::Node>>,
pub child1: Option<Box<snowball::Node>>,
}
impl Node {
pub fn preference(&self) -> Id {
let pref = self.snowball.preference() as usize;
let preferences = self.preferences.take();
let preference = preferences[pref];
self.preferences.set(preferences);
preference
}
pub fn decided_prefix(&self) -> i64 {
self.bit.get()
}
pub fn finalized(&self) -> bool {
self.snowball.finalized()
}
pub fn add(&mut self, id: &Id) -> snowball::Node {
let bit = id.bit(self.bit.get() as usize);
let child = match bit {
bits::Bit::Zero => self.child0.clone(),
bits::Bit::One => self.child1.clone(),
};
// If child is nil, then we are running an instance on the last bit. Finding
// two hashes that are equal up to the last bit would be really cool though.
// Regardless, the case is handled
if let Some(boxed_child) = child.clone() {
// +1 is used because we already explicitly check the p.bit bit
if bits::equal_subset(
self.bit.get() as usize + 1,
boxed_child.decided_prefix() as usize,
&self.preferences.get()[bit.as_usize()],
id,
) {
let boxed_child = child.unwrap();
let added_child = match *boxed_child {
snowball::Node::Unary(mut unary_node) => unary_node.add(id),
snowball::Node::Binary(mut binary_node) => binary_node.add(id),
};
match bit {
bits::Bit::Zero => self.child0 = Some(Box::new(added_child)),
bits::Bit::One => self.child1 = Some(Box::new(added_child)),
}
}
}
// If child is nil, then the id has already been added to the tree, so
// nothing should be done
// If the decided prefix isn't matched, then a previous decision has made
// the id that is being added to have already been rejected
snowball::Node::Binary(self.clone())
}
/// Returns the new node and whether the vote was successful.
/// ref. "avalanchego/snow/consensus/tree.go" "binaryNode.RecordPoll"
pub fn record_poll(&mut self, votes: Bag, reset: bool) -> (snowball::Node, bool) {
// The list of votes we are passed is split into votes for bit 0
// and votes for bit 1
let split_votes = votes.split(self.bit.get() as usize);
let mut bit = 0;
// We only care about which bit is set if a successful poll can happen
if split_votes[1].len() >= self.parameters.alpha as u32 {
bit = 1;
}
let mut updated_should_reset = self.should_reset.take();
if reset {
self.snowball.record_unsuccessful_poll();
updated_should_reset[bit] = true;
// 1-bit isn't set here because it is set below anyway
}
// they didn't get the threshold of votes
updated_should_reset[1 - bit] = true;
self.should_reset.set(updated_should_reset);
if split_votes[bit].len() < self.parameters.alpha as u32 {
// pruned votes < alpha; didn't get enough votes
self.snowball.record_unsuccessful_poll();
// The winning child didn't get enough votes either
updated_should_reset[bit] = true;
self.should_reset.set(updated_should_reset);
return (snowball::Node::Binary(self.clone()), false);
}
// this bit got alpha votes, it was a successful poll
self.snowball.record_successful_poll(bit as i64);
match bit {
0 => {
if let Some(child) = self.child0.clone() {
// The votes are filtered to ensure that they are votes
// that should count for the child
match *child {
snowball::Node::Unary(mut unary_node) => {
let filtered_votes = split_votes[bit].filter(
self.bit.get() as usize + 1,
unary_node.decided_prefix() as usize,
&self.preferences.get()[bit],
);
let (new_child, _) = unary_node
.record_poll(filtered_votes, self.should_reset.get()[bit]);
if self.snowball.finalized() {
// If we are decided here, that means we must have decided
// due to this poll. Therefore, we must have decided on bit.
return (new_child, true);
}
let mut updated_preferences = self.preferences.take();
let new_child_preference = match &new_child {
snowball::Node::Unary(n) => n.preference(),
snowball::Node::Binary(n) => n.preference(),
};
updated_preferences[bit] = new_child_preference;
self.preferences.set(updated_preferences);
self.child0 = Some(Box::new(new_child));
}
snowball::Node::Binary(mut binary_node) => {
let filtered_votes = split_votes[bit].filter(
self.bit.get() as usize + 1,
binary_node.decided_prefix() as usize,
&self.preferences.get()[bit],
);
let (new_child, _) = binary_node
.record_poll(filtered_votes, self.should_reset.get()[bit]);
if self.snowball.finalized() {
// If we are decided here, that means we must have decided
// due to this poll. Therefore, we must have decided on bit.
return (new_child, true);
}
let mut updated_preferences = self.preferences.take();
let new_child_preference = match &new_child {
snowball::Node::Unary(n) => n.preference(),
snowball::Node::Binary(n) => n.preference(),
};
updated_preferences[bit] = new_child_preference;
self.preferences.set(updated_preferences);
self.child0 = Some(Box::new(new_child));
}
};
}
}
1 => {
if let Some(child) = self.child1.clone() {
// The votes are filtered to ensure that they are votes
// that should count for the child
match *child {
snowball::Node::Unary(mut unary_node) => {
let filtered_votes = split_votes[bit].filter(
self.bit.get() as usize + 1,
unary_node.decided_prefix() as usize,
&self.preferences.get()[bit],
);
let (new_child, _) = unary_node
.record_poll(filtered_votes, self.should_reset.get()[bit]);
if self.snowball.finalized() {
// If we are decided here, that means we must have decided
// due to this poll. Therefore, we must have decided on bit.
return (new_child, true);
}
let mut updated_preferences = self.preferences.take();
let new_child_preference = match &new_child {
snowball::Node::Unary(n) => n.preference(),
snowball::Node::Binary(n) => n.preference(),
};
updated_preferences[bit] = new_child_preference;
self.preferences.set(updated_preferences);
self.child1 = Some(Box::new(new_child));
}
snowball::Node::Binary(mut binary_node) => {
let filtered_votes = split_votes[bit].filter(
self.bit.get() as usize + 1,
binary_node.decided_prefix() as usize,
&self.preferences.get()[bit],
);
let (new_child, _) = binary_node
.record_poll(filtered_votes, self.should_reset.get()[bit]);
if self.snowball.finalized() {
// If we are decided here, that means we must have decided
// due to this poll. Therefore, we must have decided on bit.
return (new_child, true);
}
let mut updated_preferences = self.preferences.take();
let new_child_preference = match &new_child {
snowball::Node::Unary(n) => n.preference(),
snowball::Node::Binary(n) => n.preference(),
};
updated_preferences[bit] = new_child_preference;
self.preferences.set(updated_preferences);
self.child1 = Some(Box::new(new_child));
}
};
}
}
_ => panic!("unexpected preference bit {}", bit),
}
// We passed the reset down
updated_should_reset[bit] = false;
self.should_reset.set(updated_should_reset);
(snowball::Node::Binary(self.clone()), true)
}
}
/// ref. <https://doc.rust-lang.org/std/string/trait.ToString.html>
/// ref. <https://doc.rust-lang.org/std/fmt/trait.Display.html>
/// Use "Self.to_string()" to directly invoke this.
impl std::fmt::Display for Node {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} Bit = {}", self.snowball, self.decided_prefix())
}
}