proofs

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. Fixed length tree does not support sorting by hash option.

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"

// 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)

// Fixed Size Tree
doctree, err = NewDocumentTree(TreeOptions{Hash: sha256.New(), LeafHash: md5.New(), TreeDepth: 32})
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 fixed size 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: