11664955435

Committed 04 Nov 2024 01:13PM UTC coverage: 62.295% (+0.09%) from 62.209%

Build # 11664955435

Build Type

Pull #1398

github

Committed by

altergui

Commit Message

arbo: add CalculateProofNodes and CheckProofBatch

Pull Request Pull Request #1398: arbo: add CalculateProofNodes

Run Details

56 of 67 new or added lines in 2 files covered. (83.58%)

23 existing lines in 2 files now uncovered.

16892 of 27116 relevant lines covered (62.3%)

38024.67 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.9

/tree/arbo/circomproofs.go

package arbo

import (
        "bytes"
        "encoding/json"
        "fmt"
        "slices"
)

// CircomVerifierProof contains the needed data to check a Circom Verifier Proof
// inside a circom circuit.  CircomVerifierProof allow to verify through a
// zkSNARK proof the inclusion/exclusion of a leaf in a tree.
type CircomVerifierProof struct {
        Root     []byte   `json:"root"`
        Siblings [][]byte `json:"siblings"`
        OldKey   []byte   `json:"oldKey"`
        OldValue []byte   `json:"oldValue"`
        IsOld0   bool     `json:"isOld0"`
        Key      []byte   `json:"key"`
        Value    []byte   `json:"value"`
        Fnc      int      `json:"fnc"` // 0: inclusion, 1: non inclusion
}

// MarshalJSON implements the JSON marshaler
func (cvp CircomVerifierProof) MarshalJSON() ([]byte, error) {
        m := make(map[string]any)

        m["root"] = BytesLEToBigInt(cvp.Root).String()
        m["siblings"] = siblingsToStringArray(cvp.Siblings)
        m["oldKey"] = BytesLEToBigInt(cvp.OldKey).String()
        m["oldValue"] = BytesLEToBigInt(cvp.OldValue).String()
        if cvp.IsOld0 {
                m["isOld0"] = "1"
        } else {
                m["isOld0"] = "0"
        }
        m["key"] = BytesLEToBigInt(cvp.Key).String()
        m["value"] = BytesLEToBigInt(cvp.Value).String()
        m["fnc"] = cvp.Fnc

        return json.Marshal(m)
}

func siblingsToStringArray(s [][]byte) []string {
        var r []string
        for i := 0; i < len(s); i++ {
                r = append(r, BytesLEToBigInt(s[i]).String())
        }
        return r
}

// FillMissingEmptySiblings adds the empty values to the array of siblings for
// the Tree number of max levels
func (t *Tree) FillMissingEmptySiblings(s [][]byte) [][]byte {
        for i := len(s); i < t.maxLevels; i++ {
                s = append(s, emptyValue)
        }
        return s
}

// GenerateCircomVerifierProof generates a CircomVerifierProof for a given key
// in the Tree
func (t *Tree) GenerateCircomVerifierProof(k []byte) (*CircomVerifierProof, error) {
        kAux, v, siblings, existence, err := t.GenProof(k)
        if err != nil && err != ErrKeyNotFound {
                return nil, err
        }
        var cp CircomVerifierProof
        cp.Root, err = t.Root()
        if err != nil {
                return nil, err
        }
        s, err := UnpackSiblings(t.hashFunction, siblings)
        if err != nil {
                return nil, err
        }
        cp.Siblings = t.FillMissingEmptySiblings(s)
        if !existence {
                cp.OldKey = kAux
                cp.OldValue = v
        } else {
                cp.OldKey = emptyValue
                cp.OldValue = emptyValue
        }
        cp.Key = k
        cp.Value = v
        if existence {
                cp.Fnc = 0 // inclusion
        } else {
                cp.Fnc = 1 // non inclusion
        }

        return &cp, nil
}

// CalculateProofNodes calculates the chain of hashes in the path of the proof.
// In the returned list, first item is the root, and last item is the hash of the leaf.
func (cvp CircomVerifierProof) CalculateProofNodes(hashFunc HashFunction) ([][]byte, error) {
        paddedSiblings := slices.Clone(cvp.Siblings)
        for k, v := range paddedSiblings {
                if bytes.Equal(v, []byte{0}) {
                        paddedSiblings[k] = make([]byte, hashFunc.Len())
                }
        }
        packedSiblings, err := PackSiblings(hashFunc, paddedSiblings)
        if err != nil {
                return nil, err
        }
        return CalculateProofNodes(hashFunc, cvp.Key, cvp.Value, packedSiblings)
}

// CheckProof verifies the given proof. The proof verification depends on the
// HashFunction passed as parameter.
func (cvp CircomVerifierProof) CheckProof(hashFunc HashFunction) (bool, error) {
        hashes, err := cvp.CalculateProofNodes(hashFunc)
        if err != nil {
                return false, err
        }
        if !bytes.Equal(hashes[0], cvp.Root) {
                return false, fmt.Errorf("calculated root doesn't match expected root")
        }
        return true, nil
}

1	package arbo
2
3	import (
4	"bytes"
5	"encoding/json"
6	"fmt"
7	"slices"
8	)
9
10	// CircomVerifierProof contains the needed data to check a Circom Verifier Proof
11	// inside a circom circuit. CircomVerifierProof allow to verify through a
12	// zkSNARK proof the inclusion/exclusion of a leaf in a tree.
13	type CircomVerifierProof struct {
14	Root []byte `json:"root"`
15	Siblings [][]byte `json:"siblings"`
16	OldKey []byte `json:"oldKey"`
17	OldValue []byte `json:"oldValue"`
18	IsOld0 bool `json:"isOld0"`
19	Key []byte `json:"key"`
20	Value []byte `json:"value"`
21	Fnc int `json:"fnc"` // 0: inclusion, 1: non inclusion
22	}
23
24	// MarshalJSON implements the JSON marshaler
25	func (cvp CircomVerifierProof) MarshalJSON() ([]byte, error) {	4✔
26	m := make(map[string]any)	4✔
27		4✔
28	m["root"] = BytesLEToBigInt(cvp.Root).String()	4✔
29	m["siblings"] = siblingsToStringArray(cvp.Siblings)	4✔
30	m["oldKey"] = BytesLEToBigInt(cvp.OldKey).String()	4✔
31	m["oldValue"] = BytesLEToBigInt(cvp.OldValue).String()	4✔
32	if cvp.IsOld0 {	4✔
33	m["isOld0"] = "1"	×
34	} else {	4✔
35	m["isOld0"] = "0"	4✔
36	}	4✔
37	m["key"] = BytesLEToBigInt(cvp.Key).String()	4✔
38	m["value"] = BytesLEToBigInt(cvp.Value).String()	4✔
39	m["fnc"] = cvp.Fnc	4✔
40		4✔
41	return json.Marshal(m)	4✔
42	}
43
44	func siblingsToStringArray(s [][]byte) []string {	4✔
45	var r []string	4✔
46	for i := 0; i < len(s); i++ {	20✔
47	r = append(r, BytesLEToBigInt(s[i]).String())	16✔
48	}	16✔
49	return r	4✔
50	}
51
52	// FillMissingEmptySiblings adds the empty values to the array of siblings for
53	// the Tree number of max levels
54	func (t *Tree) FillMissingEmptySiblings(s [][]byte) [][]byte {	10✔
55	for i := len(s); i < t.maxLevels; i++ {	56✔
56	s = append(s, emptyValue)	46✔
57	}	46✔
58	return s	10✔
59	}
60
61	// GenerateCircomVerifierProof generates a CircomVerifierProof for a given key
62	// in the Tree
63	func (t Tree) GenerateCircomVerifierProof(k []byte) (CircomVerifierProof, error) {	10✔
64	kAux, v, siblings, existence, err := t.GenProof(k)	10✔
65	if err != nil && err != ErrKeyNotFound {	10✔
66	return nil, err	×
67	}	×
68	var cp CircomVerifierProof	10✔
69	cp.Root, err = t.Root()	10✔
70	if err != nil {	10✔
71	return nil, err	×
72	}	×
73	s, err := UnpackSiblings(t.hashFunction, siblings)	10✔
74	if err != nil {	10✔
75	return nil, err	×
76	}	×
77	cp.Siblings = t.FillMissingEmptySiblings(s)	10✔
78	if !existence {	12✔
79	cp.OldKey = kAux	2✔
80	cp.OldValue = v	2✔
81	} else {	10✔
82	cp.OldKey = emptyValue	8✔
83	cp.OldValue = emptyValue	8✔
84	}	8✔
85	cp.Key = k	10✔
86	cp.Value = v	10✔
87	if existence {	18✔
88	cp.Fnc = 0 // inclusion	8✔
89	} else {	10✔
90	cp.Fnc = 1 // non inclusion	2✔
91	}	2✔
92
93	return &cp, nil	10✔
94	}
95
96	// CalculateProofNodes calculates the chain of hashes in the path of the proof.
97	// In the returned list, first item is the root, and last item is the hash of the leaf.
98	func (cvp CircomVerifierProof) CalculateProofNodes(hashFunc HashFunction) ([][]byte, error) {	18✔
99	paddedSiblings := slices.Clone(cvp.Siblings)	18✔
100	for k, v := range paddedSiblings {	162✔
101	if bytes.Equal(v, []byte{0}) {	256✔
102	paddedSiblings[k] = make([]byte, hashFunc.Len())	112✔
103	}	112✔
104	}
105	packedSiblings, err := PackSiblings(hashFunc, paddedSiblings)	18✔
106	if err != nil {	18✔
NEW 107	return nil, err	×
NEW 108	}	×
109	return CalculateProofNodes(hashFunc, cvp.Key, cvp.Value, packedSiblings)	18✔
110	}
111
112	// CheckProof verifies the given proof. The proof verification depends on the
113	// HashFunction passed as parameter.
114	func (cvp CircomVerifierProof) CheckProof(hashFunc HashFunction) (bool, error) {	10✔
115	hashes, err := cvp.CalculateProofNodes(hashFunc)	10✔
116	if err != nil {	10✔
NEW 117	return false, err	×
NEW 118	}	×
119	if !bytes.Equal(hashes[0], cvp.Root) {	12✔
120	return false, fmt.Errorf("calculated root doesn't match expected root")	2✔
121	}	2✔
122	return true, nil	8✔
123	}

vocdoni / vocdoni-node / 11664955435

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous