Normally with hashing methods, we need to take all the previous data and new data in order to create a new hash value for our data. In a homomorphic hashing method, we can basically take the previous hash, and then add on any new data values. We can also remove previous data values from our hash, too. This is more efficient in computing, as we do not have to process all of our data into a new hash, and can use simple homomorphic operations for the computation. The method we will use (LtHash) was initially defined by Bellare and Micciancio [1] and updated Lewi et al at Facebook [2].
Homomorphic Hashing with Golang |
Method
We waste so much computing power, and every bit of extra computing costs us a little more energy. So, a good of work is going into making sure we have trusted systems, but also in reducing our computational overhead. Can you thus have trust with efficiency? Well, we are currently seeing the rise of homomorphic encryption, and where we can mathematically process encrypted values. But, how can we create a new hash value, without knowing the previous values added to the hash? Well, we can do this with a homomorphic hash. So, let's look at one of the implementations of this: LtHash and initially defined by Bellare and Micciancio [1].
At the time, the homomorphic encryption method was defined as an incremental technique. The method has since been updated by Lewi et al at Facebook [2]. This paper focuses on a method by which an owner of a database — a distributor — is responsible for propagating updates to subscribers. With this, the distributor is then responsible for updating the subscribers with a signed hash. Overall, it may be possible to recompute the over hash to the data, but it would be more efficient to update the hash based on new data added. The distributer can then just take the previous hash, and then added the new data, and produce the new hash.
With homomorphic hashing, Bob (the distributor) needs to sign for updates to Grace (a subscriber). In a normally hashing method, Bob would take all the previous data and the new data, and compute a new hash (Figure 1). If we have large amounts of data, this may be a computationally intensive task. To overcome this we can use a homomorphic hashing method, where we take a previous hash and then compute the new hash using this and any new data:
Figure 1: Traditional hashing and homomorphic hashing
In Golang, we initialize a 2,048-byte hash. In this case, we will use Blake2b, and where XOF is an extendable output function (and which is similar to a normal has, but can be of any size of output):
func New16() Hash { xof, _ := blake2b.NewXOF(2048, nil) return &hash16{xof: xof} }
This initialises our hash value to a Nil hash value (“0000000000000000000000000000000000000000000000000000000000000000”). To add a hash, we take the current hash (x) and add a new one (y). We then take two bytes (16 bits) at a time from each, and then add them together, and then put it back into the current value of x:
func add16(x, y *[2048]byte) { for i := 0; i < 2048; i += 2 { xi, yi := x[i:i+2], y[i:i+2] sum := binary.LittleEndian.Uint16(xi) + binary.LittleEndian.Uint16(yi) binary.LittleEndian.PutUint16(xi, sum) } }
To perform a removal of a value (y) from x (the current hash), we just subtract the hash two bytes(16 bits) at a time:
func sub16(x, y *[2048]byte) { for i := 0; i < 2048; i += 2 { xi, yi := x[i:i+2], y[i:i+2] sum := binary.LittleEndian.Uint16(xi) - binary.LittleEndian.Uint16(yi) binary.LittleEndian.PutUint16(xi, sum) } }
Coding
The code is:
package main import ( "fmt" "os" "lukechampine.com/lthash" ) func main() { m1 := "Edinburgh" m2 := "Glasgow" m3 := "Dundee" m4 := "Aberdeen" argCount := len(os.Args[1:]) if argCount > 0 { m1 = os.Args[1] } if argCount > 1 { m2 = os.Args[2] } if argCount > 2 { m3 = os.Args[3] } if argCount > 3 { m4 = os.Args[4] } h := lthash.New16() fmt.Printf("Adding: %s\n", m1) fmt.Printf("Adding: %s\n", m2) fmt.Printf("Adding: %s\n", m3) h.Add([]byte(m1)) h.Add([]byte(m2)) h.Add([]byte(m3)) oldSum := h.Sum(nil) fmt.Printf("Sum (first 32 bytes): %x\n", oldSum[:32]) fmt.Printf("\nRemoving: %s\n", m1) fmt.Printf("Adding: %s\n", m4) h.Remove([]byte(m1)) h.Add([]byte(m4)) newSum := h.Sum(nil) fmt.Printf("Sum (first 32 bytes): %x\n", newSum[:32]) fmt.Printf("\nNow checking with: %s, %s, %s\n", m2, m3, m4) h = lthash.New16() h.Add([]byte(m2)) h.Add([]byte(m3)) h.Add([]byte(m4)) newSum = h.Sum(nil) fmt.Printf("Sum (first 32 bytes): %x\n", newSum[:32]) fmt.Printf("\nThe length of the hash is: %d bytes\n", len(newSum)) }
A sample run is:
Adding: Edinburgh Adding: Glasgow Adding: Dundee Sum (first 32 bytes): 3a2031807078ccf8c9ae4fd21ce6c4407e558e9671aedd9eff8758766d690944 Removing: Edinburgh Adding: Stirling Sum (first 32 bytes): 3c02c125fd9d9d679f5f8a536dbd6498ff55b5d1ec85440b91cd9a6969100cbf Now checking with: Glasgow, Dundee, Stirling Sum (first 32 bytes): 3c02c125fd9d9d679f5f8a536dbd6498ff55b5d1ec85440b91cd9a6969100cbf The length of the hash is: 2048 bytes
Coding
References
[1] Bellare, M., & Micciancio, D. (1997, May). A new paradigm for collision-free hashing: Incrementality at reduced cost. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 163–192). Springer, Berlin, Heidelberg.
[2] Lewi, K., Kim, W., Maykov, I., & Weis, S. (2019). Securing Update Propagation with Homomorphic Hashing. Cryptology ePrint Archive.