Bitcoin Forum
May 24, 2022, 10:36:37 PM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Use Cantor Pairing Function to combine different addresses  (Read 1590 times)
doof
Hero Member
*****
Offline Offline

Activity: 765
Merit: 503


View Profile WWW
April 30, 2014, 02:02:03 AM
 #1

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);

}

}

}

1653431797
Hero Member
*
Offline Offline

Posts: 1653431797

View Profile Personal Message (Offline)

Ignore
1653431797
Reply with quote  #2

1653431797
Report to moderator
1653431797
Hero Member
*
Offline Offline

Posts: 1653431797

View Profile Personal Message (Offline)

Ignore
1653431797
Reply with quote  #2

1653431797
Report to moderator
1653431797
Hero Member
*
Offline Offline

Posts: 1653431797

View Profile Personal Message (Offline)

Ignore
1653431797
Reply with quote  #2

1653431797
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1653431797
Hero Member
*
Offline Offline

Posts: 1653431797

View Profile Personal Message (Offline)

Ignore
1653431797
Reply with quote  #2

1653431797
Report to moderator
Manfred Macx
Full Member
***
Offline Offline

Activity: 205
Merit: 100


View Profile WWW
April 30, 2014, 08:38:45 AM
 #2

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?

Rannasha
Hero Member
*****
Offline Offline

Activity: 728
Merit: 500


View Profile
April 30, 2014, 10:20:19 AM
 #3

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.
cr1776
Legendary
*
Offline Offline

Activity: 3346
Merit: 1220


View Profile
April 30, 2014, 05:11:28 PM
 #4

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.
doof
Hero Member
*****
Offline Offline

Activity: 765
Merit: 503


View Profile WWW
May 01, 2014, 08:36:24 AM
 #5

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.
cr1776
Legendary
*
Offline Offline

Activity: 3346
Merit: 1220


View Profile
May 01, 2014, 10:17:58 AM
 #6

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.

telepatheic
Newbie
*
Offline Offline

Activity: 56
Merit: 0


View Profile
May 01, 2014, 10:35:32 AM
 #7

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.
doof
Hero Member
*****
Offline Offline

Activity: 765
Merit: 503


View Profile WWW
May 02, 2014, 06:31:49 AM
 #8

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.
doof
Hero Member
*****
Offline Offline

Activity: 765
Merit: 503


View Profile WWW
May 02, 2014, 06:33:04 AM
 #9

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
telepatheic
Newbie
*
Offline Offline

Activity: 56
Merit: 0


View Profile
May 02, 2014, 06:45:45 AM
 #10

Quote
only 12ms

12ms is extremely slow. Concatenation of two numbers should take just a few nanoseconds.
protocol6
Newbie
*
Offline Offline

Activity: 1
Merit: 0


View Profile
June 07, 2014, 11:07:34 AM
Last edit: June 07, 2014, 12:54:20 PM by protocol6
 #11

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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!