Quantum-secure backup infrastructure for BLS signatures

[JustinDrake]

Quantum-secure zkproofs of knowledge (such as STARKs) can be used as a backup signature scheme to BLS in case of a quantum apocalypse. The only infrastructure that needs to be setup today is a commitment to a secret. We currently have withdrawal_credentials which is imperfect because the committed secret (namely, the withdrawal pubkey) is revealed for transfers. A better construction would replace withdrawal_credentials by the hash_tree_root of container with two fields:

    withdrawal_pubkey: BLSPubkey
    secret: Bytes32  # Quantum secure backup for `pubkey` and `withdrawal_pubkey`

Another approach would rely on the convention the private keys corresponding to pubkey and withdrawal_pubkeys have been derived by hashing a seed, and that this secret seed is stored by validators.

(This is labelled as phase 1 because transfers are not part of phase 0.)

[dankrad]

I am in favour of this backup mechamism. Full "signatures of knowledge" using STARKs will probably be quite heavyweight, right? Would it make sense to even commit to a full Merkle root of secrets, so that other schemes can be used?

[JustinDrake]

Would it make sense to even commit to a full Merkle root of secrets, so that other schemes can be used?

Oh, interesting! There's no onchain overhead to having more than one secret. And you're right that a STARK for a SHA256 preimage will be expensive so support for Lamport signatures is wise.

[dankrad]

So one interesting question is how we would handle multisigs in this case. One way would be to do proper Lamport multisigs (as in https://ethresear.ch/t/threshold-lamport-signatures-can-survive-with-much-lower-size-by-compromising-on-per-signature-security-level/1737) but working this out properly for emergency infrastructure that is likely never used may be overkill. So I suggest a very simple Lamport multisignature scheme, where the public key consists of a Merkle tree of Lamport signatures:

     Lamport multisig key
            /  \
          /      \
        /          \
     Meta    Merkle root of Lamport public keys
    /    \
   n     m

A valid Lamport multisignature consists of Merkle proofs of m Lamport keys as well as m signatures using each of these keys.

All of this can be integrated at no extra cost by making the withdrawal key a Merkle root: of the BLS key and the Lamport public key. In order to avoid having to expose the actual lamport public key to provide Merkle proofs (as it is being considered in the BLS standardisation that the Lamport public key is the same as the BLS private key) we can also use the multisig format for them using m, n = 1.

[JustinDrake]

Paging @CarlBeek who I believe is leading the quantum-secure backup initiative. Can this issue be closed, maybe in favour of another issue? :)

[JustinDrake]

@CarlBeek mentioned that quantum-secure backup (for the single party case, not the multi-party case) has been standardised and implemented by the default deposit interface (as well as implementers).