Messing Around with Multi-Sig

Back in the day, families owned "signet rings" and would use them to stamp the wax seal on a letter to "authenticate" its author1. These rings were unique by virtue of being a physical, hand-crafted item and related directly to the family crest1. We're all familiar with the chicken scratch we now call signatures in the real world; we sign receipts when going out to eat, legal documents that come with buying a house or getting a job, and birthday cards for our loved ones. In general, they're designed as a way to lend authenticity to an action.

However, as anyone that had a rebellious streak as a kid knows, signatures are pretty easy to fake. Nowadays, they don't offer many guarantees (and neither would signet rings, with 3D printing and all). I sometimes put smiley faces on my bar tabs, and neither the bar nor the bank seem to care.

Digital Signatures

Enter digital signatures, the virtual world's equivalent. And I'm not talking about something like HelloSign, but rather a rigorous mathematical construction that efficiently provides authenticity guarantees and is impossible to forge.

A digital signature scheme has three parts:

• a pair of keys, public (pk, shared with the world) and private (sk, kept secret)
• a signing algorithm, which essentially uses a private key as a pen to sign any arbitrary thing and create a signature
• a verification algorithm, which uses the public key, the same arbitrary thing, and the signature to ensure that the corresponding private key really did sign that thing to create that signature

More formally,

KeyGen() → (pk, sk)

Sign(sk, x) → s

Verify(pk, x, s) → yes / no

Suppose I have a document (call it X) that I want to sign for the world to see. I would use my secret key (call it sk) and sign it:

sig = Sign(sk, X)

Then, I would broadcast X, sig, and pk (my public key) to the world somehow. Anyone can use all three of them to ensure that Verify(pk, X, sig) succeeds: this is undeniable proof that I (and by "I", we mean "the identity owning the keypair (pk, sk)") did in fact sign that document.

Multi-signature Schemes

Multi-signatures take the utility of digital signatures and knock it up another notch. One of the most flexible and powerful multi-signature schemes is called "m-of-n multisig". This means: of n participants, exactly m of them have to sign the value for the signature to be "valid."

This construction is particularly useful in a multi-party setting, where independent participants don't fully trust each other (or don't fully agree) but need to coordinate an action. For example, you could give each of the Supreme Court Justices a signing key and use a 4-of-7 multi-sig scheme to signify their rulings.

You can also use it in a single-party setting to do something like account recovery. Generate a handful of backup keys and save them in a secure location, and then any 1-of-n would let you use your account even if you lost your "main" secret key. You could even require more than one backup key to "replace" the main key.

There are other blockchains that offer multi-signatures natively, such as Bitcoin, but this often involves complicated setup and might be immutable after the initial configuration. Some platforms like Ethereum offer multi-sig as an additional layer via smart contracts (like Gnosis), but these bespoke solutions can lead to catastrophic security failures such as the one found in Parity's multi-sig contract.

Having native support for multi-signatures is powerful: it means security, interoperability, and extensibility. Since accounts are first-class citizens on Stellar and multi-sig has been there since Day 1, everything is easy to use and completely customizable.

Let's take a look at the details of how signatures work on Stellar.

On Stellar, multi-signatures are achieved through combining signers, their weights, and operation thresholds. You should start with this section of the docs to understand thresholds, but in summary, you can think of a transaction as being valid if the linear combination of signers and their respective weights exceeds the operation's necessary threshold:

signer_1 * weight_1 + signer_2 * weight_2 + ... >= threshold

The power comes from the fact that all of these parameters can be modified by the account signers themselves, and that modification ability itself can be controlled by thresholds.

One account, many signers

When you create a Stellar account, it only has one signer—this is the master key—and no thresholds. You can add signers to an account that have different weights, and the weights of the signatures on a transaction must exceed the threshold for its operations. For example, if an account has a medium threshold of 200 and has 5 signers with 50 weight each, you would need exactly four signatures to execute a medium-threshold operation like a Payment.

With native support for multisig, it's really straightforward to add another signer to an account. We leverage the SetOptions operation, e.g.2

const sdk = require("stellar-sdk");
const newSigner = sdk.Keypair.random();
const setOptOp = sdk.Operation.setOptions({
 masterWeight: 255,
 signer: {
 ed25519PublicKey: newSigner.publicKey(),
 weight: 255,
 },
});

