Define coloring

alberthendriks edited this page Apr 26, 2013 · 1 revision

Initially, the following defining of coloring was proposed by Alex: https://github.com/bitcoinx/colored-coin-tools/blob/master/colors.md

Below is Albert's proposal, a modification of Alex's proposal.

The color defining

(The words "color definition" are not used here, because that is a subtitle in Alex's initial document).

Recursive colorSingle tracking

a transaction output is recognized as "having colorSingle X" when it can be unambiguously traced down to output X, where X specifies a certain output of a certain (possibly earlier) transaction. Note that a transaction output can have multiple colorSingles but is the genesis of exactly one colorSingle.

Formally: In a single transaction, a transaction output is of colorSingle X when all matching inputs are of colorSingle X. An input is of colorSingle X if the output it spends is of colorSingle X.

Thus to check wheter a transaction output is of colorSingle we can perform a recursive traversal of the transaction graph until we get to the transaction output which is of colorSingle X (the genesis of colorSingle X), or we get to a coinbase transaction (not being the genesis of X).

However, this is just a definition of colorSingle. Although a "colored coin client" could implement this recursive traversal literally, there is a variety of implementation strategies which offer different performance trade-offs.

For example, it is possible to scan blockchain sequentially (breadth-first) from the start, noting all colorSingles. It is possible because we can compute colorSingles for each individual transaction independently as long as we know input colorsSingles, and if we scan transactions sequentially we always know colors of inputs by the time transaction is considered.

Order-based coloring

The definition above left matching undefined. In order-based coloring inputs and outputs are matched according to the order they appear in transaction.

To visualize this matching, imagine that each input and output is represented with a box with height proportional to number of coins in that input/output. We stack this boxes on top of each other in same order they appear in transaction. To find a colorSingle of an output box you need to check colorSingles of input boxes which are on same height.

*----* *----*
| I1 | | O1 |
------ ------
| I2 | | O2 |
------ |    |
| I3 | |    |
*----* *----*

Output O1 is matched by input I1, while O2 is matched by I2 and I3.

If I2 and I3 are of same colorSingle, then O2 is of that colorSingle too. Otherwise O2 is uncolored.

Formal definition:

Preceding sum of input i is sum of values of all outputs from 0 below i. PS(input[i]) = sum(input[x].value, x=0..(i-1)) Preceding sum of output j is sum of values of all outputs from 0 below j. PS(output[j]) = sum(output[x].value, x=0..(j-1))

Input i matches output j when segments [PS(input[i]), PS(input[i])+input[i].value] and [PS(output[j]), PS(output[j])+output[j].value] overlap.

I.e. PS(input[i]) < PS(output[j])+output[j].value and PS(input[i])+input[i].value] > PS(output[j]).

If we want to compute the colorSingles of all outputs in a transaction, we can simply go through all outputs one by one, in order they appear in the transaction, and for each output 'eat' enough inputs to cover it. If all eaten inputs share the same colorSingle, then the output is of that colorSingle too. Otherwise the output does not have that colorSingle.

(Note that the inputs maybe do share another colorSingle, in which case the output would have that other colorSingle (or even more). In case none of this is true, the output only has its own colorSingle (because every output is the genesis of its own colorSingle by definition)).

We need to maintain three state variables during iteration over outputs:

i -- index of current input to be eaten
current_amount -- remaining sum in inputs eaten so far
colorSingles -- set of colorSingle of inputs we have eaten (this is not related to colorAsset).

To eat an input we increase current_amount, update colorSingles (intersect it with inputs eaten before), and increment i.

Once we have eaten enough inputs we can "color" an output (it has the colorSingles of the variable colorSingles plus its own colorSingle) and decrease current amount by value of that output. If current_amount is zero we reset colorSingles to U.

Here is a reference implementation if this algorithm (note this is the original algorithm by Alex, without the current modification): https://github.com/killerstorm/colored-coin-tools/blob/master/color.js

ColorAsset

Finally, we define a colorAsset, which is a set of colorSingle.

Differences

Technical

  • There are no "color definitions" (bottom of Alex's document)
  • For disambiguation, we don't use the word "color". Instead we use the words "colorSingle" and "colorAsset" (colorAsset resembles Alex's "color"). ColorAsset is simply defined as a set of colorSingle and the genesis of a colorSingle is defined as:
  • The transaction output of every transaction is a unique colorSingle.
  • Each colorSingle thus has exactly 1 genesis.
  • A transaction output has its own colorSingle and possibly other colorsSingles (which is the case if and only if mixing did not occur in that transaction for that output (&& the output is > 0)).
  • For example, in Albert's way, the output of a transaction might have multiple input all of the same colorAsset. But if they are of different colorSingle, these colorSingles will be lost because of mixing and therefore the colorAsset will also be lost.

Interpretation

  • A colorSingle has no meaning and is irrelevant until someone adds it to a colorAsset set.
  • How colorAssets are constructed is currently almost entirely out of scope.
  • For now, we will simply add a config to a wallet that defines the colorAssets by explicitly mentioning their colorSingles. A wallet needs to show its colorAssets as main functionality, but the colorSingles need to be retreiveable in the wallet as well.
  • A colorAsset stands for an asset, such as "dollars", "microsoft shares", etc.
  • A colorSingle is a mathematical bitcoin concept. There can be no misunderstanding about which colorSingle(s) a transaction output is.

Pro / Cons

  • Alex's way might allow for easier precomputations of colors.
  • Albert thinks his own modification makes it mathematically more generic.
  • Albert's method allows for decentralized issuance of a colorAsset. The matter of trust is decoupled from the protocol.
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.