Discussion

https://twitter.com/kanzure/status/1168891841745494016

Chris Howe make a damn good start of a C version of Shamir secret sharing. We need to take it another level. This could be another project that we could engage on. We also didn't finish the actual paper, as such. I'd like to get both of those things resolved.

SatoshiLabs is saying that as far as they are concerned SLIP 39 is done and they are not interested in feedback or changing it or adapting it, at the words level. They just don't want to touch it. It seems like they are shipping it or are they manufacturing it already. On the other hand, they are fine if our libraries and things are abstracting the secret sharing from the encoding that allows for more functionality. The other trick is that there is some kind of header that you can kind of do-- since there is a checksum, you can change the header and see if the checksum is valid. So you can have a hacky way of doing a version which would allow you to use the encoding for other things. With their software, it would just checksum out and the checksum would be invalid because they assume the header would be the same.

They are willing to come in for a day. We also want to work on a custom secure chip. They are interested in the RISC-V architecture and various discussions about what is the minimum viable bootstrap for a secure chip and those kinds of issues. They would like to come in for a day, we should decide what day we would like them to come in, for either of those topics. They are here in Prague too but not physically here. So that's awkward.

The HTC people are here right now; they have effectively forked the Trezor sourcecode base and they run the Trezor source code in the executable environment of the trust zone. So it's more secure than a Trezor, and Trezor might not like that. I don't think it's competition; I would love to figure out how to engage with the SatoshiLab folks. Their comment was that the roadmap is on their website and all of their github issues are too, so why can't we work with them on this?

Adding write-once to HTC's TEE might require hardware changes. A Java Card is available for HTC. All of your fast memory chips are Secure Java cards because that's how they do fast memory. They are very interested in stuff and very supportive and they have a budget.

A tradeoff documents for Shamir secret sharing, multisig, verifiable secret sharing, and others. I would prefer to write code.

You split out the key into shares for each individual. That's a 256 bit number. So you can interpret this as a private key. It wasn't originally a private key, but you can use it as one. That's a secret that the owner of the share has. So the integrator can get a signed statement about what it should be signing, signed by that share. This is separate from the partial signatures approach. The signature you get here is not usable for blockchain signatures. The device can see 3-of-4... it's a way to communicate the request. If you had partial signatures, you wouldn't need the integrator and you could do it yourself, but that would require Schnorr or Taproot or whatever. Partial signatures are already viable as long as you can use Schnorr signatures.

Our goal is to have a decision about what it is that we want to try to do for this week. I think there's a lot of alignment here for things past this week. Let's gauge that and talk about the bigger issues. We talked about SatoshiLabs. I met with them recently. It was an interesting discussion. As far as objectives for Rebooting Web of Trust, I would love to finish that paper we started after rwot8 on just the peirls and promise of Shamir secret sharing. Do you guys feel like you want to work on the C library this week?

For the C library-- the previous Shamir implementation that was in the github repo had a bunch of countermeasures for sidechannel attacks. What I wrote didn't use those at all. There's certainly something to be done bringing that way of doing the gf256 arithmetic into my implementation. We can do tests. Daan's library was the most solid I was able to find. Take your implementation as a basis, but implement it into Daan's library. Either way. I am also interested in python bindings. I'd like the C code to have python bindings that more or less mirror SatoshiLab's implementation so that I can get rid of their code.

https://github.com/trezor/python-shamir-mnemonic/blob/master/shamir_mnemonic/__init__.py

Leohoven tends to take an adversarial approach to implementations. The students attack each other's code pretty hard. So by the time you get through their doctorate program, you've got a lot of adversaries that you have overcome.

So one thing we could do is python bindings and sidechannel resistance for a Shamir secret sharing library or integrating with Daan's library. Given the discussions with the SatoshiLabs people, they really don't want us to touch or change or adapt anything in the encoding aspect of SLIP 39. So how it takes the 512-byte secret and turns it into a 33 byte... So for the 256 bit, it's 33, for the 128 bit, it's 20. They don't want to change that. They have basically already put in orders for new hardware that supports this. They have committed to this path. They are open, though, to not blocking or being problematic about other layers getting built on this, like the stuff other than encoding into text. They are interested in supporting more features. Like sharing through the HTC secure network to the peers, they don't see what the words are, you can basically send them binary information instead. We should have a scheme for adding in the information that you want to store.

The format should include a memo field and also hashes of the other pieces so that you can be confident. They are arguing that you would only use this once every 5 years so it should be as short as possible. If you add more metadata, it's more information for the attacker. But I hate security by obscurity, so I would rather see it go in the other direction. We could use a varint for days since 1970 very easily. That would be 2 bytes for the birthday if you're worried about the space. You can store metadata outside the secret. So there could be another format, and the secret gets embedded in that other format. But that other format should still be specified.

The other thing that Daan's code does is that he assumed you might have a small, low entropy secret. He did something so that the entropy was spread... if you use Shamir secret sharing purely with low entropy secrets, it's more vulnerable. That's not required with a cryptographic key, because you already know it ought to be random to start off. I'm not sure which defensive programming assumption we want to take. We should have a more firm architecture between the encoding and the Shamir part and the pre-Shamir part of how do you choose your shares and some of the parameters. So if you have a short non-key secret, then you should generate a random key to encrypt that secret, keep the encrypted secret blob, and the Shamir shares of the key.

There is no upgradeability, by design, in any of the SLIP 39 stuff. They didn't want upgradeability. They said they would support any kind of binary standard for Shamir, which they are open to version information for that stuff. Their version byte says "SL" Satoshi Labs or something... so that makes it worse. It's also the initial vector for some other crypto stuff. They want you to check the checksum against the different IV values for different versions, but it's weird. Do we want to do a BIP instead, that isn't the Satoshi Labs one?

The SLIP 39 proposal has a lot of issues. The group stuff it has for specifying groups of thresholds isn't worth a lot. There's the 2 layer social key recovery thing. It's their way of doing it, which isn't what we specified at all. It lets you say-- do thresholding at a second layer, so it's k-of-n groups and for each group there's a different threshold. Most of the use cases I've considered or heard from anyone involves having different subgroups with different subthresholds based on which groups are selected. So say you have 4 groups, and you required within those, thresholds of 4-of-5, 4-of-7, etc., but if a different group of the high-level groups have a higher threshold, you might not need as much threshold as the other one. The reason why you would want to do this is not just micro-optimization but it's because you're trying to reduce the risk of loss. You're setting different thresholds so it's unlikely all the groups are going to experience catastrophic loss. These are separate splits.

I don't understand how the math would work for that. They are separate splits. They are somehow linked together. If a particular group appears in one instance as a 3-of-5 and another one as 4-of-5, there are two separate subkeys for that group. My second objection is that this seems much more complex to convey to users. That was our observation from rwot8, that this needs a good user interface design. There was an idea presented there about trust circles or social circles. The reason for the 2 levels is that, while you could nest this as much as you want, two layers is enough where if you had more than that it would be too confusing to users. But how do you represent the tradeoff about representing thresholds? This is why I wanted some of the UX people down here.

At the top layer, you have groups that as a group have specific trust in common. So one of the groups that was here, that was here last time at rwot8 was Ricachet, and they wanted to give out shares to your 100 instant messenger friends as one of the circles. So there they are going for resilience. Maybe it requires only 4 of the 100 to be restored. But because of that, you want to maybe have a family circle that must be able to have their quorum be reached. You want a mix of motivations. Statistically, you want their risk to be independent, which helps you better estimate likelihood of loss. As more groups are added with resilience, even if you require the same number of keys, you might be requiring it from independent groups that are unlikely to experience loss at the same time.

One thing that we could do is a template where we provide like 3 default templates for the users, and they could make an advanced one if they want. SLIP 39 doesn't let you use 4-of-100 because the numbers are limited to like 16. Technically you could have 100 shares, but you would have to strategically break it up into 14 or 16 shares each time. You're not getting this tradeoff, it's just a group of up to 16, and then there could be 16 groups,s o you can work out how many total people you have, but you might want to repeat them across groups too.

The benefit of SSS was large threshold groups. Multisig on bitcoin can't do that without paying high fees and doing presigned chains of transactions to have large multisig groups.

The threshold musig stuff that has been done since last time is drop-in replaceable. It's Shamir secret sharing on the secp curve. Besides the alignment with Bitcoin Core, this gives us a use for the musig work in the context for group signatures that aren't for authorizing bitcoin payments. There's at least five papers in this community where people are asking, how do we let a community sign for something? Especially when you talk about privacy-enhancing things, the wonderful thing about Schnorr is that in the end to verify that final signature, nobody can differentiate it from a single signer versus 100 people signing something. In the end, it's just a single Schnorr signature which helps for better privacy.

This links up with social key recovery. They can't sign for your bitcoin, because bitcoin doesn't support Schnorr yet, but they could sign a message on your behalf indicating something for some other protocol, in addition to being able to recover your bitcoin key.

Under Wyoming law, stockholders can be represented by keys, and all of the records of the company can be represented by cryptographic transactions now. So now we have the ability to say yes, the stockholders did sign the change of policy proposal or the new articles of incorporation because the old articles say it requires 60% of the shares and here are 60% of the shares signing to approve the change. There is also accountability and non-accountability issues that you can grapple with; Pieter Wuille had the tree signatures proposal.

There is no way to make multisig have cryptographic accountability, but you can prove it. So they could say, by protocol, you do sign-to-contract and who has signed would be part of it. You would need the signing threshold people use the right protocol. They can disable that if the entire signing threshold of people are colluding, which is true, but they could also take the bitcoin and do anything they want. In Shamir, if you give those people share, then those people as a group have 100% of control over that information. So that's the same there still.

There's a lot of stuff in the SLIP 39 spec that makes me nervous. The encryption I am not sure if that's secure, it doesn't look like it. We need to get bids from various parties to review parts of SLIP 39.

