Author

Topic: Use Cantor Pairing Function to combine different addresses (Read 1638 times)

newbie
Activity: 1
Merit: 0
Do any of the alts use something other than secp256k1 elliptic curves and HASH160?  I haven't checked them all yet.  If not, it'd be far simpler just to use the HASH160 (or a Base58Check with a network agnostic prefix) and load the same private key into each alt's wallet.  It would save not only the pairing but the key generation for multiple keys.  The client has to know how to do Base58Check encoding for its own network (which it probably does anyway) but that's it.

The only drawback I can see is if you aren't watching all the alts, you might miss that you've been sent some money.  Tacking on a list of network prefixes (or pairing them) instead of the usual single prefix might help.  For actual payments (rather than donations) the payment protocol could just include a list of amounts in different coins which would serve to limit which ones you were willing to accept.

I suppose pairing might still come in handy if, say, you only actually supported "FavouriteCoin" and wanted to send anything else to an auto-sell exchange.  Obviously you wouldn't want the exchange to have your "FavouriteCoin" key and you might not (justifiably) trust them with the bulk of your incoming payments.

A unified client library would be helpful here.   Plugins for each coin and an HD wallet that's coin agnostic for a given public key algorithm.  If a flexible enough object model was created for Satoshi's concept then the plugins would all be pretty simple except in rare cases like DarkCoin.  You could have an easy-to-use client feature to auto-trade coins with TierNolan's cross-chain trading protocol with others using similar clients.  Then the client could also auto-trade coins for you when someone wants a specific coin you don't currently have.  From an accounting perspective, it makes more sense to push the currency conversion to the customer side but being able to do it either way would be nice.  That's an idea (and code) I've been working on recently.
jr. member
Activity: 56
Merit: 1
Quote
only 12ms

12ms is extremely slow. Concatenation of two numbers should take just a few nanoseconds.
hero member
Activity: 765
Merit: 503
What's the advantage of using this pairing function over any other? The amount of data to transmit to the user is the same as if you would send both addresses separately, so there's no gain there. In addition, it would only work with compatible software and there is no userfriendly way of obtaining a regular address from the paired address by a user who doesn't have such software.

If you insist on pairing addresses, you might as well concatenate them with a separator-symbol that's outside the base58 character set. Your addresses would pair up nicely to (using + as separator):
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T+LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE

Advantage of this method is that a user w/o compatible software can still look at this paired address and identify the BTC (or LTC) portion and manually copy/paste that into his wallet-client.

I guess to have one mime type, that all wallets open.  Then unpair and take the address relevant to itself.

Sure, split function would work.  But thats not fun. Wink
hero member
Activity: 765
Merit: 503
Quote
It is a cool idea, maybe a better use can be found.

It is interesting but it isn't an efficient way of encoding two numbers computationally. The only potential benefit is reduced memory allocation when the two numbers are highly variable in length. With bitcoin addresses, the lengths are almost always the same so it has no real benefit over just concatenation of fixed length integers.

It took only 12ms on a pretty stock PC.
jr. member
Activity: 56
Merit: 1
Quote
It is a cool idea, maybe a better use can be found.

It is interesting but it isn't an efficient way of encoding two numbers computationally. The only potential benefit is reduced memory allocation when the two numbers are highly variable in length. With bitcoin addresses, the lengths are almost always the same so it has no real benefit over just concatenation of fixed length integers.
legendary
Activity: 4228
Merit: 1313
What's the advantage of using this pairing function over any other? The amount of data to transmit to the user is the same as if you would send both addresses separately, so there's no gain there. In addition, it would only work with compatible software and there is no userfriendly way of obtaining a regular address from the paired address by a user who doesn't have such software.

If you insist on pairing addresses, you might as well concatenate them with a separator-symbol that's outside the base58 character set. Your addresses would pair up nicely to (using + as separator):
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T+LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE

Advantage of this method is that a user w/o compatible software can still look at this paired address and identify the BTC (or LTC) portion and manually copy/paste that into his wallet-client.

Unless there is some advantage to it, simple concatenation seem easiest as stated above. Simple beats complicated. :-)

Encoding multiple addresses in a qr code would be useful.

True... just an idea.  Maybe the wrong application.

It is a cool idea, maybe a better use can be found. :-) 

From a tech and thinking perspective it is interesting.

hero member
Activity: 765
Merit: 503
What's the advantage of using this pairing function over any other? The amount of data to transmit to the user is the same as if you would send both addresses separately, so there's no gain there. In addition, it would only work with compatible software and there is no userfriendly way of obtaining a regular address from the paired address by a user who doesn't have such software.

