feat: EVM compatible proof plan serialization #432

JayWhite2357 · 2024-12-13T16:04:09Z

Rationale for this change

We need Solidity to be able to read Proof Plans.

What changes are included in this PR?

An initial implementation of serialization for Proof Plan is added.

Are these changes tested?

Yes

iajoiner

Hmm are you sure we don't want to use an existing serialization library such as ethabi, rlp or ssz for this?

iajoiner · 2024-12-13T17:03:56Z

crates/proof-of-sql/src/evm_compatibility/dyn_proof_plan_serializer.rs

+    TooManyResults,
+    #[snafu(display("Too many tables"))]
+    /// The number of tables in a plan is too large
+    TooManyTables,


I think we should put the exact limit in the error message or people won't even know how many are too many

iajoiner · 2024-12-13T17:04:22Z

crates/proof-of-sql/src/evm_compatibility/dyn_proof_plan_serializer.rs

+    TooManyTables,
+    #[snafu(display("Too many columns"))]
+    /// The number of columns in a plan is too large
+    TooManyColumns,


Same. It's actually plausible to have 256 columns in web2

JayWhite2357 · 2024-12-14T01:27:50Z

Hmm are you sure we don't want to use an existing serialization library such as ethabi, rlp or ssz for this?

I originally tried the abi, but found that this format is magnitudes cheaper when actually passing over the AST.

Although, I'm now considering changing this to postorder rather than preorder. The idea is that the data is in the exact order that we need it as we do the verification. Saves arithmetic and having to jump around. I'm not sure if it would work as well, though.

Not too familiar with rlp or ssz. I don't think they are Solidity/EVM formats, but are used by Ethereum for other things.

JayWhite2357 · 2024-12-16T11:26:45Z

crates/proof-of-sql/src/evm_compatibility/serialize_query_expr.rs

+    fn we_can_generate_serialized_proof_plan_for_simple_filter() {
+        let table_ref = "namespace.table".parse().unwrap();
+        let identifier_a = "a".parse().unwrap();
+        let identifier_b = "b".parse().unwrap();
+        let identifier_alias = "alias".parse().unwrap();
+
+        let column_ref_a = ColumnRef::new(table_ref, identifier_a, ColumnType::BigInt);
+        let column_ref_b = ColumnRef::new(table_ref, identifier_b, ColumnType::BigInt);
+
+        let plan = DynProofPlan::Filter(FilterExec::new(
+            vec![AliasedDynProofExpr {
+                expr: DynProofExpr::Column(ColumnExpr::new(column_ref_b)),
+                alias: identifier_alias,
+            }],
+            TableExpr { table_ref },
+            DynProofExpr::Equals(EqualsExpr::new(
+                Box::new(DynProofExpr::Column(ColumnExpr::new(column_ref_a))),
+                Box::new(DynProofExpr::Literal(LiteralExpr::new(
+                    LiteralValue::BigInt(5),
+                ))),
+            )),
+        ));
+
+        let query_expr = QueryExpr::new(plan, vec![]);
+        let bytes = serialize_query_expr::<TestScalar>(&query_expr).unwrap();
+        let expected_bytes = iter::empty::<u8>()
+            .chain([FILTER_EXEC_NUM, 0, 1]) // filter expr, table number, result count
+            .chain([COLUMN_EXPR_NUM, 0]) // column expr, column a (#0)
+            .chain([EQUALS_EXPR_NUM]) // equals expr
+            .chain([COLUMN_EXPR_NUM, 1]) // column expr, column b (#1)
+            .chain([LITERAL_EXPR_NUM, BIGINT_TYPE_NUM]) // literal expr, literal type
+            .chain([0; 31]) // leading 0s of literal value
+            .chain([5]) // literal value
+            .collect_vec();
+        assert_eq!(bytes, expected_bytes);
+    }


This is the "integration test": the top level example of what is happening in this PR.

could be a basic question but I understand we expect the filter expression to be where a = 5
so we do we have .chain([COLUMN_EXPR_NUM, 1]) // column expr, column b (#1) in line 151 ?

let expected_bytes = iter::empty::<u8>() .chain([FILTER_EXEC_NUM, 0, 1]) // filter expr, table number, result count .chain([COLUMN_EXPR_NUM, 0]) // column expr, column a (#0) .chain([EQUALS_EXPR_NUM]) // equals expr .chain([LITERAL_EXPR_NUM, BIGINT_TYPE_NUM]) // literal expr, literal type .chain([0; 31]) // leading 0s of literal value .chain([5]) // literal value .collect_vec(); @JayWhite2357 what would that be?

