the theory of colored coins

[killerstorm]

(This is based on an article which I posted on colored coins mailing list back in June. Since colored coins are mentioned here fairly frequently, it would help if settle on a concrete terminology, and so I'm posting it here.)

EDIT: A more rigorous definition which uses slightly different terminology: https://github.com/bitcoinx/colored-coin-tools/wiki/colored_coins_intro

Previously we were associating term "colored coins" with a concrete protocol/algorithm, called "order-based coloring". Sadly, it had certain deficiencies, especially after anti-dust patch made it impossible to send tiny amounts of coins, and for this reason we decided against standardizing on it.

Instead, I decided to generalize the concept; so "colored coins" is a concept now, not a particular technology. So what is it, exactly?

The core idea is this:

• we are going to associate a property or a set of properties with transaction outputs
• this property can be transferred when these transaction outputs are spent in a transaction, i.e. outputs of this transaction can somehow inherit properties of inputs

So the characteristic trait of 'colored coins' concept is that it uses Bitcoin transaction graph and works on 'transaction output' level.

Let's formalize this:

• color associates color states with transaction outputs, e.g. color X associates color state Y with transaction output Z. Perhaps we can write it down as X(Z)=Y
• color can't be an arbitrary function, it must be defined in terms of coloring kernel, which is a function which can be applied to each transaction in isolation
• coloring kernel is a function which gets a particular transaction and color states of all of its inputs as parameters, and yields color state for each transaction output. Basically, coloring kernel "colors" outputs
• we can apply coloring kernel to each transaction in a blockchain, and if it is deterministic, a certain color state will be deterministically associated with each transaction output in the blockchain
• this also applies to transactions in mempool: if transaction isn't orphan, color states of its outputs can be computed, and they won't change in future

"Order-based coloring" is a kind of a coloring kernel: you get specific coloring kernel when you combine genesis of a color with an order-based coloring algorithm. (In other words, a generic coloring function which performs order based coloring is parametrized by genesis transaction output; and when color's genesis transaction output is provided you get the concrete coloring function for this particular color.)

You can find an implementation of this coloring kernel here (Python): https://github.com/bitcoinx/coloredcoinlib/blob/master/colordef.py#L24

Smart Property protocol which was described by Mike Hearn here: https://en.bitcoin.it/wiki/Smart_Property#Theory
fits into this new colored coin model. And so do many other things which are based on it, e.g. bonds which are marked with a special transaction scripts (see here: https://en.bitcoin.it/wiki/Distributed_markets).

However, Mastercoin doesn't fit into colored coins model, for two reasons:

• it associates balances with addresses, not with transaction outputs
• it uses non-local state transitions. It is sensitive to order, i.e. even if you have exactly same transactions, but they are in a different order, you can get a very different state.

Mastercoin can only be described in terms of a more general model, and it can implement features which cannot be implemented within colored coin model. But since it doesn't make use of Bitcoin transaction graph, it is no longer protected with mechanism which prevent double-spends. I.e. we cannot say anything conclusive about Mastercoin transactions which are still in memory pool, state is fixed only if is buried in the blockchain.

OK, well, so why do we care about a formal model for colored coins?

As it turns out, coloring kernel can be separate from other aspects of colored coin implementation (such as blockchain traversal, for example). Thus we can create a colored coin client which is able to work with several different kinds of kernels, and so compatibility problems are less pressing: to add support for a different kind of colored coins we simply need to include implementation of kernel and implementation of send function.

We can also develop coloring kernels for specific purposes: we are no longer limited to a simple rule of conservation. We can implement advanced kernels which can have interesting features like demurrage, taxation, built-in referral program etc. It is also possible to design them specifically for use in derivative and prediction markets.

(In other news, I believe it is possible to create a fully decentralized prediction market. It is fairly hairy and relies on assumptions of economic nature, e.g. rationality of actors. But as far as I can tell, it is actually viable. Consequences will never be the same.)

[1715324622]

1715324622

[1715324622]

1715324622

[killerstorm]

.

[gendal]

0.2 BTC bounty goes to someone who

• understands what I have written above
• has better science/tech writing skills than me
• will rewrite the main part of this article, putting it in better words

For what it's worth, I think this article is very clear as-is.  I think it could be improved by including answers/commentary on the following topics:

1) Include a worked example.  This would be particularly useful as it would help show why it is necessary to distinguish between "color" and "color state"

2) Discuss how you anticipate the kernels working in practice.  In the most decentralised example, one can imagine that a particular kernel might only exist in the client of an issuer of a particular color (associated with that kernel) and in the client of any recipients of coins with that color... or at least those recipients who were expecting to receive such a color.   Distribution of the kernels in such a case would make for an interesting discussion. It would also be interesting to highlight that the beauty of this system is that most Bitcoin users could be completely unaware that some coins were colored - only those with a need to know would know.

3) Discuss the economics/incentives surrounding coloring.  Absent a centralised "registry" of colors, most people, most of the time, will not know that a particular output is colored.  Should they be the recipient of a transaction that uses one of these outputs as its input, they may not even realise that they are holding something of value well in excess of its nominal BTC value.   If there was some sort of "registry" of colors, their client could alert them to this... but, in general,   a recipient wouldn't know.    Now this is probably not a problem in reality since why would somebody *send* something of value unless they received something of comparable value in exchange?   But it might be interesting to explore the extent to which a generic client could alert a user that an output was colored, even if the associated kernel was not available.

