in src/proof.rs [517:616]
fn random_sampling(tree: &Self::TreeStruct, idx: &TreeIndex, secret: &Secret) -> Self {
// Fetch the lowest ancestor of the sampled index in the tree.
let (ancestor, ancestor_idx) = tree.get_closest_ancestor_ref_index(idx);
// If the sampled index is a real leaf node in the tree,
// return a padding node proof containing no padding node, and the Merkle proof of that node.
if ancestor_idx.get_height() == tree.get_height()
&& *tree.get_node_by_ref(ancestor).get_node_type() == NodeType::Leaf
{
// Get the references to the input leaf and siblings of nodes long the Merkle path from the root to the leaves.
let refs = tree.get_merkle_path_ref(idx).unwrap();
// Construct the Merkle proof given the references to all sibling nodes in the proof.
let mut proof = MerkleProof::<V>::new(*idx);
proof.set_siblings(tree.get_node_proof_by_refs(&refs[1..]));
return RandomSamplingProof::new(
*idx,
Vec::new(),
proof,
tree.get_node_proof_by_refs(&refs[0..1]),
);
}
let mut list: Vec<TreeIndex> = Vec::new();
// Fetch the index of the closest node on the left.
let res = tree.get_closest_index_by_dir(ancestor, ancestor_idx, ChildDir::Left);
if let Some(x) = res {
list.push(x);
}
// Fetch the index of the closest node on the right.
let res = tree.get_closest_index_by_dir(ancestor, ancestor_idx, ChildDir::Right);
if let Some(x) = res {
list.push(x);
}
let mut padding_proofs: Vec<V::PaddingProof> = Vec::new();
// Generate the Merkle proof of closest nodes.
let mut merkle_proof: MerkleProof<V> = MerkleProof::new_batch(&list);
let mut leaves = Vec::<V::ProofNode>::new();
// Add proofs of necessary padding nodes in the proof.
match list.len() {
0 => {
// When the tree is empty, prove that the root is a padding node.
padding_proofs.push(
tree.get_node_by_ref(tree.get_root_ref())
.get_value()
.prove_padding_node(&TreeIndex::zero(0), secret),
);
}
1 => {
// When there is only a left/right neighbour.
// Get the references to the input leaf and siblings of nodes long the Merkle path from the root to the leaves.
let refs = tree.get_merkle_path_ref(&list[0]).unwrap();
// Construct the Merkle proof given the references to all sibling nodes in the proof.
merkle_proof.set_siblings(tree.get_node_proof_by_refs(&refs[1..]));
leaves = tree.get_node_proof_by_refs(&refs[0..1]);
let padding_refs;
// Fetch the reference (offset to the end of the sibling list) to the necessary padding nodes by neighbour direction.
if list[0] < *idx {
padding_refs = SparseMerkleTree::<V>::get_padding_proof_by_dir_index_ref_pairs(
&list[0],
ChildDir::Left,
);
} else {
padding_refs = SparseMerkleTree::<V>::get_padding_proof_by_dir_index_ref_pairs(
&list[0],
ChildDir::Right,
);
}
// Add the proofs of the necessary padding nodes.
<RandomSamplingProof<V>>::add_padding_proofs(
tree,
&mut padding_proofs,
refs,
padding_refs,
secret,
)
}
_ => {
// When neighbours on both sides exist.
// Get the references to the input leaves and siblings of nodes long the batched Merkle paths from the root to the leaves.
let refs = tree.get_merkle_path_ref_batch(&list).unwrap();
// Construct the Merkle proof given the references to all sibling nodes in the proof.
merkle_proof.set_siblings(tree.get_node_proof_by_refs(&refs[2..]));
leaves = tree.get_node_proof_by_refs(&refs[0..2]);
// Fetch the reference (offset to the end of the sibling list) to the necessary padding nodes.
let padding_refs = SparseMerkleTree::<V>::get_padding_proof_batch_index_ref_pairs(
&list[0], &list[1],
);
// Add the proofs of the necessary padding nodes.
<RandomSamplingProof<V>>::add_padding_proofs(
tree,
&mut padding_proofs,
refs,
padding_refs,
secret,
)
}
}
RandomSamplingProof::new(*idx, padding_proofs, merkle_proof, leaves)
}