But where's the incentive for a miner to do this? Perhaps it is cheap enough to do this today, but as the tx volume grows it quickly becomes a significant cost, both in terms of computation power and bandwidth. And what is the punishment if a miner signs a tx and then reneges and mines an alternate version (perhaps because it includes a larger tx fee?)

Thanks guys. That's pretty much what I concluded, namely that we can prune txs ourselves, but never accept pruned blocks from (untrusted) others.   

But, if this is the use case, surely we can prune far more aggressively? Once a block is verified and sufficiently old we can drop all spent transactions in it, as well as the inputs of all the unspent transactions, without retaining so much as a hash.

This breaks our ability to prove (via the merkle branch) that the remaining unspent transactions were in the block in the first place, but we have already verified this, so unless we don't trust our past selves, there is no need to retain the proof.

The only capability that we lose relative to someone who prunes according to the recommended mechanism, is the ability to provide a third party with the details of old unspent transactions as well as the Merkle branches that links them to the block that they appeared in. But, if we assume, (as implementations that prune inevitably do) that someone else is retaining the unpruned history, this is hardly an issue, since the enquirer can simply get the proof that they seek from the unnamed someone?

Hi all.

I used to think that I understood how tx pruning works. However, I recently realised that there is an important question which I cannot seem to answer. I understand how the merkle tree can allow us to verify the block hash even when most or all of the txs in the block have been pruned.

What I do not understand is how we can be sure that unpruned txs are unspent in the presence of pruning. To give an example let's assume a tx history like this
In block 1 - A mines 50 BTC
In block 2 - A pays 50 BTC to B.
In block 3 - B pays 50 BTC to C.

Normally these three txs form an unbroken chain from the unspent output (in C's hands) all the way back to the coinbase tx. If we start pruning txs and tx 3 is unspent and buried under enough blocks we may prune txs 1 & 2. Now the only thing that a new node that downloads the block chain sees is

block 1 - txs pruned but merkle tree can be used to verify hash
block 2 - txs pruned but merkle tree can be used to verify hash
block 3 - B pays 50 BTC to C.

We can no longer verify the history of B's coins all the way back to coinbase, but we can see that the network accepted the payment at the time, so it must be valid. However, what if a malicious attacker sends us the following history.

block 1 - A mines 50 BTC.
block 2 - txs pruned but merkle tree can be used to verify hash.
block 3 - B pays 50 BTC to C.

All the hashes check out, and the blockchain is intact, so we have no reason to reject this history. But according to this it would appear as if both A and C have 50 BTC to spend (After all the pruned tx in block 2 may been "Z pays 50 BTC to B" for all I know). If we are then sent a tx where A pays the 50 BTC to D we would accept it and unwittingly assist in a double spending attack on the network by attempting to mine a block that contains this fraudulent tx.

In Satoshi's own words : "The only way to confirm the absence of a transaction is to be aware of all transactions." Transaction pruning appears to contradict this principle. All is fine if I am pruning the transactions myself after having downloaded the unpruned block chain and verified it fully. But if I am accepting a pruned chain from another node, both versions of the tx history shown above are equally believable and I have no way of knowing which is genuine.

I am sure there must be a (simple?) answer to this but I cannot seem to grasp it. Please clarify.



     

Hi coblee.

I'm afraid you don't seem to have understood my proposal. The trade involves no third party and everything is still decentralised. The nice property that anyone can implement a website (or client) that provides the exact same service is retained. The only thing that changes is that it becomes possible, but not required, to sell or gift your alias or buy one from someone else. If you don't sell your alias, then it won't ever change.

H

Cool. I thought it would still be early enough to make non-breaking changes to the algorithm (are there allready many other implementations out there?) and didn't think you would be in favour of other flavours of the firstbits idea due to the risk of confusion that you mention.

But if you are not opposed to the idea, I think I might have a go at coding a transferable decentralised address alias. Might I push my luck and ask if you would be willing to opensource the firstbits code? Would make a really nice starting point. 

I believe he is called Satoshi  . As pointed out before on this thread, that's the firstbits address of the wallet that received the coinbase payment from the genesis block. If you could transfer wallets, that would be a valuable one indeed for collectors, akin to the first dollar ever printed.

I've thought about my own proposal for signalling transfer of a firstbits alias a little more and realised a couple of things. It's not required to burn any money in order to generate a unique signaling transaction. Something as simple as inserting a NOP instruction into the pubkey script would make it distinguishable from an ordinary payment without making it impossible to spend the output. A better solution would be to use the OP_DROP instruction and include some data that indicates that this is a transfer.

Even though it is possible to do this without burning money, it may still be better to structure the tx in such a way that the output can't ever be spent, but not for the reason I thought before. The real reason is that if the output is spent, then future versions of the client may well prune this tx from the blockchain, eradicating all record of the transfer and causing the alias to revert to its original owner.

In addition, the proposed scheme effectively only verifies that the current owner of the alias is willing to transfer it, but not that the new owner is willing to receive it. You would be unhappy if 1pervert suddenly started resolving to your publicly known donation address.

So, my updated suggestion is as follows.

The buyer and seller of the alias agree on the price. The buyer then generates a normal payment tx for the agreed amount with some additional data inserted in the pubkey script using OP_DROP, marking it as an alias request. He does not yet transmit the tx on the network, but sends the hash of the tx to the seller (specifically to the key that currently has the alias he wants). The seller generates another payment tx using the hash that was sent to him as the input and sending 1 satoshi to the buyer's address using a crippled pubkey script so the output can never be claimed and the remainder to himself using a normal script. He then sends this tx to the buyer who verifies that everything is as expected and releases both txs onto the network. The firstbits algorithm recognizes this pattern on the blockchain and the alias(es) now resolve to the buyers address.

This sells the alias directly from seller to buyer without requiring trust or escrow.

Comments?

Good suggestion. Two remarks.
 
Firstly, note that it gets progressively more risky every time the wallet is passed on, since any or all of the previous owners may try to grab your income. For an account with an fb alias like 1poker or 1bank that may be sold several times and is likely to ultimately handle large amounts of transactions this is completely unacceptable.

Secondly, this can easily get very expensive in terms of transaction fees, since you will always be shifting recently received cash and some of the received txs may well be small.

Yes, you could, but, as mentioned in my post there is no way for the recipient to know that you haven't kept a copy for yourself. Only a fool would accept it.

The typo on addressess is ironic in the context.

I simply mean a firstbits address where more than the minimum number of characters are supplied as has been repeatedly suggested in this thread in order to obtain some protection against typoz.


Indeed a single character provides pretty good protection. I would want to have the checksum as a postfix rather than a prefix, simply because it is optional and it is more intuitive to drop a postfix than a prefix. Any checksum scheme where there are 35 possibilities wil provide a 97% chance of detecting an error so the last character is by no means special. Where the schemes differ is in their ability to detect common errors. The scheme I suggested can detect 100% of single character substitutions. I realized since that it does not handle all single character additions and deletions and detects no transposition errors. This is pretty damn bad. A better suggestion would be something similar to the ISBN scheme that can detect all single character substitutions and transpositions. ISBN has the advantage that unlike firstbits it is dealing with a fixed length payload, so it doesn't need to worry about insertions or deletions.


Good for you. This is why it's optional. Use it, don't use it.


Implying that you consider the solution I proposed to be impractical. Care to elaborate?

As to "problem" and "nor is it eager to be solved". Again, if it doesn't affect you, good for you. Others feel different, grant them some space.

What makes firstbits great is the fact that there is no centralized database. The blockchain is the database and it is by definition impossible to delete something that has been confirmed by enough blocks from the blockchain. So to transfer ownership one has to enter a "redirect" tx into the blockchain.

First up, thanks to FreeMoney and SgtSpike.This is awesome.

Then I would like to make two suggestions. The first relates to the checksum discussion. It is important to note that simply extending the firstbits name beyond the minimum required characters is NOT the same as a traditional checksum. Where a standard 1 character checksum is sufficient to detect any single character typo, this does not hold for extended firstbits adressess. The 1 character extended 1kk5k address is 1kk5kf. If this is mistyped as 1kk5kg it may well point to another valid address. It doesn't today, but it could. In this case the typo was actually in the "checksum" meaning that you end up worse off than you would have been had you just quoted 1kk5k as your address.

A simple way to add a (still optional) checksum would be to use a separator followed by a traditional checksum i.e. 1kk5k-A or something similar. One simple implementation would be to ensure that the sum of the characters (when interpreted as digits in a base 36 system) adds to 0 modulo 36, But you could also have multi-character checksums that can detect more elaborate typos.

Once something like this is in place, I see no reason why this shouldn't be in the mainline client. It may initially refuse to accept firstbits adresses without checksums and later allow one to bypass this rule if you click through enough "are you SURE SURE SURE" dialogs.


I can hardly believe that this hasn't been discussed more. If the discussion is elsewhere please point me to it.

Vanity addresses and the firstbits algorithm make for a potent combination. If you think 1kk5k was easy to remember, try 1spike (or even 1spike-AX since you don't really have to "remember" spike the "additional" load of remembering the checksum suddenly seems even more trivial).

The only hassle today is that there is currently no way to transfer ownership of such an address. I don't own 1Linux, but if I did, I might be willing to sell said address to BkkCoins if the price was right . Today the only mechanism to do that is to send him the private key, but he would be a fool to accept such a deal since I may well have kept a copy of the key and be in a position to steal any funds he subsequently receives.

I am pretty sure that this can be added to the existing algorithm without any breaking changes (i.e. if 1linux or 1kk5k or whatever belonged to you before it is guaranteed to still belong to you unless you choose to dispose of it). One way of doing this would be to do the lookup as before, but once the address is found to check all subsequent transactions from that address for one that matches a to be determined arbitrary pattern. If such a match is found then the destination of that address becomes the new owner of the firstbits address in question. Rinse and repeat. This is slightly more computationally expensive than the existing algo, but no one is doing millons of firstbits lookups per second are they?

One example of a pattern that may signify a transfer of ownership is a payment from 1linuxdhfgf... to 1linuxtrsyudas.. of EXACTLY 123 satoshis. The amount should be very small and chosen in such a way that no such payments allready exists in the blockchain (so no-one has accidentally transferred ownership of their firstbits alias while trying to buy coffee  ).

This is just an example to clarify the concept and not suitable for actual use because it leaves open the possibility that someone may in future transfer a firstbits alias without intending to, either due to an incredible coincidence or because they were actively tricked. A better solution would be to use the pubsig script as an indicator. An otherwise nonsensical script can be used as an indicator that 1stbits ownership is being transferred. It has the downside that some BTC is being burnt (since it would be impossible to claim that output of the tx) but I don't think anyone is going to miss a few satoshis  . On the upside, one would need a special client to transfer alias ownership so no aliases would be transferred by accident.

If this was implemented we would suddenly have a market for firstbits aliases and hopefully I can sell 1Hannes to one of the many billionares out there with Hannes as a first name  . The only downsides that I can see is the slight increase in computational complexity of a lookup (as mentioned before) and the fact that if one does a firstbits lookup under the new standard one really needs to be online and up to date with the blockchain (allthough you would be able to get away with an offline lookup 99.9999% of the time).

In my original example I showed transfer of ownership of the 1linux alias from 1linuxdhfgf... to 1linuxtrsyudas.. but one could debate whether the second address needs to start with 1linux at all. If it didn't then we would have a marketplace even for firstbits aliases that have not yet been claimed. I would like 1HannesNaude but don't have access to the ridiculous amounts of hashpower I would need to generate it myself. But for anyone that is already running vanitygen the cost of adding it to their patterns list is close to zero. If it was in everyone's pattern lists because everyone knew that I would pay a million BTC for it , it would almost certainly be generated within a day.

Obviously anyone can introduce either of these suggestions, but I really believe it would be best if the firstbits originators did it. Then there would be no confusion or competing standards. Also this is much easier to do now while there is really only a single implementation to adapt than later when many clients and e-wallets have implemented firstbits and lots of code needs to be updated.

Yes, I did think of this. I partly agree with you, but suspect that dropping the creation rate to zero may be good enough, since currency is continually being lost. This shrinkage in the money supply may be small, but in the absence of fundamental security concerns with the currency, given enough time it will bring the value back to the targeted level. The expectation that the currency will eventually return to its targeted value becomes a self fulfilling prophecy as some traders are always to keen to buy below this value. This means that the value bounces a lot sooner than what would otherwise have been the case.

Of course if there are fundamental concerns with the security of the currency (i.e. someone may be able to create more currency at will, break private keys gaining control over the funds of others or double spend) then no "long term" peg will save it, since traders don't expect that there will be a long term.


Your last sentence here raises a very important point that I have not considered. If a drop in the value of the currency, is accompanied by a drop in the supply rate as is proposed here, miners are hit with a double whammy. If enough miners withdraw, the reduction in difficulty may lead to security concerns, leading to a further reduction in value and a nasty positive feedback loop ensues that drives the value to zero.

The solution to this, is that it is critical that it must be possible to cross-mine this currency with other crypto-currencies. Withdrawing from a cross mined currency only makes sense if the sum of currency mined from all mined currencies falls to below the miner's running costs. Therefore as long as one or more of the other crypto-currencies is going strong, miners will not withdraw.

So, you're saying that it is undesirable. Errrmm

Not sure if I mentioned this before  , but I understand that it is undesirable. In fact I went as far as to call it an attack on BTC. What I'm wondering is whether such an attack could succeed (at devaluing bitcoins).

OK. Seems clear that many people have severe difficulty seeing past the ideological implications of what was hypothesized above and answer the actual question: "Irrespective of how undesirable this is, is it possible in principle?" So I came up with an alternative phrasing that may be easier to parse if phrases like "pegging to USD" make your neocortex seize up. 

Hypothetical scenario. 20 years from now. All 21 million bitcoins have been mined. The bitcoin economy has matured and bitcoins have a "stable" value in the sense that they don't vary wildly from day to day but are simply deflating at a fairly constant rate. Now a second blockchain is started up. Lets call these coins BTC2. BTC/BTC2 exchanges exist, but since these exchanges deal only with cryptocurrencies and run on the future version of tor, they are effectively impossible to shut down. The BTC2 network uses the data from these exchanges to vary supply in order to target a parity exchange rate with BTC.

Unless someone can put forward a cogent explanation why this won't work, most people will accept that it will work in the long run. Then few would sell a BTC2 for less than 1 BTC and if someone did it would be quickly snapped up by one or more of the many who would be willing to buy a BTC2 for less than 1 BTC. And similarly for buying a BTC2 for more than 1 BTC.

Would this work? And does it constitute an attack on BTC? If BTC and BTC2 are doomed to trade at parity forever, then any new BTC2s produced are effectively part of the BTC money supply. Any merchant that accepts BTC would accept BTC2 as well and while one network won't honor coins from the other, they would be equivalent in practice. And therefore, if and when large quantities of BTC are produced it would cause both BTC and BTC2 to inflate.

There, now it is stated without any reference to the much despised government money. Now could someone please explain why this won't work.

NOTE: Explaining why something is undesirable and why it won't work is not the same thing. Nukes are undesirable, but they work

Oh FFS. I get so exasperated when people fail to read. OP. FIRST line



OK, bright spark. This is exactly what I was after. Lets assume that this system exists, the coins are trading at 1:1 and the market expects this to continue for the foreseeable future. You are one of the "BTC scalpers". You have significant, but not infinite means. Please explain in detail how you would go about "screwing us all at the touch of a button".

Waiting in anticipation.

Please refer to OP. Specifically :


Firstly if these coins are a globally traded commodity, there will be a single price (up to a small approximation) at any point, just like for any other commodity. If markets are liquid and trading is friction free, the EMH guarantees this. Think of the gold price, oil price etc. If you were to actually go out and try to buy gold you may end up paying a slightly different price, but the difference is far less than 10%.

One argument for why the coins may have greater variation in price than is typical from commodities, is that arbitrage is made more risky by the fact that exchanges are unregulated (The exchange could up and leave with your money).  But if the risk of using unregulated exchanges is so great that no arbitrageur in the world can be tempted to take a 10% instant profit when it is on offer, then we can safely assume that the risk is so great that effectively no-one is using the exchanges.

As far as fees are concerned, any proportional fee can be taken into account resulting in an effective bid and effective ask being reported that allready takes the fee into account. Non-proportional or tiered fees are not as simple to handle, but the variation should still be less than 10%.

As long as there is at least one exchange somewhere in the world trading BTC for fiat, the BTC/USD exchange rate will exist. If for example Mt G*x, TradeHill and B7 are take down, but Bitomat still exists, then the BTC/USD rate is simply BTC/PLN * PLN/USD. If no exchanges exist anywhere, the block chain simply keeps going at some preset reward level. The currency still exists and transactions are still processed, there's just no feedback mechanism. But the expectation that the feedback mechanism will eventually re-emerge, means that there still is a feedback mechanism, namely traders trading on the belief that parity wil be the long term result.


Well I'd argue that in the early days of a cryptocurrency, a stable exchange rate is very desirable. Right now, many merchants are hesitant to accept BTC, purely due to the volatility of the market. At the same time, the BTC economy needs to grow if it is to become less volatile. A chicken and egg situation. I'm betting that BTC will bootstrap itself out of this, but it's not a safe call by any means.

One could design a currency that is initially pegged to some weighted average of fiat currencies, but starts to float freer and freer as time progresses, becoming completely disconnected after a pre-determined block number when the market is judged to be big enough to no longer be vulnerable to pumpers-and-dumpers and other speculators.

Similarly, you could specify that the exchange rate control mechanism only kicks in AFTER block X, since the market for the currency will initially be non-existent. This give exchanges time to arise. At the same time, the expectation that exchange rate feedback will kick in at a known block number will keep rates near the targeted level even prior to that block number.

Yes, I won't verify historical exchange rates. Only when a new block is added that would become the new head of the chain, would I decide whether to accept it or not. Alternatively one could verify the exchange rate in the last 6 blocks (therefore only needing about an hour of historical data). Depending on the bandwidth of your feedback law, data points older than X would be irrelevant anyway.
 
I don't agree that there would be a lot of forking since the NORMAL condition is for everyone to be connected to all of the exchanges and report some average value. Only when there is some network disruption, would some or all miners not be able to access some exchanges. You could have a generous margin for error on what rates you will accept for when things DO go wrong, maybe as much as 10% variation. Arbitrage should keep exchanges closer together than that. With such high noise in the measurement, the control loop will have to be quite loose, but as mentioned before, this doesn't actually matter. Once traders believe that the control law CAN work it won't actually have to work.

I don't want to get bogged down in implementation details, because I have no intention of implementing. If you don't believe it could be done decentralised, then assume for argument's sake that the exchange rate is being reported by one or more trusted entities, similar to how alert messages are provided on the bitcoin network today. They could misreport the exchange rate, but that would mean the end of the currency, since traders would immediately know that they misreported and lose faith in the system. If they are somehow temporarily prevented from reporting, the network would simply keep going at whatever reward level was set previously. The expectation that rate reports will come back online in future and force the exchange rate back to parity would keep the exchange rate at parity even in an extended absence of reports.

First off, what follows is NOT a proposed change to bitcoin. Nor is it really an idea for a new blockchain. Bitcoin has forced me to think long and hard about the nature of money and the experiment described here is one of the things that still screws with my mind.

Suppose one coded a bitcoin variant that works as follows.

Difficulty still varies up and down to target a set number of block being generated in a set time period. However, the coinbase amounts are not following a hardcoded decreasing pattern to target a fixed final amount of issued currency, but are adjusting up and down to target a fixed exchange rate, for example pegging the currency to the dollar. (Please don't get stuck at this point on how undesirable this is, I'm not advocating for it, just trying to convince myself whether it would work.)

Exchange rate is determined by demand and supply. We have no control over demand but some control over supply (not perfect control, since we can't control when hoarders will choose to sell, but assuming some miners sell their coins soon after generation, we have control over this portion of supply). In order for the network to know what the coinbase amount for the next block should be it needs to know what the exchange rate is. Therefore the current exchange rate is also placed into every block. If the exchange rate in a block is incorrect for the time when the block was generated, the block is rejected. If the exchange rate goes above one (Fiatcoins become too valuable), then the coinbase transaction is increased and if it drops below one (Fiatcoins become too cheap) then the coinbase amount is decreased. This is analogous to a central bank increasing and decreasing the money supply via interest rates which in turn affects the exchange rate of the currency.

One important point is that this may well work, not because the feedback loop thus created is particularly effective, but because it creates an expectation of what the exchange rate "should be". If a large group of people believe that the exchange rate will tend to 1:1 in the long term they will buy when the rate dips below 1 and sell when it rises above 1. The built in mechanism can only affect the the exchange rate over long periods, but the expectation that the protocol will eventually force the rate back to 1 leads traders to keep the rate at unity, even in the short term.

Of course having the exchange rate in every block causes technical issues. If everyone is getting their rates from the same exchange, then the network has a single point of failure. If we get our rates from different exchanges, then as long as there is still a functional exchange somewhere that is reachable by most miners, the network remains functional. However, if miners are free to use exchange rates from any exchange, then I can't reject any block that has a price that doesn't match the price at my reference exchange exactly, since the rate may well be different at other exchanges. I can however reject anything that deviates by more than a small margin, since arbitrageurs should keep the exchange prices close to one another.

The power of expectations is unbelievable. Give people a plausible reason to believe that the exchange rate will tend to X in the long term and it becomes a self fulfilling prophecy. Another example is the bitcoin test network. On a technical level the test and production networks are indistinguishable (aside from scale), yet bitcoins are worth almost $17 dollars each (right now, who knows what they'll be worth in 5 minutes) while test network coins are utterly worthless. Why are they worthless? Because we expect them to be.

This messes with my mind




 

But this is the difference between the way bitcoin works today and what you are proposing. Today, one would have to take on all 8 connections in order to keep the longer blockchain from a new node. With your scheme, one only needs to take on 1 and make sure that the new node sees your shorter branch first. The node eventually learns about the longer branch from its other peers, but doesn't switch. What's worse is that it is now effectively a poisoned node that will forward blocks to other new nodes in the same incorrect order that it received them. And so the rot spreads.

Whether this is true depends on you strategy when you successfully mine the 1st block. If you take the naive approach and just keep mining in order to get the 2nd block as well, one has to assume that your co-conspirators will dessert you, since there is no longer anything in it for them. So the odds that you get the money is still 10% of 10% = 1%. In other words you have to get both the first and the second block yourself, getting the 2nd after someone else got the 1st will net you nothing, and therefore getting the 1st while some helpful soul gets the 2nd for you is so unlikely as to be negligible. Unless you have some fixed agreement with you co-conspirators to remain loyal in these cases in which it makes more sense to see you as one block of 20% rather than 2 blocks of 10%.

Therefore the rational thing to do in order to pull others in is to immediately upon successful mining of a block issue a transaction that offers a further bribe for the next block by using your fraudulent gains as input and offering a substantial tx fee. So the question is, how much do you offer? Or, more to the point, how much do others typically offer? If, for example, other corrupt miners offer nothing and try to overtake the chain by themselves, then you would have been better off not relaying the initial bribe tx to them in the 1st place, since your chance of netting the bribe is unaffected (you still need to get the block yourself to claim the bribe).

I also realized recently that one should not assume that pool owners (or large scale miners of any sort) won't do this since it will hurt bitcoin and therefore themselves in the long term. The existence of derivative instruments like bitoption.org means that for all we know a power miner may be short on bitcoin in the long term, making him willing to partake in such attacks irrespective of the bribe offered. Right now there's nowhere near enough volume traded on bitoption to justify this, but I suspect that lots of people here are so bullish on bitcoin that if anyone were to offer a truly cheap call option, they would get snapped up like hotcakes.

That's a good point. However, this attack would almost certainly need a corrupt pool owner to get started in the 1st place, so anyone attempting it would send it directly to each of the pools. I suspect determining their IPs will be trivial. Haven't studied the relaying mechanism in detail so I might be way off base here.

If all corrupt miners follow the same rule, then as soon as one of the pools turn rogue, all of the corrupt miners will be connected to one another with the corrupt pool serving as a hub. However, it is not clear that even a corrupted miner will relay such a message as, in doing so, he increases the probability that the heist will be successful, but reduces the probability that he will get a cut of the gains. I need to think this through some more.