SimulSig

No files, tests, or implementation entry points are named. Start by reading the Background and Construction sections, then review the discussion about utility, scaling, signer trade-offs, and malleability; done would require agreement on the SimulSig design and its protocol implications.

I'm opening this issue to discuss a new signature type which makes it easier to construct complex protocols on Stellar. I'd love for the discussion to focus on the: utility of this feature, the scaling trade offs, and good trade-offs for multiple signers signing the same tree of transactions.

Background

In a State Channel with N participants, upgrading the channel state requires O(N^2) signature operations/interactions (N+1 signatures per participant) and two phases (Snapshot signing and Claim signing).

If it were possible to simultaneously sign all of the transactions in a round, it would be possible to reduce the number of protocol phases to one and the number of signatures to O(N).

To address this, I introduce a new primitive for simultaneous signature creation. Simulsig is generally useful for any protocol with many participants and many phases. SimulSig makes signatures sizes dependent on the number of SimulSigned transaction, O(log2(T)).

Construction

Rather than signing m=H(TransactionEnvelope), a signer signs m=MerkleTree([TransactionEnvelope]). To sign a specific Transaction Envelope, a signer includes the Merkle Path and the top level signature. Each signer can specify to verify against either the tx hash, their own provided SimulSig, or just against the last one provided (TODO: Malleability considerations?).

Discussion

For our intended use case, the merkle tree proof is amortized -- there are N signers, so a single log(N) merkle proof is negligible. However there are use cases where one might authorize a very large number of transactions (say 2^n) where the lookup proof would be substantially larger. In this case, protocols should add code to support 'existential spend path fee reduction' (if someone demonstrates a transaction they intend to broadcast with a SimulSig from you requiring a large lookup, you cooperatively provide a regular signature of that transaction).