Misplaced Pages

#859140

71-399: Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes in the tree. Conversely, in a hash list, the number is proportional to the number of leaf nodes itself. A Merkle tree is therefore an efficient example of a cryptographic commitment scheme , in which the root of the tree is seen as

142-481: A collision-resistant hash function. The main rationale was to diminish TSA trust requirements. Tree-like schemes and operating in rounds were proposed by Benaloh and de Mare in 1991 and by Bayer, Haber and Stornetta in 1992. Benaloh and de Mare constructed a one-way accumulator in 1994 and proposed its use in time-stamping. When used for aggregation, one-way accumulator requires only one constant-time computation for round membership verification. Surety started

213-409: A cryptographic hash function such as SHA-2 is used for the hashing. If the hash tree only needs to protect against unintentional damage, unsecured checksums such as CRCs can be used. In the top of a hash tree there is a top hash (or root hash or master hash ). Before downloading a file on a P2P network , in most cases the top hash is acquired from a trusted source, for instance a friend or

284-473: A basic tool for measurement and computation in many areas of science and engineering; in these contexts log  x still often means the base ten logarithm. In mathematics log  x usually means to the natural logarithm (base e ). In computer science and information theory, log often refers to binary logarithms (base 2). The following table lists common notations for logarithms to these bases. The "ISO notation" column lists designations suggested by

355-443: A commitment and leaf nodes may be revealed and proven to be part of the original commitment. The concept of a hash tree is named after Ralph Merkle , who patented it in 1979. Hash trees can be used to verify any kind of data stored, handled and transferred in and between computers. They can help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that

426-536: A data block size of 1024 bytes and uses the Tiger hash . Tiger tree hashes are used in Gnutella , Gnutella2 , and Direct Connect P2P file sharing protocols and in file sharing applications such as Phex , BearShare , LimeWire , Shareaza , DC++ and gtk-gnutella . Logarithm In mathematics , the logarithm to base b is the inverse function of exponentiation with base b . That means that

497-460: A file or set of files. Nodes farther up in the tree are the hashes of their respective children. For example, in the above picture hash 0 is the result of hashing the concatenation of hash 0-0 and hash 0-1 . That is, hash 0 = hash ( hash 0-0 + hash 0-1 ) where "+" denotes concatenation. Most hash tree implementations are binary (two child nodes under each node) but they can just as well use many more child nodes under each node. Usually,

568-447: A great aid to calculations before the invention of computers. Given a positive real number b such that b ≠ 1 , the logarithm of a positive real number x with respect to base  b is the exponent by which b must be raised to yield x . In other words, the logarithm of x to base  b is the unique real number  y such that b y = x {\displaystyle b^{y}=x} . The logarithm

639-403: A hash list or hash chain becomes fairly big. But if it is a tree, one small branch can be downloaded quickly, the integrity of the branch can be checked, and then the downloading of data blocks can start. The Merkle hash root does not indicate the tree depth, enabling a second-preimage attack in which an attacker creates a document other than the original that has the same Merkle hash root. For

710-450: A prerequisite of some formal security proofs , and helps in making some proofs tighter. Some implementations limit the tree depth using hash tree depth prefixes before hashes, so any extracted hash chain is defined to be valid only if the prefix decreases at each step and is still positive when the leaf is reached. The Tiger tree hash is a widely used form of hash tree. It uses a binary hash tree (two child nodes under each node), usually has

781-446: A product is the sum of the logarithms of the numbers being multiplied; the logarithm of the ratio of two numbers is the difference of the logarithms. The logarithm of the p -th power of a number is p  times the logarithm of the number itself; the logarithm of a p -th root is the logarithm of the number divided by p . The following table lists these identities with examples. Each of the identities can be derived after substitution of

SECTION 10

#1732787362860

852-505: A very strong sense - they satisfy the so-called "knowledge-binding" condition. The security guarantee offered by Buldas, Saarepera in 2004 is improved by diminishing the security loss coefficient from N {\displaystyle N} to N {\displaystyle {\sqrt {N}}} . The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant or even one-way; secure time-stamping schemes are probably possible even in

923-453: A web site that is known to have good recommendations of files to download. When the top hash is available, the hash tree can be received from any non-trusted source, like any peer in the P2P network. Then, the received hash tree is checked against the trusted top hash, and if the hash tree is damaged or fake, another hash tree from another source will be tried until the program finds one that matches

994-533: Is log b   y . Roughly, a continuous function is differentiable if its graph has no sharp "corners". Moreover, as the derivative of f ( x ) evaluates to ln( b ) b by the properties of the exponential function , the chain rule implies that the derivative of log b   x is given by d d x log b ⁡ x = 1 x ln ⁡ b . {\displaystyle {\frac {d}{dx}}\log _{b}x={\frac {1}{x\ln b}}.} That is,

1065-604: Is a positive real number . (If b is not a positive real number, both exponentiation and logarithm can be defined but may take several values, which makes definitions much more complicated.) One of the main historical motivations of introducing logarithms is the formula log b ⁡ ( x y ) = log b ⁡ x + log b ⁡ y , {\displaystyle \log _{b}(xy)=\log _{b}x+\log _{b}y,} by which tables of logarithms allow multiplication and division to be reduced to addition and subtraction,

1136-407: Is also protected by this data structure, making backdating of the issued time-stamps impossible, even by the issuing server itself. The top of the authenticated data structure is generally published in some hard-to-modify and widely witnessed media, like printed newspaper or public blockchain . There are no (long-term) private keys in use, avoiding PKI -related risks. Suitable candidates for

1207-426: Is called the base- b logarithm function or logarithmic function (or just logarithm ). The function log b   x can also be essentially characterized by the product formula log b ⁡ ( x y ) = log b ⁡ x + log b ⁡ y . {\displaystyle \log _{b}(xy)=\log _{b}x+\log _{b}y.} More precisely,

1278-539: Is denoted " log b   x " (pronounced as "the logarithm of x to base  b ", "the base- b logarithm of x ", or most commonly "the log, base  b , of x "). An equivalent and more succinct definition is that the function log b is the inverse function to the function x ↦ b x {\displaystyle x\mapsto b^{x}} . Several important formulas, sometimes called logarithmic identities or logarithmic laws , relate logarithms to one another. The logarithm of

1349-491: Is exactly one real number x such that b x = y {\displaystyle b^{x}=y} . We let log b : R > 0 → R {\displaystyle \log _{b}\colon \mathbb {R} _{>0}\to \mathbb {R} } denote the inverse of f . That is, log b   y is the unique real number x such that b x = y {\displaystyle b^{x}=y} . This function

1420-405: Is frequently used in computer science . Logarithms were introduced by John Napier in 1614 as a means of simplifying calculations. They were rapidly adopted by navigators , scientists, engineers, surveyors , and others to perform high-accuracy computations more easily. Using logarithm tables , tedious multi-digit multiplication steps can be replaced by table look-ups and simpler addition. This

1491-432: Is greater than one. In that case, log b ( x ) is an increasing function . For b < 1 , log b  ( x ) tends to minus infinity instead. When x approaches zero, log b   x goes to minus infinity for b > 1 (plus infinity for b < 1 , respectively). Analytic properties of functions pass to their inverses. Thus, as f ( x ) = b is a continuous and differentiable function , so

SECTION 20

#1732787362860

1562-660: Is much faster than public key cryptography. There is no need for specific cryptographic hardware with its limitations. The common technology for guaranteeing long-term attestation value of the issued time-stamps (and digitally signed data ) is periodic over-time-stamping of the time-stamp token. Because of missing key-related risks and of the plausible safety margin of the reasonably chosen hash function this over-time-stamping period of hash-linked token could be an order of magnitude longer than of public-key signed token. Stuart Haber and W. Scott Stornetta proposed in 1990 to link issued time-stamps together into linear hash-chain, using

1633-572: Is nearly as hard as finding a preimage for the used cryptographic hash function . Continuity of operation is observable by users; periodic publications in widely witnessed media provide extra transparency. Tampering with absolute time values could be detected by users, whose time-stamps are relatively comparable by system design. Absence of secret keys increases system trustworthiness. There are no keys to leak and hash algorithms are considered more future-proof than modular arithmetic based algorithms, e.g. RSA . Linked timestamping scales well - hashing

1704-575: Is possible because the logarithm of a product is the sum of the logarithms of the factors: log b ⁡ ( x y ) = log b ⁡ x + log b ⁡ y , {\displaystyle \log _{b}(xy)=\log _{b}x+\log _{b}y,} provided that b , x and y are all positive and b ≠ 1 . The slide rule , also based on logarithms, allows quick calculations without tables, but at lower precision. The present-day notion of logarithms comes from Leonhard Euler , who connected them to

1775-457: Is quite strong. Next, in 2005 it was shown that bounded time-stamping schemes with a trusted audit party (who periodically reviews the list of all time-stamps issued during an aggregation period) can be made universally composable - they remain secure in arbitrary environments (compositions with other protocols and other instances of the time-stamping protocol itself). Buldas, Laur showed in 2007 that bounded time-stamping schemes are secure in

1846-403: Is related to the number of decimal digits of a positive integer x : The number of digits is the smallest integer strictly bigger than log 10  ( x ) . For example, log 10 (5986) is approximately 3.78 . The next integer above it is 4, which is the number of digits of 5986. Both the natural logarithm and the binary logarithm are used in information theory , corresponding to

1917-411: Is written as f ( x ) = b . When b is positive and unequal to 1, we show below that f is invertible when considered as a function from the reals to the positive reals. Let b be a positive real number not equal to 1 and let f ( x ) = b . It is a standard result in real analysis that any continuous strictly monotonic function is bijective between its domain and range. This fact follows from

1988-651: The International Organization for Standardization . The history of logarithms in seventeenth-century Europe saw the discovery of a new function that extended the realm of analysis beyond the scope of algebraic methods. The method of logarithms was publicly propounded by John Napier in 1614, in a book titled Mirifici Logarithmorum Canonis Descriptio ( Description of the Wonderful Canon of Logarithms ). Prior to Napier's invention, there had been other techniques of similar scopes, such as

2059-439: The acidity of an aqueous solution . Logarithms are commonplace in scientific formulae , and in measurements of the complexity of algorithms and of geometric objects called fractals . They help to describe frequency ratios of musical intervals , appear in formulas counting prime numbers or approximating factorials , inform some models in psychophysics , and can aid in forensic accounting . The concept of logarithm as

2130-431: The decimal number system: log 10 ( 10 x )   = log 10 ⁡ 10   + log 10 ⁡ x   =   1 + log 10 ⁡ x . {\displaystyle \log _{10}\,(\,10\,x\,)\ =\;\log _{10}10\ +\;\log _{10}x\ =\ 1\,+\,\log _{10}x\,.} Thus, log 10  ( x )

2201-413: The exponential function in the 18th century, and who also introduced the letter e as the base of natural logarithms. Logarithmic scales reduce wide-ranging quantities to smaller scopes. For example, the decibel (dB) is a unit used to express ratio as logarithms , mostly for signal power and amplitude (of which sound pressure is a common example). In chemistry, pH is a logarithmic measure for

Merkle tree - Misplaced Pages Continue

2272-510: The function now known as the natural logarithm began as an attempt to perform a quadrature of a rectangular hyperbola by Grégoire de Saint-Vincent , a Belgian Jesuit residing in Prague. Archimedes had written The Quadrature of the Parabola in the third century BC, but a quadrature for the hyperbola eluded all efforts until Saint-Vincent published his results in 1647. The relation that

