feat: Add `Brillig` opcode to introduce custom non-determinism to ACVM #152

kevaundray · 2023-03-24T17:44:58Z

Related issue(s)

(If it does not already exist, first create a GitHub issue that describes the problem this Pull Request (PR) solves before creating the PR and link it here.)

Resolves (link to issue)

Description

This is a generalization of our directive functions. Right now we have directives which are defined at compile time in the code, this VM will allow us to instead have the user write the non-deterministic in their frontend like Noir , this gets compiled down to this bytecode and then ran on the VM.

From conversations with Guillaume, the directive will then look like:

struct ByteCodeDirective{
   inputs : Vec<Expression>,
   outputs : Vec<Witness>,
   bytecode : Vec<Opcode> 
}

Summary of changes

(Describe the changes in this PR. Point out breaking changes if any.)

Dependency additions / changes

(If applicable.)

Test additions / changes

(If applicable.)

Checklist

I have tested the changes locally.
I have formatted the changes with Prettier and/or cargo fmt with default settings.
I have linked this PR to the issue(s) that it resolves.
I have reviewed the changes on GitHub, line by line.
I have ensured all changes are covered in the description.

Additional context

(If applicable.)

kevaundray · 2023-03-24T17:55:25Z

Also spoke with Guillaume and it seems we could get the Oracle opcode into this instruction set rather than in the ACIR opcode set.

We have two main goals for this:

Have this working with invert directive
Have it working with Oracle directive however we choose to integrate it

The invert directive will be a full e2e test that shows that we can replace our current directives with this bytecode. Integrating the other directives will be fairly straightforward

- use ValueKind - refactor opcodes needed

* add serialization for brillig * cargo fmt

* solve the brillig directive * move brilling_bytecode out of acvm * go back to correct process_opcodes * cargo fmt * switch to using insert_witness method

- RegisterIndex -> RegisterMemIndex

* trap opcode in Opcode enum * process trap opcode

* brillig jmp process_opcode * making jump test * starting jmp opcode test * test brillig jumps * debug cleanup * remove comments from Value in vm

* jmp if not opcode and test * jmp if not opode and test * fix jmpifnot test * carog fmt * remove unnecessary registers in jmpif test * cargo fmt

* MOV opcode in brillig and a basic test * cargo fmt * fixed move to not only move source into dest, not a full swap * cargo fmt

* add lt and lte comparisons to BinaryOp + tests * briefly delete test * cargo fmt * temp remove test

acir/src/circuit/brillig.rs

* chore: make fields private on `Value` and `RegisterIndex` * Update brillig_bytecode/src/value.rs --------- Co-authored-by: kevaundray <[email protected]>

TomAFrench · 2023-05-23T14:23:27Z

Once #152 (comment) is resolved either way then I can remove the block from this PR.

If we want to merge this today in UK time then we should prioritise this so we can resolve before I go to bed (otherwise I'll have to merge in the morning).

Co-authored-by: Tom French <[email protected]>

kevaundray · 2023-05-23T14:44:09Z

Just resolved this

resolved

brillig_vm/src/value.rs

TomAFrench

one nit

kevaundray added 2 commits March 24, 2023 17:44

cargo.toml

3c71368

add initial code for non deterministic vm

7ce1431

kevaundray changed the title ~~Add initial code for non-deterministic vm~~ feat: Add initial code for non-deterministic vm Mar 24, 2023

fix clippy

5218be7

kevaundray and others added 25 commits March 27, 2023 17:48

remove unary op -- can be simulated with binary op

87c28d1

refactor API:

7dfa344

- use ValueKind - refactor opcodes needed

re-export brillig bytecode

e93ae96

add brillig

a8f553e

brillig is now re-exported from acir

0c32dcb

use acir_field instead of acir

0229519

wip

12b7f51

Merge remote-tracking branch 'origin/master' into kw/bytecode-vm

a2acde2

add directive todo

327fe75

feat: Add serialization for brillig bytecode (#158)

5cb9f3a

* add serialization for brillig * cargo fmt

feat: Solve Brillig Directive (#159)

ca4fe1a

* solve the brillig directive * move brilling_bytecode out of acvm * go back to correct process_opcodes * cargo fmt * switch to using insert_witness method

RegisterIndex -> RegisterMemIndex

5f2ebf1

- use Label

92a8f77

- RegisterIndex -> RegisterMemIndex

export RegisterMemIndex

b57bf11

conversion func for registerIndex

12a53df

add jmpifnot

824ccc4

feat: Add trap opcode (#161)

0b7bd3d

* trap opcode in Opcode enum * process trap opcode

feat: Brillig JMP and JMPIF (#162)

cb70b7d

* brillig jmp process_opcode * making jump test * starting jmp opcode test * test brillig jumps * debug cleanup * remove comments from Value in vm

fix to stop VM on Trap opcode (#163)

59eb20a

feat: JMPIFNOT (#165)

3a197aa

* jmp if not opcode and test * jmp if not opode and test * fix jmpifnot test * carog fmt * remove unnecessary registers in jmpif test * cargo fmt

feat: Mov Opcode in Brillig (#166)

01d21c6

* MOV opcode in brillig and a basic test * cargo fmt * fixed move to not only move source into dest, not a full swap * cargo fmt

feat: Comparison Binary Ops (#167)

dcae6b3

* add lt and lte comparisons to BinaryOp + tests * briefly delete test * cargo fmt * temp remove test

move Brillig from being a directive to an Opcode (#169)

d1e9c59

bootstrap register allocation

2ca6648

add bootstrap hack

404721e

TomAFrench and others added 4 commits May 23, 2023 13:34

Apply suggestions from code review

342c389

fix: properly handle brillig_bytecode default feature

3002f99

Update acvm/src/pwg.rs

a166a50

Apply suggestions from code review

f7574af

TomAFrench changed the title ~~feat: Add initial code for non-deterministic vm~~ feat: Add Brillig opcode which introduces non-determinism to ACVM May 23, 2023

TomAFrench changed the title ~~feat: Add Brillig opcode which introduces non-determinism to ACVM~~ feat: Add Brillig opcode to introduce custom non-determinism to ACVM May 23, 2023

chore: add brillig_bytecode to publish.yml

f23f1c8

TomAFrench reviewed May 23, 2023

View reviewed changes

acir/src/circuit/brillig.rs Outdated Show resolved Hide resolved

chore: make Value and RegisterIndex fields private (#308)

4e99d0b

* chore: make fields private on `Value` and `RegisterIndex` * Update brillig_bytecode/src/value.rs --------- Co-authored-by: kevaundray <[email protected]>

kevaundray and others added 6 commits May 23, 2023 15:34

Update brillig_bytecode/src/lib.rs

aba2d1a

Co-authored-by: Tom French <[email protected]>

Update brillig_bytecode/Cargo.toml

69bdf4f

Co-authored-by: Tom French <[email protected]>

Update acvm/src/pwg.rs

cc2a096

Co-authored-by: Tom French <[email protected]>

Update acir/src/circuit/brillig.rs

6bb622d

Co-authored-by: Tom French <[email protected]>

rename brillig_bytecode to brillig_vm

fc5b3c0

change UnresolvedBrillig to UnresolvedBrilligCall

bde7784

kevaundray mentioned this pull request May 23, 2023

Add more documentation on how to handle unresolved Brillig calls #309

Closed

TomAFrench reviewed May 23, 2023

View reviewed changes

brillig_vm/src/value.rs Outdated Show resolved Hide resolved

Update brillig_vm/src/value.rs

5af7637

TomAFrench approved these changes May 23, 2023

View reviewed changes

TomAFrench suggested changes May 23, 2023

View reviewed changes

chore: rename unresolved_brilligs to unresolved_brillig_calls

85c9eb0

TomAFrench approved these changes May 23, 2023

View reviewed changes

kevaundray added this pull request to the merge queue May 23, 2023

Merged via the queue into master with commit 3c6740a May 23, 2023

github-actions bot mentioned this pull request May 23, 2023

chore: Release 0.13.0 #293

Merged

kevaundray mentioned this pull request May 24, 2023

Implement Non-deterministic VM (Brillig) #191

Closed

1 task

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: Add `Brillig` opcode to introduce custom non-determinism to ACVM #152

feat: Add `Brillig` opcode to introduce custom non-determinism to ACVM #152

kevaundray commented Mar 24, 2023 •

edited

Loading

kevaundray commented Mar 24, 2023

TomAFrench commented May 23, 2023

kevaundray commented May 23, 2023

TomAFrench left a comment

feat: Add Brillig opcode to introduce custom non-determinism to ACVM #152

feat: Add Brillig opcode to introduce custom non-determinism to ACVM #152

Conversation

kevaundray commented Mar 24, 2023 • edited Loading

Related issue(s)

Description

Summary of changes

Dependency additions / changes

Test additions / changes

Checklist

Additional context

kevaundray commented Mar 24, 2023

TomAFrench commented May 23, 2023

kevaundray commented May 23, 2023

TomAFrench left a comment

Choose a reason for hiding this comment

feat: Add `Brillig` opcode to introduce custom non-determinism to ACVM #152

feat: Add `Brillig` opcode to introduce custom non-determinism to ACVM #152

kevaundray commented Mar 24, 2023 •

edited

Loading