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):

  1. 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.
  2. Split the ciphertext: E = E_0 + E_1 + …, where E_i encrypts K_i * x_i.
  3. 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>

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)

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

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>

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>

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<G: Debug + Group> Debug for RangeProof<G>

source§

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

Formats the value using the given formatter. Read more
source§

impl<'de, G: Group> Deserialize<'de> for RangeProof<G>

source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>
where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
source§

impl<G: Group> Serialize for RangeProof<G>

source§

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>
where __S: Serializer,

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations§

§

impl<G> Freeze for RangeProof<G>
where <G as ScalarOps>::Scalar: Freeze,

§

impl<G> RefUnwindSafe for RangeProof<G>

§

impl<G> Send for RangeProof<G>
where <G as ElementOps>::Element: Send, <G as ScalarOps>::Scalar: Send,

§

impl<G> Sync for RangeProof<G>
where <G as ElementOps>::Element: Sync, <G as ScalarOps>::Scalar: Sync,

§

impl<G> Unpin for RangeProof<G>
where <G as ElementOps>::Element: Unpin, <G as ScalarOps>::Scalar: Unpin,

§

impl<G> UnwindSafe for RangeProof<G>

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V

source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,