"The Story of One Wetnurse."

Lately, I found myself unable to resist the temptation to translate this very pertinent classic to English. If you, reader, know of a better translation, do not hesitate to write in. And so, here goes:


"The Story of One Wetnurse."
by Vlas Mikhailovich Doroshevich.


Emperor Jing-Li-O, nicknamed Hao-Tu-Li-Chi-San-He-Nun, which means Justice Itself, once woke up feeling unwell.

- The Emperor has taken ill!

Rumours spread through the palace. Many stopped bowing to the first minister. The court poet wrote a welcoming ode to the crown prince.

The best doctors, pale with fear, bowed and apologetic, examined the Emperor, whispered in horror, and the chief doctor, falling at his feet, exclaimed:

- Permit me to tell the whole truth, oh consolation of humanity?

- Speak! - the Emperor allowed.

- Of course, you are the Son of Heaven! - said the chief doctor. - But by your unspeakable mercy, you sometimes come down to the people and allow yourself to contract such diseases as ordinary mortals may suffer. Today is the day of your greatest indulgence: your stomach is simply upset.

The Emperor was rather surprised:

- From what? Before bed, I drank nothing but my wetnurse's milk. Three hundred and sixty months have I reigned, and I nourish myself, as befits me, with the milk of a wetnurse. I have changed three hundred and sixty wetnurses, and nothing like this has ever happened to me. Who overfed my wetnurse, and with what?

The strictest investigation was immediately carried out - but it turned out that the wetnurse had eaten only the finest dishes, and that, moreover, they had been given to her in moderation.

- It could be that she fell ill naturally. What were those who chose her for me thinking? - the Emperor was angry. - Execute the culprits.

The culprits were executed, but according to the most thorough investigation, it turned out that they were blameless: the wetnurse was completely healthy.

Then the Emperor ordered his wetnurse to be brought to him.

- Why did your milk spoil? He asked sternly.

- Son of Heaven, Benefactor of the Universe. Justice Itself, - answered the trembling wetnurse, - you are seeking the truth not where it is hidden. Nobody overfed me and I myself did not overeat. Likewise, I have never been ill in my life. My milk has spoiled because I think about everything that is going on at home.

- What is going on at your home? - asked the Emperor.

- I come from the province of Pe-Chi-Li, which you saw it fit to to entrust to the mandarin Ki-Ni. He does terrible things, oh Joy of the Universe. He sold our house and took the money for himself, because we could not give him the bribe he demanded. He took my sister as his concubine, and beheaded her husband so that he would not complain. In addition, he executed my father and imprisoned my mother. In general, he treated us the way he treats everyone. When I remember all of this, I cry - and that's why my milk spoils.

The Emperor was terribly angry.

- Summon all of my advisers to me!

And when they appeared, he strictly ordered:

- Find me an honest man now.

They found one.

And the Emperor said to him:

- Mandarin Ki-Ni, to whom I entrusted governing the province of Pe-Chi-Li, does such things that even my wetnurse's milk has spoiled. Go there now, carry out the most severe investigation in my name and report to me. And there is to be no concealment, you will neither add nor take away - so that the truth reflects in your words, like the moon appears in a calm, sleeping lake. You know, on a quiet night, when you look and cannot make out: where is the real moon and where is the reflection - in the lake or in the sky? Go forth now.

The honest man set out at once with a hundred of the most skilled investigators.

The mandarin, terrified to death, seeing that his position was unenviable, offered the messenger a hefty bribe.

But the honest man, having been sent by the Emperor himself, did not dare to take it.

The moon in heaven went through three changes, and the honest man and his hundred investigators were still unraveling the matter. Finally, when the fourth moon was nearing its end, the honest man came to the Emperor, fell at his feet and asked:

- Is it the whole truth that I shall tell, Justice Itself?

- All of it! - ordered the Emperor.

- If there is in the whole world, which belongs to you and to no one else, a corner worthy of tears, then it is the province of Pe-Chi-Li, the Son of Heaven. Truly, it could bring tears to the eyes of the most malevolent dragon. All over the province, everyone begs for alms, and there is no one to give alms, because everyone is begging for them. Houses are ravaged, rice fields lie fallow. And all of this is not because the inhabitants are uncommonly lazy, but because the Ki-Ni mandarin takes everything from them, no matter what they earn. There is no justice in the courts, and only he who gives the most to the mandarin is in the right. As for good morals, they have forgotten about them entirely. Just as soon as Ki-Ni lays his eyes on a pretty girl, he takes her for himself and away from her father and mother. And not only girls - he takes even married women.

- How could this be! - exclaimed the Emperor.

- Not only the moon, but the sun could vouch for the truth of my words! - replied the honest man. - Everything I have spoken is true. The ornament of your power, the cream of your provinces - the province of Pe-Chi-Li is dying!

The Emperor took his head in his hands, showing deep sorrow.

- I'll have to think about what to do! I'll have to think!

He ordered all of his courtiers to wait in the great hall, while he himself, retiring to his chamber, walked from corner to corner in contemplation. The whole day went by. Before nightfall, the Emperor appeared before his courtiers, solemnly sat down under the canopy and, when all of them fell face down to the ground, announced:

- The province of Pe-Chi-Li is in a terrible state, and therefore We proclaim: never again shall wetnurses be taken from there for the Emperor.

And ever since then, they have never once taken a wetnurse from the province of Pe-Chi-Li for the Emperor.

"Pest" v. 0xFE.

This is a continuation of "Pest" v. 0xFF.

Edit: A note for the innocent -- this series of articles concerns an algorithm! It is not, at the time of writing, fully implemented anywhere! Or even entirely complete.

Edit: Various problems and discussions.

Edit: billymg made a mirror of this page.

The document (very much a work in progress!) is available as a vtree. You will need:

Add the above vpatches and seals to your V-set, and press to pest_spec_FE.kv.vpatch.

To "compile" the document to HTML, run make (this requires the "markdown2" utility.)

Please submit any proposed changes to this spec in vpatch form.

The full text is reproduced below, and any reader able to spare the time for a careful reading is invited to comment!

Click here for a printer-friendly version of this text.


1. Introduction.

Version.

This document represents Protocol Version 0xFE.

1.1. What is Pest?

Pest is a peer-to-peer network protocol intended for IRC-style chat. It is designed for decentralization of control, resistance to natural and artificial interference, and fits-in-head mechanical simplicity -- in that order.

1.2. How Pest Differs from IRC and Other Chat Protocols.

Pest explicitly rejects the inherently-centralizing concepts of IRC (not even speaking of the even more noxious "walled-garden" atrocities perpetrated in recent years.) In place of IRC's collectivist concept of the server, every Pest user instead inhabits a stand-alone station of which he is the sole operator. Pest stations exchange authenticably-encrypted messages exclusively with an operator-configured set of peers known as a WOT (wall of trust.)

1.2.1. One Station -- One Operator.

An IRC server is typically inhabited by a multitude of casual users and policed by a small group of privileged curators. A Pest station, on the other hand, is under the exclusive control of one person: its operator.

1.2.2. Nets Instead of Channels.

Pest stations organize into nets. A net is formed by a group of station operators with a common interest. An operator who wishes to join a net must peer with at least one of the stations in that net.

A broadcast message is sent to every member of a station's net. Nets may easily and organically undergo schismatic splits, or, on the contrary, combine into larger nets, whenever the individual station operators so desire.

1.2.3. Identity is not Centrally-Registered.

To join a Pest net, an operator must simply find one or more current members of that net who would peer with his station, and securely exchange a small amount of information.

He may choose any handle he likes, so long as it does not collide with that of a peer. Importantly, one person may easily operate multiple Pest stations, and inhabit multiple disjoint nets; and may use, if he wishes, a different handle on each net.

1.2.4. Messages are Authenticable, but not Opposable.

All Pest messages are authenticable -- a station will only process a message if it carries a valid signature from a peer (though in some cases, the message may not have been authored by that peer.)

However, they are also repudiatable (i.e. non-opposable) -- since all packet signatures are produced with symmetric keys, the recipient of a message cannot, at any point in time, prove to a third party that he was not in fact the author of that message.1

1.2.5. Ostracism as the Sole Sanction.

Because Pest does not impose -- unlike IRC -- a hierarchical structure of control, it offers no direct equivalents to IRC's "kick" and "ban". An annoying, tedious, or habitually-spamming station operator is instead to be, at first -- warned by his fellows; then -- ignored via Usenet-style killfiles, and -- if he proves incorrigible -- unpeered by his peers. In the end, the malefactor will find himself where he belongs: either alone or in the company of his own kind.

1.2.6. Cyclic Connection Graphs Permitted.

Pest broadcast messages are flood-routed -- i.e. they traverse all available propagation paths. Unlike IRC relays, Pest stations may be connected in any topology their operators prefer; concretely, loops are permitted, in the interest of decentralization.

Infinite packet storms are prevented via deduplication at the station level -- rather than by prohibiting loops, or via a spanning tree protocol, or any other traditional routing schemes that enforce acyclic connection graphs by demanding the existence of "root nodes", "supernodes", centrally agreed-upon tables, etc.

Pest station operators are not merely permitted, but in fact are encouraged to form richly cyclic connection graphs for the highest attainable resiliency.

2. The Pest Station.

2.1. The Station and its Operator.

The operator of a Pest station -- who may be a human or a bot -- has absolute control of the station and its configuration.

A station communicates exclusively with:

  1. The operator -- via the operator console, an IRC-compatible interface.

  2. An operator-selected set of remote peer stations -- via datagrams.

2.2. Peers and Keys.

In order for a pair of Pest stations to communicate, their operators must decide to peer them by agreeing2 on a shared secret key K. Every packet sent by one peer to the other is signed/enciphered by the sender and verified/deciphered by the receiver using this K.

Additionally, at least one of the peers must have a routable, static address (here and below: IPv4 address and port, in a.b.c.d:p notation), and it must be known to the other peer.

If, at some future time, the operator of either station no longer wishes to continue in this relationship, he may terminate the peering unilaterally, and the two stations will then be said to have unpeered.

2.3. The WOT.

A Pest station may have any number of peers. One or more3 K for each peer is kept in a data structure referred to as the station's WOT. The operator may edit this structure at any time, and changes take effect immediately. The WOT is never altered by the station except by direct command of the operator.

2.4. The AT.

A Pest station has another data structure, the AT (Address Table), which holds the last known address4 of each WOT peer. The AT is used exclusively for determining where to send outgoing packets.

Like the WOT, the AT may also be edited by the operator at any time. Unlike the WOT, the AT is automatically updated by the station when a cryptographically-valid packet is received from a new address.

2.5. Operator Console.

A Pest station is controlled by its operator through the operator console -- an interface implementing a minimal subset of the classical IRC protocol.

Traditional IRC offers no provisions for secure authentication or encryption; hence, it is recommended that a Pest station and its IRC client reside in one physical machine. Alternatively, they may run on separate machines and connect via an SSH tunnel or similar mechanism.

Per RFC-1459, an IRC message shall not exceed 512 bytes in length, including the mandatory CR-LF terminator. Thus, there are 510 bytes available for a command entered into the console (including its parameters); and similarly for any message emitted via the console.

2.5.1. Control Commands.

Control commands allow a Pest station's operator to view or update the station's configuration. They follow the traditional IRC syntax (i.e. /COMMAND ARGUMENT). Any such command may be issued at any time, and must take effect (including preserving any state change to persistent storage) immediately.

Responses to control commands will be emitted through the console in the form of IRC NOTICE messages.

The following basic set of control commands must be supported:

Command Arguments Description
WOT Display the current WOT, with complete (apart from keys) data concerning each peer. This includes the peer's handles; whether the peer is paused; the timestamp of the most recent packet received from the peer; and the current address stored in the AT for the peer.
WOT HANDLE Display all WOT data concerning the peer identified by HANDLE, including all known keys, starting with the most recently used, for that peer.
PEER HANDLE Declare a new peer, identified by HANDLE. This command is required but not sufficient to establish communication with the peer (see also KEY and AT.)
UNPEER HANDLE Permanently discard all data concerning the peer identified by HANDLE, including keys and AT entries.
PAUSE HANDLE Temporarily disable all communication with the peer identified by HANDLE, without discarding any data.
UNPAUSE HANDLE Re-enable communication with the peer identified by HANDLE.
KEY HANDLE KEY Add a KEY for the peer identified by HANDLE. KEY is in all cases a base64-encoded 512-byte value, and may not previously exist anywhere in the WOT. If HANDLE is unknown, a warning is displayed.
UNKEY KEY Remove the given KEY from the WOT. However if KEY is any peer's only known key, the command has no effect and a warning is printed.
GAG HANDLE Add HANDLE (which may not correspond to a WOT peer!) to the killfile. Any incoming message where Speaker matches a killfile entry will not be processed.
UNGAG HANDLE Undo the effect of a previously-issued GAG command.
AT Display the current AT.
AT HANDLE Display the current AT entry for the peer identified by HANDLE.
AT HANDLE ADDRESS Set the current ADDRESS in the AT for the WOT peer identified by HANDLE. In order for two peers to communicate, at least one of them must issue this command to add the other's address to his AT. Subsequently, this value will be updated as required as packets are received.
RESOLVE HANDLE Resolve a fork afflicting the peer identified by HANDLE.

2.5.2. IRC-Compatible Commands.

The console will accept, at minimum, the following IRC-compatible commands:

