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
sourceimpl 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
sourceimpl Clone for RangeDecomposition
impl Clone for RangeDecomposition
sourcefn clone(&self) -> RangeDecomposition
fn clone(&self) -> RangeDecomposition
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
sourceimpl Debug for RangeDecomposition
impl Debug for RangeDecomposition
sourceimpl Display for RangeDecomposition
impl Display for RangeDecomposition
sourceimpl<G: Group> From<RangeDecomposition> for PreparedRange<G>
impl<G: Group> From<RangeDecomposition> for PreparedRange<G>
sourcefn from(decomposition: RangeDecomposition) -> Self
fn from(decomposition: RangeDecomposition) -> Self
Converts to this type from the input type.
sourceimpl PartialEq<RangeDecomposition> for RangeDecomposition
impl PartialEq<RangeDecomposition> for RangeDecomposition
sourcefn eq(&self, other: &RangeDecomposition) -> bool
fn eq(&self, other: &RangeDecomposition) -> bool
This method tests for self
and other
values to be equal, and is used
by ==
. Read more
sourcefn ne(&self, other: &RangeDecomposition) -> bool
fn ne(&self, other: &RangeDecomposition) -> bool
This method tests for !=
.
impl StructuralPartialEq for RangeDecomposition
Auto Trait Implementations
impl RefUnwindSafe for RangeDecomposition
impl Send for RangeDecomposition
impl Sync for RangeDecomposition
impl Unpin for RangeDecomposition
impl UnwindSafe for RangeDecomposition
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more