2343-579: The intermediate value theorem . Now, f is strictly increasing (for b > 1 ), or strictly decreasing (for 0 < b < 1 ), is continuous, has domain R {\displaystyle \mathbb {R} } , and has range R > 0 {\displaystyle \mathbb {R} _{>0}} . Therefore, f is a bijection from R {\displaystyle \mathbb {R} } to R > 0 {\displaystyle \mathbb {R} _{>0}} . In other words, for each positive real number y , there

2414-520: The prosthaphaeresis or the use of tables of progressions, extensively developed by Jost Bürgi around 1600. Napier coined the term for logarithm in Middle Latin, logarithmus , literally meaning ' ratio-number ' , derived from the Greek logos ' proportion, ratio, word ' + arithmos ' number ' . The common logarithm of a number is the index of that power of ten which equals

2485-407: The slope of the tangent touching the graph of the base- b logarithm at the point ( x , log b  ( x )) equals 1/( x  ln( b )) . The derivative of ln( x ) is 1/ x ; this implies that ln( x ) is the unique antiderivative of 1/ x that has the value 0 for x = 1 . It is this very simple formula that motivated to qualify as "natural" the natural logarithm; this is also one of

2556-400: The x - and the y -coordinates (or upon reflection at the diagonal line x = y ), as shown at the right: a point ( t , u = b ) on the graph of f yields a point ( u , t = log b   u ) on the graph of the logarithm and vice versa. As a consequence, log b  ( x ) diverges to infinity (gets bigger than any given number) if x grows to infinity, provided that b

2627-407: The 1970s, because it allows, at the expense of precision, much faster computation than techniques based on tables. A deeper study of logarithms requires the concept of a function . A function is a rule that, given one number, produces another number. An example is the function producing the x -th power of b from any real number  x , where the base  b is a fixed number. This function

2698-407: The advance of science, especially astronomy . They were critical to advances in surveying , celestial navigation , and other domains. Pierre-Simon Laplace called logarithms As the function f ( x ) = b is the inverse function of log b   x , it has been called an antilogarithm . Nowadays, this function is more commonly called an exponential function . A key tool that enabled

2769-528: The authenticated data structure include: The simplest linear hash chain-based time-stamping scheme is illustrated in the following diagram: The linking-based time-stamping authority (TSA) usually performs the following distinct functions: Linked timestamping is inherently more secure than the usual, public-key signature based time-stamping. All consequential time-stamps "seal" previously issued ones - hash chain (or other authenticated dictionary in use) could be built only in one way; modifying issued time-stamps

2840-425: The base is clear from the context or is irrelevant it is sometimes written log  x . The logarithm base 10 is called the decimal or common logarithm and is commonly used in science and engineering. The natural logarithm has the number  e ≈ 2.718 as its base; its use is widespread in mathematics and physics because of its very simple derivative . The binary logarithm uses base 2 and

2911-451: The base is given by: b = x 1 y , {\displaystyle b=x^{\frac {1}{y}},} which can be seen from taking the defining equation x = b log b ⁡ x = b y {\displaystyle x=b^{\,\log _{b}x}=b^{y}} to the power of 1 y . {\displaystyle {\tfrac {1}{y}}.} Among all choices for

Merkle tree - Misplaced Pages Continue

2982-405: The base, three are particularly common. These are b = 10 , b = e (the irrational mathematical constant e ≈ 2.71828183 ), and b = 2 (the binary logarithm ). In mathematical analysis , the logarithm base e is widespread because of analytical properties explained below. On the other hand, base 10 logarithms (the common logarithm ) are easy to use for manual calculations in

3053-453: The common logarithms of trigonometric functions . Another critical application was the slide rule , a pair of logarithmically divided scales used for calculation. The non-sliding logarithmic scale, Gunter's rule , was invented shortly after Napier's invention. William Oughtred enhanced it to create the slide rule—a pair of logarithmic scales movable with respect to each other. Numbers are placed on sliding scales at distances proportional to

3124-400: The differences between their logarithms. Sliding the upper scale appropriately amounts to mechanically adding logarithms, as illustrated here: For example, adding the distance from 1 to 2 on the lower scale to the distance from 1 to 3 on the upper scale yields a product of 6, which is read off at the lower part. The slide rule was an essential calculating tool for engineers and scientists until

3195-475: The example above, an attacker can create a new document containing two data blocks, where the first is hash 0-0 + hash 0-1 , and the second is hash 1-0 + hash 1-1 . One simple fix is defined in Certificate Transparency : when computing leaf node hashes, a 0x00 byte is prepended to the hash data, while 0x01 is prepended when computing internal node hashes. Limiting the hash tree size is

3266-518: The first commercial linked timestamping service in January 1995. Linking scheme is described and its security is analyzed in the following article by Haber and Sornetta. Buldas et al. continued with further optimization and formal analysis of binary tree and threaded tree based schemes. Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient. Security proof for hash-function based time-stamping schemes

3337-433: The following formula: log b ⁡ x = log k ⁡ x log k ⁡ b . {\displaystyle \log _{b}x={\frac {\log _{k}x}{\log _{k}b}}.} Typical scientific calculators calculate the logarithms to bases 10 and e . Logarithms with respect to any base  b can be determined using either of these two logarithms by

3408-482: The inverse of exponentiation extends to other mathematical structures as well. However, in general settings, the logarithm tends to be a multi-valued function. For example, the complex logarithm is the multi-valued inverse of the complex exponential function. Similarly, the discrete logarithm is the multi-valued inverse of the exponential function in finite groups; it has uses in public-key cryptography . Addition , multiplication , and exponentiation are three of

3479-462: The log base 2  ; and in photography rescaled base 2 logarithms are used to measure exposure values , light levels , exposure times , lens apertures , and film speeds in "stops". The abbreviation log  x is often used when the intended base can be inferred based on the context or discipline, or when the base is indeterminate or immaterial. Common logarithms (base 10), historically used in logarithm tables and slide rules, are

3550-433: The logarithm definitions x = b log b ⁡ x {\displaystyle x=b^{\,\log _{b}x}} or y = b log b ⁡ y {\displaystyle y=b^{\,\log _{b}y}} in the left hand sides. The logarithm log b   x can be computed from the logarithms of x and b with respect to an arbitrary base  k using

3621-410: The logarithm of a number  x to the base   b is the exponent to which b must be raised to produce x . For example, since 1000 = 10 , the logarithm base   10 {\displaystyle 10} of 1000 is 3 , or log 10  (1000) = 3 . The logarithm of x to base   b is denoted as log b  ( x ) , or without parentheses, log b   x . When

SECTION 50

#1732787362860

3692-434: The logarithm provides between a geometric progression in its argument and an arithmetic progression of values, prompted A. A. de Sarasa to make the connection of Saint-Vincent's quadrature and the tradition of logarithms in prosthaphaeresis , leading to the term "hyperbolic logarithm", a synonym for natural logarithm. Soon the new function was appreciated by Christiaan Huygens , and James Gregory . The notation Log y

3763-528: The logarithm to any base b > 1 is the only increasing function f from the positive reals to the reals satisfying f ( b ) = 1 and f ( x y ) = f ( x ) + f ( y ) . {\displaystyle f(xy)=f(x)+f(y).} As discussed above, the function log b is the inverse to the exponential function x ↦ b x {\displaystyle x\mapsto b^{x}} . Therefore, their graphs correspond to each other upon exchanging

3834-926: The lookups of the two logarithms, calculating their sum or difference, and looking up the antilogarithm is much faster than performing the multiplication by earlier methods such as prosthaphaeresis , which relies on trigonometric identities . Calculations of powers and roots are reduced to multiplications or divisions and lookups by c d = ( 10 log 10 ⁡ c ) d = 10 d log 10 ⁡ c {\displaystyle c^{d}=\left(10^{\,\log _{10}c}\right)^{d}=10^{\,d\log _{10}c}} and c d = c 1 d = 10 1 d log 10 ⁡ c . {\displaystyle {\sqrt[{d}]{c}}=c^{\frac {1}{d}}=10^{{\frac {1}{d}}\log _{10}c}.} Trigonometric calculations were facilitated by tables that contained

