Topic: [BOUNTY] 200 BTC for lightweight colored coin client(s) - page 2. (Read 10684 times)

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

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

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

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? 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 on the amount of data you can save in local storage. so even a spv client may have problems.


absolutely! 

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.

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.

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

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 and here)


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!

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?

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

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.

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.


Thanks, that would be cool!

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.

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

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.

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.

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

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.

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

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