Initial commit

11 files changed, 669 insertions, 0 deletions

diff --git a/.ethereum.go.un~ b/.ethereum.go.un~
new file mode 100644
index 000000000..42e42bcb6
--- /dev/null
+++ b/.ethereum.go.un~
diff --git a/big.go b/big.go
new file mode 100644
index 000000000..71e7573e1
--- /dev/null
+++ b/big.go
@@ -0,0 +1,20 @@
+package main
+
+import (
+  "math/big"
+)
+
+func BigPow(a,b int) *big.Int {
+  c := new(big.Int)
+  c.Exp(big.NewInt(int64(a)), big.NewInt(int64(b)), big.NewInt(0))
+
+  return c
+}
+
+func Big(num string) *big.Int {
+  n := new(big.Int)
+  n.SetString(num, 0)
+
+  return n
+}
+
diff --git a/block.go b/block.go
new file mode 100644
index 000000000..a0bcf0bd0
--- /dev/null
+++ b/block.go
@@ -0,0 +1,21 @@
+package main
+
+import (
+  _"fmt"
+)
+
+type Block struct {
+  transactions []*Transaction
+}
+
+func NewBlock(/* TODO use raw data */transactions []*Transaction) *Block {
+  block := &Block{
+    // Slice of transactions to include in this block
+    transactions: transactions,
+  }
+
+  return block
+}
+
+func (block *Block) Update() {
+}
diff --git a/block_manager.go b/block_manager.go
new file mode 100644
index 000000000..4f0ec1cdb
--- /dev/null
+++ b/block_manager.go
@@ -0,0 +1,55 @@
+
+  // Blocks, blocks will have transactions.
+  // Transactions/contracts are updated in goroutines
+  // Each contract should send a message on a channel with usage statistics
+  // The statics can be used for fee calculation within the block update method
+  // Statistics{transaction, /* integers */ normal_ops, store_load, extro_balance, crypto, steps}
+  // The block updater will wait for all goroutines to be finished and update the block accordingly
+  // in one go and should use minimal IO overhead.
+  // The actual block updating will happen within a goroutine as well so normal operation may continue
+
+package main
+
+import (
+  _"fmt"
+)
+
+type BlockManager struct {
+  vm *Vm
+}
+
+func NewBlockManager() *BlockManager {
+  bm := &BlockManager{vm: NewVm()}
+
+  return bm
+}
+
+// Process a block.
+func (bm *BlockManager) ProcessBlock(block *Block) error {
+  txCount  := len(block.transactions)
+  lockChan := make(chan bool, txCount)
+
+  for _, tx := range block.transactions {
+    go bm.ProcessTransaction(tx, lockChan)
+  }
+
+  // Wait for all Tx to finish processing
+  for i := 0; i < txCount; i++ {
+    <- lockChan
+  }
+
+  return nil
+}
+
+func (bm *BlockManager) ProcessTransaction(tx *Transaction, lockChan chan bool) {
+  if tx.recipient == 0x0 {
+    bm.vm.RunTransaction(tx, func(opType OpType) bool {
+      // TODO calculate fees
+
+      return true // Continue
+    })
+  }
+
+  // Broadcast we're done
+  lockChan <- true
+}
diff --git a/ethereum.go b/ethereum.go
new file mode 100644
index 000000000..530cbd5c1
--- /dev/null
+++ b/ethereum.go
@@ -0,0 +1,33 @@
+package main
+
+import (
+  "fmt"
+)
+
+func main() {
+  InitFees()
+
+  bm := NewBlockManager()
+
+  tx := NewTransaction(0x0, 20, []string{
+    "SET 10 6",
+    "LD 10 10",
+    "LT 10 1 20",
+    "SET 255 7",
+    "JMPI 20 255",
+    "STOP",
+    "SET 30 200",
+    "LD 30 31",
+    "SET 255 22",
+    "JMPI 31 255",
+    "SET 255 15",
+    "JMP 255",
+  })
+  tx2 := NewTransaction(0x0, 20, []string{"SET 10 6", "LD 10 10"})
+
+  blck := NewBlock([]*Transaction{tx2, tx})
+
+  bm.ProcessBlock( blck )
+
+  fmt.Printf("rlp encoded Tx %q\n", tx.Serialize())
+}
diff --git a/parsing.go b/parsing.go
new file mode 100644
index 000000000..d5dcce04f
--- /dev/null
+++ b/parsing.go
@@ -0,0 +1,113 @@
+package main
+
+import (
+  "fmt"
+  "strings"
+  "errors"
+  "math/big"
+  "strconv"
+)
+
+// Op codes
+var OpCodes = map[string]string{
+  "STOP":       "0",
+  "ADD":        "16",  // 0x10
+  "SUB":        "17",  // 0x11
+  "MUL":        "18",  // 0x12
+  "DIV":        "19",  // 0x13
+  "SDIV":       "20",  // 0x14
+  "MOD":        "21",  // 0x15
+  "SMOD":       "22",  // 0x16
+  "EXP":        "23",  // 0x17
+  "NEG":        "24",  // 0x18
+  "LT":         "32",  // 0x20
+  "LE":         "33",  // 0x21
+  "GT":         "34",  // 0x22
+  "GE":         "35",  // 0x23
+  "EQ":         "36",  // 0x24
+  "NOT":        "37",  // 0x25
+  "SHA256":     "48",  // 0x30
+  "RIPEMD160":  "49",  // 0x31
+  "ECMUL":      "50",  // 0x32
+  "ECADD":      "51",  // 0x33
+  "SIGN":       "52",  // 0x34
+  "RECOVER":    "53",  // 0x35
+  "COPY":       "64",  // 0x40
+  "ST":         "65",  // 0x41
+  "LD":         "66",  // 0x42
+  "SET":        "67",  // 0x43
+  "JMP":        "80",  // 0x50
+  "JMPI":       "81",  // 0x51
+  "IND":        "82",  // 0x52
+  "EXTRO":      "96",  // 0x60
+  "BALANCE":    "97",  // 0x61
+  "MKTX":       "112", // 0x70
+  "DATA":       "128", // 0x80
+  "DATAN":      "129", // 0x81
+  "MYADDRESS":  "144", // 0x90
+  "BLKHASH":    "145", // 0x91
+  "COINBASE":   "146", // 0x92
+  "SUICIDE":    "255", // 0xff
+}
+
+
+func CompileInstr(s string) (string, error) {
+  tokens := strings.Split(s, " ")
+  if OpCodes[tokens[0]] == "" {
+    return "", errors.New(fmt.Sprintf("OP not found: %s", tokens[0]))
+  }
+
+  code := OpCodes[tokens[0]] // Replace op codes with the proper numerical equivalent
+  op := new(big.Int)
+  op.SetString(code, 0)
+
+  args := make([]*big.Int, 6)
+  for i, val := range tokens[1:len(tokens)] {
+    num := new(big.Int)
+    num.SetString(val, 0)
+    args[i] = num
+  }
+
+  // Big int equation = op + x * 256 + y * 256**2 + z * 256**3 + a * 256**4 + b * 256**5 + c * 256**6
+  base := new(big.Int)
+  x := new(big.Int)
+  y := new(big.Int)
+  z := new(big.Int)
+  a := new(big.Int)
+  b := new(big.Int)
+  c := new(big.Int)
+
+  if args[0] != nil { x.Mul(args[0], big.NewInt(256)) }
+  if args[1] != nil { y.Mul(args[1], BigPow(256, 2)) }
+  if args[2] != nil { z.Mul(args[2], BigPow(256, 3)) }
+  if args[3] != nil { a.Mul(args[3], BigPow(256, 4)) }
+  if args[4] != nil { b.Mul(args[4], BigPow(256, 5)) }
+  if args[5] != nil { c.Mul(args[5], BigPow(256, 6)) }
+
+  base.Add(op, x)
+  base.Add(base, y)
+  base.Add(base, z)
+  base.Add(base, a)
+  base.Add(base, b)
+  base.Add(base, c)
+
+  return base.String(), nil
+}
+
+func Instr(instr string) (int, []string, error) {
+  base := new(big.Int)
+  base.SetString(instr, 0)
+
+  args := make([]string, 7)
+  for i := 0; i < 7; i++ {
+    // int(int(val) / int(math.Pow(256,float64(i)))) % 256
+    exp := BigPow(256, i)
+    num := new(big.Int)
+    num.Div(base, exp)
+
+    args[i] = num.Mod(num, big.NewInt(256)).String()
+  }
+  op, _ := strconv.Atoi(args[0])
+
+  return op, args[1:7], nil
+}
diff --git a/parsing_test.go b/parsing_test.go
new file mode 100644
index 000000000..93fe434b9
--- /dev/null
+++ b/parsing_test.go
@@ -0,0 +1,42 @@
+package main
+
+import (
+  "testing"
+  "math"
+)
+
+func TestCompile(t *testing.T) {
+  instr, err := CompileInstr("SET 10 1")
+
+  if err != nil {
+    t.Error("Failed compiling instruction")
+  }
+
+  calc := (67 + 10 * 256 + 1 * int64(math.Pow(256,2)))
+  if Big(instr).Int64() != calc {
+    t.Error("Expected", calc, ", got:", instr)
+  }
+}
+
+func TestValidInstr(t *testing.T) {
+  op, args, err := Instr("68163")
+  if err != nil {
+    t.Error("Error decoding instruction")
+  }
+
+  if op != oSET {
+    t.Error("Expected op to be 43, got:", op)
+  }
+
+  if args[0] != "10" {
+    t.Error("Expect args[0] to be 10, got:", args[0])
+  }
+
+  if args[1] != "1" {
+    t.Error("Expected args[1] to be 1, got:", args[1])
+  }
+}
+
+func TestInvalidInstr(t *testing.T) {
+}
+
diff --git a/serialization.go b/serialization.go
new file mode 100644
index 000000000..7e2e96beb
--- /dev/null
+++ b/serialization.go
@@ -0,0 +1,57 @@
+package main
+
+import (
+  "math"
+  "bytes"
+)
+
+func ToBinary(x int, bytes int) string {
+  if bytes == 0 {
+    return ""
+  } else {
+    return ToBinary(int(x / 256), bytes - 1) + string(x % 256)
+  }
+}
+
+func NumToVarInt(x int) string {
+  if x < 253 {
+    return string(x)
+  } else if x < int(math.Pow(2,16)) {
+    return string(253) + ToBinary(x, 2)
+  } else if x < int(math.Pow(2,32)) {
+    return string(253) + ToBinary(x, 4)
+  } else {
+    return string(253) + ToBinary(x, 8)
+  }
+}
+
+func RlpEncode(object interface{}) string {
+  if str, ok := object.(string); ok {
+    return "\x00" + NumToVarInt(len(str)) + str
+  } else if slice, ok := object.([]interface{}); ok {
+    var buffer bytes.Buffer
+    for _, val := range slice {
+      if v, ok := val.(string); ok {
+        buffer.WriteString(RlpEncode(v))
+      } else {
+        buffer.WriteString(RlpEncode(val))
+      }
+    }
+
+    return "\x01" + RlpEncode(len(buffer.String())) + buffer.String()
+  } else if slice, ok := object.([]string); ok {
+
+    // FIXME this isn't dry. Fix this
+    var buffer bytes.Buffer
+    for _, val := range slice {
+      buffer.WriteString(RlpEncode(val))
+    }
+    return "\x01" + RlpEncode(len(buffer.String())) + buffer.String()
+  }
+
+  return ""
+}
+
+type RlpSerializer interface {
+}
+
diff --git a/serialization_test.go b/serialization_test.go
new file mode 100644
index 000000000..adb1b6e2d
--- /dev/null
+++ b/serialization_test.go
@@ -0,0 +1,20 @@
+package main
+
+import (
+  "testing"
+  "fmt"
+)
+
+func TestRlpEncode(t *testing.T) {
+  strRes := "\x00\x03dog"
+  str := RlpEncode("dog")
+  if str != strRes {
+    t.Error(fmt.Sprintf("Expected %q, got %q", strRes, str))
+  }
+
+  sliceRes := "\x01\x00\x03dog\x00\x03god\x00\x03cat"
+  slice := RlpEncode([]string{"dog", "god", "cat"})
+  if slice != sliceRes {
+    t.Error(fmt.Sprintf("Expected %q, got %q", sliceRes, slice))
+  }
+}
diff --git a/transaction.go b/transaction.go
new file mode 100644
index 000000000..f78715d8c
--- /dev/null
+++ b/transaction.go
@@ -0,0 +1,126 @@
+package main
+
+import (
+  "math/big"
+  "fmt"
+  "encoding/hex"
+  "crypto/sha256"
+  _ "bytes"
+  "strconv"
+)
+
+/*
+Transaction   Contract       Size
+-------------------------------------------
+sender        sender       20 bytes
+recipient     0x0          20 bytes
+value         endowment     4 bytes (uint32)
+fee           fee           4 bytes (uint32)
+d_size        o_size        4 bytes (uint32)
+data          ops           *
+signature     signature    64 bytes
+*/
+
+var StepFee   *big.Int = new(big.Int)
+var TxFee     *big.Int = new(big.Int)
+var MemFee    *big.Int = new(big.Int)
+var DataFee   *big.Int = new(big.Int)
+var CryptoFee *big.Int = new(big.Int)
+var ExtroFee  *big.Int = new(big.Int)
+
+var Period1Reward *big.Int = new(big.Int)
+var Period2Reward *big.Int = new(big.Int)
+var Period3Reward *big.Int = new(big.Int)
+var Period4Reward *big.Int = new(big.Int)
+
+type Transaction struct {
+  sender      string
+  recipient   uint32
+  value       uint32
+  fee         uint32
+  data        []string
+  memory      []int
+  signature   string
+
+  addr        string
+}
+
+func NewTransaction(to uint32, value uint32, data []string) *Transaction {
+  tx := Transaction{sender: "1234567890", recipient: to, value: value}
+  tx.fee = 0//uint32((ContractFee + MemoryFee * float32(len(tx.data))) * 1e8)
+
+  // Serialize the data
+  tx.data = make([]string, len(data))
+  for i, val := range data {
+    instr, err := CompileInstr(val)
+    if err != nil {
+      fmt.Printf("compile error:%d %v", i+1, err)
+    }
+
+    tx.data[i] = instr
+  }
+
+  b:= []byte(tx.Serialize())
+  hash := sha256.Sum256(b)
+  tx.addr = hex.EncodeToString(hash[0:19])
+
+  return &tx
+}
+
+func Uitoa(i uint32) string {
+  return strconv.FormatUint(uint64(i), 10)
+}
+
+func (tx *Transaction) Serialize() string {
+  // Prepare the transaction for serialization
+  preEnc := []interface{}{
+    "0", // TODO last Tx
+    tx.sender,
+    // XXX In the future there's no need to cast to string because they'll end up being big numbers (strings)
+    Uitoa(tx.recipient),
+    Uitoa(tx.value),
+    Uitoa(tx.fee),
+    tx.data,
+  }
+
+  return RlpEncode(preEnc)
+}
+
+func InitFees() {
+  // Base for 2**60
+  b60 := new(big.Int)
+  b60.Exp(big.NewInt(2), big.NewInt(60), big.NewInt(0))
+  // Base for 2**80
+  b80 := new(big.Int)
+  b80.Exp(big.NewInt(2), big.NewInt(80), big.NewInt(0))
+
+  StepFee.Mul(b60, big.NewInt(4096))
+  //fmt.Println("StepFee:", StepFee)
+
+  TxFee.Mul(b60, big.NewInt(524288))
+  //fmt.Println("TxFee:", TxFee)
+
+  MemFee.Mul(b60, big.NewInt(262144))
+  //fmt.Println("MemFee:", MemFee)
+
+  DataFee.Mul(b60, big.NewInt(16384))
+  //fmt.Println("DataFee:", DataFee)
+
+  CryptoFee.Mul(b60, big.NewInt(65536))
+  //fmt.Println("CrytoFee:", CryptoFee)
+
+  ExtroFee.Mul(b60, big.NewInt(65536))
+  //fmt.Println("ExtroFee:", ExtroFee)
+
+  Period1Reward.Mul(b80, big.NewInt(1024))
+  //fmt.Println("Period1Reward:", Period1Reward)
+
+  Period2Reward.Mul(b80, big.NewInt(512))
+  //fmt.Println("Period2Reward:", Period2Reward)
+
+  Period3Reward.Mul(b80, big.NewInt(256))
+  //fmt.Println("Period3Reward:", Period3Reward)
+
+  Period4Reward.Mul(b80, big.NewInt(128))
+  //fmt.Println("Period4Reward:", Period4Reward)
+}
diff --git a/vm.go b/vm.go
new file mode 100644
index 000000000..353f4f39e
--- /dev/null
+++ b/vm.go
@@ -0,0 +1,182 @@
+package main
+
+import (
+  "math"
+  "math/big"
+  "fmt"
+  "strconv"
+  _ "encoding/hex"
+)
+
+// Op codes
+const (
+  oSTOP       int = 0x00
+  oADD        int = 0x10
+  oSUB        int = 0x11
+  oMUL        int = 0x12
+  oDIV        int = 0x13
+  oSDIV       int = 0x14
+  oMOD        int = 0x15
+  oSMOD       int = 0x16
+  oEXP        int = 0x17
+  oNEG        int = 0x18
+  oLT         int = 0x20
+  oLE         int = 0x21
+  oGT         int = 0x22
+  oGE         int = 0x23
+  oEQ         int = 0x24
+  oNOT        int = 0x25
+  oSHA256     int = 0x30
+  oRIPEMD160  int = 0x31
+  oECMUL      int = 0x32
+  oECADD      int = 0x33
+  oSIGN       int = 0x34
+  oRECOVER    int = 0x35
+  oCOPY       int = 0x40
+  oST         int = 0x41
+  oLD         int = 0x42
+  oSET        int = 0x43
+  oJMP        int = 0x50
+  oJMPI       int = 0x51
+  oIND        int = 0x52
+  oEXTRO      int = 0x60
+  oBALANCE    int = 0x61
+  oMKTX       int = 0x70
+  oDATA       int = 0x80
+  oDATAN      int = 0x81
+  oMYADDRESS  int = 0x90
+  oSUICIDE    int = 0xff
+)
+
+type OpType int
+const (
+  tNorm = iota
+  tData
+  tExtro
+  tCrypto
+)
+type TxCallback func(opType OpType) bool
+
+type Vm struct {
+  // Memory stack
+  stack map[string]string
+  // Index ptr
+  iptr int
+  memory map[string]map[string]string
+}
+
+func NewVm() *Vm {
+  fmt.Println("init Ethereum VM")
+
+  stackSize := uint(256)
+  fmt.Println("stack size =", stackSize)
+
+  return &Vm{make(map[string]string), 0, make(map[string]map[string]string)}
+}
+
+func (vm *Vm) RunTransaction(tx *Transaction, cb TxCallback) {
+  fmt.Printf(`
+# processing Tx (%v)
+# fee = %f, ops = %d, sender = %s, value = %d
+`, tx.addr, float32(tx.fee) / 1e8, len(tx.data), tx.sender, tx.value)
+
+  vm.stack = make(map[string]string)
+  vm.stack["0"] = tx.sender
+  vm.stack["1"] = "100"  //int(tx.value)
+  vm.stack["1"] = "1000" //int(tx.fee)
+
+  //vm.memory[tx.addr] = make([]int, 256)
+  vm.memory[tx.addr] = make(map[string]string)
+
+  // Define instruction 'accessors' for the instruction, which makes it more readable
+  // also called register values, shorthanded as Rx/y/z. Memory address are shorthanded as Mx/y/z.
+  // Instructions are shorthanded as Ix/y/z
+  x := 0; y := 1; z := 2; //a := 3; b := 4; c := 5
+out:
+  for vm.iptr < len(tx.data) {
+    // The base big int for all calculations. Use this for any results.
+    base := new(big.Int)
+    // XXX Should Instr return big int slice instead of string slice?
+    op, args, _ := Instr(tx.data[vm.iptr])
+
+    fmt.Printf("%-3d %d %v\n", vm.iptr, op, args)
+
+    opType     := OpType(tNorm)
+    // Determine the op type (used for calculating fees by the block manager)
+    switch op {
+    case oEXTRO, oBALANCE:
+      opType = tExtro
+    case oSHA256, oRIPEMD160, oECMUL, oECADD: // TODO add rest
+      opType = tCrypto
+    }
+
+    // If the callback yielded a negative result abort execution
+    if !cb(opType) { break out }
+
+    nptr := vm.iptr
+    switch op {
+    case oSTOP:
+      fmt.Println("exiting (oSTOP), idx =", nptr)
+
+      break out
+    case oADD:
+      // (Rx + Ry) % 2 ** 256
+      base.Add(Big(vm.stack[args[ x ]]), Big(vm.stack[args[ y ]]))
+      base.Mod(base, big.NewInt(int64(math.Pow(2, 256))))
+      // Set the result to Rz
+      vm.stack[args[ z ]] = base.String()
+    case oSUB:
+      // (Rx - Ry) % 2 ** 256
+      base.Sub(Big(vm.stack[args[ x ]]), Big(vm.stack[args[ y ]]))
+      base.Mod(base, big.NewInt(int64(math.Pow(2, 256))))
+      // Set the result to Rz
+      vm.stack[args[ z ]] = base.String()
+    case oMUL:
+      // (Rx * Ry) % 2 ** 256
+      base.Mul(Big(vm.stack[args[ x ]]), Big(vm.stack[args[ y ]]))
+      base.Mod(base, big.NewInt(int64(math.Pow(2, 256))))
+      // Set the result to Rz
+      vm.stack[args[ z ]] = base.String()
+    case oDIV:
+      // floor(Rx / Ry)
+      base.Div(Big(vm.stack[args[ x ]]), Big(vm.stack[args[ y ]]))
+      // Set the result to Rz
+      vm.stack[args[ z ]] = base.String()
+    case oSET:
+      // Set the (numeric) value at Iy to Rx
+      vm.stack[args[ x ]] = args[ y ]
+    case oLD:
+      // Load the value at Mx to Ry
+      vm.stack[args[ y ]] = vm.memory[tx.addr][vm.stack[args[ x ]]]
+    case oLT:
+      cmp := Big(vm.stack[args[ x ]]).Cmp( Big(vm.stack[args[ y ]]) )
+      // Set the result as "boolean" value to Rz
+      if  cmp < 0 { // a < b
+        vm.stack[args[ z ]] = "1"
+      } else {
+        vm.stack[args[ z ]] = "0"
+      }
+    case oJMP:
+      // Set the instruction pointer to the value at Rx
+      ptr, _ := strconv.Atoi( vm.stack[args[ x ]] )
+      nptr = ptr
+    case oJMPI:
+      // Set the instruction pointer to the value at Ry if Rx yields true
+      if vm.stack[args[ x ]] != "0" {
+        ptr, _ := strconv.Atoi( vm.stack[args[ y ]] )
+        nptr = ptr
+      }
+    default:
+      fmt.Println("Error op", op)
+      break
+    }
+
+    if vm.iptr == nptr {
+      vm.iptr++
+    } else {
+      vm.iptr = nptr
+      fmt.Println("... JMP", nptr, "...")
+    }
+  }
+  fmt.Println("# finished processing Tx\n")
+}