The feedback I got from Andrew was that there is a pull request for threshold signatures against Blockstream's version of the library. They aren't confident in the code (or it's not implemented) for the interactive protocol. This is using the shares to create a Schnorr signature. So they are also waiting for Schnorr and taproot to finalize for bitcoin, but they haven't looked at the idea of using this as an alternative to Shamir secret sharing. There's a concern about setup where everyone chooses their own share and they might sneakily choose one that is canceling someone else's shares. There's none of that when there's a delegator and he splits up the secret himself.

So we're thinking one thing we could do is write a BIP that is an alternative to SLIP 39 fixing some of the mistakes or strangeness.

When you start doing thresholds, you need much larger mnemonics. The number of shares increases at least linearly.

You could use a strict version of miniscript to do this, so that you can have support for arbitrary monotone boolean functions. Potentially you don't want to be on gf256 because the share space can grow much larger... the number of shares can be much larger than the size of that field.

We could implement something like monotone boolean functions with Daan's implementation of Shamir secret sharing, using miniscript either the C++ implementation or rust implementation.

References

Some references:

Abstract

Social key recovery allows users to collaborate with each other to securely recover their secrets instead of using centralized account reset procedures. Shamir secret sharing is an increasingly popular implementation for social key recovery, where a secret can be split into a number of shares with various threshold requirements or in the future any arbitrary monotone boolean function.

SatoshiLabs' SLIP 39 is one proposed implementation of Shamir secret sharing with mnemonics. SLIP 39 is Simple Shamir Secret Sharing plus a two-level fixed threshold group, and a mnemonic text encoding scheme, and an encryption scheme as well.

We are uncomfortable with some of the decisions in SLIP 39 and uncomfortable with the fact that they are all bound together tightly. In light of this, we are writing a Bitcoin Improvement Proposal that is loosely inspired by SLIP 39. In this BIP, the proposal includes a binary format, additional metadata (such as birthdate), allows for the greater flexibility of thresholds, optional pre-defined pre-parameterized threshold requirement templates, and one of the goals is to make the design so that it is possible to independently audit the independent parts of the proposal, making the proposal more modular. It will also be compatible with future upgrades like verifiable secret sharing and MuSig.

We are looking forward to championing this proposal in the community, collecting feedback, and driving the improvement proposal process. We also propose to make an implementation as required by the BIP process.

2019-09-04

TODO: better python bindings for libsecp256k1-zkp ?
python bindings for Daan's SSS library

SatoshiLabs has already conducted beta testing for SLIP 39. They are releasing it tomorrow. Changing the firmware would be problematic for them.

We're not going to address on the mnemonics. We're interested in a version 2 where the focus is a binary output that can be used for more interactive. Yes, that makes sense. We can have a standard that works for binary and works with various extensions that people want to use. So far we have been talking about Shamir secret sharing, but we want to enable VSS and MuSig capabilities in the future.

Some open concerns or questions were the nature of the implementation of the two level threshold in SLIP 39. So our question is whether we want to go with a different approach of how we do the two-layer approach. Templates make sense. In some business situations, the 16-of-16 limit--- the people at Richocet want to give out 100 shares. These wouldn't be given out as mnemonics, they will probably be given out as binary. In the binary format, it's perfectly okay to use many more shares. The point is that we wanted to keep the mnemonics short. Nobody is going to use 256-sized mnemonics.

If you have 500-of-1000, surely the share will be of fixed size? Every single word you add-- it's not individual words, it's the size of the metadata. We wanted to restrict it to some reasonable limits. So that's why we restricted it to 16.

There was discussion of using secp256k1 for the BIP. This would theoretically allow us to have compatibility to go in the direction for verifiable secret sharing. One idea was to use miniscript for the threshold requirements. This might be out of scope for the next 3 days though. We could do a reduced binary serialized miniscript. Just ANDs, ORs, threshold trees with a small binary encoding.

We want to have python bindings to Daan's C library. Howe proposed making better python bindings for libsecp256k1. You can't get the field part of it. secp treats all of its internal data structures as opaque. This would require writing some interface functions. This would be a fork of libsecp256k1 that implements threshold multisignature keyspace, and then exposes that to the bindings. There's a pull request in the Blockstream libsecp256k1-zkp. But their fork is going in the wrong direction. Their library is used for Blockstream Liquid. They have a PR that adds experimental stuff, like the threshold signatures.

Any wishlist things for SLIP 39? For Trezor, we think SLIP 39 is the best thing for hardware wallets that we have right now. We're not too curious about the binary format but we're willing to cooperate and throw our two cents in. SLIP 39 is intended for users writing down mnemonics on paper. With Daan's library, they send in a binary format to another phone. We use a PIN code to verify the public keys. They have an android app and iphone app signed by them that have the public keys in them so that they can receive these messages. It's a 3-of-5, so it has to be deprecated in Q2 2020 by HTC. Maybe offer more templates than the 3-of-5 that they offer right now. They also want to introduce a pruned full node on the node, and without the birthday metadata it requires the user to pick a this key was created date otherwise we would have to rescan the whole blockchain which on a pruned node takes 2 weeks. You can put down the birthday next to the SLIP 39 of course. The scenario is, someone says I want to use the key that was generated on some other hardware wallet, on the phone, and the only export they have is the SLIP 39 recovery words or whatever. We don't have Justin here, so I can't make decisions for the HTC team. So it's an optional restore and optional save.

We can still do mnemonics. We can defer the question of yet another mnemonic scheme, right now.

Threshold signatures pull request for libsecp256k1-zkp https://github.com/ElementsProject/secp256k1-zkp/pull/46

How can this be made more modular? Even without a mnemonic encoding thing, we should have a separate binary encoding module. We put a number of things out of scope for this BIP, and not just because of our compressed time. bech32 encoding is out of scope as well. The encryption scheme is out of scope as well.

So why is there the encryption in SLIP 39? What is the necessity for that? Why the choices of that symmetric algorithm? If you know bip39, then you're familira with the passphrase. This is the passphrase trick. It's like a password, but it also serves for plausible deniability. Whatever passphrase you enter, it gives you a valid wallet. You can have several wallets for your mnemonics. Each one is derived with a different passphrase. You can have one decoy wallet that you can use and be deniable. There's no way to check the passphrase in the standard, and that's a design goal that was used when we were designing this. It lacks authentication and integrity and it looks like bad crypto. But this is because this was one of the design goals.

We decided to not add to SLIP 39 where you can have more shares you can get the recovery key... we didn't want to make it too complex. The idea was that something about some inheritance shares which could be used as supershares or something like that. It's the mathematics behind it, not the specification. This can be added in the future very easily.

Should there be a checksum on the extra word in bip38-- that's what Lawrence did in the first variant of GreenAddress, he added the checksum there. In bip38, you still have the normal encoding of the bip39 words. But before you transform it into an xpub, you also add in (or it might be a hash or something) the entropy from the passphrase. In bip39, there was a PBKDF of 2, making it difficult to bruteforce. It's reversible in this case though. bip38 doesn't have any checksum on that extra word, it can be anything. It can even technically be binary. Errors in the 13th and 25th words seem to be one of the most common causes of total loss of funds and loss of recovery words, are errors in that word. They restored a wallet with the 25th word, they didn't type it exactly right and didn't confirm that the address was reproducible and whatever. So in the case of GreenAddress, they basically allow you to export that 25th word with a checksum.

Instead of an integrated specification that says how to do all of this, we're going to specify a binary encoding, and then there will be another BIP in the future that says this is how you turn a binary string into a set of words for backup purposes. If the final word is treated differently than the rest of it, that's irrelevant. So you can have two separate binary encodings, one for the core piece which is checksumed, and one for the final piece, or you checksum the whole thing.

You have a root wallet, which normally uses the bip32 method of deriving subkeys. But the 13th and 25th word allows for alternative or deniable wallets. So in our binary encoding, do we say, here is the root 512 bits for the master key, and here is 6 other wallets. Deniability can be an optional feature. People are going to want to encode the 2 words for their deniable and non-deniable wallet... the Wasabi coinjoin, everything in there is using this. You can't use Wasabi without that extra word. Users will expect to be able to encode into their user shares these extra entropy things. Not sure if we need to support this in the base BIP, but we need to know that this is in addition to birthdays that someone might optionally want to add to the binary.

You might not want that in your share? Maybe you're right. My take on it is, the number one loss mechanism is people improperly backing up that share. You make it less reliable when now there's one more piece of information that they have to backup or share in another way. The binary format should allow them to completely restore everything that they need. So then technically that word is a set of words, here are all the ones that I care about. In effect, it's subwallets.

If you have a deniable wallet and it has one extra recovery word, then you need a 100 bit passphrase or something to make this ungrindable. The 25th word is a "word" but it can be a passphrase. In bip39, the 25th word was allowed to be UTF encoding, but in bip38 we limited it to ASCII.

I never liked that field because the way you would end up using deniability in this context ends up destroying the secure things you're doing to protect your secret. You should not be giving up your secret, even a deniable one, to prove how much funds you have. When you do that, you have reduced your real wallet to the security of the passphrase, which is a huge downgrade from the previous setup you have. So we have this nice scheme for Shamir secret sharing and putting shares in safety deposit boxes, and then you give up the deniable wallet, and now it changes completely.

This might be useful for (COMPANY REDACTED), but it's not a good user interface to push on my mom for instance. But Mystery Company isn't going to use the 25th word-- they don't care about it. Your operational setup might make it not relevant, but the concern is kidnapping. You say to the attacker, look, I only control x% of the coins that are under custody. But people don't really have the keys on them anyway, in that operational setup.

You can use an envelope-encoding protocol. I think it's separate. Here's the 512 bits, and here's things like birthday and some number of extra wallets-- you might have several of these. Wasabi does this. You can design a protocol for specifying, given a secret, here is how you modulate it to--- this is basically what bip32 does. And have an encoding for those shares and those secrets as well. This is a separate discussion though.

The miniscript policy specification, you can at any point truncate in the middle. You have a tree specifying how to split out, and then you have a subtree which is the fake one and it's part of the larger one. To recover the whole wallet, you need to have the other part of the tree that is invisible. This lets you basically have nested key encodings and you stop the-- you extract out a subtree somehwere and make it an actual wallet. But people know you have one other branch that is secret split another way, and that needs to be recovered another way.

Right now we don't know what the optional data fields are going to be, but some candidates include birthdate (like days since 1970 which is easy to convert from unix epoch time). In CHECKSEQUENCEVERIFY, it's 512 second chunks. Yes, using that is fine. 600 seconds to a block, so it's approximately one block. Additional deniability features, like SLIP 39, would be nice. What about other metadata that might want to be shared in a longer binary secret? Metadata information about how many other shares are required and what the hash of the secret is, so you can verify you have reconstructed the correct secret.

For future extendibility, you want payload slots both inside and outside the share for adding metadata that we haven't thought of yet. The open question is, how much do we want to have outside the format? So presumably something that is outside the share is in every share, is that correct? In the scheme that I have imagined ,you have an arbitrary variable length string that you use for containing whatever information you want. You AES encrypt that with the secret, which is recoverable. So that's your metadata you can attach, and any one of the shares can have that, and they all have the encrypted blob, and to decrypt that you need to recover the full secret and then decrypt using a key.

But external information would be, I can look at a share and before reconstrucgint the secret, I know whether I can reconstruct it with some-- yes, the script policy needs to be outside the share. You need to have the policy for how the split is performed. We need some terminology here. You need to have the coordinate you're using to do the Shamir polynomial. If it's just simple Shamir, then that has to be there. The point on the curve, you have to have that. It happens that if you're just doing threhsolds, then you can just put them together and get the answer out. You do need to know how many and know the threshold, because if you don't have enough then you can get the wrong answer. If you have arbitrary AND and OR threshold trees, then you need to know that script policy. There is a minimal argument that you must have something that exists in this external outside-the-envelope container.

Is there anything besides that policy string that you need to encode? Family identification, that this thing belongs to this family of things. I could easily have 12 different share families or groups. Or maybe I have 3 different secrets, and I am going to split them up into completely different shares. I am going to distribute these around. When I'm gathering them up, I don't want to mix the families up or mix the shares from secret A up with the shares from secret B.

It can be free-floating information, but it must be in common with all the shares in the family. Say I have opened a safe deposit box, and it has a laminated piece of information and it has the words and the script policy and it has other information like its author. Is it important that the person who just found the document learns the creator information was cryptographically tied to the share? Bogus information here can be a real threat, when you bring the shares together. If it's cryptographically tied, does it need to be verified that this is the case before the keys are reconstructed? This idea of it being part of a family is really important. If you have two secrets and create shares for them, and they get disbursed, when they come back together they must not be mixed up and you want to sort them the right way- you could get garbage or malicious people doing bad things to your reconstruction.

Hashing and signing it, makes this less deniable. The deniability is only in the passphrase. If there's metadata in the share that is signed by the original key or master secret. There's a master secret you use to derive the wallet, but there's some pre-master secret that exists before you add the passphrase. You combine the shares to get the pre-master secret, then you apply the passphrase to get the master secret. We could be tlaking about the pre-master secret, which is not relevant for the question of plausible deniability. We already have something you talked about, in SLIP 39, is the identifier-- which is just a random number that we generate and we put it in front of each share which ensures the procedure you described. I like that idea, yes.

What's going on with bip39 and Lightning Labs recovery? I think they modified bip39 somehow to have a birthdate. I think they do that also. Their main motivation was that you can't go from an xpub back to recovery words. So they have a reversible....

Terminology

What do we call the whole thing? The total totality of the set. What's the whole package going to be called? In Shamir's original paper, he talked about dealing, and then reconstructing to build the secret back. You kind of have to create all the shares at the beginning in the deal. So is this called a "family"? A "deal"? Totality set. But "set" is used for everything. At Unchained, they were using "groups of shares" as "family". We liked the "circle" metaphor for the first level of shares. Circles and families. Is it called "the full deck", "the family deck", and "deal" is the verb. At some point, I "collect" and "reconstruct". It's beyond what you need to reconstruct. "Extended family" or "full deck". For now, let's go with full deck.

Quorum is a policy script. It's not just a number. When we have a qourum, which is some number of these shares, non-sequential etc., that's sufficient to recover the secret.

We need an area visible before construction, and one that is only visible after reconstruction.

In SLIP 39, the "share value" is the actual mathematical value. Then the rest was "share mnemonic". I like "share value", because that's what goes underneath the split. The "share value" is the mathematical y value payload that gets used reconstructed with the polynomial.

When I get dealt a card, which is one of the shares, what am I going to see? A policy, coordinates of where I am going to be in the share. Then there's the payload data. The payload is not just the share value or the split share. It's also wallet information necessary to load in the share. Like a bip32 derivation string. You might not want to reveal this information. The shareholder should have it, but it should be encrypted or hidden. So there's an encrypted blob with all the secrets, and the shares can decrypt the encrypted blob. When you're reconstructing, you need to have the encrypted blob. So that encrypted blob will be included with every share.

There's a publicly viewable thing with every share, and then there's an encrypted blob with each share. And the whole thing should be authenticated. It's an AEAD scheme where each share would have a different authentication tag, because each share will have some slightly different metadata like the x point, and that will need to be authenticated as well. There might be share-specific data which will be possible to define later or maybe something we come up with now. Combining the y values would give you the key to the AEAD scheme, sounds reasonable to me.

You used HMAC and 512 instead of AES? It was chosen so that it would be reversible. So right now, SLIP 39 is only used to split the master secret, which is used in bip32. But maybe you want to split a private key. In that case, you want to go the other direction. You want to first define the secret, then you want to unpassphrase it or encrypt it with a passphrase and then split that. If it's one-directional, then you get a master secret, which you have no control over, and maybe you do want to have control over that master secret because it's some curve or something. So right now it doesn't have a use, but we found that there might exist some use cases such as this one. Could you not just have used AES and decrypted the starting block? We could have, but there's some problems with AES-- padding stuff, as usual, and there's always ways around that. Another problem is that it's a very fast cipher, you want to have some sort of way to include delay, like PBKDFs, and then you now need multiple libraries like PBKDFs and one that does AES.

What symmetric algorithms are in Bitcoin Core right now, codewise? There was a new one recentlyt---- ChaCha20-Poly1305 but it's a bitcoin variant.. There's some others too. I want to minimize the audit footprint. There is an AES library in Bitcoin Core, and then there's ChaCha20-Poly1305 variant, and some PBKDF-- no that's not in Bitcoin Core. I have a preference, not a requirement, that any crypto that we can leverage that is already used in Bitcoin Core, because they have other reasons to audit, that we use that. Are any of those suitable? Bitcoin Core uses HDKDF. If there's not going to be a passphrase in this BIP, then you might not need one. This blob might have passphrases or other stuff, but you're not going to be able to get this blob unless you get your quorum.

I would like there to be an option of putting a verifiable passphrase on each share. So you can leave these things out in the open and not have someone just..... Okay, but now we have moved this to yet another thing that I have to secret share to be reliable to recover this. This would be optional, you don't have to do this. This is a social UX problem. People would say, the experts have put this in here, and therefore I should use it. But it dramatically lowers your reliability. We had this same conversation with SLIP 39. We wanted to put a passphrase on each share... it's just too complex for people. You're just moving your problem around. You can have it optional, I have nothing against that. We can get along with this not being in the standard, though. People also confuse the passphrase for their wallet with the passphrase to decrypt the shares. All the key derivation functions available to Bitcoin Core, honestly I think they should not be used in future protocols because they can be accelerated by an adversary with hardware very easily. There have been alternatives that have done well in competitions recently, but they have not been included in Bitcoin Core. Argon would be interesting, but you can't get it functioning well on a hardware wallet. You would need a lot of RAM to run it well. Argon requires a lot of memory. That's why it works. You can't do it on a Trezor or Ledger though. The alternative is to say, we're going to use this thing which you can do on a Trezor but is not actually as secure. The true alternative should be, we shouldn't be using a password security for this instance, maybe instead a dual scheme where they need the recovery of two different types of shares. There are other alternatives that are possible as well.

Why are we encrypting it all, if it can't get recovered until we have sufficient quorum until we're able to do this? The whole point of social key recovery is that you've lost it-- so you need to get it from the person you've given your share to.

A shareholder in a corporation has ownership of the corporation, but a shareholder of a share in a social key recovery scheme, is really just a shared custodian. Well then maybe share is a bad word too then. Shard is an alternative. It's a good word. I like shard. There's a "share custodian".

A share custodian might be share custodian for 20 different people and 40 different secrets. The shares need to be tagged and queryable. These cards are going to have information encoded on there, you can also encode it in text, the deck identifier so you know which one. Wolf's position is that the dealer should not put any information about his identity on the cards because then that allows somebody to go, oh, I've stolen this deck of cards and then they have an identifier. Then they can go try to find a quorum based on those people. Should there be verifiable information attached to the shards? There is a master secret and a pre-master secret, having to do with the whole full deck. That then signs the meta information. So that master secret has a public key associated with it that you can use to identify and figure this out.

A share custodian have a "share pool".

I have heard decks, shards, shares, and all of these terms. We should define some of these terms. There's also containers. There's a shard, a share value, a checksum on the whole thing. There's public information on the share that allows the share custodian to identify what to return from his share pool, which is actually bigger than the full deck. No, it's something else. Then we have the authentication of the shard, we have the public stuff that anybody can view. There might need to be a public policy. There would have to be. Then within the thing that is encrypted, we have the fundamental Shamir, and then we have this encrypted blob that is based on the fundamental Shamir but there may also need to be some authentication check on that whole thing. When we come back, let's puzzle out our names and whether we have all the pieces.

More terminology

What do we call the thing that we give to a share custodian? There could be shard and shard value. Or share and share value. I like shard over card. It has somehow resonated with lots of people. Shard is close to share, and close to card. It's close to both. I'm leaning in favor of shard. Also you can split something into shards. So the shard is given to the shard custodian.

Ideally, it's the shard dealer that reconstructs the original secret. There is probably not a universal word for that. In bridge, when you clean up the pile of cards, what is that called? It's "collector" or "aggregator". Is partial a good description? A "partial" instead of a shard. For me, "partial" means "incomplete", but it also means "incomplete transmission" which is not the case here. You have your full transmission, it's just one part of a whole.

Quorum is fine. Full deck is fine. The script policy describes what the quorum is going to be. A script policy (which is basically a predicate) can have many possible quorums.

I think we should have a "shard pool" which is the sum of all of the shards from many decks. You can identify a shard by a hash, or a public key, or whatever else.

We don't necessarily need to use the "persona" terminology but that might be of some value. There has to be some 256-bit identifier or hash, that has to do with the master secret as well as identification for each individual shard. So it would be within scope to specify how that hash is constructed, and then aspects of displaying it in a way that a user can identify it.

The share value is-- the actual bytes that represent the words. We have a collision of names here. We were also calling that a "share value". That's what they are saying for SLIP 39. The share value he is talking about it, is before you have reconstructed it or after? Before. It's the y value. So there's no collision.

There is an encrypted master secret in SLIP 39. This is encrypted by the passphrase, after the Shamir reconstruction. It's not encryption, it's derived from the passphrase. It's always derived from something. Given a master secret, you can't go back to the words, but you can construct a whole new set of shares. In SLIP 39, there's an element of randomness when you do the splitting. Shamir adds all this extra entropy on top of the--- but that can be done deterministically by seeding a random number generator. In SLIP 39, it's not done, but it could be. You shouldn't be worried about recreating shares; you want to be able to reconstruct the master secret.

The master secret should be called the "derived secret". So we're doing bip32 derivation originally-- the origina lvalue can be "root secret" or "seed secret". So it's the seed entropy that goes into bip32. This is the initial value you created in some way. Then you applied the password to derive the derived secret, and then you split it out into shares? SLIP 39 bolts on top of bip39. You can roll it backwards from your wallet words to re-create the seed entropy, to go back to shares. SLIP 39 reconstructs, after the password derivation technique, the shared master secret-- is the same as the seed entropy. When you do the reconstruction, you get the seed entropy, which is then applied with the password derivation to get the derived seed. Okay, you're right. I'm mistaken. Because you use reversible direction, you can go in any direction. In bip32, you need 512 bits, so you run it through HMAC 512.

To a certain extent, we don't care about the derived secret. People are going to use standard tools to take the seed entropy and turn it into a derived secret. We're not defining how to take this into a derived secret. Are you going to be using, in the binary format, and you're not going to save every bit of space, then it's an encryption key not the master secret. Then you encrypt the secret. We want to shard up the encryption key, so that the blob can be decrypted.

"Deck blob" might be too weird. We're calling that whole thing a "persona" in the wallet, instead of calling it a wallet or something. You might have a persona which is your personal funds, or a persona for your master key for your employer.

Are we going to assume that the person is going to store the secret in a second place? Like 1-of-1. This might be stupid, but can we do things to dissuade them from doing this? Are we eliminating the user in SLIP 39 from being able to see the secret? We allow them to split it only once, or extract it from the device only once. They can't extract a regular bip39 one... You can either recover with the share technique, or you can use the traditional, but not both. Nothing stops you from combining the shares on your computer and then doing whatever. Still, that's an interesting case.

To a certain extent, in the smart custody book, we're basically telling you to put the 24 words onto a titanium key which can resist California fire. Yes, I have the risk that if I put it in the bank and it burns down then someone can break into the box and get the titanium key. I have this nice, absolutely cold, fire resistant thing that I will not have the equivalent by default with this approach. Well, you can store binary words into titanium. You can etch a QR code into titanium. You might need a machine to do it for you. You could sit there with a dremmel if you want. I don't necessarily want to forego a titanium recovery key backup system. In SLIP 39, they are doing a mutually exclusive recovery technique. For a user perspective, will we make that same decision? Or will some user wants to be able to do both?

I think we're doing something different from that. We're building a Shamir secret sharing scheme that isn't necessarily dedicated to building an HD wallet. You want it for social key recovery, for example. What goes into the encrypted payload is whatever you want. It's potentially larger than you could expect to write down as wallet words.

Shard: A member of a deck, with both unencrypted visible information (including a shard value) and encrypted hidden information. The encrypted hidden information is encrypted by the original secret, and the dealer distributes the encrypted hidden information to each user. You want to know the unencrypted metadata, the identifier information, then there's private data which is encrypted with the key which gets derived from the secret. Then there's the y value, and then a checksum over all of this.

Many cryptographers would say don't use the same private key for a symmetric encryption and a private key. Well, we're not. You would derive a set of keys for that purpose, and you certainly wouldn't use the same bits for different purposes. The entropy here would be some acceptable value, it's not zero and it's within the group order. Those are technically some bits, don't think you can get anything out of that, but to be safe you hash it and use that as the entropy.

The reconstruction of a Shamir secret cannot be done incrementally. It would have to be done all at once, to build up the Lagrange polynomials. You take the x and y values of all the shares and you build a bunch of components that you add up to get the ... How many of those have to be in memory? Do we need to have all of them in memory, for trust purposes? I think you need to have all of them in memory. I don't understand the limits as far as how to describe the limits. Yeah, they will have to be in memory. There might be constraints from a hardware device. SLIP 39 has a constraint of 16 because of GF256 but also because of the metadata format.

Mathematically it might be possible to do incremental or progressive. What you need to have in memory are the x values. But the actual secret y values, you can get those progressively. In practice, you have it all in memory because it's paired together. Moving in and out of the trustzone environment is expensive. The complexity of your construction goes possibly quadratically, I'm not sure. I think it does. Which is probably the bigger concern, if you're getting into large numbers.

Terminology glossary

Shard dealer: An individual that has a secret that is sharded using this secret sharing scheme. The user makes a number of shards that are dealt out to different users to turn each user into a shard custodian.

Deck: A collection of shards that together can be combined (in at least one way) to reconstruct the sharded secret.

Deck identifier: Derived from the sharded secret. It is the public key derived from the sharded secret unmodified with no derivation and no other modification. The deck identifier is a public key that uniquely identifies the deck. This key can sign each shard.

Script policy: A script that specifies a policy for how the deck's secret (seed entropy) can be reconstructed from some combination of shards.

Quorum: Any set shards sufficient to meet the script policy for reconstruction.

Shard: A shard includes unencrypted metadata, an unencrypted Y value and checksum, and private encrypted data.

Shard unencrypted metadata (public metadata): Data associated with a shard that describes the shard and the deck among other things. This includes birthdate, deck identifier information, and so on.

Shard value: The mathematical or cryptographic value that can be used in the secret sharing scheme to reconstruct the sharded secret. This is the y value.

Private data (encrypted) (encrypted blob or deck blob): Encrypted data transferred with each shard. The decryption key can be computed by recombining all the shards.

Shard custodian: A user that holds a number of shards, possibly from multiple different decks.

Shard pool: A shard custodian can use software that implements a shard pool that contains their collection of shards they are responsible for. The shard pool allows for querying over the set of shards to find particular shards to respond to a request.

Sharded secret: Used to create the derived secret. This is used both as symmetric key and as a private key. This is a high entropy secret.

Derived secret: The derived secret is used to decrypt the identical private data associated with each shard.

2019-09-05

It is important to give the shard owners a mix of motivations. Choose some family members, friends, some of your twitter followers, etc. It requires a mix of motivations. Some people that have familial love for you, others that like you merely because you pay them. Look at the risk that a member of a circle will collude with another member of another circle or something. What's the collusion risk? The risk is high in the case of randomly selecting from your twitter followers.

A fun demo would be a twitter oauth demo where your followers login and authenticate by their twitter handle, and then distribute shares to them.

It would be nice if there was a way to detect that shares are being collected. Could a secret only be revealed to the spender when they spend it? You could have a watchtower that looks at the blockchain and only once all the shares are released does it decrypt something else that it can broadcast. But this requires an extra watchtower.

On trezor, you have to choose bip39 or SLIP 39 immediately. And you can't change it later. This is a limitation of Trezor. In practice, it is possible to take a bip39 secret and distribute it using Shamir secret sharing.

https://github.com/jedisct1/minisign is Schnorr signatures + ed25519. It only does signing and verification. It's like gpg --sign but no other gpg features. It would be nice to have a Schnorr-style hierarchical aggregated multisignature. ECDH has the public key embedded in the signature, and in Schnorr this is not the case.

Most of the concerns with SLIP 39, like the choice to not use AES, are mostly resolved. Using the flysuite network in the way they do, it makes the encryption reversible and there's good reason to do that. It wasn't explained very well, that's why you have to choose. It's not their fault: bip39 used one that is not reversible. You can't take a SLIP 39 secret and figure out what password would be usable to encrypt that out into... Really we should be forking bip39. We could fork bip39 and make it compatible with SLIP 39, making yet another one. We can talk about the details of that later if they are interesting to you. I'm not too concerned about most of their choices. There's no real cryptographic reason to think it is insecure, given their justifications. The only thing that remained that is pretty non-negotiable is their 2 level circles and groups scheme is not compatible with the types of use cases we were thinking about for social key recovery.

The example that I gave at the rwot8 which I'll repeat here because it's typical of what you might want to do... Say I start a business with 4 other cofounders and we have a 4-of-4 key that we want to use to authorize any changes to the business. 4-of-4 is dangerous for redundancy reasons. One of your concerns as a co-founder in a business is that all of your other cofounders nominally operate in the best interest of the business or what your vision of the company is; they might choose to write you out of it. You don't want the 3-of-4 cofounders to just write you out of it. It could be 3-of-4 but then it requires 2 of my family members or something. The reason why 2 is because one of the family members might get romantically involved with one of the other co-founders. You have three separate circles: coworkers, friends and family. The key aspect is that when you're involving other circles, you're typically doing it because you're dropping the threshold on another cirlce. When you drop the threshold, you have to involve another circle. This lets you, for each possible spending condition, maximize the security that you can get--- lets you operate at optimal security with minimal risk of loss from the aggregate shares that might be lost. Unfortunately in SLIP 39 you can specify any number of coworkers, friends and family, limited to 16, but the bigger limitation is that within each circle, you also have to specify which-- a fixed threshold for that circle which is true for all of the policies. You have to choose for your coworkers circle, you have to choose 4-of-4 or 3-of-4. You can't have it be different for different policy paths in SLIP 39. At the top level, you can specify 2-of-3 of my set of 3 groups. There are no different policy paths in SLIP 39. The policy is, you have n groups and each of n group is A of B. And then you have to have of those n groups, you need to have m of them. That's the policy. There can't be multiple policies. SLIP 39 is a threshold of a threshold. There's a list of groups, and a threshold of those groups have to sign; each group, there's a threshold of signers, and that's fixed. If you vary which groups are involved, you don't get to readjust the thresholds for the group sets. That SLIP 39 limitation nullifies most of the advantages of this approach. The justification for the circles that gets nullified here is that the requirements for security in terms of protection from theft, and the requirements for lower threshold to prevent loss of funds, are at odds with each other. With regular thresholds, by my estimation, you cannot create something that is both secure enough to use and not likely to be lost. Or alternatively, you can say the mean time before theft is lower than the mean time before key loss. Theft or key loss would happen before the lifetime expiry of the...

You can make multiple different SLIP 39 decks if you want to do different more elaborate policies. Then you distribute the SLIP 39 shares to the correct parties. By giving multiple shares to each user, the encrypted blob is the same and sent only once if each person gets multiple shares from different paths. But the metadata is different for each share, mostly.

SatoshiLabs didn't like the variable length property of my rwot8 proposal. This reduces the total number of words to write down.

At the top level there is 1-of-1 which is "me". This makes it an improvement on SLIP 39 for key export. Now we can say, myself is a circle in a sense. I might be a member of the company, but I'm not a friend and not a coworker, I'm me. I can use the secret, the payload, whatever we call that is all the same. Any other advantages we have there are all the same. If later we come up with a good compacted coding scheme, or QR code, to be consistent across.

You want to be able to specify the envelope container format that has these shares, that also has the encrypted data, the metadata, and specify how the master secret is used to validate encrypted data, and so on. There are some other key differences too, like the binary serialization format. We're also removing the constraints about the sizes of the groups from 16 to larger. There could be a policy flag like gf256 policy flag, and then another one where we have a different policy which is the VSS. The envelope would be versioned. If you want to maintain that version 1 is SLIP 39 compatible, then we can't muck around with the number of groups or the password derivation function. Ricochet wants to give out a very large number of shares out to people.

The maximum threshold is the size of the field you're doing this over. For gf256, you can have at most 255 shares. If you're in the field that secp256k1 is over, then it's something a little bit less than 2²⁵⁶ shares.

You can combine this with Reed-Solomon and have an error correcting code. One of the QR codes recommended to us, they very specifically worked on a QR code system with an interleaved error correcting type system. The reason why they picked their particular one is that the field is a minefield of patents. But something in that family, yes. Fountain codes, or something. You can come up with a scheme where you have 100-of-10000 share, but if you collect 150, then you can correct 50 errors. If people can send you bad recovery shares back, you can correct errors from them if you have enough. This gets you around people sending you malicious messages; but if you have the shares signed then maybe that doesn't matter. Script type 2 can be a Reed-Solomon error correction thing.

I am writing a Shamir module to fit into the libsecp256k1-zkp library. The multisig aggregation pull request, against the zkp library. That one is doing multisig aggregation but it's using Lagrange polynomials to aggregate signatures. So just use that. That's the idea. I don't want to rewrite it, unless they have done it wrong.

I believe the threshold signature stuff does Lagrange polynomials over curve points, and you would be doing it over field elements. I don't know how it works. I don't believe you. There's no division on-- you only have addition on curve points. It's not a field, it's a curve. You need a field to do Shamir. You need addition and multiplication.

Daan's library is over gf256. For VSS, you need to be using the secp curve. The fancy hazmat stuff doesn't apply, and the actual math doesn't work because of the sign thing. It has to be rewritten. It's not very hard though.

2019-09-06

The birthdate can be in the encrypted area.

Using the reconstructed secret as a private key might be a problem. Say you have 2-of-3 and you reveal the last byte of 2 of the shares. You think you're perfectly safe. But since the secret sharing is done bytewise, then you have revealed the last byte of the... So you can hash the secret. You use the PBKDF to distribute the entropy evenly. Once you get information about bits from the private key, you are opening up to attacks on elliptic curves. So just do a hash, and that will be fine. Hash it, and derive several keys like an encryption key and a signing key, and you derive many more bits than is the actual entropy of the secret. You don't want to reuse the key of course for the.. purposes. There aren't any good signcryptions yet, like AEAD.

Yesterday we decided to maintain SLIP 39 compatibility.

The checksum property violates the Shamir property. You're collecting some theoretic amount of information about the final result. You don't have 32 bytes of entropy left, you only have 28 bytes of entropy left. Instead, you can hash the original secret and store that hash. The checksum on each shard is okay, to make sure the shard information is stored correctly.

A pure shamir in theory when you have a 6-of-7-of-10, you have no knowledge of the secret. But in our secret, because of the checksums, if you have the 6 of the 7-of-10, you have a tiny amount of the 7th, perhaps as much as 4 bytes. Not the actual 4 bytes of it, but 4 bytes of its entropy. You've reduced the search space by 32 bits. We should probaly mention this in passing. Probably in the future, when there's 1000s of shares, there might be something where the it actually becomes feasible for you to restore it missing a share or something--- this might impact us or something. No, I don't think so. This doesn't scale that way. As you scale out more shares, you're adding more entropy to the stuff required to deal. So that scales the right way for security purposes. The problem would be decreasing the size of the secret. We said in SLIP 39 the minimum is 128 bits. In the worst case, if everything goes bad, you only have 96 bits of security, regardless of the number of shares.

I don't think we're going to have the checksum in our binary serialization. Are we talking about the same checksum? The last three words? No, it's a different checksum. There's a checksum for each share. So if you make a mistake in typing one of the words, you can immediately see it. But it's not cryptographic, in that anyone can false that. You are talking about a checksum on the actual secret, which is a result of combining the shares. In SLIP 39, I think this is called a digest. Yes, we call it a digest, to differentiate it from the checksum on each share.

It's really useful to be able to tell at the end of this thing, that you have got the right one. We already have a way of doing that, because we have a signature. We're pre-authenticating that the shares are correct when you receive them, because they have a valid signature. So we don't need a digest. Other than the SLIP 39, does not have a way to do that. Can you initialize a trezor device with SLIP 39 without the digest? It would not be valid shares.

https://github.com/BlockchainCommons/sss/pull/2

Large engineering project risk management using a bayesian belief network http://sci-hub.tw/https://www.sciencedirect.com/science/article/pii/S095741740800448X