Vectorize Resource Logic Circuits

RM
1

Abstract

Currently resource logic circuits like the transfer authorization circuit take a single witness and output the corresponding resource logic instance. This RFC proposes to instead make resource logic circuits take a vector of witnesses as inputs and output a corresponding equinumerous vector of resource logic instances. This will not reduce proving times, but it will reduce the number of logic proofs that have to be rolled up by aggregators. The example code here is done in Noir, but the main point might apply to the RISC Zero resource logic circuits.

Motivation

What resource logic circuits do today

A resource logic instance takes a single witness as a private input and outputs a corresponding resource logic instance:

fn main(witness: TransferAuthWitness) -> pub Field {
    witness._constrain().digest()
}

The inefficiencies this creates

A transaction that consumes 4 resources of the same logic (e.g. USDC) and creates 4 resource of that same logic will require 8 resource logic proofs. This means that 8 resource logic proofs and a single compliance proof now need to be rolled up into a single proof. The more the proofs that need to be rolled up, the higher the proving time.

New vectorized resource logic circuit

The following change makes the resource logic circuit receive a vector/array of transfer authorization witnesses and output an equinumerous vector/array of resource logic instances.

global BATCH_SIZE: u32 = 4;

fn main(witness: [TransferAuthWitness; BATCH_SIZE]) -> pub [Field; BATCH_SIZE] {
    witness.map(|x| x._constrain().digest())
}

Note that the original circuit was essentially multiplied by BATCH_SIZE. Moreover, the processing of each witness in the vector/array is completely independent of the processing of other witnesses. Also for Noir, probably a u32 indicating how many array slots are being used might also be needed.

Impact on total proving time for rollups

Instead of transactions containing as many resource logic proofs as there are consumed resources and created resources, transactions will now only contain as many proofs as there are distinct resource logics used in the transaction. For example, if a transaction only uses USDC resources, it will need only two proofs: one compliance proof and one resource logic proof. And for RISC Zero VM, this statement is true no matter how many resources are created or consumed.

So if the average transaction consumes 2 resources and creates 2 resources of the same logic, then instead of rolling up 5 proofs, only 2 proofs need to be aggregated. In the UltraHonk system, this would probably reduce the time spent aggregating proofs by a factor of 2.5x. All this being said, I do not know the shape of the average ARM transaction.

Impact on memory usage

Proving larger resource logic circuits is likely to use more memory. How problematic this is likely depends on the current memory usage of singleton resource logics.

2

Thank you for the writeup.

Firstly, let’s note that the proposed change is a protocol change. We would have to redesign how ARM works, how we verify proofs, how compliance circuit works, how resource <> logic proof correspondence is checked. Most importantly, it would shift the responsibility for ensuring that each resource has a correct logic proof from the protocol to the logic developer, which we don’t want.

Secondly, note that in a transaction, different entities may be creating proofs for different actions. That enables intent matching and retains information locality. So vectorized proofs would have to be either completely optional or exist only in the scope of a single action. We would have to ensure that vectorized proofs are not used when they shouldn’t. That would either happen on the protocol level (baked in the ARM checks) or done by the verifier, meaning they have to verify the correct usage of vectorized proofs judging the public data only.

Now let’s consider how it would work within a scope of a single action. Having 4 resources with the same logic, we would have to pass 4x inputs to the circuit and have 4x constraints + some potential extra for binding and ensuring correctness. If before we had 4 independent proofs that could be created in parallel (in theory, by completely independent GPU workers even), now we have one big proof. The increase in proving time may cancel out the aggregation advantage.

These optimizations are not relevant for UltraHonk since it doesn’t support variable size inputs. That means we can have neither single compliance proof nor single logic proof per action.

My take is that the potential advantage is minor in comparison to the costs of shifting the responsibility for ensuring security on the circuit developer, upgrading the protocol, and the limitations of the proposal.

1 Like