colored_coins_intro

Manuel Aráoz edited this page Nov 1, 2013 · 10 revisions

The theory of colored coins

Overview

Colored coins is a concept which allows one to associate additional properties with transaction outputs ("coins") in context of Bitcoin-like blockchain. This can be used to represent ownership of external objects within the blockchain (similar to Bitcoin Smart Property concept), and, particularly, it can be used for issuance of securities (such as stocks and bonds), private currencies, etc.

When a transaction output which has additional properties associated with it is spent in a transaction, these properties might be transferred to outputs of that transaction. A special set of rules (color kernel, see below) is used to determine whether and how this transfer happens.

Thus, we can assume that a party which is able to spend a transaction output which has an additional property associated with it is the current owner of that property, and when he spends that transaction output he transfers ownership of that property to a different party.

Formal definition

(Please note that "colored coins" is not a particular technology, it is a concept which can be applied to any particular technology based on ideas mentioned in the "overview" section.)

Color associates certain additional properties with transaction outputs from a particular blockchain/transaction graph. This additional property is called colorvalue. Each output of each valid transaction has a certain permanent colorvalue.

In other words, we can define colorvalue as a function of two parameters: transaction output txout and color Q. Function is defined for a particular pair of txout and Q if txout identifies an output of a transaction which is valid in blockchain B, and color Q is defined for a blockchain B.

Example: Suppose Issuer defined color gold for Bitcoin blockchain. He associates a certain contract with that color, for example, he might offer redemption for physical gold. (Redemption procedure will be described below.) Thus this color gold has a certain meaning now: if txout is an unspent transaction output within the Bitcoin blockchain and colorvalue(txout, gold) = x, then Issuer owes x grams of gold to a party which controls txout.

Color is defined using a color kernel function, which is applied to each transaction independently. Output of this function depends only on a transaction which is being considered and colorvalues of inputs of this transaction. I.e.

CK: (tx, tx_in_cvalues)->tx_out_cvalues

where CK is a color kernel, tx is a particular transaction, tx_in_cvalues is a vector of colorvalues of outputs references by transaction's inputs, and tx_out_cvalues is a vector of colorvalues of transaction's outputs.

