#![deny(missing_debug_implementations)]
#![deny(missing_docs)]
#![deny(unused_results)]
#![deny(dead_code)]
#![doc(html_root_url = "https://docs.rs/minisketch_rs/0.1.9")]
//! # minisketch-rs
//!
//! `minisketch-rs` is a wrapper around [minisketch],
//! a C++ library by [Pieter Wuille] for efficient set reconciliation.
//!
//! Minisketch is proposed as part of an [Erlay] technique for bandwidth-efficient TX propagation in Bitcoin.
//!
//! This library exposes type-safe Rust bindings for all minisketch functions by providing [`Minisketch`] structure.
//!
//! # Examples
//!
//! See the [examples] module.
//!
//! [examples]: examples/index.html
//! [minisketch]: https://github.com/sipa/minisketch
//! [`Minisketch`]: struct.Minisketch.html
//! [Pieter Wuille]: https://github.com/sipa
//! [Erlay]: https://arxiv.org/abs/1905.10518
pub mod examples;
use std::error::Error;
use std::fmt::{Debug, Display, Formatter};
use std::ops::BitXorAssign;
/// Error that originates from `libminisketch`, with a message.
#[derive(Debug)]
pub struct MinisketchError(String);
impl MinisketchError {
/// Creates an error with a message.
pub fn new(msg: &str) -> Self {
MinisketchError(msg.to_owned())
}
}
impl Error for MinisketchError {}
impl Display for MinisketchError {
fn fmt(&self, f: &mut Formatter) -> Result<(), std::fmt::Error> {
write!(f, "MinisketchError({})", self.0)
}
}
#[doc(hidden)]
mod ffi {
#![allow(non_upper_case_globals)]
#![allow(non_camel_case_types)]
#![allow(non_snake_case)]
include!(concat!(env!("OUT_DIR"), "/bindings.rs"));
unsafe impl Send for minisketch {}
}
/// Describes decoded sketches and holding underlying opaque type inside.
pub struct Minisketch {
inner: *mut ffi::minisketch,
bits: u32,
implementation: u32,
capacity: usize,
}
impl Minisketch {
/// Tries to create a new empty sketch.
///
/// # Errors
///
/// If the combination of `bits` and `implementation` is unavailable, or if
/// `capacity` is 0, an `Err(MinisketchError)` is returned.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let sketch = Minisketch::try_new(12, 0, 4)?;
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn try_new(
bits: u32,
implementation: u32,
capacity: usize,
) -> Result<Self, MinisketchError> {
let inner = unsafe { ffi::minisketch_create(bits, implementation, capacity) };
if !inner.is_null() {
Ok(Minisketch {
inner,
bits,
implementation,
capacity,
})
} else {
Err(MinisketchError::new("Unsupported minisketch parameters"))
}
}
/// Determine whether support for elements of size of `bits` bits was compiled in.
pub fn bits_supported(bits: u32) -> bool {
let res = unsafe { ffi::minisketch_bits_supported(bits) };
res != 0
}
/// Determine the maximum number of implementations available.
///
/// Multiple implementations may be available for a given element size, with
/// different performance characteristics on different hardware.
///
/// Each implementation is identified by a number from 0 to the output of this
/// function call, inclusive. Note that not every combination of implementation
/// and element size may exist.
pub fn implementation_max() -> u32 {
unsafe { ffi::minisketch_implementation_max() }
}
/// Returns element size in a sketch in bits.
pub fn bits(&self) -> u32 {
unsafe { ffi::minisketch_bits(self.inner) }
}
/// Returns capacity of a sketch in number of elements.
pub fn capacity(&self) -> usize {
unsafe { ffi::minisketch_capacity(self.inner) }
}
/// Returns implementation version number.
pub fn implementation(&self) -> u32 {
unsafe { ffi::minisketch_implementation(self.inner) }
}
/// Returns the size in bytes for serializing a given sketch.
pub fn serialized_size(&self) -> usize {
unsafe { ffi::minisketch_serialized_size(self.inner) }
}
/// Adds a `u64` element to a sketch.
///
/// If the element to be added is too large for the sketch, the most significant
/// bits of the element are dropped. More precisely, if the element size of
/// `sketch` is b bits, then this function adds the unsigned integer represented
/// by the b least significant bits of `element` to `sketch`.
///
/// If the element to be added is 0 (after potentially dropping the most significant
/// bits), then this function is a no-op. Sketches cannot contain an element with
/// the value 0.
///
/// Note that adding the same element a second time removes it again, as sketches have
/// set semantics, not multiset semantics.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let mut sketch = Minisketch::try_new(12, 0, 4)?;
/// sketch.add(42);
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn add(&mut self, element: u64) {
unsafe { ffi::minisketch_add_uint64(self.inner, element) }
}
/// Set the seed for randomizing algorithm choices to a fixed value.
///
/// By default, sketches are initialized with a random seed. This is important
/// to avoid scenarios where an attacker could force worst-case behavior.
///
/// This function initializes the seed to a user-provided value (any 64-bit
/// integer is acceptable, regardless of field size).
///
/// When seed is `std::u64::MAX`, a fixed internal value with predictable behavior is used.
/// It is only intended for testing.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let mut sketch = Minisketch::try_new(12, 0, 4)?;
/// sketch.set_seed(42);
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn set_seed(&mut self, seed: u64) {
unsafe { ffi::minisketch_set_seed(self.inner, seed) }
}
/// Merge the elements of another sketch into this sketch.
///
/// After merging, `sketch` will contain every element that existed in one but not
/// both of the input sketches. It can be seen as an exclusive or operation on
/// the set elements. If the capacity of `other_sketch` is lower than `sketch`'s,
/// merging reduces the capacity of `sketch` to that of `other_sketch`.
///
/// Returns the `Ok(capacity)` of `sketch` after merging has been performed (where this capacity
/// is at least 1)
///
/// It is also possible to perform this operation directly on the serializations
/// of two sketches with the same element size and capacity by performing a bitwise XOR
/// of the serializations.
///
/// You can also merge two sketches by doing xor-assignment (`^=`).
///
/// # Errors
///
/// Returns `Err(MinisketchError)` to indicate that merging has failed
/// because the two input sketches differ in their element size or implementation. If `Err` is
/// returned, `sketch` (and its capacity) have not been modified.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let mut sketch_a = Minisketch::try_new(12, 0, 4)?;
/// sketch_a.add(10);
/// sketch_a.add(43);
///
/// let mut sketch_b = Minisketch::try_new(12, 0, 4)?;
/// sketch_b.add(42);
/// sketch_b.add(43);
///
/// // Merge two sketches and extract a difference
/// let num_diffs = sketch_a.merge(&sketch_b)?;
///
/// // Extract difference
/// let mut differences = vec![0u64; num_diffs];
/// sketch_a.decode(&mut differences)?;
///
/// assert!((differences[0] == 42 || differences[0] == 10) && (differences[1] == 10 || differences[1] == 42));
///
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn merge(&mut self, other: &Self) -> Result<usize, MinisketchError> {
let capacity = unsafe { ffi::minisketch_merge(self.inner, other.inner) };
if capacity == 0 {
Err(MinisketchError::new("Merge is failed"))
} else {
Ok(capacity)
}
}
/// Decode a sketch.
///
/// `elements` is a mutable reference to a buffer of `u64`, which will be filled with the
/// elements in this sketch.
///
/// Returns `Ok(num. of decoded elements)`
///
/// # Errors
///
/// Returns `Err(MinisketchError)` if decoding failed for any reason.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let mut sketch = Minisketch::try_new(12, 0, 2)?;
/// sketch.add(42);
/// sketch.add(10);
/// let mut elements = [0u64; 2];
/// sketch.decode(&mut elements)?;
///
/// // Elements may come in arbitrary order, so check all possible variants
/// assert!((elements[0] == 42 || elements[0] == 10) && (elements[1] == 10 || elements[1] == 42));
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn decode(&self, elements: &mut [u64]) -> Result<usize, MinisketchError> {
let result =
unsafe { ffi::minisketch_decode(self.inner, elements.len(), elements.as_mut_ptr()) };
if result == -1 {
Err(MinisketchError::new("Sketch decoding failed"))
} else {
Ok(result as usize)
}
}
/// Deserialize a sketch from bytes.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
///
/// // Create Alice's sketch
/// let mut sketch_alice = Minisketch::try_new(12, 0, 2)?;
/// sketch_alice.add(42);
/// sketch_alice.add(10);
///
/// // Serialize sketch on Alice's side
/// let mut message = vec![0u8; sketch_alice.serialized_size()];
/// sketch_alice.serialize(&mut message);
///
/// // ... message is sent from Alice to Bob ...
///
/// // Deserialize sketch from Alice on Bob's side
/// let mut sketch_bob = Minisketch::try_new(12, 0, 2)?;
/// sketch_bob.deserialize(&message);
///
/// // Decode received sketch
/// let mut elements = [0u64; 2];
/// sketch_bob.decode(&mut elements)?;
/// // Elements may come in arbitrary order, so check all possible variants
/// assert!((elements[0] == 42 || elements[0] == 10) && (elements[1] == 10 || elements[1] == 42));
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn deserialize(&mut self, buf: &[u8]) {
unsafe { ffi::minisketch_deserialize(self.inner, buf.as_ptr()) }
}
/// Serialize a sketch to bytes.
///
/// # Errors
///
/// Returns `Err(MinisketchError)` if `.len()` of the provided buffer `buf` is less than a size in bytes of
/// the serialized representation of the sketch.
///
/// # Examples
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let mut sketch = Minisketch::try_new(12, 0, 2)?;
/// sketch.add(42);
/// sketch.add(10);
///
/// let mut buf = vec![0u8; sketch.serialized_size()];
/// sketch.serialize(&mut buf);
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
pub fn serialize(&self, buf: &mut [u8]) -> Result<(), MinisketchError> {
let size = self.serialized_size();
if size < buf.len() {
return Err(MinisketchError::new("Invalid size of the output buffer"));
}
unsafe { ffi::minisketch_serialize(self.inner, buf.as_mut_ptr()) }
Ok(())
}
}
/// Custom `Debug` implementation that shows basic information about opaque `minisketch`.
impl Debug for Minisketch {
fn fmt(&self, f: &mut Formatter) -> Result<(), std::fmt::Error> {
write!(
f,
"Minisketch {{ bits = {}, implementation = {}, capacity = {} }}",
self.bits(),
self.implementation(),
self.capacity(),
)
}
}
/// Custom `Drop` implementation that frees an underlying opaque sketch.
#[doc(hidden)]
impl Drop for Minisketch {
fn drop(&mut self) {
unsafe {
ffi::minisketch_destroy(self.inner);
}
}
}
/// Custom `Clone` implementation that clones an underlying opaque sketch.
#[doc(hidden)]
impl Clone for Minisketch {
fn clone(&self) -> Self {
let inner = unsafe { ffi::minisketch_clone(self.inner) };
Minisketch {
inner,
bits: self.bits,
implementation: self.implementation,
capacity: self.capacity,
}
}
}
/// Custom `^=` operator implementation on two sketches that performs merging.
///
/// # Example
///
/// ```rust
/// use minisketch_rs::Minisketch;
/// let mut sketch_a = Minisketch::try_new(12, 0, 4)?;
/// sketch_a.add(10);
/// sketch_a.add(43);
///
/// let mut sketch_b = Minisketch::try_new(12, 0, 4)?;
/// sketch_b.add(42);
/// sketch_b.add(43);
///
/// // Merge two sketches with ^= operator
/// sketch_a ^= sketch_b;
///
/// // Extract difference
/// let mut differences = vec![0u64; 2];
/// sketch_a.decode(&mut differences)?;
///
/// assert!((differences[0] == 42 || differences[0] == 10) && (differences[1] == 10 || differences[1] == 42));
///
/// # Ok::<(), minisketch_rs::MinisketchError>(())
/// ```
impl BitXorAssign for Minisketch {
fn bitxor_assign(&mut self, rhs: Minisketch) {
let _ = self.merge(&rhs);
}
}
#[cfg(test)]
mod tests {
use crate::*;
fn validate_elements(elements: &[u64]) {
// Sort differences since they're come in arbitrary order from minisketch_decode()
let mut differences = Vec::from(elements);
differences.sort();
assert_eq!(differences[0], 3_000);
assert_eq!(differences[1], 3_001);
assert_eq!(differences[2], 3_010);
assert_eq!(differences[3], 3_011);
}
#[test]
// Implement an example from minisketch's README
pub fn test_sanity_check() {
use ffi::*;
unsafe {
// Alice's side
let sketch_a = minisketch_create(12, 0, 4);
for i in 3_000..3_010 {
minisketch_add_uint64(sketch_a, i as u64);
}
let sersize = minisketch_serialized_size(sketch_a);
assert_eq!(sersize, 12 * 4 / 8);
let mut buf_a = vec![0u8; sersize];
minisketch_serialize(sketch_a, buf_a.as_mut_slice().as_mut_ptr());
minisketch_destroy(sketch_a);
let sketch_b = minisketch_create(12, 0, 4);
for i in 3_002..3_012 {
minisketch_add_uint64(sketch_b, i as u64);
}
// Bob's side
{
let sketch_a = minisketch_create(12, 0, 4); // Alice's sketch
minisketch_deserialize(sketch_a, buf_a.as_ptr()); // Load Alice's sketch
// Merge the elements from sketch_a into sketch_b. The result is a sketch_b
// which contains all elements that occurred in Alice's or Bob's sets, but not
// in both.
let _ = minisketch_merge(sketch_b, sketch_a);
let mut differences = [0u64; 4];
let num_differences = minisketch_decode(sketch_b, 4, differences.as_mut_ptr());
minisketch_destroy(sketch_a);
minisketch_destroy(sketch_b);
assert!(num_differences > 0);
validate_elements(&differences[..]);
}
};
}
#[test]
// Implement a README's example with Rust API as a sanity check
pub fn sanity_check_rust_types() {
let mut sketch_a = Minisketch::try_new(12, 0, 4).unwrap();
assert_eq!(sketch_a.bits(), 12);
assert_eq!(sketch_a.implementation(), 0);
assert_eq!(sketch_a.capacity(), 4);
for i in 3_000..3_010 {
sketch_a.add(i);
}
let sersize = sketch_a.serialized_size();
assert_eq!(sersize, 12 * 4 / 8);
let mut buf_a = vec![0u8; sersize];
sketch_a.serialize(buf_a.as_mut_slice()).unwrap();
let mut sketch_b = Minisketch::try_new(12, 0, 4).unwrap();
for i in 3_002..3_012 {
sketch_b.add(i);
}
// Bob's side (with .merge() method)
{
let mut sketch_b = sketch_b.clone();
// Alice's sketch
let mut sketch_a = Minisketch::try_new(12, 0, 4).unwrap();
sketch_a.deserialize(&buf_a); // Load Alice's sketch
// Merge the elements from sketch_a into sketch_b. The result is a sketch_b
// which contains all elements that occurred in Alice's or Bob's sets, but not
// in both.
let _ = sketch_b.merge(&sketch_a).unwrap();
let mut differences = [0u64; 4];
let num_differences = sketch_b.decode(&mut differences[..]).unwrap();
assert!(num_differences > 0);
validate_elements(&differences[..]);
}
// Bob's side (with ^= instead of .merge())
{
let mut sketch_b = sketch_b.clone();
// Alice's sketch
let mut sketch_a = Minisketch::try_new(12, 0, 4).unwrap();
sketch_a.deserialize(&buf_a); // Load Alice's sketch
// Merge the elements from sketch_a into sketch_b. The result is a sketch_b
// which contains all elements that occurred in Alice's or Bob's sets, but not
// in both.
sketch_b ^= sketch_a;
let mut differences = [0u64; 4];
let num_differences = sketch_b.decode(&mut differences[..]).unwrap();
assert!(num_differences > 0);
validate_elements(&differences[..]);
}
}
}