Introduction

Cryptocurrency Wallet and Identity Wallet is one of the most important missing pieces in the current Blockchain technology. Most cryptocurrency tokens do not get lost because they are vulnerable but because of the security of wallets. Whether it got stolen by hackers at the centralized exchange or at the user’s wallet. One of the most secure wallets we have nowadays is hardware wallets since the private keys are often stored in a protected area of a microcontroller, and cannot be transferred out of the device in plaintext. It is also immune to computer viruses that steal from software wallets. But the drawback of hardware wallets is that they can not connect to mobile phones and the backup paper is the single point attack.

To be able to use a single wallet on every platform including websites and mobile phone we need to keep secret in cloud storage. If the secret is encrypted with another secret key, users can still not be able to decrypt the secret since they can not send the decrypt secret key from mobile phone to website and vice versa. Even if the cloud wallet provider takes care of unlocking and storing the whole blockchain secret key. Trust is still an issue since they are centralized.

It is possible to divide secret key into parts and let multiple parties to keep it secure using Shamir’s Secret Sharing Scheme. Each share will contain no secrets. In order to reconstruct the original secret, a minimum number of parts is required. In the threshold scheme this number is less than the total number of parts. Otherwise all participants are needed to reconstruct the original secret.

There are three missing parts in Shamir’s Secret Sharing Scheme. The paper scope does not cover how seeds are generated, How to verify ownership of shares and those shares will never be updated. If a hacker has access to more than the threshold of part required, he will be able to reconstruct the original private key.

In this document we will explore how Coauths can solve these problems.

Secret Sharing (Shamir's)

Shamir's Secret Sharing is used to secure a secret in a distributed way, most often to secure other encryption keys. The secret is split into multiple parts, called shares. These shares are used to reconstruct the original secret.

To unlock the secret via Shamir's secret sharing, you need a minimum number of shares. This is called the threshold, and is used to denote the minimum number of shares needed to unlock the secret (wikipedia)

In Shamir Secret Sharing Scheme, If node store their shares on insecure computer servers, an attacker could crack in and steal the shares. Since cryptocurrency secrets will never be changed, the shares should be updated in a way that they generate the same secret, yet the old shares are invalidated.

Proactive Secret Sharing

There are many improvement techniques that allow shares to be updated.

Proactive secret sharing is an underlying technique in Proactive Security Protocols. It is a method to update distributed keys (shares) in a secret sharing scheme periodically such that an attacker has less time to compromise shares and as long as the attacker visits less than a threshold or a quorum group, the system remains secure.wikipedia

This follows somewhat the work in Herzberg, Amir; Jarecki, Stanislaw; Hugo, Krawczyk; Yung, Moti (1995) In order to update the shares, the dealer generates a new random polynomial with constant term zero and calculates for each remaining player a new ordered pair, where the x-coordinates of the old and new pairs are the same. Each player then adds the old and new y-coordinates to each other and keeps the result as the new y-coordinate of the secret.

All of the non-updated shares the attacker accumulated become useless. An attacker can only recover the secret if he can find enough other non-updated shares to reach the threshold. This situation should not happen because the players deleted their old shares. Additionally, an attacker cannot recover any information about the original secret from the update process because it only contains random information.

Publicly Verifiable Secret Sharing

In cryptography, a secret sharing scheme is publicly verifiable (PVSS) if it is a verifiable secret sharing scheme and if any party (not just the participants of the protocol) can verify the validity of the shares distributed by the dealer.(wikipedia)

In verifiable secret sharing (VSS) the object is to resist malicious players, such as

    • a dealer sending incorrect shares to some or all of the participants, and
    • participants submitting incorrect shares during the reconstruction protocol,cf. [CGMA85].

In publicly verifiable secret sharing (PVSS), as introduced by Stadler [Sta96], it is an explicit goal that not just the participants can verify their own shares, but that anybody can verify that the participants received correct shares. Hence, it is explicitly required that (i) can be verified publicly. — Berry Schoenmakers. A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting .

Share ownership verification and retrieving protocol

Briefly, to verify ownership of secret shares, users need to login to social networks (Facebook, Twitter, Gmail, etc.) to retrieve the Oauth verification token then send it to each node. Each node will verify the token against the social network Oauth provider. To prevent replay attacks, Each node must record the used token and only provide share only once for each token.

By the way, this simple protocol still have some flaws

    • Dishonest Nodes can forward the token to another node to retrieve share (Front Running).
    • Network can have vulnerability that hacker can intercept share while nodes are sending shares back to the user.

In Coauths, we use the following protocol to prevent this from happening.

    1. The user generate a new keypair on the client side.
    2. The user authenticate to the social network to retrieve access token.
    3. The user atomically broadcast the hash of the token and the new public key to each node.
    4. Each node records the hash, the public key and timestamp into a transaction, Only if the hash is not used before.
    5. Each node signs the hash and the public key with their well-known public key and sends it back to the user.
    6. The User verify that they received all the signature (Or at least more than the threshold).
    7. The User reveal the actual token to nodes.
    8. Nodes verify the token against the Social Network Oauth System.
    9. If the token is valid, Nodes encrypt their own share with user’s public key, Send back to user.
    10. Nodes must not send share to any other public key associated with the existing hash.
    11. Users reconstruct the original seed on the client side.

With this protocol we prevents dishonest node to front-run the user because even if the dishonest node gets the actual token and forward it to the other honest nodes. The honest node will encrypt the share with the user's public key. Which the node has no way to decrypt it. If user don’t get enough signature from nodes, The actual token will not be revealed. And the token will not be accepted twice by any honest node therefore no share will be revealed.

Atomic Broadcast, Byzantine Fault Tolerance

In this system, we only need n/2 + 1 nodes to recover the key. We decided to use n/2 + 2 for more security. But it is possible that dishonest node can pretend to be offline and listen to user's activity to gain some information for front-running. We use atomic broadcast protocol and Byzantine Fault Tolerance to ensure that the messages will reach only online nodes and if there is an online node can not receive the message, no other node will receive the message.

Key Generation

The secret to a secure key is the amount of randomness, or entropy, used in the generation of the key. Take a pack of 52 playing cards for example. In an unshuffled pack, although there are 52 variables, you know what card is coming next. If you shuffle the pack, the random nature of the sequence makes it harder to predict the next card as there are a much larger potential number of possibilities.

In order to create a true random entropy, We use mouse movement (on web wallet) or gesture (on mobile wallet) as the input just like https://www.bitaddress.org then user split the secret key into share, Encrypt by nodes’s well-known public key.

Cryptocurrency Support

Since the secret is BIP-39 Seed. It can be derived into any BIP-44 (HD Wallet) supported currency including Bitcoin, Ethereum, Litecoin, etc. You can see the list of all supported tokens here. Registered coin types for BIP-0044

In order to create a true random entropy, We use mouse movement (on web wallet) or gesture (on mobile wallet) as the input just like https://www.bitaddress.org then user split the secret key into share, Encrypt by nodes’s well-known public key.