Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
This comes up every few months. I think the problem you are trying to solve is already solved by SSL client certificates, and if you want to help make them more widespread the programs you need to upgrade are web browsers and not Bitcoin wallets. There are certainly bits of infrastructure you could reuse here and there, like perhaps a TREZOR with a custom firmware extension for really advanced/keen users, but overall Bitcoin and website authentication are unrelated problems. On Fri, Apr 4, 2014 at 2:15 PM, Eric Larchevêque ela...@gmail.com wrote: Hello, I've written a draft BIP description of an authentication protocol based on Bitcoin public address. By authentication we mean to prove to a service/application that we control a specific Bitcoin address by signing a challenge, and that all related data and settings may securely be linked to our session. The aim is to greatly facilitate sign ups and logins to services and applications, improving the Bitcoin ecosystem as a whole. https://github.com/bitid/bitid/blob/master/BIP_draft.md Demo website : http://bitid-demo.herokuapp.com/ Classical password authentication is an insecure process that could be solved with public key cryptography. The problem is that it theoretically offloads a lot of complexity and responsibility on the user. Managing private keys securely is complex. However this complexity is already being addressed in the Bitcoin ecosystem. So doing public key authentication is practically a free lunch to bitcoiners. I've formatted the protocol description as a BIP because this is the only way to have all major wallets implementing it, and because it completely fits in my opinion the BIP process category. Please read it and let me know your thoughts and comments so we can improve on this draft. Eric Larcheveque ela...@gmail.com -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
On Fri, Apr 4, 2014 at 3:22 PM, Eric Larchevêque ela...@gmail.com wrote: I see only benefits for the entire ecosystem, and if I'm working on such a proposition it is because I really need this feature. Why do you need it? Because you don't want to implement a login system? Very, very few websites are the sort of place where they'd want to authenticate with only a Bitcoin address. If for no other reason than they'd have no way to email you, and if you lost your wallet, you'd lose all your associated data. Without such a standard protocol, you could never envision a pure Bitcoin physical locker rental, or booking an hotel room via Bitcoin and opening the door through the paying address. In future there often won't be a simple paying address. For instance, if my coins are in a multi-sig relationship with a risk analysis service, there will be two keys for each input and an arbitrary number of inputs. So does that mean the risk analysis service gets to open my locker? Why? What if I do a shared spend/CoinJoin type tx? Now anyone who took part in the shared tx with me can get into my hotel room too? These are the kinds of problems that crop up when you mix together two different things: the act of paying, and the act of identifying yourself. You're assuming that replacing a password people can remember with a physical token (their phone) which can be stolen or lost, would be seen as an upgrade. Given a choice between two physical lockers, one of which lets me open it with a password and one of which insists on a cryptographic token, I'm going to go for the former because the chances of me losing my phone is much higher than me forgetting my password. All the tools you need already exist in the form of client certificates, with the advantage that web servers and web browsers already support them. The biggest pain point with them is backup and cross-device sync, which of course wallets suffer from too! -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
On Fri, Apr 4, 2014 at 9:43 AM, Mike Hearn m...@plan99.net wrote: These are the kinds of problems that crop up when you mix together two different things: the act of paying, and the act of identifying yourself. This is precisely why SINs use a different version byte from bitcoin addresses. There should never be any confusion between money/payments and identity. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
Using a bitcoin address repeatedly is something we're trying to move away from. This is indeed a flaw of the proposed protocol. However it really depends in the end of the usage : you could use an auth just once, to redeem a good you paid, or multiple times if this makes a sense (mining pool app for instance). And using a bitcoin address as a persistent identity key feels like the wrong direction to me. What would be really the difference between artificially create a certificate for identity and selecting one address for identity? Better to use something like client certificates, the FIDO alliance's (new!) specs: http://fidoalliance.org/specifications/download ... or Steve Gibson's proposed SQRL system: https://www.grc.com/sqrl/sqrl.htm The proposal is nothing more than sqrl scoped to Bitcoin keys. If one of those systems gets critical mass and actually starts being successful, then I think it would make sense to specify a standard way of using a HD wallet's deterministic seed to derive a key used for the FIDO or SQRL systems. This could be a very interesting approach. But I think the system which would get critical mass is the one which would be implemented into major Bitcoin wallets. Why adding another app or software when you already have all you need? On Fri, Apr 4, 2014 at 9:22 AM, Eric Larchevêque ela...@gmail.com wrote: What I'm trying to achieve, is to have a very simple way of authenticating yourself with one Bitcoin address from your wallet. For most of the people using Bitcoin, their wallet is on their phone. The UX is clear and simple : 1. click on connect with Bitcoin (the audience is normal people) 2. flash the QRcode with your wallet (blockchain.info, mycelium, ...) 3. accept the authentication request (same style than OpenID or Facebook connect) 4. user is autologged and identified by the chosen Bitcoin public address It makes sense only if major wallets are supporting the protocol. If you need to install a plugin or download a third party software, no one will do it. I see only benefits for the entire ecosystem, and if I'm working on such a proposition it is because I really need this feature. Of course, it can be done without a BIP, I just need to convince wallet developpers one by one to implement the feature. But I thought it was much better to start the official way, so all wallet could easily find and implement the same authentication mechanism. Bitcoin and website authentication are unrelated problems I respectfully disagree. Many services require your Bitcoin address, and to do that they artificially request an email/password to store it. This is not about authentication as an identity (as I'm Eric Larcheveque), but as in I'm proving to you that I control this address. Without such a standard protocol, you could never envision a pure Bitcoin physical locker rental, or booking an hotel room via Bitcoin and opening the door through the paying address. Eric On Fri, Apr 4, 2014 at 3:08 PM, Mike Hearn m...@plan99.net wrote: This comes up every few months. I think the problem you are trying to solve is already solved by SSL client certificates, and if you want to help make them more widespread the programs you need to upgrade are web browsers and not Bitcoin wallets. There are certainly bits of infrastructure you could reuse here and there, like perhaps a TREZOR with a custom firmware extension for really advanced/keen users, but overall Bitcoin and website authentication are unrelated problems. On Fri, Apr 4, 2014 at 2:15 PM, Eric Larchevêque ela...@gmail.com wrote: Hello, I've written a draft BIP description of an authentication protocol based on Bitcoin public address. By authentication we mean to prove to a service/application that we control a specific Bitcoin address by signing a challenge, and that all related data and settings may securely be linked to our session. The aim is to greatly facilitate sign ups and logins to services and applications, improving the Bitcoin ecosystem as a whole. https://github.com/bitid/bitid/blob/master/BIP_draft.md Demo website : http://bitid-demo.herokuapp.com/ Classical password authentication is an insecure process that could be solved with public key cryptography. The problem is that it theoretically offloads a lot of complexity and responsibility on the user. Managing private keys securely is complex. However this complexity is already being addressed in the Bitcoin ecosystem. So doing public key authentication is practically a free lunch to bitcoiners. I've formatted the protocol description as a BIP because this is the only way to have all major wallets implementing it, and because it completely fits in my opinion the BIP process category. Please read it and let me know your thoughts and comments so we can improve on this draft. Eric Larcheveque ela...@gmail.com --
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
What if I do a shared spend/CoinJoin type tx? Now anyone who took part in the shared tx with me can get into my hotel room too? Oh, if these seem too abstract, also consider bitbanks. In an ideal world nobody would outsource running of their Bitcoin wallet, but sadly people do, so then they don't control the private keys at all. The goal of writing a BIP seems to be to get lots of different wallet authors to write lots of code for you - but I *am* a wallet author, and I don't think that's the right way to get traction with a new scheme. For instance the TREZOR guys would have to support your new protocol otherwise if I paid my hotel bill with my TREZOR I couldn't open the door when I got there! But they probably have better things to be doing right now. The key difference between just generating a client certificate and using a Bitcoin address is that the client certificate is something that is used *specifically* for identification. It leaves no trace in the block chain, so no weird privacy issues, it doesn't matter how you manage your wallet, and you don't have to persuade lots of people to support your idea because it was already done 10 years ago and basically every browser/web server supports it. Some reasons client certs aren't more widely used boil down to: 1. People like passwords. In particular they like forgetting them and then having friendly people assist them to get it back. Client certs can support this use case, but only if apps are checking the identity in them and not the key. 2. The UI for managing client certs in browsers is pretty horrible. There's little incentive to improve it because of (1). 3. Cross-device sync doesn't work very well. Apple are starting to tackle this with their iCloud Keychain Sync service but then of course, Apple has all your keys and you may well just sign in to things with your Apple account (if it were to be supported). Cross-device sync where the server *doesn't* get your keys is supported by Chrome for passwords, but not client certs, because (1) None of the above issues have any obvious fix lurking within Bitcoin. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Fri, Apr 4, 2014 at 6:51 AM, Nikita Schmidt nik...@megiontechnologies.com wrote: Fair enough. Although I would have chosen the field order (p) simply because that's how all arithmetic already works in bitcoin. One field for everybody. It's also very close to 2^256, although still smaller than your maximum prime. Now of course with different bit lengths we have to pick one consistency over others. Operation mod the group order is how secret keys must be combined in type-2 private derivation for BIP-32. It's also absolutely essential if you want to build a secret sharing scheme in which the shares are usable for threshold ECDSA. I still repeat my concern that any private key secret sharing scheme really ought to be compatible with threshold ECDSA, otherwise we're just going to have another redundant specification. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
The goal of writing a BIP seems to be to get lots of different wallet authors to write lots of code for you - but I *am* a wallet author, and I don't think that's the right way to get traction with a new scheme. I started without a BIP and the feedback I got is that I should to a BIP. We cannot write all the code for all the wallets ; this is after all a communauty project. However we have and we will propose bounties for each wallet to support natively the protocol. For instance the TREZOR guys would have to support your new protocol otherwise if I paid my hotel bill with my TREZOR I couldn't open the door when I got there! But they probably have better things to be doing right now. Yes you are right. But if the concept of authenticating yourself gets traction, they will probably do it. The key difference between just generating a client certificate and using a Bitcoin address is that the client certificate is something that is used *specifically* for identification. It leaves no trace in the block chain, so no weird privacy issues, it doesn't matter how you manage your wallet, and you don't have to persuade lots of people to support your idea because it was already done 10 years ago and basically every browser/web server supports it. My view on this is mainly about the UX and the fact everyone in Bitcoinland has a wallet. It's a approach leveraging this fact, with the possibility to build interesting apps combining address auth and the blockchain. I understand the problems related to multisig, contracts etc, There is no such thing as a from address in a transaction, however many services still take first tx as the return address. People will always find way of building and doing stuff (cf the message in the blockchain debate). Some reasons client certs aren't more widely used boil down to: 1. People like passwords. In particular they like forgetting them and then having friendly people assist them to get it back. Client certs can support this use case, but only if apps are checking the identity in them and not the key. 2. The UI for managing client certs in browsers is pretty horrible. There's little incentive to improve it because of (1). 3. Cross-device sync doesn't work very well. Apple are starting to tackle this with their iCloud Keychain Sync service but then of course, Apple has all your keys and you may well just sign in to things with your Apple account (if it were to be supported). Cross-device sync where the server *doesn't* get your keys is supported by Chrome for passwords, but not client certs, because (1) None of the above issues have any obvious fix lurking within Bitcoin. There is also the benefit of revocation with certificate and central authority. But, again, you already have a wallet and a Bitcoin address. So if you add a simple auth protocol, people will use it at no cost. Eric -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
Why do you need it? Because you don't want to implement a login system? Very, very few websites are the sort of place where they'd want to authenticate with only a Bitcoin address. If for no other reason than they'd have no way to email you, and if you lost your wallet, you'd lose all your associated data. Well, the major difference is that you could sign up effortlessy to a service, and associate your email later. If more people sign up to more services, it's a good thing for the ecosystem. Without such a standard protocol, you could never envision a pure Bitcoin physical locker rental, or booking an hotel room via Bitcoin and opening the door through the paying address. In future there often won't be a simple paying address. For instance, if my coins are in a multi-sig relationship with a risk analysis service, there will be two keys for each input and an arbitrary number of inputs. So does that mean the risk analysis service gets to open my locker? Why? What if I do a shared spend/CoinJoin type tx? Now anyone who took part in the shared tx with me can get into my hotel room too? In a perfect world, you would pay your locker with a normal transaction. The same way you shouldn't play satoshi dice from a shared wallet. But your point is totaly valid, and I don't have answer to that except that I'd love to have a Bitcoin authenticated locker in our Bitcoin co working office. These are the kinds of problems that crop up when you mix together two different things: the act of paying, and the act of identifying yourself. You're assuming that replacing a password people can remember with a physical token (their phone) which can be stolen or lost, would be seen as an upgrade. Given a choice between two physical lockers, one of which lets me open it with a password and one of which insists on a cryptographic token, I'm going to go for the former because the chances of me losing my phone is much higher than me forgetting my password. All the tools you need already exist in the form of client certificates, with the advantage that web servers and web browsers already support them. The biggest pain point with them is backup and cross-device sync, which of course wallets suffer from too! Bitcoin users are normaly already paying some effort to securise and backup their wallets / keys. So it's just about leveraging that. I would myself pick a crypto locker, because I'm the kind of guy who Facebook connects and I follow the easiest path, even if it has long term costs :) Eric -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
I'm cracking my head for many months with the idea of using TREZOR for web auth purposes. Unfortunately I'm far from any usable solution yet. My main comments to your BIP: Don't use bitcoin addresses directly and don't encourage services to use this login for financial purposes. Mike is right, mixing authentication and financial services is wrong. Use some function to generate other private/public key from bitcoin's seed/private key to not leak bitcoin-related data to website. Cheers, Marek On Fri, Apr 4, 2014 at 4:42 PM, Eric Larchevêque ela...@gmail.com wrote: The goal of writing a BIP seems to be to get lots of different wallet authors to write lots of code for you - but I *am* a wallet author, and I don't think that's the right way to get traction with a new scheme. I started without a BIP and the feedback I got is that I should to a BIP. We cannot write all the code for all the wallets ; this is after all a communauty project. However we have and we will propose bounties for each wallet to support natively the protocol. For instance the TREZOR guys would have to support your new protocol otherwise if I paid my hotel bill with my TREZOR I couldn't open the door when I got there! But they probably have better things to be doing right now. Yes you are right. But if the concept of authenticating yourself gets traction, they will probably do it. The key difference between just generating a client certificate and using a Bitcoin address is that the client certificate is something that is used *specifically* for identification. It leaves no trace in the block chain, so no weird privacy issues, it doesn't matter how you manage your wallet, and you don't have to persuade lots of people to support your idea because it was already done 10 years ago and basically every browser/web server supports it. My view on this is mainly about the UX and the fact everyone in Bitcoinland has a wallet. It's a approach leveraging this fact, with the possibility to build interesting apps combining address auth and the blockchain. I understand the problems related to multisig, contracts etc, There is no such thing as a from address in a transaction, however many services still take first tx as the return address. People will always find way of building and doing stuff (cf the message in the blockchain debate). Some reasons client certs aren't more widely used boil down to: 1. People like passwords. In particular they like forgetting them and then having friendly people assist them to get it back. Client certs can support this use case, but only if apps are checking the identity in them and not the key. 2. The UI for managing client certs in browsers is pretty horrible. There's little incentive to improve it because of (1). 3. Cross-device sync doesn't work very well. Apple are starting to tackle this with their iCloud Keychain Sync service but then of course, Apple has all your keys and you may well just sign in to things with your Apple account (if it were to be supported). Cross-device sync where the server *doesn't* get your keys is supported by Chrome for passwords, but not client certs, because (1) None of the above issues have any obvious fix lurking within Bitcoin. There is also the benefit of revocation with certificate and central authority. But, again, you already have a wallet and a Bitcoin address. So if you add a simple auth protocol, people will use it at no cost. Eric -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
On Fri, Apr 4, 2014 at 4:56 PM, slush sl...@centrum.cz wrote: I'm cracking my head for many months with the idea of using TREZOR for web auth purposes. Unfortunately I'm far from any usable solution yet. My main comments to your BIP: Don't use bitcoin addresses directly and don't encourage services to use this login for financial purposes. Mike is right, mixing authentication and financial services is wrong. Use some function to generate other private/public key from bitcoin's seed/private key to not leak bitcoin-related data to website. I'm probably very naive, but the fact that the authentication key is your Bitcoin address was for me a great feature :) What are the risks associated of id yourself with a bitcoin address you plan to use on the website for transaction ? I mean, what is the difference between doing that, and id with a login/pass and add your bitcoin address in a settings field ? (knowing you could always find a mechanism to transfer the account to another bitcoin address if needed) Eric -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
Hmmm, well TREZOR requires a web plugin. So if nobody installs plugins then we have a problem :) But regardless, actually like I said, you don't need a plugin. Browsers do it all already. With the keygen tag they even create a private key and upload the public part to be signed for you, it's seamless for the user. I wanted to give you a link to a demo site, but I can't find it anymore :( So there's not even a need for people to upgrade anything! It's all there, already, for everyone. If you were to make some upgrades, then you'd want to focus on key management, which indeed is something the Bitcoin world is trying hard to solve. But that's a small subcomponent. Making a modified version of Chrome or Firefox that can take their key from a BIP32 hierarchy or 12-words scheme is certainly possible, but then you could still reuse all the rest of it. Something I'd really like to see is TREZOR supporting a simple request/response protocol that a server can trigger, via the USB plugin, that would allow a server to display some arbitrary text and get a confirmation. Slush and I talked about it before. There are a LOT of places that don't care about Bitcoin but do need some kind of safe second factor auth where users know what they are confirming (e.g. at Google!). If TREZOR could be used for these things too, that'd increase demand and help push down prices for Bitcoin users. On Fri, Apr 4, 2014 at 5:09 PM, Eric Larchevêque ela...@gmail.com wrote: On Fri, Apr 4, 2014 at 4:56 PM, slush sl...@centrum.cz wrote: I'm cracking my head for many months with the idea of using TREZOR for web auth purposes. Unfortunately I'm far from any usable solution yet. My main comments to your BIP: Don't use bitcoin addresses directly and don't encourage services to use this login for financial purposes. Mike is right, mixing authentication and financial services is wrong. Use some function to generate other private/public key from bitcoin's seed/private key to not leak bitcoin-related data to website. I'm probably very naive, but the fact that the authentication key is your Bitcoin address was for me a great feature :) What are the risks associated of id yourself with a bitcoin address you plan to use on the website for transaction ? I mean, what is the difference between doing that, and id with a login/pass and add your bitcoin address in a settings field ? (knowing you could always find a mechanism to transfer the account to another bitcoin address if needed) Eric -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
On Fri, Apr 4, 2014 at 5:37 PM, Mike Hearn m...@plan99.net wrote: Hmmm, well TREZOR requires a web plugin. So if nobody installs plugins then we have a problem :) But regardless, actually like I said, you don't need a plugin. I see the plugin as a temporary solution and we'll eliminate the plugin once there'll be any way to talk to USB HID directly from browser (which is not possible yet, but there's some effort already). Marek -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for seamless website authentication using Bitcoin address
Hmmm, well TREZOR requires a web plugin. So if nobody installs plugins then we have a problem :) But regardless, actually like I said, you don't need a plugin. Browsers do it all already. With the keygen tag they even create a private key and upload the public part to be signed for you, it's seamless for the user. I wanted to give you a link to a demo site, but I can't find it anymore :( If you buy a TREZOR you will of course install the plugin :) What I mean is that normal people are lazy : if the solution is already in their hand they will use it, if they need to install/configure something, they won't do it. I'm not trying to propose a solution to solve the auth on the web, but to ease the sign up / login on the Bitcoin ecosystem websites and apps. More sign ups to new services (whatever the services) = more usage = expanding ecosystem = more global value to Bitcoin Wallets are a key element of the equation because : - everyone has one (desktop or mobile) - everyone (in theory) has already taken all steps to backup and secure their keys - id yourself with a Bitcoin address often makes sense on a Bitcoin related service Eric -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Friday, 4 April 2014, at 5:51 pm, Nikita Schmidt wrote: On 4 April 2014 01:42, Matt Whitlock b...@mattwhitlock.name wrote: The fingerprint field, Hash16(K), is presently specified as a 16-bit field. Rationale: There is no need to consume 4 bytes just to allow shares to be grouped together. And if someone has more than 100 different secrets, they probably have a good system for managing their shares and won't need the hash anyway. Right, of course. Sorry, I didn't notice there was an update. Two bytes are plenty. I'm worried however about the dependency on SHA-512, which may be stretching it for a tiny embedded application. The other uses of HashL can be avoided. We are balancing here between consistency with the rest of this proposal, where everything is done via HashL, and consistency with the general practice of generating fingerprints with SHA-256, like in Base58Check. I'd be fine with changing the key fingerprint algorithm to something else. Do you like CRC16? Speaking of encoding, is it not wasteful to allocate three different application/version bytes just for the sake of always starting with 'SS'? It would be OK if it were accepted as a BIP, but merely as a de-facto standard it should aim at minimising future chances of collision. I agree on principle, however I think the more user-acceptable behavior is for all base58-encoded Shamir shares to begin with a common prefix, such as SS. Users are accustomed to relying on the prefix of the base58 encoding to understand what the object is: 1 for mainnet pubkey hash, 3 for mainnet script hash, 5 for uncompressed private key, P for passphrase-protected private key, etc. Yes, 5 for uncompressed private key and K or L for compressed private key. One A/VB and three prefixes in base58. Am I the only one to see this as a counter-example? However, thinking about this, I can find logic in wanting to stabilise text prefixes at a cost of six A/V bytes (as per the latest spec). There are only 58 first characters versus 256 AVBs, so we should rather be saving the former. The type of a base58-encoded object is determined not only by the application/version byte but by the payload length as well. For example, a base58-encoded object with an application/version byte of 0x80 but a payload length of 16 bytes would not be mistakable for a Bitcoin private key, even though AVB 0x80 does denote a Bitcoin private key when the payload length is 32 or 33 bytes. So it's not as simple as saying that this proposal costs 6 AVBs. It really costs one AVB for 18-byte payloads, one AVB for 21-byte payloads, one AVB for 34-byte payloads, one AVB fo 37-byte payloads, one AVB for 66-byte payloads, and one AVB for 69-byte payloads. What about using the same P256 prime as for the elliptic curve? Just for consistency's sake. The initial draft of this BIP used the cyclic order (n) of the generator point on the secp256k1 elliptic curve as the modulus. The change to the present scheme was actually done for consistency's sake, so all sizes of secret can use a consistently defined modulus. Fair enough. Although I would have chosen the field order (p) simply because that's how all arithmetic already works in bitcoin. One field for everybody. It's also very close to 2^256, although still smaller than your maximum prime. Now of course with different bit lengths we have to pick one consistency over others. As Gregory Maxwell pointed out, you can't use p when you're dealing with private keys, as that is the order of the finite field over which the elliptic curve is defined, but private keys are not points on that curve; a private key is a scalar number of times to multiply the generator point. That means you have to use the order of the generator point as the modulus when working with private keys. Also, I'm somewhat inclined towards using the actual x instead of j in the encoding. I find it more direct and straightforward to encode the pair (x, y). And x=0 can denote a special case for future extensions. There is no technical reason behind this, it's just for (subjective) clarity and consistency. There is a technical reason for encoding j rather than x[j]: it allows for the first 256 shares to be encoded, rather than only the first 255 shares. Wow, big deal. It's hard to imagine anyone needing exactly 256 shares, but who knows. And with j = x (starting from 1) we'd get user-friendly share numbering and simpler formulas in the spec and possibly in the implementation, with no off-by-one stuff. And M instead of M-2... It's common for implementation limits to be powers of two. I don't foresee any off-by-one errors, as the spec is clear on the value of each byte in the encoding. -- ___ Bitcoin-development mailing list
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Friday, 4 April 2014, at 7:14 am, Gregory Maxwell wrote: I still repeat my concern that any private key secret sharing scheme really ought to be compatible with threshold ECDSA, otherwise we're just going to have another redundant specification. I have that concern too, but then how can we support secrets of sizes other than 256 bits? A likely use case for this BIP (even more likely than using it to decompose Bitcoin private keys) is using it to decompose BIP32 master seeds, which can be 512 bits in size. We can't use secp256k1_n as the modulus there. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Friday, 4 April 2014, at 9:25 am, Gregory Maxwell wrote: On Fri, Apr 4, 2014 at 9:05 AM, Matt Whitlock b...@mattwhitlock.name wrote: On Friday, 4 April 2014, at 7:14 am, Gregory Maxwell wrote: I still repeat my concern that any private key secret sharing scheme really ought to be compatible with threshold ECDSA, otherwise we're just going to have another redundant specification. I have that concern too, but then how can we support secrets of sizes other than 256 bits? A likely use case for this BIP (even more likely than using it to decompose Bitcoin private keys) is using it to decompose BIP32 master seeds, which can be 512 bits in size. We can't use secp256k1_n as the modulus there. Well, if you're not doing anything homorphic with the result the computation should probably be over a small field (for computational efficiency and implementation simplicity reasons) and the data split up, this also makes it easier to deal with many different data sizes, since the various sizes will more efficiently divide into the small field. The field only needs to be large enough to handle the number of distinct shares you wish to issue, so even an 8 bit field would probably be adequate (and yields some very simple table based implementations). Are you proposing to switch from prime fields to a binary field? Because if you're going to break up a secret into little pieces, you can't assume that every piece of the secret will be strictly less than some 8-bit prime modulus. And if you're going to do a base conversion, then you have to do arbitrary-precision integer math anyway, so I don't see that the small field really saves you any code. If that route is taken, rather than encoding BIP32 master keys, it would probably be prudent to encode the encryption optional version https://bitcointalk.org/index.php?topic=258678.0 ... and if we're talking about a new armored private key format then perhaps we should be talking about Mark Friedenbach's error correcting capable scheme: https://gist.github.com/maaku/8996338#file-bip-ecc32-mediawiki (though it would be nicer if we could find a decoding scheme that supported list decoding without increasing the complexity of a basic implementation, since an advanced recovery tool could make good use of a list decode) Weren't you just clamoring for implementation *simplicity* in your previous paragraph? :) -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Fri, Apr 4, 2014 at 9:36 AM, Matt Whitlock b...@mattwhitlock.name wrote: Are you proposing to switch from prime fields to a binary field? Because if you're going to break up a secret into little pieces, you can't assume that every piece of the secret will be strictly less than some 8-bit prime modulus. And if you're going to do a base conversion, then you have to do arbitrary-precision integer math anyway, so I don't see that the small field really saves you any code. Yes, I'm proposing using the binary extension field of GF(2^8). There are many secret sharing and data integrity applications available already operating over GF(2^8) so you can go compare implementation approaches without having to try them our yourself. Obviously anything efficiently encoded as bytes will efficiently encode over GF(2^8). Weren't you just clamoring for implementation *simplicity* in your previous paragraph? :) I do think there is a material difference in complexity that comes in layers rather than at a single point. It's much easier to implement a complex thing that has many individually testable parts then a single complex part. (Implementing arithmetic mod some huge P is quite a bit of work unless you're using some very high level language with integrated bignums— and are comfortable hoping that their bignums are sufficiently consistent with the spec). -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Friday, 4 April 2014, at 10:08 am, Gregory Maxwell wrote: On Fri, Apr 4, 2014 at 9:36 AM, Matt Whitlock b...@mattwhitlock.name wrote: Are you proposing to switch from prime fields to a binary field? Because if you're going to break up a secret into little pieces, you can't assume that every piece of the secret will be strictly less than some 8-bit prime modulus. And if you're going to do a base conversion, then you have to do arbitrary-precision integer math anyway, so I don't see that the small field really saves you any code. Yes, I'm proposing using the binary extension field of GF(2^8). There are many secret sharing and data integrity applications available already operating over GF(2^8) so you can go compare implementation approaches without having to try them our yourself. Obviously anything efficiently encoded as bytes will efficiently encode over GF(2^8). Honestly, that sounds a lot more complicated than what I have now. I made my current implementation because I just wanted something simple that would let me divide a private key into shares for purposes of dissemination to my next of kin et al. Weren't you just clamoring for implementation *simplicity* in your previous paragraph? :) I do think there is a material difference in complexity that comes in layers rather than at a single point. It's much easier to implement a complex thing that has many individually testable parts then a single complex part. (Implementing arithmetic mod some huge P is quite a bit of work unless you're using some very high level language with integrated bignums— and are comfortable hoping that their bignums are sufficiently consistent with the spec). I already have a fairly polished implementation of my BIP, and it's not written in a very high-level language; it's C++, and the parts that do the big-integer arithmetic are basically C. I'm using the GMP library: very straightforward, very reliable, very fast. Do you have a use case in mind that would benefit from byte-wise operations rather than big-integer operations? I mean, I guess if you were trying to implement this BIP on a PIC microcontroller, it might be nice to process the secret in smaller bites. (No pun intended.) But I get this feeling that you're only pushing me away from the present incarnation of my proposal because you think it's too similar (but not quite similar enough) to a threshold ECDSA key scheme. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Fri, Apr 4, 2014 at 10:16 AM, Matt Whitlock b...@mattwhitlock.name wrote: Honestly, that sounds a lot more complicated than what I have now. I made my current implementation because I just wanted something simple that would let me divide a private key into shares for purposes of dissemination to my next of kin et al. I suggest you go look at some of the other secret sharing implementations that use GF(2^8), they end up just being a couple of dozen lines of code. Pretty simple stuff, and they work efficiently for all sizes of data, there are implementations in a multitude of languages. There are a whole bunch of these. I already have a fairly polished implementation of my BIP, and it's not written in a very high-level language; it's C++, and the parts that do the big-integer arithmetic are basically C. I'm using the GMP library: very straightforward, very reliable, very fast. With respect for the awesome work that GMP is— It's 250,000 lines of LGPLed code. It's not just pic microcontrollers that would find that scale of a dependency unwelcome. Do you have a use case in mind that would benefit from byte-wise operations rather than big-integer operations? I mean, I guess if you were trying to implement this BIP on a PIC microcontroller, it might be nice to process the secret in smaller bites. (No pun intended.) But I get this feeling that you're only pushing me away from the present incarnation of my proposal because you think it's too similar (but not quite similar enough) to a threshold ECDSA key scheme. It lets you efficiently scale to any size data being encoded without extra overhead or having additional primes. It can be compactly implemented in Javascript (there are several implementations you can find if you google), it shouldn't be burdensome to implement on a device like a trezor (much less a real microcontroller). And yea, sure, it's distinct from the implementation you'd use for threshold signing. A threshold singing one would lack the size agility or the easy of implementation on limited devices. So I do think that if there is to be two it would be good to gain the advantages that can't be achieved in an threshold ECDSA compatible approach. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
On Friday, 4 April 2014, at 10:51 am, Gregory Maxwell wrote: On Fri, Apr 4, 2014 at 10:16 AM, Matt Whitlock b...@mattwhitlock.name wrote: Honestly, that sounds a lot more complicated than what I have now. I made my current implementation because I just wanted something simple that would let me divide a private key into shares for purposes of dissemination to my next of kin et al. I suggest you go look at some of the other secret sharing implementations that use GF(2^8), they end up just being a couple of dozen lines of code. Pretty simple stuff, and they work efficiently for all sizes of data, there are implementations in a multitude of languages. There are a whole bunch of these. Okay, I will. Do you have a use case in mind that would benefit from byte-wise operations rather than big-integer operations? I mean, I guess if you were trying to implement this BIP on a PIC microcontroller, it might be nice to process the secret in smaller bites. (No pun intended.) But I get this feeling that you're only pushing me away from the present incarnation of my proposal because you think it's too similar (but not quite similar enough) to a threshold ECDSA key scheme. It lets you efficiently scale to any size data being encoded without extra overhead or having additional primes. It can be compactly implemented in Javascript (there are several implementations you can find if you google), it shouldn't be burdensome to implement on a device like a trezor (much less a real microcontroller). Those are fair points. And yea, sure, it's distinct from the implementation you'd use for threshold signing. A threshold singing one would lack the size agility or the easy of implementation on limited devices. So I do think that if there is to be two it would be good to gain the advantages that can't be achieved in an threshold ECDSA compatible approach. I agree. I'll look into secret sharing in GF(2^8), but it may take me a few days. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development