If you insist on pairing addresses, you might as well concatenate them with a separator-symbol that's outside the base58 character set. Your addresses would pair up nicely to (using + as separator):
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T+LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE

Advantage of this method is that a user w/o compatible software can still look at this paired address and identify the BTC (or LTC) portion and manually copy/paste that into his wallet-client.

Unless there is some advantage to it, simple concatenation seem easiest as stated above. Simple beats complicated. :-)

Encoding multiple addresses in a qr code would be useful.

True... just an idea.  Maybe the wrong application.
legendary
Activity: 4228
Merit: 1313
What's the advantage of using this pairing function over any other? The amount of data to transmit to the user is the same as if you would send both addresses separately, so there's no gain there. In addition, it would only work with compatible software and there is no userfriendly way of obtaining a regular address from the paired address by a user who doesn't have such software.

If you insist on pairing addresses, you might as well concatenate them with a separator-symbol that's outside the base58 character set. Your addresses would pair up nicely to (using + as separator):
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T+LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE

Advantage of this method is that a user w/o compatible software can still look at this paired address and identify the BTC (or LTC) portion and manually copy/paste that into his wallet-client.

Unless there is some advantage to it, simple concatenation seem easiest as stated above. Simple beats complicated. :-)

Encoding multiple addresses in a qr code would be useful.
hero member
Activity: 728
Merit: 500
What's the advantage of using this pairing function over any other? The amount of data to transmit to the user is the same as if you would send both addresses separately, so there's no gain there. In addition, it would only work with compatible software and there is no userfriendly way of obtaining a regular address from the paired address by a user who doesn't have such software.

If you insist on pairing addresses, you might as well concatenate them with a separator-symbol that's outside the base58 character set. Your addresses would pair up nicely to (using + as separator):
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T+LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE

Advantage of this method is that a user w/o compatible software can still look at this paired address and identify the BTC (or LTC) portion and manually copy/paste that into his wallet-client.
full member
Activity: 205
Merit: 105
Noob here. At first this seems like an interesting idea (this is the first time I heard of CPF). Could you give more details on how this would work. For example, a merchant has a combined BTC & LTC address like in your example, and when I as a client deposit BTC to that address how does the transaction get processed? Does there need to be extra software to decide if I deposited BTC or LTC and which blockchain should verify the transaction?
hero member
Activity: 765
Merit: 503
I have been toying with this idea.  Using the Cantor Pairing Function to combine different addresses.

Abstract

Given the explosion in altcoins, it will be reasonable to assume that merchants will be accepting a number of different crypto coins as payments.  We are seeing Bitcoin, Litecoin and Dogecoin as the front runners.

I propose instead of providing the user with different addresses for each currency, merchants could use the Cantor Pairing Function to provide a “mixed” address.   This would allow merchants to produce one unique QR code and address.   The user could then add the cantor paired address to their wallet of choice.

Exchanges could reduce the number of deposit addresses shown to the user.

By introducing a new mime type, wallet software could decompose the paired address, and abstract the address that is relevant.

Take address set BTC 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T, LTC LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE

Converting the base58 addresses to decimal, then applying the Cantor Pair function yields 4816056888050750582224742844031604102132678664282188647256495058920612654357063 8391750708909119424733449538336733090951

In base58

Eg mime type Cantor://4Qu9uDoad4ymwntxwBYHhMLmGvfhBivMSPKAz5tX4iyKQ8xzx21YJsJzyUWWHHAShiFg

On a desktop computer, the pair and inverse takes 12ms

Thoughts?



Code:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace CantorPairing

