FWIW I posted about consecutive miners fees (and the whole bank idea) months ago to the forums and bitcoin dev email list and didn't pursue it because of the risk that the txs wouldn't be consecutive, as well as the size. The tx-in-tx idea is what made me think it was practical without just destroying coins.

I notice that you are tying the identity to the pubkeys signing the txins. An additional problem to this is the pack of transferability means that key compromise is not recoverable. You also limit the granularity to the minimum fees, which will be much larger in the future.

What I've been working on ties the contract the bond holder is promising to oblige to to the sacrifice tx. Now you have something like one of jgarzik and others bonds, and the bonds can be moved around. For, say, a wiki the contract can be as simple as "I promise not to spam" Proving fraud the. Requires an affected service to put a timestamped proof of spam - which can be just a signature if the service is trusted - in a public place. Buyers of the bond then need to walk the tx chain back to the source, checking that public place for valid fraud notices.

I've got a write up on this almost finished; I'll post it tonight or tomorrow when I get home.

Often coding actually takes less time to solve a problem than just thinking, because by coding you let the computer help you find out if you are wrong much faster than trying to use reason to determine if you are wrong.

Has anyone tried this on testnet yet?

EDIT: and while we're at it, you realize how you're going direct to disclosing this in public, right at a time when Avalon ASIC boxes are being shipped that can mine a block every 2 days on average? Frankly I think this is rather irresponsible of you. I did the whole responsible disclosure process for the silly little nLockTime oversight I found, and here you are putting everything in public for a problem that's potentially far more serious. The dev team could have easily snuck a fix into the upcoming 0.8 release.

As an example 157i5gK7iN4bNAN39Ahuoiq6Tx5TaQukTE is owned by Hal, who has publicly confirmed that he still has access to the private key. Last substantial transaction, June 2011.

The reality is we just don't know for sure how many lost coins are out there.

I actually really like this idea. Now I do think we'll find that sending fees to charities and other specific entities will turn out to be a very bad idea for applications that need the highest security, but equally there are applications that don't need the security. Aside from that there is the disadvantage that your proof becomes quite large the transaction spending the money now has a bunch of outputs.

However, if this is a popular idea, you can fix that with multisig addresses. Have the 20-odd or whatever charities get together, submit all their private keys, and create a multisig address only spendable when they all co-operate. (or some subset of the total) They'll probably agree to split the money evenly, but in any case, that's up to them to decide. There is the issue that multisig with more than 3 parties isn't supported, the resulting transactions become large, but you can use a non-P2SH secret sharing system too resulting in just one signature.

The best part of the secret sharing design is it will result in just one address like any other, so it'll still be compatible with the "donate to a single charity" functionality. Just make sure that the specification is written in terms of scriptPubKeys rather than addresses and you can handle any case going forward.

That's pretty much it, although FWIW the particularly odd scriptPubKey posted above, "OP_IFDUP OP_IF OP_2SWAP OP_VERIFY OP_2OVER OP_DEPTH", was actually created by an old bug in P2Pool where one of the scriptPubKeys was being set to the data "script" rather than a proper serialized script. The "OP_IFDUP" etc. happens to be what that string decodes to in op-codes. The bug has been long since fixed, but the OP did mention they mined at p2pool some time ago.

They are enabled already on Testnet so you can try your experiments there.

Not at all. Remember that the modified transaction still goes to the same place, so SD still gets their money. SD just needs to stop paying out twice when it sees two transactions spending the same input.

Re-read my last point at the bottom about undetectable forms of malleability, and keep in mind it's only an issue because players communicate with SD via the blockchain, and the blockchain is public.

Just to re-iterate: this kind of modification, transaction malleability, is something that can be done by miners without the person who submitted the transaction even knowing. In other words that "high-roller" may not have had anything to do with the double-spend at all.

It's especially ugly because an evil miner can simply watch the mempool for all losing satoshi-dice transactions, and then modify every one of them and attempt to mine a block filled with now-modified transactions. Of course the miner doesn't know satoshidice's secret, so they can't pick winners or losers - they are essentially rolling the dice again - but for every game with a win probability of p your new win probability will be p + p^2. For instance if you bet on a 50% chance game, you'll now have a 75% chance of winning. On a 25% chance, you'll now have 37.5% chance.

In fact, it can be done by a non-miner who is well connected too: again, watch for satoshidice wins, and this time use a form of transaction malleability that is a standard transaction and thus will be relayed by other nodes. Now immediately broadcast the modified transaction to as many nodes as you can. The vast majority of the time nothing will happen - the modified tx won't be accepted because nodes already have the original - but every once in awhile it will happen to be accepted by a miner and get confirmed.

A simple way to fix this issue would be to first only accept bet transactions whose inputs are confirmed, and secondly change the lucky number algorithm from hmac_sha512(secert,txid:out_idx) to hmac_sha512(secert,txin_1:out_idx | txin_2:out_idx ... | txin_n:out_idx) This works because the betting transaction refers to the txin's by hash, so if you change the betting transaction hash, the lucky number doesn't change, on the other hand the txin's are already confirmed in the chain and can't be changed. Note that you'll need to ensure the SIGHASH bits in the signatures are their standard value; ANYONECANPAY still allows changing the txin set without invalidating the signatures. Of course regular double-spends are still possible, but at least they can't be done by a third party.

Note that having the txin's be confirmed is essential: if they aren't you can pull an even worse version of the same trick by modifying the txin hash, thus invalidating the bet transaction.

EDIT: While we're at it, I also noticed that satoshidice is accepting transactions with non-default SIGHASH's for the signatures. For instance I just made bde69c82fa0870bb156edb334da4a8013d5d385e93608110313a8695184d6365 with the signature using SINGLE|ANYONECANPAY, which means any node on the network is free to add their own inputs and outputs to the transaction provided they do not modify the one input and one output I signed, again changing the tx hash. It's a more minor issue, but it would allow people to setup co-operating decentralized double-spenders without even having to communicate what transactions to double-spend too.

EDIT2: The really interesting thing would be to come up with a form of malleability that is undetectable after the fact. Satoshidice could also just not transmit wins when the second, winning, transaction gets mined. They can prove their honestly by just pointing out that the second tx was modified, and the first was normal. However if you can come up with a form of malleability where both transactions are indistinguishable there will be know way of knowing if the miner turned a win to a loss or vice-versa, and hence satoshidice doesn't have much choice other than paying out the wins. At this point they simply have to change the way wins are calculated.

I know about chronobit and knew about it before I started my project - it's clever but it's not a good solution. As you know it works by getting the digest into the P2Pool share chain. The problem is the length of the chain from your share to the blockchain proper is hundreds or thousands of shares, which means a self-contained timestamp is huge - the included sample proof is 475KiB of data.

You also do not get any better precision. P2Pool shares do contain timestamps, but the timestamps follow the same 2 hour rule that Bitcoin proper does. Of course you could try counting the number of shares and multiplying by the average share time, but that doesn't work either as there isn't any way to know if the share chain ending in a Bitcoin block is actually a real p2pool share chain because old shares in the chain are discarded, and it's impractical to store every share ever made. It might be possible to convince forrest to make the p2pool chain an incremental merkle tree so that paths from the chain to a block are short, but you certainly won't be able to convince him to tighten up the 2 hour rule. We've discussed that on the forums before, and any tighter than 2 hours means mining is dependent on centralized timesources, unacceptable.

Note how the need for trust makes existing timestamping useless for anything anonymous, or even just that some large entity doesn't like; Satoshidice timestamped their secrets on the blockchain for a reason.

Lots of demand, which is why guardtime, Surety and a bunch of other services exist. On the other hand, I'd argue that what those people are selling isn't timestamping, it's lawyers. Specifically the legal frameworks to convince juries and judges in court cases that the timestamps were valid. The actual mechanism is secondary. The clients are specific, regulated markets such as digital evidence, medical trials etc. Note how services not targetting those markets, like CertTime, (graphics designers, now closed) haven't done so well.


Yup, CA's supporting RFC3161 or Authenticode are common.


Frankly trust is a big one. RFC3161 and Authenticode are pure "signature-only" timestamps that trust the issuer %100; they don't even have hash-chain-based logging to reduce fraud. (guardtime does this, but it's expensive) Scalability is also a problem: they need n units of server capacity for n timestamps, and the secure hardware running the servers is expensive; all the CA-run servers heavily rate-limit and will ban you if you try to use them in an automated way. This means isn't a free way to timestamp, say, log files as they come in, git revision id's, or say archive.org's webcrawler. Scalability is actually a big part of why I wrote OpenTimestamps: even without the blockchain it'd make timestamping with centralized servers much more usable.


You can say that for timestamping in general... What a timestamp does security-wise is tricky to understand and use to make something else secure. It's precisely why I thought I could make a masters out of the subject, and a masters that I could actually do at the industrial design department at the art school I got my degree at.


There is a lot of truth to that statement: look at how few RFC3161 implementations there are in the open source world and how there isn't a single package in the Ubuntu or Debian repositories related to timestamping at all. Having said that I think this is because all the existing solutions come from the commercial world of regulated industries and require central services that must be trusted %100 - anathema to open-source philosophy, and more practically, difficult to use because of the need to keep track of revocation lists and other on-going maintenance.

As for chronobit, like Gavin said about ease of use, why would you use something that requires dedicated mining hardware running for a few hours to make a single timestamp when you could bloat the txout set instead? It's bloody inconvenient, and on top of that the resulting timestamps are huge because they depend on P2Pool's linear block chain. (note that without a link to the Bitcoin blockchain the P2Pool timestamp is worthless, and additionally P2Pool follows Bitcoin's 2 hour rule so your resolution isn't any better) It's the same problem with coinbase timestamping: if you implemented it on just Eligius - as Luke graciously offered - it'll easily take a day or two before your timestamp gets into the blockchain. Even just having to wait up to an hour (what I've written) is problematic enough because you really need a server-side mechanism to later send the completed timestamp or the client, or maintain something like a 1s resolution calendar database for later retrieval by the client. (this is how guardtime works)

Ultimately the big thing you're up against is whatever solution you come up with has to be less expensive, in fees and in whatever else the user wants, than the fee to create a transaction. I also suspect that if we do nothing people will gradually find useful things to do with blockchain timestamping, and there's no guarantee the application that does find traction does it right. The dash-cam example above is a good, and scary, example as dash-cam's are really popular in some parts of the world.


The obvious way to do it - a pure chain with timestamps - is unlikely to work because you probably won't be able to get enough hash power to trust it by itself. Now the shares that make it to the Bitcoin blockchain directly can be trusted but you're back to the "takes a few hours" problem. That said an alt-chain might be part of a protocol to do P2P co-operative timestamping.

I started working on mine last June, and went through three designs before I settled on a core structure that I liked. I also was thinking I might be able to write it up as a masters thesis. ("it" as in a complete system including actual applications, good UI's, etc. more of a masters in UI design than cryptography really)

But it still has the "O(n)" problem in that once released people will start running their own servers - n of them - rather than using efficient centralized ones. I was hoping to design a workable, DDoS resistant way of creating a P2P co-operative network for building up the merkle tree that actually gets timestamped, preferably in a coinbase tx, but I haven't figured that part out yet.

Still, as I said above, if people are actually doing blockchain bloating timestamping already, maybe I should just release what I have... I don't mean to offend apetersson, but your bitnotar app really worries me.

Mine is a much more generalized system. The core is a generalized mechanism that takes digests and applies operations to them to produce other digests. Provided the series of operations is one-way, you know that any mechanism that has timestamped the resulting digest, implies every other digest in the chain is also timestamped. To support structures like merkle trees there is code that operates on directed-acyclic-graphs of these operations, and further more code to maintain various merkle tree structures efficiently. It's generalized enough that the whole blockchain can be represented within the system, as well as alt-chains and a whole bunch of other stuff. The actual timestamping mechanism is then called a "notary method" and Bitcoin is just one of many possible ones.

The Bitcoin-specific stuff I have implemented uses multi-sig transactions. For each timestamp I create a transaction spending an input, usually an earlier timestamp, with a scriptPubKey consisting of a bare 1-of-2 CHECKMULTISIG. One of the pubkeys is a real 33-byte compressed pubkey, and the other is just the digest to be timestamped. Thus per digest you just need a single transaction about 200 bytes in size, and again the output is spent and thus prunable. Equally you can use coinbase transactions, and because of the flexibility the client software doesn't care. Each timestamp also includes the merkle path all the way up to the block header itself, so you verify a timestamp you just check that the block header hash is a valid block; this can be done efficiently without the full block chain by SPV clients. You also don't need to implement any ECDSA crypto operations to create or validate these timestamps; just easy SHA256 hashing. An example tx is a467025de01a7707b0f0e3f7bd9ffb94a2eeb02eede115e0dfe4590361655e02

The service I setup just takes submitted digests and builds a merkle tree of them every 10 minutes (currently) and submits the top digest. The intermediate nodes in the tree are saved temporarily for clients to retrieve them once they confirm; I could also email back the timestamps. With the generality you could also use trusted-signature-based stuff like RFC3161 or PGP signing in parallel to Bitcoin to get better timestamp resolution.

I suspect you built your system in significantly less time than I did mine.  

Agreed.


Oh yeah? Where is it? I wrote one too, but haven't promoted it because I want to see if I can get a version going that has a P2P layer of co-operating nodes doing the actual timestamping tx. (coinbase or not) Currently mine only supports a single timestamping server, although it's easy to extend it to multiple redundant servers if the servers have co-operating sysadmins.

If there is demand for this stuff, please let us know and we can get a better solution than polluting the blockchain, and especially creating a bunch of unspent transaction outputs. This won't take much time either; I've already done nearly all the work myself. You have to remember that the total number of unspent outputs will be a really big issue in the future, because while not every validating node needs a full copy of the blockchain, every validating node does need a full copy of the unspent outputs. In addition any solution that needs a transaction per timestamp is also going to be paying fees - prohibitive for the dash-cam example above - while the non-blockchain-bloating solutions will be free to use.

Yup, that's another known attack. bitcoinj is going to support recursive analysis of transaction depth IIRC, so you'd be able to say "don't accept chains more than x long"

Luke is correct above, and you can also simply apply the patch Gavin posted to your 0.7 bitcoind src. I've tested this before - I wrote a slightly different version of the patch a few weeks ago - and it worked fine.


I'd be very interested to know; there are many variations of this attack.

Thanks, it's a much better title!

If Ripple succeeds I think it'll turn out to be much more useful for business-to-business, especially bank-to-bank, money transfers. Businesses and banks are already used to dealing with complex debit/credit relationships, and those relationships tend to have a lot less emotion attached to them. It's also a matter of scale, dealing with the complexity has a minimum fixed overhead cost, but pretty much any medium-sized business has enough accounting knowledge to understand payments. Finally unlike people businesses, especially banks, are far many and far more symmetric relationships with each other. Your average person has one funding source, their job, and a whole bunch of people they owe money too, which gives ripples fancy "who-owes-who" stuff nothing to work on. Meanwhile even a small bank probably will have dozens of relationships moving money in and out, and lots of opportunities to cancel debts within that relationship graph.

Without SSL there is nothing preventing me from offering some free wifi that silently intercepts websites and replaces Bitcoin addresses with my own. With SSL I at least have to get a faked SSL certificate, or hope the user doesn't notice. The former isn't something any random kid in their basement can do, the latter is a problem that is becoming less and less of an issue as UI design and other countermeasures improve. Heck, even the fake SSL certificate problem has countermeasures too, not perfect ones but they can make it pretty hard to pull off the attack.


None of those solutions work well when you want to tell your friend over the phone. People just aren't going to go to the effort. In addition making the ID pronounceable only helps if you run the ID through a key derivation function so that it's difficult to generate collisions where most of the "human-comparable data" in the "humanized" representation of the ID matches up. This approach doesn't work for the majority of use-cases because your attacker can spend far, far more effort trying to find a colliding pronounceable ID than the user can in running the key derivation function to check the pronounceable ID.


What if I just saw some ad on the subway I vaguely remember for some product that none of my friends know about?


It may be how people shop around, but they don't go off and copy-and-paste long cryptographic identities while they're doing that. People want to be able to use something short and they expect that the honest vendors website is going to be the one at the top of the Google search results. SSL provides this already with pretty decent, if far from perfect, security.