Command Arguments Description
USER username hostname servername realname Must be the first command issued upon connecting to the console. The string username must equal a preconfigured value stored on disk, or the console connection will be terminated. It is not used for any other purpose. None of the other parameters are used for any purpose, but may be present.
PASS password Must be the second command issued upon connecting to the console, and if found to be invalid, the console connection will be terminated. This is a password, or a derivative thereof; the exact authentication mechanism is unspecified.
NICK HANDLE Must be the third command issued upon connecting to the console. Every message originating at this station will have a Speaker equal to HANDLE. Importantly, HANDLE may not collide with any peer handle found in the station's WOT; nor may PEER or AKA later be invoked with an argument equal to this HANDLE.
JOIN #pest Must be the fourth command issued upon connecting to the console. The argument must start with #. This is a pseudochannel which must be used in all subsequent IRC commands which require a channel (e.g. PRIVMSG, PART.) In all examples henceforth -- will be illustratively #pest, but in fact it may be any string of up to 128 bytes in length.
PART #pest Has no effect.
VERSION Display a description of the implementation and version of the protocol currently in use.
PRIVMSG (#pest or HANDLE) MESSAGE Transmit MESSAGE as a broadcast message (if first argument starts with #) or alternatively as a direct message to HANDLE. In the latter case, HANDLE must refer to a peer for whom at least one key is known and an AT entry exists. If these conditions are not satisfied, a warning is displayed and the command has no effect.

2.5.3. Optional Commands.

The console may support certain other commands, including:

Command Arguments Description
GENKEY Use the system TRNG to generate and display a new KEY suitable for use with KEY. No change is made to the WOT.
AKA HANDLE ALIAS Permit the use of the string ALIAS synonymously with the previously-known HANDLE (which may in turn be the peer's original handle, or an alias added via this command.)
UNAKA HANDLE Remove HANDLE from the WOT. However if it is any peer's only known handle, the command has no effect and a warning is displayed.
ACHTUNG MESSAGE MESSAGE will be transmitted as a WOT circular, i.e. via a direct message addressed to each individual peer, exactly as if it had been issued via /PRIVMSG peername MESSAGE for each peer separately.
BACKUP PATH The station will back up its current state (WOT, AT, killfile, and all other) to a file at the given PATH.
RESTORE PATH The station will attempt to restore all state (WOT, AT, killfile, etc) from a file at the given PATH.
SCRAM SCRAMPASS If sha512(SCRAMPASS) matches a preconfigured value stored on disk, the station will overwrite all in-memory and on-disk state with random bytes and shut down. This command may trigger other programmatic actions configured in advance by the operator, either before or after zapping all station state (e.g. in a before action -- emit a pre-defined /ACHTUNG deathsquad is here! goodbye friends!).

3. The Pest Wire Protocol.

3.1. Message.

When a line of text is entered into the operator console, this text -- along with certain other data -- becomes a new message. This message may then be encoded into a packet and transmitted to peers; and these, in turn, will forward it to their operator consoles (and relay it to their peers) if the necessary conditions are met.

The station where a message came into being is referred to as its originator.

A Pest Message consists of 424 bytes, representing the following fields:

Bytes Description
8 Timestamp
32 SelfChain
32 NetChain
32 Speaker
320 Text

3.1.1. Timestamp.

A 64-bit timestamp5 from the message's originator. A relaying station may not alter timestamps.

A station must reject any message which carries a timestamp more than 15 minutes in either direction (i.e. into the past or the future) from the moment (per the station's clock) it was received. Such messages are referred to as stale.

3.1.2. SelfChain.

3.1.2.1. SelfChain (Broadcast Messages)

A 256-bit hash6 of the originator's most recent previous message.

A station that is broadcasting for the first time must set its first message's SelfChain to zero.

If a station receives a broadcast message where SelfChain is equal to zero, and Speaker is e.g. nebuchadnezzar, and this speaker had never been seen previously, it will emit -- prior to the message -- a warning of the following form to the operator console:

Met nebuchadnezzar !

If, however, any messages with a Speaker of nebuchadnezzar were seen at any point in the past, but this message's SelfChain does not match the hash of the previous such message, the following warning shall be emitted to the console prior to the message:

nebuchadnezzar forked! prev.: "blah..."

... where "blah..." is the text of the previously-seen message pointed to by the SelfChain (if available in the buffer; if not, a base-16 representation of SelfChain is displayed instead.)

The peer nebuchadnezzar is henceforth considered forked. While he remains forked, the warning, in the above form, shall be emitted in the console (via NOTICE) every time a message is received where Speaker is nebuchadnezzar.

The fork will be considered resolved only after the station operator executes the command /RESOLVE nebuchadnezzar (after having a stern talk with the peer who had been relaying messages from the phony nebuchadnezzar!) Note that RESOLVE marks the last seen SelfChain as valid; hence, the command should be used only after the operator is reasonably certain that only the genuine nebuchadnezzar remains.

A station must not reject a broadcast message simply because its Speaker and SelfChain indicate a state of forkage. Doing so would make recovery from certain failures (lost packets; data corruption) impossible, and constitutes a denial-of-service vector. However, station operators are encouraged to make use of out-of-band (e.g. GPG) methods to resolve a fork, should one happen to arise; and to mercilessly unpeer anyone found to be deliberately causing a fork under whatever pretext.

3.1.2.2. SelfChain (Direct Messages)

A 256-bit hash of the most recent message previously generated by the originator in direct message sessions with a particular peer. One such value is stored per peer. The same rules apply as for broadcast messages.

3.1.3. NetChain.

3.1.3.1. NetChain (Broadcast Messages)

A 256-bit hash of the most recent broadcast message previously received or originated by the originator.

Currently this is not used for anything. In the future, it may be used for message reordering and Usenet-style threading.

3.1.3.2. NetChain (Direct Messages)

Must be set to zero.

3.1.4. Speaker.

A 32-byte field representing the Handle used by the originator. If this string consists of fewer than 32 bytes, all trailing bytes must be set to zero.

3.1.5. Text.

320 bytes comprising the (typically, human-readable) payload of the message. If Text consists of fewer than 320 bytes, all trailing bytes must be set to zero.

3.2. Packets.

A message, together with certain information which helps its recipient decide what to do with it, is termed a packet. Every packet starts life as red7 (i.e. plaintext).

3.2.1. Red Packet.

A red packet consists of 444 bytes, representing the following fields:

Bytes Description
16 Nonce
1 Bounces
1 Version
1 Reserved
1 Command
424 Message

3.2.1.1. Nonce.

16 bytes of garbage, exclusively for use as cipher nonce; obtained from TRNG, if possible.

3.2.1.2. Bounces.

This 1-byte field represents the number of times the message in this packet had been relayed between stations. A station must reject messages which have experienced more than a preconfigured number of bounces. The recommended cutoff value is 3.

3.2.1.3. Version.

This is a 1-byte field representing a "degrees Kelvin" (i.e. decrementing) version.

3.2.1.4. Reserved.

This 1-byte field must equal 0.

3.2.1.5. Command.

This 1-byte field represents the intended purpose of the message carried by the packet, and must have one of these values:

Value Command Description
0x00 Broadcast The message is to be relayed to the entire net.
0x01 Direct The message is strictly for the addressee, and is not intended to be relayed.
0x02 Reserved
... ... Packet is rejected
0xFE Reserved
0xFF Ignore A station may transmit garbage messages to its peers, to frustrate traffic analysis by snoops. In such cases, it will consist of arbitrary random bytes. A recipient of such a message may relay it to an arbitrary subset of his WOT. Receipt of a garbage message must not result in any console output.

3.2.1.6. Message.

A Pest message can be either:

  1. Direct -- Intended for a single recipient.

  2. Broadcast -- Intended for the widest possible dissemination. A broadcast message is sent to every peer in the originator station's WOT, and will be propagated to their peers, and so on. From the point of view of a receiver, every incoming broadcast message is either immediate or hearsay.

A broadcast message will often reach stations which are not peers of the originator. From the point of view of these stations, such a message is termed hearsay; and, when displayed, it is specially marked so as to distinguish it from an immediate message.

3.2.2. Black Packet.

A station transmits messages exclusively to peers. Prior to transmission, a red packet is ciphered and signed using a K found in the WOT for the peer to whom it is to be sent. After this happens, the packet is referred to as black.

A black Pest packet consists of 508 bytes (excluding IP and UDP headers) representing the following fields:

Bytes Description
444 Ciphertext
64 Signature

A third party without knowledge of K is unable to read such a packet; to distinguish it from arbitrary random noise; or to generate a spurious replacement (including via replay, in whole or in part, of a previously-sent packet) that could be accepted by the addressee.

Every incoming (without exception, black) packet has its Signature verified against each K in the receiving station's WOT, in random order.

If verification of the packet against a particular K succeeds, the packet is then known to have been signed by the peer associated with that K. The packet is then decrypted (with K) and becomes red once again; at this point, the receiving station is able to process the original message.

However, if none of the attempted verifications succeed, the packet is considered "martian" and silently discarded8. The receipt of a martian packet has absolutely no effect on a station, aside from wasting a small amount of CPU time. This provides a reasonable degree of DDOS resistance. A station may keep inexpensive statistical counters of martian packets.

4. Fundamental Mechanisms.

4.1. Message Origination.

When a station operator enters a line of text into the console, creating a new message, that station is termed the originator of that message.

There are two forms of message origination:

4.1.1. Direct Message to a Peer.

Suppose that a station operator using the handle shalmaneser had issued the command:

/PRIVMSG nebuchadnezzar Come to tea.

The following actions will be performed:

  1. The station's WOT is searched for a peer with a handle nebuchadnezzar. If there isn't one, or nebuchadnezzar is currently paused, nothing further happens, and a warning will be emitted to the console.
  2. The most-recently used key K for nebuchadnezzar is found. (If no keys are known for nebuchadnezzar, nothing further happens, and a warning will be emitted to the console.)
  3. The first 32 bytes of K represent K(S) -- the signing key; while the remaining 32 bytes of K are K(C) -- the cipher key.
  4. The AT entry for nebuchadnezzar is found. (If one such does not exist... see above.)
  5. A red packet is created, where:

    Bytes Description Value
    16 Nonce random bytes
    1 Bounces 0
    1 Version 255
    1 Reserved 0
    1 Command 0x01 (Direct Message)
    424 Message as given below:
    Bytes Description Value
    8 Timestamp shalmaneser's current time
    32 SelfChain hash of shalmaneser's previous direct message to nebuchadnezzar
    32 NetChain 0
    32 Speaker shalmaneser (padded with null bytes.)
    320 Text Come to tea. (Followed by 308 null bytes.)
  6. A black packet is created from the above red packet, where:

    Bytes Description Value
    444 Ciphertext SERPENT_ENCRYPT(K(C),the 424-byte red packet)
    64 Signature HMAC512(Ciphertext, K(S))
  7. The black packet (henceforth -- packet) is stored in shalmaneser's transmission queue.

  8. The packet is transmitted to nebuchadnezzar's current address, determined in step 4.
  9. When an identical packet is echoed back from the above address, the transmission is considered complete. This is expected to happen within an operator-configurable period of time (recommended: 1 second.) If it does not, a warning will be displayed in shalmaneser's console:

    nebuchadnezzar did not ACK!

  10. The packet is removed from shalmaneser's transmission queue.

4.1.2. Broadcast Message.

Suppose a station operator using the handle shalmaneser had issued the command /PRIVMSG #pest Good morning, everyone! the following actions will be performed:

  1. For each WOT peer P in shalmaneser's WOT, in random order:
  2. The most-recently used key Pk for P is found. (If no keys are known for P, we move on to the next peer.)
  3. The first 32 bytes of Pk represent Pk(S) -- the signing key; while the remaining 32 bytes of Pk are Pk(C) -- the cipher key.
  4. The AT entry for P is found. (If one such does not exist, we move on to the next peer.)
  5. For each peer, a red packet is created, where:

    Bytes Description Value
    16 Nonce random bytes
    1 Bounces 0
    1 Version 255
    1 Reserved 0
    1 Command 0x00 (Broadcast Message)
    424 Message as given below:
    Bytes Description Value
    8 Timestamp shalmaneser's current time
    32 SelfChain hash of shalmaneser's previous broadcast message
    32 NetChain hash of the previous broadcast message seen by shalmaneser, not inclusive of this one
    32 Speaker shalmaneser (padded with null bytes.)
    320 Text Good morning, everyone! (padded with null bytes.)
  6. A black packet is created from the above red packet, where:

    Bytes Description Value
    444 Ciphertext SERPENT_ENCRYPT(Pk(C),the 424-byte red packet)
    64 Signature HMAC512(Ciphertext, Pk(S))
  7. The black packets (one for each peer) are stored in shalmaneser's transmission queue.

  8. From here, we proceed exactly as in the direct message example.

4.2. Message Receipt.

4.1.1. Common Prologue for All Packets.

Suppose that a station operated by nebuchadnezzar has received a packet. The packet is from shalmaneser, but nebuchadnezzar's station does not know this yet, it has to authenticate and decrypt it first. Since all Pest packets traveling over the public internet are black, it will have the structure:

Bytes Description Value
444 Ciphertext A red packet, ciphered with unknown key K(C).
64 Signature The result of signing Ciphertext with an unknown K(S).

nebuchadnezzar's station will carry out the following procedure:

  1. For each WOT peer P in nebuchadnezzar's WOT, in random order:
  2. For each Pk known for P... (If no keys are known for P, P is simply ignored.)
  3. The first 32 bytes of Pk represent Pk(S) -- the signing key; while the remaining 32 bytes of Pk are Pk(C) -- the cipher key.
  4. HMAC512(Ciphertext, Pk(S)) is compared to Signature. If they do not match, the next one is tried. If none match, the packet is declared martian and silently discarded.
  5. If a match was found, Pk(C) is used to decrypt Ciphertext and reproduce the original red packet.
  6. Timestamp is compared to the current system time and if it is more than 15 minutes in the past or the future, the packet is considered stale and discarded.
  7. The deduplication queue (a ring buffer holding the last hour's worth of messages, or last 256kB, whichever represents a greater number of messages) is searched for the message, . If an identical message is found in the queue, the packet is considered stale and is discarded.
  8. The message was not stale; it is placed into the deduplication queue.
  9. An identical copy of the packet is echoed to its originator to acknowledge receipt.
  10. At this point, the next step in the algorithm depends on the value of the Command field...

Let H be the set of all handles found in the station's WOT for the peer who was found to have sent the packet; e.g. {shalmaneser, ShalmaneserTheGreat}.

4.1.2. Receiving a Direct Message.

Continuing after the final step of the Common Prolog:

If Command is equal to 0x01, the message is a direct message.

  1. If Speaker is not in H, a warning is emitted, e.g.:
    Direct message from 'bob' (shalmaneser)
    ... where the string in the parentheses is a WOT handle stored with the K which had validated the packet in step 4.
  2. The SelfChain warning is displayed if required.
  3. nebuchadnezzar's console will display the Speaker, followed by the Text, e.g. shalmaneser: Come to tea. in the standard format for IRC private messages.

4.1.2. Receiving a Broadcast Message.

Continuing after the final step of the Common Prolog:

If Command is equal to 0x00, the message is a broadcast message.

  1. Bounces is compared to the operator-configured cutoff. If it is in excess of the cutoff, the packet is discarded.
  2. The next step of the algorithm will depend on whether Speaker is in H.

4.1.2.1. Receiving a Broadcast Message: Immediate Messages.

If Speaker is in H, the message is known as an immediate message. It is considered prima facie authentic, and displayed in nebuchadnezzar's console in the standard form for IRC messages, marked with channel #pest.

4.1.2.2. Receiving a Broadcast Message: Hearsay Messages.

4.1.2.2.1. Simple Hearsay.

If Speaker is NOT in H, the message is known as a hearsay message.

Consider a message received by nebuchadnezzar where H = {shalmaneser}, but Speaker is in fact hammurabi; and there is not a hammurabi in nebuchadnezzar's WOT.

nebuchadnezzar's station knows that the message was sent by shalmaneser, because a K belonging to shalmaneser had verified it. However, it also knows that this message had not been originated by shalmaneser. (Or, if it had been, he is perhaps suffering from multiple personality disease.)

In any case, nebuchadnezzar must be warned that the message is hearsay.

Therefore the Text will be displayed in nebuchadnezzar's console (in channel #pest) in the following form:

hammurabi(shalmaneser): hey listen!

... where the handle in parentheses corresponds to the peer from whom the packet had come.

4.1.2.2.2. In-WOT Hearsay.

Now suppose that Speaker is not in H, i.e. the message is a hearsay message, but that Speaker in fact is in the receiver's WOT. For instance, a message exactly like the previous example's, but where hammurabi is in fact a member of nebuchadnezzar's WOT.

This can happen if the immediate copy of hammurabi's packet (i.e. received directly from its originator) has been lost or delayed in transit.

When such a packet is received and validated, it is placed into the station's hearsay buffer and will remain there for an operator-configurable interval (recommended: 1 second) with the expectation that the original, immediate version of the packet will arrive shortly, and "knock out" the embargoed hearsay version.

If, however, the embargo interval elapses and the original packet is not received -- the hearsay packet will be processed (placed into the deduplication buffer, emitted to the station's console, and rebroadcast to peers.)

4.1.2.3. Receiving a Broadcast Message: Common Epilogue.

In both Immediate and Hearsay cases, after Text is sent to the console:

  1. Bounces is incremented by 1.
  2. The message is rebroadcast (see 4.1.2. Broadcast Message) to every WOT peer -- in random order.

5. Test Vectors.

5.1. Keys.

5.1.1. Test Key A.

The base64-encoded key:

2Newlil7CEAcrLlLJhJaX1bOhYMzhbzX5s/UPYGXM3xTTry7sqvwYyp6ffinpQmgVVKZahjgIGILrPcAH2oI6A==

... when correctly decoded and broken into two 256-bit segments, represents the following (shown here in base-16) signing key:

d8d7b096297b08401cacb94b26125a5f56ce85833385bcd7e6cfd43d8197337c

... and the following cipher key:

534ebcbbb2abf0632a7a7df8a7a509a05552996a18e020620bacf7001f6a08e8

5.1.2. Test Key B.

The base64-encoded key:

DpLg4cXUoraDQHaSfScfO7rV4jJGDKvq1RkpSnHRKKhhCZXMSvaq6QGKgcAbYriNXsw0bdiiz2/M0VeKL1Cb6g==

... when correctly decoded and broken into two 256-bit segments, represents the following (shown here in base-16) signing key:

0e92e0e1c5d4a2b6834076927d271f3bbad5e232460cabead519294a71d128a8

... and the following cipher key:

610995cc4af6aae9018a81c01b62b88d5ecc346dd8a2cf6fccd1578a2f509bea

5.2. Packets.

TBD

6. Misc. Clarifications.

6.1. Symmetric Cipher.

Serpent is the only symmetric cipher to be used.

6.2. Signature.

All signatures are to be carried out using HMAC-512.

6.3. Endianism.

All byte ordering in Pest, without exception, is little-endian unless otherwise stated.

6.4. Bots.

If an operator wishes to run bots, guest accounts, etc., additional stations may be set up to peer with his primary one; on the same physical machine, if so desired.

Notes.


  1. Of course, Pest does not somehow prevent operators from creating opposably-signed messages using other software and transmitting them to their peers, on the rare occasions which actually call for this. 

  2. Via secure means external to Pest, such as GPG, Peh, or an in-person meeting. 

  3. A K is to be generated using a TRNG whenever possible. Multiple keys associated with one peer are permitted. This is convenient when phasing out an old key in favour of a new one. The converse (the use of one key for multiple peers) is prohibited. When addressing outgoing packets to a peer for whom multiple values of K are known, the one which validated the most recently-received packet is to be used. 

  4. That is, the source address of the most recent packet received from this peer. 

  5. Current time shall be defined as the value of a station's 64-bit monotonic epoch clock. Station operators must take measures to synchronize their clocks within 15 minutes, a precision entirely achievable without recourse to centralized time servers. 

  6. In the current protocol: SHA256. The hash encompasses all message fields, in the order they are listed in the table. Any trailing padding bytes required by the hash are to equal zero. 

  7. Americanism. 

  8. All discarded packets are discarded silently; at no point is there to be any response to an invalid packet. 

"Pest" v. 0xFF.

What follows is a long-promised detailed specification of a DDOS-proof, CPU-inexpensive, ciphered-authenticated peer-to-peer communication protocol.

I would like to thank Thimbronion for implementing a large subset of this spec already despite not having seen it yet!

The document (very much a work in progress!) is available as a vtree. You will need:

Add the above vpatches and seals to your V-set, and press to pest_spec.kv.vpatch.

To "compile" the document to HTML, run make (this requires the "markdown2" utility.)

Please submit any proposed changes to this spec in vpatch form.

The full text is reproduced below, and any reader able to spare the time for a careful reading is invited to comment!
This version is obsolete! Please read v. 0xFE !

Edit: click here for a printer-friendly version of this text.

Repair of sabotaged mathematical glyphs in certain Linux distros.

Recently, I received a tip that some Linux users saw rubbish in place of certain Unicode glyphs appearing in the FFA series (in particular, in Ch. 14.)

If the following two rows of symbols do not appear recognizably-identical in your WWW browser:


← → ⇠ ⇢ ⌊ ⌋

utf test

... the following fix is likely to cure:


... on Gentoo-derived Linuxen:

emerge media-fonts/dejavu


... on Arch-derived Linuxen:

pacman -S ttf-dejavu


Anyone who has witnessed the above dysfunction, or knows the details of when and why this astonishing breakage was introduced, the systems affected, the identities of the perpetrators, or anything else pertinent -- is invited to write in.

Defeating Vendor Lock-Ins: "Liebert GXT4."

Certain double-conversion UPS units by Liebert (in my case -- a GXT4-2000RT120) appear to contain a boobytrap whereby off-the-shelf (needs two 12v/80mm) high-efficiency/quiet fans will not operate -- the boot will abort with a Fan Out of Order error.

The pill: install a 100 ohm wirewound resistor in parallel with the front fan connector (on each side, will need to snip off the original plug and solder to a standard PC 4-pin extender.) This defeats the current sensor which expects to see the original (~0.4A max) fans; but not to the extent where the death of one or both of the new fans will fail to trigger the alarm.

The 2021 Rack.

Thank you, 2020 Rack Service subscribers! I would like to wish all of you another great year of hygienic Linux on high-quality non-Fritzed iron!

The 2021 service agreement is identical to the 2020 one. With the unfortunate exception that Deedbot Wallet is closing down on Dec. 25, 2020, and hence will no longer be accepted as payment starting at Dec. 23, 2020. On that day and henceforth, all subscribers will need to use traditional Bitcoin.

Any and all communication concerning the details of a payment, is to take place strictly via PGP. And please remember to clearsign each message prior to encrypting; and to verify the signature on any reply of mine after decryption.

Additionally, the upstream monthly cost has increased by 20 $, and this increase is reflected in the 2021 Price Calculator.

Since the start of the service in November 2019, there were exactly four days during which outages exceeding five minutes in length were reported. All four were attributable to malfunctions in upstream equipment.

All affected subscribers have been compensated, per the agreed-upon scheme (one day of pro-rated service per each such day; under the condition that a subscriber must publicly report the outage.) This is reflected in the table below.

Expiration dates of all current paid subscriptions are listed below (in strictly chronological order, and without identifying the subscriber) :

Subscriber Iron Effective Through
A Dulap-128-4TB 22 Dec 2020
B RK-256 10 Feb 2021
C Dulap-128-4TB 13 Feb 2021
D Colo (1U; 100W; 1 IP) 03 Apr 2021
E APU3-2TB 16 Aug 2021
F RK-128 21 Nov 2021

If you are a subscriber, you should be able to easily find yourself in this list.

"Finite Field Arithmetic." Chapter 21A-Ter: Fix for a False Alarm in Ch.14; "Litmus" Errata.

This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical "Open Sores" abomination, in that -- rather than trusting the author blindly with their lives -- prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.


You will need:

Add the above vpatches and seals to your V-set, and press to ffa_ch21a_ter_ch14_ch20_errata.kv.vpatch.

You should end up with the same directory structure as previously.

As of Chapter 21A-Ter, the versions of Peh and FFA are 250 and 199, respectively.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.


This Chapter concerns fixes for several flaws recently reported by a careful Finnish reader known only as cgra. Thank you, cgra!

Let's begin with his first find: a false alarm bug in Chapter 14B's implementation of Barrett's Modular Reduction. (Note that the proofs given in Ch.14A and Ch.14A-Bis presently stand; the bug exists strictly in the Ada program.)

Recall Step 5 of the algorithm given in Ch.14A :

For each new input X, to compute the reduction R := X mod M:

  1. Xs := X >> JM
  2. Z  := Xs × BM
  3. Zs := Z >> SM
  4. Q  := Zs × M
  5. R  := X - Q
  6. R  := R - M, C := Borrow
  7. R  := R + (M × C)
  8. R  := R - M, C := Borrow
  9. R  := R + (M × C)
  10. R  := R - (R × DM)
  11. R is now equal to X mod M.

... and its optimization, as suggested by the physical bounds proof of Ch.14A-Bis :

2WM
Ignore X
WM - L WM + L
2WM
- Ignore Q
WM - L WM + L
= R
WM + L

... and finally, its implementation in Chapter 14B :

fz_barr.adb:

   -- Reduce X using the given precomputed Barrettoid.
   procedure FZ_Barrett_Reduce(X          : in     FZ;
                               Bar        : in     Barretoid;
                               XReduced   : in out FZ) is
 
   ..............................
 
      -- R is made one Word longer than Modulus (see proof re: why)
      Rl      : constant Indices := Ml + 1;
 
   ..............................
 
      -- Barring cosmic ray, no underflow can take place in (4) and (5)
      NoCarry : WZeroOrDie := 0;
 
   begin
 
   ..............................
 
      -- (5) R  := X - Q (we only need Rl-sized segments of X and Q here)
      FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
             Difference => R, Underflow => NoCarry);
 
   ..............................

Even though we had demonstrated that Q ≤ X, the prohibition of a nonzero subtraction borrow in (5) is fallacious.

To illustrate: this Tape, on a 256-bit run of Peh :

  .1 .FF LS .1 .3 MX # QY

... will not print the expected answer to the given modular exponentiation, i.e.:

  0000000000000000000000000000000000000000000000000000000000000002

... with a Verdict of Yes; but instead will print nothing, and yield a Verdict of EGGOG. Specifically, Peh will halt at (5) via a Constraint_Error (range check failed), when the range of NoCarry's WZeroOrDie type is violated by an assignment of 1.

This is because -- early in this modular exponentiation's sequence of Barrett reductions -- and immediately prior to (5) :

X == 0x40000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 
Q == 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

... but what will be actually computed in (5) is X(1 .. Rl) - Q(1 .. Rl), i.e.:

  0x00000000000000000000000000000000000000000000000000000000000000000000000000000000 -
  0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 
=
 
  1 (Underflow == 1)

... that is, the borrow bit is legitimately 1, in this and in a number of other readily-constructed cases. The constraints we have demonstrated for X, Q, and R do not imply that a borrow will never occur in the subtraction at (5). Therefore, the intended cosmic ray detector is strictly a source of false alarms, and we will remove it:

fz_barr.adb:

   -- Reduce X using the given precomputed Barrettoid.
   procedure FZ_Barrett_Reduce(X          : in     FZ;
                               Bar        : in     Barretoid;
                               XReduced   : in out FZ) is
 
   ..............................
 
      -- Borrow from Subtraction in (5) is meaningless, and is discarded
      IgnoreC : WBool;
      pragma Unreferenced(IgnoreC);
 
   begin
 
   ..............................
 
      -- (5) R  := X - Q (we only need Rl-sized segments of X and Q here)
      FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
             Difference => R, Underflow => IgnoreC); -- Borrow is discarded
 
   ..............................

... and that's it.


Cgra's second find concerned the Ch.20 demo script, Litmus. He had discovered that two mutually-canceling bugs exist in the program. Specifically, in :

litmus.sh:

 
..................
 
# Hashed Section Length
get_sig_bytes 2
turd+=$r
hex_to_int
sig_hashed_len=$r
 
# Hashed Section (typically: timestamp)
get_sig_bytes $sig_hashed_len
turd+=$r
sig_hashed=$r
 
# Unhashed Section Length
get_sig_bytes 1
hex_to_int
sig_unhashed_len=$r
 
# Unhashed Section (discard)
get_sig_bytes $sig_unhashed_len
 
..................
..................
 
# RSA Packet Length (how many bytes to read)
get_sig_bytes 1
hex_to_int
rsa_packet_len=$r
 
# The RSA Packet itself
get_sig_bytes $rsa_packet_len
rsa_packet=$r
 
# Digest Prefix (2 bytes)
get_sig_bytes 2
digest_prefix=$r
 
..................

... the Unhashed Section Length is erroneously treated as a 1-byte field, whereas in reality the GPG format gives 2 bytes. The script only worked (on all inputs tested to date) on account of the presence of the superfluous routine (RSA Packet reader, which remained from an early version of the demo!); in all of the test cases to date, the second byte of the Unhashed Section Length (and the unhashed section in its entirety, for so long as it does not exceed 255 bytes in length -- which it appears to never do) are consumed by get_sig_bytes $rsa_packet_len.

I am almost pleased that I had made this mistake; it is in fact a better illustration of programs which operate correctly despite erroneous logic -- as well as the unsuitability of shell script as a language for nontrivial tasks -- than anything I could readily unearth in the open literature.

And the fix is readily obvious :

 
..................
 
# Hashed Section Length
get_sig_bytes 2
turd+=$r
hex_to_int
sig_hashed_len=$r
 
# Hashed Section (typically: timestamp)
get_sig_bytes $sig_hashed_len
turd+=$r
sig_hashed=$r
 
# Unhashed Section Length
get_sig_bytes 2
hex_to_int
sig_unhashed_len=$r
 
# Unhashed Section (discard)
get_sig_bytes $sig_unhashed_len
 
..................
..................
 
# Digest Prefix (2 bytes)
get_sig_bytes 2
digest_prefix=$r
 
..................

I also incorporated cgra's earlier suggestion regarding error checking. Thank you again, cgra!

And that's it for Litmus, presently.


~ The next Chapter, 21B, will (yes!) continue the Extended-GCD sequence of Chapter 21A. ~

"Cryostat" Genesis.

Cryostat is a Fits-in-Head minimal (~700 LOC, including comments) static library for adding safe and reliable persistent storage to Ada data structures. It makes use of memory-mapped disk I/O via the MMap() system call, present in Linux (kernel 2.4 and newer) and all compatible operating systems. This mechanism permits efficient work with persistent data structures substantially larger than a machine's physical RAM.

AdaCore offers their own implementation of MMap() support in GNATColl. However, IMHO their item is an atrocity, in many ways very similarly to their GNAT Sockets pile of garbage (the near-unusability of the latter is what prompted me to write Ada-UDP in 2018.) AdaCore's MMap library is not only a behemoth replete with e.g. special cases for MS-Win support, but its use is entirely incompatible with safety-restricted compilation profiles.

Cryostat, on the other hand, does NOT require enabling the use of pointerism, unchecked conversions, the secondary stack, heap allocators, or other bulky and objectionable GNAT features, in the calling program. It does however require finalization to be enabled. This is used to guarantee the safe sync-to-disk and closing of the backing MMap when the data structure it contains goes out of scope.

Let's proceed to building Cryostat and its included demo program.

You will need:

Add the above vpatch and seal to your V-set, and press to cryostat_genesis.kv.vpatch.

Now compile the included CryoDemo:

cd demo
gprbuild

... this will build both the demo and the library.

But do not run it quite yet.


First, let's see what this demo consists of :

cryodemo.adb:

with Interfaces;  use Interfaces;
with ada.text_io; use  ada.text_io;
 
with Cryostat;
 
 
procedure CryoDemo is
 
   -- Path on disk for the example Cryostat backing file :
   File_Path : constant String := "cryotest.bin";
 
   -- Now, let's define an example data structure to place in a Cryostat :
 
   -- Example payload array's element type: byte.
   subtype ADatum is Unsigned_8;
 
   -- Let's make it 512MB - far bigger than a typical stack, to demonstrate
   -- that it will in fact reside in the Cryostat, rather than on the stack :
   A_MBytes : constant Unsigned_32 := 512;
 
   -- Example payload: an array.
   subtype ARange is Unsigned_32 range 0 .. (A_MBytes * 1024 * 1024) - 1;
 
   -- Complete the definition of the payload data structure :
   type TestArray is array(ARange) of ADatum;
 
   -- Declare a Cryostat which stores a TestArray :
   package Cryo is new Cryostat(Form     => TestArray,
                                Path     => File_Path,
                                Writable => True,  -- Permit writing
                                Create   => True); -- Create file if not exists
 
   -- Handy reference to the payload; no pointerisms needed !
   T : TestArray renames Cryo.Item;
 
   -- T can now be treated as if it lived on the stack :
 
begin
 
   Put_Line("T(0)    before :  " & ADatum'Image(T(0)));
   Put_Line("T(Last) before :  " & ADatum'Image(T(T'Last)));
 
   -- Increment each of the elements of T :
   for i in T'Range loop
      T(i) := T(i) + 1;
   end loop;
 
   Put_Line("T(0)    after  :  " & ADatum'Image(T(0)));
   Put_Line("T(Last) after  :  " & ADatum'Image(T(T'Last)));
 
   --- Optional, finalizer always syncs in this example
   --  Cryo.Sync;
 
   --- Test of Zap -- uncomment and get zeroized payload every time :
   --  Cryo.Zap;
 
   Put_Line("OK.");
 
end CryoDemo;

In the demo, we define TestArray -- a data structure consisting of a 512 megabyte array, and invoke Cryostat to create a persistent disk store for it. (When the program is first run, the array -- instantiated as T -- will contain only zeros.) After this, we increment each byte in T, and terminate. When, in the end, T goes out of scope, the finalizer kicks in and properly syncs the payload to disk. Thus, T behaves exactly like a stack-allocated variable, with the exception of the fact that its contents are loaded from disk upon its creation (on the second and subsequent runs of the program) and synced to disk upon its destruction (or if Sync were to be invoked.)

Observe that the calling code is not required to perform any file-related manipulations, or to juggle memory; all of the necessary mechanisms (including error handling) are contained in the Cryostat static library.

When we first execute the demo:

./bin/cryodemo

The following output will appear:

T(0)    before :   0
T(Last) before :   0
T(0)    after  :   1
T(Last) after  :   1
OK.

If we run it again, will see the following:

T(0)    before :   1
T(Last) before :   1
T(0)    after  :   2
T(Last) after  :   2
OK.

... and so forth. cryotest.bin, the backing file used by the Cryostat in the demo, will consist of 512 megabytes of byte value N, where N is the number of times the demo has executed. For example, after the first run, a hex dump:

hexdump -C cryotest.bin

... will yield:

00000000  01 01 01 01 01 01 01 01  01 01 01 01 01 01 01 01  |................|
*
20000000

Let's use the traditional strace tool to confirm that the demo behaves as specified:

strace ./bin/cryodemo

The following output will appear:

execve("./bin/cryodemo", ["./bin/cryodemo"], [/* 84 vars */]) = 0
arch_prctl(ARCH_SET_FS, 0x644798)       = 0
set_tid_address(0x6447d0)               = 3660
rt_sigprocmask(SIG_UNBLOCK, [RT_1 RT_2], NULL, 8) = 0
rt_sigaction(SIGABRT, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
rt_sigaction(SIGFPE, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
rt_sigaction(SIGILL, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
rt_sigaction(SIGBUS, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
sigaltstack({ss_sp=0x644a80, ss_flags=0, ss_size=16384}, NULL) = 0
rt_sigaction(SIGSEGV, {0x41c360, [], SA_RESTORER|SA_STACK|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
fstat(2, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 5), ...}) = 0
fstat(0, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 5), ...}) = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 5), ...}) = 0
open("cryotest.bin", O_RDWR|O_CREAT, 0666) = 3
ftruncate(3, 536870912)                 = 0
mmap(NULL, 536870912, PROT_READ|PROT_WRITE, MAP_SHARED, 3, 0) = 0x7f3bcc575000
writev(1, [{"", 0}, {"T(0)    before :   0\n", 21}], 2) = 21
writev(1, [{"", 0}, {"T(Last) before :   0\n", 21}], 2) = 21
writev(1, [{"", 0}, {"T(0)    after  :   1\n", 21}], 2) = 21
writev(1, [{"", 0}, {"T(Last) after  :   1\n", 21}], 2) = 21
writev(1, [{"", 0}, {"OK.\n", 4}], 2)   = 4
msync(0x7f3bcc575000, 536870912, MS_SYNC) = 0
munmap(0x7f3bcc575000, 536870912)       = 0
close(3)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++

There are a few minor knobs that still ought to be added to Cryostat (See README.TXT) but even as it presently stands, it is already sufficient for basic experimentation with clean and compact databases implemented wholly in Ada.


~ To Be Continued. ~


"Finite Field Arithmetic." Chapter 21A-Bis: Fix for Lethal Flaw in Ch.15's Greatest Common Divisor.

This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical "Open Sores" abomination, in that -- rather than trusting the author blindly with their lives -- prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.

You will need:

Add the above vpatches and seals to your V-set, and press to ffa_ch21a_bis_fix_ch15_gcd.kv.vpatch.

You should end up with the same directory structure as previously.

As of Chapter 21A-Bis, the versions of Peh and FFA are 250 and 200, respectively.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.


1. The Boojum.


strap it down

This Chapter repairs a lethal bug in Chapter 15's "Constant-Time Iterative GCD" algorithm and its implementation.

While working on Ch. 21B, I found that the algorithm used in Ch. 15 is subtly broken on a very small but readily-constructible subset of its input domain.

My original (unpublished -- it was the nominal answer to Ch. 15 Exercise 2...) proof for this algo was fallacious: the calculation as formulated there is superficially correct, but it is not guaranteed to converge in Bitness(A) + Bitness(B) iterations! It is possible to construct pairs of inputs where we end up with an incorrect GCD result, and we will discuss several examples of these in this Chapter.

