Proof-of-Stake Protocol - IOHK

21 September 2016 Bernardo David <1 min read

889

Proof-of-Stake Protocol - IOHK

This is the regular seminar of the Input Output and Tokyo Tech/Tanaka Laboratory members. The topic this time is the Proof-of-Stake Protocol designed by Aggelos Kiayias, Ioannis Konstantinou, Alexander Russel, Bernardo David and Roman Oliynykov.

Bernardo, the presenter, divided the talk in two parts: the first reviews main topics in Cryptography which would help the viewer to understand the presentation and the protocol itself. Whereas the second is about the protocol itself.

First Part - Cryptography background

  • Commitments
  • Coin Tossing/Guaranteed Output Delivery
  • Verifiable Secret Sharing

Second Part - Proof-of-Stake Protocol

  • Comparison Proof-of-Work (PoW) and Proof-of-Stake (PoS)
  • Follow the Satoshi technique
  • The protocol

The paper is

A Provably Secure Proof-of-Stake Blockchain Protocol

Transaction malleability in cryptocurrencies

14 September 2016 Dmitry Meshkov 5 mins read

Transaction malleability in cryptocurrencies - Input Output HongKong

Transaction malleability in cryptocurrencies

In this article I'm going to provide a brief review of protection methods against replay attacks, arising from signature malleability of elliptic curve cryptography.

Problem

Most cryptocurrencies are based on public-key cryptography. Each owner transfers coins to the next one digitally signing the transaction Tx containing the public key of the next owner.

Thus everyone can verify that the sender wants to send her coins to the recipient, but a problem arises - how to prevent the inclusion of transactin Tx in the blockchain twice? Without such a protection an unscrupulous recipient may repeat Tx as long as the sender has enough coins at his balance, making it impossible to reuse the same address for more then 1 transaction. In particular the adversary can withdraw some coins from an exchange and repeat this transaction until there are no coins left on exchange (such attacks have already been executed in practice, e.g. for

MtGox
attack).

The simplest way to keep all the included transactions and compare the new one to them doesn't work because of the elliplic curve signature malleability - it is possible to change a signature but keep it valid at the same time (see

here
).

Scala code that changes signature like that is very simple:

    def forgeSignature25519(signature: Array[Byte]): Array[Byte] = {  
        val modificator: BigInt = BigInt("7237005577332262213973186563042994240857116359379907606001950938285454250989")  
        signature.take(32) ++ (BigInt(signature.takeRight(32).reverse) + modificator).toByteArray.reverse  
    }

Thus, now we have a sequence of transactions Tx1, ..., TxN with the same fields, but different signatures, and there's a challenge to determine whether they are all generated by the sender or some of them are generated by the adversary.

Solutions

In this section I'll provide examples of how this problem is solved in different cryptocurrencies and will try to describe the merits and drawbacks of each approach.

Canonical signature (Factom, Ripple, Nxt)

As long as there is sequence of valid signature, there may be a rule to select only one of them. The usual way is to select canonical signature, which is lower then group generator ("7237005577332262213973186563042994240857116359379907606001950938285454250989" for curve25519). Unfortunately for some elliplic curves for any given canonical signature an alternative form of that signature can be formed that is also canonical. In such a case it's required to define fully canonical signature, being the minimum of all equivalent signatures. The main drawback of this approach is that fully canonical signature is not specified in the protocol and default elliplic curve implementations don't usually check if a signature iscanonical and don't generate canonical signature, which makes cross-platform implementation much harder.

Signature independent id

It's also possible to modify transaction uniqueness check, leaving all possible signatures valid as specified in elliptic curve protocol. For example it's possible to use the rule that the transaction data excluding yje signature should be valid. That has a drawback of being unable to create 2 transactions with the same fields, while non-deterministic signatures may indicate that sender really wanted to send 2 transaction with the same fields. To fix this it's possible to include transaction id into transaction explicitly, e.g. some cryptocurrencies sign transaction, use this signature as id and then sign this internaltransaction with signature one more time.

Nonce (Ethereum, Waves)

Another way is to add an additional field to the transactions, increasing for transactions from the same address. Current nonce for every account should be stored in the blokchain state and with each new transaction Tx nodes verify that Tx.nonce = account.nonce + 1. On top of replay attack protection nonce allows you to broadcast sequence of transactions and be confident that only one of them will be included to blockchain.

For example, if you need your transaction to be included in block as soon as possible, you may rebroadcast your transaction with the same nonce, but increased fee and be sure, that only one of your transactions will pass all checks. Nonce provides additional benefits for transactional layer, but not for free - every transaction should contain nonce, so transaction size become bigger. On the other size nonce should be big enough, because it's not clear how to handle a situation when nonce limit has been reached. To mitigiate this it's possible to reuse a transaction field as nonce, for example use timestamp as a nonce.

In such an approach it's not possible to require to increase nonce by 1, so rule Tx.timestamp > account.timestamp should be used. This leads to another attack: if someone broadcasted sequence of transactions Tx1, ...,TxN with increasing timestamp, "evil" miner may only include TxN making transactionsTx1, ..., TxN-1 invalid.

Conclusion

It's not yet clear to me what the best way is to protect against replay attacks, arising from signature malleability of elliptic curves - each approach has it's benefits and drawbacks. This approaches may be combined with each other, e.g. it's possible to require canonicalsignature together with nonce. Feel free to provide more approaches and examples in comments, it would be cool to choose an optimal solution!

Ethereum Classic: An Update

9 September 2016 Charles Hoskinson 8 mins read

Ethereum Classic An Update - Input Output HongKong

Ethereum Classic: An Update

I wanted to draft a brief update on IOHK's efforts on Ethereum Classic (ETC). We've had the opportunity to schedule more than three dozen meetings with developers, community managers and academic institutions. We've also managed to have several long discussions with several of the community groups supporting ETC to get a better sense of commitments, goals and philosophy. Overall, it's been a really fun experience getting to know a completely decentralized philosophical movement. It's also been illuminating to parse the challenges ahead for the fragile movement as it charts its own path forward. I'll break the report down into what we learned and what we are going to do.

What We Learned

Carlo Vicari and I have been trying to map out the total ETC community and also get some metadata about who they are (vocation, age, geography, interests...) so we can better understand the core constituencies. We will publish some preliminary stats sometime next week, but as a rough summary there are currently several meetup groups, a telegram group, a reddit, several Chinese specific hubs, a slack with over 1,000 members and a few other lingering groups.

Daily activity is growing and there is interest in more formal structure. With respect to developers, there are about a dozen people with development skills and knowledge of the EVM and solidity in the developer channel. They have been holding pretty deep discussions about potential directions and roadmaps. The biggest topics are currently pivoting consensus to PoW without the difficult bomb, new monetary policy and also safer smart contracts.

There is also interest in forming a pool of capital to pay for development efforts ranging from core infrastructure to DApps on top of the system. I haven't taken a position on this effort because we still need to address some governance and legal questions. Regardless of whether this pool materializes, IOHK's commitment of three full time developers will be funded solely by IOHK.

It seems that the price and trading volume of ETC has held relatively stable despite the virtual sword of damocles that is the DAO hacker and RHG funds. It seems that there is enough community interest in ETC to keep liquidity. I do think there will be tremendous volatility ahead and it's going to be impossible to predict when black swans are going to land in our laps, but I suppose that's what makes it fun?

IOHK's Commitment

After the initial conversations and analysis, we have determined the following serious deficits with ETC:

  1. There isn't an official or reliable channel of information about the events of the ecosystem or commitments of various actors. This reality has lead to FUD, impersonations and attempts at market manipulation in the absence of clarity.
  2. The roadmap of ETC needs to include at a minimum an emphasis on safety, sustainability and stability. There is a strong desire amongst the ETC community members we had discussions with to focus on reliable, high assurance applications that run on a network with proven fundamentals. Effectively, this needs to be the antithesis of move fast and break things.
  3. There is a desire amongst several well capitalized actors to donate capital to a pool to fund the growth of ETC. This desire has been complicated by the lack of a clear governance structure that will avoid fraud or misuse of funds. Furthermore an open pool would allow funds to potentially become tainted by RHG or Dao hacker donating funds to it. While code is law covers the protocol level use of funds, it does not shield actors from the legal realities of their actions. It is unclear how these funds should be treated or if accepting them would constitute a crime.
  4. The media is uncertain how to report on ETC outside of a referential curiosity to ethereum itself . There needs to be a re-branding and media strategy to ensure new users enter the ecosystem with a clear understanding of what ETC is about and how it differs from ETH.
  5. Concepts like the replay attack and also new potential technology that could be adopted are not fully understood by ETC community members or general developers. There needs to be actors dedicated to education and explanation.
  6. The Ethereum Foundation owns the Ethereum trademark. Further use of this branding could provoke a trademark infringement lawsuit to companies using the Ethereum brand and name. This complicates the formation of a centralized governance entity or steering committee if it chooses to use ethereum classic as its name. It also complicates business commitments to building on the ETC chain.
There are likely more problems, but these seem to be the most pressing for the time being. They are also compounded by the decentralized nature of the movement, which seems to be a boon for resilience, but a curse for agility. Given this fact, IOHK obviously cannot move unilaterally to address all of these problems; however, we can chart a course and invite the community to follow where they deem reasonable.

Thus IOHK is in the process of doing the following:

  1. We have interviewed several community manager candidates and will make our final selection sometime next week. He or she will be responsible for assisting meetup group founders, managing social media channels, broadcasting accurate information, combating FUD, collecting feedback from the ETC community and dealing with media entities. My hope is this position will be defined by its interactions with the ETC community and give us a starting point for timely and credible information at the very least.
  2. IOHK is going to subsidize an educator to produce content on ETC ranging from the replay attack to new proposals suggested in various roadmaps. We have one candidate in mind and are finalizing the contract and duration of the relationship. All content will be released under a creative commons license and our hope is to again let this role be community driven.
  3. IOHK has had numerous discussions with academic partners about the consensus algorithm of ETC and also the smart contract model. We would like to see if the EVM can be improved to be more secure and that Typescript and Purescript could be used as ETC's smart contract languages representing both a functional and imperative approach to development that maps nicely onto the skillsets of existing developers. We are seeing what types of partnerships are possible in the next few months and will provide an update.
  4. We've also spent quite a bit of time looking at Smart contract languages on the horizon. There are some excellent ideas coming from Synereo and Juno's Hopper. IOHK has entered into a partnership with Kent University to begin an analysis of Transaction Languages used in cryptocurrencies. We will have a survey report available sometime in Q4 of 2016. This report will form the basis of our organization's understanding of the interplay of smart contracts in cryptocurrencies. Once available we will release it to the general public as a whitepaper.
  5. We have decided that Scorex 2 will make a good base to build our ETC Main Client (Read Alex's First Blog on It). The core is going through a massive refactoring that will be finished sometime this month. From this point, we will retain a scala specific team (our three developer commitment) to fork Scorex 2 and build a full ETC Node including a wallet with GUI. The architecture of Scorex should allow for much faster iterative improvements and also a great opportunity to test our new blockchain specific database IODB .
  6. With respect to the developer hires in particular, we have taken quite a few resumes already, but also want to make the process open to the general public. Our new community manager will post the job ad on the ETC reddit once he's been hired. I expect the first developer to be announced sometime in September. Quality scala developers with the requisite skills to make meaningful contributions to Ethereum are rare and require careful vetting.
  7. With respect to a technological steering committee to guide the roadmap process, we are proposing the formation of a federated group tentatively called the smart contract engineering taskforce (after the IETF). Ideally we could develop an RFC process to propose improvement proposals from the community without the need for a formal, centralized entity. We'd love to see this form as a DAO. There could be two tracks covering changes requiring forks and changes that are iterative in nature. We will start the discussion about this group sometime in early October.
  8. IOHK cannot resolve the trademark issue, but will make a commitment to not use the Ethereum brand or name in its repos or company assets. This said, we would like to see some form of bilateral resolution to this situation. It seems pyrrhic to seek trademark enforcement on a decentralized movement. We also understand the confusion this issue is causing the general public and developers.
Overall, it's been a great two months and I look forward to the next few to see ETC continue to grow and become a strong, stable cryptocurrency. I'd like to thank the awesome community and all their help. I'd also like to thank the people who had enough patience to talk with Carlo and me despite the long meetings.

====== Edit: Special Shout out to the Ethereum Classic Russian Community:

https://ethclassic.ru/

RollerChain, a Blockchain With Safely Pruneable History

7 September 2016 Alexander Chepurnoy 3 mins read

RollerChain, a Blockchain With Safely Pruneable History - Input Output HongKong

RollerChain, a Blockchain With Safely Pruneable History

When you starting a Bitcoin node it is downloading all the transactions for more than 7 years in order to check them all. People are often asking in the community resources whether it is possible to avoid that. In a more interesting formulation the question would be “can we get fullnode security without going from genesis block”? The question becomes even more important if we consider the following scenario. Full blocks with transactions are needed only in order to update a minimal state, that is, some common state representation enough to check whether is arbitrary transaction is valid(against the state) or not. In case of Bitcoin, minimal state is unspent outputs set (we call this stateminimal as a node could also store some additional information also, e.g. historical transactions for selected addresses, but this information is not needed to check validity of an arbitrary transaction). Having this state (with some additional data to perform possible rollbacks) full blocks are not needed anymore and so could be removed.

In Bitcoin fullnodes are storing all the full blocks since genesis without a clear selfish need. This is the altruistic behavior and we can not expect nodes to follow it in the long term. But if all the nodes are rational how a new node can download and replay the history?

The proposal recently put on Arxiv
trying to solve the problems mentioned with a new Proof-of-Work consensus protocol. I very lightly list here modifications from Bitcoin, for details please read the paper.

  1. State is to be represented as an authenticated data structure(Merkle tree is the simple example of such a data structure) and a root value of it is to be included into a blockheader. It is the pretty old idea already implemented in Ethereum(and some other coins).
  2. We then modify a Proof-of-Work function. A miner is choosing uniformly k state snapshot versions out of last n a (sufficiently large) network stores collectively. In order to generate a block miner needs to provide proofs of possession for all the state snapshots. On a new block arrival a miner updates k+1 states, not one, so full blocks (since minimal value in k) are also needed.
Thus miners store a distributed database of last n full blocks AND state snapshots getting rewards for that activity. A new node downloads blockheaders since genesis first (header in Bitcoin is just 80 bytes, in Rollerchain 144 bytes if a hash function with 32 bytes output is chosen). Then it could download last snapshot or from n blocks ago, or from somewhere in between. It is proven that this scheme achieves fullnode-going-from-genesis security with probability of failure going down exponentially with “n” (see Theorem 2 in the paper). Full blocks not needed for mining could be removed by all the nodes. They can store them as in Bitcoin but we do not expect it anymore.

The RollerChain fullnode is storing only sliding window of full blocks thus storing disk space, also less bandwidth is needed in order to feed new nodes in the network and so bandwidth saved could be repurposed for other tasks.

Ode to the Contrarian Artifacts

27 August 2016 Charles Hoskinson 6 mins read

Ode to the Contrarian Artifacts - Input Output HongKong

Ode to the Contrarian Artifacts

A Fistful of Pauls

It was the night of January 3rd, 2008 in Des Moines Iowa. The temperature was a brutally cold ten degrees, yet over a hundred thousand caucus goers endured long lines, confusing rules and poorly organized events to express their political will in the republican primaries. Just days earlier, many internal and some local polls showed Ron Paul performing admirably in a dead heat with Mike Huckabee.

It seemed as if the revolution's recent fundraising wins would translate into votes. It seemed as if the entire republican establishment was going to endure a defeat harsher than the wars they inflicted on the American people over the last eight years. Yet when the results came in, each percent point was like a dagger in the heart of the movement. The end tally was roughly ten percent support for a total around 11,000 people. Some rallies attracted nearly that many people. Somehow Huckabee attracted 4 votes for each of Paul's.

It seemed as if the harsh defeat was now reserved for the Paul movement. Some campaigners, exhausted from running the full grassley twice in just a few of months cried. Other responded with rage. Some argued that the vote had been rigged- afterall, the University commitments alone were 15,000 votes. One campaigner sat silently on an outside bench without a coat carrying a grave thousand yard stare for several hours. It was an easy time to feel hopeless. The remainder of the primaries didn't help.

In the aftermath, many wrote the Ron Paul campaign off as a populist anomaly. An internet era federation of John Birchers marrying the Austrians to return the American people to the 19th century's deflationary horrors and isolationism. How dare a campaign inflict the banality of historical reflection upon the American people! How dare he ask his fellow candidates to read books and think about the nature of money!

The appraisal couldn't be further from the truth. The contrarian arguments grew and now have created an entire generation of advocates who desire to end the fed, return to the gold standard, end foreign entanglements and embrace constitutional rights. In a more abstract sense, the contrarian always seems to be maligned, mocked and diminished; however, occasionally plants seeds that will eventually overcome whatever social paradigm they are fighting against.

Dr. Infinity

Another figure that comes to mind is Cantor. He is now regarded as one of the greatest mathematicians of the last few centuries including the company of Riemann, Euler and Gauss. Analogous to Paul's heresy of addressing the inconvenient and sensitive topic of monetary policy, Cantor dared to ask deep questions about the nature of infinity. He presented a diagonalization argument that demonstrated that while both the natural and real numbers are endless, they are somehow a different type of endlessness.

This work simultaneously led to extraordinary questions like the continuum hypothesis and to Cantor's dreadful consternation at his peer's sharp dismissals ranging from "grave disease" to "scientific charlatan". While he has been posthumously vindicated, the treatment by his peers and Cantor's subsequent nervous breakdown demonstrates the social consequences of dissent. As a final irony, there are now some mathematicians such as Norman Wildberger who are actually in the opposite position.

Value of Dissent

The value of contrarians isn't in their efforts to win over the crowd with their counterarguments to the norm- many are in fact completely wrong. Their value is more significant than a policy change or a scientific retooling. The power of contrarian thinking is that it forces a more fundamental appraisal of the axioms and heuristics we tend to use to navigate life.

For example, in the heroic age of medicine, blood letting and cocaine laced mercury were the common notions. Allopathy challenged the entire basis for having these thoughts. The methodology itself was flawed and needed a change.

On the same token, Ron Paul's movement was an electoral failure, but a massive success in the thoughts about money. Value is starting to be viewed more socially and globally than siloed, institutionally enforced magical units of account.

Some of Bitcoin's earliest and more ardent adopters were Paulites who already crossed the mental gap of seeing fiat for what it is- a social artifact. Now Bitcoin is a change engine forcing this humbling truth just by its continued growth and existence.

Lex Ex Machina

Smart contracts seem to me to be another contrarian mental artifact. They are eating at the roots of the common notions of law. Who should enforce laws? What are contracts? What is intent? How should arbitration be addressed?

We have socially constructed answers to these questions forming a corpus of knowledges hundreds of years old. No human could ever appreciate the totality of opinion and elegance of such a construction much less a mathematician ever read and understand the entire proof of the classification of the finite simple groups.

Yet this system is becoming increasingly more expensive to maintain, riddled with inequities and requires legions of domain experts to just interpret its arcane wisdom. Is it moral to propagate a system that hurts the poor, drains society of resources and favors a rich minority to manipulate at a whim?

Whether the effects of smart contracts have a real impact on commercial transactions and push us towards a private legal system for trade is as relevant as Ron Paul's loss. It's the attack on the fundamentals of the existing paradigm given alternatives that is much more meaningful. Contracts can become understandable open source, composable, templatable and in many cases don't require the heavy hand of government to resolve.

There is already a growing movement from Stanford's CodeX group to IBM's Ross providing AI driven legal assistance. As a corollary, I would be authorially negligent if I didn't mention Nick Szabo's recent writings on Wet and Dry code.

Could we now be approaching a future where the government has a moral obligation to give us our own robot lawyer to interpret their Borgesian library of laws? Could we see people switching between legal systems as easily as multinational companies? Will we begin to expect an evolutionary nature in our legal system akin to the accelerating pace of technology? With the right contrarian artifacts perhaps.

An Artifact in Every Thought

The concise summary of my thoughts is that we live in a house of ideas, common notions, social conventions and biases inherited from people no smarter or better equipped than us. We cannot accept at face value their gifts and curses. We have an obligation to introduce contrarian artifacts wherever we can. In the attempt to destroy them, we will expose the naked truth of our constructed reality. It might not be pretty, but it always makes us better.