Alexander Chepurnoy

The Web of Mind

Inside a Proof-of-Stake Cryptocurrency Part 2: Forging Algorithm

| Comments

Introduction

Welcome to the second part of “Inside a Proof-of-Stake Cryptocurrency” series. First chapter defined basic structures specific to proof-of-stake(but not only) p2p cryptocurrencies. We’re going deeper now into details of a forging algo. Provided information is more specific to Nxt and Nxt-like 100% PoS currencies. It will be more code in this chapter so in the first place let’s have a closer look at some of its properties.

Functions & Types

(This section could be skipped while reading for the first time)

Everything is a function in Haskell. E.g. even txTimestamp “field” of Transaction record is a function in fact. So having value tx of Transaction type, you can get it’s timestamp by calling the function as txTimestamp tx.

Every function definition(except of implicitly defined functions e.g. record fields) starts with signature describing types of arguments and result. E.g. validate :: Transaction -> Bool signature means “function validate accepts an argument of Transaction type and returns boolean value(i.e. true or false). In the same manner calcGenerationSignature :: Block -> Account -> ByteString literally means “function calcGenerationSignature is producing ByteString value (i.e. array of bytes) from instances of Block and Account types”.

A function in Haskell is pure means the output is determined by inputs only. In case of purity violation output should be wrapped into a monad to make function pure again. Hopefully, no knowledge of monads is needed for this chapter.

Why does that matter in the context of the article?

  • Even from signatures provided in the article it’s obvious the algorithm is deterministic
  • Before reading function body try to understand its signature i.e. entities going in and out
  • All the code provided below is about field getters and pretty simple self-explanatory functions mostly. I hope the code is understandable even without Haskell knowledge.

A Chance to Be Richer

The goal of forging algorithm is to choose accounts(the only one in best case) having right to generate a block. Obviously, an algorithm should be:

  • verifiable
  • deterministic (or it will be not verifiable in cryptocurrency environment)

Target and Hit

Forging algorithm reminds distributed implementation of rock-paper-scissors game. Every account willing and having ability to forge generates pseudo-random value being called hit every second. If it’s less than stake-dependent targetvalue, a node the account is running against is going to generate a block. Other parties are preventing cheat by checking both values against incoming block, as hit and target are both deterministic.

Hit

Our first goal is to produce deterministic account-dependent hit value with fair distribution. Do you remember generationSignature :: ByteString field in Block structure? There are two purposes to have it:

  1. To link a block with a previous one.
  2. It’s also being using to generate hit

The formula for generationSignature is pretty simple: it’s the hash from generationSignature of previous block attached with generator’s public key. Following code calculates it using previous block and candidate account:

calcGenerationSignature :: Block -> Account -> ByteString
calcGenerationSignature prevBlock acct = bytestringDigest(sha256(append gsPrev pk))
    where pk = publicKey acct
          gsPrev = generationSignature prevBlock

Then hit is just a number constructed from first 8 bytes of generation signature:

calculateHit :: Block -> Account -> Integer
calculateHit prevBlock account =  fromIntegral $ runGet getWord64le first8
    where first8 = take 8 (calcGenerationSignature prevBlock account)

For genesis block generationSignature is set to some predefined value e.g. filled with zeros.

Target & Hit Verifying

To generate target value for our rock-paper-scissors game we use last block again. More preciously, we multiply its baseTarget field value by generator stake(i.e. effective balance) and elapsed time since last block generation timestamp(in seconds). Then calculated target is being used in verifyHit function having two use cases:

  • Honest forging account decides whether it has a right to forge a block by calling the function. Checking is to be done each second(and each second target increases along with a chance to generate a block by satisfying hit < target condition).
  • Other parties ensure incoming block is forged by a proper account have a right to do it

    verifyHit :: Integer -> Block -> Timestamp -> Integer -> Bool verifyHit hit prevBlock timestamp effBalance = (hit < target) && (eta > 0)

      where eta = timestamp - blockTimestamp prevBlock
            target = effBalance*(baseTarget prevBlock)*eta
    

Again, if a result of function call is true, a generator is going to form a block and push it to the network. Other nodes can check whether block is generated properly by calling the same function.

BaseTarget & Block Constructing Function

