Topic: Analysis of the "split-key" vanity address method: How does it work? (Read 206 times)
Bump
April 07, 2021, 07:28:08 AM
Allow me to share gmaxwell's post, in which he describes a method for N different people to all search for multiple vanity keys securely using a form of split-key. This would make a very powerful vanity pool while sharing computation costs.
Good find. But I wonder how you would make that idea such that you don't have to depend on all the clients who connected at starting time, because peers will disconnect all the time, and new peers will want to join.
It's a great idea but it needs to be made resistant to old/new clients changing.
April 07, 2021, 06:16:47 AM
Allow me to share gmaxwell's post, in which he describes a method for N different people to all search for multiple vanity keys securely using a form of split-key. This would make a very powerful vanity pool while sharing computation costs.
April 07, 2021, 04:23:32 AM
Reserved
April 07, 2021, 04:09:13 AM
In the interest of making information about split keys public, as it's currently scarce right now with the only source of information being in Bitsddress.org's codebase, I have elected to dig out the process of generating what's commonly called a "partial private key" and how the process manages to make the other parts of the private key to match a predefined address without exploding on your face.
Table of Contents
What is a partial private key?
How does Bitaddress.org make partial private keys?
How do we combine the partial private keys together?
Then why do vanity generators make another address out of the partial public key?
Are there any offline programs that generate or combine partial private keys?
I want to implement split-key generation in my program (developers)
Appendix 1: How multiplying split keys works
.
What is a partial private key?
A partial private key is simply a regular private key. It has the same prefix as a regular privately key, whether it is compressed or uncompressed, and you can use it in the place of a regular private key in any application that expects a real private key.
There is no black magic involved in making a partial private key - it's the same process as generating a normal private key.
.
How does Bitaddress.org make partial private keys?
Bitaddress will not let you make a vanity address until you generate a regular keypair. This particular keypair is generated on the page that has no idea that you're even going to use it as a split key. So this ordinary keypair is feeder for the next step, reinforcing the claim that partial private keys are just "ye olde private keys from wallet software".
There is no BIP for split-key address generation as far as I know, so the process has been developed as the bitaddress.org authors went along. (Maybe I should should draft a BIP?? ??)
.
How do we combine the partial private keys together?
We either add or multiply the partial private keys together, modulus the secp256k1 group order so the results aren't out of the curve, to get the final, whole private key. Bitaddress.org let's you choose between multiplication or addition for the combination step.
Could this be extended to N-M split keys? It could but I don't see the point. It would require finding private keys in such a way that all combinations of M keys add (or multiply) to the same result mod the group order. It's not easy to find such combinations of keys in practice because of the random nature of private keys, Plus, you get a form of Shamir Secret Sharing where you must store all N-1 keys yourself and have the vanity generator make the last one (but to secrets.js's credit, that author did a good job writing it).
Does it matter which operation we use? I think it does. Because there is no standard process for combining keys together, you have to be very careful that whatever operation is used, both/all of the partial private keys combined together must result in the same whole private key.
The kicker is that adding or multiplying their public keys also works. Now at this point it sounds like you must add (or multiply) both of the public keys together and also both of their respective private keys together so that the resulting whole public key and private key match.
.
Then why do vanity generators make another address out of the partial public key?
Remember that an address is just the HASH160 of the public key, so if your generator also outputs a public key, you can disregard the address and combine the public keys together if you'd like to safely make a "watch-only" vanity address.
.
Are there any offline programs that generate or combine partial private keys?
None that I know of. The lack of tools to operate with partial private key is really bogging us down, and this would make a great pull request to VanitySearch!
.
I want to implement split-key generation in my program (developers)
The following snippets from ninja.key.js will serve as a blueprint for you:
.
Appendix 1: How multiplying split keys works
Somebody asked me about this so I felt the need to add this information here, copied verbatim from one of my other posts.
Information from this post was retrieved from the ninja.vanitywallet.js and ninja.key.js source code files.
Local rules: No spam
Table of Contents
What is a partial private key?
How does Bitaddress.org make partial private keys?
How do we combine the partial private keys together?
Then why do vanity generators make another address out of the partial public key?
Are there any offline programs that generate or combine partial private keys?
I want to implement split-key generation in my program (developers)
Appendix 1: How multiplying split keys works
.
What is a partial private key?
A partial private key is simply a regular private key. It has the same prefix as a regular privately key, whether it is compressed or uncompressed, and you can use it in the place of a regular private key in any application that expects a real private key.
There is no black magic involved in making a partial private key - it's the same process as generating a normal private key.
.
How does Bitaddress.org make partial private keys?
Bitaddress will not let you make a vanity address until you generate a regular keypair. This particular keypair is generated on the page that has no idea that you're even going to use it as a split key. So this ordinary keypair is feeder for the next step, reinforcing the claim that partial private keys are just "ye olde private keys from wallet software".
There is no BIP for split-key address generation as far as I know, so the process has been developed as the bitaddress.org authors went along. (Maybe I should should draft a BIP?? ??)
.
How do we combine the partial private keys together?
We either add or multiply the partial private keys together, modulus the secp256k1 group order so the results aren't out of the curve, to get the final, whole private key. Bitaddress.org let's you choose between multiplication or addition for the combination step.
Could this be extended to N-M split keys? It could but I don't see the point. It would require finding private keys in such a way that all combinations of M keys add (or multiply) to the same result mod the group order. It's not easy to find such combinations of keys in practice because of the random nature of private keys, Plus, you get a form of Shamir Secret Sharing where you must store all N-1 keys yourself and have the vanity generator make the last one (but to secrets.js's credit, that author did a good job writing it).
Does it matter which operation we use? I think it does. Because there is no standard process for combining keys together, you have to be very careful that whatever operation is used, both/all of the partial private keys combined together must result in the same whole private key.
The kicker is that adding or multiplying their public keys also works. Now at this point it sounds like you must add (or multiply) both of the public keys together and also both of their respective private keys together so that the resulting whole public key and private key match.
.
Then why do vanity generators make another address out of the partial public key?
Remember that an address is just the HASH160 of the public key, so if your generator also outputs a public key, you can disregard the address and combine the public keys together if you'd like to safely make a "watch-only" vanity address.
.
Are there any offline programs that generate or combine partial private keys?
None that I know of. The lack of tools to operate with partial private key is really bogging us down, and this would make a great pull request to VanitySearch!
.
I want to implement split-key generation in my program (developers)
The following snippets from ninja.key.js will serve as a blueprint for you:
Code:
getECKeyFromAdding: function (privKey1, privKey2) {
var n = EllipticCurve.getSECCurveByName("secp256k1").getN();
var ecKey1 = new Bitcoin.ECKey(privKey1);
var ecKey2 = new Bitcoin.ECKey(privKey2);
// if both keys are the same return null
if (ecKey1.getBitcoinHexFormat() == ecKey2.getBitcoinHexFormat()) return null;
if (ecKey1 == null || ecKey2 == null) return null;
var combinedPrivateKey = new Bitcoin.ECKey(ecKey1.priv.add(ecKey2.priv).mod(n));
// compressed when both keys are compressed
if (ecKey1.compressed && ecKey2.compressed) combinedPrivateKey.setCompressed(true);
return combinedPrivateKey;
},
getECKeyFromMultiplying: function (privKey1, privKey2) {
var n = EllipticCurve.getSECCurveByName("secp256k1").getN();
var ecKey1 = new Bitcoin.ECKey(privKey1);
var ecKey2 = new Bitcoin.ECKey(privKey2);
// if both keys are the same return null
if (ecKey1.getBitcoinHexFormat() == ecKey2.getBitcoinHexFormat()) return null;
if (ecKey1 == null || ecKey2 == null) return null;
var combinedPrivateKey = new Bitcoin.ECKey(ecKey1.priv.multiply(ecKey2.priv).mod(n));
// compressed when both keys are compressed
if (ecKey1.compressed && ecKey2.compressed) combinedPrivateKey.setCompressed(true);
return combinedPrivateKey;
},
// ...
getByteArrayFromAdding: function (pubKeyHex1, pubKeyHex2) {
var ecparams = EllipticCurve.getSECCurveByName("secp256k1");
var curve = ecparams.getCurve();
var ecPoint1 = curve.decodePointHex(pubKeyHex1);
var ecPoint2 = curve.decodePointHex(pubKeyHex2);
// if both points are the same return null
if (ecPoint1.equals(ecPoint2)) return null;
var compressed = (ecPoint1.compressed && ecPoint2.compressed);
var pubKey = ecPoint1.add(ecPoint2).getEncoded(compressed);
return pubKey;
},
getByteArrayFromMultiplying: function (pubKeyHex, ecKey) {
var ecparams = EllipticCurve.getSECCurveByName("secp256k1");
var ecPoint = ecparams.getCurve().decodePointHex(pubKeyHex);
var compressed = (ecPoint.compressed && ecKey.compressed);
// if both points are the same return null
ecKey.setCompressed(false);
if (ecPoint.equals(ecKey.getPubPoint())) {
return null;
}
var bigInt = ecKey.priv;
var pubKey = ecPoint.multiply(bigInt).getEncoded(compressed);
return pubKey;
}
var n = EllipticCurve.getSECCurveByName("secp256k1").getN();
var ecKey1 = new Bitcoin.ECKey(privKey1);
var ecKey2 = new Bitcoin.ECKey(privKey2);
// if both keys are the same return null
if (ecKey1.getBitcoinHexFormat() == ecKey2.getBitcoinHexFormat()) return null;
if (ecKey1 == null || ecKey2 == null) return null;
var combinedPrivateKey = new Bitcoin.ECKey(ecKey1.priv.add(ecKey2.priv).mod(n));
// compressed when both keys are compressed
if (ecKey1.compressed && ecKey2.compressed) combinedPrivateKey.setCompressed(true);
return combinedPrivateKey;
},
getECKeyFromMultiplying: function (privKey1, privKey2) {
var n = EllipticCurve.getSECCurveByName("secp256k1").getN();
var ecKey1 = new Bitcoin.ECKey(privKey1);
var ecKey2 = new Bitcoin.ECKey(privKey2);
// if both keys are the same return null
if (ecKey1.getBitcoinHexFormat() == ecKey2.getBitcoinHexFormat()) return null;
if (ecKey1 == null || ecKey2 == null) return null;
var combinedPrivateKey = new Bitcoin.ECKey(ecKey1.priv.multiply(ecKey2.priv).mod(n));
// compressed when both keys are compressed
if (ecKey1.compressed && ecKey2.compressed) combinedPrivateKey.setCompressed(true);
return combinedPrivateKey;
},
// ...
getByteArrayFromAdding: function (pubKeyHex1, pubKeyHex2) {
var ecparams = EllipticCurve.getSECCurveByName("secp256k1");
var curve = ecparams.getCurve();
var ecPoint1 = curve.decodePointHex(pubKeyHex1);
var ecPoint2 = curve.decodePointHex(pubKeyHex2);
// if both points are the same return null
if (ecPoint1.equals(ecPoint2)) return null;
var compressed = (ecPoint1.compressed && ecPoint2.compressed);
var pubKey = ecPoint1.add(ecPoint2).getEncoded(compressed);
return pubKey;
},
getByteArrayFromMultiplying: function (pubKeyHex, ecKey) {
var ecparams = EllipticCurve.getSECCurveByName("secp256k1");
var ecPoint = ecparams.getCurve().decodePointHex(pubKeyHex);
var compressed = (ecPoint.compressed && ecKey.compressed);
// if both points are the same return null
ecKey.setCompressed(false);
if (ecPoint.equals(ecKey.getPubPoint())) {
return null;
}
var bigInt = ecKey.priv;
var pubKey = ecPoint.multiply(bigInt).getEncoded(compressed);
return pubKey;
}
.
Appendix 1: How multiplying split keys works
Somebody asked me about this so I felt the need to add this information here, copied verbatim from one of my other posts.
Quote
You don't multiply two points together, you multiply one of the points with a private key.
Suppose you generate a public/private key pair that is secret. Then you can send the public key to any service, the service can also generate a second private key (not associated with any public key), share the private key with you, and multiply your public key by the second private key to get a third (product) public key. Similarly, you can multiply your two private keys together to get the corresponding private key for it.
Basically, if A is your pubkey, a is its secret privkey, and b is some random privkey generated by the service and shared with you, then:
Where G is the generator point of SECP256K1.
Then you have the public/private keypair (C, c).
How you could make a vanity address out of A and b? Well, you know that this makes another private key C, so just cycle through random values of b until you get an address hash that matches the prefix. And there will eventually be a collision becuase the number of keys (2^256) is bigger than the number of addresses (2^160) and is somewhat less than the number of addresses containing the alphanumerical prefix (or suffix) that you are trying to generate.
Suppose you generate a public/private key pair that is secret. Then you can send the public key to any service, the service can also generate a second private key (not associated with any public key), share the private key with you, and multiply your public key by the second private key to get a third (product) public key. Similarly, you can multiply your two private keys together to get the corresponding private key for it.
Basically, if A is your pubkey, a is its secret privkey, and b is some random privkey generated by the service and shared with you, then:
Code:
C = A*b
c = (a*b)*G
# because:
c = (a*b)*G = (b*a)*G = b*(a*G) = b*A = A*b
c = (a*b)*G
# because:
c = (a*b)*G = (b*a)*G = b*(a*G) = b*A = A*b
Where G is the generator point of SECP256K1.
Then you have the public/private keypair (C, c).
How you could make a vanity address out of A and b? Well, you know that this makes another private key C, so just cycle through random values of b until you get an address hash that matches the prefix. And there will eventually be a collision becuase the number of keys (2^256) is bigger than the number of addresses (2^160) and is somewhat less than the number of addresses containing the alphanumerical prefix (or suffix) that you are trying to generate.
Information from this post was retrieved from the ninja.vanitywallet.js and ninja.key.js source code files.
Local rules: No spam
Jump to: