Struct RangeProof 

pub struct RangeProof<K, V, H> {
    start_proof: Proof<H>,
    end_proof: Proof<H>,
    key_values: Box<[(K, V)]>,
}

A range proof is a cryptographic proof that demonstrates a contiguous set of key-value pairs exists within a Merkle trie with a given root hash.

Range proofs are used to efficiently prove the presence (or absence) of multiple consecutive keys in a trie without revealing the entire trie structure. They consist of:

• A start proof: proves the existence of the first key in the range (or the nearest key before it)
• An end proof: proves the existence of the last key in the range (or the nearest key after it)
• The actual key-value pairs within the range

This allows verification that:

1. The provided key-value pairs are indeed part of the trie
2. There are no other keys between the start and end of the range
3. The trie has the claimed root hash

Range proofs are particularly useful in blockchain contexts for:

• State synchronization between nodes
• Light client verification
• Efficient auditing of specific key ranges

Fields

start_proof: Proof<H>

end_proof: Proof<H>

key_values: Box<[(K, V)]>

Implementations

impl RangeProof<Box<[u8]>, Box<[u8]>, Box<[ProofNode]>>

pub fn from_slice(data: &[u8]) -> Result<Self, ReadError>

Parses a FrozenRangeProof from the given byte slice.

Currently only V0 proofs are supported. See FrozenRangeProof::write_to_vec for the serialization format.

Errors

Returns a ReadError if the data is invalid. See the enum variants for the possible reasons.

impl<K, V, H> RangeProof<K, V, H>

where K: AsRef<[u8]>, V: AsRef<[u8]>, H: ProofCollection,

pub const fn new( start_proof: Proof<H>, end_proof: Proof<H>, key_values: Box<[(K, V)]>, ) -> Self

Create a new range proof with the given start and end proofs and the key-value pairs that are included in the proof.

Parameters

• start_proof - A Merkle proof for the first key in the range, or if the range starts before any existing key, a proof for the nearest key that comes after the start of the range. This proof establishes the lower boundary of the range and ensures no keys exist between the range start and the first included key. May be empty if proving from the very beginning of the trie.

• end_proof - A Merkle proof for the last key in the range, or if the range extends beyond all existing keys, a proof for the nearest key that comes before the end of the range. This proof establishes the upper boundary of the range and ensures no keys exist between the last included key and the range end. May be empty if proving to the very end of the trie.

• key_values - The actual key-value pairs that exist within the proven range. These are the consecutive entries from the trie that fall within the boundaries established by the start and end proofs. The keys should be in lexicographic order as they appear in the trie. May be empty if proving the absence of keys in a range.

pub const fn start_proof(&self) -> &Proof<H>

Returns a reference to the start proof, which may be empty.

pub const fn end_proof(&self) -> &Proof<H>

Returns a reference to the end proof, which may be empty.

pub const fn key_values(&self) -> &[(K, V)]

Returns the key-value pairs included in the range proof, which may be empty.

pub fn is_empty(&self) -> bool

Returns true if the range proof is empty, meaning it has no start or end proof and no key-value pairs.

pub fn iter(&self) -> RangeProofIter<'_, K, V>

Returns an iterator over the key-value pairs in this range proof.

The iterator yields references to the key-value pairs in the order they appear in the proof (which should be lexicographic order as they appear in the trie).

impl RangeProof<Box<[u8]>, Box<[u8]>, Box<[ProofNode]>>

pub fn write_to_vec(&self, out: &mut Vec<u8>)

Serializes this proof into the provided byte vector.

Format

The V0 serialization format for a range proof is:

• A 32-byte Header with the proof type set to ProofType::Range.
• The start proof, serialized as a sequence of ProofNodes
• The end proof, serialized as a sequence of ProofNodes
• The key-value pairs, serialized as a sequence of (key, value) tuples.

Each ProofNode is serialized as:

• The key, serialized as a sequence of bytes where each byte is a nibble of the appropriate branching factor. E.g., if the trie has a branching factor of 16, each byte is only the lower 4 bits of the byte and the upper 4 bits are all zero.
• A variable-length integer indicating the length of the parent’s key of the key. I.e., key[partial_len..] is the partial path of this node.
• The value digest:
  • If there is no value for the node, a single byte with the value 0.
  • If there is a value for the node, a single byte with the value 1 followed by:
    • If the value digest is of a full value, a single byte with the value 0 followed by the value serialized as a sequence of bytes.
    • If the value digest is of a hash, a single byte with the value 1 followed by the hash serialized as exactly 32 bytes.
    • See [ValueDigest::make_hash] as to when a value digest is a hash.
• The children bitmap, which is a fixed-size bit field where each bit indicates whether the corresponding child is present. The size of the bitmap is branching_factor / 8 bytes. E.g., if the branching factor is 16, the bitmap is 2 bytes (16 bits) and if the branching factor is 256, the bitmap is 32 bytes (256 bits). All zero bits indicate that the node is a leaf node and no children follow.
• For each child that is present, as indicated by the bitmap, the child’s node ID is serialized.
  • If the trie is using MerkleDB hashing, the ID is a fixed 32-byte sha256 hash.
  • If the trie is using Ethereum hashing, the ID is serialized as:
    • A single byte with the value 0 if the ID is a keccak256 hash; followed by the fixed 32-byte hash.
    • A single byte with the value 1 if the ID is an RLP encoded node; followed by the RLP encoded bytes serialized as a sequence of bytes. This occurs when the hash input (RLP encoded node) is smaller than 32 bytes; in which case, the hash result is the input value unhashed.

Each sequence mentioned above is prefixed with a variable-length integer indicating the number of items in the sequence.

Variable-length integers are encoded using unsigned LEB128.

Trait Implementations

impl<K: Debug, V: Debug, H: Debug> Debug for RangeProof<K, V, H>

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

Formats the value using the given formatter.

impl<'a, K, V, H> IntoIterator for &'a RangeProof<K, V, H>

where K: AsRef<[u8]>, V: AsRef<[u8]>, H: ProofCollection,

type Item = &'a (K, V)

The type of the elements being iterated over.

type IntoIter = RangeProofIter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: PartialEq, V: PartialEq, H: PartialEq> PartialEq for RangeProof<K, V, H>

fn eq(&self, other: &RangeProof<K, V, H>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<K, V, H> StructuralPartialEq for RangeProof<K, V, H>