A Canister Market

Let’s extend our escrow canister to a market canister: a trusted third party that enables the safe exchange of canisters for tokens.

Recall our escrow canister implemented the methods:

  • account_id: returns an account ID to which a caller should deposit tokens inorder to buy canisters.

  • withdraw: refunds all tokens to the caller, minus the transaction fee.

To these we add:

  • post: takes sole control of a given canister ID and lists it for sale at given price; before calling, the seller should add the market canister as one of the controllers of the canister.

  • unpost: undoes a post, that is, restores the original controllers of the canister and removes it from the list of canisters for sale.

  • catalog: returns the list of canisters for sale.

  • buy: transfers the price of a given canister from the caller’s escrow account to the seller’s main account, and on success, gives control of the canister ID to the caller.

service : {
  account_id : () -> (text) query;
  withdraw : () -> ();
  post : (record { price : nat64; canister_id : principal}) -> ();
  unpost : (nat64) -> ();
  buy : (nat64) -> ();
  catalog : () -> (vec record {
    lot : nat64;
    canister_id : principal;
    price : nat64;
    seller : principal;
    controllers : vec principal;
  }) query;
}

We must be mindful of the asynchronous nature of calls. We err on the side of simplicity: a single locked global prevents any interleaving of calls made during the execution of any of these methods; for example, if post is waiting to hear back from a call, then a withdraw call immediately fail. The caller should try again later.

It might be safe to interleave certain kinds of calls, or add extra logic to handle interleaved calls, but such optimizations may be overkill. Our methods only make calls to the ledger and management canisters, which we expect to return quickly.

The locked global means we must avoid reject system calls in callbacks, because they revert the wasm memory: it could cause our canister to lock up forever.

We must prevent bait-and-switch scams. Bob should not be able to post a canister, then unpost and post again with a higher price just before Alice’s buy call is processed. Similary, Bob should not be able to post a canister, then unpost, then upgrade the canister before reposting, causing Alice to buy something else than that was advertised.

Our solution is to associate each catalog entry with a strictly increasing index. On a post, this index is incremented and assigned to catalog entry, namely, a particular price and canister that is now controlled by the market canister. A buy call refers to a catalog entry by this index.

Suppose Bob attempts a bait-and-switch. His unpost call succeeds if it is processed before Alice’s buy call, but a second post call assigns a new index to his canister, and the buy call simply fails.

We must also prevent Bob from posting the same canister twice. This is enforced by our simple locking scheme, and checking that the caller is a controller of a posted canister. The first time Bob posts his canister, the market takes sole control of it. If Bob attemps to post the canister again, nothing happens because Bob is no longer a controller of it; only the market is.

The following source compiles to:

#include <stddef.h>
#include "string.h"
#include "sha.h"
#include "candy.h"
#define IMPORT(m,n) __attribute__((import_module(m))) __attribute__((import_name(n)));
#define EXPORT(n) asm(n) __attribute__((visibility("default")))
typedef uint32_t u32;
typedef uint64_t u64;
typedef uint8_t u8;
void reply_append(void*, u32)     IMPORT("ic0", "msg_reply_data_append");
void reply(void)                  IMPORT("ic0", "msg_reply");
u32 caller_size(void)             IMPORT("ic0", "msg_caller_size");
void caller_copy(void*, u32, u32) IMPORT("ic0", "msg_caller_copy");
u32 self_size(void)               IMPORT("ic0", "canister_self_size");
void self_copy(void*, u32, u32)   IMPORT("ic0", "canister_self_copy");
void reject(void*, u32)           IMPORT("ic0", "msg_reject");
u32 arg_size(void)                IMPORT("ic0", "msg_arg_data_size");
void arg_copy(void*, u32, u32)    IMPORT("ic0", "msg_arg_data_copy");
u32 call_perform()                IMPORT("ic0", "call_perform");
void call_append(void*, u32)      IMPORT("ic0", "call_data_append");
void call_new(void*, u32, void*, u32, u32, u32, u32, u32)
    IMPORT("ic0", "call_new");

u32 reject_code() IMPORT("ic0", "msg_reject_code");
u32 reject_msg_size() IMPORT("ic0", "msg_reject_msg_size");
void reject_msg_copy(void*, u32, u32) IMPORT("ic0", "msg_reject_msg_copy");

