On Telegram, Vladislav Gelfer of BEAM fame,
announced his creation of a Multi-sig RFC for Grin [1].
Let the commenting begin!
10 Likes
Should we comment here?
I don to see any comment button or field when I go to the proposal. Or are special rights needed for that?
1 Like
Here are my first thoughts and questions about this proposal:
Regarding the “Moniker”. If I understand you correctly it is something akin to a unique user ID.
Would it not be logical to include the slatepack address in the hash input to force uniqueness?
E.g.
hash("actor-"|"Anynomous"|"_grin1testjvsvwm3nrh7ueas8vanjs0tmvymetskf5qwl7cjmkqy7lm0sy0wmcs")?
Some questions about the part on new actors
Unlike initial actors, that can generate/restore an arbitrary secret key, new actor’s key is uniquely defined by its moniker.
I am still trying to understand this part.
I assume that the share for new users is different because the shared secret is already fixed at this point, meaning you can only derive a share and not predefined one unless you would create a new MultiSig wallet with new shared secret. If so, we need to allow the user to backup this share in the form of a new wallet file and a mnemonic, or add the encrypted share as an extra field to an existing wallet. Since Grin wallets store sthe raw entropy and not seed_bytes (hashed mnemonic) this should not be an issue since you can derive the mnemonic form the share). However, the process might be a bit different since you need an existing wallet to start the creation of this extra share 
Regarding the use of a Coin number.
I assume this refers to something like the index number in BIP44 HD wallet derivation, or even its full derivation path? If so, should the full coin number be XORed in the range proof? Just pondering about security here since you do want the publick key to allow Actors in the MultiSig to scan for outputs, yet you want the coin number to be only decryptable to MultiSig Actors and not everyone who has a rewind hash. Is there a way to store the coin number in the range proof only decryptable for the MultiSig Actors?
I searched if this is possible to encrypt such information while keeping it small enough to XOR in the range proof. Threshold ElGamal would result in to big an output 256 bytes, Lumo (AI) suggested “What you can do is combine a tiny symmetric cipher (AES‑GCM, ChaCha20‑Poly1305, etc.) with a threshold public‑key layer. The public‑key part protects a short symmetric key (16‑32 bytes), while the bulk of the data stays encrypted with the lightweight symmetric algorithm. The final transmitted blob is therefore only a few dozen bytes larger than the original payload.” - That is just AI output, I do not know if this would be secure enough or if there would be an alternative approach. The main point for me is that the coin number should always be recoverable, even if all key-holders have to recover their wallet from their mnemonic.
The proposal states
Each new coin number should not be completely random.
Does this also mean that the coin number should also always contain a random generated part? To me it sounds like the coin-number should be a concatenation of the outputs hd wallet path or index number (deterministic) with some random number should suffice. In this way it should be impossible to ever use the same coin number twice.
1 Like
-
Regarding inclusion of the slatepack address in for uniqueness - that’s an option.
Perhaps the slatepack address should even replace the moniker: it’s not only a unique ID of the user, it also (as I understand) includes the communication instructions.Most importantly: the user ID is converted into a scalar that uniquely defines the secret key ID (technically - the x-coordinate of the polynome with secret coefficients).
It’s important to make sure there’s no feasible way to craft a user ID that is transformed to a known key ID (in particular, key ID of a coin).
Hence no matter what the user ID/moniker is, it should be hashes with some prefix (like “actor-”) to separate it from coin keys (which use “coin-” prefix). -
Regarding the coin number.
I think there’s a confuse here. The so-called “coin number” is NOT secret, it’s not the blinding factor, and there’s no need to encrypt/decrypt it. You may allow anyone with the “view key” (or whatever it’s called in grin) not only to identify your coins, but also recover its value and the coin number.
Moreover, once the coin number and the value are recovered, each actor can also individually derive its pubkey (i.e. G * blinding_factor). This is good to filter-out false positives.The whole scheme works like this: (coin_number, value) → x_coin → blinding_factor
The “view key” is used to derive randoms for the bulletproof, the (coin_number, value) are XOR-ed and then recovered. Together they should be much less than 256 bits, which leaves many leading zeroes as a trigger for coin recovery.
But - the blinding factor is different. The randomness that protects it (tau1, tau2) is derived by each actor individually, and not possible to reproduce by any key.
-
“Each new coin number should not be completely random.”
I meant, coin numbers should be somewhat like auto-increment integers. Like 1, 2, 200, etc.
If the last coin number used was, let’s say, 200, there’s no reason you’ll be asked to sign a transaction where being-spent coin number is a huge number, this can be a sign that someone tries to manipulate coin numbers to get the desired delta blinding factor.But I’m not sure such precautions are really needed. When the polynome degree is high (i.e. ~10 and up) this seems like a really hard problem. Maybe it’s already infeasible for degree=1, I’m not sure.
BTW, the polynome degree can be raised artificially. In the RFC it’s assumed that each actor gets 1 share, hence M actors define M points of the polynome, means its degree is M-1.
But there can be more shares. For example, each initial validator can generate several private keys, means more points for the polynome → higher degree.
It’s also a nice exotic feature: each actor can have different number of shares, means it will have a different weight in the quorum.In short - this can be worked around. Polynome degree can be raised, such that even theoretical threat of Wagner-like attack will not be practically possible.
6 Likes
This strikes me as a very well thought out and well described high level design for threshold multi-sig outputs; a pleasure to read.
I hope we can interest some cryptographers like Andrew Poelstra or Daira Hopwood in reviewing the proposal.
Some cursory comments:
Section Motivation
Would this proposal also make sense for the simpler case of N-of-N multi-sig, such as the 2-of-2 outputs needed in atomic swaps, or would that benefit from a simpler incompatible design?
Key concepts
we assume that each message broadcasted by an actor is signed by its private key, and then verified by others vs its pubkey
Note that Grin uses a different curve (ed25519) for user authentication, such as in [1].
Message authentication
However some messages must be protected against tampering. Hence we assume that each message broadcasted by an actor is signed by its private key
Would a cheaper MAC (Message Authentication Code) also suffice for that purpose?
Wallet initialization/recovery
M initial users
An M/N wallet has N users.
This message must be signed by the actor pubkey.
Presumably some already established pubkey rather than P_i.
Adding an actor
add an additional actor.
The need for one usually only arises when an existing actor becomes inactive. I suppose it’s not possible to also invalidate their old share?
Building a transaction
list of input coins (coin number + value)
list of output coins (coin number + value)
Both sender and receiver preferably have input coins in order to enjoy the advantages of payjoin: hiding of payment direction and
avoidance of utxo set expansion.
PS: The document contains several occurrences of “polynome” which appears to be a mis-spelling of polynomial.
[1] grin-rfcs/text/0006-payment-proofs.md at master · mimblewimble/grin-rfcs · GitHub
5 Likes
Interesting thought.
Since to add a new share holder, all current share holders have to go through an interactive process to generate a new share, why not just redo the whole dance and generate a new set of shares, e.g. by incrementing the number on the account or index level for key derivation.
The only downside is that now the wallet has to scan for both the old and new derived key sets. I think that is only a very small price pay.
Second thought. To truly invalidate the old share it would mean such a change should be accompanied by transfering all coins using a commit/transaction using this new shared secret.
I guess another downside would be that the shared pubkey and slate address would change. So no, it would become a whole new wallet.
2 Likes
Would this proposal also make sense for the simpler case of N-of-N multi-sig, such as the 2-of-2 outputs needed in atomic swaps, or would that benefit from a simpler incompatible design?
It’s not only about the complexity. Using this scheme for N/N means also unneeded risks.
As mentioned, the drawback of this scheme, perhaps the biggest one, is that once M keys get leaked (for whatever reason) - the whole secret polynomial can be calculated. Means, ALL keys, both previous and future, are compromised at once.
Regarding the initialization/recovery.
An M/N wallet has N users
Yes, sure. But in the described scheme only M initial actors participate in the initialization. The others are added later, via the “adding new actor” scheme. M first actors contribute a single point to the polynomial of degree M-1. Others receive the evaluated value for their x-coordinate.
Recently I’ve discovered there’s a different initialization scheme available. In the classical ceremony (DKG/Feldman) Instead of providing separate points, each of M actors generates its own polynomial of degree M-1, and then the secret polynomial is defined as their sum.
Only then “shares” (i.e. x,y evaluations) are computed and distributed.
The advantages of this scheme is that the roles of all N users are symmetric, each initial user contributes to the randomness. It’s also considered more secure and well-studied. This is the part I’m not an expert in, this it’s related to the fact that in the previously described scheme, the last actor can grind its x-coordinate, and influence the algebraic structure of the final polynomial coefficients.
The only drawback here I can see is that none of the actors can then “restore” its share from the seed phrase.
I suppose it’s not possible to also invalidate their old share?
Not directly.
It’s possible to perform a sort of a key rotation, s.t. all keys generated after some epoch will be according to the new scheme.
Both sender and receiver preferably have input coins in order to enjoy the advantages of payjoin: hiding of payment direction and
avoidance of utxo set expansion.
There’s no problem with this. Each tx side deals with its inputs/outputs. What’s important is that each specific transaction (tx kernel) is built to balance some set of selected input and output coins. This is what all actors see: input and output coins (of their side).
1 Like
P.S.
No. Specifically by P_i. This is a critical point.
After sharing the P_i, the actor is supposed to demonstrate the so-called Proof-of-Possession (PoP), i.e. knowledge of the preimage of P_i, which can come in a form of a Schnorr’s signature, of this specific pubkey, or any other message.
This is what protects against the so-called rogue key attack. Without this protection, the last actor can craft its P_i s.t. it will know instead the private key of an arbitrary other x-coordinate. Which can correspond to the ID of a future coin, or etc.
In the classical DKG ceremony, where N actors initially demonstrate the set of P_i,j, images of the coefficients of their polynomial - the PoP must also be provided for each image.
1 Like
This strikes me as a more elegant approach, with slightly simpler polynomial computation.
Given those advantages, and (as I see it) lack of downsides, I’d prefer to see the RFC rephrased to use that approach.
2 Likes
When I read about SLIP39, I see they have an extra security feature called the “iteration_exponent”.
If I understand it correctly it is a extra hashing step needed to go from shares to the final shared secret/seed. By varying the amount of hashing rounds you can make it computationally harder to retrieve the original secret/seed.
If I understand this proposal there is no such hashing step, or is there? Now I think about it, it probably impossible to have such a hashing step since the shared secret is never calculated as such, just its pubkey.
1 Like
This is something quite different, and the whole SLIP39 standard is fundamentally different. I’ll elaborate.
In SLIP39, first the master secret is created by a single wallet (HW wallet usually) and stored on the device. It alone is used to sign transaction, so that it’ operates as a standard wallet, not a proper mutisig wallet.
The SSS is used only to backup the seed phrase. Instead of a single seed phrase, the wallet split the secret key into N shares, and show each share in terms of another seed phrase.
Now, each exported seed phrase can also OPTIONALLY be encrypted by a chosen passphrase. This is where the interation_exponent comes into play. If the attacker ever gets this encrypted share, and try to bruteforce the passphrase - the interation_exponent will make it harder.
Note that this is in essence a “classical” SSS, where there’s a single trusted dealer that knows the whole secret, which is then split into shares. And then, in order to perform any actions, the shareholders must first reconstruct the secret in a single place (i.e. restore the wallet).
Which is different from what we do. We leverage this idea using the homomorphic nature of ECC. The whole secret is never reconstructed in a single place, instead shareholders perform MPC to perform actions.
3 Likes
Please see here updated RFC:
3 Likes
First of all, thank you very much for the multisig wallet RFC and the detailed explanations.
I have a question about the recovery case in the multisig RFC:
How is the recovery case intended to work if the rewind/view seed is lost?
Without this seed, a reconstructed wallet can no longer recognize its existing UTXOs and thus also the balance.
Is this behavior intended, and does it mean that the rewind seed must be backed up separately?
Or is there a mechanism in place to regenerate it during wallet reconstruction or restore it among the actors?
I have an another question.
What happens to existing UTXOs whose blinding factors and range proofs were generated under the original set of actors when one or more actors are permanently removed?
Do these outputs have to be migrated on-chain to a new multisig configuration?
First of all, this is great work, thank you very much for making this RFC @Vlad 
I think all the security concerns that have been raised in the past few years have been discussed and solutions to mitigate them are discussed.
There are many things I love about this proposal:
-
it is fully deterministic and as such can be restored as long as a quorum is met. That is great for recoverability. Only I am not sure how that still works with:
“Each actor generates 2 nonces, using true random (i.e. non-deterministic), uses them to calculate its share of T1,T2.” -
Letting all actors contribute to the randomness - this is simple but great for security!
-
Regarding Address grinding having the proposed prestep of revealing the address beforehand sounds like a good idea to me.
-
Same for “Mitigation: include the coin value in the blidning factor derivation too.” - sounds good, if not essential.
Regarding:
“Wagner attack, Prouhet-Tarry-Escott (PTE) problem”, going for a higher order polynomial and giving actors multiple shares is indeed probably best. I tried this Wagner attack ones myself (2/3) testing an insecure python SSS implementation, it was extremely insecure. Perhaps we should make some rules for this. For example , if there are less than 4 actors (so shares <4), double the shares per actor?
It is the least important and least interesting part about the RFC, but just throw it in a text corrector to remove some typo’s.
Typo’s:
"Same for “Mitigation: include the coin value in the blidning factor derivation too.” - blinding
“But what if rgw attacker” “rogue”
Bob side
“Round 1: they reveal the images: T1,T2 for the UTXO, and the kernel noce image” - nonce
“It’s a known problem, called Prouhet-Tarry-Escott (PTE) problem. And it’s considered generally infeasible to solve, especially for large” - sentence is trimmed, large what?
1 Like
Thanks for the quick revision, Vlad!
A few more comments:
“a quorum of N/M” should be M/N
“Not that Grin Slatepack addresses” should say Note
Can’t addr_i simply be i ? Or their Grin slatepack address? Or the handle they use to talk to one another, e.g. on Telegram ? All these avoid grinding worries.
I’d first define sk_i(x) and then define sk(x) as Sum_i sk_i(x), since the sk_i(x) comes in useful later.
“since the function sk(x)” is mis-formatted, as is
“or with x_coin” further down.
“But what if rgw attacker” → the attacker
“in the blidning factor” → blinding
There can be potential reorgs, whereas transactions may be reverted, and then, after some time, included again in a block. By such it’s theoretically possible the wallet will own several coins with the same ID, but different values.
I fail to see how that is possible.
“especially for large” is missing an M.
Prouhet-Tarry-Escott (PTE) problem
One mitigation for PTE is to use payjoin for all multisig wallet transactions, so that it only ever needs a small constant number of spendable coins.
2 Likes
The seed used to “paint” UTXOs (s.t. they can be recognized later) is known to all the actors, and derived in the deterministic way during the wallet initialization.
So there seems to be no problem.
2 Likes
Actors can’t be “removed” per se.
What is possible to get rid of unwanted actors is “key rotation”. Which means a fresh initialization ceremony where new secrets are collectively derived.
This can also be called a switch to a new “epoch”. Actors will need to be able to manage several epochs, store keys for each of them.
Then there’re 2 strategies for “painting” coins.
-
Don’t change the key used to recognize the coins. Embed into so-called “Coin Number” its epoch.
This is a convenient approach. Only 1 key to scan the blockchain, and the coin number carries the epoch info, according to which its blinding factor is derived.
The drawback: removed actors will be able to continue monitoring wallet balance. -
Each new epoch also comes with the new key to paint and recognize coins.
Obviously removed actors (those who didn’t participate in the new epoch initialization) won’t be able to recognize those coins.
The drawback: need to scan blockchain with multiple keys.
I can elaborate on this in the RFC
1 Like
Going with Option 1) is best IMO.
If the remaining Actors need to obfuscate from previous actors, they can always setup a completely new Multisig wallet.
1 Like
Regarding this:
“Each actor generates 2 nonces, using true random (i.e. non-deterministic), uses them to calculate its share of T1,T2.”
Right point. But this part is not needed for UTXO recognition. T1, T2, and TauX are the only parts that depend on the blinding factor, and they’re not used to recognize the UTXO.
if there are less than 4 actors (so shares <3), double the shares per actor?
Sounds very reasonable. The polynomial degree should be at least (TBD), and then the number of shares per actor should be multiplied by some factor, if needed.
Just need to figure-out the number.
2 Likes