[cryptography/bls12381] Add Partial Multi-Signature Verification

[patrick-ogrady]

When rewarding participants in threshold-based consensus, it is necessary to agree on some set of observed partial signatures (usually by including said participation in a block). Recall, it is not possible to determine who has participated in a recovered threshold signature.

To reduce the bandwidth this process consumes, we can aggregate the partial signatures into a BLS Multi-Signature that can be verified by deriving the PublicKey of each signer by evaluating the group polynomial at the index of their share:

monorepo/cryptography/src/bls12381/primitives/poly.rs

Lines 188 to 208 in 410e7bd

	/// Evaluates the polynomial at the specified value.
	pub fn evaluate(&self, i: u32) -> Eval<C> {
	// Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L111-L129
	// We add +1 because we must never evaluate the polynomial at its first point
	// otherwise it reveals the "secret" value after a reshare (where the constant
	// term is set to be the secret of the previous dealing).
	let mut xi = Scalar::zero();
	xi.set_int(i + 1);
	// Use Horner's method to evaluate the polynomial
	let res = self.0.iter().rev().fold(C::zero(), |mut sum, coeff| {
	sum.mul(&xi);
	sum.add(coeff);
	sum
	});
	Eval {
	value: res,
	index: i,
	}
	}

When we verify a single partial signature, we already use this evaluation technique and this PR is really about extending it:

monorepo/cryptography/src/bls12381/primitives/ops.rs

Lines 168 to 176 in 410e7bd

	pub fn partial_verify_message(
	public: &poly::Public,
	namespace: Option<&[u8]>,
	message: &[u8],
	partial: &PartialSignature,
	) -> Result<(), Error> {
	let public = public.evaluate(partial.index);
	verify_message(&public.value, namespace, message, &partial.value)
	}

Credit to @StephenButtolph for the suggestion 🙏