3905-475: The main reasons of the importance of the constant  e . Linked timestamping#Provable security Linked timestamping is a type of trusted timestamping where issued time-stamps are related to each other. Linked timestamping creates time-stamp tokens which are dependent on each other, entangled in some authenticated data structure . Later modification of the issued time-stamps would invalidate this structure. The temporal order of issued time-stamps

3976-1221: The mantissa, as the characteristic can be easily determined by counting digits from the decimal point. The characteristic of 10 · x is one plus the characteristic of x , and their mantissas are the same. Thus using a three-digit log table, the logarithm of 3542 is approximated by log 10 ⁡ 3542 = log 10 ⁡ ( 1000 ⋅ 3.542 ) = 3 + log 10 ⁡ 3.542 ≈ 3 + log 10 ⁡ 3.54 {\displaystyle {\begin{aligned}\log _{10}3542&=\log _{10}(1000\cdot 3.542)\\&=3+\log _{10}3.542\\&\approx 3+\log _{10}3.54\end{aligned}}} Greater accuracy can be obtained by interpolation : log 10 ⁡ 3542 ≈ 3 + log 10 ⁡ 3.54 + 0.2 ( log 10 ⁡ 3.55 − log 10 ⁡ 3.54 ) {\displaystyle \log _{10}3542\approx {}3+\log _{10}3.54+0.2(\log _{10}3.55-\log _{10}3.54)} The value of 10 can be determined by reverse look up in

4047-447: The most fundamental arithmetic operations. The inverse of addition is subtraction , and the inverse of multiplication is division . Similarly, a logarithm is the inverse operation of exponentiation . Exponentiation is when a number b , the base , is raised to a certain power y , the exponent , to give a value x ; this is denoted b y = x . {\displaystyle b^{y}=x.} For example, raising 2 to

4118-425: The number. Speaking of a number as requiring so many figures is a rough allusion to common logarithm, and was referred to by Archimedes as the "order of a number". The first real logarithms were heuristic methods to turn multiplication into addition, thus facilitating rapid computation. Some of these methods used tables derived from trigonometric identities. Such methods are called prosthaphaeresis . Invention of

4189-504: The other peers do not lie and send fake blocks. Hash trees are used in: Suggestions have been made to use hash trees in trusted computing systems. The initial Bitcoin implementation of Merkle trees by Satoshi Nakamoto applies the compression step of the hash function to an excessive degree, which is mitigated by using Fast Merkle Trees. A hash tree is a tree of hashes in which the leaves (i.e., leaf nodes, sometimes also called "leafs") are hashes of data blocks in, for instance,

4260-414: The power of 3 gives 8 : 2 3 = 8. {\displaystyle 2^{3}=8.} The logarithm of base b is the inverse operation, that provides the output y from the input x . That is, y = log b ⁡ x {\displaystyle y=\log _{b}x} is equivalent to x = b y {\displaystyle x=b^{y}} if b

4331-424: The practical use of logarithms was the table of logarithms . The first such table was compiled by Henry Briggs in 1617, immediately after Napier's invention but with the innovation of using 10 as the base. Briggs' first table contained the common logarithms of all integers in the range from 1 to 1000, with a precision of 14 digits. Subsequently, tables with increasing scope were written. These tables listed

SECTION 60

#1732787362860

4402-570: The presence of a universal collision-finding algorithm (i.e. universal and attacking program that is able to find collisions for any hash function). This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions. At the illustration above hash tree based time-stamping system works in rounds ( t {\displaystyle t} , t + 1 {\displaystyle t+1} , t + 2 {\displaystyle t+2} , ...), with one aggregation tree per round. Capacity of

