crate-crypto / go-ipa Goto Github PK

View Code? Open in Web Editor NEW

30.0 3.0 13.0 356 KB

A Go implementation of cryptographic primitives for Verkle Trees

Home Page: https://verkle.dev

License: Apache License 2.0

Go 84.66% Assembly 15.34%

ethereum inner-product-argument verkle

go-ipa's People

Contributors

Stargazers

Watchers

Forkers

gballet jwasinger jsign holiman lcardososantos bamaao boogh46 megaeth-labs advaita-saha

go-ipa's Issues

Failing test on amd64

go-verkle has a test called TestWithRustCompatibility that fails with revision c5abbdb on amd64. For some reason, it doesn't fail on arm.

amd64:

> uname -a
Linux geth-verkle2 5.15.0-1017-aws #21~20.04.1-Ubuntu SMP Fri Aug 5 11:44:14 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
> go test .
--- FAIL: TestWithRustCompatibility (0.00s)
    tree_test.go:950: rust and golang impl are not compatible rust=10ed89d89047bb168baa4e69b8607e260049e928ddbcb2fdd23ea0f4182b1f8a, go=36b47e235a02b9dbe096f929065dbc81e9b096a8e9edc437e9dbfb39af718de0
FAIL
FAIL	github.com/gballet/go-verkle	8.259s
FAIL

and aarch64:

> uname -a
Linux Carina 5.10.65-tegra #1 SMP PREEMPT Mon May 16 20:58:07 PDT 2022 aarch64 aarch64 aarch64 GNU/Linux
> go test .
ok      github.com/gballet/go-verkle    8.159s

On the one hand, it is possible that there is an issue with the test that got revealed once I upgraded go-verkle to c5abbdb, but on the other hand it's still suspicious that it fails on one platform and not another. So I'm creating this issue to track the problem. I have tried to go back a couple revisions, but all versions have the same problem. I will keep looking for the revision that introduced the breaking change when I have a moment.

Cannot perform dynamic linking with go-ipa v0.0.0-20231025140028-3c0104f4b233

Hello !

I'm building go plugins that contain go-ipa in their dependencies (extending go-ethereum capabilities) and I'm now unable to build the dynamic library.
Here's the error I have when building

# github.com/crate-crypto/go-ipa/bandersnatch/fr
asm: element_mul_amd64.s:86: when dynamic linking, R15 is clobbered by a global variable access and is used here: 00013 (/home/mortimr/go/pkg/mod/github.com/crate-crypto/[email protected]/bandersnatch/fr/element_mul_amd64.s:86)      MULXQ   DI, R14, R15

Any idea on how this could get fixed ?

Better space time trade off for multi-exponentiation

Instead of precomputing all of the points in the matrix, we can precompute only the first row.

Using a bucket like method, we can furthermore amortise the doublings across the scalars.

Benchmarks are needed to check what will be the performance degradation with this strategy

DivideOnDomain avoid unnecessary allocations

DivideOnDomain is called multiple times and each time, we allocate a slice to hold the quotient. Instead, we should pass in a pointer and only allocate once

error in polynomial calculation

Here is a sample test modified from @tanishqjasoria:

go version:

var (
	testAccountKeys    = [][]byte{
		{245, 110, 100, 66, 36, 244, 87, 100, 144, 207, 224, 222, 20, 36, 164, 83, 34, 18, 82, 155, 254, 55, 71, 19, 216, 78, 125, 126, 142, 146, 114, 0},
		{245, 110, 100, 66, 36, 244, 87, 100, 144, 207, 224, 222, 20, 36, 164, 83, 34, 18, 82, 155, 254, 55, 71, 19, 216, 78, 125, 126, 142, 146, 114, 1},
		{245, 110, 100, 66, 36, 244, 87, 100, 144, 207, 224, 222, 20, 36, 164, 83, 34, 18, 82, 155, 254, 55, 71, 19, 216, 78, 125, 126, 142, 146, 114, 2},
		{245, 110, 100, 66, 36, 244, 87, 100, 144, 207, 224, 222, 20, 36, 164, 83, 34, 18, 82, 155, 254, 55, 71, 19, 216, 78, 125, 126, 142, 146, 114, 3},
		{245, 110, 100, 66, 36, 244, 87, 100, 144, 207, 224, 222, 20, 36, 164, 83, 34, 18, 82, 155, 254, 55, 71, 19, 216, 78, 125, 126, 142, 146, 114, 4},
	}

	testAccountValues = [][]byte{
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 100, 167, 179, 182, 224, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{197, 210, 70, 1, 134, 247, 35, 60, 146, 126, 125, 178, 220, 199, 3, 192, 229, 0, 182, 83, 202, 130, 39, 59, 123, 250, 216, 4, 93, 133, 164, 112},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	}
	testAccountRootCommitmentRust, _ = hex.DecodeString("551dbfb30ba563ce071cd5ea69b1c28467c018f740d86cf9828c4cc32c4b0305")
)

func TestWithRustCompatibility(t *testing.T) {
	root := New()
	for i, key := range testAccountKeys {
		if i != 3 {
			continue
		}
		err := root.Insert(key, testAccountValues[i], nil)
		if err != nil {
			t.Fatalf("error inserting: %v", err)
		}
	}
	commitment := root.ComputeCommitment().Bytes()
	if !bytes.Equal(commitment[:], testAccountRootCommitmentRust) {
		t.Fatalf("rust and golang impl are not compatible rust=%x, go=%x", testAccountRootCommitmentRust, golangRoot)
	}
}

rust version:

    #[test]
    fn insert_keys_test_state_root() {
        let test_account_keys: Vec<[u8; 32]> = vec![
            [
                245, 110, 100, 66, 36, 244, 87, 100, 144, 207, 224, 222, 20, 36, 164, 83, 34, 18,
                82, 155, 254, 55, 71, 19, 216, 78, 125, 126, 142, 146, 114, 3,
            ],
        ];

        let test_account_values: Vec<[u8; 32]> = vec![
            [
                197, 210, 70, 1, 134, 247, 35, 60, 146, 126, 125, 178, 220, 199, 3, 192, 229, 0,
                182, 83, 202, 130, 39, 59, 123, 250, 216, 4, 93, 133, 164, 112,
            ],
        ];

        let test_account_root_commitment_golang =
            "baa4117e95c654173f32522f6c5490826c0e23034b2675391d6951b7545cec95";

        let db = MemoryDb::new();
        let mut trie = Trie::new(TestConfig::new(db));

        for i in 0..test_account_keys.len() {
            trie.insert_single(test_account_keys[i], test_account_values[i]);
        }

        let mut hash = [0u8; 32];
        let root = trie.root_hash();
        root.serialize(&mut hash[..]).unwrap();
        println!("rustRoot{:?}", hex::encode(hash));
        println!("golangRoot{:?}", test_account_root_commitment_golang);
        assert_eq!(hex::encode(hash), test_account_root_commitment_golang);
    }

I traced it down to the polynomial evaluation for C1. The inputs are the same, the outputs are different:

inputs

go's SRS[6] and SRS[7]

github.com/crate-crypto/go-ipa/bandersnatch.PointAffine {
	X: github.com/crate-crypto/go-ipa/bandersnatch/fp.Element [762121577226591572,7821530775196431310,5100373047440631974,5742196019503850925],
	Y: github.com/crate-crypto/go-ipa/bandersnatch/fp.Element [12310760972179283916,8841254867580241768,15446295196385413576,4293784963647364233],}
github.com/crate-crypto/go-ipa/bandersnatch.PointAffine {
	X: github.com/crate-crypto/go-ipa/bandersnatch/fp.Element [762121701780643127,17298348664687560683,8735489429144563723,3297880053258990719],
	Y: github.com/crate-crypto/go-ipa/bandersnatch/fp.Element [9608063427240116455,14317165834478412410,13135388582222421981,7008628206552145110],}

rust's SRS[6] and SRS[7]

GroupProjective { x: Fp256(BigInteger256([762121577226591572, 7821530775196431310, 5100373047440631974, 5742196019503850925])), y: Fp256(BigInteger256([12310760972179283916, 8841254867580241768, 15446295196385413576, 4293784963647364233])), t: Fp256(BigInteger256([4246214571993526834, 11437250027086784426, 3974671806398050165, 3919474818681934704])), z: Fp256(BigInteger256([8589934590, 6378425256633387010, 11064306276430008309, 1739710354780652911])) } GroupProjective { x: Fp256(BigInteger256([762121701780643127, 17298348664687560683, 8735489429144563723, 3297880053258990719])), y: Fp256(BigInteger256([9608063427240116455, 14317165834478412410, 13135388582222421981, 7008628206552145110])), t: Fp256(BigInteger256([11176709466638207765, 1781433119991953391, 1793489409941133519, 3642735579956807852])), z: Fp256(BigInteger256([8589934590, 6378425256633387010, 11064306276430008309, 1739710354780652911])) }

go's input polynomial at [6] and [7]:

[]github.com/crate-crypto/go-ipa/bandersnatch/fr.Element len: 2, cap: 2, [
	[11009593134782168406,557000322706029613,13918142377749316046,71317661053470578],
	[1379562119333484100,5464475737905671763,15555916484094635670,621577570320654264],
]

rust:

Fp256(BigInteger256([11009593134782168406, 557000322706029613, 13918142377749316046, 71317661053470578]))
Fp256(BigInteger256([1379562119333484100, 5464475737905671763, 15555916484094635670, 621577570320654264]))

outputs

*github.com/crate-crypto/go-ipa/bandersnatch.PointAffine {
	X: github.com/crate-crypto/go-ipa/bandersnatch/fp.Element [16419037542388540368,13320509773298117065,16594419458173865999,6178926961025401340],
	Y: github.com/crate-crypto/go-ipa/bandersnatch/fp.Element [6784422127474512681,9802036867949429154,9305725579232444440,1571803068084914477],}

rust

new c1=GroupProjective { x: Fp256(BigInteger256([3407310714340757448, 6416364531433653599, 8678827809405273451, 7558359338707857182])), y: Fp256(BigInteger256([10585617778697260031, 11424133859830674100, 16518430011129968030, 6348898913274063006])), t: Fp256(BigInteger256([1531489984214844904, 16229847709661939639, 7889043061256795541, 5450545166596115004])), z: Fp256(BigInteger256([6788658732084728407, 18238339674574501826, 9913250985423442012, 7178531433913278380])) }

Broken go-verkle build from bigint allocation optimisation

This PR seems to break go-verkle:

BigInt Allocation opimization (#20)

Define commit interface

"Generated code, do not edit"

I noticed this when opening a PR touching https://github.com/crate-crypto/go-ipa/blob/master/bandersnatch/fr/element.go , github won't show the diff by default because it's marked as such:

https://github.com/crate-crypto/go-ipa/blob/master/bandersnatch/fr/element.go#L15

// Code generated by consensys/gnark-crypto DO NOT EDIT

It seems that some parts are generated and others are not? If so, it would be better to move all non-generated methods out into a separate file, and keep the pure generated code separate in that file. If the header lies, then it should be removed.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.