golang 实现 bitcoin内核:编码实现椭圆曲线上的点

比特币在很大程度上依赖于一个称为椭圆曲线的数学对象，如果没有这个数学结构，比特币就像海滩上的城堡，随时可能崩溃。什么是椭圆曲线，它的方程是这样的：y^2 = x^3 + ax + b，它的形状就像下面这样：

在这里插入图片描述

对于比特币，它的椭圆曲线有一个名字：secp256k1，方程是y^2 = x^3 + 7。我们不太关心椭圆曲线的功能，我们关心的是曲线上的一组特定点，让我们为曲线上的点编写一些代码。首先，我们在椭圆曲线文件夹下添加一个名为point.go的新文件，并添加以下代码：

在代码中，我们用a和b的系数初始化椭圆曲线点，并通过计算方程两边的值来检查点(x,y)是否在曲线上，如果它们不相等，我们会抛出一个panic。当我们检查两个点是否相等时，我们需要比较它的四个组成部分：a、b、x、y。

让我们尝试从main函数中创建两个椭圆点：

func main() {
	/*
		check pint(-1, -1) on y^2 = x^3 + 5x + 7 or not
	*/
	ecc.NewEllipticPoint(big.NewInt(int64(-1)), big.NewInt(int64(-1)),
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	fmt.Println("point(-1, -1) is on curve y^2=x^3+5x+7")
	/*
		check pint(-1, -2) on y^2 = x^3 + 5x + 7 or not
	*/
	ecc.NewEllipticPoint(big.NewInt(int64(-1)), big.NewInt(int64(-2)),
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	fmt.Println("point(-1, -2) is on curve y^2=x^3+5x+7")
}

我们通过使用其创建函数NewEllipticPoint构造point结构，前两个参数是点的坐标(x,y)，如果点不在曲线上，就会发生panic，否则我们可以打印出跟随创建函数的消息，让我们运行代码进行检查，使用go run main.go，得到以下结果：

```go
point(-1, -1) is on curve y^2=x^3+5x+7
panic: point:(-1, -2) is not on the curve with a: 5, b:7

我们可以看到点 (-1,-1) 在曲线上，但点 (-1, -2) 不在曲线上，现在我们来练习一下，请检查点 (2,4)、(18,77)、(5,7) 是否在曲线上。

现在我们来讨论关键点，即给定椭圆曲线上的点 A(x1,y1) 和 B(x2,y2)，我们如何定义它们的加法。我们用一条线连接这两个点，并延伸这条线，如果延伸的线可以在第三个点 C 处与曲线相交，如下所示：

那么与 C 在 x 轴上对称的点被定义为 A+B。同样适用于 A+C，当我们用一条线连接 A 和 C 时，曲线上与之相交的第三个点是 B，然后我们找到与 B 在 x 轴上对称的点，将是 A+C 的结果，B+C 也是如此。

这里的点加法定义具有以下属性：

交换性，即 A+B = B+A，这是显而易见的。
结合性，即 (A+B) + C = A + (B+C)

下图显示了 (A+B)+C：
截屏2024-03-22 15 44 07

下图显示了 A + (B+C)：
截屏2024-03-22 15 47 24

有一个特殊情况，即 A 和 B 在同一垂直线上，无论我们如何延长这条线，都不可能有第三个点与曲线相交，但我们可以给这个不存在的第三点一个名称，称为单位点，标记为 I，并定义任何点 P 在曲线上，如果它与单位点相加，结果仍然是它自己，即 P + I = P：

如果 A 和 B 是曲线上的同一个点呢？我们将此情况推迟到后面讨论，现在让我们为点加法添加一些代码。首先，我们处理一个简单情况，即至少一个参与加法的点是单位点，单位点的 x 和 y 设置为 nil，我们有如下代码：

func NewEllipticPoint(x *big.Int, y *big.Int, a *big.Int, b *big.Int) *Point {
       if x == nil && y == nil {
		return &Point{
			a: a,
			b: b,
			x: x,
			y: y,
		}
	}

	//first check (x,y) on the curve defined by a, b
	left := OpOnBig(y, big.NewInt(int64(2)), EXP)
	x3 := OpOnBig(x, big.NewInt(int64(3)), EXP)
	ax := OpOnBig(a, x, MUL)
	right := OpOnBig(OpOnBig(x3, ax, ADD), b, ADD)
	//if x and y are nil, then its identity point and
	//we don't need to check it on curve
	if left.Cmp(right) != 0 {
		err := fmt.Sprintf("point:(%v, %v) is not on the curve with a: %v, b:%v\n", x, y, a, b)
		panic(err)
	}

	return &Point{
		a: a,
		b: b,
		x: x,
		y: y,
	}
}

func (p *Point) Add(other *Point) *Point {
	//check points are on the same curve
	if p.a.Cmp(other.a) != 0 || p.b.Cmp(other.b) != 0 {
		panic("given two points are not on the same curve")
	}

	if p.x == nil {
		//current point is identity point
		return other
	}

	if other.x == nil {
		//the other point is identity
		return p
	}

/*
		another simple case, two points on the same vertical line, that is
		they have the same x but inverse y, the addition of them should be
		identity
	*/
	if p.x.Cmp(other.x) == 0 &&
		OpOnBig(p.y, other.y, ADD).Cmp(big.NewInt(int64(0))) == 0 {
		return &Point{
			x: nil,
			y: nil,
			a: p.a,
			b: p.b,
		}
	}

	//TODO
	return nil
}

func (p *Point) String() string {
	return fmt.Sprintf("x: %s, y: %s, a: %s, b: %s\n", p.x.String(),
		p.y.String(), p.a.String(), p.b.String())
}

让我们通过将一个点与单位点相加来测试代码，结果应该是该点本身：


func main() {
	p := ecc.NewEllipticPoint(big.NewInt(int64(-1)), big.NewInt(int64(-1)),
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	identity := ecc.NewEllipticPoint(nil, nil,
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	fmt.Printf("p is :%s\n", p)

	res := p.Add(identity)
	fmt.Printf("result of point p add to identity is: %s\n", res)

        p2 := ecc.NewEllipticPoint(big.NewInt(int64(-1)), big.NewInt(int64(1)),
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	res = p.Add(p2)
	fmt.Printf("result of adding points on vertical line: %s", res)
}

运行上面的代码将得到以下结果：


p is :(x: -1, y: -1, a: 5, b: 7)

result of point p add to identity is: (x: -1, y: -1, a: 5, b: 7)

result of adding points on vertical line: (x: <nil>, y: <nil>, a: 5, b: 7)

如果没有点是单位点，那么我们需要一些数学推导来计算加法。给定 A(x1,y1)、B(x2,y2)，我们需要知道 C(x3,y3)，首先我们找到线 AB 的函数。

线 AB 的斜率为 s=(y2-y1)/(x2-x1)，线 AB 的函数为 y=s(x-x1)+y1

将 y 代入方程 y^2=x3+ax+b，得到：[s(x-x1)+y1]^2=x3+ax+b，将左侧展开并移至右侧，我们得到：

我们确定 x1、x2、x3 是上面和下面方程的解：

根据维埃塔定理，相同阶次的项的系数应该相等，因此我们有：

s^2 = x1+x2+x3 => x3 = s^2 - x1 - x2

这给了我们 x3 的值，我们可以将其代入线的函数中得到 y3：

y=s(x-x1)+y1=> y3=s(x3-x1)+y1

现在我们得到了 C，并记住我们需要将其在 x 轴上反射，因此 A+B 为 (-s^2-x1-x2, -[s(x3-x1)+y1])。

让我们为此编写代码：

func (p *Point) Add(other *Point) *Point {
 ...
 //找出线 AB 的斜率
	//x1 = p.x, y1 = p.y, x2 = other.x, y2 = other.y
	numerator := OpOnBig(other.y, p.y, SUB)
	denominator := OpOnBig(other.x, p.x, SUB)
	//s = (y2-y2)/(x2-x1)
	slope := OpOnBig(numerator, denominator, DIV)

	//-s^2
	slopeSqrt := OpOnBig(slope, big.NewInt(int64(2)), EXP)
	x3 := OpOnBig(OpOnBig(slopeSqrt, p.x, SUB), other.x, SUB)
	//x3-x1
	x3Minusx1 := OpOnBig(x3, p.x, SUB)
	//y3=s(x3-x1)+y1
	y3 := OpOnBig(OpOnBig(slope, x3Minusx1, MUL), p.y, ADD)
	//-y3
	minusY3 := OpOnBig(y3, big.NewInt(int64(-1)), MUL)

	return &Point{
		x: x3,
		y: minusY3,
		a: p.a,
		b: p.b,
	}
}

让我们测试上面的代码：


func main() {
	//C = A(2,5) + B(-1, -1)
	A := ecc.NewEllipticPoint(big.NewInt(int64(2)), big.NewInt(int64(5)),
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	B := ecc.NewEllipticPoint(big.NewInt(int64(-1)), big.NewInt(int64(-1)),
		big.NewInt(int64(5)), big.NewInt(int64(7)))
	C := A.Add(B)
	fmt.Printf("A(2,5) + B(-1,-1) = %s\n", C)
}

上述代码的运行结果是：


A(2,5) + B(-1,-1) = (x: 3, y: -7, a: 5, b: 7)

如果你有疑虑，请使用纸和笔检查结果，我可以保证结果是正确的。还有一种特殊情况需要处理，那就是当 A=B 时，在这种情况下，线 AB 变成了椭圆曲线的切线：
截屏2024-03-23 03 44 04

这次我们不能轻易地获得线的斜率，我们需要微积分的帮助。为了找到曲线上的切线斜率，我们需要计算该点的导数，对于曲线的函数 y^2 = x^3 + ax+b，我们对两边的点 x 进行导数计算，得到： d(y^2)/dx = d(x^3+ax+b)/dx -> 2y * dy/dx = 3x^2 + a -> dy/dx = (3x^2+a)/2y，因此我们只需更改斜率的计算，其余步骤保持不变，以下是代码：


func (p *Point) Add(other *Point) *Point {
...
//找出线 AB 的斜率
	//x1 = p.x, y1 = p.y, x2 = other.x, y2 = other.y
	var numerator *big.Int
	var denominator *big.Int
	if p.x.Cmp(other.x) == 0 && p.y.Cmp(other.y) == 0 {
		//两个点相同，计算切线的斜率
		//分子为 (3x^2+a)
		xSqrt := OpOnBig(p.x, big.NewInt(int64(2)), EXP)
		threeXSqrt := OpOnBig(xSqrt, big.NewInt(int64(3)), MUL)
		numerator = OpOnBig(threeXSqrt, p.a, ADD)
		//分母为 2y
		denominator = OpOnBig(p.y, big.NewInt(int64(2)), MUL)
	} else {
		//s = (y2-y2)/(x2-x1)
		numerator = OpOnBig(other.y, p.y, SUB)
		denominator = OpOnBig(other.x, p.x, SUB)
	}
...
}

让我们测试这个案例：


func main() {
...
        //B=(-1,-1) C=B+B
	C = B.Add(B)
	fmt.Printf("B(-1,-1) + B(-1,-1) = %s\n", C)
}

上述代码的结果是：


B(-1,-1) + B(-1,-1) = (x: 18, y: 77, a: 5, b: 7)

完整代码获取点击此处

更多有趣内容请查看：
http://m.study.163.com/provider/7600199/index.htm?share=2&shareId=7600199
也可登录我的公众号：Coding 迪斯尼

golang 实现 bitcoin内核:编码实现椭圆曲线上的点

相关文章

[免费]基于Python的Django+Vue3在线考试系统【论文+源码+SQL脚本】

API网关 - JWT认证；原理概述与具体实践样例

【保姆级教程】实操 Linux 磁盘管理：硬盘选型分区挂载

平衡二叉树(递归）

雷池社区版新版本功能防绕过人机验证解析

黑龙江某涝区泵闸站自动化、信息化改造项目案例

Java 多线程（八）—— 锁策略，synchronized 的优化，JVM 与编译器的锁优化，ReentrantLock，CAS

【Spring IOC】实现一个简单的 Spring 容器

非线性数据结构之图

【算法】——滑动窗口专题

目前主流的人工智能学习框架有哪些？

揭开自然语言处理（NLP）的神秘面纱

C#：强大而优雅的编程语言

SQL CASE表达式与窗口函数

C++之位算法

【OJ题解】C++实现字符串大数相乘：无BigInteger库的字符串乘积解决方案

用Python将PDF表格提取到文本、CSV和Excel文件中

如何在 IntelliJ IDEA 中调整 `Ctrl+/` 快捷键生成注释的位置

深入理解对象池 sync.Pool

项目管理（软设软考高频）