pub struct RangeDecomposition { /* private fields */ }
Expand description

Decomposition of an integer range 0..n into one or more sub-ranges. Decomposing the range allows constructing RangeProofs with size / computational complexity O(log n).

§Construction

To build efficient RangeProofs, we need to be able to decompose any value x in 0..n into several components, with each of them being in a smaller predefined range; once we have such a decomposition, we can build a RingProof around it. To build a decomposition, we use the following generic construction:

0..n = 0..t_0 + k_0 * (0..t_1 + k_1 * (0..t_2 + …)),

where t_i and k_i are integers greater than 1. If x is a value in 0..n, it is decomposed as

x = x_0 + k_0 * x_1 + k_0 * k_1 * x_2 + …; x_i in 0..t_i.

For a decomposition to be valid (i.e., to represent any value in 0..n and no other values), the following statements are sufficient:

  • t_i >= k_i (no gaps in values)
  • n = t_0 + k_0 * (t_1 - 1 + k_1 * …) (exact upper bound).

The size of a RingProof is the sum of upper range bounds t_i (= number of responses) + 1 (the common challenge). Additionally, we need a ciphertext per each sub-range 0..t_i (i.e., for each ring in RingProof). In practice, proof size is logarithmic:

Upper bound nOptimal decompositionProof size
50..56 scalars
100..5 * 2 + 0..28 scalars, 2 elements
200..5 * 4 + 0..410 scalars, 2 elements
50(0..5 * 5 + 0..5) * 2 + 0..213 scalars, 4 elements
64(0..4 * 4 + 0..4) * 4 + 0..413 scalars, 4 elements
100(0..5 * 5 + 0..5) * 4 + 0..415 scalars, 4 elements
256((0..4 * 4 + 0..4) * 4 + 0..4) * 4 + 0..417 scalars, 6 elements
1000((0..8 * 5 + 0..5) * 5 + 0..5) * 5 + 0..524 scalars, 6 elements

(We do not count one of sub-range ciphertexts since it can be restored from the other sub-range ciphertexts and the original ciphertext of the value.)

§Notes

  • Decomposition of some values may be non-unique, but this is fine for our purposes.
  • Encoding of a value in a certain base is a partial case, with all t_i and k_i equal to the base. It only works for n being a power of the base.
  • Other types of decompositions may perform better, but this one has a couple of nice properties. It works for all ns, and the optimal decomposition can be found recursively.
  • If we know how to create / verify range proofs for 0..N, proofs for all ranges 0..n, n < N can be constructed as a combination of 2 proofs: a proof that encrypted value x is in 0..N and that n - 1 - x is in 0..N. (The latter is proved for a ciphertext obtained by the matching linear transform of the original ciphertext of x.) This does not help us if proofs for 0..N are constructed using RingProofs, but allows estimating for which n a Bulletproofs-like construction would become more efficient despite using 2 proofs. If we take N = 2^(2^P) and the “vanilla” Bulletproof length 2 * P + 9, this threshold is around n = 2000.

§Examples

Finding out the optimal decomposition for a certain range:

let range = RangeDecomposition::optimal(42);
assert_eq!(range.to_string(), "6 * 0..7 + 0..6");
assert_eq!(range.proof_size(), 16); // 14 scalars, 2 elements

let range = RangeDecomposition::optimal(100);
assert_eq!(range.to_string(), "20 * 0..5 + 4 * 0..5 + 0..4");
assert_eq!(range.proof_size(), 19); // 15 scalars, 4 elements

See RangeProof docs for an end-to-end example of usage.

Implementations§

source§

impl RangeDecomposition

source

pub fn optimal(upper_bound: u64) -> Self

Finds an optimal decomposition of the range with the given upper_bound in terms of space of the range proof.

Empirically, this method has sublinear complexity, but may work slowly for large values of upper_bound (say, larger than 1 billion).

§Panics

Panics if upper_bound is less than 2.

source

pub fn upper_bound(&self) -> u64

Returns the exclusive upper bound of the range presentable by this decomposition.

source

pub fn proof_size(&self) -> u64

Returns the size of RangeProofs using this decomposition, measured as a total number of scalars and group elements in the proof. Computational complexity of creating and verifying proofs is also linear w.r.t. this number.

Trait Implementations§

source§

impl Clone for RangeDecomposition

source§

fn clone(&self) -> RangeDecomposition

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl Debug for RangeDecomposition

source§

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

Formats the value using the given formatter. Read more
source§

impl Display for RangeDecomposition

source§

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

Formats the value using the given formatter. Read more
source§

impl<G: Group> From<RangeDecomposition> for PreparedRange<G>

source§

fn from(decomposition: RangeDecomposition) -> Self

Converts to this type from the input type.
source§

impl PartialEq for RangeDecomposition

source§

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

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

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.
source§

impl StructuralPartialEq for RangeDecomposition

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T> ToString for T
where T: Display + ?Sized,

source§

default fn to_string(&self) -> String

Converts the given value to a String. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V