Inumerous/infinite-time Signing

[marcoonroad]

Our signatures library is one-time. It means that, for the user to maintain a digital identity, she would need to sign a message containing the next public key embedded there. Here, the verifier would maintain an internal state for herself (and the signer as well to maintain the one-time invariant). It's possible to the signer sign a message concatenated with multiple public keys, in this case, the maintained state on the verifier side would be a tree. To avoid public key reuse, the verifier would maintain an internal state of pairs of (verified signature, verified public key). And to avoid duplication of public keys due signer bugs/mistakes, the verifier would maintain a DAG-structure instead sole tree. Thus, the whole signer identity would be represented under a bloated, ongoing mixed chains of signature requests. Garbage Collection is a further topic of study here.

But this approach of sign-message-plus-the-next-public-keys is not safe in the case of network splits. It forces the user to blindly follow a path (in the case, the split) and never go back to the other one. She may try the luck of signing a message reusing the private key, but under the Hash-based one-time signature theorem, it allows a valid signature to be made/forged by prediction attacks, and on the blockchain networks, due latency, front-running attacks (also known as race conditions) could take your funds before you settle the transaction (which reuses an one-time private key).

---

A complementary solution is to use Merkle Trees. With Merkle Trees (a.k.a Merkle Proofs), the signer can pack multiple public keys under a root hash proof. This hash proof now becomes the public key, more specifically, the master public key. Due the hashing nature, the verifier don't need to store the public keys herself, just the hashes of them. In this case, the signer, after generating the signature from the message, publishes the public key alongside. The verifier duty is only to check the signature with the passed public key, and validate the existence of the public key under this Merkle Tree. 'Cause the verifier could not differ the public key hashes (also known as public key addresses), a prefix on the signature pointing out the public key index is needed as well.

This novel mechanism of generating multiple keys packed under merkle proof also enables the reduced size on the signer size, not just on verifier size. Here, the signer can create a master private key with high-quality entropy, and this master private key serves as a seed for the private keys to be generated. 'Cause the process of generating private keys from seed is deterministic, the signer only stores the seed itself (encrypted, clearly). Such seed can be regarded as a function, for instance:

type index = int
type priv
type seed = index -> priv

Such index must not be a bigger number, small ones are enough, 'cause the memory maintained on the verifier will only grow. Take for example, index = 8. Here, the verifier spans a tree of depth = 3, while index 64 means 6 of tree depth (it's just exp 2 n, if we take into account a binary Merkle tree).

Both seed-generated private keys and Merkle tree approaches yield good memory consumption at the expense of CPU consumption. It's a trade of tradeoffs anyway. The Merkle tree approach, thus, enable the few-time, limited-signing public key Digital Signature scheme. This few-time is safe against network splits, the user should still prefer to sign the message concatenated with the next public keys, but whenever such hard-fork happens, she is protected by this Merkle tree scheme of verification and authentication - she just need to ensure to never reuse the same index, an index dedicated to every possible network split is fair enough.

[marcoonroad]

BUMP:

It's quite feasible to combine both sign-with-next-public-keys with merkle-tries-and-seeds ways in this signature scheme. There's a state for the signer (to avoid one-time private key reuse/collision) wrapped under a Git repository, so it's also possible to maintain an internal persistent state for the verifier. It would swap/refresh the new master public keys (on the sign-with-next way) by linking them, so it would become rather a infinite-time signature scheme. 🎉 🎉 🎉 🎉 👏

[marcoonroad]

(Tracked on PR #5)

[marcoonroad]

We can generate such seeds from master seeds. Seeds generate private keys, master seeds would generate seeds. In this case, we could as well generate such master seed from machine/host hashed fingerprint and a proof-of-work embedded. This final hash carrying a proof-of-work would slow down Sybil attacks in the same sense of Tezos node CLI setup. After a proper and unique master seed, seeds could be generated from indexed-hash as well, or perhaps a timestamped-hash too. This idea will be deferred for later, tho.