Our updates:
1. The problem that I have with scrypt or SeqMemoHash is that they are not memory-hard enough; they are just as memory-hard to verify as they are to compute, which puts a natural cap on how high the parameters can be tweaked. The reason why I came up with Dagger in the first place was to create a PoW that is memory-hard to compute but memory-easy to verify, since you only need a small amount of memory for one nonce, so that you can tweak up the memory requirement per thread to an extremely high value., proof-of-burn and proof-of-excellence based submissions will also be welcome in some category.
In the post I present a technique to limit the amount of work a node does, not to do any more work than the attackers work. I repost part of the paper here: Gradual verification When SeqMemoHash or RandMemoHash are used as PoW, an attacker may try a DoS attack by cheating on the difficulty of the PoW, and forcing the verifier to invest CPU resources in computing the (invalid) MemoHash digest. One way of protecting from this attack is by creating a PoW that consist of the concatenation of all intermediate results produced at steps that are power of two (e.g. at hashing steps 1,2,4,8, ..), and the final result. For the configuration given in the previous section, this requires 17 intermediate hash digests and the final hash digest (total- ing 576 bytes). The verifier must check each intermediate state against the given values during the computation. This protection assures that the attacker must have performed at least half of the operations performed by the verifier Also I added RandMemoHash, which (as I tested it) is almost as fast as scrypt also using Salsa20/8 core. With the parameters I suggest for ASIC resistance, it takes 30 msec to verify on a PC. Using the Salsa20/8 core, it takes less. Best regards! |
|
|
|
One of the features in Ethereum is the use of a PoW function specially designed to be memory-hard. While this may be true (though a formal proof is missing and the design document is quite incomplete), the authors completely forgets another key property a PoW function must provide: it must be sequential-memory hard. This means that not only the function should require large amounts of RAM, but it must not allow easy parallelization. Dagger seems to provide almost the best possible scenario for parallelization. In Dagger, a certain amount of RAM is filled by pseudo-random data derived from the header and the nonce. This data is produced in rounds. Each round, a number of elements from the previous round outputs are hashed together to produce the elements of the following round. These hashes can be performed in parallel. An optimized implementation for an ASIC (or FPGA) is evident for anyone with some discrete logic design background. A speedup from 256X to 2560X seems possible. I posted more on this issue here: http://bitslog.wordpress.com/2014/01/17/ethereum-dagger-pow-is-flawed/My own proposal (SeqMemoHash) solves this problem ( http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/) Best regards, Sergio. |
|
|
|
One of the features in Ethereum is the use of a PoW function specially designed to be memory-hard. While this may be true (though a formal proof is missing and the design document is quite incomplete), the authors completely forgets another key property a PoW function must provide: it must be sequential-memory hard. This means that not only the function should require large amounts of RAM, but it must not allow easy parallelization. Dagger seems to provide almost the best possible scenario for parallelization. In Dagger, a certain amount of RAM is filled by pseudo-random data derived from the header and the nonce. This data is produced in rounds. Each round, a number of elements from the previous round outputs are hashed together to produce the elements of the following round. These hashes can be performed in parallel. An optimized implementation for an ASIC (or FPGA) is evident for anyone with some discrete logic design background. A speedup from 256X to 2560X seems possible. I posted more on this issue here: http://bitslog.wordpress.com/2014/01/17/ethereum-dagger-pow-is-flawed/My own proposal (SeqMemoHash) solves this problem ( http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/) Best regards, Sergio. |
|
|
|
For blockchain.info orphan == stale (definition in https://blockchain.info/orphaned-blocks) This is a technical mistake, since "orphan" means "no parent", but this is how the term has been used, not only there but also in https://en.bitcoin.it/wiki/Orphan_BlockAs I understand, stale blocks will be forwarded to all the network, even if they are not in the best chain. So all nodes known how many stale blocks are created. |
|
|
|
|
Does anyone know a web page which shows a live statistic of the number of orphans created in a day ?
Is there any paper that presents this information?
Have anyone computed the average orphan rate during last year and previous years?
Best regards,
Sergio.
|
|
|
|
|
In a state of the system where the block reward has reached zero, the following protocol can work:
As in the previous other proposal each node adds something to the transaction. In this proposal, each transaction is stored in a Paycket.
A Paycket consist of :
- A transaction (Tx)
- A list of payment addresses (PayList) corresponding to the nodes that forwarded the transaction from the source to the destination.
Nodes only append the 20-byte hash of the pubkey to the PayList.
Each node is connected to N peers. For each peer the node maintains a data structure SendTo[N] which is a priority queue of the IPs (or node IDs) where a paycket origination from N should be sent, and in which priority order
When a node receives a paycket, is responds to the sending node with a new pubkeyhash created for that paycket.
When a node forwards a Paycket, it records the IP address (or ID) of the node that sent the paycket and the pubkeyhashes of the nodes where the paycket was forwarded, in SentFromTo[TxHash] --> [From, Map<node_id,pubkeyhash> ]. It also appends his own new address (the one sent back to the sender) into the PayList.
When a node receives a block, it checks each transaction to see it corresponds to any of the transaction in SentFromTo[]. If it does, it checks if his pubkey is in PayList field of the paycket. If it does, then it increases the priority in SendTo[From] to the node_id corresponding to the pubkeyhash that followed himself in the list.
If his pubkeyhash is NOT in the PayList, then it decreases the priority of all nodes in SendTo[From] for which the paycket was actually sent. A node with a priority below a certain threshold do not receive any more transaction from that peer. If the priority reaches another low threshold, they can be directly disconnected.
If the address that follows the node is not in the PayList, it means that the node that received the paycket lied about its address, or any other node following that node (including the miner). The best he can do is decrease the priority of that node, as being less trusted.
The addresses in the PayList share a percentage of the transaction fee (e.g. 10%)
After some time, the network will organize itself as a tree with some redundant branches, but where all paths are near optimal paths to the miners.
Also if a miner erases addresses from the PayList to receive a greater share of the fees, nodes will slowly begin to stop forwarding the transactions to that miner (a monetary punishment). Miners that never include addresses in their paylists will be completely banned from the network.
Any new node that tries to connect to the network will start with a low priority, so transactions will not be forwarded to the new node (but blocks will always be).
Note that a similar priority data structure can be used in the other direction to optimally send blocks from one miner to the other and reduce block propagation time. These both ideas are currently under test in the QixCoin alt-coin.
Regards, Sergio.
|
|
|
|
|
Here is an idea that can reward transaction forwarders as long as the block reward exists:
A transaction can be stored in a Packet. Packets travel the network are are included in blocks (as transactions).
A packet contains:
- A transaction or another packet.
- The hash of a ECDSA pubkey (20 bytes)
- A nonce (4 bytes)
The PoW of a packet is computed as Hash ( Hash(Tx) || key || nonce)
When a node receives a packet or a transaction he decides to store it in another packet or forward it as is.
If he decides to re-packet it, the node tries many nonces until a certain PoW is found.
If a packet is received in a block, money is minted specifically to pay for the PoW of the packets (the reward is NOT taken from the fees nor from the block reward).
Suppose that the packet PoW is P, the difficulty of the block is D, and the block reward is R. When a nodes receives a packet in a block, it creates a "packet coinbase transaction" that pays P*R*C/D coins to the key specified in the packet (is multiple packets surround a transaction, each key is paid independently), where D is a constant < 1 such as 0.1. Also if a block contains N packets, and the block size is B, then the miner of the block receives an additional reward of N*24*R*D/B, which compensates the miner of the additional space used for the packet overhead.
Setting D = 0.1 means that nodes are paid much less (10%) of what miners are being paid, which means that the incentive for mining is greater than the incentive for packet forwarding.
So nodes will try to make a rational decision regarding re-packeting a tx considering the hop distance to the miner, the packet size, the reward and the available computing resources. Also they cannot hold the tx for too much time, since the same tx may arrive to the miner from another path and make the node waste the invested packet PoW. Also miners have no incentive to exclude the packets, because they earn an extra reward on packet headers. So as long as there is a block reward, there will be an equilibrium where nodes delay transactions a few milliseconds to collect micro-payments for packet forwarding.
Knowing the current cost of SHA-256 mining vs scrypt mining (with high memory requirements), the network could set a different PoW algorithm for forwarding (such as scrypt) and still assure that the incentive for mining is always much higher than the incentive for adding packet PoWs.
In the next post I propose another way to solve if there is no block reward.
|
|
|
|
|
I also have these files, sent to me by one of the early reviewers of the code.
Another interesting fact (I talked in laBitConf) is the fact that there was already a genesis block in it, which was obviously discarded after testing was done.
Still other interesting facts are these comments in main.h
///static const unsigned int MINPROOFOFWORK = 40; /// need to decide the right difficulty to start with
static const unsigned int MINPROOFOFWORK = 20; /// ridiculously easy for testing
So Satoshi may had the capability of 2^40 hashes per 10 minute interval (but he finally fixed it at 32).
These were the latest changes during that period:
* Two more decimal digits for BTC denomination
* Added nSequence to TxOut
* Added nVersion to Block
* Changed nBits from zero bit count to compact target format.
Regards, Sergio.
|
|
|
|
I checked the page http://luke.dashjr.org/programs/bitcoin/files/charts/security.html which tracks the different clients in existence and I found strange that BitcoinJ (/BitCoinJ:xxx) is not listed (since it's one of the best clear re-implementations of the protocol). I suppose that wallet applications that use Bitcoinj change the id. Android Wallets may not be much time online, so that may be the reason. There are several that I know are based on Bitcoinj such as "Bitcoin wallet" and "Blockchain.info". Any idea? |
|
|
|
|
Re-thinking: In TierNolan's protocol, the attacker could include in the fork many (almost all) the transactions in the previous best chain, except for the redeem transactions he's attacking. I have no idea of what people will think of a kind of targeted attack that replaces a 50-block branch with another with almost the same transactions, but not all. But nothing good....
|
|
|
|
Isn't it the case that the other coin-swapping protocols are susceptible to this same weakness? This applies generally to double-spends too. The cost of mining a big-enough "attack fork" can be amortized over many concurrent double-spend attacks using the same attack fork.
Yes, you're partially right, but I think there is at least one key difference. The difference that comes to my mind is the "visibility" of the attack event: in TierNolan's protocol the attacker would need to create a long fork that everyone will see and that will become the best chain, and that will roll back tens of thousands of normal transactions, and that will destroy the credibility of one of the cryptocurrency involved. So the attack cannot be profited: if the attacker tries to cheat and get the coins of both cryptocurrencies in the trade, one of them will loose completely its value, so there is no incentive for the attack. Also the attack cannot be repeated. In p2ptradex you may do it without affecting the users of the BTC side of the chain. The attack will just prove that with enough incentives an attacker can "hire" mining power and execute the parallel attack and build a competing block branch, but without actually putting this branch "life". If does not need to be the best chain. The fake chain will only be used to prove other users that certain transactions were done, when in fact they weren't. This does not destroy the credibility of the system, but just proves that the users did not paid attention to the recommended maximum trading limits, and made risky operations. Iit has to be carefully analyzed in TierNolan's protocol what's the effect to forking at each protocol step, but I think that in every possible attack the attacker must build and publish his own long best chain. Also in both protocols there is the possibility of a miners-conspirancy not to include certain "redeem" transaction, but this will require almost all miners to be part of the clan. |
|
|
|
|
A better analysis:
Suppose that the proof length is k=6 and that each block can carry n transactions, and the block can be rooted at most t=6 blocks in the past. If the block reward is 25 BTC, then the attacker may try to attack n*t victims by mining (t+k) blocks, and filling the first t blocks with n*t fake transactions. This will cost the attacker 25*(t+k) BTC. This limits the amount of money that can be safely traded in each transaction to 25*(t+k)/(n*t). Currently n is approximately 2200, and assuming t=k=6 we have that the maximum would be 22 mBTC per transaction, or 22 USD at 1K USD/BTC exchange rate, for a 6 block length contract. If the contract specifies values of k much higher than t, then the t value in the upper term can be ignored. The approximate formula for the upper limit when t=6 becomes 1.8*k mBTC.
A trade of 1 BTC in a single transaction will therefore require almost 3 days to be executed.
|
|
|
|
I came up with an attack on my P2PTradeX protocol ( https://bitcointalk.org/index.php?topic=91843.0), which, in most cases, would thwart severely its utility. Let’s first review the protocol. A first party issues a conditional transaction in a block chain X, which contains a contract. The contract requests the the other party to provide a proof that a payment has been issued on the Bitcoin block chain. The proof consist of a Merkle branch from the Merkle root to the paying transaction, the block header plus the block headers of several confirmation blocks. The attack works as follows: if the attacker can perform simultaneous trades, then he can create a single counterfeit block branch containing many fake transactions. Almost 2200 standard looking fake transactions can be stored in a block. This block branch can be presented simultaneously to all the traders, sharing the cost of orphan mining over all the executed trades. The attack can be “pipelined” so the counterfeit branch is partially reused for each new batch of attacks performed in each new block. If the block reward is 25 BTC, then this limits the amount of money that can be safely traded to 11 mBTC per transaction, or 11 USD at 1K USD/BTC exchange rate. MitigationsIf you want to trade higher amounts (say n BTC) you should either trade them by dividing n in many transactions of 11 mBTC each or, better, create a transaction whose size is (n*0.011) times the standard transaction size, adding more inputs. Outputs could also be added, but some other standard condition must be specified on transactions to avoid reusing the outputs for different trades. Since traders request block chain branches that are recent, the attacker may not be able to reuse the fake block chain branch for many block intervals. To achieve the maximum revenue from the attack, the attacker may need to perform millions of simultaneous trades, at a rate of 3.6 trades per second. This may be impractical due to the lack of market for trades. If the trading market executes 1 order per second (1/7 of the maximum Bitcoin transaction rate) then the maximum secure trade per transaction rises to 40 mBTC. Last, if the Bitcoin chain has periodic checkpoints (e.g. 1 per day) signed by a trusted authority, then the contracts may specify that the last block header should be check-pointed. This eliminates the problem completely but slows downs trade rate considerably and requires a TTP. ConclusionIt’s has to be evaluated if the P2PTradeX is worth it’s complexity now that it has been found that it severely limits the amounts traded. Recently some other protocols have been designed that achieve the same result but do not require changing the core protocol, such as the one described by Socrates1024 in https://bitcointalk.org/index.php?topic=193281.msg3315031#msg3315031. In comparison Socreates1024 protocol requires that some non-standard transaction templates are re-enabled in both block-chains but does not limit the amounts traded, while P2PTradeX does not impose any restriction on the Bitcoin side, while requires much computing effort on the alternate coin side, and restricts traded amounts. |
|
|
|
I don't have the best idea. No one can claim to have the best idea. But I'm unsure if I'd like to be remembered as the guy that facilitated global crime.
Already done. So you can't be remembered as such, because somebody already did it (or will do it soon) ! Do you get the logic ? CoinSwap. CoinJoin. CoinControl. ZeroCoin. BlockChain info's CoinJoin implementation. Hello ? Sergio ? You there ?Yes, I'm here. And some of the arguments I read these days made me change my mind. So yesterday I began finishing the preliminary paper I started long ago.. |
|
|
|
I think eg if you read the original zercoin paper and I said similar things on bitcointalk that anonymity is the ideal building block. What you can build with it is many permutations of desired and useful privacy levels. It doesnt have to be full payee & payer anonymous just because the building block supports that. And there are many reasons in the real world that you dont get that privacy in practice. IP logging, IP geolocation, physical shipping address, knowledge of you by the person you are paying/receiving from, privacy mistakes etc.
Agree, but the protocol must support those levels of anonymity. Kind of odd if you are sitting on the holygrail crypto and not publishing for some kind of ethical considerations?
I didn't say it was the holygrail. It has advantages over the other protocols (uses old more proven crypto) and some disadvantages. The greater disadvantage is that it was not widely reviewed. But ethic was not the only reason, the other reason is that I don't like writing proofs of any crypto I do. Ok. I'll reconsider. ps Personally I think gambling has far more ethical worries than users being able to transact privately with something approaching the analogous already existing levels of privacy in other systems. For some people gambling becomes a near ruining addiction.
The levels of online poker gambling addiction are far lower than the levels of real-word casino addictions. Also the software I developing has all kinds of controls against problem gambling (but of course, you can recompile it and remove all those checks, since it will be open sourced). Best regards, Sergio. |
|
|
|
Ouch .... but it crossed my mind also.
So Sergio are you ever going to publish? Have you looked at the arguments regarding fungibility? If you truly have an idea that is possibly the best money humanity can have,
I don't have the best idea. No one can claim to have the best idea. But I'm unsure if I'd like to be remembered as the guy that facilitated global crime. the enormous economic benefits alone far outweigh any moral quandaries provide by a few errant users of the money (who, after all, have to answer to their God and their peers ultimately for their actions whatever the medium is that they choose to perpetrate them with).
If you're religious, then it's true. But still I want a paper with numbers that proves that the economic benefits of a truly anonymous untraceable coin outweigh the problems it may bring. Or a paper that proposes a system where governments may have a trapdoor to allow them get trace of all transactions over 1 M USD but no trace of transactions of lower value. ... ohhh.. I've may have came up with an idea to do just that.  |
|
|
|
|
All these problems, like hiding the transfer amount , and anonymization, etc were solved (*) by my Appecoin protocol.
Appecoin proofs are relatively small, and fast to verify.
The fact that I didn't publish it (for a year) is that I still have moral doubts of enabling a completely anonymous payment system. Somebody has to proof that the benefit of such system outweigh the costs of its illegal use.
I hope Adam you're sure that you solved that dilemma when you finally build your own protocol.
(*) This is not completely true, since my paper has received little peer review, it might contain mistakes.
|
|
|
|
|
Show Posts
