Compressed XCP Transactions

This is a draft proposal for compressed Counterparty messages. The benefits will be:

  • slightly reduced fees for ordinary XCP transactions.
  • significantly reduced fees when bundling several XCP messages in one BTC tx.

First let’s look at a typical Counterparty message:

434e5452505254590a000000000000000100000000ee6b28000000000001d6b896000000000bebc2001f800000000000000000

Prefix

The first eight bytes, 434e545250525459, is the prefix. It translates to CNTRPRTY. All Counterparty transactions use this prefix.

My proposal suggests an alternative prefix, 584350, meaning XCP. This prefix shall indicate that the message is compressed.

The next byte signals the number of messages that are pooled together, from 1 to 255.

Compression

The message contains plenty of repeated zero-bytes, making it very suitable for compression:

0a 00 00 00 00 00 00 00 01 00 00 00 00 ee 6b 28 00 00 00 00 00 01 d6 b8 96 00 00 00 00 0b eb c2 00 1f 80 00 00 00 00 00 00 00 00

I have provided working javascript code for compressing and decompressing Counterparty messages. But let’s first manually go through the process.

  1. Count consecutive non-zeros and zeros:
  1. Now we have 6 pairs of non-zeros and zeros:
    (1,7), (1,4), (3,5), (4,4), (3,1), (2,8).
  2. Multiply the first of each pair by 16 and add the second number, e.g. (1,7) => 1*16+7 = 23. We get the following values:
    23, 20, 53, 68, 48, 40
  3. Convert the values 6, 23, 20, 53, 68, 48, 40 to hex:
    06 17 14 35 44 30 28.
  4. Remove zero-bytes from the message in #1:
    0a ee 6b 28 01 d6 b8 96 0b eb c2 1f 80.
  5. Combine the values in #4 and the message without zero-bytes from #5:
    06 17 14 35 44 30 28 0a ee 6b 28 01 d6 b8 96 0b eb c2 1f 80.
  6. Finally add the prefix and a byte signaling we only have one Counterparty message:
    58 43 50 01 06 17 14 35 44 30 28 0a ee 6b 28 01 d6 b8 96 0b eb c2 1f 80.

While the original message takes up 51 bytes, the compressed version is just 25 bytes long. A reduction of more than 50%!

Special case: If you count a run of >15 in step #1, break it up. E.g you have 20 consecutive zeros but count it as 15 zeros, then 0 non-zeros, and 5 zeros.

Decompression

Now let’s decompress to get back to the original message. We start with our result from earlier:
58 43 50 01 06 17 14 35 44 30 28 0a ee 6b 28 01 d6 b8 96 0b eb c2 1f 80

  1. 58 43 50 is the XCP prefix that tells us we’re dealing with a compressed message.
  2. 01 means we only have one message to decompress.
  3. 06 signals that the next 6 bytes contain length data.
  4. Convert the next byte, 17, to decimal and get 23. Divide by 16 to get 1 with remainder 7.
  5. From the message without zero-bytes, take the first 1 byte and add 7 zero-bytes:
    0a 00 00 00 00 00 00 00
  6. Repeat with the next length-byte, 14, to get 1 with remainder 4. Append the next 1 byte and add 4 zeros:
    0a 00 00 00 00 00 00 00 01 00 00 00 00
  7. Do this for all the length bytes until the original message is recreated.
  8. Add the 43 4e 54 52 50 52 54 59, CNTRPRTY, prefix.

If we have more than 1 message to decompress, go back to #3 and recreate the remaining messages.

Compression Savings

My example is a DEX order which is particularly suitable for compression. Long runs of zeros are due to fixed sizes used for asset names and quantities. If we break it down:

  • 0000000000000001 and 0000000001d6b896 are the assets XCP and CPNEWS.
  • 00000000ee6b2800 and 0000000001d6b896 are the quantities, 4000000000 and 200000000. These are actually 40 and 2 respectively, but divisible tokens are multiplied by 100 million.
  • At the end there are eight zero-bytes which I believe are deadweight.

