Transaction signature aggregation

[SilentCicero]

Motivation:

Presently, Fuel uses secp256k1 elliptic signatures for witness verification in Fuel. This requires including 65 byte signatures for each transaction. Ethereum is currently very expensive, and every byte ends up costing users greatly.

Fuel would like to use BLS12-381 when ready with our smart-contract system, this would allow for the removal of a vast majority of signature data in Fuel blocks.

Problem Point:

One issue with using aggregate signatures in the current Fuel architecture is that Fuel uses a system of both block producer included metadata (block number, transaction index, output index, 5-7 bytes) and UTXO hash data (32 bytes) for each input spent. To save data, we remove the UTXO hash data as it is implied by verification reduction from the metadata.

This makes verifying and determining has the witness signed over the provided data straight forward.

1) Bring each full transaction proof for each input 2) Reduce the hash for that input provided 3) Reduce signature over provided transaction data with hashes derived

When we introduce aggregate signatures, this becomes more problematic, because if you remove the transaction data and the signature data, you must provide all data and all public keys for signed over by the aggregate signature. This means bringing the transaction proofs for all inputs spent in all transactions signed over by that aggregate signature proof (potentially 32 * 8 transaction proofs to validate one signature in a single round fraud proof). This would be extremely costly to reduce in one round.

Put simply, you cannot use a single round fraud proof style game to validate signatures for BLS in Fuel.

Proposal:

We would like to use aggregate signatures like BLS12-381 to remove the signature data in Fuel and enforce signature correctness using a very simple interactive verification game, which both allows the removal of UTXO hashes from Fuel transactions and signature data on a per-transaction bases.

One aggregate signature will be provided for groupings of 32 or less transactions (less in the case a block has less than 32 transactions).

One Merkle root will be posted, with the leafs of that tree being the transactionId's for each of the transactions (note, this will be used for the IVG) and a hash of the list of public keys used for that transaction.

Interactive Verification Game:

If an aggregate signature is incorrect in a group:

If any of the committed UTXO data does not derive (invalid internal Merkle root): 1) Player 1 (fraud prover) will begin the game, and ask Player 2 (block producer) to reveal any of the requested transaction index leafs within that group. 2) Once that leaf is revealed, Player 1 can show that either the transactionId/public keys committed to in the Merkle root is either valid by single round fraud proving or fraudulent (i.e. not what the output specifies) 3) This can be used to show a single transaction has not been appropriately witnessed, without having to provide all public keys and UTXO hashes per group on-chain.

If the committed data is now derivable or known and incorrect: 1) All public keys, transactionId's and UTXO hashes used for that commitment/group are provided (verified by the Merkle root derivation) 2) The aggregate signature is can be deemed valid or invalid to any of the public keys provided

Notes:

Currently, Ethereum only supports a form of BLS via the altbn_128 precompiles with less than 100 bits of security. Which we have deemed not secure enough for Fuel.

BLS12-381 is on the way with more than 100 bits of security, but will likely not be ready for use until end of year 2021 at best.

[adlerjohn]

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.

[SilentCicero]

@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.

[adlerjohn]

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.

[SilentCicero]

@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.

[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.

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.

[SilentCicero]

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.

[adlerjohn]

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.