[BOUNTY] 200 BTC for lightweight colored coin client(s)

[killerstorm]

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.

[1715059110]

1715059110

[1715059110]

1715059110

[1715059110]

1715059110

[1715059110]

1715059110

[1715059110]

1715059110

[killerstorm]

• Needs the ability to "install" a color: User needs to be able to upload a color definition 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.

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.

You say you've worked it into your Armory client fork, but I'm not seeing a reference to the original protocol.

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

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.

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...

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.

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.

[Zeilap]

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...

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.

   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.

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?

[killerstorm]

For best-first, how would you decide which node is going to be best?

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.)

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.

Exactly.

Apart from this, you pretty much have to search everything - in which case it doesn't matter which order you do it in.

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.

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?

Hard part is getting everything to work together

[Zeilap]

For best-first, how would you decide which node is going to be best?

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.)

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.

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.

Exactly.

Apart from this, you pretty much have to search everything - in which case it doesn't matter which order you do it in.

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

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. 

[Red Emerald]

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.

[killerstorm]

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.

[killerstorm]

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.

[killerstorm]

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.

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.

[killerstorm]

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. 

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.

[Zeilap]

Vitalik is going to port DFS coloring to JS.

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 with the result from the api https://blockchain.info/rawtx/29845514

Code:

{
  inputs: 
  [ { prev_out: 
     { n: 1,
       value: 3000000,
       addr: '16v13Fa9cPmfFzpm9mmbWwAkXY4gyY6uh4',
       tx_index: 29627934,
       type: 0 } },
  { prev_out: 
     { n: 1,
       value: 3600000000,
       addr: '1GPwJvMpB4vJPuMwHs9JDAZm9Lh66Y2qnS',
       tx_index: 29776308,
       type: 0 } } ]

  hash: 'd10d7127366229b341a559ddf83b53b9ac6c1b2ca792cb2e81edaf7a595d763b',
  vin_sz: 3
}

Notice vin_sz = 3, but inputs size is 2. The second input is actually 2 inputs of 2btc and 34btc.

[Red Emerald]

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.

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.

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.

[killerstorm]

Vitalik is going to port DFS coloring to JS.

Ah crap, I should have spoken sooner.

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.

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.

Wow, that's weird.

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

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

[Zeilap]

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

Details?

Also, test vectors?

[killerstorm]

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

Details?

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.

Also, test vectors?

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...

[killerstorm]

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.

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

[killerstorm]

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.

[nyusternie]

   (This is what I'm doing now, but there is a problem with dtocoinbase db, so I cannot proceed.)

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

[killerstorm]

   (This is what I'm doing now, but there is a problem with dtocoinbase db, so I cannot proceed.)

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.

[killerstorm]

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:

Code:

node color.js

Basically these things (block explorer, brainwallet, bitcoinjs-gui) can just call getColor function:

Code:

function getColor(txHash, outputIdx, callback) 

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.