# Struct elastic_elgamal::RangeProof

source · `pub struct RangeProof<G: Group> { /* private fields */ }`

## Expand description

Zero-knowledge proof that an ElGamal ciphertext encrypts a value into a certain range `0..n`

.

## §Construction

To make the proof more compact – `O(log n)`

in terms of size and proving / verification
complexity – we use the same trick as for Pedersen commitments (used, e.g., for confidential
transaction amounts in Elements):

- Represent the encrypted value
`x`

as`x = x_0 + k_0 * x_1 + k_0 * k_1 * x_2 + …`

, where`0 <= x_i < t_i`

is the decomposition of`x`

as per the`RangeDecomposition`

,`0..t_0 + k_0 * (0..t_1 + …)`

. As an example, if`n`

is a power of 2, one can choose a decomposition as the base-2 presentation of`x`

, i.e.,`t_i = k_i = 2`

for all`i`

. For brevity, denote a multiplier of`x_i`

in`x`

decomposition as`K_i`

,`K_i = k_0 * … * k_{i-1}`

;`K_0 = 1`

by extension. - Split the ciphertext:
`E = E_0 + E_1 + …`

, where`E_i`

encrypts`K_i * x_i`

. - Produce a
`RingProof`

that for all`i`

the encrypted scalar for`E_i`

is among 0,`K_i`

, …,`K_i * (t_i - 1)`

. The range proof consists of all`E_i`

ciphertexts and this`RingProof`

.

As with range proofs for Pedersen commitments, this construction is not optimal
in terms of space or proving / verification complexity for large ranges;
it is linear w.r.t. the bit length of the range.
(Constructions like Bulletproofs are *logarithmic* w.r.t. the bit length.)
Still, it can be useful for small ranges.

## §Examples

```
// Generate the ciphertext receiver.
let mut rng = thread_rng();
let receiver = Keypair::<Ristretto>::generate(&mut rng);
// Find the optimal range decomposition for our range
// and specialize it for the Ristretto group.
let range = RangeDecomposition::optimal(100).into();
let (ciphertext, proof) = RangeProof::new(
receiver.public(),
&range,
55,
&mut Transcript::new(b"test_proof"),
&mut rng,
);
let ciphertext = Ciphertext::from(ciphertext);
// Check that the ciphertext is valid
let lookup = DiscreteLogTable::new(0..100);
assert_eq!(receiver.secret().decrypt(ciphertext, &lookup), Some(55));
// ...and that the proof verifies.
proof.verify(
receiver.public(),
&range,
ciphertext,
&mut Transcript::new(b"test_proof"),
)?;
```

## Implementations§

source§### impl<G: Group> RangeProof<G>

### impl<G: Group> RangeProof<G>

source#### pub fn new<R: RngCore + CryptoRng>(
receiver: &PublicKey<G>,
range: &PreparedRange<G>,
value: u64,
transcript: &mut Transcript,
rng: &mut R
) -> (CiphertextWithValue<G, u64>, Self)

#### pub fn new<R: RngCore + CryptoRng>( receiver: &PublicKey<G>, range: &PreparedRange<G>, value: u64, transcript: &mut Transcript, rng: &mut R ) -> (CiphertextWithValue<G, u64>, Self)

Encrypts `value`

for `receiver`

and creates a zero-knowledge proof that the encrypted value
is in `range`

.

This is a lower-level operation; see `PublicKey::encrypt_range()`

for a higher-level
alternative.

##### §Panics

Panics if `value`

is outside the range specified by `range`

.

source#### pub fn from_ciphertext<R: RngCore + CryptoRng>(
receiver: &PublicKey<G>,
range: &PreparedRange<G>,
ciphertext: &CiphertextWithValue<G, u64>,
transcript: &mut Transcript,
rng: &mut R
) -> Self

#### pub fn from_ciphertext<R: RngCore + CryptoRng>( receiver: &PublicKey<G>, range: &PreparedRange<G>, ciphertext: &CiphertextWithValue<G, u64>, transcript: &mut Transcript, rng: &mut R ) -> Self

Creates a proof that a value in `ciphertext`

is in the `range`

.

The caller is responsible for providing a `ciphertext`

encrypted for the `receiver`

;
if the ciphertext is encrypted for another public key, the resulting proof will not verify.

##### §Panics

Panics if `value`

is outside the range specified by `range`

.

source#### pub fn verify(
&self,
receiver: &PublicKey<G>,
range: &PreparedRange<G>,
ciphertext: Ciphertext<G>,
transcript: &mut Transcript
) -> Result<(), VerificationError>

#### pub fn verify( &self, receiver: &PublicKey<G>, range: &PreparedRange<G>, ciphertext: Ciphertext<G>, transcript: &mut Transcript ) -> Result<(), VerificationError>

Verifies this proof against `ciphertext`

for `receiver`

and the specified `range`

.

This is a lower-level operation; see `PublicKey::verify_range()`

for a higher-level
alternative.

For a proof to verify, all parameters must be identical to ones provided when creating
the proof. In particular, `range`

must have the same decomposition.

##### §Errors

Returns an error if this proof does not verify.

## Trait Implementations§

source§### impl<G: Clone + Group> Clone for RangeProof<G>

### impl<G: Clone + Group> Clone for RangeProof<G>

source§#### fn clone(&self) -> RangeProof<G>

#### fn clone(&self) -> RangeProof<G>

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

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

`source`

. Read more