[watson145]

Dude you have superb knowledge thanks for post this article here.Thumbs up for you.

[socrates1024]

I like this approach. Maybe it will help to relate how colored coins generalize existing concepts in Bitcoin.

Transaction validation is analogous to the colored kernel. Transaction validation is a function of the blockchain history, however it's not an arbitrary function - instead it's only necessary to check the UTXO index, which is much smaller than the blockchain and only contains unspent/active coins. Similarly, the color kernel can be said to depend only on a "color table", which associates a color state to unspent coins.

[gendal]

I like this approach. Maybe it will help to relate how colored coins generalize existing concepts in Bitcoin.

Transaction validation is analogous to the colored kernel. Transaction validation is a function of the blockchain history, however it's not an arbitrary function - instead it's only necessary to check the UTXO index, which is much smaller than the blockchain and only contains unspent/active coins. Similarly, the color kernel can be said to depend only on a "color table", which associates a color state to unspent coins.

That's a very interesting point.  As you say, one could model transaction validation as an example of a color kernel. However, it has the unusual (unique?) property that 1) this kernel is implemented by bitcoind and enforced by miners and 2) its execution depends only on information that can be derived from the blockchain.

In the general case of colored coins, some form of bootstrapping is required: somebody must assert that a particular coin (or, rather, output), that was not previously associated with a particular color, is now so associated. Moreover, this "somebody" must be identifiable: the value of any coloring is critically dependent on the extent to which others believe they will make good on any promises associated with the claim.  Moreover, in a decentralised world, the kernels would not, in general, be known to all participants in the network: so, by definition, they could not operate *on* the blockchain (e.g. by providing a verification role).

Perhaps this distinction doesn't matter but it could help work through various scenarios... i.e. distinctions between kernels that require bootstrapping/external information and those that don't, distinctions between kernels that depend/provide blockchain verification function and those that don't, etc, etc.

[killerstorm]

I've improved(?) this a bit: https://github.com/bitcoinx/colored-coin-tools/wiki/colored_coins_intro

[mccoyspace]

I've written a post about an application I'm thinking about (establishing ownership of digital artworks)
https://bitcointalk.org/index.php?topic=317090.0

reading more about colored coins suggests to me that it is the right tool for the job.
My question is how far along is this project? Does useable software exist?
How do I learn how to use the system?

[killerstorm]

reading more about colored coins suggests to me that it is the right tool for the job.
My question is how far along is this project? Does useable software exist?
How do I learn how to use the system?

There are several incomplete implementations. Currently our flagship implementation, NGCCC, is probably too heavyweight for this kind of stuff.

On the other hand, a web client called WebcoinX might be OK. As it is web based, it is relatively easy to tweak user interface for a particular cause.

