search

giuliop / AlgoPlonk

The power of zero knowledge proofs on the Algorand blockchain
GNU Affero General Public License v3.0
43 stars 2 forks source link

smart signature verifiers #1

Open joe-p opened 6 months ago

joe-p commented 6 months ago

I saw you were interested in making a smart sig verifier. Doing this in conjunction with a stateful app should (I haven't looked to deeply into how exactly it's implemented here) be relatively straightforward since we can read app args from an lsig and the app can verify which lsig approved a transaction.

In this PR you can see how I took the logic from the app and put it in an lsig, then had each verify each other.

giuliop commented 6 months ago

Yes, that was the approach I had in mind. The verifier is stateless, it simply processes its inputs and either succeeds or fails, so an lsig is perfectly suitable.

Unfortunately the verifier teal program is over 3KB in size and the maximum limit is 1KB for lsigs. I think I could split the verifier in two lsigs, but that's still over the limit.

I am planning to add this comment and elaborate more on the AVM limits as a comment to your other PR here, later today

joe-p commented 6 months ago

There are two ways we can reduce program size

  1. Optimize for size over opcode budget during compilation.

For example

gamma_pre = sha256(b'gamma' + VK_S1_fs + VK_S2_fs + VK_S3_fs + VK_QL_fs
                + VK_QR_fs + VK_QM_fs + VK_QO_fs + VK_QK_fs + public_inputs_bytes

Results in a byte opcode that is nearly 800 bytes alone because all of the concatenation is done by the puya compiler. Instead we want it use the constant block which would reduce the usage of each repeated constant in the expression to 1 or 2 bytes.

  1. Offload constants in an approval program

An lsig can read the approval program of a create/update app call, so if we can offload the storage of large constants in an app (most easily done by DeleteApplication on appId 0). The hash of the approval program would be verified by the lsig and then the lsig can load constants directly from the approval program.

I am planning to add this comment and elaborate more on the AVM limits as a comment to your other PR https://github.com/algorand/go-algorand/pull/5943, later today

As currently implemented, the limit would still be 700*256 per group. I think there are arguments to increase the max program size for lsigs though. I imagine we could set the limit per group (ie. you get 16kb of total lsig size per group) or increase it to ~4kb since you can already do this approval program hack for an average of ~4kb per txn.