killerstorm edited this page Jan 21, 2014 · 1 revision

(This is just a description from email.)

ITOG parameterized color kernel

nSequence field of inputs are used to specify outputs colored coins go to.

It is fairly hard to find a good name for this scheme, I settled on ITOG, which is something like "input targeted output groups" (which doesn't sound well), but really ITOG (итог) is a Russian word for outcome.

Let's start with informal description:

The Bitcoin protocol allows one to have multiple inputs and outputs in each transaction, thus it is possible, for example, to combine value of 5 inputs and spread it among 3 outputs.

We need same thing for colored coins, but we need to take into account that one transaction can have inputs/outputs of different colors. Conceptually, we can see it is as several transfers encoded in one transaction.

We need to introduce grouping of inputs in outputs: colorvalue of a group of inputs will be merged and then used to fill a certain group of outputs.

We can use nSequence field of inputs to describe which group of outputs an input is used to fill:

  1. Each input has target-descriptor which is encoded in its nSequence
  2. target-descriptor identifies a group of outputs and padding parameter which is being used
  3. All inputs having same target-descriptor are a part of a certain input group.

Conceptually the algorithm is very simple:

input_groups = identify_input_groups(tx)
for input_group in input_groups:
     sum_of_input_colorvalues = sum([get_colorvalue(input) for input in input_group])
     target_desc = get_target_desc(input_group)
     padding = get_padding(target_desc)
     output_group = get_output_group(target_desc)
     sum_of_output_svalues = sum([get_svalue(output) for output in output_group])
     n_outputs = len(output_group)
     for output in output_group:
         output_colorvalue = (output_svalue - padding) / (sum_of_output_svalues - padding * n_outputs) *  sum_of_input_colorvalues

But devil is in details, of course. What do we do if output belongs to more than one output group?

We want unambiguous way to compute output colorvalues, and we should take into account this:

Thin clients which do not rely on server-side coloring will have to traverse the transaction graph backwards, so it is important to make sure that backward scan works correctly. To avoid problems with difference in forward-scan/backward-scan implementations, we can define coloring in terms of backward scan, as forward scan algorithm can be trivially derived from it. (This is how the order-based coloring was defined, by the way.)

for output in tx.outputs:
    # 1. we need to identify output group this output belongs to
    #      it can be the first target_desc which mentions it.
    target_desc = find_target_desc(output, tx.inputs)
    if target_desc is None:
        output.colorvalue = None
        continue
    # 2. obtain inputs associated with it:
    input_group = input_group_for_target_desc(tx.inputs, target_desc)
    # 3. and full output group:
    output_group = output_group_for_target_desc(tx.outputs, target_desc)
    # 4. obtain values which are required to compute colorvalue.
    sum_of_input_colorvalues = sum([get_colorvalue(input) for input in input_group])
    padding = get_padding(target_desc)
    output_group = output_group(target_desc)
    sum_of_output_svalues = sum([get_svalue(output) for output in output_group])
    n_outputs = len(output_group)
    # 5. compute colorvalue:
    output_colorvalue = (output_svalue - padding) / (sum_of_output_svalues - padding * n_outputs) * sum_of_input_colorvalues

Now I hope the structure of this color kernel is clear, and we can talk about specifics of target descriptors. We have 32 bits which we can use to specify output group and padding.

Suppose we use 4 bits for padding, which allows us to encode 16 different padding values: 0, 10, 100, 1000 and so on. If we assume that outputs of an output group go sequentially in a transaction, we only need to encode index of the first output in group and number of outputs in group. We have 28 bits for this, thus we can use 14 bits for index and 14 bits for number of outputs.

Let's consider an example, here's what we want to achieve:

input_0: colorvalue=25
input_1: colorvalue=75

output_0: colorvalue=1
output_1: colorvalue=33
output_2: colorvalue=66

Target descriptor needs to encode following information:

padding = 10000; bits 0100
first output = 0; bits: 00000000000000
output group length = 3; bits: 00000000000011

We concatenate bits together and get 32-bit value to be used as nSequence for inputs 0 and 1:

01000000000000000000000000000011

Output satoshi values:

output_0: svalue=10001
output_1: svalue=10033
output_2: svalue=10066

Let's see how colorvalue is calculated for output_1:

target_desc is 01000000000000000000000000000011 which is decoded into   
      {padding: 10000, first_output: 0,     output_group_length: 3}.
input_group is [input_0, input_1]
output_group is [output_0, output_1, output_2]
sum_of_input_colorvalues = 100
padding = 10000
sum_of_output_svalues = 30100
n_outputs = 3

output_1.colorvalue = int((10033 - 10000) / (30100 - 30000) * 100) = int(33/100*100) = 33

This family of coloring schemes shines (compared to OBC/POBC) when high divisibility is required, suppose we want this:

input_0: colorvalue=25000
input_1: colorvalue=75000

output_0: colorvalue=1000
output_1: colorvalue=33000
output_2: colorvalue=66000

One could use 1 satoshi per atom of colorvalue, like this:

output_0: svalue=1000+ 10000 = 11000
output_1: svalue=33000 + 10000 = 34000
output_2: svalue=660000 + 10000 = 67000

But it is wasteful. Instead, we could use 1 satoshi for 1000 atoms of colorvalue and encode it like this:

output_0: svalue=10001
output_1: svalue=10033
output_2: svalue=10066

Let's go through calculations again:

sum_of_input_colorvalues = 100000
padding = 10000
sum_of_output_svalues = 30100
n_outputs = 3

output_1.colorvalue = int((10033 - 10000) / (30100 - 30000) * 100000) = int(33/100*100) = 33000
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.