#5373

Committed 11 Oct 2024 12:48PM UTC coverage: 47.696% (+0.05%) from 47.643%

Build # #5373

Build Type

Committed by

Commit Message

secret-sharing/src/churp/switch: Verify combined bivariate polynomial

After all bivariate shares are collected and the switch either
creates a new shareholder or proactivates the share of an existing
one, the new share should be verified to ensure that the verification
matrix of the combined bivariate polynomial satisfies the non-zero
leading term requirements.

Pull Request Pull Request #5897: secret-sharing/src/churp/switch: Verify combined bivariate polynomial

Run Details

33 of 42 new or added lines in 5 files covered. (78.57%)

1 existing line in 1 file now uncovered.

4503 of 9441 relevant lines covered (47.7%)

1.11 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

75.0

/secret-sharing/src/churp/shareholder.rs

//! CHURP shareholder.

use anyhow::Result;
use group::{
    ff::{Field, PrimeField},
    Group, GroupEncoding,
};

use crate::{
    kdc::PointShareholder, poly::Polynomial, suites::FieldDigest, vss::VerificationMatrix,
};

use super::Error;

/// Encodes the given shareholder ID to a non-zero element of the prime field.
pub fn encode_shareholder<H: FieldDigest>(id: &[u8], dst: &[u8]) -> Result<H::Output> {
    let s = H::hash_to_field(id, dst).map_err(|_| Error::ShareholderEncodingFailed)?;

    if s.is_zero().into() {
        return Err(Error::ZeroValueShareholder.into());
    }

    Ok(s)
}

/// Shareholder is responsible for deriving key shares and generating
/// switch points during handoffs when the committee is trying
/// to switch to the other dimension.
pub struct Shareholder<G: Group + GroupEncoding> {
    /// Verifiable secret (full or reduced) share of the shared secret.
    verifiable_share: VerifiableSecretShare<G>,
}

impl<G> Shareholder<G>
where
    G: Group + GroupEncoding,
{
    /// Creates a new shareholder.
    pub fn new(share: SecretShare<G::Scalar>, vm: VerificationMatrix<G>) -> Self {
        VerifiableSecretShare::new(share, vm).into()
    }

    /// Returns the verifiable secret share.
    pub fn verifiable_share(&self) -> &VerifiableSecretShare<G> {
        &self.verifiable_share
    }

    /// Computes switch point for the given shareholder.
    pub fn switch_point(&self, x: &G::Scalar) -> G::Scalar {
        self.verifiable_share.share.p.eval(x)
    }

    /// Creates a new shareholder with a proactivized secret polynomial.
    pub fn proactivize(
        &self,
        p: &Polynomial<G::Scalar>,
        vm: &VerificationMatrix<G>,
    ) -> Result<Shareholder<G>> {
        if p.size() != self.verifiable_share.share.p.size() {
            return Err(Error::PolynomialDegreeMismatch.into());
        }
        if !vm.is_zero_hole() {
            return Err(Error::VerificationMatrixZeroHoleMismatch.into());
        }
        if vm.dimensions() != self.verifiable_share.vm.dimensions() {
            return Err(Error::VerificationMatrixDimensionMismatch.into());
        }

        let x = self.verifiable_share.share.x;
        let p = p + &self.verifiable_share.share.p;
        let vm = vm + &self.verifiable_share.vm;
        let share = SecretShare::new(x, p);
        let shareholder = Shareholder::new(share, vm);

        Ok(shareholder)
    }
}

impl<G> From<VerifiableSecretShare<G>> for Shareholder<G>
where
    G: Group + GroupEncoding,
{
    fn from(verifiable_share: VerifiableSecretShare<G>) -> Shareholder<G> {
        Shareholder { verifiable_share }
    }
}

impl<G> PointShareholder<G::Scalar> for Shareholder<G>
where
    G: Group + GroupEncoding,
{
    fn coordinate_x(&self) -> &G::Scalar {
        self.verifiable_share.share.coordinate_x()
    }

    fn coordinate_y(&self) -> &G::Scalar {
        self.verifiable_share.share.coordinate_y()
    }
}

/// Secret share of the shared secret.
pub struct SecretShare<F: PrimeField> {
    /// The encoded identity of the shareholder.
    ///
    /// The identity is the x-coordinate of a point on the secret-sharing
    /// univariate polynomial B(x,0) or B(0,y).
    pub(crate) x: F,

    /// The secret polynomial B(id,y) or B(x,id).
    ///
    /// The constant term of the polynomial is the y-coordinate of a point
    /// on the secret-sharing univariate polynomial B(x,0) or B(0,y).
    pub(crate) p: Polynomial<F>,
}

