Kyiv, Ukraine

26 Metalistiv St

Dnipro, Ukraine 20

Sichovykh Striltsiv St

Articles

Multisig stands for multi-signature, a specific type of digital signature that makes it possible for two or more users to sign documents as a group. Therefore, a multi-signature is produced through the combination of several unique signatures.

As a simple analogy, we can imagine a secure deposit box that has two locks and two keys. One key is held by Alice and the other one is held by Bob. The only way they can open the box is by providing both their keys at the same time, so one cannot open the box without the consent of the other. Basically speaking, the funds stored on a multi-signature address can only be accessed by using two or more signatures. Therefore, the use of a multisig wallet enables users to create an additional layer of security for their funds.

In general, multisig wallets can be divided into cryptographical and non-cryptographical.

**Non-cryptographical**

Non-cryptographical wallets can be implemented with the help of smart contracts, via some web servers or runtime modules (i.e. Substrate). With these, we have an address (contract address) or a newly generated address, and a list of participants permitted to spend money from it. Multisig with smart contracts is a secure, on-chain solution and every operation – such as the creation of new multisig transactions or signing – will cost money.

Examples of smart contract multisig wallets:

- https://github.com/ConsenSys/MultiSigWallet
- https://github.com/Gnosis/MultiSigWallet
- https://github.com/BitGo/eth-multisig-v2
- https://github.com/ethereum/dapp-bin/blob/master/wallet/wallet.sol

Example of runtime multisig module for Substrate:

** ****Cryptographical**

An off-chain solution wherein all computations occur on a web server.

In cryptographic wallets, the functionality is based on different types of cryptography. Cryptographical solutions can be categorized as follows:

- Distribute private key between participants;
- Generate private key distributively;
- Aggregate signature schemes.

Dividing a private key between participants can be done with SSS (Shamir’s Secret Sharing, Pedersen or Feldman verifiable secret sharing). The secret is split into multiple parts, called shares. These shares are used to reconstruct the original secret. To unlock the secret, you need a minimum number of shares. This is known as the threshold, and is used to denote the minimum number of shares needed to unlock the secret. But there remains a single point of failure, since the secret is generated in one place – a web server, for example – and thereafter divided among the participants. So, if the server is corrupted, the private key will be revealed.

Example of implementation of VSS and PVSS:

A more reliable protocol to distribute a secret is DKG. Unlike most public key encryption models, distributed key generation does not rely on trusted third parties. Instead, the participation of a threshold of honest parties determines whether a key pair can be computed successfully. Distributed key generation prevents single parties from having access to a private key.

The involvement of many parties requires distributed key generation to ensure secrecy in the presence of potentially malicious contributions to the key calculation. Here, every participant runs one of the verifiable secret sharing protocols on his device to generate part of the main private key by himself. When all parties generate their local secret, they start to communicate, broadcast commitments and responses, and finally everyone has the public key but nobody knows the entire private key. To make communication between participants more secure, a commitment scheme is favored; Diffie–Hellman key exchange may also be used. With these schemes, communication can be secure even in open channels.

Implementation of DKG:

The signature in DKG should also be computed distributively. Reliable signatures which can be used in distributed signing include Schnorr and BLS (Boneh-Lynn-Shacham). Actually, Schnorr and BLS can be used in any multisig implementation because both types of signatures can aggregate many signatures into one. The time needed to validate signed multisig transactions is reduced, because we will verify one signature instead of several. It should be noted that the Schnorr signature demands several communication rounds while signing transactions, so it is best not to use a cold wallet in such multisignature schemes.

BLS explanation: https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716

Schnorr explanation:

https://medium.com/cryptoadvance/how-schnorr-signatures-may-improve-bitcoin-91655bcb4744

Schnorr implementations:

- https://github.com/dedis/kyber/tree/master/sign/schnorr
- https://github.com/w3f/schnorrkel
- https://github.com/KZen-networks/multi-party-schnorr

BLS implementation: https://github.com/dedis/kyber/tree/master/sign/bls

Distributed Schnorr signature (DSS): http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps

Implementation of DSS: https://github.com/dedis/kyber/tree/master/sign/dss

**Differentiating between SSS (Shamir’s Secret Sharing), aggregated signatures (BLS), and distributed key generation (DKG).**

ex. Alice has a private key that she uses to sign transactions. Like anyone else, Alice wants to ensure that her savings are completely safe – and so looks into cryptography as an extra line of defence. She comes across three main options.

Shamir’s Secret Sharing (SSS) piques her interest. With this method, her private key is divided into shares, the idea being that even if one share is compromised, the thief cannot hope to steal the funds because he or she does not have the other shares. Alice can apportion the shares to her closest and most trusted friends or family members. When she wants to sign a transaction, she would simply ask those individuals to provide her with the shares, so that she can recreate the private key.

A popular cryptographic standard, SSS has several variants including VSSS, wherein participants can verify that untrustworthy shares are not being used, and PSSS, where secret-holders can proactively rotate their shares.

Of course, this methodology is not without its flaws. For instance, before Alice dispenses the various shares, she herself represents a single point of failure. Therefore, Alice may elect to modify the system so that she is never capable of signing a transaction alone: this is the idea behind a multi-signature system (multisig) wherein X participants sign the same transaction, with the signatures feeding into the system. The only drawback is that the transaction size increases in accordance with the number of signers needed to validate the transaction.

Cryptographic standards evolve when points of failure are eliminated and hackers’ lives are made more difficult. While strong, a multi-signature system can be refined by incorporating aggregated signatures: a Boneh-Lynn-Shacham (BLS) signature scheme allows for the compression of X signatures in a single signature. Alas, this methodology has its own drawback – it is far slower than other standards such as the Elliptic Curve Digital Signature Algorithm (ECDSA) and Edwards-cure Digital Signature Algorithm (EdDSA).

Distributed Key Generation (DKG) is another term Alice discovers in her research. DKG is not wholly dissimilar from SSS, in that it involves several participants to eliminate the single attack vector. However, with Digital Key Generation, participants actually collaborate to originate a key pair and signing operations. DKG is a prime example of Multi-Party Computation (MPC). Incidentally, the aforementioned Boneh-Lynn-Shacham (BLS) signature scheme can aggregate public keys into a single key that verifies combined signatures, permitting the origination of just such a DKG scheme.

The BLS scheme is perhaps best illustrated thus:

As is customary, Alice’s private key is a secret number pk, the public key is P = pk×G, with the message we are signing signified by m.

To calculate the signature, the message is hashed to the curve H(m) and then multiplied, resulting in the point pertaining to our private key: S = pk×H(m).

Rather simple, huh? No complex series of numbers, no additional operations; just multiplying the hash by the private key. Alice’s signature is visible as a lone point on the curve that takes a mere 33 bytes in compressed serialisation form.

To confirm the signature, it is simply a matter of taking the public key P and confirming that e(P, H(m)) = e(G, S).

Because of the neat pairing function outlined above, we get:

e(P, H(m)) = e(pk×G, H(m)) = e(G, pk×H(m)) = e(G, S)

This particular signature scheme is as elegant as it is simple, and its features are perfect for Bitcoin.

Signature aggregation

We can now combine all signatures in the block. Picture a block comprised of 1,000 transactions, with every one containing a signature Si, a public key Pi and a message signed mi. Remember, we only wish to confirm that all signatures in any given block are valid. An aggregated signature, described above, will simply be a sum of all signatures in a block:

S = S1+S2+…+S1000

To verify the block, we must ensure that the equation holds true:

e(G, S) = e(P1, H(m1))⋅e(P2, H(m2))⋅…⋅e(P1000, H(m1000))

It should be noted that all schemes summarized above can be adapted into so-called threshold schemes. We do not require n signatures from the n signers any longer, merely a threshold m of n. Thus, if a participant happens to lose the keys in their possession, or is otherwise unavailable, it is still possible to sign the transaction.

The schemes described above also assume that secret-keepers are trustworthy; other cryptographic standards exist which account for the possibility of untrustworthy participants.

Needless to say, this field is ever evolving and algorithms often spawn multiple versions of themselves.

Our team can offer a consultation to discuss all your ideas and help your business take the next step