Skip to content

EPOBC_simple

killerstorm edited this page May 12, 2015 · 3 revisions

EPOBC

EPOBC is one of possible ways of encoding colored coin transfers within Bitcoin transactions. (Also known as "color kernels".)

Color values are associated with Bitcoin transaction outputs, and are encoded using output values: 1 atom of a color value is 1 satoshi. However, we also add a certain amount of padding satoshi to satisfy Bitcoin node policies (see below).

Types of transactions

EPOBC introduces two types of transactions:

  • genesis transactions create new colored coins (of a new color); they are used for issuance
  • transfer transactions transfers existing colored coins

If colored coins are used as inputs in a transaction which isn't a transfer transaction, their value is lost, it is not transferred to outputs of this or other transaction. Also the value of colored coins might be lost in a malformed transaction.

Transaction tags

EPOBC-encoded colored coin transactions are marked in a special way to distinguish them from normal Bitcoin transactions. This is done by putting a certain tag value into a nSequence field of transaction's first input. nSequence is always present, but is otherwise unused, which means that this way of marking has zero overhead (unlike OP_RETURN-based which increases the size of the transaction).

nSequence is a 32-bit integer, and 6 of its least-significant bits encode the tag. Transfer transactions and genesis transactions have different tags:

  • bit sequence 110011 is a tag of a transfer transaction. Its hexadecimal value is 0x33.
  • bit sequence 100101 is a tag of a genesis transaction. Its hexadecimal value is 0x25.

Code which distinguishes transfer and genesis transaction:

# get nSequence of the first input
tag_nSequence = transaction.inputs[0].nSequence
# extract its lowest 6 bits
tag = tag_nSequence & 0x3F
if tag == 0x25:
    transaction_type = 'genesis'
elif tag == 0x33:
    transaction_type = 'transfer'
else:
    transaction_type = 'none'

Further treatment depends on transaction type. However, both transfer and genesis transactions have padding.

Padding

Bitcoin node policies require outputs to have at least a certain Bitcoin value, which is, at time of writing, 546 satoshi, but might change in future. We use padding to satisfy this policy, Bitcoin value of a colored coin output is computed as:

Bitcoin output value = padding + color value

where padding is either 0 (when color value is above the current dust threshold) or 2^n for some n. Padding is fixed at the time a transaction is composed and is encoded into the transaction itself. (This is necessary for unambiguous decoding, as dust threshold, and thus required padding, might change with time.)

Padding value is also encoded in the nSequence field of the first input, in the 6th to 12th least significant bits. Here's code which computes padding:

# get nSequence of the first input
tag_nSequence = transaction.inputs[0].nSequence
# extract 6th to 12th lowest bits
padding_n = (tag_nSequence & 0x0FC0) >> 6
if padding_n == 0:
    padding = 0
else:
    padding = 2 ** padding_n

Padding and tag extraction example

First input of transaction b3e4b52bf5be0450170cedea0935b70a003b3c3c5841ba528c7bee00f623aff3 has nSequence = 883.

tag_nSequence = 883
tag = tag_nSequence & 0x3F 
# tag == 0x33, a transfer tag
padding_n = (tag_nSequence & 0x0FC0) >> 6 
# padding_n = 13
padding = 2 ** padding_n
# padding = 8192

Thus 8192 are used as a padding. The value of the first output is 8292, thus if it is a valid EPOBC transaction, a color value of 8292 - 8192 = 100 was encoded.

Genesis transactions

A genesis transaction creates new colored coins, which are assigned to its first output. Value of the first output is used to determine how many coins were issued:

color_value = bitcoin_value - padding

All other outputs are assigned null colorvalue. Hash of the transaction becomes an identifier of a new color. When encoded as a color descriptor (URI), this identifier is "epobc::0:". Block height hint is a height of chain at time of issuance.

Transfer transactions

A transfer transaction has one or more colored inputs. Inputs do not need to be of the same color, e.g. "gold" and "silver" can be transferred within one transaction, which is useful for peer-to-peer trade. The order of inputs and outputs within a transaction, as it is used for non-ambiguous decoding.

We want to minimize an amount of information client needs to receive to compute a color value of a coin it receives, thus we define colorvalue computation on a single-output/single-color granularity. Clients which scan the whole blockchain might use a more efficient algorithm which processes a whole transaction is a single pass for all colors at once. However, this algorithm must produce results which are identical to those produced by the algorithm below.

High-level description of the algorithm of computing a colorvalue of a specific output of a specific transaction:

  1. Check whether transaction has transfer transaction tag. (Otherwise, handle genesis transaction or if it is neither transfer nor genesis, assign null colorvalue and exit.)
  2. Find which inputs match the output in question.
  3. Find colors and colorvalues of these inputs (they might be obtained by scanning previous transactions, or cached in the database, etc).
  4. If all matching inputs are colored and are of the same color, and the sum of their colorvalues is higher than bitcoin_value - padding, then bitcoin_value - padding is the colorvalue of the output in question and its color is same as the color of inputs.
  5. Otherwise, its colorvalue is null.

Normally colorvalues are kept as (color, value) pairs, where color is a hash of a genesis transaction, and value is an integer number. A special null value can be used for non-colored outputs.

However, if client is interested only in a single color (e.g. it only care about 'gold'), then the procedure can be simplified: all non-gold outputs will have null colorvalue. Then step 3 can be simplified: instead of identifying colors of all inputs, it is enough to check that all matching inputs have non-null gold colorvalue. This can affect thin client scalability and proof sizes.

Step 2 introduces a notion of input-output matching. This matching depends on the order of inputs and outputs within a transaction and their bitcoin values, but not color values. This means that you can find matching inputs even if you don't know their colorvalues, which is important for thin clients which compute colorvalues using recursive scanning.

Matching between inputs and outputs can be found through the following process:

  1. Discard all inputs which do not come from EPOBC-tagged transactions and all inputs after them.
  2. Find value wiihout padding (value_wop) for every input and output, as bitcoin value - padding. For inputs we use padding of the transaction they are referring to, not the spending transaction. (I.e. value_wop of an input is same as value_wop of the output it is points to.)
  3. Discard all inputs and outputs with is negative or equal to zero, and all inputs/outputs after that.
  4. Each input and output corresponds to a line segment of the length value_wop, see the picture.
  5. If a segment of input i overlaps with a segment of input j, input i matches output j.

This can be formalized as following:

  1. For every output, compute a value without padding (value_wop) as its bitcoin_value - padding, where padding is the padding of the transaction we're scanning.
  2. If there is an output with negative value_wop which precedes the output in question, return an empty list. (No matching inputs found: output cannot be colored.)
  3. Compute sum of value_wop of preceding outputs.
  4. Go through all inputs, one by one, keeping track of the running sum:
  5. If input doesn't come from a transaction with EPOBC tag (genesis or transfer), break and return the list collector so far. (Potentially, an empty list).
  6. Compute input's value without padding as bitcoin_value - padding where padding is the padding of the transaction they come from (i.e. "previous transaction"). (Note:: padding can different from padding of the transaction.)
  7. If input's value_wop is negative, break and return the list collected so far.
  8. If input overlaps with output in question, add it to the list. Overlap between segments [input_running_sum, input_running_sum + input_value_wop] and [output_preceding_sum, output_preceding_sum + output_value_wop] can be computed using the following condition: ((input_running_sum < (output_preceding_sum + output_value_wop)) and ((input_running_sum + input_value_wop) > output_preceding_sum).
  9. Increment input_running_sum with input_value_wop.
You can’t perform that action at this time.