void debug_print(void*, u32)      IMPORT("ic0", "debug_print");

void err() {
  char msg[] = "TODO: better error messages";
  reject(msg, sizeof(msg) - 1);
}

enum {
  PRINCIPAL_MAX = 32,
  CONTROLLERS_MAX = 10,
  CONTROLLERS_BUF_MAX = CONTROLLERS_MAX * PRINCIPAL_MAX + 8,
  LOTS_MAX = 128,
  ACCOUNT_MAX = 128,
};

u8 hexit(u8 n) { return n < 10 ? n + '0' : n - 10 + 'a'; }

u32 crc(u8 *p, u32 n) {
  static u32 table[256], ready, c;
  if (!ready) {
    for(u32 i = 0; i < 256; i++) {
      c = i;
      for(u32 j = 8; j; j--) c = (c>>1)^((c&1)*0xedb88320);
      table[i] = c;
    }
    ready = 1;
  }
  c = ~0;
  for(u32 i = 0; i < n; i++) c = (c >> 8) ^ table[p[i] ^ (c & 0xff)];
  return ~c;
}

u8 unhexit(char c) { return c <= '9' ? c - '0' : 10 + (c <= 'F' ? c - 'A' : c - 'a'); }
void call_append_hex(char *s) {
  u8 single[1];
  while (*s) {
    *single = unhexit(*s++) * 16;
    *single += unhexit(*s++);
    call_append(single, 1);
  }
}

void call_append_u64(u64 n) {
  u8 single[1];
  for (u32 i = 8; i; i--) {
    *single = n;
    call_append(single, 1);
    n >>= 8;
  }
}

void reply_append_u8(u8 c) {
  u8 single[1];
  *single = c;
  reply_append(single, 1);
}

void reply_append_u64(u64 n) {
  for (u32 i = 8; i; i--) {
    reply_append_u8(n);
    n >>= 8;
  }
}

void reply_append_hex(char *s) {
  while (*s) {
    u8 n = unhexit(*s++) * 16;
    n += unhexit(*s++);
    reply_append_u8(n);
  }
}

static u8 arg_read(u32 cursor) {
  u8 single[1];
  arg_copy(single, cursor, 1);
  return *single;
}

void map_leb128(void(*f)(void*, u32), u32 n) {
  u8 single[1];
  do {
    *single = n & 127;
    n >>= 7;
    if (n) *single |= 128;
    f(single, 1);
  } while(n);
}

void call_append_leb128(u32 n) { map_leb128(call_append, n); }
void reply_append_leb128(u32 n) { map_leb128(reply_append, n); }

u8 caller[PRINCIPAL_MAX];
u8 alice[32];
u8 escrow[32];
u8 md[SHA224HashSize];
SHA224Context ctx[1];
static u8 scratch[32768];

// Production ledger ID.
// u8 ledger[] = "\x00\x00\x00\x00\x00\x00\x00\x02\x01\x01";
u8 ledger[] = "\x00\x00\x00\x00\x00\x00\x00\x01\x01\x01";
u32 ledger_len = sizeof(ledger) - 1;

void compute_account(u8 *acct, u8 *id, u32 id_size, u8 *sub) {
  u8 buf[128] = "\naccount-id";
  u8 *p = buf + 11;
  for (u32 i = id_size; i; i--) *p++ = *id++;
  for (u32 i = 32; i; i--) *p++ = *sub++;
  SHA224Reset(ctx);
  SHA224Input(ctx, buf, p - buf);
  SHA224Result(ctx, acct + 4);
  u32 n = crc(acct + 4, SHA224HashSize);
  for (int i = 3; i >= 0; i--) *acct++ = n >> (8*i);
}

u8 zero32[32];

void account_id() EXPORT("canister_query account_id");
void account_id() {
  u32 n = caller_size();
  caller_copy(scratch, 0, n);
  compute_account(alice, scratch, n, zero32);

  n = self_size();
  self_copy(scratch, 0, n);
  compute_account(escrow, scratch, n, alice);

  reply_append("DIDL\0\x01\x71\x40", 8);  // Reply is text (0x71) of length 64.
  for (u32 i = 0; i < 32; i++) {
    u8 single[1];
    *single = hexit(escrow[i] / 16);
    reply_append(single, 1);
    *single = hexit(escrow[i] % 16);
    reply_append(single, 1);
  }
  reply();
}