could be a basic question but I understand we expect the filter expression to be where a = 5 so we do we have .chain([COLUMN_EXPR_NUM, 1]) // column expr, column b (#1) in line 151 ?

I flipped the a and b in the comments. It should be the other way. I'll fix it.

let expected_bytes = iter::empty::<u8>() .chain([FILTER_EXEC_NUM, 0, 1]) // filter expr, table number, result count .chain([COLUMN_EXPR_NUM, 0]) // column expr, column a (#0) .chain([EQUALS_EXPR_NUM]) // equals expr .chain([LITERAL_EXPR_NUM, BIGINT_TYPE_NUM]) // literal expr, literal type .chain([0; 31]) // leading 0s of literal value .chain([5]) // literal value .collect_vec(); @JayWhite2357 what would that be?

This is invalid. Would be something like SELECT a FROM table WHERE 5 =

so the serialized query expression is agnostic to column names. right? I see the query plan create incremental reference to column by their mentioning order

@JayWhite2357 how about result count does that refer to rows count? and needed for verification? because I don't see it needed within AST

That refers to the number of results in the filter.
e.g., SELECT a,b,c,d,e,f,g FROM table where a=5 would have 7 as the result count.

waelsy123 · 2024-12-16T13:49:56Z

crates/proof-of-sql/src/evm_compatibility/serialize_query_expr.rs

+    #[test]
+    fn we_can_generate_serialized_proof_plan_for_query_expr() {
+        let table_ref = "namespace.table".parse().unwrap();
+        let identifier_alias = "alias".parse().unwrap();


what is identifier_alias used for?

Nothing at the moment. Eventually, it will need to be used to validate the result names, if desired. But, it isn't going to be used by the EVM proof verifier.

github-actions · 2024-12-16T16:15:25Z

🎉 This PR is included in version 0.62.3 🎉

The release is available on GitHub release

Your semantic-release bot 📦🚀

JayWhite2357 requested review from waelsy123 and iajoiner December 13, 2024 16:04

iajoiner reviewed Dec 13, 2024

View reviewed changes

chore: add Clone and increase visibility of DynProofPlan types

bee82e8

JayWhite2357 force-pushed the feat/proof-plan-sol-serialize branch from 235e2df to 37d2041 Compare December 16, 2024 11:12

feat: add EVM-compatible serialization for DynProofPlan

9be37bd

JayWhite2357 force-pushed the feat/proof-plan-sol-serialize branch from 37d2041 to 9be37bd Compare December 16, 2024 11:23

JayWhite2357 requested a review from iajoiner December 16, 2024 11:24

JayWhite2357 commented Dec 16, 2024

View reviewed changes

iajoiner previously approved these changes Dec 16, 2024

View reviewed changes

waelsy123 previously approved these changes Dec 16, 2024

View reviewed changes

waelsy123 reviewed Dec 16, 2024

View reviewed changes

fixup! feat: add EVM-compatible serialization for DynProofPlan

e280155

JayWhite2357 dismissed stale reviews from waelsy123 and iajoiner via e280155 December 16, 2024 13:55

iajoiner approved these changes Dec 16, 2024

View reviewed changes

waelsy123 approved these changes Dec 16, 2024

View reviewed changes

iajoiner merged commit d4eff36 into main Dec 16, 2024
16 checks passed

github-actions bot added the released label Dec 16, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: EVM compatible proof plan serialization #432

feat: EVM compatible proof plan serialization #432

JayWhite2357 commented Dec 13, 2024

iajoiner left a comment

iajoiner Dec 13, 2024

iajoiner Dec 13, 2024

JayWhite2357 commented Dec 14, 2024

JayWhite2357 Dec 16, 2024

waelsy123 Dec 16, 2024

waelsy123 Dec 16, 2024

JayWhite2357 Dec 16, 2024

JayWhite2357 Dec 16, 2024

waelsy123 Dec 16, 2024

waelsy123 Dec 16, 2024

JayWhite2357 Dec 16, 2024

waelsy123 Dec 16, 2024

JayWhite2357 Dec 16, 2024

github-actions bot commented Dec 16, 2024

feat: EVM compatible proof plan serialization #432

feat: EVM compatible proof plan serialization #432

Conversation

JayWhite2357 commented Dec 13, 2024

Rationale for this change

What changes are included in this PR?

Are these changes tested?

iajoiner left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

JayWhite2357 commented Dec 14, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

github-actions bot commented Dec 16, 2024