However, while it works on testnet, there are many problems which prevent it from working properly on mainnet.

Unfortunately fixing all this crap is fairly hard, and we decided to prioritize development of NGCCC. But if we'll be able to return to WebcoinX, it would take about a month to make a usable version.

Meanwhile, you can try a testnet version of WebcoinX: http://bitcoinx.github.io/webcoinx/

Or this short python script if you want command-line: https://bitcointalk.org/index.php?topic=117630.0

It lacks 'decentralized exchange' aspect, but if you just want to send coins around, it might work.

[FrictionlessCoin]

reading more about colored coins suggests to me that it is the right tool for the job.
My question is how far along is this project? Does useable software exist?
How do I learn how to use the system?

There are several incomplete implementations. Currently our flagship implementation, NGCCC, is probably too heavyweight for this kind of stuff.

On the other hand, a web client called WebcoinX might be OK. As it is web based, it is relatively easy to tweak user interface for a particular cause.

However, while it works on testnet, there are many problems which prevent it from working properly on mainnet.

What are the problems with WebcoinX?  Is it due to not using bitcoind?

[FrictionlessCoin]

reading more about colored coins suggests to me that it is the right tool for the job.
My question is how far along is this project? Does useable software exist?
How do I learn how to use the system?

There are several incomplete implementations. Currently our flagship implementation, NGCCC, is probably too heavyweight for this kind of stuff.

Doesn't proof of bits also have an implementation?

[FrictionlessCoin]

I like this approach. Maybe it will help to relate how colored coins generalize existing concepts in Bitcoin.

Transaction validation is analogous to the colored kernel. Transaction validation is a function of the blockchain history, however it's not an arbitrary function - instead it's only necessary to check the UTXO index, which is much smaller than the blockchain and only contains unspent/active coins. Similarly, the color kernel can be said to depend only on a "color table", which associates a color state to unspent coins.

That's a very interesting point.  As you say, one could model transaction validation as an example of a color kernel. However, it has the unusual (unique?) property that 1) this kernel is implemented by bitcoind and enforced by miners and 2) its execution depends only on information that can be derived from the blockchain.

In the general case of colored coins, some form of bootstrapping is required: somebody must assert that a particular coin (or, rather, output), that was not previously associated with a particular color, is now so associated. Moreover, this "somebody" must be identifiable: the value of any coloring is critically dependent on the extent to which others believe they will make good on any promises associated with the claim.  Moreover, in a decentralised world, the kernels would not, in general, be known to all participants in the network: so, by definition, they could not operate *on* the blockchain (e.g. by providing a verification role).

Perhaps this distinction doesn't matter but it could help work through various scenarios... i.e. distinctions between kernels that require bootstrapping/external information and those that don't, distinctions between kernels that depend/provide blockchain verification function and those that don't, etc, etc.

What I don't understand is,  which actor executes the color kernel?   Do you envision the miners executing the color kernel?   Would that need an upgrade of the entire bitcoin network?

Will wallets with the recepient address execute the color kernel?

[killerstorm]

What I don't understand is,  which actor executes the color kernel?

Well, the point of executing color kernel is to find colorvalues... So each actor which is interested in finding colorvalues need to execute it, unless it can get colorvalues from trusted source. (E.g. via a cryptographic proof of some sort.)

Do you envision the miners executing the color kernel?

No, I see colored coins as an alternative to protocol changes. Having something on protocol level definitely has benefits, e.g. SPV (thin clients need very little information to verify payment), but it might be problematic:

1. hard fork is required (likely)
2. a problem in additional features might lead to consensus problems
3. changes are not compartmentalized
4. it's hard to add features, upgrade over time, etc. (again, hard fork is required)

But that's the theory... In practice, if you care about things like user currencies, securities and so on, they aren't that hard to implement, so a Bitcoin protocol upgrade (such as Freimarkets) is desirable.

Would that need an upgrade of the entire bitcoin network?

Yes... It is known as 'hard fork'.

Will wallets with the recepient address execute the color kernel?

