Skip to content


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
This is a quickly written utility that generates a binary tree containing a summation of the nodes below it and a verifier hash. Copyright (c) 2014 Payward, Inc. (
branch: master

improve tree generation

- enable users to verify that their node is included in the root.
- provide implementation of DB::getDataCode(int datapos)

NB: we removed a paragraph from README. the issue has been corrected/clarified and is no longer a problem (see
latest commit 78d3504a7d
@intelliot intelliot authored
Failed to load latest commit information.
Makefile first commit - add krakendb
README improve tree generation
db.cpp improve tree generation
db.h first commit - add krakendb
krakendb.cpp improve tree generation



This is a quickly written utility that generates a binary tree containing a
summation of the nodes below it and a verifier hash, similar to the one
described by gmaxwell (

Usage: krakendb <dbname> [key=verifier key] [<position>|<hash>|root|dump|gendata]

When run, if the db file <dbname>.tree does not exist, it will attempt to
use <dbname>.data to generate <dbname>.tree.  For testing purposes, the
gendata option can be used to generate a test <dbname>.data file.

Generation of the tree requires a verifier key, set with the key=verifier-key
option.  The nodes of the tree are hashed using:

Leaf nodes:

hash = SHA256(SHA256(code || ":" || value))

, where code is a random salt code for the account to make brute forcing of
value more difficult and value is the value of the account.  code and value
are known to the account holder but not to anyone else so that thee user can
verify that their node hash is indeed what is claimed.

Interior nodes:

hash = SHA256(left.hash || right.hash)

After the tree has been generated, the key option is no longer necessary and
options to dump the entire tree, query for the root node, or query for all
the nodes and adjacent nodes between the leaf node and the root node are
available.  Note that when querying by leaf node hash value, the hashes are
not guaranteed to be unique and only the first entry is returned.

In order to protect privacy (both the business and its users), a third party
is necessary to ensure that the tree is correctly being generated with the
proper math at every node, and that there aren't any negative values at the
leaf nodes designed to deflate the value of the root.  Note that there may
sometimes be negative values for some accounts for various reasons, but
there should not be a lot of negative amounts and any that have a large
negative amount require further investigation as to the reason for it.
Something went wrong with that request. Please try again.