Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

public-vm: create an api to add generic tuple lookups in the flavor #2995

Closed
Tracked by #3309
Maddiaa0 opened this issue Oct 24, 2023 · 0 comments · Fixed by #3880
Closed
Tracked by #3309

public-vm: create an api to add generic tuple lookups in the flavor #2995

Maddiaa0 opened this issue Oct 24, 2023 · 0 comments · Fixed by #3880
Assignees
Labels
C-avm Component: AVM related tickets (aka public VM)

Comments

@Maddiaa0
Copy link
Member

Overview

One of the main primitives required when constructing the vm is a generic api for lookups. Take for example the following PIL code, taken from the riscv bitwise operations machine:

https://github.com/powdr-labs/powdr/blob/88858fe6264916b3cd587c4ade13b66dd659cd2f/std/binary.asm#L42

This asserts that for every row, the lhs must be a lookup into the rhs.

As the code above is a submachine, I am assuming that the relation has a relevant selector. Perhaps the latch?

Perhaps the above example can be represented with the above:

        std::vector<HandleType> lookup_lhs() override
        {
           // Show the left hand side of the operation here
            std::tuple x = { operation_id_shift, A_byte, B_byte, C_byte }
            return {
                x,
            };
        };

        std::vector<HandleType> lookup_rhs() override
        {
            // Right hand side of the operation here
            // These columns should all be pre computed tables, hence we will need a way to mark them as such 
            // So that they can be part of the vm program's preprocessing key?
            std::tuple y = { P_operation, P_A, P_B, P_C }
            return {
                y,
            };
        };
@Maddiaa0 Maddiaa0 self-assigned this Oct 24, 2023
@github-project-automation github-project-automation bot moved this to Todo in A3 Oct 24, 2023
@jeanmon jeanmon added the C-avm Component: AVM related tickets (aka public VM) label Nov 15, 2023
@dbanks12 dbanks12 assigned Rumata888 and unassigned Maddiaa0 Nov 21, 2023
@dbanks12 dbanks12 moved this from Todo to In Progress in A3 Nov 21, 2023
@dbanks12 dbanks12 assigned Maddiaa0 and unassigned Rumata888 Jan 2, 2024
Maddiaa0 added a commit that referenced this issue Jan 9, 2024
depends on : https://github.com/AztecProtocol/powdr/pull/37/files

Lookups allow us to assert that values in a set of columns equal some
values in another set of columns.


This approach uses the log derivative method to perform lookups, where
the lookup relation requires four extra columns ( as well as the read
and write columns ) to function.
- One selector column to initiate adding a value into the READ side of
the lookup table ( lhs in pil )
- One selector column to initiate adding a value into the WRITE side of
the lookup table ( rhs in pil ) - { adding to the table }
- One selector column to compute inverses - ( helper column )
- One column to store the number of times a WRITE term is read - (
helper column )

The selector columns will need to be defined manually - as in the
`ToyAvm` example.
The inverse column and the counts columns are automatically included by
the code gen. ( this means there are two extra columns per lookup (
which is a little bit inefficient; but will do for now ).

The name of the inverse column is decided by the attribute tag
`#[attribute]` above the lookup - which is required.
The name of the counts column is `${attribute}_counts`. 

Note: that in the circuit builder you are currently required to set the
counts column value manually.

syntax:
```pil
  #[lookup_xor] // attribute
    q_xor { xor_a, xor_b, xor_c } in q_xor_table { table_xor_a, table_xor_b, table_xor_c };
    // lhs selector, lhs columns        // rhs selector, rhs columns

```

closes: #2995


Co-authored-by: Rumata888 <[email protected]>

---------

Co-authored-by: Jean M <[email protected]>
@github-project-automation github-project-automation bot moved this from In Progress to Done in A3 Jan 9, 2024
AztecBot pushed a commit to AztecProtocol/barretenberg that referenced this issue Jan 10, 2024
depends on : https://github.com/AztecProtocol/powdr/pull/37/files

Lookups allow us to assert that values in a set of columns equal some
values in another set of columns.


This approach uses the log derivative method to perform lookups, where
the lookup relation requires four extra columns ( as well as the read
and write columns ) to function.
- One selector column to initiate adding a value into the READ side of
the lookup table ( lhs in pil )
- One selector column to initiate adding a value into the WRITE side of
the lookup table ( rhs in pil ) - { adding to the table }
- One selector column to compute inverses - ( helper column )
- One column to store the number of times a WRITE term is read - (
helper column )

The selector columns will need to be defined manually - as in the
`ToyAvm` example.
The inverse column and the counts columns are automatically included by
the code gen. ( this means there are two extra columns per lookup (
which is a little bit inefficient; but will do for now ).

The name of the inverse column is decided by the attribute tag
`#[attribute]` above the lookup - which is required.
The name of the counts column is `${attribute}_counts`. 

Note: that in the circuit builder you are currently required to set the
counts column value manually.

syntax:
```pil
  #[lookup_xor] // attribute
    q_xor { xor_a, xor_b, xor_c } in q_xor_table { table_xor_a, table_xor_b, table_xor_c };
    // lhs selector, lhs columns        // rhs selector, rhs columns

```

closes: AztecProtocol/aztec-packages#2995


Co-authored-by: Rumata888 <[email protected]>

---------

Co-authored-by: Jean M <[email protected]>
michaelelliot pushed a commit to Swoir/noir_rs that referenced this issue Feb 28, 2024
depends on : https://github.com/AztecProtocol/powdr/pull/37/files

Lookups allow us to assert that values in a set of columns equal some
values in another set of columns.


This approach uses the log derivative method to perform lookups, where
the lookup relation requires four extra columns ( as well as the read
and write columns ) to function.
- One selector column to initiate adding a value into the READ side of
the lookup table ( lhs in pil )
- One selector column to initiate adding a value into the WRITE side of
the lookup table ( rhs in pil ) - { adding to the table }
- One selector column to compute inverses - ( helper column )
- One column to store the number of times a WRITE term is read - (
helper column )

The selector columns will need to be defined manually - as in the
`ToyAvm` example.
The inverse column and the counts columns are automatically included by
the code gen. ( this means there are two extra columns per lookup (
which is a little bit inefficient; but will do for now ).

The name of the inverse column is decided by the attribute tag
`#[attribute]` above the lookup - which is required.
The name of the counts column is `${attribute}_counts`. 

Note: that in the circuit builder you are currently required to set the
counts column value manually.

syntax:
```pil
  #[lookup_xor] // attribute
    q_xor { xor_a, xor_b, xor_c } in q_xor_table { table_xor_a, table_xor_b, table_xor_c };
    // lhs selector, lhs columns        // rhs selector, rhs columns

```

closes: AztecProtocol#2995


Co-authored-by: Rumata888 <[email protected]>

---------

Co-authored-by: Jean M <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-avm Component: AVM related tickets (aka public VM)
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

3 participants