static u32 locked;

void unlock(u32 whatever) {
  locked = 0;
}

static void withdraw3(u32 whatever) {
  locked = 0;
}

static void withdraw2(u32 whatever) {
  locked = 0;
  candy(arg_read);
  seek(0);
  u64 amount = read_u64(&the_value);
  // Amount must exceed the transaction fee.
  if (amount <= 10000) return;
  amount -= 10000;
  call_new(ledger, ledger_len, "transfer", 8, (u32) withdraw3, 1234, (u32) unlock, 5678);
  // record { memo = nat64 0 ; amount = record { e8s = nat64 $AMT } ; fee = record { e8s = nat64 10000 } ; to = blob $TGT ; from_subaccount = opt blob $SUB }
  // 4449444c046d7b6c01e0a9b302786e006c05fbca0100c6fcb60201ba89e5c20478a2de94eb0602d8a38ca80d010103"$TGT"10270000000000000000000000000000"$SUB""$AMT"
  call_append_hex("4449444c046d7b6c01e0a9b302786e006c05fbca0100c6fcb60201ba89e5c20478a2de94eb0602d8a38ca80d010103" "20");
  call_append(alice, 32);
  call_append_hex("10270000000000000000000000000000" "0120");
  call_append(alice, 32);
  call_append_u64(amount);
  if (call_perform()) return;
  locked = 1;
}

void withdraw() EXPORT("canister_update withdraw");
void withdraw() {
  if (locked) {
    reply_append("DIDL\0\0", 6);
    reply();
    return;
  }
  u32 n = caller_size();
  caller_copy(scratch, 0, n);
  compute_account(alice, scratch, n, zero32);
  n = self_size();
  self_copy(scratch, 0, n);
  compute_account(escrow, scratch, n, alice);
  // record { account = blob $ACCOUNT }
  // 4449444c026d7b6c01adf9e78a0a000101"$ACCOUNT"
  call_new(ledger, ledger_len, "account_balance", 15, (u32) withdraw2, 1234, (u32) unlock, 5678);
  call_append_hex("4449444c026d7b6c01adf9e78a0a000101" "20");
  call_append(escrow, 32);
  if (call_perform()) return err();
  locked = 1;
  reply_append("DIDL\0\0", 6);
  reply();
}

static u64 deal_counter;

// Map of canister ID to original controllers and current price.
struct lot_s {
  u64 deal_id;
  u32 id_size;
  u8 id[PRINCIPAL_MAX];
  u64 price;

  u32 seller_size;
  u8 seller[ACCOUNT_MAX];
  u32 controllers_size;
  u8 controllers[CONTROLLERS_BUF_MAX];
};
typedef struct lot_s lot_t[1];
typedef struct lot_s *lot_ptr;

static struct lot_s lots[LOTS_MAX];
static u32 lot_count;

void post3(u32 whatever) {
  locked = 0;
  lot_ptr p = lots + lot_count;
  p->deal_id = deal_counter++;
  lot_count++;
}

void post2(u32 whatever) {
  locked = 0;
  candy(arg_read);
  seek(0);
  if (descend(2336062691)) return;  // settings
  if (descend(570880087)) return;  // controllers
  lot_ptr p = lots + lot_count;
  u32 start = the_value;
  u32 count = unleb128(&the_value);
  if (count > CONTROLLERS_MAX) return;
  u32 found = 0;
  for (u32 i = 0; i < count; i++) {
    if (read(&the_value) != 1) return;
    u32 n = unleb128(&the_value);  // length
    if (!found && n == p->seller_size) {
      u8 buf[PRINCIPAL_MAX];
      arg_copy(buf, the_value, n);
      if (!memcmp(p->seller, buf, n)) found++;
    }
    the_value += n;
  }
  if (!found) return;
  p->controllers_size = the_value - start;
  if (p->controllers_size > CONTROLLERS_BUF_MAX) return;
  arg_copy(p->controllers, start, p->controllers_size);

  call_new("", 0, "update_settings", 15, (u32) post3, 65, (u32) unlock, 66);
  // record { canister_id = principal $A; settings = record { controllers = opt vec principal $B } }
  // 4449444c046d686e006c01d7e09b9002016c02b3c4b1f20468e3f9f5d908020103"$A""$B"
  call_append_hex("4449444c046d686e006c01d7e09b9002016c02b3c4b1f20468e3f9f5d908020103" "01");
  call_append_leb128(p->id_size);
  call_append(p->id, p->id_size);
  call_append_hex("010101");
  u32 n = self_size();
  self_copy(scratch, 0, n);
  call_append_leb128(n);
  call_append(scratch, n);
  if (call_perform()) return;
  locked = 1;
}

