Improving double-signing prevention

[tarcieri]

This issue is for brainstorming better solutions for double-signing defenses which also tolerate the failures of one or more tmkms instances.

Feel free to post your ideas in addition to the ones below:

Auditing/Reconciliation

Quoting @tarcieri from #60:

I would suggest leaning on an auditor service for the KMS (#59) to track all signing events. Ideally this auditor watches both signature events coming from the KMS as well as the public blockchain. It can alert on unlogged signatures, and also provide the last signed block height to the KMS, which can be used to bootstrap KMS instances with the current block height when they launch (with potential fail-open vs fail-closed configuration for if that service is down).

This approach is not too far off from Reconciliation Systems used by traditional payment processors, where operations on a ledger service are tracked by a reconciliation system which makes sure the ledger service is behaving correctly and the view of the ledger it presents to the reconciliation system matches the ledgers of external systems. The KMS can sit in the middle: receiving signing commands from the validator, but cross-checking them with the auditing system in order to prevent double-signing and detect validator or KMS compromise.

Collective Signing

Quoting @jleni from #60:

Adding Failover/HA to KMS is an interesting follow up. It might actually need KMS/signatory arbitration + something like Raft (consensus) to handle these cases.

This is somewhat orthogonal to something like Raft, although could be done in conjunction with it and possibly coordinated by it:

I've seen some discussion of using some sort of multisignature algorithm and allowing k-of-n KMS instances to collectively generate a compact signature. This has several nice properties, including splitting the validator key material apart into several keyshares and require a threshold are compromised in order to recover the signature key.

For example, here is a three round protocol that computes RFC 8032-compatible Ed25519 signatures:

https://github.com/KZen-networks/multi-party-eddsa/wiki/Aggregated-Ed25519-Signatures#aggregated-ed25519-signature

There are many other options, such as Boneh–Lynn–Shacham which are more compact and support offline aggregation.

This approach would have the drawback of requiring more online KMS instances, but would have the advantage of splitting the consensus key apart into several keyshares. I think it might be a nice option for anyone who can operate 3-5 KMS instances.

[tarcieri]

Gamma signatures also look interesting: https://eprint.iacr.org/2018/414.pdf