4473-475: The previous formula: log b ⁡ x = log 10 ⁡ x log 10 ⁡ b = log e ⁡ x log e ⁡ b . {\displaystyle \log _{b}x={\frac {\log _{10}x}{\log _{10}b}}={\frac {\log _{e}x}{\log _{e}b}}.} Given a number x and its logarithm y = log b   x to an unknown base  b ,

4544-403: The result with hash 0-0 and then hash 1 and finally comparing the result with the top hash . Similarly, the integrity of data block L3 can be verified if the tree already has hash 1-1 and hash 0 . This can be an advantage since it is efficient to split files up in very small data blocks so that only small blocks have to be re-downloaded if they get damaged. If the hashed file is big, such

4615-1046: The same table, since the logarithm is a monotonic function . The product and quotient of two positive numbers c and d were routinely calculated as the sum and difference of their logarithms. The product  cd or quotient  c / d came from looking up the antilogarithm of the sum or difference, via the same table: c d = 10 log 10 ⁡ c 10 log 10 ⁡ d = 10 log 10 ⁡ c + log 10 ⁡ d {\displaystyle cd=10^{\,\log _{10}c}\,10^{\,\log _{10}d}=10^{\,\log _{10}c\,+\,\log _{10}d}} and c d = c d − 1 = 10 log 10 ⁡ c − log 10 ⁡ d . {\displaystyle {\frac {c}{d}}=cd^{-1}=10^{\,\log _{10}c\,-\,\log _{10}d}.} For manual calculations that demand any appreciable precision, performing

4686-674: The system ( N {\displaystyle N} ) is determined by the tree size ( N = 2 l {\displaystyle N=2^{l}} , where l {\displaystyle l} denotes binary tree depth). Current security proofs work on the assumption that there is a hard limit of the aggregation tree size, possibly enforced by the subtree length restriction. ISO 18014 part 3 covers 'Mechanisms producing linked tokens'. American National Standard for Financial Services, "Trusted Timestamp Management and Security" ( ANSI ASC X9.95 Standard ) from June 2005 covers linking-based and hybrid time-stamping schemes. There

4757-423: The top hash. The main difference from a hash list is that one branch of the hash tree can be downloaded at a time and the integrity of each branch can be checked immediately, even though the whole tree is not available yet. For example, in the picture, the integrity of data block L2 can be verified immediately if the tree already contains hash 0-0 and hash 1 by hashing the data block and iteratively combining

4828-488: The use of nats or bits as the fundamental units of information, respectively. Binary logarithms are also used in computer science , where the binary system is ubiquitous; in music theory , where a pitch ratio of two (the octave ) is ubiquitous and the number of cents between any two pitches is a scaled version of the binary logarithm, or log 2 times 1200, of the pitch ratio (that is, 100 cents per semitone in conventional equal temperament ), or equivalently

4899-455: The values of log 10   x for any number  x in a certain range, at a certain precision. Base-10 logarithms were universally used for computation, hence the name common logarithm, since numbers that differ by factors of 10 have logarithms that differ by integers. The common logarithm of x can be separated into an integer part and a fractional part , known as the characteristic and mantissa . Tables of logarithms need only include

4970-673: Was adopted by Leibniz in 1675, and the next year he connected it to the integral ∫ d y y . {\textstyle \int {\frac {dy}{y}}.} Before Euler developed his modern conception of complex natural logarithms, Roger Cotes had a nearly equivalent result when he showed in 1714 that log ⁡ ( cos ⁡ θ + i sin ⁡ θ ) = i θ . {\displaystyle \log(\cos \theta +i\sin \theta )=i\theta .} By simplifying difficult calculations before calculators and computers became available, logarithms contributed to

5041-463: Was presented by Buldas, Saarepera in 2004. There is an explicit upper bound N {\displaystyle N} for the number of time stamps issued during the aggregation period; it is suggested that it is probably impossible to prove the security without this explicit bound - the so-called black-box reductions will fail in this task. Considering that all known practically relevant and efficient security proofs are black-box, this negative result

#859140