hyginn/qUUID.R

## qUUID.R
# qUUID.R
#
# Author: Boris Steipe (ORCID: 0000-0002-1134-6758)
# License: (c) Author (2018) + MIT
# Date: 2019-01-14
#
# A utility to generate UUIDS from qrandom::qrandom() quantum random bits.


# ==== intro ===================================================================


# Shout out to the fabulous qrandom package (Köstlmeier 2019) that
# provides an interface to the equally fabulous quantum-randomness generator at
# ANU in Canberra. (https://qrng.anu.edu.au) (Haw et al. 2005)

if (!requireNamespace("qrandom")) {
  install.packages(qrandom)
}

# ==== motivation ==============================================================


# Universally Unique IDentifiers (UUIDs) are a fantastic idea - especially for
# distributed database applications. They work by randomly choosing a number
# from a large number space, such that the probability of assigning the same
# number twice is exceedingly small. How small? UUIDs are 128 bit numbers. 6 bit
# are used for storing a version ID, that leaves us with 2^122 == 5.3e+36
# possibilities. That's 5,316,912,000,000,000,000,000,000,000,000,000,000.
# Choosing the same number twice is about as likely as winning at a 6/49 lottery
# - five times in a row! But there's a catch: in order to choose two numbers at
# random, we need to generate random numbers on our computer. Our pseudo random
# number generators are very good. But they have a potential weakness regarding
# the seed that is used to initalize them, and the seed-space for the RNG may be
# very, very, very much smaller than the potential state space of the number.

# A sound approach would therefore wish to use true random numbers, and such
# true random numbers are available from the vacuum quantum fluctuation
# measurements at the Australian National University in Canberra.

# The code below builds RFC 4122 compliant UUIDs from true random numbers
# supplied by the ANU quantum random number generator.

# ==== requirements and design =================================================


# How is a UUID formatted? Various versions of UUIDs exist, they are defined in
# RFC 4122. We will use version 4, for random UUIDs.

# The structure of the UUID is described as follows in RFC 4122 (The field names
# are relevant for alternative, time- and machine-based UUIDs, not for random
# UUIDs):
#

#    0                   1                   2                   3
#    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
#   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#   |                          time_low                             |
#   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#   |       time_mid                |         time_hi_and_version   |
#   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#   |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
#   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#   |                         node (2-5)                            |
#   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

# These are 16 octets.
# Section 4.4 of RFC 4122 specifies the algorithm to create the UUID:
#
#      o  Set the two most significant bits (bits 6 and 7) of the
#      clock_seq_hi_and_reserved to zero and one, respectively.
#
#      o  Set the four most significant bits (bits 12 through 15) of the
#      time_hi_and_version field to the 4-bit version number from
#      Section 4.1.3.    [Note: These are 0 1 0 0 ]
#
#      o  Set all the other bits to randomly (or pseudo-randomly) chosen
#      values.
#
#  This gives us the following layout of blocks with indices of an R vector
#      0                   1                   2                   3
#      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
#     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#   1 |                               |                               |  32
#     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#  33 |                               |                        0 1 0 0|  64
#     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#  65 |            0 1                |                               |  96
#     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
#  97 |                               |                               | 128
#     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

# Strategy: we build 128 bit raw vectors from blocks of 32 quantum-random
# hexadecimals. Then we overwrite the version identification into our vector,
# and collapse it back into hexadecimals.

# ==== code ====================================================================


qUUID <- function(n, type = "canonical") {
  # n: number of uuids to return
  # type: either "canonical" with a RFC 1422 8-4-4-4-12 pattern,
  #       or "block" with only the hex digits.
  # value: n RFC 1422 conforming, random UUIDs (or the equivalent hex strings).
  #
  # Note: for limitations on n, see the documentation to qrandom::qrandom().
  #

  if (type == "canonical") {
    insertHyphens <- TRUE
  } else if (type == "block") {
    insertHyphens <- FALSE
  } else {
      stop("Unrecognized \"type\" parameter.")
  }

  x2bit <- function(x) {
    # x: a 32 digit hex string
    # return: a 128 raw vector, its binary representation
    idx <- seq(1, 32, by = 4)
    x8 <- substring(x, idx, idx + 3)
    x8 <- paste0("0x", x8)
    s <- c(13:16, 9:12, 5:8, 1:4)  # undo reversal by strtoi
    m8 <- sapply(x8, FUN = function(x) { intToBits(strtoi(x))[s] })
    return(as.vector(m8))
  }

  stampVersion <- function(b) {
    # stamp the UUID random version identifier onto a 128 bit raw vector.
    b[61:64] <- as.raw(c(0, 1, 0, 0))
    b[71:72] <- as.raw(c(0, 1))
    return(b)
  }

  bit2x <- function(b) {
    # b: a 128 raw vector
    # x: the 32 digit hex string represented by b
    dim(b) <- c(4, 32)
    hMap <- c("0", "1", "2", "3", "4", "5", "6", "7",
              "8", "9", "a", "b", "c", "d", "e", "f")
    p2 <- 2^(0:3)
    x <- apply(b, 2, FUN = function(x) {hMap[sum(as.integer(x) * p2) + 1]} )
    return(paste0(x, collapse = ""))
  }

  hyphenate <- function(x) {
    # x: a 32 digit string
    # value: the string hyphenated in a 8-4-4-4-12 pattern
    from <- c(1, 9, 13, 17, 21)
    to <- c(8, 12, 16, 20, 32)
    return(paste(substring(x, from, to), collapse = "-"))
  }

  x <- qrandom::qrandom(n = n, type = "hex16", blocksize = 16)
  x <- tolower(x)
  x <- sapply(x, FUN = x2bit)
  x <- apply(x, 2, FUN = stampVersion)
  x <- apply(x, 2, FUN = bit2x)
  if (insertHyphens) {
    x <- sapply(x, FUN = hyphenate)
  }
  names(x) <- NULL

  return(x)
}

# ==== examples ================================================================


qUUID(5)
#   [1] "511bc559-46d2-6a52-d8c7-7b966ac9a03f"
#   [2] "fe9558ca-a689-6c92-a82a-975e7cd2511d"
#   [3] "ed441b6a-f39f-77f2-395b-79ca92dec0b4"
#   [4] "e2c58a3d-0f29-f6c2-4ac9-7ccef754cb00"
#   [5] "a23ea2c7-54fb-a452-399d-309de6944633"


qUUID(5, type = "block")

#   [1] "ec046929ca056942c8c8cfa399884182"
#   [2] "6dd865e4e1d6bf325ab2a883aafd92e5"
#   [3] "c7dfcb641259d9222b203c958ef0f624"
#   [4] "d9d25366b2fb093208046dd33bb5d054"
#   [5] "ee4a8a36fb191db21bfe008f1a4c6a68"

# ==== tests ===================================================================


library(testthat)

x2bit <- function(x) {
  # x: a 32 digit hex string
  # return: a 128 raw vector, its binary representation
  idx <- seq(1, 32, by = 4)
  x8 <- substring(x, idx, idx + 3)
  x8 <- paste0("0x", x8)
  s <- c(13:16, 9:12, 5:8, 1:4)  # undo reversal by strtoi
  m8 <- sapply(x8, FUN = function(x) { intToBits(strtoi(x))[s] })
  return(as.vector(m8))
}

test_that("function returns valid output", {
  xC <- qUUID(10)
  xB <- qUUID(1, type = "block")
  # returns values
  expect_equal(10,                     length(xC))
  expect_equal(1,                     length(xB))
  # correct string length
  expect_true(all(nchar(xC) == 36))
  expect_true(nchar(xB) == 32)

  xB <- c(gsub("-", "", xC), xB)  # purge hyphens
  x <- sapply(xB, FUN = x2bit)    # convert to bit matrix

  expect_true(all(x[61, ] == 0))
  expect_true(all(x[62, ] == 1))
  expect_true(all(x[63, ] == 0))
  expect_true(all(x[64, ] == 0))

  expect_true(all(x[71, ] == 0))
  expect_true(all(x[72, ] == 1))

})

# ==== references ==============================================================


# J.Y. Haw, S.M. Assad, A.M. Lance, N.H.Y. Ng, V. Sharma, P.K. Lam, and T. Symul
# (2005) Maximization of Extractable Randomness in a Quantum Random-Number
# Generator. Phys. Rev. Applied 3, 054004

# Köstlmeier, S (2019) qrandom: True Random Numbers using the ANU Quantum Random
# Numbers Server https://cran.r-project.org/package=qrandom

# Network Working Group (2005) A Universally Unique IDentifier (UUID) URN
# Namespace (RFC 4122).
# https://tools.ietf.org/html/rfc4122


# [END]
	# qUUID.R
	#
	# Author: Boris Steipe (ORCID: 0000-0002-1134-6758)
	# License: (c) Author (2018) + MIT
	# Date: 2019-01-14
	#
	# A utility to generate UUIDS from qrandom::qrandom() quantum random bits.


	# ==== intro ===================================================================


	# Shout out to the fabulous qrandom package (Köstlmeier 2019) that
	# provides an interface to the equally fabulous quantum-randomness generator at
	# ANU in Canberra. (https://qrng.anu.edu.au) (Haw et al. 2005)

	if (!requireNamespace("qrandom")) {
	install.packages(qrandom)
	}

	# ==== motivation ==============================================================


	# Universally Unique IDentifiers (UUIDs) are a fantastic idea - especially for
	# distributed database applications. They work by randomly choosing a number
	# from a large number space, such that the probability of assigning the same
	# number twice is exceedingly small. How small? UUIDs are 128 bit numbers. 6 bit
	# are used for storing a version ID, that leaves us with 2^122 == 5.3e+36
	# possibilities. That's 5,316,912,000,000,000,000,000,000,000,000,000,000.
	# Choosing the same number twice is about as likely as winning at a 6/49 lottery
	# - five times in a row! But there's a catch: in order to choose two numbers at
	# random, we need to generate random numbers on our computer. Our pseudo random
	# number generators are very good. But they have a potential weakness regarding
	# the seed that is used to initalize them, and the seed-space for the RNG may be
	# very, very, very much smaller than the potential state space of the number.

	# A sound approach would therefore wish to use true random numbers, and such
	# true random numbers are available from the vacuum quantum fluctuation
	# measurements at the Australian National University in Canberra.

	# The code below builds RFC 4122 compliant UUIDs from true random numbers
	# supplied by the ANU quantum random number generator.

	# ==== requirements and design =================================================


	# How is a UUID formatted? Various versions of UUIDs exist, they are defined in
	# RFC 4122. We will use version 4, for random UUIDs.

	# The structure of the UUID is described as follows in RFC 4122 (The field names
	# are relevant for alternative, time- and machine-based UUIDs, not for random
	# UUIDs):
	#

	# 0 1 2 3
	# 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# \| time_low \|
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# \| time_mid \| time_hi_and_version \|
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# \|clk_seq_hi_res \| clk_seq_low \| node (0-1) \|
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# \| node (2-5) \|
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	# These are 16 octets.
	# Section 4.4 of RFC 4122 specifies the algorithm to create the UUID:
	#
	# o Set the two most significant bits (bits 6 and 7) of the
	# clock_seq_hi_and_reserved to zero and one, respectively.
	#
	# o Set the four most significant bits (bits 12 through 15) of the
	# time_hi_and_version field to the 4-bit version number from
	# Section 4.1.3. [Note: These are 0 1 0 0 ]
	#
	# o Set all the other bits to randomly (or pseudo-randomly) chosen
	# values.
	#
	# This gives us the following layout of blocks with indices of an R vector
	# 0 1 2 3
	# 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# 1 \| \| \| 32
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# 33 \| \| 0 1 0 0\| 64
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# 65 \| 0 1 \| \| 96
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	# 97 \| \| \| 128
	# +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	# Strategy: we build 128 bit raw vectors from blocks of 32 quantum-random
	# hexadecimals. Then we overwrite the version identification into our vector,
	# and collapse it back into hexadecimals.

	# ==== code ====================================================================


	qUUID <- function(n, type = "canonical") {
	# n: number of uuids to return
	# type: either "canonical" with a RFC 1422 8-4-4-4-12 pattern,
	# or "block" with only the hex digits.
	# value: n RFC 1422 conforming, random UUIDs (or the equivalent hex strings).
	#
	# Note: for limitations on n, see the documentation to qrandom::qrandom().
	#

	if (type == "canonical") {
	insertHyphens <- TRUE
	} else if (type == "block") {
	insertHyphens <- FALSE
	} else {
	stop("Unrecognized \"type\" parameter.")
	}

	x2bit <- function(x) {
	# x: a 32 digit hex string
	# return: a 128 raw vector, its binary representation
	idx <- seq(1, 32, by = 4)
	x8 <- substring(x, idx, idx + 3)
	x8 <- paste0("0x", x8)
	s <- c(13:16, 9:12, 5:8, 1:4) # undo reversal by strtoi
	m8 <- sapply(x8, FUN = function(x) { intToBits(strtoi(x))[s] })
	return(as.vector(m8))
	}

	stampVersion <- function(b) {
	# stamp the UUID random version identifier onto a 128 bit raw vector.
	b[61:64] <- as.raw(c(0, 1, 0, 0))
	b[71:72] <- as.raw(c(0, 1))
	return(b)
	}

	bit2x <- function(b) {
	# b: a 128 raw vector
	# x: the 32 digit hex string represented by b
	dim(b) <- c(4, 32)
	hMap <- c("0", "1", "2", "3", "4", "5", "6", "7",
	"8", "9", "a", "b", "c", "d", "e", "f")
	p2 <- 2^(0:3)
	x <- apply(b, 2, FUN = function(x) {hMap[sum(as.integer(x) * p2) + 1]} )
	return(paste0(x, collapse = ""))
	}

	hyphenate <- function(x) {
	# x: a 32 digit string
	# value: the string hyphenated in a 8-4-4-4-12 pattern
	from <- c(1, 9, 13, 17, 21)
	to <- c(8, 12, 16, 20, 32)
	return(paste(substring(x, from, to), collapse = "-"))
	}

	x <- qrandom::qrandom(n = n, type = "hex16", blocksize = 16)
	x <- tolower(x)
	x <- sapply(x, FUN = x2bit)
	x <- apply(x, 2, FUN = stampVersion)
	x <- apply(x, 2, FUN = bit2x)
	if (insertHyphens) {
	x <- sapply(x, FUN = hyphenate)
	}
	names(x) <- NULL

	return(x)
	}

	# ==== examples ================================================================


	qUUID(5)
	# [1] "511bc559-46d2-6a52-d8c7-7b966ac9a03f"
	# [2] "fe9558ca-a689-6c92-a82a-975e7cd2511d"
	# [3] "ed441b6a-f39f-77f2-395b-79ca92dec0b4"
	# [4] "e2c58a3d-0f29-f6c2-4ac9-7ccef754cb00"
	# [5] "a23ea2c7-54fb-a452-399d-309de6944633"


	qUUID(5, type = "block")

	# [1] "ec046929ca056942c8c8cfa399884182"
	# [2] "6dd865e4e1d6bf325ab2a883aafd92e5"
	# [3] "c7dfcb641259d9222b203c958ef0f624"
	# [4] "d9d25366b2fb093208046dd33bb5d054"
	# [5] "ee4a8a36fb191db21bfe008f1a4c6a68"

	# ==== tests ===================================================================


	library(testthat)

	x2bit <- function(x) {
	# x: a 32 digit hex string
	# return: a 128 raw vector, its binary representation
	idx <- seq(1, 32, by = 4)
	x8 <- substring(x, idx, idx + 3)
	x8 <- paste0("0x", x8)
	s <- c(13:16, 9:12, 5:8, 1:4) # undo reversal by strtoi
	m8 <- sapply(x8, FUN = function(x) { intToBits(strtoi(x))[s] })
	return(as.vector(m8))
	}

	test_that("function returns valid output", {
	xC <- qUUID(10)
	xB <- qUUID(1, type = "block")
	# returns values
	expect_equal(10, length(xC))
	expect_equal(1, length(xB))
	# correct string length
	expect_true(all(nchar(xC) == 36))
	expect_true(nchar(xB) == 32)

	xB <- c(gsub("-", "", xC), xB) # purge hyphens
	x <- sapply(xB, FUN = x2bit) # convert to bit matrix

	expect_true(all(x[61, ] == 0))
	expect_true(all(x[62, ] == 1))
	expect_true(all(x[63, ] == 0))
	expect_true(all(x[64, ] == 0))

	expect_true(all(x[71, ] == 0))
	expect_true(all(x[72, ] == 1))

	})

	# ==== references ==============================================================


	# J.Y. Haw, S.M. Assad, A.M. Lance, N.H.Y. Ng, V. Sharma, P.K. Lam, and T. Symul
	# (2005) Maximization of Extractable Randomness in a Quantum Random-Number
	# Generator. Phys. Rev. Applied 3, 054004

	# Köstlmeier, S (2019) qrandom: True Random Numbers using the ANU Quantum Random
	# Numbers Server https://cran.r-project.org/package=qrandom

	# Network Working Group (2005) A Universally Unique IDentifier (UUID) URN
	# Namespace (RFC 4122).
	# https://tools.ietf.org/html/rfc4122


	# [END]