(Draft Spec) Signing & Signature Aggregation

[bvohaska]

This issue serves to provide:

• A plan for adding a signature aggregation to Filecoin
• An understanding of what specs will be affected by the addition of signature aggregation
• A high-level description on why signature aggregation will be included in Filecoin
• A high-level description of the signature aggregation technique (BLS Signature Aggregation)

The output of this effort will be,

• A PR that amends the signature spec to include signature aggregation and BLS signature support
• Enumerate all specs that need updating in order to add support for signature aggregation and BLS signatures
• A PR for that amends all specs that require updating to support signature aggregation and BLS signatures

Updated list of specs that require updating

• signatures.md (Signature, Verify, Sign, SignedMessage, Aggreagate)
• actors.md (StorageMarketActor, CreateStorageMiner)
• mining.md (VerifyBlock, VerifyBlock.ValidateSignature, VerifyTickets.ValidateSignature, VerifyTickets..getPublicKeyForMiner, Block Creation)
• expected-consensus.md (tickets)
• data-structures.md (Block, Tickets.Signature, SignedMessage)

Possible dependencies for the go-filecoin team

• In actors.md, SlashConsensusFault.ValidateSignature(blockX.Signature) may need updating in order to more clearly add support for this Signature Aggregation effort.

Support Links

• go-filecoin BLS Signature Effort

[bvohaska]

IETF spec on BLS Signatures: link

Edit: We are using variant 1 as described in the IETF BLS Spec Draft. This minimizes signature size.

There is an ongoing effort to standardize BLS signatures.

• Choice of generator: (not defined in the IETF spec)
• Serialization: link to draft type-conversion specification
• Hashing onto G1/G2: link to draft hashing specification

https://tools.ietf.org/html/draft-yonezawa-pairing-friendly-curves-00

There is also an unreleased draft spec "BLS Signature Scheme" which should be published soon.

---

Ethereum 2.0 Spec for BLS: link

Updated Ethereum issue for changes to BLS: link

[bvohaska]

Short primer on signature aggregation in Filecoin: link

TL;DR: On-chain storage space is a premium. We at Filecoin would like to find, reduce, and/or remove any burdens to our protocol's on-chain storage complexity. One way of doing this efficiently is by using BLS Signature Aggregation.

[bvohaska]

Algorithmic decisions:

• Choice of generator G1/G2
• Choice of curve set (BLS12-381)

[bvohaska]

Updates required in signatures.md

• Signature will now need to accept an Address. This Address will be taken as input into Verify, Sign, and Recover methods of a Signature.
• Signature will now need to support the IETF draft serialization standard and/or a compact conversion to<>from an on-chain representation
• Signature will now need to support BLS & libsecpk1 signatures
• SignedMessage will now need to support,
  • A conversion of Address into miner ID
  • SignedMessage will now need to support multiple Messages
  • SignedMessage.Message will need to add support for miner IDs which are used to look up the public key associated with a particular miner and signature.
• Recover will now need to support the case where the public key is not recoverable from a signature and message. In the case of BLS signatures, the recover method will be required to look up the public key of the signer in a table.
  • go-filecoin: public keys in Actors
  • go-filecoin: looking up public keys via IDs
• Verify will now need to support BLS signatures and BLS signature aggregates. link to IETF draft Verify standard
  • This method should have an Address as input.
  • Aggregate signatures should be verified according to the IETF draft Aggregate standard
  • If more than one Address is given, Verify should assume a BLS aggregate signature as input
• Sign will now need to support BLS signatures link to the IETF draft Sign standard

New methods

• Aggregate will need to be added to Signature. Link to the IETF Aggregate standard
• VerifyAggregate is a separate method for verifying an aggregate signature. This is needed for code and logic simplicity.

[bvohaska]

New Methods (requires thought into which spec they should be)

• Address.GetPublicKey - Public Key <--> ID - Used by the BLS Signature Recovery method to find a public key belonging to an ID. This will be a method on the Address structure.

[bvohaska]

@whyrusleeping: can you add a few notes about BLS Recovery here #210. Specifically, notes on how an actor will search for a a specific public key once it has an associated actor ID.

[whyrusleeping]

@bvohaska sure thing.

Given an ID, you need to look up the actor associated with it. To do that, take the current global state root, and index it with the ID. This will return to you an actor.

Now, since not all actors will need public keys, it doesnt really make sense to put the public key into the top level actor struct. Instead, we should put it into actor storage for a particular actor type. The actor that makes sense here is the "account actor" which is the actor that can be made to send messages via external input (signed messages). The account actor is actually not in the actors spec yet (somehow overlooked this one, dangit). The code in go-filecoin for it is here: https://github.com/filecoin-project/go-filecoin/blob/master/actor/builtin/account/account.go . We should add the public key to the account actors state, and provide a method for retrieving it. We also then need to figure out how that public key is gonna get there in the first place.

To do that, we can use the fact that bls addresses are just the entire bls public key, and upon account creation (which happens when funds are first sent to a new address) pass the key to the actor constructor. This behavior should be documented in the state-machine.md doc, its not spec'ed out yet. Yay finding missing things :)

Hope that helps.

[bvohaska]

Updates required in actors.md

These changes are outside the scope of signature aggregation but related to signatures in general.

• StorageMarketActor will need awareness of signatures
• CreateStorageMiner will need awareness of Addresses.protocol and selection defaults
• (@whyrusleeping) The account actor needs to be upgraded to hold public keys for bls based accounts

Possible dependencies for the go-filecoin team

• In actors.md, SlashConsensusFault.ValidateSignature(blockX.Signature) may need updating in order to more clearly add support for this Signature Aggregation effort.

[bvohaska]

Updates required in mining.md

• VerifyBlock - add note that all instatiations of ValidateSignature must implement the Signature interface
• VerifyBlock.ValidateSignature
• VerifyTickets.ValidateSignature

These changes are outside the scope of signature aggregation but related to signatures in general.

• VerifyTickets.getPublicKeyForMiner - This functionality will need to be added
• GetPublicKey(blk.Miner) - This must be defined
• Block Creation
  • A choice of defaults and signing scheme for a block must be created
  • A method for aggregating BLS signatures within a block

[whyrusleeping]

Block creation does need to be updated to show the actual aggregation of signatures

[bvohaska]

General updates/questions about the FIL spec

Copied from link

• (@whyrusleeping) What does the array of signed messages in the block look like now that some of the messages have had their signatures aggregated?
• (@whyrusleeping) How exactly do we disambiguate signatures?
• (@whyrusleeping) add the signature type to the data-structures doc, along with pointers to how things are serialized.

[bvohaska]

(@whyrusleeping, @frrist) I suggest the following solution to the question, What does the array of signed messages in the block look like now that some of the messages have had their signatures aggregated?

Context: The goal of Signature Aggregation is to move a collection of "signatures" into a single "signature". What this means in practice is that we want to represent {msg_1, SignatureBytes_1}, {msg_n, SignatureBytes_n} as {msg_1, ..., msg_n, SignatureBytes_aggreagte}.

Proposed Solution: Fortunately, we already have a structure to do that, SignedMessage as defined in the updated signature spec. This would mean that we represent all messages that we want to aggregate into a single SignedMessage which we may call BlockMessages. In this way, the block would not have individual messages and signatures but rather have a single or collection of SignedMessages and signatures (in addition to whatever other block information is needed).

• (Case 1) All messages have BLS signatures. In this case, all messages in the block can be represented in a single SignedMessage struct.
• (Case 2) All messages have BLS signatures but we don't want to group them all together for some set of reasons. In this case, we have an array of BlockMessages which are just an array of SignedMessages each of which contains a BLS signature aggregate and associated messages.
• (Case 3) The block has ECDSA and BLS signatures. Perform (Case 1) or (Case 2) for the BLS signatures and messages. Leave the ECDSA messages alone.

[bvohaska]

(@whyrusleeping, @frrist ) How exactly do we disambiguate signatures?

Right now, the spec is written to infer that data from Address and the number of elements in SignedMessage.Msgs. This inference is mostly to save space but we can explicitly declare key type if that's better.

Logic:

"Am I BLS or ECDSA?":

1. Does Address.prootocol specify 1? If so, then ECDSA
2. Does Address.protocol specify 3? If so, then BLS
3. Does Address.protocol specify 0? If so, fetch actor with ID = Address.payload, return BLS or ECDSA. <--this method needs to be specified in actors.md and should distinguish between BLS and ECDSA signatures.
4. If anything else, return INVALID <--Do we want to handle the case where 2 is returned? This specifies actor which I'm not sure how to parse.

"Am I a BLS aggregate?":

1. Is Address.protocol 3 or 0. If 0 does lookup return BLS? If not, INVALID
2. Is len(SignedMessage.Msg) > 1? If true then this is an aggregate. Otherwise, not an aggregate.

[dignifiedquire]

Some thoughts on this

1. Please use plural for something that contains many messages, eg SignedMessages or AggregatedMessages
2. If we group all messages by their signature type we can have a single aggregated signature for all BLS signed messages and simply list the ECDSA signed ones in a second part. This gives an additional benefit, that we can layout the data such that if there are no ECDSA signatures we possibly pay 0 overhead costs in terms of storage

[whyrusleeping]

@dignifiedquire re: 2, I like this. Basically we could have a place in the block where an array of signatures is linked.

Alternatively, we could just have all the messages be in one place, and if they don't have signatures they are just a different object, basically the message array would be []{Message|SignedMessage}