aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJeffrey Wilcke <jeffrey@ethereum.org>2017-02-02 05:36:51 +0800
committerJeffrey Wilcke <jeffrey@ethereum.org>2017-05-18 15:05:58 +0800
commit10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9 (patch)
tree170eb09bf51c802894d9335570d7319a2f86ef15
parenta2f23ca9b181fa4409fdee3076316f3127038b9b (diff)
downloaddexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.tar
dexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.tar.gz
dexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.tar.bz2
dexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.tar.lz
dexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.tar.xz
dexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.tar.zst
dexon-10a57fc3d45cbc59d6c8eeb0f7f2b93a71e8f4c9.zip
consensus, core/*, params: metropolis preparation refactor
This commit is a preparation for the upcoming metropolis hardfork. It prepares the state, core and vm packages such that integration with metropolis becomes less of a hassle. * Difficulty calculation requires header instead of individual parameters * statedb.StartRecord renamed to statedb.Prepare and added Finalise method required by metropolis, which removes unwanted accounts from the state (i.e. selfdestruct) * State keeps record of destructed objects (in addition to dirty objects) * core/vm pre-compiles may now return errors * core/vm pre-compiles gas check now take the full byte slice as argument instead of just the size * core/vm now keeps several hard-fork instruction tables instead of a single instruction table and removes the need for hard-fork checks in the instructions * core/vm contains a empty restruction function which is added in preparation of metropolis write-only mode operations * Adds the bn256 curve * Adds and sets the metropolis chain config block parameters (2^64-1)
-rw-r--r--consensus/ethash/consensus.go46
-rw-r--r--consensus/ethash/consensus_test.go7
-rw-r--r--core/chain_makers.go22
-rw-r--r--core/state/statedb.go91
-rw-r--r--core/state_processor.go5
-rw-r--r--core/types/transaction_signing.go18
-rw-r--r--core/vm/contracts.go49
-rw-r--r--core/vm/contracts_test.go1
-rw-r--r--core/vm/evm.go49
-rw-r--r--core/vm/instructions.go17
-rw-r--r--core/vm/interpreter.go80
-rw-r--r--core/vm/jump_table.go33
-rw-r--r--core/vm/memory.go1
-rw-r--r--crypto/bn256/bn256.go428
-rw-r--r--crypto/bn256/bn256_test.go304
-rw-r--r--crypto/bn256/constants.go44
-rw-r--r--crypto/bn256/curve.go278
-rw-r--r--crypto/bn256/example_test.go43
-rw-r--r--crypto/bn256/gfp12.go200
-rw-r--r--crypto/bn256/gfp2.go227
-rw-r--r--crypto/bn256/gfp6.go296
-rw-r--r--crypto/bn256/main_test.go71
-rw-r--r--crypto/bn256/optate.go398
-rw-r--r--crypto/bn256/twist.go249
-rw-r--r--internal/ethapi/tracer_test.go2
-rw-r--r--miner/worker.go2
-rw-r--r--params/config.go79
-rw-r--r--params/util.go8
28 files changed, 2865 insertions, 183 deletions
diff --git a/consensus/ethash/consensus.go b/consensus/ethash/consensus.go
index 2930032e5..d02542224 100644
--- a/consensus/ethash/consensus.go
+++ b/consensus/ethash/consensus.go
@@ -239,7 +239,7 @@ func (ethash *Ethash) verifyHeader(chain consensus.ChainReader, header, parent *
return errZeroBlockTime
}
// Verify the block's difficulty based in it's timestamp and parent's difficulty
- expected := CalcDifficulty(chain.Config(), header.Time.Uint64(), parent.Time.Uint64(), parent.Number, parent.Difficulty)
+ expected := CalcDifficulty(chain.Config(), header.Time.Uint64(), parent)
if expected.Cmp(header.Difficulty) != 0 {
return fmt.Errorf("invalid difficulty: have %v, want %v", header.Difficulty, expected)
}
@@ -283,16 +283,19 @@ func (ethash *Ethash) verifyHeader(chain consensus.ChainReader, header, parent *
return nil
}
-// CalcDifficulty is the difficulty adjustment algorithm. It returns the difficulty
-// that a new block should have when created at time given the parent block's time
-// and difficulty.
+// CalcDifficulty is the difficulty adjustment algorithm. It returns
+// the difficulty that a new block should have when created at time
+// given the parent block's time and difficulty.
//
// TODO (karalabe): Move the chain maker into this package and make this private!
-func CalcDifficulty(config *params.ChainConfig, time, parentTime uint64, parentNumber, parentDiff *big.Int) *big.Int {
- if config.IsHomestead(new(big.Int).Add(parentNumber, common.Big1)) {
- return calcDifficultyHomestead(time, parentTime, parentNumber, parentDiff)
+func CalcDifficulty(config *params.ChainConfig, time uint64, parent *types.Header) *big.Int {
+ next := new(big.Int).Add(parent.Number, common.Big1)
+ switch {
+ case config.IsHomestead(next):
+ return calcDifficultyHomestead(time, parent)
+ default:
+ return calcDifficultyFrontier(time, parent)
}
- return calcDifficultyFrontier(time, parentTime, parentNumber, parentDiff)
}
// Some weird constants to avoid constant memory allocs for them.
@@ -305,15 +308,15 @@ var (
// calcDifficultyHomestead is the difficulty adjustment algorithm. It returns
// the difficulty that a new block should have when created at time given the
// parent block's time and difficulty. The calculation uses the Homestead rules.
-func calcDifficultyHomestead(time, parentTime uint64, parentNumber, parentDiff *big.Int) *big.Int {
+func calcDifficultyHomestead(time uint64, parent *types.Header) *big.Int {
// https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.mediawiki
// algorithm:
// diff = (parent_diff +
// (parent_diff / 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99))
// ) + 2^(periodCount - 2)
- bigTime := new(big.Int).SetUint64(time)
- bigParentTime := new(big.Int).SetUint64(parentTime)
+ bigTime := new(big.Int).Set(parent.Time)
+ bigParentTime := new(big.Int).Set(parent.Time)
// holds intermediate values to make the algo easier to read & audit
x := new(big.Int)
@@ -329,16 +332,16 @@ func calcDifficultyHomestead(time, parentTime uint64, parentNumber, parentDiff *
x.Set(bigMinus99)
}
// (parent_diff + parent_diff // 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99))
- y.Div(parentDiff, params.DifficultyBoundDivisor)
+ y.Div(parent.Difficulty, params.DifficultyBoundDivisor)
x.Mul(y, x)
- x.Add(parentDiff, x)
+ x.Add(parent.Difficulty, x)
// minimum difficulty can ever be (before exponential factor)
if x.Cmp(params.MinimumDifficulty) < 0 {
x.Set(params.MinimumDifficulty)
}
// for the exponential factor
- periodCount := new(big.Int).Add(parentNumber, common.Big1)
+ periodCount := new(big.Int).Add(parent.Number, common.Big1)
periodCount.Div(periodCount, expDiffPeriod)
// the exponential factor, commonly referred to as "the bomb"
@@ -354,25 +357,25 @@ func calcDifficultyHomestead(time, parentTime uint64, parentNumber, parentDiff *
// calcDifficultyFrontier is the difficulty adjustment algorithm. It returns the
// difficulty that a new block should have when created at time given the parent
// block's time and difficulty. The calculation uses the Frontier rules.
-func calcDifficultyFrontier(time, parentTime uint64, parentNumber, parentDiff *big.Int) *big.Int {
+func calcDifficultyFrontier(time uint64, parent *types.Header) *big.Int {
diff := new(big.Int)
- adjust := new(big.Int).Div(parentDiff, params.DifficultyBoundDivisor)
+ adjust := new(big.Int).Div(parent.Difficulty, params.DifficultyBoundDivisor)
bigTime := new(big.Int)
bigParentTime := new(big.Int)
bigTime.SetUint64(time)
- bigParentTime.SetUint64(parentTime)
+ bigParentTime.Set(parent.Time)
if bigTime.Sub(bigTime, bigParentTime).Cmp(params.DurationLimit) < 0 {
- diff.Add(parentDiff, adjust)
+ diff.Add(parent.Difficulty, adjust)
} else {
- diff.Sub(parentDiff, adjust)
+ diff.Sub(parent.Difficulty, adjust)
}
if diff.Cmp(params.MinimumDifficulty) < 0 {
diff.Set(params.MinimumDifficulty)
}
- periodCount := new(big.Int).Add(parentNumber, common.Big1)
+ periodCount := new(big.Int).Add(parent.Number, common.Big1)
periodCount.Div(periodCount, expDiffPeriod)
if periodCount.Cmp(common.Big1) > 0 {
// diff = diff + 2^(periodCount - 2)
@@ -434,8 +437,7 @@ func (ethash *Ethash) Prepare(chain consensus.ChainReader, header *types.Header)
if parent == nil {
return consensus.ErrUnknownAncestor
}
- header.Difficulty = CalcDifficulty(chain.Config(), header.Time.Uint64(),
- parent.Time.Uint64(), parent.Number, parent.Difficulty)
+ header.Difficulty = CalcDifficulty(chain.Config(), header.Time.Uint64(), parent)
return nil
}
diff --git a/consensus/ethash/consensus_test.go b/consensus/ethash/consensus_test.go
index 683c10be4..78464bd22 100644
--- a/consensus/ethash/consensus_test.go
+++ b/consensus/ethash/consensus_test.go
@@ -23,6 +23,7 @@ import (
"testing"
"github.com/ethereum/go-ethereum/common/math"
+ "github.com/ethereum/go-ethereum/core/types"
"github.com/ethereum/go-ethereum/params"
)
@@ -71,7 +72,11 @@ func TestCalcDifficulty(t *testing.T) {
config := &params.ChainConfig{HomesteadBlock: big.NewInt(1150000)}
for name, test := range tests {
number := new(big.Int).Sub(test.CurrentBlocknumber, big.NewInt(1))
- diff := CalcDifficulty(config, test.CurrentTimestamp, test.ParentTimestamp, number, test.ParentDifficulty)
+ diff := CalcDifficulty(config, test.CurrentTimestamp, &types.Header{
+ Number: number,
+ Time: test.ParentTimestamp,
+ Difficulty: test.ParentDifficulty,
+ })
if diff.Cmp(test.CurrentDifficulty) != 0 {
t.Error(name, "failed. Expected", test.CurrentDifficulty, "and calculated", diff)
}
diff --git a/core/chain_makers.go b/core/chain_makers.go
index f34279ba0..967744282 100644
--- a/core/chain_makers.go
+++ b/core/chain_makers.go
@@ -84,7 +84,7 @@ func (b *BlockGen) AddTx(tx *types.Transaction) {
if b.gasPool == nil {
b.SetCoinbase(common.Address{})
}
- b.statedb.StartRecord(tx.Hash(), common.Hash{}, len(b.txs))
+ b.statedb.Prepare(tx.Hash(), common.Hash{}, len(b.txs))
receipt, _, err := ApplyTransaction(b.config, nil, &b.header.Coinbase, b.gasPool, b.statedb, b.header, tx, b.header.GasUsed, vm.Config{})
if err != nil {
panic(err)
@@ -142,7 +142,7 @@ func (b *BlockGen) OffsetTime(seconds int64) {
if b.header.Time.Cmp(b.parent.Header().Time) <= 0 {
panic("block time out of range")
}
- b.header.Difficulty = ethash.CalcDifficulty(b.config, b.header.Time.Uint64(), b.parent.Time().Uint64(), b.parent.Number(), b.parent.Difficulty())
+ b.header.Difficulty = ethash.CalcDifficulty(b.config, b.header.Time.Uint64(), b.parent.Header())
}
// GenerateChain creates a chain of n blocks. The first block's
@@ -209,15 +209,23 @@ func makeHeader(config *params.ChainConfig, parent *types.Block, state *state.St
} else {
time = new(big.Int).Add(parent.Time(), big.NewInt(10)) // block time is fixed at 10 seconds
}
+ parentHeader := parent.Header()
+ // adjust the parent time
+ parentHeader.Time = new(big.Int).Sub(time, big.NewInt(10))
+
return &types.Header{
Root: state.IntermediateRoot(config.IsEIP158(parent.Number())),
ParentHash: parent.Hash(),
Coinbase: parent.Coinbase(),
- Difficulty: ethash.CalcDifficulty(config, time.Uint64(), new(big.Int).Sub(time, big.NewInt(10)).Uint64(), parent.Number(), parent.Difficulty()),
- GasLimit: CalcGasLimit(parent),
- GasUsed: new(big.Int),
- Number: new(big.Int).Add(parent.Number(), common.Big1),
- Time: time,
+ Difficulty: ethash.CalcDifficulty(config, time.Uint64(), &types.Header{
+ Number: parent.Number(),
+ Time: new(big.Int).Sub(time, big.NewInt(10)),
+ Difficulty: parent.Difficulty(),
+ }),
+ GasLimit: CalcGasLimit(parent),
+ GasUsed: new(big.Int),
+ Number: new(big.Int).Add(parent.Number(), common.Big1),
+ Time: time,
}
}
diff --git a/core/state/statedb.go b/core/state/statedb.go
index 3b753a2e6..8e4ba21c0 100644
--- a/core/state/statedb.go
+++ b/core/state/statedb.go
@@ -62,8 +62,9 @@ type StateDB struct {
codeSizeCache *lru.Cache
// This map holds 'live' objects, which will get modified while processing a state transition.
- stateObjects map[common.Address]*stateObject
- stateObjectsDirty map[common.Address]struct{}
+ stateObjects map[common.Address]*stateObject
+ stateObjectsDirty map[common.Address]struct{}
+ stateObjectsDestructed map[common.Address]struct{}
// The refund counter, also used by state transitioning.
refund *big.Int
@@ -92,14 +93,15 @@ func New(root common.Hash, db ethdb.Database) (*StateDB, error) {
}
csc, _ := lru.New(codeSizeCacheSize)
return &StateDB{
- db: db,
- trie: tr,
- codeSizeCache: csc,
- stateObjects: make(map[common.Address]*stateObject),
- stateObjectsDirty: make(map[common.Address]struct{}),
- refund: new(big.Int),
- logs: make(map[common.Hash][]*types.Log),
- preimages: make(map[common.Hash][]byte),
+ db: db,
+ trie: tr,
+ codeSizeCache: csc,
+ stateObjects: make(map[common.Address]*stateObject),
+ stateObjectsDirty: make(map[common.Address]struct{}),
+ stateObjectsDestructed: make(map[common.Address]struct{}),
+ refund: new(big.Int),
+ logs: make(map[common.Hash][]*types.Log),
+ preimages: make(map[common.Hash][]byte),
}, nil
}
@@ -114,14 +116,15 @@ func (self *StateDB) New(root common.Hash) (*StateDB, error) {
return nil, err
}
return &StateDB{
- db: self.db,
- trie: tr,
- codeSizeCache: self.codeSizeCache,
- stateObjects: make(map[common.Address]*stateObject),
- stateObjectsDirty: make(map[common.Address]struct{}),
- refund: new(big.Int),
- logs: make(map[common.Hash][]*types.Log),
- preimages: make(map[common.Hash][]byte),
+ db: self.db,
+ trie: tr,
+ codeSizeCache: self.codeSizeCache,
+ stateObjects: make(map[common.Address]*stateObject),
+ stateObjectsDirty: make(map[common.Address]struct{}),
+ stateObjectsDestructed: make(map[common.Address]struct{}),
+ refund: new(big.Int),
+ logs: make(map[common.Hash][]*types.Log),
+ preimages: make(map[common.Hash][]byte),
}, nil
}
@@ -138,6 +141,7 @@ func (self *StateDB) Reset(root common.Hash) error {
self.trie = tr
self.stateObjects = make(map[common.Address]*stateObject)
self.stateObjectsDirty = make(map[common.Address]struct{})
+ self.stateObjectsDestructed = make(map[common.Address]struct{})
self.thash = common.Hash{}
self.bhash = common.Hash{}
self.txIndex = 0
@@ -173,12 +177,6 @@ func (self *StateDB) pushTrie(t *trie.SecureTrie) {
}
}
-func (self *StateDB) StartRecord(thash, bhash common.Hash, ti int) {
- self.thash = thash
- self.bhash = bhash
- self.txIndex = ti
-}
-
func (self *StateDB) AddLog(log *types.Log) {
self.journal = append(self.journal, addLogChange{txhash: self.thash})
@@ -510,21 +508,25 @@ func (self *StateDB) Copy() *StateDB {
// Copy all the basic fields, initialize the memory ones
state := &StateDB{
- db: self.db,
- trie: self.trie,
- pastTries: self.pastTries,
- codeSizeCache: self.codeSizeCache,
- stateObjects: make(map[common.Address]*stateObject, len(self.stateObjectsDirty)),
- stateObjectsDirty: make(map[common.Address]struct{}, len(self.stateObjectsDirty)),
- refund: new(big.Int).Set(self.refund),
- logs: make(map[common.Hash][]*types.Log, len(self.logs)),
- logSize: self.logSize,
- preimages: make(map[common.Hash][]byte),
+ db: self.db,
+ trie: self.trie,
+ pastTries: self.pastTries,
+ codeSizeCache: self.codeSizeCache,
+ stateObjects: make(map[common.Address]*stateObject, len(self.stateObjectsDirty)),
+ stateObjectsDirty: make(map[common.Address]struct{}, len(self.stateObjectsDirty)),
+ stateObjectsDestructed: make(map[common.Address]struct{}, len(self.stateObjectsDestructed)),
+ refund: new(big.Int).Set(self.refund),
+ logs: make(map[common.Hash][]*types.Log, len(self.logs)),
+ logSize: self.logSize,
+ preimages: make(map[common.Hash][]byte),
}
// Copy the dirty states, logs, and preimages
for addr := range self.stateObjectsDirty {
state.stateObjects[addr] = self.stateObjects[addr].deepCopy(state, state.MarkStateObjectDirty)
state.stateObjectsDirty[addr] = struct{}{}
+ if self.stateObjects[addr].suicided {
+ state.stateObjectsDestructed[addr] = struct{}{}
+ }
}
for hash, logs := range self.logs {
state.logs[hash] = make([]*types.Log, len(logs))
@@ -590,6 +592,27 @@ func (s *StateDB) IntermediateRoot(deleteEmptyObjects bool) common.Hash {
return s.trie.Hash()
}
+// Prepare sets the current transaction hash and index and block hash which is
+// used when the EVM emits new state logs.
+func (self *StateDB) Prepare(thash, bhash common.Hash, ti int) {
+ self.thash = thash
+ self.bhash = bhash
+ self.txIndex = ti
+}
+
+// Finalise finalises the state by removing the self destructed objects
+// in the current stateObjectsDestructed buffer and clears the journal
+// as well as the refunds.
+//
+// Please note that Finalise is used by EIP#98 and is used instead of
+// IntermediateRoot.
+func (s *StateDB) Finalise() {
+ for addr := range s.stateObjectsDestructed {
+ s.deleteStateObject(s.stateObjects[addr])
+ }
+ s.clearJournalAndRefund()
+}
+
// DeleteSuicides flags the suicided objects for deletion so that it
// won't be referenced again when called / queried up on.
//
diff --git a/core/state_processor.go b/core/state_processor.go
index 4fc2f1eae..90f5a4f60 100644
--- a/core/state_processor.go
+++ b/core/state_processor.go
@@ -69,7 +69,7 @@ func (p *StateProcessor) Process(block *types.Block, statedb *state.StateDB, cfg
}
// Iterate over and process the individual transactions
for i, tx := range block.Transactions() {
- statedb.StartRecord(tx.Hash(), block.Hash(), i)
+ statedb.Prepare(tx.Hash(), block.Hash(), i)
receipt, _, err := ApplyTransaction(p.config, p.bc, nil, gp, statedb, header, tx, totalUsedGas, cfg)
if err != nil {
return nil, nil, nil, err
@@ -107,7 +107,8 @@ func ApplyTransaction(config *params.ChainConfig, bc *BlockChain, author *common
usedGas.Add(usedGas, gas)
// Create a new receipt for the transaction, storing the intermediate root and gas used by the tx
// based on the eip phase, we're passing wether the root touch-delete accounts.
- receipt := types.NewReceipt(statedb.IntermediateRoot(config.IsEIP158(header.Number)).Bytes(), usedGas)
+ root := statedb.IntermediateRoot(config.IsEIP158(header.Number))
+ receipt := types.NewReceipt(root.Bytes(), usedGas)
receipt.TxHash = tx.Hash()
receipt.GasUsed = new(big.Int).Set(gas)
// if the transaction created a contract, store the creation address in the receipt.
diff --git a/core/types/transaction_signing.go b/core/types/transaction_signing.go
index b4bab0aad..e50b656b3 100644
--- a/core/types/transaction_signing.go
+++ b/core/types/transaction_signing.go
@@ -27,7 +27,12 @@ import (
"github.com/ethereum/go-ethereum/params"
)
-var ErrInvalidChainId = errors.New("invalid chaid id for signer")
+var (
+ ErrInvalidChainId = errors.New("invalid chaid id for signer")
+
+ errAbstractSigner = errors.New("abstract signer")
+ abstractSignerAddress = common.HexToAddress("ffffffffffffffffffffffffffffffffffffff")
+)
// sigCache is used to cache the derived sender and contains
// the signer used to derive it.
@@ -103,6 +108,17 @@ type Signer interface {
Equal(Signer) bool
}
+/*
+// WithSignature returns a new transaction with the given signature. This signature
+// needs to be in the [R || S || V] format where V is 0 or 1.
+func (s EIP86Signer) WithSignature(tx *Transaction, sig []byte) (*Transaction, error) {
+}
+
+// Hash returns the hash to be signed by the sender.
+// It does not uniquely identify the transaction.
+func (s EIP86Signer) Hash(tx *Transaction) common.Hash {}
+*/
+
// EIP155Transaction implements TransactionInterface using the
// EIP155 rules
type EIP155Signer struct {
diff --git a/core/vm/contracts.go b/core/vm/contracts.go
index e87640d02..90b2f913e 100644
--- a/core/vm/contracts.go
+++ b/core/vm/contracts.go
@@ -18,6 +18,7 @@ package vm
import (
"crypto/sha256"
+ "errors"
"math/big"
"github.com/ethereum/go-ethereum/common"
@@ -27,15 +28,17 @@ import (
"golang.org/x/crypto/ripemd160"
)
+var errBadPrecompileInput = errors.New("bad pre compile input")
+
// Precompiled contract is the basic interface for native Go contracts. The implementation
// requires a deterministic gas count based on the input size of the Run method of the
// contract.
type PrecompiledContract interface {
- RequiredGas(inputSize int) uint64 // RequiredPrice calculates the contract gas use
- Run(input []byte) []byte // Run runs the precompiled contract
+ RequiredGas(input []byte) uint64 // RequiredPrice calculates the contract gas use
+ Run(input []byte) ([]byte, error) // Run runs the precompiled contract
}
-// Precompiled contains the default set of ethereum contracts
+// PrecompiledContracts contains the default set of ethereum contracts
var PrecompiledContracts = map[common.Address]PrecompiledContract{
common.BytesToAddress([]byte{1}): &ecrecover{},
common.BytesToAddress([]byte{2}): &sha256hash{},
@@ -45,11 +48,9 @@ var PrecompiledContracts = map[common.Address]PrecompiledContract{
// RunPrecompile runs and evaluate the output of a precompiled contract defined in contracts.go
func RunPrecompiledContract(p PrecompiledContract, input []byte, contract *Contract) (ret []byte, err error) {
- gas := p.RequiredGas(len(input))
+ gas := p.RequiredGas(input)
if contract.UseGas(gas) {
- ret = p.Run(input)
-
- return ret, nil
+ return p.Run(input)
} else {
return nil, ErrOutOfGas
}
@@ -58,11 +59,11 @@ func RunPrecompiledContract(p PrecompiledContract, input []byte, contract *Contr
// ECRECOVER implemented as a native contract
type ecrecover struct{}
-func (c *ecrecover) RequiredGas(inputSize int) uint64 {
+func (c *ecrecover) RequiredGas(input []byte) uint64 {
return params.EcrecoverGas
}
-func (c *ecrecover) Run(in []byte) []byte {
+func (c *ecrecover) Run(in []byte) ([]byte, error) {
const ecRecoverInputLength = 128
in = common.RightPadBytes(in, ecRecoverInputLength)
@@ -76,18 +77,18 @@ func (c *ecrecover) Run(in []byte) []byte {
// tighter sig s values in homestead only apply to tx sigs
if !allZero(in[32:63]) || !crypto.ValidateSignatureValues(v, r, s, false) {
log.Trace("ECRECOVER error: v, r or s value invalid")
- return nil
+ return nil, nil
}
// v needs to be at the end for libsecp256k1
pubKey, err := crypto.Ecrecover(in[:32], append(in[64:128], v))
// make sure the public key is a valid one
if err != nil {
log.Trace("ECRECOVER failed", "err", err)
- return nil
+ return nil, nil
}
// the first byte of pubkey is bitcoin heritage
- return common.LeftPadBytes(crypto.Keccak256(pubKey[1:])[12:], 32)
+ return common.LeftPadBytes(crypto.Keccak256(pubKey[1:])[12:], 32), nil
}
// SHA256 implemented as a native contract
@@ -97,12 +98,12 @@ type sha256hash struct{}
//
// This method does not require any overflow checking as the input size gas costs
// required for anything significant is so high it's impossible to pay for.
-func (c *sha256hash) RequiredGas(inputSize int) uint64 {
- return uint64(inputSize+31)/32*params.Sha256WordGas + params.Sha256Gas
+func (c *sha256hash) RequiredGas(input []byte) uint64 {
+ return uint64(len(input)+31)/32*params.Sha256WordGas + params.Sha256Gas
}
-func (c *sha256hash) Run(in []byte) []byte {
+func (c *sha256hash) Run(in []byte) ([]byte, error) {
h := sha256.Sum256(in)
- return h[:]
+ return h[:], nil
}
// RIPMED160 implemented as a native contract
@@ -112,13 +113,13 @@ type ripemd160hash struct{}
//
// This method does not require any overflow checking as the input size gas costs
// required for anything significant is so high it's impossible to pay for.
-func (c *ripemd160hash) RequiredGas(inputSize int) uint64 {
- return uint64(inputSize+31)/32*params.Ripemd160WordGas + params.Ripemd160Gas
+func (c *ripemd160hash) RequiredGas(input []byte) uint64 {
+ return uint64(len(input)+31)/32*params.Ripemd160WordGas + params.Ripemd160Gas
}
-func (c *ripemd160hash) Run(in []byte) []byte {
+func (c *ripemd160hash) Run(in []byte) ([]byte, error) {
ripemd := ripemd160.New()
ripemd.Write(in)
- return common.LeftPadBytes(ripemd.Sum(nil), 32)
+ return common.LeftPadBytes(ripemd.Sum(nil), 32), nil
}
// data copy implemented as a native contract
@@ -128,9 +129,9 @@ type dataCopy struct{}
//
// This method does not require any overflow checking as the input size gas costs
// required for anything significant is so high it's impossible to pay for.
-func (c *dataCopy) RequiredGas(inputSize int) uint64 {
- return uint64(inputSize+31)/32*params.IdentityWordGas + params.IdentityGas
+func (c *dataCopy) RequiredGas(input []byte) uint64 {
+ return uint64(len(input)+31)/32*params.IdentityWordGas + params.IdentityGas
}
-func (c *dataCopy) Run(in []byte) []byte {
- return in
+func (c *dataCopy) Run(in []byte) ([]byte, error) {
+ return in, nil
}
diff --git a/core/vm/contracts_test.go b/core/vm/contracts_test.go
new file mode 100644
index 000000000..830a8f69d
--- /dev/null
+++ b/core/vm/contracts_test.go
@@ -0,0 +1 @@
+package vm
diff --git a/core/vm/evm.go b/core/vm/evm.go
index 71efcfa45..9296cc7ca 100644
--- a/core/vm/evm.go
+++ b/core/vm/evm.go
@@ -33,7 +33,20 @@ type (
GetHashFunc func(uint64) common.Hash
)
-// Context provides the EVM with auxiliary information. Once provided it shouldn't be modified.
+// run runs the given contract and takes care of running precompiles with a fallback to the byte code interpreter.
+func run(evm *EVM, snapshot int, contract *Contract, input []byte) ([]byte, error) {
+ if contract.CodeAddr != nil {
+ precompiledContracts := PrecompiledContracts
+ if p := precompiledContracts[*contract.CodeAddr]; p != nil {
+ return RunPrecompiledContract(p, input, contract)
+ }
+ }
+
+ return evm.interpreter.Run(snapshot, contract, input)
+}
+
+// Context provides the EVM with auxiliary information. Once provided
+// it shouldn't be modified.
type Context struct {
// CanTransfer returns whether the account contains
// sufficient ether to transfer the value
@@ -55,7 +68,13 @@ type Context struct {
Difficulty *big.Int // Provides information for DIFFICULTY
}
-// EVM provides information about external sources for the EVM
+// EVM is the Ethereum Virtual Machine base object and provides
+// the necessary tools to run a contract on the given state with
+// the provided context. It should be noted that any error
+// generated through any of the calls should be considered a
+// revert-state-and-consume-all-gas operation, no checks on
+// specific errors should ever be performed. The interpreter makes
+// sure that any errors generated are to be considered faulty code.
//
// The EVM should never be reused and is not thread safe.
type EVM struct {
@@ -68,6 +87,8 @@ type EVM struct {
// chainConfig contains information about the current chain
chainConfig *params.ChainConfig
+ // chain rules contains the chain rules for the current epoch
+ chainRules params.Rules
// virtual machine configuration options used to initialise the
// evm.
vmConfig Config
@@ -79,21 +100,23 @@ type EVM struct {
abort int32
}
-// NewEVM retutrns a new EVM evmironment.
+// NewEVM retutrns a new EVM evmironment. The returned EVM is not thread safe
+// and should only ever be used *once*.
func NewEVM(ctx Context, statedb StateDB, chainConfig *params.ChainConfig, vmConfig Config) *EVM {
evm := &EVM{
Context: ctx,
StateDB: statedb,
vmConfig: vmConfig,
chainConfig: chainConfig,
+ chainRules: chainConfig.Rules(ctx.BlockNumber),
}
evm.interpreter = NewInterpreter(evm, vmConfig)
return evm
}
-// Cancel cancels any running EVM operation. This may be called concurrently and it's safe to be
-// called multiple times.
+// Cancel cancels any running EVM operation. This may be called concurrently and
+// it's safe to be called multiple times.
func (evm *EVM) Cancel() {
atomic.StoreInt32(&evm.abort, 1)
}
@@ -134,13 +157,12 @@ func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas
contract := NewContract(caller, to, value, gas)
contract.SetCallCode(&addr, evm.StateDB.GetCodeHash(addr), evm.StateDB.GetCode(addr))
- ret, err = evm.interpreter.Run(contract, input)
+ ret, err = run(evm, snapshot, contract, input)
// When an error was returned by the EVM or when setting the creation code
// above we revert to the snapshot and consume any gas remaining. Additionally
// when we're in homestead this also counts for code storage gas errors.
if err != nil {
contract.UseGas(contract.Gas)
-
evm.StateDB.RevertToSnapshot(snapshot)
}
return ret, contract.Gas, err
@@ -175,10 +197,9 @@ func (evm *EVM) CallCode(caller ContractRef, addr common.Address, input []byte,
contract := NewContract(caller, to, value, gas)
contract.SetCallCode(&addr, evm.StateDB.GetCodeHash(addr), evm.StateDB.GetCode(addr))
- ret, err = evm.interpreter.Run(contract, input)
+ ret, err = run(evm, snapshot, contract, input)
if err != nil {
contract.UseGas(contract.Gas)
-
evm.StateDB.RevertToSnapshot(snapshot)
}
@@ -210,10 +231,9 @@ func (evm *EVM) DelegateCall(caller ContractRef, addr common.Address, input []by
contract := NewContract(caller, to, nil, gas).AsDelegate()
contract.SetCallCode(&addr, evm.StateDB.GetCodeHash(addr), evm.StateDB.GetCode(addr))
- ret, err = evm.interpreter.Run(contract, input)
+ ret, err = run(evm, snapshot, contract, input)
if err != nil {
contract.UseGas(contract.Gas)
-
evm.StateDB.RevertToSnapshot(snapshot)
}
@@ -253,8 +273,7 @@ func (evm *EVM) Create(caller ContractRef, code []byte, gas uint64, value *big.I
contract := NewContract(caller, AccountRef(contractAddr), value, gas)
contract.SetCallCode(&contractAddr, crypto.Keccak256Hash(code), code)
- ret, err = evm.interpreter.Run(contract, nil)
-
+ ret, err = run(evm, snapshot, contract, nil)
// check whether the max code size has been exceeded
maxCodeSizeExceeded := len(ret) > params.MaxCodeSize
// if the contract creation ran successfully and no errors were returned
@@ -275,10 +294,8 @@ func (evm *EVM) Create(caller ContractRef, code []byte, gas uint64, value *big.I
// when we're in homestead this also counts for code storage gas errors.
if maxCodeSizeExceeded ||
(err != nil && (evm.ChainConfig().IsHomestead(evm.BlockNumber) || err != ErrCodeStoreOutOfGas)) {
+ contract.UseGas(contract.Gas)
evm.StateDB.RevertToSnapshot(snapshot)
-
- // Nothing should be returned when an error is thrown.
- return nil, contractAddr, 0, err
}
// If the vm returned with an error the return value should be set to nil.
// This isn't consensus critical but merely to for behaviour reasons such as
diff --git a/core/vm/instructions.go b/core/vm/instructions.go
index bfc0a668e..fa4dbe428 100644
--- a/core/vm/instructions.go
+++ b/core/vm/instructions.go
@@ -27,7 +27,9 @@ import (
"github.com/ethereum/go-ethereum/params"
)
-var bigZero = new(big.Int)
+var (
+ bigZero = new(big.Int)
+)
func opAdd(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
x, y := stack.pop(), stack.pop()
@@ -599,7 +601,7 @@ func opCall(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Sta
contract.Gas += returnGas
evm.interpreter.intPool.put(addr, value, inOffset, inSize, retOffset, retSize)
- return nil, nil
+ return ret, nil
}
func opCallCode(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
@@ -633,16 +635,10 @@ func opCallCode(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack
contract.Gas += returnGas
evm.interpreter.intPool.put(addr, value, inOffset, inSize, retOffset, retSize)
- return nil, nil
+ return ret, nil
}
func opDelegateCall(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
- // if not homestead return an error. DELEGATECALL is not supported
- // during pre-homestead.
- if !evm.ChainConfig().IsHomestead(evm.BlockNumber) {
- return nil, fmt.Errorf("invalid opcode %x", DELEGATECALL)
- }
-
gas, to, inOffset, inSize, outOffset, outSize := stack.pop().Uint64(), stack.pop(), stack.pop(), stack.pop(), stack.pop(), stack.pop()
toAddr := common.BigToAddress(to)
@@ -658,7 +654,7 @@ func opDelegateCall(pc *uint64, evm *EVM, contract *Contract, memory *Memory, st
contract.Gas += returnGas
evm.interpreter.intPool.put(to, inOffset, inSize, outOffset, outSize)
- return nil, nil
+ return ret, nil
}
func opReturn(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
@@ -666,6 +662,7 @@ func opReturn(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *S
ret := memory.GetPtr(offset.Int64(), size.Int64())
evm.interpreter.intPool.put(offset, size)
+
return ret, nil
}
diff --git a/core/vm/interpreter.go b/core/vm/interpreter.go
index 8ee9d3ca7..07971f876 100644
--- a/core/vm/interpreter.go
+++ b/core/vm/interpreter.go
@@ -45,50 +45,60 @@ type Config struct {
DisableGasMetering bool
// Enable recording of SHA3/keccak preimages
EnablePreimageRecording bool
- // JumpTable contains the EVM instruction table. This
+ // JumpTable contains the in instruction table. This
// may me left uninitialised and will be set the default
// table.
JumpTable [256]operation
}
// Interpreter is used to run Ethereum based contracts and will utilise the
-// passed environment to query external sources for state information.
+// passed evmironment to query external sources for state information.
// The Interpreter will run the byte code VM or JIT VM based on the passed
// configuration.
type Interpreter struct {
- env *EVM
+ evm *EVM
cfg Config
gasTable params.GasTable
intPool *intPool
+
+ readonly bool
}
// NewInterpreter returns a new instance of the Interpreter.
-func NewInterpreter(env *EVM, cfg Config) *Interpreter {
+func NewInterpreter(evm *EVM, cfg Config) *Interpreter {
// We use the STOP instruction whether to see
// the jump table was initialised. If it was not
// we'll set the default jump table.
if !cfg.JumpTable[STOP].valid {
- cfg.JumpTable = defaultJumpTable
+ switch {
+ case evm.ChainConfig().IsHomestead(evm.BlockNumber):
+ cfg.JumpTable = homesteadInstructionSet
+ default:
+ cfg.JumpTable = baseInstructionSet
+ }
}
return &Interpreter{
- env: env,
+ evm: evm,
cfg: cfg,
- gasTable: env.ChainConfig().GasTable(env.BlockNumber),
+ gasTable: evm.ChainConfig().GasTable(evm.BlockNumber),
intPool: newIntPool(),
}
}
-// Run loops and evaluates the contract's code with the given input data
-func (evm *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err error) {
- evm.env.depth++
- defer func() { evm.env.depth-- }()
+func (in *Interpreter) enforceRestrictions(op OpCode, operation operation, stack *Stack) error {
+ return nil
+}
- if contract.CodeAddr != nil {
- if p := PrecompiledContracts[*contract.CodeAddr]; p != nil {
- return RunPrecompiledContract(p, input, contract)
- }
- }
+// Run loops and evaluates the contract's code with the given input data and returns
+// the return byte-slice and an error if one occured.
+//
+// It's important to note that any errors returned by the interpreter should be
+// considered a revert-and-consume-all-gas operation. No error specific checks
+// should be handled to reduce complexity and errors further down the in.
+func (in *Interpreter) Run(snapshot int, contract *Contract, input []byte) (ret []byte, err error) {
+ in.evm.depth++
+ defer func() { in.evm.depth-- }()
// Don't bother with the execution if there's no code.
if len(contract.Code) == 0 {
@@ -105,7 +115,8 @@ func (evm *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err e
mem = NewMemory() // bound memory
stack = newstack() // local stack
// For optimisation reason we're using uint64 as the program counter.
- // It's theoretically possible to go above 2^64. The YP defines the PC to be uint256. Practically much less so feasible.
+ // It's theoretically possible to go above 2^64. The YP defines the PC
+ // to be uint256. Practically much less so feasible.
pc = uint64(0) // program counter
cost uint64
)
@@ -113,27 +124,30 @@ func (evm *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err e
// User defer pattern to check for an error and, based on the error being nil or not, use all gas and return.
defer func() {
- if err != nil && evm.cfg.Debug {
+ if err != nil && in.cfg.Debug {
// XXX For debugging
//fmt.Printf("%04d: %8v cost = %-8d stack = %-8d ERR = %v\n", pc, op, cost, stack.len(), err)
- evm.cfg.Tracer.CaptureState(evm.env, pc, op, contract.Gas, cost, mem, stack, contract, evm.env.depth, err)
+ in.cfg.Tracer.CaptureState(in.evm, pc, op, contract.Gas, cost, mem, stack, contract, in.evm.depth, err)
}
}()
- log.Debug("EVM running contract", "hash", codehash[:])
+ log.Debug("in running contract", "hash", codehash[:])
tstart := time.Now()
- defer log.Debug("EVM finished running contract", "hash", codehash[:], "elapsed", time.Since(tstart))
+ defer log.Debug("in finished running contract", "hash", codehash[:], "elapsed", time.Since(tstart))
// The Interpreter main run loop (contextual). This loop runs until either an
// explicit STOP, RETURN or SELFDESTRUCT is executed, an error occurred during
- // the execution of one of the operations or until the evm.done is set by
+ // the execution of one of the operations or until the in.done is set by
// the parent context.Context.
- for atomic.LoadInt32(&evm.env.abort) == 0 {
+ for atomic.LoadInt32(&in.evm.abort) == 0 {
// Get the memory location of pc
op = contract.GetOp(pc)
// get the operation from the jump table matching the opcode
- operation := evm.cfg.JumpTable[op]
+ operation := in.cfg.JumpTable[op]
+ if err := in.enforceRestrictions(op, operation, stack); err != nil {
+ return nil, err
+ }
// if the op is invalid abort the process and return an error
if !operation.valid {
@@ -161,10 +175,10 @@ func (evm *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err e
}
}
- if !evm.cfg.DisableGasMetering {
+ if !in.cfg.DisableGasMetering {
// consume the gas and return an error if not enough gas is available.
// cost is explicitly set so that the capture state defer method cas get the proper cost
- cost, err = operation.gasCost(evm.gasTable, evm.env, contract, stack, mem, memorySize)
+ cost, err = operation.gasCost(in.gasTable, in.evm, contract, stack, mem, memorySize)
if err != nil || !contract.UseGas(cost) {
return nil, ErrOutOfGas
}
@@ -173,19 +187,20 @@ func (evm *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err e
mem.Resize(memorySize)
}
- if evm.cfg.Debug {
- evm.cfg.Tracer.CaptureState(evm.env, pc, op, contract.Gas, cost, mem, stack, contract, evm.env.depth, err)
+ if in.cfg.Debug {
+ in.cfg.Tracer.CaptureState(in.evm, pc, op, contract.Gas, cost, mem, stack, contract, in.evm.depth, err)
}
// XXX For debugging
//fmt.Printf("%04d: %8v cost = %-8d stack = %-8d\n", pc, op, cost, stack.len())
// execute the operation
- res, err := operation.execute(&pc, evm.env, contract, mem, stack)
+ res, err := operation.execute(&pc, in.evm, contract, mem, stack)
// verifyPool is a build flag. Pool verification makes sure the integrity
// of the integer pool by comparing values to a default value.
if verifyPool {
- verifyIntegerPool(evm.intPool)
+ verifyIntegerPool(in.intPool)
}
+
switch {
case err != nil:
return nil, err
@@ -194,6 +209,11 @@ func (evm *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err e
case !operation.jumps:
pc++
}
+ // if the operation returned a value make sure that is also set
+ // the last return data.
+ if res != nil {
+ mem.lastReturn = ret
+ }
}
return nil, nil
}
diff --git a/core/vm/jump_table.go b/core/vm/jump_table.go
index ed30100ac..c4a1430b2 100644
--- a/core/vm/jump_table.go
+++ b/core/vm/jump_table.go
@@ -47,13 +47,32 @@ type operation struct {
// jumps indicates whether operation made a jump. This prevents the program
// counter from further incrementing.
jumps bool
+ // writes determines whether this a state modifying operation
+ writes bool
// valid is used to check whether the retrieved operation is valid and known
valid bool
+ // reverts determined whether the operation reverts state
+ reverts bool
}
-var defaultJumpTable = NewJumpTable()
+var (
+ baseInstructionSet = NewBaseInstructionSet()
+ homesteadInstructionSet = NewHomesteadInstructionSet()
+)
+
+func NewHomesteadInstructionSet() [256]operation {
+ instructionSet := NewBaseInstructionSet()
+ instructionSet[DELEGATECALL] = operation{
+ execute: opDelegateCall,
+ gasCost: gasDelegateCall,
+ validateStack: makeStackFunc(6, 1),
+ memorySize: memoryDelegateCall,
+ valid: true,
+ }
+ return instructionSet
+}
-func NewJumpTable() [256]operation {
+func NewBaseInstructionSet() [256]operation {
return [256]operation{
STOP: {
execute: opStop,
@@ -357,6 +376,7 @@ func NewJumpTable() [256]operation {
gasCost: gasSStore,
validateStack: makeStackFunc(2, 0),
valid: true,
+ writes: true,
},
JUMP: {
execute: opJump,
@@ -821,6 +841,7 @@ func NewJumpTable() [256]operation {
validateStack: makeStackFunc(3, 1),
memorySize: memoryCreate,
valid: true,
+ writes: true,
},
CALL: {
execute: opCall,
@@ -844,19 +865,13 @@ func NewJumpTable() [256]operation {
halts: true,
valid: true,
},
- DELEGATECALL: {
- execute: opDelegateCall,
- gasCost: gasDelegateCall,
- validateStack: makeStackFunc(6, 1),
- memorySize: memoryDelegateCall,
- valid: true,
- },
SELFDESTRUCT: {
execute: opSuicide,
gasCost: gasSuicide,
validateStack: makeStackFunc(1, 0),
halts: true,
valid: true,
+ writes: true,
},
}
}
diff --git a/core/vm/memory.go b/core/vm/memory.go
index 99a84d227..6dbee94ef 100644
--- a/core/vm/memory.go
+++ b/core/vm/memory.go
@@ -22,6 +22,7 @@ import "fmt"
type Memory struct {
store []byte
lastGasCost uint64
+ lastReturn []byte
}
func NewMemory() *Memory {
diff --git a/crypto/bn256/bn256.go b/crypto/bn256/bn256.go
new file mode 100644
index 000000000..92418369b
--- /dev/null
+++ b/crypto/bn256/bn256.go
@@ -0,0 +1,428 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package bn256 implements a particular bilinear group at the 128-bit security level.
+//
+// Bilinear groups are the basis of many of the new cryptographic protocols
+// that have been proposed over the past decade. They consist of a triplet of
+// groups (G₁, G₂ and GT) such that there exists a function e(g₁ˣ,g₂ʸ)=gTˣʸ
+// (where gₓ is a generator of the respective group). That function is called
+// a pairing function.
+//
+// This package specifically implements the Optimal Ate pairing over a 256-bit
+// Barreto-Naehrig curve as described in
+// http://cryptojedi.org/papers/dclxvi-20100714.pdf. Its output is compatible
+// with the implementation described in that paper.
+package bn256
+
+import (
+ "crypto/rand"
+ "io"
+ "math/big"
+)
+
+// BUG(agl): this implementation is not constant time.
+// TODO(agl): keep GF(p²) elements in Mongomery form.
+
+// G1 is an abstract cyclic group. The zero value is suitable for use as the
+// output of an operation, but cannot be used as an input.
+type G1 struct {
+ p *curvePoint
+}
+
+// RandomG1 returns x and g₁ˣ where x is a random, non-zero number read from r.
+func RandomG1(r io.Reader) (*big.Int, *G1, error) {
+ var k *big.Int
+ var err error
+
+ for {
+ k, err = rand.Int(r, Order)
+ if err != nil {
+ return nil, nil, err
+ }
+ if k.Sign() > 0 {
+ break
+ }
+ }
+
+ return k, new(G1).ScalarBaseMult(k), nil
+}
+
+func (g *G1) String() string {
+ return "bn256.G1" + g.p.String()
+}
+
+// CurvePoints returns p's curve points in big integer
+func (e *G1) CurvePoints() (*big.Int, *big.Int, *big.Int, *big.Int) {
+ return e.p.x, e.p.y, e.p.z, e.p.t
+}
+
+// ScalarBaseMult sets e to g*k where g is the generator of the group and
+// then returns e.
+func (e *G1) ScalarBaseMult(k *big.Int) *G1 {
+ if e.p == nil {
+ e.p = newCurvePoint(nil)
+ }
+ e.p.Mul(curveGen, k, new(bnPool))
+ return e
+}
+
+// ScalarMult sets e to a*k and then returns e.
+func (e *G1) ScalarMult(a *G1, k *big.Int) *G1 {
+ if e.p == nil {
+ e.p = newCurvePoint(nil)
+ }
+ e.p.Mul(a.p, k, new(bnPool))
+ return e
+}
+
+// Add sets e to a+b and then returns e.
+// BUG(agl): this function is not complete: a==b fails.
+func (e *G1) Add(a, b *G1) *G1 {
+ if e.p == nil {
+ e.p = newCurvePoint(nil)
+ }
+ e.p.Add(a.p, b.p, new(bnPool))
+ return e
+}
+
+// Neg sets e to -a and then returns e.
+func (e *G1) Neg(a *G1) *G1 {
+ if e.p == nil {
+ e.p = newCurvePoint(nil)
+ }
+ e.p.Negative(a.p)
+ return e
+}
+
+// Marshal converts n to a byte slice.
+func (n *G1) Marshal() []byte {
+ n.p.MakeAffine(nil)
+
+ xBytes := new(big.Int).Mod(n.p.x, P).Bytes()
+ yBytes := new(big.Int).Mod(n.p.y, P).Bytes()
+
+ // Each value is a 256-bit number.
+ const numBytes = 256 / 8
+
+ ret := make([]byte, numBytes*2)
+ copy(ret[1*numBytes-len(xBytes):], xBytes)
+ copy(ret[2*numBytes-len(yBytes):], yBytes)
+
+ return ret
+}
+
+// Unmarshal sets e to the result of converting the output of Marshal back into
+// a group element and then returns e.
+func (e *G1) Unmarshal(m []byte) (*G1, bool) {
+ // Each value is a 256-bit number.
+ const numBytes = 256 / 8
+
+ if len(m) != 2*numBytes {
+ return nil, false
+ }
+
+ if e.p == nil {
+ e.p = newCurvePoint(nil)
+ }
+
+ e.p.x.SetBytes(m[0*numBytes : 1*numBytes])
+ e.p.y.SetBytes(m[1*numBytes : 2*numBytes])
+
+ if e.p.x.Sign() == 0 && e.p.y.Sign() == 0 {
+ // This is the point at infinity.
+ e.p.y.SetInt64(1)
+ e.p.z.SetInt64(0)
+ e.p.t.SetInt64(0)
+ } else {
+ e.p.z.SetInt64(1)
+ e.p.t.SetInt64(1)
+
+ if !e.p.IsOnCurve() {
+ return nil, false
+ }
+ }
+
+ return e, true
+}
+
+// G2 is an abstract cyclic group. The zero value is suitable for use as the
+// output of an operation, but cannot be used as an input.
+type G2 struct {
+ p *twistPoint
+}
+
+// RandomG1 returns x and g₂ˣ where x is a random, non-zero number read from r.
+func RandomG2(r io.Reader) (*big.Int, *G2, error) {
+ var k *big.Int
+ var err error
+
+ for {
+ k, err = rand.Int(r, Order)
+ if err != nil {
+ return nil, nil, err
+ }
+ if k.Sign() > 0 {
+ break
+ }
+ }
+
+ return k, new(G2).ScalarBaseMult(k), nil
+}
+
+func (g *G2) String() string {
+ return "bn256.G2" + g.p.String()
+}
+
+// CurvePoints returns the curve points of p which includes the real
+// and imaginary parts of the curve point.
+func (e *G2) CurvePoints() (*gfP2, *gfP2, *gfP2, *gfP2) {
+ return e.p.x, e.p.y, e.p.z, e.p.t
+}
+
+// ScalarBaseMult sets e to g*k where g is the generator of the group and
+// then returns out.
+func (e *G2) ScalarBaseMult(k *big.Int) *G2 {
+ if e.p == nil {
+ e.p = newTwistPoint(nil)
+ }
+ e.p.Mul(twistGen, k, new(bnPool))
+ return e
+}
+
+// ScalarMult sets e to a*k and then returns e.
+func (e *G2) ScalarMult(a *G2, k *big.Int) *G2 {
+ if e.p == nil {
+ e.p = newTwistPoint(nil)
+ }
+ e.p.Mul(a.p, k, new(bnPool))
+ return e
+}
+
+// Add sets e to a+b and then returns e.
+// BUG(agl): this function is not complete: a==b fails.
+func (e *G2) Add(a, b *G2) *G2 {
+ if e.p == nil {
+ e.p = newTwistPoint(nil)
+ }
+ e.p.Add(a.p, b.p, new(bnPool))
+ return e
+}
+
+// Marshal converts n into a byte slice.
+func (n *G2) Marshal() []byte {
+ n.p.MakeAffine(nil)
+
+ xxBytes := new(big.Int).Mod(n.p.x.x, P).Bytes()
+ xyBytes := new(big.Int).Mod(n.p.x.y, P).Bytes()
+ yxBytes := new(big.Int).Mod(n.p.y.x, P).Bytes()
+ yyBytes := new(big.Int).Mod(n.p.y.y, P).Bytes()
+
+ // Each value is a 256-bit number.
+ const numBytes = 256 / 8
+
+ ret := make([]byte, numBytes*4)
+ copy(ret[1*numBytes-len(xxBytes):], xxBytes)
+ copy(ret[2*numBytes-len(xyBytes):], xyBytes)
+ copy(ret[3*numBytes-len(yxBytes):], yxBytes)
+ copy(ret[4*numBytes-len(yyBytes):], yyBytes)
+
+ return ret
+}
+
+// Unmarshal sets e to the result of converting the output of Marshal back into
+// a group element and then returns e.
+func (e *G2) Unmarshal(m []byte) (*G2, bool) {
+ // Each value is a 256-bit number.
+ const numBytes = 256 / 8
+
+ if len(m) != 4*numBytes {
+ return nil, false
+ }
+
+ if e.p == nil {
+ e.p = newTwistPoint(nil)
+ }
+
+ e.p.x.x.SetBytes(m[0*numBytes : 1*numBytes])
+ e.p.x.y.SetBytes(m[1*numBytes : 2*numBytes])
+ e.p.y.x.SetBytes(m[2*numBytes : 3*numBytes])
+ e.p.y.y.SetBytes(m[3*numBytes : 4*numBytes])
+
+ if e.p.x.x.Sign() == 0 &&
+ e.p.x.y.Sign() == 0 &&
+ e.p.y.x.Sign() == 0 &&
+ e.p.y.y.Sign() == 0 {
+ // This is the point at infinity.
+ e.p.y.SetOne()
+ e.p.z.SetZero()
+ e.p.t.SetZero()
+ } else {
+ e.p.z.SetOne()
+ e.p.t.SetOne()
+
+ if !e.p.IsOnCurve() {
+ return nil, false
+ }
+ }
+
+ return e, true
+}
+
+// GT is an abstract cyclic group. The zero value is suitable for use as the
+// output of an operation, but cannot be used as an input.
+type GT struct {
+ p *gfP12
+}
+
+func (g *GT) String() string {
+ return "bn256.GT" + g.p.String()
+}
+
+// ScalarMult sets e to a*k and then returns e.
+func (e *GT) ScalarMult(a *GT, k *big.Int) *GT {
+ if e.p == nil {
+ e.p = newGFp12(nil)
+ }
+ e.p.Exp(a.p, k, new(bnPool))
+ return e
+}
+
+// Add sets e to a+b and then returns e.
+func (e *GT) Add(a, b *GT) *GT {
+ if e.p == nil {
+ e.p = newGFp12(nil)
+ }
+ e.p.Mul(a.p, b.p, new(bnPool))
+ return e
+}
+
+// Neg sets e to -a and then returns e.
+func (e *GT) Neg(a *GT) *GT {
+ if e.p == nil {
+ e.p = newGFp12(nil)
+ }
+ e.p.Invert(a.p, new(bnPool))
+ return e
+}
+
+// Marshal converts n into a byte slice.
+func (n *GT) Marshal() []byte {
+ n.p.Minimal()
+
+ xxxBytes := n.p.x.x.x.Bytes()
+ xxyBytes := n.p.x.x.y.Bytes()
+ xyxBytes := n.p.x.y.x.Bytes()
+ xyyBytes := n.p.x.y.y.Bytes()
+ xzxBytes := n.p.x.z.x.Bytes()
+ xzyBytes := n.p.x.z.y.Bytes()
+ yxxBytes := n.p.y.x.x.Bytes()
+ yxyBytes := n.p.y.x.y.Bytes()
+ yyxBytes := n.p.y.y.x.Bytes()
+ yyyBytes := n.p.y.y.y.Bytes()
+ yzxBytes := n.p.y.z.x.Bytes()
+ yzyBytes := n.p.y.z.y.Bytes()
+
+ // Each value is a 256-bit number.
+ const numBytes = 256 / 8
+
+ ret := make([]byte, numBytes*12)
+ copy(ret[1*numBytes-len(xxxBytes):], xxxBytes)
+ copy(ret[2*numBytes-len(xxyBytes):], xxyBytes)
+ copy(ret[3*numBytes-len(xyxBytes):], xyxBytes)
+ copy(ret[4*numBytes-len(xyyBytes):], xyyBytes)
+ copy(ret[5*numBytes-len(xzxBytes):], xzxBytes)
+ copy(ret[6*numBytes-len(xzyBytes):], xzyBytes)
+ copy(ret[7*numBytes-len(yxxBytes):], yxxBytes)
+ copy(ret[8*numBytes-len(yxyBytes):], yxyBytes)
+ copy(ret[9*numBytes-len(yyxBytes):], yyxBytes)
+ copy(ret[10*numBytes-len(yyyBytes):], yyyBytes)
+ copy(ret[11*numBytes-len(yzxBytes):], yzxBytes)
+ copy(ret[12*numBytes-len(yzyBytes):], yzyBytes)
+
+ return ret
+}
+
+// Unmarshal sets e to the result of converting the output of Marshal back into
+// a group element and then returns e.
+func (e *GT) Unmarshal(m []byte) (*GT, bool) {
+ // Each value is a 256-bit number.
+ const numBytes = 256 / 8
+
+ if len(m) != 12*numBytes {
+ return nil, false
+ }
+
+ if e.p == nil {
+ e.p = newGFp12(nil)
+ }
+
+ e.p.x.x.x.SetBytes(m[0*numBytes : 1*numBytes])
+ e.p.x.x.y.SetBytes(m[1*numBytes : 2*numBytes])
+ e.p.x.y.x.SetBytes(m[2*numBytes : 3*numBytes])
+ e.p.x.y.y.SetBytes(m[3*numBytes : 4*numBytes])
+ e.p.x.z.x.SetBytes(m[4*numBytes : 5*numBytes])
+ e.p.x.z.y.SetBytes(m[5*numBytes : 6*numBytes])
+ e.p.y.x.x.SetBytes(m[6*numBytes : 7*numBytes])
+ e.p.y.x.y.SetBytes(m[7*numBytes : 8*numBytes])
+ e.p.y.y.x.SetBytes(m[8*numBytes : 9*numBytes])
+ e.p.y.y.y.SetBytes(m[9*numBytes : 10*numBytes])
+ e.p.y.z.x.SetBytes(m[10*numBytes : 11*numBytes])
+ e.p.y.z.y.SetBytes(m[11*numBytes : 12*numBytes])
+
+ return e, true
+}
+
+// Pair calculates an Optimal Ate pairing.
+func Pair(g1 *G1, g2 *G2) *GT {
+ return &GT{optimalAte(g2.p, g1.p, new(bnPool))}
+}
+
+func PairingCheck(a []*G1, b []*G2) bool {
+ pool := new(bnPool)
+ e := newGFp12(pool)
+ e.SetOne()
+ for i := 0; i < len(a); i++ {
+ new_e := miller(b[i].p, a[i].p, pool)
+ e.Mul(e, new_e, pool)
+ }
+ ret := finalExponentiation(e, pool)
+ e.Put(pool)
+ return ret.IsOne()
+}
+
+// bnPool implements a tiny cache of *big.Int objects that's used to reduce the
+// number of allocations made during processing.
+type bnPool struct {
+ bns []*big.Int
+ count int
+}
+
+func (pool *bnPool) Get() *big.Int {
+ if pool == nil {
+ return new(big.Int)
+ }
+
+ pool.count++
+ l := len(pool.bns)
+ if l == 0 {
+ return new(big.Int)
+ }
+
+ bn := pool.bns[l-1]
+ pool.bns = pool.bns[:l-1]
+ return bn
+}
+
+func (pool *bnPool) Put(bn *big.Int) {
+ if pool == nil {
+ return
+ }
+ pool.bns = append(pool.bns, bn)
+ pool.count--
+}
+
+func (pool *bnPool) Count() int {
+ return pool.count
+}
diff --git a/crypto/bn256/bn256_test.go b/crypto/bn256/bn256_test.go
new file mode 100644
index 000000000..866065d0c
--- /dev/null
+++ b/crypto/bn256/bn256_test.go
@@ -0,0 +1,304 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+import (
+ "bytes"
+ "crypto/rand"
+ "math/big"
+ "testing"
+)
+
+func TestGFp2Invert(t *testing.T) {
+ pool := new(bnPool)
+
+ a := newGFp2(pool)
+ a.x.SetString("23423492374", 10)
+ a.y.SetString("12934872398472394827398470", 10)
+
+ inv := newGFp2(pool)
+ inv.Invert(a, pool)
+
+ b := newGFp2(pool).Mul(inv, a, pool)
+ if b.x.Int64() != 0 || b.y.Int64() != 1 {
+ t.Fatalf("bad result for a^-1*a: %s %s", b.x, b.y)
+ }
+
+ a.Put(pool)
+ b.Put(pool)
+ inv.Put(pool)
+
+ if c := pool.Count(); c > 0 {
+ t.Errorf("Pool count non-zero: %d\n", c)
+ }
+}
+
+func isZero(n *big.Int) bool {
+ return new(big.Int).Mod(n, P).Int64() == 0
+}
+
+func isOne(n *big.Int) bool {
+ return new(big.Int).Mod(n, P).Int64() == 1
+}
+
+func TestGFp6Invert(t *testing.T) {
+ pool := new(bnPool)
+
+ a := newGFp6(pool)
+ a.x.x.SetString("239487238491", 10)
+ a.x.y.SetString("2356249827341", 10)
+ a.y.x.SetString("082659782", 10)
+ a.y.y.SetString("182703523765", 10)
+ a.z.x.SetString("978236549263", 10)
+ a.z.y.SetString("64893242", 10)
+
+ inv := newGFp6(pool)
+ inv.Invert(a, pool)
+
+ b := newGFp6(pool).Mul(inv, a, pool)
+ if !isZero(b.x.x) ||
+ !isZero(b.x.y) ||
+ !isZero(b.y.x) ||
+ !isZero(b.y.y) ||
+ !isZero(b.z.x) ||
+ !isOne(b.z.y) {
+ t.Fatalf("bad result for a^-1*a: %s", b)
+ }
+
+ a.Put(pool)
+ b.Put(pool)
+ inv.Put(pool)
+
+ if c := pool.Count(); c > 0 {
+ t.Errorf("Pool count non-zero: %d\n", c)
+ }
+}
+
+func TestGFp12Invert(t *testing.T) {
+ pool := new(bnPool)
+
+ a := newGFp12(pool)
+ a.x.x.x.SetString("239846234862342323958623", 10)
+ a.x.x.y.SetString("2359862352529835623", 10)
+ a.x.y.x.SetString("928836523", 10)
+ a.x.y.y.SetString("9856234", 10)
+ a.x.z.x.SetString("235635286", 10)
+ a.x.z.y.SetString("5628392833", 10)
+ a.y.x.x.SetString("252936598265329856238956532167968", 10)
+ a.y.x.y.SetString("23596239865236954178968", 10)
+ a.y.y.x.SetString("95421692834", 10)
+ a.y.y.y.SetString("236548", 10)
+ a.y.z.x.SetString("924523", 10)
+ a.y.z.y.SetString("12954623", 10)
+
+ inv := newGFp12(pool)
+ inv.Invert(a, pool)
+
+ b := newGFp12(pool).Mul(inv, a, pool)
+ if !isZero(b.x.x.x) ||
+ !isZero(b.x.x.y) ||
+ !isZero(b.x.y.x) ||
+ !isZero(b.x.y.y) ||
+ !isZero(b.x.z.x) ||
+ !isZero(b.x.z.y) ||
+ !isZero(b.y.x.x) ||
+ !isZero(b.y.x.y) ||
+ !isZero(b.y.y.x) ||
+ !isZero(b.y.y.y) ||
+ !isZero(b.y.z.x) ||
+ !isOne(b.y.z.y) {
+ t.Fatalf("bad result for a^-1*a: %s", b)
+ }
+
+ a.Put(pool)
+ b.Put(pool)
+ inv.Put(pool)
+
+ if c := pool.Count(); c > 0 {
+ t.Errorf("Pool count non-zero: %d\n", c)
+ }
+}
+
+func TestCurveImpl(t *testing.T) {
+ pool := new(bnPool)
+
+ g := &curvePoint{
+ pool.Get().SetInt64(1),
+ pool.Get().SetInt64(-2),
+ pool.Get().SetInt64(1),
+ pool.Get().SetInt64(0),
+ }
+
+ x := pool.Get().SetInt64(32498273234)
+ X := newCurvePoint(pool).Mul(g, x, pool)
+
+ y := pool.Get().SetInt64(98732423523)
+ Y := newCurvePoint(pool).Mul(g, y, pool)
+
+ s1 := newCurvePoint(pool).Mul(X, y, pool).MakeAffine(pool)
+ s2 := newCurvePoint(pool).Mul(Y, x, pool).MakeAffine(pool)
+
+ if s1.x.Cmp(s2.x) != 0 ||
+ s2.x.Cmp(s1.x) != 0 {
+ t.Errorf("DH points don't match: (%s, %s) (%s, %s)", s1.x, s1.y, s2.x, s2.y)
+ }
+
+ pool.Put(x)
+ X.Put(pool)
+ pool.Put(y)
+ Y.Put(pool)
+ s1.Put(pool)
+ s2.Put(pool)
+ g.Put(pool)
+
+ if c := pool.Count(); c > 0 {
+ t.Errorf("Pool count non-zero: %d\n", c)
+ }
+}
+
+func TestOrderG1(t *testing.T) {
+ g := new(G1).ScalarBaseMult(Order)
+ if !g.p.IsInfinity() {
+ t.Error("G1 has incorrect order")
+ }
+
+ one := new(G1).ScalarBaseMult(new(big.Int).SetInt64(1))
+ g.Add(g, one)
+ g.p.MakeAffine(nil)
+ if g.p.x.Cmp(one.p.x) != 0 || g.p.y.Cmp(one.p.y) != 0 {
+ t.Errorf("1+0 != 1 in G1")
+ }
+}
+
+func TestOrderG2(t *testing.T) {
+ g := new(G2).ScalarBaseMult(Order)
+ if !g.p.IsInfinity() {
+ t.Error("G2 has incorrect order")
+ }
+
+ one := new(G2).ScalarBaseMult(new(big.Int).SetInt64(1))
+ g.Add(g, one)
+ g.p.MakeAffine(nil)
+ if g.p.x.x.Cmp(one.p.x.x) != 0 ||
+ g.p.x.y.Cmp(one.p.x.y) != 0 ||
+ g.p.y.x.Cmp(one.p.y.x) != 0 ||
+ g.p.y.y.Cmp(one.p.y.y) != 0 {
+ t.Errorf("1+0 != 1 in G2")
+ }
+}
+
+func TestOrderGT(t *testing.T) {
+ gt := Pair(&G1{curveGen}, &G2{twistGen})
+ g := new(GT).ScalarMult(gt, Order)
+ if !g.p.IsOne() {
+ t.Error("GT has incorrect order")
+ }
+}
+
+func TestBilinearity(t *testing.T) {
+ for i := 0; i < 2; i++ {
+ a, p1, _ := RandomG1(rand.Reader)
+ b, p2, _ := RandomG2(rand.Reader)
+ e1 := Pair(p1, p2)
+
+ e2 := Pair(&G1{curveGen}, &G2{twistGen})
+ e2.ScalarMult(e2, a)
+ e2.ScalarMult(e2, b)
+
+ minusE2 := new(GT).Neg(e2)
+ e1.Add(e1, minusE2)
+
+ if !e1.p.IsOne() {
+ t.Fatalf("bad pairing result: %s", e1)
+ }
+ }
+}
+
+func TestG1Marshal(t *testing.T) {
+ g := new(G1).ScalarBaseMult(new(big.Int).SetInt64(1))
+ form := g.Marshal()
+ _, ok := new(G1).Unmarshal(form)
+ if !ok {
+ t.Fatalf("failed to unmarshal")
+ }
+
+ g.ScalarBaseMult(Order)
+ form = g.Marshal()
+ g2, ok := new(G1).Unmarshal(form)
+ if !ok {
+ t.Fatalf("failed to unmarshal ∞")
+ }
+ if !g2.p.IsInfinity() {
+ t.Fatalf("∞ unmarshaled incorrectly")
+ }
+}
+
+func TestG2Marshal(t *testing.T) {
+ g := new(G2).ScalarBaseMult(new(big.Int).SetInt64(1))
+ form := g.Marshal()
+ _, ok := new(G2).Unmarshal(form)
+ if !ok {
+ t.Fatalf("failed to unmarshal")
+ }
+
+ g.ScalarBaseMult(Order)
+ form = g.Marshal()
+ g2, ok := new(G2).Unmarshal(form)
+ if !ok {
+ t.Fatalf("failed to unmarshal ∞")
+ }
+ if !g2.p.IsInfinity() {
+ t.Fatalf("∞ unmarshaled incorrectly")
+ }
+}
+
+func TestG1Identity(t *testing.T) {
+ g := new(G1).ScalarBaseMult(new(big.Int).SetInt64(0))
+ if !g.p.IsInfinity() {
+ t.Error("failure")
+ }
+}
+
+func TestG2Identity(t *testing.T) {
+ g := new(G2).ScalarBaseMult(new(big.Int).SetInt64(0))
+ if !g.p.IsInfinity() {
+ t.Error("failure")
+ }
+}
+
+func TestTripartiteDiffieHellman(t *testing.T) {
+ a, _ := rand.Int(rand.Reader, Order)
+ b, _ := rand.Int(rand.Reader, Order)
+ c, _ := rand.Int(rand.Reader, Order)
+
+ pa, _ := new(G1).Unmarshal(new(G1).ScalarBaseMult(a).Marshal())
+ qa, _ := new(G2).Unmarshal(new(G2).ScalarBaseMult(a).Marshal())
+ pb, _ := new(G1).Unmarshal(new(G1).ScalarBaseMult(b).Marshal())
+ qb, _ := new(G2).Unmarshal(new(G2).ScalarBaseMult(b).Marshal())
+ pc, _ := new(G1).Unmarshal(new(G1).ScalarBaseMult(c).Marshal())
+ qc, _ := new(G2).Unmarshal(new(G2).ScalarBaseMult(c).Marshal())
+
+ k1 := Pair(pb, qc)
+ k1.ScalarMult(k1, a)
+ k1Bytes := k1.Marshal()
+
+ k2 := Pair(pc, qa)
+ k2.ScalarMult(k2, b)
+ k2Bytes := k2.Marshal()
+
+ k3 := Pair(pa, qb)
+ k3.ScalarMult(k3, c)
+ k3Bytes := k3.Marshal()
+
+ if !bytes.Equal(k1Bytes, k2Bytes) || !bytes.Equal(k2Bytes, k3Bytes) {
+ t.Errorf("keys didn't agree")
+ }
+}
+
+func BenchmarkPairing(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ Pair(&G1{curveGen}, &G2{twistGen})
+ }
+}
diff --git a/crypto/bn256/constants.go b/crypto/bn256/constants.go
new file mode 100644
index 000000000..ab649d7f3
--- /dev/null
+++ b/crypto/bn256/constants.go
@@ -0,0 +1,44 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+import (
+ "math/big"
+)
+
+func bigFromBase10(s string) *big.Int {
+ n, _ := new(big.Int).SetString(s, 10)
+ return n
+}
+
+// u is the BN parameter that determines the prime: 1868033³.
+var u = bigFromBase10("4965661367192848881")
+
+// p is a prime over which we form a basic field: 36u⁴+36u³+24u²+6u+1.
+var P = bigFromBase10("21888242871839275222246405745257275088696311157297823662689037894645226208583")
+
+// Order is the number of elements in both G₁ and G₂: 36u⁴+36u³+18u²+6u+1.
+var Order = bigFromBase10("21888242871839275222246405745257275088548364400416034343698204186575808495617")
+
+// xiToPMinus1Over6 is ξ^((p-1)/6) where ξ = i+9.
+var xiToPMinus1Over6 = &gfP2{bigFromBase10("16469823323077808223889137241176536799009286646108169935659301613961712198316"), bigFromBase10("8376118865763821496583973867626364092589906065868298776909617916018768340080")}
+
+// xiToPMinus1Over3 is ξ^((p-1)/3) where ξ = i+9.
+var xiToPMinus1Over3 = &gfP2{bigFromBase10("10307601595873709700152284273816112264069230130616436755625194854815875713954"), bigFromBase10("21575463638280843010398324269430826099269044274347216827212613867836435027261")}
+
+// xiToPMinus1Over2 is ξ^((p-1)/2) where ξ = i+9.
+var xiToPMinus1Over2 = &gfP2{bigFromBase10("3505843767911556378687030309984248845540243509899259641013678093033130930403"), bigFromBase10("2821565182194536844548159561693502659359617185244120367078079554186484126554")}
+
+// xiToPSquaredMinus1Over3 is ξ^((p²-1)/3) where ξ = i+9.
+var xiToPSquaredMinus1Over3 = bigFromBase10("21888242871839275220042445260109153167277707414472061641714758635765020556616")
+
+// xiTo2PSquaredMinus2Over3 is ξ^((2p²-2)/3) where ξ = i+9 (a cubic root of unity, mod p).
+var xiTo2PSquaredMinus2Over3 = bigFromBase10("2203960485148121921418603742825762020974279258880205651966")
+
+// xiToPSquaredMinus1Over6 is ξ^((1p²-1)/6) where ξ = i+9 (a cubic root of -1, mod p).
+var xiToPSquaredMinus1Over6 = bigFromBase10("21888242871839275220042445260109153167277707414472061641714758635765020556617")
+
+// xiTo2PMinus2Over3 is ξ^((2p-2)/3) where ξ = i+9.
+var xiTo2PMinus2Over3 = &gfP2{bigFromBase10("19937756971775647987995932169929341994314640652964949448313374472400716661030"), bigFromBase10("2581911344467009335267311115468803099551665605076196740867805258568234346338")}
diff --git a/crypto/bn256/curve.go b/crypto/bn256/curve.go
new file mode 100644
index 000000000..93f858def
--- /dev/null
+++ b/crypto/bn256/curve.go
@@ -0,0 +1,278 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+import (
+ "math/big"
+)
+
+// curvePoint implements the elliptic curve y²=x³+3. Points are kept in
+// Jacobian form and t=z² when valid. G₁ is the set of points of this curve on
+// GF(p).
+type curvePoint struct {
+ x, y, z, t *big.Int
+}
+
+var curveB = new(big.Int).SetInt64(3)
+
+// curveGen is the generator of G₁.
+var curveGen = &curvePoint{
+ new(big.Int).SetInt64(1),
+ new(big.Int).SetInt64(-2),
+ new(big.Int).SetInt64(1),
+ new(big.Int).SetInt64(1),
+}
+
+func newCurvePoint(pool *bnPool) *curvePoint {
+ return &curvePoint{
+ pool.Get(),
+ pool.Get(),
+ pool.Get(),
+ pool.Get(),
+ }
+}
+
+func (c *curvePoint) String() string {
+ c.MakeAffine(new(bnPool))
+ return "(" + c.x.String() + ", " + c.y.String() + ")"
+}
+
+func (c *curvePoint) Put(pool *bnPool) {
+ pool.Put(c.x)
+ pool.Put(c.y)
+ pool.Put(c.z)
+ pool.Put(c.t)
+}
+
+func (c *curvePoint) Set(a *curvePoint) {
+ c.x.Set(a.x)
+ c.y.Set(a.y)
+ c.z.Set(a.z)
+ c.t.Set(a.t)
+}
+
+// IsOnCurve returns true iff c is on the curve where c must be in affine form.
+func (c *curvePoint) IsOnCurve() bool {
+ yy := new(big.Int).Mul(c.y, c.y)
+ xxx := new(big.Int).Mul(c.x, c.x)
+ xxx.Mul(xxx, c.x)
+ yy.Sub(yy, xxx)
+ yy.Sub(yy, curveB)
+ if yy.Sign() < 0 || yy.Cmp(P) >= 0 {
+ yy.Mod(yy, P)
+ }
+ return yy.Sign() == 0
+}
+
+func (c *curvePoint) SetInfinity() {
+ c.z.SetInt64(0)
+}
+
+func (c *curvePoint) IsInfinity() bool {
+ return c.z.Sign() == 0
+}
+
+func (c *curvePoint) Add(a, b *curvePoint, pool *bnPool) {
+ if a.IsInfinity() {
+ c.Set(b)
+ return
+ }
+ if b.IsInfinity() {
+ c.Set(a)
+ return
+ }
+
+ // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
+
+ // Normalize the points by replacing a = [x1:y1:z1] and b = [x2:y2:z2]
+ // by [u1:s1:z1·z2] and [u2:s2:z1·z2]
+ // where u1 = x1·z2², s1 = y1·z2³ and u1 = x2·z1², s2 = y2·z1³
+ z1z1 := pool.Get().Mul(a.z, a.z)
+ z1z1.Mod(z1z1, P)
+ z2z2 := pool.Get().Mul(b.z, b.z)
+ z2z2.Mod(z2z2, P)
+ u1 := pool.Get().Mul(a.x, z2z2)
+ u1.Mod(u1, P)
+ u2 := pool.Get().Mul(b.x, z1z1)
+ u2.Mod(u2, P)
+
+ t := pool.Get().Mul(b.z, z2z2)
+ t.Mod(t, P)
+ s1 := pool.Get().Mul(a.y, t)
+ s1.Mod(s1, P)
+
+ t.Mul(a.z, z1z1)
+ t.Mod(t, P)
+ s2 := pool.Get().Mul(b.y, t)
+ s2.Mod(s2, P)
+
+ // Compute x = (2h)²(s²-u1-u2)
+ // where s = (s2-s1)/(u2-u1) is the slope of the line through
+ // (u1,s1) and (u2,s2). The extra factor 2h = 2(u2-u1) comes from the value of z below.
+ // This is also:
+ // 4(s2-s1)² - 4h²(u1+u2) = 4(s2-s1)² - 4h³ - 4h²(2u1)
+ // = r² - j - 2v
+ // with the notations below.
+ h := pool.Get().Sub(u2, u1)
+ xEqual := h.Sign() == 0
+
+ t.Add(h, h)
+ // i = 4h²
+ i := pool.Get().Mul(t, t)
+ i.Mod(i, P)
+ // j = 4h³
+ j := pool.Get().Mul(h, i)
+ j.Mod(j, P)
+
+ t.Sub(s2, s1)
+ yEqual := t.Sign() == 0
+ if xEqual && yEqual {
+ c.Double(a, pool)
+ return
+ }
+ r := pool.Get().Add(t, t)
+
+ v := pool.Get().Mul(u1, i)
+ v.Mod(v, P)
+
+ // t4 = 4(s2-s1)²
+ t4 := pool.Get().Mul(r, r)
+ t4.Mod(t4, P)
+ t.Add(v, v)
+ t6 := pool.Get().Sub(t4, j)
+ c.x.Sub(t6, t)
+
+ // Set y = -(2h)³(s1 + s*(x/4h²-u1))
+ // This is also
+ // y = - 2·s1·j - (s2-s1)(2x - 2i·u1) = r(v-x) - 2·s1·j
+ t.Sub(v, c.x) // t7
+ t4.Mul(s1, j) // t8
+ t4.Mod(t4, P)
+ t6.Add(t4, t4) // t9
+ t4.Mul(r, t) // t10
+ t4.Mod(t4, P)
+ c.y.Sub(t4, t6)
+
+ // Set z = 2(u2-u1)·z1·z2 = 2h·z1·z2
+ t.Add(a.z, b.z) // t11
+ t4.Mul(t, t) // t12
+ t4.Mod(t4, P)
+ t.Sub(t4, z1z1) // t13
+ t4.Sub(t, z2z2) // t14
+ c.z.Mul(t4, h)
+ c.z.Mod(c.z, P)
+
+ pool.Put(z1z1)
+ pool.Put(z2z2)
+ pool.Put(u1)
+ pool.Put(u2)
+ pool.Put(t)
+ pool.Put(s1)
+ pool.Put(s2)
+ pool.Put(h)
+ pool.Put(i)
+ pool.Put(j)
+ pool.Put(r)
+ pool.Put(v)
+ pool.Put(t4)
+ pool.Put(t6)
+}
+
+func (c *curvePoint) Double(a *curvePoint, pool *bnPool) {
+ // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
+ A := pool.Get().Mul(a.x, a.x)
+ A.Mod(A, P)
+ B := pool.Get().Mul(a.y, a.y)
+ B.Mod(B, P)
+ C := pool.Get().Mul(B, B)
+ C.Mod(C, P)
+
+ t := pool.Get().Add(a.x, B)
+ t2 := pool.Get().Mul(t, t)
+ t2.Mod(t2, P)
+ t.Sub(t2, A)
+ t2.Sub(t, C)
+ d := pool.Get().Add(t2, t2)
+ t.Add(A, A)
+ e := pool.Get().Add(t, A)
+ f := pool.Get().Mul(e, e)
+ f.Mod(f, P)
+
+ t.Add(d, d)
+ c.x.Sub(f, t)
+
+ t.Add(C, C)
+ t2.Add(t, t)
+ t.Add(t2, t2)
+ c.y.Sub(d, c.x)
+ t2.Mul(e, c.y)
+ t2.Mod(t2, P)
+ c.y.Sub(t2, t)
+
+ t.Mul(a.y, a.z)
+ t.Mod(t, P)
+ c.z.Add(t, t)
+
+ pool.Put(A)
+ pool.Put(B)
+ pool.Put(C)
+ pool.Put(t)
+ pool.Put(t2)
+ pool.Put(d)
+ pool.Put(e)
+ pool.Put(f)
+}
+
+func (c *curvePoint) Mul(a *curvePoint, scalar *big.Int, pool *bnPool) *curvePoint {
+ sum := newCurvePoint(pool)
+ sum.SetInfinity()
+ t := newCurvePoint(pool)
+
+ for i := scalar.BitLen(); i >= 0; i-- {
+ t.Double(sum, pool)
+ if scalar.Bit(i) != 0 {
+ sum.Add(t, a, pool)
+ } else {
+ sum.Set(t)
+ }
+ }
+
+ c.Set(sum)
+ sum.Put(pool)
+ t.Put(pool)
+ return c
+}
+
+func (c *curvePoint) MakeAffine(pool *bnPool) *curvePoint {
+ if words := c.z.Bits(); len(words) == 1 && words[0] == 1 {
+ return c
+ }
+
+ zInv := pool.Get().ModInverse(c.z, P)
+ t := pool.Get().Mul(c.y, zInv)
+ t.Mod(t, P)
+ zInv2 := pool.Get().Mul(zInv, zInv)
+ zInv2.Mod(zInv2, P)
+ c.y.Mul(t, zInv2)
+ c.y.Mod(c.y, P)
+ t.Mul(c.x, zInv2)
+ t.Mod(t, P)
+ c.x.Set(t)
+ c.z.SetInt64(1)
+ c.t.SetInt64(1)
+
+ pool.Put(zInv)
+ pool.Put(t)
+ pool.Put(zInv2)
+
+ return c
+}
+
+func (c *curvePoint) Negative(a *curvePoint) {
+ c.x.Set(a.x)
+ c.y.Neg(a.y)
+ c.z.Set(a.z)
+ c.t.SetInt64(0)
+}
diff --git a/crypto/bn256/example_test.go b/crypto/bn256/example_test.go
new file mode 100644
index 000000000..b2d19807a
--- /dev/null
+++ b/crypto/bn256/example_test.go
@@ -0,0 +1,43 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+import (
+ "crypto/rand"
+)
+
+func ExamplePair() {
+ // This implements the tripartite Diffie-Hellman algorithm from "A One
+ // Round Protocol for Tripartite Diffie-Hellman", A. Joux.
+ // http://www.springerlink.com/content/cddc57yyva0hburb/fulltext.pdf
+
+ // Each of three parties, a, b and c, generate a private value.
+ a, _ := rand.Int(rand.Reader, Order)
+ b, _ := rand.Int(rand.Reader, Order)
+ c, _ := rand.Int(rand.Reader, Order)
+
+ // Then each party calculates g₁ and g₂ times their private value.
+ pa := new(G1).ScalarBaseMult(a)
+ qa := new(G2).ScalarBaseMult(a)
+
+ pb := new(G1).ScalarBaseMult(b)
+ qb := new(G2).ScalarBaseMult(b)
+
+ pc := new(G1).ScalarBaseMult(c)
+ qc := new(G2).ScalarBaseMult(c)
+
+ // Now each party exchanges its public values with the other two and
+ // all parties can calculate the shared key.
+ k1 := Pair(pb, qc)
+ k1.ScalarMult(k1, a)
+
+ k2 := Pair(pc, qa)
+ k2.ScalarMult(k2, b)
+
+ k3 := Pair(pa, qb)
+ k3.ScalarMult(k3, c)
+
+ // k1, k2 and k3 will all be equal.
+}
diff --git a/crypto/bn256/gfp12.go b/crypto/bn256/gfp12.go
new file mode 100644
index 000000000..f084eddf2
--- /dev/null
+++ b/crypto/bn256/gfp12.go
@@ -0,0 +1,200 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+// For details of the algorithms used, see "Multiplication and Squaring on
+// Pairing-Friendly Fields, Devegili et al.
+// http://eprint.iacr.org/2006/471.pdf.
+
+import (
+ "math/big"
+)
+
+// gfP12 implements the field of size p¹² as a quadratic extension of gfP6
+// where ω²=τ.
+type gfP12 struct {
+ x, y *gfP6 // value is xω + y
+}
+
+func newGFp12(pool *bnPool) *gfP12 {
+ return &gfP12{newGFp6(pool), newGFp6(pool)}
+}
+
+func (e *gfP12) String() string {
+ return "(" + e.x.String() + "," + e.y.String() + ")"
+}
+
+func (e *gfP12) Put(pool *bnPool) {
+ e.x.Put(pool)
+ e.y.Put(pool)
+}
+
+func (e *gfP12) Set(a *gfP12) *gfP12 {
+ e.x.Set(a.x)
+ e.y.Set(a.y)
+ return e
+}
+
+func (e *gfP12) SetZero() *gfP12 {
+ e.x.SetZero()
+ e.y.SetZero()
+ return e
+}
+
+func (e *gfP12) SetOne() *gfP12 {
+ e.x.SetZero()
+ e.y.SetOne()
+ return e
+}
+
+func (e *gfP12) Minimal() {
+ e.x.Minimal()
+ e.y.Minimal()
+}
+
+func (e *gfP12) IsZero() bool {
+ e.Minimal()
+ return e.x.IsZero() && e.y.IsZero()
+}
+
+func (e *gfP12) IsOne() bool {
+ e.Minimal()
+ return e.x.IsZero() && e.y.IsOne()
+}
+
+func (e *gfP12) Conjugate(a *gfP12) *gfP12 {
+ e.x.Negative(a.x)
+ e.y.Set(a.y)
+ return a
+}
+
+func (e *gfP12) Negative(a *gfP12) *gfP12 {
+ e.x.Negative(a.x)
+ e.y.Negative(a.y)
+ return e
+}
+
+// Frobenius computes (xω+y)^p = x^p ω·ξ^((p-1)/6) + y^p
+func (e *gfP12) Frobenius(a *gfP12, pool *bnPool) *gfP12 {
+ e.x.Frobenius(a.x, pool)
+ e.y.Frobenius(a.y, pool)
+ e.x.MulScalar(e.x, xiToPMinus1Over6, pool)
+ return e
+}
+
+// FrobeniusP2 computes (xω+y)^p² = x^p² ω·ξ^((p²-1)/6) + y^p²
+func (e *gfP12) FrobeniusP2(a *gfP12, pool *bnPool) *gfP12 {
+ e.x.FrobeniusP2(a.x)
+ e.x.MulGFP(e.x, xiToPSquaredMinus1Over6)
+ e.y.FrobeniusP2(a.y)
+ return e
+}
+
+func (e *gfP12) Add(a, b *gfP12) *gfP12 {
+ e.x.Add(a.x, b.x)
+ e.y.Add(a.y, b.y)
+ return e
+}
+
+func (e *gfP12) Sub(a, b *gfP12) *gfP12 {
+ e.x.Sub(a.x, b.x)
+ e.y.Sub(a.y, b.y)
+ return e
+}
+
+func (e *gfP12) Mul(a, b *gfP12, pool *bnPool) *gfP12 {
+ tx := newGFp6(pool)
+ tx.Mul(a.x, b.y, pool)
+ t := newGFp6(pool)
+ t.Mul(b.x, a.y, pool)
+ tx.Add(tx, t)
+
+ ty := newGFp6(pool)
+ ty.Mul(a.y, b.y, pool)
+ t.Mul(a.x, b.x, pool)
+ t.MulTau(t, pool)
+ e.y.Add(ty, t)
+ e.x.Set(tx)
+
+ tx.Put(pool)
+ ty.Put(pool)
+ t.Put(pool)
+ return e
+}
+
+func (e *gfP12) MulScalar(a *gfP12, b *gfP6, pool *bnPool) *gfP12 {
+ e.x.Mul(e.x, b, pool)
+ e.y.Mul(e.y, b, pool)
+ return e
+}
+
+func (c *gfP12) Exp(a *gfP12, power *big.Int, pool *bnPool) *gfP12 {
+ sum := newGFp12(pool)
+ sum.SetOne()
+ t := newGFp12(pool)
+
+ for i := power.BitLen() - 1; i >= 0; i-- {
+ t.Square(sum, pool)
+ if power.Bit(i) != 0 {
+ sum.Mul(t, a, pool)
+ } else {
+ sum.Set(t)
+ }
+ }
+
+ c.Set(sum)
+
+ sum.Put(pool)
+ t.Put(pool)
+
+ return c
+}
+
+func (e *gfP12) Square(a *gfP12, pool *bnPool) *gfP12 {
+ // Complex squaring algorithm
+ v0 := newGFp6(pool)
+ v0.Mul(a.x, a.y, pool)
+
+ t := newGFp6(pool)
+ t.MulTau(a.x, pool)
+ t.Add(a.y, t)
+ ty := newGFp6(pool)
+ ty.Add(a.x, a.y)
+ ty.Mul(ty, t, pool)
+ ty.Sub(ty, v0)
+ t.MulTau(v0, pool)
+ ty.Sub(ty, t)
+
+ e.y.Set(ty)
+ e.x.Double(v0)
+
+ v0.Put(pool)
+ t.Put(pool)
+ ty.Put(pool)
+
+ return e
+}
+
+func (e *gfP12) Invert(a *gfP12, pool *bnPool) *gfP12 {
+ // See "Implementing cryptographic pairings", M. Scott, section 3.2.
+ // ftp://136.206.11.249/pub/crypto/pairings.pdf
+ t1 := newGFp6(pool)
+ t2 := newGFp6(pool)
+
+ t1.Square(a.x, pool)
+ t2.Square(a.y, pool)
+ t1.MulTau(t1, pool)
+ t1.Sub(t2, t1)
+ t2.Invert(t1, pool)
+
+ e.x.Negative(a.x)
+ e.y.Set(a.y)
+ e.MulScalar(e, t2, pool)
+
+ t1.Put(pool)
+ t2.Put(pool)
+
+ return e
+}
diff --git a/crypto/bn256/gfp2.go b/crypto/bn256/gfp2.go
new file mode 100644
index 000000000..3981f6cb4
--- /dev/null
+++ b/crypto/bn256/gfp2.go
@@ -0,0 +1,227 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+// For details of the algorithms used, see "Multiplication and Squaring on
+// Pairing-Friendly Fields, Devegili et al.
+// http://eprint.iacr.org/2006/471.pdf.
+
+import (
+ "math/big"
+)
+
+// gfP2 implements a field of size p² as a quadratic extension of the base
+// field where i²=-1.
+type gfP2 struct {
+ x, y *big.Int // value is xi+y.
+}
+
+func newGFp2(pool *bnPool) *gfP2 {
+ return &gfP2{pool.Get(), pool.Get()}
+}
+
+func (e *gfP2) String() string {
+ x := new(big.Int).Mod(e.x, P)
+ y := new(big.Int).Mod(e.y, P)
+ return "(" + x.String() + "," + y.String() + ")"
+}
+
+func (e *gfP2) Put(pool *bnPool) {
+ pool.Put(e.x)
+ pool.Put(e.y)
+}
+
+func (e *gfP2) Set(a *gfP2) *gfP2 {
+ e.x.Set(a.x)
+ e.y.Set(a.y)
+ return e
+}
+
+func (e *gfP2) SetZero() *gfP2 {
+ e.x.SetInt64(0)
+ e.y.SetInt64(0)
+ return e
+}
+
+func (e *gfP2) SetOne() *gfP2 {
+ e.x.SetInt64(0)
+ e.y.SetInt64(1)
+ return e
+}
+
+func (e *gfP2) Minimal() {
+ if e.x.Sign() < 0 || e.x.Cmp(P) >= 0 {
+ e.x.Mod(e.x, P)
+ }
+ if e.y.Sign() < 0 || e.y.Cmp(P) >= 0 {
+ e.y.Mod(e.y, P)
+ }
+}
+
+func (e *gfP2) IsZero() bool {
+ return e.x.Sign() == 0 && e.y.Sign() == 0
+}
+
+func (e *gfP2) IsOne() bool {
+ if e.x.Sign() != 0 {
+ return false
+ }
+ words := e.y.Bits()
+ return len(words) == 1 && words[0] == 1
+}
+
+func (e *gfP2) Conjugate(a *gfP2) *gfP2 {
+ e.y.Set(a.y)
+ e.x.Neg(a.x)
+ return e
+}
+
+func (e *gfP2) Negative(a *gfP2) *gfP2 {
+ e.x.Neg(a.x)
+ e.y.Neg(a.y)
+ return e
+}
+
+func (e *gfP2) Add(a, b *gfP2) *gfP2 {
+ e.x.Add(a.x, b.x)
+ e.y.Add(a.y, b.y)
+ return e
+}
+
+func (e *gfP2) Sub(a, b *gfP2) *gfP2 {
+ e.x.Sub(a.x, b.x)
+ e.y.Sub(a.y, b.y)
+ return e
+}
+
+func (e *gfP2) Double(a *gfP2) *gfP2 {
+ e.x.Lsh(a.x, 1)
+ e.y.Lsh(a.y, 1)
+ return e
+}
+
+func (c *gfP2) Exp(a *gfP2, power *big.Int, pool *bnPool) *gfP2 {
+ sum := newGFp2(pool)
+ sum.SetOne()
+ t := newGFp2(pool)
+
+ for i := power.BitLen() - 1; i >= 0; i-- {
+ t.Square(sum, pool)
+ if power.Bit(i) != 0 {
+ sum.Mul(t, a, pool)
+ } else {
+ sum.Set(t)
+ }
+ }
+
+ c.Set(sum)
+
+ sum.Put(pool)
+ t.Put(pool)
+
+ return c
+}
+
+// See "Multiplication and Squaring in Pairing-Friendly Fields",
+// http://eprint.iacr.org/2006/471.pdf
+func (e *gfP2) Mul(a, b *gfP2, pool *bnPool) *gfP2 {
+ tx := pool.Get().Mul(a.x, b.y)
+ t := pool.Get().Mul(b.x, a.y)
+ tx.Add(tx, t)
+ tx.Mod(tx, P)
+
+ ty := pool.Get().Mul(a.y, b.y)
+ t.Mul(a.x, b.x)
+ ty.Sub(ty, t)
+ e.y.Mod(ty, P)
+ e.x.Set(tx)
+
+ pool.Put(tx)
+ pool.Put(ty)
+ pool.Put(t)
+
+ return e
+}
+
+func (e *gfP2) MulScalar(a *gfP2, b *big.Int) *gfP2 {
+ e.x.Mul(a.x, b)
+ e.y.Mul(a.y, b)
+ return e
+}
+
+// MulXi sets e=ξa where ξ=i+9 and then returns e.
+func (e *gfP2) MulXi(a *gfP2, pool *bnPool) *gfP2 {
+ // (xi+y)(i+3) = (9x+y)i+(9y-x)
+ tx := pool.Get().Lsh(a.x, 3)
+ tx.Add(tx, a.x)
+ tx.Add(tx, a.y)
+
+ ty := pool.Get().Lsh(a.y, 3)
+ ty.Add(ty, a.y)
+ ty.Sub(ty, a.x)
+
+ e.x.Set(tx)
+ e.y.Set(ty)
+
+ pool.Put(tx)
+ pool.Put(ty)
+
+ return e
+}
+
+func (e *gfP2) Square(a *gfP2, pool *bnPool) *gfP2 {
+ // Complex squaring algorithm:
+ // (xi+b)² = (x+y)(y-x) + 2*i*x*y
+ t1 := pool.Get().Sub(a.y, a.x)
+ t2 := pool.Get().Add(a.x, a.y)
+ ty := pool.Get().Mul(t1, t2)
+ ty.Mod(ty, P)
+
+ t1.Mul(a.x, a.y)
+ t1.Lsh(t1, 1)
+
+ e.x.Mod(t1, P)
+ e.y.Set(ty)
+
+ pool.Put(t1)
+ pool.Put(t2)
+ pool.Put(ty)
+
+ return e
+}
+
+func (e *gfP2) Invert(a *gfP2, pool *bnPool) *gfP2 {
+ // See "Implementing cryptographic pairings", M. Scott, section 3.2.
+ // ftp://136.206.11.249/pub/crypto/pairings.pdf
+ t := pool.Get()
+ t.Mul(a.y, a.y)
+ t2 := pool.Get()
+ t2.Mul(a.x, a.x)
+ t.Add(t, t2)
+
+ inv := pool.Get()
+ inv.ModInverse(t, P)
+
+ e.x.Neg(a.x)
+ e.x.Mul(e.x, inv)
+ e.x.Mod(e.x, P)
+
+ e.y.Mul(a.y, inv)
+ e.y.Mod(e.y, P)
+
+ pool.Put(t)
+ pool.Put(t2)
+ pool.Put(inv)
+
+ return e
+}
+
+func (e *gfP2) Real() *big.Int {
+ return e.x
+}
+
+func (e *gfP2) Imag() *big.Int {
+ return e.y
+}
diff --git a/crypto/bn256/gfp6.go b/crypto/bn256/gfp6.go
new file mode 100644
index 000000000..8fd777d52
--- /dev/null
+++ b/crypto/bn256/gfp6.go
@@ -0,0 +1,296 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+// For details of the algorithms used, see "Multiplication and Squaring on
+// Pairing-Friendly Fields, Devegili et al.
+// http://eprint.iacr.org/2006/471.pdf.
+
+import (
+ "math/big"
+)
+
+// gfP6 implements the field of size p⁶ as a cubic extension of gfP2 where τ³=ξ
+// and ξ=i+9.
+type gfP6 struct {
+ x, y, z *gfP2 // value is xτ² + yτ + z
+}
+
+func newGFp6(pool *bnPool) *gfP6 {
+ return &gfP6{newGFp2(pool), newGFp2(pool), newGFp2(pool)}
+}
+
+func (e *gfP6) String() string {
+ return "(" + e.x.String() + "," + e.y.String() + "," + e.z.String() + ")"
+}
+
+func (e *gfP6) Put(pool *bnPool) {
+ e.x.Put(pool)
+ e.y.Put(pool)
+ e.z.Put(pool)
+}
+
+func (e *gfP6) Set(a *gfP6) *gfP6 {
+ e.x.Set(a.x)
+ e.y.Set(a.y)
+ e.z.Set(a.z)
+ return e
+}
+
+func (e *gfP6) SetZero() *gfP6 {
+ e.x.SetZero()
+ e.y.SetZero()
+ e.z.SetZero()
+ return e
+}
+
+func (e *gfP6) SetOne() *gfP6 {
+ e.x.SetZero()
+ e.y.SetZero()
+ e.z.SetOne()
+ return e
+}
+
+func (e *gfP6) Minimal() {
+ e.x.Minimal()
+ e.y.Minimal()
+ e.z.Minimal()
+}
+
+func (e *gfP6) IsZero() bool {
+ return e.x.IsZero() && e.y.IsZero() && e.z.IsZero()
+}
+
+func (e *gfP6) IsOne() bool {
+ return e.x.IsZero() && e.y.IsZero() && e.z.IsOne()
+}
+
+func (e *gfP6) Negative(a *gfP6) *gfP6 {
+ e.x.Negative(a.x)
+ e.y.Negative(a.y)
+ e.z.Negative(a.z)
+ return e
+}
+
+func (e *gfP6) Frobenius(a *gfP6, pool *bnPool) *gfP6 {
+ e.x.Conjugate(a.x)
+ e.y.Conjugate(a.y)
+ e.z.Conjugate(a.z)
+
+ e.x.Mul(e.x, xiTo2PMinus2Over3, pool)
+ e.y.Mul(e.y, xiToPMinus1Over3, pool)
+ return e
+}
+
+// FrobeniusP2 computes (xτ²+yτ+z)^(p²) = xτ^(2p²) + yτ^(p²) + z
+func (e *gfP6) FrobeniusP2(a *gfP6) *gfP6 {
+ // τ^(2p²) = τ²τ^(2p²-2) = τ²ξ^((2p²-2)/3)
+ e.x.MulScalar(a.x, xiTo2PSquaredMinus2Over3)
+ // τ^(p²) = ττ^(p²-1) = τξ^((p²-1)/3)
+ e.y.MulScalar(a.y, xiToPSquaredMinus1Over3)
+ e.z.Set(a.z)
+ return e
+}
+
+func (e *gfP6) Add(a, b *gfP6) *gfP6 {
+ e.x.Add(a.x, b.x)
+ e.y.Add(a.y, b.y)
+ e.z.Add(a.z, b.z)
+ return e
+}
+
+func (e *gfP6) Sub(a, b *gfP6) *gfP6 {
+ e.x.Sub(a.x, b.x)
+ e.y.Sub(a.y, b.y)
+ e.z.Sub(a.z, b.z)
+ return e
+}
+
+func (e *gfP6) Double(a *gfP6) *gfP6 {
+ e.x.Double(a.x)
+ e.y.Double(a.y)
+ e.z.Double(a.z)
+ return e
+}
+
+func (e *gfP6) Mul(a, b *gfP6, pool *bnPool) *gfP6 {
+ // "Multiplication and Squaring on Pairing-Friendly Fields"
+ // Section 4, Karatsuba method.
+ // http://eprint.iacr.org/2006/471.pdf
+
+ v0 := newGFp2(pool)
+ v0.Mul(a.z, b.z, pool)
+ v1 := newGFp2(pool)
+ v1.Mul(a.y, b.y, pool)
+ v2 := newGFp2(pool)
+ v2.Mul(a.x, b.x, pool)
+
+ t0 := newGFp2(pool)
+ t0.Add(a.x, a.y)
+ t1 := newGFp2(pool)
+ t1.Add(b.x, b.y)
+ tz := newGFp2(pool)
+ tz.Mul(t0, t1, pool)
+
+ tz.Sub(tz, v1)
+ tz.Sub(tz, v2)
+ tz.MulXi(tz, pool)
+ tz.Add(tz, v0)
+
+ t0.Add(a.y, a.z)
+ t1.Add(b.y, b.z)
+ ty := newGFp2(pool)
+ ty.Mul(t0, t1, pool)
+ ty.Sub(ty, v0)
+ ty.Sub(ty, v1)
+ t0.MulXi(v2, pool)
+ ty.Add(ty, t0)
+
+ t0.Add(a.x, a.z)
+ t1.Add(b.x, b.z)
+ tx := newGFp2(pool)
+ tx.Mul(t0, t1, pool)
+ tx.Sub(tx, v0)
+ tx.Add(tx, v1)
+ tx.Sub(tx, v2)
+
+ e.x.Set(tx)
+ e.y.Set(ty)
+ e.z.Set(tz)
+
+ t0.Put(pool)
+ t1.Put(pool)
+ tx.Put(pool)
+ ty.Put(pool)
+ tz.Put(pool)
+ v0.Put(pool)
+ v1.Put(pool)
+ v2.Put(pool)
+ return e
+}
+
+func (e *gfP6) MulScalar(a *gfP6, b *gfP2, pool *bnPool) *gfP6 {
+ e.x.Mul(a.x, b, pool)
+ e.y.Mul(a.y, b, pool)
+ e.z.Mul(a.z, b, pool)
+ return e
+}
+
+func (e *gfP6) MulGFP(a *gfP6, b *big.Int) *gfP6 {
+ e.x.MulScalar(a.x, b)
+ e.y.MulScalar(a.y, b)
+ e.z.MulScalar(a.z, b)
+ return e
+}
+
+// MulTau computes τ·(aτ²+bτ+c) = bτ²+cτ+aξ
+func (e *gfP6) MulTau(a *gfP6, pool *bnPool) {
+ tz := newGFp2(pool)
+ tz.MulXi(a.x, pool)
+ ty := newGFp2(pool)
+ ty.Set(a.y)
+ e.y.Set(a.z)
+ e.x.Set(ty)
+ e.z.Set(tz)
+ tz.Put(pool)
+ ty.Put(pool)
+}
+
+func (e *gfP6) Square(a *gfP6, pool *bnPool) *gfP6 {
+ v0 := newGFp2(pool).Square(a.z, pool)
+ v1 := newGFp2(pool).Square(a.y, pool)
+ v2 := newGFp2(pool).Square(a.x, pool)
+
+ c0 := newGFp2(pool).Add(a.x, a.y)
+ c0.Square(c0, pool)
+ c0.Sub(c0, v1)
+ c0.Sub(c0, v2)
+ c0.MulXi(c0, pool)
+ c0.Add(c0, v0)
+
+ c1 := newGFp2(pool).Add(a.y, a.z)
+ c1.Square(c1, pool)
+ c1.Sub(c1, v0)
+ c1.Sub(c1, v1)
+ xiV2 := newGFp2(pool).MulXi(v2, pool)
+ c1.Add(c1, xiV2)
+
+ c2 := newGFp2(pool).Add(a.x, a.z)
+ c2.Square(c2, pool)
+ c2.Sub(c2, v0)
+ c2.Add(c2, v1)
+ c2.Sub(c2, v2)
+
+ e.x.Set(c2)
+ e.y.Set(c1)
+ e.z.Set(c0)
+
+ v0.Put(pool)
+ v1.Put(pool)
+ v2.Put(pool)
+ c0.Put(pool)
+ c1.Put(pool)
+ c2.Put(pool)
+ xiV2.Put(pool)
+
+ return e
+}
+
+func (e *gfP6) Invert(a *gfP6, pool *bnPool) *gfP6 {
+ // See "Implementing cryptographic pairings", M. Scott, section 3.2.
+ // ftp://136.206.11.249/pub/crypto/pairings.pdf
+
+ // Here we can give a short explanation of how it works: let j be a cubic root of
+ // unity in GF(p²) so that 1+j+j²=0.
+ // Then (xτ² + yτ + z)(xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
+ // = (xτ² + yτ + z)(Cτ²+Bτ+A)
+ // = (x³ξ²+y³ξ+z³-3ξxyz) = F is an element of the base field (the norm).
+ //
+ // On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
+ // = τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)
+ //
+ // So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)
+ t1 := newGFp2(pool)
+
+ A := newGFp2(pool)
+ A.Square(a.z, pool)
+ t1.Mul(a.x, a.y, pool)
+ t1.MulXi(t1, pool)
+ A.Sub(A, t1)
+
+ B := newGFp2(pool)
+ B.Square(a.x, pool)
+ B.MulXi(B, pool)
+ t1.Mul(a.y, a.z, pool)
+ B.Sub(B, t1)
+
+ C := newGFp2(pool)
+ C.Square(a.y, pool)
+ t1.Mul(a.x, a.z, pool)
+ C.Sub(C, t1)
+
+ F := newGFp2(pool)
+ F.Mul(C, a.y, pool)
+ F.MulXi(F, pool)
+ t1.Mul(A, a.z, pool)
+ F.Add(F, t1)
+ t1.Mul(B, a.x, pool)
+ t1.MulXi(t1, pool)
+ F.Add(F, t1)
+
+ F.Invert(F, pool)
+
+ e.x.Mul(C, F, pool)
+ e.y.Mul(B, F, pool)
+ e.z.Mul(A, F, pool)
+
+ t1.Put(pool)
+ A.Put(pool)
+ B.Put(pool)
+ C.Put(pool)
+ F.Put(pool)
+
+ return e
+}
diff --git a/crypto/bn256/main_test.go b/crypto/bn256/main_test.go
new file mode 100644
index 000000000..0230f1b19
--- /dev/null
+++ b/crypto/bn256/main_test.go
@@ -0,0 +1,71 @@
+package bn256
+
+import (
+ "testing"
+
+ "crypto/rand"
+)
+
+func TestRandomG2Marshal(t *testing.T) {
+ for i := 0; i < 10; i++ {
+ n, g2, err := RandomG2(rand.Reader)
+ if err != nil {
+ t.Error(err)
+ continue
+ }
+ t.Logf("%d: %x\n", n, g2.Marshal())
+ }
+}
+
+func TestPairings(t *testing.T) {
+ a1 := new(G1).ScalarBaseMult(bigFromBase10("1"))
+ a2 := new(G1).ScalarBaseMult(bigFromBase10("2"))
+ a37 := new(G1).ScalarBaseMult(bigFromBase10("37"))
+ an1 := new(G1).ScalarBaseMult(bigFromBase10("21888242871839275222246405745257275088548364400416034343698204186575808495616"))
+
+ b0 := new(G2).ScalarBaseMult(bigFromBase10("0"))
+ b1 := new(G2).ScalarBaseMult(bigFromBase10("1"))
+ b2 := new(G2).ScalarBaseMult(bigFromBase10("2"))
+ b27 := new(G2).ScalarBaseMult(bigFromBase10("27"))
+ b999 := new(G2).ScalarBaseMult(bigFromBase10("999"))
+ bn1 := new(G2).ScalarBaseMult(bigFromBase10("21888242871839275222246405745257275088548364400416034343698204186575808495616"))
+
+ p1 := Pair(a1, b1)
+ pn1 := Pair(a1, bn1)
+ np1 := Pair(an1, b1)
+ if pn1.String() != np1.String() {
+ t.Error("Pairing mismatch: e(a, -b) != e(-a, b)")
+ }
+ if !PairingCheck([]*G1{a1, an1}, []*G2{b1, b1}) {
+ t.Error("MultiAte check gave false negative!")
+ }
+ p0 := new(GT).Add(p1, pn1)
+ p0_2 := Pair(a1, b0)
+ if p0.String() != p0_2.String() {
+ t.Error("Pairing mismatch: e(a, b) * e(a, -b) != 1")
+ }
+ p0_3 := new(GT).ScalarMult(p1, bigFromBase10("21888242871839275222246405745257275088548364400416034343698204186575808495617"))
+ if p0.String() != p0_3.String() {
+ t.Error("Pairing mismatch: e(a, b) has wrong order")
+ }
+ p2 := Pair(a2, b1)
+ p2_2 := Pair(a1, b2)
+ p2_3 := new(GT).ScalarMult(p1, bigFromBase10("2"))
+ if p2.String() != p2_2.String() {
+ t.Error("Pairing mismatch: e(a, b * 2) != e(a * 2, b)")
+ }
+ if p2.String() != p2_3.String() {
+ t.Error("Pairing mismatch: e(a, b * 2) != e(a, b) ** 2")
+ }
+ if p2.String() == p1.String() {
+ t.Error("Pairing is degenerate!")
+ }
+ if PairingCheck([]*G1{a1, a1}, []*G2{b1, b1}) {
+ t.Error("MultiAte check gave false positive!")
+ }
+ p999 := Pair(a37, b27)
+ p999_2 := Pair(a1, b999)
+ if p999.String() != p999_2.String() {
+ t.Error("Pairing mismatch: e(a * 37, b * 27) != e(a, b * 999)")
+ }
+}
diff --git a/crypto/bn256/optate.go b/crypto/bn256/optate.go
new file mode 100644
index 000000000..24e0bbc13
--- /dev/null
+++ b/crypto/bn256/optate.go
@@ -0,0 +1,398 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+func lineFunctionAdd(r, p *twistPoint, q *curvePoint, r2 *gfP2, pool *bnPool) (a, b, c *gfP2, rOut *twistPoint) {
+ // See the mixed addition algorithm from "Faster Computation of the
+ // Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
+
+ B := newGFp2(pool).Mul(p.x, r.t, pool)
+
+ D := newGFp2(pool).Add(p.y, r.z)
+ D.Square(D, pool)
+ D.Sub(D, r2)
+ D.Sub(D, r.t)
+ D.Mul(D, r.t, pool)
+
+ H := newGFp2(pool).Sub(B, r.x)
+ I := newGFp2(pool).Square(H, pool)
+
+ E := newGFp2(pool).Add(I, I)
+ E.Add(E, E)
+
+ J := newGFp2(pool).Mul(H, E, pool)
+
+ L1 := newGFp2(pool).Sub(D, r.y)
+ L1.Sub(L1, r.y)
+
+ V := newGFp2(pool).Mul(r.x, E, pool)
+
+ rOut = newTwistPoint(pool)
+ rOut.x.Square(L1, pool)
+ rOut.x.Sub(rOut.x, J)
+ rOut.x.Sub(rOut.x, V)
+ rOut.x.Sub(rOut.x, V)
+
+ rOut.z.Add(r.z, H)
+ rOut.z.Square(rOut.z, pool)
+ rOut.z.Sub(rOut.z, r.t)
+ rOut.z.Sub(rOut.z, I)
+
+ t := newGFp2(pool).Sub(V, rOut.x)
+ t.Mul(t, L1, pool)
+ t2 := newGFp2(pool).Mul(r.y, J, pool)
+ t2.Add(t2, t2)
+ rOut.y.Sub(t, t2)
+
+ rOut.t.Square(rOut.z, pool)
+
+ t.Add(p.y, rOut.z)
+ t.Square(t, pool)
+ t.Sub(t, r2)
+ t.Sub(t, rOut.t)
+
+ t2.Mul(L1, p.x, pool)
+ t2.Add(t2, t2)
+ a = newGFp2(pool)
+ a.Sub(t2, t)
+
+ c = newGFp2(pool)
+ c.MulScalar(rOut.z, q.y)
+ c.Add(c, c)
+
+ b = newGFp2(pool)
+ b.SetZero()
+ b.Sub(b, L1)
+ b.MulScalar(b, q.x)
+ b.Add(b, b)
+
+ B.Put(pool)
+ D.Put(pool)
+ H.Put(pool)
+ I.Put(pool)
+ E.Put(pool)
+ J.Put(pool)
+ L1.Put(pool)
+ V.Put(pool)
+ t.Put(pool)
+ t2.Put(pool)
+
+ return
+}
+
+func lineFunctionDouble(r *twistPoint, q *curvePoint, pool *bnPool) (a, b, c *gfP2, rOut *twistPoint) {
+ // See the doubling algorithm for a=0 from "Faster Computation of the
+ // Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
+
+ A := newGFp2(pool).Square(r.x, pool)
+ B := newGFp2(pool).Square(r.y, pool)
+ C := newGFp2(pool).Square(B, pool)
+
+ D := newGFp2(pool).Add(r.x, B)
+ D.Square(D, pool)
+ D.Sub(D, A)
+ D.Sub(D, C)
+ D.Add(D, D)
+
+ E := newGFp2(pool).Add(A, A)
+ E.Add(E, A)
+
+ G := newGFp2(pool).Square(E, pool)
+
+ rOut = newTwistPoint(pool)
+ rOut.x.Sub(G, D)
+ rOut.x.Sub(rOut.x, D)
+
+ rOut.z.Add(r.y, r.z)
+ rOut.z.Square(rOut.z, pool)
+ rOut.z.Sub(rOut.z, B)
+ rOut.z.Sub(rOut.z, r.t)
+
+ rOut.y.Sub(D, rOut.x)
+ rOut.y.Mul(rOut.y, E, pool)
+ t := newGFp2(pool).Add(C, C)
+ t.Add(t, t)
+ t.Add(t, t)
+ rOut.y.Sub(rOut.y, t)
+
+ rOut.t.Square(rOut.z, pool)
+
+ t.Mul(E, r.t, pool)
+ t.Add(t, t)
+ b = newGFp2(pool)
+ b.SetZero()
+ b.Sub(b, t)
+ b.MulScalar(b, q.x)
+
+ a = newGFp2(pool)
+ a.Add(r.x, E)
+ a.Square(a, pool)
+ a.Sub(a, A)
+ a.Sub(a, G)
+ t.Add(B, B)
+ t.Add(t, t)
+ a.Sub(a, t)
+
+ c = newGFp2(pool)
+ c.Mul(rOut.z, r.t, pool)
+ c.Add(c, c)
+ c.MulScalar(c, q.y)
+
+ A.Put(pool)
+ B.Put(pool)
+ C.Put(pool)
+ D.Put(pool)
+ E.Put(pool)
+ G.Put(pool)
+ t.Put(pool)
+
+ return
+}
+
+func mulLine(ret *gfP12, a, b, c *gfP2, pool *bnPool) {
+ a2 := newGFp6(pool)
+ a2.x.SetZero()
+ a2.y.Set(a)
+ a2.z.Set(b)
+ a2.Mul(a2, ret.x, pool)
+ t3 := newGFp6(pool).MulScalar(ret.y, c, pool)
+
+ t := newGFp2(pool)
+ t.Add(b, c)
+ t2 := newGFp6(pool)
+ t2.x.SetZero()
+ t2.y.Set(a)
+ t2.z.Set(t)
+ ret.x.Add(ret.x, ret.y)
+
+ ret.y.Set(t3)
+
+ ret.x.Mul(ret.x, t2, pool)
+ ret.x.Sub(ret.x, a2)
+ ret.x.Sub(ret.x, ret.y)
+ a2.MulTau(a2, pool)
+ ret.y.Add(ret.y, a2)
+
+ a2.Put(pool)
+ t3.Put(pool)
+ t2.Put(pool)
+ t.Put(pool)
+}
+
+// sixuPlus2NAF is 6u+2 in non-adjacent form.
+var sixuPlus2NAF = []int8{0, 0, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 1, 0,
+ 0, 1, 1, 0, -1, 0, 0, 1, 0, -1, 0, 0, 0, 0, 1, 1,
+ 1, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1,
+ 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0, 1, 1}
+
+// miller implements the Miller loop for calculating the Optimal Ate pairing.
+// See algorithm 1 from http://cryptojedi.org/papers/dclxvi-20100714.pdf
+func miller(q *twistPoint, p *curvePoint, pool *bnPool) *gfP12 {
+ ret := newGFp12(pool)
+ ret.SetOne()
+
+ aAffine := newTwistPoint(pool)
+ aAffine.Set(q)
+ aAffine.MakeAffine(pool)
+
+ bAffine := newCurvePoint(pool)
+ bAffine.Set(p)
+ bAffine.MakeAffine(pool)
+
+ minusA := newTwistPoint(pool)
+ minusA.Negative(aAffine, pool)
+
+ r := newTwistPoint(pool)
+ r.Set(aAffine)
+
+ r2 := newGFp2(pool)
+ r2.Square(aAffine.y, pool)
+
+ for i := len(sixuPlus2NAF) - 1; i > 0; i-- {
+ a, b, c, newR := lineFunctionDouble(r, bAffine, pool)
+ if i != len(sixuPlus2NAF)-1 {
+ ret.Square(ret, pool)
+ }
+
+ mulLine(ret, a, b, c, pool)
+ a.Put(pool)
+ b.Put(pool)
+ c.Put(pool)
+ r.Put(pool)
+ r = newR
+
+ switch sixuPlus2NAF[i-1] {
+ case 1:
+ a, b, c, newR = lineFunctionAdd(r, aAffine, bAffine, r2, pool)
+ case -1:
+ a, b, c, newR = lineFunctionAdd(r, minusA, bAffine, r2, pool)
+ default:
+ continue
+ }
+
+ mulLine(ret, a, b, c, pool)
+ a.Put(pool)
+ b.Put(pool)
+ c.Put(pool)
+ r.Put(pool)
+ r = newR
+ }
+
+ // In order to calculate Q1 we have to convert q from the sextic twist
+ // to the full GF(p^12) group, apply the Frobenius there, and convert
+ // back.
+ //
+ // The twist isomorphism is (x', y') -> (xω², yω³). If we consider just
+ // x for a moment, then after applying the Frobenius, we have x̄ω^(2p)
+ // where x̄ is the conjugate of x. If we are going to apply the inverse
+ // isomorphism we need a value with a single coefficient of ω² so we
+ // rewrite this as x̄ω^(2p-2)ω². ξ⁶ = ω and, due to the construction of
+ // p, 2p-2 is a multiple of six. Therefore we can rewrite as
+ // x̄ξ^((p-1)/3)ω² and applying the inverse isomorphism eliminates the
+ // ω².
+ //
+ // A similar argument can be made for the y value.
+
+ q1 := newTwistPoint(pool)
+ q1.x.Conjugate(aAffine.x)
+ q1.x.Mul(q1.x, xiToPMinus1Over3, pool)
+ q1.y.Conjugate(aAffine.y)
+ q1.y.Mul(q1.y, xiToPMinus1Over2, pool)
+ q1.z.SetOne()
+ q1.t.SetOne()
+
+ // For Q2 we are applying the p² Frobenius. The two conjugations cancel
+ // out and we are left only with the factors from the isomorphism. In
+ // the case of x, we end up with a pure number which is why
+ // xiToPSquaredMinus1Over3 is ∈ GF(p). With y we get a factor of -1. We
+ // ignore this to end up with -Q2.
+
+ minusQ2 := newTwistPoint(pool)
+ minusQ2.x.MulScalar(aAffine.x, xiToPSquaredMinus1Over3)
+ minusQ2.y.Set(aAffine.y)
+ minusQ2.z.SetOne()
+ minusQ2.t.SetOne()
+
+ r2.Square(q1.y, pool)
+ a, b, c, newR := lineFunctionAdd(r, q1, bAffine, r2, pool)
+ mulLine(ret, a, b, c, pool)
+ a.Put(pool)
+ b.Put(pool)
+ c.Put(pool)
+ r.Put(pool)
+ r = newR
+
+ r2.Square(minusQ2.y, pool)
+ a, b, c, newR = lineFunctionAdd(r, minusQ2, bAffine, r2, pool)
+ mulLine(ret, a, b, c, pool)
+ a.Put(pool)
+ b.Put(pool)
+ c.Put(pool)
+ r.Put(pool)
+ r = newR
+
+ aAffine.Put(pool)
+ bAffine.Put(pool)
+ minusA.Put(pool)
+ r.Put(pool)
+ r2.Put(pool)
+
+ return ret
+}
+
+// finalExponentiation computes the (p¹²-1)/Order-th power of an element of
+// GF(p¹²) to obtain an element of GT (steps 13-15 of algorithm 1 from
+// http://cryptojedi.org/papers/dclxvi-20100714.pdf)
+func finalExponentiation(in *gfP12, pool *bnPool) *gfP12 {
+ t1 := newGFp12(pool)
+
+ // This is the p^6-Frobenius
+ t1.x.Negative(in.x)
+ t1.y.Set(in.y)
+
+ inv := newGFp12(pool)
+ inv.Invert(in, pool)
+ t1.Mul(t1, inv, pool)
+
+ t2 := newGFp12(pool).FrobeniusP2(t1, pool)
+ t1.Mul(t1, t2, pool)
+
+ fp := newGFp12(pool).Frobenius(t1, pool)
+ fp2 := newGFp12(pool).FrobeniusP2(t1, pool)
+ fp3 := newGFp12(pool).Frobenius(fp2, pool)
+
+ fu, fu2, fu3 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
+ fu.Exp(t1, u, pool)
+ fu2.Exp(fu, u, pool)
+ fu3.Exp(fu2, u, pool)
+
+ y3 := newGFp12(pool).Frobenius(fu, pool)
+ fu2p := newGFp12(pool).Frobenius(fu2, pool)
+ fu3p := newGFp12(pool).Frobenius(fu3, pool)
+ y2 := newGFp12(pool).FrobeniusP2(fu2, pool)
+
+ y0 := newGFp12(pool)
+ y0.Mul(fp, fp2, pool)
+ y0.Mul(y0, fp3, pool)
+
+ y1, y4, y5 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
+ y1.Conjugate(t1)
+ y5.Conjugate(fu2)
+ y3.Conjugate(y3)
+ y4.Mul(fu, fu2p, pool)
+ y4.Conjugate(y4)
+
+ y6 := newGFp12(pool)
+ y6.Mul(fu3, fu3p, pool)
+ y6.Conjugate(y6)
+
+ t0 := newGFp12(pool)
+ t0.Square(y6, pool)
+ t0.Mul(t0, y4, pool)
+ t0.Mul(t0, y5, pool)
+ t1.Mul(y3, y5, pool)
+ t1.Mul(t1, t0, pool)
+ t0.Mul(t0, y2, pool)
+ t1.Square(t1, pool)
+ t1.Mul(t1, t0, pool)
+ t1.Square(t1, pool)
+ t0.Mul(t1, y1, pool)
+ t1.Mul(t1, y0, pool)
+ t0.Square(t0, pool)
+ t0.Mul(t0, t1, pool)
+
+ inv.Put(pool)
+ t1.Put(pool)
+ t2.Put(pool)
+ fp.Put(pool)
+ fp2.Put(pool)
+ fp3.Put(pool)
+ fu.Put(pool)
+ fu2.Put(pool)
+ fu3.Put(pool)
+ fu2p.Put(pool)
+ fu3p.Put(pool)
+ y0.Put(pool)
+ y1.Put(pool)
+ y2.Put(pool)
+ y3.Put(pool)
+ y4.Put(pool)
+ y5.Put(pool)
+ y6.Put(pool)
+
+ return t0
+}
+
+func optimalAte(a *twistPoint, b *curvePoint, pool *bnPool) *gfP12 {
+ e := miller(a, b, pool)
+ ret := finalExponentiation(e, pool)
+ e.Put(pool)
+
+ if a.IsInfinity() || b.IsInfinity() {
+ ret.SetOne()
+ }
+
+ return ret
+}
diff --git a/crypto/bn256/twist.go b/crypto/bn256/twist.go
new file mode 100644
index 000000000..1e052456e
--- /dev/null
+++ b/crypto/bn256/twist.go
@@ -0,0 +1,249 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bn256
+
+import (
+ "math/big"
+)
+
+// twistPoint implements the elliptic curve y²=x³+3/ξ over GF(p²). Points are
+// kept in Jacobian form and t=z² when valid. The group G₂ is the set of
+// n-torsion points of this curve over GF(p²) (where n = Order)
+type twistPoint struct {
+ x, y, z, t *gfP2
+}
+
+var twistB = &gfP2{
+ bigFromBase10("266929791119991161246907387137283842545076965332900288569378510910307636690"),
+ bigFromBase10("19485874751759354771024239261021720505790618469301721065564631296452457478373"),
+}
+
+// twistGen is the generator of group G₂.
+var twistGen = &twistPoint{
+ &gfP2{
+ bigFromBase10("11559732032986387107991004021392285783925812861821192530917403151452391805634"),
+ bigFromBase10("10857046999023057135944570762232829481370756359578518086990519993285655852781"),
+ },
+ &gfP2{
+ bigFromBase10("4082367875863433681332203403145435568316851327593401208105741076214120093531"),
+ bigFromBase10("8495653923123431417604973247489272438418190587263600148770280649306958101930"),
+ },
+ &gfP2{
+ bigFromBase10("0"),
+ bigFromBase10("1"),
+ },
+ &gfP2{
+ bigFromBase10("0"),
+ bigFromBase10("1"),
+ },
+}
+
+func newTwistPoint(pool *bnPool) *twistPoint {
+ return &twistPoint{
+ newGFp2(pool),
+ newGFp2(pool),
+ newGFp2(pool),
+ newGFp2(pool),
+ }
+}
+
+func (c *twistPoint) String() string {
+ return "(" + c.x.String() + ", " + c.y.String() + ", " + c.z.String() + ")"
+}
+
+func (c *twistPoint) Put(pool *bnPool) {
+ c.x.Put(pool)
+ c.y.Put(pool)
+ c.z.Put(pool)
+ c.t.Put(pool)
+}
+
+func (c *twistPoint) Set(a *twistPoint) {
+ c.x.Set(a.x)
+ c.y.Set(a.y)
+ c.z.Set(a.z)
+ c.t.Set(a.t)
+}
+
+// IsOnCurve returns true iff c is on the curve where c must be in affine form.
+func (c *twistPoint) IsOnCurve() bool {
+ pool := new(bnPool)
+ yy := newGFp2(pool).Square(c.y, pool)
+ xxx := newGFp2(pool).Square(c.x, pool)
+ xxx.Mul(xxx, c.x, pool)
+ yy.Sub(yy, xxx)
+ yy.Sub(yy, twistB)
+ yy.Minimal()
+ return yy.x.Sign() == 0 && yy.y.Sign() == 0
+}
+
+func (c *twistPoint) SetInfinity() {
+ c.z.SetZero()
+}
+
+func (c *twistPoint) IsInfinity() bool {
+ return c.z.IsZero()
+}
+
+func (c *twistPoint) Add(a, b *twistPoint, pool *bnPool) {
+ // For additional comments, see the same function in curve.go.
+
+ if a.IsInfinity() {
+ c.Set(b)
+ return
+ }
+ if b.IsInfinity() {
+ c.Set(a)
+ return
+ }
+
+ // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
+ z1z1 := newGFp2(pool).Square(a.z, pool)
+ z2z2 := newGFp2(pool).Square(b.z, pool)
+ u1 := newGFp2(pool).Mul(a.x, z2z2, pool)
+ u2 := newGFp2(pool).Mul(b.x, z1z1, pool)
+
+ t := newGFp2(pool).Mul(b.z, z2z2, pool)
+ s1 := newGFp2(pool).Mul(a.y, t, pool)
+
+ t.Mul(a.z, z1z1, pool)
+ s2 := newGFp2(pool).Mul(b.y, t, pool)
+
+ h := newGFp2(pool).Sub(u2, u1)
+ xEqual := h.IsZero()
+
+ t.Add(h, h)
+ i := newGFp2(pool).Square(t, pool)
+ j := newGFp2(pool).Mul(h, i, pool)
+
+ t.Sub(s2, s1)
+ yEqual := t.IsZero()
+ if xEqual && yEqual {
+ c.Double(a, pool)
+ return
+ }
+ r := newGFp2(pool).Add(t, t)
+
+ v := newGFp2(pool).Mul(u1, i, pool)
+
+ t4 := newGFp2(pool).Square(r, pool)
+ t.Add(v, v)
+ t6 := newGFp2(pool).Sub(t4, j)
+ c.x.Sub(t6, t)
+
+ t.Sub(v, c.x) // t7
+ t4.Mul(s1, j, pool) // t8
+ t6.Add(t4, t4) // t9
+ t4.Mul(r, t, pool) // t10
+ c.y.Sub(t4, t6)
+
+ t.Add(a.z, b.z) // t11
+ t4.Square(t, pool) // t12
+ t.Sub(t4, z1z1) // t13
+ t4.Sub(t, z2z2) // t14
+ c.z.Mul(t4, h, pool)
+
+ z1z1.Put(pool)
+ z2z2.Put(pool)
+ u1.Put(pool)
+ u2.Put(pool)
+ t.Put(pool)
+ s1.Put(pool)
+ s2.Put(pool)
+ h.Put(pool)
+ i.Put(pool)
+ j.Put(pool)
+ r.Put(pool)
+ v.Put(pool)
+ t4.Put(pool)
+ t6.Put(pool)
+}
+
+func (c *twistPoint) Double(a *twistPoint, pool *bnPool) {
+ // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
+ A := newGFp2(pool).Square(a.x, pool)
+ B := newGFp2(pool).Square(a.y, pool)
+ C := newGFp2(pool).Square(B, pool)
+
+ t := newGFp2(pool).Add(a.x, B)
+ t2 := newGFp2(pool).Square(t, pool)
+ t.Sub(t2, A)
+ t2.Sub(t, C)
+ d := newGFp2(pool).Add(t2, t2)
+ t.Add(A, A)
+ e := newGFp2(pool).Add(t, A)
+ f := newGFp2(pool).Square(e, pool)
+
+ t.Add(d, d)
+ c.x.Sub(f, t)
+
+ t.Add(C, C)
+ t2.Add(t, t)
+ t.Add(t2, t2)
+ c.y.Sub(d, c.x)
+ t2.Mul(e, c.y, pool)
+ c.y.Sub(t2, t)
+
+ t.Mul(a.y, a.z, pool)
+ c.z.Add(t, t)
+
+ A.Put(pool)
+ B.Put(pool)
+ C.Put(pool)
+ t.Put(pool)
+ t2.Put(pool)
+ d.Put(pool)
+ e.Put(pool)
+ f.Put(pool)
+}
+
+func (c *twistPoint) Mul(a *twistPoint, scalar *big.Int, pool *bnPool) *twistPoint {
+ sum := newTwistPoint(pool)
+ sum.SetInfinity()
+ t := newTwistPoint(pool)
+
+ for i := scalar.BitLen(); i >= 0; i-- {
+ t.Double(sum, pool)
+ if scalar.Bit(i) != 0 {
+ sum.Add(t, a, pool)
+ } else {
+ sum.Set(t)
+ }
+ }
+
+ c.Set(sum)
+ sum.Put(pool)
+ t.Put(pool)
+ return c
+}
+
+func (c *twistPoint) MakeAffine(pool *bnPool) *twistPoint {
+ if c.z.IsOne() {
+ return c
+ }
+
+ zInv := newGFp2(pool).Invert(c.z, pool)
+ t := newGFp2(pool).Mul(c.y, zInv, pool)
+ zInv2 := newGFp2(pool).Square(zInv, pool)
+ c.y.Mul(t, zInv2, pool)
+ t.Mul(c.x, zInv2, pool)
+ c.x.Set(t)
+ c.z.SetOne()
+ c.t.SetOne()
+
+ zInv.Put(pool)
+ t.Put(pool)
+ zInv2.Put(pool)
+
+ return c
+}
+
+func (c *twistPoint) Negative(a *twistPoint, pool *bnPool) {
+ c.x.Set(a.x)
+ c.y.SetZero()
+ c.y.Sub(c.y, a.y)
+ c.z.Set(a.z)
+ c.t.SetZero()
+}
diff --git a/internal/ethapi/tracer_test.go b/internal/ethapi/tracer_test.go
index 0ef450ce3..5093dafd6 100644
--- a/internal/ethapi/tracer_test.go
+++ b/internal/ethapi/tracer_test.go
@@ -48,7 +48,7 @@ func runTrace(tracer *JavascriptTracer) (interface{}, error) {
contract := vm.NewContract(account{}, account{}, big.NewInt(0), 10000)
contract.Code = []byte{byte(vm.PUSH1), 0x1, byte(vm.PUSH1), 0x1, 0x0}
- _, err := env.Interpreter().Run(contract, []byte{})
+ _, err := env.Interpreter().Run(0, contract, []byte{})
if err != nil {
return nil, err
}
diff --git a/miner/worker.go b/miner/worker.go
index e64917261..803015390 100644
--- a/miner/worker.go
+++ b/miner/worker.go
@@ -523,7 +523,7 @@ func (env *Work) commitTransactions(mux *event.TypeMux, txs *types.TransactionsB
continue
}
// Start executing the transaction
- env.state.StartRecord(tx.Hash(), common.Hash{}, env.tcount)
+ env.state.Prepare(tx.Hash(), common.Hash{}, env.tcount)
err, logs := env.commitTransaction(tx, bc, coinbase, gp)
switch err {
diff --git a/params/config.go b/params/config.go
index bc63a45b9..5fb414d62 100644
--- a/params/config.go
+++ b/params/config.go
@@ -26,28 +26,32 @@ import (
var (
// MainnetChainConfig is the chain parameters to run a node on the main network.
MainnetChainConfig = &ChainConfig{
- ChainId: MainNetChainID,
- HomesteadBlock: MainNetHomesteadBlock,
- DAOForkBlock: MainNetDAOForkBlock,
- DAOForkSupport: true,
- EIP150Block: MainNetHomesteadGasRepriceBlock,
- EIP150Hash: MainNetHomesteadGasRepriceHash,
- EIP155Block: MainNetSpuriousDragon,
- EIP158Block: MainNetSpuriousDragon,
- Ethash: new(EthashConfig),
+ ChainId: MainNetChainID,
+ HomesteadBlock: MainNetHomesteadBlock,
+ DAOForkBlock: MainNetDAOForkBlock,
+ DAOForkSupport: true,
+ EIP150Block: MainNetHomesteadGasRepriceBlock,
+ EIP150Hash: MainNetHomesteadGasRepriceHash,
+ EIP155Block: MainNetSpuriousDragon,
+ EIP158Block: MainNetSpuriousDragon,
+ MetropolisBlock: MainNetMetropolisBlock,
+
+ Ethash: new(EthashConfig),
}
// TestnetChainConfig contains the chain parameters to run a node on the Ropsten test network.
TestnetChainConfig = &ChainConfig{
- ChainId: big.NewInt(3),
- HomesteadBlock: big.NewInt(0),
- DAOForkBlock: nil,
- DAOForkSupport: true,
- EIP150Block: big.NewInt(0),
- EIP150Hash: common.HexToHash("0x41941023680923e0fe4d74a34bdac8141f2540e3ae90623718e47d66d1ca4a2d"),
- EIP155Block: big.NewInt(10),
- EIP158Block: big.NewInt(10),
- Ethash: new(EthashConfig),
+ ChainId: big.NewInt(3),
+ HomesteadBlock: big.NewInt(0),
+ DAOForkBlock: nil,
+ DAOForkSupport: true,
+ EIP150Block: big.NewInt(0),
+ EIP150Hash: common.HexToHash("0x41941023680923e0fe4d74a34bdac8141f2540e3ae90623718e47d66d1ca4a2d"),
+ EIP155Block: big.NewInt(10),
+ EIP158Block: big.NewInt(10),
+ MetropolisBlock: TestNetMetropolisBlock,
+
+ Ethash: new(EthashConfig),
}
// RinkebyChainConfig contains the chain parameters to run a node on the Rinkeby test network.
@@ -68,15 +72,15 @@ var (
// AllProtocolChanges contains every protocol change (EIPs)
// introduced and accepted by the Ethereum core developers.
- // TestChainConfig is like AllProtocolChanges but has chain ID 1.
//
// This configuration is intentionally not using keyed fields.
// This configuration must *always* have all forks enabled, which
// means that all fields must be set at all times. This forces
// anyone adding flags to the config to also have to set these
// fields.
- AllProtocolChanges = &ChainConfig{big.NewInt(1337), big.NewInt(0), nil, false, big.NewInt(0), common.Hash{}, big.NewInt(0), big.NewInt(0), new(EthashConfig), nil}
- TestChainConfig = &ChainConfig{big.NewInt(1), big.NewInt(0), nil, false, big.NewInt(0), common.Hash{}, big.NewInt(0), big.NewInt(0), new(EthashConfig), nil}
+ AllProtocolChanges = &ChainConfig{big.NewInt(1337), big.NewInt(0), nil, false, big.NewInt(0), common.Hash{}, big.NewInt(0), big.NewInt(0), big.NewInt(0), new(EthashConfig), nil}
+ TestChainConfig = &ChainConfig{big.NewInt(1), big.NewInt(0), nil, false, big.NewInt(0), common.Hash{}, big.NewInt(0), big.NewInt(0), nil, new(EthashConfig), nil}
+ TestRules = TestChainConfig.Rules(new(big.Int))
)
// ChainConfig is the core config which determines the blockchain settings.
@@ -95,8 +99,10 @@ type ChainConfig struct {
EIP150Block *big.Int `json:"eip150Block,omitempty"` // EIP150 HF block (nil = no fork)
EIP150Hash common.Hash `json:"eip150Hash,omitempty"` // EIP150 HF hash (fast sync aid)
- EIP155Block *big.Int `json:"eip155Block,omitempty"` // EIP155 HF block
- EIP158Block *big.Int `json:"eip158Block,omitempty"` // EIP158 HF block
+ EIP155Block *big.Int `json:"eip155Block"` // EIP155 HF block
+ EIP158Block *big.Int `json:"eip158Block"` // EIP158 HF block
+
+ MetropolisBlock *big.Int `json:"metropolisBlock"` // Metropolis switch block (nil = no fork, 0 = alraedy on homestead)
// Various consensus engines
Ethash *EthashConfig `json:"ethash,omitempty"`
@@ -141,6 +147,7 @@ func (c *ChainConfig) String() string {
c.EIP150Block,
c.EIP155Block,
c.EIP158Block,
+ c.MetropolisBlock,
engine,
)
}
@@ -251,6 +258,13 @@ func configNumEqual(x, y *big.Int) bool {
return x.Cmp(y) == 0
}
+func (c *ChainConfig) IsMetropolis(num *big.Int) bool {
+ if c.MetropolisBlock == nil || num == nil {
+ return false
+ }
+ return num.Cmp(c.MetropolisBlock) >= 0
+}
+
// ConfigCompatError is raised if the locally-stored blockchain is initialised with a
// ChainConfig that would alter the past.
type ConfigCompatError struct {
@@ -281,3 +295,22 @@ func newCompatError(what string, storedblock, newblock *big.Int) *ConfigCompatEr
func (err *ConfigCompatError) Error() string {
return fmt.Sprintf("mismatching %s in database (have %d, want %d, rewindto %d)", err.What, err.StoredConfig, err.NewConfig, err.RewindTo)
}
+
+// Rules wraps ChainConfig and is merely syntatic sugar or can be used for functions
+// that do not have or require information about the block.
+//
+// Rules is a one time interface meaning that it shouldn't be used in between transition
+// phases.
+type Rules struct {
+ ChainId *big.Int
+ IsHomestead, IsEIP150, IsEIP155, IsEIP158 bool
+ IsMetropolis bool
+}
+
+func (c *ChainConfig) Rules(num *big.Int) Rules {
+ chainId := c.ChainId
+ if chainId == nil {
+ chainId = new(big.Int)
+ }
+ return Rules{ChainId: new(big.Int).Set(chainId), IsHomestead: c.IsHomestead(num), IsEIP150: c.IsEIP150(num), IsEIP155: c.IsEIP155(num), IsEIP158: c.IsEIP158(num), IsMetropolis: c.IsMetropolis(num)}
+}
diff --git a/params/util.go b/params/util.go
index bf833d510..d4d43d047 100644
--- a/params/util.go
+++ b/params/util.go
@@ -17,6 +17,7 @@
package params
import (
+ "math"
"math/big"
"github.com/ethereum/go-ethereum/common"
@@ -38,6 +39,9 @@ var (
TestNetSpuriousDragon = big.NewInt(10)
MainNetSpuriousDragon = big.NewInt(2675000)
- TestNetChainID = big.NewInt(3) // Testnet default chain ID
- MainNetChainID = big.NewInt(1) // Mainnet default chain ID
+ TestNetMetropolisBlock = big.NewInt(math.MaxInt64)
+ MainNetMetropolisBlock = big.NewInt(math.MaxInt64)
+
+ TestNetChainID = big.NewInt(3) // Test net default chain ID
+ MainNetChainID = big.NewInt(1) // main net default chain ID
)