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
use crate::Ledger;
use snarkos_errors::{objects::BlockError, storage::StorageError};
use snarkos_models::{algorithms::LoadableMerkleParameters, objects::Transaction};
use snarkos_objects::{BlockHeader, BlockHeaderHash};
const OLDEST_FORK_THRESHOLD: u32 = 1024;
#[derive(Clone, Debug)]
pub enum BlockPath {
ExistingBlock,
CanonChain(u32),
SideChain(SideChainPath),
}
#[derive(Clone, Debug)]
pub struct SideChainPath {
pub shared_block_number: u32,
pub new_block_number: u32,
pub path: Vec<BlockHeaderHash>,
}
impl<T: Transaction, P: LoadableMerkleParameters> Ledger<T, P> {
pub fn get_block_path(&self, block_header: &BlockHeader) -> Result<BlockPath, StorageError> {
let block_hash = block_header.get_hash();
if self.block_hash_exists(&block_hash) {
return Ok(BlockPath::ExistingBlock);
}
if &self.get_latest_block()?.header.get_hash() == &block_header.previous_block_hash {
return Ok(BlockPath::CanonChain(self.get_latest_block_height() + 1));
}
let mut side_chain_path = vec![];
let mut parent_hash = block_header.previous_block_hash.clone();
for _ in 0..=OLDEST_FORK_THRESHOLD {
match &self.get_block_number(&parent_hash) {
Ok(block_num) => {
let longest_path = self.longest_child_path(block_hash)?;
side_chain_path.extend(longest_path.1);
return Ok(BlockPath::SideChain(SideChainPath {
shared_block_number: *block_num,
new_block_number: block_num + side_chain_path.len() as u32,
path: side_chain_path,
}));
}
Err(_) => {
side_chain_path.insert(0, parent_hash.clone());
parent_hash = self.get_block_header(&parent_hash)?.previous_block_hash;
}
}
}
Err(StorageError::BlockError(BlockError::IrrelevantBlock(
block_hash.to_string(),
)))
}
pub fn longest_child_path(
&self,
block_hash: BlockHeaderHash,
) -> Result<(usize, Vec<BlockHeaderHash>), StorageError> {
let children = self.get_child_block_hashes(&block_hash)?;
let mut final_path = vec![block_hash];
if children.len() == 0 {
Ok((1, final_path))
} else {
let mut paths = vec![];
for child in children {
paths.push(self.longest_child_path(child)?);
}
match paths.iter().max_by_key(|x| x.0) {
Some((longest_child_path_length, longest_child_path)) => {
final_path.extend(longest_child_path.clone());
Ok((*longest_child_path_length + 1, final_path))
}
None => Ok((1, final_path)),
}
}
}
}