Bitcoin Forum

It would be cool if more people tried using colored coins: it would help us to gather feedback and develop protocol further. But right now the only client is ArmoryX, and trying it out is pretty involved: it requires fully synced Satoshi Bitcoin client, and besides that ArmoryX eats about 1 GB of RAM. Few people would do that just to play with it...

So we want to see a web-based Bitcoin client which would support colored coins. Support for colored coins means that

• it should show balance for each installed color separately
• it should allow sending coins of a certain color
• it should implement p2ptrade protocol

Currently we 200 BTC for bounties for this project. We'll probably break the whole thing into smaller tasks and allocate bounty for each task.

As for architecture, we haven't settled on this now, but a perspective direction is to have server which can provide data about transactions in same way blockchain.info does, and client will identify colored transaction outputs using backward scan. Currently people are investigating whether it is feasible in terms of performance...

bitcoinjs seems to be a good basis both for client and for server.

If development of web client costs less than 200 BTC we will consider bounties for development of other color-aware thin clients like Electrum and MultiBit.

This is a preliminary announcement as there is no concrete plan yet, but people who are interested in doing this are welcome to apply. (Post here, send PM or post to bitcoinX mailing list: http://groups.google.com/group/bitcoinX/ )

Oh, by the way, of course it would be great if more people will chip in with bounty pledges. All results will be open source etc. It would be shame if we only do web but no Electrum.

I'm really looking forward to seeing what comes out of this. Colored coins are a big step in the right direction for bitcoin.

My dream is to someday hold oil, gold, and stable currencies in my bitcoin wallet. I probably won't buy colored coins yet (since you currently have to trust a third party to correct price divergences when the market doesn't), but I expect that self-correcting currencies aren't far behind (I think they will work something like this: https://sites.google.com/site/2ndbtcwpaper/2ndBitcoinWhitepaper.pdf).

Glad to see this bounty posted, and thanks Alex for his hard work.

I think the turning point when Bitcoin really became usable was when Blockchain.info launched. Let's do the same for BitcoinX.

While we're at it - I believe that not all of Blockchain.info's code is open sourced today, right? Alex, could we make the result of this project open source? It could benefit any existing/new alt chains that don't want to or can't use BitcoinX directly.

Everything is going to be open source, however I'm not sure if we'll make considerable improvements to things which aren't directly related to colored coins. It won't be exactly like blockchain.info.

Of course. Building a full blockchain.info clone would cost more than 200 BTC.

MVP first.

BTW, I guess that whatever portion of blockchain.info is opened source might be forked and used in favor of this project. It might take some more effort than building from scratch (or might initially appear to be more effort), but the benefit of forking blockchain.info's code is that it's battle tested.

Of course I could be completely wrong and blockchain's code might be a horrible fit for this project, I don't know it so I can't make that call.

Maybe the fact that you have to beg people to participate should give you some sort of a hint.  ;)

Let's hope that piuk directly will get the bounty :D
He seems a good and fast dev.

Anyway, I really hope to see a secure p2p market/exchange :)

Huh?

Colored coins are definitely useless now because nobody have issued anything of value yet. And nobody have issued anything of value because the protocol isn't finalized and implementation is immature.

Effectively it's only a demo now.

And going through blockchain download and running ArmoryX just to play with it is a bit too involved.

I don't think bootstrapping would be that hard once we'll get all software done.

End users don't even need to know that they are using colored coins.

For example, they might interact with an exchange similar to https://btct.co/ but with extra features like anonymous trading, offline storage, transfer between exchanges and so or.

Or they might interact with a payment system which is able to transfer USD, but doesn't require any registration.

Awesome! I've started poking around in the Electrum source, intending to implement the atomic/P2P trade tools for that platform.

Quite stoked to see colored coins hitting the rest of the clients codebases. There are some cool applications in the pipeline.

Depending on what functionality you exactly need, https://bitcointalk.org/index.php?topic=22785.0 (ABE, Alternative BlockExplorer) is at least already able to read bitcoin style block chains and can also generate various reports. I guess it would not be ok to create a webwallet out of it, but at least some display/3rd party auditing for colored coin exchanges could maybe built in there.

bitcoinjs-server acts as a full Bitcoin node, it keeps its own blockchain database and so on.

https://github.com/bitcoinjs/bitcoinjs-server


Yes, but I think bitcoinjs-server is a better choice. Of course it can be used for "colored block explorer".

This is a shame colored coins haven't gained more traction.  They're a fantastic way to create stock or something, and a great new way to make bitcoins (or at least some of them!) even more valuable.  It really is a good idea and good addition to bitcoin.

Can someone explain what a colored coin is?

It doesn't it exist, it's stupid, it's frivolous, fuck it.

Edit: p.s. whiskey.

It's an itty-bitty fraction of a Bitcoin that represents ownership of an asset.

That asset could be a bond (in which case payments could be made to all bondholders without knowing who they are pretty trivially by inspecting the blockchain), ownership stakes in a company (in which case stockholders could vote by signing one side or another of a decision with a private key corresponding to the public key to which the colored coin was most recently transferred), or tokens for smart property (in which case your car would ask you to sign a random character string which it would validate against the public key to which its ownership colored coin was transferred most recently).

General info about colored coins for those who need it: https://bitcointalk.org/index.php?topic=106373.0

Have you seen my post on fidelitybonds and contracts (https://github.com/petertodd/trustbits/blob/master/fidelitybond.md)? Fidelity bonds are a close cousin to colored coins, with the exception that every txout is associated with a contract. For fidelity bonds this is the contract describing how the holder promises they will act, but for colored coins the "contract" could simply be the identifier of the color; the colored coin protocol for fidelity bonds uses the least significant bits of the txout value to separate contract and change outputs, and thus allows for arbitrary precision. Currently there is just contract and change, but the idea that can easily be extended to multiple different colors in a transaction by using more bits if required, allowing fidelity bonds to be traded for colored coins representing other assets in the future.

Contracts also allow for off-chain trading by inserting a special contract stating that some trusted ledger holder, possibly kept trustworthy by a fidelity bond, will maintain balances for the coins beyond some point. Of course, obviously the problem of trusting some central ledger is exactly the problem that colored coins is trying to solve, but there is room for both solutions, especially as demand on the limited block space becomes high. Trusted ledgers can after all still transfer some of the balance they are keeping a ledger of back onto the block chain, allowing you to get your balance back onto the block chain. Similarly the trusted ledger might actually be a merge-mined alt-chain using cross-chain coin trading (https://en.bitcoin.it/wiki/Contracts#Example_5:_Trading_across_chains). (reminds me, I should ensure the contracts protocol is compatible with those transactions)

Of course, you're pretty far along with colored coins with your existing protocol, but I thought you might be interested in what I'm working on. Also, thanks for everyone who developed the idea of colored coins in the first place; the fidelity bonds and contracts proposal wouldn't have happened without your ideas.

What about command-line-tool/JSON-rpc for the concept? I think that would be the key to get it to the masses.

As a developer, I'm starting to look at what features this would mean; is this accurate in starting to break down what those "smaller tasks" you mentioned are?

it should show balance for each installed color separately

• Needs the ability to "install" a color: User needs to be able to upload a color definition (https://github.com/killerstorm/colored-coin-tools/blob/master/colors.md#color-definitions) file to inform the server of that "color" of coin. => File upload with parsing/verification of the upload file, or typing each of the four fields in
  
• The definition files would be global among all users of the site, such that caching the blockchain of where those coins are at would be shared across the site => A separate database would need to be designed for them
• Non-logged-in users could see the balance/location of colored coins the site knows of, and logged-in users can see what their balance of colored coins is. => The blockchain logic would need to be augmented to keep a running total of colored coin locations, and keep track of colored coins that were inadvertently destroyed by badly-formed transactions merging a colored input into an uncolored input via a single output.

it should allow sending coins of a certain color

• Needs the ability to create a transaction that follows the order-based coloring rules (https://github.com/killerstorm/colored-coin-tools/blob/master/colors.md#order-based-coloring). The site would ensure that if two inputs are directed at one output, that both are colored, so colored coins don't get destroyed in the process.
  

.
it should implement p2ptrade protocol
This one I'm not finding a definition for; where's the protocol specification for the "p2ptrade" protocol? I found "P2PTradeX (https://bitcointalk.org/index.php?topic=91843.0)" (cross-chain protocol), is that what you mean? You say you've worked it into your Armory client fork, but I'm not seeing a reference to the original protocol.

---

Incidentally, I'm excited to see this functionality added to the Bitcoin environment, both for tracking assets, and it could be a way to mark stolen coins to see where they end up. While the Bitcoin protocol itself guards against double-spends and address collision, there's still a few cases of hacking/social engineering that parted people from their coins. In the real world criminals fence/launder money and goods to disguise stolen items. If coins gained unethically were marked as "colored" by some authoritative source (who verified someone's not just crying wolf saying it was stolen), the logic used to track a colored coin through the blockchain could be used by individuals/merchants who don't want to accept stolen coins as payment. Yes, criminals could "launder" the colored coins by merging two inputs into one output by the current protocol, but the matching protocol could easily be extended to figure out what portion of an output is colored, since the protocol sorts the transaction inputs and outputs and matches up their values, there could be logic saying that output N is "red" for the first X BTC, "blue" for the next Y BTC, and uncolored for the rest. If output N then becomes an input for output M, the same logic could split M out by color too. A color-aware client could also un-scramble a given output's colors, then; assigning multiple outputs to that one input.

What's the use case?

You can write Python scripts which will work with ArmoryX implementation, that's pretty much trivial.

However, the problem is it takes like 3 minutes to load it up (scanning whole blockchain) in the best case, so you'll probably want a long-running

Here's an example of fully automated Satoshi-Dice-style trading:

https://github.com/killerstorm/BitcoinArmory/blob/color/autotrade.py
https://github.com/killerstorm/BitcoinArmory/blob/color/extras/autotrade-test.py

Whole application in 150 lines of code...

Also, there is bitpaint.py command line tool (fairly primitive compared to what ArmoryX does), it wasn't wildly popular...

OK, here's an overview of a plan:

1. We need bitcoinjs-server server side. Eventually we'll probably customize node-bitcoin-exit, but for now we are using a fork of node-bitcoin-explorer called https://github.com/domtancredi/bitcoinjs-color

    The difference is that this one can provide relevant information about transactions.

   We will run this stuff on our server so it will be available for testing and development and whatnot.

2. Coloring algorithm. We have a broken implementation in JS 
  https://github.com/domtancredi/bitcoinjs-color/blob/master/async.js

  There is also one which actually works in Python:

  https://github.com/vbuterin/BitcoinArmory/blob/color/gettxcolor.py

  However, it's very basic... I think the worst case can happen on uncolored output, and we need to optimize for this case via different traversal strategies: depth-first, breadth-first, best-first...

   To make it clear, coloring algorithm isn't the hard part. When I was participating in programming contests (ACM ICPC) I could implement an algo like that in a hour or so.

3. Making wallet color-aware: Wallet will probably be based on bitcoinjs-gui (https://github.com/bitcoinjs/bitcoinjs-gui), I haven't looked at it closely so I don't know for sure.

   Quite likely same approach I was using in ArmoryX will work here too, and it is easy to implement.

4. Color definitions... For now it's largely trivial.

5. p2ptrade: I was referring to distributed exchange protocol implemented in ArmoryX:
   https://github.com/killerstorm/BitcoinArmory/blob/color/p2ptrade.py

   Algorithm is fairly complex, but JS implementation can simply copy Python implementation, so I think in the end it's fairly easy.

   Biggest problem is that ArmoryX uses so-called TXDP for partial transaction serialization and tx surgey. But it's only available in Armory. I think we'll have to implement a different serialization format and port it to ArmoryX so it won't depend on TXDP.

   Is it hard? I dunno, everything about serialization scares me ("endiannes, motherfucker, do you speak it?"), but there are people who can easily edit transactions in hex.

   So I suspect it isn't hard for people who are used to doing this stuff.

6. And the rest is cosmetics and usability features.

No, I have a different strategy in mind. User has his own private wallet which stores color definitions and private key (seed) he owns. This wallet might be kept (encrypted) on server, or it might be in browsers local storage. (But then we need to be sure that user can't accidentally nuke his wallet.)

Server simply provides information about transactions and acts as exit node (i.e. like block explorer or electrum server, basically), it doesn't do anything color-related.

All coloring is performed on client. There are two reasons for this:

 * client cannot trust coloring which comes from server anyway (it has to verify information he receives from server, and verification isn't very different from color identification)
 * implementing coloring on server is fairly complex

Basically people were trying to implement server-side coloring for some time, and now I'm like "Fuck it, we'll do it live!", I mean directly on client.

I believe performance won't be an issue if we'll use best-first traversal strategy, also eventually we can add caching and whatnot.




Well, p2ptrade.py is the definition of the protocol :-)

Of course I'll try to produce a spec, but I think it's fairly easy to understand once you read p2ptrade.py.

https://github.com/killerstorm/BitcoinArmory/blob/color/p2ptrade.py




I don't think so, they have different goals:

 * taint is contagious: mixing tainted with untainted coins produces tainted result
 * color is anti-contagious: mixing colored with uncolored coin produces uncolored result

So you really want to use a different algorithm...


There was a proposal for colored algorithm to work like that, but that's not how it works now... I'd say uncoloring mixed results is actually a feature: property certificate which was accidentally destroyed can be replaced by issuer.

Anyway, I don't think it's particularly useful for tracking stolen coins as quite likely some unsuspecting party will end up with tainted coins.

From looking at the python code, you use a heap for the traversal, but the heap is sorted lexicographically by the transaction hash, which means that the traversal is pretty much random. You can change it to be breadth-first by using a tuple (depth, txhash) in your heap where depth is the depth of the transaction, so that all the transactions of a certain depth will be visited before the next depth. For depth first, swap out the heap for a list and always visit the last item.
For best-first, how would you decide which node is going to be best?

Also, I'm struggling to see how the traversal strategy really matters. Your only optimization that I can see is the case where you have more than 2 matching inputs, and you find that 2 of them don't have the same colour, then you don't have to check the rest, or you find that 1 input is uncoloured, and you don't have to check the rest. Apart from this, you pretty much have to search everything - in which case it doesn't matter which order you do it in.

Wait, this confuses me more. The coding of the current python algorithm isn't hard, or the porting to JS isn't hard, or the modification of the python to change the traversal strategy isn't hard? What's the hard part?


Also, surely it would be better for the server to do the colouring algorithm and scan forward, updating its blockchain DB as it goes? That way the traversal only happens once when you import a colour definition, and querying the server for colour information of a particular transaction wouldn't require any work, and more importantly, any time.
You have to trust that the server isn't lying about transactions, so why is it a problem if you have to trust it to tell you the colour?

If worst case is achieved on uncolored txo we need to find at least one provable uncolored output (e.g. coinbase) in history to prove that end result is uncolored.

Best algorithm is one which goes to coinbase as fast as possible.

It is fairly easy to write an algorithm which finds shortest past, but it requires assistance from server.

So for now we'll use breadth-first, Vitalik just wrote me that he have implemented it.

(To make it clear, there is short-circuiting in traversal.)



Exactly.


Yeah, but maybe it makes sense to avoid dfs to avoid blowing stack.

Also perhaps later we'll perform optimizations which involve caching, buffering etc.


Hard part is getting everything to work together :)

Ok, good. I don't really know the inner workings of bitcoin, so I didn't know that it was possible to find the shortest path efficiently.

Another optimization - thought of it earlier and then forgot about it  ::)
For a given colour, get the block of the genesis transaction, let's call it the 'creation block', now we have the following scenario
 - Suppose we have 2 (or more) inputs and find that input 1 is coloured red. Now we know that we can stop as soon as we find another input that isn't red.
 - If we know the creation block for 'red', then when traversing transactions, if we get to a transaction in block X, and X came before the creation block, then we can stop traversing any deeper because no inputs in this block can possibly be coloured red.

Additionally, out of all our colour definitions that we're interested in, we can take the earliest out of all the creation blocks, and now we know that we never have to search any deeper than this.

Well, it's only going to blow the stack if you search recursively. If you maintain a list of nodes to visit (as you currently do) but make it a LIFO instead of a heap, then you avoid the stack problem. Of course, the list may grow so big that it blows the heap (memory), but then you also have this problem with the current heap (data structure) approach - it really depends on the shape of the tree.

Also, what state is the bitcoinjs code in? The last commit to any of those projects was 6 months ago, and most are over a year without any changes.  :-\

I've been playing around with electrum and the electrum-server.  I'm starting to be more hesitant when trusting anything javascript and Armory is rather heavy as a client.

A blockexplorer type site would be nice for browsing colored coins, but I'd really be interested in a desktop client that uses the stratum protocol.

I've tested coloring via bfs traversal on the real blockchain, and it doesn't work so well: sometimes it needs to scan like 20000 transactions to get to coinbase one. (And thus prove that output in uncolored.)

DFS seems to be a little better, but it blew up Python stack on at least one output, which means that depth is about 1000, which isn't cool either.

So I think we need a solution which finds the shortest path.

So to start with this we'll allocate two bounties:

1. Port dfs backward-scan coloring to JavaScript: 5 BTC.

As I've already mentioned, it is already implemented in Python by Vitalik Buterin.

BFS version: https://github.com/vbuterin/BitcoinArmory/blob/color/gettxcolor.py

DFS version: https://github.com/vbuterin/BitcoinArmory/blob/92f021b0770cf7504bbe5df17d89044b97fc901b/gettxcolor.py

However, DFS should be implemented in such way that it doesn't blow up the stack, also it needs asynchronous queries, so it's going to be considerable different from Python version in structure. But still you need something like get_matching_inputs to do the coloring.

Theory: https://github.com/bitcoinx/colored-coin-tools/blob/master/colors.md

To access transaction information you can use blockchain.info API: http://blockchain.info/ru/api/blockchain_api (and async queries, of course!), but please abstract transaction-data query function so we will be able to use it with a different API.

You can take this code for an inspiration: https://github.com/domtancredi/bitcoinjs-color/blob/master/async.js it kinda tries to implement this via DFS, but is broken. Still you can borrow general structure etc.

2. Build shortest path database based on bitcoinjs server: 7 BTC.

We need to know distance from a transaction output to nearest coinbase. We will store these distances in database, and then query this database to find shortest path.

Algorithm is fairly simple:

Scan all transactions in blockchain sequentially starting with the first block:
1. If transaction is coinbase its outputs have zero distance to coinbase.
2. Otherwise, for each tx output, we find all matching tx inputs (same function is used for coloring, see get_matching_inputs here: https://github.com/vbuterin/BitcoinArmory/blob/color/gettxcolor.py)
    Fetch distance of each input from database (they are already there because we're scanning sequentially).
    Find minimum of input distances, then output's distance is minimum+1.
    Write this number to database.

I recommend using this as a starting point: https://github.com/0i0/bitcoin-tx-spent-db
It is a thing you need to run together with bitcoinjs server, basically it installs its query code into bitcoinjs, then it provides REST API to database it have built.

You can either fork it and replace spent-db code with distance-to-coinbase code. Or you can extend this code and write to two separate collections. It's up to you.

The starting point is  https://github.com/0i0/bitcoin-tx-spent-db/blob/master/app.js -> everParseBlock -> getCollection, it is a function which goes through transactions and adds the to database, but in our case it should find shortest distance for each output and write it to database.

Please note that working with main net is very resource intensive, you'll need 20+ GB of disk space and 20+ hours for processing. Use testnet, there is a command line option for bitcoinjs. (Don't forget that genesis tx hash is different, for some reason it is used in app.js)

Both tasks share the need for get_matching_inputs. It would be cool to implement it only once in JS, but it's not critical, I guess.

That's all... Whoever wants to work on this, please let me know. Questions are welcome not matter whether you're going to work or not.

If you think that bounty is too low (e.g. you would do it for 10 BTC), please let me know.

Vitalik is going to port DFS coloring to JS.

Shortest distance to coinbase server is still up for grabs.

I think it's only a couple of hours of works for an experienced developer who knows both node js and bitcoin stuff, so 7 BTC bounty corresponds to ~$100/hour pay, which is pretty good. :-) Of course, this number is lower for a person who cannot develop it this fast.

Yeah, I suspicious of in-browser wallets too.

Now ArmoryX is more-or-less dead, and so Electrum development will likely get higher priority, so we can allocate bounties for color-aware Electrum. (I'm not sure how much exactly, though.)

However, my opinion is that electrum-server is a piece of shit, and it is not suitable for what we need out of box. (At least it wasn't when I've checked it.)

I'd rather use a different server. Protocol doesn't matter much.

To be honest, I have no idea.

All I know is that server can get transaction history from Bitcoin network, and that's enough.

If client side was working once, it probably still works now. Client just needs cryptography to work, the rest is fairly straightforward.

There are talks about using bitsofproof instead of bitcoinjs server. bitsofproof is being actively developed now.

Ah crap, I should have spoken sooner.

Anyway, seeing as I did this earlier, he'll probably want to know that there is a weird bug in blockchain.info so it gives the wrong transaction data when inputs are from the same address - it adds their values together and makes it appear as a single input. From the firefox it works correctly, but happens in Chromium and importantly when I request from node.js, even if I set all the http headers to the same as firefox.

So you might want to change to a different source of transaction data.

Compare https://blockchain.info/tx-index/29845514 (https://blockchain.info/tx-index/29845514) with the result from the api https://blockchain.info/rawtx/29845514
Notice vin_sz = 3, but inputs size is 2. The second input is actually 2 inputs of 2btc and 34btc.

I went through a few weeks ago and cleaned up a lot of code and made everything PEP8 compliant. I've got a branch in development that vastly improves the logging. Once that is in, I want to clean up some of the design patterns and write unit tests. Then I want to make a plugin architecture that would make it easy to add any sort of backend or frontend. I'm busy with my job though and so haven't had much time.

If you/someone builds a full server, I recommend at the very least that you use the stratum protocol. It's pretty simple to implement and standards are always nice to stick to if possible.

Actually you have a chance to do this if you want.

I talked to Vitalik, he will start with shortest distance db first, and he haven't started with DFS-coloring, so it's an open task now.


Wow, that's weird.


Yes, we have our own half-assed tx data server which can work instead of blockchain.info, I think.

Details?

Also, test vectors?

http://178.33.22.12:3333/json/tx/8f6c8751f39357cd42af97a67301127d497597ae699ad0670b4f649bd9e39abf

Format is obvious, I think. Server code: https://github.com/domtancredi/bitcoinjs-color

It is serving data for testnet, and that's for a reason.


Well, here's a test (for testnet): https://github.com/vbuterin/BitcoinArmory/blob/color/txcolortest.py

But I don't have color definitions it's based on, I'll ask Vitalik...

Well, suppose we have funding for that, what's the best way to proceed?

Further development of web client:

Here is a preliminary list of tasks. It is preliminary because it lacks some details and might change a bit. (I'm going to test things a bit before finalizing it.)
So it is not actionable, but it gives you an idea, and whoever wants to work on these things can already 'book' a spot.

Improvements on server side:
1. Merge bitcoinjs-color, bitcoin-tx-spent-db and, later, node-bitcoin-exit. There is no reason to have them separate, I think.
2. tx data access API (called bitcoinjs-color) needs to be updated:
    * JSON API needs to return values correctly is satoshi, not in floating point values.
    * provide raw transaction data
    * provide cryptographic proof, i.e. Merkle branches which link transaction to block and block headers
    * support for batch queries
3. Make sure it continuously gets new data from blocks and can work with transactions in mempool.

Development on client side:
1. Coloring: Use distance-to-coinbase data to guide DFS to get optimal performance on uncolored outputs.)
    (This is what I'm doing now, but there is a problem with dtocoinbase db, so I cannot proceed.)
2. Make it so client verifies crypto stuff rather than simply trusts server
3. Hook coloring algo to front-ends:
    * block explorer
    * brainwallet
    * bitcoinjs-gui
4. Improve front-ends until they are usable

There is also an admin task: install all the crap on a powerful server, populate dbs etc.
Currently it runs on my VPS which is enough for testnet, but populating spent-db on mainnet will be really painful.

There is at least 50 BTC in bounties for this list of tasks.

what is "dtocoinbase db"?
what problem are you having?

DFS-based coloring will used distance-to-coinbase db built on server to make sure that scanning uncolored outputs does not take too much time. It's just not ready, requires a bit more work.

So that was a general plan (which might change). As for immediate target, I'm going to make sure that DFS coloring is indeed usable, and to look into how to integrate coloring into block explorer, brainwallet, bitcoinjs-gui etc.

If somebody wants to into it instead of me, that would be cool. :-)

Here is coloring code: https://github.com/Zeilap/colors/blob/master/color.js

You can just run test via node:
Basically these things (block explorer, brainwallet, bitcoinjs-gui) can just call getColor function:


whenever for transaction outputs they see. Perhaps we'll modify this API later, but for now it's OK.

E.g. block explorer will just show color, other things can use it to filter outputs etc.

ok, i see. i don't know that much about dfs, but from what i've read it doesn't seem possible on a key-value db like leveldb (which is what bitcoinjs uses by default). have you implemented a custom/separate db for the coloring? coincidentally, i just spent this past weekend experimenting with an rdbms backend for the coloring features i'm working on. the database is built "lazily" after a new color definition is requested. works okay, but i'm concerned about scalability (more experimentation is needed).


color.js works perfect ... but ... it does a recursive query using http. to me that seems a bit ... insane. at the very least sockets would seem more efficient.  but why not just do all the recursion work on the server-side? (is that the eventual goal?? -- plug the color.js module into bitcoinjs -- sorry if i missed this somewhere .. suffering from information overload)

also, i'm confused, because i'm pretty sure the color definitions are based on addressHash160. but your code seems to key on specific transactions. i assumed you would query back to each address' "first appearance" as the origin. mainly because then you can easily distribute more coins of the same color (how can this be done with tx origins?)

i've mentioined before that i'm trying to keep my own work in line with your "official" coloring implementation. my biggest problem right now is multiple-color txs (using ordered ins and outs).  i'm sure i just need more time & understanding working with the bitcoin protocol (so this will come eventually).

i've got too many distractions this week (family-related) to realistically make any significant progress, but i'm really-Really-REALLY hoping to be able to publish something within the next 2 weeks. i've been testing my current implementation with friends & family for about a week now ... so far so good :)

This is a monster of a task - it equates to implementing most of the functionality of an SPV node in the browser. The crypto is intimately tied to the binary representation of the transaction data, so you need to implement full parsing of the raw transaction and block header structures.

Also, without having the blockchain headers in the browser (say in local storage) and verifying them, the cryptographic proof is meaningless - you don't have verification of the block header that the transactions are linked to. So you additionally need to have a way for the server to provide a full header chain download and verification code in the browser.

Anyway, I think if this is your plan, I can do this (assuming I have the time), but it's a lot of work, so can you break it down and assign individual bounties.

DFS is just a specific form of backward scan, i.e we go back in history.


Well... We'll optimize it later :) The thing is that performance should be acceptable as long as coin's history is small.


Well, that creates far more problems than it solves.

One thing is that it is a fundamentally flawed model w.r.t. security: client cannot and shouldn't trust server to do coloring properly, it should check on its own.

Another thing is that opens server to DoS attacks because this scan can be very computationally expensive.

It makes sense to do recursion on server to send all the data in one batch, but it's just a performance optimization and it isn't a priority right now. We can do it later.


I think if we do coloring on server, we should use database and whatnot.


There are two models: "genesis" and "issuing address". "Genesis" is simpler, easier and more secure.

I'm not even sure we should do "issuing address", but the reference implementation, ArmoryX, does both.


Yes, "issuing address" allows one to create more coins... Which is both a good and a bad thing.

In genesis model, it is possible to issue more coins by adding more genesis tx outputs, duh. However that would require color definition update protocol, which isn't implemented/standardized yet.


Have you seen this: http://killerstorm.xen.prgmr.com/alex/color.html
It is a demo from colored-coin-tools.


Thanks, that would be cool!

Currently the algorithm finds the matching inputs for the given output and then visits each of these inputs. It is depth first because the order in which the inputs are put on and taken off of the queue is last-in, first-out. What killerstorm wants is to pre-calculate the depth of each output and store this depth with the output itself. This way, when adding the transaction inputs to the queue, you sort them in order so that the one with the smallest depth is always the last item in the queue, and thus is the next output that will be visited.



I think the plan is that the code I wrote will actually end up browser side, replacing the node specific http requests with jquery ajax or something. The idea is that the server knows nothing about colored coins or any color definitions. Instead, all it provides is transaction data so that the client can store color definitions and perform the color-matching algorithm itself. This way you do not have to trust the server.

I wrote the code with the idea that it was probably going to be cannibalized and modified later when it gets integrated into the rest of the work. It is mostly a proof of concept that the idea works and that the performance is acceptable for an end user.



A color definition is a pair of transaction hash and output index. This uniquely specifies a given output. When an address receives funds, what it actually means is that there was a transaction where the output specified that address as the receiver. The inputs of each transaction are simply the outputs of a previous transaction (or reward for mining a block). This way, you can trace all the bitcoins back to their creation, or similarly, trace all the created coins forward to where they are now.

The colored coins idea is that we simply label a given transaction output and then we can trace the location of this output forward as it gets transferred and split up between other people. By using addresses rather than outputs, you would limit the ability to use colored coins with non-standard transactions, and really, colored coins are much more interesting if you combine them with exotic transactions.

Yes, that's the only way to make it secure.


Well, all JS wallet implementations can do that... Kind of...

For example, Brainwallet can give you a signed raw transaction ( http://brainwallet.org/#tx ), and it is very simple.

So I don't think it is monstrous at all... Just glue some pieces together.


Not quite... We can estimate how hard it is to make a fake block from this block alone. If we have some reasonable estimation of current difficulty, we can estimate opportunity cost of attack.

Note that one needs to mine a fake block after transaction was submitted... You cannot pre-mine some fake blocks and insert transactions there, it would change Merkle root.

So, all in all, if you know current difficulty, you can estimate that faking one block costs about 50 BTC.


I don't think it is a problem: server can collect all information needed by client in one blob. Client will then parse this blob to get block headers, Merkle branches, transactions etc. Size of this blob? Maybe a couple of megabytes... It isn't big by internet standards.


Yeah, I think we will leave juicy crypto parts for later :)

Ah, I wasn't aware of this.

Ok, fair enough, but that assumes that you are trying to fake a recent block. If you want to fake an old block, the difficulty is much lower.


If you do this, then wouldn't it be simpler not to do backwards scan in the client at all? Instead, the client provides the server with the definition and the output he wants to test, the server then does a forward or backward scan and determines whether the output is colored, constructing a proof as it goes. Then it sends the proof to the client. Maybe this was your idea all along?

seems simple enough, but just so that i'm clear, would that mean that bfs would go forward (oldest -> recent)? (my knowledge thus far come from here (http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/) and here (http://www.cs.sunysb.edu/~skiena/combinatorica/animations/search.html))


this is VERY helpful. i'll take some time to work through the code, however, just a quick question .. why is "mixed" a drop-down option? how can you have a "single" mixed input (wouldn't those colors have be destroyed)?


this may come from being a bitcoin n00b, but i'm 100% in favor of spv over full node. i just can't see how having the full blockchain is practical for "most" users and given the amount of complaining about latent SD "dust spam", i don't think it should be. my belief is that "most" users should find node(s) that they TRUST (like they would a traditional bank) and simply run a thin-client. given the strength of cloud-computing, SAAS and the like, heavy "client-side" processing (especially in the browser -- which is where i like to live) seems imo outdated. but, i can certainly appreciate the security advantages, which have many use-cases.


that's the problem i would have. i'm looking to distribute shares in batches (maybe 20+ over time). "genesis" would force everyone to update their definitions after each batch.  "issuing address" would mean that i can even have private offerings and everyone would still be able to easily track the outstanding distribution.


what do you mean by exotic transactions? unfortunately, my creative thinking seems stalled.


this is "almost" how my implementation works now (except without the proof-of-work).  obviously, this is not very good for client-side security, but its FAST-as-hell (and imo, more practical for the "average" user). could you please elaborate on HOW you could provide that proof? (i'm guessing it has something to do with merkle trees???)

this way, the burden then rests squarely on the server's implementation and capabilities.  i have this idea in my head that it would be ideal to have at least enough ram to hold the FULL blockchain. bitcoinjs is currently around 13GB (with my mods almost 20GB). so does a 32GB nodejs/event-driven server seem practical? too much? possibly not enough? (obviously load-balancing could also be used)

this is very exciting stuff.
cheers!

This is an updated version of code: https://github.com/bitcoinx/colored-coin-tools/blob/master/color.js
compute_colors() are much easier to follow in this version because validation was moved to separate functions.


Yes, 'mixed' is same as uncolored, implementation in ArmoryX does not distinguish between mixed and uncolored. So just forget about them :)

No, choice of traversal order is orthogonal to choice of traversal direction.

In context of coloring, the difference between DFS and BFS is in how fast they detect uncolored outputs. There is no performance difference for colored outputs, they need to go through all transactions in history anyway.

DFS can detect uncolored outputs faster, basically it just goes to nearest coinbase transaction, which is by definition uncolored.


When implemented properly SPV requires no trust. If it requires trust, it isn't SPV. See here: https://en.bitcoin.it/wiki/Thin_Client_Security


We can use servers, but we don't need to trust them.


You can issue maximum authorized number of shares via single genesis, but park them on issuer's address and distribute as needed.

This way accounting is same as with "issuing address": number of outstanding shares = number of issued shares - number of shares held on issuer's address.

However, it is just easier to track shares back to one genesis transaction output... Also it limits maximal number of shares.

I think "issuing address" makes sense only if you absolutely cannot issue shares in one batch. For example, if shares have large "metal value" so issuing them costs money.


The usual Bitcoin output script (https://en.bitcoin.it/wiki/Script) pays to a single address.
But there are many other possibilities. Say, m-of-n multi-signature scripts. (They are standard now.)

Also, contracts: https://en.bitcoin.it/wiki/Contracts

When you have something other than simplest transaction you cannot associate a single address with it.


Yes, Merkle trees... Basically you send a bunch of hashes to prove that transaction is linked to a block. But the whole scheme is rather contrived.


Yes, it is definitely doable, but blockchain will grow in future, so it isn't clear how it can work in future.

There are several other implementations. Particularly, bitcoinjs-server is a full, verifying Bitcoin node, so it obviously has all the necessary cryptography... I'm not sure whether it is possible to port it to browser env, though.


Yes, this was the original plan (more-or-less), and people started implementing it back in November 2012... But the only result is bitcoin-tx-spent-db, which is far from a complete coloring server.

So I thought it's better to start with something simpler and started investigating the possibility of doing coloring on client side, as it is fairly hard to do it on server-side.

The priority is to get something demonstrable. Security and performance are secondary targets for now.

dfs vs bfs ??? i've obviously got a lot more reading to do


oh, i see. so i guess then a "proper" spv client is "required" to download all the block headers?  i think this is how the sd android app works. it takes a while to fully sync, but no where near as long as bitcoin-qt. and i think ultraprune in v0.8 is similar

but then how would you classify an app like BitcoinSpinner (https://en.bitcoin.it/wiki/BitcoinSpinner)? You just start it up and it WORKS without any syncing? or for that matter any app that uses the blockchain.info api or how about bitcoinjs-gui?


makes sense. this is actually how i originally implemented my version of colored coins. i changed after i reviewed ArmoryX's use of the address definition as well as the whole idea of coins being destroyed. when accommodating users by allowing coins to be re-issued, address definition seems a hell of lot more convenient "for the user" (maintain total share count w/out the need to install/track new definitions). This does create additional burdens for the issuer, but i think it works well for my use-case (i certainly see the advantages of tx definitions -- as you described the various creative scripting options)

i should mention that i've implemented the firstSeen feature that was missing from bitcoinjs, which makes searching for issuing address just as fast as tx searches.


there are limits (http://dev.w3.org/html5/webstorage/#disk-space) on the amount of data you can save in local storage. so even a spv client may have problems.


absolutely!  ;D

Actually link you posted has a good illustration: http://www.cs.sunysb.edu/~skiena/combinatorica/animations/search.html

Suppose what we are looking for is in the first pentagon. DFS will arrive there faster because it won't go to other pentagons before it scans the first one.


Yes.  But if you just link to one block header, it's still much better than nothing because it is hard to fake just one block header.


As far as I understand it downloads whole blocks because there is no way to download only headers, however it discards block contents unless it looks for wallet transactions.


No, ultraprune is a full verifying node implementation, it is just more efficient.


They trust that server protects them against double-spends. Also, they pull blockchain info from server instead of downloading it directly on Bitcoin network.


There is no need to store everything locally.

It is in fact theoretically possible to implement a full, verifying, mining node when you have only 32 bytes of local storage :)

But that's a fairly complex topic...

I've started with block explorer: http://178.33.22.12:3333/bexplo.html

color-aware block explorer kinda works now:

http://178.33.22.12:3334/bexplo.html

It is on testnet because there are performance issues with mainnet... Likely need to upgrade server to run it on mainnet... Also fix code, I guess.

Two color definitions are loaded: red and blue. (In future one could just point it to a color definition bundle of his choice.)

Genesis of blue:
b1586cd10b32f78795b86e9a3febe58dcb59189175fad884a7f4a6623b77486e
(loaded at start)

Genesis of red:
8f6c8751f39357cd42af97a67301127d497597ae699ad0670b4f649bd9e39abf

There is a bug: in some cases, colored input might be shows as having color 'none' at first, but when it shows same transaction again (click 'show' button) color is displayed correctly.

E.g. here: bd34141daf5138f62723009666b013e2682ac75a4264f088e75dbd6083fa2dba (4 blue inputs are merged into one).

Code is here: https://github.com/killerstorm/bitcoin-tx-spent-db (branch 'extra')

very nice.
-----------------

just need to say that i really appreciate you taking the time recently to answer all of my questions.

since i started with bitcoin back in nov, i feel like i'm back in school doing math problems with paper and pen. when all i really want is a damn calculator.

thanks a million ;)

Fixed a bug (sounds like the one you describe) - check pull request.

Yeah, works now. Thanks.

Your second patch didn't work though: it says no valueToBigInt function, or something like that.

Ah, sorry, the calls to valueToBigInt should have been to Util.valueToBigInt.

I'm trying to get bitcoinjs-server working under Windows 7. Where is bin/bitcoinjs supposed to find module "step"?

in ../node_modules

should pull in everything it needs though.

That's brave.

We have a Linux server for development... I can give you ssh access.

Or even set up NX...

 I worked via NX for about a month, until I bought a new laptop which made it unnecessary.

New bounties will be announced via issue tracker.

Updates (fragments of emails from bitcoinX mailing list, sorry); :

---

Here's it running on testnet: http://devel.hz.udoidio.info:3125/index.html
You can grab testcoins here: http://testnet.mojocoin.com/

"Colorize" button doesn't do anything useful... It simply identifies color of each unspent transaction output in a wallet. If that is successful it alerts 'triumph'.

---

Here's how to run it:

1. I use nodejs 0.8.9, otherwise there seems to be a problem with building bitcoinjs-server.
    Although if you feel enthusiastic you can try later version of node. Maybe I'm missing something...
2. clone git repos:
git clone https://github.com/killerstorm/bitcoinjs-server.git
git clone https://github.com/killerstorm/bitcoinjs-gui.git --recursive
git clone https://github.com/killerstorm/node-bitcoin-exit.git --recursive
git clone https://github.com/killerstorm/bitcoin-tx-spent-db.git

For bitcoin-tx-spent-db, make sure you're on branch extra, and if you already cloned it before you need to wipe some commits, sorry:

git reset --hard refs/remotes/origin/extra

2. install bitcoinjs-server as described here: https://github.com/bitcoinjs/bitcoinjs-server/wiki/Installation
3. launch bitcoinjs-server:
3.1. launch bitcoind -testnet, it seriously speeds up blockchain download for some reason
3.2. run bitcoinjs run --testnet, once it initializes hit ctrl-c and edit ~/.bitcoinjs/testnet/settings.js:
        add cfg.verifyScripts = false; to the end
        set cfg.jsonrpc.password = "admin"; and cfg.jsonrpc.enable = true;
3.3. copy ~/.bitcoinjs/testnet/settings.js to ~/.bitcoinjs/settings.js
3.4. now you can run bitcoinjs run --tesnet and let it download blockchain

4. copy bitcoinjs-gui/config/config.sample.js to bitcoinjs-gui/config/config.js and edit exitNodeHost
    ln -s ~/bitcoinjs-gui ~/node-bitcoin-exit/public

5. in node-bitcoin-exit:
   npm link bitcoinjs
   npm install

6. stop bitcoinjs, in node-bitcoin-exit run `node server.js --testnet`
7.in bitcoin-tx-spend-db, npm install and then run `node app.js`
8. it should work now, point browser to http://localhost:3125/index.html

Note that even though it is on testnet, it shows mainnet address, so it won't properly.

To fix this, edit 7th line of bitcoinjs-gui/scripts/vendor/bitcoinjs-lib/src/address.js

  this.version = 0x6f;

(Yep, it should be automatic, in theory, but nobody bothered to implement it...
I'm not even sure you can detect whether it is testnet in context of bitcoinjs-lib...)

---

First, we need a better name... Original author called it webcoin, I like it. But I guess we need to distinguish it...
Maybe WebcoinX?

I'm going to try issue tracker-driven process:

1. tasks will be posted to issue tracker. it includes bounty amount
2. if you want to do it, assign it to yourself
3. write code, commit it to your repo
4. include your bitcoin address in commit's comment
5. notify me
6. after your commit is reviewed and incorporated, bounty will be paid to your address

We are going to try github's issue tracker for the start. Since project is spread over many repositories, it won't be issue tracker associated with a concrete repo, but instead this one:

https://github.com/bitcoinx/colored-coin-tools/issues

Should you use pull requests? Well, I don't see value in them, just write an issue comment, notify me over email or something.
If you are a big fan of pull requests, I don't mind.

Repositories hosted on https://github.com/killerstorm/ account should be considered dev branches
Repositories hosted on https://github.com/bitcoinx/ will be more like a stable branch.

Policy:
We need to develop this software as fast as possible, so it is not acceptable to grab task for a long time and make no progress, as it will slow down progress of a whole project.
So, please, grab an issue right before you start working on it. If it takes a lot of time, or you cannot work on it anymore for some reason, consider releasing it so other can grab. If not sure, write a comment. Release partial code.

If there is anything which doesn't fit to a particular issue, please post a message to this list, or write to me personally.
Discussion of code architecture, refactoring etc. is welcome.

If you think bounty is too low, notify me, I'll bump it upward, no problem.

It is possible to make a special arrangement to take ownership of a part of a code base.
It will make it easier to do refactoring in that area without going through issue tracker.

If github isn't adequate for this stuff we'll try something else.

i'll check this out over the weekend.
see if there is anywhere i can contribute.

Demo is running at:

http://webcoinx.tumak.cz/index.html

Chrome only (lots of debug console).

You'll need to use armory to issue yourself a color and add it as /colordefs/<colorid>.colordef in settings dialog. The web wallet is able to handle the rest (sending, receiving, color balances & tx sheet). Or simply post your testnet address and i'll hook you up :)

It is possible to issue colored coins without ArmoryX:

1. Send coins to yourself, for example, to webcoin wallet from testnet faucet (e.g. http://testnet.mojocoin.com/ )
2. Find transaction hash (in webcoin you can click button  in tx view and it shows you txhash there)
3. Find output index of output which belongs to you. Unfortunately, http://blockexplorer.com/testnet shows transactions only after they are included into blocks, but our own block explorer can show them immediately:
  http://devel.hz.udoidio.info:3334/bexplo.html
  (Ignore color definition form field, paste tx hash and click show. you can find your output by value it is supposed to have. Note that it shows value in satoshis.)
4. Use this form to generate color definition: http://btx.udoidio.info:8080/
    Name is up to your taste,
    unit is number of satoshis per unit of currency, for example 1.
    In textarea write txhash and outindex like this:

    df6b2f7bc5562b1209ba4b42ae2b0925e363bcb62962dfde50d694dc08b7b1d8:1
    Public key is not needed.
5. After you click submit, it will show you color ID and link to color definition file.
6. If you indend to use it for Webcoin, you only need colorid, go to Webcoin (logo)->Settings->Color settings, add it as /colordefs/<colorid>.colordef
7. You now can see your balance in colored coins are issued. (Use a dropdown menu to switch.)
8. Don't forget that when you send colored coins, recipient should have color definition installed BEFORE he receives them, otherwise coins might get lost.

Some users reported all balances disappearing after transactions get confirmed in a block. This is bug in bitcoinjs (yet to be tracked down) unrelated to bitcoinx. Once this happens, only remedy at the moment is to generate new wallet.

when i first started working with bitcoinjs this was a very troubling bug (lost more than few btc -- back when they were $12). it occurs when the server is restarted and/or when the tx cache is cleared.

take a look at the storage.js file (towards the end)


can be change to:


basically, it was only reading the last input

iirc this will fix that bug and ALL coins will automagically reappear ;D
that is unless you've deleted your wallet from the browser's storage in which case you're sol
even if you created a new wallet, the old one should still be there, just not active
let me know if you need help recovering any coins

edit: oh wait, you're running on testnet. so i guess its not a big deal

I already fixed this one, but I think there is another bug in getAffectedTransactions(): it only returns hashes for one addressm hashes for other addresses are forgotten. (Check how hashes are passed in steps.)

huh, i vaguely remember that issue, but if i recall it was a problem with the exit node (in pubkeys.js), not with the server directly.

to be quite honest, i ran into so many issues with storage.js (or i just couldn't make sense of it) that i ended up re-writting the file from scratch. i'm now using async vs. step.

my development branch is a total mess right now as i'm experimenting with too many different things, however, I can review the code on my prod server and see if anything rings a bell. iirc it was a quick fix

Bug seems to be fixed:

https://github.com/katuma/bitcoinjs-server/commit/5bc47f6db270ccdf35026446df4db27164cf4ae6

Thanks to killerstorm for pointing out. At this point the web client seems to be solid, just did couple of dozen transactions without glitches. Cleaned up code for pull to bitcoinx repos & step by step guide how to deploy it will be released soon.

Just heads up, service is down for the moment, color server @

http://btx.udoidio.info:8080/static/colordefs

seems to be offline. Killerstorm?

Now that flattr accepting funding through bitcoin have you thought of setting up a flattr profile for the projects.  So that the projects can receive regular funding.  I'd be happy to set up a subscription.

Our main developer (tumak) disappeared about 1 month ago.

We have quite functional prototype:

code: https://github.com/bitcoinx/webcoinx
demo: http://bitcoinx.github.io/webcoinx/

but it has many deficiencies, so both core and user interface need to be refactored/rewritten.

We are looking for developer(s) willing to take over development of colored coin web client and make it into a solid, stable product. (It won't be cut into multiple bounties, at least not at early stages.)

I'm mainly concerned about core part, i.e. one which implements wallet, coloring, transaction handling etc.

So we are looking mostly for candidates who

• understand Bitcoin and Bitcoin-related cryptography (hashes, public/private keys, signing etc.)
• understands security, i.e. is able to prevent problems which can lead to loss
• has good 'software architect' skills, i.e. can organize code in such a way that parts will work well with each other, but offer great flexibility

Finding front-end developers is of lower priority.

Server side won't be implemented in JS, instead we'll use electrum-server with some colored coin-specific modifications. I'll be responsible for server side.

If you are interested, please contact me so we can discuss details.

1. Flattr doesn't pay in Bitcoins, as far as I can tell
2. Do you think such funding will be significant?
3. I really don't mind, but I'm not responsible for the web site (I'm responsible for everything else, LOL). So if you want to proceed with this I recommend using 1) contact form on http://www.bitcoinx.org/ 2) new web site is being planned, you can contact Amos in this regard (see mailing list)