void post() EXPORT("canister_update post");
void post() {
  if (locked) {
    reply_append("DIDL\0\0", 6);
    reply();
    return;
  }
  lot_ptr p = lots + lot_count;
  candy(arg_read);
  seek(0);
  if (descend(3364572809)) return err();  // price
  p->price = read_u64(&the_value);
  seek(0);
  if (descend(1313628723)) return err();  // canister_id
  the_value++;
  p->id_size = unleb128(&the_value);
  p->seller_size = caller_size();
  caller_copy(p->seller, 0, p->seller_size);

  // record {canister_id = principal $A}
  // 4449444c016c01b3c4b1f204680100"$A"
  call_new("", 0, "canister_status", 15, (u32) post2, 65, (u32) unlock, 66);
  call_append_hex("4449444c016c01b3c4b1f204680100" "01");

  call_append_leb128(p->id_size);
  arg_copy(p->id, the_value, p->id_size);
  call_append(p->id, p->id_size);
  if (call_perform()) return err();
  locked = 1;
  reply_append("DIDL\0\0", 6);
  reply();
}

static lot_ptr locked_lot;

void unpost2(u32 whatever) {
  lot_count--;
  if (lot_count) memcpy(locked_lot, lots + lot_count, sizeof(struct lot_s));
  locked = 0;
}

static u8* buf_start;
static u32 buf_sz;
static u8 buf_read_at(u32 i) {
  return buf_start[i];
}
static void buf_read_init(void* start, u32 sz) {
  buf_start = start;
  buf_sz = sz;
  set_read_at(buf_read_at);
}

void unpost() EXPORT("canister_update unpost");
void unpost() {
  if (locked) {
    reply_append("DIDL\0\0", 6);
    reply();
    return;
  }
  u32 n = caller_size();
  caller_copy(caller, 0, n);
  candy(arg_read);
  seek(0);
  u64 deal = read_u64(&the_value);
  u32 lot_found;
  for (lot_found = 0; lot_found < lot_count; lot_found++) {
    locked_lot = lots + lot_found;
    if (locked_lot->deal_id == deal) {

      buf_read_init(locked_lot->controllers, locked_lot->controllers_size);
      u32 buf_i = 0;
      u32 count = unleb128(&buf_i);
      u32 i;
      for (i = 0; i < count; i++) {
        buf_i++;
        u32 m = unleb128(&buf_i);  // length
        if (m == n && !memcmp(caller, buf_start + buf_i, m)) break;
        buf_i += m;
      }
      if (i == count) return err();
      break;
    }
  }
  if (lot_found == lot_count) return err();

  call_new("", 0, "update_settings", 15, (u32) unpost2, 67, (u32) unlock, 68);
  // record { canister_id = principal $A; settings = record { controllers = opt vec principal $B } }
  // 4449444c046d686e006c01d7e09b9002016c02b3c4b1f20468e3f9f5d908020103"$A""$B"
  call_append_hex("4449444c046d686e006c01d7e09b9002016c02b3c4b1f20468e3f9f5d908020103" "01");
  call_append_leb128(locked_lot->id_size);
  call_append(locked_lot->id, locked_lot->id_size);
  call_append_hex("01");
  call_append(locked_lot->controllers, locked_lot->controllers_size);

  if (call_perform()) return err();
  locked = 1;
  reply_append("DIDL\0\0", 6);
  reply();
  return;
}

