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>

9 files changed, 256 insertions, 0 deletions

diff --git a/guests/evaluate_polynomial/.no_jolt b/guests/evaluate_polynomial/.no_jolt
new file mode 100644
index 0000000..124c1d8
--- /dev/null
+++ b/guests/evaluate_polynomial/.no_jolt
@@ -0,0 +1 @@
+Runtime error "Unknown instruction PC:ffffffff80019578 WORD:94f09db"
diff --git a/guests/evaluate_polynomial/.no_nexus b/guests/evaluate_polynomial/.no_nexus
new file mode 100644
index 0000000..22c4b59
--- /dev/null
+++ b/guests/evaluate_polynomial/.no_nexus
@@ -0,0 +1 @@
+Dependency "hex" requires the standard library
diff --git a/guests/evaluate_polynomial/.no_zkwasm b/guests/evaluate_polynomial/.no_zkwasm
new file mode 100644
index 0000000..c3821db
--- /dev/null
+++ b/guests/evaluate_polynomial/.no_zkwasm
@@ -0,0 +1 @@
+Runtime error "The number of instructions of the image(41139) is too large"
diff --git a/guests/evaluate_polynomial/Cargo.lock b/guests/evaluate_polynomial/Cargo.lock
new file mode 100644
index 0000000..817aca6
--- /dev/null
+++ b/guests/evaluate_polynomial/Cargo.lock
@@ -0,0 +1,168 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "bitvec"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1bc2832c24239b0141d5674bb9174f9d68a8b5b3f2753311927c172ca46f7e9c"
+dependencies = [
+ "funty",
+ "radium",
+ "tap",
+ "wyz",
+]
+
+[[package]]
+name = "block-buffer"
+version = "0.10.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3078c7629b62d3f0439517fa394996acacc5cbc91c5a20d8c658e77abd503a71"
+dependencies = [
+ "generic-array",
+]
+
+[[package]]
+name = "bls12_381"
+version = "0.8.0"
+source = "git+https://github.com/sp1-patches/bls12_381#9ea427c0eb1a7e2ac16902a322aea156c496ddb0"
+dependencies = [
+ "digest",
+ "ff",
+ "group",
+ "pairing",
+ "rand_core",
+ "subtle",
+]
+
+[[package]]
+name = "crypto-common"
+version = "0.1.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1bfb12502f3fc46cca1bb51ac28df9d618d813cdc3d2f25b9fe775a34af26bb3"
+dependencies = [
+ "generic-array",
+ "typenum",
+]
+
+[[package]]
+name = "digest"
+version = "0.10.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9ed9a281f7bc9b7576e61468ba615a66a5c8cfdff42420a70aa82701a3b1e292"
+dependencies = [
+ "block-buffer",
+ "crypto-common",
+]
+
+[[package]]
+name = "evaluate_polynomial"
+version = "0.1.0"
+dependencies = [
+ "bls12_381",
+ "guests_macro",
+ "hex",
+]
+
+[[package]]
+name = "ff"
+version = "0.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ded41244b729663b1e574f1b4fb731469f69f79c17667b5d776b16cda0479449"
+dependencies = [
+ "bitvec",
+ "rand_core",
+ "subtle",
+]
+
+[[package]]
+name = "funty"
+version = "2.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6d5a32815ae3f33302d95fdcb2ce17862f8c65363dcfd29360480ba1001fc9c"
+
+[[package]]
+name = "generic-array"
+version = "0.14.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "85649ca51fd72272d7821adaf274ad91c288277713d9c18820d8499a7ff69e9a"
+dependencies = [
+ "typenum",
+ "version_check",
+]
+
+[[package]]
+name = "group"
+version = "0.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f0f9ef7462f7c099f518d754361858f86d8a07af53ba9af0fe635bbccb151a63"
+dependencies = [
+ "ff",
+ "rand_core",
+ "subtle",
+]
+
+[[package]]
+name = "guests_macro"
+version = "0.1.0"
+
+[[package]]
+name = "hex"
+version = "0.4.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7f24254aa9a54b5c858eaee2f5bccdb46aaf0e486a595ed5fd8f86ba55232a70"
+
+[[package]]
+name = "pairing"
+version = "0.23.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "81fec4625e73cf41ef4bb6846cafa6d44736525f442ba45e407c4a000a13996f"
+dependencies = [
+ "group",
+]
+
+[[package]]
+name = "radium"
+version = "0.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "dc33ff2d4973d518d823d61aa239014831e521c75da58e3df4840d3f47749d09"
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+
+[[package]]
+name = "subtle"
+version = "2.6.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "13c2bddecc57b384dee18652358fb23172facb8a2c51ccc10d74c157bdea3292"
+
+[[package]]
+name = "tap"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "55937e1799185b12863d447f42597ed69d9928686b8d88a1df17376a097d8369"
+
+[[package]]
+name = "typenum"
+version = "1.18.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1dccffe3ce07af9386bfd29e80c0ab1a8205a2fc34e4bcd40364df902cfa8f3f"
+
+[[package]]
+name = "version_check"
+version = "0.9.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0b928f33d975fc6ad9f86c8f283853ad26bdd5b10b7f1542aa2fa15e2289105a"
+
+[[package]]
+name = "wyz"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "05f360fc0b24296329c78fda852a1e9ae82de9cf7b27dae4b7f62f118f77b9ed"
+dependencies = [
+ "tap",
+]
diff --git a/guests/evaluate_polynomial/Cargo.toml b/guests/evaluate_polynomial/Cargo.toml
new file mode 100644
index 0000000..d235978
--- /dev/null
+++ b/guests/evaluate_polynomial/Cargo.toml
@@ -0,0 +1,18 @@
+[package]
+name = "evaluate_polynomial"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+bls12_381 = { git = "https://github.com/sp1-patches/bls12_381", features = ["experimental"]  }
+guests_macro = { version = "0.1.0", path = "../../guests_macro" }
+hex = "0.4"
+
+[features]
+no_std = []
+jolt = []
+nexus = []
+risc0 = []
+sp1 = []
+zkm = []
+zkwasm = []
diff --git a/guests/evaluate_polynomial/default.env b/guests/evaluate_polynomial/default.env
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/guests/evaluate_polynomial/default.env
diff --git a/guests/evaluate_polynomial/default_private_input.toml b/guests/evaluate_polynomial/default_private_input.toml
new file mode 100644
index 0000000..8a9306c
--- /dev/null
+++ b/guests/evaluate_polynomial/default_private_input.toml
@@ -0,0 +1 @@
+target = "af8e0095ecc662f65b95ce57e5bd2f8739ff93b0621a1ad53f5616538d1323ff40e6e9ddd7132298710974fe6fc0344e"
diff --git a/guests/evaluate_polynomial/default_public_input.toml b/guests/evaluate_polynomial/default_public_input.toml
new file mode 100644
index 0000000..9a03192
--- /dev/null
+++ b/guests/evaluate_polynomial/default_public_input.toml
@@ -0,0 +1,5 @@
+pks = [
+    "92cad77a95432bc1030d81b5465cb69be672c1dd0da752230bf8112f8449b03149e7fa208a6fae460a9f0a1d5bd175e9",
+    "98876a81fe982573ec5f986956bf9bf0bcb5349d95c3c8da0aefd05a49fea6215f59b0696f906547baed90ab245804e8",
+    "ad2c4e5b631fbded449ede4dca2d040b9c7eae58d1e73b3050486c1ba22c15a92d9ff13c05c356f974447e4fca84864a"
+]
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);
+    }
+}