Reduce the cost of a bus interaction #2337
Comments
|
@Schaeff How hacky do you think it would be to do all of this in the linker? Basically, for each bus interaction, it would have to:
If both are false (which would hopefully be the case for most interactions), we can call a different PIL function that doesn't persist the folded tuple (reduces cost by 2x). Also, we could have a PIL function that adds 2 interactions at the cost of one. Would it be possible to chunk interactions in the linker? |
github-merge-queue bot
pushed a commit
that referenced
this issue
Jan 30, 2025
In our manual bus witgen, we currently assume that all second-stage witness columns in source order are always of the form: "folded" payloads for bus interaction 1, accumulators for bus interaction 1, "folded" payloads for bus interaction 2, ... As we implement #2337, this will no longer be the case (we might not have a folded payload, or there might be two interactions using the same accumulator). I tried to write code to find the accumulators from the polynomial identities, but I failed. So now, they are simply part of the `PhantomBusInteraction` annotation, which I think is fair. I still hope that we can automatically find the "folded" columns if they exist.
github-merge-queue bot
pushed a commit
that referenced
this issue
Feb 6, 2025
) Depends on #2428 and implements the second bullet point from #2337 (comment). **Test Coverage** Not sure why CI isn't running but currently `static_bus_multi.asm` passes test with `cargo run pil test_data/asm/static_bus_multi.asm --force --linker-mode bus --prove-with mock --field bn254` but NOT if `--field gl` with all else equal. See bottom for error from `--field gl`, which are obviously field extension constraints not passing for `folded` columns. **Questions** 1. Probably the biggest problem is with the degree-3 bound of Plonky3. The non batched version already has a degree of 3 (https://github.com/powdr-labs/powdr/blob/main/std/protocols/bus.asm#L86-L89). Therefore, this batched version has a degree of 4 and therefore doesn't work with Plonky3. The degree bound issue is also mentioned in #2337. 2. This comment (https://github.com/powdr-labs/powdr/blob/main/std/protocols/bus.asm#L52-L56) seems to say that `--field bn254` uses auto witgen and therefore manual witgen (which I'm trying to test here) isn't working. 3. According to this chunk (https://github.com/powdr-labs/powdr/blob/main/std/protocols/bus.asm#L60-L69) Does `--field bn254` correspond to no constraints for line 65 or whatsoever? With `--field bn254`, it seems that the accumulator adds up the folded columns but there's no constraint that the folded columns are correctly calculated from payload, id, and challenges. Am I missing something? (I think this might also explain why my `--field bn254` test has no constraint errors for `folded` columns, because they don't exist?) 4. I checked the following constraint errors against our field extension APIs and seems that `mul_ext`, `finger_print_inter_with_id`, `add_ext`, and `constrain_eq_ext` etc. are applied correctly. Any insights on whether `mock` works with `gl` and/or field extensions to start with? I still have a last resort of simply hand computing the values from the error below to see why it's not working with field extension... ``` ➜ powdr git:(bus-multi-interaction) ✗ cargo run pil test_data/asm/static_bus_multi.asm --force --linker-mode bus --prove-with mock --field gl [00:00:05 (ETA: 00:00:00)] ████████████████████ 100% - Starting... Witness generation took 5.538085s Writing ./commits.bin. Backend setup for mock... Setup took 0.0644265s Generating later-stage witnesses took 0.00s Machine main has 64 errors Error: Identity fails on row 0: main::folded_0 = std::prelude::challenge(0, 5) - (123 + (std::prelude::challenge(0, 1) * main::intermediate_fingerprint_0_2 + 11 * std::prelude::challenge(0, 2) * main::intermediate_fingerprint_1_2)); main::intermediate_fingerprint_0_2 = 16683533738167355631 main::intermediate_fingerprint_1_2 = 8619433688316392780 main::folded_0 = 14379784368020248175 std::prelude::challenge(0, 1) = 2206609067086327257 std::prelude::challenge(0, 2) = 11876854719037224982 std::prelude::challenge(0, 5) = 15794382300316794652 Error: Identity fails on row 0: main::folded_0_1 = std::prelude::challenge(0, 6) - (std::prelude::challenge(0, 2) * main::intermediate_fingerprint_0_2 + std::prelude::challenge(0, 1) * main::intermediate_fingerprint_1_2); main::intermediate_fingerprint_0_2 = 16683533738167355631 main::intermediate_fingerprint_1_2 = 8619433688316392780 main::folded_0_1 = 3590326197943317962 std::prelude::challenge(0, 1) = 2206609067086327257 std::prelude::challenge(0, 2) = 11876854719037224982 std::prelude::challenge(0, 6) = 18147521187885925800 Error: Identity fails on row 0: main::folded_1 = std::prelude::challenge(0, 7) - (456 + (std::prelude::challenge(0, 3) * main::intermediate_fingerprint_0_5 + 11 * std::prelude::challenge(0, 4) * main::intermediate_fingerprint_1_5)); main::intermediate_fingerprint_0_5 = 9393166848595961660 main::intermediate_fingerprint_1_5 = 14353807143801496692 main::folded_1 = 4794846700896775308 std::prelude::challenge(0, 3) = 18270091135093349626 std::prelude::challenge(0, 4) = 6185506036438099345 std::prelude::challenge(0, 7) = 7364705619221056123 Error: Identity fails on row 0: main::folded_1_1 = std::prelude::challenge(0, 8) - (std::prelude::challenge(0, 4) * main::intermediate_fingerprint_0_5 + std::prelude::challenge(0, 3) * main::intermediate_fingerprint_1_5); main::intermediate_fingerprint_0_5 = 9393166848595961660 main::intermediate_fingerprint_1_5 = 14353807143801496692 main::folded_1_1 = 16858051030421639712 std::prelude::challenge(0, 3) = 18270091135093349626 std::prelude::challenge(0, 4) = 6185506036438099345 std::prelude::challenge(0, 8) = 2404222719611925354 Error: Identity fails on row 0: main::folded_0_2 = std::prelude::challenge(0, 5) - (456 + (std::prelude::challenge(0, 1) * main::intermediate_fingerprint_0_8 + 11 * std::prelude::challenge(0, 2) * main::intermediate_fingerprint_1_8)); main::intermediate_fingerprint_0_8 = 16683533738167355631 main::intermediate_fingerprint_1_8 = 8619433688316392780 main::folded_0_2 = 14379784368020247842 std::prelude::challenge(0, 1) = 2206609067086327257 std::prelude::challenge(0, 2) = 11876854719037224982 std::prelude::challenge(0, 5) = 15794382300316794652 ... and 59 more errors ```
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We currently commit to two extension field elements per interaction (for GL: 2 cols / ext; for BB/M31: 4 cols / ext).
We can reduce them in two ways:
So overall, it could be reduced by a factor of 4, but it is not simple to implement in PIL without additional language features.
But what we could do today:
multi_sendfunction that generates one accumulator for two sends (for receives, we should only have one per machine to begin with). Use this in the ASM linker.The text was updated successfully, but these errors were encountered: