Alexander Chepurnoy

The Web of Mind

Phasing Transactions in Nxt Part 1: Introduction, Phasing-Safety

| Comments

Two-Phased Transactions are similar a bit to Bitcoin’s multisig transactions implementation in Nxt but different in many aspects as well.

Simplest example: Alice starts a Two-Phased transaction. In the first stage a transaction is included in a blockchain but it isn’t processed immediately and has the status of ‘pending’. For it to be processed, Bob has to complete the second phase of the transaction by approving it. This has to be done before the deadline set by Alice has elapsed.

Please note the biggest difference from Bitcoin’s multisig: phased transaction is going to be included into blockchain immediately.

Use cases

  • Bob approving a transaction of Alice
  • Shareholders voting whether to send another 1M Nxt to a marketing service or not
  • Multisig wallet protected from a hacker(think about BTER case etc) (needs Account Control)
  • Trustless escrows
  • Conditional or unconditional transaction happening in some certain moment in future

Features

  • most types of transaction could be 2-phased (but not all, see “Phasing-Safe Transactions” section)!
  • different consensus types: M-of-N account consensus,shareholders voting with assets, currency holders voting with a Monetary System currency units
  • possible vote threshold setting(e.g. only accounts holding 100+ assets could vote)
  • whitelist of voters
  • transaction could be released only prior to finishHeight(or at the height exactly )

Consensus(Voting) models

  • None - synthetic mode, used for unconditional transaction execution at some height in future
  • By account - 1 account is 1 vote
  • By balance - 1 nqt is 1 vote
  • By asset - 1 qnt(asset’s quant, so non-divisible part) is 1 vote
  • By MS currency - 1 unit is 1 vote
  • By transaction - phasing transaction becomes approved if there are transactions in blockchain with hashes set in phasing transaction
  • By hash - another synthetic mode, used for pay-with-secret

Phasing-safe transactions

Not all transaction types are phaseable, so some of them couldn’t be phased at all. Some phasing transactions are phaseable but not phasing-safe, means they doesn’t make sense as phasing transactions(e.g. message could be phased, but you can read it immediately) or there’s a risk a transaction couldn’t be applied at finish height due to some changes in the outer world’s state. Following table shows phaseable & safe transaction types. Please note unsafe phasing transaction could be pretty safe in some practical case, but that’s not guaranteed by the core.


Transaction Type Is Phaseable ? Is Safe ?
Payment Yes Yes
Arbitrary Message Yes No
Alias Assignment Yes No
Alias Sell Yes No
Alias Buy Yes No
Alias Delete Yes No
Poll Creation Yes No
Vote Casting Yes No
Phasing Vote Casting Yes Yes
Hub Announcement Yes Yes
Account Info Yes Yes
Asset Issuance Yes Yes
Asset Transfer Yes Yes
Ask/Bid Order Placement Yes Yes
Order Cancellation Yes Yes
Dividend Payment Yes Yes
DGS Listing / Delisting Yes Yes
DGS Price Change Yes No
DGS Quantity Change Yes No
DGS Purchase Yes No
DGS Delivery Yes No
DGS Feedback Yes No
DGS Refund Yes No
Forging Balance Leasing Yes Yes
Tagged Data Upload No -
Tagged Data Extend No -

Voting System Guide for Developers & Experienced Users

| Comments

This blogpost describes voting system presented in NRS(Nxt Reference Software) 1.5 for application developers & experienced users. For simple use cases, wallet’s UI is self-explanatory and enough.

Features

  • Different voting models supported: voting by account(1 account = 1 vote), balance(1 Nqt = 1 vote), asset balance(1 Qnt = 1 vote), or Monetary System token balance(1 currency unit = 1 vote)

  • Voting has finite predefined duration(finish block height, to say precisely)

  • Poll has minimum and maximum number of options to provide opinion for. E.g. choose from 2 to 5 options out of 8

  • Range is the vote parameter. E.g. give a rate from 0 to 10.

  • By combining number of options & range a lot of specific poll types could be done. E.g. binary poll is poll where range is from 0 to 1 (i.e. no or yes). UI can handles some ranges in such a meaningful way.

  • Anonymous voting ( https://bitbucket.org/JeanLucPicard/nxt/issue/176/private-polls ) is not implemented. It could be implemented with e.g. Blind signatures(https://en.wikipedia.org/wiki/Blind_signature) but it’s not known how to implement that on top of the blockchain. So it seems an anonymous voting could be implemented by trusted 3rd party services only.

Parameters

Voting models

Four voting models exist:

  • By account, 1 account = 1 Vote

  • By balance, 1 Nqt = 1 Vote (nqt, not nxt!)

  • By asset, 1 Asset Qnt = 1 Vote

  • By Monetary System token, 1 curency unit = 1 Vote

All the models could be enhanced by additional parameter, describing min balance in units(nqt/qnt/currency units).

Counting

Counting happens at the finish block height set during poll creation. And a vote being counted only if it satisfies poll parameters(min balance etc) at that finish height. Please note, a voter could vote with balance < min balance needed to vote(at height where vote has been sent), and that’s valid, but a vote will be counted only if balance >= threshold balance at poll finish height.

Mandatory Parameters

name - a poll’s title, no more than 100 characters

description - detailed poll description, no more than 1000 characters

options - possible options titles to choose from and give a rate to. Minimum one option, maximum 100.

votingModel - four possible values for by-account, by-balance, by-asset, by-token voting

finishHeight - block height in future poll is finishing and counting taking at. Minimum 1 block since inclusion height(so set current height + 2 at least), maximum 14*1440 blocks = 20160 blocks since inclusion height

minNumberOfOptions , maxNumberOfOptions - minimum and maximum number of options a voter can choose

minRangeValue , maxRangeValue - a vote’s value is within this range

minBalance - 0 by default. A vote is counted only if account balance @ finishing height (in nqts/qnts/MS tokens) >= minBalance. Mandatory for by-account voting (i.e. should be more than 0 in case of by-account voting)

minBalanceModel - used in by-account voting to distinguish which kind of units used for minbalance, nqt balance / assets / currency units. For last two options holdingId parameter is also required

Optional parameters

  • holdingId - for voting by assets or MS tokens, also used for minBalance in by-account voting

Notes

  • Voting by asset could be started by anyone, not just asset/currency issuer or even owner

HTTP API

  • Create poll

Use POST request to createPoll API call to create a new poll. Example with curl:

1
curl -d 'name=cryptos&description=rate+cryptos+you+like&finishHeight=300000&votingModel=1&minNumberOfOptions=1&maxNumberOfOptions=2&minRangeValue=-5&maxRangeValue=5&secretPhrase=very+secret+phrase&deadline=1000&feeNQT=1000000000&option00=nxt&option01=btc' http://localhost:6876/nxt?requestType=createPoll

Parameters:

name - mandatory - poll title, not longer than 100 chars

description - mandatory - detailed poll description, max 1000 chars

finishHeight - mandatory - height of block when voting will be finished i.e. counted(should be > current one)

votingModel - mandatory - by-asset, by-account, or by-balance. see corresponding numeric value below

minBalance - mandatory for by-account voting, optional for other types - min amount of money or assets to vote, in nxt or qnt. by default 0(if skipped)

minBalanceModel - mandatory for by-account voting - what kind of tokens to use for vote threshold, nqt/qnt/ms token. See below for possible field values.

minNumberOfOptions - mandatory - min number of options to choose

maxNumberOfOptions - mandatory - max number of options to choose

minRangeValue - mandatory - min vote value possible, no more than 100

maxRangeValue - mandatory - max vote value possible, no less than -100

holdingId - mandatory in case of by-asset voting, could be also usedin addition with minBalance in by-account voting - asset or ms token id in unsigned form

option00,option01,option02,option03,…option99 - titles of corresponding options, please note parameter is always with two digits, starting with 00

Use following numerical values to set voting model:

1
2
3
4
VotingModel.ACCOUNT = 0;
VotingModel.NQT = 1;
VotingModel.ASSET = 2;
VotingModel.CURRENCY = 3;   //MS Token

Use following numerical values to set voting minBalanceModel:

1
2
3
4
MinBalanceModel.NONE = 0;
MinBalanceModel.NQT = 1;
MinBalanceModel.ASSET = 2;
MinBalanceModel.CURRENCY = 3; //MS Token
  • Vote casting

Use POST request to castVote API call to send your vote to the NRS. Example:

1
curl -d 'poll=12528572507118413418&secretPhrase=secret+phrase&deadline=1000&feeNQT=100000000&vote00=1&vote00=0' http://localhost:6876/nxt?requestType=castVote

Parameters are pretty straightforward. Use poll’s transaction id as poll parameter value, use vote00..vote99 to provide weights for option00..option99 options.

Please note, poll should be included into the blockchain to vote on it.

  • Get poll data

Use GET request getPoll to get poll data, e.g.

1
http://localhost:6876/nxt?requestType=getPoll&poll=12528572507118413418 

could returns something like

1
{"minRangeValue":-5,"votingModel":1,"description":"rate cryptos you like","finished":false,"poll":"4555214309048629195","requestProcessingTime":1,"minNumberOfOptions":1,"minBalance":"0","accountRS":"NXT-DV37-DD8K-3Q74-8LE2W","name":"cryptos","options":["nxt","btc"],"finishHeight":300000,"maxNumberOfOptions":2,"minBalanceModel":1,"account":"7926777737834261541","maxRangeValue":5,"timestamp":45731391}
  • Get poll results

Use GET request getPollResult to get poll results, e.g.

1
http://localhost:6876/nxt?requestType=getPollResult&poll=12528572507118413418

example result:

1
{"votingModel":1,"minBalance":"0","options":["nxt","btc"],"finished":false,"poll":"4555214309048629195","requestProcessingTime":1,"minBalanceModel":1,"results":[{"result":"1942320000000","weight":"1942320000000"},{"result":"","weight":"0"}]}

“finished” value is false, so voting still happens!

The request accepts some interesting parameters: votingModel , holding , minBalance , minBalanceModel - you can play with these parameters to see how results could be different depending on polls' input parameters(with the same set of voters).

  • Get polls

Use POST request to getPolls :

1
curl -d 'account=7926777737834261541&firstIndex=0&lastIndex=5&includeFinished=true'  http://localhost:6876/nxt?requestType=getPolls

There’s additional includeFinished parameter(self-explanatory). If account=0, all limited by indexes polls in the chain (active only if includeFinished=false) will be returned.

  • Get vote(s) details

There’re two API calls to get vote details, getPollVote & getPollVotes . First one accepts poll & account parameters, while second accepts just poll (& firstIndex, lastIndex).

  • Search polls

Use searchPoll to find relevant polls by text query. Example query with all the four parameters possible.

curl -d ‘query=cryptos&firstIndex=0&lastIndex=5&includeFinished=true’ http://localhost:6876/nxt?requestType=searchPolls

Fees

If poll contains less than 20 options, fee for it’s creation is 10 Nxt, otherwise each additional option costs 1 Nxt as well.

Vote fee is 1 Nxt.

Settings

There’s only one setting at the moment which could be overriden in nxt.properties:

1
2
3
# If disabled, polls are not processed at finish height and results are not stored in the database.
# When requested, poll results will be calculated on-the-fly, if the votes are still available.
nxt.processPolls=true

Set the value to false if you run a lean node & don’t need for results of all the polls in the chain to be calculated & stored.

Use Cases & Application Ideas

Out of the scope of simple voting, there are a lot of possibilities Voting System provides:

  • Distributed shareholders meetings (using assets as voting rights)
  • Publicly verifiable community decisions (using e.g. Monetary System tokens as community currency)
  • Building consensus protocols on top of the blockchain with strong evidence of a consensus

  • (to be continued)

Internal details (for developers)

This section is for developers working with core, studying the NRS code, or writing apps working closely with the core(so using low-level Java API not HTTP, though that way isn’t recommended unless a developer knows why he’s doing that).

Attachments

There are two kinds of attachments related to voting system: MessagingPollCreation & MessagingVoteCasting. Also please take a look PollBuilder helper implementing Builder pattern to create MessagingPollCreation objects:

1
2
3
4
5
6
7
8
9
10
11
12
val pb = new PollBuilder(question, desc, options, finishBlockHeight, votingModel,
      minNumberOfChoices, maxNumberOfChoices, minRangeValue, maxRangeValue)

minBalanceOpt.map { mb =>
    minBalanceModelOpt match {
      case Some(minBalanceModel) => pb.minBalance(minBalanceModel, mb)
      case None => pb.minBalance(mb)
    }
}
holdingIdOpt.map(hi => pb.holdingId(hi))

issueTx(phrase, pb.build())

Transaction types

There are two transaction types related to VS: Messaging.POLL_CREATION and Messaging.VOTE_CASTING.

Getting data

Take a look to static methods of the Poll class to get data you want. E.g. getPoll(long id) returns poll by its id, getPollsByAccount returns polls created by an account specified etc.

Scorex - Ultracompact Cryptocurrency Engine for Hackers

| Comments

Motivation

There are two huge problems around cryptocurrencies development project Scorex aims to help to solve:

  • Bitcoin source code contains more 100K lines of code(80K of C++ only), Nxt is about more than 45K line of Java code. All parts of the design(network/transactions/consensus layers) are mixed in a hard way. So researchers & developers are definitely not in a good start position to make any experiments. In opposite, Scorex is less than 4K lines of Scala code. Transactions layer is as simple as just tokens transfers. Consensus algo could be switched easily(with two consensus algos out of the box, one could be replaced with an another with just one line of code edited!)

  • Major coins forks are trying to make IPO immediately, often having just one or two pretty controversial features introduced. Scorex is intentionally not production-ready, so please participate in any non-commercial experiments built on top of it, but don’t buy tokens unless you are 100+% sure what are you doing.

Features

  • Compact, functional, actors-powered code
  • Two 100% Proof-of-Stake consensus algos out of the box, Nxt-like and Qora-like. One algo could be replaced with an another with just one line of code edited (in Constants.scala)
  • Simplest transactions model
  • Asynchronous network layer on top of TCP
  • JSON API
  • Command line client for the JSON API
  • Curve25519 for signatures

Releases

There are two releases planned at the moment:

Lagonaki - initial release aiming to provide modular and simple product for hackers.

Kizhi - another branch in development with proof-of-stake consensus algo allows contribution to multiple branches following our papers, along with Nothing-at-Stake attack script etc.

Roadmap

Lagonaki release is mostly ready, there are about 30 todos in code to get done though. We’ll fix them within next few weeks. Some documentation will be written as well. At this point it will be an announcement(this message is the pre-announcement).

Then we’ll test Nxt forging algo improvements proposals with it(a proposal document will be published within next few weeks). And then we’ll work on Kizhi.

Authors

Scorex is made by Consensus Research microteam previously worked on Proof-of-Stake investigation:

Alexander Chepurnoy aka kushti - Nxt developer & smartcontract.com cofounder. Has few published papers in Computer Science field(finite state systems related), writing PHD at the moment.

andruiman - serial entrepreneur with theoretical physics background, big fan of Coq interactive theorem prover & functional programming.

Contributions

We’re highly welcome contributions in form of pull requests, testing, issues reporting, and forking for sure :)

Donations

Also we would be happy to get donations. You can buy our asset on Nxt Assets Exchange: https://trade.secureae.com/#5841059555983208287, Bitcoin wallet is 17YksFD7eRB4NhPfEtGrGnuvuwpkAeBd7f .

Repository URL

https://github.com/ConsensusResearch/Scorex-Lagonaki

CAP Theorem and the Blockchain as the Database

| Comments

CAP Theorem

Before the NXT cryptocurrency I used to be a developer of a distributed system crawling articles around the Web and building Kohonen’s self-organizing map filled with them. During those days I read a lot about CAP theorem. The theorem states pretty common in everyday life principle “you can pick only two out of three” (e.g. in the “Price – Quality – Delivery” triangle). The three desirable options of any distributed system are consistency, system availability and tolerance to a partition fault. And you can pick only two of them.

CAP & Distributed Ledger - The Problem

In case of a distributed ledger CAP properties mean:

  • Consistency - all nodes have the same ledger at the same time
  • Availability - the network accepts transactions at any time
  • Partition tolerance - the network is resistant to a node(s) failure

The sad thing is that widely acceptable currency couldn’t exists without all the three conditions met. Nobody will use a currency if it’s offline during data synchronizations(CP system). Nobody will use a currency if network is vulnerable to a node failure(CA system). And for sure nobody will use currency if different nodes operate with different ledgers(PA system).

The Blockchain Solution

Blockchain is the elegant bypass of a CAP problem for storing a distributed(& decentralized) ledger. So transactions are grouped in blocks, and you can trust block only after some number of confirmations(i.e. number of new blocks added after). In case of Bitcoin, you can rely on transaction just included into the blockchain after 6 confirmations(with a negligible probability of transaction being reversed even after that), in many practical cases 2 or 3 confirmations are enough though (see original Nakamoto’s paper for precise numbers satisfy your needs).

So in terms of consistency the blockchain is about very weak consistency! Working with Riak and other databases with weak consistency, I’ve never seen anything like that.

Forging Simulation Tool for a Proof-of-Stake Cryptocurrency

| Comments

Introduction

I’m the proud member of Consensus Research. Recently we published two executable simulations of forging(term for generating blocks activity in Proof-of-Stake). Multibranch forging simulation has the paper about it. I’m going to describe Nxt-like single-branch forging simulation tool in series of posts, some blogposts about multibranch will be published later also to give simplified description of the tool.

The Tool

The simulation tool is published on GitHub along with short description. Some internal details described in the Inside a Proof-of-Stake Cryptocurrency Part 4: The Executable Forging Simulation article. I don’t want to repeat myself here, so let’s take a closer look on how the tool works and what results it dumps out.

After launching the program it prints out “Starting cryptocurrency simulation…” then does its job silently and dumps out few results to the console when simulation is done:

Alt text

So it dumps out a balance of every node from it’s own balances sheet and common sub-chain length of a node with each other node. The screenshot above shows that most of nodes are agreeing on a chain with 121 or 122 blocks, while there’s a cluster of nodes having 130 blocks in common chain and one node stuck in fork at the moment of the end of an experiment with 116 common blocks.

A lot of detailed data goes into output folder, readme describes files going there.

Forging Quality

Forging quality seems to be worse than in real-world implementations e.g. Nxt mainnet blockchain: big forgers producing few blocks in a row more often(especially after connecting to a network with a genesis state), common chain is behind the current moment. I see some reasons for that:

  • in Nxt a node waits for blockchain to be downloaded then starts to forge, in simulation not
  • there are no latencies, clocks de-synchronization, also all processes are tied to the world clocks, so in case two nodes generate blocks at the same time a hard battle between forks has begun
  • Nxt Reference Software has some additional checks and patches not being presenting in the model

But our goal wasn’t to replicate Nxt forging and propagation processes, so it’s okay for now to have what we have.

Performance

Performance is bad at the moment. And I did not optimizations for the reason: for now understandability is much more important.

Simulating Different Models

Using the simulation tool a researcher can make experiments and get results quickly. For example, to change cumulative difficulty measure from sum of 1/baseTarget to sum of 1/(baseTarget^2) just one line modification needed:

cumulativeDifficulty chain = sum(map (\bl -> two64 / ((fromIntegral $ baseTarget bl)**2) ) chain)

And from first look things are getting worse after that.

Further Improvements

  • Better output, e.g. CSV format usage to work with results in Excel or statistics tools
  • Some aggregated metrics, e.g. number of forks living in a network, overall network consensus quality etc
  • Latency modelling
  • For now nodes stay online forever, better to model going offline at random moments
  • Better performance

Usage

  • We already using the mix of this tool with multibranch forging simulation to play with Nothing-at-Stake issues(a paper on that is ready and will be published soon)

  • We can make experiments very quickly (see “Simulating Different Models” section above)

  • As result, community can compare different forging models without long debates, e.g. compare Nxt & Qora forging, or see improvement proposals in action

Inside a Proof-of-Stake Cryptocurrency Part 4: The Executable Forging Simulation

| Comments

Introduction

In first 3 parts Nxt-like 100% proof-of-stake forging algorithm was described. It would be exciting to run executable simulation of it to see network-wide consensus in action. And now this simulation tool is published! Please take a look to it’s README for details, and this article is about some aspects of the source code unrevealed yet.

Modules

All the code is split into three modules(files):

  • blockchain.hs, module Blockchain.Structures - basic structures and functions, building bricks for the simulated cryptocurrency network & its forging algorithm

  • simulation.hs, module Blockchain.Simulation - structures & functions related to simulation

  • launcher.hs. module Main - some auxiliary functions & main function running simulation and dumping results into files

Most of basic structures and functions were decscribed in first 3 parts of the series, so now we’re going to take a look into simulation functions.

systemTransform

The most important function in simulation module is systemTransform taking current state of a network along with timestamp and common data for the simulation and transforming it to resulting network state by applying some partial transformers:

systemTransform :: SimulationData -> Network -> Network
systemTransform sd network = networkForge sd $ generateTransactions sd $
            propagateLastBlock sd $ propagateTransactions sd $ downloadBlocksNetwork sd $
        dropConnections sd $ generateConnections sd $ addNode sd $ addInvestorNode sd network

Where

  • addInvestorNode makes some initial investor online. Network starts with just one online investor out of 20, system balance is spread uniformly in a genesis block. Max number of investors online (14,000 seconds after genesis and on) are 13, means 65% forging power being online

  • addNode adds a node to the simulated network with no blockchain & empty account. The node needs to download a blockchain from other nodes.

  • generateConnections generates a connection for a node to another node if number of outgoing connection is less than a limit given in settings file(20 by default)

  • dropConnections works once per 60 seconds, drop oldest connection for a node, if number of outgoing connections equals to the limit

  • downloadBlocksNetwork selects random neighbour for each peer and check it’s cumulative difficulty, and if this metrics is better for the neighbour, the node is going to download a chunk of blockchain after common chain(14,400 blocks max)

  • propagateTransactions selects random neighbour for each peer and sends transactions from peer’s unconfirmed transactions pool a naighbour doesn’t have

  • propagateLastBlock selects nodes having last block generated by other node not more than 15 seconds ago and sends it out to a random neighbour

  • generateTransactions generates random transactions sending max 5% stake out(for account having more than 200 coins out of 1,000,000,000 issued)

  • networkForge asks each node whether it has a right to generate a block(by it’s own opinion) and if so generates blocks for forgers found and sends them out to random neighbours

Nothing-at-Stake simulation

By mixing multibranch forging simulation tool published previously with blockchain forging simulation tool described in the article it’s possible now to simulate Nothing-at-Stake attack, e.g. by mixing nodes doing blockchain forging with “attacker” doing multibranch forging. We’ll publish our work on that soon.

Conclusion & Further Work

Well, it’s the last article in the “Inside a Proof-of-Stake Cryptocurrency” series. All of them:

And executable code corresponding is on GitHub: https://github.com/ConsensusResearch/ForgingSimulation. Some modifications will be made, I want to replace all the constants with configurable parameters, at least. Performance optimization is also needed, for now it’s performance isn’t good for simplicity’s sake.

Inside a Proof-of-Stake Cryptocurrency Part 3: A Local Ledger

| Comments

Pre-Introduction: Consensus Research Group

After previous article I started to work with friend of mine, andruiman on deeper investigation of proof-of-stake. We are working now as Consensus Research group and have successful Phase 1 crowdfunding almost done.

We have published paper on multibranch forging, while I continue to describe a model of 100% Proof-of-Stake single-branch forging.

Introduction

Cryptocurrency ledger lives in p2p network and as any information shared in AP distributed environment it’s a subject of inconsistency. So we will talk about local ledger as there’s no global ledger in a network though algorithms behind a cryptocurrency try to build some common view under some assumptions.

Local Ledger

In pt. 1 global network-wide structure System was defined slightly wrong for simplicity’s sake:

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

For now this simplification becomes too rude, so we’re going to remove accounts and rename the structure to Network (connections definition also changed but just for performance’s sake)

data Network = Network {
    nodes :: [Node],
    connections :: Map Node [Node]
}

New field to be injected into node to store it’s local state is localView,

data Node =
    Node {
        localView :: LocalView,
        unconfirmedTxs :: [Transaction],
        account :: Account          -- simplification - one account per node
        isForging :: Bool
    }

and consist of two entities:

data LocalView =
    LocalView{
        nodeChain :: BlockChain,        -- simplification - one blockchain per node(but true for NRS)
        balances :: Map Account Int
    }

The latter entity containing balances for known accounts isn’t strictly necessary but without it simple question “what’s the account balance now?” will need for whole local blockchain to be processed to answer.

To update balances during transaction processing we define ‘applyTx’ transformer function:

applyTx :: Transaction -> Map Account Int -> Map Account Int
applyTx tx blns = addMoney amt (recipient tx) $ addMoney (-amt) (sender tx) blns
    where amt = amount tx

where auxiliary function addMoney just adds some diff value to an account balance:

addMoney ::  Int -> Account ->  Map Account Int -> Map Account Int
addMoney diff acc blns = insert acc ((findWithDefault 0 acc blns) + diff) blns

To process a block, we process each transaction it contains then add sum of all transaction fees to a block generator balance:

processBlock :: Block -> Map Account Int -> Map Account Int
processBlock block priorBalances = appliedWithFees
    where
        txs = transactions block
        txApplied = foldl (\bs tx -> applyTx tx bs) priorBalances txs
        fees = sum(map fee txs)
        appliedWithFees = addMoney fees (generator block) txApplied

A Local Ledger & The Network Consensus

In a proof-of-stake environment chance to generate block & incoming block check result are depend on a balance of an account. But information about balances is local, so all decisions are also made locally. E.g. If cluster of nodes have own view of network, they will reject blocks from other nodes and build own blockchain. Is that good or bad? Well, the question is open, as well as other consensus properties in proof-of-stake networks.

Further Work

Next chapter will be about building blocks of an executable simulation of Nxt-like single-branch forging. Sources of the simulation tool will be published the same time.

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 in case of Bitcoin). We will use sum of 1/baseTarget to select canonical blockchain from possible options and call this function cumulativeDifficulty:

cumulativeDifficulty :: BlockChain -> Double
cumulativeDifficulty chain = sum(map (\bl -> 1 / (fromIntegral $ baseTarget bl) ) chain)

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.