hash function in cryptography
In the last discussion, we have looked into the consensus mechanism in consensus the general distributed consensus architecture so in this particular talk we look into how The consensus in Bitcoin – I achieved in a bitcoin-based permissionless blockchain environment.
CONSENSUS IN BITCOIN
So here is the consensus algorithm in bitcoin so the objective of the consensus algorithm in bitcoin is to be a new block to the existing blockchain.
Now there can be multiple miners in the bitcoin network and individual miner s can propose their new blocks based on the transaction that they have hard off so one miner can hard the transaction 15,16,18 and 19 whereas another miner can hard the transaction 15,16 and 17 so it interesting to note as I have also mentioned in the last lecture that it is not necessary that if the miner will propose a new block or better to say every minor will propose the same block.
so it is all like that transaction the miner has hard off till now better or to say that the time that the last block has been added in the blockchain the can include all those transactions in the new block provided that the total size of the block does not exist certain ratio so in this particular example we have 3 miners so these individual 3 miners have the 3 individual blocks
which have been proposed by them and the objective here is to this decision that which particular block needs to be added to the existing blockchain so the consensus objective is which block do we add next out of the 3 blocks proposed by the miner.
The miners do not know each other
now the challenge here is that the minor does not know each other because it is an open network it is a permissionless network so anyone can participate in the network as a miner and they can collect the transaction coming from the client and they can propose a new block so under this certain scenario how value insures that the miners will come to a consensus
Broadcast the information and then apply a choice function- traditional distributed consensus algorithms
so let us look into one possible solution which is closer to the traditional distributed consensus algorithm where every miner whenever there propose in some new blocks they will broadcast information in the network.
After broadcasting the information to the network they will wait for a certain amount of time and see the whether any other blocks from other miners and based on that they apply a choice function to select one of the blocks but there is a problem in this particular mechanism so what is the problem.
The problem here is that whenever been are saying that a miner will wait for a certain duration that is technically infeasible in this particular environment why because first of all the miners do not know each other because the miners do not know they do not know that how many other miners are there in the network who are going to propose new block and 2nd one is that the internet is inherently asynchronous.
Asynchronous in the sense like whenever a miner will propose a block there can be an arbitrary delay in transmitting those new blocks.
May not be feasible:
You do not have a global clock! How much time will you wait to hear the transactions?
Remember the impossibility result
so in this Particular environment having a consensus-based on a broadcasting algorithm by applying a traditional distributed mechanism may not be feasible so if you remember the Impossibility theorem where we have mention that coming to a consensus is impossible in a purely asynchronous distributed network in the presence of even a single failure
so in this particular architecture even if they are some miner which a malicious miner even in the presence of the single malicious miner another miner may not be able to collect all the blocks which are coming from the legitimate miner having a consensus by applying this kind of traditional distributed algorithm based on broadcasting are based come Message passing is least see that what we can do
Observation – 1:
- Any valid block (a block with all valid transactions) can be accepted, even if it is proposed by only one miner
We have 2 different observations here. 1st observation is interesting that in case of a blockchain environment (a block with all valid transactions) Can be accepted any of propose block even if it is proposed by only one miner so it is not necessary that a block need to be proposed to multiple miners together even if it is coming from a single miner it a valid block we can accept the block to the existing blockchain so that was 1st observation.
Observation – 2:
- The protocol can work in rounds
- Broadcast the accepted block to the peers
- Collect the next set of transaction
2nd observation is that the entire protocol can run in rounds means once a valid block has been accepted or say the system has reach to the consensus from that point rounds starts the miner starts getting the transaction and then they can find out that which are the transaction which are not already committed on the blockchain and based on that they can propose new block so if you look in to this particular example
in this example the last block in the blockchain it has transaction 11,12,13 and 14 so all the miners once this particular block has been committed in the blockchain the miners they can find out well transaction 11,12,13 and 14 has already been committed so do not need to include those transactions again in a new block so they can propose a new block by excluding
the transaction which has already committed in the blockchain so that way once a commitment has been done that means the block is added to a particular blockchain the miners can try to figure out which are the next transaction that needs to be added to the blockchain they can propose a new block-based on that.
So based on these 2 observations we can design a solution in this way where every miner independently tries to solve it by the challenge. So the challenge is provided by the network. so they will Independently try to solve the challenge and the block is accepted for the miner who can prove fast the challenge has been solved.
So this particular keyword prove first is important here because this keyword says that every individual miner they are trying to solve a solution impost by a network and the miner who is able to solve the problem fast they act the solution of the problem to the existing block and at an act that block to the blockchain
So this particular algorithm is known as proof of work the term proof comes from the fact that miner he has been able to the miner Who is proposing to the solution he was able to prove that he has found out the solution of the problem so that is the solution architecture that when the miner finds out that they are the solution he proposed to block to the other miner saying that I have already received the solution.
so here already received a solution and another miner start of finding out the solution for the challenge and stars finding new blocks from the transaction which are coming from the clients. Now 1 interesting point to note is that this particular communication can work asynchronously so wherever you are advertising the solution to the other miners in the network the miners can work for mining the previous block during that time.
say I am a miner I am trying to find out the solution for a giving challenge and whenever I will find out that well a new block has been added in the blockchain during that time if I find out that well that particular block has a start in a set of transaction which is also part of the block so there is an overlapping of the transaction between in the block that I am trying to proof and the newly added block in the blockchain if that is the scenario then I just stop the mining at that point accept the most updated blockchain and then start finding out blocks with a new transaction which are coming from the client
So once the solution has been obtaining so the block has been added to the existing blockchain so block transaction 15,16,18 and 19 has been added to the blockchain
Now the interesting fact that whenever this particular information updated blockchain is propagate to all the miners in the network so all the miners can see so the other miner they were at that time they were also trying to mine the block was this transaction 18,19 we’re there so if u look into the earlier slide so this miner was also trying to mine a block
were transaction 15,16,17 was there the second minor was trying to mine a block were transaction 15,16,17,18 was there now this new block has been added to the blockchain and they can find out that well in the newly added block transaction these 15,16,18 and 19 there but transaction 17 has not been included in the block.
Now in the next round, every miner can include transaction 17 and at the same time along with transaction 17 the other transactions that they have heard in that time duration so those transactions can be added and they can start mining those specific blocks so the same process repeats in rounds and they can try to find out than what can be the solution for that particular challenge.
PROOF OF WORK (POW)
- An economic measure to deter service abuses by requiring some work from the service requester(usually processing time by a computer)
- The idea came from Dwork and Naor (1992), to combat junk emails
- You have to do some work to send valid emails
- The attacker would be discouraged to send junk emails
So what should be the challenge so to generate the challenge bitcoin relies on a mechanism called proof of work So what is the proof of work.
the proof of work is an economic measure to determine service abuses requiring some work from the service requester ( usually processing time by a computer) Say if u are requesting for a service you have to show to the service provider that you have Spent significant interest on the service that you are requesting for
so I will give u an example that how this kind of proof of work-based can help you to prevent junk emails or spam emails that is an interesting idea but the broad idea of this proof of work is that every service requester must spend some time on the service that he or see asking for before actually requesting for the service so that way it shows you form the economic perspective that the service requester has some interest on the service
so if the service is provided to that service requester will genuinely accept that service and it will not use it maliciously.
So that idea is actually an old idea which came from Torque 1992 from an interesting paper Published in a crypto conference to combine the junk emails so in that particular paper the idea they had a share that you have to do some work to send a valid email now the attacker this way they will be discouraged to send junk email because in that case, they have to do the same work of the same Complicity over the junk email that will not prove beneficial for day
PROOF OF WORK (POW) features
- The work must be moderately hard, but feasible for the service requester
- The work must be easy to check for the service provider
- Service requesters will get discouraged to forge the work, but service providers can easily check the validity of the work
So this kind of proof of work-based system should have certain features one important feature is Asymmetry that means work must be moderately hard, but feasible for the service requester.
So you should try to solve moderately hard work feasible work to the service requester side whereas at the service provider side the work must be easy to check or must be easy to validate so that way the service requester they will get discouraged to force the work so
because they have to Spent some significant amount of time to complete that particular work they will be discouraged to submit any kind of spam or junk work to the system but the service provider, on the other hand, they can easily check the validity of the work because of the asymmetry nature that the work is easier to validate for the service providers but it is hard but not infeasible for the service requester
CRYPTOGRAPHIC HASH AS THE POW
- Use the puzzle friendliness property of a cryptographic hash function as the work
- Given X and Y, find out k, such that Y = Hash (X||k)
- It is difficult (but not infeasible) to find such k
- However, once you have a k, you can easily verify the challenge
- Used in Hashcash, a proof of work that can be added with an email as a “good-will” token
So let us look into that how cryptographic hash can work as a good indicator for proof or work so while Discussing about different types or cryptographic hash functions he have looked into the Puzzle friendliness property of cryptographic hash function so the puzzle friendliness property says that give an X and Y you need to find out K such that Y=Hash(X||K)
so if X and Y are known in that case it is very difficult to find out the certain K you have to the best algorithm to find out this kind of K is to apply certain kind of root force mechanism or some kind of random such over the possible value so this particular work it is difficult to find but it is easier to validate so once you have find out such K it is easier to find out or it easier to validate the whether hash value of X || K becomes equal to y or not
Now this concept was used in hash cash so this hash cash work was proposed by adamant in 2002 which was a proof of work mechanism that can be added with an email as a goodwill token.
so it is like that the hash cash can be only generated or the sender of the legitimate email will be interested to generate hash cash whereas the spam email generated they will be discouraging to generate hash cash so the latest look into the details of the hash case mechanism and how it works.
- A textual encoding of a hashcash stamp is included in an email header
- Proof that the sender has expended a modest amount of CPU time calculating the stamp before sending the email
- It is unlikely that the sender is a spammer
- The receiver can verify the hashcash stamp very easily
- Any change in the header requires a change in the hashcash
- Brute force is the only way to find a hashcash
Now, this hash case proof of work is a textual encoding, or u can think of it is hashcash stamp which is included in an email header. So this hashcash is proof that the sender has expended a modest amount of CPU time calculating the stamp before sending the email.
Now if the sender has spent a modest amount of time to generate the hashcash before sending the email.
It is unsightly that the sender is a spammer Because the spammer will be interested to send a repeated email one of the other by some auto-generated script.
so if they have to wait for a certain amount of time for sending every email the spammer not be benefited out of time.
But the other hand the email receiver they can verify the hashcash them very easily by applying certain hash function but any change in the header also require a change in the hashcash because you are generating a hashcash from the header so if you want to modify certain field inside the email header you have to regenerate a hashcash which is for which the good for system only way to find ab new hashcash so that way the attacker will also be discouraged to temper the email header.
- The hashcash in the included in the email header looks like this
- The version number of zero bits in the hashed code: date: resource: optional extension: a string of random character: counter
So here as an example of a hashcash so the hashcash which is included in an email header it looks like that you have a hashcash field after the hashcash field you have certain individual fields. So the first field one it talks about version number so we are using hashcash version one the 20 is a certain number of bits where we can say that it is the number of zero bits. that need to be there in the hashed code.
So this 20 says that you need to generate a hash function where the first 20 bits of the hash function will be 0.
So that is the challenge that is the post to the email sender. now the email sender has to find out the hash value where the first 20 bits are zero. Then the timestamp value that here it was generated on 1 April 2018. So it is that year month date format 180401. than certain resources here I put my email I’d. Then a random number.
a string of random characters. The string of random character is included in the hashcash and what is the importance of the string of random character that will see later on and then a counter value. So this counter value is working like a nonce. so the email sender for them this all the fields like the version number of zero bits, the date time stamp, the resource fields, the string of random characters all these fields are fixed.
The only field the email sender can change is that counter field. So the email sender needs to check different counter value by providing different counter Value that for which counter value it can find out the expected hash value where the objective is to have a 20 number of zero at the prefix.
So on the sender side, the hashcash is constructed in this way so you first construct the header so the constructs the header you have individual fields after putting individual fields in the header then the sender initializes the counter value to a random number.
so once the sender initializes the counter value to a random number then the sender computes in a traditional hashcash we use a 160-bit SHA one algorithm so by applying a 160-bit SHA one algorithm you try to find out the hash value where the first 20 bit of the hash is all zeros.
If u can find out a hash value where the first 20 bit of the hash is all zero then that particular hash is accepted. Otherwise, you try with a different counter you change the counter value and check bit a different counter value and find out that way the result is produce that requires to 20 bit on the beginning or not.
HASHCASH POW – RECIPIENT SIDE
- Recipient checks
- The date – should be within two days
- Email address
- The random string – should not be used repeatedly within a certain duration (prevent replay)
- Compute the 160 bit SHA-1 hash of the entire received string
- If the first 20 bits are not zero then it is invalid
Now the at the recipient side a recipient checks certain parameters the date. The date should be within two days as per the hashcash version one. So if someone is changing the date if some email spammer or some attacker is making a change in the date version he needs to again recompute the hashcash.
The email address it checks that will the email address in the hashcash it exactly match as with the sender email address so that means the sender has generated that particular hashcash value and the random string so this random string should not be used repeatedly within a certain duration so it prevents the replay attack something like this where the attacker has stored the previous hashcash and the attacker has cashed the previous hash cash and by cashing the previous hashcash with every junk email he or she is sending that previous hashcash.
So this random string is utilized to prevent those kinds of replay attacks where every time whenever you are sending a new email you have to change the random string. If you Change the random string you have to generate a new hashcash value and that way you have a spent certain time to generate by the corresponding hashcash. Now once you have checked all the fields next time to validate the hashcash.
Validating the hashcash is easy you straight the entire string find out the160 bit SHA one hash function out of that string and if you can find out that will the first 20 bits are zero all zeros that mean that was you earlier objective that you can find out by looking at the string that the first 20 bit should be zero so if the first 20 bits are all zero then you accept the particular email otherwise you discarded.
- On average, the sender will have to try 2^20 hash values to find a valid header (takes about a few seconds in a general-purpose computer )
- There are 2^160 possible hash values
- 20 zero bits at the beginning – 2^140 possible hash values that satisfy this criterion
- The chance of randomly selecting a header with 20 zero bits at the prefix is 1 in 2^20
- The recipient requires around 2 microseconds to validate
Well, some analysis of hashcash proof of work so because you are utilizing 160-bit SHA one hash function so you can have to 2^160 possible hash Values now what do you want then if you want to 20 at the beginning that means you can have 2^140 possible hash values which satisfy the criteria where the first 20 bits are zeros and remaining 140 bits can be either 0 or 1.
So the chance of randomly selecting a header bit 20 leading zero bits at the prefix that probability is 1 out of the 2^20. So that means if you can try with 2^20 different hash function with a high probability you can get a hash value so that way the expected number of rehash the sender has to do is 2^20.
Which takes a certain amount of time in today computer it takes in the order of few second to compute the hashcash but on the other hand, validating the hashcash at the receiver side is very fast the receiver require around 2 microseconds to validate the hashcash.
READ MORE ARTICLE: R3 CORDA
follow us on facebook