Cut corners are to be paid for, and I will admit that I would rather pay for this one now, with a Vpatch, a new proof, and an apology to readers, than later -- when I put FFA to use in anger, and offer BTC bounties for reporting defects.

Several supposedly-attentive FFA students at various times reported that they have eaten Ch. 15; and at least one of last year's readers even signed it. However, no one reported the defect, which I ended up uncovering while testing the final version of the Ch. 21 Extended-GCD against Ch. 15's conventional one. The breakage is triggered by a small subset of the possible input space where one or both input FZs to GCD consist almost entirely of ones (i.e. most of the bits are set.) No such case turned up in Ch. 15's randomly-generated test battery, reinforcing Dijkstra's famous observation that testing can reveal the presence of bugs, but never their absence.

Only proof can be relied on, and the proof had better be correct.


Let's proceed with two concrete examples of inputs which break the Ch. 15 GCD:

Ch. 15 GCD Counter-Example No. 1:

This Tape:

  .FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBB
  .FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB
  G
  #

... produces 4, when fed into a 256-bit-FZ run of Peh. But the two numbers are in fact co-prime, i.e. their actual GCD is 1.

Click here to see what happens when this Tape runs.


And this Tape:

Ch. 15 GCD Counter-Example No. 2:

  .FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEB
  .FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB
  G
  #

... produces 0. Which is not only not the correct answer (again 1; the given numbers are yet again co-prime) but is in fact an impossible output of any GCD invocation apart from GCD(0,0) -- and is true there only by convention.

Click here to see what happens when this Tape runs.

It is possible to generate further counter-examples, but these are quite enough to demonstrate that the Ch. 15 GCD algorithm does not work as specified.


Now let's review the broken algo:


Chapter 15 Algorithm 3: Broken Constant-Time Iterative GCD.


For FZ integers A and B:

  1. Twos := 0
  2. Iterate Bitness(A) + Bitness(B) times:
  3.    Ae   := 1 - (A AND 1)
  4.    Be   := 1 - (B AND 1)
  5.    A    := A >> Ae
  6.    B    := B >> Be
  7.    Twos := Twos + (Ae AND Be)
  8.    D    := |A - B|, C ← Borrow
  9.    B    := {C=0 → B, C=1 → A}
  10.    A    := D
  11. A := A << Twos
  12. A contains the GCD.


put it in only with tongues

To those who have read Ch. 21A, the defect may be already apparent.

Specifically, when we introduce the Iterate Bitness(A) + Bitness(B)... condition in place of the original non-constant-time algo's Iterate until B = 0..., steps 8...10 become erroneous, in two respects.

First: in a run which requires exactly Bitness(A) + Bitness(B) - 1 iterations to reach the point where A = B, A will end up equal to zero, while the GCD ends up permanently trapped in B.

The root of the problem is that D := |A - B| becomes the new value of A even when D = 0 (i.e. A and B were equal.) For virtually the whole input space of the algo, this state is temporary: the final GCD will move into A in the very next iteration, and stays there. But if there is no remaining iteration, we end up with the invalid output 0. This is illustrated by Ch. 15 GCD Counter-Example No. 2.

Second: the logic of steps 8...10 permits a condition where one or more rounds of the iteration execute without reducing the bitness of either A or B. Enough of these, and the algorithm in fact will not converge. This is illustrated by Ch. 15 GCD Counter-Example No. 1.

This time, the problem is that the subtractive step is performed without demanding (as we did starting with Algorithm 2 of Ch. 21A) that both A and B be odd. This can result in an iteration where we in fact get no closer to convergence than we were at the preceding one.

To understand exactly how the Ch.15 algo is subtly broken, let's pretend that we had a 8-bit FZ (for didactic purposes strictly; the minimal FZ bitness in FFA is 256); and then construct and illustrate a simple example, where two 8-bit quantities -- which, theoretically, would be expected to converge to their correct GCD (1) in 16 iterations -- fail to do so.


For clarity, this and all subsequent worked examples will show binary representations of A and B.

Sad_Ch15_GCD(0xfb, 0xdb) :

i Ai Bi AEven : BEven : Twos A ← |A - B| B ←?← A Ai+1 Bi+1
A ← A/2 B ← B/2
1 11111011 11011011 0 100000 11011011 100000 11011011
2 100000 11011011 10000 0 11001011 10000 11001011 10000
3 11001011 10000 1000 0 11000011 1000 11000011 1000
4 11000011 1000 100 0 10111111 100 10111111 100
5 10111111 100 10 0 10111101 10 10111101 10
6 10111101 10 1 0 10111100 1 10111100 1
7 10111100 1 1011110 0 1011101 1 1011101 1
8 1011101 1 0 1011100 1 1011100 1
9 1011100 1 101110 0 101101 1 101101 1
10 101101 1 0 101100 1 101100 1
11 101100 1 10110 0 10101 1 10101 1
12 10101 1 0 10100 1 10100 1
13 10100 1 1010 0 1001 1 1001 1
14 1001 1 0 1000 1 1000 1
15 1000 1 100 0 11 1 11 1
16 11 1 0 10 1 10 1
17 10 1 1 0 0 1 0 1
18 0 1 0 0 1 0 1 0
GCD (Incorrect) 10

The iterations marked in red, would have been necessary for successful convergence, but never execute; those marked in yellow, do not reduce the bitness of A or B.


The mine is in the fact that, if, at step 8 of the algo:

  1.    D    := |A - B|, C ← Borrow
  2.    B    := {C=0 → B, C=1 → A}
  3.    A    := D

... it so happens that A is even and B is odd, then D (and consequently the value of A in the next iteration) will be odd. And, if A ≥ B, then B will remain odd in the next iteration; and we will get an iteration cycle where the total bitness of A and B will not decrease, unless A and B happen to be close enough in value for the subtraction in step 8 to decrease it.

Thus we have seen how to construct a condition where carrying out an iteration of Ch. 15's GCD does not reduce the bitness of either A or B.


The interesting bit is that in virtually all possible inputs to GCD, this flaw does not lead to an ultimately incorrect output, because -- given sufficient iterations -- the correct answer is obtained. But in a very small number of possible input pairs, convergence will not be reached inside 2 × FZ_Bitness iterations.

It appears to be virtually impossible to arrive at the fatal condition by chance.

This kind of thing could be an ideal cryptological boobytrap, if GCD were in fact a key element in any known cryptosystem.

But AFAIK, there is no such cryptosystem. On top of this, from a cryptological point of view, the broken GCD "fails safe", i.e. it can be coaxed into reporting two co-prime inputs as being non-coprime, but not the opposite.

And, fortunately (or unfortunately, from the POV of quickly turning up possible defects) FFA does not currently use conventional-GCD inside any other internal algorithm. But let's consider where we have thus far made use of GCD.

Apart from the original Ch.15 tests, the only two places in the series where we have used GCD were the primorial generator demo depicted in Ch. 18C and the prime generator demo which used it.

The primorial generator was unaffected -- it apparently produces correct primorials for all valid FZ Widths from 256 to -- at least -- 16384.

The prime generator was also unaffected. In principle, a defective GCD would result, there, in a... slightly slower prime generator, which would attempt a larger number of doomed Miller-Rabin tests; GCD was used there strictly as speedup pre-filter for the intake candidates. But there was no detectable decrease in the number of M-R-failed runs after I put the corrected GCD into service.

The Ch. 21A material, interestingly, is also unaffected: the initially non-constant-time algo from the middle of Ch. 15 is given there as a starting point. And that algo (and all of the subsequent extensions offered) was... correct. Only the constant-time version which was used to actually write the GCD routine in Ch. 15, was not...

The bullet, it could be said, went through the hat, but not the head. Nevertheless, it is a serious defect, and will be corrected in this Chapter. And this time, the full proof of convergence will be given.


2. The Cure.


Let's rewrite the GCD algo, so that a reduction of the bitness of A, B, or both, is in fact guaranteed at every iteration.

First, we'll write a readability-optimized schematic version (expressed with branching logic) of the correct algorithm :


Chapter 21A-Bis Algorithm 1: Schematic Version of Corrected Constant-Time Iterative GCD :


For FZ integers A and B:

  1. Twos := 0
  2. Iterate Bitness(A) + Bitness(B) - 1 times:
  3.    D := |A - B|
  4.    If Odd(A) and Odd(B) :
  5.       If A < B :
  6.          B := A
  7.       A := D
  8.    If Even(A) and Even(B) :
  9.       Twos := Twos + 1
  10.    If Even(A):
  11.       A := A / 2
  12.    If Even(B):
  13.       B := B / 2
  14. A := Bitwise-OR(A, B)
  15. A := A * 2Twos
  16. A contains the GCD.


Second, and equivalently, a properly constant-time formulation of the above :

Chapter 21A-Bis Algorithm 2: Corrected Constant-Time Iterative GCD :


For FZ integers A and B:

  1. Twos := 0
  2. Iterate Bitness(A) + Bitness(B) - 1 times:
  3.    OO   := (A AND 1) AND (B AND 1)
  4.    D    := |A - B|, C ← Borrow
  5.    B    := {(OO AND C)=0 → B, (OO AND C)=1 → A}
  6.    A    := {OO=0 → A, OO=1 → D}
  7.    Ae   := 1 - (A AND 1)
  8.    Be   := 1 - (B AND 1)
  9.    A    := A >> Ae
  10.    B    := B >> Be
  11.    Twos := Twos + (Ae AND Be)
  12. A := A OR B
  13. A := A << Twos
  14. A contains the GCD.


Now, let's show, step by step, that Algorithm 1 and Algorithm 2 are arithmetically-equivalent.

Algorithm 1 Operation Description Algorithm 2 Operation
  1. Twos := 0
Initialize the common-power-of-two counter to 0.
  1. Twos := 0
  1. Iterate Bitness(A) + Bitness(B) - 1 times:
Begin a loop with exactly Bitness(A) + Bitness(B) - 1 iterations. In FFA, this is definitionally equivalent to 2×FZ_Bitness(N) - 1, where N is any of the inputs A, B or the output GCD.
  1. Iterate Bitness(A) + Bitness(B) - 1 times:
Start of Iteration
  1. D := |A - B|
Compute the absolute value of the difference A - B. In the constant-time Algorithm 2, we save the carry bit to C, which will trigger subsequent operations predicated on the condition A < B.
  1. D := |A - B|, C ← Borrow
  1. If Odd(A) and Odd(B) :
Determine whether both A and B are presently odd.
  1. OO := (A AND 1) AND (B AND 1)
  1.     If A < B :
  2.         B := A
Assign A to B if A and B were both odd, and A < B.
  1. B := {(OO AND C)=0 → B, (OO AND C)=1 → A}
  1.     A := D
Assign D to A if A and B were both odd.
  1. A := {OO=0 → A, OO=1 → D}
  1. If Even(A) and Even(B) :
  2.     Twos := Twos + 1
If both A and B are presently even, increment the common power-of-two counter.
  1. Ae := 1 - (A AND 1)
  2. Be := 1 - (B AND 1)
  1. Twos := Twos + (Ae AND Be)
  1. If Even(A):
  2.     A := A / 2
If A was found to be even, divide it by two. In Algorithm 2, this is accomplished via a Right Shift by 1.
  1. A := A >> Ae
  1. If Even(B):
  2.     B := B / 2
If B was found to be even, divide it by two. In Algorithm 2, this is accomplished via a Right Shift by 1.
  1. B := B >> Be
End of Iteration
  1. A := Bitwise-OR(A, B)
Normally, B will contain the intermediate result after convergence. However, when calculating GCD(N, 0), where N > 0, it will be found in A. The other variable will always equal 0. Hence, we obtain the final result by performing a bitwise-OR of A, B. It is assigned to A.
  1. A := A OR B
  1. A := A * 2Twos
Reintroduce the common-power-of-two factor into the intermediate GCD result. If there was none (i.e. one or both inputs were odd to begin with) this will be 20, i.e. 1, and then has no effect. In Algorithm 2, the multiplication is accomplished via a constant-time Left Shift.
  1. A := A << Twos
  1. A contains the GCD.
A now contains the actual GCD of the two input integers.
  1. A contains the GCD.
GCD is in A.

If you are entirely satisfied that Algorithm 1 and Algorithm 2 are equivalent in their effects, proceed to the proof below. For clarity, we will base it on Algorithm 1.

First, let's demonstrate that each iteration of the loop preserves the GCD of A, B :

Algorithm 1 Operation Identity
  1. D := |A - B|
  2. If Odd(A) and Odd(B) :
  3.     If A < B :
  4.         B := A
  5.     A := D

A restatement of Euclid's original :

GCD(A, B) = GCD(|A - B|, Min(A, B))

Observe that |A - B|, the new value of A, is necessarily even, while
Min(A, B), the new value of B, remains odd.

  1. If Even(A) and Even(B) :
  2.     Twos := Twos + 1

A common factor of 2 will be removed (in steps 11 and 13) from A and B, respectively, and the Twos counter is incremented, so we can multiply 2Twos back in at step 15.

GCD(2 × K, 2 × L) = 2 × GCD(K, L)

  1. If Even(A):
  2.     A := A / 2

A factor of 2 is removed from A.

GCD(2 × K, B) = GCD(K, B)

  1. If Even(B):
  2.     B := B / 2

A factor of 2 is removed from B.

GCD(A, 2 × L) = GCD(A, L)

Now, let's confirm that Algorithm 1 is in fact guaranteed to converge within at most Bitness(A) + Bitness(B) - 1 iterations. Let's exhaustively describe the effects of an iteration across the four possible combinations of parities of A and B. (Steps 8 and 9 do not affect the bitness of A or B and will be omitted.)

A is Odd, B is Odd :
Algorithm 1 Operation Effect on Bitness of A Effect on Bitness of B
  1. D := |A - B|
  2. If Odd(A) and Odd(B) :
  3.     If A < B :
  4.         B := A
  5.     A := D
No guaranteed effect (but may decrease by 1 or more bits). However, A is now necessarily even. No guaranteed effect (but may decrease by 1 or more bits). B remains odd.
  1. If Even(A):
  2.     A := A / 2
As A is guaranteed to have become even in step 7: decreases by 1 bit. None
  1. If Even(B):
  2.     B := B / 2
None None
Net Effect on Bitnesses: Decreased by at least 1 bit. May become zero if A and B had been equal. None; may decrease by 1 or more bits.

Note that in the convergence case where A=1 B=1, the above parity combination will yield A=0 B=1.

A is Odd, B is Even :
Algorithm 1 Operation Effect on Bitness of A Effect on Bitness of B
  1. D := |A - B|
  2. If Odd(A) and Odd(B) :
  3.     If A < B :
  4.         B := A
  5.     A := D
None None
  1. If Even(A):
  2.     A := A / 2
None None
  1. If Even(B):
  2.     B := B / 2
None Decreases by 1 bit, unless B = 0.
Net Effect on Bitnesses: None Decreased by 1 bit, unless B = 0.
A is Even, B is Odd :
Algorithm 1 Operation Effect on Bitness of A Effect on Bitness of B
  1. D := |A - B|
  2. If Odd(A) and Odd(B) :
  3.     If A < B :
  4.         B := A
  5.     A := D
None None
  1. If Even(A):
  2.     A := A / 2
Decreases by 1 bit, unless A = 0. None
  1. If Even(B):
  2.     B := B / 2
None None
Net Effect on Bitnesses: Decreased by 1 bit, unless A = 0. None
A is Even, B is Even :
Algorithm 1 Operation Effect on Bitness of A Effect on Bitness of B
  1. D := |A - B|
  2. If Odd(A) and Odd(B) :
  3.     If A < B :
  4.         B := A
  5.     A := D
None None
  1. If Even(A):
  2.     A := A / 2
Decreases by 1 bit, unless A = 0. None
  1. If Even(B):
  2.     B := B / 2
None Decreases by 1 bit, unless B = 0.
Net Effect on Bitnesses: Decreased by 1 bit, unless A = 0. Decreased by 1 bit, unless B = 0.

We have shown that each iteration of Algorithm 1 (and, as we have demonstrated their equivalence -- Algorithm 2) is guaranteed to reduce the bitness of A, B, or of both A and B, by at least 1 bit -- supposing we have not yet reached convergence (i.e. when nothing can be reduced because one of A or B is equal to zero, while the other is odd.)

Therefore, to compute the GCD of A, B where each is of bitness W, we in fact need at most (2 × W) - 1 iterations (i.e. to arrive at a GCD of 1, which is of bitness 1.)

Now, let's illustrate two concrete symmetric cases where the maximum permitted number of iterations is in fact required. Each of these pairs of 8-bit inputs demands 15 (i.e. ( 2 × 8 ) - 1) shots for convergence.

GCD(0x80, 0xff) :

i Ai Bi AOdd and BOdd : AEven : BEven : Twos Ai+1 Bi+1
A ← |A - B| B ← A A ← A/2 B ← B/2
1 10000000 11111111 1000000 0 1000000 11111111
2 1000000 11111111 100000 0 100000 11111111
3 100000 11111111 10000 0 10000 11111111
4 10000 11111111 1000 0 1000 11111111
5 1000 11111111 100 0 100 11111111
6 100 11111111 10 0 10 11111111
7 10 11111111 1 0 1 11111111
8 1 11111111 11111110 1 1111111 0 1111111 1
9 1111111 1 1111110 1 111111 0 111111 1
10 111111 1 111110 1 11111 0 11111 1
11 11111 1 11110 1 1111 0 1111 1
12 1111 1 1110 1 111 0 111 1
13 111 1 110 1 11 0 11 1
14 11 1 10 1 1 0 1 1
15 1 1 0 1 0 0 0 1
GCD 1

GCD(0xff, 0x80) :