Now it’s time to define baseTarget :: Integer field of a block used as an initial value for a forger to generate its own target in previous section. As well as generationSignature, baseTarget is also depends on a previous block’s field value with some predefined constant for genesis block. In case of Nxt the base target value for the genesis block is:

initialBaseTarget :: Integer
initialBaseTarget = 153722867

Why 153722867? Well, chapter 3 of this series will give precise formula describing that. The baseTarget of a block is baseTarget of a previous block multiplied by elapsed time since previous block generation timestamp, in minutes. It’s also bounded to be not less than half of a previous block field value nor more than twice as high as it. Also it couldn’t be less than 1 and more than maxBaseTarget which is:

maxBaseTarget :: Integer
maxBaseTarget = initialBaseTarget * systemBalance

Having rules to calculate generationSignature and baseTarget we can define the function to form a block based on previous block, generator account, block generation timestamp and transactions to be included:

formBlock :: Block -> Account -> Timestamp -> [Transaction] -> Block
formBlock prevBlock gen timestamp txs =
    Block{transactions = txs, blockTimestamp = timestamp, baseTarget = bt, generator = gen, generationSignature = gs}
    where prevTarget = baseTarget prevBlock
          maxTarget = min (2*prevTarget)  maxBaseTarget
          minTarget = max (prevTarget `div` 2)  1
          candidate = prevTarget*(timestamp - (blockTimestamp prevBlock)) `div` 60
          bt = min (max minTarget candidate) maxTarget
          gs = calcGenerationSignature prevBlock gen

Difficulty

Within blocktree canonical blockchain is the path having max value e.g. height. We will use sum of baseTarget to select canonical blockchain from possible options and call this function cumulativeDifficulty:

cumulativeDifficulty :: BlockChain -> Integer
cumulativeDifficulty BlockChain {blocks=bs} = sum(map baseTarget bs)

Transparent Forging

There’s a lot of buzz about transparent forging these days. The transparent forging concept is about a forger of a next block is to be known for all online network members in prior. It’s possible because the algorithm is deterministic but in practice there are some issues to be resolved:

  • A forger could miss its turn(there are some workarounds to make block generation quicker for a next forger though)
  • List of forging accounts for the whole network is needed. And it’s not possible to have it consistent constantly.
  • Even in case of pretty weak consistency it could be a tricky task to implement gossiping about forgers in privacy-friendly way.

Conclusion & Further Work

This chapter of the series defined functional building blocks and whole forging algorithm as well. Next chapter will be kind of academic paper about statistical modelling of Nxt forging algo with some interesting results. After that we will go deeper into forging simulation with Haskell.

Inside a Proof-of-Stake Cryptocurrency Part 1: Basic Structures

| Comments

Introduction

Pure and hybrid Proof-of-Stake cryptocurrencies are on the rise today. The most known pure PoS example, Nxt, has tens of forks at the moment (some of them are quite promising), the Ethereum team thinks about hybrid (PoS/PoW) mining principle, and so on. At the same time, there are many concerns about the concept, not formalized well enough, unfortunately, for example for example even the famous “nothing-at-stake” attack has not a good description. The sad thing is both good and bad things about proof-of-stake have no good formal description and model behind. The challenge of this series is to make some progress in this area.

Prerequisites

I assume you know some common things about Bitcoin and proof-of-work mining. It’s better to have basic coding skills to understand code snippets. Haskell programming language is being using for them (though Haskell knowledge isn’t required). We will start with model as simple as possible. I prefer to make a simplest thing harder than to work with complicated case from day one.

Time

Wikipedia defines time as “a measure in which events can be ordered from the past through the present into the future, and also the measure of durations of events and the intervals between them”. For distributed environments working with time means headache because of clock synchronization, events ordering etc. Fortunately blockchain-based networks make some problems easier. Due to this our model could be even easier: we assume all clocks in the system are synchronized! Fortunately, we will lose not too much in modelling quality because of that. Later we can introduce local clocks.

Time in our approach is just a number of seconds from genesis block, so our first entity definition is pretty simple:

type Timestamp = Integer

Transaction Model

Unlike the Bitcoin-like model where transaction has inputs connected with other transaction’s outputs as well as own outputs(possibly unspent), we will work with simpler approach. First, we introduce the Account entity:

data Account =
    Account {
        balance :: Integer,
        publicKey :: ByteString,
        isForging :: Bool
    }

It has an explicitly defined balance. Many simplifications made in comparison with real cryptocurrencies, in particular:

  • We use no addresses. In real cryptocurrencies the address is hash(publicKey), while we use publicKey itself as an address.

  • We even don’t use the private key! The private key is needed for transaction signing, and that is out of scope of our study.

Having Timestamp and Account entities described, we can define transaction as:

data Transaction =
    Transaction {
        sender :: Account,
        recipient :: Account,
        amount :: Integer,
        fee :: Integer,
        txTimestamp :: Timestamp
    }

Again, it’s far away from practical use. There’s no id, no even signature, so anyone could print money easily.

Forging

In proof-of-stake currencies there are no third-party “workers”, instead, stake holders are block generators. Instead of term mining we’ll use forging. The meaning is the same though: forging is a process of blocks generation. Remember the Account definition? The isForging field there shows whether account is participating in forging or not.

Blockchain

In every cryptocurrency I know transactions are grouped into blocks. With the following block definition Proof-of-Stake nature of our model starts to appear:

data Block =
    Block {
        transactions :: [Transaction],
        generator :: Account,
        blockTimestamp :: Timestamp
        baseTarget :: Integer,
        generationSignature :: ByteString
    }

transactions and blockTimestamp fields are self-describing. generator is account generated this block. baseTarget and generationSignature fields are related to forging algorithm and will be described in a next chapter of the tutorial.

The Blockchain is just a sequence of blocks:

data BlockChain = BlockChain { blocks :: [Block] }

Effective Balance

In proof-of-stake the probability of block generation depends on the account’s balance. In Nxt-like currencies, it is a function of the effective balance . E.g. in Nxt itself the effective balance is the balance 1440 blocks ago from last one minus all spendings for that period plus leasing forging balance given by other accounts etc. We can simplify again:

effectiveBalance :: Account -> Integer
effectiveBalance acc = balance acc

So the effective balance in our model is just the current balance.

The Network

Nothing has been said about whole p2p network yet. The first entity to be defined here is a node in the network:

data Node =
    Node {
        nodeChain :: BlockChain,
        unconfirmedTxs :: [Transaction],
        account :: Account
    }

Again, we’re dealing with simplifications:

  • Only one blockchain per node(this is true though e.g.for current Nxt Reference Software implementation)

  • Only one account per node

Having the Connection entity defined as just a tuple of Nodes:

type Connection = (Node, Node)

we can define biggest type in our model, System:

data System =
    System {
        nodes :: [Node],
        connections :: [Connection],
        accounts :: [Account]
    }

In proof-of-stake currencies all the money is usually being “printed” in a genesis block. The Nxt system has ~ 1 Billion balance from the genesis block:

systemBalance :: Integer
systemBalance = 1000000000

Forks

Forks are possible as well as with proof-of-work mining. How could we define fork? Well, a blockchain is stored in a node, and System has a list of nodes([Node]), so tree of blocks could be exctracted from System by function with following signature(implementation is missed for now).

 blockTree :: System -> BlockTree

Where Blocktree is just the alias for a list of Blockchain: type BlockTree = [BlockChain]

Why is a list called a tree? All blockchains have some common prefix(genesis block at least), so in fact we’re dealing with a tree structure. However, not enforcing tree structure by type system is not the best design definitely, but for simplicity’s sake we leave it as is for now.

Properties Analysis

How can Haskell code helps us with formal model analysis? Let’s start with a property given in Gavin Wood’s Ethereum YellowPaper :

The canonical blockchain is a path from root to leaf through the entire block tree. In order to have consensus over which path it is, conceptually we identify the path that has had the most computation done upon it, or, the heaviest path.

Canonical blockchain could be defined with a function having signature:

canonicalBlockchain :: System -> Maybe BlockChain

(again, no implementation for now). Maybe BlockChain could be Just blockchain(so defined), or Nothing(means undefined). So if function result is defined a system has some canonical blockchain. We can then enforce more strict conditions, e.g canonical blockchain for some time ago should be the prefix of current canonical blockchain.

There are two ways to make conclusions about the property:

  1. We can make executable forging algo model then gather statistics about function result.

  2. We can translate our Haskell model some Haskell-like language with dependent types(e.g. Coq) then, thanks to Curry–Howard correspondence, theorems could be formulated and proven about model properties.

Both ways will be shown in action in next chapters!

Conclusion & Further Work

Data structures needed for model (Timestamp, Account, Transaction, Block, BlockChain, Node, Connection, System, BlockTree) are described along with simplest functions over them. In next chapter forging algo functions will be defined, then executable imitation and formal analysis will be provided.

(Next part: Forging Algorithm)

Inside a Cryptocurrency / Inside the Nxt - Announce

| Comments

Have been working as Nxt developer for few months(and investigating cryptocurrencies before) I see a lack of understanding of proof-of-stake currencies and Nxt as well amongst many developers in the industry. To change this to a better I’m starting two blog series:

Inside a Cryptocurrency

You could read the series title as “Inside a PoS Cryptocurrency”. In Proof-of-stake(PoS further) currencies right to generate a block out of unconfirmed transactions is given to stakeholders, not miners, and chance of generation is proportional to an actual balance. PoS has many pros: probably faster block generation, less energy footprint, 51% stake is usually more expensive than 51% mining power so PoS currency could be more secure etc. On other side, there are some issues, the most known is so-called “Nothing-at-Stake”. Unlike previous attempts, I will describe Nothing-at-Stake attack in most formal way to the moment.

Articles in this series will be about very simple account-based proof-of-stake cryptocurrency model with code examples in Haskell. The model is exctracted from Nxt, but true for other 100%-PoS currencies I know.

Inside Nxt

Second series will contain shorter articles about NRS(Nxt Reference Software), it’s interaction with outer world, my https://github.com/kushti/NxtScala. Also I would like to give out some information for those who willing to contribute and some critics for sure!

Frequency & Contribution

I’ll post one or two articles per week probably in “Inside a Cryptocurrency”. I would be happy if someone could helps me with schemes or very simple pictures drawing. I don’t sure about “Inside Nxt” updates schedule at the moment.

Shareholders Meeting via Blockchain in 20 Lines of Code

| Comments

Seems we are witnesses of a new revolution in the corporate world caused by blockchain technologies. We’re moving quickly to virtual corporations, distributed autonomous corporations, smart contracts, new models of funding and so on. This article is about an exciting possibility of having distributed shareholders meetings where results are public and counted in trustless way.

Since late April I’m working on NXT cryptocurrency as a core developer. NXT is a 100% proof-of-stake cryptocurrency aiming “to transform a cryptocurrency into a decentralised financial platform that supports a thriving and fast-growing digital economy” (unlike hybrid Ripple’s approach which isn’t fully decentralized). Since May, 12th NXT has Asset Exchange (NXT AE) as a core feature. Anyone can issue assets on this totally decentralized and uncontrolled exchange and trade them. You can watch the assets being issued in web via several sites, e.g. NextBlocks, NXTReporting or SecureAE (you can even buy stocks with Bitcoins there). Spending some time on assets investigation you can find many possible applications of NXT AE, and many more are undiscovered yet.

In particular, you can fund your business via asset issuance getting money from anyone (not just angels/VCs) like KickStarter, but from day one and with no any fees. Probably you’ll get money from a community having a need for you product. It would be awesome to get feedback and community-powered decisions also, right?

With voting system I have finished recently that will be possible. The voting system will be introduced in NRS (NXT Reference Software) 1.3.x (x>0) or 1.4.0. The next stable release version is 1.2.1, so voting API & GUI will be accessible sometime in September, probably (earlier in testnet). But I can share some API details right now as they will be untouched probably.

Consider the example of an indy developer making a game. He got some funds via asset exchange. Then he made promising v.1 of the game. A concept is still raw as well as an implementation but fans are excited! So he wants to ask the community whether he should polish v.1 or make v.2 immediately built on top of better concept, or… So he’s starting the poll:

    val question = "Further directions in game development. "
    val description = "I got some great reviews. I have 10000 NXTs left. How should I spend them?"

    val finishBlockHeight = Nxt.getBlockchain.getHeight + 1440 // ~= 1 day
    val options = Array("Improve graphics and release it ASAP", "Start to work on v.2 to get funds for it's development", "Better ask experts, e.g. attend GameDev Conference", "Game is abortive. Stop working on it.")

    val optionModel = Poll.OPTION_MODEL_CHOICE
    val votingModel = Poll.VOTING_MODEL_ASSET

    val pb = new PollBuilder(question, desc, options, finishBlockHeight, optionModel, votingModel)
    val assetId: Long =  // assetId here
    pb.assetId(ai)
    pb.optionsNumRange(1, 1) // only 1 option to choose

    issueTxToGodId(new Attachment.MessagingPollCreation(pb), phrase1)

A vote could be sent with following code:

    val poll = Poll.getByName(question).head
    val vote = Array(0.toByte, 1.toByte, 0.toByte, 0.toByte)
    val attachment = new Attachment.MessagingVoteCasting(poll.getId, vote)
    issueTxToGodId(attachment, phrase2) 

1440 blocks after starting the poll we can get and print to console poll results(where 1 asset=1 vote):

    val pr = PollResults.get(poll.getId).get
    pr match {
        case cpr: nxt.PollResults#Choice =
            val m = cpr.getResults.toMap
            println(m)      
    }

So we have fair, cheap, public & distributed shareholders voting! Just imagine how it could change the world of business.

Faster Cosine Similarity Between Two Dicuments With Scala&Lucene

| Comments

For calculating cosine similarity between two documents I used modified(and rewritten to Scala) example by Sujit Pal/Mark Butler(http://sujitpal.blogspot.ch/2011/10/computing-document-similarity-using.html, http://stackoverflow.com/questions/1844194/get-cosine-similarity-between-two-documents-in-lucene?rq=1). It’s working, but under big workload(hundreds of comparisons in second in my case) it consumes a lot of CPU / memory and even worse, some of threads getting stuck for few minutes(!) somewhere inside the Lucene code. So I had to rewrite that code to avoid RAMDirectory / IndexReader usage(I need no to store documents to Lucene storage at all). Here are two functions I have written and now want to share:

  1. extractTerms function which extracts terms from document(presented as String) with stemming & stopwords removing:

     def extractTerms(content: String): Map[String, Int] = {    
         val analyzer = new StopAnalyzer(Version.LUCENE_46)
         val ts = new EnglishMinimalStemFilter(analyzer.tokenStream("c", content))
         val charTermAttribute = ts.addAttribute(classOf[CharTermAttribute])
    
         val m = scala.collection.mutable.Map[String, Int]()
    
         ts.reset()
         while (ts.incrementToken()) {
             val term = charTermAttribute.toString
             val newCount = m.get(term).map(_ + 1).getOrElse(1)
             m += term -> newCount       
         }
    
         m.toMap
     }  
    
  2. similarity function which calculates similarity between two term vectors

     def similarity(t1: Map[String, Int], t2: Map[String, Int]): Double = {
         //word, t1 freq, t2 freq
         val m = scala.collection.mutable.HashMap[String, (Int, Int)]()
    
         val sum1 = t1.foldLeft(0d) {case (sum, (word, freq)) =>
             m += word ->(freq, 0)
             sum + freq
         }
    
         val sum2 = t2.foldLeft(0d) {case (sum, (word, freq)) =>
             m.get(word) match {
                 case Some((freq1, _)) => m += word ->(freq1, freq)
                 case None => m += word ->(0, freq)
             }
             sum + freq
         }
    
         val (p1, p2, p3) = m.foldLeft((0d, 0d, 0d)) {case ((s1, s2, s3), e) =>
             val fs = e._2
             val f1 = fs._1 / sum1
             val f2 = fs._2 / sum2
             (s1 + f1 * f2, s2 + f1 * f1, s3 + f2 * f2)
         }
    
         val cos = p1 / (Math.sqrt(p2) * Math.sqrt(p3))
         cos
     }
    

To calculate cosine similarity between text1 and text2 just call similarity(extractTerms(text1), extractTerms(text2))

In tests my code is 7-10 times faster and has less memory footprint. Enjoy!

Investigating Namecoin Database Pt. 1 : Introduction & Objects Counting

| Comments

Introduction

Probably you get some knowledge about cryptocurrencies from all that massive buzz around. But cryptocurrencies are not only buzz about another merchant accepting Bitcoin, market news, fun story involving dogecoin etc. A lot of tech possibilities we have now behind just money as digital property being transferring from one peer to another.

One of the notable alternative cryptocurrencies is Namecoin, which could be considered as currency and key-value database as well with auto-expiration of records injected in the blockchain. Owner of record has to pay (0.01 NMC for now) to have it in database for period of time of 36,000 blocks(~250 days).

You can insert any name-value record in the database, though there are some formal namespaces, two for now: DNS system for .bit domains(names starting with “d/”) and NameId which is fully decentralized OpenId alternative(names starting with “id/”).

Objects Counting

We are starting to get deeper into the Namecoin database with counting named objects in it.

First, install Namecoin daemon namecoind (very like Bitcoin’s bitcoind installation), for details, visit namecoin.info or namecoin.org . Wait while blockchain will be downloaded.

Then pull out all active records into out.txt file with

namecoind name_scan "" 1000000 > out.txt

To count all objects in database dump you have now use

cat out.txt | grep '"name"' | wc -l

To count .bit domains being registered

cat out.txt | grep '"name" : "d/' | wc -l

To count NameId entries

cat out.txt | grep '"name" : "id/' | wc -l

As of today, Feb 26th, 2014, Namecoin database contains 156276 entries in total, including 140237 .bit domains and 2919 NameIds.

Flattening Scala Futures(Future[Future[T]] –> Future[T])

| Comments

Well, as scala.concurrent.Future class has no .flatten method, you could be wondered how to convert Future of Future e.g. Future[Future[T]] to just Future[T]. That’s can be easy done with combination of flatMap and identity functions:

//having fft:Future[Future[T]]
val ft:Future[Int] = fft.flatMap(x=> x) 

Learn Play! Framework by Example

| Comments

Play! Framework is probably the most popular Web framework for Scala Language(and one of the most popular Web frameworks for Java too). It’s stateless, it’s elegant, it’s a good friend of functional reactive programming.

To learn framework, the site contains very good tutorial, also there are some samples within ‘samples’ folder. And I’m happy to present another option to dive into the framework.

The sample application was developed with aim to test Mechanize Framework, but GistLabs published it as standalone application.

Application contains following examples:

  • Controllers with different response codes: 302 redirect, 302 infinite redirect, 466 code, internal server error with custom message
  • Cookies examples: printing cookies got in request, setting cookie
  • XML examples: simple XML document output and echoing value passed in an input XML document passed with PUT request
  • JSON example: echoing value passed in an input JSON document passed with PUT request
  • Not-Modified example: on first request Etag/Cache-Control headers are sent in response, then Not-Modified result sent
  • Forms: GET/POST forms, POST form with validation
  • Files: single file upload, multiple files upload, POST/PUT/GET service example(create a file with random filename on POST, create a file with specified filename on PUT, then get file with GET request)
  • Auth: login to see secret token, or try to access secret area directly(with redirect to index page)

Pull sources from GitHub and learn Play! by example!

P.S. Next part of the story will be about different Play! sample applications around the Web

Console Applications With Play Framework 2.x

| Comments

What if you want to launch a part of your application within IDE to see log output? What if you want to have console launcher for actor system which is the part of your Play 2.x app? If your code uses Play classes(e.g. play.api.Logger) or it needs , you can’t write ordinary console app because it will throw “There is no started application” error during run.

How to get Play context within console application? Just extend your launcher class from play.core.StaticApplication class, pass path to application root to StaticApplication instance constructor. Simple example:

object ConsoleLauncher extends StaticApplication(new File(".")) {
    def main(args: Array[String]) {
        DataExtractionActorSystem.start()
    }
}

How to Remove Task Dependency in Gradle

| Comments

What if you want to remove dependency for Gradle task? For example, remove dependency from compileGroovy for compileJava(to add dependency in opposite dirrection and avoid cyclic dependency problem). Should be simple, but I didn’t find ready solution using search engines, though two minutes experiment provided me working code:

compileGroovy.taskDependencies.values -= "compileJava"

Ready solution to compile first Groovy classes then Java:

compileGroovy.taskDependencies.values -= "compileJava"
compileJava.dependsOn(compileGroovy)