Jump to content

The Scrypt Algorithm: A Primer


sdf
 Share

Recommended Posts

10/15/2013: This thread is intended to be an introduction for anyone looking to learn more about the scrypt algorithm, which is the current "mining algorithm" in use for MinCoin.

 

I will be adding to/coherently organizing this when I have more time, but for now it is good to start the discussion.

 

 

 

The Scrypt Algorithm: A Primer

(http://www.tarsnap.com/scrypt/scrypt.pdf) (main site)

(http://www.tarsnap.com/scrypt/scrypt.pdf) (white paper)

 

Scrypt was created by Colin Percival in May 2009 in an attempt to make a much more secure encryption mechanism than PBKDF2 and bcrypt. "Secure" is used here in the sense of being extremely expensive in both time and hardware to decrypt without the cryptographic key used to gain access to the information that has been encrypted.

 

 

Q: What does this mean?

It means that compared to other encryption mechanisms (say SHA256, Bitcoin's), it is many thousands of times more expensive to "attack" a person's encrypted data by trying to guess their password by trying millions of guesses. This is called brute forcing.

 

Q: But why?

The way I've read it so far, scrypt is "sequentially memory-hard" (it stores a lot of data in RAM during hashing). Specialized RAM is super expensive because engineers want to be paid a lot of money for trying to figure out how to make it store more data quickly. In fact, Percival estimates that it would take $19 billion USD in technology and electricity and one year of time to use all possible guesses on a scrypt-encrypted, 8 character password string. That's expensive compared to a password encrypted in bcrypt or PBKDF2 (millions and thousands respectively).

 

Q: Why is scrypt so hard to attack?

This question is above my head currently. You should read the white paper published freely by Percival, and you should also read D.J. Bernstein's work on salsa20, the scrambling function in scrypt. (http://cr.yp.to/salsa20.html)

 

Q: What does this have to do with MinCoin?

Roughly every minute, a block is successfully mined and reported to the MinCoin network. Transactions reported to the network are stored in blocks. To prevent people from spamming fake transactions to the network, transactions are verified with cryptographic keys, which are hard to fraudulently make unless you are the true owner. This is the cryptography part of cryptocurrencies that makes them so useful and valuable- encrypted bits of data are valuable because they are so secure and unreproducible that they simulate owning a physical object of value (USD, gold, cake, whatever).

 

I will eventually make both a simpler and more technical discussion of the algorithm here.

 

Please reply/pm/email me with any questions you have about this material!

Link to comment
Share on other sites

  • 3 weeks later...

I've read a bit on scrypt, but this paper is extremely informative, even if some of us goes over my head.  Still though, just like after reading Brian Greene's "The Elegant Universe", I have a much better understanding of it than I did before.  And, as Greene's book inspired me to learn more about theoretical physics, so too did this paper inspire me to learn more about, not just scrypt, but cryptography in general, something I've been meaning to do for a while but just haven't gotten around to.

 

Thanks for the post bro.  It's insane how powerful scrypt is relative to other encryption algorithms.  Let's just hope P!=NP lol (normally I would feel awkward making a math joke, but I feel very comfortable doing one here...plus, if it's proven that P does equal NP, well...that's the day I'm selling every coin I own and changing every password I have on every website and then going totally offline until I figure out what to do lol...)

 

PS.  Your top two links are both to the PDF.  The one that says main site is the same link as the white paper - the PDF.  I think you were probably trying to go for http://www.tarsnap.com/scrypt.html

Link to comment
Share on other sites

I've read a bit on scrypt, but this paper is extremely informative, even if some of us goes over my head.  Still though, just like after reading Brian Greene's "The Elegant Universe", I have a much better understanding of it than I did before.  And, as Greene's book inspired me to learn more about theoretical physics, so too did this paper inspire me to learn more about, not just scrypt, but cryptography in general, something I've been meaning to do for a while but just haven't gotten around to.

 

Thanks for the post bro.  It's insane how powerful scrypt is relative to other encryption algorithms.  Let's just hope P!=NP lol (normally I would feel awkward making a math joke, but I feel very comfortable doing one here...plus, if it's proven that P does equal NP, well...that's the day I'm selling every coin I own and changing every password I have on every website and then going totally offline until I figure out what to do lol...)

 

PS.  Your top two links are both to the PDF.  The one that says main site is the same link as the white paper - the PDF.  I think you were probably trying to go for http://www.tarsnap.com/scrypt.html

 

Thanks for catching the goof! I'll fix it right now :)

Link to comment
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use.