You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

374 lines
11KB

  1. package main
  2. import "fmt"
  3. import "math/big"
  4. import "crypto/rand"
  5. import mrand "math/rand"
  6. import "encoding/binary"
  7. //import "encoding/hex"
  8. import "github.com/kubernetes/klog"
  9. import "github.com/clearmatics/bn256"
  10. type KeyPair struct {
  11. x *big.Int
  12. y *bn256.G1
  13. }
  14. func (k KeyPair) String() string {
  15. x := fmt.Sprintf("x (secretkey): %x\n", k.x)
  16. x += fmt.Sprintf("y: %s", k.y)
  17. return x
  18. }
  19. var G *bn256.G1 = NewGeneratorParams(1).G // global generator point
  20. // ToDo encode the balance so only the receiver can decode transferred amount easily
  21. type Statement struct {
  22. CLn []*bn256.G1
  23. CRn []*bn256.G1
  24. Publickeylist []*bn256.G1 // Todo these can be skipped and collected back later on from the chain, this will save ringsize * POINTSIZE bytes
  25. C []*bn256.G1 // commitments
  26. D *bn256.G1
  27. roothash *big.Int // note roothash contains the merkle root hash of chain, when it was build
  28. }
  29. type Witness struct {
  30. SecretKey *big.Int
  31. R *big.Int
  32. TransferAmount uint32 // total value being transferred
  33. Balance uint32 // whatever is the the amount left after transfer
  34. index []int // index of sender in the public key list
  35. }
  36. type Transaction struct {
  37. statement *Statement
  38. proof *Proof
  39. }
  40. func RandomScalar() *big.Int {
  41. a, _ := rand.Int(rand.Reader, bn256.Order)
  42. return a
  43. }
  44. // this will return fixed random scalar
  45. func RandomScalarFixed() *big.Int {
  46. return RandomScalar()
  47. }
  48. func GenerateKeyPair() *KeyPair {
  49. var k KeyPair
  50. var y bn256.G1
  51. k.x = RandomScalar()
  52. k.y = &y
  53. y.ScalarMult(G, k.x)
  54. return &k
  55. }
  56. // this basically does a Schnorr ignature
  57. func sign(address *big.Int, k *KeyPair) (c, s *big.Int) {
  58. var tmppoint bn256.G1
  59. tmpsecret := RandomScalar()
  60. tmppoint.ScalarMult(G, tmpsecret)
  61. serialize := []byte(fmt.Sprintf("%s%s", k.y.String(), tmppoint.String()))
  62. c = reducedhash(serialize)
  63. s = new(big.Int).Mul(c, k.x) // basicaly scalar mul add
  64. s = s.Mod(s, bn256.Order)
  65. s = s.Add(s, tmpsecret)
  66. s = s.Mod(s, bn256.Order)
  67. return
  68. }
  69. func init_blockchain() *Blockchain {
  70. return &Blockchain{registeredusers: map[string]*bn256.G1{}, balances: map[string]*Balance{}}
  71. }
  72. func (b *Blockchain) registerUser(u *KeyPair) error {
  73. c, s := sign(new(big.Int).SetUint64(0), u)
  74. return b.RegisterUser(u.y, c, s)
  75. }
  76. // register a user to blockchain
  77. // this must be done via a empty transaction
  78. // however, such transactions must themselves have some proof of work (independent from mining PoW) so as
  79. // to avoid creation of billions of dummy accounts
  80. // also, note we should have some sort of account destruction mechanism if someone wishes to do so,
  81. // the leftover balance (if not empty can be donated and so on)
  82. // will allow user u
  83. func (b *Blockchain) RegisterUser(u *bn256.G1, c, s *big.Int) error {
  84. tmppoint := new(bn256.G1).Add(new(bn256.G1).ScalarMult(G, s), new(bn256.G1).ScalarMult(u, new(big.Int).Neg(c)))
  85. serialize := []byte(fmt.Sprintf("%s%s", u.String(), tmppoint.String()))
  86. c_calculated := reducedhash(serialize)
  87. if c.String() != c_calculated.String() {
  88. return fmt.Errorf("Registration signature is invalid")
  89. }
  90. if _, ok := b.registeredusers[u.String()]; ok {
  91. return fmt.Errorf("Already Registered ")
  92. } else {
  93. b.registeredusers[u.String()] = u
  94. var balance Balance
  95. balance.C[0].Set(u)
  96. balance.C[1].Set(G)
  97. b.balances[u.String()] = &balance
  98. }
  99. return nil
  100. }
  101. // fund a a user any arbitrary amount
  102. func (b *Blockchain) FundUser(u *bn256.G1, amount uint32) error {
  103. if _, ok := b.registeredusers[u.String()]; !ok {
  104. return fmt.Errorf("user not Registered ")
  105. } else {
  106. balance := b.balances[u.String()]
  107. balance.C[0].Add(&balance.C[0], new(bn256.G1).ScalarMult(G, new(big.Int).SetUint64(uint64(amount))))
  108. klog.Infof("User %s funded %d", u.String(), amount)
  109. return nil
  110. }
  111. }
  112. // fund a a user any arbitrary amount
  113. // this is a pure bruteforce, but can be optimized to instantly report under most of the conditions
  114. func (b *Blockchain) ReadBalance(u *bn256.G1, secretkey *big.Int) (uint32, error) {
  115. if _, ok := b.registeredusers[u.String()]; !ok {
  116. return 0, fmt.Errorf("user not Registered ")
  117. }
  118. balance := b.balances[u.String()]
  119. var CL, CR, gb bn256.G1
  120. CL.Set(&balance.C[0])
  121. CR.Set(&balance.C[1])
  122. gb.Add(&CL, new(bn256.G1).Neg(new(bn256.G1).ScalarMult(&CR, secretkey)))
  123. var acc bn256.G1
  124. acc.ScalarMult(G, new(big.Int).SetUint64(0))
  125. var tmp bn256.G1 // avoid allocation every loop
  126. for i := 0; i <= 65536; i++ {
  127. if acc.String() == gb.String() {
  128. return uint32(i), nil
  129. }
  130. tmp.Set(&acc)
  131. acc.Add(&tmp, G)
  132. }
  133. klog.Fatalf("balance not found or > 65535\n")
  134. return 0, nil
  135. }
  136. // this currently does not do semantic checks
  137. func (b *Blockchain) ExecuteTransaction(tx *Transaction) bool {
  138. // Todo check whether all the public keys exist in the chain or not
  139. for i := range tx.statement.Publickeylist {
  140. if _, ok := b.balances[tx.statement.Publickeylist[i].String()]; !ok { // note these are pointer and updated real time
  141. return false
  142. }
  143. }
  144. if tx.proof.Verify(tx.statement) {
  145. // this should be atomic, either all should be done or none at all
  146. for i := range tx.statement.Publickeylist {
  147. ebalance := b.balances[tx.statement.Publickeylist[i].String()] // note these are pointer and updated real time
  148. ebalance.C[0].Add(new(bn256.G1).Set(&ebalance.C[0]), tx.statement.C[i])
  149. ebalance.C[1].Add(new(bn256.G1).Set(&ebalance.C[1]), tx.statement.D)
  150. }
  151. return true
  152. }
  153. return false
  154. }
  155. // generate proof etc
  156. func (b *Blockchain) BuildTransaction(sender *KeyPair, receiver_publickey *bn256.G1, value uint32, anonset_publickeys []*bn256.G1) *Transaction {
  157. var tx Transaction
  158. var publickeylist, C, CLn, CRn []*bn256.G1
  159. var D bn256.G1
  160. anonset_publickeys_copy := make([]*bn256.G1, len(anonset_publickeys))
  161. copy(anonset_publickeys_copy, anonset_publickeys)
  162. var buf [8]byte
  163. _, err := rand.Read(buf[:])
  164. if err != nil {
  165. panic("cannot seed math/rand package with cryptographically secure random number generator")
  166. }
  167. mrand.Seed(int64(binary.LittleEndian.Uint64(buf[:]))) // mrand shuffle is backed by crypto seed
  168. var witness_index []int
  169. for i := 0; i < 2+len(anonset_publickeys); i++ { // todocheck whether this is power of 2 or not
  170. witness_index = append(witness_index, i)
  171. }
  172. for {
  173. mrand.Shuffle(len(witness_index), func(i, j int) {
  174. witness_index[i], witness_index[j] = witness_index[j], witness_index[i]
  175. })
  176. // make sure sender and receiver are not both odd or both even
  177. // sender will always be at witness_index[0] and receiver will always be at witness_index[1]
  178. if witness_index[0]%2 != witness_index[1]%2 {
  179. break
  180. }
  181. }
  182. // Lots of ToDo for this, enables satisfying lots of other things
  183. r := RandomScalar() // revealing this will disclose the amount and the sender and receiver and separate anonymouse rings memeber
  184. for i := 0; i < 2+len(anonset_publickeys); i++ {
  185. switch i {
  186. case witness_index[0]:
  187. publickeylist = append(publickeylist, sender.y)
  188. case witness_index[1]:
  189. publickeylist = append(publickeylist, receiver_publickey)
  190. default:
  191. publickeylist = append(publickeylist, anonset_publickeys_copy[0])
  192. anonset_publickeys_copy = anonset_publickeys_copy[1:]
  193. }
  194. }
  195. for i := range publickeylist { // setup commitments
  196. var x bn256.G1
  197. switch {
  198. case i == witness_index[0]:
  199. x.ScalarMult(G, new(big.Int).SetInt64(0-int64(value))) // decrease senders balance
  200. case i == witness_index[1]:
  201. x.ScalarMult(G, new(big.Int).SetInt64(int64(value))) // increase receiver's balance
  202. default:
  203. x.ScalarMult(G, new(big.Int).SetInt64(0))
  204. }
  205. x.Add(new(bn256.G1).Set(&x), new(bn256.G1).ScalarMult(publickeylist[i], r)) // hide all commitments behind r
  206. C = append(C, &x)
  207. }
  208. D.ScalarMult(G, r)
  209. for i := range publickeylist {
  210. var ll, rr bn256.G1
  211. ebalance := b.balances[publickeylist[i].String()] // note these are taken from the chain live
  212. ll.Add(&ebalance.C[0], C[i])
  213. CLn = append(CLn, &ll)
  214. rr.Add(&ebalance.C[1], &D)
  215. CRn = append(CRn, &rr)
  216. }
  217. // time for bullets-sigma
  218. statement := GenerateStatement(CLn, CRn, publickeylist, C, &D) // generate statement
  219. statement.roothash = new(big.Int).SetUint64(10) // currently it is a dummy param, until blockchain hash persistance
  220. balance, _ := b.ReadBalance(sender.y, sender.x)
  221. witness := GenerateWitness(sender.x, r, value, balance-value, witness_index)
  222. u := new(bn256.G1).ScalarMult(HashToPoint(HashtoNumber(append([]byte(PROTOCOL_CONSTANT), convertbiginttobyte(statement.roothash)...))), sender.x) // this should be moved to generate proof
  223. Print(statement, witness)
  224. tx.statement = statement
  225. tx.proof = GenerateProof(statement, witness, u)
  226. return &tx
  227. }
  228. func Print(s *Statement, w *Witness) {
  229. for i := range s.CLn {
  230. klog.V(1).Infof("CLn[%d] %s\n", i, s.CLn[i].String())
  231. }
  232. for i := range s.CRn {
  233. klog.V(1).Infof("CRn[%d] %s\n", i, s.CRn[i].String())
  234. }
  235. for i := range s.Publickeylist {
  236. klog.V(1).Infof("P[%d] %s\n", i, s.Publickeylist[i].String())
  237. }
  238. for i := range s.C {
  239. klog.V(1).Infof("C[%d] %s\n", i, s.C[i].String())
  240. }
  241. klog.V(1).Infof("D: %s\n", s.D.String())
  242. klog.V(1).Infof("Merkle roothash): %s\n", s.roothash)
  243. klog.V(1).Infof("secretkey 0x%s\n", w.SecretKey.Text(16))
  244. klog.V(1).Infof("R 0x%s\n", w.R.Text(16))
  245. klog.V(1).Infof("Value %d\n", w.TransferAmount)
  246. klog.V(1).Infof("Balance %d\n", w.Balance)
  247. klog.V(1).Infof("index %d\n", w.index)
  248. }
  249. func (tx *Transaction) Size() int {
  250. return tx.statement.Size() + tx.proof.Size()
  251. }
  252. func (s *Statement) Size() int {
  253. return (len(s.CLn)+len(s.CRn)+len(s.Publickeylist)+len(s.C))*POINT_SIZE + 2*FIELDELEMENT_SIZE
  254. }
  255. // statement hash
  256. func (s *Statement) Hash() *big.Int {
  257. var input []byte
  258. for i := range s.CLn {
  259. input = append(input, s.CLn[i].Marshal()...)
  260. }
  261. for i := range s.CRn {
  262. input = append(input, s.CRn[i].Marshal()...)
  263. }
  264. for i := range s.C {
  265. input = append(input, s.C[i].Marshal()...)
  266. }
  267. input = append(input, s.D.Marshal()...)
  268. for i := range s.Publickeylist {
  269. input = append(input, s.Publickeylist[i].Marshal()...)
  270. }
  271. input = append(input, convertbiginttobyte(s.roothash)...)
  272. return reducedhash(input)
  273. }
  274. // generate statement
  275. func GenerateStatement(CLn, CRn, publickeylist, C []*bn256.G1, D *bn256.G1) *Statement {
  276. return &Statement{CLn: CLn, CRn: CRn, Publickeylist: publickeylist, C: C, D: D}
  277. }
  278. // generate witness
  279. func GenerateWitness(secretkey, r *big.Int, TransferAmount, Balance uint32, index []int) *Witness {
  280. return &Witness{SecretKey: secretkey, R: r, TransferAmount: TransferAmount, Balance: Balance, index: index}
  281. }
  282. // converts a big int to 32 bytes, prepending zeroes
  283. func convertbiginttobyte(x *big.Int) []byte {
  284. var dummy [128]byte
  285. joined := append(dummy[:], x.Bytes()...)
  286. return joined[len(joined)-32:]
  287. }