HashCash
The term HashCash: Defined in Cryptocurrency in this page explains hashcash and how bitcoin uses it.
Bitcoin uses the hashcash Proof_of_work
functions as a mining core.
All bitcoin miners whether CPU, GPU, FPGA
or ASICs are creating hashcash proofs-of-work
which is the blockchain evolution and validate the
blockchain transaction log.
Algorithms hashcash uses hash function s
as a building block, in the same way that HMAC, or RSA signatures are
defined on a pluggable hash-function.
This is commonly denoted by naming an algorithm-hash: HMAC-SHA1, HMAC-MD5, HMAC-SHA256,
RSA-SHA1, etc, hashcash can be instantiated with different functions,
hashcash-SHA1, hashcash-SHA256^2 (bitcoin),
hashcash-Scrypt(iter=1).
History
Hashcash / proof-of-work function invented in 1997 by Adam Back,
and proposed for anti-DoS attack uses preventing the anonymous remailer
and mail2news gateway abuse.
The name "nym" on nymservers is a pseudonymous for remailer severs and as a general email
anti-spam, and general network abuse throttling.
Before bitcoin hashcash
was used by SpamAssasin, and the incompatible format by Microsoft named "email postmark" in hotmail, exchange, outlook etc and
by i2p anonymity network, mixmaster anonymous remailer components and
other systems.
Hashcash was also used by Hal Finney's bitcoin precursor RPOW as a way to mine coins.
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.
Hash functions
In 1997 algorithm hashcash that used SHA1, because at that
time, this is/was their defacto and the NIST recommended hash, and the previous
defacto hash MD5 had recently started to show signs of weakness, and as all do over time.
Bitcoin
being specified/released in 2008/2009 uses SHA256 and improving.
There is no
strong reason SHA1 will not have worked, and hashcash relies only on
the hash partial preimage resistance property which is a security up to hash-size,
160-bit with SHA1, and security up to
80-bit), so the SHA1 hash is big enough, but...
Bitcoin is built to
128-bit security related to 256-bit ECDSA being used, which also offers
128-bit security.
The SHA256 is more
conservative choice and SHA1 has started to show some weaknesses.
Cryptanalytic Risk
An issue switching to hashcash-SHA3 is it will
invalidate all existing ASIC mining hardware, and is a security risk.
There is
no indication that SHA1 or SHA256, or SHA256^2 are vulnerable to
pre-image hacker attack.
The motivation is missing absent new cryptanalytic
developments.
If SHA256^2 became easier due to
cryptanalytic attack, as miners start to using whatever the new
algorithmic was, regardless, as difficulty
would just adapt to it.
One side-effect will be to introduce more memory or computation trade-offs could
make ASICs unprofitable and currently is.
Computation advantages willo replace the hash with SHA3. Withoutl speculation as pre-image affecting cryptanalytic
attacks are found on SHA256 is catalyst for change.
Hashcash function
Hashcash algorithms relatively simple to understand.
These idea
builds on security property of cryptographic hashes, designed to make difficult to invert, regards, any pre-image resistant
property attack.
Version 0 of hashcash protocol (1997) used a partial 2nd
pre-image, however the later version 1 (2002) uses partial pre-images of
a fairly chosen string, rather than digits of pi or something
arbitrary, 0^k (ie all 0 string) is used for convenience, so the work is
to find x such that H(x)=0.
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 16-bytes of
space in the coinbase. For privacy bitcoin expect the miner to use a
different reward address on each successful block.
More Precise Work
Hashcash as originally proposed has work 2^k where k is an integer,
this means difficulty can only be scaled in powers of 2, this is
slightly simpler as you can see and fully measure the difficulty just by
counting 0s in hex/binary and was adequate for prior uses. (A lot of
hashcash design choices are motivated by simplicity).
Work, difficulty & cryptographic security
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.
It is easier to deal with high difficulties in log2 scale
(a petahash/second is a 16 decimal digit number of hashes per second),
and makes them comparable to other cryptographic security statements.
The EFF "deepcrack" DES cracker
project built a hardware brute force machine capable of breaking a DES
key in 56 hours to make a political point that 56-bit DES was too weak
in 1998 at a cost of $250,000 design time.
By
comparison bitcoin network does 62-bits (including +1 for double hash)
every 10-minutes.
Miner privacy
In principle a miner should therefore for privacy use a different
reward-address for each block.
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, (penetrations advisory), which is a bitcoin mining privacy bug, and a great loop-hole already fixed.
In
fact with bitcoin the counter also should be obscured revealing your effort level, and with increased mining power
that will 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, as no one can tell if it is a powerful and unlucky
miner who worked hard, or a weak miner who was very lucky or hacked.
The introduction of mining pools, and the miner
uses the same reward address for all users, which is what the current
mining protocols does which is a risk that users may redo work.
Avoiding miners redoing work, the miners hand out defined work for the users to
do.
However this creates an unnecessary communication round trip and in
early protocol versions and which means the miners are not
validating their own blocks, and this delegates validation authority,
though not work, to the pool operator, reducing the security of the
bitcoin network.
Recent mining protocol version allows miners
to add their own block definition. This unnecessarily incur round
trips for handing out work allocation.
Scrypt proof-of-work
A misunderstanding about the Scrypt proof-of-work is a scrypt not intended as a proof-of-work function.
Scrypt proof-of-work scrypt is a stretched
key-derivation function.
Scrypt proof-of-work 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.
It is salted
(to prevent pre-computation/rainbow table attacks), and the hash is
iterated many times to slow down passphrase grinding.
Scrypt is similar
in purpose to the defacto standard passphrase key-derivation function
PBKDF2 and which uses HMAC-SHA1 internally.
The differentiator is why
people choose Scrypt rather than PBDF2 is that Scrypt's inner hash
uses more memory so the GPU.
This does not use the key-stretching feature of Scrypt so mining
is not actually using Scrypt directly.
The inner Scrypt hash
(accessed by setting the iteration parameter to one iteration).
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.
Scrypt's key-stretching can not be used for mining
this simultaneously makes more expensive to verify by the same
factor.
Hashcash variant will be denoted
hashcash-Scrypt(iter=1,mem=128KB) or shortened to hashcash-Scrypt(1).
Other major scrypt parameter denotes amount of memory to 128kB. Decentralization: hash-cash-Scrypt vs hashcash-SHA256
This 128kB Scrypt memory footprint is less vulnerable
to centralization of mining power arising from limited access to or
ownership of ASIC equipment by users resolves a profit based industry working against miners.
The hashcash-SHA256^2 is very simple. This
simplicity ensures that many people will do it and ASICs should become
less available that only serves mining farms and nto the common people.
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 128kB.
This makes validating scrypt blockchains more
CPU and memory intensive for all full nodes.
May The Crypto-Forces Be With You Always, and Be Careful/Safe!
No comments:
Post a Comment