SimulSig

[JeremyRubin]

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

[robdenison]

Can you achieve this alternatively by pre-signing a transaction that preauthorizes all of the transactions in the snapshot set?

If there are N transactions, and each of them has to include a Merkle proof, the total overhead for the snapshot transactions will be O(N log N), right?

Also, I think state channels with N >> 2 (or even N > 2) will probably be pretty rare...

[JeremyRubin]

No, that doesn't work for a couple different reasons.

1) need to simulsig across accounts. 2) Requires a known sequence number/freeze to simul authorize 3) requires publishing all pre-signed (O(N))

Even in the N=2 case, it is an improvement because it allows turning a 2 phase protocol into a single phase.

[theaeolianmachine]

@JeremyRubin, would you like to write a CAP, or would you like for another owner to take this over for putting this in a draft?

[JeremyRubin]

I think @jonjove should take a look at this one as he'll have a handle on the least annoying way to implement.

Not sure it's particularly hi impact -- but it is something we want to fix in general -- so we should just leave issue open for now rather than invest engineering resource.