# Struct elastic_elgamal::RangeDecomposition

source · `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 `RangeProof`

s with size / computational complexity `O(log n)`

.

## §Construction

To build efficient `RangeProof`

s, 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
`n`

s, 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`RingProof`

s, 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

### impl RangeDecomposition

source#### pub fn optimal(upper_bound: u64) -> Self

#### 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

#### 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

#### pub fn proof_size(&self) -> u64

Returns the size of `RangeProof`

s 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

### impl Clone for RangeDecomposition

source§#### fn clone(&self) -> RangeDecomposition

#### fn clone(&self) -> RangeDecomposition

1.0.0 · source§#### fn clone_from(&mut self, source: &Self)

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

`source`

. Read moresource§### impl Debug for RangeDecomposition

### impl Debug for RangeDecomposition

source§### impl Display for RangeDecomposition

### impl Display for RangeDecomposition

source§### impl<G: Group> From<RangeDecomposition> for PreparedRange<G>

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

source§#### fn from(decomposition: RangeDecomposition) -> Self

#### fn from(decomposition: RangeDecomposition) -> Self

source§### impl PartialEq for RangeDecomposition

### impl PartialEq for RangeDecomposition

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

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

`self`

and `other`

values to be equal, and is used
by `==`

.