Support recursive ERC1271 signatures

[spengrah]

Currently, FarcasterDelegator assumes/requires that signatures produced on its behalf are true ECDSA signatures. Since the custom signature scheme treats the first 65 bytes of the signature bytes as the actual signature to validate, there is no room for other signature schemes that support ERC1271 contract signatures.

This constraint limits which accounts can serve as valid signers on a FarcasterDelegator's behalf. For example, it limits the accounts that can be delegated casting rights for a given fid. This will become especially limiting as smart accounts and AA proliferate.

One solution is to alter the custom signature scheme to more flexibly accept larger signatures. For example:

Offset	Length	Description
0	2	Length of signature, len
2	len	signature
2+ len	32	typehash
34 + len	any	EIP712 typed data

By allowing signature submitters to specify the length of their signatures within the signature itself, we can accommodate arbitrary other signature schemes within our own signature scheme, thereby supporting recursive ERC1271 contract signatures.

[spengrah]

In order to enable "recovery" of the signing contract address from an ERC-1271 signature, we can enforce something like Safe's treatment, which assumes that when v==0, the signing contract's address will be encoded into r:

https://github.com/safe-global/safe-smart-account/blob/2278f7ccd502878feb5cec21dd6255b82df374b5/contracts/Safe.sol#L285

if (v == 0) {
    // If v is 0 then it is a contract signature
    // When handling contract signatures the address of the contract is encoded into r
    currentOwner = address(uint160(uint256(r)));

    // Check that signature data pointer (s) is not pointing inside the static part of the signatures bytes
    // This check is not completely accurate, since it is possible that more signatures than the threshold are send.
    // Here we only check that the pointer is not pointing inside the part that is being processed
    if (uint256(s) < requiredSignatures.mul(65)) revertWithError("GS021");

    // The contract signature check is extracted to a separate function for better compatibility with formal verification
    // A quote from the Certora team:
    // "The assembly code broke the pointer analysis, which switched the prover in failsafe mode, where it is (a) much slower and (b) computes different hashes than in the normal mode."
    // More info here: https://github.com/safe-global/safe-smart-account/pull/661
    checkContractSignature(currentOwner, dataHash, signatures, uint256(s));

This is implemented in FarcasterDelegator here: https://github.com/Hats-Protocol/farcaster-delegator/blob/8fae7e6041e1cfed62acd41311104845412212fc/src/FarcasterDelegator.sol#L323

[spengrah]

After discussion with @gershido, I realized that we may be able to store the length of the extra ERC1271 signature bytes array inside of s instead of requiring an additional two byte prefix.

This is similar to how Safe's implementation utilizes s to store the pointer to (aka offset of) the extra signature bytes. Safe needs to do this because, as a multisig, there may be more than one actual signature included. The pointer stored in s is therefore the first byte after the final actual signature.

But since our case does not need to support multiple signatures, we know that the signature bytes will begin after the first signature — ie after the 65th byte — and so we don't need to store a pointer. Instead, we can store the length of the signature bytes.

Here is a modified schema:

Offset	Length: ECDSA sig	Length: contract sig	Description
0	32	32	r — if a contract signature, this should be the address of the signing contract
32	32	32	s — if a contract signature, this should contain the length of the signature bytes
64	1	1	v — if a contract signature, this should == 0
65	0	s	if a contract signature, the extra contract signature bytes; otherwise empty
65 + s or 0	32	32	typehash
97 + s or 0	any	any	EIP712 typed data related to the typehash

[!NOTE] Note: r, s, and v are the components of a standard ECDSA signature. These could easily be referenced as a single 65-byte element just like in the present implementation, but listing them individually allows us to include notes about the expected values in the case of a contract signature.