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
andk_i
equal to the base. It only works forn
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 ranges0..n
,n < N
can be constructed as a combination of 2 proofs: a proof that encrypted valuex
is in0..N
and thatn - 1 - x
is in0..N
. (The latter is proved for a ciphertext obtained by the matching linear transform of the original ciphertext ofx
.) This does not help us if proofs for0..N
are constructed usingRingProof
s, but allows estimating for whichn
a Bulletproofs-like construction would become more efficient despite using 2 proofs. If we takeN = 2^(2^P)
and the “vanilla” Bulletproof length2 * P + 9
, this threshold is aroundn = 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
sourcepub 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.
sourcepub fn upper_bound(&self) -> u64
pub fn upper_bound(&self) -> u64
Returns the exclusive upper bound of the range presentable by this decomposition.
sourcepub 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 ==
.