Struct RangeDecomposition

pub struct RangeDecomposition { /* private fields */ }

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 n	Optimal decomposition	Proof size
5	0..5	6 scalars
10	0..5 * 2 + 0..2	8 scalars, 2 elements
20	0..5 * 4 + 0..4	10 scalars, 2 elements
50	(0..5 * 5 + 0..5) * 2 + 0..2	13 scalars, 4 elements
64	(0..4 * 4 + 0..4) * 4 + 0..4	13 scalars, 4 elements
100	(0..5 * 5 + 0..5) * 4 + 0..4	15 scalars, 4 elements
256	((0..4 * 4 + 0..4) * 4 + 0..4) * 4 + 0..4	17 scalars, 6 elements
1000	((0..8 * 5 + 0..5) * 5 + 0..5) * 5 + 0..5	24 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

impl RangeDecomposition

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.

pub fn upper_bound(&self) -> u64

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

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

impl Clone for RangeDecomposition

fn clone(&self) -> RangeDecomposition

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for RangeDecomposition

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

Formats the value using the given formatter.

impl Display for RangeDecomposition

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

Formats the value using the given formatter.

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

fn from(decomposition: RangeDecomposition) -> Self

Converts to this type from the input type.

impl PartialEq for RangeDecomposition

fn eq(&self, other: &RangeDecomposition) -> 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 StructuralPartialEq for RangeDecomposition