当前位置：首页 > article >正文

golang 实现比特币内核：椭圆曲线有限域的代码实现

article 2024/11/6 2:46:40

让我们开始有限域的代码之旅，进入一个空目录，创建一个名为bitcoin的新文件夹，在bitcoin目录中，再创建一个名为elliptic-curve的新文件夹。在该文件夹中初始化一个新的包，运行以下命令：


go init mod elliptic_curve

然后我们创建一个新文件finite-element，我们将在这里编写有限域元素的代码，将以下代码放入文件中：


package elliptic_curve

import (
	"fmt"
)

type FieldElement struct {
	order uint64 // field的阶
	num   uint64 // 该元素在域中的值
}

func NewFieldElement(order uint64, num uint64) FieldElement {
	/*
		FieldElement的构造函数，相当于Python中的__init__
	*/

	if num >= order || num < 0 {
		err := fmt.Sprintf("Num not in the range from 0 to %d", order)
		panic(err)
	}

	return FieldElement{
		order: order,
		num:   num,
	}
}

func (f FieldElement) String() string {
	// 将对象格式化为可打印的字符串，相当于Python中的__repr__
	return fmt.Sprintf("FieldElement{order: %d, num: %d}", f.order, f.num)
}

func (f FieldElement) EqualTo(other FieldElement) bool {
	/*
		两个域元素在阶和数值相等时才相等
	*/
	return f.order == other.order && f.num == other.num
}

现在我们已经有了有限域元素的基本结构，让我们添加更多的方法。对于域元素有两种操作，一种是“+”即模加法，另一种是“.”即模乘法。让我们看看如何进行加法操作：


func (f *FieldElement) Add(other *FieldElement) *FieldElement {
	if other.order != f.order {
		panic("add need to do on field element with the same order")
	}

	// 记得做模运算
	return NewFieldElement(f.order, (f.num+other.num)%f.order)
}

func (f *FieldElement) Negate() *FieldElement {
	/*
		对于一个域元素a，其负值是域中另一个元素b，使得(a + b) % order= 0
		（注意模数是order），由于域中元素的值小于其阶，我们可以通过order - a得到a的负值。
	*/

	return NewFieldElement(f.order, f.order-f.num)
}

func (f *FieldElement) Substract(other *FieldElement) *FieldElement {
	// 如何实现？
	return nil
}

现在在main.go文件中调用以上代码来检查结果，如下所示：


package main

import (
	ecc "elliptic_curve"
	"fmt"
)

func main() {
	/*
		构建阶为57的域，并进行加减法操作
	*/
	f44 := ecc.NewFieldElement(57, 44)
	f33 := ecc.NewFieldElement(57, 33)
	// 44 + 33 等于 (44+33) % 57 等于 20
	res := f44.Add(f33)
	fmt.Printf("域元素44加上域元素33结果是：%v\n", res)
	// -44是域元素44的负值，即57 - 44 = 13
	fmt.Printf("域元素44的负值是：%v\n", f44.Negate())
}

然后运行以下命令：


go run main.go

如果一切正常，您将看到以下结果：


field element 44 add to field element 33 is : FieldElement{order: 57, num: 20}
negate of field element 44 is : FieldElement{order: 57, num: 37}```

现在我们解决减法的问题，对于域元素a, b，我们希望找到域元素c，使得c = a - b。注意a - b等于a + (-b)，而(-b)是b的负值，这意味着c等于a加上b的负值。让我们将其写入代码：


func (f *FieldElement) Subtract(other *FieldElement) *FieldElement {
	// 首先找到other的负值
	// 将其加上other的负值
	return f.Add(other.Negate())
}

现在在main中添加一些代码来运行Subtract函数：


func main() {
    ....
fmt.Printf("域元素44 - 33结果是：%v\n", f44.Substract(f33))
	fmt.Printf("域元素33 - 44结果是：%v\n", f33.Subtract(f44))

	// 检查 (11+33)%57 == 44
	// 检查 (46 + 44) % 57 == 33
	fmt.Printf("检查46 + 44在57模下结果是%d\n", (46+44)%57)
	// 使用域元素检查
	f46 := ecc.NewFieldElement(57, 46)
	fmt.Printf("域元素46 + 44结果是%v\n", f46.Add(f44))
}

运行代码，我们可以得到以下结果：


field element 44 add to field element 33 is : FieldElement{order: 57, num: 20}
negate of field element 44 is : FieldElement{order: 57, num: 37}
field element 44 - 33 is : FieldElement{order: 57, num: 11}
field element 33 - 44 is : FieldElement{order: 57, num: 46}
check 46 + 44 over modulur 57 is 33
field element 46 + 44 is FieldElement{order: 57, num: 33}

我们可以进行一些简单的算术计算，(46+44) % 57的结果确实是33，这意味着我们的代码逻辑是正确的。接下来我们看看如何添加乘法和幂运算操作，即在模数order下的乘法和幂操作，代码如下：


func (f *FieldElement) checkOrder(other *FieldElement) {
	if other.order != f.order {
		panic("add need to do on field element with the same order")
	}
}

func (f *FieldElement) Multiplie(other *FieldElement) *FieldElement {
	f.checkOrder(other)
	// 在模数order下乘法
	return NewFieldElement(f.order, (f.num*other.num)%f.order)
}

func (f *FieldElement) Power(power int64) *FieldElement {
	return NewFieldElement(f.order, uint64(math.Pow(float64(f.num), float64(power)))%f.order)
}

我们运行新增的代码进行测试，在main.go中添加如下代码：


func main() {
...
    fmt.Printf("元素46自身相乘的结果是：%v\n", f46.Multiplie(f46))
    fmt.Printf("元素46的2次幂是%v\n", f46.Power(2))
}

运行结果是：

multiplie element 46 with itself is :FieldElement{order: 57, num: 7}
element 46 with power to 2 is FieldElement{order: 57, num: 7}

可以看到，元素46的自乘等于其2次幂的计算结果。现在是问题时间了，对于阶为19的有限域，随机选择一个元素k，计算{k . 0, k . 1, … k . 18}，结果会是什么呢？

让我们用代码来解决这个问题，首先我们需要为域元素添加一个方法，使其可以乘以标量数：


func (f *FieldElement) ScalarMul(val uint64) *FieldElement {
	return NewFieldElement(f.order, (f.num*val)%f.order)
}

现在到main.go中，并用以下代码解决问题：


package main

import (
	ecc "elliptic_curve"
	"fmt"
	"math/rand"
)

func SolveField19MultiplieSet() {
	// 随机选择一个1到18的数
	min := 1
	max := 18
	k := rand.Intn(max-min) + min
	fmt.Printf("随机选择的k是：%d\n", k)
	element := ecc.NewFieldElement(19, uint64(k))
	for i := 0; i < 19; i++ {
		fmt.Printf("元素%d乘以%d的结果是%v\n", k, i, element.ScalarMul(uint64(i)))
	}
}

func main() {
	SolveField19MultiplieSet()
}

如果运行以上代码，您可能会得到以下结果：

element 2 multiplie with 0 is FieldElement{order: 19, num: 0}
element 2 multiplie with 1 is FieldElement{order: 19, num: 2}
element 2 multiplie with 2 is FieldElement{order: 19, num: 4}
element 2 multiplie with 3 is FieldElement{order: 19, num: 6}
element 2 multiplie with 4 is FieldElement{order: 19, num: 8}
element 2 multiplie with 5 is FieldElement{order: 19, num: 10}
element 2 multiplie with 6 is FieldElement{order: 19, num: 12}
element 2 multiplie with 7 is FieldElement{order: 19, num: 14}
element 2 multiplie with 8 is FieldElement{order: 19, num: 16}
element 2 multiplie with 9 is FieldElement{order: 19, num: 18}
element 2 multiplie with 10 is FieldElement{order: 19, num: 1}
element 2 multiplie with 11 is FieldElement{order: 19, num: 3}
element 2 multiplie with 12 is FieldElement{order: 19, num: 5}
element 2 multiplie with 13 is FieldElement{order: 19, num: 7}
element 2 multiplie with 14 is FieldElement{order: 19, num: 9}
element 2 multiplie with 15 is FieldElement{order: 19, num: 11}
element 2 multiplie with 16 is FieldElement{order: 19, num: 13}
element 2 multiplie with 17 is FieldElement{order: 19, num: 15}
element 2 multiplie with 18 is FieldElement{order: 19, num: 17}