/* Rebel Candid:
vec { record {
  lot = nat64 $INDEX;
  canister_id = principal $ID;
  price = nat64 $PRICE;
  seller = principal $SELLER;
  controllers = vec principal $CONTROLLERS
} }
*/
void catalog() EXPORT("canister_query catalog");
void catalog() {
  reply_append_hex("4449444c036d686c0591a9c90278d7e09b900200b3c4b1f20468ffd8e1d10668899dadc40c786d010102");
  reply_append_leb128(lot_count);
  for (lot_ptr p = lots; p < lots + lot_count; p++) {
    reply_append_u64(p->deal_id);
    reply_append(p->controllers, p->controllers_size);
    reply_append_u8(1);
    reply_append_leb128(p->id_size);
    reply_append(p->id, p->id_size);
    reply_append_u8(1);
    reply_append_leb128(p->seller_size);
    reply_append(p->seller, p->seller_size);
    reply_append_u64(p->price);
  }
  reply();
}

static u8 buyer[PRINCIPAL_MAX];
static u32 buyer_size;

void buy3(u32 whatever) {
  locked = 0;
}

void buy2(u32 whatever) {
  locked = 0;
  candy(arg_read);
  seek(0);
  u32 n = unleb128(&the_value);
  if (n != 0) return;  // Abort on failed transfer.
  lot_ptr p = locked_lot;
  lot_count--;
  if (lot_count) memcpy(p, lots + lot_count, sizeof(struct lot_s));
  call_new("", 0, "update_settings", 15, (u32) buy3, 67, (u32) unlock, 68);
  // record { canister_id = principal $A; settings = record { controllers = opt vec principal $B } }
  // 4449444c046d686e006c01d7e09b9002016c02b3c4b1f20468e3f9f5d908020103"$A""$B"
  call_append_hex("4449444c046d686e006c01d7e09b9002016c02b3c4b1f20468e3f9f5d908020103" "01");
  call_append_leb128(p->id_size);
  call_append(p->id, p->id_size);
  call_append_hex("010101");
  call_append_leb128(buyer_size);
  call_append(buyer, buyer_size);
  if (call_perform()) return;
  locked = 1;
}

void buy() EXPORT("canister_update buy");
void buy() {
  if (locked) {
    reply_append("DIDL\0\0", 6);
    reply();
    return;
  }
  candy(arg_read);
  seek(0);
  u64 deal = read_u64(&the_value);
  buyer_size = caller_size();
  caller_copy(buyer, 0, buyer_size);

  for (lot_ptr p = lots; p < lots + lot_count; p++) {
    if (p->deal_id == deal) {
      locked_lot = p;
      u64 amount = p->price;
      call_new(ledger, ledger_len, "transfer", 8, (u32) buy2, 1234, (u32) unlock, 5678);
      // record { memo = nat64 0 ; amount = record { e8s = nat64 $AMT } ; fee = record { e8s = nat64 10000 } ; to = blob $TGT ; from_subaccount = opt blob $SUB }
      // 4449444c046d7b6c01e0a9b302786e006c05fbca0100c6fcb60201ba89e5c20478a2de94eb0602d8a38ca80d010103"$TGT"10270000000000000000000000000000"$SUB""$AMT"
      call_append_hex("4449444c046d7b6c01e0a9b302786e006c05fbca0100c6fcb60201ba89e5c20478a2de94eb0602d8a38ca80d010103" "20");
      compute_account(scratch, p->seller, p->seller_size, zero32);
      call_append(scratch, 32);
      call_append_hex("10270000000000000000000000000000" "0120");

      compute_account(alice, buyer, buyer_size, zero32);
      call_append(alice, 32);
      call_append_u64(amount);
      if (call_perform()) return err();
      locked = 1;
      reply_append("DIDL\0\0", 6);
      reply();
      return;
    }
  }
  return err();
}

Testing

We create a bunch of identities:

dfx identity new minter
dfx identity new alice
dfx identity new bob

In a new subdirectory, and fetch the ledger canister:

export IC_VERSION=dd3a710b03bd3ae10368a91b255571d012d1ec2f
curl -o ledger.wasm.gz https://download.dfinity.systems/ic/${IC_VERSION}/canisters/ledger-canister_notify-method.wasm.gz
gunzip ledger.wasm.gz

Copy market.wasm and hello.wasm to this directory, setup dfx.json, and start a replica:

touch nothing
cat > dfx.json << EOF
{"canisters":
  {"ledger":{"type":"custom","candid":"nothing","wasm":"ledger.wasm"},
  "market":{"type":"custom","candid":"market.did","wasm":"market.wasm"},
  "hello":{"type":"custom","candid":"nothing","wasm":"hello.wasm"}
}}
EOF
dfx start

Start another terminal. Thanks to our Rebel Candid tool, we can deploy the ledger without downloading any Candid interface files. We feed a template of the initial ledger argument to rebel to encode the message for us:

echo 'record {minting_account = text $MINT_ACC; initial_values = vec { record { text $ALICE_ACC; record { e8s=nat64 100_000_000_000 } } }; send_whitelist = vec principal {}}' | rebel

Unlike other canisters, the ledger initialization argument expects account IDs to be written in hexdecimal in text fields! As we’re crafting a raw message, we must hex-encode this text a second time, and also prepend each account ID with 0x40, the length of each text field.

dfx identity use minter
MINT_ACC=$(echo -n 40; echo -n $(dfx ledger account-id) | basenc --base16 -w0)
dfx identity use alice
ALICE_ACC=$(echo -n 40; echo -n $(dfx ledger account-id) | basenc --base16 -w0)
dfx deploy ledger --argument-type raw --argument 4449444c056d686c01e0a9b302786c02007101016d026c0390c5a3a90100aecbeb880471fdbacfcc0d03010400"$MINT_ACC"01"$ALICE_ACC"00e8764817000000

Alice now has 1000 ICP:

LEDGER=$(grep -A1 ledger .dfx/local/canister_ids.json | sed -n '/local/p' | sed 's/.*"\([^"]*\)"$/\1/')
dfx ledger balance --ledger-canister-id $LEDGER

Alice deploys the market canister, and transfers 42 ICP to her escrow account:

dfx deploy market
dfx ledger transfer --ledger-canister-id $LEDGER $(dfx canister call market account_id | grep -o '[a-z0-9]*') --amount 42 --memo 0

Now Bob deploys a canister, and puts it up for sale by adding the market canister as a controller, then calling the post method. The price is 12.34 ICP.

dfx identity use bob
dfx deploy hello
HELLO=$(grep -A1 hello .dfx/local/canister_ids.json | sed -n '/local/p' | sed 's/.*"\([^"]*\)"$/\1/')
MARKET=$(grep -A1 market .dfx/local/canister_ids.json | sed -n '/local/p' | sed 's/.*"\([^"]*\)"$/\1/')
dfx canister update-settings --add-controller $MARKET hello
dfx canister call market post --type raw $(echo 'record { canister_id = principal "'$HELLO'"; price = nat64 1_234_000_000 }' | rebel)

The market’s catalog query now features Bob’s canister:

dfx canister call market catalog

Alice buys Bob’s canister:

dfx identity use alice
dfx canister call market buy --type raw $(echo nat64 0 | rebel)

Alice confirms she now owns the hello canister. She withdraws the rest of her money from her escrow account. She confirms her balance is 1000 - 12.34 minus some transaction fees:

dfx canister info hello
dfx canister call market withdraw
dfx ledger balance --ledger-canister-id $LEDGER

Bob also confirms he was paid:

dfx identity use bob
dfx ledger balance --ledger-canister-id $LEDGER

Further work

To bound memory use, and to keep catalog cheap enough to be a query method, we bound the number of catalog entries. A malicious person could fill the catalog with junk, making this canister useless. To mitigate this, we could require Bob to pay or provide a refundable deposit when listing an entry. We might also expire older entries. Perhaps a simple but effective scheme is to automatically unpost the oldest the entry when a posting to a full catalog.

We ought to provide freeze and unfreeze methods, which only the controller of the market canister can call. When frozen, the methods post, buy, and unpost do nothing and return immediately.

Then to upgrade the market canister, we would freeze it first, then call catalog to record the current deals. Then we could either implement an controller-only unpost_all method that restores all listed canisters to their original controllers, or a controller-only append_catalog, in which case we start the upgraded market canister in a frozen state, and add back the existing deals before unfreezing.

An alternative may be a layer of indirection: we split off the tricky parts into a backend canister that is controlled by the frontend market canister.


💡