Struct rustreexo::accumulator::proof::Proof

pub struct Proof {
    pub targets: Vec<u64>,
    pub hashes: Vec<NodeHash>,
}

A proof is a collection of hashes and positions. Each target position points to a leaf to be proven. Hashes are all hashes that can’t be calculated from the data itself. Proofs are generated elsewhere.

Fields

targets: Vec<u64>

Targets are the i’th of leaf locations to delete and they are the bottommost leaves. With the tree below, the Targets can only consist of one of these: 02, 03, 04.

  // 06
  // |-------\
  // 04      05
  // |---\   |---\
  //         02  03

hashes: Vec<NodeHash>

All the nodes in the tree that are needed to hash up to the root of the tree. Here, the root is 06. If Targets are [00, 01], then Proof would be [05] as you need 04 and 05 to hash to 06. 04 can be calculated by hashing 00 and 01.

 // 06
 // |-------\
 // 04      05
 // |---\   |---\
 // 00  01  02  03

Implementations

impl Proof

pub fn new(targets: Vec<u64>, hashes: Vec<NodeHash>) -> Self

Creates a proof from a vector of target and hashes. targets are u64s and indicates the position of the leaves we are trying to prove. hashes are of type NodeHash and are all hashes we need for computing the roots.

Assuming a tree with leaf values [0, 1, 2, 3, 4, 5, 6, 7], we should see something like this:

 // 14
 // |-----------------\
 // 12                13
 // |---------\       |--------\
 // 08       09       10       11
 // |----\   |----\   |----\   |----\
 // 00   01  02   03  04   05  06   07

If we are proving 00 (i.e. 00 is our target), then we need 01, 09 and 13’s hashes, so we can compute 14 by hashing both siblings in each level (00 and 01, 08 and 09 and 12 and 13). Note that some hashes we can compute by ourselves, and are not present in the proof, in this case 00, 08, 12 and 14.

Example

use bitcoin_hashes::Hash;
use bitcoin_hashes::HashEngine;
use rustreexo::accumulator::node_hash::NodeHash;
use rustreexo::accumulator::proof::Proof;
let targets = vec![0];

let mut proof_hashes = Vec::new();
let targets = vec![0];
// For proving 0, we need 01, 09 and 13's hashes. 00, 08, 12 and 14 can be calculated
// Fill `proof_hashes` up with all hashes
Proof::new(targets, proof_hashes);

pub fn verify( &self, del_hashes: &[NodeHash], roots: &[NodeHash], num_leaves: u64 ) -> Result<bool, String>

Public interface for verifying proofs. Returns a result with a bool or an Error True means the proof is true given the current stump, false means the proof is not valid given the current stump.

Examples

use std::str::FromStr;

use bitcoin_hashes::sha256;
use bitcoin_hashes::Hash;
use bitcoin_hashes::HashEngine;
use rustreexo::accumulator::node_hash::NodeHash;
use rustreexo::accumulator::proof::Proof;
use rustreexo::accumulator::stump::Stump;
let s = Stump::new();
// Creates a tree with those values as leaves
let test_values: Vec<u8> = vec![0, 1, 2, 3, 4, 5, 6, 7];
// Targets are the nodes we intend to prove
let targets = vec![0];

let mut proof_hashes = Vec::new();
// This tree will look like this
// 14
// |-----------------\
// 12                13
// |---------\       |--------\
// 08       09       10       11
// |----\   |----\   |----\   |----\
// 00   01  02   03  04   05  06   07
// For proving 0, we need 01, 09 and 13's hashes. 00, 08, 12 and 14 can be calculated
proof_hashes.push(
    NodeHash::from_str("4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a")
        .unwrap(),
);
proof_hashes.push(
    NodeHash::from_str("9576f4ade6e9bc3a6458b506ce3e4e890df29cb14cb5d3d887672aef55647a2b")
        .unwrap(),
);
proof_hashes.push(
    NodeHash::from_str("29590a14c1b09384b94a2c0e94bf821ca75b62eacebc47893397ca88e3bbcbd7")
        .unwrap(),
);

let mut hashes = Vec::new();
for i in test_values {
    let mut engine = sha256::Hash::engine();
    engine.input(&[i]);
    hashes.push(sha256::Hash::from_engine(engine).into())
}
let s = s.modify(&hashes, &vec![], &Proof::default()).unwrap().0;
let p = Proof::new(targets, proof_hashes);
assert!(s.verify(&p, &[hashes[0]]).expect("This proof is valid"));

pub fn get_proof_subset( &self, del_hashes: &[NodeHash], new_targets: &[u64], num_leaves: u64 ) -> Result<Proof, String>

Returns the elements needed to prove a subset of targets. For example, a tree with 8 leaves, if we cache [0, 2, 6, 7], and we need to prove [2, 7] only, we have to remove elements for 0 and 7. The original proof is [1, 3, 10], and we can compute [8, 9, 11, 12, 13, 14]. But for [2, 7] we need [3, 6, 8, 10], and compute [9, 11, 12, 13, 14]

 // 14
 // |---------------\
 // 12              13
 // |------\        |-------\
 // 8       9       10      11
 // |---\   |---\   |---\   |---\
 // 0   1   2   3   4   5   6   7

pub fn serialize<W: Write>(&self, writer: W) -> Result<usize>

Serializes the proof into a byte array. The format is (all integers are little endian):

• number of targets (u64)
• targets (u64)
• number of hashes (u64)
• hashes (32 bytes)

Example

use rustreexo::accumulator::node_hash::NodeHash;
use rustreexo::accumulator::proof::Proof;
use rustreexo::accumulator::stump::Stump;

let proof = Proof::default();
let mut serialized_proof = vec![];
proof.serialize(&mut serialized_proof).unwrap();
// An empty proof is only 16 bytes of zeros, meaning no targets and no hashes
assert_eq!(
    vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    serialized_proof
);

pub fn deserialize<Source: Read>(buf: Source) -> Result<Self, String>

Deserializes a proof from a byte array.

Example

use std::io::Cursor;

use rustreexo::accumulator::node_hash::NodeHash;
use rustreexo::accumulator::proof::Proof;
use rustreexo::accumulator::stump::Stump;
let proof = Cursor::new(vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
let deserialized_proof = Proof::deserialize(proof).unwrap();
// An empty proof is only 16 bytes of zeros, meaning no targets and no hashes
assert_eq!(Proof::default(), deserialized_proof);

pub fn targets(&self) -> usize

Returns how many targets this proof has

pub fn update( self, cached_hashes: Vec<NodeHash>, add_hashes: Vec<NodeHash>, block_targets: Vec<u64>, remembers: Vec<u64>, update_data: UpdateData ) -> Result<(Proof, Vec<NodeHash>), String>

Uses the data passed in to update a proof, creating a valid proof for a given set of targets, after an update. This is useful for caching UTXOs. You grab a proof for it once and then keep updating it every block, yielding an always valid proof over those UTXOs.

Trait Implementations

impl Clone for Proof

fn clone(&self) -> Proof

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Proof

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Proof

fn default() -> Proof

Returns the “default value” for a type.

impl PartialEq<Proof> for Proof

fn eq(&self, other: &Proof) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for Proof

impl StructuralEq for Proof

impl StructuralPartialEq for Proof