proofs

package
v0.0.0-...-d4e9fa9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 23, 2019 License: MIT Imports: 20 Imported by: 0

Documentation

Overview

Package proofs lets you construct merkle trees out of protobuf messages and create proofs for fields of an object by just specifying the dot notation of a field.

Field names are not taken from the struct attributes but the protobuf field names. Protobuf field names stay the same across different programming languages (the struct field names are camel cased to follow Go's style guide which they would not be in a javascript implementation.

Supported types: * string * int64 * timestamp.Timestamp

Available Protobuf Options

Fields can be excluded from the flattener by setting the custom protobuf option `proofs.exclude_from_tree` found in `proofs/proto/proof.proto`.

Fields can be treated as raw (already hashed values) by setting the option `proofs.hashed_field`.

Field salts are optional. This will make the proofs simpler to validate. Only recommended on fields that have higher variadic nature, like hashes. 

message Document {
	string value_a = 1;
	string value_b = 2 [
		(proofs.exclude_from_tree) = true
	];
	bytes value_c = 3 [
		(proofs.hashed_field) = true
	];
	bytes value_d = 4 [
		(proofs.no_salt) = true
	];
}

Nested, Repeated and Mapped Structures

Nested, repeated, and map fields will be flattened following a dotted notation. Given the following example: 

message NestedDocument {
  string fieldA = 1;
  repeated Document fieldB = 2;
  repeated string fieldC = 3;
  map<string, Document> fieldD = 4 [
      (proofs.field_length) = 4
  ];
  map<uint64, string> fieldE = 5;
}

message Document {
  string fieldA = 1;
}

NestedDocument{
	fieldA: "foobar",
	fieldB: []Document{Document{fieldA: "1"}, Document{fieldA: "2"}},
	fieldC: []string{"a", "b", "c"},
	fieldD: map[string]Document{
	    "a": Document{fieldA: "1"},
	    "b": Document{fieldA: "2"},
	    "c": Document{fieldA: "3"},
	},
	fieldE: map[uint64]string{
	    0: "zero",
	    1: "one",
	    2: "two",
	},
}

A tree will be created out of this document by flattening all the fields values as leaves. This would result in a tree with the following leaves:

  • "fieldA" aka [1]
  • "fieldB.length" aka [2]
  • "fieldB[0]" aka [2, 0]
  • "fieldB[1]" aka [2, 1]
  • "fieldC.length" aka [3]
  • "fieldC[0]" aka [3, 0]
  • "fieldC[1]" aka [3, 1]
  • "fieldC[2]" aka [3, 2]
  • "fieldD.length" aka [4]
  • "fieldD[a]" aka [4, 97]
  • "fieldD[b]" aka [4, 98]
  • "fieldD[c]" aka [4, 99]
  • "fieldE.length" aka [5]
  • "fieldE[0]" aka [5, 0]
  • "fieldE[1]" aka [5, 1]
  • "fieldE[2]" aka [5, 2]

Proof format

This library defines a proof format that ensures both human readable, concise and secure Merkle proofs: 

{
   "readableName":"ValueA",
   "value":"Example",
   "salt":"1VWQFUGCXl1AYS0iAULHQow4XEjgJF/TpAuOO2Rnm+E=",
   "hashes":[
       { "right":"kYXAGhDdPiFMq1ZQMOZiKmSf1S1eHNgJ6BIPSIExOj8=" },
       { "left":"GDgT7Km6NK6k4N/Id4CZXErL3p6clNX7sVnlNyegdG0=" },
       { "right":"qOZzS+YM8t1OfC87zEKgkKz6q0f3wwk5+ed+PR/2cDA=" }
   ]
}

This library can also create proofs with more compact property fields: 

{
   "compactName":[0,0,0,1],
   "value":"Example",
   "salt":"1VWQFUGCXl1AYS0iAULHQow4XEjgJF/TpAuOO2Rnm+E=",
   "hashes":[
       { "right":"kYXAGhDdPiFMq1ZQMOZiKmSf1S1eHNgJ6BIPSIExOj8=" },
       { "left":"GDgT7Km6NK6k4N/Id4CZXErL3p6clNX7sVnlNyegdG0=" },
       { "right":"qOZzS+YM8t1OfC87zEKgkKz6q0f3wwk5+ed+PR/2cDA=" }
   ]
}

Sorted Hashes

This implementation allows for more concise representation of proofs, saving some space that is valuable for on-chain verifications. The hash function to hash two leaves is modified in this case in the following way: 

  HashTwoNodes(A, B):
    if A > B:
	   return Hash(B, A)
	else:
	    return Hash(A, B)

This makes it unncessary to give a left/right designation in the proof. The drawback of using this way of hashing a tree is that you can't make statements about the position of a leaf in the tree.

The respective JSON for the proof would be: 

{
  "property":"ValueA",
  "value":"Example",
  "salt":"1VWQFUGCXl1AYS0iAULHQow4XEjgJF/TpAuOO2Rnm+E=",
  "sortedHashes":[
      "kYXAGhDdPiFMq1ZQMOZiKmSf1S1eHNgJ6BIPSIExOj8=",
      "GDgT7Km6NK6k4N/Id4CZXErL3p6clNX7sVnlNyegdG0=",
      "qOZzS+YM8t1OfC87zEKgkKz6q0f3wwk5+ed+PR/2cDA="
  ]
}

There are a few things to note:

  • When calculating the hash of the leaf, the dot notation of the property, the value and salt should be concatenated to produce the hash.
  • The default proof expects values of documents to be salted to prevent rainbow table lookups.
  • The value is included in the file as a string value not a native type.

Salt Message

salts field contained in a message is used to feed salts (for other fields) to Precise-Proofs library by client

Field for slice/map length

We encode the length of a slice or map field in the tree as an additional leaf so a proof can be created about the size of a field. Default is "_length". The new added length field can be customized with the ReadablePropertyLengthSuffix option. 

message Document {
  repeated string fieldA = 1;
  map<string,string> fieldB = 2;
}

Custom Document Prefix

Library supports adding a prefix to the document path by setting up `TreeOption.ParentPrefix` to the desired value.

Field Padding Support

Library supports padding bytes and string field, one usage of `proto.field_length` is used to define fixed length of a bytes or string field, if the length of field contained in message is less than fixed length, this field will be padded with `0x0`s, if length of field contained in message is bigger than fixed length, an error is returned. `TreeOption.FixedLengthFieldLeftPadding` is used to control padding direction, `true` means padding in the left, default `false` means padding in the right.

Fixed Length Tree

`TreeOption.TreeDepth` is used to define an optional fixed length tree. If this option is provided, the tree will be extended to have the depth specified in the option, so a fixed number of `(2**TreeDepth)` leaves. Empty leaves with hash `hash([]byte{})` will be added to the tree if client does not provide enough leaf nodes. If the provided leaf nodes surpass `(2**TreeDepth)`, an error will be returned.

Use Customized Leaf Hash Function

`TreeOption.LeafHash` is used to define hash funtion used by leaf node, when do hashing on leaf node of document tree this hash funtion will be used instead of `TreeOption.Hash`. If this option is not provided, then `TreeOption.Hash` will be used when do leaf node hashing operation.

Append Fields

Simple Structure: Append Field property when enabled on a protobuf message will flatten the message fields into a single leaf. Leaves are appended in sorted order of the field names. 

	message Name {
		string first = 1;
    	string last = 2;
	}

	message Document {
		Name name = 1 [ (proofs.append_fields) = true; ];
	}

Result:

  • document.name = first+last

Example: 

{
	"name": {
		"first": "john",
		"last": "doe"
	}
}

Result:

  • document.name = "johndoe"

Repeated field: Append field property when enabled on repeated protobuf message will flatten structure as follows. 

message Document {
	repeated Name names = 1 [ (proofs.append_fields) = true; ];
}

Result:

  • document.names[0] = name[0].first + name[0].last
  • document.names[1] = name[1].first + name[1].last

Example: 

{
	names: [
		{
			"first": "john",
			"last": "doe"
		},

		{
			"first": "bob",
			"last": "barker"
		}
	]
}

Result:

  • document.names[0] = "johndoe"
  • document.names[1] = "bobbarker"

Mapped Field and Repeated field with `mapping_key` enabled: Append field property when enabled on Map or repeated field with `mapping_key` enabled will flatten structure as follows. 

	message PhoneNumber {
    	string type = 1;
    	string country_code = 2;
    	string number = 3;
	}

	message Document {
		repeated phone_numbers PhoneNumber = 3 [
      		(proofs.mapping_key) = "type";
      		(proofs.append_fields) = true;
  		];
	}

Result:

  • document.phone_numbers[phone_numbers[0].type] = phone_number[0].country_code + phone_numbers[0].number
  • document.phone_numbers[phone_numbers[1].type] = phone_number[1].country_code + phone_numbers[1].number

Example: 

{
	"phone_numbers": [
		{
			"type": "home",
			"country_code": "+1",
			"number": "123 4567 89"
		}
	]
}

Result:

  • document.phone_numbers["home"] = "+1123 4567 89"
Example (Complete) 
// ExampleDocument is a protobuf message
document := documentspb.ExampleDocument{
	Value1:      1,
	ValueA:      "Foo",
	ValueB:      "Bar",
	ValueBytes1: []byte("foobar"),
	Name: &documentspb.Name{
		First: "Foo",
		Last:  "Bar",
	},
}

doctree, err := NewDocumentTree(TreeOptions{Hash: sha256.New(), LeafHash: md5.New()})
if err != nil {
	panic(err)
}

err = doctree.AddLeavesFromDocument(&document)
if err != nil {
	panic(err)
}

err = doctree.Generate()
if err != nil {
	panic(err)
}

fmt.Printf("Generated tree: %s\n", doctree.String())

// Generate the actual proof for a field. In this case the field called "valueA".
proof, _ := doctree.CreateProof("valueA")
proofJson, _ := json.Marshal(proof)
fmt.Println("Proof:\n", string(proofJson))

// Validate the proof that was just generated
valid, _ := doctree.ValidateProof(&proof)

fmt.Printf("Proof validated: %v\n", valid)

Output:

Index

Examples

Constants

View Source 
const DefaultReadablePropertyLengthSuffix = "length"

DefaultReadablePropertyLengthSuffix is the suffix used to store the length of slices (repeated) fields in the tree. It can be customized with the ReadablePropertyLengthSuffix TreeOption

View Source 
const ElemFormat = "%s[%s]"

ElemFormat represents how the property name of a slice or map element is derived from its parent

View Source 
const SaltsFieldName = "Salts"
View Source 
const SubFieldFormat = "%s.%s"

SubFieldFormat represents how the property name of a struct field is derived from its parent

Variables

View Source 
var Empty = Property{}

Functions

func AsBytes 

func AsBytes(propName proofspb.PropertyName) []byte

AsBytes encodes a PropertyName for hashing

Human-readable property names are encoded using UTF-8 Compact property names are encoded by using big-endian encoding on the individual components

func CalculateHashForProofField 

func CalculateHashForProofField(proof *proofspb.Proof, hashFunc hash.Hash) (hash []byte, err error)

CalculateHashForProofField takes a Proof struct and returns a hash of the concatenated property name, value & salt. Uses ConcatValues internally.

func CompactName 

func CompactName(prop ...byte) *proofspb.Proof_CompactName

CompactName creates a PropertyName from a byte slice

func ConcatValues 

func ConcatValues(propName proofspb.PropertyName, value []byte, salt []byte) (payload []byte, err error)

ConcatValues concatenates property, value & salt into one byte slice.

func HashTwoValues 

func HashTwoValues(a []byte, b []byte, hashFunc hash.Hash) (hash []byte)

HashTwoValues concatenate two hashes to calculate hash out of the result. This is used in the merkleTree calculation code as well as the validation code.

func ReadableName 

func ReadableName(prop string) *proofspb.Proof_ReadableName

ReadableName creates a PropertyName from a human-readable name

func ValidateProofHashes 

func ValidateProofHashes(hash []byte, hashes []*proofspb.MerkleHash, rootHash []byte, hashFunc hash.Hash) (valid bool, err error)

ValidateProofHashes calculates the merkle root based on a list of left/right hashes.

func ValidateProofSortedHashes 

func ValidateProofSortedHashes(hash []byte, hashes [][]byte, rootHash []byte, hashFunc hash.Hash) (valid bool, err error)

ValidateProofHashes calculates the merkle root based on a list of left/right hashes.

Types

type DocumentTree 

type DocumentTree struct {
	// contains filtered or unexported fields
}

DocumentTree is a helper object to create a merkleTree and proofs for fields in the document

func NewDocumentTree 

func NewDocumentTree(proofOpts TreeOptions) (DocumentTree, error)

NewDocumentTree returns an empty DocumentTree

func NewDocumentTreeWithRootHash 

func NewDocumentTreeWithRootHash(proofOpts TreeOptions, rootHash []byte) (DocumentTree, error)

NewDocumentTree returns a DocumentTree that has a root hash set. It can be used to validate proofs but not for creating any.

func (*DocumentTree) AddLeaf 

func (doctree *DocumentTree) AddLeaf(leaf LeafNode) error

AddLeaf appends a single leaf to the tree This function can be called multiple times and leaves will be added from left to right. Note that the lexicographic sorting doesn't get applied in this method but in the protobuf flattening. The order in which leaves are added in in this method determine layout of the tree.

func (*DocumentTree) AddLeaves 

func (doctree *DocumentTree) AddLeaves(leaves []LeafNode) error

AddLeaves appends list of leaves to the tree's leaves. This function can be called multiple times and leaves will be added from left to right. Note that the lexicographic sorting doesn't get applied in this method but in the protobuf flattening. The order in which leaves are added in in this method determine layout of the tree.

func (*DocumentTree) AddLeavesFromDocument 

func (doctree *DocumentTree) AddLeavesFromDocument(document proto.Message) (err error)

AddLeavesFromDocument iterates over a protobuf message, flattens it and adds all leaves to the tree

func (*DocumentTree) CreateProof 

func (doctree *DocumentTree) CreateProof(prop string) (proof proofspb.Proof, err error)

CreateProof takes a property in dot notation and returns a Proof object for the given field

func (*DocumentTree) CreateProofWithCompactProp 

func (doctree *DocumentTree) CreateProofWithCompactProp(prop []byte) (proof proofspb.Proof, err error)

CreateProofWithCompactProp takes a property in compact form and returns a Proof object for the given field

func (*DocumentTree) Generate 

func (doctree *DocumentTree) Generate() error

Generate calculated the merkle root with all supplied leaves. This method can only be called once and makes the tree immutable.

func (*DocumentTree) GetCompactPropByPropertyName 

func (doctree *DocumentTree) GetCompactPropByPropertyName(prop string) []byte

GetCompactPropByPropertyName returns a leaf compact name if it is found

func (*DocumentTree) GetLeafByCompactProperty 

func (doctree *DocumentTree) GetLeafByCompactProperty(prop []byte) (int, *LeafNode)

GetLeafByCompactProperty returns a leaf if it is found

func (*DocumentTree) GetLeafByProperty 

func (doctree *DocumentTree) GetLeafByProperty(prop string) (int, *LeafNode)

GetLeafByProperty returns a leaf if it is found

func (*DocumentTree) GetLeaves 

func (doctree *DocumentTree) GetLeaves() LeafList

GetLeaves returns the leaves of the doc tree.

func (*DocumentTree) IsEmpty 

func (doctree *DocumentTree) IsEmpty() bool

IsEmpty returns false if the tree contains no leaves

func (*DocumentTree) PropertyOrder 

func (doctree *DocumentTree) PropertyOrder() []Property

PropertyOrder returns an with all properties of a doctree in order

func (*DocumentTree) RootHash 

func (doctree *DocumentTree) RootHash() []byte

func (*DocumentTree) String 

func (doctree *DocumentTree) String() string

func (*DocumentTree) ValidateProof 

func (doctree *DocumentTree) ValidateProof(proof *proofspb.Proof) (valid bool, err error)

ValidateProof by comparing it to the tree's rootHash

type FieldNum 

type FieldNum uint32

FieldNum is a compact, unique identifier for a Property, relative to its parent

func ExtractFieldTags 

func ExtractFieldTags(protobufTag string) (string, FieldNum, error)

ExtractFieldTags takes the protobuf tag string of a struct field and returns the field name and number

type FieldNumForSliceLength 

type FieldNumForSliceLength uint64

type HashNode 

type HashNode struct {
	Left bool
	Leaf uint64
}

func CalculateProofNodeList 

func CalculateProofNodeList(node, leafCount uint64) (nodes []*HashNode, err error)

CalculateProofNodeList returns a list of slice positions to fetch the nodes required for creating a proof from Tree.Nodes.

type LeafList 

type LeafList []LeafNode

LeafList is a list implementation that can be sorted by the LeafNode.Property value. This is needed for ordering all leaves before generating a merkleTree out of it.

func (LeafList) Len 

func (s LeafList) Len() int

Len returns the length of the list

func (LeafList) Swap 

func (s LeafList) Swap(i, j int)

Swap two items in the list

type LeafNode 

type LeafNode struct {
	Property Property
	Value    []byte
	Salt     []byte
	// Hash contains either the hash that is calculated from Value, Salt & Property or a user defined hash
	Hash []byte
	// If set to true, the the value added to the tree is LeafNode.Hash instead of the hash calculated from Value, Salt
	// & Property
	Hashed bool
}

LeafNode represents a field that can be hashed to create a merkle tree

func FlattenMessage 

func FlattenMessage(message proto.Message, salts Salts, readablePropertyLengthSuffix string, hashFn hash.Hash, compact bool, parentProp Property, fixedLengthFieldLeftPadding bool) (leaves []LeafNode, err error)

FlattenMessage takes a protobuf message struct and flattens it into an array of nodes.

The fields are sorted lexicographically by their protobuf field names.

func (*LeafNode) HashNode 

func (n *LeafNode) HashNode(h hash.Hash, compact bool) error

HashNode calculates the hash of a node provided it isn't already calculated.

type Property 

type Property struct {
	Parent     *Property
	Text       string
	Compact    []byte
	NameFormat string
}

Property uniquely identifies a LeafNode

func NewProperty 

func NewProperty(name string, bytes ...byte) Property

NewProperty return a new root property

func (Property) CompactName 

func (n Property) CompactName() (pn []byte)

CompactName returns the compact name of a property, derived from protobuf tags

func (Property) FieldProp 

func (n Property) FieldProp(name string, num FieldNum) (field Property)

FieldProp returns a child Property representing a field of a struct

func (Property) FieldPropFromTag 

func (n Property) FieldPropFromTag(protobufTag string) (Property, error)

FieldPropFromTag takes the protobuf tag string of a struct field and returns a child Property representing that field of the struct

func (Property) LengthProp 

func (n Property) LengthProp(readablePropertyLengthSuffix string) Property

LengthProp returns a child Property representing the length of a repeated field

func (Property) MapElemProp 

func (n Property) MapElemProp(k interface{}, keyLength uint64) (Property, error)

MapElemProp takes a map key and returns a child Property representing the value at that key in the map

func (Property) Name 

func (n Property) Name(compact bool) proofspb.PropertyName

Name returns either the compact or human-reable name of a Property

func (Property) ReadableName 

func (n Property) ReadableName() string

ReadableName returns the human-readable name of a property

func (Property) SliceElemProp 

func (n Property) SliceElemProp(i FieldNumForSliceLength) Property

SliceElemProp takes a repeated field index and returns a child Property representing that element of the repeated field

type Salts 

type Salts func(compact []byte) ([]byte, error)

type TreeOptions 

type TreeOptions struct {
	//	EnableHashSorting: Implement a merkle tree with sorted hashes
	EnableHashSorting bool
	Salts             Salts
	// ReadablePropertyLengthSuffix: As precise proofs support repeated fields, when generating the merkle tree we need to add a
	// leaf that represents the length of the slice. The default suffix is `_length`, although it is customizable so it
	// does not collide with potential field names of your own proto structs.
	ReadablePropertyLengthSuffix string
	Hash                         hash.Hash
	LeafHash                     hash.Hash
	// ParentPrefix defines an arbitrary prefix to prepend to the parent, so all fields are prepended with it
	ParentPrefix                Property
	CompactProperties           bool
	FixedLengthFieldLeftPadding bool
	TreeDepth                   uint
}

TreeOptions allows customizing the generation of the tree

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.