Thottbot ethereum prison key
42 comments
Litecoin minergate
Like many cryptographic algorithms hashcash uses a hash function as a building block, in the same way that HMAC, or RSA signatures are defined on a pluggable hash-function commonly denoted by the naming convention of algorithm-hash: The Hashcash proof-of-work function was invented in by Adam Back , and proposed for anti-DoS uses including preventing: Before bitcoin, hashcash was used by SpamAssasin, and with an incompatible format by Microsoft with the name "email postmark" in hotmail, exchange, outlook etc and by i2p anonymity network, mixmaster anonymous remailer components and other systems.
Wei Dai 's B-money Proposal , and Nick Szabo 's similar Bit Gold proposal bitcoin precursors, also were proposed in the context of hashcash mining. In the original algorithm hashcash used SHA1 because at that time, this was the defacto and NIST recommended hash, and the previous defacto hash MD5 had recently started to show signs of weakness.
There is actually no strong reason SHA1 would not have worked also, hashcash relies only on the hash partial preimage resistance property security up to hash-size, bit with SHA1 and not birthday collision hardness security up to bit , so the SHA1 hash is big enough.
Bitcoin is anyway built to bit security because bit ECDSA is used, which also offers bit security. Never the less SHA is the correct and more conservative choice because even SHA1 has started to show some weakenesses, though only in birthday collision, not in 2nd-preimage. While hashcash relies on pre-image resistance and so is not vulnerable to birthday attacks, a generic method of hardening SHA1 against the birthday collision attack is to iterate it twice.
And this is what bitcoin does, it is not necessary given hashcash reliance on preimage security, but it is a defensive step against future cryptanalytic developments. It seems clear from the SHA1 break, and SHA is a similar design, that there was previously a misunderstanding about the security of hash functions against birthday collisions, and SHA3 finalists all aim to fix that issue.
One aspect of relevance for hashcash-SHA3 is that there is some debate within the NIST comments process on the proposal of weakening SHA3's resistance to pre-image attacks down to bit vs the full hash size as with previous hashes. The motivation is a small performance gain, with the rationale that some hash-pluggable algorithms do not rely on full-length pre-image resistance. The proposal has met with significant negative feedback due to it creating a non-standard security assumption compared to all previous hashes , and therefore it creates risk and all hash-pluggable algorithms like HMAC, RSA, DSA, hashcash etc would need to be re-examined on a case by case basis to see if SHA3 is safe to use with them; from the balance of the feedback it seems probable that NIST will accept the feedback and SHA3 will retain the full bit pre-image resistance.
One likely side-effect however would be that it would introduce more memory or pre-computation tradeoffs which could make ASICs unprofitable, or give advantages to people with large resources to do the pre-computations. Pre-computation advantages would perhaps be enough motivation to replace the hash with SHA3. Anyway this is all speculation if and until any pre-image affecting cryptanalytic attacks are found on SHA The hashcash algorithm is relatively simple to understand.
The idea builds on a security property of cryptographic hashes, that they are designed to be hard to invert so-called one-way or pre-image resistant property. It takes a lot of memory, but there are memory-time tradeoffs.
This is also equally fair and only requires one hash invocation to verify vs two with 2nd partial-pre-images. It is actually the output that partially matches, not the pre-image, so could perhaps more accurately called a pre-image with a partial output match, however partial pre-image effectively a short-hand for that. The miner varies counter c until this is true. The service string could be a web server domain name, a recipients email address, or in bitcoin a block of the bitcoin blockchain ledger.
One additional problem is that if multiple people are mining, using the same service string, they must not start with the same x or they may end up with the same proof, and anyone looking at it will not honor a duplicated copy of the same work as it could have been copied without work, the first to present it will be rewarded, and others will find their work rejected.
This is what hashcash version 1 and bitcoin does. In fact in bitcoin the service string is the coinbase and the coinbase includes the recipients reward address, as well as the transactions to validate in the block.
Bitcoin actually does not include a random start point x, reusing the reward address as the randomization factor to avoid collisions for this random start point purpose, which saves bytes of space in the coinbase. For privacy bitcoin expect the miner to use a different reward address on each successful block. A lot of hashcash design choices are motivated by simplicity. Of course because of luck the block time actually has quite high variance, but the average is still more accurately targeted by the introduction of fractional k.
Bitcoin also defines a new notion of relative difficulty which is the work required so that at current network hashrate a block is expected to be found every 10 minutes. Bitcoin difficulty is simple to approximately convert to log2 cryptographic security: In principle a miner should therefore for privacy use a different reward-address for each block and reset the counter to 0.
Why Satoshi's early mined bitcoins were potentially linked, was because while he changed the reward-addresss, he forgot to reset the counter after each successful mine, which is a bitcoin mining privacy bug. In fact with bitcoin the counter also should be obscured otherwise you would reveal your effort level, and if you have a lot of mining power that may imply who the coin belongs to.
Bitcoin does this via the nonce and extra-nonce. Nonce starts at 0, but extra nonce is random. Together these form a randomized counter hiding the amount of effort that went into the proof, so no one can tell if it was a powerful but unlucky miner who worked hard, or a weak miner who was very lucky. Additionally with the introduction of mining pools, if the miner uses the same reward address for all users, which is what the current mining protocols do, then there is risk that users may redo work.
To avoid users redoing work, miners hand out defined work for the users to do. However this creates an unnecessary communication round trip and in early protocol versions perhaps was a factor in the decision to have the pool send the actual block to mine, which means the miners are not validating their own blocks, which delegates validation authority, though not work, to the pool operator, reducing the security of the bitcoin network.
The more recent mining protocol version allows the user to add their own block definition, but still unnecessarily incur round trips for handing out work allocation. Because the new pooled-mining protocol has a miner chosen extraNonce this acts as a random start factor so there is actually no need to talk to the pool for work allocation, a pool could have a static published address, and miners could just do work of whatever size they chose, and submit it to the pool as a UDP packet.
If privacy is required by the miner, it could use the public derivation method from BIP 32 to allow the node to tell the miner via an encrypted message with the mining work, which factor to multiply the static public key by. It is a misunderstanding to talk about the Scrypt proof-of-work. Scrypt is not intended as a proof-of-work function, but a stretched key-derivation function, and while it is by design expensive to compute with high iterations, it can not be used to make an efficiently publicly auditable proof-of-work, as verifying costs the same as creating.
Hashcash with the internal hash function of Scrypt may be denoted hashcash-Scrypt 1. Scrypt, by Colin Percival, is a key-derivation function for converting user chosen passphrases into keys. This does not use the key-stretching feature of Scrypt so mining is not actually using Scrypt directly, but only the inner Scrypt hash accessed by setting the iteration parameter to one iteration.
So Scrypt's key-stretching function is not being used at all to contribute to the hardness, unlike its normal use for key protection eg in deriving the encryption key from user passphrase to encrypt bitcoin wallets. The reason Scrypt's key-stretching can not be used for mining is because that simultaneously makes it more expensive to verify by the same factor.
The other major scrypt parameter denotes the amount of memory used usually kB. The kB Scrypt memory footprint makes litecoin arguably less vulnerable to centralization of mining power arising from limited access to or ownership of ASIC equipment by users. It's arguable and unclear, because there are counter arguments: This simplicity ensures that many people will do it and ASICs should become available.
Conversely it is somewhat more difficult in comparison to make an hashcash-Scrypt 1 ASIC so perhaps litecoin will prove in the mid-term actually worse for centralization, if a well funded commercial entity corners the market by having faster, but proprietary, not available on the market, hashcash-Scrypt 1 ASICs that render litecoin GPU mining unprofitable.
This is claimed because of the argument that the die area taken up by kB of RAM, which it might be thought must be dedicated to each Scrypt 1 core, would reduce the number of Scrypt 1 cores that fit per chip.
Note however that Scrypt 1 is not actually securely memory-hard in that it makes no attempt to prevent time-memory tradeoffs, so it is actually possible to repeat the computation of internal rounds to reduce the memory requirement.
In hardware the time-memory tradeoff would be optimized to find the optimal amount of memory to use, and it is quite possible the optimal amount would be less than kB. This makes validating the litecoin blockchain more CPU and memory intensive for all full nodes. Note however that the dominating CPU work of validation is the verification of the per transaction ECDSA signatures of the multiple transactions in a block.
This page explains hashcash and how bitcoin uses it. Retrieved from " https: Navigation menu Personal tools Create account Log in. Views Read View source View history. Sister projects Essays Source.
This page was last edited on 25 March , at Content is available under Creative Commons Attribution 3. Privacy policy About Bitcoin Wiki Disclaimers.