search

vbakke / trytes

Converting between trytes and bytes
6 stars 1 forks source link

trytes conversion doesn't work for longer trytes #11

Open akashgoswami opened 6 years ago

akashgoswami commented 6 years ago

While converting larger trytes in IOTA, the conversion doesn't work reliably and produces different output than the conventional method.

Here is a program which demonstrates the problem

const Trytes = require('trytes');

var RADIX = 3;
var RADIX_BYTES = 256;
var MAX_TRIT_VALUE = 1;
var MIN_TRIT_VALUE = -1;
var BYTE_HASH_LENGTH = 48;

// All possible tryte values
var trytesAlphabet = "9ABCDEFGHIJKLMNOPQRSTUVWXYZ"

// map of all trits representations
var trytesTrits = [
    [ 0,  0,  0],
    [ 1,  0,  0],
    [-1,  1,  0],
    [ 0,  1,  0],
    [ 1,  1,  0],
    [-1, -1,  1],
    [ 0, -1,  1],
    [ 1, -1,  1],
    [-1,  0,  1],
    [ 0,  0,  1],
    [ 1,  0,  1],
    [-1,  1,  1],
    [ 0,  1,  1],
    [ 1,  1,  1],
    [-1, -1, -1],
    [ 0, -1, -1],
    [ 1, -1, -1],
    [-1,  0, -1],
    [ 0,  0, -1],
    [ 1,  0, -1],
    [-1,  1, -1],
    [ 0,  1, -1],
    [ 1,  1, -1],
    [-1, -1,  0],
    [ 0, -1,  0],
    [ 1, -1,  0],
    [-1,  0,  0]
];

function Trits( input, state ) {

    var trits = state || [];

    if (Number.isInteger(input)) {

        var absoluteValue = input < 0 ? -input : input;

        while (absoluteValue > 0) {

            var remainder = absoluteValue % 3;
            absoluteValue = Math.floor(absoluteValue / 3);

            if (remainder > 1) {
                remainder = -1;
                absoluteValue++;
            }

            trits[trits.length] = remainder;
        }
        if (input < 0) {

            for (var i = 0; i < trits.length; i++) {

                trits[i] = -trits[i];
            }
        }
    } else {

        for (var i = 0; i < input.length; i++) {

            var index = trytesAlphabet.indexOf(input.charAt(i));
            trits[i * 3] = trytesTrits[index][0];
            trits[i * 3 + 1] = trytesTrits[index][1];
            trits[i * 3 + 2] = trytesTrits[index][2];
        }
    }

    return trits;
}

const NUMBER_OF_TRITS_IN_A_BYTE = 5;
const NUMBER_OF_TRITS_IN_A_TRYTE = 3;

function Trits2Bytes(trits) {

    var expectedLength = Math.floor((trits.length + NUMBER_OF_TRITS_IN_A_BYTE - 1) / NUMBER_OF_TRITS_IN_A_BYTE);
    var output = new Uint8Array(expectedLength);

    for (var i = 0; i < expectedLength; i++) {
        var value = 0;
        for (var j = (trits.length - i * NUMBER_OF_TRITS_IN_A_BYTE) < 5 ? (trits.length - i * NUMBER_OF_TRITS_IN_A_BYTE) : NUMBER_OF_TRITS_IN_A_BYTE; j-- > 0; ) {
            value = value * 3 + trits[ i * NUMBER_OF_TRITS_IN_A_BYTE + j];
        }

        output[i] = value & 0xFF;
    }

    return output;

}