Yes... Basically, when you see an incoming UTXO, you want to know its colorvalue, so you run the computation... But there are several different computation strategies, like pre-computing everything, or computing on demand only.

[FrictionlessCoin]

Yes... Basically, when you see an incoming UTXO, you want to know its colorvalue, so you run the computation... But there are several different computation strategies, like pre-computing everything, or computing on demand only.

Took a shower and realized the answer to my question.

The miners merely validate if the input transactions are more than the output transactions.

When the client sees the transaction that it targeted to its address, it can do what ever it needs to do to process that transaction. 

So the actual semantics of processing the transaction is decentralized.

Did I get that correct?

Further,  why does the whitepaper alternative coloring mechanisms?  Is there a preferred one?   Are we at this time saying that coloring will be preserved only if we use a compatible client?

[killerstorm]

Did I get that correct?

Yes.

Further,  why does the whitepaper alternative coloring mechanisms?  Is there a preferred one?

We haven't settled on the best one, so we need to consider several alternatives.

However, the point of this theoretic model is that multiple mechanisms can co-exist.

For the start we are most interested in one which simply follows the rule of conservation, as it has many uses. But there are other interesting applications, which will require custom color kernels. (One example is prediction/derivatives market.)

Are we at this time saying that coloring will be preserved only if we use a compatible client?

It's always the case... But, in practice, special 'color addresses' prevent potential incompatibility problems: each color has an identifier, hash of that identifier is embedded into the address in such a way that client can check if identifier matches. This means that if your client doesn't support color "green", you won't be able to produce an address for color "green", and thus nobody will send you "green" coins.

[FrictionlessCoin]

For the start we are most interested in one which simply follows the rule of conservation, as it has many uses. But there are other interesting applications, which will require custom color kernels. (One example is prediction/derivatives market.)

Could you expound a bit on how you would do derivatives?   I had some intuition that you could, but I have not worked out the details how you would be able to do this.

It's always the case... But, in practice, special 'color addresses' prevent potential incompatibility problems: each color has an identifier, hash of that identifier is embedded into the address in such a way that client can check if identifier matches. This means that if your client doesn't support color "green", you won't be able to produce an address for color "green", and thus nobody will send you "green" coins.

Are you saying that there you are embedding in the address creation mechanism a way to uniquely create a colored address?  I did not see this in the specification.

[bluemeanie1]

 Why Not Color Coins? problems, limitations, and criticisms of the Bitcoin Color Coins architecture.

 http://altchain.org/?q=content/why-not-color-coins-problems-limitations-and-criticisms-bitcoin-color-coins-architecture

 -bm

[killerstorm]

Could you expound a bit on how you would do derivatives?   I had some intuition that you could, but I have not worked out the details how you would be able to do this.

There are several different approaches here... The basic idea is that two parties enter a contract by signing a transaction of special form (with contract details encoded in OP_RETURN data, for example) together.

They can close it in two ways:

1. both of them agree on settlement payout
2. one of parties forces the settlement, referencing evidence of some sort in the transaction

In the later case, others can check if settlement is right.

There is also a more centralized variant: only some kind of authority can make a transaction with forced settlement.

Are you saying that there you are embedding in the address creation mechanism a way to uniquely create a colored address?

No, it's just a different format of addresses. Like <color_id>@<bitcoin_address>.

I did not see this in the specification.

The specification is incomplete.

If you mean the one written by Vitalik Buterin, it is pretty much completely unrelated to how it is actually implemented.

[killerstorm]

 Why Not Color Coins? problems, limitations, and criticisms of the Bitcoin Color Coins architecture.

 http://altchain.org/?q=content/why-not-color-coins-problems-limitations-and-criticisms-bitcoin-color-coins-architecture

Mastercoin and colored coins work in very different ways.

[FrictionlessCoin]

No, it's just a different format of addresses. Like <color_id>@<bitcoin_address>.

I did not see this in the specification.

The specification is incomplete.

If you mean the one written by Vitalik Buterin, it is pretty much completely unrelated to how it is actually implemented.

So are you saying that this new address form is placed inside the script?