impl<F> SecretShare<F>
where
    F: PrimeField,
{
    /// Creates a new secret share.
    pub fn new(x: F, p: Polynomial<F>) -> Self {
        Self { x, p }
    }

    /// Returns the polynomial.
    pub fn polynomial(&self) -> &Polynomial<F> {
        &self.p
    }

    /// Returns the x-coordinate of a point on the secret-sharing
    /// univariate polynomial B(x,0) or B(0,y).
    pub fn coordinate_x(&self) -> &F {
        &self.x
    }

    /// Returns the y-coordinate of a point on the secret-sharing
    /// univariate polynomial B(x,0) or B(0,y).
    pub fn coordinate_y(&self) -> &F {
        self.p
            .coefficient(0)
            .expect("polynomial has at least one term")
    }
}

/// Verifiable secret share of the shared secret.
pub struct VerifiableSecretShare<G: Group + GroupEncoding> {
    /// Secret (full or reduced) share of the shared secret.
    pub(crate) share: SecretShare<G::Scalar>,

    /// Verification matrix used to verify that the polynomial in the secret
    /// share is an evaluation B(x,id) or B(id,y) of the secret bivariate
    /// polynomial B(x,y).
    pub(crate) vm: VerificationMatrix<G>,
}

impl<G> VerifiableSecretShare<G>
where
    G: Group + GroupEncoding,
{
    /// Creates a new verifiable secret share.
    pub fn new(share: SecretShare<G::Scalar>, vm: VerificationMatrix<G>) -> Self {
        Self { share, vm }
    }

    /// Returns the secret share.
    pub fn secret_share(&self) -> &SecretShare<G::Scalar> {
        &self.share
    }

    /// Returns the verification matrix.
    pub fn verification_matrix(&self) -> &VerificationMatrix<G> {
        &self.vm
    }

    /// Verifies the secret share and the verification matrix.
    pub fn verify(&self, threshold: u8, zero_hole: bool, full_share: bool) -> Result<()> {
        self.verify_verification_matrix(threshold, zero_hole)?;
        self.verify_secret_share(threshold, full_share)?;
        Ok(())
    }

    /// Verifies the verification matrix.
    fn verify_verification_matrix(&self, threshold: u8, zero_hole: bool) -> Result<()> {
        let (rows, cols) = Self::calculate_dimensions(threshold);

        if self.vm.dimensions() != (rows, cols) {
            return Err(Error::VerificationMatrixDimensionMismatch.into());
        }
        if self.vm.is_zero_hole() != zero_hole {
            return Err(Error::VerificationMatrixZeroHoleMismatch.into());
        }

        // Verify that the bivariate polynomial `B(x, y)`, from which
        // the verification matrix was constructed and the share was derived,
        // satisfies the non-zero leading term requirements. Specifically,
        // the polynomials `B(x, y)`, `B(x, 0)`, and `B(0, y)` must have
        // non-zero leading terms.
        let i = rows - 1;
        let j = cols - 1;

        if self.vm.element(i, j).unwrap().is_identity().into() {
            return Err(Error::InsecureBivariatePolynomial.into());
        }
        if self.vm.element(i, 0).unwrap().is_identity().into() {
            return Err(Error::InsecureBivariatePolynomial.into());
        }
        if self.vm.element(0, j).unwrap().is_identity().into() {
            return Err(Error::InsecureBivariatePolynomial.into());
        }

        Ok(())
    }

    /// Verifies the secret share.
    fn verify_secret_share(&self, threshold: u8, full_share: bool) -> Result<()> {
        let (rows, cols) = Self::calculate_dimensions(threshold);

        if full_share {
            if self.share.p.size() != cols {
                return Err(Error::PolynomialDegreeMismatch.into());
            }
            if !self.vm.verify_x(&self.share.x, &self.share.p) {
                return Err(Error::InvalidPolynomial.into());
            }
        } else {
            if self.share.p.size() != rows {
                return Err(Error::PolynomialDegreeMismatch.into());
            }
            if !self.vm.verify_y(&self.share.x, &self.share.p) {
                return Err(Error::InvalidPolynomial.into());
            }
        }

        Ok(())
    }

    /// Calculates the number of rows and columns in the verification matrix
    /// based on the given threshold.
    const fn calculate_dimensions(threshold: u8) -> (usize, usize) {
        let rows: usize = threshold as usize + 1;
        let cols = threshold as usize * 2 + 1;
        (rows, cols)
    }
}

