Transaction signature aggregation about fuel-specs HOT 7 OPEN

Summary of some offline discussion. It looks like doing BLS signature aggregation for all signatures possible is quite challenging and may not be of much benefit. However, signature aggregation is petty good for witnesses for InputType.Coin inputs (i.e. just simple EOA-owned coins). I suggest adding a new transaction type that is only a simple transfer of a coin UTXO to a single account (let's say 2-in-2 out for enough flexibility to be useful), and have a super-compact representation.

I also suggest segregating these transactions to a different "part" of the block (kind of like the different roots in Fuel v1). So that all transactions in this one part are all "simple transfers with BLS aggregate signatures." This would also allow much bigger batches over which to aggregate potentially.

from fuel-specs.

I don't think cross-transaction aggregate signatures will ever be used in our system. Per-transaction aggregate signatures maybe, but those are of much less value. This issue goes beyond the IVG and affects the VM (see https://ethresear.ch/t/adding-cross-transaction-bls-signature-aggregation-to-ethereum/7844 for more info).

The issue with cross-transaction aggregate signatures is that the aggregator (and later on the fraud prover in the IVG) needs to know every message that is signed over (or more specifically, the message hash).

Consider the case of token transfers. There are others, but this is the simplest. Since we don't have a concept of EOAs, we need token transfers from a user account to be accompanied by a digital signature. That signature would be over something like hash(<domain separator magic bytes> ++ sender ++ receiver ++ token id ++ amount ++ nonce). This would be embedded in the contract bytecode, and so is a one-time calldata cost on contract deployment. If you want to aggregate these signatures, then you need to provide the message hash in the transaction: you can't expect the block producers and provers to understand arbitrary code to pull out the message hashes from the bytecode. That's 32 bytes, basically nullifying all your gains from aggregate signatures.

from fuel-specs.

@adlerjohn can you describe the fraud proving mechanics for verifying witness data in the normal case of a say a non-script/contract transfer of tokens in Fuel?

Is the current witness fraud prover model from V1 not valid here at all, considering it seems you are saying hash data wont be known at that level, and is tucked away inside the bytecode and VM's?

I'll comment on the possibility of whether I think this is possible once I get a better understanding of these embedded cases. I actually still think it's possible though.

from fuel-specs.

describe the fraud proving mechanics for verifying witness data in the normal case of a say a non-script/contract transfer of tokens in Fuel

Currently the FuelVM only supports a single asset. Tokens are implemented as a smart contract in the FuelVM, so any IVG would be over the FuelVM execution trace.

Is the current witness fraud prover model from V1 not valid here at all, considering it seems you are saying hash data wont be known at that level, and is tucked away inside the bytecode and VM's?

Right. With Fuel v1 the only witness type we supported was "sign over the whole tx." With Fuel v2 we will support witness data for different things, e.g. signing to authorize a token transfer, or #40, so we fundamentally can't aggregate those signatures without re-introducing huge overhead in the form of message hashes.

from fuel-specs.

@adlerjohn so in that case you can absolutely just play the game over an execution trace to derive any signed over hash, the additional merkle commitments would allow you to map this I believe.

So long as 1) those hashes are derivable via a IVG (execution trace or otherwise), and 2) the reference to the committed hash/public key etc. in the VM is clear, I still believe a facsimile of model could be used here.

If the hash is deeply embedded in logic that still shouldn't matter, you simply have to provide that execution step which would expect that specific hash to appear, you would have to maybe have more by way of an index or something to specify what aggregate signature witness you are referencing. But I think my game over the proposed root would be just fine.

32 bytes in those cases is also fine, that would still be half of the 64 byte requirement. A 50% reduction there is not nothing.

I do still think it's possible. Even if it's not for certain cases as well, I do think it could be leveraged for more broader cases, and cover 70-80% of witness cases in Fuel, which ultimately would still achieve our compression goals.

from fuel-specs.

so in that case you can absolutely just play the game over an execution trace to derive any signed over hash, the additional merkle commitments would allow you to map this I believe.

No, an interactive verification game only works for a disputable assertion on the trace. Signature aggregation does not occur at the level of the VM, so it's not disputable via an IVG of the VM. In other words,

1. those hashes are derivable via a IVG (execution trace or otherwise)

will never hold true (put another way, we agree that the proposed scheme does not work).

Recall that to verify an aggregate signature you need 1) the signature 2) the pubkeys and 3) the message (hashes). What if a malicious block proposer makes a contract in the FuelVM that does a EXPECT_BLS_SIGNATURE operation 1 million times, all on different messages? Then you need to extract all those 1 million message hashes all at once. Intuitively: your idea of limiting the number of transactions per batch is specifically to limit the maximum number of messages (and pubkeys), but this constraint is no longer enforced if witnesses are no longer tied to inputs.

Another thing to keep in mind is that in the above scenario, how would you extract the 1 million EXPECT_BLS_SIGNATURE operations from a valid trace? There's nothing to dispute and thus nothing to do an IVG over. An IVG only works to dispute a commitment to an invalid trace. It doesn't give you the location of every operation of a certain type. You could extract them non-interactively, but as above, that is an exploit vector.

32 bytes in those cases is also fine, that would still be half of the 64 byte requirement. A 50% reduction there is not nothing.

You also need to add bytes to account for the overhead of flagging some witness data as signing over the tx vs signing for a predicate/script/contract. Those bytes add up because every since witness needs them to discriminate.

from fuel-specs.

In this case, I'd suggest we offer a BLS fast lane option at the TX level in future, to allow for BLS signed simple transfers of base level assets and tokens. Using smart-contracts however, can remain as a per-transaction signature option.

from fuel-specs.