var raw = "999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999THIRRJFYZLEFMIWYVWLGUQST9A9A9CSJMD9M9MXQYYGKTEGJBYCVLPEJYNBARFUVZPTVFBOFWTVNPRTCX9SOVSA999999999999999999999999999999999999999999999999IBV9XZD99C99999999C99999999TRMRK9PYWHCSPCHLNAKHPEHI9BJUOILLILO9KCAHGNN9CUG9OXBQGRBMNDUTL9IQIAFYKWOWHKL9QIAOXZKGDXZNBSAKIZXSDUCHKVAATCSNV9RKOCE99IYHYSVVTECXFP9EQVZ9JFNZMSNOKCBVVEJQKXPOWYO999ZKGDXZNBSAKIZXSDUCHKVAATCSNV9RKOCE99IYHYSVVTECXFP9EQVZ9JNZMSNOKCBVVEJQKXPOWYO999999999999999999999999999999KMDGQWQLE999999999MMMMMMMMM9F9VUKQUCZWOOGZZSSYHQDCXNSK";

var trits = Trits(raw);
var bytes = Trits2Bytes(trits);
var bytes2 = Trytes.encodeTryteStringAsBytes(raw);    

console.log("Length ", bytes.length, bytes2.length);

for ( var i = 0; i < bytes.length; i++){
    if (bytes[i] !== bytes2[i]){
        console.log("Index ", i, " unequal. ", bytes[i], bytes2[i]);
    }
}
akashgoswami commented 6 years ago

Produced output