1	//! CHURP shareholder.
2
3	use anyhow::Result;
4	use group::{
5	ff::{Field, PrimeField},
6	Group, GroupEncoding,
7	};
8
9	use crate::{
10	kdc::PointShareholder, poly::Polynomial, suites::FieldDigest, vss::VerificationMatrix,
11	};
12
13	use super::Error;
14
15	/// Encodes the given shareholder ID to a non-zero element of the prime field.
16	pub fn encode_shareholder<H: FieldDigest>(id: &[u8], dst: &[u8]) -> Result<H::Output> {	×
17	let s = H::hash_to_field(id, dst).map_err(\|_\| Error::ShareholderEncodingFailed)?;	×
18
19	if s.is_zero().into() {	×
20	return Err(Error::ZeroValueShareholder.into());	×
21	}
22
23	Ok(s)	×
24	}
25
26	/// Shareholder is responsible for deriving key shares and generating
27	/// switch points during handoffs when the committee is trying
28	/// to switch to the other dimension.
29	pub struct Shareholder<G: Group + GroupEncoding> {
30	/// Verifiable secret (full or reduced) share of the shared secret.
31	verifiable_share: VerifiableSecretShare<G>,
32	}
33
34	impl<G> Shareholder<G>
35	where
36	G: Group + GroupEncoding,
37	{
38	/// Creates a new shareholder.
39	pub fn new(share: SecretShare<G::Scalar>, vm: VerificationMatrix<G>) -> Self {	1✔
40	VerifiableSecretShare::new(share, vm).into()	1✔
41	}
42
43	/// Returns the verifiable secret share.
44	pub fn verifiable_share(&self) -> &VerifiableSecretShare<G> {	1✔
45	&self.verifiable_share	×
46	}
47
48	/// Computes switch point for the given shareholder.
49	pub fn switch_point(&self, x: &G::Scalar) -> G::Scalar {	1✔
50	self.verifiable_share.share.p.eval(x)	1✔
51	}
52
53	/// Creates a new shareholder with a proactivized secret polynomial.
54	pub fn proactivize(	1✔
55	&self,
56	p: &Polynomial<G::Scalar>,
57	vm: &VerificationMatrix<G>,
58	) -> Result<Shareholder<G>> {
59	if p.size() != self.verifiable_share.share.p.size() {	1✔
60	return Err(Error::PolynomialDegreeMismatch.into());	×
61	}
62	if !vm.is_zero_hole() {	1✔
63	return Err(Error::VerificationMatrixZeroHoleMismatch.into());	×
64	}
65	if vm.dimensions() != self.verifiable_share.vm.dimensions() {	1✔
66	return Err(Error::VerificationMatrixDimensionMismatch.into());	×
67	}
68
69	let x = self.verifiable_share.share.x;	1✔
70	let p = p + &self.verifiable_share.share.p;	1✔
71	let vm = vm + &self.verifiable_share.vm;	2✔
72	let share = SecretShare::new(x, p);	1✔
73	let shareholder = Shareholder::new(share, vm);	1✔
74
75	Ok(shareholder)	1✔
76	}
77	}
78
79	impl<G> From<VerifiableSecretShare<G>> for Shareholder<G>
80	where
81	G: Group + GroupEncoding,
82	{
83	fn from(verifiable_share: VerifiableSecretShare<G>) -> Shareholder<G> {	1✔
84	Shareholder { verifiable_share }
85	}
86	}
87
88	impl<G> PointShareholder<G::Scalar> for Shareholder<G>
89	where
90	G: Group + GroupEncoding,
91	{
92	fn coordinate_x(&self) -> &G::Scalar {	1✔
93	self.verifiable_share.share.coordinate_x()	1✔
94	}
95
96	fn coordinate_y(&self) -> &G::Scalar {	1✔
97	self.verifiable_share.share.coordinate_y()	1✔
98	}
99	}
100
101	/// Secret share of the shared secret.
102	pub struct SecretShare<F: PrimeField> {
103	/// The encoded identity of the shareholder.
104	///
105	/// The identity is the x-coordinate of a point on the secret-sharing
106	/// univariate polynomial B(x,0) or B(0,y).
107	pub(crate) x: F,
108
109	/// The secret polynomial B(id,y) or B(x,id).
110	///
111	/// The constant term of the polynomial is the y-coordinate of a point
112	/// on the secret-sharing univariate polynomial B(x,0) or B(0,y).
113	pub(crate) p: Polynomial<F>,
114	}
115
116	impl<F> SecretShare<F>
117	where
118	F: PrimeField,
119	{
120	/// Creates a new secret share.
121	pub fn new(x: F, p: Polynomial<F>) -> Self {	3✔
122	Self { x, p }
123	}
124
125	/// Returns the polynomial.
126	pub fn polynomial(&self) -> &Polynomial<F> {	2✔
127	&self.p	×
128	}
129
130	/// Returns the x-coordinate of a point on the secret-sharing
131	/// univariate polynomial B(x,0) or B(0,y).
132	pub fn coordinate_x(&self) -> &F {	2✔
133	&self.x	3✔
134	}
135
136	/// Returns the y-coordinate of a point on the secret-sharing
137	/// univariate polynomial B(x,0) or B(0,y).
138	pub fn coordinate_y(&self) -> &F {	1✔
139	self.p	1✔
140	.coefficient(0)
141	.expect("polynomial has at least one term")
142	}
143	}
144
145	/// Verifiable secret share of the shared secret.
146	pub struct VerifiableSecretShare<G: Group + GroupEncoding> {
147	/// Secret (full or reduced) share of the shared secret.
148	pub(crate) share: SecretShare<G::Scalar>,
149
150	/// Verification matrix used to verify that the polynomial in the secret
151	/// share is an evaluation B(x,id) or B(id,y) of the secret bivariate
152	/// polynomial B(x,y).
153	pub(crate) vm: VerificationMatrix<G>,
154	}
155
156	impl<G> VerifiableSecretShare<G>
157	where
158	G: Group + GroupEncoding,
159	{
160	/// Creates a new verifiable secret share.
161	pub fn new(share: SecretShare<G::Scalar>, vm: VerificationMatrix<G>) -> Self {	2✔
162	Self { share, vm }
163	}
164
165	/// Returns the secret share.
166	pub fn secret_share(&self) -> &SecretShare<G::Scalar> {	2✔
167	&self.share	×
168	}
169
170	/// Returns the verification matrix.
171	pub fn verification_matrix(&self) -> &VerificationMatrix<G> {	2✔
172	&self.vm	3✔
173	}
174
175	/// Verifies the secret share and the verification matrix.
176	pub fn verify(&self, threshold: u8, zero_hole: bool, full_share: bool) -> Result<()> {	1✔
177	self.verify_verification_matrix(threshold, zero_hole)?;	2✔
178	self.verify_secret_share(threshold, full_share)?;	2✔
179	Ok(())	1✔
180	}
181
182	/// Verifies the verification matrix.
183	fn verify_verification_matrix(&self, threshold: u8, zero_hole: bool) -> Result<()> {	1✔
184	let (rows, cols) = Self::calculate_dimensions(threshold);	1✔
185
186	if self.vm.dimensions() != (rows, cols) {	1✔
187	return Err(Error::VerificationMatrixDimensionMismatch.into());	1✔
188	}
189	if self.vm.is_zero_hole() != zero_hole {	1✔
190	return Err(Error::VerificationMatrixZeroHoleMismatch.into());	1✔
191	}
192
193	// Verify that the bivariate polynomial `B(x, y)`, from which
194	// the verification matrix was constructed and the share was derived,
195	// satisfies the non-zero leading term requirements. Specifically,
196	// the polynomials `B(x, y)`, `B(x, 0)`, and `B(0, y)` must have
197	// non-zero leading terms.
198	let i = rows - 1;	2✔
199	let j = cols - 1;	2✔
200
201	if self.vm.element(i, j).unwrap().is_identity().into() {	2✔
NEW 202	return Err(Error::InsecureBivariatePolynomial.into());	×
203	}
204	if self.vm.element(i, 0).unwrap().is_identity().into() {	2✔
NEW 205	return Err(Error::InsecureBivariatePolynomial.into());	×
206	}
207	if self.vm.element(0, j).unwrap().is_identity().into() {	2✔
NEW 208	return Err(Error::InsecureBivariatePolynomial.into());	×
209	}
210
211	Ok(())	1✔
212	}
213
214	/// Verifies the secret share.
215	fn verify_secret_share(&self, threshold: u8, full_share: bool) -> Result<()> {	1✔
216	let (rows, cols) = Self::calculate_dimensions(threshold);	1✔
217
218	if full_share {	1✔
219	if self.share.p.size() != cols {	1✔
220	return Err(Error::PolynomialDegreeMismatch.into());	×
221	}
222	if !self.vm.verify_x(&self.share.x, &self.share.p) {	1✔
223	return Err(Error::InvalidPolynomial.into());	×
224	}
225	} else {
226	if self.share.p.size() != rows {	1✔
227	return Err(Error::PolynomialDegreeMismatch.into());	×
228	}
229	if !self.vm.verify_y(&self.share.x, &self.share.p) {	1✔
230	return Err(Error::InvalidPolynomial.into());	×
231	}
232	}
233
234	Ok(())	1✔
235	}
236
237	/// Calculates the number of rows and columns in the verification matrix
238	/// based on the given threshold.
239	const fn calculate_dimensions(threshold: u8) -> (usize, usize) {	1✔
240	let rows: usize = threshold as usize + 1;	1✔
241	let cols = threshold as usize * 2 + 1;	2✔
242	(rows, cols)	×
243	}
244	}

oasisprotocol / oasis-core / #5373

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous