DAG简介

基于DAG技术的分布式账本(distributed ledger)系统与比特币(bitcion),以太坊(ethereum)等主流数字货币系统和传统区块链(blockchain)系统不同。其特色是使用DAG(Directed Acyclic Graph,有向无环图)来组织交易(transaction)。

传统的区块链技术,以比特币为例,使用的基本方式是矿工通过POW(工作量证明)共识,(即网络认为最⻓的链为真实链,因为最⻓的链拥有最大的工作量证明),将交易打包到区块(block)中,而每一个区块通过在区块头记录前一个区块的hash值来链接到前一个区块上。通过这种方式,后一个区块直接或者间接的确认了前面所有区块的交易,这样通过POW共识解决了双花问题。

与基于区块链的传统分布式账本技术(基于POW和单链式数据结构)不同,基于DAG技术的分布式账本技术,去掉了区块的限制,通过有向无环图的数据结构,允许后一交易同时连接到多个父亲交易,将交易通过有向图的方式直接连接在一起。 在DAG中,交易构成了图中所有的节点。而带有方向的图的边(edge)表达了交易之间的先后确认关系。箭头由子节点指向父节点,表示了子交易直接或间接地确认了父交易的这种关系,同时也说明了子交易和父交易确认的先后顺序,即子交易一定被确认在父交易之后。这种父子关系是DAG确认机制和抵抗双花的核心。当一个交易产生时,该新产生的交易需要选取某些当前待确实交易来作为该交易的父交易(一个子交易可以有多个父交易)。子交易总是希望连接到包含更多的先辈节点的父交易上。对于一个新交易,在可选有限个父交易的情况下,为了直接或者间接的确认更多的祖先节点,子交易总是试图连接无孩交易(即tips)做为他的父交易,这样使得DAG的方向性得以建立。

DAG技术的优势

  • DAG技术对于高并发具有先天的优势。
  • DAG技术交易确认快,网络可实现即时确认的。不需要向比特币那样需要等待10分钟左右的出块时间,或者像以太坊那样等待15到16秒。
  • DAG技术不受区块大小的限制,不存在区块扩容问题。所以其可伸缩性只取决于网络带宽,CPU处理速度(例 如数字签名加密算法的处理速度)和存储容量的限制。

DAG技术的难点

  • 由于DAG技术这种允许先连接,再判断的方式,对于双花处理则需要更加复杂的设计,从而解决基于DAG的双花问题,这就给如何实现基于DAG技术的区块链系统带来了很多复杂性,这也是目前基于DAG系统的区块链系统还极为少⻅的原因。
  • 目前还没有完美的基于DAG技术的分布式共识算法。
  • 技术还不够成熟,市场接受程度低。

DAG技术的未来

  • DAG技术将是未来区块链和分布式账本技术发展的一种核心趋势。(如Spectre协议和以太的Casper协议)
  • 基于DAG技术的分布式账本技术有可能广泛的应用于金融交易系统和企业资产管理系统中。(如Ripple,Corda,hyperledger等系统的有力竞争者)
  • 基于DAG技术的智能合约能有效解决智能合约的可扩展性(scalability),并且降低合约执行成本。

注释

  • 目前比特币的区块容量是1M,实际情况约能容纳2000多个交易。而以太坊区块大约能容纳200多个交易。比特币社区因为扩容问题带来的争议而严重影响了客戶体验,使得比特币的发展陷入一个瓶颈。同时以太坊试图以分片(sharding)的方式解决扩容的问题,但分片的方式将增加跨区智能合约的事务复杂度,对如何实现分片和分片环境下智能合约的开发都带来很多新的挑战,是否可以解决问题还有待时间去验证。
  • 目前世界上主要有两个有名项目使用DAG技术:IOTA 项目和字节雪球(byteball)项目。相信未来有更多的项目使用DAG技术。

DAG技术发展历史

  • DAG数据结构 (?)
    • https://en.wikipedia.org/wiki/Directed_acyclic_graph
  • lamport lock and partital order (1978)
    • https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
  • Git (2005, Linus Torvalds)
  • Ghost (2013) (Yonatan Sompolinsky and Aviv Zohar -> see Spectre&Daglab)
    • https://eprint.iacr.org/2013/881.pdf
    • Ethereum (2014)
  • NXT (2014,mthcl,Come-from-Beyond)
    • https://nxtforum.org/proof-of-stake-algorithm/dag-a-generalized-blockchain/?all
    • mtchl -> Serguei Popov (founder of IOTA)
    • cfb -> Sergey Ivancheglo (founder of IOTA)
  • IPFS (2014,Juan Bennet)
    • Git+Merkle -> Merkle DAG
    • https://ipfs.io/ipfs/QmR7GSQM93Cx5eAg6a6yRzNde1FQv7uL6X1o4k7zrJa3LX/ipfs.draft3.pdf
    • https://github.com/ipfs/ipfs/issues/1
  • dagcoin (2015, Sergio Demian Lerner, chief scientist of RSK)
    • https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf
  • Triangle/JINN -> IOTA (2015)
    • https://nxtforum.org/news-and-announcements/iota-jinn/?all
  • Bytball (2016, Anton Churyumov)
    • https://byteball.org/Byteball.pdf
  • HashGraph (2016, Leemon Baird, co-founder and CTO of Swirlds)
    • The algorithm is protected by patents in the USA.)
    • http://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf
  • Spectre/daglab (2016~2017, Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar)
    • Yonatan Sompolinsky -> (PhD student at the Hebrew University, -> Computer Scientist at daglib)
    • Yoad Lewenberg -> PhD student at the Hebrew University -> Research Engineer at daglab
    • Aviv Zohar -> (Senior Lecturer (Assistant. Prof.) at The School of Engineering and Computer Science at The Hebrew University )
    • https://eprint.iacr.org/2016/1159.pdf
    • https://www.daglabs.com/

Wallet

Intro

A deterministic wallet is a system of deriving keys from a single starting point known as a seed. The seed allows a user to easily back up and restore a wallet without needing any other information and can in some cases allow the creation of public addresses without the knowledge of the private key. Seeds are typically serialized into human-readable words in a Mnemonic phrase.

How MEW works with Ledger

  • https://github.com/kvhnuke/etherwallet/blob/f8fdab1ea92d436015119e3c2ba865308289e88d/app/scripts/controllers/decryptWalletCtrl.js#L21
  • https://github.com/kvhnuke/etherwallet/blob/f8fdab1ea92d436015119e3c2ba865308289e88d/app/scripts/controllers/decryptWalletCtrl.js#L43
  • https://github.com/kvhnuke/etherwallet/blob/f54c093c1b1e230b60e238582f2765afd61b2a05/app/scripts/staticJS/ledger-eth.js#L76
  • https://github.com/kvhnuke/etherwallet/blob/f54c093c1b1e230b60e238582f2765afd61b2a05/app/scripts/staticJS/ledger-eth.js#L45
  • https://github.com/LedgerHQ/blue-app-eth/blob/cdc8c7436c76d7600d855f1411b5bc00e55980b7/src_genericwallet/main.c#L63 0x02 -> INS_GET_PUBLIC_KEY
  • https://github.com/LedgerHQ/blue-app-eth/blob/cdc8c7436c76d7600d855f1411b5bc00e55980b7/src_genericwallet/main.c#L2153
  • https://github.com/LedgerHQ/blue-app-eth/blob/dca33eab262730e94353c9c6ea57027389bb03da/src_common/ethUtils.c#L177

How MEW show addresses

以ledger为例,MEW了获取"m/44'/60'/0'"这个路径下的公钥,然后使用hdkey,得到5个derivedKey(m/0 ~m/4), 再使用ethereumjs-util生成了前五个地址。

  • https://github.com/kvhnuke/etherwallet/blob/f8fdab1ea92d436015119e3c2ba865308289e88d/app/scripts/controllers/decryptWalletCtrl.js#L272 result['publicKey'], result['chainCode']
  • https://github.com/kvhnuke/etherwallet/blob/f8fdab1ea92d436015119e3c2ba865308289e88d/app/scripts/controllers/decryptWalletCtrl.js#L267 注:hdk来自于var HDKey = require('hdkey');
    • https://github.com/cryptocoinjs/hdkey/blob/0.7.1/lib/hdkey.js#L13
  • https://github.com/kvhnuke/etherwallet/blob/f8fdab1ea92d436015119e3c2ba865308289e88d/app/scripts/controllers/decryptWalletCtrl.js#L183
  • https://github.com/kvhnuke/etherwallet/blob/mercury/app/scripts/myetherwallet.js#L171
    • https://github.com/ethereumjs/ethereumjs-util/blob/v5.1.2/index.js#L287
    • https://github.com/ethereumjs/ethereumjs-util/blob/v5.1.2/index.js#L440

Let's see electrum

  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/wallet.py#L1746
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/wallet.py#L93
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/wallet.py#L1645,L1655
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/wallet.py#L1638
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/keystore.py#L232
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/bitcoin.py#L1013
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/bitcoin.py#L878-L891
  • https://github.com/spesmilo/electrum/blob/3.0.1/lib/synchronizer.py

Server side

  • client side request address history
    • https://github.com/spesmilo/electrum/blob/3.0.1/lib/network.py#L640
  • https://github.com/spesmilo/electrum-server/blob/master/src/blockchain_processor.py#L310
  • https://github.com/spesmilo/electrum-server/blob/master/src/storage.py#L309
  • https://github.com/spesmilo/electrum-server/blob/master/src/storage.py#L205

注意electrum混合使用了自己的levelDB库和bitcoind,某些调用走bitcoind,而某些调用走自己的库,例如utxo,address等。electurm会在后台同步(catch_up)bitcoind的数据,从bitcoind中读取block,然后存放在自己的数据库里面。这是为了优化查询。

  • https://github.com/spesmilo/electrum-server/blob/master/src/blockchain_processor.py#L608
  • https://github.com/spesmilo/electrum-server/blob/master/src/blockchain_processor.py#L407

Account discovery

When the master seed is imported from an external source the software should start to discover the accounts in the following manner:

  1. derive the first account's node (index = 0)
  2. derive the external chain node of this account
  3. scan addresses of the external chain; respect the gap limit described below
  4. if no transactions are found on the external chain, stop discovery
  5. if there are some transactions, increase the account index and go to step 1

References

  • BIPs
    • BIP39 : Mnemonic code for generating deterministic keys
      • https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
    • BIP32 : Hierarchical Deterministic Wallets
      • https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
    • BIP43/BIP44 : Multi-Account Hierarchy for Deterministic Wallets
      • https://github.com/bitcoin/bips/blob/master/bip-0043.mediawiki
      • https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki
      • https://github.com/satoshilabs/slips/blob/master/slip-0044.md
  • https://en.bitcoin.it/wiki/Deterministic_wallet
  • https://en.bitcoin.it/wiki/Deterministic_wallet_tools

BIP39

  • https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
  • https://github.com/trezor/python-mnemonic/blob/master/mnemonic/wordlist/english.txt (2048)

PGP Worldlist

  • https://en.wikipedia.org/wiki/PGP_word_list
  • The Decred wallet seed is initialised with a 33 word selection from a 512 word dictionary, the PGP Word List. BIP39 in comparison for 256 bits of entropy with 8 bits of checksum uses 24 words from a standardised 2048 word dictionary.
  • http://docs.electrum.org/en/latest/seedphrase.html
  • https://github.com/decred/dcrwallet/issues/956
  • https://github.com/decred/dcrwallet/blob/master/walletseed/seed.go
  • https://github.com/decred/dcrwallet/blob/master/pgpwordlist/pgpwordlist.go

Testnet & faucet

Testnet5

  • Testnet5 block explorer
    • https://testnet5.blockchain.info/
  • Testnet5 faucet
    • http://li1164-223.members.linode.com/request
    • https://faucet.haskoin.com/

Ropsten

  • https://ropsten.etherscan.io
  • http://faucet.ropsten.be:3001
  • https://faucet.metamask.io/
  • https://www.rinkeby.io/#faucet

Kovan

  • https://github.com/kovan-testnet/proposal
  • http://kovan-stats.parity.io/
  • https://kovan.etherscan.io/
  • https://github.com/kovan-testnet/faucet
    • https://gitter.im/kovan-testnet/faucet
    • https://kovan.etherscan.io/tx/0x935f7e405c5f8f747c0f7cea71bb2f5102bb57c419377e6b2f80e85974307190

Oracles.org

  • http://testnet.oracles.org:4000/
  • http://oraclesfaucet.herokuapp.com/
    • http://testnet.oracles.org:4000/tx/0x52126c5841c86d055a2c24d0455653dfa786b531307ed9fc03f2ebe432787d96

Byteball Testnet

Address

Base58 encoding

Reference

DAG数据结构与算法

深度优先&广度优先 (Breadth-First Vs. Depth-first Search)

screen shot 2017-10-27 at 12 24 10 pm

DAGs and Topological Ordering

screen shot 2017-10-27 at 12 30 38 pm

  • The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability.

  • The reachability relationship in any directed acyclic graph can be formalized as a partial order ≤ on the vertices of the DAG. In this partial order, two vertices u and v are ordered as u ≤ v exactly when there exists a directed path from u to v in the DAG; that is, when v is reachable from u.[5] However, different DAGs may give rise to the same reachability relation and the same partial order.[6] For example, the DAG with two edges a → b and b → c has the same reachability relation as the graph with three edges a → b, b → c, and a → c. Both of these DAGS produce the same partial order, in which the vertices are ordered as a ≤ b ≤ c.

  • Every directed acyclic graph has a topological ordering, an ordering of the vertices such that the starting endpoint of every edge occurs earlier in the ordering than the ending endpoint of the edge. The existence of such an ordering can be used to characterize DAGs: a directed graph is a DAG if and only if it has a topological ordering. In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.[9]

  • The family of topological orderings of a DAG is the same as the family of linear extensions of the reachability relation for the DAG,[10] so any two graphs representing the same partial order have the same set of topological orders.

Steven S Skiena. The Algorithm Design Manual

Three important facts about topological sorting are

  1. Only DAGs can be topologically sorted, since any directed cycle provides an inherent contradiction to a linear order of tasks.
  2. Every DAG can be topologically sorted, so there must always be at least one schedule for any reasonable precedence constraints among jobs.
  3. DAGs can often be topologically sorted in many different ways, especially when there are few constraints. Consider n unconstrained jobs. Any of the n! permutations of the jobs constitutes a valid topological ordering.

References

  • https://en.wikipedia.org/wiki/Directed_acyclic_graph
  • http://www3.cs.stonybrook.edu/~algorith/files/topological-sorting.shtml
  • https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/traverse/TopologicalOrderIterator.java
    • https://github.com/jgrapht/jgrapht/wiki/DependencyDemo
  • Graphs and Digraphs BFS Priority search DAG Connectivity
  • https://homes.cs.washington.edu/~jrl/421slides/lec5.pdf

Intro

  • Ripple
  • Corda
  • Cosmos
  • Hyperledger

References

  • https://ripple.com/build/transactions/
  • https://cosmos.network/whitepaper#transaction-types
  • https://docs.corda.net/tutorial-building-transactions.html

Reference

  • http://learnmeabitcoin.com/glossary/transaction-data
  • http://royalforkblog.github.io/2014/11/20/txn-demo/
  • https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc

Index stored in LevelDB

Block Index

'b' + 32-byte block hash -> block index record. :
The block header.
The height.
The number of transactions.
To what extent this block is validated.
In which file, and where in that file, the block data is stored.
In which file, and where in that file, the undo data is stored.
'f' + 4-byte file number -> file information record. 
The number of blocks stored in the block file with that number.
The size of the block file with that number ($DATADIR/blocks/blkNNNNN.dat).
The size of the undo file with that number ($DATADIR/blocks/revNNNNN.dat).
The lowest and highest height of blocks stored in the block file with that number.
The lowest and highest timestamp of blocks stored in the block file with that number.
'l' -> 4-byte file number: the last block file number used.
'R' -> 1-byte boolean ('1' if true): whether we're in the process of reindexing.
'F' + 1-byte flag name length + flag name string -> 1 byte boolean ('1' if true, '0' if false): various flags that can be on or off. Currently defined flags include:
'txindex': Whether the transaction index is enabled.
't' + 32-byte transaction hash -> transaction index record. These are optional and only exist if 'txindex' is enabled (see above). :
Which block file number the transaction is stored in.
Which offset into that file the block the transaction is part of is stored at.
The offset from the start of that block to the position where that transaction itself is stored.

chain state

https://github.com/bitcoin/bitcoin/blob/d4a42334d447cad48fb3996cad0fd5c945b75571/src/coins.h#L21L69

'c' + 32-byte transaction hash -> unspent transaction output record for that transaction. 
These records are only present for transactions that have at least one unspent output left.:
The version of the transaction.
Whether the transaction was a coinbase or not.
Which height block contains the transaction.
Which outputs of that transaction are unspent.
The scriptPubKey and amount for those unspent outputs.
'B' -> 32-byte block hash: the block hash up to which the database represents the unspent transaction outputs.

RFC

  • rfc6962
    • https://tools.ietf.org/html/rfc6962#page-4

MTree in Bitcion

MTree in Ethereum

MTree in Corda

  • https://github.com/corda/corda/blob/master/core/src/main/kotlin/net/corda/core/crypto/PartialMerkleTree.kt
    • https://github.com/corda/corda/blob/master/core/src/main/kotlin/net/corda/core/crypto/MerkleTree.kt
  • https://github.com/corda/corda/blob/master/core/src/test/kotlin/net/corda/core/crypto/PartialMerkleTreeTest.kt
    • https://docs.corda.net/releases/release-M10.1/merkle-trees.html
    • https://docs.corda.net/releases/release-M10.1/oracles.html
  • https://github.com/corda/corda/blob/master/core/src/main/kotlin/net/corda/core/transactions/MerkleTransaction.kt
    • https://github.com/corda/corda/blob/master/core/src/main/kotlin/net/corda/core/transactions/WireTransaction.kt
  • https://github.com/corda/corda/blob/master/core/src/test/kotlin/net/corda/core/transactions/CompatibleTransactionTests.kt
    • https://docs.corda.net/head/tutorial-tear-offs.html

Reference

Intro

by G.W at The future of Ethereum: "DΞV and Beyond", London ethereum meetup

  • Ethereum state is just the state of a number of accounts
  • Tx is the way to alter the state

References

  • https://github.com/ethereum/wiki/wiki/Patricia-Tree
  • https://crypto.stanford.edu/cs251/hw/hw3.pdf
  • https://github.com/ethereum/wiki/wiki/RLP
  • https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/
  • http://hidskes.com/blog/2014/04/02/ethereum-building-blocks-part-1-rlp/

screen shot 2017-10-27 at 4 10 24 pm

Intro

The purpose of the IAVL+ data structure is to provide persistent storage for key-value pairs in the application state such that a deterministic Merkle root hash can be computed efficiently. The tree is balanced using a variant of the AVL algorithm, and all operations are O(log(n)).

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Whenever this condition is violated upon an update, the tree is rebalanced by creating O(log(n)) new nodes that point to unmodified nodes of the old tree. In the original AVL algorithm, inner nodes can also hold key-value pairs. The AVL+ algorithm (note the plus) modifies the AVL algorithm to keep all values on leaf nodes, while only using branch-nodes to store keys. This simplifies the algorithm while keeping the merkle hash trail short.

The AVL+ Tree is analogous to Ethereum’s Patricia tries. There are tradeoffs. Keys do not need to be hashed prior to insertion in IAVL+ trees, so this provides faster ordered iteration in the key space which may benefit some applications. The logic is simpler to implement, requiring only two types of nodes – inner nodes and leaf nodes. The Merkle proof is on average shorter, being a balanced binary tree. On the other hand, the Merkle root of an IAVL+ tree depends on the order of updates.

References

  • https://github.com/tendermint/merkleeyes
  • https://cosmos.network/whitepaper#iavl-tree

IPFS的数据结构

  • merkleDAG
    • https://github.com/ipfs/go-ipfs/tree/master/merkledag
    • https://github.com/ipfs/go-ipfs/blob/master/core/commands/dag/dag.go
    • https://github.com/ipfs/go-ipfs/blob/master/core/coredag/dagtransl.go
  • merkleDAG Doc
    • https://github.com/ipfs/specs/tree/master/merkledag

IPFS白皮书

  • http://decentralized.blog/understanding-the-ipfs-white-paper-part-1.html
  • http://decentralized.blog/understanding-the-ipfs-white-paper-part-2.html

Data Storage

Intro

There are basically four pieces of data that are maintained:

  • blocks/blk*.dat: the actual Bitcoin blocks, in network format, dumped in raw on disk. They are only needed for rescanning missing transactions in a wallet, reorganizing to a different part of the chain, and serving the block data to other nodes that are synchronizing.
  • blocks/index/:* this is a LevelDB database that contains metadata about all known blocks, and where to find them on disk. Without this, finding a block would be very slow.
  • chainstate/*: this is a LevelDB database with a compact representation of all currently unspent transaction outputs and some metadata about the transactions they are from. The data here is necessary for validating new incoming blocks and transactions. It can theoretically be rebuilt from the block data (see the -reindex command line option), but this takes a rather long time. Without it, you could still theoretically do validation indeed, but it would mean a full scan through the blocks (140 GB as of july 2017) for every output being spent.
  • blocks/rev*.dat: these contain "undo" data. You can see blocks as 'patches' to the chain state (they consume some unspent outputs, and produce new ones), and see the undo data as reverse patches. They are necessary for rolling back the chainstate, which is necessary in case of reorganisations. So yes, everything but the block data itself is indeed redundant, as it can be rebuilt from it. But validation and other operations would become intolerably slow without them.

NOTE: database/:* BDB database environment; only used for wallet since 0.8.0

References

  • https://bitcoin.stackexchange.com/a/11108
  • https://en.bitcoin.it/wiki/Bitcoin_Core_0.11_(ch_2):_Data_Storage
  • https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/doc/files.md
2017-11-04 05:15:09 Cache configuration:
2017-11-04 05:15:09 * Using 2.0MiB for block index database
2017-11-04 05:15:09 * Using 8.0MiB for chain state database
2017-11-04 05:15:09 * Using 440.0MiB for in-memory UTXO set (plus up to 286.1MiB of unused mempool space)
2017-11-04 05:15:09 init message: Loading block index...
2017-11-04 05:15:09 Opening LevelDB in /work/_DATA/Bitcoin_test/1/blocks/index
2017-11-04 05:15:09 Opened LevelDB successfully
2017-11-04 05:15:09 Using obfuscation key for /work/_DATA/Bitcoin_test/1/blocks/index: 0000000000000000
2017-11-04 05:15:10 LoadBlockIndexDB: last block file = 0
2017-11-04 05:15:10 LoadBlockIndexDB: last block file info: CBlockFileInfo(blocks=119836, size=133991641, heights=0...119835, time=2009-01-03...2011-04-23)
2017-11-04 05:15:10 Checking all blk files are present...
2017-11-04 05:15:10 LoadBlockIndexDB: transaction index disabled
2017-11-04 05:15:10 Opening LevelDB in /work/_DATA/Bitcoin_test/1/chainstate
2017-11-04 05:15:10 Opened LevelDB successfully
2017-11-04 05:15:10 Wrote new obfuscate key for /work/_DATA/Bitcoin_test/1/chainstate: cb7b45d88624f992
2017-11-04 05:15:10 Using obfuscation key for /work/_DATA/Bitcoin_test/1/chainstate: cb7b45d88624f992

heights=0...119835, time=2009-01-03...2011-04-23

共识

https://en.wikipedia.org/wiki/Consensus_(computer_science)

  • 对多件事件进行排序,并且得到大家认可。

Lamport Clock (1978)

  • 问题
    • 一致性不是简单的让两个节点最终对一个值的结果一致, 很多时候还需要对这个值的变化历史在不同节点上的观点也要一致
    • 不能简单的以接受到消息的时间作为事件的顺序判断的依据。
    • 物理时间的不可依赖,导致事件的先后关系在分布式系统中退化为事件先后顺序的偏序关系(partital order), 问题的核心演变成如何找出因果关系来取消对物理时钟的依赖。(如果一致性继续弱化的情况下,最终一致(弱一致性)连因果关系都不需要)
  • 论文:Time, Clock and Ordering of Events in a Distributed System
    • https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
  • Lamport Clock
    • 是针对事件发生历史的逻辑时钟, 它让我们能够把所有的历史事件找到偏序关系, 而且不仅在各自节点的逻辑时间参考系内顺序一致, 全局上的顺序也是一致的。

screen shot 2017-10-25 at 6 53 06 pm

P/Q/R是三个节点, 从下往上代表物理时间的流逝, p1, p2, q1, q2, r1, r2 …. 表示事件,波浪线表示事件的发送, 比如p1->q2表示 P把p1事件发送给了Q, Q接受此消息作为q2事件。

screen shot 2017-10-25 at 6 54 20 pm

screen shot 2017-10-25 at 6 51 11 pm

  • 两种一致性模型(Seq,linear)
    • Sequential Consistency (1979)
      • How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
      • https://lamport.azurewebsites.net/pubs/pubs.html#new-approach
      • https://lamport.azurewebsites.net/pubs/pubs.html#multi
    • linearizability Consistency (1990, M.P. Herlihy & J.M Wing)
      • 线性一致性:Seq的前提下,加强进程间的操作排序

2PC

  • 1978
  • Jim Gary
  • Tuxedo (XA/Open规范)

3PC

  • 1981
  • Dale Skeen - Nonblocking Commit Protocols

拜占庭将军问题

  • 1982
  • Lamport - The Byzantine Generals Problem
  • https://en.wikipedia.org/wiki/Byzantine_Generals_problem

FLP不可能原理

  • 1985

  • FLP是论文作者(Fischer, Lynch and Patterson)名的缩写。

  • No completely asynchronous consensus protocol can tolerate even a single unannounced process death. [ Impossibility of Distributed Consensus with One Faulty Process,Journal of the Association for Computing Machinery, Vol. 32, No. 2, April 1985] 在异步网络环境中只要有一个故障节点, 不存在一个共识算法能解决一致性问题。

  • 在允许节点失效的情况下,纯粹异步系统无法确保一致性在有限的时间内完成。

  • 同步:网络中节点间的时钟误差存在上限,消息传递必须在一定时间内完成,否则为失败;同时节点完成处理消息的时间是一定的。

    • 对于同步系统,可以很容易判断消息是否丢失
  • 异步:网络中节点时钟差异可以很大,消息传输时间可以任意长,节点处理消息的时间也可以任意长。

    • 那么消息无法响应无法知道是传输故障还是节点故障。
  • 工程上通过付出代价的方式来达到共识。

  • http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/ (A Brief Tour of FLP Impossibility)

CAP原理

  • 2000
  • 一致性consistency、可用性availability、分区容忍性partition 无法同时保证
  • 一致性 :这里之强一致性,任何操作都是原子的,发生在后面的事件能够看到前面事件发生所导致的结果。(换句话,即保证结果一致,也保证过程/顺序一致) ** 弱化一致性 : Gossip,CouchDB,Cassandra
  • 可用性 :在有限时间内,任何非失败节点都能应答请求。 ** 弱化可用性 :MongoDB、Redis、MapReduce。Paxos、Raft。
  • 分区容忍 : 允许网络分区(脑裂),即节点直接通信无法保障。 ** 弱化分区容忍 :2PC,Zookeeper

Paxos

  • 1990 ~ 2001
  • Paxos Made Simple (2001)

Zookeeper

Raft

PBFT

POW (bitcoin)

  • The Bitcoin Backbone Protocol: Analysis and Applications
    • https://eprint.iacr.org/2014/765.pdf
    • http://crypto.2014.rump.cr.yp.to/59182e301d011c3b5b6146b8cdf91815.pdf
  • The Bitcoin Backbone Protocol with Chains of Variable Difficulty
    • https://eprint.iacr.org/2016/1048.pdf
  • Bitcoin as a Transaction Ledger: A Composable Treatment
    • https://eprint.iacr.org/2017/149.pdf
  • Analysis of the Blockchain Protocol in Asynchronous Networks
    • https://eprint.iacr.org/2016/454.pdf

Table of Contents

IOHK/ada

  • Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol
    • https://eprint.iacr.org/2016/889.pdf
  • Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain
    • https://eprint.iacr.org/2017/573.pdf

白皮书研究

解决PoS的核心问题 : the leader election process.

  • 问题:entropy -> randomized election among stakeholders <- an adversary controlling a set of stakeholders, “grinding” vulnerability, use computational resources to bias the leader election.
  • 方法:
    • 第一:模型
      • persistence 和 liveness
      • P是机制保证Tx变成stable,就会全网finality (常见的思路是more than k blocks deep)
      • L是机制保证合法Tx在某个时间段后一定能stable(也就是说合法交易一定能活下去)
    • 第二:选主协议
      • a coin-flipping protocol ->randomness -> leader election
      • a snapshot of the current set of stakeholders is taken in regular intervals called epochs
      • a secure multiparty computation takes place utilizing the blockchain itself as the broadcast channel
      • in each epoch a set of randomly selected stakeholders form a committee which is then responsible for executing the coin-flipping protocol
      • The outcome of the protocol determines the set of next stakeholders to execute the protocol in the next epoch as well as the outcomes of all leader elections for the epoch.
    • 第三:一组规则
      • protect persistence and liveness.
      • (1) any honest stakeholder is able to communicate with any other stakeholder,
      • (2) a number of stakeholders drawn from the honest majority is available as needed to participate in each epoch,
      • (3) the stakeholders do not remain offline for long periods of time
      • (4) "forkable strings” (???)
    • 第四:经济激励
      • 基于博弈论/纳什均衡设计对抗 block withholding 和 selfish-mining
      • positive payoff --> cannot be stifled by a coalition of parties --> an equilibrium when all players are rational. (问题是玩家理性吗?)
    • 第五:代理机制
      • stake delegation mechanism -> delegate “voting rights”
      • 可以revoke delegation

抗攻击性的考虑

  • double spending attacks
  • transaction denial attacks
  • 51% attacks
  • nothing-at-stake
  • desynchronization attacks

性能

  • transaction confirmation time is from 10 to 16 times faster than that of bitcoin
  • analysis of double-spending attacks relies on our combinatorial analysis of forkable and covertly forkable strings and applies to a much broader class of adversarial behavior than Nakamoto’s more simplified analysis. (???)
  • prototype implementation and report on benchmark experiments run in the Amazon cloud that showcase the power of our proof of stake blockchain protocol in terms of performance.

其他的一些POS协议

Sleepy consensus

  • https://eprint.iacr.org/2016/918.pdf
    • considers a fixed stakeholder distribution (i.e., stake does not evolve over time) and targets a “mixed” corruption setting, where the adversary is allowed to be adaptive as well as perform fail-stop and recover corruptions in addition to Byzantine faults.
    • It is actually straightforward to extend our analysis in this mixed corruption setting, resulting security can be argued only in the “corruptions with delay” setting, and thus is not fully adaptive.

Snow White

  • https://eprint.iacr.org/2016/919.pdf
    • addresses an evolving stakeholder distribution and uses a corruption delay mechanism similar to ours for arguing security.
    • susceptible to a “grinding” type of attack that can bias high probability events in favor of the adversary. While this does not hurt security asymptotically, it prevents a concrete parameterisation that does not take into account adversarial computing power.

Algorand

  • https://arxiv.org/pdf/1607.01341.pdf
    • distributed ledger following a Byzantine agreement per block approach that can withstand adaptive corruptions.
    • Given that agreement needs to be reached for each block, such protocols will produce blocks at a rate substantially slower than a PoS blockchain (where the slow down matches the expected length of the execution of the Byzantine agreement protocol) but they are free of forks.
    • In this respect, despite the existence of forks, blockchain protocols exhibit the flexibility of permitting the clients to set the level of risk that they are willing to undertake, allowing low risk profile clients to enjoy faster processing times in the optimistic sense.

Fruitchain

  • https://eprint.iacr.org/2016/916.pdf
    • reward mechanism and an approximate Nash equilibrium proof for a PoW-based blockchain.
    • We use a similar reward mechanism at the blockchain level, nevertheless our underlying mechanics are different since we have to operate in a PoS setting.
    • The core of the idea is to provide a PoS analogue of “endorsing” inputs in a fair proportion using the same logic as the PoW-based byzantine agreement protocol for honest majority

Cardano SL

  • The core idea of proof of stake is that instead of wasting electricity on cracking computationally heavy problems, a node is selected to mint a new block, with a probability proportional to the amount of coins this node has. If a node has positive (> 0) stake, it is called a stakeholder. If a node eventually becomes chosen to mint a block, it is called a slot leader.
  • Cardano SL is called “Layer” for a reason. It is the first component of the Cardano Platform. Eventually, it will be expanded with a Control Layer, serving as a trusted computation framework to evaluate a special kind of proofs to ensure that a certain computation was carried out correctly. In gaming and gambling, such systems are used for verifying honesty of random number generation and game outcomes. Accompanied with side chains, it will make possible to accomplish such tasks as provably fair distribution of winnings in games. But the application of Control Layer lies well beyond gaming and gambling. Identity management, credit system and more will be a part of Cardano Platform. We are also aiming to evolve Daedalus, the Cardano SL wallet application, into a universal cryptocurrency wallet featuring automated cryptocurrency trading and cryptocurrency-to-fiat transactions.

Ouroboros POS算法

  • proof : having evidence that blocks of transactions are legitimate.
  • Stake : the relative value held by addresses on the node. “relative value” we mean “all value held by wallets on a particular node divided by total value in the system”.
  • Slot : A small period of time that is significantly larger than the expected difference in clocks on different nodes.
  • slot leaders: generate blocks for the blockchain. Anyone can become a slot leader if the coin selection algorithm would select a coin they own. Nothing except for the network state and network participants being online matters for the sake of proof of stake.
  • Follow the Satoshi (FTS) is an algorithm, that verifiably picks a coin, providing randomness. When your coin gets selected, you become a slot leader and can listen to transactions announced by others, make a block of those transactions, sign it with your secret key and publish it to the network. (随机选择算法)
  • Multi Party Computation approach: select nodes provide the so-called “commitments”, and then those get “revealed”, producing a random value generated independently by participants of the network. (提供算力)

Slot-leader 选择算法

  • Leaders for each slot of the current epoch are computed by FTS in the beginning of the current epoch.
  • So genesis block contains a list of selected slot leaders.
  • The number of selected slot-leaders corresponds to a number of slots in epoch, and this number depends on fundamental security parameter k defined in configuration file.
  • Theoretical aspects of the slot leader selection process is described in paper, page 11.
  • The node sorts all unspent outputs (utxo) in a deterministic way (lexicographically), so result is an ordered sequence of pairs (StakeholderId, Coin), where StakeholderId is an id of stakeholder (its public key hash) and Coin is an amount of coins this stakeholder has. It’s assumed that utxo isn’t empty.
  • Then the node chooses several random is between 1 and amount of Lovelaces in the system. To find owner of i-th coin node finds the lowest x such that sum of all coins in this list up to ‘i’-th is not less than ‘i’ (and then ‘x’-th address is the owner of i-th coin).
  • The result is a non-empty sequence of StakeholderId, ids of selected stakeholders. This sequense of SlotLeaders is storing in the node’s runtime context.
  • With P2SH addresses, node doesn’t know who is going to end up with funds sent to them. Therefore, P2SH addresses can contain destination address which specifies which addresses should count as “owning” funds for the purposes of FTS.

代码

  • https://github.com/input-output-hk/cardano-sl
  • 版本历史

screen shot 2017-10-18 at 3 32 29 pm

FTS (Follow the Satoshi)

  • https://github.com/input-output-hk/cardano-sl/blob/master/lrc/Pos/Lrc/Fts.hs

Blockchain

  • https://github.com/input-output-hk/cardano-sl/blob/master/lib/src/Pos/Block/Core/Genesis/Chain.hs
  • https://github.com/input-output-hk/cardano-sl/tree/master/lib/src/Pos/Block/Logic

参考文档

  • https://cardanodocs.com/introduction/#what-makes-cardano-sl-special
  • https://cardanodocs.com/cardano/proof-of-stake/
  • https://cardanodocs.com/technical/leader-selection/
  • https://cardanodocs.com/cardano/explorer/
  • https://cardanoexplorer.com/
  • https://cardanodocs.com/glossary/
  • https://cardanodocs.com/technical/blocks/

Video

问题

  • Proof of stake with rigorous security guarantees. 严格安全保证在哪里?
  • Proof of Stake protocols and we prove that, given this mechanism, honest behavior is an approximate Nash equilibrium 如果是基于博弈论和纳什均衡的话,那么以太的casper也是这样。区别是什么?

BW怼cardano事件

  • https://steemit.com/cardamon/@dan/peer-review-of-cardano-s-ouroboros
  • BW认为ada抄袭(copy)了他的工作,但是没有提他( Ouroboros is a copy of Delegated Proof of Stake (DPoS) with a few counter-productive modifications. In fact their paper refers to the term “πDPoS” 17 times without mentioning or recognizing any of my prior work.)
  • 结果上,BW认为ada的性能和效率完败
    • 出块 EOS: 0.5 seconds vs. Ouroboros: 20 seconds
    • 稳定 EOS: <= 2 seconds vs. Ouroboros: > 5 hours
  • ada的安全在工程上不可行:400公斤的防弹衣没法穿。(为啥BW没说明)
  • 对dPOS的分析
    • 选人 (Selecting a set of block producers)
    • 排队 (Scheduling the producers into time slots)
  • 选人
    • 时间轮: BTS 1h vs Ouroboros:5 days
    • 参与要求:Steem 没有下限 vs. Ouroboros at least 1% stake
  • 排队
    • 随机性:
      • Steem 从确定一组里面随机抽(uses deterministic scheduling with pseudorandom shuffling)
      • Ouroboros 随机性由随机选定的权益人生成(sampling from a source of provable randomness created by a committee of randomly selected stakeholders)
    • 安全性:
      • Steem / BitShares / EOS 靠投票(人为)select a set of unlikely to collude entities by approval voting then schedule them in a pseudorandom order。 同时EOS要取消shuffle ( EOS will be removing the random shuffle all together.)
      • Ouroboros 随机选择导致时间和延时无法预期 Ouroboros the length of time until 2/3+ of the stake is “randomly selected” is not known. unpredictable latency like bitcoin
  • 分布式安全(Distribution Security Issues)
    • Steem 14 people confirm a block each round.
    • 只有投票才能对抗基于stake权重的中心化 stake-weighted voting creates a very high centralization that can only be countered with approval voting
    • Corruption takes place at the individual level, not the stake level. it is wrong to assume that large stake holders will behave like a group of smaller stakeholders of similar size

BLS

  • https://en.wikipedia.org/wiki/Boneh%E2%80%93Lynn%E2%80%93Shacham
  • https://crypto.stanford.edu/pbc/
  • https://github.com/dfinity/bn/blob/master/bls/src/bls_c.cpp
  • https://github.com/dfinity/go-dfinity-crypto/blob/master/bls/bls.go

Threshold Relay

which applies cryptography to create randomness on demand of sufficient network participants

  • https://dfinity.org/faq.html

  • The composition of each group is entirely random such that they can intersect and clients can be presented in multiple groups. In DFINITY, each group is comprised of 400 members. When a group is defined, the members attempt to set up a BLS threshold signature system using a distributed key generation protocol. If they are successful within some fixed number of blocks, they then register the public key ("identity") created for their group on the global blockchain using a special transaction, such that it will become part of the set of active groups in a following mining "epoch". The network begins at "genesis" with some number of predefined groups, one of which is nominated to create a signature on some default value. Such signatures are random values - if they were not then the group's signatures on messages would be predictable and the threshold signature system insecure - and each random value produced thus is used to select a random successor group. This next group then signs the previous random value to produce a new random value and select another group, relaying between groups ad infinitum and producing a sequence of random values.

  • How to Achieve Near-Instant Finality in Public Blockchains using a VRF

  • DFINITY Crypto Techniques

Quorum & Quorum slices

screen shot 2017-10-26 at 5 03 21 pm => screen shot 2017-10-26 at 5 03 40 pm

  • Quoram 决定全局共识
  • Quoram slices 决定区域共识
  • 这就是所谓FBFT的Federated的来由,所谓结盟的含义。
  • Quoram slices就是从我自己视角里面我信任的成员,所谓我的帮派,我的同盟。

screen shot 2017-10-26 at 5 19 41 pm

Reference

  • https://www.stellar.org/developers/guides/concepts/scp.html
  • https://www.stellar.org/papers/stellar-consensus-protocol.pdf
  • https://medium.com/a-stellar-journey/on-worldwide-consensus-359e9eb3e949
  • https://github.com/stellar/stellar-core/blob/master/docs/readme.md
  • https://github.com/stellar/stellar-core/tree/master/src/scp
  • https://github.com/stellar/stellar-core/blob/master/src/xdr/Stellar-SCP.x
  • https://github.com/stellar/stellar-core/blob/master/src/scp/SCP.h

介绍

  • https://matrix.org

协议

  • https://matrix.org/docs/spec/
  • https://matrix.org/docs/spec/intro.html

2.4 Event Graphs

Events exchanged in the context of a room are stored in a directed acyclic graph (DAG) called an "event graph". The partial ordering of this graph gives the chronological ordering of events within the room. Each event in the graph has a list of zero or more "parent" events, which refer to any preceding events which have no chronological successor from the perspective of the homeserver which created the event. Typically an event has a single parent: the most recent message in the room at the point it was sent. However, homeservers may legitimately race with each other when sending messages, resulting in a single event having multiple successors. The next event added to the graph thus will have multiple parents. Every event graph has a single root event with no parent. To order and ease chronological comparison between the events within the graph, homeservers maintain a depth metadata field on each event. An event's depth is a positive integer that is strictly greater than the depths of any of its parents. The root event should have a depth of 1. Thus if one event is before another, then it must have a strictly smaller depth. ......

2.5 Room structure

...... Federation maintains shared data structures per-room between multiple home servers. The data is split into message events and state events. Message events: These describe transient 'once-off' activity in a room such as an instant messages, VoIP call setups, file transfers, etc. They generally describe communication activity. State events: These describe updates to a given piece of persistent information ('state') related to a room, such as the room's name, topic, membership, participating servers, etc. State is modelled as a lookup table of key/value pairs per room, with each key being a tuple of state_key and event type. Each state event updates the value of a given key.

The state of the room at a given point is calculated by considering all events preceding and including a given event in the graph. Where events describe the same state, a merge conflict algorithm is applied. The state resolution algorithm is transitive and does not depend on server state, as it must consistently select the same event irrespective of the server or the order the events were received in. Events are signed by the originating server (the signature includes the parent relations, type, depth and payload hash) and are pushed over federation to the participating servers in a room, currently using full mesh topology. Servers may also request backfill of events over federation from the other servers participating in a room. ......

Dendrite

  • 基于Go的参考实现
    • https://github.com/matrix-org/dendrite
    • https://github.com/matrix-org/dendrite/blob/master/DESIGN.md
    • https://github.com/matrix-org/dendrite/blob/master/WIRING.md

Ripple

基于拜占庭,注意Proposer的使用

Component

  • Server: A server is any entity running the Ripple Server software (as opposed to the Ripple Client software which only lets a user send and receive funds), which participates in the consensus process.
  • Ledger: The ledger is a record of the amount of currency in each user’s account and represents the “ground truth” of the network. The ledger is repeatedly updated with transactions that successfully pass through the consensus process.
  • Last-Closed Ledger: The last-closed ledger is the most recent ledger that has been ratified by the consensus process and thus represents the current state of the network.
  • Open Ledger: The open ledger is the current operating status of a node (each node maintains its own open ledger). Transactions initiated by end users of a given server are applied to the open. ledger of that server, but transactions are not considered final until they have passed through the consensus process, at which point the open ledger becomes the last-closed ledger.
  • Unique Node List (UNL) : Each server, s, maintains a unique node list, which is a set of other servers that s queries when determining consensus. Only the votes of the other members of the UNL of s are considered when determining consensus (as opposed to every node on the network). Thus the UNL represents a subset of the network which when taken collectively, is “trusted” by s to not collude in an attempt to defraud the network. Note that this definition of “trust” does not require that each individual member of the UNL be trusted (see section 3.2).
  • Proposer : Any server can broadcast transactions to be included in the consensus process, and every server attempts to include every valid transaction when a new consensus round starts. During the consensus process, however, only proposals from servers on the UNL of a server s are considered by s.

共识算法

screen shot 2017-10-28 at 11 34 34 am

  1. Initially, each server takes all valid transactions it has seen prior to the beginning of the consensus round that have not already been applied (these may include new transactions initiated by endusers of the server, transactions held over from a previous consensus process, etc.), and makes them public in the form of a list known as the “candidate set”.
  2. Each server then amalgamates the candidate sets of all servers on its UNL, and votes on the veracity of all transactions.
  3. Transactions that receive more than a minimum percentage of “yes” votes are passed on to the next round, if there is one, while transactions that do not receive enough votes will either be discarded, or included in the candidate set for the beginning of the consensus process on the next ledger.
  4. The final round of consensus requires a minimum percentage of 80% of a server’s UNL agreeing

注意Propose和Validate的区分

screen shot 2017-10-28 at 12 04 25 pm screen shot 2017-10-28 at 12 04 51 pm screen shot 2017-10-28 at 12 05 18 pm screen shot 2017-10-28 at 12 05 54 pm

Reference

Code

  • https://github.com/ripple/rippled.git

Casper

Casper CBC

  • https://github.com/ethereum/cbc-casper
  • https://github.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf
  • https://youtu.be/Yo9o5nDTAAQ?t=22530
  • https://github.com/ethereum/sharding/blob/develop/sharding/contracts/validator_manager.v.py

POS + BFT

  • chain-based POS (mimics POW & build a chain of blocks & simulates mining)
  • BFT based POS (Tendermint, Algorand)

Casper解决的问题

  • 如何惩罚坏人 -> solve "nothing at stake” problem -> validator’s entire deposit
  • validators如何更新 -> validator set to change over time
  • 如何应对攻击
    • long range revision attacks,
    • 1/3 validators drop offline

介绍

  • first version of Casper a hybrid PoW/PoS system
  • future versions converting the block proposal into a some kind of PoS round-robin block signing scheme.
  • simple version : a fixed set of validators and a proposal mechanism which produces child blocks of existing blocks, forming an ever-growing block tree. the root of the tree is the “genesis block”.
  • Casper’s job is to choose a single child from each parent, thus choosing one canonical chain from the block tree. (canonical chain!)

References

People

Vlad Zamfir at Ethereum ÐΞVcon-0 with Gavin Wood, Berlin, Nov. 2014

screen shot 2017-11-03 at 8 24 26 pm

POA

  • https://github.com/paritytech/parity/wiki/Proof-of-Authority-Chains
  • https://github.com/paritytech/parity/wiki/Demo-PoA-tutorial
  • https://github.com/paritytech/parity/wiki/Aura
  • https://github.com/paritytech/parity/wiki/Chain-specification
  • https://github.com/paritytech/parity/wiki/Pluggable-Consensus
  • https://github.com/paritytech/parity-bridge

Oracles Network

  • https://hackmd.io/s/HkV8Vw7_-#introduction
  • https://medium.com/oracles-network/cross-chain-bridges-paving-the-way-to-internet-of-blockchains-422ac94bc2e5
  • https://github.com/paritytech/parity-bridge/compare/master...oraclesorg:master
  • https://github.com/oraclesorg/oracles-contract/blob/master/src/ValidatorsManager.sol

Tendermint

  • Tendermint
    • https://github.com/tendermint/tendermint/tree/master/consensus

PBFT

  • Fabric 0.6
    • https://github.com/hyperledger/fabric/blob/v0.6/consensus/pbft/pbft-core.go
  • HoneyBadgerBFT
    • https://github.com/amiller/HoneyBadgerBFT
  • 小蚁
    • https://github.com/neo-project/neo/blob/master/src/AntShares/Consensus/ConsensusService.cs

References

  • https://blog.cosmos.network/consensus-compare-tendermint-bft-vs-eos-dpos-46c5bca7204b
  • https://steemit.com/blockchain/@anonymint/consortium-blockchains-e-g-dpos-and-tendermint-can-t-internet-scale

DBFT (NEO)

DBFT 全称为 Delegated Byzantine Fault Tolerant,是一种通过代理投票来实现大规模节点参与共识的拜占庭容错型共识机制。NEO 管理代币的持有者通过投票,可以选出其所支持的记账人。随后由被选出的记账人团体通过 BFT 算法,来达成共识并生成新的区块。投票在 NEO 网络持续实时进行,而非按照固定任期。

DBFT 对由 n 个共识节点组成的共识系统,提供 f=⌊(n-1)/3⌋ 的容错能力,这种容错能力同时包含安全性和可用性,可以抵抗一般性故障和拜占庭故障,并适用于任何网络环境。DBFT 具有良好的最终性,一个确认即最终确认,区块无法被分叉,交易也不会发生撤销或回滚。

在 NEO 的 DBFT 共识机制下,每 15~20 秒生成一个区块,交易吞吐量实测可达到约 1000tps,在公有链中性能优秀。通过适当优化,有能力到达 10000TPS,可以支持大规模的商业化应用。

DBFT 结合数字身份技术,使得记账人可以是实名的个人或机构。从而使得冻结、撤销、继承、找回、司法判决过户等非常规操作成为可能。这有利于合规性金融资产在 NEO 网络中的登记发行。NEO 网络计划在必要的时候支持此类操作。

dPOS

BTS

  • https://bitshares.org/technology/delegated-proof-of-stake-consensus/

Steem

EOS

Lisk

  • https://github.com/LiskHQ/lisk/blob/development/logic/vote.js
  • https://docs.lisk.io/docs/the-lisk-protocol-transactions#section-vote-transaction
  • https://docs.lisk.io/docs/the-lisk-protocol-consensus

References

  • https://github.com/neo-project/neo/blob/master/neo/Consensus/ConsensusService.cs

Algorand ideally proceeds as follows

  • First, a randomly selected user, the leader, proposes and circulates a new block.
    • (This process includes initially selecting a few potential leaders and then ensuring that, at least a good fraction of the time, a single common leader emerges.)
  • Second, a randomly selected committee of users is selected, and reaches Byzantine agreement on the block proposed by the leader.
    • (This process includes that each step of the BA protocol is run by a separately selected committee.)
  • The agreed upon block is then digitally signed by a given threshold of committee members.
  • These digital signatures are circulated so that everyone is assured of which is the new block.
    • (This includes circulating the credential of the signers, and authenticating just the hash of the new block,
      ensuring that everyone is guaranteed to learn the block, once its hash is made clear.)

References

  • https://arxiv.org/pdf/1607.01341.pdf
  • https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
  • https://github.com/fractalide/fractalchains
  • https://zhuanlan.zhihu.com/p/29429006
  • https://www.youtube.com/watch?v=QNQHbfI3IAQ

screen shot 2017-11-08 at 6 41 14 pm

借truebit的图:

  • TPS
    • OnChain
      • Structure change
      • Sharding
      • Paralleling
    • OffChain
      • State channel
      • SideChain
  • Network
  • Storage

Intro

“Ouroboros Praos”, a proof-of-stake blockchain protocol that, for the first time, provides security against fully-adaptive corruption in the semi-synchronous setting: Specifically, the adversary can corrupt any participant of a dynamically evolving population of stakeholders at any moment as long the stakeholder distribution maintains an honest majority of stake; furthermore, the protocol tolerates an adversarially-controlled message delivery delay unknown to protocol participants.

To achieve these guarantees we formalize and realize in the universal composition setting a suitable form of forward secure digital signatures and a new type of verifiable random function that maintains unpredictability under malicious key generation. Our security proof develops a general combinatorial framework for the analysis of semi-synchronous blockchains that may be of independent interest. We prove our protocol secure under standard cryptographic assumptions in the random oracle model.

References

  • https://eprint.iacr.org/2017/573.pdf

EOS parallel

Latency is the time it takes for one account to send a message to another account and then receive a response. The goal is to enable two accounts to exchange messages back and forth within a single block without having to wait 3 seconds between each message. To enable this, the EOS.IO software divides each block into cycles. Each cycle is divided into threads and each thread contains a list of transactions. Each transaction contains a set of messages to be delivered. This structure can be visualized as a tree where alternating layers are processed sequentially and in parallel.

  Block

    Cycles (sequential)

      Threads (parallel)

        Transactions (sequential)

          Messages (sequential)

            Receiver and Notified Accounts (parallel)

How EOS dPOS work

  • https://github.com/EOSIO/eos/blob/master/libraries/chain/include/eos/chain/types.hpp#L120
  • https://github.com/EOSIO/eos/blob/master/libraries/chain/include/eos/chain/config.hpp#L51
  • https://github.com/EOSIO/eos/blob/master/libraries/chain/include/eos/chain/global_property_object.hpp#L32
  • https://github.com/EOSIO/eos/blob/master/libraries/chain/chain_controller.cpp#L269
  • https://github.com/EOSIO/eos/blob/master/libraries/chain/chain_controller.cpp#L1430
  • https://github.com/EOSIO/eos/blob/master/libraries/chain/chain_controller.cpp#L1290
  • https://github.com/EOSIO/eos/blob/master/libraries/native_contract/native_contract_chain_administrator.cpp#L18
  • https://github.com/EOSIO/eos/blob/master/plugins/producer_plugin/producer_plugin.cpp#L282
  • https://github.com/EOSIO/eos/blob/master/plugins/producer_plugin/producer_plugin.cpp#L265
  • https://github.com/EOSIO/eos/blob/master/libraries/native_contract/producer_objects.cpp#L60

Using the EOS.IO software blocks are produced in rounds of 21. At the start of each round 21 unique block producers are chosen. The top 20 by total approval are automatically chosen every round and the last producer is chosen proportional to their number of votes relative to other producers. The selected producers are shuffled using a pseudorandom number derived from the block time. This shuffling is done to ensure that all producers maintain balanced connectivity to all other producers

References

  • https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md#deterministic-parallel-execution-of-applications
  • https://github.com/EOSIO/Documentation/blob/master/zh-CN/TechnicalWhitePaper.md#应用程序的确定性并行执行
    • https://github.com/BlockchainTranslator/EOS/blob/master/TechDoc/EOS.IO%20Technical%20White%20Paper.md

Reference

Validation

Intro

  • https://bitcoincore.org/en/2016/01/26/segwit-benefits/
    • CN https://bitcoincore.org/zh_CN/2016/01/26/segwit-benefits/
  • http://learnmeabitcoin.com/faq/segregated-witness
  • http://learnmeabitcoin.com/workshops/files/segwit.pdf
  • http://blog.oleganza.com/post/163955782228/how-segwit-makes-security-better

Segwit with LN

https://www.reddit.com/r/Bitcoin/comments/5dt8tz/confused_is_segwit_needed_for_lightning_network/

Lightning Network uses payment channels with Hashed TimeLock Contracts. Both of those things are currently usable on Bitcoin mainnet without segwit, so LN is possible without segwit.

However, without segwit or another malleability fix, LN channels have to deal with situations where transactions get mutated ("malleated"), which makes them get stuck at various steps. Preventing them from getting stuck permanently requires either introducing trust (which we don't want to do) or setting some annoying timeouts that limit the efficiency of channels.

LN can also take advantage of many of segwits other benefits such as:

  • Increased security for multisig: every segwit transaction uses multisig, and because it's a new protocol, it can trivially make use of the new segwit output format that allows using this feature.
  • Script versioning: can be used to add new features to Bitcoin more easily than they can be added without segwit (some features being made more easy to add than others). Two features currently being researched are MAST and signature aggretation---both of which can provide modest increases to the capacity of the network and which can help improve transaction privacy.
  • More block space: meaning more channels can be opened or closed in any particular block.
  • Better cost accounting for transactions: related to the above, this provides benefits to people who produce transactions that reduce the short-term and long-term load on full nodes. Lightning-style transactions are effective at doing this, so they benefit from this segwit feature.

Also, fixing malleability for upgraded software makes designing LN-compatible (and any Bitcoin-compatible) wallets much easier in general, so that's a huge plus too.

Segwit with RSK

Spec

  • https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki

References

Intro

Several sources of malleability are known:

  • Non-DER encoded ECDSA signatures Right now, the Bitcoin reference client uses OpenSSL to validate signatures. As OpenSSL accepts more than serializations that strictly adhere to the DER standard, this is a source of malleability. Since v0.8.0, non-DER signatures are no longer relayed already.

  • Non-push operations in scriptSig Any sequence of script operations in scriptSig that results in the intended data pushes, but is not just a push of that data, results in an alternative transaction with the same validity.

  • Push operations in scriptSig of non-standard size type The Bitcoin scripting language has several push operators (OP_0, single-byte pushes, data pushes of up to 75 bytes, OP_PUSHDATA1, OP_PUSHDATA2, OP_PUSHDATA4). As the later ones have the same result as the former ones, they result in additional possibilities.

  • Zero-padded number pushes In cases where scriptPubKey opcodes use inputs that are interpreted as numbers, they can be zero padded.

  • Inherent ECDSA signature malleability ECDSA signatures themselves are already malleable: taking the negative of the number S inside (modulo the curve order) does not invalidate it.

  • Superfluous scriptSig operations Adding extra data pushes at the start of scripts, which are not consumed by the corresponding scriptPubKey, is also a source of malleability.

  • Inputs ignored by scripts If a scriptPubKey starts with an OP_DROP, for example, the last data push of the corresponding scriptSig will always be ignored.

  • Sighash flags based masking Sighash flags can be used to ignore certain parts of a script when signing. New signatures by the sender The sender (or anyone with access to the relevant private keys) is always able to create new signatures that spend the same inputs to the same outputs.

References

  • https://en.bitcoin.it/wiki/Transaction_Malleability
  • https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki
  • https://bitcoin.org/en/developer-guide#standard-transactions
  • https://eklitzke.org/bitcoin-transaction-malleability
  • https://bitcointechtalk.com/transaction-malleability-explained-b7e240236fc7
  • https://www.blackhat.com/docs/us-14/materials/us-14-Chechik-Bitcoin-Transaction-Malleability-Theory-In-Practice.pdf
  • http://www.righto.com/2014/02/bitcoins-hard-way-using-raw-bitcoin.html
  • https://github.com/shirriff/bitcoin-code
  • http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html
  • http://www.righto.com/2014/02/bitcoin-transaction-malleability.html
  • http://www.righto.com/2014/02/the-bitcoin-malleability-attack-hour-by.html
  • http://www.righto.com/2014/03/the-programming-error-that-cost-mt-gox.html
  • https://github.com/sipa/bitcoin/commit/87fe71e1fc810ee120a10063fdd26c3245686d54
  • https://github.com/bitcoinbook/bitcoinbook/blob/second_edition/ch03.asciidoc

A transaction ID is not authoritative until a transaction has been confirmed. Absence of a transaction hash in the blockchain does not mean the transaction was not processed. This is known as "transaction malleability," because transaction hashes can be modified prior to confirmation in a block. After confirmation, the txid is immutable and authoritative.

双花检查研究

Bitcoin

代码

  • https://github.com/dindinw/bitcoin/blob/alex_tx_test/src/test/txvalidationcache_tests.cpp
$ ./test_bitcoin --log_level=unit_scope --run_test=tx_validationcache_tests/tx_mempool_block_doublespend

Using Web service to check unspent BTC

  • BCI
    • https://blockchain.info/unspent?active=<your_addr>
  • Chain.So
    • https://chain.so/api/v2/get_tx_unspent/BTC/<your_addr>

Ethereum

Byteball

代码

  • https://github.com/byteball/byteballcore/blob/master/validation.js#L1443
  • https://github.com/byteball/byteballcore/blob/master/validation.js#L1570,L1675
  • https://github.com/byteball/byteballcore/blob/master/graph.js#L116,L167

Ethereum Simple replay attack protection

  • https://github.com/ethereum/EIPs/blob/master/EIPS/eip-155.md

Segwit2x Replay Protection

References

  • https://bitcointechtalk.com/how-segwit2x-replay-protection-works-1a5e41767103
  • https://bitcoinmagazine.com/articles/segwit2x-and-case-strong-replay-protection-and-why-its-controversial/
  • commit add at Oct 3, 2017
  • commit revert at Oct 8, 2017
  • ReplayProtection.patch by gavinandresen
  • https://github.com/btc1/bitcoin/issues/34
  • https://github.com/btc1/bitcoin/pull/117
    • https://github.com/btc1/bitcoin/pull/134
    • https://github.com/jgarzik/bitcoin/blob/2017_optin_replay/src/primitives/transaction.cpp#L117,L130
  • https://github.com/btc1/bitcoin/pull/127
    • https://github.com/BitcoinUnlimited/BitcoinUnlimited/pull/790
  • https://github.com/btc1/bitcoin/pull/131

Intro

Bitcoin and Ethereum, whose miners arguably collectively comprise the most powerful computational resource in the history of mankind, offer no more power for processing and verifying transactions than a typical smart phone. The system described herein bypasses this bottleneck and brings scalable computation to Ethereum.

Our new system consists of a financial incentive layer atop a dispute resolution layer where the latter takes form of a versatile “verification game.”

In addition to secure outsourced computation, immediate applications include decentralized mining pools whose operator is an Ethereum smart contract, a cryptocurrency with scalable transaction throughput, and a trustless means for transferring currency between disjoint cryptocurrency systems.

TrueBit’s primary purpose is to realize correct, trustless computations despite miners’ limited computation bandwidth. Intuitively, we wish to reward participants who correctly perform computational tasks, but who decides whether these tasks were done correctly? In absence of a dispute, the party who performs a computational task on behalf of a TrueBit contract simply receives a reward. On the other hand, if a dispute does occur, we must rely on the only trusted resource, the limited network of miners, to resolve it.

Video

References

  • https://truebit.io/
  • https://github.com/TrueBitFoundation
  • https://people.cs.uchicago.edu/~teutsch/papers/truebit.pdf
  • https://medium.com/@simondlr/an-intro-to-truebit-a-scalable-decentralized-computational-court-1475531400c3

Money & Token

Dust

"Dust" is defined in terms of CTransaction::minRelayTxFee, which has units satoshis-per-kilobyte. If you'd pay more than 1/3 in fees to spend something, then we consider it dust.

  • A typical spendable non-segwit txout is 34 bytes big, and will need a CTxIn of at least 148 bytes to spend: so dust is a spendable txout less than 546*minRelayTxFee/1000 (in satoshis).
  • A typical spendable segwit txout is 31 bytes big, and will need a CTxIn of at least 67 bytes to spend: so dust is a spendable txout less than 294*minRelayTxFee/1000 (in satoshis).

By default, with a minimum relay fee of 0.00005BTC/KB, the dust is defined as 2730 satoshi. If a transaction pays a decent fee but has an output that has less than 2730 satoshi, it won't be relayed by the nodes with this kind of configuration.

546*5000/1000=2730
294*5000/1000=1740

UPDATE for (0.15.x)

DUST_RELAY_TX_FEE = 3000

Min feerate for defining dust, Historically this has been based on the minRelayTxFee, however changing the dust limit changes which transactions are standard and should be done with care and ideally rarely. It makes sense to only increase the dust limit after prior releases were already not creating outputs below the new threshold.

References

  • https://bitcointalk.org/index.php?topic=1728802.msg17300880#msg17300880
  • https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/src/policy/policy.h#L48

RBF

replace-by-fee, allow users to "undo" transactions after they have been sent ("undo" the unconfirmed transactions)

References

  • https://github.com/petertodd/bips/blob/bip-full-rbf-deadline/bip-full-rbf-deadline.mediawiki
  • https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07829.html
  • https://github.com/bitcoin/bitcoin/pull/6176
  • https://github.com/bitcoin/bitcoin/pull/6352
  • https://medium.com/@octskyward/replace-by-fee-43edd9a1dd6d
  • https://medium.com/@octskyward/double-spending-in-bitcoin-be0f1d1e8008
  • https://medium.com/@bramcohen/the-inevitable-demise-of-unconfirmed-bitcoin-transactions-8b5f66a44a35

Ethereum TxFee

ERC20

  • https://theethereum.wiki/w/index.php/ERC20_Token_Standard
    • https://theethereum.wiki/w/index.php/Golem_Network_Token
  • https://github.com/ethereum/EIPs/blob/master/EIPS/eip-20-token-standard.md
    • https://github.com/ethereum/EIPs/issues/20
  • Zeppelin Token
    • https://github.com/OpenZeppelin/zeppelin-solidity/tree/master/contracts/token
  • DS-Token
    • https://dapp.tools/dappsys/ds-token.html
    • https://github.com/dapphub/ds-token/blob/master/src/token.sol

ERC223

  • https://www.youtube.com/watch?v=GS62VNyPVHs
  • https://github.com/Dexaran/ERC223-token-standard/tree/Recommended

Parity multi-sig

  • Nov-6, 2017 kill bug
    • instead of invoking initWallet on any wallet contract, the attacker called initWallet in the library contract itself.
    • Parity did not anticipate the scenario of this library contract being suicided.
    • https://blog.ethcore.io/security-alert/
    • https://blog.comae.io/the-280m-ethereums-bug-f28e5de43513
    • https://blog.zeppelinos.org/parity-wallet-hack-reloaded/
    • https://ethereum.stackexchange.com/a/30130
    • tx1 : https://etherscan.io/tx/0x05f71e1b2cb4f03e547739db15d080fd30c989eda04d37ce6264c5686e0722c9
    • tx2 : https://etherscan.io/tx/0x47f7cff7a5e671884629c93b368cb18f58a993f4b19c2a53a8662e3f1482f690
  • July-19, 2017 initWallet bug
    • https://blog.zeppelin.solutions/on-the-parity-wallet-multisig-hack-405a8c12e8f7
    • https://github.com/paritytech/parity/commit/e06a1e8dd9cfd8bf5d87d24b11aee0e8f6ff9aeb
    • https://blog.ethcore.io/the-multi-sig-hack-a-postmortem/
    • https://www.youtube.com/watch?v=VUH4gRDQYsA (迄今为止见过的最为详尽的视频介绍,甚至包括如何一步一步重现攻击)
  • Fix
    • danger of delegatecall
      • https://ethereum.stackexchange.com/questions/3667/difference-between-call-callcode-and-delegatecall
    • using Aragon/zeppelin way
      • https://blog.aragon.one/library-driven-development-in-solidity-2bebcaf88736

ERC721

  • ERC721代币的核心是“Non-Fungible Tokens” NFT,不可互换的代币。怎么理解“不可互换”? 比如你有2只猫(猫A和猫B),你的代币数量就是2,但是猫A和猫B是不同的,当你卖出你的猫时,你必须指定是卖哪只猫,因为猫A和猫B是不可以互换的。类比ERC20,就好比你有2块钱,这两块钱,你花其中任意一块钱,都不影响结果,只要账户里扣一块钱就可以了。 ERC721每个代币都有一个独立唯一的tokenid,这个id在这个cryptokitties里就是猫的id.

  • In economics, fungibility is the property of a good or a commodity whose individual units are essentially interchangeable. For example, since one kilogram of pure gold is equivalent to any other kilogram of pure gold, whether in the form of coins, ingots, or in other states, gold is fungible.

  • fungibility, 可互换,可互换物品,可替代性

  • https://github.com/ethereum/EIPs/issues/721

    • http://ethfans.org/posts/eip-721-non-fungible-token-standard

以太猫

  • https://etherscan.io/address/0x06012c8cf97bead5deae237070f9587f8e7a266d#readContract

References

  • https://consensys.github.io/smart-contract-best-practices/
    • (CN) https://github.com/ConsenSys/smart-contract-best-practices/blob/master/README-zh.md

什么是Pre-image

Pre-image是密码学哈希函数的一个安全级别。有的翻译为原像。哈希函数的安全级别包括:

  • Pre-image resistance (抗原像) 给定一个哈希值h,难以找到输入m,使得h = hash(m)。pre-image安全,或者抗per-image,也就意味着这个哈希函数的单向性得以保证。
  • Second pre-image resistance (抗第二原像) 给定一个输入m1,难以找到输入m2,使得hash(m1) = hash(m2)。第二原像,也称为弱抗碰撞性。
  • Collision resistance 抗碰撞性 难以找到两条不同的消息m1m2,使得hash(m1) = hash(m2)。也称为强抗碰撞性。抗碰撞包含了抗第二原像,但并不能保证抗原像。

参考: https://en.wikipedia.org/wiki/Cryptographic_hash_function

Note on RSA and Dual_EC_DRBG

  • https://en.wikipedia.org/wiki/Dual_EC_DRBG
  • http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
  • http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-90a.pdf
  • https://blog.0xbadc0de.be/archives/155

Prime Test

  • https://en.wikipedia.org/wiki/Primality_test
  • https://en.wikipedia.org/wiki/Fermat%27s_little_theorem (费马小定理)
  • https://en.wikipedia.org/wiki/Fermat_primality_test
  • https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
  • https://en.wikipedia.org/wiki/AKS_primality_test

signatures

https://bitcoin.stackexchange.com/a/12556

There are two different encodings used. DER and compact

Everything in the Bitcoin protocol, including transaction signatures and alert signatures, uses DER encoding. This results in 71 bytes signatures (on average), as there are several header bytes, and the R and S valued are variable length.

For message signatures, a custom encoding is used which is more compact (and more recent) and supports public key recovery (given a message and a signature, find which public key would have created it). The code you're referring to in the question is for creating such signatures.

A correct DER-encoded signature has the following form:

  • 0x30: a header byte indicating a compound structure. A 1-byte length descriptor for all what follows.
  • 0x02: a header byte indicating an integer. A 1-byte length descriptor for the R value The R coordinate, as a big-endian integer.
  • 0x02: a header byte indicating an integer. A 1-byte length descriptor for the S value. The S coordinate, as a big-endian integer.

Where initial 0x00 bytes for R and S are not allowed, except when their first byte would otherwise be above 0x7F (in which case a single 0x00 in front is required). Also note that inside transaction signatures, an extra hashtype byte follows the actual signature data.

RI

C/C++

  • https://github.com/bitcoin-core/secp256k1
  • by Peter Wuille
  • 又名 libsecp256k1

How bitcoin using secp256k1

  • https://github.com/bitcoin/bitcoin/blob/v0.15.1/src/wallet/rpcwallet.cpp#L163-L171
    • https://github.com/bitcoin/bitcoin/blob/v0.15.1/src/wallet/wallet.cpp#L3437 (pubkey from pool)
      • https://github.com/bitcoin/bitcoin/blob/v0.15.1/src/wallet/wallet.cpp#L125-L158 (how pubkey gen)
        • https://github.com/bitcoin/bitcoin/blob/v0.15.1/src/key.cpp#L152 (use secp256k1 to create pubkey)
    • https://github.com/bitcoin/bitcoin/blob/v0.15.1/src/pubkey.h#L144 (hash160)
    • https://github.com/bitcoin/bitcoin/blob/v0.15.1/src/base58.cpp#L197 ( CBitcoinAddress(keyID).ToString() -> base58check)
$ src/bitcoin-cli getnewaddress
1Fop9P6BvWX5PdYcnABur6vXYbRVK2zjXp
$ src/bitcoin-cli dumpprivkey 1Fop9P6BvWX5PdYcnABur6vXYbRVK2zjXp
L3o684tsf6E4ZKwHXWwLd3pzjRksG7e9eeknqQP8XBytjTv8utje
$ echo L3o684tsf6E4ZKwHXWwLd3pzjRksG7e9eeknqQP8XBytjTv8utje|bx wif-to-public|bx ec-to-address
1Fop9P6BvWX5PdYcnABur6vXYbRVK2zjXp

How ex using secp256k1

  • https://github.com/libbitcoin/secp256k1 (is fork of bitcoin-core/secp256k1)
    • https://github.com/libbitcoin/libbitcoin/blob/v3.3.0/src/math/elliptic_curve.cpp
    • https://github.com/libbitcoin/libbitcoin/blob/v3.3.0/src/math/elliptic_curve.cpp#L85
    • https://github.com/libbitcoin/libbitcoin/blob/v3.3.0/src/wallet/ec_private.cpp#L201
    • https://github.com/libbitcoin/libbitcoin-explorer/blob/v3.3.0/src/commands/ec-new.cpp#L53
$ echo 000000000000000000000000000000000000000000000000 |bx ec-new
f00ccc9dae46346963a579b2ffb3deb67a1cb0da158aef9c7b839ac05640d190
$ echo 000000000000000000000000000000000000000000000000 |bx ec-new |bx ec-to-public
03dc8335336fe1ea6936f2c13c5ac06b5ab585e5c72434f8bc74829349c9d14054
$ echo 000000000000000000000000000000000000000000000000 |bx ec-new |bx ec-to-public |bx ec-to-address
12KWaMA14HonuGKvEruKwe7rAFPbUzpwVM

$ echo 000000000000000000000000000000000000000000000000 |bx ec-new |bx ec-to-wif
L5GLUwKZA1VLu1u85n4ZqViWcDFrvh7nDzENesWwsk1Ed4wCHBXe
$ echo 000000000000000000000000000000000000000000000000 |bx ec-new |bx ec-to-wif |bx wif-to-ec
f00ccc9dae46346963a579b2ffb3deb67a1cb0da158aef9c7b839ac05640d190
$ echo 000000000000000000000000000000000000000000000000 |bx ec-new |bx ec-to-wif |bx wif-to-ec|bx ec-to-public
03dc8335336fe1ea6936f2c13c5ac06b5ab585e5c72434f8bc74829349c9d14054
$ echo 000000000000000000000000000000000000000000000000 |bx ec-new |bx ec-to-wif |bx wif-to-ec|bx ec-to-public|bx ec-to-address
12KWaMA14HonuGKvEruKwe7rAFPbUzpwVM

How picocoin works with secp256k1

  • picocoin is C light lib by Jeff Garzik ( Gavin Andresen的朋友,segwit2x的主要开发)
  • https://github.com/jgarzik/picocoin/blob/v0.5/lib/key.c#L57-L73

how rust-bitcoin works with libsecp256k1

  • https://github.com/apoelstra/rust-bitcoin/blob/master/src/util/address.rs#L55-L64
  • https://github.com/apoelstra/rust-secp256k1/blob/master/src/key.rs#L146-L160
  • https://github.com/apoelstra/rust-secp256k1 is a wrapper around libsecp256k1,

how bitcoinj works with libsecp256k1

  • Using JNI (which provided by libsecp256k1 officially)
    • https://github.com/bitcoin-core/secp256k1/tree/master/src/java/
  • https://github.com/bitcoinj/bitcoinj/blob/v0.14.5/core/src/main/java/org/bitcoin/NativeSecp256k1.java
  • Note: bitcoinj looks maintained by greenaddress

Python

  • https://github.com/vbuterin/pybitcointools By VB
>>> sha256('some big long brainwallet password')
'57c617d9b4e1f7af6ec97ca2ff57e94a28279a7eedd4d12a99fa11170e94f5a4'
>>> decoded_private_key = bitcoin.decode_privkey(sha256('some big long brainwallet password'), 'hex')
>>> public_key = bitcoin.fast_multiply(bitcoin.G, decoded_private_key)
>>> hex_encoded_public_key = bitcoin.encode_pubkey(public_key, 'hex')
>>> bitcoin.pubkey_to_address(public_key)
'1CQLd3bhw4EzaURHbKCwM5YZbUQfA4ReY6'
>>> (public_key_x, public_key_y) = public_key
>>> compressed_prefix = '02' if (public_key_y % 2) == 0 else '03'
>>> hex_compressed_public_key = compressed_prefix + bitcoin.encode(public_key_x, 16)
>>> bitcoin.pubkey_to_address(hex_compressed_public_key)
'1EHw4jytKnzMSX8szNrXJ9FQiahKYnuuji'
$ echo 57c617d9b4e1f7af6ec97ca2ff57e94a28279a7eedd4d12a99fa11170e94f5a4|bx ec-to-public|bx ec-to-address
1EHw4jytKnzMSX8szNrXJ9FQiahKYnuuji

Javascript

  • https://github.com/cryptocoinjs/secp256k1-node

Go

  • Package btcec implements elliptic curve cryptography needed for working with Bitcoin (secp256k1 only for now).
  • https://github.com/btcsuite/btcd/tree/master/btcec
    • https://github.com/btcsuite/btcd/blob/master/btcec/pubkey.go#L69-L122

How Ethereum works with secp256k1

  • Ethereum use the hybrid solution
    • 公钥生成使用标准go api (crypto/ecdsa)
      • https://github.com/ethereum/go-ethereum/blob/v1.7.2/accounts/keystore/key.go#L161-L167
    • 签名使用cgo来调用libsecp256k1的c代码 (性能考虑)
      • https://github.com/ethereum/go-ethereum/blob/v1.7.2/crypto/secp256k1/secp256.go#L68-L97
    • 同时集成了btcec包, 当使用non-cgo模式时候,则使用这种方式(https://github.com/ethereum/go-ethereum/pull/3680 non-cgo fallback implementation of secp256k1 operations. The fallback implementation is not used when cgo is available. )
      • https://github.com/ethereum/go-ethereum/blob/v1.7.2/crypto/signature_nocgo.go#L48-L72

C#

  • https://github.com/MetacoSA/NBitcoin/blob/v4.0.0.42/NBitcoin/Crypto/ECKey.cs#L98
  • https://github.com/MetacoSA/NBitcoin/blob/v4.0.0.42/NBitcoin/BouncyCastle/math/ec/custom/sec/SecP256K1Curve.cs

Object-C

  • https://github.com/oleganza/CoreBitcoin/blob/0.6.8.1/openssl/include/openssl/obj_mac.h#L384-L386
  • https://github.com/oleganza/CoreBitcoin/blob/0.6.8.1/CoreBitcoin/BTCKey.h
  • https://github.com/oleganza/CoreBitcoin/blob/0.6.8.1/CoreBitcoin/BTCKey.m
  • https://github.com/oleganza/CoreBitcoin/blob/0.6.8.1/CoreBitcoin/BTCCurvePoint.h
  • https://github.com/oleganza/CoreBitcoin/blob/0.6.8.1/CoreBitcoin/BTCCurvePoint.m

Reference

  • https://en.bitcoin.it/wiki/Secp256k1
  • https://bitcoin.stackexchange.com/a/21911
  • https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc
  • https://github.com/bitcoinbook/bitcoinbook/blob/develop/code/key-to-address-ecc-example.py

Prepare

  • https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

  • https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

  • https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Zk-SNARKs

  • https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

    • http://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
  • https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

ZK-STARKs

  • http://vitalik.ca/general/2017/11/09/starks_part_1.html
  • https://www.youtube.com/watch?v=HJ9K_o-RRSY
    • Transparent scalable computational integrity - Eli Ben Sasson, Silicon Valley ethereum meetup
    • Eli is one of the main minds behind zk-SNARKs; he presented on STARKS, which have many properties similar to SNARKs, but do not require the trusted setup.

Intro

Reference

  • CoinJoin (by Gregory Maxwell)
    • https://en.wikipedia.org/wiki/CoinJoin
    • https://bitcointalk.org/index.php?topic=279249.0
    • https://en.bitcoin.it/wiki/CoinJoin
  • DarkCoin->Dash
  • Tumblebit (by Ethan Heilman)
    • https://github.com/BUSEC/TumbleBit
    • https://eprint.iacr.org/2016/575.pdf
    • https://medium.com/@nopara73/tumblebit-vs-coinjoin-15e5a7d58e3
    • https://hackernoon.com/understanding-tumblebit-part-1-making-the-case-823d786113f3
  • elements projects' confidential-transactions
    • https://www.elementsproject.org/elements/confidential-transactions/investigation.html
    • https://www.elementsproject.org/elements/schnorr-signatures/

Intro

  • CryptoNote (Bytecoin (BCN) in July 2012)
  • ShadowCash (dead)
  • Monero(XMR)

screen shot 2017-11-12 at 6 24 28 pm

Bob decides to spend an output, which was sent to the one-time public key. He needs Extra (1), TxOutNumber (2), and his Account private key (3) to recover his one-time private key (4).

screen shot 2017-11-12 at 6 24 42 pm

When sending a transaction to Carol, Bob generates its Extra value by random (5). He uses Extra (6), TxOutNumber (7) and Carol's Account public key (8) to get her Output public key (9). In the input Bob hides the link to his output among the foreign keys (10). To prevent double-spending he also packs the Key image, derived from his One-time private key (11). Finally, Bob signs the transaction, using his One-time private key (12), all the public keys (13) and Key Image (14). He appends the resulting Ring Signature to the end of the transaction (15).

RingCT

  • Ring Confidential Transactions
    • https://lab.getmonero.org/pubs/MRL-0005.pdf
  • RingCT 2.0: A Compact Accumulator-Based (Linkable Ring Signature) Protocol for Blockchain Cryptocurrency Monero
    • https://eprint.iacr.org/2017/921.pdf

CryptoNote Currencies

  • https://cryptonote.org/coins/
  • Create your own Cryptocurrency Easiest way to launch a Coin in 10 minutes!
    • https://cryptonotestarter.org/index.html

References

  • https://cryptonote.org/inside.php
  • https://cryptonote.org/whitepaper.pdf
  • https://en.wikipedia.org/wiki/Ring_signature
  • https://bitcointalk.org/index.php?topic=583449.0%EF%BC%89%26%2365289%3B
  • https://github.com/cryptonotefoundation/cryptonote

Intro

  • SM2 -> ECC
  • SM3 -> Hash
  • SM4 -> EDS/AES

References

https://github.com/yeasy/fintech_talk/blob/master/20171206_SM2/content.md

Intro

lattice-based

NTRU Prime

  • https://ntruprime.cr.yp.to/index.html
  • https://github.com/companyzero/sntrup4591761 (go实现,by https://github.com/dajohi decred开发)
  • https://github.com/companyzero/zkc/pull/54
  • https://github.com/companyzero/zkc

Reading

Messaging

Node discovery

Gossip 协议

介绍

  • https://en.wikipedia.org/wiki/Gossip_protocol

规范

  • SWIM
    • https://www.cs.cornell.edu/~asdas/research/dsn02-swim.pdf

参考实现

mesh

  • https://github.com/weaveworks/mesh/blob/master/gossip.go

hyperledger

  • https://github.com/hyperledger/fabric/blob/release/gossip/gossip/gossip.go

Smudge

  • https://github.com/clockworksoul/smudge

Cassandra

  • https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/gms/Gossiper.java

参考

  • https://en.wikipedia.org/wiki/Distributed_hash_table
  • Profiling a million user dht
    • http://conferences.sigcomm.org/imc/2007/papers/imc150.pdf
  • https://bitcoin.stackexchange.com/questions/37366/why-doesnt-bitcoin-use-a-dht-for-choosing-peers
    • Bitcoin does not have any local data specific to a node, and every node needs to learn everything anyway. We have peer selection logic, but it optimizes for DoS protection robustness and propagation speed. What exactly would it use a DHT for? by Pieter Wuille
  • https://en.wikipedia.org/wiki/Kademlia
  • https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

Code

  • https://github.com/arvidn/libtorrent/tree/master/src/kademlia

Synchronization

Intro

NetMsgType

  • https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/src/protocol.cpp#L47-L74
Data Msg

screen shot 2017-11-05 at 4 00 56 pm

Control Msg

screen shot 2017-11-05 at 4 04 41 pm

Message Process

  • https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/src/net_processing.cpp#L1175

headers-first sync

  • https://bitcoin.org/en/glossary/headers-first-sync
  • https://bitcoin.org/en/developer-reference#headers
  • https://en.bitcoin.it/wiki/Protocol_documentation#Block_Headers
  • https://en.bitcoin.it/wiki/Protocol_documentation#headers
  • strCommand == NetMsgType::HEADERS https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/src/net_processing.cpp#L2238
  • https://bitcoin.org/en/developer-reference#block
  • https://en.bitcoin.it/wiki/Protocol_documentation#block
  • strCommand == NetMsgType::BLOCK https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/src/net_processing.cpp#L2387

References

  • https://github.com/bitcoin/bitcoin/blob/v0.15.0.1/src/net_processing.cpp#L2883,L2906
  • https://github.com/bitcoin/bitcoin/pull/4468/files
  • https://bitcoin.org/en/developer-reference#p2p-network
  • https://en.bitcoin.it/wiki/Protocol_documentation#Message_types
    • CN (https://zh-cn.bitcoin.it/wiki/%E5%8D%8F%E8%AE%AE%E8%AF%B4%E6%98%8E)

Intro

  • Atomic_cross-chain
  • HTLC(Hashed Timelocked Contracts)

References

  • https://en.bitcoin.it/wiki/Atomic_cross-chain_trading
  • https://z.cash/blog/htlc-bip.html
  • https://github.com/bitcoin/bips/blob/master/bip-0199.mediawiki

Interledger Protocol (ILP)

Intro

decentralized payment protocol screen shot 2017-10-28 at 1 44 12 pm

Crypto-Conditions

The crypto-conditions specification defines a set of encoding formats and data structures for conditions and fulfillments. A condition uniquely identifies a logical "boolean circuit" constructed from one or more logic gates, evaluated by either validating a cryptographic signature or verifying the preimage of a hash digest. A fulfillment is a data structure encoding one or more cryptographic signatures and hash digest preimages that define the structure of the circuit and provide inputs to the logic gates allowing for the result of the circuit to be evaluated.

screen shot 2017-10-31 at 3 38 09 pm

screen shot 2017-10-31 at 3 23 15 pm

  • https://tools.ietf.org/html/draft-thomas-crypto-conditions-02
  • https://docs.bigchaindb.com/projects/server/en/latest/data-models/inputs-outputs.html
  • https://github.com/go-interledger/cryptoconditions
  • https://github.com/bigchaindb/cryptoconditions
  • https://github.com/rfcs/crypto-conditions/

Comments

https://github.com/wanchain/crypto/blob/master/%E8%B7%A8%E9%93%BE%E6%8A%80%E6%9C%AF%E8%B0%83%E7%A0%94%E6%8A%A5%E5%91%8A.pdf

Interledger 是 Ripple 于 2015 年ᨀ出的跨链交易协议,简称 ILP。它的目标是作为所有账本的仲裁器,无论是分布式账本还是中心化账本,目前代码开发已经基本完全。Interledger了两种交易的方式,atomic mode 和 universal mode。在 atomic mode 下,节点先选定公证人(notaries),然后发送者将资金发送到可信第三方的账户(escrow),然后 connector 将资金发入接收者所在链的可信第三方账户,之后公证人获取到接收者的 commit 后,通过 PBFT 达成共识,通知两条链上的可信第三方,由两条链上的可信第三方再将资金分别转到connector 和接收者的账户;如果节点无法选定公证人,则进入 universal mode,在这一模式下,不再由公证人决定交易进行状态,而是假设参与者均为理性的,由利益驱使整个交易的完成。Interledger 的设计上有如下的问题:

  • 需要选取公证人,且公证人无 membership change,无 weighting
  • 资金的接收者必须在线才能完成交易
  • 需要可信第三方 escrow
  • 无跨链交易历史明细纪录

References

  • https://interledger.org/rfcs/0003-interledger-protocol/
  • https://www.youtube.com/watch?v=Dyi3RB50dDQ
  • https://www.youtube.com/watch?v=UdCxrqP6w3I

Video

Intro

Decentralized Identifiers (DIDs) are a new type of identifier intended for verifiable digital identity that is "self-sovereign", fully under the control of an entity and not dependent on a centralized registry, identity provider, or certificate authority.

DIDs resolve to DID Documents — simple documents that contain all the metadata needed to interact with the DID. Specifically, a DID Document typically contains at least three things.

  • The first is a set of mechanisms that may be used to authenticate as as a particular DID (e.g. public keys, pseudonymous biometric templates, etc.).
  • The second is a set of authorization information that outlines which entities may modify the DID Document.
  • The third is a set of service endpoints, which may be used to initiate trusted interactions with the entity. This document specifies a common data model, format, and operations that all DIDs support.

Decentralized Identifiers (DIDs) as personal trust anchors. Anyone can propose a DID method — ideally they leverage the power of blockchains, but a blockchain is not required. There are DID methods being proposed for public blockchains (Bitcoin, Blockstack, Ethereum), private blockchains (Sovrin/Indy), non-blockchain (IPFS), and even legacy web-of-trust identity systems (PGP).

Decentralized identifier (DID) is simply a new type of globally unique identifier with special features designed for blockchains. But at a deeper level, DIDs are actually the tip of the iceberg or the tip of the spear of an entirely new layer of decentralized digital identity and public key infrastructure (PKI) for the Internet. This decentralized public key infrastructure (DPKI) could have as much impact on global cybersecurity and cyber-privacy as the development of the SSL/TLS protocol for encrypted Web traffic (now the largest PKI in the world).

目标:cross-chain rooting, indexing, and resolution of decentralized identifiers and names.

References

  • https://w3c-ccg.github.io/did-spec/
  • http://www.weboftrust.info/papers.html
    • https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2016/blob/master/final-documents/hubs.pdf
  • https://github.com/WebOfTrustInfo/
    • https://github.com/WebOfTrustInfo/btcr-hackathon
  • http://identity.foundation/
  • https://github.com/decentralized-identity/
    • https://github.com/decentralized-identity/hubs
  • https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2017
    • https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2017/blob/master/topics-and-advance-readings/did-primer.md
    • https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2017/blob/master/topics-and-advance-readings/verifiable-claims-primer.md
    • https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2017/blob/master/topics-and-advance-readings/functional-identity-primer.md
    • https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2017/blob/master/topics-and-advance-readings/self-sovereign-identity-primer.md

0x Protocol

Intro

a protocol that facilitates low friction peer-to-peer exchange of ERC20 tokens on the Ethereum . screen shot 2017-10-28 at 2 52 39 pm

References

  • https://github.com/0xProject/whitepaper/raw/master/0x_white_paper.pdf
  • https://github.com/0xProject/wiki/blob/master/protocol/Message-Format.md
  • https://github.com/0xProject/wiki/blob/master/smart-contracts/Contract-Interactions.md
  • https://github.com/0xProject/wiki/blob/master/smart-contracts/Architecture.md

Polkadot

Cosmos

  • https://cosmos.network/whitepaper

Cosmos IBC

  • https://github.com/cosmos/ibc/blob/master/CosmosIBCSpecification.pdf
    • https://steemit.com/cn/@legendx/cosmos-1

Intro

  • settlement
  • clearinghouse
  • exchange data
  • Ethereum smart contracts
  • protocol tokens

References

  • https://cdn.omise.co/omg/whitepaper.pdf
    • https://cdn.omise.co/omg/CNwhitepaper.pdf

Intro

  • Market type
    • off-chain markets with single-price batches
    • off-chain brokers
    • on-chain markets
  • Oracle type
    • subcurrency voting oracles
    • betting oracles
    • public feeds.

Reference

  • https://github.com/zack-bitcoin/amoveo/blob/master/docs/progress_reports/october_2017.md
  • https://github.com/zack-bitcoin/amoveo/blob/master/docs/progress_reports/november_2017.md
  • https://github.com/zack-bitcoin/amoveo/blob/master/docs/design/state_channel_without_off_chain_market.md

Gnosis

Augur

Amoveo

Intro

  • Bitcoin integration
  • Verified contracts (F*)
  • Contract lifeCycle (Active Contract Set)
  • Multihash mining
  • Merklized Oracle

References

  • https://www.zenprotocol.com/files/multi_hash_mining.pdf
  • https://www.zenprotocol.com/files/zen_protocol_bitcoin_integration.pdf
  • https://www.zenprotocol.com/files/technical_paper.pdf
  • https://www.zenprotocol.com/files/zen_protocol_white_paper.pdf
  • https://github.com/zenprotocol
  • http://alpha.zenprotocol.com/Contract/Index/DbOcE1MstU26MJvFCkgLk_6ghiq0NUpucPP_i9oUaA01

Video

SmartContract

ETH

BaneEx smart-asset

  • https://github.com/BankEx/whitepaper/blob/master/bankex-whitepaper.pdf
  • https://github.com/BankEx/smart-asset-core/blob/dev/contracts/SmartAsset.sol
    • https://dev-web-prototype-bankex.azurewebsites.net/

trustlines.network

熟人借贷经济模式

IOU

‘I owe you’

  • https://github.com/trustlines-network/TLPR/blob/master/Trustlines_White_Paper_v3.md#ious-on-the-blockchain
  • https://github.com/trustlines-network/TLPR/blob/master/Trustlines_White_Paper_v3.md#credit-line

Fee & Loan

  • https://github.com/trustlines-network/TLPR/blob/master/Trustlines_White_Paper_v3.md#fees-1
  • https://github.com/trustlines-network/TLPR/blob/master/Trustlines_White_Paper_v3.md#loans

中文白皮书

https://mp.weixin.qq.com/s?__biz=MzI3OTYzOTU3NQ==&mid=2247485250&idx=2&sn=93eefc5b64791e8b780731b00984ad1b&chksm=eb45e43adc326d2ceec725154a4b1f77b21c0f11c9b3264736a693b768c42142de84612821ac&mpshare=1&scene=1&srcid=12196z27RQalxHRUwrU8nOXu&pass_ticket=pkSrVZFPaIM%2Fwwg%2Fbd9qRkyHRpBOYHgRepR0dsTnmSo%3D#rd

Reference

  • https://github.com/trustlines-network/relay/blob/master/relay/graph.py (dijkstra_path)
  • https://github.com/trustlines-network/contracts/blob/master/contracts/lib/Resolver.sol

参考文档

  • https://forum.qtum.org/topic/193/qtum%E6%98%9F%E7%81%AB%E7%BD%91%E7%BB%9C-sparknet-%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95%E5%8F%8A%E8%AF%B4%E6%98%8E
  • https://github.com/qtumproject/qtum/blob/testnet-1/doc/sparknet-guide.md
  • https://github.com/qtumproject/qtum/wiki/Qtum-Blockchain-Instruction
  • https://bodhiproject.github.io/wiki/deployment/
  • https://github.com/hayeah/qtum-dapp-counter#developing-the-dapp-ui

EVM对比 Qtum vs. Ethereum

  • Qtum的EVM来自Cpp Ethereum代码
  • Qtum基于UTXO模型,加入了账户抽象层(Account Abstraction Layer),用于将UTXO模型转换成可供EVM执行的账户模型。
  • Qtum对Bitcoin的Opcode进行扩展,添加了3个新的Opcode
    • OP_CREATE – 用于执行EVM智能合约的创建,把通过交易传输的字节代码存放到合约RLP数据库,并生成一个合约账户
    • OP_CALL – 用于传递调用智能合约所需要的相关数据(即EVM中的CALLERDATA)和地址信息,并执行合约中的代码内容。该操作符还可为智能合约发送资金。
    • OP_SPEND – 将当前合约的ID哈希值作为输入的交易HASH,或发送到合约的UTXO的交易HASH,然后使用OP_SPEND作为花费指令构建交易脚本。

Qtum Contract命令包括:

  • createcontract
  • callcontract ("query" mode, 所有的计算都是在链下(本地,local blockchain)进行,不需要消耗gas)
  • sendtocontract (“commit” mode, 所有的计算都是在链上进行的,并且所有的状态改变都会同步到链上。这个命令可以向合约发送代币,会消耗gas)
  • listcontracts

createcontract

$ ./src/qtum-cli -testnet help createcontract
createcontract "bytecode" (gaslimit gasprice "senderaddress" broadcast)
Create a contract with bytcode.

Arguments:
1. "bytecode"  (string, required) contract bytcode.
2. gasLimit  (numeric or string, optional) gasLimit, default: 2500000, max: 40000000
3. gasPrice  (numeric or string, optional) gasPrice QTUM price per gas unit, default: 0.0000004, min:0.0000004
4. "senderaddress" (string, optional) The quantum address that will be used to create the contract.
5. "broadcast" (bool, optional, default=true) Whether to broadcast the transaction or not.
6. "changeToSender" (bool, optional, default=true) Return the change to the sender.

Result:
[
  {
    "txid" : (string) The transaction id.
    "sender" : (string) QTUM address of the sender.
    "hash160" : (string) ripemd-160 hash of the sender.
    "address" : (string) expected contract address.
  }
]

Examples:
> qtum-cli createcontract "60606040525b33600060006101000a81548173ffffffffffffffffffffffffffffffffffffffff02191690836c010000000000000000000000009081020402179055506103786001600050819055505b600c80605b6000396
000f360606040526008565b600256"
> qtum-cli createcontract "60606040525b33600060006101000a81548173ffffffffffffffffffffffffffffffffffffffff02191690836c010000000000000000000000009081020402179055506103786001600050819055505b600c80605b6000396
000f360606040526008565b600256" 6000000 0.0000004 "QM72Sfpbz1BPpXFHz9m3CdqATR44Jvaydd" true

实现

https://github.com/qtumproject/qtum/blob/master/src/wallet/rpcwallet.cpp

    if(fBroadcast){
        CValidationState state;
        if (!pwalletMain->CommitTransaction(wtx, reservekey, g_connman.get(), state))
            throw JSONRPCError(RPC_WALLET_ERROR, "Error: The transaction was rejected! This might happen if some of the coins in your wallet were already spent, such as if you used a copy of the wallet and coins were spent in the copy but not marked as spent here.");

        std::string txId=wtx.GetHash().GetHex();
        result.push_back(Pair("txid", txId));

        CBitcoinAddress txSenderAdress(txSenderDest);
        CKeyID keyid;
        txSenderAdress.GetKeyID(keyid);

        result.push_back(Pair("sender", txSenderAdress.ToString()));
        result.push_back(Pair("hash160", HexStr(valtype(keyid.begin(),keyid.end()))));

        std::vector<unsigned char> SHA256TxVout(32);
        vector<unsigned char> contractAddress(20);
        vector<unsigned char> txIdAndVout(wtx.GetHash().begin(), wtx.GetHash().end());
        uint32_t voutNumber=0;
        BOOST_FOREACH(const CTxOut& txout, wtx.tx->vout) {
            if(txout.scriptPubKey.HasOpCreate()){
                std::vector<unsigned char> voutNumberChrs;
                if (voutNumberChrs.size() < sizeof(voutNumber))voutNumberChrs.resize(sizeof(voutNumber));
                std::memcpy(voutNumberChrs.data(), &voutNumber, sizeof(voutNumber));
                txIdAndVout.insert(txIdAndVout.end(),voutNumberChrs.begin(),voutNumberChrs.end());
                break;
            }
            voutNumber++;
        }
        CSHA256().Write(txIdAndVout.data(), txIdAndVout.size()).Finalize(SHA256TxVout.data());
        CRIPEMD160().Write(SHA256TxVout.data(), SHA256TxVout.size()).Finalize(contractAddress.data());
        result.push_back(Pair("address", HexStr(contractAddress)));
    }else{
        string strHex = EncodeHexTx(*wtx.tx, RPCSerializationFlags());
        result.push_back(Pair("raw transaction", strHex));
    }
    return result;

callcontract

$ ./src/qtum-cli -testnet help callcontract
callcontract "address" "data" ( address )

Argument:
1. "address"          (string, required) The account address
2. "data"             (string, required) The data hex string
3. address              (string, optional) The sender address hex string
4. gasLimit             (string, optional) The gas limit for executing the contract

sendtocontract

$ ./src/qtum-cli -testnet help sendtocontract
sendtocontract "contractaddress" "data" (amount gaslimit gasprice senderaddress broadcast)
Send funds and data to a contract.

Arguments:
1. "contractaddress" (string, required) The contract address that will receive the funds and data.
2. "datahex"  (string, required) data to send.
3. "amount"      (numeric or string, optional) The amount in QTUM to send. eg 0.1, default: 0
4. gasLimit  (numeric or string, optional) gasLimit, default: 250000, max: 40000000
5. gasPrice  (numeric or string, optional) gasPrice Qtum price per gas unit, default: 0.0000004, min:0.0000004
6. "senderaddress" (string, optional) The quantum address that will be used as sender.
7. "broadcast" (bool, optional, default=true) Whether to broadcast the transaction or not.
8. "changeToSender" (bool, optional, default=true) Return the change to the sender.

Result:
[
  {
    "txid" : (string) The transaction id.
    "sender" : (string) QTUM address of the sender.
    "hash160" : (string) ripemd-160 hash of the sender.
  }
]

Examples:
> qtum-cli sendtocontract "c6ca2697719d00446d4ea51f6fac8fd1e9310214" "54f6127f"
> qtum-cli sendtocontract "c6ca2697719d00446d4ea51f6fac8fd1e9310214" "54f6127f" 12.0015 6000000 0.0000004 "QM72Sfpbz1BPpXFHz9m3CdqATR44Jvaydd"

以太的创建合约与调用

创建合约

  • https://github.com/ethereum/wiki/wiki/JavaScript-API#web3ethsendtransaction
// compiled solidity source code using https://chriseth.github.io/cpp-ethereum/
var code = "603d80600c6000396000f3007c01000000000000000000000000000000000000000000000000000000006000350463c6888fa18114602d57005b6007600435028060005260206000f3";

web3.eth.sendTransaction({data: code}, function(err, transactionHash) {
  if (!err)
    console.log(transactionHash); // "0x7f9fade1c0d57a7af66ab4ead7c2eb7b11a91385"
});
  • from: String - The address for the sending account. Uses the web3.eth.defaultAccount property, if not specified.
  • to: String - (optional) The destination address of the message, left undefined for a contract-creation transaction.
  • value: Number|String|BigNumber - (optional) The value transferred for the transaction in Wei, also the endowment if it's a contract-creation transaction.
  • gas: Number|String|BigNumber - (optional, default: To-Be-Determined) The amount of gas to use for the transaction (unused gas is refunded).
  • gasPrice: Number|String|BigNumber - (optional, default: To-Be-Determined) The price of gas for this transaction in wei, defaults to the mean network gas price.
  • data: String - (optional) Either a byte string containing the associated data of the message, or in the case of a contract-creation transaction, the initialisation code.
  • nonce: Number - (optional) Integer of a nonce. This allows to overwrite your own pending transactions that use the same nonce.

https://github.com/ethereum/go-ethereum/blob/v1.7.3/internal/ethapi/api.go#L339,L371

// SendTransaction will create a transaction from the given arguments and
// tries to sign it with the key associated with args.To. If the given passwd isn't
// able to decrypt the key it fails.
func (s *PrivateAccountAPI) SendTransaction(ctx context.Context, args SendTxArgs, passwd string) (common.Hash, error) {
    // Look up the wallet containing the requested signer
    account := accounts.Account{Address: args.From}

    wallet, err := s.am.Find(account)
    if err != nil {
        return common.Hash{}, err
    }

    if args.Nonce == nil {
        // Hold the addresse's mutex around signing to prevent concurrent assignment of
        // the same nonce to multiple accounts.
        s.nonceLock.LockAddr(args.From)
        defer s.nonceLock.UnlockAddr(args.From)
    }

    // Set some sanity defaults and terminate on failure
    if err := args.setDefaults(ctx, s.b); err != nil {
        return common.Hash{}, err
    }
    // Assemble the transaction and sign with the wallet
    tx := args.toTransaction()

    var chainID *big.Int
    if config := s.b.ChainConfig(); config.IsEIP155(s.b.CurrentBlock().Number()) {
        chainID = config.ChainId
    }
    signed, err := wallet.SignTxWithPassphrase(account, passwd, tx, chainID)
    if err != nil {
        return common.Hash{}, err
    }
    return submitTransaction(ctx, s.b, signed)
}
...
// submitTransaction is a helper function that submits tx to txPool and logs a message.
func submitTransaction(ctx context.Context, b Backend, tx *types.Transaction) (common.Hash, error) {
    if err := b.SendTx(ctx, tx); err != nil {
        return common.Hash{}, err
    }
    if tx.To() == nil { //如果目标地址为空, 则记录该TX为contract创建
        signer := types.MakeSigner(b.ChainConfig(), b.CurrentBlock().Number())
        from, err := types.Sender(signer, tx)
        if err != nil {
            return common.Hash{}, err
        }
        addr := crypto.CreateAddress(from, tx.Nonce()) 
        log.Info("Submitted contract creation", "fullhash", tx.Hash().Hex(), "contract", addr.Hex())
    } else {
        log.Info("Submitted transaction", "fullhash", tx.Hash().Hex(), "recipient", tx.To())
    }
    return tx.Hash(), nil
}

合约地址的生成

// Creates an ethereum address given the bytes and the nonce
func CreateAddress(b common.Address, nonce uint64) common.Address {
    data, _ := rlp.EncodeToBytes([]interface{}{b, nonce})
    return common.BytesToAddress(Keccak256(data)[12:])
}
def mk_contract_address(sender, nonce):
    return sha3(rlp.encode([normalize_address(sender), nonce]))[12:]

读取数据(非修改状态)

Call is to be used only when the request does not modify the state of the blockchain (typically only reading fields or calling constant marked functions.

  • Creating contract instance: asynchronous call (using sendTransaction). Completion is managed through the callback, called once with the Tx hash and a second time with the contract address.
  • Reading contract data: synchronous call to the local node via the call methodology.
  • Updating data: asynchronous call (using sendTransaction) with methods that do not return values. Call returns synchronously (or eventually async.) the Tx hash that can then be monitored for completion via the getTransactionReceipt (using the eth.filter('latest') that tells when the next block has been mined)
  • Receiving info asynchronously: Use of event in the contract. Monitor the reception via eth.filter( options, callback ).
  • Catching up with events after a disconnected period: use eth.filter({fromBlock: xyz, toBlock: eth.currentBlock, ...}).get()