Length  1604 1605
Index  1312  unequal.  154 222
Index  1313  unequal.  84 83
Index  1314  unequal.  247 18
Index  1315  unequal.  29 32
Index  1316  unequal.  240 227
Index  1317  unequal.  80 107
Index  1320  unequal.  157 144
Index  1321  unequal.  75 158
Index  1322  unequal.  218 214
Index  1323  unequal.  214 201
Index  1324  unequal.  158 225
Index  1325  unequal.  181 176
Index  1326  unequal.  249 20
Index  1330  unequal.  57 138
Index  1335  unequal.  226 240
Index  1336  unequal.  74 157
Index  1337  unequal.  62 71
Index  1339  unequal.  95 98
Index  1341  unequal.  204 191
Index  1342  unequal.  90 92
Index  1343  unequal.  106 115
Index  1344  unequal.  137 151
Index  1345  unequal.  112 111
Index  1346  unequal.  138 134
Index  1348  unequal.  229 54
Index  1349  unequal.  204 191
Index  1350  unequal.  224 238
Index  1351  unequal.  142 212
Index  1352  unequal.  209 204
Index  1354  unequal.  220 45
Index  1355  unequal.  222 209
Index  1356  unequal.  101 128
Index  1357  unequal.  41 125
Index  1358  unequal.  171 167
Index  1359  unequal.  74 101
Index  1360  unequal.  247 72
Index  1361  unequal.  184 171
Index  1362  unequal.  96 123
Index  1363  unequal.  56 140
Index  1393  unequal.  202 189
Index  1394  unequal.  212 198
Index  1395  unequal.  175 162
Index  1396  unequal.  78 161
Index  1409  unequal.  193 180
Index  1410  unequal.  99 126
Index  1411  unequal.  149 217
Index  1412  unequal.  4 3
Index  1413  unequal.  191 205
Index  1414  unequal.  163 233
Index  1415  unequal.  30 29
Index  1416  unequal.  194 208
Index  1417  unequal.  183 172
Index  1418  unequal.  111 110
Index  1419  unequal.  14 41
Index  1420  unequal.  208 195
Index  1421  unequal.  160 146
Index  1422  unequal.  234 221
Index  1423  unequal.  28 27
Index  1426  unequal.  219 47
Index  1430  unequal.  252 5
Index  1432  unequal.  178 165
Index  1433  unequal.  66 65
Index  1434  unequal.  135 149
Index  1435  unequal.  255 1
Index  1436  unequal.  203 190
Index  1438  unequal.  220 45
Index  1439  unequal.  17 26
Index  1440  unequal.  192 206
Index  1441  unequal.  149 216
Index  1442  unequal.  118 117
Index  1443  unequal.  95 122
Index  1444  unequal.  157 225
Index  1445  unequal.  106 114
Index  1447  unequal.  227 52
Index  1449  unequal.  208 195
Index  1450  unequal.  208 197
Index  1451  unequal.  147 142
Index  1452  unequal.  225 239
Index  1453  unequal.  34 33
Index  1455  unequal.  246 17
Index  1457  unequal.  225 221
Index  1458  unequal.  53 80
Index  1460  unequal.  230 217
Index  1461  unequal.  147 161
Index  1462  unequal.  86 88
Index  1463  unequal.  6 15
Index  1465  unequal.  254 79
Index  1466  unequal.  183 179
Index  1468  unequal.  183 173
Index  1469  unequal.  102 101
Index  1470  unequal.  22 49
Index  1471  unequal.  178 165
Index  1472  unequal.  25 33
Index  1473  unequal.  140 154
Index  1474  unequal.  240 67
Index  1475  unequal.  175 162
Index  1476  unequal.  186 173
Index  1477  unequal.  183 172
Index  1478  unequal.  2 1
Index  1480  unequal.  170 238
Index  1481  unequal.  241 227
Index  1482  unequal.  100 127
Index  1483  unequal.  159 230
Index  1484  unequal.  43 51
Index  1485  unequal.  178 165
Index  1486  unequal.  99 101
Index  1487  unequal.  252 5
Index  1488  unequal.  234 221
Index  1489  unequal.  159 229
Index  1490  unequal.  0 8
Index  1491  unequal.  185 172
Index  1492  unequal.  137 204
Index  1493  unequal.  117 125
Index  1494  unequal.  140 154
Index  1495  unequal.  138 208
Index  1496  unequal.  31 30
Index  1498  unequal.  159 230
Index  1499  unequal.  92 91
Index  1500  unequal.  44 71
Index  1501  unequal.  73 154
Index  1502  unequal.  144 140
Index  1503  unequal.  198 212
Index  1504  unequal.  220 47
Index  1506  unequal.  229 216
Index  1507  unequal.  114 116
Index  1509  unequal.  226 240
Index  1510  unequal.  136 206
Index  1511  unequal.  185 171
Index  1513  unequal.  203 190
Index  1514  unequal.  229 224
Index  1515  unequal.  100 127
Index  1516  unequal.  238 63
Index  1519  unequal.  83 86
Index  1520  unequal.  193 180
Index  1522  unequal.  41 125
Index  1523  unequal.  254 7
Index  1524  unequal.  45 72
Index  1525  unequal.  221 46
Index  1529  unequal.  71 80
Index  1530  unequal.  25 52
Index  1531  unequal.  65 149
Index  1532  unequal.  191 187
Index  1534  unequal.  247 72
Index  1535  unequal.  159 146
Index  1536  unequal.  148 135
Index  1537  unequal.  52 132
Index  1538  unequal.  245 241
Index  1540  unequal.  137 205
Index  1541  unequal.  117 125
Index  1542  unequal.  140 154
Index  1543  unequal.  138 208
Index  1544  unequal.  31 30
Index  1546  unequal.  159 230
Index  1547  unequal.  92 91
Index  1548  unequal.  44 71
Index  1549  unequal.  73 154
Index  1550  unequal.  144 140
Index  1551  unequal.  198 212
Index  1552  unequal.  220 47
Index  1570  unequal.  175 162
Index  1571  unequal.  121 120
Index  1572  unequal.  206 193
Index  1573  unequal.  146 213
Index  1574  unequal.  165 160
Index  1575  unequal.  160 147
Index  1576  unequal.  1 0
Index  1587  unequal.  175 162
Index  1588  unequal.  82 81
Index  1589  unequal.  200 196
Index  1590  unequal.  240 227
Index  1591  unequal.  237 64
Index  1592  unequal.  248 235
Index  1593  unequal.  171 185
Index  1594  unequal.  44 127
Index  1595  unequal.  249 236
Index  1596  unequal.  26 53
Index  1597  unequal.  56 140
Index  1598  unequal.  71 80
Index  1599  unequal.  98 125
Index  1601  unequal.  138 134
Index  1602  unequal.  46 73
vbakke commented 6 years ago

Sorry, could you please elaborate? When I test your code, and change the content of raw, the two algorithms differ not just for long trytes, but any tryte. Well, except 9's that gets encoded the same, it looks like.

raw Trits2Bytes() Trytes.encodeTryteStringAsBytes()
AZ 230, 0 217,2,254
TEST 141,152,254 155, 219,6,244
TEST9 141,152,254 155, 219,6

When I try to decode back to the original raw:

    var raw = "999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999THIRRJFYZLEFMIWYVWLGUQST9A9A9CSJMD9M9MXQYYGKTEGJBYCVLPEJYNBARFUVZPTVFBOFWTVNPRTCX9SOVSA999999999999999999999999999999999999999999999999IBV9XZD99C99999999C99999999TRMRK9PYWHCSPCHLNAKHPEHI9BJUOILLILO9KCAHGNN9CUG9OXBQGRBMNDUTL9IQIAFYKWOWHKL9QIAOXZKGDXZNBSAKIZXSDUCHKVAATCSNV9RKOCE99IYHYSVVTECXFP9EQVZ9JFNZMSNOKCBVVEJQKXPOWYO999ZKGDXZNBSAKIZXSDUCHKVAATCSNV9RKOCE99IYHYSVVTECXFP9EQVZ9JNZMSNOKCBVVEJQKXPOWYO999999999999999999999999999999KMDGQWQLE999999999MMMMMMMMM9F9VUKQUCZWOOGZZSSYHQDCXNSK";
    var bytes2 = Trytes.encodeTryteStringAsBytes(raw);    
    var reverted = Trytes.decodeTryteStringFromBytes(bytes2);
    console.log('Strings: '+ (raw === reverted ? 'are equal' : 'MISMATCH'));

I get Strings: are equal, which is the purpose of this library. To retrieve the original tryte string, after taking a detour via the binary world.

akashgoswami commented 6 years ago

You are right, I think our conversion methods fundamentally are different. I was trying to decode IOTA gossip protocol (between two IRIs) using your library and that's when I discovered the difference.

IOTA converts Trytes to trits and then converts 5 trits to a single byte in a 2's complement representation. I wrote another utility which converts Trytes to Trits and then to bytes in the format which is understood by IOTA.

http://trytes-bytes.surge.sh/

So I think we could close this by clearly explaining that this is not compliant with IOTA gossip protocol conversion method.

vbakke commented 6 years ago

Ah. That makes more sense. :)

I've based my conversion on the trits forming values from 0-26, unsigned, and counting up to 0-242 when shifting trits into tryte5s.

Will add a note that states this is not gossip compliant.

Length of original message

I like your web site. I see that you too have the problem of needing exactly 5 of the tryte3 characters, to avoid the trailing 9s, when converting back. Not sure if the gossip protocol also has that problem.

You need to either accept the limitation of 5 trytes; add a length value; or add a terminator.

I ended up adding a terminator, one that indicates who many trytes to shave off when decoding the bytes back to trytes.

Encoding instead of conversion

Also, as a last note of what I found out, having a tryte-byte-fight. There is no such thing as a two way tryte-byte conversion, using the same methods. (The IOTA Foundation is doing the same mistake, using a method name like trytesToAscii() that can only take values up to 255, not all the way to 727. : )

Just looking at you web site, I get the impression that I can also take a byte array, and convert it to trytes, and then convert it back later. (Let's say if I want to send Unicode message in an IOTA transaction, or convert an encrypted seed (which will use the full 0-255 range of a byte) into trytes.

But sadly it dosen't work like that. I recommend you rename it to indicate that your are only encoding trytes as bytes, and that you can decode them back to the original trytes.

Try converting the three bytes '0x37 0x80 0x2E' to trytes, and then back... ;-)