i Ai Bi AOdd and BOdd : AEven : BEven : Twos Ai+1 Bi+1
A ← |A - B| B ← A A ← A/2 B ← B/2
1 11111111 10000000 1000000 0 11111111 1000000
2 11111111 1000000 100000 0 11111111 100000
3 11111111 100000 10000 0 11111111 10000
4 11111111 10000 1000 0 11111111 1000
5 11111111 1000 100 0 11111111 100
6 11111111 100 10 0 11111111 10
7 11111111 10 1 0 11111111 1
8 11111111 1 11111110 1 1111111 0 1111111 1
9 1111111 1 1111110 1 111111 0 111111 1
10 111111 1 111110 1 11111 0 11111 1
11 11111 1 11110 1 1111 0 1111 1
12 1111 1 1110 1 111 0 111 1
13 111 1 110 1 11 0 11 1
14 11 1 10 1 1 0 1 1
15 1 1 0 1 0 0 0 1
GCD 1

In both of these examples, Bitness(A)+Bitness(B) is reduced by exactly one in each iteration. And we have already demonstrated that it is impossible to construct a case -- aside from the convergence case -- where an iteration will reduce this quantity by 0. So in fact these are instances of the "worst case" number of required iterations. (Recall that we are writing a constant-time algo, and the "worst case" number of iterations will always execute.)


Now, let's illustrate what happens in the "degenerate" cases. Starting with GCD(0,0) :

GCD(0, 0) :

i Ai Bi AOdd and BOdd : AEven : BEven : Twos Ai+1 Bi+1
A ← |A - B| B ← A A ← A/2 B ← B/2
1 0 0 0 0 1 0 0
2 0 0 0 0 2 0 0
3 0 0 0 0 3 0 0
... 0 0 0 0 ... 0 0
iLast 0 0 0 0 i 0 0
GCD 0

For illustrative purposes, three iterations are shown. But the end result, without regard to FZ Width, will always be the same: 0. The Twos counter increases with each additional iteration, as both A and B remain even, but this has no effect on the final output.


Now, let's examine the case GCD(0, N) where N > 0 :

GCD(0, 3) :

i Ai Bi AOdd and BOdd : AEven : BEven : Twos Ai+1 Bi+1
A ← |A - B| B ← A A ← A/2 B ← B/2
1 0 11 0 0 0 11
2 0 11 0 0 0 11
3 0 11 0 0 0 11
... 0 11 0 0 0 11
iLast 0 11 0 0 0 11
GCD 11

It should be clear at this point that once A has become equal to 0, and B is odd, further iterations have no effect.


Lastly, let's illustrate the "interesting", from the POV of the new algo, degenerate case: GCD(N, 0) where N > 0 :

GCD(3, 0) :

i Ai Bi AOdd and BOdd : AEven : BEven : Twos Ai+1 Bi+1
A ← |A - B| B ← A A ← A/2 B ← B/2
1 11 0 0 0 11 0
2 11 0 0 0 11 0
3 11 0 0 0 11 0
... 11 0 0 0 11 0
iLast 11 0 0 0 11 0
GCD 11

In this and only this case, the intermediate result will wind up in A rather than in B, given as the subtractive step demands an odd A and odd B, and this never happens in the (N, 0) case.

This is why we need step 14: A := Bitwise-OR(A, B).

Let's conclude with a second arbitrary example of the above :

GCD(0x80, 0x0) :

i Ai Bi AOdd and BOdd : AEven : BEven : Twos Ai+1 Bi+1
A ← |A - B| B ← A A ← A/2 B ← B/2
1 10000000 0 1000000 0 1 1000000 0
2 1000000 0 100000 0 2 100000 0
3 100000 0 10000 0 3 10000 0
4 10000 0 1000 0 4 1000 0
5 1000 0 100 0 5 100 0
6 100 0 10 0 6 10 0
7 10 0 1 0 7 1 0
8 1 0 0 7 1 0
... 1 0 0 7 1 0
iLast 1 0 0 7 1 0
GCD 10000000

At this point, there is not much else left to say about the algorithm per se.


And now, let's see the implementation of the new GCD:

fz_gcd.adb:

package body FZ_GCD is
 
   -- Find Greatest Common Divisor (GCD) of X and Y.
   -- Note that by convention, GCD(0, 0) = 0.
   procedure FZ_Greatest_Common_Divisor(X      : in  FZ;
                                        Y      : in  FZ;
                                        Result : out FZ) is
 
      -- Widths of X, Y, and Result are equal
      subtype Width is Word_Index range X'Range;
 
      -- Working buffers for GCD computation, initially equal to the inputs
      A      : FZ(Width) := X;
      B      : FZ(Width) := Y;
 
      -- Evenness (negation of lowest bit) of A and B respectively
      Ae, Be : WBool;
 
      -- Common power-of-2 factor: incremented when Ae and Be are both 1
      Twos   : Word := 0;
 
      -- This flag is set when A and B are BOTH ODD
      OO     : WBool;
 
      -- |A - B|
      D      : FZ(Width);
 
      -- This flag is set iff A < B
      A_lt_B : WBool;
 
   begin
 
      -- To converge, requires number of shots equal to (2 * FZ_Bitness) - 1:
      for i in 1 .. (2 * FZ_Bitness(X)) - 1 loop
 
         -- Whether A and B are currently BOTH ODD :
         OO := FZ_OddP(A) and FZ_OddP(B);
 
         -- D := |A - B|
         FZ_Sub_Abs(X => A, Y => B, Difference => D, Underflow => A_lt_B);
 
         -- IFF A,B both ODD, and A < B : B' := A ; otherwise no change :
         FZ_Mux(X => B, Y => A, Result => B, Sel => OO and A_lt_B);
 
         -- IFF A,B both ODD: A' := |A - B| ; otherwise no change :
         FZ_Mux(X => A, Y => D, Result => A, Sel => OO);
 
         -- If A is now EVEN: A := A >> 1; otherwise no change
         Ae := 1 - FZ_OddP(A);
         FZ_ShiftRight(A, A, WBit_Index(Ae));
 
         -- If B is now EVEN: B := B >> 1; otherwise no change
         Be := 1 - FZ_OddP(B);
         FZ_ShiftRight(B, B, WBit_Index(Be));
 
         -- If both A and B were even, increment the common power-of-two
         Twos := Twos + (Ae and Be);
 
      end loop;
 
      -- Normally, B will contain the GCD, but in the (N,0) N > 0 case -- A.
      -- The other variable will always equal 0. Hence, take Bitwise-OR(A,B):
      FZ_Or(X => A, Y => B, Result => A);
 
      -- Reintroduce the common power-of-2 factor stored in 'Twos'
      FZ_Quiet_ShiftLeft(N => A, ShiftedN => A, Count => Indices(Twos));
 
      -- Output final result -- the GCD.
      Result := A;
 
   end FZ_Greatest_Common_Divisor;
 
end FZ_GCD;


It is very slightly more expensive than the Ch.15 routine: by one MUX (in the loop) and one FZ_Or (outside of the loop.) But this is not a tragedy. Overall it comes out to cost just about the same, after taking into account the reduced (by one) number of iterations.


Unsurprisingly, this corrected variant of GCD passes the Ch.15 test battery; properly swallows both of the Ch.15 counter-examples given earlier; and, of course, the...

Ch. 21A-Bis GCD "Worst Case" Tape for 256-bit FZ :

  .8000000000000000000000000000000000000000000000000000000000000000
  .FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
  G
  #

... correctly produces the output 1, converging -- as predicted -- in the 511th and final iteration.

To generate this test for any FZ Width, all you need is:

Ch. 21A-Bis GCD "Worst Case" Tape for arbitrary FZ Width :

  .1 .0~W.1- LS
  .0~
  G
  #


~ The next Chapter, 21B, will continue the Extended-GCD sequence of Chapter 21A. ~

"The Advantages of a Dragon."

Lately, I found myself unable to resist the temptation to translate this very pertinent classic of science fiction to English. If you, reader, know of a better translation, do not hesitate to write in. Meanwhile, here goes:


"The Star Diaries of Ijon Tichy: The Advantages of a Dragon."
Stanislaw Lem (1921-2006).


Until now, I've said nothing about my journey to the planet Abrasia, in the Cetus constellation. The civilization there had turned a dragon into the basis of its economy. Not being an economist myself, I, sadly, was not able to make sense of this, even though the Abrasians were more than willing to explain themselves. Perhaps someone well-versed in the particulars of dragons will understand the subject a little better.

The Arecibo radio telescope had been picking up indecipherable signals for quite some time. Jr. Prof. Katzenfenger was the only one able to make headway. He puzzled over the enigma while suffering from a terrible case of the sniffles. His stuffed and dripping nose, ever interfering with his scholarly labours, at a certain point led him to a thought: that the inhabitants of the uncharted planet, unlike us, might be creatures who rely on smell rather than sight.

And indeed their code turned out to consist not of alphabetic letters, but of symbols for various smells. But, truth be told, there were some perplexing passages in Katzenfenger's translation. According to this text, Abrasia is populated not only by intelligent beings, but also by a creature larger than a mountain, uncommonly ravenous and taciturn. The scientists, however, were less surprised by this curio of interstellar zoology, than by the fact that it was specifically the creature's insatiable hunger that brought great returns to the local civilization. It aroused horror, and the more horrible it became, the more they profited from it. I have long had a weakness for all kinds of mysteries, and when I heard about this one, I made up my mind to set out for Abrasia straight away.

Upon arriving, I learned that the Abrasians are entirely humanoid. Except that, where we have ears, they have noses, and vice-versa. Like us, they had descended from apes; but while our apes were either narrow- or wide-nosed, their simian ancestors had either a single nose or two. The one-nosed had gone extinct from famine. A great many moons orbit their planet, causing frequent and lengthy eclipses. At those times, it becomes pitch-dark. Creatures who sought food with the aid of sight could turn up nothing. Relying on smell worked better, but it worked best of all for those who had two widely-spaced noses, and used their sense of smell stereoscopically, just as we make use of our paired eyes and stereophonic hearing.

Later on, the Abrasians had invented artificial lighting, and, even though twin-nosedness had ceased to be essential to their survival, the anatomical quirk inherited from their ancestors was here to stay. In the colder times of the year, they wear hats with ear flaps, or, rather, nose flaps, so as not to freeze their noses off. Of course, I may be mistaken. It seemed to me that they were not exactly thrilled with these noses of theirs -- reminders of a troublesome past. Their fairer sex hides their noses beneath various decorations, often as large as a dinner plate. But I did not pay much attention to this. Interstellar travel has taught me that anatomical differences tend to be of little significance. The real problems hide far deeper. On Abrasia, that problem turned out to be the local dragon.

On that planet, there is only one very large continent, and on it -- something like eighty countries. The continent is surrounded by ocean on all sides. The dragon is located in the far north. Three principalities directly border him -- Claustria, Lelipia and Laulalia. After studying satellite photos of the dragon, as well as 1:1000000 scale models of him, I came to the conclusion that he is a quite unpleasant creature. I must say though that he was not the least bit similar to the dragons we know from Earth's stories and legends. Their dragon doesn't have seven heads; he has no head at all, and, it would also appear, no brain. And as for wings, he also hasn't any, and so flight is out of the question. The matter of legs is less clear, but it would appear that the dragon has no limbs of any sort. What he resembles most is an enormous mountain range, copiously slathered with something rather like jelly. The fact that you are beholding a living thing only becomes apparent if you are very patient. He moves uncommonly slowly, as a worm does, and quite often violates the borders of Claustria and Lelipia. This creature devours something like eighteen thousand tonnes of foodstuffs every day. The dragon is fond of grains, porridges made from same, and cereals in general. But he is not a vegetarian. Food is delivered to him by countries which consist in the Union of Economic Cooperation. The bulk of these provisions are carried by rail to special unloading stations, soups and syrups are pumped into the dragon through pipelines, and in the wintertime, when a lack of vitamins is perceived, they airdrop these from specially-equipped cargo planes. And at no point does anyone need to look for a mouth -- the beast is able to grab a meal with any and all parts of its enormous carcass.

When I arrived in Claustria, my first impulse was to ask why they go to such great lengths to feed this monster, instead of letting it perish from hunger. But straight away I learned that I had landed in the midst of a scandal, an "attempted dragon assassination", and promptly shut my mouth. Some Lelipian, dreaming of winning the laurels of a savior, had founded a secret paramilitary organization, with the aim of slaying the insatiable giant. To do this, he proposed to poison the vitamin supplements with a substance which causes unbearable thirst, -- so that the beast would take to drinking from the ocean, until it bursts. This reminded me of a well-known Earth legend about a brave hero who defeated a dragon (whose diet consisted chiefly of fair maidens) by throwing him a sheepskin stuffed with sulfur. But this is where the resemblance between the Earth legend and the Abrasian reality ended.

The local dragon was under the full protection of international law. Not only that: the treaty concerning cooperation with the dragon, signed by the forty-nine signatory governments, guaranteed him a steady supply of tasty foodstuffs. The computerized translator, with which I never part on my voyages, allowed me to make a detailed study of their press. The news of the failed assassination had thoroughly dismayed the public.

It demanded severe and exemplary punishment for the failed assassins. This surprised me, because the dragon per se didn't seem to evoke much in the way of sympathy from anyone. Neither the journalists nor the authors of letters to the editor made any secret of the fact that the subject of the conversation is a creature repulsive in the extreme. And so, in the beginning, I had come to think that he, to them, were something like an evil god, a punishment from the heavens, and, as for the sacrifices, they, following some peculiar local custom, spoke of them as "export." You can speak ill of the devil, but you cannot disregard him entirely. At the same time, the devil can tempt people; when you sell him your soul, you can count on a great many earthly pleasures in exchange. The dragon, however, near as I could tell, had made no promises to anyone, and there was absolutely nothing tempting about him. From time to time, he would strain mightily and flood the bordering regions with the byproducts of his digestion, and in ill weather one could feel the stench from forty-odd kilometers away. At the same time, the Abrasians held that their dragon is to be cared for, and that the stink is evidence of indigestion; it means that they must take care to give him medicines which limber up the metabolism. As for the attempt on his life, they said, if, God forbid, it had succeeded, the result would be an unprecedented catastrophe.

I read everything in the newspapers, but none of it shed any light on the question of exactly what kind of catastrophe they had in mind. Exasperated, I took to visiting the local libraries, leafed through encyclopaedias, histories of Abrasia, and even visited the Society of Friendship with the Dragon; but even there, I learned nothing. Except for a few members of the staff, not a soul was there. They offered me a membership if I'd only pony up a year's worth of dues, but this wasn't what I had come for.

The states which bordered the dragon were liberal democracies; there, you were allowed to speak your mind, and after a lengthy search, I was able to find publications which condemned the dragon. But even their authors still held that when dealing with him, one ought to make reasonable compromises. The use of guile or force could have grave consequences. Meanwhile, the would-be poisoners cooled their heels in the local jail. They did not plead guilty, despite confessing their intention to kill the dragon. The government press called them irresponsible terrorists, the opposition press -- noble fanatics, not quite in their right mind. And one Claustrian illustrated magazine suggested that they might be provocateurs. Behind them, it said, stands the government of a neighbouring country: thinking that the quota on dragon exports established for it by the Union of Economic Cooperation was too stingy, it hoped, via this subterfuge, to get it reconsidered.

I asked the reporter who came to interview me about the dragon. Why, instead of being given a chance to finally put an end to him, were the assassins tossed in the clink? The journalist answered that it would have been a despicable murder. The dragon, by his nature, is kindly, but the severe conditions of life in the polar regions prevent him from expressing his innate kind-heartedness. If you had to go hungry constantly, you too would become ill-tempered, even if you are not a dragon. We must carry on feeding him, and then he will stop creeping southward and become kindlier.

- Why are you so sure of this? I asked. - I've been collecting clippings from your newspapers. Here's a few headlines: "Regions of northern Lelipia and Claustria are getting depopulated. The torrent of refugees continues." Or this: "The dragon has once more swallowed a group of tourists. For how much longer will irresponsible travel agencies peddle such dangerous tours?" Or here's another: "In the past year, the dragon has expanded his footprint by 900000 hectares." What do you say to this?

- That it only confirms what I was saying. We are still underfeeding him! With tourists, yes, there's been some incidents, and quite tragic ones, but one really oughtn't irritate the dragon. He really can't stand tourists, especially the photographing kind. He's allergic to photo flashes. What would you have him do? Remember, he lives in total darkness three-quarters of the year... And I'll say, just the production of high-calorie dragon fodder gives us 14600 employment positions. Yes, some handful of tourists perished, but how many more people would perish of hunger, if they were to lose their jobs?

- Just a minute, just a minute, - I interrupted him. - You bring the dragon foodstuffs, and this surely costs money. Who pays for it?
- Our parliaments pass laws which bestow export credits...
- So, it is your taxpayers who pay for the dragon's upkeep ?
- In some sense, yes, but these outlays bring returns.
- Wouldn't it be more profitable to put an end to the dragon?
- What you are saying is monstrous. In the last thirty years, over forty billion have been invested in industries connected with dragon-feeding...
- Maybe it would be better to spend these sums on yourselves?
- You are repeating the arguments of our most reactionary conservatives! the reporter exclaimed with irritation. - They are inciting murder! They want to turn the dragon into tinned meat! Life is sacred. No one ought to be killed.

Seeing that our conversation was leading nowhere, I parted ways with the journalist. After a bit of thinking, I went off to the Archive of Print and Ancient Documents, so that, after digging through dusty newsprint clippings, I could find out just where this dragon had come from. It took a great deal of effort, but I was able to discover something quite intriguing.

Half a century ago, when the dragon took up a mere two million hectares, no one had taken him seriously. I ran across many articles which proposed to uproot the dragon from the ground, or to flood him with water through specially built canals, so that he might freeze over in wintertime; but the economists explained that this operation would be quite expensive. But when the dragon, who in those days was still subsisting solely on lichens and mosses, doubled in size, and the inhabitants of neighbouring regions began to complain of the unbearable stench (especially in the spring and summer, when the warm breezes start to blow), charitable organizations offered to sprinkle the dragon with perfume; and when this didn't help, they took up collections of baked goods for him. At first, their project was laughed at, but with time it really took off. In newspaper clippings from later times, there was no longer any talk of liquidating the dragon, but instead more and more talk of the profits that are to be gained from bringing him aid. And so, I was indeed able to learn some things, but I decided that this was not enough, and set off to the university, to visit the Department of General and Applied Draconistics. Its dean received me quite courteously.

- Your questions are anachronistic to the utmost degree, - he answered with a condescending smile after hearing me out. - The dragon is a part of our objective reality, an inseparable, and, in a certain sense, central part, and therefore it must be studied as an international problem of the greatest importance.
- Can you be more specific? - I asked. - Where did he come from in the first place, this dragon?
- Oh, who knows, - the draconologist answered phlegmatically. - Archaeology, predraconistics, and the genetics of dragons are not in my circle of interests. I do not study draconogenesis. While he was still small, he did not present a serious problem. That is a general rule, esteemed foreigner.
- I was told that he descended from mutant snails.
- I doubt it. At the same time, it isn't important just where he came from, given that he already exists, and not merely exists! If he were to disappear, it would be a catastrophe. And we would not likely recover from it.
- Really? Why is that?
- Automation led us to unemployment. Including among the scientific intelligentsia.
- And what, the dragon helped?
- Of course. We had enormous surpluses of foodstuffs, mountains of pasta, lakes of vegetable oil, and the overproduction of baked goods was a genuine calamity. Now we export these surpluses up north, and, remember, they also have to be refined. He won't scarf up just anything.
- The dragon?
- Well yes. To develop an optimal programme for his nourishment, we had to create a system of scientific research centres, such as the Chief Institute of Dragon-husbandry and the Higher School of Dragon Hygiene; in each university, there is at least one draconistics department. Special enterprises produce new types of fodder and nutritional supplements. The propaganda ministry created special information networks, so as to explain to society just how profitable trade with the dragon can be.
- Trade? So he sends you something? I can hardly believe this!
- He sends, of course. Chief of all, the so-called dracoline. It's a secretion of his.
- That shiny slime? I saw it in the photos. What's it good for?
- When it congeals - for plasticine, for children in kindergartens. But of course there are a few problems. It is hard to get rid of the smell.
- It stinks?
- In the usual sense - very much. To get the smell out, they add special deodorants. For the time being, dragon plasticine costs eight times more than the ordinary kind.
- Professor, what do you think of the attempt on the dragon's life? The scientist scratched his ear, which hung above his lips.
- If it had succeeded, then, first of all, we would have an epidemic on our hands. Just try and imagine the vapours that would emanate from such an enormous cadaver? And, second, the banks would go broke. The total destruction of our monetary system. To make a long story short, catastrophe, esteemed foreigner. A terrible catastrophe.
- But his presence makes itself known, doesn't it? To tell the truth, it's extremely unpleasant, isn't it?
- What do you mean, unpleasant? - he said with a profound philosophical calm. The post-draconic crisis would be far more unpleasant still! Remember, please, that we not only feed him, but conduct extra-nutritional work with him. We try to soften his temper, keep it within certain boundaries. This -- is our program of so-called domestication, or appeasement. Lately he is being given large quantities of sweets. He likes sweets.
- Somehow I doubt that his temperament will get sweeter from this, - I blurted out.
- But at the same time, the export of baked goods has quadrupled. And you mustn't forget about the work of the CMDR.
- What's that?
- Committee for the Mitigation of Draconic Repercussions. It provides employment for many university and college graduates. The dragon has to be studied, investigated, and, from time to time - healed; previously we had a surplus of medics, but now every young doctor is assured of finding work.
- Well then, I said without much conviction. - But all of this is exported philanthropy. Why don't you start doing philanthropy right here, among yourselves?
- How do you mean?
- Well... you spend mountains of money on that dragon!
- So, what - should we be handing it out to citizens just like that? This runs against the very basics of any school of economics! You, I see, are a total ignoramus in economics. Credits, which back draconic export, warm up the economy. Thanks to them, the exchange of goods and services grows...
- But the dragon grows too, - I interrupted him. - The more you feed him, the bigger he gets, and the bigger he gets, the bigger is his appetite. Where's the sense in this? Don't you know that in the end, he'll drive you into penury and eat you up?
- Nonsense! - the professor fumed. Banks add the credits to their portfolios!
- So, they're, what, bonds? And he'll repay them in what? In his plasticine?
- Don't take things so literally. If it weren't for the dragon, for whom would we then build the pipelines through which we pump flour extract? Don't you see, that's iron-works, pipe factories, welding robots, networks of transport, and so forth. The dragon has real needs. See, now you understand? Production has to work for somebody! Industrialists would not produce anything, if the finished product had to be thrown into the sea. A real consumer, on the other hand, that's something entirely different. The dragon -- is a gigantic, amazingly capacious foreign market, with a colossal demand pressure...
- I don't doubt it, - I noted, seeing that this chat is leading nowhere.
- And so, have I convinced you?
- No.
- This is because you hail from a civilization that is so utterly different from our own. At any rate, the dragon has long ago stopped being a mere importer of our production.
- So what has he turned into?
- An idea. A historic necessity. Our state interest. The mightiest factor which justifies our united efforts. Try to look at this business through exactly that lens, and you will see what fundamental problems can be discovered in what is, to be fair, a quite revolting creature, if it grows to a planetary scale.

September 1983

P.S. They say that the dragon has broken up into a multitude of little ones, but their appetite is anything but weaker.