Multisig, Hashes, and the Math Behind Trustless Record Keeping

Table of Links

Abstract and 1. Introduction

1. System model

2. Initial node state

3. Append process

   4.1 Local append

   4.2 Append from another node

   4.3 Record validation

   4.4 State consistency

4. Replication process

5. Proof of correctness

6. M-of-N connections

7. Extensions and optimizations

References

4. Append process

4.1 Local append

The append process looks like that:

\

1. Each new record should have key, value and version fields

   \

2. On append, the algorithm should create hash of record: ℎ𝑎𝑠ℎ = 𝑠ℎ𝑎256(𝑘𝑒𝑦, 𝑣𝑎𝑙𝑢𝑒, 𝑣𝑒𝑟𝑠𝑖𝑜𝑛). This hash brings uniqueness to the record

   \

3. Then algorithm should create partial signature as follow: partialSignature = (privateKey ∗ hash)𝑚𝑜𝑑 𝑁, where 𝑁 is curve parameter.

   \

4. Then algorithm add timestamp and timestamp index to the record. The timestamp – is a timestamp when record is created. The timestamp index is used when concurrency is possible, and two or more records can be created at the same time. In case this happens, all records with the same time have their own index (like 0, 1, 2).

   \

5. Then this record, alongside with hash and signature can be stored locally (for instance in database)

   \

6. This record is called intermediate

\

\

4.2 Append from another node

When one node receives new records from another (for instance node A obtained records from node B) during replication process, the append rules vary:

\

1. The algorithm should validate the record

   \

2. Then algorithm should check, do this node already has this record (it can be done by finding the record by hash).

   \ 2.1)If record exist then:

   \ 2.1.1) In case received record is multisig and local record is intermediate – then algorithm should replace local intermediate record with received multisig and update the root.

   \ 2.1.2) In case local and received records are multisig, then the highest multisig is chosen (the algorithm compares 2 signatures by value) and stored in local record.

   \ 2.1.3) In case local record is multisig and received one is intermediate – then algorithm ignore this record (i.e. doesn’t apply) 2.1.4) In case local and received records are intermediate – then algorithm just take signatures from received record (which are not present on local record) and append them to local record.

   \ 2.2)if record doesn’t exist:

   \ 2.2.1) then algorithm should sign the hash of the received record (like was in local append described above), add it to this record and store

   \

3. Then the algorithm should check if there are enough signatures for multisig (this number is defined by quorum size).

   \ 3.1) if yes then:

   \ 3.1.1) algorithm build multisig: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖𝑚𝑜𝑑 𝑁

   \ 3.1.2) algorithm build shared public key: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ

   \ 3.1.3) algorithm replace intermediate signatures with multisig and sharedPublicKey

   \ 3.1.4) algorithm save the record and update the root.

\ \

\

4.3 Record validation

The validation process works as follows:

\

1. First signatures are validated: in case of intermediate signatures

\ 1.1) If signatures are intermediate, then for each intermediate signature the algorithm validate that: 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ = 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺, where G – is a curve parameter (SECP256K1)

\ 1.2)If signature is multisig, then

\ 1.2.1) sharedPublicKey is reconstructed from involved public keys in signature process (the public keys with signatures are stored in record) and compared against received sharedPublicKey. If it’s not equal – then validation is not passed

\ 1.2.2) then multisignature is validated as: 𝑚𝑢𝑙𝑡𝑖𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦

\

4.4 State consistency

To make sure, that all nodes have the same sets of records, the root has been introduced. The root is represented as sum of hashes of confirmed records (records with multisig): 𝑟𝑜𝑜𝑡 = ∑ ℎ𝑎𝑠ℎ 𝑖 𝑚𝑜𝑑 𝑛, where 𝑛 is a curve parameter. The following formula allows to build the root without order, so technically the append order of hashes doesn’t make any sense in this case. Also, keep in mind, as algorithm has eventual consistency (without rollback option) – we can’t guarantee any ordering.

\ Also, to make root update quick, the algorithm stores the root on record level:

\

1. On multisig record insert, the algorithm updates the root by addition of previous root to record’s hash: 𝑟𝑜𝑜𝑡 = (𝑟𝑜𝑜𝑡𝑝𝑟𝑒𝑣 + ℎ𝑎𝑠ℎ) 𝑚𝑜𝑑 𝑛

   \

2. Then this root hash is appended to the record (I call it stateHash)

   \

3. During next append of another new record, there is no need to recalculate the hash root of all records, but we sort confirmed (multisig) records in DESC order by timestamp and timestamp index, and take stateHash from the first record (which is the most recent one)

\ This approach is also useful for traceability and validation purpose, as all state can be replayed up to any point of history and calculated hash root can be compared with stateHash.

\

:::info Author:

(1) Egor Zuev (zyev.egor@gmail.com)

:::

:::info This paper is available on arxiv under CC0 1.0 UNIVERSAL license.

:::

\