{

classProgram

{

staticvoid Main(string[] args)

{

//

Console.Write("Start with a bitcoin address as decimal 4824855521912883454204125328393785564172057950402473856794");

Console.WriteLine("or 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T");

Console.Write("Add a litecoin address as decimal 305531613334489417964998059632233568427215324197451409291673");

Console.WriteLine("or LaxGrwMeokoMgv5zYpv5btT4yNUB9DaiqE");

 

System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

Org.BouncyCastle.Math.BigInteger btc =new Org.BouncyCastle.Math.BigInteger("4824855521912883454204125328393785564172057950402473856794");

Org.BouncyCastle.Math.BigInteger ltc =new Org.BouncyCastle.Math.BigInteger("305531613334489417964998059632233568427215324197451409291673");

 

Org.BouncyCastle.Math.BigInteger bigResult = CantorPair(btc, ltc);

 

Console.WriteLine("The cantor pairing function yields the number ", bigResult);

 

Org.BouncyCastle.Math.BigInteger[] pair = Reverse(bigResult);

 

 

sw.Stop();

 

Console.WriteLine(bigResult +" in "+ sw.ElapsedMilliseconds +"ms");

Console.WriteLine("Btc {0}", pair[0]);

Console.WriteLine("Ltc {0}", pair[1]);

 

Console.ReadKey();

}

 

staticint CantorPair(short x, short y)

{

return ((x + y) * (x + y +1)) /2+ y;

}

 

static Org.BouncyCastle.Math.BigInteger CantorPair(Org.BouncyCastle.Math.BigInteger x, Org.BouncyCastle.Math.BigInteger y)

{

Org.BouncyCastle.Math.BigInteger xplusy = x.Add(y);

Org.BouncyCastle.Math.BigInteger xplusyplus1 = xplusy.Add(Org.BouncyCastle.Math.BigInteger.One);

Org.BouncyCastle.Math.BigInteger inside = xplusy.Multiply(xplusyplus1);

Org.BouncyCastle.Math.BigInteger twoplusy = Org.BouncyCastle.Math.BigInteger.Two.Add(y);

 

return xplusy.Multiply(xplusyplus1).Divide(Org.BouncyCastle.Math.BigInteger.Two).Add(y);

}

 

staticshort[] Reverse(int z)

{

short[] pair =newshort[2];

int t = (int)Math.Floor((-1D+Math.Sqrt(1D+8* z)) /2D);

int x = t * (t +3) /2- z;

int y = z - t * (t +1) /2;

pair[0] = (short)x;

pair[1] = (short)y;

return pair;

}

 

static Org.BouncyCastle.Math.BigInteger[] Reverse(Org.BouncyCastle.Math.BigInteger z)

{

//"constants"

Org.BouncyCastle.Math.BigInteger three =new Org.BouncyCastle.Math.BigInteger("3");

Org.BouncyCastle.Math.BigInteger eight =new Org.BouncyCastle.Math.BigInteger("8");

 

Org.BouncyCastle.Math.BigInteger[] pair =new Org.BouncyCastle.Math.BigInteger[2];

Org.BouncyCastle.Math.BigInteger t = eight.Multiply(z).Add(Org.BouncyCastle.Math.BigInteger.One);

 

Byte[] tempBytes = t.ToByteArray();

Array.Reverse(tempBytes);

 

System.Numerics.BigInteger temp =new System.Numerics.BigInteger(tempBytes);

System.Numerics.BigInteger root = Sqrt(temp);

 

String root3 = root.ToString();

 

Org.BouncyCastle.Math.BigInteger root2 =new Org.BouncyCastle.Math.BigInteger(root3);

 

t = root2.Subtract(Org.BouncyCastle.Math.BigInteger.One);

t = t.Divide(Org.BouncyCastle.Math.BigInteger.Two);

 

Org.BouncyCastle.Math.BigInteger tplus3 = t.Add(three);

Org.BouncyCastle.Math.BigInteger tplus1 = t.Add(Org.BouncyCastle.Math.BigInteger.One);

 

Org.BouncyCastle.Math.BigInteger x = t.Multiply(tplus3).Divide(Org.BouncyCastle.Math.BigInteger.Two).Subtract(z); // * (t + 3) / 2 - z;

Org.BouncyCastle.Math.BigInteger y = t.Multiply(tplus1).Divide(Org.BouncyCastle.Math.BigInteger.Two); //- t * (t + 1) / 2;

y = z.Subtract(y);

 

pair[0] = x;

pair[1] = y;

return pair;

}

 

publicstatic System.Numerics.BigInteger Sqrt(System.Numerics.BigInteger n)

{

if (n ==0) return0;

if (n >0)

{

int bitLength =Convert.ToInt32(Math.Ceiling(System.Numerics.BigInteger.Log(n, 2)));

System.Numerics.BigInteger root = System.Numerics.BigInteger.One << (bitLength /2);

 

while (!isSqrt(n, root))

{

root += n / root;

root /=2;

}

 

return root;

}

 

thrownewArithmeticException("NaN");

}

 

privatestaticBoolean isSqrt(System.Numerics.BigInteger n, System.Numerics.BigInteger root)

{

System.Numerics.BigInteger lowerBound = root * root;

System.Numerics.BigInteger upperBound = (root +1) * (root +1);

 

return (n >= lowerBound && n < upperBound);

}

}

}

Jump to: