Re: [Bitcoin-development] Version bits proposal
I like the idea but I think we should leave at least 16 bits of the version fixed as an extra-nonce. If we don't then miners may use them as a nonce anyway, and mess with the soft-fork voting system. My original proposal was this: https://github.com/bitcoin/bitcoin/pull/5102 Best regards -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Reducing the block rate instead of increasing the maximum block size
On 11/05/2015 04:25 p.m., Leo Wandersleb wrote: I assume that 1 minute block target will not get any substantial support but just in case only few people speaking up might be taken as careful support of the idea, here's my two cents: In mining, stale shares depend on delay between pool/network and the miner. This varies substantially globally and as Peter Todd/Luke-Jr mentioned, speed of light will always keep those at a disadvantage that are 100 light milli seconds away from the creation of the last block. If anything, this warrants to increase block target, not reduce. (The increase might wait until we have miners on Mars though ;) ) An additional delay of 200 milliseconds means loosing approximately 0.3% of the revenue. Do you really think this is going to be the key factor to prevent a mining pool from being used? There are lot of other factors, such as DoS protections, security, privacy, variance, trust, algorithm to distribute shares, that are much more important than that. And having a 1 minute block actually reduces the payout variance 10x, so miners will be happy for that. And many pool miners may opt to do solo mining, and create new full-nodes. If SPV also becomes 10 times more traffic intensive, I can only urge you to travel to anything but central Europe or the USA. The SPV traffic is minuscule. Bloom-filers are an ugly solution that increases bandwidth and does not provide a real privacy solution. Small improvements in the wire protocol can reduce the traffic two-fold. I want bitcoin to be the currency for the other x billion and thus I oppose any change that moves the balance towards the economically upper billion. Because having a 10 minute rate Bitcoin is a good Internet money. If you have a 1 minute rate, then it can also be a retail payment method, an virtual game trading payment method, a gambling, XXX-video renting (hey, it takes less than 10 minutes to see one of those :), and much more. You can reach more billions by having near instant payments. Don't tell me about the morning caffe, I would like that everyone is buying their coffe with Bitcoin and there are millions of users before we figure out how to do that off-chain. Best regards, Sergio. -- One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] A way to create a fee market even without a block size limit (2013)
El 10/05/2015 06:07 p.m., Gregory Maxwell escribió: On Sun, May 10, 2015 at 8:45 PM, Sergio Lerner sergioler...@certimix.com wrote: Can the system by gamed? Users can pay fees or a portion of fees out of band to miner(s); this is undetectable to the network. Then this is exactly what is needed. Let me explain. I know of 5 methods for a user to pay fees to a miner. I will explain each method and why these methods do not prevent the fee market from being created: 1) By transaction fees This is the standard, which would be limited by the CoVar algorithm, and would create the fee market, if it were the only way to pay fees. 2) By creating multiple transactions, each adding an output that pays to each miner (to a known miner address) the fees. User does not pre-negotiate anything with miners. This requires a transaction to have an additional output and requires sending through the p2p network one different transaction to each miner, each having an output with a known address of that miner. But the network does not propagates double-spends, so those transaction would need to be sent directly to the top miners, and to all at the same time. The IP addresses of the top miners are not generally publicly available, and then may not accept new incoming connections. Also having an additional output means the transactions would be larger, so they will score lower by any metric the miner uses to choose transactions. Last, miners must be programmed to automatically interpret payments to their addresses as fees. The resulting protocol is very difficult to do reliably, expensive, as any delay would make one miner receive the transaction from other miner and reject the double-spend that is being send directly to it, increasing the average confirmation time. 3) By adding an anyone-can-spend output for fees, so the miner can spend that output in the same block. User does not pre-negotiate anything with miners. We can hard-fork not to allow spending outputs created in the same block. This is a drawback, unless we reduce the block rate, which is my proposal. However, spending in the same block also requires an storing in the block an additional input, which consumes at least 40 bytes more, and the transaction containing the input cannot be relayed to the network in advance. Then the block that uses this method to collect fees from many transactions will propagate slower, and the miner may end loosing money. The any-one-can-spend output would take approximately 10 bytes. So if transmitting 10+40=50 bytes, cost more than the fees earned, then miners do not have an incentive to game the system. It's has been studied that each kilobyte costs an additional 80ms delay until a majority knows about the block. (Information propagation in the Bitcoin network). So 50 bytes costs 3.9 ms in propagation time, which having a a 25 BTC subsidy is roughly equivalent to 0.2 mBTC. Currently this is more than what transactions do pay in fees (about 0.1 mBTC), so this should not be a problem for at least 5 years. And again, we could just prevent spending outputs in the same block they are created. 4) Using a transaction having a single input having exactly the desired output amount plus fees and signing the input with SIGHASH_SINGLE | SIGHASH_ANYONECANPAY and adding to the transaction a single output with the desired amount. The miner will be able to join many of these transactions and finally add an output to collect all fees together, without using standard transaction fees. This is unreliable and cannot be systematically repeated without creating a pre-transaction just to prepare the single input having the amount plus fees exactly. The pre-transaction would need to pay fees, so the problem is not avoided, just moved around. 5) By negotiating out of band with the miner previously. Anything could be agreed by the user and the miner. This actually creates a parallel out-of-band market for fees, which is exactly what we want. If a user-to-miner pre-negotiation will take place, then the miner can establish whatever price policy he wants to compete and stay in business, as block data propagation costs money. So there will be two fee markets, the out-of-band market, and the in-band market, and both should converge. My conclusion is that fee markets will be created, and any alternate fee-paying methods (without a pre-negotiation) are not reliable nor cost-saving options. The full proposal would be to use the CoVar method, reduce the block rate to 1 minute, and do not allow spending outputs in the same block they are created. Best regards, Sergio. -- One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk
[Bitcoin-development] Reducing the block rate instead of increasing the maximum block size
In this e-mail I'll do my best to argue than if you accept that increasing the transactions/second is a good direction to go, then increasing the maximum block size is not the best way to do it. I argue that the right direction to go is to decrease the block rate to 1 minute, while keeping the block size limit to 1 Megabyte (or increasing it from a lower value such as 100 Kbyte and then have a step function). I'm backing up my claims with many hours of research simulating the Bitcoin network under different conditions [1]. I'll try to convince you by responding to each of the arguments I've heard against it. Arguments against reducing the block interval 1. It will encourage centralization, because participants of mining pools will loose more money because of excessive initial block template latency, which leads to higher stale shares When a new block is solved, that information needs to propagate throughout the Bitcoin network up to the mining pool operator nodes, then a new block header candidate is created, and this header must be propagated to all the mining pool users, ether by a push or a pull model. Generally the mining server pushes new work units to the individual miners. If done other way around, the server would need to handle a high load of continuous work requests that would be difficult to distinguish from a DDoS attack. So if the server pushes new block header candidates to clients, then the problem boils down to increasing bandwidth of the servers to achieve a tenfold increase in work distribution. Or distributing the servers geographically to achieve a lower latency. Propagating blocks does not require additional CPU resources, so mining pools administrators would need to increase moderately their investment in the server infrastructure to achieve lower latency and higher bandwidth, but I guess the investment would be low. 2. It will increase the probability of a block-chain split The convergence of the network relies on the diminishing probability of two honest miners creating simultaneous competing blocks chains. To increase the competition chain, competing blocks must be generated in almost simultaneously (in the same time window approximately bounded by the network average block propagation delay). The probability of a block competition decreases exponentially with the number of blocks. In fact, the probability of a sustained competition on ten 1-minute blocks is one million times lower than the probability of a competition of one 10-minute block. So even if the competition probability of six 1-minute blocks is higher than of six ten-minute blocks, this does not imply reducing the block rate increases this chance, but on the contrary, reduces it. 3, It will reduce the security of the network The security of the network is based on two facts: A- The miners are incentivized to extend the best chain B- The probability of a reversal based on a long block competition decreases as more confirmation blocks are appended. C- Renting or buying hardware to perform a 51% attack is costly. A still holds. B holds for the same amount of confirmation blocks, so 6 confirmation blocks in a 10-minute block-chain is approximately equivalent to 6 confirmation blocks in a 1-minute block-chain. Only C changes, as renting the hashing power for 6 minutes is ten times less expensive as renting it for 1 hour. However, there is no shop where one can find 51% of the hashing power to rent right now, nor probably will ever be if Bitcoin succeeds. Last, you can still have a 1 hour confirmation (60 1-minute blocks) if you wish for high-valued payments, so the security decreases only if participant wish to decrease it. 4. Reducing the block propagation time on the average case is good, but what happen in the worse case? Most methods proposed to reduce the block propagation delay do it only on the average case. Any kind of block compression relies on both parties sharing some previous information. In the worse case it's true that a miner can create and try to broadcast a block that takes too much time to verify or bandwidth to transmit. This is currently true on the Bitcoin network. Nevertheless there is no such incentive for miners, since they will be shooting on their own foots. Peter Todd has argued that the best strategy for miners is actually to reach 51% of the network, but not more. In other words, to exclude the slowest 49% percent. But this strategy of creating bloated blocks is too risky in practice, and surely doomed to fail, as network conditions dynamically change. Also it would be perceived as an attack to the network, and the miner (if it is a public mining pool) would be probably blacklisted. 5. Thousands of SPV wallets running in mobile devices would need to be upgraded (thanks Mike). That depends on the current upgrade rate for SPV wallets like Bitcoin Wallet and BreadWallet. Suppose that the upgrade rate is 80%/year: we develop the source code for the change now and apply the change in
[Bitcoin-development] A way to create a fee market even without a block size limit (2013)
Two years ago I presented a new way to create a fee market that does not depend on the block chain limit. This proposal has not been formally analyzed in any paper since then, but I think it holds a good promise to untangle the current problem regarding increasing the tps and creating the fee market. BTW, think the maximum tps should be increased, but not by increasing the block size, but by increasing the block rate (I'll expose why in my next e-mail). The original post is here (I was overly optimistic back then): https://bitcointalk.org/index.php?topic=147124.msg1561612#msg1561612 I'll summarize it here again, with a little editing and a few more questions at the end: The idea is simple, but requires a hardfork, but is has minimum impact in the code and in the economics. Solution: Require that the set of fees collected in a block has a dispersion below a threshold. Use, for example, the Coefficient of Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If the CoVar is higher than a fixed threshold, the block is considered invalid. The Coefficient of variation is computed as the standard deviation over the mean value, so it's very easy to compute. (if the mean is zero, we assume CoVar=0). Note that the CoVar function *does not depend on the scale*, so is just what a coin with a floating price requires. This means that if there are many transactions containing high fees in a block, then free transactions cannot be included. The core devs should tweak the transaction selection algorithm to take into account this maximum bound. *Example* If the transaction fee set is: 0,0,0,0,5,5,6,7,8,7 The CoVar is 0.85 Suppose we limit the CoVar to a maximum of 1. Suppose the transaction fee set is: 0,0,0,0,0,0,0,0,0,10 Then the CoVar is 3.0 In this case the miner should have to either drop the 10 from the fee set or drop the zeros. Obviously the miner will drop some zeros, and choose the set: 0,10, that has a CoVar of 1. *Why it reduces the Tx spamming Problem?* Using this little modification, spamming users would require to use higher fees, only if the remaining users in the community rises their fees. And miners won't be able to include an enormous amounts of spamming txs. *Why it helps solving **the tragedy-of-the-commons fee problem?* As miners are forced to keep the CoVar below the threshold, if people rises the fees to confirm faster than spamming txs, automatically smamming txs become less likely to appear in blocks, and fee-estimators will automatically increase future fees, creating a the desired feedback loop. *Why it helps solving the block size problem?* Because if we increase the block size, miners that do not care about the fee market won't be able to fill the block with spamming txs and destroy the market that is being created. This is not a solution against an attacker-miner, which can always fill the block with transactions. *Can the system by gamed? Can it be attacked?* I don't think so. An attacker would need to spend a high amount in fees to prevent transactions with low fees to be included in a block. However, a formal analysis would be required. Miller, Gun Sirer, Eyal.. Want to give it a try? * Can create a positive feedback to a rise the fees to the top or push fess to the bottom? *Again, I don't think so. This depends on the dynamics between the each node's fee estimator and the transaction backlog. MIT guys? *Doesn't it force miners to run more complex algorithms (such as linear programming) to find the optimum tx subset ? *Yes, but I don't see it as a drawback, but as a positive stimulus for researchers to develop better tx selection algorithms. Anyway, the greedy algorithm of picking the transactions with highest fees fees would be good enough. * PLEASE don't confuse the acronym CoVar I used here with co-variance.* Best regard, Sergio. -- One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] network disruption as a service and proof of local storage
Matt is right: the goal is to prove digital copies of a public file. Nothing more, nothing less. Regarding the IP, I don't claim that every machine should provide the protocol. Mobiles phones shouldn't. But machines that what to be prioritized in some way or that want to be rewarded for hosting a node should use a fixed IP. That's the cost of prioritization/reward. The protocol could be a service bit, advertised in the version message. My response to your comment below: On 27/03/2015 03:40 p.m., Jeremy Spilman wrote: It would be extremely impressive to achieve a reliable mechanism for discerning a local copy exists under these constraints, particularly without false positives and false negatives, and without imposing very substantial one-time encoding costs, e.g. on par with doubling the verification cost. I see it differently. The asymmetric-time protocol is quite reliable. If can be made to have almost no false positives/false negatives (not considering rare communication problems, such as congestion and packet loss for more than 5 seconds). These are my back-of-the-envelope calculations: Bitcoind takes approximately 1 second to serve a 1 Mb block (seek time, but mostly transfer time) Then decryption of a block can take 150 msec without problem (15% overhead). The last N blocks could be cached so they don't need to be decrypted to be sent. In 150 msec a PC can decrypt a 1MB of data split over 1024-bit blocks decrypted by modexp 3 (0.2 msec for 3 bigint multiplications), so a full block can be decrypted. Encrypting such block would take approximately 15 seconds (which is much less than the 10 minutes available to encrypt each block) Then the protocol works with a security margin of approximately 50x. A communication problem during 5 seconds would be needed to disturb a protocol of that takes 100 msec for the prover. Regards, Sergio. -- Dive into the World of Parallel Programming The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net/ ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] network disruption as a service and proof of local storage
If I understand correctly, transforming raw blocks to keyed blocks takes 512x longer than transforming keyed blocks back to raw. The key is public, like the IP, or some other value which perhaps changes less frequently. Yes. I was thinking that the IP could be part of a first layer of encryption done to the blockchain data prior to the asymetric operation. That way the asymmetric operation can be the same for all users (no different primers for different IPs, and then the verifiers does not have to verify that a particular p is actually a pseudo-prime suitable for P.H. ) and the public exponent can be just 3. Two protocols can be performed to prove local possession: 1. (prover and verifier pay a small cost) The verifier sends a seed to derive some n random indexes, and the prover must respond with the hash of the decrypted blocks within a certain time bound. Suppose that decryption of n blocks take 100 msec (+-100 msec of network jitter). Then an attacker must have a computer 50 faster to be able to consistently cheat. The last 50 blocks should not be part of the list to allow nodes to catch-up and encrypt the blocks in background. Can you clarify, the prover is hashing random blocks of *decrypted*, as-in raw, blockchain data? What does this prove other than, perhaps, fast random IO of the blockchain? (which is useful in its own right, e.g. as a way to ensure only full-node IO-bound mining if baked into the PoW) How is the verifier validating the response without possession of the full blockchain? You're right, It is incorrect. Not the decrypted blocks must be sent, but the encrypted blocks. There correct protocol is this: 1. (prover and verifier pay a small cost) The verifier sends a seed to derive some n random indexes, and the prover must respond with the the encrypted blocks within a certain time bound. The verifier decrypts those blocks to check if they are part of the block-chain. But then there is this improvement which allows the verifier do detect non full-nodes with much less computation: 3. (prover pays a small cost, verifier smaller cost) The verifier asks the prover to send a Merkle tree root of hashes of encrypted blocks with N indexes selected by a psudo-random function seeded by a challenge value, where each encrypted-block is previously prefixed with the seed before being hashed (e.g. N=100). The verifier receives the Markle Root and performs a statistical test on the received information. From the N hashes blocks, it chooses M N (e.g. M = 20), and asks the proved for the blocks at these indexes. The prover sends the blocks, the verifier validates the blocks by decrypting them and also verifies that the Merkle tree was well constructed for those block nodes. This proves with high probability that the Merkle tree was built on-the-fly and specifically for this challenge-response protocol. I also wonder about the effect of spinning disk versus SSD. Seek time for 1,000 random reads is either nearly zero or dominating depending on the two modes. I wonder if a sequential read from a random index is a possible trade-off,; it doesn't prove possession of the whole chain nearly as well, but at least iowait converges significantly. Then again, that presupposes a specific ordering on disk which might not exist. In X years it will all be solid-state, so eventually it's moot. Good idea. Also we don't need that every node implements the protocol, but only nodes that want to prove full-node-ness, such as the ones which want to receive bitnodes subsidy. -- Dive into the World of Parallel Programming The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net/ ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] network disruption as a service and proof of local storage
The problem of pseudo-nodes will come over and over. The cat and mouse chase is just beginning. It has been discussed some times that the easiest solution world be to request some kind of resource consumption on each peer to be allowed to connect to other peers. Gmaxwell proposed Proof of Storage here: https://bitcointalk.org/index.php?topic=310323.msg3332919#msg3332919 I proposed a (what I think) is better protocol for Proof of Storage that I call Proof of Local storage here https://bitslog.wordpress.com/2014/11/03/proof-of-local-blockchain-storage/ . It's better because it does not need the storage of additional data, but more importantly, it allows you to prove full copy of the blockchain is being maintained by the peer. This is specially important now that Bitnodes is trying a full-node incentive program that may be easily cheated (http://qntra.net/2015/02/pseudonode-proxy-fools-bitcoin-full-node-incentive-program/) Proof of local storage allows a node to prove another peer that he is storing a LOCAL copy of a PUBLIC file, such as the blockchain. So the peer need not waste more resources (well, just some resources to encode/decode the block-chain). The main idea is to use what I called asymmetric-time-encoding. Basically you encode the block-chain in a way that it takes 100 more times to write it than to read it. Since the block-chain is an append-only (write-only) file, this fit good for our needs. For instance (and as a simplification), choosing a global 1024-bit prime, then splitting the block-chain in 1024-bit blocks, and encrypting each block using Polihg-Hellman (modexp) with decryption exponent 3. Then encryption is at least 100 times slower than decryption. Before PH encryption each node must xor each block with a pseudo-random mask derived from the public IP and the block index. So block encryption could be: BlockEncryptIndex(i) = E(IP+i,block(i))^inv(3) (mod p), where inv(3) is 3^-1 mod (p-1). E() could be a fast tweaked encryption routine (tweak = index), but we only need the PRNG properties of E() and that E() does share algebraic properties with P.H.. Two protocols can be performed to prove local possession: 1. (prover and verifier pay a small cost) The verifier sends a seed to derive some n random indexes, and the prover must respond with the hash of the decrypted blocks within a certain time bound. Suppose that decryption of n blocks take 100 msec (+-100 msec of network jitter). Then an attacker must have a computer 50 faster to be able to consistently cheat. The last 50 blocks should not be part of the list to allow nodes to catch-up and encrypt the blocks in background. 2. (prover pay a high cost, verified pays negligible cost). The verifier chooses a seed n, and then pre-computes the encrypted blocks derived from the seed using the prover's IP. Then the verifier sends the seed, and the prover must respond with the hash of the encrypted blocks within a certain time bound. The proved does not require to do any PH decryption, just take the encrypted blocks for indexes derived from the seed, hash them and send the hash back to the verifier. The verifier validates the time bound and the hash. Both protocols can me made available by the client, under different states. For instance, new nodes are only allowed to request protocol 2 (and so they get an initial assurance their are connecting to full-nodes). After a first-time mutual authentication, they are allowed to periodically perform protocol 1. Also new nodes may be allowed to perform protocol 1 with a small index set, and increase the index set over time, to get higher confidence. The important difference between this protocol and classical remote software attestation protocols, is that the time gap between a good peer and a malicious peer can be made arbitrarily high, picking a larger p. Maybe there is even another crypto primitive which is more asymmetric than exponent 3 decryption (the LUC or NTRU cryptosystem?). In GMaxwell proposal each peer builds a table for each other peer. In my proposal, each peer builds a single table (the encrypted blockchain), so it could be still possible to establish a thousands of connections to the network from a single peer. Nevertheless, the attacker's IP will be easily detected (he cannot hide under a thousands different IPs). It's also possible to restrict the challenge-response to a portion of the block-chain, the portion offset being derived from the hash of both IP addresses and one random numbers provided by each peer. Suppose each connection has a C-R space equivalent to 1% of the block-chain. Then having 100 connections and responding to C-R on each connection means storing approximate 1 copy of the block-chain (there may be overlaps, which would need to be stored twice) , while having 1K connections would require storing 10 copies of the blockchain. Best regards, Sergio -- Dive into the World of
Re: [Bitcoin-development] BIP: Voluntary deposit bonds
On 30/12/2014 01:51 a.m., Gregory Maxwell wrote: On Mon, Dec 29, 2014 at 7:21 PM, Sergio Lerner sergioler...@certimix.com wrote: I propose to allow miners to voluntarily lock funds by letting miners add additional inputs to the coinbase transaction. Currently the coinbase transaction does not allow any real input to be added (only a pseudo-input). To make that more concrete. E.g. You make your anyone can spend output PUSHhash of coinbase output script_pubkeys OP_NOP3. Now this anyone can pay transaction is really just a coinbase input. Slight off-topic: That looks like an abuse of the VM. Even P2SH is an abuse of the VM. Gavin's OP_EVAL (hard-fork) should had been chosen. I'm taking about a simple change that goes along the lines of Satoshi's original design. Bitcoin was a beautiful design, and extra complexity is making it ugly. We need Bitcoin to be simple to understand for new programmers so they can keep the project going. It doesn't help the project that one needs to be a guru to code for Bitcoin. -- Dive into the World of Parallel Programming! The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] BIP: Voluntary deposit bonds
I propose to allow miners to voluntarily lock funds by letting miners add additional inputs to the coinbase transaction. Currently the coinbase transaction does not allow any real input to be added (only a pseudo-input). This is a hard-fork, and we could include it the next time a hardfork is made. The modifications to the code are minimal (no more than 12 lines modified where IsCoinBase() is called), and they generally involve removing code, not adding. Why ? Because sometime in the future (maybe 5-10 years) we may have to deal with problems of securing the blockchain, as the subsidy is lowered. We don't want the number of confirmation blocks to be increased in compensation because Bitcoin won't be able to compete with other payment networks. Then by having this hardfork now, we will be able to soft-fork later to any rule we may came come up with involving deposit bonds, proof-of-stake, and the penalization of double-mining (mining two blocks at the same height) to prevent short-range attacks. Can it hurt? No. I doesn't not change the incentives or the security in any way, as adding additional inputs to the coinbase transaction would be voluntary until the time for a soft-fork comes. We shouldn't hard-fork for this change only, but maybe we could do this change when the next hard-fork is scheduled (when we increase the block size?). Regards, S. -- Dive into the World of Parallel Programming! The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] ACK NACK utACK Concept ACK
Is that the full terminology or are there more acronyms? Is this documented somewhere? Best regards, Sergio. -- Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server from Actuate! Instantly Supercharge Your Business Reports and Dashboards with Interactivity, Sharing, Native Excel Exports, App Integration more Get technology previously reserved for billion-dollar corporations, FREE http://pubads.g.doubleclick.net/gampad/clk?id=164703151iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Death by halving (pro-active proposals)
Instead of discussing what will happen when the subsidy is halved (which nobody really knows) maybe we can think about of what we can do to mitigate any damage in case something unwanted happens. Let's be proactive. For instance, any form of merged-mining (like higher frequency side-chains) will end-up increasing miners profit, even by a small margin. Then that margin can compensate miners not to turn off their equipment. Then we can encourage merge-mining on SHA-256, instead of discouraging SHA-256 alt-coins. Also we can encourage mining during the trouble period by creating a donation pool: suppose we manage to convince miners to donate 1% of their revenue in order to pay back to the miners for the first month after the reward halving. If every block pays 1% for 10 months, then every block during the first month of halving will earn 20% more. Of course, convincing miners of this may be difficult, but not impossible. It could be done automatically with nLockTime freeze of transactions with high fees, so no TTP is necessary. So here are two proposals, any other idea? Best regards, Sergio. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
On 06/10/2014 08:43 p.m., Tom Harding wrote: On 10/5/2014 4:00 PM, Sergio Lerner wrote: If everyone acts rationally in his own interest, then the best choice for the remaining miners is to try to mine a competing block at the same height n including the high-fee transaction, to collect the fee for themselves. Sergio -- Just some thoughts on your interesting problem. Since everybody but M10 is on equal footing, I would expect M10 to have some fixed advantage depending on assumptions, and the bigger the advantage, the shorter the freeze time. Yes, that's how simulation works. The problem is that the existence of high-fee delays the decision to switch to M10. Since the network is moving slower (because of fragmentation) the effect of the high-fee is twofold: it delays the convergence because it promotes selfishness and it delays convergence because it promotes fragmentation. During that time window where the network is frozen, any other high-fee transaction only makes things worse. This is a very rare example where a well distributed network (100 miners having 1% each) is much much worse than 3 miners having 33% each. Using the my previous terminology, automatic fee-sharing (ORBS) is a solution to the freeze problem (FRONT) but opens the windows to CHAKIDO double-spending. and CHAKIDO double-spending is a much worse problem than FRONT. But as Tamas pointed out, sooner or later someone will implement something like ORBS, get over the critical mass of miner adoption, and then the CHAKIDO problem will be inevitable. The only clean solution to this problem is the DECOR+ protocol, which shares block-rewards by including uncles (as GHOST does) and splitting the reward between all miners at the same height until coinbase maturity is over. This way the best choice is always cooperative. PS: Using so many acronyms makes arguments much more concise, but suggest we should have all the attack terminology described in a single Bitcoin Security Wiki... -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
On 07/10/2014 04:16 p.m., Gregory Maxwell wrote: Then I spend the output of the fraudulent spend nlocked one block higher, and spend the output of that one again, nlocked one block higher, and so on... each step paying fees. Yes, you're right. I didn't consider that case. But the problem is that this is not automatic. Currently there is a clear division between miners how will not take the kickback (irrrational) and miners who will (rational). If somebody modifies the bitcoind to make this choice automatic, then DECOR+ is the only solution I know about to avoid people doing anonymous double-spends (with chained kickbacks, as you mention). The locktime on normal transactions you proposed does not solve the problem, just diminishes it in a constant value (which currently is very low) -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
Comments between lines... On 06/10/2014 03:42 a.m., Alex Mizrahi wrote: . This doesn't require protocol changes(*) and can be simply incorporated into a piece of code which decides what to do when a transaction with unusually large fee appears. (I.e. it will automatically share the fee, and others will recognize that). And if the biggest miner has 25% of all hashrate, sharing 25% of your loot doesn't sound that bad. The problem with this approach is that once the bitcoind has been modified to allow this sharing of the high-tx fee by delegation, then the same system can be used for an attack. Let's call a system that makes the Optimum Rational Best-chain Selection for maximizing profit ORBS, just to give it a name. The system assures that the best chain chosen is always the optimum in terms of profit, taking into account fee delegation and all the game-theoretic incentives derived. It's only a theoretical abstraction, but could be approximated in practice. The attack is called Chained Kickback DOuble-spend attack (or “CHAKIDO”) and is an extension of Bonneau's kickback attack. Basically the attack is to create the ORBS patch, and start convincing miners to use it, sending some probe high-fees tx. Once you have ORBS working in a majority of the mining nodes, you can perform a double-spend against a target like an exchange by: - Buy some btc X - Send those btc to an exchange (suppose the exchange requires 6 confirmations) in a transaction TX - Immediately convert those btc to an alt-coin, and collect the alt-coins - Create a high fee tx that is a double-spend of TX having a high fee Y such that Y X but Y triggers a ORBS reorganization. - Profit (This rollback attack was performed against whitecoin, I think) This attack gets terrible powerful if there is no subsidy. You may need 500 blocks of confirmation to protect from a 10 BTC spend with current fees and no subsidy. This is because once 100% of the nodes use ORBS, the fee delegation is linear (it doesn't grow exponentially with the number of blocks). So ORBS should never be implemented without additional protective measures in merchant applications. If we had a closed formula for ORBS, then all merchants could compute the minimum confirmation blocks such that always Y X, but such formula involves many unknowns which would need to be dynamically estimated, and also it should take into account the number of simultaneous payment attempts. My conclusions are: - We should never allow ORBS to be implemented unless merchants are also aware of it. If are aware of ORBS then Bitcoin with no subsidy will be become a terrible slow payment system so ... - We could implement the protections that work even if some nodes implement ORBS, such as fee and burn btc sharing, as I described before - Or we need some high percentage of miners to be irrational, to force ORBS fee delegation have an exponential decay. Best regards, Sergio. -- Slashdot TV. Videos for Nerds. Stuff that Matters. http://pubads.g.doubleclick.net/gampad/clk?id=160591471iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
I would like to share with you a vulnerability in the Bitcoin protocol I've been thinking of which might have impact on the future of Bitcoin. Please criticize it! *The Freeze on Transaction Problem * The freeze problem occurs if someone publishes a transaction with fees much higher than the block subsidy. I don't remember who described the attack first. Suppose that, by mistake, a transaction is published with 50 BTC in fees. The transaction is included in a block at height n. If everyone acts rationally in his own interest, then the best choice for the remaining miners is to try to mine a competing block at the same height n including the high-fee transaction, to collect the fee for themselves. All the miners having solved the block at height n, now move on mining at height (n+1). But they won't choose each other branches until one branch is sufficiently longer so that it is better to switch to it and abandon their own branch rather than try to keep the block with the high fee. This case is different from the real block competition case we see periodically on the blockchain, where the miners are generally split between two branches. Here there are multiple branches competing. If there are 10 top miners each having 10% of the network hashing power, then 10 different branches will compete. The analysis for this case is similar to the Gambler's Ruin problem analysis present in the Satoshi paper, but with a fixed constant monetary incentive not to switch. Since the incentive to switch grows exponentially with the branch length difference, any initial constant is diluted. In the special and rare case that all the miners have exactly the same hashing power, then the network diverges, and this is equivalent as having two miners having exactly 50% of the hashing power each. So in principle the freeze on transaction problem is just a temporary disruption in the network, but not a fatal halt. Nevertheless, since during the freeze period each miner is mining on his own branch, it also means that moving forward with blocks is a lot slower. Assuming 10 miners having 10% of the total hashing power each (+/- 3%), the network becomes 10 times slower. I simulated it with a 50 BTC tx freeze fee, and 10 miners, and it takes approximately 6 blocks to converge, so the freeze time is approximately 60 times the block interval, or 10 hours. If the distribution is approximately 25% of the hashing power for each top miner, the freeze time is 4 hours. Obviously what's needed for the freeze problem to occur is that miners are 100% rational, greedy and prepared. They need to have a modified version of bitcoind which can automatically detect a high-fee transaction and prevent adding to the best chain a not-owned block containing such transaction. There will be no time for the miners to patch bitcoind if such transaction is manually spotted. Also the latest versions of bitcoind have preventions not to allow high fees by mistake. So the freeze problem is currently non-existent, but may pop up in the future in form of a state-sponsored attack. *The Freeze problem as an Attack* If an attacker plans to repeat such attack periodically at the expense of wasting a lot of BTC, there is little the current protocol can do, because miners will be prepared to take advantage of the attack. If the attacker issues a new fee burning transaction before the network converges, then the attacker can maintain incentives to keep every miner separated in his own branch. So wasting 50 BTC every 4 hours, an attacker can maintain the network frozen forever. Even if we restrict the maximum fee per transaction, the scripting system has infinite ways to create transactions whose output can be taken by anyone, and the attacker can announce the method miners can use to collect those BTC and even prepare and publish the bitcoind patches to automate collecting those transaction outputs. The best thing the community can do is act together and cooperate to share the high transaction fee. This will neutralize the attack completely and allow miners to earn extra bitcoins. But cooperation in the Bitcoin community has never been easy. There is a technical solution which is to modify the Bitcoin protocol so that every transaction output has a maturity time of 6 blocks, and if a transaction output is redeemed multiple times in a 6 block interval, then the BTC amount is split between all redeemers, and also fees would be automatically shared in a 6 block sliding window. At a first glance, this provides a way for miners to cooperate even anonymously and there is no immediate drawback, but an in depth analysis is necessary. -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog
Re: [Bitcoin-development] [BIP draft] CHECKLOCKTIMEVERIFY - Prevent a txout from being spent until an expiration time
I like the proposal. I suggest that applications and nodes should only broadcast transactions having OP_CHECKLOCKTIMEVERIFY a few blocks after the timeout value. If a node broadcasts a TX having OP_CHECKLOCKTIMEVERIFY and nLockTime is equal to the current height and equal to the timeout value, but that peer is one block behind in the blockchain, the transaction will be rejected by the peer and the source will be banned. Another option will be not to ban peers sending transactions failing to verify OP_CHECKLOCKTIMEVERIFY , but I don't like this. Still another option would be that the sender checks periodically the height of it's peers (using the version command) in order to be sure to send the transaction having OP_CHECKLOCKTIMEVERIFY only to the peers that are up to date with the blockchain. Regards, Sergio. -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Improvement to the Test Framework in the processing of test blocks
We've coded and tested changes to the Bitcoin testing framework to allow the creation and processing of blocks in unit test cases in order to test ProcessBlock(), CheckBlock(), ActivateBestChain(), ActivateBestChainStep() and ConnectTip(), including block-chain reorganizations, majority rules, block version changes and more. Several new test cases were added to enrich the test suite. Please review and comment the pull request: https://github.com/bitcoin/bitcoin/pull/4688 Best regards, Sergio Demian Lerner Timo Hanke -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Miners MiTM
Since the information exchanged between the pool and the miner is public, all that's needed is a mutual private MAC key that authenticates messages. This requires a registration step, that can be done only once using a simple web interface over https to the miner website. But the miner website is not the miner server, so the worst DoS would be preventing new miners to join the pool, which is not very often. The MAC key can be provided directly by the miner. And the pool associates the MAC key with a Bitcoin public address. The overhead would be minimal. -Sergio. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
Hi Tim, It's clear from the paper that the second party in the protocol can de-anonymize the first party. So it's seems that dishonest shufflers would prefer to be in that position in the queue. There are two possible solutions to this: 1. Derive the first order of parties in the shuffle from the hash of all inputs provided (as a seed for a pseudo-random number generator). 2. Repeat the shuffle several times with an different party order (e.g. an order that is deterministically derived from the hash of all the outputs) Best regards, Sergio/ On 09/08/2014 07:04 a.m., Tim Ruffing wrote: You are raising valid questions and one goal of our posting here is indeed to discuss exactly these system issues. On Thursday 07 August 2014 15:00:11 you wrote: I think the description at your website leaves out the truly interesting part: How do you decentralize this securely? - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is used for communication and how? The simplest approach is obviously to use direct connections to a randomly elected leader, who is also responsible for the broadcasts. One advantage of CoinShuffle is that the unlinkability between input and output addresses is guaranteed, no matter which underlying network you use. (Still, it is a good idea in general to hide your IP address but we can let the user decide here.) Of course, there would be other possibilities, such as overlay networks. Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses TomP2P, a distributed hash table, for communication. Do you have any hints regarding this point? - How does Alice know that Bob, Charlie and Dave are not the same person? (= how do you prevent a Sybil attack?) Because thats the real problem with mixing it seems - ensuring that your mixing partners are actually 100 people and not just 1 attacker. There are probably many mixing algorithms which work if you solve that problem, but I don't see how you offer a solution for it :( It's true that there are a few proposals for mixing protocols which all have their advantages and disadvantages. However, it's not true that the mixing itself becomes simple if you solve the problem of Sybil attacks. Still, mixing is difficult to get right: Even if there are no Sybil attacks, you have to ensure that the participants (or a server) cannot break unlinkability or steal money. Actually that's why there are several proposals for mixing protocols, because there is no obvious perfect solution. Regarding your question: It is indeed very important to get this right. Fundamentally, there is nothing that prevents the attacker from creating a lot of identities participating in a lot of CoinJoins. However, there are ways that make it hard for the attacker to put an honest user together only with malicious users. For a moment, assume that you can reliably establish a pool of users that would like to participate in the protocol. (I will discuss this later.) You have to divide the users to individual groups, i.e., CoinJoins runs. If the assignment cannot be influenced by the attacker, then the probability that there are also honest users in a run is quite high. Of course, the attacker is able to reduce your anonymity set but they cannot just put you together only with their malicious identities. Note that the attacker has to pay transaction fees for joining many transaction. One could even increase the required fee depending on the number of users in the pool (enforced by honest CoinShuffle participants that would not accept CoinJoins that pay a lower transaction fee). And making sure that the attacker cannot influence the assignment is simple: One can use the hash of all users' public keys in the pool to determine the assignment for example. For the initial setup step, i.e., creating the pool of participants, you need some kind of bulletin board. One possibility is to use an underlying peer-to-peer network. Bitcoin itself is the first that comes to the mind but it does not allow arbitrary messages. So if we do not want to change the Bitcoin protocol, chans in Bitmessage are a very promising possibility. Bitmessage relies basically on the same broadcast mechanism as Bitcoin. If you as a peer use enough outgoing connections to other peers, it's very difficult for an attacker to ensure that your message will not be spread among the network. (Btw, people have used this to do CoinJoin manually already https://forum.namecoin.info/viewtopic.php?f=2t=1694 .) Solutions like distributed hashtables (TomP2P again) are another possibility. We are not sure which of those approaches provides the best robustness against malicious nodes that try to stop single participants from reaching the network. For the setup step, latency is not an issue, so Bitmessage is indeed a promising candidate here. I think that in general, P2P is
[Bitcoin-development] Question on creating test cases for block.CheckBlock()
I'm working on a BIP which needs to modify the block acceptance rules. I have two ways of testing: - Mining blocks on the testnet - Creating test cases for Bitcoin Core. I want to create those test cases for block.CheckBlock(), which involves verifying 100 dynamically generated blocks. What is the state of the blockchain when a test case is executed ? Is is configured for the regtest, testnet3 or mainnet? What blocks are in the blockchain? Only the genesis block? checkblock_tests.cpp seems to be the only test case for CheckBlock() and it assumes the mainnet is configured. I need to use the regtest so I can create blocks of difficulty 1. Best regards and thank you in advance, -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] BlockPow: A Practical Proposal to prevent mining pools AND reduce payoff variance:
I propose a setting that prevent mining pools AND reduce payoff variance which requires two changes: increasing the block-rate and changing the Bitcoin PoW (but still allowing current Bitcoin ASICs to work (as far as I know)). The block rate must be increased at least 20 times and block must still be near full (e.g. there must be at least 20 more transactions/second than there is today) BlockPow is kind of PoW that only practically prevents mining pools for certain cryptocurrency settings based on concepts similar to parmacoin, but in a much simple degree. The idea is that if miners try to join a pool, then they incur in overhead of transmitting information and earn less than working solo. Let b (the payload) contain a full block. b must contain all the transactions and the header, and not only the transaction hashes. b should not hide anything. Let h be the block header (which contains the previous block hash and the Merkle tree root of the transactions). Let d be the difficulty. hash-block-length(b) returns the number of blocks processed by the hash function when fed with the block b. The target is divided by hash-block-length(b) so that the difficulty does not depend on the length of the block. Some other function can be used to encourage nodes to add more or less transactions. Def: Basic BlockPoW concept For each r in the nonce-range: if H ( H( r || b ) || h || r) ) 2^-d/ hash-block-length(b) then return r return null The header (h) is appended to the hashed message to allow SPV clients to verify the PoW without requiring the full block to be downloaded. Peers can send only (x,r,h) to SPV nodes, where x = H( r || b ), so they can verify the PoW. The verification procedure is obvious, and is skipped here. r is inserted at the beginning of the message to prevent pool administrators from keeping a secret mid-state of the hash function secret in order to prevent block stealing and also to force the miner to know b in the inner mining loop. So now mining requires the knowledge of the block b to be mined, and b must be received at each block-chain epoch. This could create an incentive not to include any transaction and use an almost empty b, because that way the bandwidth requirements is decreased. But this incentive should not exists normally, since by including transactions the solo miner gets an additional revenue from fees, which is lost if the block is empty. Anyway, to prevent this possible incentive we can append to b a subset of previous blocks (e.g 100 blocks). The block subset to include could be derived from a peudo-random function seeded by the previous block hash. Then a node would still need to download part or all the block-chain in order to mine. Now if the miner wants to be a dumb node and take part of a pool, then the current working unsolved block (the template) must be sent each time from the pool admin to each miner. If the pool admin hosts 1000 miners, then to serve them with fresh block templates he needs 1000 times more bandwidth that the miners, making this much more expensive. If miners create another network topology to distribute templates, they are incurring in the same overhead as being actively part of the cryptocurrency network, so they gain nothing. For example, in a block-chain with a 5 seconds block-rate, such as in NimbleCoin http://nimbleCoin.org, each block can be as large as 200 Kbytes (100 tps are allowed). A miner will require the block template to be ready as fast as possible, say before 3 seconds, so as not to loose more than 60% of the times the transaction fees present in the block template. This means that a pool admin serving 1000 clients must have a upload bandwidth of at least 60 Mbytes/sec, and load balance servers, because all miners will demand the block template at the same time and will compete for it. The same miner, working solo, will not loose the 60% of block fees. If block fees are 10% of block reward, then solo miners earn 6% more than pool miners. Also, having a block rate of 5 seconds allows solo miners to receive payments more often and so it reduces the payment variance. This method to discourage mining pools only work as long as time is takes to transmit a block is comparable to the block interval time, e.g. 20%. This seems not to be a problem since if the cryptocurrency becomes popular, then we can expect blocks to be near full, while if is is not, then nobody will care about mining pools. For this method to work for Bitcoin, Bitcoin should reduce the block rate to at least 1 minute, and keep blocks of at least 10 Mbytes. Or go the NimbleCoin way, and reduce the block interval to 5 seconds. The sole reduction of the block rate from 10 minutes to 5 seconds would reduce notably the mining reward variance, which is the main reason miners don't mine solo. BitcoinBlockPow The basic BlockPoW is incompatible with Bitcoin ASICs as is but it can be made partially compatible with some tweaks: The value b is replaced by a a a subset or an
Re: [Bitcoin-development] Paper Currency
Alex, I think that what you are talking about more or less something like the Firmcoin Check: http://firmcoin.com/?p=92 On 18/05/2014 08:47 a.m., Alex Kotenko wrote: One problem we couldn't figure out here though - how to protect the notes from unauthorized redeem. Like if someone else tries to reach your wallet with his own NFC - how can we distinguish between deliberate redeem by owner and fraudulent redeem by anybody else with custom built long range NFC antenna? Any ideas? The firmcoin has two capacitive buttons that you have to press in sequence to redeem to coins. No long range antenna can do that. Best regards, Sergio. PS: the device has patents pending -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] DECOR+ Better block selection rule
This e-mail is an extract of my post: http://bitslog.wordpress.com/2014/05/07/decor-2/ Some posts ago I presented the DECOR protocol. One of the assumptions I did was that the amount of coins each miner earned in competing blocks was approximately the same. This could be true for cryptocurrencies with never ending block subsidies (inflationary designs) because the block subsidy may be an order of magnitude higher than the fees collected in the block. In Bitcoin we don’t really know what will happen with fees when the reward is halved. Less we know if in that case the number of transactions per block (and fees collected) will be fairly constant or there will be high variability. If Alice and Bob compete for a certain block height with blocks A and B respectively, and Alice’s block reward (subsidy+fees) is half of Bob’s reward, then even if Hash(A) Hash(B) (and the DECOR incentives are set to prefer A) it may be the case that both Alice and Bob would prefer to mine on top of B since they both earn much more even paying the higher penalty d of burnt coins. In limit cases, Alice’s optimal choice may not be the same as Bob’s optimal choice. I propose a slight modification of the protocol such that even with different block rewards the optimal choice of parent is always the same for all miners. Instead of choosing the block with less hash digest, miners will choose the block with higher reward (subsidy+fees). Splitting the higher reward block would always be more profitable than splitting lowest reward block. In the rare case both blocks have exactly the same reward, then the block with lowest hash is chosen. Even if rewards are approximately equal, the change adds a new monetary incentive to cooperate. Compared with the DECOR protocol, the only modification is in step 6. *DECOR+ Mining strategy* 1. If there is no block Y having a sibling X in the main chain whose reward has not matured then mine in the standard way and exit this procedure 2. Add a reference to Y in the new block that is being prepared. 3. Let x := BlockReward(X) 4. Let q := x*a 5. Let z :=x*b 6. If (BlockReward(X)BlockReward(Y)) OR (BlockReward(X)=BlockReward(Y)) AND (Hash(X)Hash(Y)) then q :=q-(x*c) z :=z+(x*d) 7. Let w :=x*e 8. Add a transaction that has as input the coinbase output of X and has four outputs: o pay q coins to the address specified in the coinbase output of block Y o pay w coins to an owned address o burns z coins o pay the remaining coins to the same address as the input address. BlockReward() returns the block subsidy plus the transaction fees in the block. *Conditions on constants* If you want to choose different values of a,b,c,d,e that still force miners selections converge into a single parent then these conditions must be satisfied: * e 0 * 1-a-e-b a-c * 1+e-a-e-b a-c * a 1-a-c-e-b-d * a+e 1-a-c-e-b-d And all constants are between 0 and 1. It's interesting that now it's much easier to prove that for two competing miners the DECOR+ protocol cannot be abused, since there is no dependence on the block content. Best regards, Sergio. -- Is your legacy SCM system holding you back? Join Perforce May 7 to find out: #149; 3 signs your SCM is hindering your productivity #149; Requirements for releasing software faster #149; Expert tips and advice for migrating your SCM now http://p.sf.net/sfu/perforce___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Block collision resolution using the DECOR protocol and Bonneau's Kickbacks problem
On 02/05/2014 10:56 a.m., Joseph Bonneau wrote: This is an interesting idea Sergio. I have two concerns: You mention 50% of the block reward going to the uncle block. Does this mean the parent gets 1, and the uncle 0.5, or both get 0.5? In the first interpretation (which I assumed was the design), mining is no longer a zero-sum game and this could have lots of unforeseen implications. For example, selfish mining might be more profitable, since you're less disincentivized to avoid conflicts. The second interpretation is the correct one. In the second interpretation, there's pressure to have the next miner ignore the uncle to not share the reward. This would encourage kickback-style attacks and advantage large mining pools because they can mine on their own blocks and ignore colliding uncles. Including an uncle can be done at any time before a coinbase matures (100 blocks) (of course the term uncle is misleading in those cases) . So, for example, the uncle can be included 50 blocks afterward. So it's very difficult that a miner prevents other miners from including the uncle and taking the reward given by uncle inclusion. Same ineffective attack: A big miner could try to bribe all other miners not to include the uncle, but this would be terribly costly. Suppose that I mine a block ignoring an uncle Z and then I publish this message: Every miner from block number X to block number Y that does not include this uncle Z will be given Q Bitcoins. How much would Q be? Since by including the uncle the miner gets 5 BTC of reward (in the example case where block reward is 50 BTC), then each bribery payment would have to be higher than 5 BTC, totaling 500 BTC ! much more than the 25 BTC the miner will loose by including the uncle. Just by sending a transaction with a lot of fees that depends on my block does not prevent subsequent miners from including the supposedly banned uncle. Then, I think there are no kickback-style attacks. Also, I think this came up in the Princeton meet-up, but it's not ideal to just hash the blocks to decide the winner because this lets you know in advance your block's likelihood of winning a collision by looking at how high or low its hash is, in which case you can publish a weak block right away or withhold a strong one and do selfish mining. A better approach to break ties between blocks A and B is to see if H(A||B) H(B||A). That way neither block holder can find out in advance if their block is likely to win a collision. In the DECOR protocol, I think selfish miners cannot get any advantage, because the blocks that loose the latency race will come back as uncles and get their reward share anyway. Maybe Ittay Eyal and Emin Gun Sirer can say more about this... Best regards, Sergio. -- Is your legacy SCM system holding you back? Join Perforce May 7 to find out: #149; 3 signs your SCM is hindering your productivity #149; Requirements for releasing software faster #149; Expert tips and advice for migrating your SCM now http://p.sf.net/sfu/perforce ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] About Compact SPV proofs via block header commitments
On 27/04/2014 02:05 p.m., Mark Friedenbach wrote: On 04/27/2014 05:36 AM, Sergio Lerner wrote: Without invoking moon math or assumptions of honest peers and jamming-free networks, the only way to know a chain is valid is to witness the each and every block. SPV nodes on the other hand, simply trust that the most-work chain is a valid chain, based on economic arguments about the opportunity cost of mining invalid blocks. I argue that you cannot talk about the most-work chain without actually making an assumption about honest peers. I should have said without invoking moon math or interactive protocols requiring honest peers over jamming-free networks. The interactive protocol was more the point than the honest peers and jamming-free network. Yes, without an honest peer and an un-jammed network, you might never learn about the most-work chain in the first place. But having the security of the proof not depend on query access to an honest full node is absolutely necessary for some applications and certainly desirable in others. The problem is not having or not access to a honest full node. The SPV client MUST have access to a honest full node sometime. The problem is WHEN. One can make the security assumption that during an attack (someone gives you a fake block) you also loose the possibility to reach any honest node. Then SPV proofs come into play. Here are the security assumptions I added to my post about SmartSPV to clarify this: *Security Assumptions * First let’s review the main security assumption of headers-only SPV: * The attacker does not control all your communications with the payment network. This means that there is at least a single connected peer that behaves honestly. This assumption is quite strong and may not hold during short periods of time, such as during application power-on (when only a few peers have been connected), or when moving to a place where the ISP is untrusted. For SmartSPV we’ll require weaker security assumptions: * The attacker cannot control all your communications with the payment network for more than a fixed period of time (e.g. 2016 blocks for Bitcoin or approximately 15 days) * The attacker is rational: it won’t spend an huge amount of money to steal a much smaller amount. This assumptions imply that the attacker may control all your Internet connections while he sends you a malicious block branch containing a fake payment to you. First this is a method that uses NPPs, not SPV proofs. Since the method chooses all peers that are synchronized (have the latest current block) then going back means only skipping a potential short fork (which I suppose has never been more than 3 blocks during normal network conditions). You're looking for a common ancestor, not the checkpoint. So the linear scan is actually O(1). The exact value can be approximated by the sum of the convergent infinite geometrical sequence of forking probabilities, which it's about 1.03 without considering selfish-mining, and probably less than 2.03 considering it. Unless you're connected to attacker nodes which are wildly divergent from each other. It's relatively easy to create a massive fake history of difficulty-1 blocks. Since in my use case (SmartSPV) I proposed you start from the most recent block and go backwards, the attacker must compete in PoW with the real current difficulty informed. Suppose the SPV client looks for 6-block chains backwards starting from the last current block. Suppose you know or estimate the current network difficulty. Suppose a malicious peer creates a fake 6-block chain Cm and the honest peer gives you the 6-block chain Ch. If Ch has not the expected work it's discarded. If both has the expected work, then you better not true any of them and walk their parents until you find a common parent. That's the block you should trust. If you don't have an honest node connected, then the only decide to trust or not Cm is by it's accumulated work (and you have already a bound for it) If you assume honest peers things get very easy. But that's not a safe assumption to be making. With back-link block-history commitments, on the other hand, an interactive protocol allows you to do a binary search to find common ancestors, and have trust that the intermediate links actually exist. So you agree that: you need a periodic connection to a honest node, but during an attack you may loose that connection. This is the assumption we should be working on, and my use case (described in http://bitslog.wordpress.com/2014/04/25/smartspv-a-better-simplified-payment-verification-for-smartphones/) assumes that. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available. Simple to use. Nothing
Re: [Bitcoin-development] About Compact SPV proofs via block header commitments
El 27/04/2014 03:43 a.m., Mark Friedenbach escribió: I don't think there's an official definition of SPV proof. I wasn't trying to make a argument from definition (that would be fallacious!). Rather I suspected that we had different concepts in mind and wanted to check. So to disambiguate I define the most general definition as a NPP (non-interactive payment proof). Without invoking moon math or assumptions of honest peers and jamming-free networks, the only way to know a chain is valid is to witness the each and every block. SPV nodes on the other hand, simply trust that the most-work chain is a valid chain, based on economic arguments about the opportunity cost of mining invalid blocks. I argue that you cannot talk about the most-work chain without actually making an assumption about honest peers. If you do not make the assumption, you compute the economic arguments wrong. Now regarding your use case: For the remaining peers, the client starts asking for parents blocks until all parents agree (this is the last common parent). This linear scan of block headers is what I would prefer to avoid. By using back-links you make it have log(N) space usage. First this is a method that uses NPPs, not SPV proofs. Since the method chooses all peers that are synchronized (have the latest current block) then going back means only skipping a potential short fork (which I suppose has never been more than 3 blocks during normal network conditions). You're looking for a common ancestor, not the checkpoint. So the linear scan is actually O(1). The exact value can be approximated by the sum of the convergent infinite geometrical sequence of forking probabilities, which it's about 1.03 without considering selfish-mining, and probably less than 2.03 considering it. -- Start Your Social Network Today - Download eXo Platform Build your Enterprise Intranet with eXo Platform Software Java Based Open Source Intranet - Social, Extensible, Cloud Ready Get Started Now And Turn Your Intranet Into A Collaboration Platform http://p.sf.net/sfu/ExoPlatform ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] About Compact SPV proofs via block header commitments
I read the post in this threads about Compact SPV proofs via block header commitments (archived e-mail in https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg04318.html). I was working on the same problem almost at the same time, which is something that's becoming very common nowadays.. The proposal starts with the following claim: In simple payment verification (SPV) proofs it is currently necessary that every intervening block header be provided between two blocks in order to establish both connectivity and proof of work. I think this is false. Let's first assume that at the time of an attack we're connected only to the attacker (no honest nodes). An non-interactive SPV proof needs to prove that a transaction belongs to the best chain because creating a counterfeit proof cost more than the amount of money involved in the proof. Suppose that the proof consist at least of a block header and a merkle branch to the claimed transaction. Do the proof need connectivity with the last checkpoint known by the verifier? (here checkpoint is any block known for sure to be in the best chain) Not much, because connectivity only proves that the proof was not pre-computed before the checkpoint. Only if the checkpoint is very near (say 10 blocks back) it brings some practical evidence that the attacker did not have much time to prepare an attack. Do the proof need to know the interleaving proof-of-work? Not much. If the distance between blocks is less than 2016 blocks, then the difficulty may have change only by a factor of 4. Currently difficult adjustments are much lower (I suppose that about 1.1 or so). Then one can assume that the proof block target difficulty is almost the same as the last known difficulty if the block distance is less than 2016. If the distance is more, we just load all the interleaving re-target blocks to detect the actual difficulty. Do the proof need to have a certain number of confirmations? Yes and no, because this is the only evidence that the prover has either spend money in creating the fake block or took a genuine block. The cost of creating a fake block can be approximated as the minimum of: - The current reward of the block (since currently fees are much lower than the reward) - The average block fees (when the reward goes to zero) - The minimum electricity cost of mining the block. As time passes one could assume that the electricity cost of mining will approach the other two. But there is the problem of parallel synchronized attacks: if an attacker can reuse the same fake SPV proof to attack several victims, then the reward for cheating increases proportionally but the cost stays the same. For instance, if 6 confirmations are required, and each block can hold 2000 transactions, the attacker can find 2000 victims and re-use the same 6 block chain to prove payments to 2000 victims. Also the cost of mining 6 blocks can be amortized by mining 7, and attacking in the first two 4000 victims, etc... Any scheme than relies on non-interactive SPV proofs will fail if Bitcoin will scale up-to a point where victims can be easily found and synchronized. So I think one should assume that at least one peer is honest... But if we assume than during the attack least one peer is honest, then we could directly ask every peer to give us the blocks of their best-chains at the same heights of the presented proof. No back-links are necessary. If any peer shows a different block, then we should carefully detect which of the two nodes is the one attacking us and ban it, by downloading the best-chain headers from the last checkpoint to the block of the proof. This would be rare so I don't see when the back-links can help. The use case should be: ==Use cases== For SPV client that has just come online asks peers what is the last block height/time. If a peer replies with an old block, then that peer is still downloading the block-chain and it's ignored. For the remaining peers, the client starts asking for parents blocks until all parents agree (this is the last common parent). If (U)TxO hash-tree commitments are available, then the wallet is updated using this data from the common parent block. At the same time the client retrieves compact non-interactive proofs-of-inclusion (possibly orphan) for its transactions without having to download every intervening block header. Is there something wrong with this? Best regards, Sergio. -- Start Your Social Network Today - Download eXo Platform Build your Enterprise Intranet with eXo Platform Software Java Based Open Source Intranet - Social, Extensible, Cloud Ready Get Started Now And Turn Your Intranet Into A Collaboration Platform http://p.sf.net/sfu/ExoPlatform ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net
Re: [Bitcoin-development] About Compact SPV proofs via block header commitments
El 26/04/2014 10:43 p.m., Mark Friedenbach escribió: Sergio, First of all, let's define what an SPV proof is: it is a succinct sequence of bits which can be transmitted as part of a non-interactive protocol that convincingly establishes for a client without access to the block chain that for some block B, B has an ancestor A at some specified height and work distance back, and the cost of creating a false proof is at least as much work as it claims to represent. Ok. I was thinking with another definition SPV proof. For me a SPV proof is a sequence of bits which can be transmitted as part of a non-interactive protocol that convincingly establishes for a client without access to the block chain that a block B is part of the best-chain. I understand that SPV nodes require SPV proofs as defined in my definition, but I can't realize how to prove that SPV nodes require SPV proofs under your definition. So your definition sounds to me like one possible solution, but not the need. Is your definition something well-established in the community? -- Start Your Social Network Today - Download eXo Platform Build your Enterprise Intranet with eXo Platform Software Java Based Open Source Intranet - Social, Extensible, Cloud Ready Get Started Now And Turn Your Intranet Into A Collaboration Platform http://p.sf.net/sfu/ExoPlatform ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Coinbase reallocation to discourage Finney attacks
On 23/04/2014 05:51 p.m., Mike Hearn wrote: On Wed, Apr 23, 2014 at 10:44 PM, Adam Ritter arit...@gmail.com mailto:arit...@gmail.com wrote: Isn't a faster blockchain for transactions (maybe as a sidechain) solving the problem? If there would be a safe way for 0-confirmation transactions, the Bitcoin blockchain wouldn't even be needed. The 10 minute average comes from a desire to balance wasted work due to natural chain splits with latency. With a very fast block interval you end up with lots of forks and things take longer to converge, also, it can make attacks easier because an attacker is building on his own blocks so he doesn't suffer propagation delays and the attendant splits. It's not clear you can just make a faster block chain. 10 minutes is somewhat arbitrary, it could be 5 minutes and the system would still work, but it probably can't be 5 seconds. 5 seconds block interval is possible. I've simulate it with great success and I encourage anyone to repeat or check my simulations. There are a very few protocol modifications that are required to allow 5 seconds block, and most of them have already been discussed in the forums. For more information you can check my post: http://bitslog.wordpress.com/2014/02/17/5-sec-block-interval/ Also NimbleCoin is a new alt-coin that uses 5-sec block intervals, allows 100 tps and it's based on BitcoinJ (NimbleCoinJ now). So not only it is possible, but it was coded by Mike itself. Important note: the 5-sec block interval method probably requires a block reward forever. It doesn't work well if there is no block reward at all. Unfortunately for best physical-world usability you really need very fast payments. A few seconds is competitive with modern credit cards. Another solution to achieve 5 secs block intervals is this: http://bitslog.wordpress.com/2014/03/20/mincen-a-new-protocol-to-achieve-instant-payments/ So the problem with 0-confirmations is solely of Bitcoin and other alt-coins, new alt-coins may achieve instant transactions and no not have to rely on 0-confirmations. Best regards, Sergio. -- Start Your Social Network Today - Download eXo Platform Build your Enterprise Intranet with eXo Platform Software Java Based Open Source Intranet - Social, Extensible, Cloud Ready Get Started Now And Turn Your Intranet Into A Collaboration Platform http://p.sf.net/sfu/ExoPlatform___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Coinbase reallocation to discourage Finney attacks]
(this e-mail is cc to the bitcoin-research list) Hi everyone from the bitcoin-development mailing list! I decided to join this legendary list because it seems that all the research fun is taking place in here, and I don't want to miss the research party. Regarding the discussion about BitUndo, a year ago I posted about an attack (which I called the the Bitcoin Eternal Choice for the Dark Side Attack or ECDSA) that tries to erode the confidence in Bitcoin by offering double-spends as a service. I think it's related to the last post from Peter Todd about the problems with BitUndo. Here is the link if anyone is interested in reading about it... http://bitslog.wordpress.com/2013/06/26/the-bitcoin-eternal-choice-for-the-dark-side-attack-ecdsa/ Sergio D. Lerner. On 23/04/2014 12:29 p.m., Peter Todd wrote: Interesting discussion re: incentive compatibility happening on the bitcoin-development email list: - Forwarded message from Mike Hearn m...@plan99.net - Date: Wed, 23 Apr 2014 09:55:30 +0200 From: Mike Hearn m...@plan99.net To: Bitcoin Dev bitcoin-development@lists.sourceforge.net Subject: [Bitcoin-development] Coinbase reallocation to discourage Finney attacks Lately someone launched Finney attacks as a service (BitUndo). As a reminder for newcomers, Finney attacks are where a miner secretly works on a block containing a double spend. When they eventually find a block, they run to the merchant and pay, then broadcast the block. In a simpler variant of this attack you make purchases as normal with a modified wallet that always submits a double spend to the service, and then N% of the time where N is the percentage of overall hash power the dishonest miners have, you get your money back minus their fee. N does not need to be very high to render Bitcoin much less useful. Real time transactions are very important. Although I never expected it when I first started using Bitcoin, nowadays most of my purchases with it are for food and drink. If Bitcoin could not support such purchases, I would use it much less. Even with their woeful security many merchants see 1-2% credit card chargeback rates, and chargebacks can be disputed. In fact merchants win about 40% of chargeback disputes. So if N was only, say, 5%, and there was a large enough population of users who were systematically trying to defraud merchants, we'd already be having worse security than magstripe credit cards. EMV transactions have loss rates in the noise, so for merchants who take those Bitcoin would be dramatically less secure. The idea of discouraging blocks that perform Finney attacks by having honest miners refuse to build on them has been proposed. But it has a couple of problems: 1. It's hard to automatically detect Finney attacks. Looking for blocks that contain unseen transactions that override the mempool doesn't work - the dishonest users could broadcast all their double spends once a Finney block was found and then broadcast the block immediately afterwards, thus making the block look like any other would in the presence of double spends. 2. If they could be automatically identified, it possibly could be converted into a DoS on the network by broadcasting double spends in such a way that the system races, and every miner produces a block that looks like a Finney attack to some of the others. The chain would stop advancing. 3. Miners who want to vote no on a block take a big risk, they could be on the losing side of the fork and end up wasting their work. We can resolve these problems with a couple of tweaks: 1. Dishonest blocks can be identified out of band, by having honest miners submit double spends against themselves to the service anonymously using a separate tool. When their own double spend appears they know the block is bad. 2. Miners can vote to reallocate the coinbase value of bad blocks before they mature. If a majority of blocks leading up to maturity vote for reallocation, the value goes into a pot that subsequent blocks are allowed to claim for themselves. Thus there is no risk to voting no on a block, the work done by the Finney attacker is not wasted, and users do not have to suffer through huge reorgs. This may seem a radical suggestion, but I think it's much less radical than some of the others being thrown around. The above approach works as long as the majority of hashpower is honest, defined to mean, working to stop double spending. This is the same security property as described in the white paper, thus this introduces no new security assumptions. Note that assuming *all* miners are dishonest and are willing to double spend automatically resolves the Bitcoin experiment as a failure, because that would invalidate the entire theory upon which the system is built. That doesn't mean the assumption is wrong! It may be that an entirely unregulated market for double
