Create JS implementation of Chat name generating code

[jakubgs]

Currently the only place that has an implementation of Status chat name generation is: https://github.com/status-im/status-go/tree/develop/protocol/identity/alias The method used is GenerateFromPublicKeyString(). It uses a simplified form of Linear-feedback shift register and was implemented by @cammellos.

We need a JS implementation for the sake of https://github.com/status-im/universal-links-handler/issues/17.

[jakubgs]

According to the specs "Public/Private Keypairs" are:

An ECDSA (secp256k1 curve) public/private keypair MUST be generated via a BIP43 derived path from a BIP39 mnemonic seed phrase.

https://github.com/status-im/specs/blob/master/status-account-spec.md#publicprivate-keypairs

[jakubgs]

The correct way of parsing a chat key in the form of a string seems to be UnmarshalPubkey():

// UnmarshalPubkey converts bytes to a secp256k1 public key.
func UnmarshalPubkey(pub []byte) (*ecdsa.PublicKey, error) {
    x, y := elliptic.Unmarshal(S256(), pub)
    if x == nil {
        return nil, errInvalidPubkey
    }
    return &ecdsa.PublicKey{Curve: S256(), X: x, Y: y}, nil
}

https://github.com/status-im/status-go/blob/c8a911eb/eth-node/crypto/gethcrypto.go#L145-L152

[jakubgs]

I made a test code to verify this using my own public chat key:

import (
    "fmt"
    "github.com/status-im/status-go/eth-node/crypto"
)

func main() {
    var pubKey string = "0x0461f576da67dc0bca9888cdb4cb28c80285b756b324109da94a081585ed6f007cf00afede6b3ee5638593674fee100b590318fc7bdb0054b8dd9445acea216ad2"
    key, err := statuscrypto.UnmarshalPubkey([]byte(pubKey))
    if err != nil {
        fmt.Println("Error:", err)
        os.Exit(1)
    }
    fmt.Println("%v", key)
}

But it seems to fail with:

Error: invalid secp256k1 public key

[cammellos]

@jakubgs you need to parse it as an hex string, hex.DecodeString("string-without-0x"), otherwise is the bytes of the ascii characters

[jakubgs]

There's also HexToECDSA():

// HexToECDSA parses a secp256k1 private key.
func HexToECDSA(hexkey string) (*ecdsa.PrivateKey, error) {
    b, err := hex.DecodeString(hexkey)
    if err != nil {
        return nil, errors.New("invalid hex string")
    }
    return ToECDSA(b)
}

https://github.com/status-im/status-go/blob/c8a911eb/eth-node/crypto/gethcrypto.go#L161-L168

[jakubgs]

Thanks @cammellos, I think HexToECDSA already does that, but I'm still hitting invalid hex string.

According to encoding/hex docs:

package main

import (
    "encoding/hex"
    "fmt"
    "log"
)

func main() {
    const s = "48656c6c6f20476f7068657221"
    decoded, err := hex.DecodeString(s)
    if err != nil {
        log.Fatal(err)
    }

    fmt.Printf("%s\n", decoded)

}

https://golang.org/pkg/encoding/hex/#DecodeString Which shows the string without the 0x prefix. But without it I get invalid length, need 256 bits.

[jakubgs]

Ooooh, it's for parsing Private keys, as the comment states:

// HexToECDSA parses a secp256k1 private key.
func HexToECDSA(hexkey string) (*ecdsa.PrivateKey, error) {

[cammellos]

just to make sure, the last example has an invalid key, have you used the right one?

0461f576da67dc0bca9888cdb4cb28c80285b756b324109da94a081585ed6f007cf00afede6b3ee5638593674fee100b590318fc7bdb0054b8dd9445acea216ad2

On Wed, Feb 5, 2020, 15:47 Jakub notifications@github.com wrote:

Thanks @cammellos https://github.com/cammellos, I think HexToECDSA already does that, but I'm still hitting invalid hex string.

According to encoding/hex docs:

package main import ( "encoding/hex" "fmt" "log" ) func main() { src := []byte("48656c6c6f20476f7068657221")

dst := make([]byte, hex.DecodedLen(len(src))) n, err := hex.Decode(dst, src) if err != nil { log.Fatal(err) }

fmt.Printf("%s\n", dst[:n])

}

https://golang.org/pkg/encoding/hex/#Decode

Which shows the string without the 0x prefix. But without it I get invalid length, need 256 bits.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/status-im/js-status-chat-name/issues/1?email_source=notifications&email_token=AAHYJMCO3FAYFPKVFDNPOR3RBLGPHA5CNFSM4KQMGAJ2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEK3VY3Q#issuecomment-582442094, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHYJMBY2ZGLXRDE6QOVJNTRBLGPHANCNFSM4KQMGAJQ .

[jakubgs]

Okay, this works:

package main

import (
    "encoding/hex"
    "log"
    "os"

    "github.com/status-im/status-go/eth-node/crypto"
)

func main() {
    var pubKey string = "0461f576da67dc0bca9888cdb4cb28c80285b756b324109da94a081585ed6f007cf00afede6b3ee5638593674fee100b590318fc7bdb0054b8dd9445acea216ad2"

    decodedKey, err := hex.DecodeString(pubKey)
    if err != nil {
        log.Fatal(err)
    }

    key, err := crypto.UnmarshalPubkey(decodedKey)

    if err != nil {
        log.Fatal(err)
        os.Exit(1)
    }

    log.Println("Key:", key)
}

Result:

Key: &{0xc0000a6ff0 44308044137722526298873970255257088877331767345348136454115113789599809208444 108574511170606251106232248014541053132732342948972321192770438015881895307986}

[jakubgs]

So it looks like I will either need an ECDSA JS library to make parsing of public keys work, or write something myself into this one.

[jakubgs]

This library looks promising: https://www.npmjs.com/package/ecdsa-secp256r1

[jakubgs]

Looks like the format for the public key is:

• 0x - To indicate the format is a hexadecimal string.
• 04 - Control byte, not sure what it does yet.
• 64 chars - The X of the ECDSA Public Key
• 64 chars - The Y of the ECDSA Public Key

[jakubgs]

Based on this I can parse the Chat Key in JS like this:

function dropControlByte(str) {
  return str.substring(2)
}

function parseHexString(str) { 
  if (str.length != 128) {
    throw "Wrong Hex length for public key!"
  }
  return {
      x: parseInt(str.substring(0, 64), 16),
      y: parseInt(str.substring(64, 128), 16),
  }
}

let pubKey = "0461f576da67dc0bca9888cdb4cb28c80285b756b324109da94a081585ed6f007cf00afede6b3ee5638593674fee100b590318fc7bdb0054b8dd9445acea216ad2";

let parsedKey = parseHexString(dropControlByte(pubKey))
console.dir(parsedKey)

Which gives me:

{ x: 4.4308044137722527e+76, y: 1.0857451117060626e+77 }

Which matches with what I got from Go:

Key: &{
0xc0000a6ff0  
44308044137722526298873970255257088877331767345348136454115113789599809208444
108574511170606251106232248014541053132732342948972321192770438015881895307986
}

[jakubgs]

Andrea found where the 04 prefix is defined:

/** Prefix byte used to tag various encoded curvepoints for specific purposes */
#define SECP256K1_TAG_PUBKEY_EVEN 0x02
#define SECP256K1_TAG_PUBKEY_ODD 0x03
#define SECP256K1_TAG_PUBKEY_UNCOMPRESSED 0x04
#define SECP256K1_TAG_PUBKEY_HYBRID_EVEN 0x06
#define SECP256K1_TAG_PUBKEY_HYBRID_ODD 0x07

https://github.com/bitcoin-core/secp256k1/blob/0d9540b1/include/secp256k1.h#L180

As far as I know we display only the uncompressed version of the public key in the app and it's unlikely someone would want to use the compressed one. For that reason this library will handle only the uncompressed form for now.

[jakubgs]

My problem is that Number.MAX_SAFE_INTEGER in JavaScript is 9007199254740991, and in Go we use uint64 to store the X of the public key, since it's such a big number:

44308044137722526298873970255257088877331767345348136454115113789599809208444

There are some libraries that allow you to manipulate 64bit unsigned integers in JavaScript:

• https://github.com/substack/node-bigint
• https://github.com/justmoon/node-bignum
• https://github.com/broofa/node-int64

I might have to use one of them that provides bitwise operations to make this work.

[jakubgs]

All of those libraries are only for Node.js, and we need something that will work in the browser.

Looks like big-integer package might be what we need.

[jakubgs]

I can just do:

const bigInt = require("big-integer");

function dropControlByte(str) {
  return str.substring(2)
}

function parseHexString(str) { 
  if (str.length != 128) {
    throw "Wrong Hex length for public key!"
  }
  return {
      x: bigInt(str.substring(0, 64), 16),
      y: bigInt(str.substring(64, 128), 16),
  }
}

let pubKey = "0461f576da67dc0bca9888cdb4cb28c80285b756b324109da94a081585ed6f007cf00afede6b3ee5638593674fee100b590318fc7bdb0054b8dd9445acea216ad2";

let parsedKey = parseHexString(dropControlByte(pubKey))
console.dir(parsedKey)

And I get:

Key:
{
  x: Integer {
    value: 44308044137722526298873970255257088877331767345348136454115113789599809208444n
  },
  y: Integer {
    value: 108574511170606251106232248014541053132732342948972321192770438015881895307986n
  }
}

[jakubgs]

Looks like I also have to truncate the Integer I get because in Go the call looks like this:

func GenerateFromPublicKey(publicKey *ecdsa.PublicKey) string {
    return generate(uint64(publicKey.X.Int64()))
}

https://github.com/status-im/status-go/blob/14501520/protocol/identity/alias/generate.go#L26-L28 Which turns:

44308044137722526298873970255257088877331767345348136454115113789599809208444n

Into:

5334537423578660988

By using the Int64() method from the [math/big]() package:

func (x *Float) Int64() (int64, Accuracy)

Int64 returns the integer resulting from truncating x towards zero. If math.MinInt64 <= x <= math.MaxInt64, the result is Exact if x is an integer, and Above (x < 0) or Below (x > 0) otherwise. The result is (math.MinInt64, Above) for x < math.MinInt64, and (math.MaxInt64, Below) for x > math.MaxInt64. https://golang.org/pkg/math/big/#Float.Int64

And here's the code: https://golang.org/src/math/big/float.go?s=20918:20959#L765

[jakubgs]

But what's weird is that math.MaxInt64 on my system is 9223372036854775807, and yet it returns 5334537423578660988 for my X, which doesn't make sense because according to the description it should return math.MaxInt64.

[jakubgs]

Oh wait, I was looking at the Float, not the Int, this is it:

func (x *Int) Int64() int64

Int64 returns the int64 representation of x. If x cannot be represented in an int64, the result is undefined. https://golang.org/pkg/math/big/#Int.Int64 Code:

// Int64 returns the int64 representation of x.
// If x cannot be represented in an int64, the result is undefined.
func (x *Int) Int64() int64 {
v := int64(low64(x.abs))
if x.neg {
v = -v
}
return v
}

https://golang.org/src/math/big/int.go?s=8801:8828#L361

If x cannot be represented in an int64, the result is undefined.

That's a very worrying sentence... @cammellos ? Maybe using Int64() was a bad idea.

[jakubgs]

This is low64:

// low64 returns the least significant 64 bits of x.
func low64(x nat) uint64 {
    if len(x) == 0 {
        return 0
    }
    v := uint64(x[0])
    if _W == 32 && len(x) > 1 {
        return uint64(x[1])<<32 | v
    }
    return v
}

[jakubgs]

A nat is an array of Word types, which are normally int64:

// An unsigned integer x of the form
//
//   x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0]
//
// with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n,
// with the digits x[i] as the slice elements.
//
// A number is normalized if the slice contains no leading 0 digits.
// During arithmetic operations, denormalized values may occur but are
// always normalized before returning the final result. The normalized
// representation of 0 is the empty or nil slice (length = 0).
//
type nat []Word

And:

type StdSizes struct {
    WordSize int64 // word size in bytes - must be >= 4 (32bits)
    MaxAlign int64 // maximum alignment in bytes - must be >= 1
}

https://golang.org/pkg/go/types/

[jakubgs]

I tried defining the function how I think it would work but so far no cigar:

> i = bigInt("44308044137722526298873970255257088877331767345348136454115113789599809208444")
> find = (num, size) => {
    let x = num.toArray(size);
    return  bigInt(x.value[1]).shiftLeft(32).or(x.value[0]);
  }

> find(i, 4294967295)
Integer { value: 1554388171175065309n }
> find(i, 2103293935)
Integer { value: 6201892260997496947n }
> find(i, 2147483647)
Integer { value: 8843785722042253409n }
> find(i, 18446744073709551615)
Integer { value: 47207106826859989540934519808n }
> find(i, 9223372036854775807)
Integer { value: 4849864829967884576874299398n }

I'm trying max values for various types:

gore> :import "math"
gore> math.MaxInt32
2147483647
gore> math.MaxInt64
9223372036854775807
gore> math.MaxUint32
4294967295
gore> math.MaxUint64
constant 18446744073709551615 overflows int

[jakubgs]

> find = (num, size) => {
    let x = num.toArray(bigInt(size));
    return  bigInt(x.value[1]).shiftLeft(32).or(x.value[0]);
  }

> sizes = [
    "2103293935",
    "2147483647",
    "4294967295",
    "9223372036854775807",
    "18446744073709551615"
  ]

> for (let s of sizes) { console.log(find(i, s)) }
Integer { value: 6201892260997496947n }
Integer { value: 8843785722042253409n }
Integer { value: 1554388171175065309n }
Integer { value: 4849864829967884576874299398n }
Integer { value: 58929326457023034808424205312n }

[jakubgs]

Andrea helped me by showing me that I can get the right seed by doing:

bigInt(pubkey.substring(48, 64), 16)

This gives me 5334537423578660988 which can be used for seed.

[jakubgs]

I have it almost working. Go version gets me:

Name: Studious Gold Mustang

And JS version gets me:

[ 'Studious', 'Ample', 'Bernesemountaindog' ]

It fucks up on the last step of the second word. I'll debug it tomorrow.

[jakubgs]

I encountered some discrepancy at the very end of calculation of the second number between Go and JavaScript which causes the second word to be different:

gore> var i uint64 = 10669074847157321977
gore> fmt.Println(i<<1)
2891405620605092338

> const bigInt = require('big-integer')
> i = bigInt("10669074847157321977")
> i.shiftLeft(1)
Integer { value: 21338149694314643954n }

The two values of the left-shift operation on 10669074847157321977 do not match!

I ran it in Wolfram Alpha and I also got 21338149694314643954: https://www.wolframalpha.com/input/?i=10669074847157321977+%3C%3C+1

[jakubgs]

I think I'm using big-integer library unnecessarily, JavaScript now has the BigInt type: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt Which gives the same result:

> i = BigInt("10669074847157321977")
10669074847157321977n
> i << BigInt(1)
21338149694314643954n

[cammellos]

In go we use uint64 for both bit and data. This is capped to 64bits. When shifting left, this value might "overflow", meaning that any bit in position greater than 64 will be set to 0 (in golang it just does not exist). In the js implementation we use bigInt, which are not capped, therefore shifting left actually preservers those bytes, and gives to a difference in calculation.

To overcome this we always and any value with the mask 0xffffffffffffffff which only preservers the 64 least significant bits.

[jakubgs]

I generated a bunch of test cases for the JS using this script:

package main

import (
    "encoding/hex"
    "fmt"
    "os"

    "github.com/status-im/status-go/eth-node/crypto"
    "github.com/status-im/status-go/protocol/identity/alias"
)

type Pair struct {
    publicKey string
    chatName  string
}

func genPubKeyAndName() (*Pair, error) {
    privateKey, err := crypto.GenerateKey()
    if err != nil {
        return nil, err
    }
    publicKey := hex.EncodeToString(crypto.FromECDSAPub(&privateKey.PublicKey))
    chatName := alias.GenerateFromPublicKey(&privateKey.PublicKey)
    return &Pair{publicKey, chatName}, nil
}

func main() {
    for i := 0; i < 10; i++ {
        pair, err := genPubKeyAndName()
        if err != nil {
            fmt.Println(err)
            os.Exit(1)
        }
        fmt.Println(pair)
    }
}

Result:

 $ go run main.go
&{041c678bdeb6940df3e436cee76612ae6177f46e54e541fc024b572fafd9be89ba43612d6e26bba8f3961b5d379efe1fb031a718ea24936a83550086f4ba2c5c94 Enormous Vain Angwantibo}
&{0417b1f4e7e0d2ab09381875d66c4ac9fd1a576cfe3886955d08cfa57d5c204f22f90f27f2a9f575b59e63999ffe399e80b15a7cecbf1c4e3d6fb87b047944f1d9 Smoggy Noteworthy Ivorybackedwoodswallow}
&{0447b772a4bb239b78d20f980e88c015d885e174b78654bbf7c35f38b1d9b73197decf7d769a7da261089e32f740154a6c8a33c577c0debc9caa57d2803fc29c4c Grandiose Cooperative Kitfox}
&{048bea344d9e618556de6e6735987ab11984fa7a74f8cddfef81c906ea6647c5022b0dead89d33c104adf452e304cf7c2c5c37257a77837af6e839c80e1b310f65 Quarrelsome Equatorial Curlew}
&{04f6b657140489de221184b0ec3134de0d5486c07fd04ebba3e28b26237904f7a37087ad60a60c1255dfbe94a37e835581f5c6a435dcd4226f12ad73485ebd0282 Insecure Grumpy Adouri}
&{04232d990f05e918ab1cbf9c5b3fe103280a21900b650477dfbeff2835651a77e9bbc0d40c44d41d3aaf16eae16f1b3d604107032c43275d996f5d7a7242ae66bb Humming Brilliant Aoudad}
&{0419cdc5d7316e4f9ae55e5eda00c337600c64fb21451e0ddec37b6e5a5b19936daafcc8a0c61da05ef963d9d342b5cbb661de89f11f02f1791ea97a70ce4b4fa0 Sentimental Stiff Wallaby}
&{049c450deea541169809902d6199f0269bfb60439cd93b7339af98cf0bf6d553d6e73435105c7131a72d512c75707bc073bd426ad742aecde64d14f74d0dca5f5c Amused Cadetblue Acouchi}
&{04722d1a490efc6fdb811c266fc3fa0a59ea5f2984538bb134cec219da0e4e6646ce31c57522e58839e8d441c1af792f9d367558560632b48fca68fde00fe5de0c Alive Jagged Alligator}
&{040bc5bdbd8edf82962b191e80541d7ca8868920b1b415fcd999d6bd723cbbcff17f34e1e6e0484c11d9c7c63b164878a6da3173a49ceaf5fea2faac98928f8a47 Defensive Impartial Impala}

[jakubgs]

Tests work well:

 $ yarn test
yarn run v1.21.1
$ node -r esm test/main.js
TAP version 13
# uncompressedPublicKeyToChatName
ok 1 - should return Studious Gold Mustang
ok 2 - should return Enormous Vain Angwantibo
ok 3 - should return Smoggy Noteworthy Ivorybackedwoodswallow
ok 4 - should return Grandiose Cooperative Kitfox
ok 5 - should return Quarrelsome Equatorial Curlew
ok 6 - should return Insecure Grumpy Adouri
ok 7 - should return Humming Brilliant Aoudad
ok 8 - should return Sentimental Stiff Wallaby
ok 9 - should return Amused Cadetblue Acouchi
ok 10 - should return Alive Jagged Alligator
ok 11 - should return Defensive Impartial Impala
1..11

# ok
# success: 11
# skipped: 0
# failure: 0
Done in 0.22s.

Code: https://github.com/status-im/js-status-chat-name/blob/fcc52aca93e122d138fb6a4e626c2398b47fd6ab/test/main.js#L1-L34

[jakubgs]

I have created the first 0.1.1 release: https://github.com/status-im/js-status-chat-name/releases/tag/v0.1.1 It was bundle together using Rollup.js in the iife format.

[jakubgs]

Closing this since I think it works as intended.