error in polynomial calculation

[gballet]

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

go

*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])) }

[kevaundray]

Can you specify the commit hash that you used for go-ipa and also for rust-verkle?

Note: Go outputs points using affine representation while rust outputs points using extended projective representation, so its not immediately clear to me that the outputs are different by solely looking at them in the format above.

[gballet]

rust-verkle commit hash: 11149e0a2a457d7c2b57ec0c4c01678d287f42ce (just before banderwagon)

go-ipa commit hash: 816621cb2ec4

[gballet]

The discrepancy is due to go-verkle returning a serialized commitment whereas rust-verkle returns group_to_field(commitment). The two implementations agree when the serialized commitment doesn't overflow the modulus. Closing this issue.