Mixing addresses with Cantor Pairing Function

Posted by on Apr 30, 2014 in Technical, Thoughts, Wallets | No Comments

Cantor Pairing Function for n currency 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 48160568880507505822247428440316041021326786642821886472564950589206126543570638391750708909119424733449538336733090951

In base58

Eg mime type Cantor://4Qu9uDoad4ymwntxwBYHhMLmGvfhBivMSPKAz5tX4iyKQ8xzx21YJsJzyUWWHHAShiFg

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

cantor

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

}

}

}

[/Code]