Notice that we set the weight of the new signer to 255 (the maximum). This means the signer has "full strength," so it has the same privileges as the master key. We can lower this weight all the way down to 1.

You can go here to read more about that: in summary, you similarly use SetOptions. For example, let's set the account's thresholds to be 100, 200, and 255 for low, medium, and high-threshold operations, respectively:

const threshOp = sdk.Operation.setOptions({
 lowThreshold: 100,
 mediumThreshold: 200,
 highThreshold: 255
});

Each operation must meet a particular threshold, and you can use these to control what operations are possible by what signers, including when the signers collaborate. This will unlock the advanced multi-party consensus behavior we'll discuss later.

Alternative signature types

You may have noticed that we specified an ed25519PublicKey when adding the new signer. If you guessed that this implies that there are other types of signers, you guessed right! And that's where the true power of native multi-signature support comes in. The other signer types are outlined on the Multisignature glossary entry alluded to earlier, but here's a quick recap:

• Pre-authorized transactions: You can actually sign a transaction "in advance," such that it might be valid in the future. To accomplish this, you add the hash of the transaction as a signer on the account. Then, when that transaction actually gets submitted to the network, it acts as if it was already signed by the account!
• Hash signatures: You can add the hash of any value as the signer to an account. Then, the value itself can be used as a signature. Of course, once it's used, it is revealed to the world, so it can be used by anyone.
• Signed payloads: You can require that a signer includes the signature for an arbitrary payload. In some ways, this is the opposite of a hash signature: the payload is public and you need the secret key to create a signature, rather than the payload being secret and the hash (comparable to the signature) being public.

Signed payloads are the more-complicated signers in the bunch, so let's elaborate on them some more. You start with a keypair, (pk, sk) and a payload P. Then, you configure a "signed payload" signer with (pk, P). This means that Sign(sk, P) is a valid transaction signature.

We can combine multi-signatures and the various signer types to do some fun stuff!

The following case studies will be pretty unrealistic, but will do the job in demonstrating the cool behavior that can emerge from these primitive building blocks.

Let me emphasize something here: These "case studies" are just demonstrations of functionality. Please don't use them as foundations for anything: neither utility nor security were considered deeply in creating these toy examples.

Multi-Party Consensus, No DAObt

We demonstrated how multi-sig can be set up for a single account earlier, but let's do something even better than that. Since a single account can have multiple signers, and a single transaction can have multiple accounts signing it, we can have complicated mechanisms like majority voting using independent governance groups.

Now, Stellar does not have smart contracts (yet!), but we can still simulate the voting mechanisms of a DAO using multi-party, multi-signature consensus.

Our DAO will be a little limited in its functionality, restricted to doing things possible with Stellar's native functionality: vote off members, make payouts, etc. but it will be a DAO nonetheless.

DAO-Land

Suppose our DAO starts off with three members, all agreeing to fund the DAO with 1000 lumens each.

They decide to structure the DAO such that each member (i.e. signer) has weight proportional to its contribution to the DAO. To start, all three members have signers weighing 85. The founders also decide that only a super-majority vote (2/3rds) can execute high-threshold operations, while everything else can be done with a simple majority:

// Assume that A, B, and C are the keypairs of the inaugural members.
const initDAO = [A, B, C].map((kp) => {
 sdk.Operation.setOptions({
 signer: {
 ed25519PublicKey: kp.publicKey(),
 weight: 85,
 }
});
}).concat([
 sdk.Operation.setOptions({
 lowThreshold: 128, // simple majority
 medThreshold: 128, // simple majority
 highThreshold: 170, // super majority
 masterWeight: 0,
 }),
]); 

If everyone (including the DAO account) signs a transaction with this set of operations, the DAO will be set up with their initial voting structure.

Political Parties

Stellar has some fundamental guardrails around multi-sig:

1. Accounts are limited to having 1000 sub-entries.
2. A transaction can only have 20 signatures.

If we have a DAO "controlling" an account, then, “actions” are limited to only 20 votes. Now, George Washington may have advised us against the formation of political parties, but they are inevitable in this case: We must introduce them to create cascading membership hierarchies that vote together to get around these limitations.

Let's not get into that here, though. It should be enough to say that we can avoid the limitation by having members be signers on accounts that are signers on accounts that are ... etc. with increasing authority in the DAO. A bit like a representative democracy, but with more direct influence on the “electorate”.

Membership

Membership in the DAO is controlled by existing members, and everyone adjusts their weights for new members appropriately.

To join the DAO, people must offer up a special transaction for signing:

• First, they must recalculate the new weights of each member after taking into account their contribution to its reserves. If the first new member offered 100 lumens, then, they would own floor(100 / (3000 + 100)) = 3% of the voting rights, meaning the weights are now (82, 82, 82, 7).
• Second, they must add a SetOptions(source: DAO, signer: {address, weight}) operation for every DAO member with the aforementioned "rebalanced" weight, including themselves.
• Finally, they add a payment operation funding the DAO to indicate their proposed contribution.

Naturally, they must sign this transaction. If enough members sign the transaction (i.e. a super majority, since SetOptions is a high-threshold operation), then the transaction becomes valid and the new member becomes part of the DAO.

Taking Action

At any given time, now, the DAO can collectively vote with their signatures to let the governing account take action. They can send all of their funds to a single destination (e.g. making a donation), vote members off (i.e. by removing their signer), issue assets (e.g. holding an asset could represent some legislation), and more.

This is the power of multi-party consensus at work!

Pre-Auth Transactions: Future Validity

Pre-authorized transaction signers allow accounts to plan future behavior.

A simple, useful example is escrow resolution: The escrow account could pre-authorize two transactions with the same sequence number: one that sends money to one destination, while the other sends it elsewhere. Because sequence numbers have to be unique, it's guaranteed that at most one of the transactions will execute.

This can also be useful in unfreezing asset supplies, e.g. when locking an account that issues NFTs. Since locking accounts (i.e. removing all signers) is permanent, you can use a pre-authorized transaction that lets you "unlock" the account back at some point in the future. This could be used to expand your NFT supply after a certain date.

As a more fun example, we can add some sinister behavior to the "DAO" described above. The initial three founders decided that they want to add a contingency plan to their organization, giving them the right to completely reset the voting rights if they want to:

const builder = sdk.TransactionBuilder(daoAccount, {
 networkPassphrase: sdk.Network.TESTNET,
 fee: sdk.BASE_FEE
}).setTimeout(sdk.TIMEOUT_INFINITE);
 
initDAO.forEach(builder.addOperation);

They then set this transaction hash as a pre-authorized signer on the DAO account before opening up membership:

const resetDAO = sdk.Operation.setOptions({
 signer: {
 preAuthTx: builder.build().hash(),
 weight: 255
 }
}); 

Of course, a responsible citizen of DAO-Land would question why there's a mysterious pre-authorized transaction signer on the governing account before joining, but that would take away from the fun of this case study.

Hash Signatures: Commitments

The cryptographic idea of a "commitment scheme" has some interesting applications, and they can be expanded to any human scenario where you need to commit to something in advance without revealing the commitment itself.

The simplest commitment scheme is one where you reveal your commitment as c = H(x), where x is "the thing you committed to" and H is a cryptographic hash function like SHA2, which makes c a "one way commitment." This means that it's impossible to derive x when you only have c. For example, you tell me you flipped a coin and committed to a “result.” Then, I can make a guess on the outcome of the flip, and you can reveal what you previously committed without being able to deceive me about the outcome.

That’s exactly like hash signatures on Stellar! So what can we do with that?

Let's get weird: let's use the network to make a betting platform. It won't be entirely trustless, unfortunately, as participants will still need to trust "The House", but we can still have fun leveraging some of Stellar's multi-sig primitives.

Pick a number, any number

The betting game will be a simple "guess the number" game, where the number is 4 bits long, allowing for 24 = 16 different values. The "House" or "casino" account C first commits to a value by giving itself a hash signer with the value H(r || x) and a weight of 1.

Here, r is a randomly-generated 252-bit value (a "nonce") and x is the actual 0-15 value that will get rewards. The || syntax indicates bitwise concatenation, which just means smushing r and x together into a single 256-bit value.

We use a nonce here because if we just used x, someone could quickly just try all possible values for x and learn the value (e.g. "Does H(0) = x? No, then does H(1) = x?" and so on...). The nonce makes the input value too large to brute force like that.

The signer has a weight of 1 because its only purpose is to be a public commitment to x.

Placing bets

Now that the casino has committed to a value, participants can place their bets. To do so, bettors follow a "handshake" with the casino to establish an escrow account. It involves three phases: two commitment phases and an execution phase.

