o1-labs / o1js

TypeScript framework for zk-SNARKs and zkApps
https://docs.minaprotocol.com/en/zkapps/how-to-write-a-zkapp
Apache License 2.0
514 stars 116 forks source link

Discussion: Refactor internal CircuitValues to use Struct instead #559

Closed MartinMinkov closed 2 weeks ago

MartinMinkov commented 1 year ago

Description

We have several useful primitives exposed in SnarkyJS that are implemented with the deprecated CircuitValue class. An example of such a primitive is the Merkle Tree implementation.

Should we refactor such primitives to use Struct instead?

bkase commented 1 year ago

Will start with a subset -- and will identify the list of tasks

MartinMinkov commented 1 year ago

Identified the following classes that extend CircuitValue that is used internally:

In src/lib

$ find src/lib -type f -name '*.ts' | xargs grep -n '.* extends CircuitValue'
src/lib/merkle_map.ts:116:export class MerkleMapWitness extends CircuitValue {
src/lib/merkle_tree.ts:149:class BaseMerkleWitness extends CircuitValue {
src/lib/signature.ts:11:class PrivateKey extends CircuitValue {
src/lib/signature.ts:77:class PublicKey extends CircuitValue {
src/lib/signature.ts:184:class Signature extends CircuitValue {
src/lib/string.ts:9:class Character extends CircuitValue {
src/lib/string.ts:37:class CircuitString extends CircuitValue {
src/lib/int.ts:12:class UInt64 extends CircuitValue {
src/lib/int.ts:248:class UInt32 extends CircuitValue {
src/lib/int.ts:480:class Sign extends CircuitValue {
src/lib/int.ts:525:class Int64 extends CircuitValue implements BalanceChange {

In src/examples

$ find src/examples/ -type f -name '*.ts' | xargs grep -n '.* extends CircuitValue'
src/examples/sudoku/sudoku-zkapp.ts:15:class Sudoku extends CircuitValue {
src/examples/schnorr_sign.ts:12:class Witness extends CircuitValue {
src/examples/zkapps/merkle_tree/merkle_zkapp.ts:41:class Account extends CircuitValue {
src/examples/zkapps/local_events_zkapp.ts:27:class Event extends CircuitValue {
src/examples/zkapps/voting/member.ts:21:export class Member extends CircuitValue {
src/examples/zkapps/voting/election_preconditions.ts:3:export default class ElectionPreconditions extends CircuitValue {
src/examples/zkapps/voting/participant_preconditions.ts:3:export default class ParticipantPreconditions extends CircuitValue {
src/examples/rollup/wip.ts:43:class RollupAccount extends CircuitValue {
src/examples/rollup/wip.ts:49:class RollupTransaction extends CircuitValue {
src/examples/rollup/wip.ts:56:class RollupDeposit extends CircuitValue {
src/examples/rollup/wip.ts:61:class RollupState extends CircuitValue {
src/examples/rollup/wip.ts:66:class RollupStateTransition extends CircuitValue {
src/examples/rollup/merkle_proof.ts:24:  verify<T extends CircuitValue>(commitment: Field, x: T): Bool {
src/examples/rollup/merkle_proof.ts:30:export function MerkleAccumulatorFactory<A extends CircuitValue>(
src/examples/rollup/merkle_proof.ts:125:export abstract class IndexedAccumulator<A> extends CircuitValue {
src/examples/rollup/merkle_proof.ts:134:  K extends CircuitValue,
src/examples/rollup/merkle_proof.ts:135:  V extends CircuitValue
src/examples/rollup/merkle_stack.ts:4:export class MerkleStack<A extends CircuitValue> {
src/examples/rollup/merkle_stack.ts:11:  static pushCommitment<B extends CircuitValue>(x: B, comm: Field): Field {

I will start to tackle some of these in follow up PRs

mitschabaude commented 1 year ago

Here's a challenge that I just remembered: Some of the old-style APIs like Circuit.if which rely on Provable<T> stuff like toFields, don't take the Provable as input, but instead rely on magically figuring out toFields, first by looking for instance methods toFields / fromFields and then by other means. This won't currently work for Structs, unless they are manually given those instance methods.

I would actually suggest requiring the Provable argument, as we do in most other APIs already:

Circuit.if(someBool, MyStruct, structA, structB)

(this is already one of the supported function signatures; I'd make it the only one)

MartinMinkov commented 1 year ago

Yup! I ran into this while refactoring PublicKey :sweat: That sounds good!

mitschabaude commented 2 weeks ago

now I don't think the internal types should be Struct anymore, but we should have a nice internal API to create provable types, and put that type on say PublicKey.provable where it doesn't interfere at all with designing the interface to the PublicKey class as it makes sense for public keys.

and to solve the issue Martin mentioned, we should have a consistent way of getting the .provable just from the value for all our internal types (e.g. value.constructor), and create a sum type of all "types that we know the provable shape of", so we can accept those at the type level