(Note: This is similar to Bitcoin transaction validation: to check whether transaction is valid we only need to check that all of its inputs are valid, and that transaction itself is well-formed, has correct scripts and generally follows the rules. It cannot be influenced by transactions it doesn't depend on.)

Since we cannot obtain colorvalue of an input of coinbase transaction, we assume that it has special null color value. We can compute colorvalues for all transaction outputs in a certain transaction graph by applying color kernel to each transaction in that graph.

Parametrized color kernels

Of course, it would be useful to introduce some scheme which would allow anyone to create as many colors as he needs. To do this, we will define parametrized color kernels: concrete color kernel for a concrete color will be obtained when one provides all necessary parameters.

Typically, a genesis transaction output serves as a parameter: that is, colored coins will be "injected" into a blockchain via a particular transaction output, and from that point they can be further transferred and distributed. Usually we call this act 'issuance', and a party which performs it is an issuer. (It is similar to issuance of securities.)

Order-based coloring

One example of a parametrized color kernel is order-based coloring. To find colorvalue of an output, we first need to identify a set of inputs which match it. To do this, we represent each input and output as a segment on a line.

Input i is represented by a segment [a(i), b(i)] which starts where previous input's segment ends: a(i) = b(i-1) and its length equals its value: b(i) - a(i) = value(i). For the first input, a(0) = 0, i.e. it starts at origin.

In a same way, output j is represented by a segment [c(j), d(j)], which starts where previous output's segment ends.

Now we can defined that input i matches output j if their segments overlap.

If all inputs which match output j have non-null colorvalues, then output j has colorvalue which equals its value in satoshi. Otherwise, it has null colorvalue.

Order-based coloring is simple and straightforward, but it has certain disadvantages. First, we need transaction outputs with small amounts of satoshis in them to represent small colorvalues, but such outputs are currently discouraged by Bitcoin nodes as they can be used to create large amounts of unspent transaction outputs ("dust") which can strain nodes' resources.

Second problem is that it isn't possible to identify outputs which potentially have non-null colorvalues by considering a transaction in isolation, and for this reason thin clients which use backward scan to find colorvalues have to do this scan for uncolored outputs (ones having null colorstate), which can be very computationally expensive.

For this reason, we introduce padded order-based coloring parametrized color kernel.

Padded order-based coloring

To avoid problems with small-valued outputs, we can "pad" them, i.e. we will define colorvalue to be equal (value - padding) where value is a satishi value of an output, and padding is a parameter which is defined for a color.

When padding is 0, we have simple order-based coloring (with an exception of more strict rules defined below). Setting padding to 10000 satoshi would allow us to avoid problems with existing anti-dust rules, as we won't have output values smaller than 10000.

We need to adjust rules to take padding into account.

First of all, if input/output has satoshi value (svalue) less or equal to padding, it is removed from consideration together with all subsequent inputs/outputs.

Input i is represented by a segment [a(i), b(i)] where a(0) = 0, a(i) = b(i-1), and b(i) = a(i) + svalue(i) - padding. In other words, length of a segment is svalue(i)-padding, which is equal to colorvalue of input i if it has non-null colorvalue.

Likewise, output j is represented by a segment [c(j), d(j)] which is constructed using a similar rule.

A sequence of outputs j, j+1, ..., j+n matches a sequence of inputs i, i+1, ..., i+m if a(i) = c(j) and b(i + m) = d(j + n); that is, segment which is spanned by a sequence of outputs is same as a segment which is spanned by a sequence of inputs.

If all inputs within this sequence have non-null colorvalues, then each output in a sequence has colorvalue which equals svalue(j) - padding for output j.

Let's consider an example:

Input svalues: [10001, 10002, 10003, 75555]
Output svalues: [10001, 10005, 65555] 
           (10000 satoshi went into a fee)
Input segments: [ [0, 1], [1, 3], [3, 6], [6, 65561] ]
Output segments: [ [0, 1], [1, 6], [6, 55561] ]
Input colorvalues: [null, 2, 3, null]
Output colorvalues: [null, 5, null]

Second output is matched by a sequence of second and third outputs, as they occupy segment [1, 5]. As both inputs have non-null colorvalues, second output has non-null colorvalue which equals 5.

Now we can specify how this parametrized color kernel computes output colorvalues:

  1. If transaction is a genesis transaction, all outputs except genesis output have null colorvalue, while genesis transaction output j has colorvalue which equals svalue(j) - padding.
  2. Otherwise, if all transaction inputs have null colorvalues, all outputs have null colorvalues.
  3. Otherwise, it checks whether all inputs with non-null colorvalue are adjacent. If they aren't, we abort the process: all outputs are assigned null colorvalues.
  4. Otherwise, we find a sequence of inputs which has all inputs with non-null colorvalues and no inputs with null colorvalues. Then we check if there is a sequence of outputs matching it. If there is one, all outputs in this sequence get colorvalue which equals svalue(j) - padding for output j, while all other outputs get null colorvalue.
  5. Otherwise, if matching output sequence doesn't exist, all outputs get null colorvalue.

In other words, outputs are colored only if transaction is well-formed, i.e. all colored inputs are adjacent and colored outputs match them exactly. Otherwise, we abort the process and colored coins get destroyed.

Rationale for this strict validation is following:

  1. Colorvalues are computed via a simple and straightforward process, so we can expect that all colored coin clients will implement it correctly, which is crucial.
  2. We believe that it is better to destroy colored coins which were used in a malformed transaction than to recover some of them: when colored coins are destroyed, issuer can identify the last legitimate owner and send him replacement coins, or pay a compensation (if contract demands this). Malformed transaction could have sent coins to a wrong party, and it might be impossible to recover them from it.
  3. Client can check whether transaction is well-formed right before publishing it on network, and this extra validation can prevent loss of colored coins due to potential bugs in client implementation.
  4. Most Bitcoin transactions which do not involve colored coins will have no matching input/output sequences, thus thin clients can abort backward scan as soon as they discover such transactions.