The result for other transaction types:

TypeOrigComprSave
Enhanced Send46379 (20%)
Enh. Send w. Memo65587 (11%)
Broadcast1241177 (6%)
Dividend332013 (39%)
Issuance73649 (12%)
DEX Order512526 (51%)
DEX Cancel4141
Dispenser Open634419 (30%)
Dispenser Close421428 (67%)

The impact of compression depends on encoding:

Op_return

This is the most common encoding for Counterparty. It is limited to 80 bytes of data.

  • For a regular single transaction, a compressed message will not make much difference. It will shave off some bytes, reducing fees, but the bitcoin transaction takes about 220 bytes. So the overall percentage saving will be less than shown in the table, realistically a few percent.
  • However, with compression and bundling it will be possible to both cancel an order and place a new one inside op_return. I.e. you will have a chain of two Counterparty transactions inside one op_return, thereby reduce fees by almost half.
  • The same is possible with dispensers. One op_return can fit both a closing and opening of a new dispenser.

Segwit

This is an encoding which uses a chain of two bitcoin transactions to encode large amounts of Counterparty data. The overhead is pretty big (I don’t have a number but think it is around 500 bytes). The marginal efficiency, however, is near 100%.

  • By adding a longer chain of compressed transactions, the marginal footprint goes toward the numbers in the table. For example, the above issuance would only cost 64 bytes worth of fees. If you want to issue a set of subassets, this method will really save time and fees.

Advantages

Counterparty has a history of introducing specialized group transactions; dividends, multi-send, sweep. Each comes with risks of bugs, complicated database logic and the challenge of setting appropriate XCP fees.

This proposal introduces one general solution. All logic is isolated at the parsing, so no modifications are needed for specific transaction types or DB tables.

Technical Considerations

My javascript implementation was able to decompress more than a million messages per second. Speed is not an issue.

Counterparty messages are scrambled with RC4 and a short prefix is therefore expected to collide occasionally with protocols like OMNI. With the three letter XCP prefix, this will happen with about one in 16 million messages. However, when it does happen, the length bytes will not match and the message shall be rejected. In theory you could argue that length bytes can line up, but without formally estimating I’m pretty sure the risk is less than a one in a trillion. And even in this case, all that will happen is that Counterparty detects an invalid transaction.

Code

I wrote a script which compresses and then decompresses Counterparty messages. I didn’t put effort into making an elegant solution. I only tested to make sure that it works both ways.

To test any Counterparty message, copy the transaction ID from Xchain and get hex code from the Counterparty Decoder.

<!DOCTYPE html>
<html>
  <head>
    <title>Compressed XCP Message</title>
    <script>
      let prefix_standard = '434e545250525459'; //CNTRPRTY
      let prefix_compressed = '58435001'; //XCP1

      let msgs = ['434e5452505254590200000000000000010000000b97542d4400cbfbcd51af4e7ff152b1b0625003a765f56f3fbb', //enhanced send, https://jpja.github.io/Electrum-Counterparty/decode_tx.html?tx=2
                  '434e5452505254590200000b5b4a037cd1000000000000000100312f9d3880c4134887800341f7ce7d563189ccd74265686176696f72206e65766572206c696573', //enhanced send w memo, tx=3
                  '434e5452505254590000001e545105c7bff0000000000000000000006a706a612e6e65742f7064662f56616c75652d6f662d5843502e706466202d2032626361393565623931653662653165396165356232336465356638333733393532393837663063646562626437663662306434383438323139353166343836', //Broadcast, tx=12
                  '434e5452505254593200000000000f4240000000000002926e0000000006c8bb31', //Dividend, tx=15
                  '434e545250525459140000473f7a265142000000000000002100000068747470733a2f2f6e667473682e6172742f692f4f786e6b526e3079416a66626f59436a4762374c2e6a736f6e', //Issuance, https://xchain.io/tx/2216656
                  '434e5452505254590a000000000002926e000000000000000100000000000000000000000002625a0000900000000000000000', //DEX JPJA-BTC, https://xchain.io/tx/1906227
                  '434e5452505254590a000000000000000100000000ee6b28000000000001d6b896000000000bebc2001f800000000000000000', //DEX CPNEWS-XCP, https://xchain.io/tx/1906227
                  '434e545250525459468c4ee553e2325d479474e28d353c77558afb6dbe9d7a24e33051ad31b590a207', //DEX Cancel Order, https://xchain.io/tx/2014492
                  '434e5452505254590c00000015957722ae00000000000000010000000000000001000000000010c8e00100d28e4bf3d70f76c6757580d4b1d9a4e9834f5cd6', //Dispenser LOCHNESS, https://xchain.io/tx/2152628
                  '434e5452505254590c000000000003ded80000000000000000000000000000000000000000000000000a', //Dispenser – OLGA Close, https://jpja.github.io/Electrum-Counterparty/decode_tx.html?tx=6bef5be1766b87f90f94de1f01fee0613248b9aed7a1e164e11667783eea6221

                 ];

      function compress(msg){

        if (msg.substring(0,16) == prefix_standard) {
          msg = msg.substring(16);
        } else {
          return 'err; lacks CNTRPRTY prefix';
        }

        //bytes
        let b = msg.match(/.{1,2}/g);

        //pattern of zeros (Z) and non-zeros (N)
        let pattern = '';
        let non_zeros = '';
        for (var i = 0; i < b.length; i++) {
          if (b[i] == '00') {
            pattern += 'Z';
          } else {
            pattern += 'N';
            non_zeros += b[i];
          }
        }

        //count run lengths of N's and Z's
        let runs = [];
        let run = 0;
        for (let i = 0; i < pattern.length; i++) {
          run += 1;
          if (i == 0 && pattern[i] == 'Z') { //first "run" is 0 N's 
            runs.push(0);
          } 
          if (i == pattern.length-1 && pattern[i] == 'N') { //ends with N
            runs.push(run);
            runs.push(0); 
          } else if (i == pattern.length-1 && pattern[i] == 'Z') { //ends with Z 
            runs.push(run);
          } else if (pattern[i] != pattern[i+1]) { //run ends
            runs.push(run);
            run = 0;
          } else if (run == 15) { //break down long runs
            runs.push(run);
            runs.push(0);
            run = 0;
          }
        }

        //get number of run pairs of N and Z
        let num_pairs = (runs.length / 2).toString(16);
        num_pairs = num_pairs.padStart(2, '0');

        //each run pair is represented by an integer [0,255]
        let msg_ind = '';
        for (var i = 0; i < runs.length; i+=2) {
          let pair = (runs[i]*16 + runs[i+1]).toString(16);
          pair = pair.padStart(2, '0')
          msg_ind += pair;
        }

        let compr_msg = num_pairs + msg_ind + non_zeros;
        return prefix_compressed + compr_msg;
      }


      function decompress(msg){

        if (msg.substring(0,prefix_compressed.length) == prefix_compressed) {
          msg = msg.substring(prefix_compressed.length);
        } else {
          return 'err; lacks compressed XCP prefix';
        }

        //get number of pairs of Ns and Zs
        let num_pairs = msg.substring(0,2);
        num_pairs = parseInt(num_pairs,16);

        //get the length of each run
        let runs = [];
        let pos = 0;
        let run_pos = [];
        for (var i = 1; i <= num_pairs; i++) {
          let pair = msg.substr(i*2,2);
          pair = parseInt(pair,16);
          let N = Math.floor(pair / 16);
          run_pos.push(pos);
          runs.push(N);
          pos += N*2;
          let Z = pair % 16;
          run_pos.push(0);
          runs.push(Z);
        }

        //compressed message begins after length info
        let non_zeros = msg.substring(2+num_pairs*2);
        //add zeros
        let uncompressed = '';
        for (var i = 0; i < runs.length-1; i+=2) {
          uncompressed += non_zeros.substr(run_pos[i],runs[i]*2);
          uncompressed += '000000000000000000000000000000'.substr(0,runs[i+1]*2);
        }

        return prefix_standard + uncompressed;
      }

      function speed_compress(iter) {
        var start = new Date().getTime();      
        for (i = 0; i < iter; ++i) {
          let ind = i % msgs.length;
          compress(msgs[ind]);
        }
        var end = new Date().getTime();
        var time = end - start;
        var speed = iter / time * 1000;
        console.log('Compression speed:   ' + speed.toFixed(0) + '/sec');
      }

      function speed_decompress(iter) {
        var compr = [];
        for (i = 0; i < msgs.length; ++i) {
          compr.push(compress(msgs[i]));
        }
        var start = new Date().getTime();
        for (i = 0; i < iter; ++i) {
          let ind = i % msgs.length;
          decompress(compr[ind]);
        }
        var end = new Date().getTime();
        var time = end - start;
        var speed = iter / time * 1000;
        console.log('Decompression speed: ' + speed.toFixed(0) + '/sec');
      }

      function test() {
        for (let i=0; i < msgs.length; i++) {
          let orig = msgs[i];
          let compressed = compress(orig);
          let uncompressed = decompress(compressed);
          let orig_len = orig.length / 2;
          let compr_len = compressed.length / 2;
          let save = orig_len - compr_len;
          let save_pst = (save / orig_len * 100).toFixed(0);
          let save_prefix = (prefix_standard.length - prefix_compressed.length) / 2;
          console.log('*** i = ' + i);
          console.log(orig_len + '  ' + orig);
          console.log(compr_len + '  ' + compressed);
          console.log(save + ' bytes saved (' + save_pst +'%)');
          console.log('  ' + save_prefix  + ' bytes prefix save');
          console.log('  ' + (save - save_prefix) + ' bytes compression save');
          //console.log(uncompressed);
          if (orig != uncompressed) console.log('ERROR');
        }
      }

    </script></head>
  <body onload="speed_compress(1e5);speed_decompress(1e5);test();">
    View results in console.
  </body>
</html>

Multiple Senders in One Transaction

This is a more complicated solution which I do not propose at this point.

The idea is to sign a Counterparty message, then pool it together with other XCP transactions from other users, and have a separate operator who bundles all of these XCP txs inside one Bitcoin transaction.

A 32 byte ECDSA signature must be added for each XCP user but the overall efficiency is very high. This could be an excellent option in case Bitcoin fees skyrocket again.

Output Ordering

The op_return data containing the Counterparty message shall be the first output.

TODO: Look into other encoding used by Counterparty. How is the XCP data ordered for these relative to other BTC outputs?

At least two Counterparty tx types also use a BTC dust output to determine recipient:

  • Classic send
  • Issuance (if present, the BTC dust initiates transfer of ownership)

Since compressed transactions allow batching of several Counterparty messages, it must be specified which output that corresponds to the classic send or issuance. Therefore these two transactions shall have one byte inserted after the ID specifying the position of the BTC dust.

In case this byte reads 00 for an issuance there is no transfer of ownership. For a classic send 00 will fail, as a recipient is required.

Special Case: Dispense

A Bitcoin transaction without a Counterparty message can trigger a dispense. It would be nice to trigger a dispense also within the batch sequence. A useful example may be to do these three instructions all within one BTC tx:

  1. Buy 0.5 XCP for dispenser
  2. Issue MYASSET
  3. Offer a MYASSET token on the DEX

To make this possible one new TX ID must be reserved. I suggest 21 (hex 15). This puts it right after 20, which signals the creation of a new dispenser. The byte after the TX ID specifies which output that shall trigger a dispense.

This will take up four bytes, 01 20 15 01:

  • 01 – the next one byte contains all length data.
  • 20 – the length byte indicating the message exists of 2 non-zeros followed by no zeros (notice that hex 20 is decimal 32 which divided by 16 gives 2 with reminder 0, see definition above).
  • 15 – dispense.
  • 01 – the second output may trigger a dispense.

Categories: Uncategorized