feat(guests): Add polynomial evaluation programevaluate_polynomial

Adapted from
https://github.com/metacraft-labs/dvt-circuits/blob/master/crates/bls_utils/src/bls.rs#L26

Co-authored-by: Marto <martindobrev0@gmail.com>

1 files changed, 61 insertions, 0 deletions

diff --git a/guests/evaluate_polynomial/src/lib.rs b/guests/evaluate_polynomial/src/lib.rs
new file mode 100644
index 0000000..d647899
--- /dev/null
+++ b/guests/evaluate_polynomial/src/lib.rs
@@ -0,0 +1,61 @@
+use bls12_381::{ G1Affine, G1Projective, Scalar };
+
+pub const BLS_PUBKEY_SIZE: usize = 48;
+pub type BLSPubkey = [u8; BLS_PUBKEY_SIZE];
+
+// Originally implemented in https://github.com/metacraft-labs/dvt-circuits/blob/master/crates/bls_utils/src/bls.rs
+#[guests_macro::proving_entrypoint]
+pub fn main(
+    pks: Vec<String>,
+    target: String,
+) -> bool {
+    let pks: Vec<G1Affine> = pks
+        .iter().map(|pk| -> BLSPubkey {
+            hex::decode(pk).unwrap().try_into().unwrap()
+        })
+        .map(|pk| G1Affine::from_compressed(&pk).into_option().unwrap()).collect();
+
+    let id = bls_id_from_u32(1);
+    let result = evaluate_polynomial(pks, id);
+
+    hex::encode(result.to_compressed()) == target
+}
+
+pub fn bls_id_from_u32(id: u32) -> Scalar {
+    let unwrapped_le: [u8; 4] = (id as u32).to_le_bytes();
+    let mut bytes = [0u8; 32];
+    bytes[..4].copy_from_slice(&unwrapped_le);
+    Scalar::from_bytes(&bytes).unwrap()
+}
+
+// https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
+//
+// In Shamir's secret sharing, a secret is encoded as a n-degree polynomial
+// F where the secret value is equal to F(0). Here, F(0) is provided as mask[0].
+//
+// A key share is generated by evaluating the polynomial in the `id` point.
+// Later we can use at least N of these points to recover the original secret.
+//
+// Furthermore, if we sign some message M with at least K of the secret key
+// shares we can restore from them the signature of the same message signed
+// with original secret key.
+//
+// For a more gentle introductiont to Shamir's secret sharing, see also:
+//
+// https://github.com/dashpay/dips/blob/master/dip-0006/bls_m-of-n_threshold_scheme_and_dkg.md
+// https://medium.com/toruslabs/what-distributed-key-generation-is-866adc79620
+pub fn evaluate_polynomial(cfs: Vec<G1Affine>, x: Scalar) -> G1Affine {
+    let cfst: Vec<G1Projective> = cfs.iter().map(|c| G1Projective::from(c)).collect();
+    let count = cfst.len();
+    if count == 0 {
+        return G1Affine::identity();
+    } else if count == 1 {
+        return cfs[0];
+    } else {
+        let mut y = cfst[count - 1];
+        for i in 2..(count + 1) {
+            y = y * x + cfs[count - i];
+        }
+        return G1Affine::from(y);
+    }
+}