First, the bettor B creates an escrow account E with its bet as the starting balance. Then, it commits to a particular guess by creating a hash signer H(s || y), where s is a different random value and y is the guess (akin to what the casino did). Then, it creates a transaction with the following effects:

• setting all thresholds to 255
• raising the master key weight to 255
• adding its commitment, the hash signer H(s || y), with weight 1
• adding the casino's commitment, H(r || x), as a signer with weight 100
• adding the casino itself as a signer with weight 100

At this point, the account is ready for escrow but is still in full control of the participant. This lets the participant back out and keep their funds until the casino does its part in the process.

The participant now pre-signs a transaction which will relinquish control to the casino if the casino places its counterbet into escrow. The transaction will:

• make the casino put 16x the bet (since the odds are 16:1) into escrow
• remove the escrow master account as a signer
• set all of the escrow account’s thresholds to 201

To "pass the torch" to the casino, it could store the transaction hash and its signature as data entries in the escrow account, but a real platform would just use an external communication channel for this.

If the casino accepts the terms and escrow “checks out,” it adds its signature to the transaction and submits it to the network. Now, the escrow account can be controlled by the casino if and only if it reveals its committed pick, x, and if the bettor reveals their guess, y.

This is where trust comes in: once the bettor reveals y, the casino would have full control over the account, so it could sweep out its funds.

However, in doing so, it makes its own foul play public knowledge: not only does it admit that it knows the bettor's guess, y, it also reveals its own hidden value, x. Everyone will see that if x=y, that the casino stole from the escrow account. This reduces cheating incentives, since the casino can only cheat once before nobody will want to play anymore.

Distributing winnings

The final phase is where the bettor reveals their guess. Much like an electoral candidate on election night, the bettor prepares two transactions: one for winning, one for losing.

Both of them contain an account merge operation; in one case, the merge is into the bettor's account, while in the other case, the merge is into the casino's account. These transactions get signed with s || y, revealing the bettor's nonce and guess. Once partially signed, the casino can choose which transaction to sign and submit based on whether or not the bettor's guess is correct!

Proof-of-Work on Stellar?

The heading is a bit of click-bait: we aren't going to be doing full-fledged Nakamoto consensus on the network. Instead, we can use hash signatures to simulate "mining rewards". Obviously, we shouldn't incentivize people to waste CPU cycles for no reason (hence why Stellar is one of the greenest blockchains out there34), but it's a fun demo nonetheless.

Here's how it works: We create an account, fund it with some "reward" lumens, and add a hash signer to it. Except here's the fun part: the input x to the hash signer H(x) is not just some random value, but is instead partially revealed to the world. For example, if we reveal the first 24 bytes of x to the world (through a centralized means like Twitter, or even as a data entry on the account), whoever can determine the last 8 bytes can get partial access to the account.

We give the hash signer a weight of 200 and the master key a weight of 55. We also set all thresholds to 255, so the only way someone can do something to the account is with both signers. Then, we reveal a transaction T that modifies all thresholds to 200 that is only signed by the master. If submitted, it will let the "winner" have free reign on the account and cash out the reward.

Once someone has "cracked" the last 8 bytes of the hash, they can sign the above transaction T, submit it to the network, then cash out their reward!

As you can see, having multi-signatures as a native feature of the Stellar network is powerful. It's more secure, flexible, and efficient relative to other blockchain platforms that rely on third-party solutions for multi-sig. They can also grow in capabilities as the network matures; for example, signed payloads (which we didn't really cover here, but are an important part of payment channels) were only released in Protocol 19, but they get all of the protocol’s existing multi-sig features “for free” as a result of being native.

Having multi-signatures and a variety of signer types lets us build some interesting things without needing full-fledged smart contracts. Of course, the things we designed here were toy projects intended to demonstrate concepts, but that just further highlights the power and flexibility of multi-sig on Stellar.

-----

1https://www.thehistorypress.co.uk/articles/a-brief-history-of-signet-rings/

2Note: For the sake of brevity, I don't include code to check errors, prepare/sign/submit transactions, etc. unless they deviate from the norm. Otherwise, they're implied parts of the demo that should be self-explanatory to anyone who builds on Stellar.

3 https://stellar.org/blog/developers/diving-into-energy-use-on-stellar-blockchain-payment-efficiency-examined

4 https://stellar.org/resources/sustainability-report

‍