feat!: add support for u1 in the avm circuit & witgen by dbanks12 · Pull Request #8570 · AztecProtocol/aztec-packages

dbanks12 · 2024-09-16T16:22:58Z

Circuit & witgen updates for u1
Simulator & transpiler updates for u1
Includes modification to the ToRadix AVM opcode to include the output_bits flag (is output in bits mode).
Includes modification to the ToRadix AVM and Brillig opcode's radix operand to be a memory offset instead of an immediate.
AVM comparator instructions (EQ/LT/LTE) now output U1.

radix_offset's read is not constrained due to #8603

dbanks12 · 2024-09-16T16:23:13Z

chore: clean up avm transpiler after simplifications from u1 #8607
feat!: add support for u1 in the avm circuit & witgen #8570 👈
master

This stack of pull requests is managed by Graphite. Learn more about stacking.

Join @dbanks12 and the rest of your teammates on Graphite

dbanks12 · 2024-09-17T17:32:29Z

    let num_bits = val.num_bits();
-    if num_bits < 8 {
+    if num_bits <= 8 {
        8
-    } else if num_bits < 16 {
+    } else if num_bits <= 16 {
        16
-    } else if num_bits < 32 {
+    } else if num_bits <= 32 {
        32
-    } else if num_bits < 64 {
+    } else if num_bits <= 64 {
        64
-    } else if num_bits < 128 {
+    } else if num_bits <= 128 {
        128


This was just a bug

dbanks12 · 2024-09-17T17:34:23Z

 {
-    std::string bytecode_hex = to_hex(OpCode::ADD_16) +   // opcode ADD
-                               "00"                       // Indirect flag
-                               "01"                       // U8
+    std::string bytecode_hex = to_hex(OpCode::ADD_16) + // opcode ADD
+                               "00"                     // Indirect flag
+                               + to_hex(AvmMemoryTag::U8) +
                               "0007"                     // addr a 7


I changed this across the whole file so that we aren't using magic numbers

dbanks12 · 2024-09-17T17:40:20Z

+template <typename T>
+    requires(std::unsigned_integral<T>)
+std::string to_hex(T value)
+{
+    std::ostringstream stream;
+    auto num_bytes = static_cast<uint64_t>(sizeof(T));
+    auto mask = static_cast<uint64_t>((static_cast<uint128_t>(1) << (num_bytes * 8)) - 1);
+    auto padding = static_cast<int>(num_bytes * 2);
+    stream << std::setfill('0') << std::setw(padding) << std::hex << (value & mask);
+    return stream.str();
+}
+
+std::string to_hex(bb::avm_trace::AvmMemoryTag tag);


Moved from opcode.hpp because it's now useful for memory tags too

dbanks12 · 2024-09-17T17:45:30Z

+type IntegralClass = typeof Uint1 | typeof Uint8 | typeof Uint16 | typeof Uint32 | typeof Uint64 | typeof Uint128;
+
+describe.each([Uint1])('Integral Types (U1 only)', (clsValue: IntegralClass) => {
+  describe(`${clsValue.name}`, () => {
+    it(`Should construct a new ${clsValue.name} from a number`, () => {
+      const x = new clsValue(1);
+      expect(x.toBigInt()).toStrictEqual(1n);
+    });


Not sure it's worth spending the effort at this time to combine this with the test cases for non-U1 types since they use values other than 0 and 1.

dbanks12 · 2024-09-17T17:46:02Z

    public toBuffer(): Buffer {
+      if (bits < 8) {
+        return toBufferBE(this.n, 1);
+      }
      return toBufferBE(this.n, bits / 8);
    }


Still need a whole byte for a Uint1

IlyasRidhuan · 2024-09-17T20:41:17Z

+                                     uint32_t dst_offset,
+                                     uint32_t radix_offset,
+                                     uint32_t num_limbs,
+                                     uint8_t output_bits)


Is there a reason this isn't of type bool?

Just would be a one-off I think. Wasn't sure if I should leave it as a byte which is what it is in the wire format for the instruction. Instruction wire format operates in bytes.

But I could certainly change this to be type bool

TomAFrench · 2024-09-17T20:48:51Z

Hey all, this shouldn't cause a problem for noir syncing.

Using an older version of bb with the new brillig format will result in it misinterpreting the memory address as an immediate value but as bb doesn't use the brillig for anything, it won't cause any unexpected behaviour.

jeanmon

LGTM! Very good job! Check my comments.

jeanmon · 2024-09-18T11:13:23Z

    // This holds the product over the integers
-    pol PRODUCT = a_lo * b_lo + LIMB_BITS_POW * partial_prod_lo + MAX_BITS_POW * (partial_prod_hi + a_hi * b_hi);
+    // (u1 multiplication only cares about a_lo and b_lo)
+    pol PRODUCT = a_lo * b_lo + (1 - u1_tag) * (LIMB_BITS_POW * partial_prod_lo + MAX_BITS_POW * (partial_prod_hi + a_hi * b_hi));


We should not need the exception for u1, ie., the term (1 - u1_tag) can be removed I think.

Without that exception for u1, I believe a_hi and b_hi are underconstrained since LIMB_BITS_POW is 0. Or am I wrong?

dbanks12 force-pushed the db/u1-avm-circuit branch 2 times, most recently from 876c708 to 34a7a3a Compare September 16, 2024 17:31

dbanks12 marked this pull request as ready for review September 16, 2024 17:52

dbanks12 requested review from IlyasRidhuan, Maddiaa0, fcarreiro and jeanmon as code owners September 16, 2024 17:52

dbanks12 removed the request for review from Maddiaa0 September 16, 2024 17:52

dbanks12 force-pushed the db/u1-avm-circuit branch from 34a7a3a to 8d63104 Compare September 16, 2024 18:11

fcarreiro reviewed Sep 16, 2024

View reviewed changes

Comment thread yarn-project/simulator/src/avm/avm_memory_types.ts Outdated

Comment thread barretenberg/cpp/src/barretenberg/vm/avm/trace/trace.cpp

dbanks12 force-pushed the db/u1-avm-circuit branch from 8d63104 to f45b6d5 Compare September 16, 2024 20:49

dbanks12 marked this pull request as draft September 16, 2024 20:49

dbanks12 requested a review from sirasistant September 17, 2024 01:58

dbanks12 force-pushed the db/u1-avm-circuit branch from f45b6d5 to 1f4b7b9 Compare September 17, 2024 02:01

sirasistant reviewed Sep 17, 2024

View reviewed changes

Comment thread noir/noir-repo/compiler/noirc_evaluator/src/brillig/brillig_ir/codegen_intrinsic.rs

dbanks12 force-pushed the db/u1-avm-circuit branch 2 times, most recently from cbdd5f0 to e2ddcf1 Compare September 17, 2024 17:28

dbanks12 commented Sep 17, 2024

View reviewed changes

dbanks12 force-pushed the db/u1-avm-circuit branch from e2ddcf1 to c34a75b Compare September 17, 2024 17:35

dbanks12 commented Sep 17, 2024

View reviewed changes

dbanks12 force-pushed the db/u1-avm-circuit branch 2 times, most recently from 54870c3 to 6d7d35f Compare September 17, 2024 17:44

dbanks12 commented Sep 17, 2024

View reviewed changes

dbanks12 force-pushed the db/u1-avm-circuit branch from 6d7d35f to 62c53fc Compare September 17, 2024 18:09

dbanks12 marked this pull request as ready for review September 17, 2024 18:27

dbanks12 requested review from TomAFrench and vezenovm as code owners September 17, 2024 18:27

dbanks12 force-pushed the db/u1-avm-circuit branch from e6741b3 to 81d6194 Compare September 17, 2024 20:37

IlyasRidhuan reviewed Sep 17, 2024

View reviewed changes

jeanmon approved these changes Sep 18, 2024

View reviewed changes

dbanks12 force-pushed the db/u1-avm-circuit branch 2 times, most recently from 5066620 to e4c8a5b Compare September 18, 2024 15:22

dbanks12 enabled auto-merge (squash) September 18, 2024 15:45

feat: add support for u1 in the avm circuit & witgen

cc3d469

dbanks12 force-pushed the db/u1-avm-circuit branch from e4c8a5b to cc3d469 Compare September 18, 2024 15:46

dbanks12 merged commit 1785737 into master Sep 18, 2024

dbanks12 deleted the db/u1-avm-circuit branch September 18, 2024 16:42

This was referenced Sep 18, 2024

chore(master): Release 0.56.0 #8597

Merged

feat: Sync from aztec-packages noir-lang/noir#6104

Closed

feat: Sync from aztec-packages noir-lang/noir#6109

Closed

feat: Sync from aztec-packages noir-lang/noir#6151

Merged

noirwhal mentioned this pull request Sep 25, 2024

chore: Release Noir(0.35.0) noir-lang/noir#6030

Merged

noirwhal mentioned this pull request Oct 3, 2024

chore: Release Noir(0.36.0) noir-lang/noir#6213

Merged

dbanks12 mentioned this pull request Oct 7, 2024

[EPIC] AVM instruction set and wire format are finalized #9059

Closed

noirwhal mentioned this pull request Oct 23, 2024

chore: Release Noir(0.37.0) noir-lang/noir#6321

Merged

noirwhal mentioned this pull request Oct 31, 2024

chore: Release Noir(0.38.0) noir-lang/noir#6422

Merged

noirwhal mentioned this pull request Nov 8, 2024

chore: Release Noir(0.39.0) noir-lang/noir#6484

Merged

noirwhal mentioned this pull request Nov 19, 2024

chore: Release Noir(1.0.0-beta.0) noir-lang/noir#6559

Closed

Conversation

dbanks12 commented Sep 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dbanks12 commented Sep 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

TomAFrench commented Sep 17, 2024

Uh oh!

jeanmon left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

dbanks12 commented Sep 16, 2024 •

edited

Loading

dbanks12 commented Sep 16, 2024 •

edited

Loading