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.

447 lines
12KB

  1. package main
  2. //import "fmt"
  3. import "math/big"
  4. //import "crypto/rand"
  5. //import "encoding/hex"
  6. import "github.com/clearmatics/bn256"
  7. //import "golang.org/x/crypto/sha3"
  8. type FieldVector struct {
  9. vector []*big.Int
  10. }
  11. func NewFieldVector(input []*big.Int) *FieldVector {
  12. return &FieldVector{vector: input}
  13. }
  14. func (fv *FieldVector) Length() int {
  15. return len(fv.vector)
  16. }
  17. // slice and return
  18. func (fv *FieldVector) Slice(start, end int) *FieldVector {
  19. var result FieldVector
  20. for i := start; i < end; i++ {
  21. result.vector = append(result.vector, new(big.Int).Set(fv.vector[i]))
  22. }
  23. return &result
  24. }
  25. //copy and return
  26. func (fv *FieldVector) Clone() *FieldVector {
  27. return fv.Slice(0, len(fv.vector))
  28. }
  29. func (fv *FieldVector) SliceRaw(start, end int) []*big.Int {
  30. var result FieldVector
  31. for i := start; i < end; i++ {
  32. result.vector = append(result.vector, new(big.Int).Set(fv.vector[i]))
  33. }
  34. return result.vector
  35. }
  36. func (fv *FieldVector) Sum() *big.Int {
  37. var accumulator big.Int
  38. for i := range fv.vector {
  39. var accopy big.Int
  40. accopy.Add(&accumulator, fv.vector[i])
  41. accumulator.Mod(&accopy, bn256.Order)
  42. }
  43. return &accumulator
  44. }
  45. func (fv *FieldVector) Add(addendum *FieldVector) *FieldVector {
  46. var result FieldVector
  47. if len(fv.vector) != len(addendum.vector) {
  48. panic("mismatched number of elements")
  49. }
  50. for i := range fv.vector {
  51. var ri big.Int
  52. ri.Mod(new(big.Int).Add(fv.vector[i], addendum.vector[i]), bn256.Order)
  53. result.vector = append(result.vector, &ri)
  54. }
  55. return &result
  56. }
  57. func (gv *FieldVector) AddConstant(c *big.Int) *FieldVector {
  58. var result FieldVector
  59. for i := range gv.vector {
  60. var ri big.Int
  61. ri.Mod(new(big.Int).Add(gv.vector[i], c), bn256.Order)
  62. result.vector = append(result.vector, &ri)
  63. }
  64. return &result
  65. }
  66. func (fv *FieldVector) Hadamard(exponent *FieldVector) *FieldVector {
  67. var result FieldVector
  68. if len(fv.vector) != len(exponent.vector) {
  69. panic("mismatched number of elements")
  70. }
  71. for i := range fv.vector {
  72. result.vector = append(result.vector, new(big.Int).Mod(new(big.Int).Mul(fv.vector[i], exponent.vector[i]), bn256.Order))
  73. }
  74. return &result
  75. }
  76. func (fv *FieldVector) InnerProduct(exponent *FieldVector) *big.Int {
  77. if len(fv.vector) != len(exponent.vector) {
  78. panic("mismatched number of elements")
  79. }
  80. accumulator := new(big.Int)
  81. for i := range fv.vector {
  82. tmp := new(big.Int).Mod(new(big.Int).Mul(fv.vector[i], exponent.vector[i]), bn256.Order)
  83. accumulator.Add(accumulator, tmp)
  84. accumulator.Mod(accumulator, bn256.Order)
  85. }
  86. return accumulator
  87. }
  88. func (fv *FieldVector) Negate() *FieldVector {
  89. var result FieldVector
  90. for i := range fv.vector {
  91. result.vector = append(result.vector, new(big.Int).Mod(new(big.Int).Neg(fv.vector[i]), bn256.Order))
  92. }
  93. return &result
  94. }
  95. func (fv *FieldVector) Flip() *FieldVector {
  96. var result FieldVector
  97. for i := range fv.vector {
  98. result.vector = append(result.vector, new(big.Int).Set(fv.vector[(len(fv.vector)-i)%len(fv.vector)]))
  99. }
  100. return &result
  101. }
  102. func (fv *FieldVector) Times(multiplier *big.Int) *FieldVector {
  103. var result FieldVector
  104. for i := range fv.vector {
  105. res := new(big.Int).Mul(fv.vector[i], multiplier)
  106. res.Mod(res, bn256.Order)
  107. result.vector = append(result.vector, res)
  108. }
  109. return &result
  110. }
  111. func (fv *FieldVector) Invert() *FieldVector {
  112. var result FieldVector
  113. for i := range fv.vector {
  114. result.vector = append(result.vector, new(big.Int).ModInverse(fv.vector[i], bn256.Order))
  115. }
  116. return &result
  117. }
  118. func (fv *FieldVector) Concat(addendum *FieldVector) *FieldVector {
  119. var result FieldVector
  120. for i := range fv.vector {
  121. result.vector = append(result.vector, new(big.Int).Set(fv.vector[i]))
  122. }
  123. for i := range addendum.vector {
  124. result.vector = append(result.vector, new(big.Int).Set(addendum.vector[i]))
  125. }
  126. return &result
  127. }
  128. func (fv *FieldVector) Extract(parity bool) *FieldVector {
  129. var result FieldVector
  130. remainder := 0
  131. if parity {
  132. remainder = 1
  133. }
  134. for i := range fv.vector {
  135. if i%2 == remainder {
  136. result.vector = append(result.vector, new(big.Int).Set(fv.vector[i]))
  137. }
  138. }
  139. return &result
  140. }
  141. type FieldVectorPolynomial struct {
  142. coefficients []*FieldVector
  143. }
  144. func NewFieldVectorPolynomial(inputs ...*FieldVector) *FieldVectorPolynomial {
  145. fv := &FieldVectorPolynomial{}
  146. for _, input := range inputs {
  147. fv.coefficients = append(fv.coefficients, input.Clone())
  148. }
  149. return fv
  150. }
  151. func (fv *FieldVectorPolynomial) Length() int {
  152. return len(fv.coefficients)
  153. }
  154. func (fv *FieldVectorPolynomial) Evaluate(x *big.Int) *FieldVector {
  155. result := fv.coefficients[0].Clone()
  156. accumulator := new(big.Int).Set(x)
  157. for i := 1; i < len(fv.coefficients); i++ {
  158. result = result.Add(fv.coefficients[i].Times(accumulator))
  159. accumulator.Mul(accumulator, x)
  160. accumulator.Mod(accumulator, bn256.Order)
  161. }
  162. return result
  163. }
  164. func (fv *FieldVectorPolynomial) InnerProduct(other *FieldVectorPolynomial) []*big.Int {
  165. var result []*big.Int
  166. result_length := fv.Length() + other.Length() - 1
  167. for i := 0; i < result_length; i++ {
  168. result = append(result, new(big.Int)) // 0 value fill
  169. }
  170. for i := range fv.coefficients {
  171. for j := range other.coefficients {
  172. tmp := new(big.Int).Set(result[i+j])
  173. result[i+j].Add(tmp, fv.coefficients[i].InnerProduct(other.coefficients[j]))
  174. result[i+j].Mod(result[i+j], bn256.Order)
  175. }
  176. }
  177. return result
  178. }
  179. type PedersenCommitment struct {
  180. X *big.Int
  181. R *big.Int
  182. Params *GeneratorParams
  183. }
  184. func NewPedersenCommitment(params *GeneratorParams, x, r *big.Int) *PedersenCommitment {
  185. pc := &PedersenCommitment{Params: params, X: new(big.Int).Set(x), R: new(big.Int).Set(r)}
  186. return pc
  187. }
  188. func (pc *PedersenCommitment) Commit() *bn256.G1 {
  189. var left, right, result bn256.G1
  190. left.ScalarMult(pc.Params.G, pc.X)
  191. right.ScalarMult(pc.Params.H, pc.R)
  192. result.Add(&left, &right)
  193. return &result
  194. }
  195. func (pc *PedersenCommitment) Add(other *PedersenCommitment) *PedersenCommitment {
  196. var x, r big.Int
  197. x.Mod(new(big.Int).Add(pc.X, other.X), bn256.Order)
  198. r.Mod(new(big.Int).Add(pc.R, other.R), bn256.Order)
  199. return NewPedersenCommitment(pc.Params, &x, &r)
  200. }
  201. func (pc *PedersenCommitment) Times(constant *big.Int) *PedersenCommitment {
  202. var x, r big.Int
  203. x.Mod(new(big.Int).Mul(pc.X, constant), bn256.Order)
  204. r.Mod(new(big.Int).Mul(pc.R, constant), bn256.Order)
  205. return NewPedersenCommitment(pc.Params, &x, &r)
  206. }
  207. type PolyCommitment struct {
  208. coefficient_commitments []*PedersenCommitment
  209. Params *GeneratorParams
  210. }
  211. func NewPolyCommitment(params *GeneratorParams, coefficients []*big.Int) *PolyCommitment {
  212. pc := &PolyCommitment{Params: params}
  213. pc.coefficient_commitments = append(pc.coefficient_commitments, NewPedersenCommitment(params, coefficients[0], new(big.Int).SetUint64(0)))
  214. for i := 1; i < len(coefficients); i++ {
  215. pc.coefficient_commitments = append(pc.coefficient_commitments, NewPedersenCommitment(params, coefficients[i], RandomScalarFixed()))
  216. }
  217. return pc
  218. }
  219. func (pc *PolyCommitment) GetCommitments() []*bn256.G1 {
  220. var result []*bn256.G1
  221. for i := 1; i < len(pc.coefficient_commitments); i++ {
  222. result = append(result, pc.coefficient_commitments[i].Commit())
  223. }
  224. return result
  225. }
  226. func (pc *PolyCommitment) Evaluate(constant *big.Int) *PedersenCommitment {
  227. result := pc.coefficient_commitments[0]
  228. accumulator := new(big.Int).Set(constant)
  229. for i := 1; i < len(pc.coefficient_commitments); i++ {
  230. tmp := new(big.Int).Set(accumulator)
  231. result = result.Add(pc.coefficient_commitments[i].Times(accumulator))
  232. accumulator.Mod(new(big.Int).Mul(tmp, constant), bn256.Order)
  233. }
  234. return result
  235. }
  236. /*
  237. // bother FieldVector and GeneratorVector satisfy this
  238. type Vector interface{
  239. Length() int
  240. Extract(parity bool) Vector
  241. Add(other Vector)Vector
  242. Hadamard( []*big.Int) Vector
  243. Times (*big.Int) Vector
  244. Negate() Vector
  245. }
  246. */
  247. // check this https://pdfs.semanticscholar.org/d38d/e48ee4127205a0f25d61980c8f241718b66e.pdf
  248. // https://arxiv.org/pdf/1802.03932.pdf
  249. var unity *big.Int
  250. func init() {
  251. // primitive 2^28th root of unity modulo q
  252. unity, _ = new(big.Int).SetString("14a3074b02521e3b1ed9852e5028452693e87be4e910500c7ba9bbddb2f46edd", 16)
  253. }
  254. func fft_FieldVector(input *FieldVector, inverse bool) *FieldVector {
  255. length := input.Length()
  256. if length == 1 {
  257. return input
  258. }
  259. // lngth must be multiple of 2 ToDO
  260. if length%2 != 0 {
  261. panic("length must be multiple of 2")
  262. }
  263. //unity,_ := new(big.Int).SetString("14a3074b02521e3b1ed9852e5028452693e87be4e910500c7ba9bbddb2f46edd",16)
  264. omega := new(big.Int).Exp(unity, new(big.Int).SetUint64((1<<28)/uint64(length)), bn256.Order)
  265. if inverse {
  266. omega = new(big.Int).ModInverse(omega, bn256.Order)
  267. }
  268. even := fft_FieldVector(input.Extract(false), inverse)
  269. odd := fft_FieldVector(input.Extract(true), inverse)
  270. omegas := []*big.Int{new(big.Int).SetUint64(1)}
  271. for i := 1; i < length/2; i++ {
  272. omegas = append(omegas, new(big.Int).Mod(new(big.Int).Mul(omegas[i-1], omega), bn256.Order))
  273. }
  274. omegasv := NewFieldVector(omegas)
  275. result := even.Add(odd.Hadamard(omegasv)).Concat(even.Add(odd.Hadamard(omegasv).Negate()))
  276. if inverse {
  277. result = result.Times(new(big.Int).ModInverse(new(big.Int).SetUint64(2), bn256.Order))
  278. }
  279. return result
  280. }
  281. // this is exactly same as fft_FieldVector, alternate implementation
  282. func fftints(input []*big.Int) (result []*big.Int) {
  283. size := len(input)
  284. if size == 1 {
  285. return input
  286. }
  287. //require(size % 2 == 0, "Input size is not a power of 2!");
  288. unity, _ := new(big.Int).SetString("14a3074b02521e3b1ed9852e5028452693e87be4e910500c7ba9bbddb2f46edd", 16)
  289. omega := new(big.Int).Exp(unity, new(big.Int).SetUint64((1<<28)/uint64(size)), bn256.Order)
  290. even := fftints(extractbits(input, 0))
  291. odd := fftints(extractbits(input, 1))
  292. omega_run := new(big.Int).SetUint64(1)
  293. result = make([]*big.Int, len(input), len(input))
  294. for i := 0; i < len(input)/2; i++ {
  295. temp := new(big.Int).Mod(new(big.Int).Mul(odd[i], omega_run), bn256.Order)
  296. result[i] = new(big.Int).Mod(new(big.Int).Add(even[i], temp), bn256.Order)
  297. result[i+size/2] = new(big.Int).Mod(new(big.Int).Sub(even[i], temp), bn256.Order)
  298. omega_run = new(big.Int).Mod(new(big.Int).Mul(omega, omega_run), bn256.Order)
  299. }
  300. return result
  301. }
  302. func extractbits(input []*big.Int, parity int) (result []*big.Int) {
  303. result = make([]*big.Int, len(input)/2, len(input)/2)
  304. for i := 0; i < len(input)/2; i++ {
  305. result[i] = new(big.Int).Set(input[2*i+parity])
  306. }
  307. return
  308. }
  309. func fft_GeneratorVector(input *GeneratorVector, inverse bool) *GeneratorVector {
  310. length := input.Length()
  311. if length == 1 {
  312. return input
  313. }
  314. // lngth must be multiple of 2 ToDO
  315. if length%2 != 0 {
  316. panic("length must be multiple of 2")
  317. }
  318. // unity,_ := new(big.Int).SetString("14a3074b02521e3b1ed9852e5028452693e87be4e910500c7ba9bbddb2f46edd",16)
  319. omega := new(big.Int).Exp(unity, new(big.Int).SetUint64((1<<28)/uint64(length)), bn256.Order)
  320. if inverse {
  321. omega = new(big.Int).ModInverse(omega, bn256.Order)
  322. }
  323. even := fft_GeneratorVector(input.Extract(false), inverse)
  324. //fmt.Printf("exponent_fft %d %s \n",i, exponent_fft.vector[i].Text(16))
  325. odd := fft_GeneratorVector(input.Extract(true), inverse)
  326. omegas := []*big.Int{new(big.Int).SetUint64(1)}
  327. for i := 1; i < length/2; i++ {
  328. omegas = append(omegas, new(big.Int).Mod(new(big.Int).Mul(omegas[i-1], omega), bn256.Order))
  329. }
  330. omegasv := omegas
  331. result := even.Add(odd.Hadamard(omegasv)).Concat(even.Add(odd.Hadamard(omegasv).Negate()))
  332. if inverse {
  333. result = result.Times(new(big.Int).ModInverse(new(big.Int).SetUint64(2), bn256.Order))
  334. }
  335. return result
  336. }
  337. func Convolution(exponent *FieldVector, base *GeneratorVector) *GeneratorVector {
  338. size := base.Length()
  339. exponent_fft := fft_FieldVector(exponent.Flip(), false)
  340. /*exponent_fft2 := fftints( exponent.Flip().vector) // aternate implementation proof checking
  341. for i := range exponent_fft.vector{
  342. fmt.Printf("exponent_fft %d %s \n",i, exponent_fft.vector[i].Text(16))
  343. fmt.Printf("exponent_ff2 %d %s \n",i, exponent_fft2[i].Text(16))
  344. }
  345. */
  346. temp := fft_GeneratorVector(base, false).Hadamard(exponent_fft.vector)
  347. return fft_GeneratorVector(temp.Slice(0, size/2).Add(temp.Slice(size/2, size)).Times(new(big.Int).ModInverse(new(big.Int).SetUint64(2), bn256.Order)), true)
  348. // using the optimization described here https://dsp.stackexchange.com/a/30699
  349. }